Робототехника.Фу, Ли, Гонсалес (962794), страница 81
Текст из файла (страница 81)
Древовидная грамматика определяется как пятерка 6 (й(, ~'„Р, г 5), (8 5-! 2) 47к где й( и Х вЂ” соответственно множества терминальных и петер. минальных символов; 5 — начальный символ, который в общем случае может быть деревом; Р— набор производящих правил вида Т, — Ть где Т, и Т, являются деревьями; г — функция ранжировании, которая указывает число прямых потомков вершины, помеченной терминальным символом грамматики. Расширенная древовидная грамматика имеет производящие правила вида А — «а ь с 7) Аз — а где между простейшими элементами из прямых линий устанавливаются связи типа «начало одного с концом другого», а для простейшего элемента в виде окружности связи могут быть установлены в любом месте этой окружности.
В этом случае функция ранжирования имеет следующий вид; г(а)= (О, 1), г(Ь) г(с()= г(е)= (!), г(с)= (2). Отметим, что ограничение, состоя!нее в том, чтобы правила 2, 4 и 6 были применены одинаковое число раз, приведет к структуре, у которой все три ветви будут иметь одинаковую длину. Аналогично, требование, чтобы правила 4 и 6 были применены одинаковое число раз, 473 ! А, ... Л„ где Л, Ль ..., Аи — нетерминальные символы, и а — терминальный символ. Пример. Скелет структуры, показанной на рис. 8.57, а, можно создать с помощью древовидной грамматики, имеющей следующие правила: 1)5 — а 2)А,— Ь ! А, А, д) А,— с 4) Аз — Н 1 1 '12 Аз Аз 5) Л,— «е 6) А,— е Аз Рис. 8.87.
Объект (а) и простеиизие элементы, использоваииые дли представления скелета с помощью древовидиой грзммити. ки (б). — .1 1 Л 1 474 приведет к структуре, симметричной относительно вертикальной оси фигуры, изображенной на рис. 8.57,а. В заключение рассмотрим кратко грамматику, предложенную в работе (95) для построения трехмерных объектов, состоящих из кубических структур. Как и выше, основным моментом Рис. 8.58.
Простейшие элементы в виде вершин (95( при создании объекта с помошью синтаксических л!етодов является подробное описание набора простейших элементов и их взаимосвязей. В этом случае простейшими элементами являются вершины, показанные на рис. 8.58, В зависимости от сг Рис, 8.59 Классифииаиин вершин типа Т. локальной информации вершина типа Т может быть либо вершиной Т1, либо Т,.
Если вершина Т содержится среди вершин параллелограмма, она относится к типу Тш в противном случае она относится к вершине Т1. Эта классификация приведена на рис. 8.59. Грамматические правила заключаются в описании взаимосвязей между структурами (рис. 8.60). Вершины, обозначенные ( 1 Г 1 1 1 77дяргдда !! ! Г ! фвйтттр Я! ! ! ! --- — — — 1 Г 1 lт~атуилв 3 ! И 1 1 1 ! ! 1 1 г 1 1 у нйввр 4'! И и ! ! 1 г — — — — — "-т .! 1 1 фабилоод.
! ! ! 1 1 1 1 1 1 и' ! с ! 1 т, т, 1 1 т, 1 т, 1 Л ! 1 ! ! 1 1 Г 1 1 1 1 1 1 1 сураСГа ЛвитЬла а ф- лсраФала 8 I ! ! 1 8.6. ИНТЕРПРЕТАЦИЯ 8вис 8.60. Правила, используемые для геиерааии трехмерных структур. Пу- атые круги оаиачают, что допустимо насколько типов вершин ~95]. 477 Г ! и ! с ! ! ! г, ! ! Г 1 ! фаФмла 7! ! ! Г ! ! ! ,88аауиа и! ! ! ч г и ! 1 с ! г) ! г ! я с 5 ! ! ! двойными окружностями, обозначают центральные вершины конечного куба объекта, откуда можно осуществлять дальнейшие связи.
Это иллюстрируется рис. 8.61, на котором показан рис. 8.6!. Построение модели с помощью правил, приведенных на рис. 8.60 (958 типичный вывод, использующий правила, приведенные на рис. 8.60. На рис. 8.62 приводятся виды структур, которые могут быть построены с помощью этих правил. В этом разделе мы рассматриваем интерпретацию как процесс, который позволяет системе технического зрения приобрести более глубокие знания об окружающей среде по сравнению со знаниями, полученными с помощью методов, изложенных выше. Рассматриваемая с этой точки зрения интерпретация охватывает данные методы как неотъемлемую часть процесса Ркс. 6,62. Модели трехмерных структур, соадапвые с помощью правил, при- веденных па рпс.
6.60 1951, 478 понимания зрительной сцены. Хотя в области технического зрения она и является объектом активных исследований, достижения пока весьма незначительны. Ниже мы кратко рассмотрим проблемы, представляющие современные исследования в этой области технического зрения. Мощность системы технического зрения определяется ее способностью выделять из сцены значимую информацию при различных условиях наблюдения и использовании минимальных знаний об объектах сцены. По ряду причин (неравномерное освещение, наличие тел, загораживающих объекты, геометрия наблюдения) этот тип обработки представляет трудную задачу. В разд.
7.3 много внимания уделено методам уменьшения разброса в интенсивности. Способы обратного и структурирован. ного освещения, рассмотренные в разд. 7.3, позволяют устранить трудности, связанные с произвольным освещением рабочего пространства. К этим трудностям относятся теневые эффекты, усложняющие процесс определения контуров, и неоднородности на гладких поверхностях.
Это часто приводит к тому, что они распознаются как отдельные объекты. Очевидно, многие из этих проблем обусловлены тем, что относительно мало известно о моделировании свойств освещения и отражения трехмерных сцен. Методы разметки линий и соединений, изложенные в равд. 8.4, представляют собой некоторые попытки в этом направлении, но они не в состоянии количественно объяснить эффекты взаимодействия освещения и отражения. Более перспективный подход основан на математических моделях, описывающих наиболее важные связи между освещением, отражением и характеристиками поверхности, такими, как ориентация 1124, !42, 1891.
Проблема загораживання одних объектов другими имеет место, когда рассматривается большое число объектов в реальном рабочем пространстве. Например, рассмотрим сцену, показанную на рис. 8.63, а. ь!еловек без труда определил бы, что за втулками находятся два гаечных ключа.
Однако для лташины интерпретация этой сцены происходит совершенно по-другому. Даже если бы система была способна идеально выделить группу объектов из фона, то все ранее рассмотренные двумерные процедуры описания и распознавания дали бы плохой результат для большинства загороженных объектов. Применение трехмерных дескрипторов, рассмотренных в разделе 8.4, было бы более успешным, но даже они дали бы неполную информацию. Например, некоторые нз втулок оказались бы частично цилиндрическими поверхностями н средний гаечный ключ был бы представлен двумя отдельными объекталти. Для обработки таких сцен, какая показана на рис.
8.63,а требуются описания, которые должны содержать информацию о формах и объемах объектов, а также процедуры для установ- 479 8.7. ЗАКЛЮЧЕНИЕ 480 !6К.атаев 8.63. Два вида одной трехмерной сцены. ления связей между этими описаниями, даже когда они не являются полнымн. Несомненно, эти проблемы будут решены только путем разработки методов, позволяющих обрабатывать трехмерную информацию (полученную либо в результате непосредственных измерений, лэбо с помощью геометрических методов вывода) и устанавливать (необязательно количественно) трехмерные связи на основе информации об интенсивности образа. В качестве примера читатель может дать подробную интерпретацию объектов, приведенных на рпс. 8.63,а, зз исключением объекта, загороженного отверткой.
Знание о том, в каких случаях интерпретация сцены или части сцены является невозможной, так же важно, как и правильный анализ сцены. Просмотр сцены из различных точек (рнс. 8,63,б) решил бы эту проблему и был бы естественной реакцией интеллектуального наблюдателя. В этом направлении одним из наиболее перспективных подходов являются исследования в области технического зрения, основанного на моделях (33). Основной идеей метода является интерпретация сцены на основе обнаружения отдельных случаев соответствия между данными образа и трехмерными моделямн простейших объемных элементов нлн же целых объектов, представляющих интерес.
Зрение, основанное на трехмерных моделях, имеет другое важное преимущество: оно дает возможность обрабатывать несоответствия в геометрии наблюдения. Изменчивость образа объекта, наблюдаемого из различных положений, является одной из наиболее серьезных проблем технического зрения. Даже для двх мерных случаев, где определена геометрия наблюдения, ориентация объекта может сильно влиять на процесс распознавания. если он пе управляется соответствующим образом (см.
замечания в разд. 8.3). Одно нз пренмупьеств подхода, основанносо на моделях, состоит в том, что в зависимости от известной геометрии наблюдения можно подбирать ориентацию трехмерных моделей с целью упрощения соответствия между неизвестным обьектом и тем, что система видит нз чанной точки наблюдения. Основное внимание в главе уделено понятиям и методам технического зрения, применяемым в промышленных приложениях. Как указывалось в разд. 8.2, сегментация является одним из наиболее важных процессов на ранней стадии распознавания образов системой технического зрения.