7.2.1. Пояснение основных понятий

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

Таблица 7.2 (см. скан) Грамматика, порождающая язык для описания нарисованных домов

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

Рассмотрим фигуру которую можно описать цепочкой где интерпретируется как „находиться сверху". Ледли (1962) использовал эту и другие подобные операции (приведенные в табл. 7.1) для определения языка, описывающего нарисованные дома. Контекстно-свободная грамматика, представленная в табл. 7.2, порождает язык, описывающий изображения на рис. 7.1, а, но не на рис. 7.1, б.

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

(кликните для просмотра скана)

Предположим, что изображение преобразовано в цифровую форму, так что программа может „проследить линии», проходя в матричном представлении изображения по соседним элементам, равным 1. Считывание линий осуществляется передвижением „жука“ (показанного в верхнем левом углу рис. 7.2) слева направо и сверху вниз до тех пор, пока не встретится какая-нибудь линия. Жук движется по этой линии до тех пор, пока не приходит к точке, в которой он уже был. Когда встречается разветвление еще не прослеженных направлений, жук поворачивает по часовой стрелке 2). Он последовательно проходит по всем различным компонентам изображения. На рис. 7.2 жук попадает на первую линию в точке 1 и отследит элемент , т. е. трубу. Для того чтобы получить лингвистическую цепочку терминальных символов, нужна грамматика, определяющая каждый элемент в терминах основных передвижений жука; иапример, за горизонтальной линией следует из ее правого конца вертикальная, связанная с другой горизонтальной, проходящей через ее нижний конец, и т. д. Такие грамматики довольно сложно иаписать, поскольку рассматриваемые линии должны оканчиваться на определенных вершинах. Подробности можно найти у Клюса (1969) и Розенфельда (1969а, б), а примеры у Шоу (1969) и Нарасимхана (1965). Во всяком случае, предположим, что, когда достигнута точка 2, жук может определить, что он отследил основной элемент. Он также обнаружит в точке 3 линию, которую он не проходил. Поэтому он движется от точки 3, отслеживая фигуру 3—4—5—6—7—4, т. е. крышу. Поскольку известны координаты как крыши, так и трубы, можно вывести цепочку Просмотр затем возвращается в точку 4, в которой была обнаружена еще не пройденная линия 4—8. Далее будет отслеживаться элемент 4—8—5. В конечном счете будет отслежен весь дом, кроме окон. Для их обнаружения жук должен возобновить свой прерванный просмотр слева направо от точки 1 и продолжать двигаться, игнорируя уже отслеженные линии, пока не наткнется на окна в точках 9 и 10. Когда окна отслежены, их координаты используются для расположения их на стене 6—5—11—12. Теперь у нас есть цепочка терминальных символов, которую можно исследовать обычными методами синтаксического

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

Приведенное описание очень коротко, и, возможно, задача выглядит проще, чем она есть на самом деле. Следует повторить, что рассматриваемые методы хорошо работают для простых рисунков, но быстро становятся запутанными по мере усложнения изображений или даже при незначительной деформации „прямых" линий. К сожалению, действительно интересные изображения именно такого сорта. Так как это специальная тема, мы не будем ее касаться (хорошее введение дано Розенфельдом (1969б)). Мы займемся проблемой вывода, возникающей в анализе изображений.