| Main page Upper page
MSU DSP Course |
Домашнее задание 2:
вопросы и ответы
Общие
Форматы файлов WAV и BMP
Фильтрация
Палитризация
Псевдотонирование
Интерполяция
FFT
Стереопанорама
Спектр
- А какой у Юрия Матвеевича e-mail?
ymb@graphicon.ru
- У меня 2 отдельных программы, как оформлять
архив? (сколько должно быть файлов readme и как
называть папки?) Нужно ли в readme файле указывать
выполненные/невыполненные подпункты задания?
Оформить
можно как угодно, только чтобы понятно было. А
выполненные пункты надо указать.
- Нужна ли в программе проверка на ошибки:
например, если bmp-файл испорчен или это вообще не
bmp-файл, или если пользователь вводит
недопустимые значения?
В этом задании не
обязательно. При проверке будут использоваться
только нормальные входные данные.
- Можно ли использовать другие языки? (т. е. не
VC++) Будут ли за это сниматься баллы?
Можно.
Баллы сниматься не будут.
- Что делать, если нет звуковой карты?
Звуковая карта не обязательно нужна для
второго задания. Без нее просто невозможно будет
прослушать результаты. А при построении спектра
вообще прослушивать ничего не требуется. Для
выполнения задания нужны только WAV-файлы. Если у
кого-то нет - могу прислать по почте (200 - 300 Кб).
- Где можно прочитать про методы обработки
изображений, указанные в форулировке задания?
Где можно найти конкретные формулы и алгоритмы, а
не общие идеи? Нет ли каких других общеизвестных
названий приведенных методов? Поиск по названиям
методов ничего существенного не дает.
В презентации лекции, а более подробно - легче
всего найти в Интернет. Рассказанного на лекции
должно быть достаточно. Вращение картинки и
звуковые задания будут на следующей лекции. Но
если хочется подробнее, то можно поискать в
Интернет. Кое-что есть на нашем сервере: http://graphics.cs.msu.ru в курсах
прошлых лет. А остальное можно искать в Google: K-Means
Clustering, Error Diffusion Halftoning, Bilinear Interpolation, Unsharp Mask.
- Что означают отрицательные значения
сигнала (сэмплов) для звуковых файлов?
В
звуковой волне вообще отрицательных значений
примерно столько же, сколько и положительных.
Ноль - это некое среднее значение, тишина. А при
колебании происходит отклонение от нуля в обе
стороны: в плюс и в минус.
- А оценка не будет снижена, если ограничить
размер изображения 1024x1024? Для хранения картинки
используетя CBitmap, а он почему-то не хочет хранить
большие картинки.
Нет, не будет. Но это не
очень хорошо.
- Можно ли для загрузки и сохранения bmp-файлов
пользоваться готовыми функциями из MSDN или
учебников по C++?
Да, можно. Но нужно знать
устройство bmp-файла.
- Как в стерео WAV-файле расположены
относительно друг друга сэмплы левого и правого
каналов?
Они чередуются по одному: левый1,
правый1, левый2, правый2, ...
- Чтобы применить сведение изображения к
монохромному, мне надо воспользоваться формулой
Mono = 0.3red + 0.59green + 0.11blue, но как я могу вынуть все эти
компоненты из .bmp файла? Я имею в виду, что
может быть есть какая-то структура, в которой все
эти значения
хранятся?В непалитровых ("RGB")
BMP-файлах для каждого пикселя хранятся его
цветовые компоненты: B, G, R: всего 3 байта на пиксел
(это основные данные, BitmapData). Структура BMP-файла
есть здесь.
Нет, в этом задании достаточно сделать
поддержку формата 44100 Гц, 16 бит, стерео.
- При Гауссовом размытии абсолютно белого
листа я заметил, что он темнеет (с 255 до 254). Это
нормально или нет?
Такого быть не должно.
Во-первых - нужно проверить, что сумма
коэффициентов фильтра равна единице. Во-вторых -
что преобразование чисел с плавающей точкой в
целочисленные цвета делается округлением, а не
усечением. В-третьих - проверить сам алгоритм
фильтрации.
- При применении некоторых фильтров
(например, увеличение чёткости или нахождение
границ) цветные картинки резко меняют цвета или
вообще вырождаются в набор цветных точек так, что
не улавливается исходная картинка. Это
правильно? Фильтрую я отдельно каждую из
компонент цвета.
При нахождении границ это
допустимо (хотя контуры исходной картинки должны
быть ясно видны). При увеличении четкости такого
быть не должно. Примеры нахождения границ и
увеличения четкости можно посмотреть в Adobe Photoshop.
- Можно ли сначала в отфильтрованном
изображении получить те цвета, что нужны по
алгоритму, а затем, если есть превышение по
яркости, найти максимум и умножить все яркости на
такой коэффициент, что яркость в точке максимума
станет равной 255? Что это даст? Могу ли я так
избежать некоторых артефактов в общем случае?
Нет,
обычно это нежелательно, т.к. может привести к
заметному сдвигу общей яркости или уменьшению
контрастности изображения. Стандартный способ -
усечение только "превышающих" пикселей.
- Какой параметр сигма лучше использовать
для тестирования Гауссова размытия и какие
следует ожидать результаты? Вообще что должно
произойти?
Должно произойти размытие
картинки. От параметра сигма зависит степень
размытия: слабое или сильное. Размер фильтра тоже
нужно брать пропорциональным сигме, чтобы горб
гауссиана более-менее уместился в квадрате
фильтра. Желательно сделать размер фильтра (и
сигму) настраиваемыми.
- При сигма = 1 изображение смещается на 1
пиксель по вертикали и горизонтали - это
правильно или в моём алгоритме ошибка?
Смещаться
изображение не должно. Большинство фильтров
квадратные, и в них центральная точка
соответствует "исходному" пикселю. Т.е. при
свертке каждый пиксель размывается в квадрат,
симметричный относительно исходного пикселя. В
формуле гауссиана Ker[k,p]=(1/Sum)*exp((k*k+p*p)/(-2*б*б))
индексация матрицы ядра идёт от -n до n (где n -
размер ядра). Таким образом, центральный
("исходный") элемент имеет индекс [0,0].
- Что понимается под "Устранение краевых
эффектов при фильтрации"?
В операции
свертки в формировании граничных пикселей
формально могут участвовать "заграничные"
пиксели, т.е. те, которых нет в изображении.
Например, если свертка такова, что Dest[i] = Src[i-2] +
Src[i-1] + Src[i] + Src[i+1] + Src[i+2], то для формирования
пиксела [0] нужны пикселы [-2] и [-1]. Если вместо них
положить нули, то по краям отфильтрованной
картинки может появиться "рамка". Задача в
том, чтобы этого избежать. Для этого есть
несколько способов. Например - положить
"заграничные" пиксели равными ближайшим
"существующим" пикселям. Или не
обрабатывать их совсем.
- Что такое радиус фильтра при Гауссовом
размытии, то есть в каком формате он задается и
как но нему определить размеры ядра свертки k и p?
Нужно ли делать параметр сигма настраиваемым или
его нужно вычислять в зависимости от других
параметров (в какой зависимости)?
Радиус фильтра - это сигма в знаменателе
формулы. Он задает, насколько широкий будет
гауссиан. Размеры ядра свертки делаются
пропорциональными сигме, так, чтобы в это ядро
свертки уместился основной горб гауссиана,
вплоть до затухания порядка 0.1 - 0.3 от
максимального значения. k и p - это не параметры
фильтра, а индексы при адресации его элементов. Нужно сделать настраиваемую сигма и
вычислять размер ядра фильтра пропорцианально
ей (следя, чтобы размер был нечетным).
- Каковы пределы изменения параметра силы
эффекта при применении фильтра unsharp mask?
От "нет эффекта" до "сильно выраженный
эффект". Попробуйте сами исследовать,
какие значения параметра соответствуют этим
определениям.
- Что имеется ввиду под "Адаптация к
количеству шума, регулируемый порог": параметр
threshold? Если да, то как он влияет на параметр силы
эффекта и на фильтр вообще?
В слайдах лекции написано, какую разность
надо анализировать и сравнивать с порогом. Если
она ниже порога, то в этом месте нужно ослабить
(или совсем не применять) эффект Unsharp Mask, т.к.
считается, что в этом месте шум. Если она выше
порога, то в этом месте можно применять эффект
Unsharp Mask с полной силой (которая задана
пользователем), т.к. считается, что в этом месте не
шум, а полезная информация.
- У меня возникла проблема с фильтром unsharp mask.
При вычислениях (сила эффекта 2 (или больше), порог
255) появляется двойственность изображения. Мне
кажется, что это как-то связано с ядром фильтра
размытия. По какой формуле считать коэффициенты
ядра?
Проверьте, чтобы после применения размытия
картинка не сдвигалась. Скорее всего, у вас она
сдвигается, и из-за этого при вычитании
получается двойной контур. Чтобы картинка не
сдвигалась, нужно чтобы при свертке ядро было
симметрично относительно индекса [0, 0], т.е. каждый
пиксель результирующего изображения
формировался из своей симметричной окрестности.
Коэффициенты ядра размытия считаются по формуле
Гауссиана, приведенной на лекции. Как легко
заметить, Гауссиан - симметричное ядро.
- Что в формуле Гаусса является радиусом
фильтра и что является силой
эффекта?
Сигма называется радиусом фильтра, она же
задает силу размытия. Размер матрицы фильтра
выбирается в зависимости от сигмы.
- Как анализировать разность X - GX для
адаптации к кол-ву шума? Для всех компонент сразу,
т.е. брать сумму модулей разности каждого из
цветов R, G, B(например) или расчитывать её для
каждой компоненты цвета независимо? Каким должен
быть диапазон изменения порога?
Лучше брать для всех компонент сразу, чтобы
сила эффекта была одинаковой во всех трех
компонентах. Диапазон изменения порога лучше
сделать пошире.
- В задании упоминается построение палитры
методом К-средних,
и всвязи с этим вопрос такой: как выбирать
начальную палитру?Начальную палитру можно
выбрать произвольно. Например - взять N
различных цветов из исходного изображения.
- Как брать начальное приближение в методе
К-средних? Дело в том, что, если случайным образом
выбрать из 255^3 К цветов, то при маленьких К цвета
палитры не похожи на цвета изображения. А если
брать случайным образом из изображения, то
некоторые мелкие детали изображения могут быть
потеряны. Например, белый цветок на черном фоне
может превратиться в черный квадрат.
Начальное
приближение трудно подобрать так, чтобы палитра
сразу получилась "хорошей" (один из методов -
провести маленький процесс K-средних для
небольшой случайной выборки пикселей
изображения). Для этого и существуют последующие
итерации K-средних. Попробуйте и так, и так. После
нескольких итераций палитра должна значительно
улучшиться.
- Чем отличается метод К средних
посторения палитры от метода кластеризации К
средних?
Это одно и то же. Цвета палитры
получаются методом кластеризации К-средних,
примененном ко всем цветам пикселей изображения.
- Построение палитры выполняется достаточно
долго. Нужно ли делать Progress Bar? И, если нужно, то,
как узнать, когда последовательность цветов
сойдется и построение завершиться?
Progress Bar -
это элемент хорошего интерфейса, а за хороший
интерфейс можно получить дополнительный балл.
Достаточно сделать некоторое фиксированное
число итераций, которое подходит для большинства
изображений.
- Распределение ошибки осуществляется
только на тех 4-х соседей, которые указаны в
лекции или вообще на всех? (если да, то с какими
коэфициентами)?
По методу
Флойда-Штейнберга - только на тех, которые
указаны в лекции. На остальных распространить и
не удастся: они уже "пройдены".
- В методе Floyd-Steinberg функция quantize(Src[i][j]) - это то
же самое, что truncate(Src[i][j]), или она выполняет ещё
какие-то действия?
Это то же самое. Просто
округление к ближайшему из цветов палитры.
- В методе Floyd-Steinberg коэффициенты при e должны
быть именно такие, как указаны в слайдах, или они
зависят от картинки? (А то у меня Ваша бывшая
девушка после обработки фильтром получается не
такая, как в слайдах, или, может, это из-за того,
что я прохожу массив не сверху вниз, а снизу вверх
(хотя, это, пожалуй, вряд ли)).
Вообще-то,
должно получиться очень похоже. Если нет - это,
скорее всего, ошибка в алгоритме. Коэффициенты не
зависят от входного изображения. В зависимости
от направления обхода, может поменяться
распределение черных и белых точек, но визуально
картинка останется практически такой же.
- Есть проблемы с палитризации изображения
при использовании метода диффузии ошибки и
построении палитры методом К-средних. Например,
берём градиентно залитый прямоугольник от
чёрного до белого и строим палитру из 2 цветов по
методу К-средних. Получается что-то около $404040 и
$C0C0C0. Так вот чёрный и белый цвета при таком
раскладе вообще отсутствуют, а при
псевдотонировании возникают огромные ошибки
(полквадрата вообще цвета $404040). Нужно ли
что-нибудь делать в таких случаях? (видоизменять
метод или оставить как есть)Предлагаю
ограничить максимальный модуль ошибки
квантования, чтобы она не накапливалась.
Например, величиной в районе 200.
Поэкспериментируйте.
- Метод К-средних построения цветной палитры
работает долго, так как надо делать расчёт для
каждого цвета пиксела. Можно/нужно ли делать
какие-нибудь ограничения на время работы метода?
(по кол-ву итераций, времени, Eps)
Желательно сделать выбираемое количество
итераций. Или просто выбрать какое-то
фиксированное небольшое число итераций, которое
дает хороший результат для большинства картинок.
Можно попробовать пойти на ухищрения, например -
производить построение палитры не по всем
пикселям изображения, а только по каждому
четвертому, например (это ускорит метод в 4 раза).
Если для всего этого сделать отключаемые опции,
то можно заработать доп. баллы.
- Что делать, если пользователь задаёт больше
цветов в палитре, чем есть в картинке?
Хорошо бы отследить такой случай, и корректно
сделать палитру из меньшего числа цветов. Но
баллы в случае некорректной обработки данной
ситуации снижаться не будут.
- Куда "распространять" ошибку при
применении метода Флойда-Стейнберга, если
обрабатывается самый нижний или самый правый ряд
пикселей?
Эту ошибку можно никуда не распространять.
- При повороте картинки, те углы, которые
выходят за рамку изображения, не видны. Нужно ли
менять размеры картинки и размещать повернутое
изображение целиком?
Это не обязательно.
- Никак не могу разобраться с
преобразованием Фурье. На входе у нас дискретный
сигнал - N комплексных чисел (где действ. часть это
одна из компонент цвета, мнимая - 0), на
выходе N+2 числа А[k], 0<=k<=N/2 и B[k] 0<=k<=N/2. И
причем B[0], B[N/2] = 0, поэтому остается N. Функция FFT из
файла FFT.C как раз и возвращает нам N чисел?
Вопросы: верно ли все вышесказанное? Верно ли, что
возвращаются как раз A[k] и B[k]? Если да то в
каком порядке? Хотя в пособии написано, что
"первые N/2+1 коэффициентов совпадут со спектром
действительного ДФП" - что это значит?
Функция
FFT фозвращает N комплексных чисел X[k]. В них
X[k].Re = A[k], X[k].Im = B[k], k = 0,..., N/2.
- Нас интересуют только амплитуды поэтому мы
преобразуем А[k] и B[k] к С[k], вводя фазу. Вопросы:
амплитуда это комплексное число? С[k] = sqrt
(sqr(A[k] + sqr(B[k])) или нас интересует только ее модуль
и указанное равенство верно для модулей?
Амплитуда
- это действительное неотрицательное число.
A[k] и B[k] - это тоже действительные числа. С[k] =
sqrt (sqr(A[k] + sqr(B[k])) - это и есть определение
амплитуды.
- Вопрос по FFT. В FAQ приводится вопрос для
картинки и там
говорится, что мы передаём N комплексных чисел,
где RE - компонента
цвета, а IM = 0. В случае со звуковым файлом мы имеем
значения для
левого и правого канала. Так вот, как их
передавать и как строить
результат? Отдельно для правого и левого или
усреднять или только для
одного?
Об этом будет рассказано на лекции во вторник.
Если вкратце, то спектр звука - одномерный график,
а спектр изображения - двумерный. Звуковая волна
записывается в Re, обнуляется Im и производится FFT.
(Обычно FFT берут после применения весового окна).
После этого от полученного одномерного вектора
коэффициентов вычисляются амплитуды (т.е. модули
комплексных чисел). Они и отображаются в виде
зависимости от частоты (т.е. от номера
коэффициента).
- При компиляции файла FFT.C комилятор выдает
ошибку: M_PI undeclared
identifier (где-то в районе 70 строки). Что такое M_PI?
M_PI - это число Пи. Определите его
самостоятельно:
#define M_PI (3.1415926535897932384626433832795)
- Не могли бы Вы выложить или отправить или
показать где взять или рассказать как сделать
файлы для тестирования? Из того, что удалось
достать - либо все файлы моно, либо содержат
заголовки LIST или INFO, которые моя программа читать
не умеет.
Если есть CoolEdit - то можно
пересохранить там WAV-файлы, сняв галку "Save
additional information" в окне сохранения.
Вот пара готовых примеров WAV-файлов: letemps.wav
(1.2 Mb); roxette.wav (0.6 Mb). Оба файла для
уменьшения размера имеют частоту дискретизации
22 кГц.
На некоторых файлах эффект караоке
роботает отлично, на других на выходеочень много
шума, голос не всегда отфильтровывается. Файл
считывается без ошибок, это подтверждается тем,
что тождественное преобразование работае
правильно всегда. Вопрос такой: как можно
понизить уровень помех, и будет ли засчитан
элемент задания, если он прорамма будет давать
хороший результат не на всех файлах?
Эффект караоке, действительно, работает
не для всех файлов. Т.к. это просто вычитание двух
каналов, то он хорошо сработает, когда голос
расположен в центре стереопанорамы (т.е. поровну
в левом и правом каналах). Если же это не так, то
голос не удалится.
Это можно сделать как угодно. Можно
считать, что памяти достаточно.
Проверьте, чтобы значения отсчетов,
выходящих за диапазон -32768...+32767, были правильно
округлены к максимальным или минимальным
значениям.
Нет.
- Является ли логарифмическим масштабом
частот то, что строится в CoolEdit при отключении
"Linear view"? Т.е. равным промежуткам на графике
соответствуют интервалы частот, увеличивающиеся
в 2 раза на каждый интервал?
Да, именно так.
- Что такое весовое окно Ханна, или хотя бы
где об этом можно почитать?
Весовое окно Ханна - это колоколообразная
весовая функция вида sin(x)^2. Про весовые окна можно
прочитать в методичке по DSP, доступной в разделе
"Библиотека" нашего сайта
- Что понимается под сеткой частот и амплитуд?
Сетка частот и амплитуд - это разметка осей
графика значениями частоты и амплитуды, а также
прямоугольная сетка под графиком. Пример можно
посмотреть в редакторе CoolEdit или в слайдах лекции
по DSP.
|
