автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Алгоритмы построения трехмерных компьютерных моделей реальных объектов для систем виртуальной реальности

На правах рукописи

Конушин Антон Сергеевич

Алгоритмы построения трехмерных компьютерных моделей реальных объектов для систем виртуальной реальности

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2005

Работа выполнена в Институте прикладной математики им. М.В.Келдыша РАН

Научный руководитель - кандидат физико-математических наук, доцент Баяковский Юрий Матвеевич

Официальные оппоненты:

- доктор физико-математических наук, Кугушев Евгений Иванович

- кандидат физико-математических наук, Иванов Денис Владимирович

Ведущая организация:

Государственный Научно-Исследовательский Институт Авиационных Систем (ГосНИИАС)

Защита состоится «_»_2005 г. в_часов

на заседании Диссертационного совета Д 002.024.01 в Институте прикладной математики им. М.В. Келдыша РАН по адресу: 125047, Москва, Миусская пл. 4.

С диссертацией можно ознакомится в библиотеке Института прикладной математики им. М.В. Келдыша РАН

Автореферат разослан «_»_2005 г.

Ученый секретарь диссертационного совета

доктор физико-математических наук

Т.А. Полилова

2ЯХ-Ч

/9061

Общая характеристика работы Актуальность работы

Термином «Виртуальная реальность» (ВР) обозначают новые виды компьютерных интерфейсов, нацеленных на создание у пользователя ощущения реальности окружения. Это ощущение вынуждает пользователя взаимодействовать с окружающим миром точно так же, как он бы вел себя в реальности. Типичным примером систем ВР являются тренажеры различных транспортных средств от автомобилей до пилотируемых космических аппаратов, достоверно воспроизводящие ощущения водителя или пилота, позволяющие обучать людей управлению ими, Рис. 1(а). Элементы виртуальной реальности также используются в интерфейсах, называемых «расширенной реальностью», когда в изображения реального мира добавляются синтезированные объекты. Последнее необходимо, например, при архитектурном планировании строительства и реконструкции зданий, Рис. 1(6).

(а) (б)

Рис. 1 Интерфейсы типа "виртуальная реальность" (а) и "расширенная

реальность"(б)

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

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

уровня системы, например, Cañóme, требуют

3 СПгтч*Цгрг \ 09

■ i Л~т #

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

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

Цель работы

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

Научная новизна работы

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

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

Практическая значимость и реализация

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

На основе разработанных автором алгоритмов разработана система построения моделей 3-х мерных объектов простой формы по фотографиям и видеопоследовательностям, не требующая большого объема взаимодействия с пользователем. Система разрабатывалась в Лаборатории Компьютерной Графики и Мультимедиа факультета ВМиК МГУ им. Ломоносова по заказу Samsung Advanced Institute of Technologies.

Апробация работы и публикации

Основные результаты работы докладывались и обсуждались на:

• 15-ой международной конференции по компьютерной графике и машинному зрению GraphiCon 2005, Россия, Новосибирск, 2005

• 12-ой международной конференции «Ломоносов-2005»

• 14-ой международной конференции по компьютерной графике и машинному зрению GraphiCon 2004, Россия, Москва, 2004

• 13-ой международной конференции по компьютерной графике и машинному зрению GraphiCon 2003, Россия, Москва, 2003

• Международной конференции по обработке изображений «International Conference on Image Processing 2002», США, Рочестер, 2002

• Семинаре по компьютерной графике и машинному зрению Ю.М.Баяковского (ф-т ВмиК МГУ)

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

Структура и объем работы

Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложения. Содержание работы изложено на 158 страницах (включая 8 страниц приложения). Список литературы включает 91 наименование. В работе содержится 45 рисунков и 4 таблицы.

Содержание работы

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

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

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

■ЕГЛ

1=}

Фотосъемка

Поиск и согласование точечных особенностей

Вычисление 3-х мерных точек И траектории движения камеры

Построение модели

Изображения

Соответствия

Точечных особенностей

Траектория движения камеры и набор 3-х мерных точек

Модель объекта

Рис. 2 Общая схема работы системы построения 3-х мерных моделей по набору изображений

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

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

такой, что f(x,8)=о; где x = {x,},i = \..n - набор точек исходных данных, f(x,0) задает исследуемую математическую модель. Классическим примером задачи оценки параметров является аппроксимация набора точек прямой линией. В таком случае л-= {*,}.,=i.jv- это набор точек, f(x,6) - уравнение прямой, в -параметры прямой. Исходные данные х загрязнены, т.е. помимо точек, порожденных исследуемой моделью, в данных содержатся загрязняющие точки, порожденные ошибками измерений, которые никак не зависят от исследуемой модели. Загрязняющие точки называются выбросами (outliers) Доля порожденных исследуемой моделью данных обозначается как уе[о,ц. Точки, порожденные исследуемой моделью зашумлены некоторой помехой е, математическое ожидание которой л/(*> = о, а дисперсия D(s)=a\o=const. Метод оценки параметров модели по набору загрязненных исходных данных называется робастным методом оценки. Наибольшее распространение в области машинного зрения получили методы на основе случайных выборок. Первый подобный алгоритм RANdom SAmpling Consensus (RANSAC) был предложен в 1981 году Фишером и Болесом.

Для того, чтобы оценить параметры модели необходимо определить, какие точки из исходного набора являются загрязняющими выбросами, а какие нет. Однако в общем случае не существует способа определить заранее, является ли данная точка выбросом. Схема RANSAC решает эту проблему путем случайного перебора некоторого количества выборок из исходных данных. По каждой выборке оцениваются параметры модели о. Предполагается, что значение функции f(x,e) достигает своего минимума на гипотезе в, оцененной по выборке, не содержащей выбросов. Каждая выборка строится случайным образом, т.е. из набора исходных данных последовательно выбирается нужное количество точек. Каждая из точек набора исходных данных берется с равной вероятностью. Для максимизации вероятности построения выборки без выбросов, размер выборки Н берется минимально необходимым для оценки параметров модели.

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

алгоритма робастной оценки параметров модели, адаптирующегося к уровню шума и доле загрязнения.

Для точной робастной оценки параметров моделей, в диссертационной работе предложен новый алгоритм AMLESAC (Adaptive Maximum Likelihood Estimation SAmpling Consensus). Он основан на общей схеме робастной оценки параметров на основе случайных выборок, но дает оценку максимального правдоподобия гипотезы с одновременным вычислением параметров шума, с которым генерировались исходные данные. Алгоритм поиска вектора параметров модели в с наибольшим правдоподобием опирается на предположение, что исходные данные х представляют собой смесь двух выборок. Первая выборка состоит из точек, удовлетворяющих исследуемой модели. Для таких точек ошибка согласования с моделью удовлетворяет нормальному распределению. Вторая выборка состоит из выбросов, ошибка согласования которых удовлетворяет равномерному распределению. Полная схема алгоритма может быть сформулирована следующим образом:

1) Вычислить количество итераций алгоритма М по априорной оценке у.

2) Повторить М раз:

a. Построить случайную выборку исходных данных s„ с X.

b. Оценить гипотезу в„ по выборке Sk.

c. Применить локальную оптимизацию к гипотезе вк.

d. Построить случайную выборку исходных данных ТксХ.

e. Оценить параметры смеси <ти у для текущей гипотезы в, и выборки

т>-

f. Измерить правдоподобие гипотезы et по всем исходным данным X с оцененными значениями а и у.

3) Выбрать гипотезу в с максимальным правдоподобием.

4) С помощью метода нелинейной минимизации уточнить гипотезу в

В качестве целевой функции используется логарифм правдоподобия исходных данных X для модели с параметрами в :

где е =|*-х| - это расстояние (норма L2) между измеренными координатами х и их математическим ожиданием х реальной точки х . х - это такая точка, которая удовлетворяет уравнению F(x,e) = о, и минимизирует L2 норму е =||х -х||, v - это объем пространства, внутри которого выбросы распределены равномерно.

(В)

(а) (б)

(г)

(Д)

(е)

Рис. 3 Применение АМЪЕБАС для задачи оценки позы камеры, (а),(б) Репроекция 3-х мерных точек на б и 9 кадры при оценке позы с помощью МБАС (г).(д) Репроекция 3-х мерных точек на 6 и 9 кадры при оценке позы с помощью АМЬЕБАС (в).(е) Траектория движения камеры и 3-х мерные

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

Значение правдоподобия гипотезы зависит от доли у и дисперсии ошибок а, поэтому точность оценки правдоподобия напрямую зависит от точности оценки этих параметров. Для каждого набора исходных данных значение этих параметров может быть разным, поэтому в каждом случае они должны оцениваться отдельно. В предлагаемом алгоритме для каждой гипотезы в производится поиск в пространстве у и а таких значений, при которых правдоподобие в достигает максимума. Для этого проверяются с некоторым шагом все варианты доли ук е 0,^,1], начиная с минимального значения утт. Для каждого ^оценка ак вычисляется с помощью медианы ошибок ук '.V точек с наименьшей ошибкой. По ак с помощью итеративного алгоритма вычисляется уточненное значение ук . В качестве (у,<т) выбирается пара {ук ,<гк), соответствующая наименьшему значению логарифма правдоподобия, которая дополнительно уточняется методом градиентного спуска.

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

ошибка в оценке траектории движения камеры

х с наименьшей ошибкой е =|х - х ||. Как показывают эксперименты, локальная оптимизация значительно повышает точность оценки параметров смеси (у,<т) и самой гипотезы.

Для снижения вычислительной сложности алгоритма параметры смеси (у,<т) оцениваются с использованием не всех исходных данных, а только части. Для этого случайным образом строится выборка Tt с х, и параметры оцениваются

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

Количество итераций М выбирается таким образом, чтобы вероятность построения выборки без выбросов размером Н с априорной оценкой максимальной доли выбросов в исходных данных (1-у) была больше заданной, обычно 95% - 97%.

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

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

Точечной особенностью х' изображения называется точка, чья окрестность отличается от окрестностей близлежащих точек по выбранной мере, т.е. {V*: < г -> р(Пх, )>£•}, где С1; -окрестность точки х, называемая окном поиска, a p(Qx,Qx) - функция близости окрестностей по некоторой мере. Последовательность положений точечной особенности },/ = «„„„,, где i -номер кадра видеопоследовательности, называется следом точечной особенности. пааП - первый кадр, на котором обнаружена точечная особенность, nem¡ - последний кадр, на котором определено положение точечной

особенности, nend >пшп. След точечной особенности {*',},/ = nJM„, nenJ называется корректным, если существует точка трехмерной сцены X, такая что х', = P,(X),i = niurl,niml, где Р, - уравнение перспективной проекции, соответствующее i-ому изображению. Такая точка X называется точечной особенностью наблюдаемой сцены. Другими словами, корректный след точечной особенности представляет собой совокупность проекций некоторой точки сцены на сегмент кадров исходной последовательности. Выделение на последовательности изображений набора следов точечных особенностей устанавливает предполагаемое соответствие между изображениями и набором точечных особенностей сцены. Соответствием (match) называется пара точек х,,де2 на изображениях которые соответствуют одной и той же точечной особенности х'. Фактически, любая пара точек xh, xh из следа точечной особенности {*',}, / = пмп, nend является соответствием. Соответствие называется корректным, если существует точка трехмерной сцены X, проекциями которой являются точки хн, xh.

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

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

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

матрицы. Для поиска нового ключевого кадра используется алгоритм отслеживания особенностей Лукаса-Канаде. Пусть /, - последний ключевой кадр, тогда отслеживание продолжается до нового ключевого кадра 11, такого, что оцененная на соответствиях точечных особенностей на паре кадров (/,,/,) фундаментальная матрица лучше согласуется с исходными данными, чем томография. Для сравнения степени согласия используется информационный критерий ОМС. Если на протяжении 10 кадров фундаментальная матрица оказывается менее согласованной с построенным набором соответствий, то в качестве нового ключевого кадра выбирается кадр 1М0. В этом случае корректным видом ограничения на этом сегменте признается томография.

После определения нового ключевого кадра производится сегментация ложных следов на сегменте [/,,/;]• Те из следов, которые не удовлетворяют корректному виду ограничений, признаются ложными и отбрасываются.

(а) (б) (в)

Рис. 4 Управляемое слежение, (а) Соответствия, найденные алгоритмом Лукаса-Канаде (б) Положение точек на новом кадре, предсказанное с помощью переноса томографией (в) Результат работы управляемого слежения.

Все углы рамки были корректно отслежены.

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

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

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

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

инициализации следов из каждой области выбирается одинаковое количество особенностей, вследствие чего возрастает равномерность распределения следов по изображению, снижается вероятность образования доминантного подмножества. Пример работы адаптивной схемы приведен на Рис. 5.

(а) (б)

Рис. 5 Адаптивная схема инициализации следов, (а) Обычная схема

инициализации следов, (б) Адаптивная схема инициализации следов.

Необходимо отметить, что на количество выбранных особенностей на салфетке значительно снизилось, а на коробке выросло. Соответственно следы более равномерно распределены по изображению.

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

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

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

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

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

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

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

алгоритм разбивает исходную последовательность ключевыми кадрами на сегменты, на каждом из которых структура и движение вычисляются независимо последовательным алгоритмом. Затем траектории движения камеры на соседних сегментах объединяются, для чего вычисляется относительное положение и ориентация в пространстве камер последнего и первого кадров соседних сегментов. Процесс повторяется до тех пор, пока не будет вычислена траектория движения камеры на всей исходной последовательности изображений. Для повышения точности калибровки при уточнении методом связок на каждом сегменте используются только такие 3-х мерные точки, следы которых определяются как корректные на протяжении всего сегмента.

Для оценки позы камеры используется подмножество точек структуры сцены, видимых с данного кадра, и набор их проекций, взятых из набора следов точечных особенностей. Для устойчивой к накоплению ошибок оценке позы камеры предлагается новый алгоритм оценки позы камеры, использующий алгоритм АМЬЕвАС, автоматически адаптирующийся к уровню ошибок и загрязнения в исходных данных. Для оценки позы камеры по набору из 6 трехмерных точек и соответствующих им проекций без выбросов также предлагается новый линейный алгоритм. Он состоит из следующих шагов:

1. Вычисление проекций точек на идеальной плоскости камеры

2. Оценка матрицы перспективной проекции методом наименьших квадратов (МНК) путем составления и решения системы линейных уравнений

3. Вычисление ориентации камеры в пространстве по матрице перспективной проекции

4. Оценка положения камеры в пространстве методом МНК с учетом вычисленной ориентации камеры

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

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

вышеописанными лучами. рЩ

(а) (б) (в)

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

Проведенная серия экспериментов на синтетических и реальных данных продемонстрировала превосходство предложенных алгоритмов над существующими аналогами по устойчивости и точности оценки. Пример работы алгоритма приведен на Рис. 6.

В пятой главе описываются два подхода к построению трехмерной модели наблюдаемых объектов: на основе методов подгонки примитивов и с использованием методов плотного стерео, а также приводит описание некоторых алгоритмов обработки построенных моделей.

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

• Выделение пользователем изображения моделируемого объекта на исходных изображениях

• Выбор пользователем типа параметрической модели

• Поиск начального приближения значений параметров модели

• Уточнение значений параметров

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

Предложенный алгоритм подгонки модели цилиндра в качестве параметров использует положение оси цилиндра в пространстве, высоту и радиус цилиндра. На первом шаге находится начальное приближение оси цилиндра. Пусть {р,},1=1,М- набор точек на поверхности тела вращения, {л(},; = 1,М-нормали к поверхности тела вращения. Тогда ось вращения тела вращения пересекает большинство линий вида {р1 +аи,}. Оценка множества нормалей производиться путем аппроксимации плоскостью множества точек из окрестности выбранной точки. Аппроксимация производится с помощью робастного алгоритма \1SAC, причем нормаль оценивается только по таким плоскостям, степень согласования которых с множеством точек из окрестности не превышает заданного порога. По построенным нормалям строится множество прямых вида {р, +ап,}, использующихся как исходные данные для оценки оси цилиндра. Оценка производится робастным алгоритмом МБАС. Каждая гипотеза выбирается как прямая, сумма расстояний от которой до всех прямых из выборки минимальная. На втором шаге верхняя и нижняя границы цилиндра определяются как верхняя и нижняя границы множества проекций точек цилиндра на ось. Радиус цилиндра вычисляется как среднее расстояние от оси цилиндра до точек, не лежащих на его верхней и нижней границах.

После того, как получено начальное приближение значений параметров цилиндра, они уточняются с помощью нелинейного алгоритма минимизации Гаусса-Ньютона или Левенберга-Макардта. Пусть Су! - поверхность цилиндра. т В качестве целевой функции используется взвешенная сумма расстояний от точек до поверхности цилиндра:

где и>(.) - робастная весовая функция, называемая М-оценкой, предназначенная для минимизации влияния загрязняющей помехи, т.е. таких точек, которые не лежат на поверхности цилиндра.

(а) (б) (в)

Рис. 7 Подгонка цилиндра.(а) Исходное множество точек (б) Построенная параметрическая модель (в) Проекция сеточной модели на исходное

изображение

Рис. 7 иллюстрирует процесс подгонки модели цилиндра к набору трехмерных точек, полученных по последовательности изображений реальной сцены.

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

• Выделение плоскостей видимых граней с помощью робастного алгоритма

• Определение осей параллелепипеда

• Определение границ граней параллелепипеда

• Определение невидимых граней по вычисленным границам видимых

Плоскости в наборе точек выделяются с помощью итеративного применения робастного алгоритма М8АС, каждая плоскость-гипотеза проводится по к>3 точкам с помощью метода МНК. Оси параллелепипеда определяются путем вычисления множества нормалей к видимым граням и их векторного произведения. Границы грани оцениваются как границы множества проекций точек, принадлежащих грани, на оси параллелепипеда. На Рис. 8 приведен пример работы алгоритма на наборе 3-х мерных точек, полученных с последовательности изображений реальной сцены.

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

Для вычисления текстуры поверхности моделируемого объекта по полученной параметрической модели строится сеточная модель поверхности объекта.

(а) (б) (в)

Рис. 8 Инициализация параметров параллелепипеда (а) Исходное множество точек (б)Найденные робастным алгоритмом плоскости (в) Все плоскости параллелепипеда

Второй подход к реконструкции трехмерных моделей использует представление моделей в виде набора изображений с картами глубины. Подобные модели называются основанными на изображениях (image-based models), Совместно с другими сотрудниками Лаборатории Компьютерной Графики МГУ автором был разработан формат записи таких моделей, который был принят в стандарт AFX MPEG4. Разработанный формат опирается на иерархическое представление сцены, используемое в языке описания трехмерных моделей и сцен VRML, и совместим с бинарным форматом сцен BIFS, являющимся основой стандарта MPEG4. Алгоритм построения таких моделей формулируется следующим образом:

• Вычисление карт глубины для всех исходных изображений {/,},/= 1,ЛГ с

помощью алгоритма плотного стерео

• Совместная обработка набора изображений с картами глубины для получения модели объекта

Плотным стерео называется задача поиска для каждого пикселя на одном изображении I, соответствующего ему пикселя на другом изображении 1Г После установления попиксельного соответствия между изображениями, для каждого пикселя вычисляется положение соответствующей ему 3-х мерной точки с помощью алгоритма триангуляции.

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

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

(а) (б) (в)

Рис. 9 Примеры реконструированных моделей объектов реального мира

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

На Рис. 9 приведены примеры построенных моделей реальных объектов.

В заключении сформулированы основные результаты работы.

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

Основные результаты диссертационной работы:

1. Предложены новые алгоритмы построения следов точечных особенностей на последовательности фотоизображений или видеопоследовательности, которые позволяют добиться более высокой точности определения траектории движения камеры.

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

3. Разработан комплекс алгоритмов для генерации трехмерной модели объектов простой формы типа цилиндр и параллелепипед по облаку трехмерных точек. Алгоритмы успешно функционируют на загрязненных данных, что позволяет сократить объем взаимодействия с пользователем для уточнения полученных моделей.

4. На основе предложенных алгоритмов разработана программная система построения трехмерных компьютерных моделей реальных объектов по набору фотоизображений или видеопоследовательности для формирования виртуальной среды.

Публикации по теме диссертации

1. A.Konouchine, V.Gaganov, V.Vezhnevets "AMLESAC: A New Maximum Likelihood Robust Estimator", Proc. Graphicon-2005, pp, 93-100, Novosibirsk, June 2005

2. A.Konouchine, V.Gaganov, V.Vezhnevets "Combined Guided Tracking and Matching with Adaptive Track Initialization", Proc. Graphicon-2005, pp. 301-304, Novosibirsk, June 2005

3. А.Конушин «Система построения трехмерных моделей реальных объектов по последовательности изображений» (тезисы), с.ЗО, Москва, Ломоносов-2005

4. А.Конушин, К.Мариничев, В.Вежневец "Обзор робастных схем оценки параметров моделей на основе случайных выборок". Труды конференции Graphicon-2004, с.275-278, Москва, сентябрь 2004.

5. Е.Лисицин, А.Конушин, В.Вежневец "Отслеживание точечных особенностей в видеопоследовательностях с изменениями резкости". Труды конференции Graphicon-2004, с.233-236, Москва, сентябрь 2004.

6. L. Levkovich-Maslyuk, A.Ignatenko, A.Zhirkov, A.Konushin, I.KJPark, M. Han, Y. Bayakovski. "Depth Image-Based Representation and Compression for Static and Animated 3-D Objects". IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 14, NO. 7, pp. 1032-1045, JULY 2004.

7. A.Ignatenko, A.Konushin. "A Framework for Depth Image-Based Modeling and Rendering". Proc. Graphicon-2003, pp. 169-172, Moscow, Russia, September 2003.

8. Y. Bayakovski, L. Levkovich-Maslyuk, A. Ignatenko, A. Konushin, D. Timasov, A. Zhirkov, M.Han, I.K.Park "Depth Image-Based representations for static and animated 3D objects". IEEE 2002 International Conference on Image Processing, vol.3, pp.25-28, Rochester, New York, September 22-25, 2002

»20377

РНБ Русский фонд

2006-4 19037

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N00510 от 01.12.99 г. Подписано к печати 24.10.2005 г. Формат 60x90 1/16. Усллечл. 1,5. Тираж 100 экз. Заказ 691. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

ВВЕДЕНИЕ.

ГЛАВА 1. СИСТЕМА РЕКОНСТРУКЦИИ 3-Х МЕРНЫХ МОДЕЛЕЙ ПО НАБОРУ ИЗОБРАЖЕНИЙ.

1.1 Обзор существующих подходов.

1.2 Предлагаемая система.

ГЛАВА 2. РОБАСТНАЯ ОЦЕНКА ПАРАМЕТРОВ МОДЕЛИ.

2.1 Постановка задачи.

2.2 РОБАСТНАЯ ОЦЕНКА ПАРАМЕТРОВ МОДЕЛИ.

2.2.1 Общая схема оценки параметров на основе случайных выборок.J б

2.2.2 Робастное уточнение оценки параметров модели.

2.3 Обзор существующих алгоритмов на основе случайных выборок.

2.3.1 Варианты оценочных функции.

2.3.2 Варианты схемы выборки.

2.3.3 Модификации схемы оценки модели.

2.3.4 Другие модификации.

2.4 Колебания шума в последовательности оценок.

2.4.1 Задача оценки позы камеры.

2.4.2 Колебание шума.

2.5 Предлагаемый алгоритм.

2.5.1 Оценка максимального правдоподобия.

2.5.2 Оценка параметров шума в исходных данных.

2.5.3 Критерий остановки.

2.5.4 Оценка параметров смеси вероятностей на выборке исходных данных.

2.5.5 Локальная оптимизация.

2.5. б Полная схема алгоритма AMLESA С.

2.6 Нелинейная минимизация.~.

2. б. 1 Оценка параметров смеси по текущей гипотезе.

2. б. 2 Параметры смеси как свободные параметры модели.

2.7 Применение алгоритма на реальных данных.

2.8 Применение алгоритма на синтетических данных.

2.8.1 Тесты на синтетических данных — подгонка линий.

2.8.2 Оценка позы камеры - тесты на синтетических данных.

Термином «Виртуальная реальность» (BP) обозначают новые виды компьютерных интерфейсов, нацеленных на создание у пользователя ощущения реальности окружения. Это ощущение вынуждает пользователя взаимодействовать с окружающим миром точно так же, как он бы вел себя в реальности. Типичным примером систем BP являются тренажеры различных транспортных средств от автомобилей до пилотируемых космических аппаратов, достоверно воспроизводящие ощущения водителя или пилота, позволяющие обучать людей управлению ими, Рис. 1(a). Элементы виртуальной реальности также используются в интерфейсах, называемых «расширенной реальностью», когда в изображения реального мира добавляются синтезированные объекты. Такое расширение реальности необходимо, например, при архитектурном планировании строительства и реконструкции зданий, Рис. 1 (б). а) (б)

Рис, 1 Интерфейсы типа "виртуальная реальность" (а) и "расширенная реальность" (б).

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

Наиболее легкодоступным источником информации об объектах реального мира являются фотоизображения, поэтому в последние 15 лет большое внимание уделяется разработке алгоритмов и систем построения моделей реальных объектов по изображениям. Однако доведенные до коммерческого уровня системы, например, Canoma [1], ImageModeler [2], PhotoModeler [3], требуют точного выделения вершин, ребер и границ объектов на фотоизображениях и сопоставления их вершинам, ребрам и границам выбранной модели простой формы. Этот процесс очень трудоемок, поэтому подобные системы не получили широкого распространения.

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

Цель работы

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

Научная новизна работы

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

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

Практическая значимость и реализация

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

На основе предложенных алгоритмов разработана система построения моделей 3-х мерных объектов простой формы по фотографиям и видеопоследовательностям, не требующая большого объема взаимодействия с пользователем. Система разрабатывалась в Лаборатории Компьютерной Графики и Мультимедиа факульте- i та ВМиК МГУ им. Ломоносова по заказу Samsung Advanced Institute of Technologies.

Апробация работы и публикации

Основные результаты работы докладывались и обсуждались на:

• 15-ой международной конференции по компьютерной графике и машинному зрению GraphiCon 2005, Россия, Новосибирск, 2005

• 12-ой международной конференции «Ломоносов-2005»

• 14-ой международной конференции по компьютерной графике и машинному зрению GraphiCon 2004, Россия, Москва, 2004

• 13-ой международной конференции по компьютерной графике и машинному зрению GraphiCon 2003, Россия, Москва, 2003

• Международной конференции по обработке изображений «International Conference on Image Processing 2002», США, Рочестер, 2002

• Семинаре по компьютерной графике и машинному зрению Ю.М.Баяковского (ф-т ВмиК МГУ)

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

Структура работы

Диссертация состоит из пяти глав, введения и приложения.

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

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

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

Четвертая глава посвящена методам вычисления траектории камеры и построения структуры наблюдаемой сцены по набору следов точечных особенностей.

В пятой главе описываются два подхода к построению трехмерной модели наблюдаемых объектов: на основе методов подгонки примитивов и с использованием методов плотного стерео, а также приводит описание некоторых алгоритмов обработки построенных моделей.

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

Основные результаты работы состоят в следующем:

1. Предложены новые алгоритмы построения следов точечных особенностей на последовательности фотоизображений или видеопоследовательности, которые позволяют добиться более высокой точности определения траектории движения камеры.

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

3. Разработан комплекс алгоритмов для генерации трехмерной модели объектов простой формы типа цилиндр и параллелепипед по облаку трехмерных точек. Алгоритмы успешно функционируют на загрязненных данных, что позволяет сократить объем взаимодействия с пользователем для уточнения полученных моделей.

4. На основе предложенных алгоритмов разработана программная система построения трехмерных компьютерных моделей реальных объектов по набору фотоизображений или видеопоследовательности для формирования виртуальной среды.

Благодарности

Автор выражает благодарность научному руководителю Ю.М. Баяковскому за содействие и помощь в работе и своим коллегам В.П.Вежневцу, А.В. Игнатенко, В.А. Гаганову и Е.В. Лисицину за ценные консультации и плодотворные совместные обсуждения.

5.5 Заключение

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

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

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

Алгоритм построения модели объекта в форме параллелепипеда опирается на выделение видимых плоскостей робастным алгоритмом. Положение невидимых плоскостей вычисляется с помощью определения осей и границы проекции 3-х мерных точек на эти оси.

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

Г) (Д) <0

Рис. 40 Примеры построенных моделей реальных объектов.

Также в данной главе рассмотрен разработанный алгоритм для построения и обработки моделей в виде набора изображений с картами глубины. Модель записывается в файл формата MPEG4 AFX. Предложен алгоритм модификации текстуры моделей в виде набора изображений с глубиной, которые требует от пользователя непосредственного редактирования визуализированных изображений модели

1. Сапота, http://www.metacreations.com/products/canoma/

2. Image modeler, http://www.realviz.com/products/im/index.php

3. Photomodeler, http://www.photomodeler.com

4. P. Debevec, C. Taylor, J. Malik. Modeling and Rendering Architecture from Photographs: A Hybrid Geometry and Image-Based Approach. In Proc. Siggraph'96, pp.ll-20, ACM Press, New York, 1996.

5. V.Valiev. 3D Reconstruction of Architectural Objects from Photos. In Proc. Graphi-con'99, pp.171-173, Russia, 1999.

6. Барладян Б.Х., Зуева Е.Ю., Кугушев E. И. Параметрические модели трехмерных объектов и их использование для реконструкции сцен. Сборник "Вопросы кибернетики" (ВК-181), с. 136-147, Москва, 1995.

7. I. Сох, S. Hingorani, S. Rao. A Maximum Likelihood Stereo Algorithm. Computer Vision and Image Understanding, Vol. 63, No. 3, May 1996.

8. D. Scharstein, R. Szeliski. A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms. IJCV Vol.47, Issue 1-3, pp.7-42, April-June 2002.

9. S.M. Seitz, C.R. Dyer. Photorealistic Scene Reconstruction by Voxel Coloring. In. Proc. CVPR'97, pp. 1067-1073, 1997.

10. K. N. Kutulakos, S. M. Seitz. A Theory of Shape by Space Carving. International Journal of Computer Vision, Vol. 38, No. 3, pp. 199-218, July 2000.

11. P. Eisert, E. Steinbach, B. Girod. Multi-hypothesis, Volumetric Reconstruction of 3D Objects from Multiple Calibrated Camera Views. ICASSP, pp. 3509-3512, 1999.

12. P. Eisert, E. Steinbach, B. Girod, M. Levoy, P. Hanrahan. Lightfield Rendering. Proc. SIGGRAPH '96, pp 31-12, ACM Press, New York, 1996.

13. S. Gortler, R. Grzeszczuk, R. Szeliski, M. F. Cohen. The Lumigraph. Proc. SIGGRAPH'96, pp. 43-54, ACM Press, New York, 1996.

14. V. A. Knyaz, S. Yu. Zheltov. Approach to Accurate Photorealistic Model Generation for Complex 3D Objects. International Archives of Photogrammetry and Remote Sensing, Vol. XXXIII, part B5/1, pp. 428-433, Amsterdam, The Netherlands, 2000.

15. V.A.Knyaz, S.YU. heltov, Stepanyants D.G., Automated photogrammetric system for photorealistic skull 3D reconstruction. Proceeding of SPIE Videometrics and Optical Methods for 3D Shape Measurements,Vol. 4309, pp. 336-345, 2001.

16. A.Fitzgibbon, A.Zisserman, Automatic camera tracking. In Proc. Video Registration^, pp. 17-35, 2003.

17. P. A. Beardsley, P. H. S. Torr, A. Zisserman. 3D model acquisition from extended image sequences. In Proc. ECCV'96, pp. 683-695, Cambridge, 1996.

18. S. Gibson, J. Cook, T. L. J. Howard, R. J. Hubbold, D. Oram. Accurate camera calibration for offline, video-based augmented reality. In Proc. ISMAR'02 pp.37-46, 2002.

19. Boujou, http://www.2d3.com

20. PFTrack, http://www.thepixelfarm.co.uk/products/products.aspx?PID=3

21. M. Pollefeys, R. Koch, M. Vergauwen, B. Deknuydt, L.Van Gool. Three-dimensional scene reconstruction from images. In Proc. SPIE Electronic Imaging, Three-Dimensional Image Capture and Applications III, Vol. 3958, pp.215-226, 2000.

22. C.V.Stewart. Robust parameter estimation in computer vision. SI AM Review v.l, n.3, pp. 513-537, 1999.

23. J.Illingworth. J.Kittler. A survey of the Hough transform. CVGIP v.44 pp. 87-116, 1988.

24. P.J.Rousseeuw. Least median of squares regression. Journal of the American Statistical Association, vol.79 pp.871-880, 1984.

25. M.A.Fischler, R.C.Bolles. Random Sample Consensus: A paradigm for model fitting with applications to image analysis and automated cartography. In Communications of the ACM, 24 (6), pp. 381-395, 1981.

26. P.H.S. Torr and A. Zisserman. Robust parameterization and computation of the trifocal tensor. In proc. Image and Vision Computing, 15, pp. 591-605, 1997.

27. P.H.S.Torr, A.Zisserman. Robust Computation and Parameterization of Multiple View Relations. In Proc. ICCV'98, pp.727-732, 1998.

28. В. Triggs, P. McLauchlan, R. Hartley, A. Fiztgibbon, Bundle Adjustment A Modern Synthesis. In B. Triggs, A. Zisserman, R. Szeliski (Eds.), Vision Algorithms: Theory and Practice, LNCS, Vol.1883, pp.298-372, Springer-Verlag, 2000.

29. А.Конушин, К.Мариничев, В.Вежневец. Обзор робастных схем оценки параметров на основе случайных выборок. Труды Графикон-2004, с.275-278, 2004.

30. P.H.S.Torr, A.Zisserman, MLESAC: A New Robust Estimator with Application to Estimating Image Geometry. In CVIU, vol. 78, pp. 138-156, 2000.

31. D.Forsyth, J.Ponce. Computer Vision: A modern approach. Prentice Hall, 2003.

32. B. Tordoff, D. Murray. Guided sampling and consensus for motion estimation. In Proc. ECCV'02, v. 1, pp. 82-96, 2002.

33. P.H.S. Torr. Bayesian Model Estimation and Selection for Epipolar Geometry and Generic Manifold Fitting. In IJCV, Vol. 50, Issue. 1, pp. 27-45, 2002.

34. Z.Zhang, R.Deriche, O.Faugeras, Q.T.Luong. A robust technique for matching two uncalibrated images through the recovery of the unknown epipolar geometry. AI Journal, vol.78, pp. 87-119, 1994.

35. D. Myatt, P.H.S. Torr, S. Nasuto, R. Craddock. NAPSAC: High Noise, High Dimensional Robust Estimation. In Proc. BMVC'02, pp. 458-467, 2002.

36. O.Chum, J.Matas. Randomized RANSAC with T(d,d) test. In Proc. British Machine Vision Conf., pp. 448-457, 2002.

37. D.Nister. Preemptive RANSAC for live structure and motion estimation. In Proc. ICCV'03, pp. 199-206, 2003.

38. O.Chum, J.Matas, J.Kittler. Locally Optimized RANSAC. In Proc. 25th Pattern Recognition Symposium (DAGM), Vol. 2781 of LNCS, pp. 236-243, 2003.

39. O.Chum, J.Matas, S.Obdrzalek. Enhancing RANSAC by Generalized Model Optimization. In Proc. ACCV 2004, p. 812-817, 2004.

40. C.Harris, M. Stephens. A combined corner and edge detector. Fourth Alvey Vision Conference, pp. 147-151, 1988.

41. A.Fusiello. Uncalibrated Euclidean reconstruction: A review. Image and Vision Computing, Vol.18, Issue 6-7, pp. 555-563, 2000.

42. R. Hartley, P. Sturm, Triangulation. In CVIU, Vol.68, Issue.2, pp.146-157, 1997.

43. C.L.Feng, Y.S.Hung. A Robust Method for Estimating the Fundamental Matrix. In Proc. DICTA 2003, pp. 633-642, 2003.

44. A.Konouchine, V.Gaganov, V.Vezhnevets. AMLESAC: A New Maximum Likelihood Robust Estimator. In Proc. Graphicon'05, pp.93-100, 2005.

45. S.M.Smith, J.M.Brady. SUSAN a new approach to low-level image processing. IJCV, Vol. 23(1): pp. 45-78, 1997.

46. P.Smith, D.Sinclair, R.Cipolla, K.Wood, Effective corner matching. In. Proc. BMVC'98, Vol.2, pp.545-556, 1998.

47. D.Lucas, T.Kanade. An Iterative Image Registration Technique with an Application to Stereo Vision. In Proc. UCAI'81, pp 674-679, 1981.

48. C.Tomasi, T.Kanade. Detection and tracking of point features. Technical Report CMU-CS-91-132,Carnegie Mellon University, April 1991.

49. J. Shi, C. Tomasi. Good features to track. In Proc. CVPR'94, pp. 593-600, 1994.

50. H.Jin, P.Favaro, S.Soatto. Real-time tracking and outlier rejection with changes in illumination. In Proc. ICCV'01, vol.1, pp.684-692, 2001.

51. J.Y. Bouguet. Pyramidal implementation of the lucas-kanade feature tracker, Microsoft Research Labs, Tech. Rep., 1999.

52. T. Tommasini, A. Fusiello, E. Trucco, V. Roberto. Making good features to track better. In Proc. IEEE CVPR'98, pp. 178-183, 1998.

53. A.Fusiello, E.Trucco, T.Tommasini, V.Roberto. Improving feature tracking with robust statistics. Pattern Analysis and Applications, Vol. 2, No. 4, pp.312-320, 1999.

54. R. Hartley. In Defense of the Eight-Point Algorithm. PAMI, Vol. 19, No.6, pp.580593, 1997.

55. P.H.S. Torr, A.W. Fitzgibbon. Invariant Fitting of Two View Geometry. In PAMI, Vol.26, No.5, pp. 648-650, 2004.

56. H. Akaike. A new look at the statistical model identification. In Proc. Trans Aut Ctrl, Vol. AC-19, Issue.6, pp.716-723, 1974.

57. P.H.S.Torr. An assesment of information criteria for motion model selection. In Proc. CVPR'97, pp. 47-53, 1997.

58. P.H.S.Torr, A.Fitzgibbon, A.Zisserman. Maintaining Multiple Motion Model Hypotheses Over Many Views to Recover Matching and Structure. In Proc. ICCV'04, pp.485-492, 2004.

59. A.Konouchine, V.Gaganov, V.Vezhnevets. Combined Guided Tracking and Matching with Adaptive Track Initialization. In Proc. Graphicon'05, pp.301-304, 2005.

60. Е.Лисицин, А.Конушин, В.Вежневец. Отслеживание точечных особенностей в видеопоследовательностях с изменениями резкости. Труды конференции Graphi-соп'04, с.233-236, Москва, 2004.

61. P. Vivirito, S. Battiato, S. Curti, M. La Cascia, R. Pirrone. Restoration of out of focus images based on circle of confusion estimate. In. Proc. SPIE 47th Annual Meeting. vol.4790, USA, 2002.

62. F.Rooms, A.Pizurica W. Philips. Estimating image blur in the wavelet domain. In. Proc. ACCV'02, pp.210-215, 2002.

63. J.Elder, S. Zucker. Local Scale Control for Edge Detection and Blur Estimation. In. IEEE PAMI, vol. 20, no. 7, pp. 699-716, 1998.

64. S.Zucker, J.Elder. Scale space localization, blur, and contour-based image coding. In Proc. CVPR'96. pp.27-34, 1996.

65. Z. Zhang. A flexible new technique for camera calibration. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.22(l 1), pp. 1330-1334, 2000.

66. R. Hartley. Estimation of Relative Camera Positions for Uncalibrated Cameras. In Proc. ECCV'92, pp.579-587, 1992.

67. D.Nister. An Efficient Solution to the Five-Point Relative Pose Problem. In PAMI, Vol.26, Issue 6, pp. 756-777, 2004.

68. T.Thormahlen, H.Broszio, A.Weissenfeld. Keyframe Selection for Camera Motion and Structure Estimation from Multiple Views. In Proc.ECCV'04, pp.523-535, 2004.

69. M.Ameller, B. Triggs, L. Quan. Camera pose revisited a new linear algorithm. In Proc. ECCV'00, 2000.

70. B.Horn. Relative Orientation. IJCV Vol.4., Issue 1, pp.59-78, 1989.

71. T.Sato, M. Kanbara, N. Yokoya, H. Takemura. Dense 3-D Reconstruction of an Outdoor Scene by Hundreds-baseline Stereo using a Hand-held Video Camera. IJCV, Vol.47, Issues. 1-3, pp.119-129,2002.

72. A.Zisserman, D. Murray, P. A. Beardsley. Sequential updating of projective and af-fine structure from motion. IJCV Vol.23, Issue 3, pp.235-259, 1994.

73. Y-K. Yu, K-H. Wong. M.M-Y. Chang. A Fast Recursive 3D Model Reconstruction Algorithm for Multimedia applications. In Proc. ICPR'04, pp.241-244, 2004.

74. A.Fitzgibbon, A.Zisserman. Automatic Camera Recovery for Closed or Open Image Sequences. In Proc. ECCV'98, pp.311-326, 1998.

75. А.Конушин. Система построения трехмерных моделей реальных объектов по последовательности изображений. Тезисы Ломоносов'05, с.30, 2005.

76. Y. Bayakovski, L. Levkovich-Maslyuk, A. Ignatenko, A. Konushin, D. Timasov, A. Zhirkov, M.Han, I.K.Park. Depth Image-Based representations for static and animated 3D objects. In Proc. ICIP'02 vol.3, pp.25-28, 2002.78. VRML, www.web3d.org

77. ISO/IEC JTC1/SC29/WG11 14496-1, Coding of Audio-Visual Objects: Systems.

78. Curless, M. Levoy. A Volumetric Method for Building Complex Models from Range Images. In Proc. Siggraph'96, pp.303-312, 1996.

79. G. Turk, M. Levoy. Zippered Polygon Meshes from Range Images. In Proc. Sig-graph'94, pp.311-318, 1994.

80. S. Gibson, T.L.J. Howard. Interactive Reconstruction of Virtual Environments from Photographs, with Application to Scene-of Crime Analysis. In Proc. VRCT'00, pp. 4148, 2000.

81. W.A.Hoff, F.W.Hood, R.H.King. An Interactive System for Creating Object Model from Range Data based on Simulated Annealing. In Robotics and Automation, Vol.3, pp. 2559-2564, 1997.

82. D.Marshall, G.Lukacs, R.Martin. Robust Segmentation of Primitives from Range Data in the Presence of Geometric Degeneracy. In PAMI, Vol.23, I. 3, pp.304-314, 2001.

83. M. Callieri, P. Cignoni, R. Scopigno. Reconstructing Textured Meshes from Multiple Range+RGB Maps, In Proc VMW'02, pp. 665 672, 2002.

84. S. Gumustekin, R.W. Hall. Mosaic image generation on a flattened gaussian sphere. In Proc. IEEE Workshop on Applications of Computer Vision, pp. 50-55, 1996.

85. C.Loops, Z.Zhang. Computing Rectifying Homographies for Stereo Vision. In Proc. CVPR'99, pp.125-131, 1999.

86. S. Birchfield, C. Tomasi. Depth discontinuities by pixel-to-pixel stereo. In Proc. ICCV'98, pp. 1073-1080, 1998.

87. A.Ignatenko, A.Konushin. A Framework for Depth Image-Based Modeling and Rendering. In. Proc. Graphicon-2003, pp. 169-172,2003.

88. S. Seitz, K. Kutulakos. Plenoptic image editing. In Proc. ICCV'98, pp. 17-24, 1998.

89. B.M. Oh, M. Chen, J. Dorsey, F. Durand. Image-Based modeling and photo-editing. International Conference on Computer Graphics and Interactive Techniques, pp.433-442, 2001.