Гистограммный кластерный алгоритм поиска кластеров с отделимостью ниже заданной

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

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

Используемый алгоритм - использован разработанный автором гистограммный иерархический алгоритм. Целью иерархического деления кластеров является достижение предельной детальности для заданной разделимости кластеров. Алгоритм находит различную предельную детальность в подкластерах векторного пространства признаков, которая зависит от свойств области данных. Подробно описан в [1,2]. Приложение алгоритма к пятиспектральному спутниковому снимку иллюстрировано на сайте  http://loi.sscc.ru/lab/RFFI10/RU/sidorova_separability.htm.

[1] V. S. Sidorova. Hierarchical Cluster Algorithm for Remote Sensing Data of Earth. // Pattern Recognition and Image Analysis, 2012, Vol. 22, No. 2, pp. 373–379. http://link.springer.com/static-content/0.5825/lookinside/259/art%253A10.1134%252FS1054661812020149/000.png

[2] Сидорова В.С. Новый гистограммный алгоритм с автоматическим выбором детальности кластеризации по заданной разделимости кластеров. Труды международного конгресса “ГЕО-СИБИРЬ - 2012”, Новосибирск, 2012, СС. 149-154

 Функциональные возможности - Гистограммный алгоритм не требует задания числа кластеров и никаких предположений о функциях распределения. Требуется ввести изображение и задать значение максимальной разделимости кластеров. Алгоритм найдет кластеры с  отделимостью, ниже заданной, и максимальные  детальности квантования соответствующих подобластей векторного пространства признаков. Фильтрация кластеров по разделимости, встроенная в процесс иерархической кластеризации, позволяет в результате получить их небольшое число. Алгоритм автоматизирует выбор сеток квантования, совершенствуя метод Наредры [3,4].  Может быть использовано до 8 спектральных каналов, файл входного изображения объемом до 8 мегабайт. Обработка изображения {5 спектр. каналов, 1000*1000 пикселей}, требует около 3 минут для заданной отделимости 0.1 (при максимально возможной 1.),  на ПК указанной ниже конфигурации (включая построение 5-мерной гистограммы входных данных). При построении многомерной гистограммы с числом спектральных каналов больше трех используется взаимодействие  хэширования и сортировки Шелла, предложенное в [4]. Алгоритм позволяет подробно исследовать структуру данных. Строится  карта кластеров (сегментация).

[3] Narendra P.M. and Goldberg M.  A non-parametric clustering scheme for LANDSAT  // Pattern Recognition. – 1977 – 9 – P. 207-215. 

[4] V. S. Sidorova, Separating of the Multivariate Histogram on the Unimodal Clusters, Proceedings of the Second IASTED International Conference “Automation Control and Information Technology”, Novosibirsk, 2005, P. 267–274.      

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