CV2015. Лекция 2. Простые методы распознавания изображений.
1 like2,796 views
Курс "Введение в компьютерное зрение", читаемый на ВМК МГУ имени М.В. Ломоносова в весеннем семестре 2015 года. Лектор - Конушин Антон. Лекция 2. Простые методы распознавания изображений. Рассматриваются методы бинаризации изображений, основы математической морфологии, медианная фильтрация, выделение связанных компонент, метод последовательного сканирования, метод К-средних, оценка характеристик сегментов.
![
111
1]1[1
111
Результат операции сужения
010
1]1[1
010
0011100
0111110
1111111
111]1[111
1111111
0111110
0011100](https://image.slidesharecdn.com/cv201502basicanalysis-150323044105-conversion-gate01/85/CV2015-2-25-320.jpg)
![Рекурсивный алгоритм
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++);
}
}](https://image.slidesharecdn.com/cv201502basicanalysis-150323044105-conversion-gate01/85/CV2015-2-40-320.jpg)
![Рекурсивный алгоритм
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);
}
}](https://image.slidesharecdn.com/cv201502basicanalysis-150323044105-conversion-gate01/85/CV2015-2-41-320.jpg)
More Related Content
What's hot (20)
Similar to CV2015. Лекция 2. Простые методы распознавания изображений. (19)
More from Anton Konushin (10)
CV2015. Лекция 2. Простые методы распознавания изображений.
- 1. Простой анализ изображений Many slides adapted from Fei-Fei Li, Rob Fergus,Antonio Torralba, Jean Ponce and Svetlana Lazebnik Антон Конушин
- 2. Выделение объектов Здание ЛицоТекст Лицо Текст Человек Человек Необходимо определить, есть ли на изображении объекты заданного типа и если да, то определить их положение
- 3. Изменчивость изображений Внешние факторы: • Положение камеры • Внутренние свойства камеры • Освещение Внутренние факторы: • Деформации объектов • Внутриклассовая изменчивость • Пока приходится задачу упрощать, вводя ограничения на ракурс съёмки, условия освещения, типы объектов • Мы будем рассматривать простые случаи, когда все факторы варьируются незначительно
- 4. Примеры простых задач Клетки крови Монеты и купюры Ложки и сахар Номера
- 5. Какие параметры меняются мало? Монеты и купюры Номера Внешние факторы: • Положение камеры • Внутренние свойства камеры • Освещение Внутренние факторы: • Деформации объектов • Внутриклассовая изменчивость Да все!
- 6. Из чего состоит изображение?
- 7. Из «кусков» - отдельных объектов
- 8. Сегментация • Сегментация - это способ разделения сцены на «куски», с которыми проще работать • Тесселяция - разбиение изображения на неперекрывающиеся области, покрывающие все изображение и однородные по некоторым признакам • Можно и по другому сегментировать изображение • Пересекающиеся области • Иерархическое представление
- 9. Требования к сегментации • Сегментация - это способ разделения сцены на «куски», с которыми проще работать • Границы сегментов должны соответствовать границам объектов
- 10. Результат сегментации • Как мы будем записывать результат сегментации? • Сделаем карту разметки – изображение, в каждом пикселе которого номер сегмента, которому принадлежит этот пиксель • Визуализировать удобно каждый сегмент своим цветом
- 11. Алгоритмы к рассмотрению • Бинаризация и выделения связанных компонент • Последовательное сканирование • Метод K-средних
- 12. Алгоритмы к рассмотрению • Бинаризация и выделения связанных компонент • Последовательное сканирование • Метод K-средних
- 13. Простейшая сегментация • Все объекты яркие, фон тёмный • Объекты «контрастны» по отношению к простому (однотонному) фону • Для сегментации такого изображения нам достаточно: • пороговая бинаризация • обработки шума • выделения связанных компонент Чем отличаются объекты на этом изображении?
- 14. Пороговая бинаризация Пороговая фильтрация (thresholding) Пиксели, которых выше/ниже некоторого порога, заданного «извне», помечаются 1 Ниже порога помечаются 0 Бинарное изображение – пиксели которого могут принимать только значения 0 и 1 Бинаризация - построение бинарного изображения по полутоновому / цветному
- 15. Пороговая фильтрация Более интересный способ – определение порога автоматически, по характеристикам изображения • Нужно проанализировать распределение пикселей по яркости • Анализ гистограммы яркости
- 16. Гистограмма яркости Гистограмма – это график распределения яркостей на изображении. На горизонтальной оси - шкала яркостей тонов от белого до черного, на вертикальной оси - число пикселей заданной яркости. 0 255 0 255
- 17. Гистограмма для нашего случая
- 18. Анализ гистограммы Анализ симметричного пика гистограммы Применяется когда фон изображения дает отчетливый и доминирующий пик гистограммы, симметричный относительно своего центра. 1. Сгладить гистограмму; 2. Найти ячейку гистограммы hmax с максимальным значением; 3. На стороне гистограммы не относящейся к объекту (на примере – справа от пика фона) найти яркость hp, количество пикселей с яркостью >= hp равняется p% (например 5%) от пикселей яркости которых >= hmax; 4. Пересчитать порог T = hmax - (hp - hmax);
- 19. Шум в бинарных изображениях Пример бинарного изображению с сильным шумом Часто возникает из-за невозможности полностью подавить шум в изображениях, недостаточной контрастности объектов и т.д.
- 20. Шум в бинарных изображениях По одному пикселю невозможно определить – шум или объект? Нужно рассматривать окрестность пикселя!
- 21. Подавление и устранение шума Широко известный способ - устранение шума с помощью операций математической морфологии: Сужение (erosion) Расширение (dilation) Закрытие (closing) Раскрытие (opening)
- 22. Математическая морфология A B • Множество A обычно является объектом обработки • Множество B (называемое структурным элементом) – инструмент обработки
- 23. Расширение A B A(+)B Операция «расширение» - аналог логического «или»
- 24. Сужение A B A(-)B Операция «расширение» - аналог логического «и»
- 26. Важное замечание Результат морфологических операций во многом определяется применяемым структурным элементом. Выбирая различный структурный элемент можно решать разные задачи обработки изображений: • Шумоподавление • Выделение границ объекта • Выделение скелета объекта • Выделение сломанных зубьев на изображении шестерни
- 27. Операции раскрытия и закрытия Морфологическое раскрытие (opening) • open(A, B) = (A (-) B) (+) B Морфологическое закрытие (closing) • close(A, B) = (A (+) B) (-) B Попробуйте догадаться, что эти операции делают?
- 28. 111 111 111 Применение открытия 010 111 010 0011100 0111110 1111111 1111111 1111111 0111110 0011100 Применим операцию открытия к изображению с сильным шумом:
- 29. Сужение vs Открытие Сужение Открытие
- 30. Дефекты бинаризации Пример бинарного изображению с дефектами распознаваемых объектов
- 31. 111 111 111 Применение закрытия 0011100 0111110 1111111 1111111 1111111 0111110 0011100 01110 11111 11111 11111 01110 Применим операцию закрытия к изображению с дефекиами объектов:
- 32. Не лучший пример для морфологии Не во всех случаях математическая морфология так легко убирает дефекты, как хотелось бы…
- 33. 111 111 111 Применения операции открытия 010 111 010 0011100 0111110 1111111 1111111 1111111 0111110 0011100 Часто помогает медианная фильтрация!
- 34. Медианный фильтр • Посмотрим вначале в общем виде, на примере однотонного изображения (канал яркости) • Строим выборку из пикселей по окрестности • Сортируем и выбираем центральное значение («медиану)) Source: K. Grauman
- 35. Для бинарных изображений • Выбираем то значение, которого в окрестности больше • Границы областей обычно остаются на месте • Тонкие (по сравнению с размером фильтра» линии исчезнут • Ещё про медианный фильтр мы вспомним на следующей лекции 111 101 111 001 110 000 111 111 000 110 110 110 010 010 010
- 36. Медианный фильтр Фильтр с окрестностью 3x3 Теперь можем с помощью морфологии убрать оставшиеся точки, линии и т.д.
- 37. Что дальше? Получили бинарное изображение Нужна карта разметки
- 38. Выделение связных областей Определение связной области: • Множество пикселей, у каждого пикселя которого есть хотя бы один сосед, принадлежащий данному множеству. • (или) Любые два пикселя которого связаны путём, проходящим только через пиксели множества Соседи пикселей: 4-связность 8-связность
- 39. Разметка связных областей 1 1 2 2 2 1 1 2 2 2 3 4 4 5 4 4 4 6 6 6 6 6 7 Бинарное изображение Размеченное изображение
- 40. Рекурсивный алгоритм 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++); } }
- 41. Рекурсивный алгоритм 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); } }
- 42. Последовательное сканирование Последовательно, сканируем бинарное изображение сверху вниз, слева направо: if A = O do nothing else if (not B labeled) and (not C labeled) increment label numbering and label A else if B xor C labeled copy label to A else if B and C labeled if B label = C label copy label to A else copy either B label or C label to A record equivalence of labels За сколько операций мы разметим изображение?
- 44. Алгоритмы к рассмотрению • Бинаризация и выделения связанных компонент • Последовательное сканирование • Метод K-средних
- 45. Сегментация На основе последовательного сканирования можно сделать и метод сегментации изображений на однородные области Для простоты будем оценивать только яркость пикселов
- 46. Сегментация методом последовательного сканирования 1. if I(A) – Iavg(Cl(B)) > δ and I(A) – Iavg(Cl(C)) > δ - создаем новую область, присоединяем к ней пиксел A 2. 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) – яркость пиксела A Cl(B) – область к которой принадлежит пиксел B Iav g(Cl(B)) – средняя яркость области к которой принадлежит B Сканируем изображение сверху вниз, слева направо:
- 48. Алгоритмы к рассмотрению • Бинаризация и выделения связанных компонент • Последовательное сканирование • Метод K-средних
- 49. Кластеризация Метод k-средних – метод кластеризации данных. Целью задачи кластеризации является разбиение множества объектов на группы (кластеры) на основе некоторой меры сходства объектов. X2 X1
- 50. Сегментация через кластеризацию Что в случае сегментации изображения «объекты»? • «Пиксели» изображения • Мы «группируем» пиксели по похожести • По каким признакам можем оценить похожесть пикселей?
- 51. Кластеризация K-cредними • Дано: • Набор векторов xi i=1,…,p • k – число кластеров, на которые нужно разбить набор xi • Найти: • k векторов mj, j=1,…,k (центров кластеров) • Отнести каждый из векторов xi к одному из k кластеров • При этом должен достигаться минимум суммы квадратов Евклидовых расстояний между точками xi и назначенными им центрами кластеров mj k k i ji mxMXD cluster cluster inpoint 2 )(),(
- 52. Алгоритм k-средних 1. Случайным образом выбрать k средних mj j=1,…,k 2. Для каждого xi i=1,…,p : • подсчитать расстояние от xi до каждого из mj j=1,…,k • Отнести (приписать) xi к кластеру j’, расстояние до центра которого mj’ минимально 3. Пересчитать средние mj j=1,…,k по всем кластерам 4. Повторять шаги 2, 3 пока кластеры не перестанут изменяться
- 53. Пример кластеризации в 2D Исходные данные 8 10 12 14 16 18 20 7 8 9 10 11 12 13 14
- 54. Пример кластеризации в 2D Случайная инициализация центров кластеров (шаг 1) 8 10 12 14 16 18 20 7 8 9 10 11 12 13 14 Initial Cluster Centers at Iteration 1
- 55. Пример кластеризации в 2D Кластеры после первой итерации (шаг 2) 8 10 12 14 16 18 20 7 8 9 10 11 12 13 14 Updated Memberships and Boundary at Iteration 1 XVariable YVariable
- 56. Пример кластеризации в 2D Пересчет центров кластеров после первой итерации (шаг 3) 8 10 12 14 16 18 20 7 8 9 10 11 12 13 14 Updated Cluster Centers at Iteration 2
- 57. Пример кластеризации в 2D Кластеры после второй итерации (шаг 2) 8 10 12 14 16 18 20 7 8 9 10 11 12 13 14 Updated Memberships and Boundary at Iteration 2 XVariable YVariable
- 58. Пример кластеризации в 2D Стабильная конфигурация после четвертой итерации 8 10 12 14 16 18 20 7 8 9 10 11 12 13 14 Updated Memberships and Boundary at Iteration 4 XVariable YVariable
- 59. Сегментации изображения по яркости Рассматриваем одномерное пространство яркостей пикселей и производим в нем кластеризацию с помощью k-средних. Это дает автоматическое вычисление яркостных порогов. (Для получения бинарного изображения k=2)
- 60. Алгоритм К-средних. Примеры. Исходное изображение Кластеры по яркости Кластеры по цвету Вектор признак – {яркость} Вектор признак – {R, G, B}
- 61. Алгоритм К-средних • Однопараметрический • Требует знания только о количестве кластеров • Рандомизирован • Зависит от начального приближения • Не учитывает строения самих кластеров Есть целый ряд других, более совершенных методов кластеризации!
- 62. Признаки изображения Какие признаки мы можем использовать для сравнения пикселей и регионов? • Яркость • Цвет • ?
- 63. Пример Image source: Landy & Graham (2004) Видите отдельные области?
- 64. Область 1 Image source: Landy & Graham (2004)
- 65. Область 2 Image source: Landy & Graham (2004)
- 66. Область 2 Image source: Landy & Graham (2004)
- 67. Текстура Image source: VPfaCGP Fig 8.5 • Текстура — преимущественная ориентация элементов, составляющих материал (одно из определении) • (b) - типичные примеры шаблонов (текстурных элементов) для исследований психофизиологоического восприятия изображений • Человек явно учитывает свойства текстуры фрагмента при распознавании изображений и выделении областей
- 68. «Простые клетки» V1 • В первичной визуальной коре головного мозга есть клетки, чувствительные к краям определенной ориентации • Для каждой области есть набор таких клеток, чувствительные к ориентации элементов текстуры • Как их измерять – в следующей лекции
- 69. Психологическое свойство текстуры Image source: Todd et al. 2005
- 70. Форма из текстуры • Человек интуитивно считает текстуру изотропной, т.е. с постоянными свойствами на поверхности объекта • Shape from texture: Исходя из предположения об изотропности шаблона текстуры, можно определить наклон поверности Image source: VPfaCGP Fig 8.7
- 71. Современные алгоритмы • Задача сегментации изображений продолжает активно исследоваться. • Иногда используется один признак, иногда множество • Подробнее алгоритмы сегментации рассматриваются в ск «Доп. главы компьютерного зрения»
- 72. Анализ выделенных областей Для анализа требуется вычислить некоторые числовые характеристики (признаки) областей: геометрические признаки фотометрические признаки На основе этих характеристик можно классифицировать получаемые области
- 73. Геометрические признаки Для каждой области можно подсчитать некий набор простейших числовых характеристик: • Площадь • Центр масс • Периметр • Компактность • Ориентацию главной оси инерции • Удлиненность (эксцентриситет)
- 74. Площадь и центр масс • Площадь – количество пикселей в области; m x n y yxIA 0 0 ),( A yxyI y A yxxI x m x n y m x n y 0 00 0 ),( ; ),( • Центр масс
- 75. Периметр и компактность • Компактность – отношение квадрата периметра к площади; Наиболее компактная фигура – круг: A P C 2 π4C • Периметр – количество пикселей принадлежащих границе области;
- 76. Подсчет периметра области 1. Пиксель лежит на границе области, если он сам принадлежит области и хотя бы один из его соседей области не принадлежит. (внутренняя граница) 2. Пиксель лежит на границе области, если он сам не принадлежит области и хотя бы один из его соседей области принадлежит. (внешняя граница) Периметр зависит также от того 4-х или 8-ми связность используется для определения соседей.
- 77. Пример периметров области Область Внутренняя граница Внешняя граница
- 78. Операция оконтуривания объекта При работе с бинарными изображениями контуры объекта можно получить с помощью операций математической морфологии Внутреннее оконтуривание • CI = A – (A (-) B) Внешнее оконтуривание • CO = (A (+) B) – A
- 80. Статистические моменты области Дискретный центральный момент mij области определяется следующим образом: n Syx ji ji yxIyyxxm , ),()()( Центр масс области
- 81. Инвариантные характеристики Для распознавания нас интересуют характеристики инвариантные по отношению к масштабированию, переносу, повороту: Удлиненность, нецентрированность (эксцентриситет) Компактность A P C 2 2 11 2 02200220 2 11 2 02200220 4)( 4)( mmmmm mmmmm elongation A E A B B
- 82. Ориентация главной оси инерции Не является инвариантной к повороту, но в ряде случаев предоставляет полезную информацию об ориентации объекта: 0220 112 arctan 2 1 θ mm m X Y Главная ось Центр масс
- 84. Фотометрические признаки Для каждой области можно подсчитать некий набор простейших числовых характеристик: • Средняя яркость • Средний цвет (если изображение цветное) • Распределение яркости или цвета • Признаки текстуры • Про распределение цветов и текстурные признаки будем говорить отдельно дальше Разумеется, все это считается по исходному, а не бинарному изображению!
- 85. Как анализировать признаки • Пример – ложки и сахар
- 86. Как анализировать признаки • Как воспользоваться признаками для классификации? • Подобрать диапазоны значений для разных классов вручную, экспериментально (может быть весьма трудоемко) • Подобрать диапазоны значений графически (нужна база для тренировки, трудно, если признаков много) • Обучить классификатор с помощью машинного обучения
- 87. Ручной подбор • Из общих соображений: • Ложки более вытянутые, чем сахарные кусочки • Ложки больше чем сахарные кусочки • Сахарные кусочки квадратные • Области появляющиеся из-за шума обычно небольшие и неквадратные • Пытаемся сконструировать решающее правило, проверяем экспериментально • Может быть весьма утомительно
- 88. Примеры
- 89. Графический анализ • Собрать тренировочную базу изображений • Где только ложки • Где только сахар • Где только шум Как получить такие? Да просто закрасить все остальное. • Брать признаки и строить графики
- 90. Графический анализ • Диаграмма распределения эксцентриситета (проблема – не получается отличить шум от ложек) 1 2 3 4 5 6 7 8 9 10 11 12 Ложки 0 0.2 0.4 0.6 0.8 1 Эксцентриситет Примеры Ложки Шум Сахар
- 91. Графический анализ • График распределения эксцентриситета и площади (гораздо лучше – можем подобрать значения порогов) 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 2000 4000 6000 8000 Площадь Эксцентриситет Шум Ложки Сахар
- 92. Машинное обучение • Причина бурного развития компьютерного зрения в последние годы. • Требуются большие коллекции примеров для обучения. • Посмотрим один из методов на 4ой лекции
- 93. Схема простого алгоритма Предобработка изображения Сегментация изображения Вычисление признаков сегментов и классификация
- 94. Резюме лекции • Сегментация изображения позволяет работать не со всем изображением в целом, а с отдельными значимыми фрагментами • Сегменты могут выбираться по критериям однородности по яркости, цвету, текстуре и по комбинации этих признаков • В отдельных случаях мы можем решить задачу распознавания, анализируя геометрические и фотометрические признаки сегментов