12.4. АНАЛИЗ МНОГОГРАННИКОВ

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

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

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

12.4.1. СЕМАНТИКА ЛИНИЙ

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

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

эти типы краев представлены в сцене рис. 12.7, на которой показан камин с приподнятым основанием. Например, линии AM и FQ представляют собой вогнутые края, линии BN и DE — выпуклые края, а линии АВ, ВС и EI — закрывающие края. Важно отметить, что, поскольку мы имеем дело с объектами, ограниченными плоскостями, смысл линии должен оставаться неизменным по всей ее длине. В качестве обозначения мы будем отмечать выпуклые линии знаком плюс, вогнутые — знаком минус и закрывающие линии — стрелкой. Направление стрелки выбирается таким образом, что, если вы мысленно встанете на плоскость картинки и посмотрите на линию в направлении стрелки, незакрытая плоскость будет лежать справа от линии.

Рис. 12.7. Камин с основанием.

Второе важное наблюдение заключается в том, что вершины трехгранных тел бывают только четырех характерных типов. Если считать, что плоскости, определяющие вершину, делят окружающее пространство, грубо говоря, на октанты, то сам многогранник может занимать один, три, пять или семь этих октантов Основная идея отнесения вершины к некоторому типу становится значительно ясней с помощью иллюстрации. Рис. 12.8 показывает четыре возможных типа вершин; на каждой иллюстрации вершина помечена цифрой, означающей число октантов, занимаемых твердым веществом. Все четыре типа вершин имеются также на рис. 12.7. Вершины В и N относятся к типу 1, вершины Е и — к типу 3, вершины А и D (и некоторые другие) — к типу 5, вершины G и L — к типу 7. Важно отметить, что данный тип вершин может иметь на картинке

различные представления; например, вершины А и D обе относятся к типу 5, но они даже не обладают одинаковым числом расходящихся от них линий. Это подчеркивает тот факт, что тип вершины является свойством геометрического тела, а не вида объекта на картинке.

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

Рис. 12.8. Четыре типа вершин трехгранных тел.

К счастью, здесь не очень много возможностей; вершина каждого типа может рассматриваться только со стороны одного из окружающих пустых октантов, и, поскольку перемещение точки зрения в пределах одного октанта не дает существенно отличной картинки, число возможностей резко ограничено. Поэтому оказывается осуществимым составление списка в точности всех возможных представлений четырех типов вершин и создание таким образом «каталога», показанного на рис. 12.9, а — м. Каждая конфигурация помечена в соответствии с введенными нами обозначениями знаками «+» и «-» для линий, представляющих соответственно выпуклые или вогнутые края, и стрелками для закрывающих краев, причем примыкающие к ним плоскости оказываются

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

Рис. 12.9. Список всех возможных представлений вершин трехгранных тел.

Вершина N, например, легко опознается как вершина типа 1, показанная на рис. вершина D — как вершина типа 5 на рис. 12.9, з; вершина I — как вершина типа 3, показанная на рис. и, наконец, вершину L, относящуюся к типу 7, можно опознать как вершину рис.

Мы можем убедиться, что каталог типов вершин является полным, обратившись к тому факту, что любую вершину можно рассматривать только со стороны одного из окружающих пустых октантов. Таким образом, каталог показывает одну вершину типа 7, три вершины типа 5 и пять вершин типа 3. Он показывает только три

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

Рис. 12.10. Пример разметки вершин.

Рассмотрение рис. 12.9 ясно показывает, что тип вершины на картинке нельзя определить осмотром только этой вершины; в конце концов, каталог изображает шесть вершин в форме «V» (рис. 12.9, а — е), три вершины в форме (рис. 12.9, ж - а) и три вершины в форме (рис. 12.9, к — м). Кроме того, вершина в форме на рис. 12.9, н реально имеет четыре различных возможных значения в соответствии с четырьмя различными возможными Метками на ее ножке. Если мы хотим, в конечном счете, пометить вершины (а следовательно, и линии) на данной картинке, мы, очевидно, можем это сделать, только используя какую-то информацию о контексте.

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

заметим, что внешняя граница L может быть помечена по часовой стрелке последовательностью стрелок, как это показано на рис. 12.10, б. Теперь осмотрим вершины А, В, С и D на рис. 12.10, б; каждая из них относится к вёршинам в форме со стрелками на внешних отростках. Просматривая каталог типов вершин, находим, что только рис. обладает этим свойством; следовательно, средние отростки вершин А, В, С и D могут быть помечены знаком как показано на рис. 12.10, в.

Рис. 12.11. Коробка с прямоугольным отверстием.

На рис. 12.10, в мы также поместили стрелку вблизи единственной вершины в форме поскольку нам известно, что поперечина всегда помечена стрелками, как показано на рис. 12.9, н. Таким образом, в этом примере мы легко смогли приписать единственную метку каждой линии. С другой стороны, рис. 12.10, г, лишь немного более сложный, представляет более трудную задачу; вершинам В, Е и G не может быть приписана единственная законная метка. На то имеется серьезная причина: по картинке невозможно определить, стоит ли перевернутый блок L на плите или плавает над ней. Тем не менее единственная законная разметка, т. е. разметка, не ведущая к противоречиям на других вершинах, рассматривает обе эти ситуации как единственно возможные.

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

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

Рис. 12.12. Дерево поиска для коробки с прямоугольным отверстием.

Чтобы проиллюстрировать эту процедуру, рассмотрим коробку с прямоугольным отверстием на рис. 12.11; начальная часть связанного с ней дерева поиска дана на рис. 12.12. Мы произвольно решили просматривать вершины в том порядке, в каком они пронумерованы. Вершина 1 — часть прямоугольного отверстия — может быть любой из трех вершин типа в каталоге рис. 12.9. Дуги, исходящие из узла 1, могут быть поэтому отмечены буквами, соответствующими этим

трем элементам каталога. Для наглядности мы начертили также возле каждой дуги линии, замыкающие прямоугольное отверстие, и разметили их в соответствии с предписанием относящихся к ним типов вершин. Мы имеем теперь три различных альтернативных ограничения на вершину 2, соответствующих трем возможным отметкам вершины 1, и каждое из них должно исследоваться. Если вершина 1 соответствует элементу каталога вершина 2 должна удовлетворять условию «вершина типа V с исходящей стрелкой слева». Просматривая каталог, мы находим, что только элементы удовлетворяют этому условию, и, следовательно, из крайнего левого узла 2 на рис. 12.12 спускаются две дуги. Подобным же образом используются другие альтернативные ограничения на вершину 2, чтобы заполнить второй уровень дерева. В этом месте мы имеем четыре ограничения (не все они различны) на вершину 3 — вершину типа Поскольку эти ограничения затрагивают только ножку «7», мы видим из каталога, что поперечина может быть помечена стрелками справа налево (если рассматривать в правильном положении). Теперь у нас есть четыре альтернативных ограничения на вершину 4. Каждому из этих ограничений соответствует полная, хотя и пробная, разметка линий вершины, поскольку смежные вершины 2 и 3 уже получили пробные отметки типов каталога. Три условия из четырех для вершины 4 не могут быть удовлетворены, т. е. не существует элементов каталога, подходящих к данной пробной разметке линий. В соответствии с этим в трех подходящих узлах дерево «обрезается», и в качестве жизнеспособного варианта остается только четвертый узел. Эта процедура поиска продолжается до тех пор, пока либо все вершины многогранника получат совместимые метки, либо все узлы на окончаниях дерева окажутся «обрезанными» и дальнейший поиск будет невозможен. В последнем случае мы можем быть уверены, что не существует трехгранного тела, соответствующего данной картинке, т. е. контурный рисунок содержит ошибку. В первом случае может оказаться, что имеется более чем один способ совместимой разметки вершин. Читатель может легко убедиться, что дерево рис. 12.12 можно достроить полностью единственным образом, дав тем самым единственную интерпретацию каждой линии рис. 12.11.

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

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