Формирование интеллектуальных критериев в задачах кластеризации сложной графической информации

Размещено на http://www.allbest.ru/

ФОРМИРОВАНИЕ ИНТЕЛЛЕКТУАЛЬНЫХ КРИТЕРИЕВ В ЗАДАЧАХ КЛАСТЕРИЗАЦИИ СЛОЖНОЙ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ

М.И. Бояркин

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

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

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

Для решения задачи группировки графических образов можно применить кластеризацию данных. Кластеризация - это процесс группировки образов различной природы по некоторым, заранее выбранным признакам. Образы - это вектора, состоящие из значений различных свойств или признаков кластеризуемых объектов. Набор выбранных признаков должен достаточно полно характеризовать объект с интересующей исследователя точки зрения. В нашем случае признаки - это цифровые значения пикселов изображения, построенного в градациях серого. По общему смысловому определению процедуры кластеризации, образы внутри одной группы должны быть более похожи друг на друга, чем образы из разных групп. Рассматриваемая в данной статье модифицированная модель кластеризации графических данных, учитывающая специфику обрабатываемых, в данном случае, изображений лиц людей, позволяет группировать изображения по признаку их визуального сходства [1]. Специфика данных упомянута неслучайно, так как структура данных и принцип их поступления в систему (как и в прочих случаях практического использования моделей кластеризации) накладывают существенные ограничения на выбор алгоритмических схем кластеризации.

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

Для такой структуры работы подходят так называемые «последовательные алгоритмы кластеризации». Наиболее распространенным представителем данного семейства алгоритмов является «базовая последовательная алгоритмическая схема» (basic sequential algorithmic scheme (BSAS)) [2].

Основой разработанного метода кластеризации является более сложная многоуровневая модификация последовательной алгоритмической схемы [1]. В данной статье будут рассмотрены ключевые моменты подобных алгоритмических схем в задаче группировки графических образов по признаку их визуального сходства. Для иллюстрации ключевых моментов алгоритма BSAS вполне достаточно. В разных алгоритмических схемах наибольшую важность представляют различные параметры (заранее определенное количество кластеров, выбор стоимостной функции кластеризации). Как видно из данного алгоритма (см. рисунок), ключевыми элементами являются функция , которая называется мерой различия (dissimilarity measure), а также значение порога И.

Для того чтобы функция могла исполнять роль меры различия в терминах кластеризации, она должна удовлетворять некоторым требованиям [3]: ,

где X - набор образов, подвергающихся кластеризации.

кластеризация графический образ визуальный

;(1)

;(2)

. (3)

Basic Sequential Algorithmic Scheme (BSAS)

·

·

·

o

o

§

§

o

§

§ Если нужно, обновить «представителя».

o

·

Схема работы алгоритма BSAS

В большинстве случаев . обозначает меру различия между образом и кластером. В таких случаях в основном используется мера различия между образом и «представителем» кластера C (в рассматриваемой модели представителем кластера является некоторая группа образов, называемая «ядром» кластера [1]). Видов функций, удовлетворяющих условиям (1) - (3) и эффективно исполняющих роль меры различия в прикладных задачах кластеризации, довольно много [4]. Однако в большинстве случаев используемая мера различия не учитывает специфику обрабатываемых данных, а работает в основном непосредственно с числовыми векторами и их геометрическим положением в пространстве модели (например, часто используется евклидова метрика [3]). При решении данной специфической задачи мера должна отражать не только близость образов в геометрическом смысле, но также коррелировать со степенью их визуального сходства, т.е. для эффективного решения данной задачи требуется ввести в меру некоторый «интеллектуальный» распознающий элемент.

Основная «геометрическая» составляющая меры вычисляется следующим образом: для векторов x и y выполняется разложение на ортогональные составляющие

,

,

где , - вектор «Да» и вектор «Нет» соответственно. Так как образы в системе представляются нормированными векторами действительных чисел, то соблюдается . Мера различия . Данная мера различия удовлетворяет требованиям (1)-(3). Более того, из ее описания логично вытекает значение порога. Составляющая «Нет» должна быть меньше составляющей «Да»:

.

Если требуется рассчитать меру между образом и группой образов (например, для расчета меры между образом и «представителем» кластера), то y заменяется на матрицу, сформированную из образов как из столбцов: . «Интеллектуальный» элемент вводится при помощи некоторой модификации алгоритма в целом. При поиске кластера С, в который попадает образ , выбирается не минимальный из кластеров с , а берутся все кластеры такие, что

.

После этого применяется модель распознавания на основе синергетической нейронной сети Хакена, предложенная в [5] и позднее развитая в [6, 7].

В процессе распознавания модель со временем эволюционирует в одно из устойчивых состояний - узлов в фазовом пространстве мод, соответствующее одному из запомненных образов системы согласно динамике системы дифференциальных уравнений вида:

,

где - в общем случае неотрицательные настраиваемые параметры, а начальные условия определяются соотношениями: , , ; векторы-столбцы составляют матрицу V.

Номер победившей моды указывает на кластер, к которому, в конечном итоге, будет отнесен образ .

Внедрение подобной интеллектуальной в смысле распознавания образов [6] прослойки позволяет эффективно учитывать при кластеризации визуальное сходство изображений лиц людей. Реализация данной идеи в алгоритме последовательной кластеризации совместно с реализацией других инновационных идей дает возможность создать мощную интеллектуальную систему поиска изображений в сети Интернет на основе их контекстного содержания. Эффективность и работоспособность разработанной модели кластеризации подтверждается тестированием и анализом результатов ее работы в данный момент времени в составе системы www.picollator.ru.

Библиографический список

Бояркин М.И., Данилушкин И.А., Колпащиков С.А., Миронов А.А., Рязанов А.С., Юдашкин А.А. Возможности кластеризации сложной графической информации в соответствии с топологическими свойствами фазового пространства динамической системы распознавания образов // Вестн. Самар. гос. техн. ун-та. Сер. Физ.-мат. науки. 2007. № 2(15). С. 202-204.

Hall A.V. Methods for demonstrating resemblance in taxonomy and ecology // Nature. 1967. Vol. 214. P. 830-831.

Theodoridis S., Koutroumbas K. Pattern recognition. 2ed., Elsevier, 2003.

Spath H. Cluster Analysis Algorithms. Ellis Horwood, 1980.

Haken H. Synergetic computers and cognition: A top-down approach to neural nets. Berlin: Springer-Verlag, 1991.

Юдашкин А.А. Бифуркации стационарных решений в синергетической нейронной сети и управление распознаванием образов // Автоматика и Телемеханика. 1996. №11. C. 139-147.

Yudashkin A., Danilushkin I., Kolpaschikov S., Maslennikov A., Demyanenko R. Mobile Biometric Person Identification System on the Basis of Pattern Recognition Software and GSM Cellular Networks // In: eAdoption and the Knowledge Economy: Issues, Applications, Case Studies (Proc. of eChallenges-2004, Vienna, Austria, 2004). Amsterdam, Berlin, Oxford, Tokyo, Washington: IOS Press, 2004. Part 1. P. 102-108.

Размещено на Allbest.ru