Лекция 2

Анализ изображений
Темы этой лекции
Выделение краев
Градиент изображения
Алгоритм Canny
Работа с контурами
Цепные коды
Полигональная аппроксимация
Ψ-s представление
Дескрипторы контуров
Как проводить прикладное исследование?

Выделение краев
Цель – преобразовать изображение в набор кривых для:
выделения существенных характеристик сокращения объема информации для анализа

Выделение краев

Откуда берутся края?
Край – резкий переход яркости.
Различные причины возникновения:
Резкое изменение глубины сцены
Резкое изменение цвета поверхности
Резкое изменение освещенности
Резкое изменение нормали поверхности

Как найти резкое изменение яркости?
Нас интересуют области резкого изменения яркости – нахождение таких областей можно организовать на основе анализа первой и второй производной изображения.
Рассмотрим одномерный случай…
График функции
График производной
График 2ой производной

Как найти резкое изменение яркости?
Известно, что наибольшее изменение функции происходит в направлении ее градиента. Величина изменения измеряется абсолютной величиной градиента.

Градиент яркости изображения
Известно, что наибольшее изменение функции происходит в направлении ее градиента
Приведем примеры…

Градиент яркости изображения
Направление градиента задается:
«Направление края» задается перпендикулярным градиенту
«Сила края» задается абсолютной величиной градиента:
Иногда используется приближенное вычисление градиента:

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

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

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

Выделение краев
Нужно:
Убрать слабые края и шум
Сделать края тонкими
Объединить пиксели краев в связные кривые

Алгоритм Canny
Давно придуман, однако до сих пор широко используется
Шаги:
Убрать шум и лишние детали из изображения
Рассчитать градиент изображения
Сделать края тонкими (edge thinning )
Связать края в контура (edge linking)

Начало…
Размыть изображение с помощью фильтра Гаусса
Убрать шум, лишние детали текстуры
Рассчитать градиент изображения
Одним из операторов – например, Собеля
Размытое изображение

…середина…
Все пиксели где сила краев < T убрать из рассмотрения

…середина…
Поиск локальных максимумов
Проверяя – является ли пиксель локальным максимумом вдоль направления градиента
Приходится интерполировать «нецелые» пиксели p и r

… финал
Выбираем еще не обработанную точку локального максимума p в которой сила края
Прослеживание края выбранного локального максимума p:
Предсказание следующей точки края q;
Проверка – ?
Если да – p = q, переход на начало шага 2;
Если нет - переход на шаг 1;

Пояснения
Как предсказать следующую точку края?
От текущей точки шаг в сторону перпендикулярную градиенту
В данном случае – в точку r или s

Пояснения
Для чего используются два порога?
Чтобы уменьшить влияние шума для инициализации кривой используем больший порог
Чтобы «не потерять хвост» используем меньший порог при прослеживании

Алгоритм Canny
Размыть изображение фильтром Гаусса c некоторым σ
Убрать шум, лишние детали текстуры
Рассчитать градиент изображения
Одним из операторов – например, Собеля
Все пиксели где сила краев < T убрать из рассмотрения
Поиск локальных максимумов
Прослеживание краев из точек локальных максимумов

Canny - результат

Влияние σ (параметр фильтра Гаусса)
Canny с
Canny с
исходное

Вопрос
Получив контур объекта (связный набор пикселей) – как его дальше анализировать?
Вариант - нужно преобразовать контур в некоторое численное представление
Один из способов – использование цепных кодов

Работа с контурами
Полигональная аппроксимация
Цепные коды
Дескрипторы контуров

Полигональная аппроксимация
Постановка:
Аппроксимация точечной кривой ломаной линией
Цель:
Сжатие информации
Борьба с дискретностью и шумом
Облегчение дальнейшего анализа

Полигональная аппроксимация
Постановка:
Аппроксимация точечной кривой ломаной линией
Цель:
Сжатие информации
Борьба с дискретностью и шумом
Облегчение дальнейшего анализа

Алгоритм Дугласа-Пекера
(рекурсивное подразбиение)
Инициализация – начнем с прямой, идущей от начальной точки к конечной
Если контур замкнутый – выберем точки максимально удаленные друг от друга

Алгоритм Дугласа-Пекера
(рекурсивное подразбиение)
Шаг №1 – найти точку контура максимально удаленную от прямой
Если расстояние от нее до прямой d < ε – разбиение завершено, если нет – к шагу 2

Алгоритм Дугласа-Пекера
(рекурсивное подразбиение)
Шаг №2 – добавить узел к ломаной линии
Затем рекурсивно вызвать Шаг №1 для каждой из половинок ломаной

Алгоритм Дугласа-Пекера
(рекурсивное подразбиение)
Результат:

Цепной код – 8-ми связные контура
Кодирование контура как последовательности перемещений
Код: 12232445466601760

Цепной код – 4-х связные контура
Кодирование контура как последовательности перемещений
Код: 1122322333010033010112

Цепной код - свойства
Свойства
Цепной код – представление контура, независимое к его перемещению
При замене в 8-ми связном кода любого n но (n mod 8) + 1 контур будет повернут по часовой стрелке на 45 градусов
Некоторые особенности контуров, такие как уголки, например могут быть сразу рассчитаны по анализу цепных кодов
Сложности
В цепном коде важна начальная точка – при ее изменении меняется и код
Небольшие вариации границы (шум) серьезно меняют код. Сравнение двух шумных контуров по цепному коды – сложно
Цепной код не инвариантен к повороту

Разностный код
Это «производная» цепного кода
Формула
yi = (xi+1- xi ) mod 8 – восьмисвязный
yi = (xi+1- xi) mod 4 – четырехсвязный

Разностный код
Свойства:
Инвариантен к повороту кратному 45 градусам (восьмисвязный)
Проблемы:
Также чувствителен к шуму
Не инвариантен к повороту на произвольный угол

Ψ-s представление
Аналогично считаем направление контура в каждой точке, но:
Направление не ограничиваем точностью в 45 градусов – считаем точную касательную (угол ψ)

Ψ-s представление
Обратите внимание:
Результирующая функция ψ(s) зависит от длины дуги s (при движении «наискосок» она увеличивается быстрее)
Расстояние между соседними пикселами

Ψ-s представление
NB на данном графике ось абсцисс – не длина дуги,
а ее горизонтальная проекция (для наглядности)

Ψ-s представление
Свойства:
Если нормировать полную длину к 1 – инвариантно к масштабу
Несложным преобразованием можно свести к практически инвариантной к повороту мере
Как быстро сравнить между собой две функции ψ(s)?
Использовать функцию плотности наклона
(slope density function)
Это гистограмма распределения углов наклона касательной контура

Кривизна
Кривизна (curvature) – производная ψ(s)
Аналогично разностному цепному коду, но со знаком
Представление, инвариантное к повороту
и переносу
Функция плотности кривизны
Гистограмма распределения значений кривизны

Дескрипторы Фурье
Контур задается набором точек:
Кол-во точек нормализуется к некоторому числу N
Вычисляем коэффициенты дискретного ПФ:

Дескрипторы Фурье
Вычисляем амплитуды коэффициентов:
Дескрипторы:
Свойства:
Инвариантны к переносу (вычли среднюю точку)
Инвариантны к повороту (берем модули коэффициентов)
Инвариантны к масштабу (нормировали на нулевой коэффициент)
Общая форма – первые по порядку дескрипторы,
детали и шум – в конце
Нельзя характеризовать локальные особенности кривой

Признаки для распознавания контуров
Цепной код (разностный код)
Ψ-s представление
Функция плотности наклона
(slope density function)
Функция плотности кривизны
(curvature density function)
Дескрипторы Фурье

Как вести прикладное исследование?
Подготовительный этап
Уяснить постановку задачи
Собрать данные для проверки работы методов
Провести обзор литературы
Уяснить отличия, сильные/слабые стороны методов, трудоемкость реализации
Фиксировать критерии сравнения до начала обзора
Выбрать потенциально подходящие методы