Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 92
Текст из файла (страница 92)
д. до любого желаемого уровня детальности. Зтот процесс последовательного уточнения структурного описания сцены носит заметное сходство с процессом получения структурного описания английского предложения. В соответствии с этим естественно рассмотреть понятие грамматики как некоторой формальной системы, в рамках которой можно описывать изображение. Такая формальная система тщательно изучалась в связи с ее приложениями к языкам программирования и к задачам автома- 466 Гл.
!г. Сосгновлекие и воработка описвннй тического перевода с языка на язык; следовательно, синтаксический подход ') привлекателен как совокупность сложившихся теоретических методов, потенциально применимых к задачам анализа сцен. Мы начнем наше обсуждение синтаксических методов, ограничив свое внимание одномерными строками символов. Такие строки символов, конечно, представляют собой исходный материал.
обычного синтаксического анализа. Позднее мы рассмотрим способы, посредством которых идеи обычного анализа могут примениться на двумерной плоскости изображения. Грамматика представляет собой формальную конструкцию, содержащую образования трех типов: терминальные или первичные символы, нетерминальные символы и правила подстановок илн пороясдающие правила. Грамматика может использоваться либо в порождающем, либо в анализирующем режиме.
Когда грамматика используется в порождающем режиме, она позволяет конструировать строки терминальных символов путем последовательного при. менения правил подстановок. Строка терминальных символов, построенная с помощью данной грамматики в порождающем режиме, называется предложением. Множество всех предложений, которые могут быть построены с помощью данной грамматики, называется язьисом этой грамматики. Прежде чем рассматривать применение грамматики для анализа, проиллюстрируем эти абстрактные идеи на примере очень простой грамматики.
Пусть дано множество терминальных символов Т= ==(а, Ь) н множество нетерминальных символов У=(5, В). Символ 3 означает «предложение» (зеп1епсе) и, таким образом, отличается от других нетерминальных символов. Наша иллюстративная грамматика содержит следующие пять правил подстановок: 1. 5::=а. 2, 5::=аЯ. 3. 5::=-аВ. 4. В::=Ь. 5. В::=ЬВ. Когда грамматика используется в порождающем режиме, символ ю:=» имеет смысл «заменить символ слева строкой символов справа». Применим грамматику для построения простого предложения. Начнем с того, что приравняем символ, обозначающий предложение, самому себе: Произвольно выбрав правило 2 и применив его к правой части равенства, получаем Я=аЯ. «1 В отечественной литературе применяется термин лингвистический, нлн тррктррнмй, подход.— Прим.
перев. !2.2. Фор»»««»н«е пр«дсаа«ление очи«ание Применяя правило 2 еще раз, получаем 5=аа5. Теперь, применив правило 3, получаем 5==аааВ. Применяя правило 5, мы получаем 5= Ь5. И наконец, применение правила 1 дает нам 5 =-аааЬа, и дальнейшие подстановки невозможны. Таким образом, если применять порождающие правила в последовательности 2, 2, 3, 5, ! к исходному символу предложения 5, порождается роследовательность терминальных символов аааЬа. Очевидно, что применение правил в другой последовательности даст другую последовательность символов.
Теперь обратимся к задаче использования грамматики для анализа строки первичных символов. Мы должны ответить на два вопроса: во-первых, является ли данная строка предложением языка, определяемого грамматикой, и, во-вторых, какова структура строки, если она является предложением? Процесс ответа на эти вопросы посредством использования грамматики в анализирующем режиме называется грамматическим разбором. Один из методов грамматического разбора строки, называемый разбором сверху вниз, основан на конструировании дерева всех возможных способов, посредством которых можно применять правила подстановок для построения стоящей на первом месте исходной строки.
Если нельзя найти такую последовательность правил, строка не является предложением; если имеется единственная последовательность, то полный путь по дереву определяет структуру строки. Если имеется более чем одна последовательность правил, структура строки синтаксически неоднозначна. Понять, что такое грамматический разбор, проще всего с помощью примера. Предположим поэтому, что мы разбираем построенную ранее строку аааЬа (которая, конечно, является предложением), Основная идея заключается в том, чтобы просмотреть набор порождающих правил и проверить, какие из них применимы к исходной строке. Поскольку строка начинается с символа «а», применимы только первые три правила.
Поэтому строка имеет форму'либо «о», либо «а5», либо «аВм Очевидно, что строка не просто «а». Можно было бы для начала отнести ее к форме «аВ», если бы мы не видели из правил, что все формы «В» должны начинаться с символа «Ь»; поэтому наша строка не может иметь форму «аВ». Следовательно, строка должна иметь форму «а5», где теперь 5 =ааЬа. На рис. 12,2 Гя. 1я, Састааяеиие и обрабоии«а описаииа этот повторяющийся процесс показан в виде дерева грамяиипичгского разбора. Цифры на ветвях дерева представляют собой номера правил. Узлы помечены крестом, если для них нет применимых правил подстановок.
Заметим, что законченное дерево определяет последовательность правил подстановок 2, 2, 3, 5, 1, которая использовалась для порождения исходной строки. Более того, в этом примере Ркс. !2.2. Г«ерево грамматического разбора. имеется только один путь через дерево; следовательно, предложение аааЬа порождается грамматикой единственным образом. Читатель, может быть, уже заметил, что легко дать характеристику языку нашей очень простой грамматики; он состоит из всех последовательностей символов «аа и «Ьа, начинающихся с «аъ и не содержащих нигде двух символов «Ь» подряд. В более общем случае не так легко охарактеризовать ни язык грамматики, ни грамматику, порождающую данное множество предложений.
Эти вопросы и родственные им вопросы эффективности грамматического разбора и учета его неоднозначности относятся к области теории формальных языков. Как бы ни были интересны эти темы, мы воздержимся от их обсуждения и сосредоточимся на основной проблеме — применении синтаксических методов к двумерным сценам. Основная теоретическая трудность, с которой приходится сталкиваться при распространении формального синтаксиса на, двумер- !2.2.
Формальное нредсьналленн«оно«аной ный случай, проистекает из следующего фундаментального факта: одномерная линия упорядочена естественным образом, а двумерная плоскость — иет. Следовательно, естественный способ обработки одномерной строки символов заключается в замене одного символа за другим по цепочке. Никакой естественной аналогии для двумерного случая не существует. Чтобы сделать это различие более наглядным, рассмотрим снова простую сцену рис. 12.1. На рис. 12,3 показано одно возможное дерево грамматического разбора для этой сцены (не нуждающееся в объяснениях). Однако, даже если мы укажем точные описания для таких первичных элементов, как «поверх- Рис. 12.3.
Возмоисное дерево грамматического разбора длн сцены рис. 12.1. ностып это дерево будет описывать сцену только весьма смутно. Например, три поверхности можно соединить вместе различными способами, н только некоторые из них образуют коробки. Проблему, поставленную отсутствием естественного упорядочения для плоскости, пытались решить различными путями. Может быть, наиболее прямой состоит в том, чтобы опираться только на границу объекта, пользуясь, таким образом, естественным упорядочением одномерного множества точек. В качестве тривиального примера такого подхода мы можем определить «четырехугольник» следующим образом: четырехугольник:: = линия + линия + линия + линия, где знак «+» означает сцепление и подразумевается, что цепочка должна замкнуться на себя.
В этом простом примере выбор первичных элементов (прямых линий) очевиден. Для объектов более общего вида, ограниченных, скажем, гладкими кривыми, выбор менее ясен. Даже после того, как мы задали некоторое множество первичных кривых, часто оказывается нелегко решить, где на границе объекта кончается один первичный элемент и начинается другой. 4бо Гл. 12. Составление и обработка описаний Эта проблема идентификации первичных элементов в сцене не является особенностью только подхода, основанного на описании границы: такого рода трудность характерна для всех синтаксических методов. Подход, основанный на описании границы, имеет очевидные ограничения.
Предположим, например, что мы хотим описать коробку на рис. 12.1, используя прямолинейные отрезки в качестве первичных элементов. Если считать, что четырехугольные поверхности (нетерминальные символы) уже описаны в терминах прямолинейных отрезков, то нам еще нужно задать отношения между тремя четырехугольниками. Один из способов, посредством которых это может быть 1 В з сделано, состоит в том, чтобы задать «крюки» или точки притяжения на каждом четырехугольнике. Такой я , вариант показан на рис. 12.4, где для ясности мы изобразили четырехугольники в таком же виде, как и стороны коробки на рис. Рис. Шл Разделение коробки иа четырех.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
