20.3. СИНТАКСИЧЕСКИЕ МЕТОДЫ

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

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

 

Формальные определения языка

 

Синтаксис — описание языка.

Язык — множество предложений, составленных согласно некоторому набору правил.

Предложение — совокупность терминальных символов.

Терминальный символ — элемент предложения.

Нетерминальный символ — элемент правила подстановки (синтаксического правила).

Алфавит — некоторый конечный набор символов.

Грамматика — совокупность терминальных символов, нетерминальных символов, правил подстановки и начальных символов.

Правило подстановки (Production rule) — правило замены нетерминального символа другим нетерминальным символом или терминальным символом.

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

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

 В качестве примера рассмотрим простое предложение

            (20.3.1)

где  обозначает пробел. Для написания этого предложения используются следующие терминальные символы:

        (20.3.2)

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

    (20.3.3)

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

Рис. 20.3.1, а иллюстрирует синтез предложения (20.3.1) посредством грамматического разбора «сверху вниз». На каждом этапе этой процедуры постепенно продвигаются от целевого символа  к строке терминальных символов, заменяя правые части правила подстановки на их левые части. На конечном этапе строка найденных символов сравнивается с исходным предложением (20.3.1). Если эти предложения совпадают, то процедура заканчивается; в противном случае разбор должен начаться снова при другом порядке применения правил подстановки. Это продолжается до тех пор, пока не будет достигнуто совпадение или не будут исчерпаны все возможности. При использовании грамматического разбора «снизу вверх», схема которого показана на рис. 20.3.1, б, начинают с исходного предложения (20.3.1) и пытаются выполнить преобразования, которые могли бы привести к целевому символу . Правильность преобразований контролируется правилами подстановки. Комбинации из правил подстановки должны проверяться до тех пор, пока не будет достигнут успех или же исчерпаны все возможности. Эффективность алгоритмов грамматического разбора исследована Гриффитсом и Петриком [13].

Синтаксический метод анализа цепочки букв алфавита для проверки ее правильности можно применить и к анализу изображений. При распространении синтаксического подхода на двумерные объекты возникают трудности. Во-первых, отсутствуют очевидные принципы выбора простых терминальных элементов. Что представляет собой аналог буквы алфавита для картинки? Во-вторых, двумерность изображения порождает затруднения при разработке правил подстановки. Что представляет собой аналог цепочки слов для картинки?

На рис. 20.3.2 представлен пример грамматического разбора «сверху вниз» стилизованной сцены на терминальные макросимволы: НЕБО, СОЛНЦЕ, ДВЕРЬ, КРЫША и т. д. Предположим, что эту сцену требуется проанализировать, чтобы определить, имеется ли на ней дом. Следуя по дереву разбора, дом определяется по треугольной крыше и стене, которая в свою очередь имеет окно и дверь. Исходя из общих представлений, дом можно распознавать путем поиска в сцене таких терминальных символов, как ОКНО, ДВЕРЬ, ФАСАД, и проверки их пространственных отношений, чтобы выяснить, образуют ли эти символы нетерминальный символ СТЕНА. Затем необходимо возобновить поиск, чтобы обнаружить символ КРЫША и проверить его структурное отношение к символу СТЕНА. Если все правила подстановки выполняются, то считается, что дом в сцене имеется. Этот пример служит иллюстрацией трудностей, связанных с двумерным синтаксическим анализом изображений.

Рис. 20.3.1. Пример синтеза и анализа предложения. а — синтез «сверху вниз»; 6 — анализ «снизу вверх».

Рис. 20.3.2. Пример грамматического разбора сцены. а - сцена; б — дерево разбора

Успех этой процедуры основан на обнаружении довольно сложных терминальных макросимволов. Число макросимволов может быть достаточно большим при более широком классе сцен. Если макросимволы нельзя обнаружить с достаточной надежностью, то следует произвести разбор сцены при других более простых терминальных символах, таких, как отрезки линий и пятна. Это приводит к быстрому росту числа символов. С увеличением числа символов растет набор правил подстановки. Значительные трудности при решении этих проблем ограничили возможность использования синтаксических методов анализом изображений, имеющих простую структуру. Впервые синтаксический анализ сцен был использован в работах [14] и [15] по символическому представлению рукописного текста. Нарасимхан [16, 17] впервые применил синтаксический метод к более общим классам изображений, уделив особое внимание обработке фотографий треков ядерных частиц в пузырьковых камерах. В модели Нарасимхана терминальные символы, названные основными множествами, состоят из отдельных отрезков линий, узлов, образованных этими линиями, и концов линий.

Рис. 20.3.3. Пример грамматического разбора изображений с помощью языка PDL: а — образны линий; б — разбор буквы W; в — разбор буквы Е.

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

Шоу [18, 19] разработал язык описания изображений PDL (Picture Description Language), основанный на синтаксических понятиях. В этом языке терминальные символы представлены отрезками линий, которые имеют метки «голова» и «хвост». Эти отрезки связываются простыми операторами:

 голова  присоединена к хвосту ,

 хвост  присоединен к хвосту ,

голова  присоединена к голове

и хвост  присоединен к хвосту ,

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

Составным структурам, которые порождаются этими операторами, также приписываются метки головы и хвоста. На рис. 20.3.3 приведен пример образования нескольких букв из простых прямолинейных отрезков. Шоу использовал язык PDL для грамматического разбора фотографий, полученных на искровых камерах.

Рис. 20.3.4. Пример синтаксической классификации хромосом Ледли [21]

Ледли [20, 21] применил синтаксические методы для машинной классификации хромосом. В его системе участки замкнутой границы хромосомы классифицируются на несколько категорий отличающихся формой. На рис. 20.3.4 дан пример участков пяти таких категорий. В результате разбиения границы хромосомы на участки и классификации этих участков образуется строка терминальных символов, которая подвергается грамматическому разбору в соответствии с правилами подстановки. Затем полученное в результате разбора описание хромосомы сравнивается с описанием эталонных хромосом и производится классификация.

Исследования Нарасимхана, Шоу и Ледли показали, что синтаксические методы применимы к задачам анализа «простых» изображений. Вопрос о том, можно ли синтаксические приемы успешно распространить на классы более сложных изображений, остается открытым.