3. Анализ метрики пространства признаков. Минимизация объема описаний. Решающие границы в пространстве признаков.

Основные этапы распознавания – это формирование признакового пространства, получение эталонных описаний классов и построение правила принятия решения о наблюдаемом классе объектов.

Совокупность признаков должна в наибольшей степени отражать те свойства объектов, которые важны для классификации. При этом от размерности p признакового пространства зависит вычислительная сложность процедур обучения и принятия решения, достоверность классификации, затраты на измерение характеристик объектов. Первоначальный набор признаков формируется из числа доступных измерению характеристик объекта Y1,…,Yg, отражающих наиболее существенные для классификации свойства. На следующем этапе формируется новый набор X1,…,Xp; p < g. Традиционные способы формирования новых признаков в условиях полного априорного знания основаны на максимизации некоторой функции J(Y1,…,Yg), называемой критерием и обычно понимаемой, как некоторое расстояние между классами в признаковом пространстве с координатами Y1,…,Yg. В других случаях критерий J(Y1,…,Yg) выражает диаметр или объем области, занимаемый классом в признаковом пространстве, и новые признаки формируются путем минимизации критерия.

Последовательность действий при формирования гиперпространства, занимаемого объектами одного класса, обычно выглядит, как экстраполяция множества точек представленных обучающей выборкой с целью формирования замкнутой оболочки множества центральных моментов этого класса. Область оболочки дополняется гиперэллипсоидами доверительных интервалов элементов обучающей выборки. На выходе данной процедуры обобщенные конфигурации, описывающие на языке вероятностей данный класс. Эта процедура объемна и ее осуществление требует больших затрат. Можно ли ее упростить, облегчить? Этот желание лежит в основе целого ряда направлений теории распознавания. Метод опорных векторов (SVM) одно из них. Он не исключает необходимости решения общей задачи, но на первом, стартовом этапе достаточно эффективен. Процедуры метода схожи с поиском отрезков плоскости линейной регрессии и ее смещения для каждого класса в отдельности, которое минимизирует среднеквадратичную ошибку распознавания.

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

По Лагранжу, если искомая функция в точке достигает условного минимума при фиксированном наборе то и - новая модифицированная целевая функция ( - множители Лагранжа и уравнения ограничений соответственно) так же будет достигнут минимум по всем переменным но уже без ограничений.

Минимум можно искать следующим образом:

1. Найдем все производные от модифицированной функции по переменным и приравняем их нулю;

2. Приравняв производные нулю найдем через ;

3. Получим систему уравнений подстановкой в .

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

Модифицированная функция . Производные по равны: ; . Приравнивая их нулю, получим . Подставив в уравнение ограничения, получим . Выбираем точку минимума.

При ограничениях , минимизируем модифицированную квадратичную функцию , где С – коэффициент ошибки. В терминах метода Лагранжа необходимо найти минимум по , , штрафам и максимум по - приведенной функции при условии и .

Эта новая целевая функция называется Лагранжианом. Производная по приравненная нулю, дает новый вектор выраженный через множители Лагранжа, . Искомый вектор должен быть линейной комбинацией учебных векторов для которых . Если , учебный вектор называется опорным вектором (support vector). Уравнение разделяющей гиперплоскости выглядит как . Вектор подлежит распознаванию.

Беря производную по b получим . Выражая через и подставляя в Лапласиан получаем новое уравнение с множителями, при которых достигается максимум.

при ограничениях и . Полученная функция выпукла и любой локальный максимум этой функции является ее глобальным максимумом. Задача стала задачей экстремумов по множителям Лагранжа. Целевая же функция зависит теперь от скалярных произведений .Скалярное произведение играет в этом случае роль метрики близости и показывает количество совпадений признаков.

Этапы последовательного решения задачи.

1. Определить набор , удовлетворяющих ограничениям.

2. Выбрать стартовую пару улучшаемого произведения .

3. Подставив их изменить в сторону экстремума эту пару.

4. Повторить 2 и 3 до наступления стоп условия.

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

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

Для достижения надежности распознавания расширяют пространство признаков до получения устойчивого условия останова.

Машина опорных векторов.

1. Выбираем отображение векторов в новое, расширенное пространство.

2. Формируем новую функцию скалярного произведения . Это ядро и главный параметр настройки машины опорных векторов.

3. Находим разделяющую гиперплоскость в новом пространстве. Т.е. вместо подставляем . Находим новую матрицу коэффициентов и решаем задачу оптимизации.

4. Найдя и , поучаем различающую поверхность .

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

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

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

• сжатие допустимо до тех пор, пока не пересекутся крайние точки доверительных интервалов классов дополненные доверительными зонами крайних объектов в соседних классах (рис. 6.1.).

Рис.6.1. Сжатие описаний пространства признаков

до соприкосновения доверительных интервалов границ классов (А и В)

В исходном описании изображений первой процедурой является процедура укрупнения пикселя.

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

На рис. 6.2. приведены графики сигналов до (пунктир) и после (сплошная) укрупнения. Сигнал поднят на 200 единиц для лучшего различия. Из графиков видно то, что два объекта после сжатия сохранили свойство обнаружения.

Рис.6.2. Сигналы от объектов до и после сжатия

Следующей процедурой идет уменьшение размерности описания пикселя. Обычно исходное описание в 3-х цветной модели имеет размер 24, 30, 48 бит в зависимости от разрядности систем оцифровки аналоговых сигналов.

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

Как правило, при перекодировке учитывается частота появления цветов о объектов исследуемого класса.

Перекодировка обычно выполняется табличным преобразованием, при котором исходные компоненты описания пикселя является смещениями для таблиц перекодировки.

Интегрально таблицы преобразований выглядят как новые цветовые палитры.

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

Например: если W - исходное изображение , w - бинаризованное изображение, y, x - координаты бинаризуемой точки, xs, ys - размеры сегмента, hx, hy - шаг смешения сегмента, nx - число сегментов по x, то правило бинаризации можно записать следующим выражением:

, где среднее, медиана или мода j - го сегмента.

Однако множество задач с признаковым пространством остается открытыми. Это и минимизация влияния масштабирования, разворота объектов, 3D трансформация и т.п. Ниже приведен фрагмент задачи распознавания рукописных букв. Написанная от руки одна и та же буква может иметь различное изображение в виде прописных и печатных начертаний. В таком случае необходимо также разбивать базу этих образов на столько классов, сколько принципиально различных символьных представителей имеет соответствующий образ. Чем выше разрешение (например, номинальное 120 по горизонтали на 160 по вертикали = 19 200 точек), тем более точно можно выявить закономерности и правильно подстроить модель. Для получения более точных характеристик должна быть введена достаточно большая БД эталонных элементов, состоящая не менее 1 000 разновидностей одного элемента. Более подходит в рукописных символах матрица 12х16 т.е. 192 точки, но и она очень велика для дешифрации произвольной ситуации.

(Объем пространства исходов - = 6,2771017353866807638357894232077· ).

Рис.6.3. Бинарный образ рукописной цифры, подлежащей распознаванию

Ниже приведены и маски 3 D фигуры, усложняющей ее распознавание.

Рис.6.4. Бинарный образ Распознаваемых контуров вертолетов в 3D