Машинное зрение: поиск клада

Авторы задания:

Вежневец Владимир
Вежневец Александр
Мариничев Кирилл

Полезные ресурсы

Собственно задание

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

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

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

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

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

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

ex0.gif (3353 bytes)

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

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

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

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

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

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

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

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

Также дополнительно поощряются:

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

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

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

Советы:

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

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

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

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

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

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

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

Примечания

  1. Можно написать программу под MatLab, для кого это проще.

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

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

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

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

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

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

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

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

Все остальные функции также желательно вынести в интерфейс, но перечисленное выше - обязательно.

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

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


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

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

     dAngle = 0.5 * atan(2 * dM11 / (dM20 - dM02));

Единственное что функция atan в C возвращает угол от -π/2 до π/2 - получается неоднозначность, поэтому лучше использовать функцию atan2, она возвращает угол от -π до π:

     dAngle = 0.5 * atan2(2 * dM11, (dM20 - dM02));

Это было проверено, это работает.

Оформление

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

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

Результаты работы будут опубликованы на сайте в течение трех дней после окончания срока выполнения задания.

© Лаборатория компьютерной графики при ВМиК МГУ