12.2. ФОРМАЛЬНОЕ ПРЕДСТАВЛЕНИЕ ОПИСАНИЙ

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

12.2.1. СИНТАКСИЧЕСКИЕ ОПИСАНИЯ

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

Рис. 12.1. Простая сцена.

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

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

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

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

Прежде чем рассматривать применение грамматики для анализа, проиллюстрируем эти абстрактные идеи на примере очень простой грамматики. Пусть дано множество терминальных символов и множество нетерминальных символов . Символ S означает «предложение» (sentence) и, таким образом, отличается от других нетерминальных символов. Наша иллюстративная грамматика содержит следующие пять правил подстановок:

Когда грамматика используется в порождающем режиме, символ имеет смысл «заменить символ слева строкой символов справа». Применим грамматику для построения простого предложения. Начнем с того, что приравняем символ, обозначающий предложение, самому себе:

Произвольно выбрав правило 2 и применив его к правой части равенства, получаем

Применяя правило 2 еще раз, получаем

Теперь, применив правило 3, получаем

Применяя правило 5, мы получаем

И наконец, применение правила 1 дает нам

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

Теперь обратимся к задаче использования грамматики для анализа строки первичных символов. Мы должны ответить на два вопроса: во-первых, Является ли данная строка предложением языка, определяемого грамматикой, и, во-вторых, какова структура строки, если она является предложением? Процесс ответа на эти вопросы посредством использования грамматики в анализирующем режиме называется грамматическим разбором. Один из методов грамматического разбора строки, называемый разбором сверху вниз, основан на конструировании дерева всех возможных способов, посредством которых можно применять правила подстановок для построения стоящей на первом месте исходной строки. Если нельзя найти такую последовательность правил, строка не является предложением; если имеется единственная последовательность, то полный путь по дереву определяет структуру строки. Если имеется более чем одна последовательность правил, структура строки синтаксически неоднозначна.

Понять, что такое грамматический разбор, проще всего с помощью примера. Предположим поэтому, что мы разбираем построенную ранее строку (которая, конечно, является предложением). Основная идея заключается в том, чтобы просмотреть набор порождающих правил и проверить, какие из них применимы к исходной строке. Поскольку строка начинается с символа применимы только первые три правила. Поэтому строка имеет форму либо либо либо Очевидно, что строка не просто Можно было бы для начала отнести ее к форме если бы мы не видели из правил, что все формы должны начинаться с символа ; поэтому наша строка не может иметь форму Следовательно, строка должна иметь форму где теперь . На рис. 12.2

этот повторяющийся процесс показан в виде дерева грамматического разбора. Цифры на ветвях дерева представляют собой номера правил. Узлы помечены крестом, если для них нет применимых правил подстановок. Заметим, что законченное дерево определяет последовательность правил подстановок 2, 2, 3, 5, 1, которая использовалась для порождения исходной строки.

Рис. 12.2. Дерево грамматического разбора.

Более того, в этом примере имеется только один путь через дерево; следовательно, предложение порождается грамматикой единственным образом.

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

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

случай, проистекает из следующего фундаментального факта: одномерная линия упорядочена естественным образом, а двумерная плоскость — нет. Следовательно, естественный способ обработки одномерной строки символов заключается в замене одного символа за другим по цепочке. Никакой естественной аналогии для двумерного случая не существует. Чтобы сделать это различие более наглядным, рассмотрим снова простую сцену рис. 12.1. На рис. 12.3 показано одно возможное дерево грамматического разбора для этой сцены (не нуждающееся в объяснениях). Однако, даже если мы укажем точные описания для таких первичных элементов, как «поверхность», это дерево будет описывать сцену только весьма смутно.

Рис. 12.3. Возможное дерево грамматического разбора для сцены рис. 12.1.

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

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

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

Эта проблема идентификации первичных элементов в сцене не является особенностью только подхода, основанного на описании границы: такого рода трудность характерна для всех синтаксических методов.

Подход, основанный на описании границы, имеет очевидные ограничения. Предположим, например, что мы хотим описать коробку на рис. 12.1, используя прямолинейные отрезки в качестве первичных элементов. Если считать, что четырехугольные поверхности (нетерминальные символы) уже описаны в терминах прямолинейных отрезков, то нам еще нужно задать отношения между тремя четырехугольниками. Один из способов, посредством которых это может быть сделано, состоит в том, чтобы задать «крюки» или точки притяжения на каждом четырехугольнике. Такой вариант показан на рис. 12.4, где для ясности мы изобразили четырехугольники в таком же виде, как и стороны коробки на рис. 12.1. Синтаксическое описание такой коробки может указывать с помощью подходящих обозначений, что «четырехугольник А, крюк 1, притягивает четырехугольник С, крюк 4», и т. д. для всех вершин.

Рис. 12.4 Разделение коробки на четырехугольники.

Сходный метод задания отношений между первичными элементами основан на стандартных точках притяжения. Пусть мы заранее договорились, что каждый первичный элемент имеет две характерные точки — голову и хвост. Сцеплению двух терминальных символов придается смысл «сложения векторов», т. е. сцепления по принципу «голова с хвостом» первичных элементов изображения, связанных с терминальными символами. Развивая эту мысль, примем, что каждая нетерминальная конструкция изображения также имеет голову и хвост. Ее хвост совпадает с хвостом начального первичного элемента в ее определении, а ее голова совпадает с головой последнего первичного элемента. Таким образом, если терминальные символы а, b и с представляют три первичных элемента изображения, то нетерминальная цепочка А, определяемая формулой будет иметь в качестве хвоста хвост элемента «а», а в качестве головы голову элемента «с», т. е. формальная система, имеющая дело со сцеплением (или с анализом) терминальных

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

Рис. 12.5. Набор первичных элементов изображения.

Мы тогда запишем вполне очевидное, хотя, конечно, не единственно возможное выражение:

С помощью не нуждающихся в объяснении нетерминальных символов это предложение можно разобрать следующим образом:

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

1. Цилиндр

2. Боковая поверхность

3. Крышка

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

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

Предположим теперь, что нам дана картинка и мы хотим узнать, содержит ли она цилиндр. Применяя процедуру грамматического разбора сверху вниз, мы узнаем из порождающих правил 1 и 2, что цилиндр должен содержать боковую поверхность и что боковая поверхность должна содержать вертикальную линию. Поэтому мы просматриваем картинку, чтобы определить расположение вертикальной линии. (Заметим, что, если бы мы разбирали одномерную строку символов, мы бы просто осмотрели первый элемент.) Найдя вертикальную линию, мы будем считать ее нижний конец головой, а ее верхний конец хвостом, поскольку нас скорее интересует «да, чем «и». Из порождающего правила 2 мы видим, что с головой вертикальной линии должен соединяться первичный элемент , и поэтому осматривается область вокруг нижнего конца вертикальной линии. Если элемент «b» не найден, мы должны снова поискать какую-то другую вертикальную линию. Предположим, что, напротив, элемент «b» найден. Как предписывает порождающее правило 2, окрестность конца кривой «b» осматривается с тем, чтобы определить положение второй вертикали. Если она найдена, мы можем заявить, что найдена боковая поверхность. Теперь внимание переключается на поиск крышки, соединенной с боковой поверхностью согласно предписанию порождающего правила 1. Если такая крышка и в самом деле найдена, процесс разбора успешно заканчивается; более того, мы имеем подробное описание, которое позволяет нам идентифицировать части изображения с определенными частями абстрактного «цилиндра».

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

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

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