3.8.2. РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ НА ОСНОВЕ НЕЧЕТКОЙ КЛАСТЕРИЗАЦИИ ПО с-СРЕДНИМ [37]

Кластеризация представляет собой метод разбиения множества разбросанных данных на несколько групп. Разбиение осуществляется так, чтобы данные в одной группе обладали похожими свойствами, а свойства в среднем между группами максимально различались. Пусть данных, а X множество этих данных; -мерный вектор, тогда

Рассмотрим разбиение этого множества на с кластеров Степень принадлежности кластеру обозначим через При жесткой кластеризации принимает два значения: 0 или 1, при нечеткой - значение может быть произвольным от 0 до 1:

В любом случае

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

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

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

Значения при которых формула (3.40) минимальна (обозначаются как , при удовлетворяют следующим условиям:

Значение обеспечивающее минимум (3.40), можно найти с помощью следующей итеративной процедуры.

Шаг 1. Выбрать значение т и число кластеров с и определить соответствующим образом норму в выражении (3.41). Для U задать начальное значение целесообразно выбрать случайным образом независимо от .

Шаг 2. Вычислить центр кластера используя и формулу (3.42).

Шаг 3. Определить используя и формулу (3.41).

Шаг 4. Задать подходящую норму и граничное значение и выполнять предыдущие шаги до тех пор, пока .

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

Остается неизвестным значение с. Изменяя произвольным образом значение с, следует выяснить, какое из них будет наилучшим образом представлять физический процесс. Поскольку формулы (3.41) и (3.42) определяют минимум изменяя начальное значение U, можно изменять конечные значения. Для получения хорошего результата следует более внимательно подходить к выбору начального значения. Кроме того, в любом случае трудно распознать небольшую изолированную область.

В работах [39-42] приведены различные примеры применения НСС в распознавании изображений. Ниже мы рассмотрим пример анализа изображения, полученный методом телеметрии. В работе [43] рассматривается распознавание изображений с изменением его уровня. В частности, на нижнем уровне осуществляется грубая кластеризация. Например, на аэрофотоснимке города распознаются в общих чертах торговые центры, жилые кварталы и другие объекты. Затем проверяется однородность, и если обнаруживается неоднородная область, осуществляется ее распознавание на более высоком уровне - производится деление на дома,

Рис. 3.59. Нечеткая кластеризация.

строения, автомобили и т. п. Если это изобразить в виде рисунка, то при нечеткой кластеризации для крупных элементов появляются серые области (рис. 3.59). Деление этих элементов на более мелкие на высоком уровне дает картину, изображенную на рис. 3.60. Распознавание можно распространять на все более мелкие элементы. В работе [43] на примере телеметрического изображения, показанного на рис. 3.61, рассматривается метод НСС. Одни и те же участки обводятся с использованием трех типов спектра. Изображение делится на 32 х 32 элемента; каждый элемент состоит из 10 х 10 ячеек. В данном случае целесообразно деление на четыре кластера: река, постройка, земля, лес. Результат,

Рис. 3.60. Кластеризация высокого уровня.

Рис. 3.61. Пример для анализа.

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

Если изучить три изображения по уровням серого цвета характерных мест четырех кластеров MR (река), (постройка), МА (земля), MF (лес), выделенных человеком, то получаются следующие результаты:

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

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

мала, поэтому, очевидно, трудно определить центр кластера . В связи с этим метод НСС был применен вторично при для элементов с максимальным значением принадлежности ниже 0,5. Получены следующие результаты:

В данном случае близко к приведенному выше значению близки к . В работе [43] рассмотрено также применение метода НСС на втором уровне, причем кластеризация при первом применении проводилась для элементов (элемент - 20 х 20 ячеек), . В результате 175 элементов рассматривались как неоднородные и их вновь классифицировали по четырем типам. Для новых 700 элементов (10 х 10 ячеек) на втором уровне применяли НСС при и, как сообщается, получены результаты, почти совпадающие с указанными выше.