8.4. СИНТАКСИЧЕСКОЕ ОПИСАНИЕ ОБРАЗОВ

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

случай. Как отмечалось в § 8.1, в этой главе мы в основном занимаемся двумерными объектами.

Правила подстановки в грамматиках цепочек заключаются в простом соединении цепочек с целью формирования новых. Соединение двумерных структур не является, однако, простым вопросом. Читатель может лично в этом убедиться, рассмотрев разнообразные двумерные структуры, получающиеся в результате соединения простых ненроизводных символов Непосредственное решение этого вопроса связано с заданием положения двумерных объектов достаточно общим образом. Рассмотрим, например, позиционный дескриптор обозначающий, что структура, представленная символом а, расположена над структурой, представленной и позиционный дескриптор означающий, что а находится слева от Квадратная структура , составленная из непроизводных элементов и , описывается при помощи этих дискрипторов предложением Основная трудность при подобном подходе заключается в определении содержания дескрипторов и Так, например, предыдущему описанию квадрата удовлетворяет также и структура Можно считать этот образ допустимым или нет, зависит от конкретной ситуации. Очевидно, однако, что обобщенные позиционные дескрипторы с трудом поддаются точному определению. Чаще всего в таких случаях на взаимоотношения структур налагаются ограничения. В частности, разумным ограничением для дескриптора является требование, чтобы хотя бы часть элемента а находилась над элементом . В таком случае структура не будет считаться допустимой, так как элемент — не находится над элементом и элемент не находится над элементом .

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

простая схема, заключающаяся в соединении структур только в особых точках. Одним из способов достижения этого является требование, чтобы каждая структура имела две выделенные точки. Более того, соединение структур должно происходить только в этих точках. Позднее мы рассмотрим систему синтаксического распознавания образов, использующую этот способ. Как показано на рис. 8.2, а, две выделенные точки в этой системе интерпретируются как «головной» и «хвостовой» концы стрелы. Типичные допустимые правила соединения для данной системы показаны на рис. 8.2,б. Совершенно очевидно, что такой подход эффективно сводит задачу двумерного соединения к эквивалентной задаче действий с цепочками, поддающейся решению с помощью обыкновенной цепочечной грамматики, рассмотренной выше.

Рис. 8.2. (см. скан) Сведение задачи соединения объектов к одномерному случаю посредством обобщенного представления объектов ориентированными отрезками прямых, а — выборочные образы; б — характерные действенные правила соединения обобщенных образов.

Для описания двумерных отношений используется и другая полезная методика, основывающаяся на древовидных структурах. Дерево — это конечное множество Т, состоящее из одного или более узлов, таких, что 1) существует один выделенный узел, называемый корнем дерева, и 2) остальные узлы (исключая корень) разделены на непересекающихся множеств каждое из которых в свою очередь является деревом.

Деревья называются поддеревьями корня. Число поддеревьев узла называется степенью этого узла. Узел с нулевой степенью называется листом, а узел с наиболее высокой степенью — узлом ветви. Наконец, представление образа в виде дерева называется деревом образа

Рис. 8.3. (см. скан) Представление образов в виде деревьев.

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

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