12.4.2.     ОБЪЕДИНЕНИЕ ОБЛАСТЕЙ В ОБЪЕКТЫ

Фундаментальной проблемой в анализе изображений многогранников является проблема разделения изображения на отдельные объекты. В дальнейшем мы будем обсуждать эвристический подход к этому классу проблем — подход, который основан на догадке и интуиции, но не опирается на какой-либо полный теоретический анали?. Однако, прежде чем описывать какие-то специальные методы, следует сделать несколько предварительных замечаний.

Предположим, что у нас есть контурный рисунок, показывающий несколько многогранников, которые, возможно, закрывают друг друга, и мы хотим разделить картинку на отдельные тела. Чтобы сформулировать задачу несколько более точно, мы можем рассматривать контурный рисунок как набор отделенных друг от друга областей; задача заключается в соединении этих областей в группы таким образом, чтобы каждая группа представляла на картинке один многогранник. Заметим теперь, что, если у нас имеются предварительные сведения об определенном многограннике из окружающей обстановки, мы можем для решения задачи использовать какой-то вариант метода подбора модели; здесь же мы примем, что знаем только то, что все объекты суть многогранники. Первое, что нужно отметить при таком допущении,— это то, что задача не имеет однозначного решения. Чтобы показать это, рассмотрим снова рис. 12.10, г. Мы отмечали раньше возможность того, что перевернутый блок «L» может либо опираться на плиту, либо плавать над ней. Если имеет место последний случай, блок «L» и плита, безусловно, различные объекты; если первый, то блок «L» либо связан с плитой (в этом случае они вместе образуют единый невыпуклый многогранник), либо представляет собой отдельное тело. Здесь имеется дополнительно и более глубокий вид двусмысленности, которую следует учитывать: каждая область сцены может интерпретироваться как основание объекта пирамидальной формы. Вершины пирамид закрыты основаниями, а сами пирамиды разме

щены в пространстве таким образом, что их основания как раз образуют области картинки. (Заметим, что мы не приняли никакой гипотезы об опоре для объектов; мы не приняли, что камера находится в общем положении, и, наконец, мы не приняли, что все многогранники степени 3.) В свете этих замечаний очевидно, что поставленная задача разделения картинки на объекты не является корректной, поскольку не имеется тестов для проверки правильности предполагаемого решения. Тогда самое большое, на что мы можем надеяться, будет метод разделения, дающий «разумные» ответы для большинства картинок, т. е. мы можем рассчитывать на решения, которые большинство людей сочтет «честными» и пріавдоподобны- ми.

Чтобы обосновать эвристический подход, которому мы будем следовать, рассмотрим простой многогранник, показанный на рис. 12.13а.

В этом простейшем из примеров мы, конечно, ожидаем, что любой разумный метод разделения отнесет области 1, 2 и 3 к одной группе, а область 4 (фон) к другой. Если мы просмотрим семь видимых вершин многогранника, мы увидим, что три имеют форму V (по определению предыдущего раздела), три — форму

Wu однаформу У. Такой осмотр вместе с тем обстоятельством, что области 1, 2 и 3 составляют одну группу, подсказывает следующие эвристические правила:

1.   Вершина типа Y свидетельствует о том, что три области, сходящиеся в Y, должны быть сгруппированы вместе.

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

На тех же основаниях мы можем также выдвинуть правило, согласно которому вершина типа V свидетельствует о том, что две об-

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

3.   Вершина типа X свидетельствует в пользу группировки областей, лежащих по разные стороны «сквозной прямой» линии в X. (На рис. 12.13, б вершина А свидетельствует в пользу объединения областей 5 и 6 в одну группу и областей 7 и 8 в другую.)

Теперь, наконец, рассмотрим вершины С и D типа Т. Мы видели в предыдущем обсуждении,' что поперечина Т всегда закрывает более удаленную часть сцены (это справедливо независимо от того, имеют многогранники степень 3 или нет). Однако тот факт, что ножки двух Т коллинеарны, говорит больше, чем просто о загораживании; он подсказывает, что области, лежащие с одной и той же стороны от каждой из ножек, являются частями одного и того же объекта. Здесь может оказаться, что по одну и ту же сторону от каждой из ножек лежит одна область; в этом случае свидетельство в пользу группировки областей является ценным, но избыточным. Заметим в качестве примера, что вершины С и D на рис. 12.13, б свидетельствуют о том, что области 2 и 3 принадлежат одной и той же группе; они дают также избыточное свидетельство о том, что область 9 вблизи точки С принадлежит к той же группе, что и область 9 вблизи точки D. На основании этого примера мы примем следующее эвристическое правило:

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

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

Мы только что видели, что вершины (на изображении многогранников) свидетельствуют в пользу объединения некоторых областей в качестве частей объектов. Эвристические правила, которые мы сформулировали, являются разумными и правдоподобными, но было бы, конечно, удивительно, если бы удалось доказать, что они непогрешимы; ведь, в конце концов, они выведены только на основе не-

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

усеченную пирамиду, установленную на плите. Исследование вершин дает информацию о связях, показанную на рис. 12.15, б, где мы представили области картинки узлами графа, а связи между областями — дугами, соединяющими узлы. Для ясности каждая из дуг (связей) помечена символом вершины, по которой она получена; например, связь между узлами (областями) 1 и 3 является результатом того факта, что вершина D имеет форму Y, и соответствует связям на рис. 12.14, а. Осмотр рис. 12.15, б подтверждает подозрение, что одиночные связи сами по себе являются недостаточным свидетельством в пользу объединения областей; области 1 и 4, которые «явно» принадлежат разным объектам, связаны. Чтобы обойти эту трудность, мы примем следующее эвристическое правило объединения узлов (а следовательно, и областей):

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

Рис. 12.15,е иллюстрирует применение этого правила к графу рис. 12.15,6. На рис. 12.15,б имеются несколько пар соединенных

двойными связями узлов; мы произвольно применили правило к узлам 2 и 3 и к узлам 5 и 6. Заметьте, что в соответствии со второй частью правила связи от остальных узлов подключены к новым групповым узлам. Поскольку граф рис. 12-. 15, в содержит узлы, связанные по крайней мере двумя дугами, можно применить снова то же

самое эвристическое правило. На рис. 12.15, г показан результат такого применения; больше нет узлов, соединенных по крайней мере двумя дугами, и поэтому процесс заканчивается. Окончательная группировка областей определяется узлами последнего графа. В данном случае области 1,2 и 3 объединены в один объект, области 4, 5 и 6 образуют другой объект и, наконец, область 7 — фон — образует третий объект. Таким образом, в этом примере процесс перво-

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

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

1'. Вершина типа У свидетельствует о том, что три области, сходящиеся в Y, должны быть объединены, если только одна из них не является фоном, и в этом случае никакие области не должны объединяться.

Читатель может убедиться, что это правило (которое неявно предполагает, что мы заранее знаем, какие области представляют фон) приводит к удовлетворительным результатам для сцены рис. 12.16, а. Мы не должны, однако, ожидать, что эта единственная модификация даст нам непогрешимый набор правил. Доводы, которые привели нас к правилу Г, оказываются несостоятельными на рис. 12.16., б; здесь вершины Л и В создают достаточно связей, чтобы вызвать объединение всех областей, кроме фона, в один объект.

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

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

Наша первая цель сводится к тому, чтобы разработать общий метод определения трехмерной структуры по информации, поставляемой единственной картинкой, и по «небольшому числу» дополнительных фактов. Затем мы усовершенствуем этот метод, приняв дополнительное ограничение, что многогранные объекты имеют степень 3.

Для начала обратимся вновь к некоторым основным свойствам перспективных преобразований. Для конкретности мы свяжем эти свойства с простым многогранником, показанным на рис. 12.17. Каждая точка этой сцены» и в особенности каждое изображение вершины, определяет положение луча в пространстве. Каждая вершина реального трехмерного тела должна лежать на луче, который исходит из центра объектива камеры, проходит через образ вершины и продолжается в пространстве; точное положение вершины фиксировано, если мы знаем ее расстояние от центра объектива. Таким образом, если дана картинка (монокулярная), задача определения трехмерной структуры многогранника эквивалентна задаче определения расстояний от центра объектива до каждой из его семи вершин. Должно быть ясно, что картинка вместе с тем дополнительным фактом, что показанный объект есть многогранник, не дает достаточно информации для решения этой задачи. Предположим, однако, что мы также знаем положение в трехмерном пространстве

вершин 1, 2, 3 и 7. Поскольку три точки задают положение плоскости, мы можем использовать трехмерные координаты вершин 1,

2    и 7, чтобы определить положение в пространстве плоскости А. Заметим теперь, что вершина 6 лежит на плоскости А; следовательно, ее положение фиксировано на пересечении соответствующего ей луча с этой плоскостью. Подобным же образом положение в пространстве вершины 4 можно определить, зная положения вершин 2,

3    и 7. В этой ситуации известны положения в пространстве вершин 4, 6 и 7, поэтому плоскость С фиксирована, и можно найти положение вершины 5. То есть в этом примере и для данной картинки достаточно иметь информацию о том, что показанный на картинке объект есть многогранник,, и знать положение в пространстве вершин 1, 2, 3 и 7, чтобы определить положение в пространстве остальных вершин и, следовательно, трехмерную структуру видимой части многогранника.

В связи с предыдущим примером естественно задать вопрос, достаточно ли в общем случае четырех любых «известных» вершин для определения трехмерной структуры. Ответ на этот вопрос отрицательный: если четыре точки не являются независимыми, т. е. если любые три из них лежат на одном ребре или если все они лежат на одной грани, то, как легко показать, этих точек недостаточно. Предположим, однако, что мы знаем четыре независимые точки многогранника, но допустим, что невозможно сцепить их вместе, как в предыдущем случае. Например, для,рис. 12.17 мы можем знать пары противоположных вершин, таких, как 1, 2, 4 и 5; будет ли их достаточно, чтобы определить структуру? Для этого примера ответ положителен. Обозначив символом d неизвестное расстояние от объектива до вершины 7, можно задать вершину 6 через d и затем задать вершину 5 через d; но положение вершины 5 уже известно, поэтому можно найти величину d и определить положение всех вершин.

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

где X — трехмерный вектор точки, лежащей на плоскости, а ѵ — нормальный относительно плоскости трехмерный вектор, длина которого обратна расстоянию от начала координат до плоскости. Пусть Р — произвольная точка, лежащая на плоскости; ее образ, скажем Р', задает луч в пространстве. Поскольку мы поместили начало координаі в центр объектива, любая точка на луче имеет вид т,

где u — единичный трехмерный вектор, направленный по лучу, и а — расстояние от точки до начала координат. Тогда условие того, что точка Р лежит на луче, заданном ее образом, и одновременно на плоскости, определяемой вектором ѵ, может быть записано в виде

или

Применим этот простой анализ к сцене рис. 12.17. Мы будем индексировать переменные буквами или цифрами, чтобы указать плоскость или точку, к которой они относятся. Поскольку вершины I, 2, 6 и 7 находятся на плоскости А, мы напишем

Подобным же образом для плоскостей В и С мы напишем  и

Эта система линейных уравнений отображает тот факт, что различные характерные точки (в этом примере — все вершины) лежат на определенных плоскостях многогранника. Векторы U; определяются прямо по картинке и, следовательно, известны. Каждая из трех плоскостей определяется одним трехмерным вектором, а каждая из семи точек — скаляром. Следовательно, мы имеем систему из 12 уравнений с 16 неизвестными. Если уравнения линейно независимы, можно найти единственное решение, зафиксировав любую четверку неизвестных переменных, при условии, как мы видели выше, что фиксированные переменные независимы.

Поучительно найти для случая произвольной картинки (с многогранником) число уравнений и переменных, использу-емых для вы-

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

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

Разность между числом переменных и числом уравнений дает нижнюю границу для числа переменных, которые должны быть известны при определении трехмерной структуры многогранника. Нижняя граница достигается, когда результирующая система линейных уравнений имеет полный ранг *).

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

Теперь нам хотелось бы дать другую интерпретацию описанной выше процедуры. Интерпретация ограничена картинками трехгранных тел, но представляет интерес, поскольку она уточняет расплывчатое понятие «сцепления» одной грани многогранника с другой. Интерпретация основана на использовании определенного вида дуального графа изображения многогранника. Узлы дуального графа соответствуют видимым плоскостям многогранника; два узла дуального графа связаны дугой, если у их граней имеется общее (и видимое) ребро *). Однако, если две плоскости связаны более чем одним ребром (которые все обязательно.коллинеарны), между соответствующими узлами помещается только одна дуга. Рис. 12.18, а показывает ступенчатое трехгранное тело; соответствующий дуальный граф показан на рис. 12.18, б. Чтобы показать, как можно

использовать дуальный граф для интерпретации последовательного процесса сцепления одной грани многогранника с другой, предположим, что положения вершин А, С, D и Е известны; тогда известны положения граней 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, д. Этот процесс в нашем примере может повторяться, пока все первоначальные узлы не сольются в один.

Проиллюстрированный выше процесс реально представляет собой всего лишь способ слежения на всех стадиях анализа за теми гранями многогранника, положение которых в трехмерном пространстве уже было определено. Основное правило слияния двух узлов, если они связаны по крайней мере двумя дугами, представляет собой другую формулировку условий, при которых положение одной грани может быть найдено по известным положениям смежных с ней других граней. Первоначальное добавление дуги может рассматриваться как некоторая уловка, позволяющая развязать процесс. Она равносильна утверждению, что две грани имеют общие неколлинеарные ребра; это явно невозможно, но дополнительное ребро представляет собой фиктивный эквивалент того, что положения двух плоскостей заданы. В данном примере это был случай, когда добавление единственного ребра позволяет нам слить все узлы в один. Когда такое имеет место, т. е. когда мы можем добавить единственную дугу таким образом, что все узлы могут быть последовательно слиты вместе, мы говорим, что граф 1-сливаемый. Мы неформально показали, что структура видимой части трехгранного тела может быть определена ііо четырем известным точкам, если дуальный граф 1-сливаемый. В более общем случае дуальный граф k-сливаемый, если нужно добавить не меньше, чем k дуг, чтобы посредством ряда слияний уменьшить граф до единственного узла. Нетрудно показать, что структура видимой части трехгранного тела определяется по k-\-3 независимым точкам во всех случаях, когда дуальный граф fe-сливаемый. Например, многогранник рис. 12.10, а имеет 2-сливаемый дуальный граф, и легко убедиться, что для определения видимой структуры должны быть известны положения пяти точек.

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