Разработка систем создания виртуальной реальности является сегодня одной из бурноразвивающихся областей информатиии [1-3]. В числе наиболее важных здесь является задача формирования мнимой реальности, геометрия которой повторяет геометрию реальной трехмерной среды, Очень интересным подходом может быть реконструкция реальных обьектов на основе серии обычных фотографий физических объеков и сред, сделанньк с различных точек наблюдения [7]. К сожалению, сегодня совсем немного систем, позволяющих делать зто в полной мере и достаточно эффективно,хотя работы в этом направлении интенсивно ведутся, Наиболее продвинутой для практического применения является система "Fotomodeler" [4,5], результатом работы которой является сцена, представленная в виде треугольной аппроксимации видимых поверхностей реальных объектов. В данной статье приведено описание нового подхода к этой задаче, позволяющего реконструировать трехмерную геометрию среды в полной мере, не ограничиваясь восстановлением только отдельных частей поверхности объектов, а восстанавливать их как полноценные трехмерные тела.
В общем случае процедура реконструкции трехмерной геометрии по серии фотоизображений реальной среды состоит из нескольких этапов:
- калибровка и взаимное ориентирование отдельных фотоизображений (фотокамер), необходимых для последующего решения фотограмметрической задачи;
- выбор готовых моделей из библиотеки или создание новой параметрической модели реконструируемого объекта;
- нахождение и согласование двумерных особенностей анализируемой сцены, определение по ним трехмерных особенностей реконструируемых объектов и вычисление их координат путем решения фотограмметрической задачи;
- идентификация внешних параметров модели (ВПМ) реконструируемого объекта путем минимизации целевой функции, характеризующей отклонение особенностей, полученных путем решения фотограмметрической задачи от соответствующих особенностей реальной модели.
Главным направлением наших исследований было решение второй и четвертой задач. Решение первой задачи рассматривается в различных работах и является самостоятельной и достаточно сложной проблемой, когда система получает семейство направленных стереопар изображений.
Требования, предъявляемые к моделям объектов сцены существенно зависят от типа геометрических особенностей, используемых при идентификации их параметров, поэтому мы сначала рассмотрим типы особенностей.
Типы особенностей, способы их выделения и накопления
Основным типом трехмерной особенности, которую обычно можно выделить на фотоизображениях реальных сцен, является точка. Существует ряд подходов к автоматическому восстановлению поверхности по стереоизображениям, основанных на различных методах идентификации трехмерных особенностей. Предварительным результатом их работы обычно является множество согласованных пар точек, первая из которых принадлежит левому, а вторая - правому снимку, причем известно, что эта пара двухмерных точек является изображением одной и той же трехмерной точки. Следует отметить, что основной проблемой всех этих методов является отбраковка ложных точек, которые были идентифицированы как согласованные, но на самом деле являются двухмерными изображениями различных трехмерных точек.
Подход к реконструкции реальной сцены с помощью параметрических моделей принципиально отличается от классических автоматических методов тем, что для восстановления реальной геометрии требуется существенно меньше точек. При таком подходе оператор в состоянии контролировать каждую используемую точку,и проблема "ложных" особенностей существенно упрощается. Точка, как основная сущность, может порождаться в самых разнообразных случаях. Наиболее типичная точечная особенность - это верши на многогранника. Очень часто точка может быть идентифицирована с помощью различных оптических неоднородностей на видимой поверхности объекта. Например, в качестве точечной особенности очень удобно использовать изображения мелких предметов, присутствующих на сцене. В ряде случаев решение фотограмметрической задачи может быть совмещено с решением задачи согласования точек. Например, если на обоих снимках видна одна и та же линия, то отметив точку, принадлежащую ей на одном снимке, можно определить соответствующую точку на второй фотографии по пересечению эпиполяры с изображением линии. Таким образом, наиболее типичными особенностями, получаемыми по двум или более фотоизображениям, является множество пар согласованных точек. После решения фотограмметрической задачи для каждой пары согласованных точек мы получим координаты соответствующей ей трехмерной точки.
Кроме точек можно рассматривать и более сложные типы особенностей. Например, если на двух фотоизображениях видно какое-нибудь прямолинейное ребро, то можно определить не только координаты трехмерных точек, лежащих на этом ребре, но и непосредственно коэффициенты уравнения соответствующей прямой в пространстве. Аналогично может быть поставлена, а в некоторых случаях и решена, задача прямого восстановления коэффициентов уравнений поверхностей второго порядка по их "абрисам", видимым на двух или более фотоизображениях. Полученные результаты далее можно использовать для восстановления трехмерной геометрии сцены. В данной статье мы ограничимся лишь рассмотрением использования множества трехмерных точек для реконструкции сцены. Про каждую из таких точек известно, что она принадлежит одной или нескольким произвольным граням реконструируемого объекта. Для многогранника это означает, что точка принадлежит грани, ребру или является вершиной. Последнее свидетельство того, что она одновременно принадлежит всем плоскостям, образующим вершину.
Следует отметить, что координаты трехмерных точек, получаемых с помощью решения фотограмметрической задачи, обладают конечной точностью. Она обуславливается целым множеством факторов, главными среди которых являются точность решения задачи калибровки и взаимного ориентирования фотоизображений, дискретная природа используемых фотоизображений и ошибки указания особенностей на снимках. В силу всех этих причин для реконструкции следует использовать существенно большее количество точек, чем минимально необходимое. Используя такой подход, можно повысить результирующую точность решения задачи реконструкции, а также обнаружить и отбраковать ошибочные точки.
Параметрическая модель реконструкции геометрии трехмерных объектов
Идентификация параметров параметрической модели реконструируемого объекта, как уже отмечалось, производится путем минимизации целевой функции, характеризующей отклонение полученных путем решения фотограмметрической задачи особенностей реальных объектов от соответствующих особенностей модели. Если ограничиться рассмотрением реконструкции только многогранников, то в качестве целевой функции можно выбрать среднеквадратическое расстояние от рассматриваемых точек до плоскостей, на которых они должны лежать. Из такого выбора целевой функции вытекает одно из основных требований к методу построения параметрических моделей реконструируемых многогранников - он должен обеспечивать достаточно эффективное вычисление коэффициентов плоскостей, образующих грани. Кроме того, оказалось полезным иметь топологическое описание реконструируемого многогранника, где в явном виде указана взаимная инцидентность вершин, ребер и граней. Это описание необходимо для решения двух задач. Во-первых, для каждой вершины или ребра необходимо уметь определять образующие их грани. Во вторых, при изменении параметров модели может изменяться ее топология, о чем необходимо предупреждать оператора. Исходя из этих требований, было предложено использовать CSG (Constructive Solid Geometry) представление, когда объемы определяются путем применения булевых операций к элементарным телам - примитивам [6].
Классическое представление CSG использует три объемные булевские операции VBO (Volumetric Boolean Operation) объединение, пересечение и вычитание, которое мы заменим отрицанием. Для построения многогранников достаточно использовать всего один примитив - плоское полупространство. Операция отрицания в этом случае тривиальна. Попытаемся использовать CSG только в каноническом виде, когда каждый объект представляется в виде объединения пересечений примитивов или их отрицаний. Пересечение примитивов или их отрицаний будем называть кластером, объект рассматривая как объединение некоторого количества кластеров.
Множество допустимых примитивов является расширяемым. Обычно для определения примитивов используются аналитически определяемые поверхности, которые разделяют трехмерное пространство на два полупространства внутреннее, или положительное, и внешнее, или отрицательное. Примерами могут служить плоскость, поверхность сферы, конуса, параболоида и т. д. Если такие полупространства используются в качестве примитивов, то, в зависимости от поставленной цели, можно ссылаться на внешнее или внутреннее полупространство. Замена внутреннего полупространства на внешнее и наоборот является операцией отрицания, используемой в предлагаемом подходе вместо операции вычитания. Кроме аналитически определяемых поверхностей для определения примитивов можно также использовать поверхности вращения и протяжки, кусочно-аналитические поверхности и другие.
Каждый примитив разбивает пространство на две области. Поверхность примитива может быть замкнутой, например сфера, или бесконечной плоское полупространство. В описании объекта используется специальный ключ (селектор), определяющий, какое из полупространств будет использоваться в дальнейшем. В частности, селектор определяет направление внешней нормали к поверхности. Селектор устанавливается для каждого примитива и фактически реализует VBO, операцию отрицания.
Введем теперь два понятия, необходимые для определения параметрических моделей - операторы, определяющие примитив (ООП), и функции, связывающие параметры (ФСП).
Каждый примитив имеет собственное множество параметров (ПП), полностью определяющее его геометрию, позицию и ориентацию в пространстве. Например, прямоугольный параллелепипед имеет 9 параметров: высоту, ширину, длину и 6 параметров положения/ориентации в пространстве. Сфера имеет 4 параметра: радиус и три координаты центра. Конус имеет 6 параметров: угол конуса, три координаты вершины и два угла, определяющие ориентацию оси конуса.
ПП полностью определяют геометрию примитива и его позицию/ориентацию в пространстве в собственной системе координат объекта. Тем не менее, прямое использование ПП может быть не всегда удобным. Например, в случае если требуется расположить сферу, так чтобы четыре заданные точки лежали на ее поверхности, или ориентировать параллелепипед в пространстве так, чтобы его грани были параллельны трем плоскостям и расположены на заданном расстоянии от них. Если такие операции используются часто, то разумно ввести специальные средства их применения в удобной для пользователя форме. Будем называть эти операции операторами, определяющими примитив (0ОП). Целью ООП является преобразование множества параметров в стандартное множество параметров примитива (ПП). ООП имеет собственное множество параметров (ПООП), по которым и вычисляются величины ПП. Может быть несколько ООП для заданного примитива. Например, для плоского полупространства удобно использовать два следующих ООП:
(А) ООН_СДВИГ. Заданная координатная плоскость, определяющая плоское полупространство, сдвигается на заданное расстояние в направлении вектора нормали.
(Б) ООН_ВРАЩЕНИЕ. Координатная плоскость (YZ) сдвигается на заданное расстояние (dist) в направлении вектора нормали, поворачивается вокруг оси Y и оси Z на заданные углы (alpha и beta). Иначе говоря, эта плоскость касательна сфере радиуса dist в точке со еферичеекими координатами alpha и beta и ее вектор нормали направлен наружу сферы.
В параметрических моделях ПП различных примитивов могут быть связаны друг с другом с помощью различных геометрических связей, например параллельность плоскостей или осей, а также равенство длин. Для того чтобы связать ПП, мы используем множество функций, связывающих параметры (ФСП), используемое для вычисления ПООП через внешние параметры модели (ВПМ). Таким образом, геометрия и позиция/ориентация объекта определяется следующим образом:
- ФСП вычисляют ПООП через ВПМ.
- ООП вычисляют ПП через ПООП. Таким образом, геометрия и позиция/ориентация для каждого примитива объекта оказывается полностью определенной в собственной системе координат. Для перехода в мировую систему координат используются также параметры положения/ориентации (ППО) объекта (модели) в целом.
Рассматриваемый подход к созданию параметрических геометрических моделей позволяет создавать довольно широкий класс объектов, а не только многогранники.
Идентификация параметров модели
В качестве минимизируемой целевой функции выбрано среднеквадратическое расстояние от точек, координаты которых определяются с помощью решения фотограмметрической задачи, до плоскостей на которых эти точки должны лежать. Параметрами целевой функции являются ВПМ и ППО, а целевая функция в результате имеет вид:
W (p [1], р [2],...,p [n] ), (1)
где р [1], р [2],...,р [п] - ВПО или ППО.
Для минимизации целевой функции применялся комбинированный алгоритм, использующий градиентный метод и метод Ньютона. Для обоих методов необходимо вычислять целевую функцию W [n], вектор первых частных производных ~gradW [n] (градиент) и матрицу вторых частных производных HESSW [n] [n] (гессиан). W [n] - обозначает, что функция зависит от n параметров, а для градиента и гессиана [n] обозначает их размерность.
Заключение
Изложенный подход реконструкции трехмерной геометрии объектов по небольшому количеству идентифицированных трехмерных особенностей на базе использования соответствующих параметрических моделей был реализован в экспериментальном программном комплексе для ПК и показал достаточно хорошие результаты при реконструкции интерьеров реальных помещений и сцен.
Литература
[1] Bishop С. Fuchs Н. et al. Research Directions in Virtual Environments. Computer Graphics, v.26 (3), Аид. 1992, р.153-177.
[2] IEEE Computer Graphics & Applications, v.14 (1), Jan.1994. (Special issue on Virtual Reality).
[3] Multimedia, Hypermedia und Virtual Reality, Proceedings MHVR'94 1nternational Conference, September, 14-16, 1994, Moscow, Russia.
[4] PhotoModeler. Computer Graphics World, Cadence, CADalyst, 3D Artist and AutoCAD World. Jan./Feb.
[5] PhotoModeler. Eos Systems Inc. Vancouver, В.С., Canada V6J 2G2, 1994.
[6] Woo, Т. С., 1977, Computer aided recognition of volumetric designs. In, McPherson, В. (Ed.), Advances in Computer-Aided Manufacture. North-Holand, Amsterdam.
[7] Д.Волков. Дорогу осилит идущий. Открытые системы сегодня. #8 (29), 1995.
ГРАДИЕНТНЫЙ МЕТОД
~gradW[i] = dW/dp[i] (2) и HESSW[i][j] = d2W/dp[i]dp[j] (3)
Для градиентного метода
p[i][k+1] = p[i][k] + lumbd [k]* v [i][k] (4)
где i, j - номера параметров
k - номер интерации,
lumbd[k] - шаг интерации и v[i][k] = - dW/dp [i] (5)
В (5) производные вычисляются для величин параметров на шаге k и таким образом, зависят от номера итерации. Шаг итерации также перевычисляется на каждой итерации по формуле:
lumbd [k] = (6) sum (i = 1,n) (dW/dp [i]**2) sum (i = 1,n) (sum (l = 1,n) (d2W/dp [i] dp [l]) * dW/dp [i] * dW/dp [l]),
где все произвольные вычислены для величин параметров на шаге k.
МЕТОД НЬЮТОНА
Для метода Ньютона итерации начинаются с некоторой заданной начальной точки ~p0 = |p[1][0]) и продолжаются до получения удовлетворительного результата путем решения следующей системы линейных уравнений:
dW/dp [i] + sum(l=1,n) (d2W/dp[i]*(p[l][k+1] - p[l][k])) = 0 (7) i = 1,...,n
