Содержание к диссертации
Введение
ГЛАВА 1. Система реконструкции 3-х мерных моделей по набору изображений 10
1.1 Обзор существующих подходов 10
1.2 Предлагаемая система 13
Глава 2. Робастная оценка параметров модели 15
2.1 Постановка задачи 15
2.2 Робастная оценка параметров модели 16
2.2.1 Общая схема оценки параметров на основе случайных выборок 16
2.2.2 Робастное уточнение оценки параметров модели 18
2.3 Обзор существующих алгоритмов на основе случайных выборок 20
2.3.1 Варианты оценочных функции 20
2.3.2 Варианты схемы выборки 21
2.3.3 Модификации схемы оценки модели 23
2.3.4 Другие модификации 23
2.4 Колебания шума в последовательности оценок 24
2.4.1 Задача оценки позы камеры 25
2.4.2 Колебание шума 25
2.5 Предлагаемый алгоритм 26
2.5.1 Оценка максимального правдоподобия 27
2.5.2 Оценка параметров шума в исходных данных 28
2.5.3 Критерий остановки 29
2.5.4 Оценка параметров смеси вероятностей на выборке исходных данных. 30
2.5.5 Локальная оптимизация 30
2.5.6 Полная схема алгоритма AMLESAC 32
2.6 Нелинейная минимизация .7. 32
2.6.1 Оценка параметров смеси по текущей гипотезе 33
2.6.2 Параметры смеси как свободные параметры модели 34
2.7 Применение алгоритма на реальных данных 34
2.8 Применение алгоритма на синтетических данных 37
2.8.1 Тесты на синтетических данных — подгонка линий 38
2.8.2 Оценка позы камеры -тесты на синтетических данных. 39
2.9 Заключение 41
Глава 3. Отслеживание точечных особенностей 42
3.1 Постановка задачи 42
3.1.1 Критерии качества набора следов точечных особенностей 46
3.1.2 Исходные последовательности изображений 47
3.1.3 Подзадачи 47
3.2 Обзор 48
3.2.1 Обнаружение точечных особенностей 48
3.2.2 Виды алгоритмов поиска соответствий 49
3.2.3 Краткий обзор методов сопоставления точечных особенностей 50
3.2.4 Краткий обзор методов отслеживания точечных особенностей 51
3.2.5 Сравнение алгоритмов отслеживания и сопоставления 53
3.2.6 Обзор алгоритмов сегментации ложных следов и соответствий 55
3.2.7 Обзор алгоритмов построения набора следов точечных особенностей 61
3.3 Предлагаемый алгоритм построения набора следов 67
3.3.1 Управляемое слежение 67
3.3.2 Управляемое сопоставление 70
3.3.3 Коррекция следов по точечным особенностям 71
3.3.4 Инициализация следов с разбиением на корзины 73
3.3.5 Выбор ключевых кадров 78
3.3. б Общая структура алгоритма 79
3.3.7 Применение алгоритма на реальных данных 81
3.4 Алгоритм построения следов в видеопоследовательностях с изменениями резкости 83
3.4.1 Предлагаемый алгоритм 83
3.4.2 Определение резкости изображений. 85
3.4.3 Зависимость количества найденных особенностей от резкости изображения 85
3.4.4 Сопоставление особенностей и сегментация ложных 87
3.4.5 Сопоставление особенностей до и после дефектного участка 88
3.4.6 Применение алгоритма на реальных данных 89
3.5 ЗАКЛЮЧЕНИЕ 89
ГЛАВА 4. Определение траектории движения камеры 91
4.1 Постановка задачи 91
4.2 Обзор существующих алгоритмов 93
4.2.1 Общий подход крещению задачи структуры и движения 93
4.2.2 Подзадачи 93
4.2.3 Инициализация движения 94
4.2.4 Инициализация 3-х мерной структуры 94
4.2.5 Выбор ключевых кадров для инициализации движения камеры 95
4.2.6 Определение позы камеры 95
4.2.7 Уточнение структуры 98
4.2.8 Метод связок 98
4.2.9 Алгоритмы определения структуры и движения 99
4.3 Предлагаемый алгоритм 100
4.3.1 Общая схема 100
4.3.2 Разбиение последовательности на сегменты 101
4.3.3 Вычисление траектории движения на сегменте 102
4.3.4 Объединение траектории камеры на сегментах 106
А А Применение предложенного алгоритма на реальных данных 109
4.5 заключение 110
ГЛАВА 5. Построение 3-х мерных моделей 111
5.1 ПОСТАНОВКА ЗАДАЧИ 111
5.1.1 Сеточная модель трехмерного объекта 111
5.1.2 Набор изображений с глубиной 112
5.1.3 Параметрические модели 115
5.1.4 Классификация методов построения 3-х мерных моделей 116
5.2 Подгонка параметрической модели 118
5.2.1 Выделение объектов 119
5.2.2 Краткий обзор существующих методов 120
5.2.3 Подгонка цилиндра 123
5.2.4 Подгонка параллелепипеда 126
5.2.5 Текстурирование модели по изображениям 129
5.3 Алгоритм реконструкции на основе плотного стерео 130
5.5.7 Построение карты глубины 130
5.3.2 Совместный анализ карт глубины 133
5.3.3 Редактирование модели 135
5.4 Результаты применения на реальных данных 140
5.5 Заключение 140
Основные результаты работы 143
Приложение . 144
Свойства перспективной проекции 144
Эпиполярная геометрия 148
Литература
- Предлагаемая система
- Общая схема оценки параметров на основе случайных выборок
- Исходные последовательности изображений
- Инициализация 3-х мерной структуры
Введение к работе
Актуальность работы
Термином «Виртуальная реальность» (ВР) обозначают новые виды компьютерных интерфейсов, нацеленных на создание у пользователя ощущения реальности окружения. Это ощущение вынуждает пользователя взаимодействовать с окружающим миром точно так же, как он бы вел себя в реальности. Типичным примером систем ВР являются тренажеры различных транспортных средств от автомобилей до пилотируемых космических аппаратов, достоверно воспроизводящие ощущения водителя или пилота, позволяющие обучать людей управлению ими, Рис. 1(a). Элементы виртуальной реальности также используются в интерфейсах, называемых «расширенной реальностью», когда в изображения реального мира добавляются синтезированные объекты. Последнее необходимо, например, при архитектурном планировании строительства и реконструкции зданий, Рис. 1(6).
(а) "(б)
Рис. 1 Интерфейсы типа "виртуальная реальность" (а) и "расширенная
реальность" (б)
Достоверная визуализация виртуального мира играет важную роль при создании у пользователя ощущения реальности. Степень реалистичности изображения в настоящее время сильно зависит от точности и качества используемых моделей. В системах расширенной реальности для корректного встраивания виртуальных объектов в изображения необходимо точно определить положение камеры в пространстве, и оценить общее пространственное расположение наблюдаемых объектов.
Наиболее легкодоступным источником информации об объектах реального мира являются фотоизображения, поэтому в последние 15 лет большое внимание уделяется разработке алгоритмов и систем построения моделей реальных объектов по изображениям. Однако доведенные до коммерческого уровня системы, например, Canoma, ImageModeler, PhotoModeler, требуют
точного выделения вершин, ребер и границ объектов на фотоизображениях и сопоставления их вершинам, ребрам и границам выбранной модели простой формы. Этот процесс очень трудоемок, поэтому подобные системы не получили широкого распространения.
В сложившейся ситуации возникла очевидная потребность в автоматизированных системах построения трехмерных моделей по изображениям, не требующих дорогостоящей дополнительной аппаратуры, в которых взаимодействие с пользователем сводится к малому количеству простых операций.
Цель работы
Целью работы является исследование и разработка алгоритмов и методов построения трехмерных компьютерных моделей реальных объектов, позволяющих существенно снизить необходимый объем взаимодействия с пользователем по сравнению с существующими методами, а также разработка системы построения трехмерных моделей для апробации предложенных алгоритмов и методов.
Научная новизна работы
Предложен новый алгоритм робастной оценки параметров моделей, показано его преимущество по точности и устойчивости при решении задачи калибровки камеры по сравнению с существующими аналогичными методами. Разработан новый алгоритм отслеживания точечных особенностей, превосходящий по характеристикам существующие алгоритмы, особенно при применении к задаче вычисления траектории движения камеры. Предложен алгоритм построения следов, устойчивый к перепадам резкости в последовательности изображений. Разработаны новые алгоритмы определения параметров камеры и траектории ее движения.
Предложены новые методы построения моделей для объектов формы типа цилиндр и параллелепипед по набору зашумленных трехмерных точек, лежащих на их поверхности.
Практическая значимость и реализация
Разработаны и доведены до практической реализации методы и алгоритмы вычисления траектории движения фото- и видеокамеры и построения трехмерных объектов по последовательности изображений. Программные реализации описываемых в диссертации методов удовлетворяют всем требованиям и ограничениям, сформулированным при постановке задачи.
На основе разработанных автором алгоритмов разработана система построения моделей 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 научных публикациях. Системы, в которые внедрены разработанные алгоритмы, защищены российскими и международными патентами.
Структура и объем работы
Предлагаемая система
Существующие полностью автоматические подходы к построению 3-х мерных моделей реальных объектов не обеспечивают той надежности реконструкции и не обладают широкими возможностями для корректирования результата, которыми обладает опирающаяся на взаимодействие с пользователем система «Фасад». С другой стороны, избыточный объем взаимодействия затрудняет использование системы типа «Фасад». Поэтому для снижения объема взаимодействия предлагаемая система опирается на автоматическое определение траектории движения камеры и вычисление множества 3-х мерных точек на поверхностях наблюдаемых объектов. Множество 3-х мерных точек затем используется для подгонки параметрических моделей аналогично системе «Фасад» и алгоритмам, предложенным в работах [5].[6]. Однако вместо точного выделения точек и ребер на изображениях объекта, пользователю достаточно выделить на нескольких исходных изображениях прямоугольной рамкой области, соответствующие изображению объекта. 3-х мерные точки, проецирующиеся в выделенные области, считаются лежащими на поверхности моделируемого объекта. Поскольку на самом деле часть из выделенных точек лежит на поверхностях других объектов, разработаны алгоритмы подгонки параметрических моделей типа «шестигранник», «параллелепипед» и «цилиндр», устойчивые к присутствию не принадлежащих объекту точек.
Алгоритмам автоматического определения траектории движения камеры посвящено большое количество работ, к наиболее известным среди которых относятся [16].[17].[18]. Большой интерес к таким алгоритмам объясняется актуальностью их применения при создании компьютерных спецэффектов в кинофильмах [19].[20]. Также эти алгоритмы используются в некоторых исследовательских системах построения 3-х мерных моделей на основе методов плотного стерео [21].
Все алгоритмы определения траектории движения камеры опираются на автоматическое выделение точеных особенностей в исходных изображениях и вычисление соответствующих им трехмерных точек на поверхностях объектов наблюдаемой сцены. Общая принципиальная схема работы таких алгоритмов приводится в работе Полифая [21] и может быть сформулирована следующим образом: 1. Выделение точечных особенностей в исходных изображениях 2. Согласование точечных особенностей между изображениями 3. Вычисление 3-х мерных точек и взаимное ориентирование камер в пространстве в соответствии с точечными особенностями, найденными на изображениях
Множество вычисленных 3-х мерных точек используется для подгонки параметрических моделей, а информация о калибровке камер, с которых были получены исходные изображения, используется для построения текстуры моделей. Таким образом, смысл оценки трехмерных точек и взаимного ориентирования камер заключается в подготовке исходных данных для алгоритмов вычисления формы поверхностей моделей. Решение задачи согласования точечных особенностей в свою очередь подготавливает исходные данные для взаимного ориентирования камер. Блок-схема предлагаемой системы построения моделей по набору изображений приводится на Рис. 2.
Одной из ключевых задач машинного зрения является сопоставление информации, содержащейся в изображении, с некоторой математической моделью. Общую задачу оценки параметров модели по имеющимся данным можно записать следующим образом. Нужно определить вектор параметров в, такой чтобы: где x = {x,],i = i..N - набор точек исходных данных, р{Х,в) задает исследуемую математическую модель. Классическим примером задачи оценки параметров является аппроксимация набора точек прямой линией. В таком случае = { = і.,лг- это набор точек, F(X,&) - уравнение прямой, в - параметры прямой.
Для оценки параметров моделей в математике традиционно применяются такие методы как метод максимального правдоподобия или метод максимизации апостериорной вероятности. При этом исходят из следующего предположения об исследуемой модели и исходных данных: все данные х = {х,} порождены исследуемой моделью и зашумлены некоторой помехой є, математическое ожидание которой м{є) = о, а дисперсия D(E) = ог,(г = const. Однако это предположение зачастую не верно.
Исходные данные х могут быть загрязнены, т.е. помимо точек, порожденных исследуемой моделью, в данных содержатся загрязняющие точки, порожденные ошибками измерений, никак не зависящими от исследуемой модели. Загрязняющие точки называются выбросами (outliers). Доля порожденных исследуемой моделью данных обозначается у є [0,1]. Результат оценки параметров модели с помощью метода максимального правдоподобия без специального учета загрязняющих данных может оказаться сколь угодно далек от реальных параметров модели. Метод оценки параметров модели по набору загрязненных исходных данных называется робастным методом оценки. Существует целая группа робастных методов оценки параметров: М-оценки (M-estimators) [22], схемы голосования (например, преобразование Хафа [23]), метод наименьшей медианы квадратов (Least Median of Squares) [24], а также семейство методов на основе случайных выборок (RANSAC) [25].
Такие робастные методы как М-оценки или метод наименьшей медианы квадратов опираются на методы нелинейной минимизации или итеративные процедуры, требующие довольно точного начального приближения параметров целевой модели. Если такого приближения нет, или его точность недостаточна, то наличие даже небольшой доли загрязнения в исходных данных делает невозможным применение подобных методов. Схемы голосования экспоненциально зависят от количества оцениваемых параметров, поэтому обладают очень низкой эффективностью при оценке моделей высокой размерности.
Доля загрязняющих выбросов может составлять половину и более общего объема выборки при решении многих задач машинного зрения. Высокая размерность исследуемых моделей затрудняет использование методов голосования. Обычно нет никакой априорной информации о значении параметров модели, которая могла бы использоваться для вычисления начального приближения итеративных методов. Поэтому для оценки различных моделей в алгоритмах 3-х мерной реконструкции и калибровки камеры обычно применяются методы на основе случайных выборок,
Общая схема оценки параметров на основе случайных выборок
Пусть исходные данные х = {х,),ы\..ы состоят из N точек размерности s, у e[o,i] из которых порождены исследуемой моделью F(x,0). Для того, чтобы оценить параметры модели 9, необходимо определить, какие точки из х являются загрязняю вдими выбросами, а какие нет. Однако в общем случае не существует способа определить заранее, является ли данная точка выбросом. В 1981 году Фишером и Бо-лесом был предложен алгоритм RANdora SAmpling Consensus (RANSAC), в котором эта проблема решается путем случайного перебора некоторого количества выборок из исходных данных. По каждой выборке оцениваются параметры модели в. Предполагается, что значение функции р(х,в) достигает своего минимума на в оцененной по выборке, не содержащей выбросов. Каждая выборка строится случайным образом, т.е. из набора исходных данных последовательно выбирается нужное количество точек. Каждая из точек набора исходных данных берется с равной вероятностью. Для максимизации вероятности построения выборки без выбросов, размер выборки берется минимально необходимым для оценки параметров модели. Пусть минимальный размер выборки равен Н. Алгоритм RANSAC состоит из М повторений следующего цикла: Построение выборки st с X из Я точек; Построение гипотезы на вк основе выборки st; Оценка степени согласия Rt гипотезы екш всех исходных данных х-,
После построения и оценки всех М гипотез, из них выбирается гипотеза с наи лучшей оценкой я = max(/?t) которая и принимается за результат робастной оценки. Для каждой доли выбросов у є [о,1] можно вычислить такое количество итераций алгоритма М, что среди М построенных случайным образом выборок размера Н, с вероятностью Р есть выборка, не содержащая выбросов [22].
Принципиальным и неустранимым недостатком любого алгоритма, основанного на этой схеме, является построение гипотезы только по выборке исходных данных, а не по всем исходным данным без загрязнения. Поскольку размер этой выборки обычно выбирается минимально необходимым, точность оценки оказывается низкой. Именно поэтому необходимо дальнейшее уточнение параметров модели по всем исходным данным.
Помимо этого, существует небольшая вероятность, что за все М повторений не будет получено ни одной выборки без выбросов. Поэтому применение алгоритма RANSAC не гарантирует получение желаемого результата. Он обеспечивается с некоторой, пусть и высокой вероятностью.
После того, как получено начальное приближение значений параметров интересующей модели, они могут быть уточнены с использованием как можно большей доли исходных данных.
Уточнение обычно производится с помощью одного из методов нелинейной многомерной оптимизации. В качестве минимизируемой целевой функции обычно используется сумма квадратов отклонений точек исходных данных от своих оценок максимального правдоподобия с учетом текущей модели, Л ,в)-ї,-х((, і где сумма берется по всем точкам исходного набора после удаления из него загрязняющих выбросов.
Эффективность нелинейной оптимизации во многом зависит от выбранной параметризации модели. Эта параметризация может не совпадать с той, которая использовалась на этапе робастной оценки модели алгоритмом на основе случайных выборок. Оптимальная параметризация должна удовлетворять двум требованиям -согласованности и минимальности. Условие минимальности заключается в том, что параметризация должна состоять из минимально необходимого для описания модели числа параметров, т.е. количество параметров должно равняться числу степеней свободы модели. Требование согласованности состоит в том, чтобы любой набор значений параметров определял корректную, т.е. существующую модель. Выполнение условия согласованности позволяет избавиться от проверки существования модели с таким набором параметров. Выполнение условия минимальности повышает эффективность оптимизации за счет снижения размерности пространства поиска.
Исходные последовательности изображений
Пусть {х }и {х?} - два набора точечных особенностей на изображениях /, и /2. Каждая точечная особенность определяется только своим окном поиска, поэтому в изображениях высокодетализированных сцен, особенно с повторяющейся текстурой, существует множество особенностей с очень похожими по любой мере окнами поиска. Поэтому при непосредственном сравнении точечных особенностей обоих изображений, особенности с наиболее похожими окнами поисками зачастую не соответствуют одной и той же точке сцены. Для уменьшения влияния этой проблемы необходимо накладывать на соответствия дополнительные ограничения. В качестве подобных ограничений чаще всего используются два: Ограничение на смещение особенности между кадрами Эпиполярное ограничение
Поскольку в качестве исходных данных используются видеопоследовательности, то смещение особенности между кадрами обычно меньше нескольких десятков пикселей. В качестве ограничения задается порог Т на расстояние между точками разных кадров соответствий. Обычно порог Т выбирается равным порядка 50 пикселей. Использование эпиполярного ограничения совместно с порогом позволяет значительно сузить количество проверяемых соответствий. Однако вычислить эпиполярное ограничение можно только по уже известному набору соответствий.
С учетом вышеприведенных соображений, общий алгоритм поиска сопоставлений можно сформулировать следующим образом [34]: 1) Для каждой точечной особенности х, из /, a) Составить набор всевозможных соответствий (х],х2), где х2 . особенности из кадра /2, таких что , - х21 Т b) Вычислить меру близости Sy соответствий ( ДГ-, Xj ) c) Выбрать из всех соответствий одно или несколько, удовлетворяющих некоторым ограничениям, называемых предполагаемыми соответствиями (putative correspondences) 2) Робастным методом оценить эпиполярное ограничение в виде фундаментальной матрицы по всем построенным соответствиям 3) Отбросить соответствия, которые не удовлетворяют эпиполярному ограничению 4) Повторить этапы 1-3 с учетом эпиполярного ограничения на этапе 1
После этапа 3 нам уже известно эпиполярное ограничение. Поскольку на этапе 4 среди всех потенциальных соответствий выбираются и проверяются только такие, которые удовлетворяют эпиполярному ограничению, то этот этап называется «направленным поиском соответствий» (guided matching) или пересчетом соответствий (rematching).
Различные алгоритмы поиска соответствий отличаются используемой мерой близости изображений для сравнения окон поиска и методом выбора предполагаемых соответствий на этапе 1(c).
В качестве меры близости изображений при сопоставлении особенностей наиболее широко используется нормализованные кросс-корреляция и сумма квадратов отклонений. Нормализация позволяет снизить влияние изменения яркости и контраста окна поиска особенности при изменении освещенности от кадра к кадру. Исследовалась применимость других известных мер, таких как мера %г ь Дивергенция Джеффри (Jeffrey Divergence) [46], однако они обеспечивают меньшую долю корректных соответствий среди всех найденных.
Простейший метод выбора предполагаемых соответствий заключается в выборе соответствия, особенности которого наиболее близки друг к другу по выбранной мере. Более сложные методы опираются на различные эвристики [34]. Например, на свойство уникальности, согласно которому каждой точечной особенности на одном кадре может соответствовать только одна точечная особенность на другом.
Все современные алгоритмы слежения за особенностями опираются на работу 1981 году Лукаса и Канаде [47]. В 1991 году этот алгоритм был переформулирован в работе [48], которая стала основой большинства последующих алгоритмов слежения, В алгоритме Лукаса-Канаде в качестве модели движения пикселей из окна поиска особенностей используется параллельный перенос. Пусть х - точечная особенность в изображении i,.. Производится итеративный поиск такого вектора переноса /, что что сумма квадратов разностей окон изображений /, и 12 с центрами в х и х +1 достигается минимума: = Х[Л( + )-Л( )Г
В отсутствии априорной информации, начальное значение /0 выбирается равным нулю. Вычисление продолжаются до тех пор, пока изменение г, не станет меньше заданного порога или выйдет за заданную границу.
В работе [49] в качестве модели движения пикселей из окрестности точечной особенности рассматривается не простой сдвиг, а афинное преобразование, которое более точно аппроксимирует преобразование окрестности особенности между кадрами. Задача слежения за особенностью сводится к проблеме определения параметров аффинного преобразования, на которой достигается минимум функции ошибки: S = \\[1г (Ах, +d)-Ix [хх )f v( i )dxy, w где хг =Ах{ +d, Лє9ї2 2,/є912 - афинное преобразование, w(x) - весовая функция, W - окно особенности.
В алгоритме Джин-Фаваро-Соато [50] афинная модель была дополнена линейным преобразованием освещенности окна поиска, что позволило учесть изменения освещенности от кадра к кадру.
Особенностью всех алгоритмов, основанных на алгоритме Лукаса-Канаде, является возможность использовать любое начальное приближение t0. В отсутствие априорной информации, вектор /0 обычно берется равным нулю.
В работе [51] предложен многомасштабный вариант алгоритма Лукаса-Канаде. Строится многомасштабная пирамида изображений. На первом шаге поиск производится в изображениях наименьшего разрешения. Полученное значение используется как начальное приближения для поиска в изображениях с большим разрешением.
Инициализация 3-х мерной структуры
Кадры 1т4 и 1т, исходной последовательности, которые были выбраны для инициализации структуры и движения, называются ключевыми. От выбора ключевых кадров зависит точность оценки структуры и движения. Точность оценки координат 3-х мерной точки X тем выше, чем ближе к прямому угол между лучами
Окт),0;т, , исходящими из центров камер Ок,Ог Если расстояние между оптическими центрами Ok,Ot мало, то мал и угол для всех соответствий (т ,т ). С другой стороны, чем больше расстояние Ок,0,, тем меньше соответствий (mf,m ) определяется между кадрами (ImA,Im,), а их количество влияет на точность оценки движения камеры. В качестве ключевых кадров выбирается пара (Irat,Im,), на которой обеспечивается оптимальный баланс обоих параметров.
Расстояние между оптическими центрами камер невозможно вычислить до того, как будет определена траектория движения камеры. Однако его можно оценить косвенно с помощью эпиполярной геометрии. Если расстояние р(Ок,0,) велико, тогда соответствия (m ,m ) лучше согласуются с фундаментельной матрицей, нежели чем с томографией. На этом принципе основаны критерии Полифая [21] и Гибсона [18]. Алгоритм Тормаллена [68] оценивает непосредственно погрешность вычисления 3-х мерных точек, но требует инициализации структуры и движения для каждой пары кадров, поэтому значительно уступает другим алгоритмам по скорости вычисления.
Пусть X {Х ,1 = 1,...,N - набор 3-х мерных точек, м = {т;},; = 1,...,лг - их проекции на изображение Im . Задачей определения позы камеры называется вычисле ниє такой матрицы Р, 4ToJP = argmin( ]pCmf,/ )2). Если известна матрица внут 1=1 ренней калибровки К, тогда задача определения позы камеры сводится к оценке матрицы внешней калибровки камеры С, такой что, р = к Е с, где Е- матрица 3 4 с единицами на главной диагонали.
Перспективная проекция задает отношение между 3-х мерной точкой Хі в пространстве и ее проекцией на изображение m,: т, = РХ,
Каждое известное соответствие (mi5X() позволяет составить два однородных линейных уравнения на параметры матрицы перспективной проекции Р. Поскольку матрица Р имеет размерность 3 на 4, то 6 известных соответствий (mi,Xj) достаточно, чтобы решить полученную систему с помощью метода наименьших квадратов. Поэтому данный метод и получил название линейного 6-й точечного.
Матрицу перспективной проекции можно факторизовать в произведение матриц К, Ей С[31]. Если матрица внутренней калибровки К известна, тогда можно использовать следующий алгоритм оценки позы камеры: Найти mi, наретинальной плоскости камеры как т. =К хт, Вычислить матрицу Р по набору соответствий (т,-\ЛТ,) с помощью ли нейного 6-й точечного метода Найти ортогональную матрицу С, ближайшую к матрице Р 0 0 0 Если известно более 6 соответствий {тпХ,), то все они могут быть использованы для составления системы линейных уравнений. Поэтому линейный метод широко используется для оценки позы камеры по всем точкам, после того, как были сегментированы ложные соответствия.
Этот метод основан на теореме косинусов [69]. Поскольку нам известны трехмерные точки {Х}}, то известно и расстояние между любой парой (Х„Х;). С помощью известной матрицы внутренней калибровки К для каждой точки т-можно найти соответствующую ей точку mt- на ретинальной плоскости изображения. По 2-м точкам т/ и т. вычисляется косинус угла m?Om}\ По 4-м известным соответствиям (m Xj) можно составить и решить линейную систему уравнений на длины отрезков [OXt]. Продлив каждый луч От/на расстояние [ОХ,] можно получить оценку Х\ в системе координат, связанной с камерой. С помощью алгоритма Хорна [70] можно найти матрицу С евклидова преобразования системы координат, переводящего множество точек {Xj} в{Х,}. Матрица С которая и будет являться матрицей внешней калибровки камеры.
Среди всех соответствий {тпХ1} которые используются для оценки позы камеры, часть может быть построена по лишь локально-корректным следам. Такие соответствия являются загрязнением, поэтому при оценке позы камеры необходимо использование робастных алгоритмов. Наиболее широко для этой задачи применяются алгоритмы на основе случайных выборок, как подробно рассмотрено в Главе 2. После того, как с помощью робастного алгоритма будет получено начальное приближение позы камеры и сегментированы ложные соответствия, поза камеры уточняется с помощью нелинейной минимизации или линейного алгоритма.
