Методы, основанные на кластеризации

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

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

Алгоритм k-средних — это итеративный метод, который используется, чтобы разделить изображение на K кластеров. Опишем словесно алгоритм следующим образом:

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

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

3. Заново вычислить центры кластеров, усредняя все пиксели в кластере.

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

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

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

Применить метод k-средних к изображению можно рассматривая пространство яркостей пикселей. В этом случае кластеризация является одномерной задачей по одному признаку – яркости. Одномерное пространство яркостей пикселей, хорошо представимо гистограммой (рис. 5.10).

а)

б)

в)

Рис. 5.10. Применение k-средних для сегментации изображений по яркости

Для приведенного изображения (рис. 5.10, а) метод k-средних для K равного двум определит два кластера с центрами в точках C1 и С2 (рис. 5.10, б), и изображение будет разделено на два сегмента, закрашенных черным и белым цветом (рис. 5.10, в). В этом случае можно сказать, что метод k-средних провел пороговую фильтрацию и получил бинарное изображение.

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

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

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

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