Xreferat.com » Рефераты по радиоэлектронике » Автоматизированные Системы Обработки Информации

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

alt="" width="2" height="42" align="LEFT" />






МЕТОДЫ РАСПОЗНАВАНИЯ ОБРАЗОВ

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 - вектор средних значений, а х - представляет образ с переменными характеристиками(классифицируемый образ).


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

Объекты классов и реализация представляются в виде булевых функций:

Ω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.


  1. СТРУКТУРНЫЕ МЕТОДЫ

При структурном подходе к распознаванию признаками служат образы, называемые непроизводными элементами, а также отношения между ними, характеризующие структуру образа.

Для описания образов через непроизводные элементы и их отношения специальный язык образов.

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

Пример:

Заданы непроизводные элементы:

в d

а с

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

в

а

Фигура будет иметь следующую грамматическую структуру: авсd.


В основе процедур(алгоритмов) распознавания лежат правила грамматического разбора.


  1. ВЕРОЯТНОСТНЫЕ МЕТОДЫ

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

Пример. Пусть совокупность объектов подразделена на два класса -Ω1 и Ω2, а для характеристики объектов используется один признак х. Известны описания классов - условные плотности распределения вероятностей значений признака объектов 1-го и 2-го классов, т.е. функции f1(x) и f2(x), а также априорные вероятности появления объектов 1-го и 2-го классов: р(Ω1) и р(Ω2).

В результате эксперимента определено значение признака распознаваемого объекта, равное х0.

Определить, к какому классу относится объект ?

Обозначим через х0 некоторое пока не определенное значение признака х и условимся о следующем правиле принятия решений:

  • если измеренное значение признака распознаваемого объекта х0>х0, то объект будем относить ко второму классу;

  • если х0< х0 - к первому.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: