Робототехника.Фу, Ли, Гонсалес (962794), страница 79
Текст из файла (страница 79)
Подбор индексов формы. Рассмотрим процедуру сравнения двух границ объектов, описанных с помощью индексов формы. Она аналогична процедуре, изложенной в разд. 8.5.1, для векторного представления объектов. В соответствии с разд. 8.3.1 степенью схожести й между двумя границами объсктов А и В назовем наибольшее значение совпадающих индексов формы, а а а Начало и' Ь казанного иа рис. 8.53, б. Корень дерева соответствует наименьшей рассматриваемой степени схожести, которая в данном примере равна 4. Из рис. 8.53,б видно, что все формы являются идентичными вплоть до шестой степени (и до восьмой степени, если исключить форму А).
Таким образом, степень схожести формы А по отношению ко всем другим формам равна 6. Г1родолжая исследование, мы находим, что степень схожести формы 0 по отношению к остающимся формам равна 8 и т. д. Снтенень Рпс. 8.52. Граиллпа объекта (и), простейшие элемеиты (б) и гранича, эакодироваииая простейшими элементами (в). Соответствующая Попочка имеет вид оппьсьььсг(г(осл(.
т. е. мы имеем 84(А)= зл(В), за(А)= за(В), за(А)- за(В) за(А) = за(В), зава(А) ча зала(В), за44(А) ч- заэл(В), где з является индексом формы, а нижний индекс означает порядок. Расстояние между двумя формами границы А и В определяется как величина, обратная степени схожести: 0(А, В)= —,'. (8.5-6) Это расстояние удовлетворяет следующим свойствам: а) 0(А, В)~)0; б) 0(А, В)=0, если А=В; в) 0(А, С)(свах[0(А, В), 0(В, С)), Для сравнения двух форм границы используется либо й, либо О. Если используется степень схожести, из сказанного выше сле- дует, что чем больше (т, тем формы оказываются более близ- кими. Обратное справедливо, когда применяется расстояние. Пример.
Для иллюстрации приведенных понятий предполо- жим, что мы хотим определить, какая из пяти форм (А, В, О, Е, Р) (рис. 8.53,а) наилучшим образом соответствует форме С. Это аналогично предположению о том, что свойства пяти форм известны, и требуется определить, какая из ннх наилучшим об- разом соответствует форме с неизвестными свойствами.
Поиск можно представить наглядно с помощью дерева схожести, по- 464 ро ~3 ~о- — — —— 12 —--- 14— Р с и ь к о в 8 8 В 8 8 Рис. 8.53 Формы (а), лсрсво око кести (о) и ллатрипа око ке сти (в) (811. В данном случае только форма Р наиболее соответствует форме С, поскольку их степени схожести выше, чем для любых других форм. Если бы неизвестной предполагалась форма Е, также была бы найдена единственная форма, но с более низкой степенью схожести. Если была бы неизвестной форма А, применяя этот метод, мы могли бы сказать, что она подобна другим пяти формам со степенью схожести, равной 6.
Всю информацию можно объединить в матрицу схожести (рис.8.53, в). Установление соответствия с помощью цепочек. Предположим, что два контура Сл и С, закодированы цепочками аь 465 ик ... а„и 5162 ... (> соответственно, Пусть А является числом соответствий мелсду двумя цепочками, и мы говорим, что соответствие появляется в !ъй позиции, если а; = Ьр Число символов, между которыми нет соответствия, дается выражением В= шах((с! 1, (се!) — А, (8.5-8) где (С/ является длиной (числом символов) цепочки С. Можно показать, что В = 0 только тогда, когда С> н Сз идентичны.
Простая мера схожести между цепочками С! и Ск определяется отношением А А В п>вк((С,(, (Сг() — А ' (8.5-9) Поскольку в знаменателе стоит В, то Я равно бесконечности для идеального соответствия и нулю, когда между символами в С! н С, нет ни одного соответствия (т. е. в этом случае А = 0). Поскольку соответствие устанавливается в результате поочередного сравнения соответствующих символов, то прн создании цепочки, описываюшей границу, важно местоположение начальной точки.
В противном случае если для каждой границы выбраны произвольные начальные точки, то надо сдвигать одну из цепочек (по кругу) и определять В по уравнению (8.5-9) для каждого сдвига. Число сдвигов, требуемое для выг<олнения всех необходимых сравнений, равно п>ах((С,(, (Се() Пример. На рис. 8.54, а и б показаны эталонные границы для двух классов объектов. Границы были аппроксимированны многоугольниками (рис. 8.54, в и г). Затем в результате вычисления внутренних углов между сегментами л>ногоугольника были сформированы цепочки, причем многоугольник обходился в направлении по часовой стрелке. Углы были закодированы одним из восьми возможных символов, соответствующих прнрашению 45; 0'< 0 < 45', 8,: 45' < 0 < 90', ..., 8,; 315'< 0 < 360', Результаты вычисления ((> для эталонной границы объекта ! и его пяти моделей показаны на рнс.
8.54,д, где записи соответствуют значениям В =А/В (например, обозначение 1.с соответствует третьей цепочке для объекта класса 1). На рис. 8.54, е показаны результаты для цепочек объекта второго класса. Наконец, на рис, 8.54,ж показана таблица значений В, полученных в результате сравнения цепочек обоих классов. Важно отметить, что в последней таблице все значения )Р существенно меньше, чем в предыдущих двух таблицах. Из этого следует, что значения В соответствуют высокой степени различия между двумя классами объектов. Например, если бы цепочка !.а соответствовала неизвестной форме границы, то ее наименьшее значение при сравнении с другой цепочкой класса 1 было бы равно 4,6>.
Наоборот, ее наиболыпее значение прп сравнении с цепочкой второго класса было бы 1,24. Отсюда следует, что эта цепочка относится к первому классу. 4об Синтаксические методы. Среди структурных л>етодов синтаксические методы наиболее часто применяются для задач распознавания образов. Основная идея, лежащая в основе синтаксических методов, состоит в подробном описании структурной модели простейшими элементами в соответствии с набором пра- 18 !с 11 ! 34 132 !47 1,33 ! 48 ! 48 1,48 140 1., п,,п „ 1,33 14 18 2с 1,02 1,18 1, !9 >,М 1!9 1,Ы 1,>Ч ! 72 1 39 ! 02 2.с 0,93 1,07 1,08 1 19 1 24 1,28 ! О7 1,Оз Ойв 1 14 1,11 1,18 Рнс. 8.54.
Грвннпы объектов, прннвдле>квщнх двум различным классам (а, б), соответсгвующне нм вппрокснмвпнн многоугольниками (в, г) н твблнпы >2 = А(В (с> — ж) 1276) вил (грамматикой). Сначала рассмотрим грамматики цепочек, а затем распространим эти идеи на грамматики более высокой размерности, Грамматики цепочек. Предположим, что мы имеек> два класса объектов о>1 и о>2, которые представляются цепочками из простейших элементов (равд. 8.5.2). Каждый простейший элемент можно интерпретировать как допустимый символ некоторой грамматики, где под грамматикой подразумевается набор синтаксических правил (отсюда название — синтаксическое распознавание образов).
С помощью этих правил из допустимых символов можно создавать предлоясения, В данном случае предло- жениями являются цепочки символов, которые в свою очередь служат для описания моделей объектов. Рассмотрим две грамматики 6, и 6ь Правила грамматики 6, позволяют создавать предложения только для объектов класса эоь а правила грамматики 6э — только для объектов класса сов. Набор предложений, созданный грамматикой 6, называется языком и обозначается Е(6). После определения двух грамматик 61 и 6д процесс синтаксического распознавания образов в принципе довольно прост. Если дано предложение, представляющее неизвестную модель объекта, задача состоит в определении языка, к которому это предложение относится. Если предложение относится к языку Е(6,), мы говорим, что модель описывает объект класса шь Аналогично мы говорим, что объект относится к классу шь если данное предложение из языка Е(6э). Однако предложение может одновременно относиться сразу к двум языкам (.(6,) и с,(6в).
В этом случае оно отбрасывается. Когда имеется больше двух классов моделей объектов, подход синтаксической классификации тот же, что описанный выше, Различие заключается в том, что рассматривается большее число грамматик (по меньшей мере одна на класс), В этом случае модель объекта относится к классу <а„если она является предложением только из языка 1.(6,). Если предложение не относится ни к одному языку пли же относится сразу к нескольким, то модель, соответствующая этому предложению, исключается из рассмотрения Для цепочки определим грамматику как четверку 6=(У, ~:, Р, 5), (8,5-10) где У вЂ” конечный набор негерминальных символов или переменных, Š— конечный набор терминальных символов или констант, Р— конечный набор производящих правил (правил вывода).
Символ 5, принадлежащий У, является начальиыси символом. Наборы У и Е не должны пересекаться. Далее нетерминальные символы обозначаются прописными буквами: А, В, ... ..., 5, .... Константы обозначаются строчными буквами начала алфавита: а, Ь, с, а цепочки из констант — строчными буквами конца алфавита: о, и, х, у, г. Цепочки, состоящие из констант и переменных, обозначаются строчными буквами греческого алфавита: а, р, 8, ....
Пустое предложение (предложение, не имеющее символов) обозначается ),, Наконец, если задан набор символов У, то У' будет обозначать все предложения, составленные из элементов У, Грамматики цепочек характеризуются в основном видом их производящих правил. Определенный интерес для синтаксического распознавания образов представляют регулярные грам- 468 магики, производящие правила которых всегда имеют вид Л-м аВ или А-э а, причем А и В принадлежат У, а а принадлежит 2 . Представляют интерес также контекстно-свободные грамматики с производящими правилами вида А»а, А принадлежит У, а сс принадлежит набору (У() ~) — д; т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
