8.5. ГРАММАТИКИ, ИСПОЛЬЗУЕМЫЕ В РАСПОЗНАВАНИИ ОБРАЗОВ

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

8.5.1. Синтаксически ориентированное распознавание

В § 8.3 было отмечено, что формальные грамматики можно использовать в распознавании образов, определяя, является ли данных объект терминальным предложением какой-либо из соответствующих рассматриваемой задаче грамматик. Основным вопросом, после того как определены грамматики, является разработка процедуры, устанавливающей, является или нет данный объект допустимым предложением. Процедура, применяемая для этого в теории формальных языков, называется грамматическим разбором. Мы рассматриваем в основном два типа грамматического разбора: сверху вниз и снизу вверх. Эти названия становятся более осмысленными, если обратиться к семантическому дереву, такому, например, как представленное на рис. 8.1. Вершина или корень (инвертированного) дерева — это начальный символ Терминальные предложения (образы) представляют нижнюю часть или листья дерева. Процедура разбора сверху вниз начинается с корневого символа и заключается в попытках посредством повторяющегося применения грамматических правил получить заданное терминальное предложение. С другой стороны, процедура разбора снизу вверх начинается с конкретного предложения и заключается в попытках дойти до символа с помощью инверсии правил подстановки. В каждом из этих случаев при неудачном исходе грамматического разбора

заданный образ отклоняется как представляющий неправильное предложение.

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

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

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

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

Структуры, напоминающие квадраты, изображенные на рис. 8.4,б, порождаются последовательностью грамматических правил

Это правило заменяет начальный символ непроизводным элементом расположенным над некоторым пока еще не определенным объектом Правило

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

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

Наконец, О, заменяется на два вертикальных непроизводных элемента посредством применения правила

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

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

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

Синтаксически ориентированный грамматический разбор снизу вверх, заключающийся в применении правил подстановки в обратном порядке, происходит следующим образом. Сначала мы пытаемся обнаружить объект определяя, содержит ли данный объект непроизводный элемент слева от непроизводного элемента Если поиск оказался удачным, процедура продолжается; в противном случае образ отклоняется. Заметим, что, поскольку процедура разбора снизу вверх начинается с терминального предложения, сначала должны рассматриваться те правила подстановки, применение которых приводит исключительно к терминальным символам. Для продолжения грамматического разбора необходимо на следующем шаге получить объект который состоит из объекта расположенного над непроизводным элементом Если этот шаг оказался успешным, мы пытаемся вывести начальный символ отыскивая непроизводпый элемент расположенный над Если может быть выведен, то образ принимается, в противном случае на этом шаге он отклоняется. Объекты, изображенные на

рис. 8.4,б, поддаются грамматическому разбору, тогда как объекты, изображенные на рис. 8.4, в, будут отклонены на одном из этапов грамматического разбора.