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

На прошлой лекции…
На прошлой лекции научились работать со структурами «с нулевой площадью» на изображении (с контурами)
Выделять
Анализировать (отличать)
На этой лекции – перейдем к «объектам с площадью». Будем:
Выделять
Анализировать (отличать)

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

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

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

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

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

Определение сегментации 1
«Жесткая» сегментация
Разбиение изображения на неперекрывающиеся области, покрывающие все изображение и однородные по некоторому признаку
Формально:
Разбиение изображения на набор областей

Рассмотрим семейства методов:
Основанные на поиске краев
Основанные на формировании однородных областей
Метод водораздела / tobogganing
Методы из теории графов

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

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

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

Алгоритм
Найдём все контура на изображении алгоритмом Canny;
Найдем все замкнутые контура;
«Внутренности» замкнутых контуров являются искомыми однородными областями;

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

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

Гистограммы
Гистограмма (одноканального изображения) – график распределения яркостей пикселей:
На горизонтальной оси - шкала яркостей от черного до белого
На вертикальной оси - число пикселей заданной яркости

Гистограммы
Свойства:
Рассчитываются глобально для всего изображения
Пространственная информация (расположение пикселей различной яркости) полностью игнорируется
Это можно использовать для сравнения изображений:

Гистограммы
Свойства:
Рассчитываются глобально для всего изображения
Пространственная информация (расположение пикселей различной яркости) полностью игнорируется
Это можно использовать для сравнения изображений:

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

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

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

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

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

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

Поиск пиков в гистограмме
Найти соседние локальные максимумы в гистограмме gi
Рассчитать меру «пиковости» для gi
Отфильтровать пики с слишком маленькой «пиковостью».
Для оставшихся найти самые «низкие» точки между пиками – это и будут пороги.

Мера «пиковости»

Зашумленность гистограмм
93 пика
Это проблема – много «лишних» локальных максимумов

Сглаживание гистограмм
Сглажено 1 раз
54 пика
«Пиковость» проходят 18
2 раза
21 пика
«Пиковость» проходят 7
3 раза
11 пиков
«Пиковость» проходят 4 peaks
Сглаживание посредством усреднения соседних значений
Свертка одномерным box-фильтром

Области найденные по пикам

Адаптивный порог
Проблема:
Яркость фона может быть разной в разных частях изображения
Единый порог не подойдет

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

Адаптивный порог
r=7, T=0
r=7, T=7
r=75, T=10
Исходное

Адаптивный порог
Другая формулировка
Приближение фона усреднением
Вычитание фона - I(x, y) – C(x,y) > T
I(x,y) - C(x,y), r=18
Исходное

Адаптивный порог
Хорошо работает
Когда размер искомого объекта заметно меньше размера оцениваемой окрестности
Хуже работает,
Когда объект велик по сравнению с самим изображением
r=7
r=140
Исходное
r=300

Кластеризация k-средних
Способ определения нескольких порогов одновременно
Нужно заранее знать k - количество диапазонов яркостей
В принципе можно k найти по гистограмме с помощью анализа «пиковости»

Алгоритм k-средних
Случайным образом выбрать k средних mj j=1,…,k;
Для каждого vi i=1,…,p подсчитать расстояние до каждого из mj j=1,…,k,
Отнести (приписать) vi к кластеру j’, расстояние до mj’ минимально;
Пересчитать средние mj j=1,…,k по всем кластерам;
Повторять шаги 2, 3 пока кластеры не перестанут изменяться;
Входные данные – набор векторов n-мерного пр-ва vi i=1,…,p.
Выходные данные– центры кластеров mj j=1,…,k и принадлежность vi к кластерам

Пример кластеризации в 2D
Исходные данные

Пример кластеризации в 2D
Случайная инициализация центров кластеров (шаг 1)

Пример кластеризации в 2D
Кластеры после первой итерации (шаг 2)

Пример кластеризации в 2D
Пересчет центров кластеров после первой итерации (шаг 3)

Пример кластеризации в 2D
Кластеры после второй итерации (шаг 2)

Пример кластеризации в 2D
Стабильная конфигурация после четвертой итерации

k-средних для сегментации
Если изображение одноканальное
vi = I(x, y) – работаем в одномерном пространстве
Получается итеративный алгоритм пересчета порога
Если изображения трехканальное (RGB)
vi = (R(x, y), G(x,y), B(x, y)) – работаем в трехмерном пространстве
Можно работать и с многоканальными изображениями
Например – RGB + инфракрасный канал

Алгоритм k-средних для одноканального изображения
Случайным образом выбрать k средних mj j=1,…,k;
Для каждого пикселя (x,y) подсчитать Dj=|I(x,y) - mj| для j=1,…,k
Приписать (x,y) к кластеру j’, Dj’=min{Dj, j=1,..,k};
Пересчитать средние mj j=1,…,k по всем кластерам;
Повторять шаги 2, 3 пока кластеры не перестанут изменяться;

Сравнение k-средних с порогом по средней яркости
Чем отличается сегментация с помощью k-средних на 2 кластера от простейшей пороговой бинаризации по средней яркости изображения?
Пример:
k-средних
Порог по средней яркости
В причинах предлагается разобраться самостоятельно

Общие недостатки описанного
Игнорируется пространственное расположение пикселей
За исключением адаптивного порога, но и там соседство не учитывается
Перейдем к методам, учитывающим взаимное расположение пикселей

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

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

Разрастание регионов
(Region growing)
Простая идея – начиная с некоторого “семени” обходить пиксели и объединять в области пока выполняется условие однородности

Что необходимо определить
Критерий однородности
Гистограмма содержит не больше 1 значительного пика
Отклонение любого пикселя от средней яркости < Tavg
Разница между соседними пикселями < Tdiff
«Слабая» граница между регионами (только для слияния) - позже

Пример δ = 1
Алгоритм разрастания регионов
Среднее: 1
Среднее: 1.125

Алгоритм разрастания регионов
Пример δ = 1

Разрастание регионов
if |I(A) – Clavg(B)| > δ and |I(A) – Clavg(C)| > δ -
создаем новую область, присоединяем к ней пиксел A
if |I(A) – Clavg(B)| ≤ δ xor |I(A) – Clavg(C)| ≤ δ –
добавить A к одной из областей
if |I(A) – Clavg(B)| ≤ δ and |I(A) – Clavg(C)| ≤ δ :
|Clavg(B) - Clavg(C)| ≤ δ –
сливаем области B и C.
|Clavg(B) - Clavg(C)| > δ–
добавляем пиксел A к тому классу, отклонение от которого минимально.
I(A) – яркость пиксела A
Clavg(B) – средняя яркость области к которой принадлежит B
Сканируем изображение сверху вниз, слева направо:

Разделение областей
Первый шаг – всё изображение это одна область, поместить область в стек
Пока стек не пуст
Взять область S из стека
Проверить область на однородность
Если область неоднородна
разделить ее, новые области поместить в стек
Если область однородна
область больше не трогаем

Что необходимо определить 2
Правило разделения областей
Распространенный вариант – на 4 части, как квадродерево
Просто реализовать, но границы получившихся областей вряд ли будут соответствовать границам объектов

Пример
Алгоритм разбиения
(split)

Первое разбиение
Алгоритм разбиения
(split)

Второе разбиение
Алгоритм разбиения
(split)

Третье разбиение
Алгоритм разбиения
(split)

Что необходимо определить 3
Правило разделения областей – более умно
Найти в гистограмме пики, разделить гистограмму по ним
Для каждой части гистограммы найти связные компоненты – это будут новые области
Реализовать сложнее, работает дольше

Слияние областей
Первый шаг – каждый пиксель это отдельная область, поместить все области в стек
Пока стек не пуст
Взять область S из стека, для всех соседних областей Si:
Проверить S’=S U Si на однородность
Если S’ однородна -
Слить S и Si , S’ поместить в стек, Si из стека удалить, перейти на 2
Если область не однородна
Пробуем другого соседа

Алгоритм «фагоцита»
Истаивание границ
Убирает слабые границы
«Слабость границ» определяется по разности яркостей граничных пикселей
S1
S2
клетка способная захватывать и переваривать посторонние тела

Алгоритм «фагоцита»
S1
S2

Алгоритм «фагоцита»
Слить две области если:
где P1 и P2 – периметры областей S1 and S2
Слить две области если:

Алгоритмы разбиения и слияния
Недостатки:
Разбиение
Может дать слишком много регионов
Если использовать квадродерево, границы скорее всего будут неверны
Слияние
Долго работает, если начинать с индивидуальных пикселей
Вывод:
Нужен комбинированный метод!

Алгоритм разбиения/слияния
(split and merge)
Идея:
Сначала провести разбиение на небольшие однородные области
Обычно используется принцип квадродерева
Затем слить между собой те из них, которые вместе не нарушат требование однородности
Продолжать до тех пор, пока остаются регионы которые можно объединить

Слияние
Алгоритм разбиения/слияния
(split and merge)

Результат
Алгоритм разбиения/слияния
(split and merge)

Результат
Сравним с разрастанием регионов

Сравним подходы
Сегментация на основе областей
В результате всегда замкнутые границы областей
Использование многоканальных изображений (RGB, RGB + ИК) обычно улучшает результаты
Сегментация на основе границ
Границы обычно лучше локализованы

Алгоритм водораздела
(watershed)
Идея метода:
Вспомним – большие значения градиента соответствуют резким переходам на изображении
Рассмотрим абсолютную величину градиента как карту высот ландшафта
Там где резкие границы – получатся «стены»
Будем «лить воду» в «ямы» и искать получающиеся «озера»

Алгоритм водораздела
Область водораздела, бассейн (catchment basin): область в которой поток из всех точки «стекает» к одной общей точке
Слева – профиль интенсивностей изображения, справа – локальные минимумы определяют бассейны, локальные максимумы – линии водораздела.

Алгоритм водораздела
Алгоритм, как и разбиение дает множество небольших регионов
Очень чувствителен к шуму – ищет все локальные минимумы
Градиент < 10 обращен в 0
Результат по данному градиенту
Абс. величина градиента

Алгоритм «погружения»
Алгоритм «погружения» (immersion) :
Начнем с самых «глубоких» (темных) пикселей
(они определят начальные бассейны)
Для каждой яркости k:
Для каждой связной компоненте пикселей яркости k:
Если прилежит только к одному существующему бассейну
Добавить компоненту к бассейну
Если прилежит более чем к одному существующему бассейну
Пометить как границу (водораздел)
Иначе – создать новый бассейн
Аналог – вода медленно поднимается, пока не погрузятся в нее водоразделы

Алгоритм tobogganing
Идея:
Из каждого пикселя «спускаемся» в локальный минимум среди его соседей
Спускаемся до тех пор, пока есть куда спускаться
Пиксели «спустившиеся» в один минимум – одна область
Как с горы на санках

Алгоритм tobogganing
58 46 50 64 80 88 99 108
80 63 68 106 137 164 185 202
55 113 152 179 202 217 225 227
147 180 199 208 209 202 191 177
192 204 202 190 169 145 122 96
194 186 167 140 109 83 56 63
177 154 124 91 54 41 95 136
159 131 104 81 56 94 142 178
Из каждого пикселя «спускаемся» в локальный минимум среди его соседей
Спускаемся до тех пор, пока есть куда спускаться
Пиксели «спустившиеся» в один минимум – одна область

Алгоритм tobogganing
58 46 50 64 80 88 99 108
80 63 68 106 137 164 185 202
55 113 152 179 202 217 225 227
147 180 199 208 209 202 191 177
192 204 202 190 169 145 122 96
194 186 167 140 109 83 56 63
177 154 124 91 54 41 95 136
159 131 104 81 56 94 142 178
Из каждого пикселя «спускаемся» в локальный минимум среди его соседей
Спускаемся до тех пор, пока есть куда спускаться
Пиксели «спустившиеся» в один минимум – одна область

Tobogganing и водораздел
В зависимости от задачи можно анализировать
само изображение
абсолютную величину его градиента
distance transform изображения (в каждой точке хранится расстояние до ближайшей границы)
Часто генерируют слишком много регионов, как и разделение
Требуется постобработка для слияния
В комбинации с distance transform хорошо для перекрывающихся регионов

Методы теории графов
Теория графов – хороший инструмент для работы с изображениями
Хорошая теоретическая база
Много проработанных методов
Изображение легко «превращается» в граф
Математические модели теории графов хорошо применимы в частности для сегментации

Граф и изображение
Изображение превращается во взвешенный неориентированный граф
Пиксели – вершины графа
Ребра – связи между соседними пикселями
Вес ребер пропорционален «похожести» пикселей

Критерии «похожести» пикселей
По расстоянию
По яркости
По цвету
По текстуре

Создать граф
Разрезать граф
Каждую связную компоненту после разреза рассматривать как отдельную область
Сегментация с помощью разрезов графа

Разрез графа
G=(V,E)
Непересекающиеся подмножества вершин A и B из V
Удаляем все ребра, связывающие A и B
Cut(A,B) – мера «силы связности» множеств A и B

Разрез графа
Разрез графа превращает граф в два несвязанных друг с другом подграфа

Разрез графа
Если множества A и B не заданы заранее – разрезать граф можно по-разному:
Минимальный разрез – разрез, превращающий граф в несвязный, с минимальной суммой весов удаленных ребер

Минимальный разрез хорош
не всегда
На данном рисунке вес ребер графа показан расстоянием между вершинами

Нормализованный разрез графа
(Normalized cut)
Другая мера разреза – измеряет «похожесть» двух групп вершин, нормированную на «объем», занимаемый ими в графе

Минимальный нормализованный разрез
Минимальный нормализованный разрез – разрез, превращающий граф в несвязный, с минимальной величиной NCut
Как его найти?

Матрицы…
D – диагональная матрица n x n:
W is an n x n symmetrical matrix

Можно вывести что:
При условиях:
Если разрешить задача сводится к задаче на собственные значения:

Алгоритм сегментации c помощью normalized cuts
Задать граф на изображении.
Рассчитать матрицы W и D
Решить задачу (D-W)y= λDy, найти вектора с наименьшими собственными значениями
По вектору со вторым наименьшим с.з. разрезать граф на две части
Рекурсивно разбить получившиеся области, если требуется

Пример:

Подытожим:
Рассмотрели следующие методы
Использующие края
Edge-based
Пороговой фильтрации
Thresholding
k-средних
k-means
Разрастания регионов
Region growing
Разделения / слияния
Split and merge
Водораздела
Watershed, tobogganing
Нормализованный разрез графа
Normalized cut

Анализ областей после сегментации
Владимир Вежневец, Антон Конушин
Александр Вежневец
Курс – «Введение в компьютерное зрение»
МГУ ВМК, Graphics & Media Lab,
Осень 2006

Какие параметры формы областей помогут различить объекты на этом примере?

Свойства области
Характеристики границы области
См. предыдущую лекцию
Площадь
Кол-во «дырок» внутри
Центр масс
Периметр
Компактность
Моменты
Ориентация главной оси
Цвет/яркость

Площадь
Кол-во пикселей в области

Центр масс
Центр масс:

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

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

Дискретный момент mij области определяется следующим образом:
- значение пикселя изображения
Моменты

X
Y
7
Площадь
20
33
159
Моменты инерции
64
93
Моменты

Центральные моменты
Инвариантны к переносу
Центр масс области

Центральные моменты

Ориентация главной оси инерции
Главная ось
Центр масс

Моменты Hu
Инвариантны к повороту, переносу, скалированию

Пример

Инвариантные характеристики области
Удлиненность, нецентрированность (эксцентриситет)

Цвет, яркость
Цвет и яркость области тоже хорошие признаки. Варианты
Гистограмма яркости, цветов в данной области
Средняя яркость, средний цвет
Дисперсия яркости, цветов (R, G, B) внутри области

Немного о машинном обучении
Мы рассмотрели сейчас методы «низкого уровня»
Они анализируют небольшое кол-во «простой» информации
При рассказе о машинном обучении будут упомянуты методы производящие более «умный» анализ изображения

Задание
Выдадим на следующей лекции
Выполнятся будем на MATLAB
Всем желающим получить задание нужно будет записаться на лекции
Будет распределение по вариантам