|
СЕГМЕНТАЦИЯ ЦВЕТНЫХ ИЗОБРАЖЕНИЙ СРЕДСТВАМИ
КЛАСТЕРНОГО АНАЛИЗА
Е.В. Глухов
Военно-технический институт Национальной гвардии Республики
Узбекистан
Сегментация изображения – это процесс разделения изображения на
множество непересекающихся областей, объединение которых даст целое
изображение. К областям, получаемым в результате сегментации,
предъявляются следующие требования:
1. Области должны быть однородны относительно определенных
характеристик.
2. Внутренние части областей должны быть простыми без большого
количества маленьких отверстий.
3. Смежные области должны существенно отличаться по значениям
выбранных характеристик, относительно которых они считаются
однородными.
4. Границы каждого сегмента должны быть простыми, пространственно
точными.
Сегментация является наиболее критической процедурой компенсации
движения, поскольку ее результаты влияют в дальнейшем на все последующие
действия, связанные с анализом изображения: представление выделенных
объектов, измерение признаков, а также другие задачи более высокого уровня
(классификация объектов, интерпретация сцен и т.д.).
Задачу сегментации можно рассматривать как задачу поиска кластеров,
соответствующих однородным областям. Каждому пикселю изображения
ставится в соответствие вектор-признак и выполняется кластеризация в
пространстве этих признаков. Область формируется из пикселей, векторы-
признаки которых вошли в соответствующий кластер.
Задача автоматического выбора количества кластеров является важной
для всех алгоритмов кластеризации. Для определения количества кластеров
сначала выполняется кластеризация при заданном максимальном количестве
кластеров Q, а после этого применяются функции оценки для выбора
оптимального количества кластеров Ω≤Q. Этот алгоритм использует
алгоритмы кластерного анализа для сегментации цветного изображения
размером m×n пикселей, описанного в системе RGB.
Для преобразования исходного изображения в множество векторов-
признаков в процессе экспериментальных исследований для каждого пикселя
с координатами (i, j) были отобраны следующие девять признаков:
R
ij
, G
ij
,B
ij
– соответственно значения яркости красного, зеленого и синего
цветов пикселя с координатами i; j (1 ≤ i ≤ m, 1 ≤ j ≤ n); Grad
Rij
, Grad
Gij
, Grad
Bij
– значения градиента яркости пикселя вдоль каждой из трех цветовых осей;
D
Rij
= maxΔR
ij
/minΔR
ij
– отношение значений максимальной и
минимальной разности яркостей красного цвета между пикселем i, j и его
253
соседями в окрестности [3x3]; D
Gij
= maxΔG
ij
/minΔG
ij
– отношение значений
максимальной и минимальной разности яркостей зеленого цвета между
пикселем i, j и его соседями; D
Bij
= maxΔB
ij
/minΔB
ij
– отношение значений
максимальной и минимальной разности яркостей синего цвета между
пикселем i, j и его соседями (в случае, если minΔR
ij
=0, D
Rij
= maxΔR
ij
).
Алгоритм состоит из следующих этапов:
Этап 1. Построение признакового описания изображения. Каждому
пикселю (i, j) со значениями яркостей (R
ij
,G
ij
,B
ij
) необходимо поставить в
соответствие его образ (вектор-признак) V
ij
:
V
ij
=(R
ij
,G
ij
,B
ij
,Grad
Rij
,Grad
Gij
,Grad
Bij
,D
Rij
,D
Gij
,D
Bij
)
и сформировать множество S, которое состоит из m×n образов:
S= {V
ij
, i=1,2,…m; j=1,2,…,n}.
В нем каждый образ соответствует одному пикселю исходного
изображения.
Этап 2. Кластеризация. Кластеризация признакового пространства
осуществляется с помощью алгоритма k–средних.
Алгоритм k-средних – наиболее популярный метод
кластеризации
. Он
разбивает
множество
элементов
векторного пространства
на заранее
известное число кластеров k. Действие алгоритма таково, что он стремится
минимизировать
дисперсию
на точках каждого кластера:
где k – число кластеров, S
i
– полученные кластеры,i=1, 2, …k и μ
i
–
центры масс векторов
i
j
S
x
.
Основная идея заключается в том, что на каждой
итерации
перевычисляется
центр масс
для каждого кластера, полученного на
предыдущем шаге, затем векторы разбиваются на кластеры вновь в
соответствии с тем, какой из новых центров оказался ближе по выбранной
метрике
. Алгоритм завершается, когда на какой-то итерации не происходит
изменения кластеров.
Этап 3. Постобработка. На сегментированном изображении кластеру в
признаковом пространстве могут соответствовать несколько мелких областей.
Поэтому требуется постобработка полученных результатов, которая
заключается в следующем. Анализируются всевозможные пары кластеров, и
вычисляются расстояния между их центрами. Вычисляется среднее
расстояние d
s
между кластерами. Если расстояние между центрами двух
кластеров меньше чем среднее расстояние d
s
, и при этом количество образов,
254
входящих в один из кластеров, меньше одной трети количества пикселей
другого кластера, то такие кластеры объединяются в один. В случае
объединения
вычисляется
центр
вновь
созданного
кластера
и
пересчитываются расстояния между центрами кластеров. В результате этого
количество кластеров уменьшается с Q до Ω.
Разработанные алгоритмы могут использоваться в системах обработки
и сжатия цифровых изображений.
Do'stlaringiz bilan baham: |
