Последнее изменение: 27 марта 2013  12-15



ИНФОРМАЦИОННЫЕ РЕСУРСЫ 


For English version click here

 

Иерархический кластерный алгоритм для автоматизации распознавания данных дистанционного зондирования

Сидорова В.С.

 
Краткая аннотация

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

The histogram cluster algorithm, which creates hierarchy of distributions with clusters separated best, is proposed. The new hierarchical algorithm optimizes average cluster separability at the choice of the different quantizing nets system for subareas of feature vector space. It allows us to study the structure of the data and get a small number of well-separated clusters. Application to unsupervised classification of land cover data is illustrated.

Алгоритм реализован в программной среде системы объектно-ориентированного программирования Visual C++ версии 5.0 фирмы Microsoft c библиотекой классов MFC, разработанной для ОС Windows. При разработке программы  использовался механизм многодокументного интерфейса MDI.

Спецификой рассматриваемых многоспектральных данных дистанционного зондирования Земли является их большой объем, высокая плотность и значительная корреляция для различных типов покрытия земной поверхности. Гистограмма рассматривается как аппроксимация плотности вероятности векторов признаков. Быстрый непараметрический алгоритм Нарендры разделяет векторное пространство признаков по унимодальным кластерам, модальные векторы которых соответствуют локальным максимумам гистограммы, а границы кластеров проходят по долинам гистограммы, то есть по областям низкой плотности векторов. Описание алгоритма Нарендры [1] и демонстрационная версия его применения для классификации спутникового изображения приведены на сайте
http://ipl.sscc.ru/lab/Weblab/LeraKlas/DEMRU/DemonRu.htm
.

Для сокращения объема данных и уменьшения числа кластеров  алгоритм Нарендры предполагал предварительное квантование дискретного векторного пространства. В [2] было предложено автоматизировать выбор, основываясь на оценке разделимости полученных кластеров. В [2] были также определены мера изолированности  для унимодального кластера и мера качества распределения в целом  по K кластерам. Для сомкнутых унимодальных кластеров мера удовлетворяет требованиям, предъявляемым к мерам качества классификации в задачах кластерной достоверности. Природа классифицируемых объектов, – типов покрытия земной поверхности, – такова, что подавляющая часть спектральных  признаков составляют тесно сомкнутые кластеры.

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

Пример 1

  Рассмотрим фрагмент изображения земной поверхности, полученного со спутника NOAA  24 апреля 2003г.  на рис.1 слева. Верхнюю часть изображения занимают тающие снега, внизу – оттаявшая поверхность. На рис. 1 справа вверху в указанном квадрате классификация тающего снега, выполненная Гидрометцентром по данным наземных измерений.  На рис.1 справа внизу кластерная карта, построенная предложенным иерархическим алгоритмом (кластеризация по двум каналам: ближнему инфракрасному R и голубому видимого спектра B).  Показанная классификация соответствует минимуму меры 0.07, число кластеров всего K =13. Минимум получен для четвертого этапа иерархии. При этом число уровней квантования n для заснеженной области достигло n = 23, а для оттаявшей n = 48. Для снегов получено хорошее соответствие с классификацией схемы рис.1b: четыре кластера относятся к тающему снегу. К оттаявшей поверхности относятся четыре кластера. Кластер 13 соответствует хвойным борам. Кластер 11, видимо, связан с высотой рельефа, его границы на карте близки к границам Казахского мелкосопочника.

Для сравнения: достижение полученной детальности оттаявшей части (n = 48) основным алгоритмом (без иерархии) приводит к K=55 кластерам и значению меры разделимости 0.43.

  1

 Пример 2

Для первого уровня иерархии минимум меры изолированности кластеров, равный 0.14, получен для 16 уровней квантования, семи кластеров. На рис. 4a карта кластеров. Объекты, относящиеся к водным поверхностям, лугам и пескам выделились в отдельные кластеры. Почти все лесные объекты попали в один большой кластер 1. На рис. 4b  показана классификация второго этапа иерархии, число подкластеров 16.

На рис.3a черно-белый аэроснимок ландшафта лиственных лесов изображения, на рис. 3b картосхема выделов, полученная наземной таксацией. Представлены выделы ивняков и тополевников в различных возрастных состояниях. Слева вверху березняки. Для классификации было использовано три признака статистической модели текстуры SAR [3]: ρ, средний тон T и дисперсия D. Результирующая карта кластеров  на рис. 3c.

В результате окончательной классификации получено 55 кластеров, 24 из них относится к лесу, значение меры разделимости по всем полученным унимодальным кластерам равно 0.28. Максимальное значение числа уровней квантования равно 64.  Положение сегментов кластеров соответствует положению выделов на картсхеме выделов. Каждому типу леса соответствует по 1-3 кластерам, точность распознавания типов покрытия земной поверхности и леса не уступает наземной таксации.

Когда кластеризация проводилась не иерархическим методом, то минимум меры (2), достигаемый в диапазоне изменения n: 256>n>40 при n=61, был равен 0.38. Число кластеров при этом равно 365, причем большинство кластеров относилось к плохо разделимым тонким ложным кластерам, возникающим на границах текстур на изображении

2

Литература
1.Narendra P.M. and Goldberg M.  A non-parametric clustering scheme for  LANDSAT. //  Pattern Recognition. 1977.  9. P. 207.

2.Сидорова В.С. Оценка качества классификации многоспектральных изображений гистограммным методом.//Автометрия. 2007.Т. 43, №1, С. 37–43

3.V.S. Sidorova. Unsupervised Classification of Forest’s Image by Texture Model Features. // Pattern Recognition and Image Analysis.­ 2009.Vol. 19, No.4. pp.698–703


СТРУКТУРА ЛАБОРАТОРИИ*ШТАТ ЛАБОРАТОРИИ*ЛАБОРАТОРИЯ ОБРАБОТКИ ИЗОБРАЖЕНИЙ

© 2013 Институт Вычислительной Математики и Математической Геофизики СО РАН