Nonparametric clustering is attractive because of its ability to discover arbitrary shaped clusters. Mean-shift is a well-known mode-seeking procedure that is capable of producing accurate results. However, it has high time complexity. On the other hand, grid-based methods are computationally efficient, but their accuracy is limited by the grid structure. A novel clustering algorithm that combines grid-based HCA algorithm with mean-shift procedure is proposed. Experiments show significant improvement of clustering accuracy over HCA and high computational efficiency.
Рылов С.А.
Институт вычислительных технологий СО РАН, Новосибирск Непараметрические алгоритмы кластеризации позволяют выделять кластеры сложной формы. Однако вычислительная трудоемкость распространенных методов затрудняет их применение к обработке изображений. Сеточные алгоритмы кластеризации являются вычислительно эффективными, но при этом точность выделения кластеров зависит от сеточной структуры. В работе предлагается новый алгоритм кластеризации, основанный на сеточном алгоритме HCA и использовании процедуры среднего сдвига для уточнения границ кластеров. Экспериментальные исследования показывают увеличение точности кластеризации и демонстрируют высокую вычислительную эффективность алгоритма.
Ключевые слова: сеточный алгоритм кластеризации, непараметрический подход, процедура среднего сдвига, сегментация изображений.
Введение. При решении целого ряда прикладных задач возникает необходимость кластеризации больших массивов данных. Например, использование алгоритмов кластеризации является одним из наиболее распространенных подходов к сегментации мультиспектральных спутниковых изображений [1]. При этом априорные сведения о вероятностных характеристиках классов, а также обучающие выборки, как правило, отсутствуют. В этих условиях наиболее подходящими являются непараметрические алгоритмы, которые не требуют жестких предположений о виде функции плотности распределения и позволяют выделять кластеры сложной формы [2,3]. Однако они не получили распространения на практике из-за свойственной им высокой вычислительной трудоемкости. Применение сеточного подхода, при котором пространство признаков разделяется на конечное число ячеек, позволяет добиться высокой вычислительной эффективности, но при этом точность выделения кластеров сильно зависит от сеточной структуры [4].
В данной работе предлагается новый непараметрический алгоритм кластеризации, основанный на сеточном алгоритме HCA и использовании процедуры «среднего сдвига» (Meanshift) для уточнения границ кластеров. Комбинация этих подходов позволяет получить одновременно высокую точность разделения кластеров и высокое быстродействие.
Краткое описание сеточного алгоритма кластеризации HCA. Предлагаемый алгоритм основывается на иерархическом сеточном алгоритме кластеризации HCA [5], который обладает высокой вычислительной эффективностью и способен выделять кластеры сложной формы. Далее приведено его краткое описание.
Пусть множество объектов X состоит из векторов, лежащих в пространстве признаков Rd : как
X {xi (xi1,..., xid ) Rd ,i 1, N} , и ограниченных гиперпараллелепипедом [l1, r1] ... [l d , r d ] : l j min xi X xij , r j max xi X xij . Сеточная структура определяется разбиение пространства признаков на клетки гиперплоскостями: x j (r j l j ) i / m l j , i 0,..., m, где m – число разбиений Ω по каждой размерности. Множество клеток, смежных с B , обозначается через AB . Плотность DB клетки B определяется как число элементов множества X , попавших в клетку B .
Непустая клетка Bi непосредственно связна с непустой клеткой B j (Bi B j ) , если B j – максимальная по номеру клетка, удовлетворяющая условиям: B j arg max BkABi DBk и DBj DBi . Непустые смежные клетки Bi и B j непосредственно связны (Bi B j ) , если такие, что k1 i, kl j и для всех p 1,..., l 1 выполнено Bkp Bkp1 . Введение отношения связности порождает разбиение множества непустых клеток на компоненты связности G1,,GS . Под компонентой связности понимается максимальное множество попарно связных клеток. Представителем компоненты связности G называется максимальная по номеру клетка Y (G) , удовлетворяющую условию Y (G) arg max BG DB .
Выделенные компоненты связности соответствуют одномодовым кластерам, а их представители – модам плотности этих кластеров. Далее, для построения иерархии между компонентами вводится специальная метрика.
Расстояние hij между смежными компонентами Gi и G j определяется по формуле hij min Pijij 1 min BktPij DBkt / min( DYi , DYj ) , где ij {Pij} – множество всех цепочек, связывающих представителей компонент связности, Pij Y Gi Bk1 ,..., Bkt , Bkt1 ,..., Bkl Y Gj таких, что для всех t 1,..., l 1 : 1) Bkt Gi Gj ; 2) Bkt , Bkt1 – смежные клетки.
После формирования матрицы расстояний между смежными компонентамиhij , к ней применяется алгоритм построения дендрограммы методом ближайшего соседа (SLINK). В результате получается иерархическая структура на множестве компонент связности.
Алгоритм HCA при низких вычислительных затратах позволяет выделять сложные многомодовые кластеры, а также получать иерархическое представление результатов. Однако точность разделения кластеров зависит от сеточной структуры, что может приводить к ошибкам, особенно при неудачном выборе параметра масштаба сетки m .
Краткое описание процедуры «среднего сдвига». Для непараметрической оценки плотности распределения данных одной из наиболее широко используемых является оценка Розенблатта–Парзена [6]. Плотность оценивается как суммарное влияние элементов выборки, при этом вклад каждого элемента описывается колоколообразной функцией (ядром) K(x) , зависящей от расстояния до этого элемента. Формула для вычисления оценки плотности f (x) с параметром сглаживания h в произвольной точке x имеет вид:
1 N fˆh (x) x xi .
Nhd i1 K h В качестве K(x) можно использовать классическое ядро Гаусса:
KG x h xi exp x2h2xi .
Однако на практике, в целях сокращения вычислительных затрат используются ограниченные ядра, такие как например ядро Епанечникова:
KEp x h xi 1 x h2xi 2 I x xi h2 , где I(x) – индикаторная функция. В данном подходе кластеры соответствуют локальным максимумам функции оценки плотности (модам). А элементы данных относятся к кластерам с помощью процедуры «среднего сдвига» (Mean-shift) [3,7], сходящейся по градиенту к соответствующему локальному мещается в точку сдвига xk1 m(xk ) вплоть до сходимости, где: m(x) iN1 xi K (x xi ) .
iN1 K (x xi ) Вектор m(x) x называется вектором «среднего сдвига» и его направление совпадает с направлением максимального роста плотности в точке x .
Алгоритмы кластеризации на основе использования процедуры среднего сдвига позволяют получать качественные разбиения, однако основной проблемой для использования этого подхода при обработке изображений является высокая вычислительная сложность [3,6-8].
Новый алгоритм кластеризации на основе комбинации сеточного подхода и процедуры среднего сдвига. Предлагаемый алгоритм основан на использовании сеточного алгоритма кластеризации HCA, при этом к элементам граничных клеток применяется процедура «среднего сдвига», в результате чего происходит уточнение границ получаемых кластеров. Далее приведено описание разработанного алгоритма HCA-MS.
На первом этапе происходит выполнение представленного выше алгоритма HCA с заданным параметром сетки m. В результате на сеточной структуре выделяются компоненты связности, на множестве которых строится иерархия.
На втором этапе осуществляется индексирование элементов данных по клеткам, позволяющее иметь быстрый доступ к списку элементов произвольной клетки.
На третьем этапе рассматриваются непустые клетки, находящиеся на границах компонент связности (т.е. такие, для которых существует смежная клетка, принадлежащая другой компоненте). К каждому элементу такой клетки применяется процедура «среднего сдвига» с ограниченным ядром и параметром h, равным ширине клетки в сеточной структуре. При этом для поиска элементов в радиусе h достаточно перебрать элементы только из смежных клеток. Данный процесс останавливается, если рассматриваемый элемент перемещается в другую непустую клетку. Если новая клетка принадлежит другой компоненте связности, то элемент перемещается в эту компоненту. Максимальное число итераций ограничивается параметром.
После коррекции границ между компонентами связности, соответственно оказываются скорректированными и границы получаемых кластеров на всех уровнях иерархии.
С точки зрения реализации предложенного алгоритма можно отметить следующие детали. 1) Максимальное число итераций процедуры «среднего сдвига» было ограничено тремя. Данное значение было выбрано эмпирически на основе экспериментальных исследований. 2) В процессе работы алгоритма формируется и используется таблица весов (число повторений элементов с совпадающими значениями векторов признаков). Для изображений характерна высокая частота повторяемости векторов спектральных яркостей, поэтому использование весов существенно сокращает вычислительные затраты. При этом значения всех признаков приводятся к диапазону [0, 255] с 256-ю уровнями квантования. 3) Обработку граничных клеток можно проводить независимо друг от друга, поэтому третий этап был распараллелен для выполнения на ядрах центрального процессора.
Экспериментальные исследования. В данном разделе представлены результаты экспериментальных исследований предложенного алгоритма HCA-MS на модельных данных и изображениях. Приведено сравнение времени работы и точности кластеризации алгоритмов HCA-MS, HCA и Mean-shift.
Указанные алгоритмы были реализованы на языке программирования Java. Вычисления проводились на ПЭВМ с процессором Intel Core i5, 3.5 ГГц (4 ядра). При реализации алгоритма Mean-shift также использовалось индексирование элементов данных по клеткам, таблица весов и распараллеливание. Максимальное число итераций было ограничено десятью. Эксперимент 1. Использовались двумерные модельные данные, в которых один кластер, описываемый нормальным распределением, окружен двумя кластерами в форме колец (рис. 1,в) [9]. Алгоритм кластеризации Mean-shift не способен выделить многомодовые кластеры в форме колец. В свою очередь алгоритм HCA позволяет успешно выделить все три кластера, однако допускает ошибки при неудачном выборе параметра сетки: при m=30 точность кластеризации составляет 98.21% (рис. 1,а); при m=42 допущена ошибка в 3 точках (рис. 1,б); а при m=46 получена точность 100% (рис. 1,в). Использование предложенного алгоритма позволяет скорректировать ошибки, вызванные сеточным эффектом: в результате работы HCA-MS во всех трех случаях получается безошибочный результат (рис. 1,в).
Эксперимент 2. На рис. 2,а представлена модель с тремя сильно пересекающимися нормально-распределенными кластерами [9]. На рис. 2,б представлен результат кластеризации этой модели алгоритмом HCA при m=20, точность составила 94.93%. В данном случае точность можно повысить, используя более мелкую сетку: например, при m=40 точность – 96%. Однако, измельчение сетки может быть недопустимо при выделении кластеров сложной структуры. В тоже время, алгоритм HCA-MS при m=20 демонстрирует точность 96.4% (рис. 2,в). Алгоритм Mean-shift достигает точности 96.33% при h=27.
а б в Рис. 1. Результаты кластеризации модельных данных алгоритмом HCA при m=30 (а), m=42 (б), m=46 (в) и результат кластеризации HCA-MS при тех же параметрах (в).
а б в Рис. 2. Результаты кластеризации модельных данных (а) алгоритмом HCA (б)
и алгоритмом HCA-MS при m=20 (в).
Эксперимент 3. В таблице ниже приведено сравнение времени работы алгоритмов HCA-MS, HCA и Mean-shift на изображениях разного размера. В эксперименте использовались как цветные фотоизображения, так и мультиспектральные снимки, полученные со спутника WorldView-2 (кластеризация проводилась по 4-м каналам: 1, 3, 5, 7). Обрабатывавшиеся изображения [10] представлены на рис. 3 (в том же порядке, как в таблице). Параметры алгоритмов (m и h) были выбраны исходя из желания получить адекватные и схожие результаты сегментации. Результаты эксперимента показывают, что предложенный алгоритм характеризуется существенно меньшей вычислительной трудоемкостью по сравнению с алгоритмом Mean-shift и позволяет обрабатывать цветные изображения большого размера за несколько секунд, а мультиспектральные – за несколько минут.
Заключение. В работе предложен алгоритм кластеризации, основанный на сеточном иерархическом алгоритме HCA и использовании процедуры «среднего сдвига» для уточнения границ кластеров. Результаты экспериментов на модельных данных показывают, что предложенный алгоритм позволяет исправлять ошибки, обусловленные сеточным эффектом, тем самым повышая точность кластеризации и упрощая процедуру настройки параметра сетки m. Вычислительная эффективность алгоритма HCA-MS позволяет применять его к мультиспектральным спутниковым изображениям большого размера (состоящим из миллионов пикселей).
В дальнейшем планируется проверить, насколько значимый эффект оказывает уточнение границ кластеров на качество результатов сегментации спутниковых изображений, а также реализовать предложенный алгоритм для выполнения на графических процессорах.
ЛИТЕРАТУРА [1] [2] [3] [4] [5] [6] [7] [8]