Курсы лаборатории компьютерной графики
Обязательный полугодовой курс ВМиК МГУ
     

Задание №3. Обработка и анализ изображений.

Начало: 29 марта 2004 года.
Конец:  12 апреля 2004 года (23:59)

Авторы задания:
Вежневец Владимир
Вежневец Александр
Мариничев Кирилл

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

На изображениях для обработки находятся 3 типа объектов интереса:

  • белые стрелки, указывающие путь;
  • начальная стрелка (всегда красного цвета);
  • "клад" - некоторый объект на который указывает последняя в пути стрелка;

В чем состоит задание? Задание формулируется следующим образом: на входном изображении нужно обнаружить стрелки, построить путь от начальной точки до "клада".

Правила отображения результатов:

  1. Нарисовать путь по стрелочкам от начальной точки до клада в виде ломаной линии;
  2. Отметить клад на рисунке (либо прямоугольной рамкой, либо оконтуриванием объекта);

ex0.gif (3353 bytes)

Исходная картинка (слева) и результат работы (справа)

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

Требуется написать программу, выполняющую следующие операции над изображениями из категории "simple" (отсутствие шума, черный фон, светлые объекты):

  • Загрузка и отображение BMP-файла. Достаточно сделать поддержку только  RGB (непалитровых) форматов изображений;
  • Преобразование изображения в бинарное с помощью любого из рассказанных на лекции алгоритмов
  • Выделение связных областей любым из алгоритмов, рассказаных на лекции;
  • Обнаружение объектов на изображении (стрелки, начальная стрелка, клад) с помощью их характеристик (цвет, хар-ки связных областей, что еще придумаете);
  • Построение пути от красной стрелки до клада;
  • Отображние должно быть оформлено, как написано выше, оба пункта правил отображения обязательны.

Программа должна реализовывать универсальный алгоритм, одинаково (правильно) работающий на всех изображениях из категории "simple". За реализация минимального задания дается 7 баллов.

Для тех, кто хотел бы самостоятельно придумать алгоритм распознавания для картинок "simple", я здесь ничего не пишу. Те, кому нужна подсказка, найдут ее здесь.

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

За быструю работу алгоритмов, удобный и красивый (не путать с вычурным) интерфейс и аккуратно и грамотно оформленный код (в соотвествии с рекомендациями) будут начисляться призовые баллы (всего не более +3 баллов). Также дополнительно поощряются:

  • Реализация медианной фильтрации с задаваемым размером окрестности;
    (2 балла)
  • Реализация выделения связных областей путем последовательного сканирования;
    (2 балла)
  • Реализация операций математической морфологии (cужение, расширение, открытие, закрытие);
    (2 балла)
  • Реализация любого метода автоматического определения порога сегментации (треугольника, k-средних, симметричного пика);
    (2 балла)
  • Реализация одного из методов коррекции контрастности/цветности; (серый мир, растяжение диапазона)
    (1 балл)
  • Оконтуривание клада методами выделения краев или мат. морфологии;
    (1 балл)

Помимо "простых" для распознавания изображений (набор "simple"), даются два дополнительных набора. Один - с зашумленными изображениями, для тех, кому интересно решить более сложную задачу ("medium") и один с сильно испорченными изображениями ("maniac").

За успешное обработку с применением шумоподавления и коррекции изображения известными вам способами изображений "medium" дается дополнительно до +4 баллов (в зависимости от того, с какими картинками справитесь).

Успешное распознавание изображений из набора "maniac" также премируется до +4 баллов.

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

Советы:

  • Сначала реализуйте и доведите до рабочего состояния обязательную часть задания, и только потом наращивайте дополнительную функциональность.
  • Пробуйте разные фильтры, морфологию с разными структурными элементами.
  • Для одной из картинок из раздела "maniac" требуется реализация выравнивания освещенности. Алгоритм описан вот здесь.
  • Пробуйте применять различные предобработки для разных задач. Скажем, для нахождения стрелок - одна последовательность фильтров, после этого, опираясь на полученные знания, можно применить к исходному изображдению другую последовательность фильтров для нахождения клада.

Исходные данные для обработки

Архив с изображениями "simple"
Архив с зашумленными изображениями "medium"
Архив с зашумленными изображениями "maniaс"

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

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

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

Программа должна быть под Windows, скомпилирована со всеми библиотеками, подключаемыми статически.

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

Оформление

Оформление не отличается от обычного.

ZIP-архив с исходными текстами и исполняемыми файлами, названный по схеме GZV_nnnnnnnn.zip (где G - последняя цифра номера группы, Z - номер задания, V - номер версии задания, nnnnnnnn - номер студенческого билета) присылайте на assign3@graphics.cs.msu.su

Например, студент 206 группы с номером студенческого билета 06529042, сдающий обновленную (вторую) версию программы по второму заданию, должен прислать архив с именем 622_06529042.zip.

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

Не забудьте положить в архив файл readme.txt. В файле описать интерфейс програмы (алгоритм работы с программой, пункты меню, управляющие клавиши)

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

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

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

Примечания

  1. Задание выполняется строго индивидуально. За совместную работу или обмен кусками кода ставится -5 баллов всем участникам, если факт командной работы не был указан в readme.txt заданий.
  2. Рекомендуется написание программы под семейство ОС Windows. Написание под другие операционные системы нежелательно и может вызвать задержки с проверкой таких работ.

ЧаВо по заданию

Почему иногда не работает алгоритм k-средних?

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

Пример: изображения с яркостями от 0 до 130. Если при первом шаге разделения выпадут случайные средние 128 и 200, то получится, что к среднему яркости 200 не окажется приписанным ни одного пикселя. И в результате получится один кластер вместо двух.

Чтобы избежать этой ситуации нужно иметь ввиду такую возможность и предпринимать некие действия для решения проблемы, например: случайным образом вычислять средние исходя из реального диапазона яркостей изображения (в нашем примере от 0 до 130), и/или при обнаружении среднего с нулем приписанных к нему пикселей заново инициализировать его случайным образом.

Какие функции нужно обязательно выносить в пользовательский интерфейс?

Нужно предусмотреть возможность вызвать (кнопкой или меню):

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

Я придумал хитрый алгоритм распознавания, отличающийся от данного в задании. Я молодец?

Если алгоритм работает - то да. Не забудьте только реализовать вещи, перечисленные в обязательной части. И еще не забудьте описать в readme ваш алгоритм (четко, кратко и понятно). Оригинальные идеи будут премироваться дополнительными баллами.

Что будет с теми кто пришлет плагиат?

Будут ставиться отрицательные баллы всем владельцам одинаковых работ. Берегите ваши работы от нечистоплотных любителей халявы.

А я - чиста реальный пацан (дивчонка). Я типа не учицца сюда пришол (пришла), а чиста за дипломом. Мне типа ваш машграф савершенна не нужин. Мне тут адин товарищ за деньги прогу написал, тока я ниче в ней не понимаю. Че будет если меня вызавут, спросют че там где, а я не отвечу?

Всем, кто не разбирается в том, что он сдал (как в алгоритмах, так и в программе) будет ставиться -5 баллов. Специально для "реальных людей" часть студентов (случайным образом выбранных) будет приглашена на собеседование.

Не получается по формуле в лекциях вычислить ось главной инерции стрелочки. Как это сделать?

Почему не получается - непонятно, ибо формула правильная и проверенная. Вот код, который совершенно точно работает:

     dAngle = 0.5 * atan(2 * dM11 / (dM20 - dM02));
Единственное что функция atan в C возвращает угол от -π/2 до π/2 - получается неоднозначность, поэтому лучше использовать функцию atan2, она возвращает угол от -π до π:
     dAngle = 0.5 * atan2(2 * dM11, (dM20 - dM02));
Это было проверено, это работает.

Your comments and questions (перед отсылкой уберите пробелы): vvp @ graphicon . ru
Главная | О курсе | Лекции | Библиотека | Задания | Оценки | FAQs
  (с) Лаборатория компьютерной графики, 1997-2004
Дизайн: Алексей Игнатенко