Контуры
Рассматривая контурный рисунок, подобный приведенному на рис. 24.13, мы получаем живое восприятие трехмерной формы и расположения. Благодаря чему это происходит? Ведь уже было сказано выше, что к получению одного и того же контурного рисунка приводит обработка не одной конфигурации сцены, а бесконечного количества таких конфигураций. Кроме того, следует отметить, что контурный рисунок позволяет даже получить представление о наклоне и повороте поверхностей. Такое ощущение может достигаться благодаря использованию сочетания знаний высокого уровня (знаний о типичных формах) с ограничениями низкого уровня.
Рассмотрим, какие качественные знания могут быть получены с помощью контурного рисунка. Как было описано выше, линии на рисунке могут иметь много разных трактовок (см. рис. 24.4 и его подрисуночную подпись). Задача оценки фактической значимости каждой линии на изображении называется разметкой линий; она была одной из первых задач, изучаемых в области машинного зрения. На данный момент займемся изучением упрощенной модели мира, в которой объекты не имеют отметок на поверхности, а линии, обусловленные наличием сосредоточенных неоднородностей освещенности, такие как края теней и блики, были удалены на каком-то из этапов предварительной обработки, что позволяет нам сконцентрировать свое внимание на контурных рисунках, где каждая линия соответствует сосредоточенной неоднородности либо по глубине, либо по ориентации.
В таком случае каждую линию можно отнести к одному из двух классов: рассматривать ее как проекцию лимба (геометрического места тех точек на поверхности, где луч зрения проходит по касательной к поверхности) или как край (поверхностная нормальная сосредоточенная неоднородность). Кроме того, каждый край может быть классифицирован как выпуклый, вогнутый или закрывающий (под этим подразумевается, что он закрывает то, что находится за ним). Что касается закрывающих краев и лимбов, то желательно иметь возможность определять, какая из двух поверхностей, примыкающих к кривой на контурном рисунке, является ближайшей к наблюдателю в данной сцене. Такие наложения линий могут быть представлены путем присваивания каждой линии одной из шести перечисленных ниже возможных меток линий, как показано на рис. 24.14.
1. Метки + и - представляют соответственно выпуклые и вогнутые края. Они связаны с поверхностными нормальными сосредоточенными неоднородностями, в которых видны обе поверхности, стыкующиеся вдоль этого края.
2. Метка <— или -> представляет закрывающий выпуклый край. При просмотре сцены из видеокамеры обе конечные части поверхности, ограниченные замкнутой кривой, которые стыкуются вдоль этого края, лежат на одной и той же стороне, но одна из них закрывает другую. По мере перемещения по направлению стрелки эти закрывающие поверхности остаются справа.
3. Метка <—<— или ->-> представляет лимб. На этой линии поверхность плавно искривляется по кругу, закрывая саму себя. По мере перемещения в направлении, обозначенным двойной стрелкой, закрывающая поверхность остается справа. Луч зрения проходит по касательной к поверхности во всех точках лимба. По мере изменения точки зрения лимбы меняют свое положение на поверхности объекта.
Если количество линий на рисунке равно п, то количество вариантов присваивания меток линий, определяемое законами комбинаторики, равно 6П, но количество физически возможных вариантов присваивания по сравнению с этим количеством составляет лишь очень небольшую величину. Задача определения таких возможных присваиваний меток называется задачей разметки линий. Следует отметить, что эта задача имеет смысл, только если метка остается одинаковой на всем протяжении линии. Но такое условие не всегда соблюдается, поскольку метки могут изменяться вдоль линий на изображениях выпукло-вогнутых криволинейных объектов. В настоящей главе для предотвращения указанных сложностей будут рассматриваться исключительно только многогранные объекты.
Хаффмен [702] и Клоувс [271] независимо друг от друга впервые предприняли попытку применить систематический подход к анализу сиен с многогранными объектами. В своем анализе Хаффмен и Клоувс ограничивались сценами с непрозрачными трехгранными твердыми телами; таковыми являются объекты, в которых в каждой вершине сходятся три и только три плоские поверхности. В случае наличия сцен с многочисленными объектами они, кроме этого, исключали такие выравнивания объектов, которые могли бы привести к нарушению предположения о наличии только трехгранных объектов, например сцен, в которых два куба имеют общий край. Не допускалось также наличие трещин (т.е. "краев", вдоль которых касательные плоскости являются непрерывными). Для такого мира трехгранных объектов Хаффмен и Клоувс подготовили исчерпывающий список всех различных типов вершин и описали всевозможные способы, с помощью которых эти вершины могут рассматриваться под общей точкой зрения. Условие, согласно которому должна существовать общая точка зрения, фактически гарантирует то, что если возникает небольшое движение глаза наблюдателя, ни одно из соединений плоскостей не меняет свой характер. Например, из этого условия следует, что если три линии пересекаются на изображении, то должны также пересекаться соответствующие края в сцене.
Четыре способа, с помощью которых три плоские поверхности могут быть соединены в одной вершине, показаны на рис. 24.15. Эти примеры могут быть также составлены путем разделения куба на восемь октантов. В таком случае различные возможные трехгранные вершины в центре куба создаются путем заполнения разных октантов. Вершина, обозначенная цифрой 1, соответствует одному заполненному октанту, вершина с цифрой 3 — трем заполненным октантам и т.д. Рекомендуем читателям самим убедиться в том, что на данном рисунке действительно представлены все возможности. Например, попытка заполнить два октанта в кубе не приводит к созданию допустимой трехгранной вершины в центре. Следует также отметить, что эти четыре случая соответствуют различным комбинациям выпуклых и вогнутых краев, которые встречаются в данной вершине.
Три края, встречающихся в вершине, делят окружающее пространство на восемь октантов. Вершина видна из любого октанта, не заполненного твердым материалом. Перемещение точки зрения в пределах одного октанта не приводит к получению изображения с различными типами соединений. Вершина, обозначенная цифрой 1 на рис. 24.15, может рассматриваться из любого из оставшихся семи октантов; при этом наблюдаются метки соединения, показанные на рис. 24.16.
Работа по составлению исчерпывающего списка различных способов, с помощью которых может рассматриваться каждая вершина, привела к получению вариантов, показанных на рис. 24.17. Получено четыре различных типа соединений, которые могут быть выделены на изображении: L-соединения, Y-соединения, стреловидные соединения и Т-соединения. L-соединения соответствуют двум видимым краям. Y-соединения и стреловидные соединения соответствуют результатам рассмотрения трех краев, но различие между ними состоит в том, что в Y-соединении ни один из трех углов не превышает 180°. Т-соединения связаны с закрытием одной поверхности другой. Если ближайшая, непрозрачная поверхность закрывает вид на дальше расположенный ее край, будет получен непрерывный край, который встречается с частично закрытым краем. Четыре метки Т-соединения соответствуют закрытию четырех различных типов краев.
При использовании этого словаря соединений во время поиска разметки для контурного рисунка приходится решать задачу определения того, какие интерпретации соединений являются глобально совместимыми. Соблюдение свойства совместимости обеспечивается путем применения правила, согласно которому каждой линии на рисунке вдоль всей ее длины должна быть присвоена одна и только одна метка. Вальц [1552] предложил алгоритм решения этой задачи (фактически применимый даже дня расширенной ее версии с тенями, трещинами и разделимо вогнутыми краями), который стал одним из первых приложений метода удовлетворения ограничений в искусственном интеллекте (см. главу 5). В терминологии задач CSP переменными являются соединения, значениями — разметки дня этих соединений, а ограничениями служит то, что каждая линия имеет единственную метку. Хотя задача разметки линии для сцен с трехгранными объектами является NP-полной, на практике стандартные алгоритмы CSP показали высокую производительность при их решении.
Зрение позволяет нам надежно распознавать людей, животных и неодушевленные объекты. В области искусственного интеллекта или машинного зрения для обозначения всех этих способностей принято использовать термин распознавание объектов. К этому относится определение класса конкретных объектов, представленных на изображении (например, лица), а также распознавание самих конкретных объектов (например, лица Билла Клинтона). Ниже перечислены прикладные области, которые стимулируют развитие этого научно-технического направления.
• Биометрическая идентификация. Криминальные расследования и контроль доступа на объекты, допускающие присутствие ограниченного круга лиц, требуют наличия возможности однозначно идентифицировать личность людей. Операции снятия отпечатков пальцев, сканирования радужной оболочки глаза и фотографирования лица в фас приводят к получению изображений, которые должны быть сопоставлены с данными, относящимися к конкретным людям.
• Выборка изображений с учетом их содержимого. В текстовом документе можно легко найти местонахождение любой строки, например "cat" (кошка), если она там имеется; такую возможность предоставляет любой текстовый редактор. А теперь рассмотрим задачу поиска в изображении подмножества пикселов, которые соответствуют изображению кошки. Если бы система машинного зрения обладала такой способностью, то позволяла бы отвечать на запросы, касающиеся содержимого изображений, такие как "Найдите фотографию, на которой показаны вместе Билл Клинтон и Нельсон Мандела", "Найдите фотографию конькобежца, который в процессе бега полностью оторвался ото льда", "Найдите фотографию Эй-фелевой башни ночью" и т.д., без необходимости вводить ключевые слова, озаглавливающие каждую фотографию в коллекции. По мере того как увеличиваются коллекции фотографий и видеофильмов, задача ввода вручную аннотаций к отдельным объектам из этой коллекции становится все сложнее.
• Распознавание рукописного текста. К примерам такого текста относятся подписи, блоки адресов на конвертах, суммы в чеках и введенные пером данные в персональных цифровых ассистентах (Personal Digital Assistant — PDA).