'

Простой анализ изображений

Понравилась презентация – покажи это...





Слайд 0

Простой анализ изображений Many slides adapted from Fei-Fei Li, Rob Fergus, Antonio Torralba, Jean Ponce and Svetlana Lazebnik


Слайд 1

Общая информация Страница курса http://courses.graphicon.ru/main/vision Этот курс подготовлен и читается при поддержке


Слайд 2

Внешние факторы: Положение камеры Освещение Внутриклассовая изменчивость Изменчивость изображений Внутренние факторы:


Слайд 3

Внутриклассовая изменчивость


Слайд 4

Изменчивость: Положение камеры Освещение q Сопоставление (Alignment) или (Matching) Roberts (1965); Lowe (1987); Faugeras & Hebert (1986); Grimson & Lozano-Perez (1986); Huttenlocher & Ullman (1987) Фиксируем форму объекта Сопоставление


Слайд 5

Сопоставление L. G. Roberts, Machine Perception of Three Dimensional Solids, Ph.D. thesis, MIT Department of Electrical Engineering, 1963.


Слайд 6

Сопоставление Huttenlocher & Ullman (1987)


Слайд 7

Сопоставление шаблонов Фиксируем объект Опишем объект его изображением – шаблоном (pattern) Хотим найти объект в изображении Ограничим возможные преобразования (внешние факторы) Сдвиг, размер, поворот Освещение? Будем искать объект в изображении путём попиксельного сравнения шаблона и всех фрагментов изображения «Pattern matching»


Слайд 8

Метрики (SAD) Sum of absolute differences (SSD) Sum of squared differences (CC) Cross-correlation SAD, SSD – минимизируются (0 – точное совпадение) CC – максимизируется (1 – точное совпадение)


Слайд 9

Нормализация освещенности Освещённость может меняться Можно нормализовать интенсивности пикселей шаблона и фрагмента изображения Средняя интенсивность Норма интенсивности окна Нормализованный пиксель


Слайд 10

Выравнивание освещенности Исходное изображение Линейная функция освещенности Скорректированное освещенности Выравнивание гистограммы (контраста)


Слайд 11

Пример: пульт ТВ Шаблон (слева), изображение (в центре), карта нормализованной корреляции (справа) Пик яркости (максимум корреляции) соответствует положению руки (искомого шаблона)


Слайд 12

Пример: пульт ТВ


Слайд 13

Пример: пульт ТВ


Слайд 14

Пример: пульт ТВ


Слайд 15

Пример: пульт ТВ


Слайд 16

Ограничения и проблемы Ищем конкретный объект, а не класс / категорию объектов Не «символ», а конкретную букву в конкретном шрифте Трудоёмкость Полный перебор параметров Модель преобразования В простом варианте неизвестно только положение, размер и ориентация фиксированы Чтобы учесть поворот и ориентацию придётся перебрать все возможные параметры Шаблонов может быть много OCR – распознавание символов По шаблону на каждый символ


Слайд 17

Как улучшить подход?


Слайд 18

Поиск краев Интуитивно понятно, что основная информация в картинке содержится как раз в границах (краях) Компактное представление Соответствует устройству мозга Задача: Выделить резкие изменения (разрывы) изображения Идеал: рисунок художника (но артист уже пользуются своими знаниями об объектах) Source: D. Lowe


Слайд 19

Края для сопоставления шаблонов Будем учитывать только часть, но очень важную, для распознавания шаблонов Даже улучшим обобщающую способность


Слайд 20

Откуда берутся границы Существует множество причин формирования границ на изображении Резкое изменение глубины Резкое изменение цвета поверхности Резкое изменение освещеенности Резкое изменение нормали поверхности Source: Steve Seitz Резкое изменение = «разрыв»


Слайд 21

Описание «края» Край – это точка резкого изменения значений функции интенсивности изображения изображение Slide by S. Lazebnik


Слайд 22

Градиент направлен в сторону наибольшего изменения интенсивности Градиент изображения Градиент изображения: Направления градиента задается как: Как направление градиента соответствует направлению края? Сила края задается величиной (нормой) градиента: Source: Steve Seitz


Слайд 23

Дифференцирование и свёртка Для функции 2х переменных, f(x,y): Линейная и инвариантная к переносу, поэтому м.б. Результатом свертки Разностная производная: Свёртка! Source: D. Forsyth, D. Lowe


Слайд 24

Вычисление градиента Математический смысл – приближенное вычисление производных по направлению Робертса Превитт Собеля Семейство методов основано на приближенном вычисление градиента, анализе его направления и абсолютной величины. Свертка по функциям:


Слайд 25

Примеры карты силы краев Примеры: Робертса Превитт Собеля


Слайд 26

Влияние шума Рассмотрим строку или столбец изображения Интенсивность от положения можно рассматривать как сигнал Source: S. Seitz


Слайд 27

Влияние шума Разностные производные очень чувствительны к шуму Зашумленные пиксели отличаются от соседей Чем сильнее шум, тем выше отклик Сглаживание Сглаживание делает все пиксели (зашумленные?) чуть более похожими на соседей Source: D. Forsyth


Слайд 28

Предобработка (сглаживание) f Source: S. Seitz


Слайд 29

Операции свертки и дифференцирования ассоциативны: Это экономит 1 операцию: Свойства свертки Source: S. Seitz


Слайд 30

Производная фильтра гаусса * [1 -1] = Slide by S. Lazebnik


Слайд 31

Производная фильтра гаусса x-direction y-direction Slide by S. Lazebnik


Слайд 32

Сглаженные производные подавляют шум, но размывают края. Плюс края находится на разных «масштабах» 1 pixel 3 pixels 7 pixels Поиск баланса Source: D. Forsyth


Слайд 33

Выделение краев Вычисление градиента – это еще не всё… Чего не хватает? Точности – края «толстые» и размытые Информации о связности Карта силы краев


Слайд 34

Разработка детектора краев Критерии качества детектора: Надежность: оптимальный детектор должен редко ошибаться (ложные края и пропущенные края) Точная локализация: найденный край должен быть как можно ближе к истинному краю Единственный отклик: детектор должен выдавать одну точку для одной точки истинного края, т.е. локальных максимум вокруг края должно быть как можно меньше Связанность: хотим знать, какие пиксели принадлежат одной линии края Source: L. Fei-Fei


Слайд 35

Детектор Canny Свертка изображения с ядром – производной от фильтра гаусса Поиск нормы и направления градиента Выделение локальных максимумов (Non-maximum suppression) Утоньшение полос в несколько пикселей до одного пикселя Связывание краев и обрезание по порогу (гистерезис) : Определяем два порога: нижний и верхний Верхний порог используем для инициализации кривых Нижний порог используем для продолжения кривых MATLAB: edge(image, ‘canny’) Source: D. Lowe, L. Fei-Fei


Слайд 36

Пример Исходное изображение (Lena) Slide by S. Lazebnik


Слайд 37

Пример Норма градиента Slide by S. Lazebnik


Слайд 38

Пример Отсечение по порогу Slide by S. Lazebnik


Слайд 39

Пример Утоньшение (non-maximum suppression) Slide by S. Lazebnik


Слайд 40

Поиск локальных максимумов Максимум достигается в q, если значение больше p и r. Значения в p и r интерполируем. Source: D. Forsyth


Слайд 41

Пусть отмеченная точка – край. Строим касательную к границе (нормаль к направлению градиента) и используем ее для предсказания новой точки (это либо s либо r). Связывание точек Source: D. Forsyth


Слайд 42

Отсечение по порогу Проверяем точку, чтобы значение градиента было выше порога Используем гистерезис Большой порог для начала построения кривой и низкий порог для продолжения края (связывания) Source: S. Seitz


Слайд 43

Эффект гистерезиса Исходное изображение Source: L. Fei-Fei


Слайд 44

Влияние ? Canny with Canny with original Выбор ? (размера ядра размытия) зависит от задачи большое ? - поиск крупных границ малая ? - выделение мелких деталей Source: S. Seitz


Слайд 45

Ограничения детектора Source: Martin et al. 2003


Слайд 46

Поиск краев – это только начало… Berkeley segmentation database: http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench/ image human segmentation gradient magnitude Slide by S. Lazebnik


Слайд 47

Края для сопоставления шаблонов Получили карту краёв шаблона и изображения Как их сравнить друг с другом? Просто попиксельно явно не оптимально


Слайд 48

Метрики Сhamfer Distance Для каждого пикселя a края шаблона A вычисляем расстояние до ближайшего пикселя b края изображения B Суммируем все найденные расстояния Hausdorff Distance Почти то же самое, но берём не сумму, а максимальное расстояния


Слайд 49

Метрики Свойства метрик Сhamfer требует нормализации, Hausdorff нет Chamfer cимметрична, Hausdorff нет HausDist (A,B) <> HausDist(B,A) Можно использовать не max, а медиану (медленнее) Какую метрику использовать? Обычно заранее сказать нельзя, нужна экспериментальная проверка


Слайд 50

Поиск ближайших пикселей края Вопрос: как найти ближайший пиксель края на изображении?


Слайд 51

Distance Transform Для каждого пикселя вычисляется расстояние до ближайшего пикселя края


Слайд 52

Применение DT Совмещаем шаблон и карту DT Вычисляем ошибку, суммирую все значения в пикселях краев


Слайд 53

Простейший алгоритм – N проходов Первый проход помечает края 0 На втором помечаем все граничащие с 0 пиксели как 1 И т.д. Существует двухпроходный алгоритм Вычисление DT


Слайд 54

Пример DT DT может использоваться для поиска «скелета» – осей объекта


Слайд 55

Пример поиска с помощью DT


Слайд 56

Пример


Слайд 57

Резюме сопоставления шаблонов Подходит в тех случаях, когда объекты фиксированы и модель преобразования не очень сложная Цифры на знаках Цифры на конвертах Аэрофотосъёмка / Космическая съёмка Не очень быстрые методы Требуются специальные процедуры для ускорения, пр. отбраковка ложных фрагментов по упрощённым критериям и т.д. Номера


Слайд 58

Изменчивость Инвариантность к: Duda & Hart ( 1972); Weiss (1987); Mundy et al. (1992-94); Rothwell et al. (1992); Burns et al. (1993) Положение камеры Освещение Внутренние параметры Инвариантность


Слайд 59

Примеры Клетки крови Монеты и купюры Ложки и сахар Номера Контрастные объекты на фоне!


Слайд 60

В общем случае, для 3D объектов не существует проективных инвариантов (Burns et al., 1993) Более сложные примеры Инвариантность к перспективным искажениям – проективные инварианты (Rothwell et al., 1992)


Слайд 61

Схема простого алгоритма


Слайд 62

Схема простого алгоритма Предобработка изображения для упрощения анализа (например – шумоподавление) Выделение на изображении контрастных областей-кандидатов в которых может находится искомый объект Вычисление признаков (инвариантов) по выделенным фрагментам Проверка – является ли фрагмент изображения изображением нужного нам объекта по измеренным параметрам


Слайд 63

Бинаризация изображений Пиксель бинарного изображения может принимать только значения 0 и 1 Бинаризация – построение бинарного изображения по полутоновому / цветному Смысл? Разделить изображение на фон и контрастные объекты Объекты помечены 1, фон 0


Слайд 64

Пороговая фильтрация Простейший вариант - пороговая фильтрация (thresholding) Выделение областей, яркость которых выше/ниже некоторого порога, заданного «извне»


Слайд 65

Пороговая фильтрация Более интересный способ – определение порога автоматически, по характеристикам изображения Анализ гистограммы


Слайд 66

Анализ гистограммы Анализ симметричного пика гистограммы Применяется когда фон изображения дает отчетливый и доминирующий пик гистограммы, симметричный относительно своего центра. Сгладить гистограмму; Найти ячейку гистограммы hmax с максимальным значением; На стороне гистограммы не относящейся к объекту (на примере – справа от пика фона) найти яркость hp, количество пикселей с яркостью >= hp равняется p% (например 5%) от пикселей яркости которых >= hmax; Пересчитать порог T = hmax - (hp - hmax);


Слайд 67

Адаптивная бинаризация Необходима в случае неравномерной яркости фона/объекта.


Слайд 68

Адаптивная бинаризация Необходима в случае неравномерной яркости фона/объекта. Для каждого пикселя изображения I(x, y): В окрестности пикселя радиуса r высчитывается индивидуальный для данного пикселя порог T; Если I(x, y) > T + C , результат 1, иначе 0; Варианты выбора T: T = mean T = median T = (min + max) / 2


Слайд 69

Адаптивная бинаризация r=7, C=0 r=7, C=7 r=75, C=10 Исходное


Слайд 70

Шум в бинарных изображениях Пример бинарного изображению с сильным шумом Часто возникает из-за невозможности полностью подавить шум в изображениях, недостаточной контрастности объектов и т.д.


Слайд 71

Шум в бинарных изображениях По одному пикселю невозможно определить – шум или объект? Нужно рассматривать окрестность пикселя!


Слайд 72

Подавление и устранение шума Широко известный способ - устранение шума с помощью операций математической морфологии: Сужение (erosion) Расширение (dilation) Закрытие (closing) Раскрытие (opening)


Слайд 73

Математическая морфология A B Множество A обычно является объектом обработки, а множество B (называемое структурным элементом) – инструментом.


Слайд 74

Расширение в дискретном случае A B A(+)B Операция «расширение» - аналог логического «или»


Слайд 75

Расширение Расширение (dilation) A (+) B = {t ? R2: t = a + b, a ? A, b ? B} B A (+) B


Слайд 76

Cужение Сужение (erosion) A (-) B = (AC (+) B)С, где AC – дополнение A A(-)B B A


Слайд 77

Результат операции сужения


Слайд 78

Свойства Коммутативный закон A (+) B = B (+) A A (-) B < > B (-) A Ассоциативный закон A (+) (B (+) C) = (A (+) B) (+) C A (-) (B (-) C) = (A (-) B) (-) C


Слайд 79

Важное замечание Результат морфологических операций во многом определяется применяемым структурным элементом. Выбирая различный структурный элемент можно решать разные задачи обработки изображений: Шумоподавление Выделение границ объекта Выделение скелета объекта Выделение сломанных зубьев на изображении шестерни


Слайд 80

Расширение void Dilation(BIT* src[], bool* mask[], BIT* dst[]) { // W, H – размеры исходного и результирующего изображений // MW, MH – размеры структурного множества for(y = MH/2; y < H – MH/2; y++) { for(x = MW/2; x < W – MW/2; x++) { BIT max = 0; for(j = -MH/2; j <= MH/2; j++) { for(i = -MW/2; i <= MW/2; i++) if((mask[i][j]) && (src[x + i][y + j] > max)) { max = src[x + i][y + j]; } } dst[x][y] = max; } } }


Слайд 81

Сужение void Erosion(BIT* src[], bool* mask[], BIT* dst[]) { // W, H – размеры исходного и результирующего изображений // MW, MH – размеры структурного множества for(y = MH/2; y < H – MH/2; y++) { for(x = MW/2; x < W – MW/2; x++) { BIT min = MAXBIT; for(j = -MH/2; j <= MH/2; j++) { for(i = -MW/2; i <= MW/2; i++) if((mask[i][j]) && (src[x + i][y + j] < min)) { min = src[x + i][y + j]; } } dst[x][y] = min; } } }


Слайд 82

Операции раскрытия и закрытия Морфологическое раскрытие (opening) open(A, B) = (A (-) B) (+) B Морфологическое закрытие (closing) close(A, B) = (A (+) B) (-) B


Слайд 83

Применение открытия Применим операцию открытия к изображению с сильным шумом:


Слайд 84

Сужение vs Открытие Сужение Открытие


Слайд 85

Дефекты бинаризации Пример бинарного изображению с дефектами распознаваемых объектов


Слайд 86

Применение закрытия Применим операцию закрытия к изображению с дефекиами объектов:


Слайд 87

Не лучший пример для морфологии Не во всех случаях математическая морфология так легко убирает дефекты, как хотелось бы…


Слайд 88

Применения операции открытия Часто помогает медианная фильтрация!


Слайд 89

Медианный фильтр Фильтр с окрестностью 3x3


Слайд 90

Выделение связных областей Определение связной области: Множество пикселей, у каждого пикселя которого есть хотя бы один сосед, принадлежащий данному множеству. Соседи пикселей: 4-связность 8-связность


Слайд 91

Разметка связных областей 1 1 2 2 2 1 1 2 2 2 3 4 4 5 4 4 4 6 6 6 6 6 7 Бинарное изображение Размеченное изображение


Слайд 92

Рекурсивный алгоритм 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++); } }


Слайд 93

Рекурсивный алгоритм 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); } }


Слайд 94

Последовательное сканирование Последовательно, сканируем бинарное изображение сверху вниз, слева направо: 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


Слайд 95

Последовательное сканирование Случай конфликта: Постобработка - переразметка с учетом эквивалентностей областей (второй проход в алгоритме)


Слайд 96

Выделенные связанные компоненты


Слайд 97

Анализ выделенных областей Для дальнейшего анализа требуется вычислить некоторые числовые характеристики (признаки) областей: геометрические признаки фотометрические признаки На основе этих характеристик можно классифицировать получаемые области


Слайд 98

Геометрические признаки Для каждой области можно подсчитать некий набор простейших числовых характеристик: Площадь Центр масс Периметр Компактность Ориентацию главной оси инерции Удлиненность (эксцентриситет)


Слайд 99

Площадь и центр масс Площадь – количество пикселей в области; Центр масс


Слайд 100

Периметр и компактность Компактность – отношение квадрата периметра к площади; Наиболее компактная фигура – круг: Периметр – количество пикселей принадлежащих границе области;


Слайд 101

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


Слайд 102

Пример периметров области Область Внутренняя граница Внешняя граница


Слайд 103

Операция оконтуривания объекта При работе с бинарными изображениями контуры объекта можно получить с помощью операций математической морфологии Внутреннее оконтуривание CI = A – (A (-) B) Внешнее оконтуривание CO = (A (+) B) – A


Слайд 104

Пример оконтуривания объекта


Слайд 105

Статистические моменты области Дискретный центральный момент mij области определяется следующим образом: Центр масс области


Слайд 106

Инвариантные характеристики Для распознавания нас интересуют характеристики инвариантные по отношению к масштабированию, переносу, повороту: Удлиненность, нецентрированность (эксцентриситет) Компактность


Слайд 107

Ориентация главной оси инерции Не является инвариантной к повороту, но в ряде случаев предоставляет полезную информацию об ориентации объекта:


Слайд 108

Пример Вычисленные значения признаков


Слайд 109

Другие признаки Другие инвариантные характеристики области:


Слайд 110

Фотометрические признаки Для каждой области можно подсчитать некий набор простейших числовых характеристик: Средняя яркость Средний цвет (если изображение цветное) Гистограмма распределения яркостей (или три гистограммы распределения R, G, B) Дисперсию (разброс) яркостей или цвета Разумеется, все это считается по исходному, а не бинарному изображению!


Слайд 111

Как анализировать признаки Пример – ложки и сахар


Слайд 112

Как анализировать признаки Как воспользоваться признаками для классификации? Подобрать диапазоны значений для разных классов вручную, экспериментально (может быть весьма трудоемко) Подобрать диапазоны значений графически (нужна база для тренировки, трудно, если признаков много) Обучить классификатор с помощью машинного обучения На будущих лекциях! Второе задание!


Слайд 113

Ручной подбор Из общих соображений: Ложки более вытянутые, чем сахарные кусочки Ложки больше чем сахарные кусочки Сахарные кусочки квадратные Области появляющиеся из-за шума обычно небольшие и неквадратные Пытаемся сконструировать решающее правило, проверяем экспериментально Может быть весьма утомительно


Слайд 114

Графический анализ Собрать тренировочную базу изображений Где только ложки Где только сахар Где только шум Как получить такие? Да просто закрасить все остальное. Брать признаки и строить графики


Слайд 115

Графический анализ Диаграмма распределения эксцентриситета (проблема – не получается отличить шум от ложек)


Слайд 116

Графический анализ График распределения эксцентриситета и площади (гораздо лучше – можем подобрать значения порогов)


Слайд 117

Машинное обучение Причина бурного развития компьютерного зрения в последние годы. Требуются большие коллекции примеров для обучения. Рассмотрим позднее!


Слайд 118

На следующей лекции Методы представления изображений Избыточность данных «Компактность» vs «Разреженность» Обработка изображений на основе обучаемых словарей


×

HTML:





Ссылка: