Методы распознавания образов. Часть 2

Структурные методы распознавания

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

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

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

Язык описания образов – язык, который обеспечивает структурное описание образов в терминах множества непроизводных элементов и операций композиции этих элементов.

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

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

Пример структурного распознавания образов

Байесовский подход к принятию решения

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

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

Байесовский классификатор на основе наблюдаемых признаков относит объект к классу, к которому этот объект принадлежит с наибольшей вероятностью. Основной байесовского подхода в статистике является теорема Байеса. Предположим, что мы наблюдаем некоторую случайную величину X, которая имеет плотность вероятности p(x,w) с параметром w. А хотим сделать вывод о другой случайной величине w, имеющей некоторое распределение вероятности τ(w). Пусть в результате наблюдений получены статистические данные x. Из определения условной вероятности следует:

Также следует

Подставив (2) в (1) получим формулу Байеса

формула байеса

Для нашей задачи имеется m классов, т.е. m возможных переменных (w_1…w_m), то

применение формулы байеса

Распределение Pr(w) называют априорным распределением вероятностей возможных значений w. Это распределение принимается прежде, чем получены статистические данные.

Распределение Pr(w|x) – апостериорное распределение значений w, при условии получения статистических данных. При этом w_i – гипотеза, а x – свидетельство, поддерживающее гипотезу. Если все классы w_i характеризуются собственными несовместными вероятностями, охватывающими все возможные случаи, то можно применить правило Байеса для вычисления апостериорных вероятностей каждого класса по априорным вероятностям этих классов и распределениям условной вероятности для x.

На практике необходимо каким-то образом обеспечить вычисление p(x|w_i). Эмпирический подход предполагает разбиение диапазона х, на интервалы, затем подсчет частот появления х среди значений каждого интервала и сохранение в гистограмму. Необходимо нормировать функцию вероятности так, чтобы сумма всех значений х равнялась 1. Если х похоже на одну из известных параметрических моделей, то можно представить распределение с помощью небольшого количества характеризующих его параметров.

Обычно используется распределения Пуассона, экспоненциальное и нормальное.

Непрерывная случайная величина Х имеет нормальный закон распределения (закон Гаусса) с параметрами μ и σ^2, если ее плотность вероятности имеет вид:

Непрерывная случайная величина Х

Пример распределения Гаусса для различных параметров µ и σ показан ниже

Распределение Гаусса (нормальное распределение)

Применительно к классификатору: вычисляются расстояния между векторами или вероятности P(w_i |x), что по правилу Байеса можно вычислить как p(x¦w_i )P(w_i )/p(x). p(x) – одинакова для всех функциональных блоков, следовательно, ее можно игнорировать и принимать классификационное решение w_i по максимальному значению p(x¦w_i )P(w_i ). Для проектирования байесовского классификатора необходимы сведения Y об априорной вероятности каждого класса p(x¦w_i ). Знание этих характеристик позволяет принимать оптимальные решения в процессе распознавания. Однако часто бывает трудно оценить эти априорные вероятности.

Нейронные сети

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

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

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

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

Литература

Комментарии

comments powered by Disqus