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

1 Сегментация изображений Часть 2

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

3 Разметка связанных областей Разметка необходима для дальнейшего анализа областей. Методы объединения областей Разрастание областей (1-2 проходные) Уникальное построение области (1 проходные)

4 Разметка связанных областей Разрастание областей ШАГ 1 Проводим линейный поиск до обнаружения объекта ШАГ 2 Обойти все пиксели и объединять в области с учетом вида связанности ШАГ 3 Проверка конфликтной ситуации ШАГ 4 Поиск нового объекта и выполнение шага 2 В случае обнаружения конфликтной ситуации необходимо провести переразметку конфликтных областей переразметка происходит с учетом эквивалентностей областей

5 Алгоритм «Рекурсивная разметка связных областей» ч1 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++); }

6 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); } Алгоритм «Рекурсивная разметка связных областей» ч2

7 ОДНОПРОХОДНЫЙ АЛГОРИТМ ВЫДЕЛЕНИЯ ОБЛАСТЕЙ ШАГ 1 поиск фрагмента ШАГ 2 проверка связей маркировочным окном в указанном порядке ШАГ 3 запись связей в таблицу по возрастанию значения маркера ШАГ 4 проверка окрестности элемента и замещение одиночно-связанных фрагментов из таблицы ШАГ 5 расчет плотности распределения для фрагментов Пример маркировки фрагмента изображения

8 Разрастание регионов (Region growing) Простая идея – начиная с некоторого семени обходить пиксели и объединять в области пока выполняется условие однородности –Критерий однородности Гистограмма содержит не больше 1 значительного пика Отклонение любого пикселя от средней яркости < T avg Разница между соседними пикселями < T diff

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

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

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

12 Метод разделения областей ШАГ 1 Всё изображение это одна область, поместить область в стек ШАГ 2 Пока стек не пуст ШАГ 2.1 Взять область S из стека ШАГ 2.2 Проверить область на однородность ШАГ 2.3 Если область неоднородна разделить ее, новые области поместить в стек ШАГ 2.4 Если область однородна область больше не трогаем

13 Метод разделения областей Правило разделения областей (квадродерево) Распространенный вариант – на 4 части, как квадродерево S1S1 S3S3 S4S4 S 21 S 22 S 23 S 24 S1S1 S3S3 S4S4 S 21 S 22 S 24 S 23 S S2S2 Просто реализовать, но границы получившихся областей вряд ли будут соответствовать границам объектов

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

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

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

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

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

19 Метод слияния областей ШАГ 1 каждый пиксель это отдельная область, поместить все области в стек ШАГ 2 Пока стек не пуст ШАГ 2.1 Взять область S из стека, для всех соседних областей S i : ШАГ 2.2 Проверить S=S U S i на однородность ШАГ 2.3 Если S однородна – Слить S и S i, S поместить в стек, S i из стека удалить, перейти на шаг 2 ШАГ 2.4 Если область не однородна Пробуем другого соседа

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

21 Алгоритм «фагоцита» S1S1 S2S2

22 Слить две области если: где P 1 и P 2 – периметры областей S 1 and S 2 Слить две области если:

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

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

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

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

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

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

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

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

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

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

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

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

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