Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 99
Текст из файла (страница 99)
Подобным же образом для плоскостей В и С мы напишем и, У„=Ь„ иь' ув =Ьв и, ча=-Ь„ и,.ч„=-Ь, иь чс Ьь иь'чс =Ьь иь Ус =Ьв иг ьс Ьг' Эта система линейных уравнений отображает тот факт, что различные характерные точки 1в этом примере — все вершины) лежат на определенных плоскостях многогранника. Векторы и~ определяются прямо по картинке и, следовательно, известны, Каждая из трех плоскостей определяется одним трехмерным вектором, а каждая из семи точек — скаляром.
Следовательно, мы имеем систему из 12 уравнений с 16 неизвестными. Если уравнения линейно независимы, можно найти единственное решение, зафиксировав любую четверку неизвестных переменных, при условии, как мы видели выше, что фиксированные переменные независимы. Поучительно найти для случая произвольной картинки (с многогранником) число уравнений и переменных, используемых для вы- Гл. /2.
Составление и обработка описания ражения инцидентности точек и плоскостей. Для задания каждой плоскости необходимы три числа, а для каждой характерной точки — еще одно число, поэтому (Число переменных) =Зх(Число плоскостей)+ + (Число характерных точек). С другой стороны, для каждой характерной точки на каждой пло- скости может быть записано одно уравнение, поэтому (Число уравнений) =- ~е (Число характерных точек на плоскости).
Разность между числом переменных и числом уравнений дает нижнюю границу для числа переменных, которые должны быть известны при определении трехмерной структуры многогранника. Нижняя граница достигается, когда результирующая система линейных уравнений имеет полный ранг '). До сих пор разработанный метод был полностью общим. Для заданной произвольной картинки ннцидентность точек и плоскостей можно выразить в виде линейной системы, обычными методами найти ранг системы и определить число свободных параметров. Если какими-либо другими средствами можно найти положения необходимого числа точек (независимых), то уравнения могут быть решены единственным образом, и задача определения трехмерной структуры оказывается решенной.
Теперь нам хотелось бы дать другую интерпретацию описанной выше процедуры. Интерпретация ограничена картинками трехгранных тел, но представляет интерес, поскольку она уточняет расплывчатое понятие «сцепления» одной грани многогранника с другой. Интерпретация основана на использовании определенного вида дуального графа изображения многогранника. Узлы дуального графа соответствуют видимым плоскостям многогранника; два узла дуального графа связаны дугой, если у их граней имеется общее (и видимое) ребро '). Однако, если две плоскости связаны более чем одним ребром (которые все обязательно.коллинеарны), между соответствующими узлами помещается только одна дуга.
Рис. 12.18, а показывает ступенчатое трехгранное тело; соответствующий дуальный граф показан на рис. 12.18, б. Чтобы показать, как можно х) То есть когда ранг матрицы снстемы равен числу неизвестных.— Прим. лере. ') Заметим, что процедура разметки линий, обсуждавшаяся выше, позволяет нам установнть по картинке, имеют лн две грани многогранника общее ребро. Две грани имеют общее ребро, если разделяющая нх лянка помечена либо плюсом, либо минусом, если разделяющая нх линия помечена стрелкой, она представляет собой закрывающнй край, а не общее ребро.
! ».4, Анализ многогранно«о» 49! использовать дуальный граф ного процесса сцепления одн предположим, что положения вершин А, С, 0 и Е известны; тогда известны положения граней 1 и 5. Чтобы показать, что эти грани известны, мы сольем вместе соответствующие узлы, как это видно на рис. 12.18, г; другие дуги, связанные с узлами 1 и 5, остаются связанными и после слияния, так же как и в процессе слияния узлов, обсуждавшемся выше. Чтобы поддержать соответствие с последующими шагами, рис.
12.18, в показывает предварительную дугу, введенную между узлами 1 и 5. Мы будем следовать правилу, что узлы могут быть слиты, если они связаны по крайней мере двумя дугами. Продолжение показано на рис. 12.18, г, где слитный узел «1,5» означает, что положение граней 1 и 5 в трехмерном пространстве известно. Теперь узел «1,5» связан двумя дугами с узлом 2. Это означает, что грань 2 имеет два общих неколлинеарных ребра с гранями, положение которых известно; поскольку известны положения граней, положения ребер также известны. Поскольку плоскость определяется двумя лежащими на ией произвольными неколлинеарными линиями, положение грани 2 также извес узел 2 сливается с узлом «1,5» для интерпретации последовательой грани многогранника с другой, тно. Чтобы отобразить этот факт„ , образуя узел «1, 5, 2», как показа- д Рис.
12.18. Слияние дуальиого графа трек- граииого тела. Гт IК Соетаеееиие и обработка описаний но на рис. 12.!8, д. Этот процесс в нашем примере может повторяться, пока все первоначальные узлы ие сольются в один. Проиллюстрированный выше процесс реально представляет собой всего лишь способ слежения ва всех стадиях анализа за теми гранями многогранника, положение которых в трехмерном пространстве уже было определено, Основное правило слияния двух узлов, если они связаны по крайней мере двумя дугами, представляет собой другую формулировку условий, при которых положение одной грани может быть найдено по известным положениям смежных с ней других граней. Первоначальное добавление дуги может рассматриваться как некоторая уловка, позволяющая развязать процесс. Оиа равносильна утверждению, что две грани имеют общие неколлинеариые ребра; это явно невозможно, но дополнительное ребро представляет собой фиктивный эквивалент того, что положения двух плоскостей заданы.
В данном примере это был случай, когда добавление единственного ребра позволяет нам слить все узлы в один. Когда такое имеет место, т. е. когда мы можем добавить единственную дугу таким образом, что все узлы могут быть последовательно слиты вместе, мы говорим, что граф 1-слиаае,иый.
Мы неформально показали, что структура видимой части трехгранного тела может быть определена йо четырем известным точкам, если дуалвный граф 1-сливаемый. В более общем случае дуальный граф й-сливаемый, если нужно добавить не меньше, чем й дуг, чтобы посредством ряда слияний уменьшить граф до единственного узла.
Нетрудно показать, что структура видимой части трехгранного тела определяется по й+3 независимым точкам во всех случаях, когда дуальный граф й-сливаемый. Например, многогранник рис. 12.10, а имеет 2-сливаемый дуальный граф, и легко убедиться, что для определения видимой структуры должны быть известны положения пяти точек.
С практической точки зрения дуальный граф приводит к альтернативному решению задачи определения числа степеней свободы в трехмерной структуре многогранника, а именно задача определения ранга системы линейных уравнений может быть заменена задачей определения степени сливаемости графа. Более того, конкретная последовательность слияний соответствует последовательности шагов, которые может сделать человек, раскрывая трехмерную структуру посредством цепного процесса. Это само по себе может привести к полезным догадкам, поскольку это демонстрирует шаги процесса, а не прячет их в одном «глобальном» процессе типа обращения матрицы.
12.б. Библиографические и исторические сведения 493 ИЬЗ. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ СВЕДЕНИЯ Исследователи, работавшие в области анализа сцен, в течение некоторого времени открыли много задач, требующих методов решения, основанных на описании, а не на классификации. Первоначальная работа в этом направлении была основана на синтаксическом анализе, и, может быть, первый пример разложения картинки на первичные элементы был дан Гримсдейлом и др. (1959). Синтаксический подход получил дополнительный толчок в результате работ Кирша (1964) и Нарасимхана (1964, 1969), в которых были представлены формальные грамматики для целей обработки изображений.
О применении синтаксических методов к задаче автоматического анализа хромосом сообщил Ледли (1964), который мог использовать только подход, основанный на описании границы. Шоу (1969, 1970) разработал развитый «язык описания изображений», фрагмент которого мы представили как метод стандартных точек притяжения. Гренандер (1969) дал абстрактное математическое описание механизма преобразования идеальных, или незашумленных, объектов в реальные. Пфальц и Розенфельд (!969) в попытке найти естественное обобщение синтаксического метода на два измерения ввели грамматику сетей. Эванса (1970) особенно интересовало определение по набору сцен грамматики, которая может их порождать.
Уинстон (1970) использовал графы отношений в исследовании, направленном на построение абстрактных моделей объектов по набору сцен. Два хороших обзора по синтаксическим методам в анализе сцен были написаны Миллером и Шоу (1968), а также Фу н Свайном (1971). Фельдман и Грие (1968) написали, видимо, самое лучшее введение в обширную литературу по синтаксическому анализу и грамматическому разбору; Эрли-(1970) описал особенно эффективный алгоритм грамматического разбора. О применении трехмерных моделей в анализе сцен, которое в ретроспективе можно считать прямым подходом, не было известно ничего до появления имевшей большой резонанс статьи Робертса ((965).
Дуда и Харт (1970) использовали частичные трехмерные модели для управления анализом сцены,- выполняемым подвижным роботом. Барроу и Поппельстоуи (1971) хранили информацию о модели в виде графов отношений, описывающих скорее изображения объектов, чем сами объекты. Методы подбора модели часто требуют решения проблемы невидимых линий — проблемы определения той части трехмерного объекта, которая видна в данной проекции.
Алгоритмы для решения такой задачи были описаны Уориоком (1968), Лоутрелом (!970) и Букнайтом (1970). Кажущаяся простота многогранных объектов привлекла внимание многих исследователей. Хаффман (1971) интересовался в первую очередь формулировкой свойств изображений реальных трех. гранных тел, чтобы определять, не показывает ли картинка иевоз- Гл. /2. Составление и обработка описаний можный, или бессмысленный, объект; наша процедура разметки линий основана прямо на его работе. Альтернативная процедура дана Клоувзом (1971).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
