Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 97
Текст из файла (страница 97)
Мы уже отмечали выше, что внешняя граница объекта может всегда быть размечена стрелками в направлении часовой стрелки, и при этом уменьшается число типов каталога, Г«. 12. С«ставя«и«и обработка о«и«азий которые могут быть приписаны вершинам, находящимся на границе. Читатель может убедиться, что, хотя эта информация бесполезна при разметке первых пяти вершин рис. 12.11, она оказывает существенную помощь при разметке остальных вершин. И наконец, заметим, что каталог типов вершин не содержит повторений или неоднозначностей; тнп вершины определяется точно и единственным образом сразу же после разметки ее линий.
Таким образом, мы можем сделать общий вывод, что процесс разметки линий в соответствии с их смыслом позволяет нам интерпретировать некоторые части сцены однозначно и в то же время может обнаружить совершенно явные двусмысленности, разрешение которых возможно только с помощью более детального анализа.
!2.4.2. ОБЪЕДИНЕНИЕ ОБЛАСТЕЙ В ОБЪЕКТЫ Фундаментальной проблемой в анализе изображений многогранников является проблема разделения изображения на отдельные объекты. В дальнейшем мы будем обсуждать эвристический подход к этому классу проблем — подход, который основан на догадке и интуиции, но не опирается на какой-либо полный теоретический анализ. Однако, прежде чем описывать какие-то специальные методы, следует сделать несколько предварительных замечаний. Предположим, что у нас есть контурный рисунок, показывающий несколько многогранников, которые, возможно, закрывают друг друга, и мы хотим разделить картинку на отдельные тела.
Чтобы сформулировать задачу несколько более точно, мы можем рассматривать контурный рисунок как набор отделенных друг от друга областей; задача заключается в соединении этих областей в группы таким образом, чтобы каждая группа представляла на картинке один многогранник.
Заметим теперь, что, если у нас имеются предварительные сведения об определенном многограннике из окружающей обстановки, мы можем для решения задачи использовать какой-то вариант метода подбора модели; здесь же мы примем, что знаем только то, что все объекты суть многогранники. Первое, что нужно отметить при таком допущении,— зто то, что задача не имеет однозначного решения. Чтобы показать это, рассмотрим снова рис. 12.!О, г.
Мы отмечали раньше возможность того,что перевернутый блок «Ь» может либо опираться на плиту, либо плавать над ней. Если имеет место последний случай, блок «1м и плита, безусловно, различные объекты; если первый, то блок «Е» либо связан с плитой (в этом случае они вместе образуют единый невыпуклый многогранник), либо представляет собой отдельное тело. Здесь имеется дополнительно и более глубокий вид двусмысленности, которую следует учитывать: каждая область сцены может интерпретироваться как основание объекта пирамидальной формы.
Вершины пирамид закрыты основаниями, а сами пирамиды разме- 12.4. Анилиэ лноэогринниноо щены в пространстве таким образом, что их основания как раз образуют области картинки. (Заметим, что мы не приняли никакой гипотезы об опоре для объектов; мы не приняли, что камера находится в общем положении, и, наконец, мы не приняли, что все многогранники степени 3.) В свете этих замечаний очевидно, что поставленная задача разделения картинки на объекты не является корректной, поскольку с не имеется тестов для про- в верки правильности предполагаемого решения. Тогда са- б мое большое, на что мы можем 3 надеяться, будет метод разделения, дающий «разумные» Е ответы для большинства картинок, т.
е. мы можем рас- Г считывать на решения, которые большинство людей сочтет «честными» и правдоподобными. Чтобы обосновать эвристический подход, которому мы будем следовать, рассмот- и р им простой многогранник, ч показанный на рис. 12.13а. о а 6 В этом простейшем из приме- г Е ров мы, конечно, ожидаем, г Я в в что любой разумный метод в с разделения отнесет области 1, 2 и 3 к одной группе, а об- л ласть 4 (фон) к другой.
Если Я мы просмотрим семь видимых вершин многогранника, мы увидим, что три имеют форму )Г (по определению предыду- Рис. 12.13. Дв«цРоотых сцоны. щего раздела), три — форму ЯГ и одна — форму У. Такой осмотр вместе с тем обстоятельством, что области 1, 2 и 3 составляют одну группу, подсказывает следующие эвристические правила: 1. Вершина типа )' свидетельствует о том, что три области, сходящиеся в )', должны быть сгруппированы вместе. 2. Вершина типа -Яу свидетельствует о том, что две области, заключенные в острых углах Яг, должны быть сгруппированы вместе.
На тех же основаниях мы можем также выдвинуть правило, сог- ла%о которому вершина типа У свидетельствует о том, что две об- 4зл Гл. 12. Составление и обработка олисаний ласти, сходящиеся в У, не должны быть сгруппированы вместе, но в данном изложении мы ограничимся только «положительнымио утверждениями. Рис.
!2.13, б, на котором показаны две уложенные друг на друга коробки и треугольная призма позади них, подсказывает еще несколько эвристических правил группировки областей на основании анализа вершин. Вершина А, которую мы будем называть вершиной типа Х, подсказывает следующее эвристическое правило: 3. Вершина типа Х свидетельствует в пользу группировки областей, лежащих по разные стороны «сквозной прямой» линии в Х, (На рис. 12.13, б вершина А свидетельствует в пользу объединения областей 5 и 8 в одну группу и областей 7 и 8 в другую.) Теперь, наконец, рассмотрим вершины С и 1л типа Т. Мы видели в предыдущем обсуждении, что поперечина Т всегда закрывает более удаленную часть сцены (это справедливо независимо от того, имеют многогранники степень 3 или нет). Однако тот факт, что ножки двух Т коллинеарны, говорит больше, чем просто о загораживании; он подсказывает, что области, лежащие с одной и той же стороны от каждой из ножек, являются частями одного и того же объекта.
Здесь может оказаться, что по одну и ту же сторону от каждой из ножек лежит одна область; в этом случае свидетельство в пользу группировки областей является ценным, но избыточным. Заметим в качестве примера, что вершины С и 0 на рис. 12.13, б свидетельствуют о том, что области 2 и 3 принадлежат одной и той же группе; они дают также избыточное свидетельство о том, что область 9 вблизи точки С принадлежит к той же группе, что и область 9 вблизи точки О. На основании этого примера мы примем следующее эвристическое правило: 4. Две вершины в форме коллинеарных Т свидетельствуют в пользу группировки областей, лежащих по одну и ту же сторону от ножек Т; если по одну и ту же сторону от обеих ножек лежит одна область, это свидетельство не принимается во внимание.
Эти четыре эвристических правила проиллюстрированы на рис. 12.14, а — г, где мы использовали пунктирные линии, чтобы связать области в соответствии со свидетельством, даваемым вершинами. Для целей последующего обсуждения мы определим термин связь как элемент свидетельства, подсказываемого некоторой вершиной, в пользу соединения вместе двух областей в качестве частей одного и того же объекта, Мы только что видели„что вершины (на изображении многогранников) свидетельствуют в пользу объединения некоторых областей в качестве частей объектов.
Звристические правила, которые мы сформулировали, являются разумными и правдоподобными, но было бы, конечно, удивительно, если бы удалось доказать, что они непогрешимы; ведь, в конце концов, они выведены только иа основе не- 12ли Анализ нногоеранниноо скольких простых примеров. Кажется ясным, что единственная связь сама по себе не должна рассматриваться как достаточно силь. ное свидетельство в пользу безоговорочного объединения двух связанных областей в качестве частей одного и того же объекта.
Вместо того мы можем захотеть анализировать отношения между связями, чтобы накапливать более сильные свидетельства в пользу объединения областей. Мы перейдем к примеру, чтобы проиллюстрировать один метод. На рис. 12.15, а показана простая сцена, содержащая Рис. !2Л4. Иллюстрация четырех эвристических правил. усеченную пирамиду, установленную иа плите. Исследование вершин дает информацию о связях, показанную на рис.
12,15, б, где мы представили области картинки узлами графа, а связи между областями — дугами, соединяющими узлы. Для ясности каждая из дуг (связей) помечена символом вершины, по которой она получена; например, связь между узлами (областямн) 1 и 3 является результатом того факта, что вершина 0 имеет форму Г, и соответствует связям на рис. 12,14, а. Осмотр рис.
12.15, б подтверждает подозрение, что одиночные связи сами по себе являются недостаточным свидетельством в пользу объединения областей; области 1 и 4, которые «явно» принадлежат разным объектам, связаны. Чтобы обойти эту трудность, мы примем следующее эвристическое правило объединения узлов (а следовательно, и областей): Два узла следует объединить, если между ними имеются по крайней мере две связи. Все связи от этих двух узлов к другим узлам соединяются со вновь сформированным «групповым узлом». Рис. 12.15,в иллюстрирует применение этого правила к графу рис. 12.15,б.
На рнс.)2.15,б имеются несколько пар соединенных тя.е. Анализ анееаеяаииаиее двойными связями узлов; мы произвольно применили правило к узлам 2 и 3 и к узлам 5 и 6. Заметьте, что в соответствии со второй частью правила связи от остальных узлов подключены к новым групповым узлам. Поскольку граф рис. 12т15„в содержит узлы, связанные по крайней мере двумя дугами, можно применить снова то же а Рнс. 12.16. Дяе сцены, представляющие трудность для объедннення областей. самое эвристическое правило. На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
