Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 93

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 93)

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

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

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

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

Набор первичных элементов изображения. хотя, конечно, не единственно возможное выражение: цилиндр =о+Ь+о+1+Ь. С помощью не нуждающихся в объяснении нетерминальных символов это предложение можно разобрать следующим образом: а+Ь+и+1+Ь. аоноваа нрмшна поверхность цилиндр Нам иет необходимости ограничивать себя только определенными выше операторами «+» и «». Чтобы продемонстрировать еще одну возможность, определим операцию «рнд» как «соединение головы р с головой д и хвоста р с хвостом а». Пользуясь этим дополнительным оператором, мы можем описать изображение цилиндра, например, посредством следующих порождающих правил: 1. Цилиндр ::=Боковая поверхностьеКрышка. 2.

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

В нашем примере независимо от выбора порождающих правил необходимы распознаватели для обнаружения вертикаль- 4б2 Гв. !в. Состав»ение и обработка описаний ных линий н двух видов кривых линий. Заметим также, что мы ничего не сказали о представлении анализируемой картинки; она может быть аналоговым изображением, градиентным изображением, контурным рисунком или может иметь какую-либо другую форму. Мы предполагаем, что распознаватели первичных элементов пригодны для работы с данной конкретной формой представления изображений. Предположим теперь, что нам дана картинка и мы хотим узнать, содержит ли она цилиндр. Применяя процедуру грамматического разбора сверху вниз, мы узнаем из порождающих правил 1 и 2, что цилиндр должен содержать боковую поверхность н что боковая поверхность должна содержать вертикальную линию.

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

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

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

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

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

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

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

12.2.2. ГРАФЫ ОТНОШЕНИЙ Во многих задачах анализа сцен нас интересует описание «на словах», т. е. символически, структуры конкретной сцены. Мы только что видели, что в таких ситуациях могут применяться формальные синтаксические методы; другим средством составления символических описаний являются графы отношений. Вместо того чтобы открывать эту тему формальным определением, возьмемся за нее с помощью примера.

На рис. 12.3 мы показали дерево грамматического разбора для сцены рис. 12.1. Узле«дерева помечены как части сцены; дуги дерева (дуги представляют собой соединения между узлами) не помечены. Хотя эти дуги не имеют точных меток, мы можем заметить, что вкладываемый в них смысл сводится к тому, что узел на нижнем конце дуги «является частью» узла на ее верхнем конце '). Другими словами, дуги дерева грамматического разбора задают определенное отношение между узлами, которые они связывают. ') Более точно, мы должны сказать, что часть сцены, представленная узлом иа нижнем конце дуги, «является частью» части сцены, представленной узлом на верхнем конце дуги.

Зто слишком громоздко, и не стоит говорить так более одного раза. 22.3. Трехмерные недели Основную идею использования дуги для обозначения отношения можно обобщить несколькими очевидными способами. Во-первых, мы можем расширить класс разрешенных отношений с тем, чтобы включить в него каждое отношение, которое удобно устанавливать по изображению. Мы можем также рассматривать не деревья, а графы отношений, чтобы можно было задавать отношения между двумя произвольными узлами. (Граф в общем случае содержит замкнутые петли, а дерево их не содержит.) С помощью этих обобщений мы можем составлять более богатые описания, чем с помощью простых деревьев грамматического разбора.

В качестве иллюстрации предположим, что мы перерабатываем дерево разбора рис. 12.3 в более полное описание сцены рис. 12.1 графом отношений. Мы условимся применять выбранные произвольно отношения «являться частью», «являться видом», «прилегать к», «находиться слева от», «находиться справа от», «находиться над» н «находиться под». Одно из описаний этой сцены графом отношений показано на рис. 12.б. Для удобства мы поместили стрелки на каждой из дуг, чтобы показать смысл отношения, н превратили тем самым граф отношений в направленный грецй.

Направления стрелок были выбраны таким образом, что, если прочесть сначала метку узла в хвосте стрелки, затем метку стрелки и, наконец, метку узла в голове стрелки, получится грубый «перевод на русский язык» '). Заметим, что показанный граф отношений можно сделать более информативным, даже не вводя дополнительных отношений; так, например, круглая поверхность и кривая поверхность цилиндра связаны не только отношением «прилегать к», но и симметричной парой отношений «находиться над» и «находиться под».

Характеристики

Список файлов книги