Сегментация

Автор: | 31.07.2018

Сегментация — выделение областей, однородных по какому-либо критерию, например по яркости.

Существуют два альтернативных подхода к решению задачи сегментации:

Первый подход основан на идее “разрывности” свойств точек изображения при переходе от одной области к другой.  При этом выделение границ областей позволяет идентифицировать и сами области.

Второй подход реализует стремление выделить точки изображения, однородные по своим локальным свойствам, и объединить их в область, которой позже будет присвоено имя или смысловая метка. Этот подход можно подразделить на следующие:

Более подробно см. Исследование методов сегментации изображений.

Морфологический подход

Морфологические преобразования рассмотрены в разделе Предварительная обработка изображений. Пример использования морфологической дилатации для сегментации изображения показан на рисунке:

Процедура наращивания области сводится к проходу шаблоном по изображению, начиная с некоторой точки p.  Процедура завершается тогда, когда на текущем шаге не было не обнаружено ни одной новой связной компоненты.

Разбиение по признаку однородности

Известен ряд методов, основанных на процедуре выращивании областей, которая состоит в группировке элементов и мелких областей изображения в более крупные, начиная из так называемых «центров кристаллизации». Проблемы таких методов — выбор критерия близости и признака остановки процесса выращивания областей.

Алгоритм «Region growth»  (Выращивание областей)

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

Альтернативой выращиванию является методы, основанные на первичном разбиении изображения на множество малых непересекающихся областей и осуществлении последующего их слияния и разделения.

Алгоритм «Split & Merge» (Разделение и слияние):

  • большие неоднородные области разбиваются на более мелкие области, которые могут быть однородными.
  • соседние области сравниваются и объединяются, если они достаточно близки по некоторому свойству.

Область изображения делится на 4 области. Затем каждая делится еще на 4.  Этот процесс, продолжается до определенного предела. Как правило, этот предел налагается из-за соображений хранения или ограничения времени обработки или из-за разрешения устройства вывода. Пиксель — это наименьшая область деления.

Алгоритм «WaterShed»  (Cегментация по водоразделам)

В предыдущих 2-х алгоритмах явно не отражены проблемы выбора критериев близости и признака остановки процесса выращивания (деления) областей. Эта проблема частично решена в алгоритме «WaterShed».

В алгоритме  «Region growth» исходные пиксели для наращивания областей выбирались произвольно. В этом алгоритме они выбираются по минимальным значениям интенсивности. При этом количество исходных пикселей (соответственно и областей) определяется заведомо.

Наращивание областей происходит параллельно, поднятием уровня интенсивности до тех пор, пока не установится конкуренция по установлению близости между соседними областями.

Этот метод также можно объяснить метафорой, основанной на поведении воды в ландшафте. Когда идет дождь, капли воды, падающие в разных регионах, будут следовать вниз по склонам.

Как только на каком-то участке вода достигает локального максимума, там строится перегородка (создается граница области), при этом вода продолжает заполняться вплоть до достижения глобального максимума.

В этом алгоритме «локальные минимумы ландшафта» (исходные пиксели областей) определяются предварительно,  а локальные и глобальный максимумы (вершины ландшафта) определяются в процессе заполнения областей.

Классификация в пространстве признаков

Классификация в пространстве признаков заключается в выборе отображения набора входных данных в некоторое многомерное пространство признаков и последующее решение классической задачи кластеризации — разбиении выбранного пространства на классы, базируясь на плотности распределения в нем. Эти методы особенно удобны, когда заранее известно количество классов объектов, содержащихся в изображении, но могут определять количество классов и автоматически (метод Mean Shift).

Метод к-средних (k-means)

Необходимо минимизировать суммарное квадратичное отклонение точек кластеров от центров (центроидов) этих кластеров.

 

  1. Из множества пикселей выбираем те пиксели, которые будут центроидами соответствующих k кластеров.
    Выборка начальных центроидов может быть как рандомной так и по определенному алгоритму.
  2. Входим в цикл, который продолжается до тех пор, пока центроиды кластеров не перестанут изменять свое положение.
  3. Обходим каждый пиксель и смотрим, к  центроиду какого кластера он является близлежащим.
  4. Нашли близлежащий центроид? Привязываем пиксель к кластеру этого центроида.
  5. Перебрали все пиксели? Теперь нужно высчитать новые координаты центроидов k кластеров.
  6. Теперь проверяем координаты новых центроидов. Если они соответственно равны предыдущим центроидам, выходим из цикла, если нет, возвращаемся к пункту 3.

Метод среднего сдвига (Mean Shift)

В отличие от  алгоритма K-Means, метод Mean Shift не требует указания количества кластеров заранее. Количество кластеров определяется алгоритмом по исходным данным. Направление к ближайшему кластерному центроиду определяется тем, где находится большая часть ближайших точек.

Рассмотрим пример. В нем синие точки — исходные точки данных, а красные — центроиды этих точек на каждой итерации.

Начальное состояние. Красные и синие точки данных полностью перекрываются. Т.е., количество кластеров соответствует количеству точек.


Итерация 1. Красные точки приближаются к своим кластерам. Похоже, будет 4 кластера.


Итерация 2. Левый и верхний правый кластеры, похоже, достигли схождения признаков уже по двум итерациям. Центральный и нижний правый кластеры выглядят так, будто они сливаются в один, поскольку их центроиды стали ближе.


Итерация 3. Без особых изменений в левом и верхнем правом кластерах, положение их центроидов уточняется. Остальные два кластера имеют центроиды уже совсем близко друг от друга. По мере сближения точки этих кластеров все больше влияют на смещение их центроидов. Очевидно кластеры сливаются в один.

Итерация 4. Все кластеры определились.

Итерация 5. Алгоритм останавливается здесь, так как никаких изменений не обнаружено для всех центроидов.

Результат. Meanshift обнаружил 3 кластера.

Выше была продемонстрирована общая картина того, как Meanshift работает. Теперь давайте посмотрим, что происходит с каждой точкой, и обобщим алгоритм на все точки.

Ближайшим кластером точек может быть юг или север от начальной точки данных.

Красный путь показывает, что после каждой итерации точка движется ближе к центру южного кластера. Можно заметить, что шаг перемещения постепенно уменьшается после каждой итерации, Это связано с тем, что точка приближается к центроиду кластера.

Немного математики. Что вам для нее необходимо:

  • Функция N (x) для определения соседей точки x ∈ X.
  • Гауссовское ядро K (d), d — расстояние между двумя точками данных.

Теперь, с вышесказанным, это алгоритм среднего сдвига для набора точек данных X:

1. Для каждого datapoint x ∈ X найдем соседние точки N (x) x.

2. Для каждого datapoint x ∈ X вычислим средний сдвиг m (x) из этого уравнения:

3. Для каждой datapoint x ∈ X обновить x ← m (x).
4. Повторить 1. для n_itations или пока точки не перестанут перемещаться.

Самая важная часть — вычисление среднего сдвига m (x).  Обратите внимание, что обведенные красным части по существу одинаковы:

Давайте заменим их на Wi, тогда формула станет следующей:

По сути, meanshift просто вычисляет средневзвешенное значение.

Подведем итог: алгоритм находит набор близлежащих точек, которые влияют на дату-точку, а затем сдвигают ее туда, где находится большинство точек, а ближайшие точки имеют большее влияние, чем остальные точки. Это повторяется для всех datapoints, пока не прекратится движение.

Сравнение методов K-Means и Meanshift

Meanshift очень похож на K-Means, оба метода перемещают точку ближе к кластерным центроидам. В чем отличие?

Meanshift не требует от пользователя указания количества кластеров. А в некоторых случаях не так просто угадать правильное количество кластеров. Однако, Meanshift определяет количество кластеров, подходящих для предоставленного набора данных, за счет большой затраты времени.

 

Автор: Николай Свирневский

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *