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

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

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

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

Рис. 12.13. Две простых сцены.

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

В этом простейшем из примеров мы, конечно, ожидаем, что любой разумный метод разделения отнесет области 1, 2 и 3 к одной группе, а область 4 (фон) к другой. Если мы просмотрим семь видимых вершин многогранника, мы увидим, что три имеют форму V (по определению предыдущего раздела), три — форму W и одна — форму Y. Такой осмотр вместе с тем обстоятельством, что области 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.14. Иллюстрация четырех эвристических правил.

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

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

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

(см. скан)

Рис. 12.15. Пример объединения областей

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

Рис. 12.16. Две сцены, представляющие трудность для объединения областей.

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

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

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

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

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

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