Сегментация изображений с применением алгоритмов кластеризации

Михин Андрей Михайлович – студент Национального исследовательского ядерного университета «МИФИ».

Бухтияров Иван Романович – студент Национального исследовательского ядерного университета «МИФИ».

Аннотация: Задача сегментации изображений в наши дни является актуальной, т.к. очень важно уметь распознавать составные части изображения. Решение данной задачи может быть полезно для распознавания элементов одежды человека и построения дальнейшей рекомендательной системы на основе его стиля, для автоматического построения карты, используя снимок спутника, и во многих других случаях. Многие разработчики используют для этого готовые нейронные сети, которые надо периодически переобучать после появления новых данных для обеспечения более качественной работы. Так же нейронным сетям необходимы размеченные данные для обучения, что может являться нецелесообразным или невозможным в ряде задач. Преимуществом методов кластеризации является то, что изначально задача кластеризации является задачей обучения без учителя, т.е. не требует каких-то подготовленных данных.

Ключевые слова: Кластеризация, обработка изображений.

Постановка задачи сегментации изображения

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

В общем виде алгоритм сегментации изображения можно представить в следующем виде:

1. Представление изображение в формате RGB матрицы цветов пикселей.
2. Применение одного из методов сегментации.
3. Интерпретация полученных меток пикселей

Существующие метрики

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

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

Для определения резкости перехода между пикселями можно использовать следующие метрики:

Евклидово расстояние — наиболее распространенное расстояние. Оно является геометрическим расстоянием в многомерном пространстве.

(1)

где k — размерность пространства.

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

(2)

Расстояние городских кварталов (манхэттенское расстояние). Это расстояние является просто средним разностей по координатам. Для этой меры влияние отдельных больших разностей (выбросов) уменьшается (так как они не возводятся в квадрат). Наглядным представлением данной метрики на шахматной доске является количество клеток, которые необходимо пройти Королю без ходьбы по диагоналям.

(3)

Расстояние Чебышева. Это расстояние может оказаться полезным, когда желают определить два объекта как «различные», если они различаются по какой-либо одной координате (каким-либо одним измерением).

(4)

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

(5)

x должно быть>= 1, иначе нарушается неравенство треугольника.

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

Алгоритм k-means

Одним из основных алгоритмов кластеризации, используемых для сегментации изображений, является метод k-средних (k-means). Алгоритм описывается следующими шагами [2]:

1. Инициализация начальных центров кластеров .

2. Распределение пикселей на кластеры относительно их близости к центрам.

3. Пересчёт центров кластеров

(6)

4. Проверка условия продолжения

(7)

5. Если условие выполнено, то конец продолжить с шага 2, иначе конец алгоритма.

Проблемы алгоритма k-means:

• Необходимо заранее знать количество кластеров.
• Алгоритм очень чувствителен к выбору начальных центров кластеров. В следствие этого Не гарантируется достижение глобального минимума суммарного квадратичного отклонения, а только одного из локальных минимумов.

Метод локтя для нахождения оптимального числа кластеров

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

1. Вычисляется кластеризация k-средних для определённых значений k (допустим, от 1 до 10).
2. Для каждого k вычисляется общая сумма квадратов расстояний внутри кластера.
3. Строится график суммы внутрикластерных квадратов в зависимости от выбранного k.
4.  Расположение изгиба (локтя, в честь которого метод получил своё название) будет соответствовать оптимальному количеству кластеров (Рис.1)

Рисунок 1. Демонстрация метода локтя.

Алгоритм Канни

Вторым распространённым алгоритмом является алгоритм Канни [3]. Суть данного алгоритма заключается в обнаружении краёв цветовых зон изображения при подавлении шума. Данный алгоритм можно разделить на следующие этапы:

1. Сглаживание изображения для уменьшения шумов с помощью оператора Канни

(8)

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

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

Сегментация изображений

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

Для начала была проведена сегментация изображения алгоритмом k-means без использования метода локтя с числом кластеров k=3

Рисунок 2. Демонстрация работы алгоритма k-meansбез применения метода локтя.

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

Рисунок 3. Демонстрация работы алгоритма k-means с применением метода локтя.

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

Рисунок 4. Демонстрация выделения контуров с использованием алгоритма Канни.

Список литературы

1. Прэтт У. - Цифровая обработка изображений — Мир, 1982
2. Яншин В.В Анализ и обработка изображений. Принципы и алгоритмы — Машиностроение, 1994
3. Клетте Рейнхард Компьютерное зрение. Теория и алгоритмы — ДМК Пресс, 2015
4. Луис Педро Коэльо, Вилли Ричард Построение систем машинного обучения на языке Python – ДМК Пресс, 2016
5. Bryan WC Chung - Pro Processing for Images and Computer Vision with OpenCV - Apress Media, 2017
6. S. Gupta, R. Girshick, P. Arbelaez, and J. Malik. Learning rich features from RGB-D images for object detection and segmentation. — ECCV. Springer, 2014