cg2014_02_basicanalysis (Раздаточные материалы)

Простой анализ изображенийАнтон КонушинMany slides adapted from Fei-Fei Li, Rob Fergus, Antonio Torralba, Jean Ponce and Svetlana LazebnikЗадача распознавания изображений• Понять, что запечатлено наизображении• «To see means to know what is whereby looking»• David Marr, Vision, 1982• «Тест Тьюринга» - компьютер долженответить на любой вопрос обизображении, на который можетответить человекМы видимКомпьютер видитSource: S. NarasimhanВыделение объектовЗданиеФлагФлагЛицоТекстАвтобусТекстАвтобусНеобходимо определить, есть ли на изображении объектызаданного типа и если да, то определить их положениеИзменчивость изображенийВнешние факторы:• Положение камеры• Внутренние свойства камеры• ОсвещениеВнутренние факторы:• Деформации объектов• Внутриклассоваяизменчивость• Пока приходится задачу упрощать, вводя ограничения наракурс съёмки, условия освещения, типы объектов• Мы будем рассматривать простые случаи, когда всефакторы варьируются незначительноПримеры простых задачКлетки кровиЛожки и сахарНомераМонеты и купюрыИз чего состоит изображение?Из «кусков» - отдельных объектовСегментация• Сегментация - это способ разделения сцены на«куски», с которыми проще работать• Тесселяция - разбиение изображения нанеперекрывающиеся области, покрывающие всеизображение и однородные по некоторымпризнакам• Можно и по другому сегментировать изображение• Пересекающиеся области• Иерархическое представлениеТребования к сегментации• Сегментация - это способ разделения сцены на«куски», с которыми проще работать• Границы сегментов должны соответствоватьграницам объектовРезультат сегментации• Как мы будем записывать результат сегментации?• Сделаем карту разметки – изображение, в каждомпикселе которого номер сегмента, которомупринадлежит этот пиксель• Визуализировать удобно каждый сегмент своимцветомАлгоритмы к рассмотрению• Бинаризация и выделениясвязанных компонент• Последовательное сканирование• Метод K-среднихАлгоритмы к рассмотрению• Бинаризация и выделениясвязанных компонент• Последовательное сканирование• Метод K-среднихПростейшая сегментацияЧем отличаются объекты на этом изображении?••Все объекты яркие, фон тёмныйДля сегментации такого изображения нам достаточно:пороговая бинаризация• обработки шума• выделения связанных компонент•Пороговая бинаризацияПороговая фильтрация (thresholding)Пиксели, которых выше/ниже некоторого порога, заданного«извне», помечаются 1 Ниже порога помечаются 0Бинарное изображение – пиксели которого могутпринимать только значения 0 и 1 Бинаризация - построение бинарного изображения пополутоновому / цветномуПороговая фильтрацияБолее интересный способ – определение порогаавтоматически, по характеристикам изображения• Нужно проанализироватьраспределение пикселей пояркости• Анализ гистограммы яркостиГистограмма яркостиГистограмма – это график распределения яркостей наизображении.

На горизонтальной оси - шкала яркостейтонов от белого до черного, на вертикальной оси число пикселей заданной яркости.00255255Гистограмма для нашего случаяАнализ гистограммы1.2.3.4.Анализ симметричного пика гистограммыПрименяется когда фон изображения даетотчетливый и доминирующий пик гистограммы,симметричный относительно своего центра.Сгладить гистограмму;Найти ячейку гистограммы hmax с максимальным значением;На стороне гистограммы не относящейся к объекту (на примере –справа от пика фона) найти яркость hp, количество пикселей сяркостью >= hp равняется p% (например 5%) от пикселей яркостикоторых >= hmax;Пересчитать порог T = hmax - (hp - hmax );Шум в бинарных изображенияхПример бинарного изображению с сильным шумомЧасто возникает из-за невозможности полностьюподавить шум в изображениях, недостаточнойконтрастности объектов и т.д.Шум в бинарных изображенияхПо одному пикселю невозможно определить –шум или объект? Нужно рассматривать окрестность пикселя!Подавление и устранение шумаШироко известный способ - устранение шумас помощью операций математическойморфологии: Сужение (erosion) Расширение (dilation) Закрытие (closing) Раскрытие (opening)Математическая морфологияAB• Множество A обычно является объектомобработки• Множество B (называемое структурнымэлементом) – инструмент обработкиРасширениеABA(+)BОперация «расширение» - аналог логического «или»СужениеABA(-)BОперация «расширение» - аналог логического «и»Результат операции сужения0 1 01 [1] 10 1 01 1 11 [1] 11 1 100111000 11 11 11 11 11 10 111 0 01 1 0 1 1 1[1] 1 1 1 1 1 1 11 1 1 01 1 0 0 11Важное замечаниеРезультат морфологических операций во многомопределяется применяемым структурным элементом.Выбирая различный структурный элемент можнорешать разные задачи обработкиизображений:• Шумоподавление• Выделение границ объекта• Выделение скелета объекта• Выделение сломанных зубьев на изображениишестерниОперации раскрытия и закрытияМорфологическое раскрытие (opening)• open(A, B) = (A (-) B) (+) BМорфологическое закрытие (closing)• close(A, B) = (A (+) B) (-) BПопробуйте догадаться, что эти операции делают?Применение открытияПрименим операцию открытия к изображениюс сильным шумом:0 1 01 1 10 1 01 1 11 1 11 1 100111000 1 1 1 0 01 1 1 1 1 0 1 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 00 1 1 1 0 0 Сужение vs ОткрытиеСужениеОткрытиеДефекты бинаризацииПример бинарного изображению с дефектамираспознаваемых объектовПрименение закрытияПрименим операцию закрытия к изображениюс дефекиами объектов:1 1 11 1 11 1 1011101 1 1 01 1 1 1 1 1 1 11 1 1 11 1 1 0 00111000 1 1 1 0 01 1 1 1 1 0 1 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 00 1 1 1 0 0 Не лучший пример для морфологииНе во всех случаях математическаяморфология так легко убирает дефекты,как хотелось бы…Применения операции открытия0 1 01 1 10 1 01 1 11 1 11 1 1Часто помогает медианная фильтрация!00111000 1 1 1 0 01 1 1 1 1 0 1 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 00 1 1 1 0 0 Медианный фильтр• Выбор медианы из выборки пикселей поокрестности данногоSource: K.

GraumanСвойства медианного фильтра• Не появляется новых (промежуточных) значений• Подавляет «выбросы» (отдельные резкоотличающиеся точки)Source: K. GraumanМедианный фильтрФильтр с окрестностью 3x3Теперь можем с помощью морфологии убратьоставшиеся точки, тонкие линии и т.д.Что дальше?Получили бинарноеизображениеНужна карта разметкиВыделение связных областейОпределение связной области:Множество пикселей, у каждогопикселя которого есть хотя бы одинсосед, принадлежащий данномумножеству.Соседи пикселей:4-связность8-связностьРазметка связных областей1 11 12 2 22 22354 44 446 66 6 67Бинарное изображениеРазмеченное изображениеРекурсивный алгоритмvoid Labeling(BIT* img[], int* labels[]){// labels должна быть обнуленаL = 1;for(y = 0; y < H; y++)for(x = 0; x < W; x++){Fill(img, labels, x, y, L++);}}Рекурсивный алгоритмvoid Fill(BIT* img[], int* labels[], int x, int y, int L){if( (labels[x][y] = = 0) && (img[x][y] = = 1) ){labels[x][y] = L;if( x > 0 )Fill(img, labels, x – 1, y, L);if( x < W - 1 )Fill(img, labels, x + 1, y, L);if( y > 0 )Fill(img, labels, x, y - 1, L);if( y < H - 1 )Fill(img, labels, x, y + 1, L);}}Последовательное сканированиеПоследовательно, сканируем бинарное изображение сверхувниз, слева направо:if A = Odo nothingelse if (not B labeled) and (not C labeled)increment label numbering and label Aelse if B xor C labeledcopy label to Aelse if B and C labeledif B label = C labelcopy label to Aelsecopy either B label or C label to Arecord equivalence of labelsЗа сколько операций мы разметим изображение?Выделенные связанные компонентыАлгоритмы к рассмотрению• Бинаризация и выделениясвязанных компонент• Последовательное сканирование• Метод K-среднихСегментацияНа основепоследовательногосканирования можносделать и методсегментации изображенийна однородные областиВыделение однородных областей методомпоследовательного сканированияСканируем изображение сверху вниз, слева направо:1.if I(A) – Iavg(Cl(B)) > δ and I(A) – Iavg(Cl(C)) > δ создаем новую область, присоединяем к ней пиксел A2.if I(A) – Iavg(Cl(B)) < δ xor I(A) – Iavg(Cl(C)) < δ –добавить A к одной из областей3.if I(A) – Iavg(Cl(B)) < δ and I(A) – Iavg(Cl(C)) < δ :1.Iavg(Cl(B)) - Iavg(Cl(C)) < δ –сливаем области B и C.2.Iavg(Cl(B)) - Iavg(Cl(C)) > δ–добавляем пиксел A к тому классу, отклонение откоторого минимально.I(A) – яркость пиксела ACl(B) – область к которой принадлежит пиксел BIav g(Cl(B)) – средняя яркость области к которой принадлежит BВыделение однородных областей методомпоследовательного сканированияПример:Алгоритмы к рассмотрению• Бинаризация и выделениясвязанных компонент• Последовательное сканирование• Метод K-среднихКластеризацияМетод k-средних – метод кластеризации данных.Целью задачи кластеризации является разбиениемножества объектов на группы (кластеры) наоснове некоторой меры сходства объектов.Что в случае сегментации изображения «объекты»?•••«Пиксели» изображенияМы «группируем» пиксели по похожестиПо каким признакам можем оценить похожестьпикселей?Алгоритм k-среднихДано:• Набор векторов xi i=1,…,p;• k – число кластеров, на которые нужноразбить набор xi;Найти:• k средних векторов mj j=1,…,k (центровкластеров);• отнести каждый из векторов xi к одному из kкластеров;Алгоритм k-средних1.