Введение в компьютерную графику
Полугодовой курс ВМиК МГУ, 2002

Задание №2. Цифровая обработка сигналов.

Начало: 28 февраля
Конец: 13 марта

Для выполняющих дополнительные пункты, связанные с фильтрацией или звуком, срок сдачи продлен до 21 марта

Автор задания:
Алексей Лукин

Цель задания

Освоить на практике важнейшие понятия и методы цифровой обработки сигналов применительно к изображениям: дискретизацию, фильтрацию, ДПФ.

Описание задания

Введение

Теория цифровой обработки сигналов предлагает мощные средства для работы с изображениями, звуком и другими данными, представленными в виде сигналов, т.е. дискретных выборок непрерывных функций. В этом задании предлагается большой выбор алгоритмов для реализации. Многие из этих алгоритмов широко применяются в программах обработки изображений.

Обязательная часть

Предлагается реализовать простейший редактор BMP-файлов под Windows со следующими возможностями:

  1. Загрузка и сохранение BMP-файлов (достаточно ограничиться поддержкой 24-битного формата).

  2. Гауссово размытие изображения с регулируемым радиусом размытия.

  3. Нахождение краев изображения (достаточно реализовать один любой подходящий для этого фильтр).

  4. Сведение изображения к монохромному (из двух цветов: черного и белого) двумя способами: с использованием порога и с использованием псевдотонирования (достаточно реализовать один любой алгоритм псевдотонирования; подсказка: самый простой - это диттеринг белым шумом ;).

  5. Уменьшение и увеличение изображения в небольшое целое число раз (достаточно реализовать любой алгоритм; подсказка: самый простой - это метод ближайшего соседа).

Для выполнения обязательной части достаточно реализовать любые 4 требования из 5 перечисленных выше.

Дополнительная часть

Дополнительные задания приблизительно отсортированы по возрастающей сложности. Все из нижеперечисленного сделать нереально, но это и не требуется (т.к. существует нестрогий лимит на максимальную оценку). При выполнении заданий можно пользоваться стандартной процедурой вычисления комплексного БПФ (но не более того :).

  1. Дополнительный набор фильтров: тиснение ("embossing"), медианный "фильтр". Желательно - с регулируемыми настройками.

  2. Псевдотонирование изображений с помощью метода диффузии ошибки. Исследование достоинств и недостатков данного метода по сравнению с другими.

  3. Вычисление и отображение спектра (только амплитуд) черно-белого изображения  в логарифмическом масштабе амплитуд (яркость точек пропорциональна логарифму амплитуды гармоник). Исследование спектров различных типов изображений.

  4. Выравнивание освещенности изображения методом гомоморфной обработки. Желательно так нормализовывать пересчет цветов и яркостей в алгоритме, чтобы результирующее изображение было действительно "лучше" исходного. Желательно иметь регулируемый радиус размытия при НЧ-фильтрации и  возможность выбора пропорции смешивания исходного и обработанного изображений.

  5. Конструирование одномерного фильтра с произвольной заданной частотной характеристикой. Желательно иметь возможность как-то задавать частотную характеристику, выбирать размер фильтра и тип взвешивающего окна. Желательно отображать полученный фильтр на экране или сохранять его в WAV-файл.

  6. Секционная БПФ-фильтрация (быстрая свертка) одномерного сигнала из WAV-файла с заданным (в другом WAV-файле) ядром свертки.

  7. Ресамплинг изображений в целое число раз с применением алгоритма интерполяции / фильтрации / прореживания. Сюда входит конструирование фильтра с требуемой для анти-алиасинга частотной характеристикой. Исследование эффекта Гиббса, анти-алиасинга, распечатка коэффициентов (желательно - в WAV-файл) и частотной характеристики фильтра.

  8. Произвольное задание с использованием конструирования и/или применения фильтров. Например - эквалайзер для звуковых WAV-файлов (для его реализации нужно прочитать WAV-файл, сконструировать фильтр по требуемой частотной характеристике, выполнить секционную свертку и сохранить результат в WAV-файле). Достаточно ограничиться поддержкой какого-нибудь одного формата звуковых файлов, например - WAV 44100 Hz, 16 bits, mono.

Источники информации

Очень рекомендуется методичка по цифровой обработке сигналов: "Введение в цифровую обработку сигналов (математические основы)", Алексей Лукин, 2002. В ней рассматриваются алгоритмы выполнения обязательных заданий № 2, 4, 5 и дополнительных заданий № 3, 4, 5, 6, 7, 8. Остальные алгоритмы были рассмотрены на лекциях.

При выполнении заданий рекомендуется пользоваться стандартной процедурой комплексного БПФ (прямое и обратное преобразования).

Также доступны документы по структуре WAV-файла (краткий и более развернутый).

Просматривать содержимое WAV-файлов и строить их спектрограммы можно с помощью звукового редактора Cool Edit Pro.

Загрузить несколько примеров WAV-файлов можно здесь:

Синусоида

Белый шум

Музыка1

Музыка2

Еще один источник информации - мой электронный адрес lukin@ixbt.com  В течение всего срока выполнения задания можно присылать мне письма с вопросами (особенно по методичке). Я постараюсь ответить на разумные вопросы в течение одного дня. Неразумные темы для вопросов - это программирование на C++ под Windows и алгоритмы, не затронутые в методичке.

Требования к программе

Обязательные требования

Обязательное требование - выполнить обязательную часть задания :).

Еще одно обязательное требование - разбираться в материале. В спорных ситуациях оценка выставляется после личной беседы, выявляющей понимание принципа действия основных алгоритмов.

Почти обязательное требование - это Windows-интерфейс программы.

Еще один важный пункт. К программе должны прилагаться все необходимые для ее запуска библиотеки (опускать можно только слишком большие библиотеки, если они явлются стандартными). Отсутствие библиотек создает неудобства при проверке, однако не фатально. У нас есть набор из наиболее часто недостающих библиотек для Borland C++ Builder и MS Visual C++.

Дополнительные требования

Очень приветствуется удобный интерфейс на правильном английском языке.

Для длинных (дольше 5 сек) преобразований желательно отображать индикатор прогресса.

Если в дополнительном задании имеется пункт "исследовать", то нужно представить краткий устный или письменный отчет о проделанной работе. В нем нужно указать, какие изображения были обработаны, какие результаты получены, какие закономерности выявлены. Например, при исследовании спектров различных изображений желательно указать какие-нибудь характерные особенности спектров для различных классов изображений, например - для фотографий, текста, текстур, однородного фона.

Оценка

Приведенные оценки приблизительны. Реально максимальная суммарная оценка ограничена примерно 15 баллами (хотя для выдающихся работ могут быть сделаны исключения).

Обязательная часть задания 4 - 6 баллов
Дополнительный набор фильтров 2 балла
Диффузия ошибки 2 балла
Вычисление и отображение спектра. 2 балла
Выравнивание освещенности изображения. 3 балла
Конструирование произвольного фильтра до 4 баллов
Секционная БПФ-фильтрация до 4 баллов
Ресамплинг изображений до 7 баллов
Эквалайзер звуковых файлов до 7 баллов
Произвольное задание по фильтрам до 8 баллов

Удобство работы с программой также влияет на оценку (причем в обе стороны). В первую очередь ценятся простота и интуитивность использования.

Оформление

ZIP-архив с исходными текстами и исполняемыми файлами, названный по схеме NMaaa_b.zip (где N-номер задания, M - номер группы, aaa - три первые латинские буквы фамилии, b - первая латинская буква имени) присылайте на assign2@graphics.cs.msu.su

Также смотрите здесь, какие файлы нам присылать и как их оформить Советуем прочитать FAQ

Если из меню вашей программы не сразу становится очевидно, какие обязательные и дополнительные возможности реализованы в программе, то в README-файле нужно явно это указать.

Если вы реализовали какой-либо оригинальный метод, опишите его в README-файле.

Внимание: обратите внимание на правильное именование и структуру архива с работой, а также на содержание файла readme.txt. Если ваша работа не будет соответствовать требованиям, баллы могут быть снижены.

Результаты работы

Результаты смотрите в интернете или на стенде около комнаты 703.
Все вопросы присылать автору.

Примечания

  1. Задание выполняется строго индивидуально. За совместную работу или обмен кусками кода ставится ноль баллов всем участникам, если факт командной работы не был указан в readme.txt заданий.
  2. Очень сильно рекомендуется написание программы под Windows. В крайнем случае можно использовать DOS. Написание под другие операционные системы крайне нежелательно, т.к. в этом случае мы не сможем самостоятельно проверить задание.
Главная | О курсе | Лекции | Библиотека | Задания | Оценки | FAQs
  (с) Лаборатория компьютерной графики, 1997-2002
Дизайн: Алексей Игнатенко