Невозможно отобразить презентацию
Похожие презентации:
Сегментация изображений. Часть II Лекция 8. Анализ и обработка изображений
Сегментация изображений часть II Лекция 8 Анализ и обработка изображений Разрастание регионов (Region growing)
• Простая идея – начиная с некоторого “семени” обходить пиксели и объединять в области пока выполняется условие однородности Критерий однородности
• Гистограмма содержит не больше 1 значительного пика
• Отклонение любого пикселя от средней яркости <Tavg
• Разница между соседними пикселями <T diff
• «Слабая» граница между регионами (только для слияния) diffTqIpIpNqSp<−∈∀∈∀)()()(,avgSqTqINpISp<−∈∀∑∈)(1)( Критерии присоединения к региону
• Близость точки к центру региона
• Близость к соседней точке, присоединенной к региону на предыдущем шаге
• Близость по некоторой статистике региона
• Стоимость кратчайшего пути от точки до центра региона Разрастание регионов 1.if |I(A) – Clavg (B)| > δ and |I(A) – Clavg (C)| > δ - создаем новую область, присоединяем к ней пиксел A 2.if |I(A) – Clavg (B)| ≤ δ xor |I(A) – Clavg (C)| ≤ δ – добавить A к одной из областей 3.if |I(A) – Clavg (B)| ≤ δ and |I(A) – Clavg (C)| ≤ δ : a)|Clavg (B) - Clavg (C)| ≤ δ – сливаем области B и C.
b)|Clavg (B) - Clavg (C)| > δ– добавляем пиксел A к тому классу, отклонение от которого минимально.
Пример δ = 1 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Алгоритм разрастания регионов1 Среднее: 1 Среднее: 1.125δ<−∈∀∑∈SqINpISp)(1)( 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Алгоритм разрастания регионов2δ<−∈∀∑∈SqINpISp)(1)( Пример δ = 1δ<−∈∀∑∈SqINpISp)(1)( Разделение областей 1.Первый шаг – всё изображение это одна область, поместить область в стек 2.Пока стек не пуст– Взять областьS из стека– Проверить область на однородность– Если область неоднородна
• разделить ее, новые области поместить в стек– Если область однородна
• область больше не трогаем Правило разделения областей1
• Распространенный вариант – на 4 части, как квадродеревоS1S3S4S21S22S23S24S1S3S4S21S22S24S23S2 Просто реализовать, но границы получившихся областей вряд ли будут соответствовать границам объектов Пример 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Алгоритм разбиения (split)1 Первое разбиение 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Алгоритм разбиения (split)2 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Второе разбиение Алгоритм разбиения (split)3 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Третье разбиение Алгоритм разбиения (split)4 Гистограммные методы
• Метод поиска моды гистограммы Правило разделения областей2– Найти в гистограмме пики, разделить гистограмму по ним– Для каждой части гистограммы найти связные компоненты – это будут новые области Реализовать сложнее, работает дольше Рекурсивный гистограммный метод Оландера (Ohlander)
• Усовершенствованный гистограммный метод кластеризации
• Используется рекурсивная процедура поиска мод Алгоритм Ота (Ohta)
• Гистограммы для цветных изображений вычисляются по набору переменных– (R+G+B)/3– (R-B)/2– (2G-R-B)/4 Методы дробления-слияния состоят из двух основных этапов:
• дробление
• слияние Слияние областей 1.Первый шаг – каждый пиксель это отдельная область, поместить все области в стек 2.Пока стек не пуст– Взять областьS из стека, для всех соседних областейSi:
• Проверить S’=S USi на однородность
• Если S’ однородна -– СлитьS иSi , S’ поместить в стек,Si из стека удалить, перейти на 2
• Если область не однородна– Пробуем другого соседа Алгоритмы разбиения и слияния1
• Недостатки:– Разбиение
• Может дать слишком много регионов
• Если использовать квадродерево, границы скорее всего будут неверны– Слияние
• Долго работает, если начинать с индивидуальных пикселей Алгоритмы разбиения и слияния2
• Вывод:– Нужен комбинированный метод! Алгоритм разбиения/слияния (split and merge)3
• Идея:– Сначала провести разбиение на небольшие однородные области
• Обычно используется принцип квадродерева– Затем слить между собой те из них, которые вместе не нарушат требование однородности
• Продолжать до тех пор, пока остаются регионы которые можно объединить Слияние 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Алгоритм разбиения/слияния (split and merge)4 Результат12103149810184101631015631015621010 Алгоритм разбиения/слияния (split and merge)5 Результат12103149810184101631015631015621010 Сравним с разрастанием регионов 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Алгоритм водораздела (watershed)
• Идея метода:– большие значения градиента соответствуют резким переходам на изображении– абсолютная величина градиента как карта высот ландшафта– там где резкие границы – получатся «стены»– будем «лить воду» в «ямы» и искать получающиеся «озера» Алгоритм водораздела Область водораздела, бассейн( catchment basin): область в которой поток из всех точек «стекает» к одной общей точке Алгоритм водораздела
• Алгоритм, как и разбиение дает множество небольших регионов
• Очень чувствителен к шуму – ищет все локальные минимумы Градиент < 10 обращен в 0 Результат по данному градиенту Абс.
величина градиента Алгоритм tobogganing1
• Идея:– Из каждого пикселя «спускаемся» в локальный минимум среди его соседей– Спускаемся до тех пор, пока есть куда спускаться– Пиксели «спустившиеся» в один минимум – одна область Алгоритм tobogganing2 58465064808899108 806368106137164185202 55113152179202217225227 147180199208209202191177 19220420219016914512296 194186167140109835663 17715412491544195136 159131104815694142178
• Из каждого пикселя «спускаемся» в локальный минимум среди его соседей
• Спускаемся до тех пор, пока есть куда спускаться
• Пиксели «спустившиеся» в один минимум – одна область Алгоритм tobogganing3 58465064808899108 806368106137164185202 55113152179202217225227 147180199208209202191177 19220420219016914512296 194186167140109835663 17715412491544195136 159131104815694142178
• Из каждого пикселя «спускаемся» в локальный минимум среди его соседей
• Спускаемся до тех пор, пока есть куда спускаться
• Пиксели «спустившиеся» в один минимум – одна область Алгоритм кластеризации ISODATA
• Iterative Self-Organizing Data Analysis Techniques (ИСОМАД в рус.яз.)
• Итерационные разделения-слияния
• Сравнение с гистограммными методами Алгоритм ISODATA0 0.
Задаются параметры, определяющие процесс кластеризации K − число кластеровθN − параметр, с которым сравнивается кол-во образов, вошедших в кластерθs − параметр, характеризующий среднеквадратичное отклонениеθс − параметр, характеризующий компактность I − допустимое число циклов итераций Алгоритм ISODATA1 1.Заданные N образов распределяются по кластерам по правилуjiNiSxcj≠=<∈;
,...,2,1,z-xz-x еслиij 2.Ликвидируются подмножества образов, в состав которых входит менее θN элементов 3.Каждый центр кластера zj локализуется и корректируется∑∈=jSxjxjNz1 Алгоритм ISODATA2 4.Вычисляется среднее расстояние между объектами, входящими в подмножество Sj , и соответствующим центром кластераcSxjNjzxNDj ,...,2,1,1=−=∑∈ 5.Вычисляется обобщенное среднее расстояние между объектами, находящихся в отдельных кластерах, и соответствующими центрами кластеров∑=cNjcDND1 Алгоритм ISODATA3 6.Если a)текущий цикл итерации последний, то θс =0 и переход к шагу 10b)Nc ≥ 2K, то переход к шагу 10c)Nc ≤ K/2, то переход к шагу 7 d)текущий номер итерации − четный, то переход к шагу 10 e)текущий номер итерации − нечетный, то переход к шагу 7 Алгоритм ISODATA4 7.Для каждого кластера вычисляется вектор среднеквадратичного отклонения()∑∈−=jSxijikjijnjjzxN21 где, ,...,,σ 8.В каждом векторе σj отыскивается максимальная компонента σ jmax Алгоритм ISODATA5 9.Если для любого σ jmax выполняются условия σ jmax > θsи()12и)+>NjNDaθ или2/)KNbc≤ то кластер с центром zj расщепляется на два кластера zj+ и zj-:zj+= zj+γjzj-= zj-γjγj =kσ jmax и перейти к шагу 1 иначе перейти к шагу 10 Алгоритм ISODATA6 10.Вычисляются расстояния Dij между всеми парами центров кластеровjiijzD−=
• Те L расстояний Dij , которые меньше θс, ранжируются в порядке возрастания Алгоритм ISODATA7 12.К отсортированным по возрастанию L расстояниямDij применяется процедура слияния: кластеры с центрами zi и zj сливаются (если на текущем шаге итерации к ним не применялось слияние)[]jijizNzNz⋅+⋅+=1* 13.Если текущий цикл итерации − последний, то выполнение алгоритма прекращается, иначе возвращаемся либо к шагу 0 (изменение настроек), либо к шагу 1 Иллюстрация работы алгоритма ISODATA Графовое разбиение Ши (Shi)
• Сегментация на основе– цвета,– текстуры– или любой комбинации этих или других характерных признаков•
• Простая идея – начиная с некоторого “семени” обходить пиксели и объединять в области пока выполняется условие однородности Критерий однородности
• Гистограмма содержит не больше 1 значительного пика
• Отклонение любого пикселя от средней яркости <Tavg
• Разница между соседними пикселями <T diff
• «Слабая» граница между регионами (только для слияния) diffTqIpIpNqSp<−∈∀∈∀)()()(,avgSqTqINpISp<−∈∀∑∈)(1)( Критерии присоединения к региону
• Близость точки к центру региона
• Близость к соседней точке, присоединенной к региону на предыдущем шаге
• Близость по некоторой статистике региона
• Стоимость кратчайшего пути от точки до центра региона Разрастание регионов 1.if |I(A) – Clavg (B)| > δ and |I(A) – Clavg (C)| > δ - создаем новую область, присоединяем к ней пиксел A 2.if |I(A) – Clavg (B)| ≤ δ xor |I(A) – Clavg (C)| ≤ δ – добавить A к одной из областей 3.if |I(A) – Clavg (B)| ≤ δ and |I(A) – Clavg (C)| ≤ δ : a)|Clavg (B) - Clavg (C)| ≤ δ – сливаем области B и C.
b)|Clavg (B) - Clavg (C)| > δ– добавляем пиксел A к тому классу, отклонение от которого минимально.
Пример δ = 1 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Алгоритм разрастания регионов1 Среднее: 1 Среднее: 1.125δ<−∈∀∑∈SqINpISp)(1)( 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Алгоритм разрастания регионов2δ<−∈∀∑∈SqINpISp)(1)( Пример δ = 1δ<−∈∀∑∈SqINpISp)(1)( Разделение областей 1.Первый шаг – всё изображение это одна область, поместить область в стек 2.Пока стек не пуст– Взять областьS из стека– Проверить область на однородность– Если область неоднородна
• разделить ее, новые области поместить в стек– Если область однородна
• область больше не трогаем Правило разделения областей1
• Распространенный вариант – на 4 части, как квадродеревоS1S3S4S21S22S23S24S1S3S4S21S22S24S23S2 Просто реализовать, но границы получившихся областей вряд ли будут соответствовать границам объектов Пример 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Алгоритм разбиения (split)1 Первое разбиение 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Алгоритм разбиения (split)2 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Второе разбиение Алгоритм разбиения (split)3 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Третье разбиение Алгоритм разбиения (split)4 Гистограммные методы
• Метод поиска моды гистограммы Правило разделения областей2– Найти в гистограмме пики, разделить гистограмму по ним– Для каждой части гистограммы найти связные компоненты – это будут новые области Реализовать сложнее, работает дольше Рекурсивный гистограммный метод Оландера (Ohlander)
• Усовершенствованный гистограммный метод кластеризации
• Используется рекурсивная процедура поиска мод Алгоритм Ота (Ohta)
• Гистограммы для цветных изображений вычисляются по набору переменных– (R+G+B)/3– (R-B)/2– (2G-R-B)/4 Методы дробления-слияния состоят из двух основных этапов:
• дробление
• слияние Слияние областей 1.Первый шаг – каждый пиксель это отдельная область, поместить все области в стек 2.Пока стек не пуст– Взять областьS из стека, для всех соседних областейSi:
• Проверить S’=S USi на однородность
• Если S’ однородна -– СлитьS иSi , S’ поместить в стек,Si из стека удалить, перейти на 2
• Если область не однородна– Пробуем другого соседа Алгоритмы разбиения и слияния1
• Недостатки:– Разбиение
• Может дать слишком много регионов
• Если использовать квадродерево, границы скорее всего будут неверны– Слияние
• Долго работает, если начинать с индивидуальных пикселей Алгоритмы разбиения и слияния2
• Вывод:– Нужен комбинированный метод! Алгоритм разбиения/слияния (split and merge)3
• Идея:– Сначала провести разбиение на небольшие однородные области
• Обычно используется принцип квадродерева– Затем слить между собой те из них, которые вместе не нарушат требование однородности
• Продолжать до тех пор, пока остаются регионы которые можно объединить Слияние 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Алгоритм разбиения/слияния (split and merge)4 Результат12103149810184101631015631015621010 Алгоритм разбиения/слияния (split and merge)5 Результат12103149810184101631015631015621010 Сравним с разрастанием регионов 11111112 11111110 31499810 11888410 11666310 11566310 11566210 11111100 Алгоритм водораздела (watershed)
• Идея метода:– большие значения градиента соответствуют резким переходам на изображении– абсолютная величина градиента как карта высот ландшафта– там где резкие границы – получатся «стены»– будем «лить воду» в «ямы» и искать получающиеся «озера» Алгоритм водораздела Область водораздела, бассейн( catchment basin): область в которой поток из всех точек «стекает» к одной общей точке Алгоритм водораздела
• Алгоритм, как и разбиение дает множество небольших регионов
• Очень чувствителен к шуму – ищет все локальные минимумы Градиент < 10 обращен в 0 Результат по данному градиенту Абс.
величина градиента Алгоритм tobogganing1
• Идея:– Из каждого пикселя «спускаемся» в локальный минимум среди его соседей– Спускаемся до тех пор, пока есть куда спускаться– Пиксели «спустившиеся» в один минимум – одна область Алгоритм tobogganing2 58465064808899108 806368106137164185202 55113152179202217225227 147180199208209202191177 19220420219016914512296 194186167140109835663 17715412491544195136 159131104815694142178
• Из каждого пикселя «спускаемся» в локальный минимум среди его соседей
• Спускаемся до тех пор, пока есть куда спускаться
• Пиксели «спустившиеся» в один минимум – одна область Алгоритм tobogganing3 58465064808899108 806368106137164185202 55113152179202217225227 147180199208209202191177 19220420219016914512296 194186167140109835663 17715412491544195136 159131104815694142178
• Из каждого пикселя «спускаемся» в локальный минимум среди его соседей
• Спускаемся до тех пор, пока есть куда спускаться
• Пиксели «спустившиеся» в один минимум – одна область Алгоритм кластеризации ISODATA
• Iterative Self-Organizing Data Analysis Techniques (ИСОМАД в рус.яз.)
• Итерационные разделения-слияния
• Сравнение с гистограммными методами Алгоритм ISODATA0 0.
Задаются параметры, определяющие процесс кластеризации K − число кластеровθN − параметр, с которым сравнивается кол-во образов, вошедших в кластерθs − параметр, характеризующий среднеквадратичное отклонениеθс − параметр, характеризующий компактность I − допустимое число циклов итераций Алгоритм ISODATA1 1.Заданные N образов распределяются по кластерам по правилуjiNiSxcj≠=<∈;
,...,2,1,z-xz-x еслиij 2.Ликвидируются подмножества образов, в состав которых входит менее θN элементов 3.Каждый центр кластера zj локализуется и корректируется∑∈=jSxjxjNz1 Алгоритм ISODATA2 4.Вычисляется среднее расстояние между объектами, входящими в подмножество Sj , и соответствующим центром кластераcSxjNjzxNDj ,...,2,1,1=−=∑∈ 5.Вычисляется обобщенное среднее расстояние между объектами, находящихся в отдельных кластерах, и соответствующими центрами кластеров∑=cNjcDND1 Алгоритм ISODATA3 6.Если a)текущий цикл итерации последний, то θс =0 и переход к шагу 10b)Nc ≥ 2K, то переход к шагу 10c)Nc ≤ K/2, то переход к шагу 7 d)текущий номер итерации − четный, то переход к шагу 10 e)текущий номер итерации − нечетный, то переход к шагу 7 Алгоритм ISODATA4 7.Для каждого кластера вычисляется вектор среднеквадратичного отклонения()∑∈−=jSxijikjijnjjzxN21 где, ,...,,σ 8.В каждом векторе σj отыскивается максимальная компонента σ jmax Алгоритм ISODATA5 9.Если для любого σ jmax выполняются условия σ jmax > θsи()12и)+>NjNDaθ или2/)KNbc≤ то кластер с центром zj расщепляется на два кластера zj+ и zj-:zj+= zj+γjzj-= zj-γjγj =kσ jmax и перейти к шагу 1 иначе перейти к шагу 10 Алгоритм ISODATA6 10.Вычисляются расстояния Dij между всеми парами центров кластеровjiijzD−=
• Те L расстояний Dij , которые меньше θс, ранжируются в порядке возрастания Алгоритм ISODATA7 12.К отсортированным по возрастанию L расстояниямDij применяется процедура слияния: кластеры с центрами zi и zj сливаются (если на текущем шаге итерации к ним не применялось слияние)[]jijizNzNz⋅+⋅+=1* 13.Если текущий цикл итерации − последний, то выполнение алгоритма прекращается, иначе возвращаемся либо к шагу 0 (изменение настроек), либо к шагу 1 Иллюстрация работы алгоритма ISODATA Графовое разбиение Ши (Shi)
• Сегментация на основе– цвета,– текстуры– или любой комбинации этих или других характерных признаков•