RETINEX

Single Scale Retinex Алгоритм SSR (Single-Scale Retinex) выравнивает освещенность изображения, сохраняя локальный контраст в плохо и ярко освещенных областях. Коррекция происходит по формуле: где G Гауссиан, sigma коэффициента размытия, "*" оператор свертки (применение фильтра). После применения SSR, основная часть полученных пикселей принадлежит диапазону [-1; 1], для визуализации изображения, значения необходимо нормализовать по формуле:

Single Scale Retinex sigma = 8

Multi Scale Retinex Алгоритм MSR (Multi-Scale Retinex) это взвешенная сумма SSR с разными коэффициентами размытия. MSR = w1·SSR1 + w2·SSR2 +… + wn·SSRn причем w1+w2+...+wn=1. Обычно, на практике n=3 sigma = 8, 20, 40, 120

Сегментация изображениях

Сегментация изображения Анализ высокого уровня: –отделение находящихся на изображении объектов от фона (и друг от друга) Анализ низкого уровня: –разбиение на области «похожих» между собой пикселей

Сегментация изображения Автоматика и интерактивность Сегментация изображения подразделяется –Интерактивная Сегментация, управляемая пользователем, допускающая и/или требующая ввода дополнительной информации –Пример – «волшебная палочка» в Photoshop –Автоматическая Сегментация производимая без взаимодействия с пользователем –Картинка на входе, регионы на выходе

Применение сегментации Фото(видео)монтаж, композиция

Применение сегментации Измерение параметров объектов

Применение сегментации Предобработка перед высокоуровневым анализом И различным моделированием

Рассматривается задача разбиения на 2 области - объект и фон На вход алгоритм получает: –исходное изображение –дополнительную информацию от пользователя: ограничение на то, что некоторые конкретные пиксели обязательно должны принадлежать объекту (фону) ограничивающий прямоугольник вокруг объекта примерную границу объекта В процессе работы алгоритма пользователь может уточнять или дополнять входные данные. Интерактивная сегментация

8 кликов мыши, более 20 кликов, причем некоторые части оленя остались неотсегментированными Алгоритм интерактивной сегментации Magic Wand «Волшебная палочка» (пример работы)

Сегментация изображения Пороговые методы Наращивание областей Выделение границ Текстурные методы Градиентные методы Вторые производные Активные контуры Другие методы Статистические методы Структурные методы Центроидное связывание Слияние – расщепление Метод водоразделов Фиксированный порог Адаптивный порог Сегментация изображений

Автоматическая сегментация Как можно сформировать однородные области? –Отталкиваясь от неоднородности на границах Пример – ищем резкие переходы яркости, берем их как границы областей –Отталкиваясь от однородности внутри областей Пример – объединяем в одну область пиксели, близкие по значению интенсивности в спектрах цветовой модели

Однородность Варианты однородности: По яркости По цвету По близости на изображении – По текстуре – По глубине (Если есть 3D информация)

Семейства методов сегментации Некоторые виды представители методов автоматической сегментации Сегментация через поиск неоднородностей –Основанные на поиске контуров (границ) Градиентные методы Вторые производные Сегментация через поиск однородностей –Методы основанные на формировании однородных областей –Метод водораздела

Сегментация через поиск неоднородностей Наиболее простой и чаще всего используемый вариант: –Поиск неоднородностей яркости через выделение границ (краев), путем формирования контурного представления

Алгоритм сегментации на основе выделения контуров (границ) 1.Найдём все контура на изображении 2.Найдем все замкнутые контура; 3.«Внутренности» замкнутых контуров являются искомыми однородными областями;

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

Выделение контуров пример

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

Подчеркивание контуров объекта Рассмотрим подчеркивание краев (границ) Край (edge) он же граница – резкое изменение яркости на изображении, часто соответствует границам объектов на изображении.

Нахождение резкого изменения интенсивности (яркости) Нас интересуют области резкого изменения яркости – нахождение таких областей можно организовать на основе анализа первой и второй производной изображения. График функции График производной График 2ой производной

Нахождение резкого изменения интенсивности (яркости) Известно, что наибольшее изменение функции происходит в направлении ее градиента. Величина изменения измеряется абсолютной величиной градиента. На дискретной сетке компоненты вектора градиента аппроксимируются конечными разностями первого порядка: G h, G v – горизонтальная и вертикальная составляющие градиента

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

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

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

Метод Робертса Данный метод работает с двумерной апертурой 2х2 следующего вида: где G – пиксель, с которым ведётся работа; D – соседние пиксели; GD DD Операторы Робертса: Формулы расчёта значения «нового» пикселя:

Метод Робертса (Пример)

Метод Собела Данный метод работает с двумерной апертурой 3х3 следующего вида: где G – пиксель с которым ведётся работа; D – соседние пиксели; GD DD Формулы расчёта значения «нового» пикселя: DDD D D Операторы Cобеля:

Метод Собела (Пример)

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

Нахождение резкого изменения интенсивности вторая производная применение оператора к изображению I(i,j) сводится к свертке изображения с маской вида: Вторые производные, в отличие от градиента, не детектируют, а подчеркивают перепад яркости. Для получения положения границы надо найти точки, в которых вторая производная равна нулю Также существуют и другие маски, используемые для аппроксимации оператора Лапласа, они имеют вид где C new, C old – новые и старые значения пикселей изображения соответственно; A k,l – коэффициент из оператора Лапласа

Метод Лапласа (Пример)

Примеры работы методов – оригинальное изображение 2 – изображение полученное по методу Робертса 3 – изображение полученное по методу Лапласа (Положительный центральный элемент) 4 – изображение полученное по методу Лапласа (Отрицательный центральный элемент) 5 – изображение полученное по методу Собела (работа со спектром яркости из HLS) 6 – изображение полученное по методу Собела (работа cо спектром RGB)

– оригинальное изображение 2 – изображение полученное по методу Робертса 3 – изображение полученное по методу Лапласа (Положительный центральный элемент) 4 – изображение полученное по методу Лапласа (Отрицательный центральный элемент) 5 – изображение полученное по методу Собела (работа со спектром яркости из HLS) 6 – изображение полученное по методу Собела (работа cо спектром RGB) Примеры работы методов

1 – оригинальное изображение 2 – изображение полученное по методу Робертса 3 – изображение полученное по методу Лапласа (Положительный центральный элемент) 4 – изображение полученное по методу Лапласа (Отрицательный центральный элемент) 5 – изображение полученное по методу Собела (работа со спектром яркости из HLS) 6 – изображение полученное по методу Собела (работа cо спектром RGB) Примеры работы методов

Дальнейшая работа с контурным представлением Получив контур объекта (связный набор пикселей) – как его дальше анализировать? - преобразовать контур в некоторое численное представление Методы формирования численного представления Полигональная аппроксимация Цепные коды

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

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

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

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

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

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

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

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

Сегментация на основе поиска однородных областей Сегментация без учета пространственных связей –Пороговая фильтрация –Кластеризация по цвету Сегментация с учетом пространственных связей –Разрастание областей (region growing) –Слияние/разделение областей (region merging/splitting)

Пороговая фильтрация Разделение пикселей на n классов по их характеристикам интенсивности спектров в рассматриваемой цветовой модели –Чаще всего используется 2 класса (бинаризация)

Гистограммы Свойства: –Рассчитываются глобально для всего изображения –Пространственная информация (расположение пикселей различной яркости) полностью игнорируется Можно использовать для сравнения изображений: Однако при анализе сложных сцен это может мешать –Сильно различные «с виду» сцены могут иметь очень похожие гистограммы

Пороговая фильтрация Яркий объект на темном фоне –Выбрать величину T разделяющую яркость объекта и фона –Каждый пиксель (x,y) яркость которого I(x,y)>T принадлежит объекту 0 255

В каждом конкретном случае хотим уметь рассчитать правильный порог –Вариант решения – анализ гистограммы изображения Как определить правильную пороговую величину T ?

Автоопределение пороговой величины T Можно использовать следующее: 1. Предположение о яркости объектов 2. Размеры объектов 3. Площадь изображения занятого объектом 4. Количество различных типов объектов Вопрос - как?

Метод P-tile: –Если знаем (предполагаем) что объект занимает P% площади –T устанавливаем так, чтобы отсечь P% пикселей на гистограмме Определение пороговой величины T Метод P-tile

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

Особенно эффективен, когда объект дает слабый пик гистограммы. ШАГ 1 Сгладить гистограмму; ШАГ 2 Найти ячейку гистограммы h max с максимальным значением; ШАГ 3Найти ячейку гистограммы, соответствующую минимальной яркости h m с ненулевым значением; ШАГ 4 Найти ячейку с максимальным расстоянием (d) от линии соединяющей h max и h m до «верхушки столбика» h b; ШАГ 5 Порог T = h з ; Определение пороговой величины T Метод треугольника

Расчет пороговой величины путем последовательных приближений Частный случай алгоритма k-средних ШАГ 1 Выбрать порог T равным середине диапазона яркостей; ШАГ 2 Вычислить среднюю яркость всех пикселей с яркостью T; ШАГ 3 Пересчитать порог T = (m 1 + m 2 ) / 2; ШАГ 4 Повторять шаги 2, 3 порог не перестанет изменяться;

ШАГ 1 Найти соседние локальные максимумы в гистограмме g i ШАГ 2 Рассчитать меру «пиковости» для g i ШАГ 3 Отфильтровать пики с слишком маленькой «пиковостью». ШАГ 4 Для оставшихся найти самые «низкие» точки между пиками которые и будут являться порогами. Определение пороговых величин на основе поиска пиков в гистограмме Формула меры «пиковости»

Общие недостатки пороговой фильтрации Игнорируется пространственное расположение пикселей –За исключением адаптивного порога, но и там соседство не учитывается Сложность подбора порога для выделения интересующих нас объектов в автоматическом режиме