Понятие разделяющей и решающей функции при распознавании образов, представленных наборами (векторами) параметров .

Метод гиперпараллелепипедов.

При конкретном наборе интересующих нас классов {Ak}, k=1,...,K, значения признаков для образов различных классов в n-мерном пространстве яркостей могут совпадать или перекрываться по одним координатам и различаться по другим. Если области для разных классов хорошо разделяются хотя бы по одной из n координат, мы можем задать границы каждого класса Ak интервалами значений Wj(k)=[ajk,bjk] по каждой координате j=1,…,n и классифицировать сигнатуры пикселей по простому правилу:

x1Î[a1k,b1k], x2Î[a2k,b2k],…, xnÎ[ank,bnk] Þ xÎAk.

Геометрическая интерпретация этого случая при n=2, K=3 показана на рис. 20. Здесь W1(1)=W1(2)+W1(3), но класс А1 разделяется попарно с классами А2 и А3 по признаку х2. В то же время W2(2)=W2(3), но эти классы разделяются по признаку х1.

Рис.20. Простой случай разделения классов (гиперпараллелепипеды).

Метод классификации, основанный на правиле (1), называют методом гиперпараллелепипедов. Его разновидности имеются в большинстве пакетов обработки данных ДЗ. Иногда его используют и при частично перекрывающихся гиперпараллелепипедах, когда ширина Dxj параллелепипеда в каждом канале определяется по значениям яркостей x сигнатуры класса как Dxj=xj(max)-xj(min) .

В таком случае, однако, необходимо вводить отдельное правило принятия решения для областей перекрытия. Возможные решения, предлагаемые в пакете ERDAS Imagine, описаны в [1]. Главным достоинством метода является то, что здесь не используются никакие предположения о статистических свойствах сигнатур классов; границы параллелепипедов определяются по разбросу эталонных выборок. Это удобно в57 тех случаях, когда класс неоднороден по яркости или выборки слишком малы для надежной оценки средних яркостей по каналам и других необходимых статистических характеристик. Конечно, точность классификации при этом может оказаться недостаточно высокой. Но когда эталоны тематических классов выбираются путем традиционного визуального анализа отдельных каналов, то есть по яркостному контрасту, этот метод может дать вполне приемлемый результат.

7.2. Линейные разделяющие функции. Методы, в которых границы классов строятся без каких-либо предположений о статистических свойствах сигнатур классов, называются непараметрическими. Кроме метода гиперпараллелепипедов, в ERDAS Imagine имеется еще один непараметрический метод классификации – на основе построения границ классов непосредственно в пространстве признаков. Этот метод так и называется - Feature space. Как и в предыдущем случае, технология построения таких областей требует предварительного определения положения классов в признаковом пространстве. Для этих целей удобнее всего использовать аппарат связывания изображения с проекциями признакового пространства на пары каналов. Методика такого анализа описана в [1].

В общем случае множество значений признаков для спектральных образов класса Ak - это область W(k) в пространстве X, ограниченная некоторой гиперповерхностью произвольной формы. Перекрытие областей, соответствующих различным классам, приводит к ошибкам классификации. Поэтому во всех методах классификации гиперповерхности, разделяющие множества W(k), строятся так, чтобы обеспечить тем или иным способом минимум ошибок при распределении образов по классам. Уравнения таких гиперповерхностей имеют вид d(x)=0 и называются разделяющими функциями или дихотомиями. Во многих классических алгоритмах автоматического распознавания используются линейные разделяющие функции (рис.21). Области решений в пользу каждого из классов в этом случае описываются системой линейных неравенств. Например, для класса A1 на рис.21 эта система имеет вид:

d1(x1,x2)>0,

d2(x1,x2)>0, (18)

d3(x1,x2)>0.

Когда мы рисуем область-многоугольник в признаковом пространстве, мы, фактически, определяем такую систему неравенств-ограничений. Увеличивая число неравенств, можно аппроксимировать границу с любой желаемой точностью. Интервалы классов по каналам в этом случае могут и перекрываться.

Качество выбора границ классов можно проверить, наложив «маску» эталона на изображение, как это описано в (1)

Где-то тут про решающую функцию

7.3. Параметрические методы классификации. В непараметрических методах классифицируются не все точки изображения, а только те, сигнатуры которых попадают в ограниченные нами области признакового пространства. Остальная часть признакового пространства образует области отказов от распознавания. Что же делать с такими точками?

Мы, конечно, можем отнести все эти точки в класс отказов и назвать его «прочие объекты». Однако иногда требуется сплошная классификация, то есть все пиксели должны быть куда-то отнесены. В этом случае применяются так называемые параметрические методы, в которых используются определенные предположения о характере статистического распределения сигнатур в классах и соответствующие параметры такого распределения. Как мы уже знаем, характер такого распределения, при достаточно большом количестве пикселей, можно оценить по гистограмме.

В случае нескольких каналов анализ n-мерной гистограммы напрямую не представляется возможным. Средства пакета ERDAS Imagine позволяют анализировать гистограммы выбранных классов только отдельно в каждом канале. Тем не менее, это также позволяет нам судить о том, насколько однороден класс по яркостному признаку.

В параметрических методах классификации используется предположение, что сигнатуры классов подчиняются нормальному (Гауссову) закону распределения. Это означает, что распределение сигнатур для каждого класса можно описать вектором средних значений m и характером рассеяния точек вокруг среднего. Для многомерного нормального распределения график плотности p(x) представляет собой «гиперколокол» с максимумом p(m) в точке, соответствующей среднему значению m. Сечения такого многомерного59 «колокола» параллельно плоскостям, образуемым каждой парой координат, представляют собой эллипсоиды рассеяния, которые в разных направлениях имеют разные значения σ. Поэтому рассеяние вокруг среднего значения описывается ковариационной матрицей C, элементы которой определяются выражением (13) из раздела 5.3. На рис.22 показан пример таких эллипсоидов рассеяния для функций распределения спектральной яркости трех классов на диаграмме рассеяния в красном и ближнем ИК диапазонах.

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

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

Рис.22. Эллипсоиды рассеяния для трех классов в красном и ближнем ИК диапазонах.

Уравнение таких разделяющих функций d(x)ks=0 для пары классов k, s можно преобразовать к виду

d(x)ks=rk(x)-rs(x)=0,

где rk(x) – функция, для которой на области W(k) выполняется условие

rk(x)>rl(x) для всех l¹k, k,l=1,..., K.

а неравенства, ограничивающие область решения для k-го класса, представить в виде rk(x)>rs(x) для всех s=1,…,K.

Функции rk(x) называются решающими функциями или дискриминантами. Если для всех классов k=1,...,K заданы решающие функции rk(x), задача классификации конкретного вектора-образа х в такой постановке сводится к вычислению значений rk(x) и нахождению max{r ( )} s s x :

rk(x)= max{r ( )} s s x Þ xÎ Ak. (19)

ёВ программных реализациях алгоритмов классификации изображений вместо решающей функции обычно используется функция, принимающая при выполнении условия (19) минимальное значение. Она называется расстоянием или метрикой и в каждом методе функционально связана с соответствующей решающей функцией. Использование метрики вместо решающей функции позволяет использовать общую процедуру оценки качества классификации для всей группы реализованных в пакете методов. Тем более что в ряде параметрических алгоритмов расстояние непосредственно используется в качестве меры сходства образа с классом.

Простейшее из параметрических правил – классификация по минимуму расстояния. В ней используется только один параметр статистического распределения – среднее значение m (в многомерном случае – вектор средних значений m). В этом случае также удобно предполагать, что яркости в классах распределены по нормальному закону, хотя эта гипотеза напрямую не используется. Векторы-образы относятся к k-му классу по минимуму евклидова расстояния до центра класса mk:

Разделяющие функции между классами при использовании в качестве меры близости евклидова расстояния (20) представляют собой гиперплоскости (линейные разделяющие функции), перпендикулярные к линиям, соединяющим центры кластеров, и равноудаленные от этих центров. Это означает, что такой метод классификации обеспечит минимальные ошибки только в том случае, когда эллипсоиды рассеяния сигнатур классов примерно одинаковы и их форма близка к сферической. Эта ситуация встречается на изображениях, где представлены преимущественно объекты, однородные по яркости, например, травянистая растительность, вода и почвы. Для древесно-кустарниковой растительности, лесов и, тем более, сложных комплексов, включающих растительную компоненту (например, городская застройка), это условие выполняться не будет. В таких случаях необходимо применять статистические методы классификации, которые будут рассмотрены ниже.61

К параметрическим методам классификации можно условно отнести и неконтролируемую классификацию, поскольку в ней используется, по меньшей мере, один параметр статистического распределения признаков внутри каждого класса – вектор их средних значений m.

Вопрос 2

ЛОГИЧЕСКИЕ МЕТОДЫ

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

В самом общем виде логические методы можно охарактеризовать как разновидность поиска по обучающей выборке логических закономерностей и формирование некоторой системы логических решающих правил (например, в виде конъюнкций элементарных событий), каждое из которых имеет собственный вес. Группа логических методов разнообразна и включает методы различной сложности и глубины анализа. Для дихотомических (булевых) признаков популярными являются так называемые древообразные классификаторы, метод тупиковых тестов, алгоритм “Кора” и другие. Более сложные методы основываются на формализации индуктивных методов Д.С.Милля. Формализация осуществляется путем построения квазиаксиоматической теории и базируется на многосортной многозначной логике с кванторами по кортежам переменной длины [46].

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

Логические системы.

а) Метод решения задачи распознавания: логический, основанный на дискретном анализе и исчислении высказываний;

б) Метод априорного описания классов: логические связи, выражаемые через систему булевых уравнений, где признаки - переменные, классы - неизвестные величины.

Структурные (лингвистические) системы.

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

б) Метод априорного описания классов: подмножества предложений, описывающих объекты каждого класса.

Мы рассмотрим здесь один из наиболее простых и распространенных логических методов распознавания - алгоритм вычисления оценок (метод голосования) [24,25]. Он может применяться в тех случаях, когда выделяемые классы характеризуются наличием определенных комбинаций признаков-индикаторов, причем некоторые из этих признаков или комбинаций имеют различную значимость (вес) для разных классов. Суть метода заключается в следующем. Пусть для наших объектов (образов) задан набор булевых признаков S={s1,…,sn} и перечень классов W={w1,…,wK}, по которым мы хотим распределить эти объекты. Рассмотрим основные этапы построения алгоритма вычисления оценок. 1. На основе анализа доступных данных формируем типичные для каждого класса наборы значений булевых переменных {s1,…,sn}. Удаляем наборы, одинаковые для разных классов. В ряде случаев, чтобы «уравновесить» такие наборы по классам, целесообразно ввести весовые коэффициенты, характеризующие степень «типичности» определенных наборов в каждом классе. 2. Выделяем опорные множества - группы признаков SlÌS, l=1,…,L по которым лучше всего определяется принадлежность объекта тому или иному классу. Если таковые выделить не удается, в [22], например, предлагается использовать все возможные наборы. Однако такой подход сильно увеличивает вычислительную емкость и далеко не всегда оправдан. 3. Задаем меру близости dl , l=1,…,L между наборами признаков объектов внутри каждого множества Sl и правила вычисления оценки gl подобия образов на множестве Sl . Самой простой мерой близости является совпадение наборов по каждому опорному множеству Sl . 4. Задаем правила вычисления оценок Gkl=aklgl k=1,…,K, l=1,…,L для каждого из K классов на основе выбранных оценок подобия между образами. Заметим, что вместо введения весовых коэффициентов на полные наборы булевых переменных, как предложено в пункте 1, можно ввести весовые коэффициенты akl на каждое из опорных множеств. 5. Выбираем вид суммарной оценки Gk=SbklGkl по всем опорным множествам для принятия решения о принадлежности объекта тому или иному классу. Коэффициенты bkl определяют значимость каждого из L опорных множеств. В простейшем случае они могут быть равны единице. При распознавании для каждого предъявляемого системе образа вычисляются оценки Gkl по опорным множествам и суммарные оценки Gk по всем K классам. Решение о принадлежности объекта тому или иному классу принимается по максимальному значению оценки Gk , то есть по “большинству голосов” в пользу данного класса. Таким образом, достоинством данного метода является оценка не по отдельным признакам, а по группам. Поскольку каждая группа может иметь свой весовой коэффициент, и для каждого класса группы могут браться тоже со своими весовыми коэффициентами, то этот метод можно рассматривать как «промежуточный» между статистическими и чисто логическими методами классификации. Чисто логические методы ближе к теории экспертных систем.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 6