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

Начало: 1 апреля 2006 года.
Конец: 16 апреля 2006 года (23:59)

Авторы задания:
Владимир Вежневец
Анна Дегтярева

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

На изображениях для обработки находятся 2 типа объектов интереса: "слоны" и "бамбук". Все остальное - шум, нас не интересующий.

В чем состоит задание? Коротко - На входном изображении нужно обнаружить слонов, поделить между ними бамбук и рассчитать сколько бамбука съест каждый слон.

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

1. Прямоугольниками разного цвета отметить на изображении слонов и бамбук (для всех слонов - один цвет, для всего бамбука - второй);
2. Вывести путь каждого слона при поедании бамбука;
3. Вывести характеристики каждого слона (слоны нумеруются сверху вниз, справа налево);

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

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

Как питаются слоны?

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

1. Слоны делят бамбук. Каждое растение достается самому ближнему к нему слону. Расстояние считается между центами масс бамбука и слона.
2. Каждый слон выбирает ближайший бамбук (из доставшихся ему), перемещается к нему и съедает его.
3. Затем слон выбирает следующий ближайший (к текущему положению слона) бамбук, идет к нему и съедает его. И так далее...

Само задание

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

• Загрузка и отображение BMP-файла. Достаточно сделать поддержку только 24bit RGB (непалитровых) форматов изображений;

• Преобразование изображения в бинарное любым из алгоритмов, рассказаных на лекции;

• Выделение связных областей любым из алгоритмов, рассказаных на лекции;

• Вычисление инвариантных характеристик областей и их классификация - (слоны, бамбук, шум);

• Расчет количества съеденного бамбука;

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

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

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

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

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

Усложненное задание

Для дополнительного задания взаимосвязь слонов и бамбука усложняется.

Разноцветные слоны

На самом деле не всякий бамбук подходит слону! Если слон серый - он может есть любой бамбук, если же он какого-то оттенка (красного, синего, и т.д.) - он может (и будет) есть только тот бамбук, который такого же оттенка как сам слон. Соответственно при дележке бамбука в присутствии цветных слонов нужно это учитывать и для каждого растения выбирать не просто ближайшего слона, а ближайшего из тех, для которых данный бамбук съедобен. За корректное распределение бамбука между цветными слонами до +3 баллов.

Цвет слона определяется по его среднему цвету (средние значения R, G и B по всем пикселям слона). Если эти значения не равны - значит слон не серый! Обратите внимание! На простых изображениях слоны могут быть с виду серые, а на самом деле слегка, скажем, розоватые - не судите на глаз. На шумных изображениях мы сделали их более явно цветными (чтобы шум меньше мешал).

Цветные слоны

1. Серый слон - R ~= B ~= G (с точностью до 3);
2. Красный слон - R > B && R > G (с точностью до 3);
3. Желтый слон - R > B && G > B (с точностью до 3);
4. Синий слон - B > R && B > G (с точностью до 3);
5. Фиолетовый слон - R > G && B > G (с точностью до 3);
6. Зеленый слон - G > B && G > R (с точностью до 3);

Обратите внимание! В разделе ЧаВо к заданию дана поправка к критериям отбора по цвету!

Зашумленные изображения

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

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

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

Призы

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

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

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

Советы:

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

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

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

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

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

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

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

Оформление

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

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

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

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

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

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

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

Результаты смотрите в интернете и/или на стенде около комнаты 703
Все вопросы и комментарии задавать в форуме. Ответы на наиболее часто задаваемые вопросы будут отражены в разделе ЧаВо по заданию

Примечания

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

Ух ты, в лекциях целых два метода последовательного сканирования - для разметки связных областей и для выделения однородных областей! За какой из них дают дополнительные баллы?

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

Цвет (255, 5, 0) по данным в задании критериям является как красным так и желтым, и цвет (255, 250, 0) тоже, в то время как в действительности первый из них это красный, а второй желтый. Так как же быть???

Давайте пересмотрим критерии, чтобы убрать неоднозначность:

1. Находим max попарную разницу между R, G, B (|R-G|, |B-G|, |R-B|)
2. Если она >3 - слон цветной
3. Как определить цвет?
   1. Берем mean = (max(R, G, B) + min(R, G, B)) / 2.
   2. Если интенсивность 1 канала > mean, цвет решается однозначно
   3. Если интенсивность двух каналов > mean - цвет решается по их комбинации. (R и G > mean - желтый и т.д.)

Как на картинке simple2 (слоны на желтом с разводами фоне) отделить слонов и бамбук от фона?

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

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

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

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

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

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

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

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

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

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

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