Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 96
Текст из файла (страница 96)
Второе важное наблюдение заключается в том, что вершины трехгранных тел бывают только четырех характерных типов. Если считать, что плоскости, определяющие вершину, делят окружающее пространство, грубо говоря, на октанты, то сам многогранник может занимать один, три, пять или сеМь этих октантов '). Основная идея отнесения вершины к некоторому типу становится значительно ясней с помощью иллюстрации. Рис. 12.8 показывает четыре возможных типа вершин; на каждой иллюстрации вершина помечена цифрой, означающей число октантов, занимаемых твердым веществом.
Все четыре типа вершин имеются также на рнс. 12.7. Вершины В и й7 относятся к типу 1, вершины Е и 7 — к типу 3, вершины А и 0 (и некоторые другие) — к типу 5, вершины 6 и Š— к типу 7. Важно отметить, что данный тип вершин может иметь на картинке з) Строго говоря, мы должны использовать термин «октантыз только в том сзучае, когда плоскости взаимно перпендикулярны; тем не менее, общие замечания относятся к плоскостям, сходящимся под произвольнымв углами. 474 Гл. И.
Составление и обработка описаний различные представления; например, вершины А н 0 обе относятся к типу 5, но они даже не обладают одинаковым числом расходящихся от ннх линий. Это подчеркивает тот факт, что тип вершины является свойством геометрического тела, а не вида объекта на картинке. Поскольку один н тот же тип вершин может иметь более чем одно представление на картинке, естественна исследовать различные Рис. 12.8. Четыре типа вершин трехгранных теа.
возможные виды разных типов. К счастью, здесь не очень много возможностей; вершина каждого типа может рассматриваться только со стороны одного из окружающих пустых октантов, и, поскольку перемещение точки зрения в пределах одного октанта не дает существенно отличной картинки, число возможностей резко ограничено. Поэтому оказывается осуществимым составление списка в точности всех возможных представлений четырех типов вершин и создание таким образом «каталога», показанного на рнс. 12.9, а — м. Каждая конфигурация помечена в соответствии с введенными нами обозначениями знаками «+» и « — » для линий, представляющих соответственно выпуклые илн вогнутые края, и стрелками для закрывающих краев„причем примыкающие к ним плоскости оказываются 1».4.
Анализ многогранников 415 на картинке справа, если смотреть вдоль стрелки. Мы умышленно показали 12 возможных конфигураций в стандартных положениях, чтобы получить енейтральный» каталог для применения в последующем анализе. Многие из этих конфигураций видны иа рис. 12.7. Вершина Ф, например, легко опознается как вершина типа 1, пока- Рис.
12.9, Список всех возможных представлений вершин трехгранных тел. ванная на рис. 12.9, Ак вершина 0 — как вершина типа б иа рис. 12,9, з; вершина 1 — как вершина типа 3, показанная на рис. 12.9, б; и, наконец, вершину Ь, относящуюся к типу 7, можно опознать как вершину рис. 12.9, л. Мы можем убедиться, что каталог типов вершин является полным, обратившись к тому факту, что любую вершину можно рассматривать только со стороны одного из окружающих пустых октантов. Таким образом, каталог показывает одну вершину типа 7, три вершины типа б и пять вершин типа 3.
Он показывает только три 47В Ге. 12. Сосеаееение и оораоошна они«анна вершины типа 1 (вместо семи) -в связи с учетом определенной симметрии. На рис. !2.9, и показана конфигурация в форме «Та; «Та всегда соответствует краю (поперечина «Тв), закрывающему более удаленную часть объекта, но не вершине реального трехгранного тела.
Краткое размышление показывает, что поперечина «Тв должна быть всегда помечена стрелкой справа налево, а ножка «Т» может в общем иметь любую метку. г Рис. 12.1О. Пример разметки вершин, Рассмотрение рис. 12.9 ясно показывает, что тип вершины на картинке нельзя определить осмотром только этой вершины; в конце концов, каталог изображает шесть вершин в форме «$г» (рис. 12.9, а— е), три вершины в форме «Ф'» (рис.
12.9, зк — -и) и три вершины в форме «)е» (рис. 12.9, к — м). Кроме того, вершина в форме «Т» иа рис. 12.9, н реально имеет четыре различных возможных значения в соответствии с четырьмя различными возможными Метками на ее ножке. Если мы хотим, в конечном счете, пометить вершины (а следовательно, и линии) на данной картинке, мы, очевидно, можем это сделать, только используя какую-то информацию о контексте. Чтобы проиллюстрировать основной метод, рассмотрим следующий пример.
На рис. 12.10, а показано простое трехгранное тело— перевернутый блок в виде буквы Л. Начиная процесс разметки ли. «2.4. Анализ лгнагагдиннина« ний, заметим, что внешняя граница Е может быть помечена по часовой стрелке последовательностью стрелок, как это показано на рнс. 12.10, б '). Теперь осмотрим вершины А, В, С и 0 на рис. 12.10, б; каждая из них относится к вершинам в форме «Му» со стрелками на внешних отростках. Просматривая каталог типов вершин, находим, что только рис.
12.9, ж обладает этим свойством; следовательно, средние отростки вершин А, В, С и еу могут быть помечены знаком «+», как показано на рис. 12.!О, в. На рнс. 12.10, в мы также поместили стрелку вблизи 11 единственной вершины в форме «Т», поскольку нам ! = з: б известно, что поперечина «Т» всегда помечена стрел- 11:4: камн, как показано на !!!~$~1~ ! рис. 12.9, н. Таким обра- !!!фф! ~1~,~~! 7 зом, в этом примере мы ~~ 1!4 )1~,~ ' легко смогли приписать единственную метку каждой линии. С другой стороны, рис. 12,!О, г, лишь немного более сложный, пред- Рис. 1й 11 Коробка с прямоугольным атверставляет более трудную за- стнем. дачу; вершинам В, Е и 6 не может быть приписана единственная законная метка.
На то имеется серьезная причина: по картинке невозможно определить, стоит ли перевернутый блок Т. на плите или плавает над ней. Тем не менее единственная законная разметка, т. е. разметка, не ведущая к противоречиям на других вершинах, рассматривает обе эти ситуации как единственно возможные. Суммируем итоги предыдущего примера формальной процедуры разметки вершин. Для обоснования такого рода формализма заметим сначала, что существо метода заключается в пробном приписывании одной нз вершин некоторого типа согласно каталогу и в выяснении тех ограничений, которые накладываются этим приписыванием на элементы каталога, пригодные для смежных вершин. Этот процесс повторяется до тех пор, пока мы не придем к вершине (илн не обнаружим, что попали в нее сразу), у которой пробная разметка линий не удовлетворяет никакой записи каталога, и в этом месте должна быть сделана попытка использовать другие пробные метки.
»1 Эго прямое следствие того факта, что, если мы прослеживаем внеглннио границу объекта на картинке по часовой стрелке, все плоскости объекта всегда лежат справа от иас. То есть граница на произвольной картинке всегда может быть помечена па часовой стрелке последовательностью стрелок. Гл.
12. Сосигаеление и обработка онисаний 478 Очевидно, что процесс приводит к систематическому поиску' на дереве возможных разиеток вершин. В соответствии с этим мы связываем с данной картиной трехгранного тела дерево поиска. Узлы дерева поиска соответствуют вершинам на картинке, а дуги, исходящие из данного узла, соответствуют возможным меткам ка- Рис. 12.12. Лерево поиска для коробки с прямоугольным отверстием. талога, которые могут быть приписаны вершине. Чтобы пронллюстрироватьзту процедуру, рассмотрим коробку с прямоугольным отверстием на рис. 12.11; начальная часть связанного с ней дерева поиска дана на рис. 12.12. Мы произвольно решили просматривать вершины в том порядке, в каком они пронумерованы.
Вершина 1— часть прямоугольного отверстия — может быть любой из трех вершин типа «йрв в каталоге рис. 12.9. Дуги, исходящие из узла 1, могут быть поэтому отмечены буквами, соответствующими этим 19.4. Анализ»п«о«огра«ни«»в 479 трем элементам каталога. Для наглядности мы начертили также возле каждой дуги линии, замыкающие прямоугольное отверстие, н разметили их в соответствии с предписанием относящихся к ним типов вершин. Мы имеем теперь три различных альтернативных ограничения на вершину 2, соответствующих трем возможным отметкам вершины 1, и каждое из них должно исследоваться. Если вершина 1 соответствует элементу каталога (ж), вершина 2 должна удовлетворять условию «вершина типа Р с исходящей стрелкой слева».
Просматривая каталог, мы находим, что только элементы (г) и (д) удовлетворяют этому условию, и, следовательно, из крайнего левого узла 2 на рис. !2.12 спускаются две дуги. Подобным же образом используются другие альтернативные ограничения на вершину 2, чтобы заполнить второй уровень дерева.
В этом месте мы имеем четыре ограничения (не все они различны) на вершину 3— вершину типа «Т>. Поскольку эти ограничения затрагивают только ножку «Т», мы видим из каталога, что поперечина может быть помечена стрелками справа налево (если рассматривать «Т» в правильном положении). Теперь у нас есть четыре альтернативных ограничения на вершину 4. Каждому из этих ограничений соответствует полная, хотя и пробная, разметка линий вершины, поскольку смежные вершины 2 и 3 уже получили пробные отметки типов каталога. Три условия из четырех для вершины 4 не могут быть удовлетворены, т. е.
не существует элементов каталога, подходящих к данной пробной разметке линий. В соответствии с этим в трех подходящих узлах дерево «обрезается», и в качестве жизнеспособного варианта остается только четвертый узел. Эта процедура поиска продолжается до тех пор, пока либо все вершины многогранника получат совместимые метки, либо все узлы на окончаниях дерева окажутся «обрезанными» и дальнейший поиск будет невозможен. В последнем случае мы можем быть уверены, что не существует трехгранного тела, соответствующего данной картинке, т. е. контурный рисунок содержит ошибку.
В первом случае может оказаться, что имеется более чем один способ совместимой разметки вершин. Читатель может легко убедиться, что дерево рнс. 12.12 можно достроить полностью единственным образом, дав тем самым единственную инте претацию каждой линии рис. 12.11. К режде чем покончить с этой темой, сделаем несколько заключительных замечаний. Во-первых, отметим, что процедура позволяет нам делать некоторый вывод относительно смысла одной части сцены по информации о других ее частях. Эта процедура представляет собой поэтому особенно ясный, хотя и элементарный, пример использования контекста в анализе изображения. Заметим также, что процесс исследования дерева поиска может проводиться различными способами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
