15.6. Маркировка линейных рисунков

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

Если линия соответствует ограничивающему ребру, полезно знать, какая из двух областей, расположенных по разные стороны от линии, соответствует ограничивающей грани. Будем использовать удобное графическое обозначение, маркируя ограничивающие линии стрелками. Направление стрелки показывает, какая область соответствует ограничивающей грани; соответствующая область изображения лежит справа от нас, если смотреть по направлению стрелки.

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

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

Мы ограничимся случаем, когда в одной вершине встречаются три грани. (Другие типы вершин очень затрудняют анализ.) Более того, мы будем предполагать, что все пересекающиеся линии изображения соответствуют ребрам, которые встречаются в вершине некоторого объекта. Таким образом, мы избегаем случайного выравнивания, когда смотрим на вершину так, что она оказывается лежащей на одной линии с более удаленным ребром. Мы будем также предполагать, что внешние линии линейного рисунка (его силуэт) соответствуют ребрам, которые отделяют «фон».

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

Рис. 15.1. (см. скан) В мире многогранников, в котором разрешены только трехгранные вершины, легко составить словарь всех допустимых маркировок, поскольку имеется всего четыре типа узлов.

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

Следовательно, одна из возможных маркировок -узла (соединения, в котором три линии встречаются под углом, меньшим 180°) — обозначить все три линии выпуклыми.

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

две другие линии маркируются как «закрывающие» в том смысле, что грани на стороне, содержащей «древко» стрелки, соответствуют закрывающим граням.

Из других октантов видны только обе закрывающие линии. Таким образом, одна из возможных маркировок -узла имеет обе линии, закрывающие в том смысле, что закрывающая грань лежит на той стороне, где угол между линиями меньше чем 180°.

Эта процедура может повторяться для случая, в котором объект находится не в одном, а в 3, 5 и 7 октантах. Например, в первом случае для -узла возможна только одна корректная маркировка (все линии являются выпуклыми). Всего находится 5 возможных меток для -узла: три — для узла-стрелки и шесть — для -узла (рис. 15.1). Сравните это со всеми возможными способами приписывания четырех меток трем или двум линиям соответственно!

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

Теперь мы располагаем «словарем» возможных маркировок узлов (рис. 15.1). Как нам использовать этот словарь для маркировки линейного рисунка? Выбираемые нами метки должны согласовываться со словарем. Каждая линия должна иметь только одну метку, а оба ее конца должны быть помечены одинаково. В качестве примера рассмотрим корректную маркировку линейного рисунка камина с навесом на рис. 15.2.

Одна из возможных процедур может состоять в переборе всех

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

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

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

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

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

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