12.3. ТРЕХМЕРНЫЕ МОДЕЛИ

К задаче описания сцен, составленных из трехмерных объектов, ведут два явно различных пути. Один подход заключается в том, чтобы игнорировать трехмерную природу реальных объектов и описывать сцену в терминах двумерных конструкций, как мы это уже делали. Часто, однако, более полезно интерпретировать сцену в терминах трехмерных объектов. Таким образом, второй подход состоит в том, чтобы описывать не саму картинку в чистом виде, а трехмерную обстановку, с которой был снят вид сцены. Будем называть эти два альтернативных подхода двумерным и трехмерным описанием сцены. Чтобы проиллюстрировать различие между ними, рассмотрим снова очень простую сцену, показанную на рис. 12.1. Двумерное

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

Краткое размышление приводит к выводу, что трехмерное описание может быть получено по единственной картинке только с помощью предварительной информации об объектах, которые входят в интересующее нас окружение. Фундаментальная причина этого заключена в природе перспективных преобразований, отображающих много точек в одну; существует бесконечно много трехмерных объектов, которые могут соответствовать некоторому единственному виду. Тогда для того, чтобы получать трехмерное описание сцены, нам нужен как набор трехмерных моделей объектов окружения, так и хорошо определенная процедура интерпретации заданной сцены в терминах этих моделей. Если окружение достаточно простое, набор моделей не нужно задавать слишком детально, и процедура подбора модели может быть тривиальной. Чтобы продолжить с помощью примера рис. 12.1, предположим, что все объекты окружающей обстановки представляют собой коробки и цилиндры. Тогда наша модель окружающей обстановки может быть задана в такой грубой форме: «коробка, у которой все края прямые, и цилиндр, у которого некоторые края кривые». Даже такая грубая модель скорее позволила бы нам интерпретировать рис. 12.1 в терминах трехмерных объектов, чем в терминах плоских фигур. Хотя этот пример элементарен, лежащая в его основе идея является важной; предварительные знания могут быть в виде информации о трехмерных объектах так же, как и в виде информации только о двумерных представлениях объектов.

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

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

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

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

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

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

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

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

Попробуем набросать приближенное аналитическое решение задачи определения геометрических параметров для заданных соответственных множеств из точек изображения и точек объекта. Для начала перепишем формулу (17) гл. 10, которая задает общее перспективное преобразование в однородных координатах:

Затем мы определим матрицу V размерностью содержащую векторов , в качестве столбцов, а также матрицу V размерностью содержащую в качестве столбцов векторов Другими словами, матрица V составлена из набора точек модели (в однородных координатах), а матрица V — из набора наблюдаемых точек изображения. Определим матрицу Н размерностью как произведение матриц со стертой второй строкой. Нам хотелось бы теперь иметь возможность сформулировать нашу задачу как задачу отыскания матрицы Н, такой, что Или, на словах, мы ищем для заданных точек модели и изображения перспективное преобразование Н (которое учитывает относительное расположение модели и камеры), такое, что каждая точка модели проектируется в соответствующую ей точку изображения. К сожалению, ситуация оказывается несколько более сложной. Во-первых, хотя матрица Н содержит 12 компонент, имеется только пять независимых параметров, а именно это три параметра переноса и два параметра вращения камеры. Каждая из 12 компонент матрицы Н является функцией этих параметров. Таким образом, в принципе мы не имеем возможности выбирать произвольную матрицу Н. Мы проигнорируем эту трудность ради простоты изложения, но, поступая так, мы должны подчеркнуть, что результирующий анализ является только приближенным. Второе усложнение связано с тем обстоятельством, что мы не можем одновременно задать масштаб и точки объекта (в однородных координатах), и соответствующей ей точки изображения (также, конечно, в однородных координатах). А именно, если у нас есть точка объекта и точка изображения мы не можем произвольно записать их однородные представления в виде поскольку для этого потребовалось бы, чтобы в перспективном преобразовании Н одно и то же число w фигурировало в качестве последней однородной координаты и точки объекта, и соответствующей ей точки изображения. Чтобы избежать этой ловушки, мы введем диагональную матрицу масштаба D, которая

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

В этом матричном уравнении имеется неизвестных, из которых входят в матрицу в матрицу , и всего имеется уравнений. Следовательно, мы можем рассчитывать найти решение, если равно по крайней мере 6. На практике мы, по-видимому, будем пытаться получить более чем шесть точек модели, и поэтому естественно решать это уравнение методом наименьших квадратов. А именно нам хотелось бы найти такие матрицы чтобы сумма квадратов разностей между компонентами HV и VD была минимальна. Эта задача минимизации приводит к обычным преобразованиям, и поэтому мы просто выпишем результат, который, к сожалению, имеет несколько беспорядочный вид. Пусть

пусть

и пусть S представляет собой матрицу, элемент которой (Или, словами, матрица S образована поэлементным перемножением матриц А и ). Пусть -мерный вектор d имеет в качестве компонент диагональные элементы матрицы D. Тогда решение задачи минимизации сводится к использованию в качестве диагональных элементов матрицы D решения однородного уравнения

и к вычислению

Прежде чем двигаться дальше, сделаем паузу и прокомментируем форму решения. Заметим, во-первых, что, хотя однородная форма перспективного преобразования и полезна, она не может замаскировать существенно нелинейную природу этого преобразования. Использование диагональной матрицы D представляет собой ловкий прием, призванный компенсировать другой прием — однородные координаты. Подобным же образом определение матрицы S включает явно нелинейную операцию над матрицами.

После того как получена матрица , мы можем найти значения геометрических параметров, приравняв соответствующие компоненты матрицы и компоненты произведения PGRT. Например, с помощью непосредственного перемножения мы находим, что компонента (1, 1) произведения PGRT равна и поэтому мы можем

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

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

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