Автоматизированные Системы Обработки Информации
![]()
![]()


![]()
МЕТОДЫ РАСПОЗНАВАНИЯ ОБРАЗОВ
1. ГЕОМЕТРИЧЕСКИЕ МЕТОДЫ.
В основе геометрических методов лежит понятие меры близости объектов в n-мерном признаковом пространстве описаний. Центральной задачей при создании систем распознавания является выбор типа меры близости.
Меру близости необходимо выбирать таким образом, чтобы она, с одной стороны, отвечала представлению разработчика о близости объектов рассматриваемых классов, а с другой - позволяла бы упростить процедуры синтеза оптимальных частных алгоритмов.
Сущность меры близости применительно к рассматриваемому классу задач покажем на примере двух классов в 2-х мерном пространстве описаний.
![]()
Интерпретация рисунка приводит к естественному выводу о предпочтительности отнесения объекта Х к первому классу. В то же время классификация объекта Хi вызывает затруднения и необходимы расчеты.
Очевидно, что классификация образов с помощью функции расстояния эффективен только в тех случаях, когда классы образов обнаруживают тенденцию к кластеризации (группированию).
Поскольку близость классифицируемого образа к образам класса будет использоваться в качестве критерия для его классификации, назовем такой подход классификацией образов по критерию минимума расстояния.
Классы могут быть представлены путем перечисления членов класса (как на рисунку: точки в кластерах) или с помощью эталонных образов (например, центральными объектами z1 и z2).
Заметим также, что в рассматриваемом классе задач описания объектов являются векторными.
Рассмотрим М классов. Пусть эти классы допускают их представление с помощью эталонных образов Z1,Z2, . . .,Zm. Евклидово расстояние между произвольным вектором образа Х и i-м эталоном определяется следующим выражением:
_____________
Di = || X - Zi || = √(X - Zi)/ (X - Zi) (1)
где || Х || - Евклидова норма;
![]()
х1
х2
Х = х3 - вектор образа распознаваемого объекта;
:
хn
![]()
z1
Z = : - вектор образа эталона класса;
zn
n 1
|| Х || = [Σ Xj2 ]2
j=1
X / = ( x1 ,x2 , . . .,xn) - транспонированный вектор;
X / Z - скалярное произведение;
n
X/ Z = Σ Xj/ Zj
j = 1
Классификатор, построенный по принципу минимума расстояния, вычисляет расстояние, отделяющее классифицируемый образ Х от эталона каждого класса, и зачисляет этот образ в класс,, оказавшийся ближайшим к нему. Другими словами, образ Х приписывается к классу Wi , если условие Di < Dj для всех j № i .
Путем несложных преобразований исходно формуле (1) можно придать более удобный для вычислений вид.
di (X) = X/ Zi - 1/2 Zi/ Zi, i = 1,2,...,M,
где образ Х относится к классу Wi, если условие di (X) > dj (X) справедливо для всех j № i.
Пример:
z1 . . . z5
z1/ = ( 1 2 6 3 1 ) z2/ = ( 6 4 3 2 1 )
x/ = ( 1 3 5 2 1 )
![]()
![]()
![]()
![]()
![]()
![]()
d1(x) = ( 1 3 5 2 1 ) -1/2 ( 1 2 6 3 1 ) = ( 1+6+30+6+1 ) - 1/2 ( 1+4+36+9+1 ) =
= 44 - 1/2 51 = 18.5;
d2(x) = (6+12+15+4+1) - 1/2 (36+16+9+4+1) = 38 - 1/2 66 =5
d1(x) > d2(x) , поэтому образ х принадлежит первому классу.
Меры сходства не исчерпываются расстояниями. В качестве примера можно привести не метрическую функцию сходства
z x/
s(x,z) = -----------,
|| x || || z ||
представляющую собой косинус угла, образованного векторами X и Z. Этой мерой целесообразно пользоваться, когда кластеры располагаются вдоль главных осей или растянуты вдоль лучей, направленных от начала координат.
![]()
Однако использование данной меры связано с определенными ограничениями: достаточное отстояние кластеров друг от друга и от начала координат.
Для двоичных признаков (признаки принимают значения либо `` 0`` либо ``1``) может использоваться мера Танимото
z x/
s(x,z) = ------------------- .
x/ x + z/ z - x/ z
Перечисленные меры близости не учитывают корреляционные связи между признаками. Устранить этот недостаток позволяет критерий известный по названием расстояние Махаланобиса, определяемое для образов x и m как
d = ( x - m ) / с -1 ( x - m ),
где c - ковариационная матрица совокупности образов, m - вектор средних значений, а х - представляет образ с переменными характеристиками(классифицируемый образ).
ЛОГИЧЕСКИЕ МЕТОДЫ
Объекты классов и реализация представляются в виде булевых функций:
Ωi = fi (x1, . . . , xn) , i = 1, . . . ,k
и G = (x1 , . . . , xn).
Заданы правила использования булевых функций при распознавании:
W = (w1 , . . . , wn).
Процедура распознавания состоит в определении неизвестной функции
F(Ω1 , . . . ,Ωk),удовлетворяющей уравнению
_
G (x1,. . . , xn ) + F(Ω1 , . . . , Ωk)= I, (1)
Где F - совокупность булевых функций априорного описания.
Пример:
F(Ω1) = x1x2+x3 или 110 + 001
Ωi = f1i + f2i
F(Ω2) = x1x3+x2 или 101 + 010
Правило классификации:
_ _
G ЄΩi, если G + f1 = I или G + f2 = I .
_
Пусть G = x1 x2 или 110 ( G = 001).
Найти F такую, чтобы выполнялось равенство 1.
_
G + f1 = 001 + 110 = 111 = I
Ω1 : _
G + f2 = 001 + 001 = 001 № I
_
G + f1
= 001 + 101 = 101 №
I
Ω:2: _
G + f2 = 001 + 010 = 011 № I
Вывод: G принадлежит Ω1.
СТРУКТУРНЫЕ МЕТОДЫ
При структурном подходе к распознаванию признаками служат образы, называемые непроизводными элементами, а также отношения между ними, характеризующие структуру образа.
Для описания образов через непроизводные элементы и их отношения специальный язык образов.
Правила такого языка, позволяющие составлять образы из непроизводных элементов, называется порождающей грамматикой.
Пример:
Заданы непроизводные элементы:
![]()
![]()
![]()
в d
а с
и правило объединения: головная часть присоединяется к хвостовой по прямым углом и записывается, например, ав, т.е.
в
а
![]()
![]()
Фигура
будет иметь
следующую
грамматическую
структуру:
авсd.
![]()
В основе процедур(алгоритмов) распознавания лежат правила грамматического разбора.
ВЕРОЯТНОСТНЫЕ МЕТОДЫ
Статистический подход основывается на математических правилах классификации, которые формулируются и выводятся в терминах математической статистики.
Пример. Пусть совокупность объектов подразделена на два класса -Ω1 и Ω2, а для характеристики объектов используется один признак х. Известны описания классов - условные плотности распределения вероятностей значений признака объектов 1-го и 2-го классов, т.е. функции f1(x) и f2(x), а также априорные вероятности появления объектов 1-го и 2-го классов: р(Ω1) и р(Ω2).
В результате эксперимента определено значение признака распознаваемого объекта, равное х0.
Определить, к какому классу относится объект ?
Обозначим через х0 некоторое пока не определенное значение признака х и условимся о следующем правиле принятия решений:
если измеренное значение признака распознаваемого объекта х0>х0, то объект будем относить ко второму классу;
если х0< х0 - к первому.


![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()