1.2 Методы сегментации. Кластеризация

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

В качестве признаков точки изображения можно использовать представление ее цвета в некотором цветовом пространстве, примером метрики (меры близости) может быть евклидово расстояние между векторами в пространстве признаков. Тогда результатом кластеризации будет квантование цвета для изображения. Задав отображение в пространство признаков, можно воспользоваться любыми методами кластерного анализа. Наиболее популярные методы кластеризации, используемые для сегментации изображений - к-средних.

K-средних - это итеративный метод, который используется, чтобы разделить изображение на K кластеров. Базовый алгоритм приведён ниже:

- выбрать K центров кластеров, случайно или на основании некоторой эвристики;

- поместить каждый пиксель изображения в кластер, центр которого ближе всего к этому пикселю;

- заново вычислить центры кластеров, усредняя все пиксели в кластере;

- повторять шаги 2 и 3 до сходимости (например, когда пиксели будут оставаться в том же кластере).

Здесь в качестве расстояния обычно берётся сумма квадратов или абсолютных значений разностей между пикселем и центром кластера. Разность обычно основана на цвете, яркости, текстуре и местоположении пикселя, или на взвешенной сумме этих факторов. K может быть выбрано вручную, случайно или эвристически.

Этот алгоритм гарантированно сходится, но он может не привести к оптимальному решению. Качество решения зависит от начального множества кластеров и значения K.

Основная проблема методов кластеризации, состоит в том, что пространственное расположение точек либо не учитывается совсем, либо учитывается косвенно (например, используя координаты точки как один из признаков). Поэтому обычно после кластеризации точек изображения проводят процедуру выделения связных компонент.

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