Построение 3D модели по неупорядоченной коллекции изображений

Чепрасов Дмитрий Евгеньевич

Построение 3D модели по неупорядоченной коллекции изображений

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

Общественные науки в целом

Диссертации

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d368b5f1be77c40d591ff

UUID: 9edc5143-70b7-4ae1-88dc-529b6c8d08bf

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 425

Чепрасов Дмитрий Евгеньевич

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 5318776 bytes

Поделиться работой

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КАФЕДРА КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ И СИСТЕМ Чепрасов Дмитрий Евгеньевич Магистерская диссертация Построение 3D модели по неупорядоченной коллекции изображений Направление 02.04.02 Фундаментальная информатика и информационные технологии Магистерская программа «Автоматизация научных вычислений» Научный руководитель, кандидат физ.-мат. наук, доцент Погожев С. В. Санкт-Петербург

2016 2

Содержание Введение...................................................................................................................3 Постановка задачи...................................................................................................5 Обзор литературы....................................................................................................7 Глава 1. Структура системы реконструкции трехмерных сцен........................13 Глава 2. Восстановление трехмерных сцен........................................................15 2.1. Восстановление трехмерных сцен по коллекции изображений методом факторизации матриц................................................................................15 2.1.1. Локальные особенности изображений.......................................... 15 2.1.2. Восстановление 3D координат локальных особенностей...........16 2.1.3. Математический вывод приближений...........................................19 2.1.4. Метод факторизации матриц..........................................................23 2.1.5. Формирование плотной матрицы измерений...............................27 2.2. Восстановление структуры трехмерных сцен из одного изображения по закраске...................................................................................................... 28 2.3. Комбинирование подходов........................................................................ 31 Глава 3. Результаты работы алгоритма................................................................ 32 Заключение.............................................................................................................37 Список литературы................................................................................................38 Приложение............................................................................................................43

Введение Восстановление трехмерной модели сцены по набору изображений – классическая задача в компьютерном зрении, в которой трехмерная модель сцены должна быть восстановлена из набора фотографий этой сцены. Развитие виртуальной реальности, систем управления транспортными средствами [1–3], визуализации на основе анализа изображений, медицинской промышленности, а также других областей, требующих построения трехмерных моделей, привело к увеличению внимания к этой области. Наибольшим интересом пользуются случаи, в которых положение камер и их внутренние параметры не известны и/или могут меняться с течением времени. Так, например, в системах активного зрения калибровочные параметры могут меняться во время работы системы. Конечно, существуют лазерные 3D сканеры, позволяющие создавать очень точную трехмерную модель сцены, но им свойственно множество недостатков. В их числе очень высокая стоимость подобной аппаратуры, ве сьма ограниченные размеры сканируемых объектов, низкая производительность и многое другое. Более того, такие устройства не совсем безопасны для человека, в частности для глаз. Известны также успешные результаты применения стереоскопического зрения, когда камеры, осуществляющие съемку, калибруются таким образом, что их внутренние параметры известны, а внешние определены относительно некоторой глобальной системы отсчета. Однако, такой подход не возможен, когда калибровочные параметры с течением времени меняются (это имеет место быть, например, в системах активного зрения). Существует огромное количество методов, являющихся частью одной зачачи под названием «восстановление трехмерной сцены из …», позволяющих восстановить 3 D модель, но каждый из них ограничен своей областью использования и не применим для восстановления общих сцен. Все эти методы принято делить на классы по типу данных, которые используются 4

для реконструкции. Среди таких классов основными являются:  реконструкция сцены из одного изображения по закраске;  реконструкция сцены по коллекции изображений, полученной с камеры, зафиксированной в одном положении, при фокусировке на различные объекты сцены;  реконструкция сцены из стереопары изображений;  реконструкция сцены по коллекции изображений, снятых с различных позиций и в разное время;  реконструкция сцены по коллекции изображений, полученной с камеры, зафиксированной в одном положении, при этом каждое изображение снято с разной степенью оптического увеличения. Основные идеи данных подходов будут подробно рассмотрены в разделе «Обзор литературы». В основной части будут описаны алгоритмы, используемые в данной работе для восстановления общих 3D сцены, а также будут приведены результаты работы описанных методов. 5

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

Рис. 1. Набор изображений сцены с чайной баночкой 7

Обзор литературы В этой главе, мы предоставляем краткий обзор существующих подходов к решению задачи реконструкции сцены в литературе. Алгоритмы восстановления структуры сцены по закраске Алгоритмы этого класса считаются самыми первыми алгоритмами реконструкции 3D сцены. Часть из них были разработаны еще в 70-х годах [1]. Несмотря на это они продолжают оставаться актуальными и в настоящее время. Для восстановления трехмерной сцены данными алгоритмам достаточно всего лишь одного полутонового изображения реальной сцены. В их основе лежит тот факт, что в каждой точке поверхностей с ламбертовым законом рассеивания яркость остается неизменной при изменении местоположения наблюдателя и к тому же пропорциональна значению косинуса угла между направлением на источник освещения и нормалью к поверхности. Основная проблема применения данных алгоритмов на практике состоит в том, что количество неизвестных в ней больше, чем исходных данных, поэтому для ее регуляризации применяются разного рода ограничения на множество возможных решений. Кроме того, существуют методы, благодаря которым в ряде случаев возможно применение алгоритмов данного класса к сценам с неодинаковым альбедо [2]. Подход заключается в том, что на первоначальном этапе для каждой точки изображения производится оценка величины альбедо, после этого изображение сегментируется по значению альбедо, а для каждого пикселя исходного изображения значение альбедо делится на среднее альбедо точек того же сегмента. После чего используется алгоритм реконструкции сцены для постоянного альбедо, значение которого равно единице. Подробный обзор существующих алгоритмов, принадлежащих классу реконструкции сцен по закраске предложен в [3], из них, самым простым 8

является алгоритм Пентланда, описанный в [4]. В [5] приведен сравнительный анализ эффективности алгоритмов описанных в [3]. Стоит заметить, что помимо алгоритмов реконструкции поверхностей с ламбертовским законом рассеяния, имеются также методы реконструкции поверхностей с другими законами рассеяния света [6]. Алгоритмы данного класса могут быть достаточно полезны при реконструкции сложных сцен. Пусть, например, на фотографии изображена некоторая сцена, на который присутствует объект со слабо выраженной текстурой, например, бетонная стена сложной формы. Алгоритмы реконструкции по закраске, очевидно, не способны восстановить всю сцену. К тому же, очевидно, что восстановить форму бетонной стены посредством алгоритмов других классов также не представляется возможным, так как она не имеет достаточного количества особых точек. Поэтому, можно общую сцену реконструировать каким-либо алгоритмом типа «Shape from Stereo» или «Shape from motion», а бетонный объект выделить из изображения, восстановить его форму посредством алгоритма реконструкции по закраске и совместить реконструированную сцену и бетонный объект в общую 3D модель реальной сцены. Алгоритмы восстановления структуры сцены по фокусировке Данные алгоритмы построения модели сцены основаны на том, что глубина резкости оптических систем конечна. При управлении параметрами фокусировки камеры можно достичь резкого изображения различных точек объекта, а уже зная параметры фокусировки камеры при которых достигается нужная резкозть можно оценить глубину этих точек. В [7] описан алгоритм реконструкции сцены по фокусировке, обладающий большой точностью. В работе исследован порядок точности алгоритма, а также методические погрешности, однако, авторы акцентируют внимание на том, что сходимость данного метода не доказана, что, вообще говоря, является типичным для подобных задач. 9

Алгоритмы восстановления структуры сцены по стереопаре изображений Алгоритмы реконструкции сцены, основанные на обработке стереоизображений подразделяются на следующие типы: основанные на поиске и обработке особых точек, основанные на обработке областей [8], а также смешанные алгоритмы [9–11]. Методы первого типа, осуществляют поиск локальных особенностей, а после этого устанавливают между ними соответствия: для каждой особой точки вычисляется коэффициент корреляции в некоторой ее окрестности и потом сравнивается с коэффициентами кореляции особенностей на другом изображении. После этого, используя метод триангуляции, находится расстояние до точек (для которых соответствие было найдено). Вычисление расстояния до оставшихся точек осуществляется посредством интерполяции. Алгоритмы второго типа основаны на вычислении расстояния до всех точек изображения. Среди смешанных методов наибольший интерес представляет алгоритм Бернарда [9], основная идея которого состоит в построении карты смещения, которая строится на основе вычисления смещения в каждой точке изображения. Однако этот алгоритм не эффективен при недостаточном количестве информации о пространственной структуре. В [12] описан метод, который позволяет объединить алгоритмы восстановления по закраске и по стереопаре для более точного обнаружения ребер, границ и других крупных деталей. Алгоритмы восстановления структуры сцены по набору изображений, полученных при движении наблюдателя В настоящее время, алгоритмы этого класса пользуются наибольшей популярностью [13–15]. Здесь предполагается, что изображения, по которым реконструируется сцена, сняты с различных позиций и возможно в разное 10

время, при этом часто предполагается, что неизвестны положения камеры и неизвестны или постоянно меняются ее внутренние параметры. Общий процесс реконструкции модели сцены в рамках этой группы алгоритмов состоит из двух этапов: 1) Поиск особых точек: на изображениях осуществляется поиск локальных особенностей в виде точек, линий, а также ищутся соответствия между найденными о собенно стями на 2) последовательности изображений. Вычисление структуры: д л я н а й д е н н ы х с о от ве т с т в и й вычисляются их позиции в трехмерном пространстве по принципу триангуляции. На полученный объект натягивается поверхность. Входными данными для алгоритмов этого типа являются координаты особых точек на изображениях и особые индентификаторы соответствующие им, благодаря которым каждую особую точку можно отличить от дугих, причем, на всей коллекции изображений каждой точке, являющейсяся проекцией некоторой точки на трехмерной сцене должен соответствовать одинаковый индентификатор. Непосредственно с изображениями алгоритмы данной группы не работают. В последнее время, большое внимание исследователей привлекают методы, в основе которых лежит идея факторизации матриц [16–19]. В [16], [18] подробно описана основная идея таких методов. В [17] рассматривается случай, когда на сцене присутствует несколько, возможно движущихся, объектов, а также предлагается метод подсчета и разделения таких объектов. В [19] описана модификация для приложений реального времени. Модель строится по имеющимся данным, а при поступлении новых данных модель уточняется. При таком подходе не обязательно иметь все изображения сцены на момент начала построения трехмерной модели и на практике требуется меньше вычислительных ресурсов. Однако, в этом случае на каждой итерации дополнения и уточнения модели сцены будет происходить накопление погрешностей. Эта проблема пока никак не решена. 11

Выводы После изучения существующих подходов к решению задачи реконструкции трехмерных сцен можно сделать следующий вывод: данная задача в общем случае не может быть решена в рамках одного алгоритма или подхода, так как все они имеют ограничения условий применения. Отсюда непременно возникает необходимость создания интегрированной системы, которая могла бы сочетать в себе сильные стороны различных подходов, за счет чего компенсировать слабые стороны каждого из подхода в отдельности, путем выбора наиболее подходящих алгоритмов реконструкции для различных участков сложной сцены. В качестве основы такой системы было принято решение взять алгоритмы реконструкции сцены по набору изображений, полученных при движении наблюдателя, основанные на декомпозиции матриц. Причиной такого выбора стали следующие достоинства алгоритмов этого класса: 1. невысокая сложность и объем обрабатываемых данных, полученных из значительного числа изображений; 2. согласованная обработка данных; 3. позволяют достраивать и уточнять ране созданную модель при получении новых данных о сцене; 4. высокая точность построения модели трехмерной сцены; Другие подходы могут интегрироваться в такую систему различными способами. Методы реконструкции, основанные на декомпозиции матриц восстанавливают пространственные координаты только для особых точек сцены, таким образом, имеет место задача интерполяции – на основе найденных пространственных координат необходимо уметь построить поверхности сцены между найденными точками. Так алгоритмы реконструкции по фокусировке хорошо работают с поверхностями, у которых текстура зависит от масштаба. Для поверхностей, текстура которых слабо 12

различима, хорошо подойдут алгоритмы реконструкции по закраске. Отсюда вытекают как минимум два подхода для интегрирования остальных алгоритмов реконструкции 3D сцены: 1) Задача интерполяции может быть заменена на задачу восстановления структуры части сцены, границы которой могут быть получены из ранее полученной модели. Для объектов, которые находятся близко к камере, можно выполнить разделение по признаку удаленности и для них использовать наилучший подход для реконструкции. Выделение можно также произвести для движущихся объектов, используя дефокусировку с совмещенной камерой [20], это тоже облегчит 2) обработку трэкером особых точек выделенных областей [21]. Также можно получить начальное приближение поверхностей сцены, а потом его уточнять описанными выше методами. Для выбора метода уточнения можно произвести анализ текстур и оценку расстояния от камер до нужной части сцены. К областям, текстура которых слабо выражена, могут быть применены алгоритмами реконструкции по закраске, для неоднородных областей – алгоритмы [22]. На практике построение такого начального приближения серьезно увеличивает скорость сходимости. 13

Глава 1. Структура системы реконструкции трехмерных сцен Как уже было сказано система реконструкции трехмерных сцен общего вида должна быть построена так, чтобы была возможность интегрировать в нее различные алгоритмы реконструкции 3D сцен. За основу были взяты алгоритмы основанные на декомпозиции матриц [16], [17], [23]. Результатом работы этих алгоритмов является множество трехмерных точек сцены. По этим точкам можно построить полигональную сетку [24], [25], [26], кроме того могут быть вычислены координаты и ориентации камер. Это позволяет уточнять и дополнять модель, используя другие подходы. Схема системы реконструкции 3D сцены представлена на рис. 2, компоненты, которые на текущий момент реализованы отмечены рамкой. Рис. 2. Схема системы реконструкции трехмерной сцены Стоит заметить, что алгоритмы основанные на декомпозиции матриц требуют наличия всех отслеживаемых особых точек на всех изображениях 14

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

Глава 2. Восстановление трехмерных сцен 2.1. Восстановление трехмерных сцен по коллекции изображений методом факторизации матриц 2.1.1. Локальные особенности изображений Обнаружение особых точек является первым крупным шагом на пути к созданию модели сцены и оценки движения камеры. Основными особенностями, детектируемыми на изображениях, являются точки и линии. Сразу стоит заметить, что особой точкой(линией) будем называть точку (линию), которая вместе со своей окрестностью отличается от любой соседней точки с ее окрестностью и вероятно будет найдена на другом изображении этого же объекта. Детектор – метод, который осуществляет п о и с к локальным особенностей изображения. Вообще говоря, детектор особенностей должен обладать инвариантностью к преобразованиям изображения для более точного нахождения особенностей. Детекторы особенностей принято делить на категории по типу особенностей, которые они ищут. К примеру, детекторы на контурной основе находят контуры на изображении и ищут точки, обладающие особыми свойствами, например, стыки, концы контуров или точки, в которых кривизна кривой контура приобретает максимальное значение [27]. Детекторы на основе интенсивности находят особые точки, путем изучения изменения интенсивности. Таким детектором является, к примеру, хорошо известный детектор уголков Харриса [28], он частично инвариантен к повороту и к изменению яркости, но не инвариантен к масштабу. В целях создания инвариантного к масштабированию детектора был предложен механизм детектирования блобов. Блобами называют каплевидные окрестности с особой точкой в центре. Большинство таких 16

детекторов связаны с автокорреляционной матрицей [28], [29], [30]. Однако более новые детекторы, такие как SIFT [31], используют фильтр лапласиан гауссианов (LoG) или разности гауссианов (DoG). 2.1.2. Восстановление 3D координат локальных особенностей Следующая задача в процессе построения модели сцены – восстановление структуры, учитывая найденные на предыдущем шаге соответствия особенностей в качестве входа в систему. Информация о структуре представляется в виде пространственных координат, полученных из особенностей изображений. Пусть имеется P F особых точек, принадлежащих объектам сцены на изображениях (см. рис. 3). Рис. 3. Задача реконструкции сцены для F камер. Запишем уравнения, которые отображают связь между координатами точки на изображении, координатами точки в мировой системе координат и фокусным расстоянием камеры (см. рис. 4): { xfp ~ u = fp , z fp l f y fp ~ v = fp . z fp l f (2.1.1) Данную систему можно переписать, перейдя к произвольной системе 17

координат в векторной форме: { i⃗ (⃗s −t⃗ ) ~ u fp=l f f p f , z fp ⃗ ~v =l j f (⃗s p −t⃗ f ) , fp f z fp z fp =k f ( ⃗s p−t⃗ f ) . (2.1.2) Эти уравнения – основа решения задачи реконструкции структуры сцены, рассмотрим их подробнее. У нас имеется P точек на F изображениях, у каждой точки две координаты, соответственно всего 2 FP известных величин. Неизвестны вектора s p ,t f , l f , также неизвестны вектора систем координат связанных с изображениями, на которые действуют ограничения ортонормированности: Рис. 4. Связь МСК и систем координат связанных с изображениями. { ( i⃗ f , i⃗ f )=1, ( ⃗j f , ⃗j f )=1 , ( i⃗ f , ⃗j f )=0, (2.1.3) ⃗k f =[ i⃗ f , ⃗j f ] . Итого 3 P+3 F+ F+(6−3)F=3 P+7 F неизвестных величин. Это значение вообще говоря может быть уменьшено, если, например, внутренние параметры камеры известны. Например, при постоянном фокусном 18

расстоянии число неизвестных уменьшается на F−1 . Система (2.1.2) может быть решена при помощи МНК относительно имеющихся неизвестных, если 2 FP>3 P+7 F . Это ограничение справедливо при большом количестве изображений и найденых особых точек. Очевидно, что реконструкция сцены осуществляется с точностью до масштаба. Для реконструкции сцены с сохранением масштаба необходимо знать расстояние между любыми двумя точками сцены или же парой камер. Такой подход используется в алгоритмах реконструкции по стереопаре. Съемка производится двумя камерами одновременно, при этом внутренние параметры камер и их ориентация полностью идеентичны, а также известно расстояние между камерами. При получении изображений при помощи цифровых камер размер пикселя вообще говоря не известен, поэтому имеет смысл перейти к величинам, которые можно измерить – к координатам пикселя. Таким образом уравнение (2.1.1) может быть записано в виде: { x l a a ~ ufp e = fp ef , ~ u fp N z fp ~ u fp N ~v a = y fp l f a . fp ~ e v N z ~v e N fp fp (2.1.4) fp Здесь a>0 – масштабный коэффициент, ~uefp , ~v efp – размеры одного элемента фотоматрицы в метрических единицах, N =max (N x , N y ), N x , N y – разрешение по x и y . При переходе к новым переменным: { ~ ufp nx , e =a ~ N ufp v fp n a ~ v fp = =a y , e ~ N v fp N u fp= здесь α−¿ a N (2.1.5) lf 1 gf =a e = , ~ ufp N γ ~ue α= fpe , ~v fp соотношение сторон фотоэлемента, n x , n y−¿ координаты 19

пикселя (расстояние от центра кадра), γ=tg n x −a a ∈[ , ] , N 2 2 n y −a a ∈[ , ] , N 2 2 α max ,α max −¿ максимальный угол обзора камеры. Система уравнений 2 (2.1.4) теперь может быть переписа в виде: { x fp , z fp y v fp =α gf fp . z fp ufp =g f (2.1.6) Примем α=1 . Значение нормировочного коэффициента α влияет только на устойчивость, а также точность численных методов. Те п е р ь о с у щ е с т в и м п е р е ход к М С К . В н е й радиус-вектор T s p=( x p , y p , z p ) , з ад ает положение о соб ой точ ки P p=1, . .. , P отслеживаемой в потоке изображений, – радиус-вектор tf характеризующий положение камеры связанной c изображением f , а ориентация этой камеры задается тройкой векторов ( i⃗ f , ⃗jf , k⃗ f ) (см. рис. 4). Таким образом система уравнений (2.1.6) может быть записана в следующем виде: { i⃗ f ( ⃗s p −t⃗ f ) , z fp ⃗jf ( ⃗s p −t⃗ f ) v fp =gf , z fp z fp =k⃗ f ( ⃗s p−t⃗ f ) . u fp=g f (2.1.7) 2.1.3. Математический вывод приближений Поместим начало МСК в центр масс точек объекта: P ∑ ⃗s p=0. (2.1.8) p=1 Тогда z – координата центра масс на кадре f P ⃗k f P 1 z = ∑ ∑ ⃗s − ⃗k ⃗t =−k⃗ f t⃗ f = zf P p=1 fp P p=1 p f f в МСК: (2.1.9) 20

z – координату точки p можно представить как: ( z fp= z f + ⃗k f ⃗s p =z f 1+ k⃗ f ⃗s p zf ). (2.1.10) Перепишем (2.1.7) с учетом (2.1.10) в следующем виде: { ufp=gf v fp =gf ⃗if ( s⃗ p− t⃗ f ) ( ⃗k ⃗s z f 1+ f p zf ⃗j f ( ⃗s p − t⃗ f ) ( ⃗k s⃗ z f 1+ f p zf , ) (2.1.11) . ) Разложим (2.1.11) в ряд Тейлора относительно ⃗k f ⃗s p zf до членов второго порядка и переобозначим сумму на σ , получим: { ufp =g f v fp =gf ( ) ( ( i⃗ f , ( ⃗s p−t⃗ f )) zf ( ⃗j f , ( ⃗s p−t⃗ f ) zf ( ) ) ( ) ) 2 k⃗ f ⃗s p k⃗ f s⃗ p ( i⃗ f , ( ⃗s p−t⃗ f ) ) 1− + +… =g f σ, zf zf zf ⃗k f s⃗ p ⃗k f s⃗ p 2 ( ⃗j f , ( ⃗s p−t⃗ f )) 1− + +… =g f σ. zf zf zf (2.1.12) Соберем члены при s p и t f : { ( ) σ v =g ( ⃗j , ⃗s ) −( ⃗j , t⃗ ) . ( zσ z ) σ σ ufp =g f ( ⃗if , s⃗ p ) −( i⃗ f , t⃗ f ) , zf zf fp f f p f f f (2.1.13) f Пусть |s p|≪ z f и|t f|≈ z f , тогда z f =z и gt =g т. е. константны для всех g ' g ' изображений. Обозначим s p=s p z и t f =t f z , тогда: { ' ' u fp=i⃗ f ( s p −t f ) , v fp = ⃗j f ( s 'p −t 'f ) . Множитель g z (2.1.14) не имеет большого значения, потому что, как уже было сказано, реконструкция производится с точностью до масштаба. Система уравнений (2.1.14) соответствует модели ортографической проекции [18]. 21

Если брать в расчет только |s p|≪ z f , и заменить в (2.1.7) z fp на z f получаем систему уравнений для модели масштабируемой ортографической проекции [16]: { u fp= v fp = ⃗if ( s'p−t 'f ) ' zf ⃗j f ( s 'p −t 'f ) zf = gf ' zf = , , ' zf −( k⃗ f , t⃗ f ) gf (2.1.15) . А если в (2.1.13) оставить только линейные по s p члены: { ( (( )) )) ( )( 1 1 ⃗k f s⃗ p ufp =g f ( i⃗ f , ⃗s p ) −( i⃗ f , t⃗ f ) − 2 , zf zf zf v fp =gf (2.1.16) k⃗ ⃗s ⃗jf , ⃗s p ) 1 −( ⃗j f , t⃗ f 1 − f p , 2 zf zf zf то получаем систему уравнений для параперспективной проекции [16]: { [( [( ] ) ) ) ufp = 1 ⃗ ( i⃗ f , t⃗ f ) ⃗ if + k f ⃗s p −( i⃗ f , t⃗ f ) , z 'f g z 'f v fp = 1 ' zf ⃗j f + ' zf = ( ⃗j f , t⃗ f gz ' f ] (2.1.17) ⃗k f ⃗s p −( ⃗j f , t⃗ f ) , z f −( ⃗k f , t⃗ f ) = . gf gf Введём следующие обозначения: Таблица 2.1.1. ОП МОП x f =−( i⃗ f , t⃗ ) ' f y f =−( ⃗j f , t⃗ f ) xf = ' ' zf = −( ⃗k f , ⃗t f ) z = ≈1 g g yf = z 'f = ППП −( i⃗ f , t⃗ ) ' f ' ' xf = ' yf = zf ' −( ⃗j f , ⃗t f ) zf −( k⃗ f , t⃗ f ) gf −( i⃗ f , t⃗ f ) z 'f = ' zf ' −( ⃗j f , ⃗t f ) ' zf −( k⃗ f , t⃗ f ) gf 22

m ⃗f = n⃗ f = ⃗if m ⃗f = ' f z ⃗j f n⃗ f = z 'f ⃗if ( ( 1 ⃗ xf ⃗ if − k f g z 'f y 1 n⃗ f = ' ⃗j f − f k⃗ f g zf m ⃗f = ' f z ⃗j f z 'f ) ) Согласно таблице 2.1.1, все указанные приближения сводятся к единому виду: { u fp=⃗ m f ⃗s p + x f v fp =⃗nf ⃗s p + y f (2.1.18) Отдельного внимания заслуживает модель перспективной проекции, так как она наиболее приближена к реальности. Используя приведенные ранее обозначения, их можно записать в следующем виде: { ufp= gf i⃗ f ( ⃗s p− ⃗t f ) , k⃗ f ( ⃗s p−t⃗ f ) ⃗j f ( ⃗s p − ⃗t f ) v fp =gf , k⃗ f ( ⃗s p−t⃗ f ) { ( i⃗ f , ⃗s p ) +x f , ( ⃗k f , ⃗s p ) + zf ( ⃗j f , ⃗s p ) + y f v fp =gf , ( ⃗k f , ⃗s p) + zf u fp=g f ⇒ (2.1.19) где { x f =−i⃗ f t⃗ f , y f =− ⃗j f t⃗ f , z f =−k f t⃗ f . (2.1.20) Существует несколько алгоритмов, позволяющих решить точную задачу. В рамках данной работы минимизируется ошибка: F P ε=∑ ∑ f =1 p=1 [( )( 2 ⃗j s⃗ + y i⃗ f ⃗s p + x f ufp −g f + v fp−g f f p f ⃗k f ⃗s p+ z f k⃗ f ⃗s p + z f )] 2 (2.1.21) Из ортов системы координат связанной с изображением формируется матрица поворота в виде функции углов α f , β f , γ f : ( cos α f cos β f ( cos α f sin β f sin γ f −sin α f cos γ f ) ( cos α f sin β f cos γ f −sin α f sin γ f ) ⃗ ⃗ ⃗ R ( i f , j f , k f )= sin α f cos β f ( sin α f sin β f sin γ f −cos α f cos γ f ) ( sin α f sin β f cos γ f −cosα f sin γ f ) sin β f cos β f sin γ f cos β f cos γ f ) (2.1.22) Таким образом, движение камеры определяется параметрами: 23

x f , y f , z f , α f , β f , γ f , а форма сцены параметрами s p=[s p 1 , s p 2 , s p 3 ] , т. е. количество неизвестных – 6 F +3 P , для них уравнения (2.1.19) задают переопределённую систему 2 FP уравнений, а с учетом (2.1.22) можно минимизировать ошибку (2.1.21). Начальные значения будем уточнять итерационно. Однако, при использовании МНК, на каждом шаге итерации нужно создавать и обращать матрицу размерности (6 F +3 P)×(6 F+3 P) . При достаточно большом количестве переменных, задачу минимизации ошибки будет невозможно разрешить. В связи с этим стоит решать их отдельно для переменных структуры и отдельно для переменных движения. То есть, сначала фиксируем переменные, характеризующие структуру сцены, решаем уравнения, минимизируя ошибку (2.1.21) (решаем F систем с 6 ю неизвестными). При этом, минимизация осуществляется отдельно по каждой переменной. После чего фиксируем переменные движения и снова решаем уравнения, минимизируя ошибку (2.1.21) по переменным, характеризующим структуру сцены (решаем P систем с 3 неизвестными). Итерацию заканчиваем, когда ошибка достигнет своего минимума. Сложность задачи понижена и теперь ее можно решить. 2.1.4. Метод факторизации матриц И з к о о р д и н а т { ( u fp , v fp )|f =1 … F , p=1 … P } измерений размера 2 F × P вида: [ ] u11 ⋮ u U W= = F1 V v 11 ⋮ v F1 [] ⋯ ⋱ … ⋯ ⋱ ⋯ u1 P ⋮ uFP v1 P ⋮ v FP с ф о р м и р у е м матрицу . С учетом (2.1.18) перепишем эту матрицу в следующем виде: W =RS+T [1 … 1] ⏟ P гд е R – матрица размерности 2 F × 3 , (2.1.23) характеризующая ориентацию 24

камер, S−¿ матрица размерности 3 × P характеризующая структуру сцены, а T – вектор размерности 2 F × 1 характеризующий положение камер в пространстве: [] [] T R= m1 ⋮ mTF nT1 ⋮ T nF , S=[ s 1 x1 ⋮ x ⋯ sp] , T = F y1 ⋮ yF . Поместим начало координат МСК в центр масс точек объекта (2.1.8): P 1 ∑ s =0 . P p=1 p (2.1.24) Обратим внимание на то, что вектор T также может быть получен суммированием элементов матрицы W . Тогда дальше имеет смысл работать c матрицей ~ W =W −T [⏟ 1 … 1 ] =RS . P Ранг матрицы ~ W , очевидно, не может быть больше, чем 3 , так эта матрица является произведением матриц R и S размерности 2 F × 3 и 3 × P соответственно. Матрица ~ W называется матрицей зарегистрированных измерений. Допустим, что 2 F ≥ P , тогда матрицу ~ W следующие матрицы: O1 Σ можно разложить на размерности 2 F × P , диагональную матрицу размерности P × P и матрицу O 2 размерности P × P : ~ W =Q 1 Σ Q 2 , (2.1.25) таким образом, что Q T1 Q1 =QT2 Q2 =Q 2 Q T2 =I , где I – единичная матрица размерности P × P . Наше допущение о том, что 2 F ≥ P не является критичным, потому как в противном случае те же самые манипуляции можно повторить с транспонированной ~ W . Σ – это диагональная матрица, содержащая сингулярные числа матрицы ~ W : σ 1 ≥ … ≥ σ P , упорядоченные по не 25

возрастанию. Такое разложение называется факторизацией ранга 3 матрицы ~ W методом сингулярного разложения. Разобьем матрицы Q 1 , Σ , Q 2 следующим образом: ' '' Q 1 =[ Q ⏟1∨Q⏟1 ]}2 F 3 Σ= [ P−3 ] ' Σ ¿ 0 }3 '' −¿+¿−¿ 0 ¿ Σ ¿}P−3 ⏟ ¿⏟ 3 (2.1.26) P−3 [ ] ' Q2 }3 Q2= '' −¿ Q2 ¿}P−3 ¿ ¿⏟ ¿ P−3 в таком случае ' ' ' '' '' '' Q 1 Σ Q 2=Q1 Σ Q 2 +Q 1 Σ Q 2 . Предположим, что мы обращаем внимание только на первое слагаемое данной суммы, то есть на три наибольших сингулярных числа матрицы ~ W и соответствующие им элементы. ¿ Обозначим ~ W идеальную матрицу зарегистрированных измерений. Это матрица, которую мы получили бы в случае отсутствия шума. Ее ранг не ¿ больше, чем 3. Тогда, ~ W имеет не более трех ненулевых сингулярных числа и все они будут содержаться в Σ' , так как элементы Σ упорядочены по не возрастанию. Более того, можно показать [32], что наилучшая возможная аппроксимация иде а льной матрицы ¿ зарегистрированных измерений ~ W матрицей 3-го ранга это произведение: ^ =Q '1 Σ ' Q'2 . W Тогда, можно сделать следующий вывод: наилучшая возможная структура объекта и оценка поворота получается при рассмотрении только трёх наибольших сингулярных значений ~ W , вместе с соответствующими левыми и правыми собственными векторами. 26

¿ является наилучшей оценкой ~ W . Теперь, ^ Таким образом, W определим новые переменные 1 ' 2 ^ =O [ Σ ] , R Тогда мы можем записать: ' 1 1 ^ [ Σ' ] 2 O'2 S= ^ =R ^ S^ . W Размерности матриц R^ и S^ совпадают с размерностями требуемых матриц структуры сцены и движения R соответственно. Однако R^ (2.1.27) и S – 2 F×3 и 3× P и S^ в общем случае отличаются от истинных матриц движения и структуры R и S , так как разложение (2.1.27), очевидно, не является единственным. Так, если Q обратимой матрицей размерности 3 ×3 , то R^ Q является любой и Q−1 S^ также являются ^ , поскольку допустимым разложением матрицы W ^ . ( ^R Q ) ( Q−1 S^ ) = R^ ( Q Q−1) S^ = R^ S^ =W Стоит заметить, что в случае отсутствия шума, R^ является линейным преобразованием реальной матрицы движения R , а S^ – линейным преобразованием реальной матрицы структуры сцены S . Действительно, при отсутствии шума, R и R^ порождают пространство столбцов ~ ~¿ ^ . Так что пространство столбцов является трехмерным, а W = W =W ^ R R и – различные базисы для одного и того же пространства, следовательно между ними существует линейное преобразование. То есть, существует матрица Q размерности 3 ×3 такая что R= ^ RQ , −1 S=Q S^ . Базисные вектора, задающие системы координат связанные с кадрами обладают свойством ортонормированности: { |i⃗ f|=1, |⃗j f|=1, ( i⃗ f , ⃗j f )=0. ⇒ { mf|=1, |⃗ |n⃗ f|=1, (⃗ mf , n⃗ f )=0. Получаем систему для нахождения Q : 27

ОП: { ^ f Q QT m ^ Tf =1, m T T n^ f Q Q n^ f =1, ^ f Q Q T n^ Tf =0. m { ^ f Q QT m ^ Tf −n^ f Q Q T n^ Tf =0, m ^ f Q QT n^ Tf =0, m ^ f Q QT m ^ Tf =1. m ППП, МОП: (2.1.28) ^ f и n^ f принимают следующие значения для различных проекций: здесь m Таблица 2.1.2. ОП МОП ⃗ ^ f =i⃗ f m ⃗ ^f= m n⃗^ f = ⃗j f n⃗^ f = ППП ⃗if ( ( 1 ⃗ xf ⃗ if − k f g z 'f y 1 n⃗^ f = ' ⃗j f − f k⃗ f g zf ⃗ ^f= m ' f z ⃗j f z 'f ) ) Решение систем (2.1.28) ищется при помощи МНК с использованием сингулярного разложения матриц. Неоднозначность в структуре объектов сцены связана с возможностью внесения в задачу знаковой неоднозначности заменой матрицы Q на ( ±1 0 0 Q 0 ±1 0 0 0 ±1 ) Приняв оси системы координат аналогичным образом, как и в системе координат любой камеры можно устранить неоднозначность в первом и втором знаке. На практике для этого лучше брать камеру, ориентация которой ближе всего к нормали снимаемой поверхности. Неоднозначность в третьем знаке возникает из-за того, что во всех приближениях не принимается в расчет глубина объекта, поскольку расстояние до объекта значительно больше. 2.1.5. Формирование плотной матрицы измерений На практике при построении матрицы измерений очень часто имеет место ситуация, когда некоторые особенности наблюдаются только на некоторых изображениях. Однако для описанного выше алгоритма необходимо присутствие всех особых точек на всех изображениях. В связи с этим, имеет место задача выделения наиболее полной матрицы измерений. 28

Решение этой задачи можно свести к решению задачи поиска клик в графе, построенном определенным образом. Для того чтобы не терять данные, мы будем рассматривать не только максимальную, а все клики. Граф, о котором шла речь выше, строится следующим образом образом: множество вершин графа Г={X , E } – все кадры F и все особые точки P , а множество ребер задается следующими условиями: 1) 2) и P−¿ полностью зависимые множества; если точка p имеется на изображении f , то между f ∈ F и F p∈P есть ребро (рис. 5). Рис. 5. Построение плотной матрицы измерений. Не существует механизма поиска оптимального решения задачи поиска клик в графе за полиномиальное время [33]. Однако есть множество алгоритмов, которые способны за полиномиальное время найти близкое к оптимальному решение. В данной работе предлагается использовать алгоритм, описанный в [34]. 2.2. Восстановление структуры трехмерных сцен из одного изображения по закраске Считается, что алгоритмы реконструкции сцены по закраске появились 29

самыми первыми еще в начале 70-х. Несмотря на это, они остаются актуальными и в наше время. Как уже было сказано, основной плюс данных алгоритмов заключается в том, что для построения модели сцены необходимо всего лишь одно изображение в градациях серого. Все алгоритмы реконструкции по закраске используют тот факт, что для поверхностей, обладающих ламбертовым законом рессеивания, яркость каждой точки зависит от значения косинуса угла между направлением на источник света и нормалью поверхности. Выберем систему координат таким образом, чтобы базисные вектора имели те же направления, что и у системы координат связанной с изображением. В таком случае, реконструированная модель сцены может быть описана функцией Z ( x , y ) . Нормали к данной поверхности тогда имеет вид: { ⃗n=( n x n y n z )= p (√ p q 1 1+ p +q √ 1+ p +q ∂ Z ( x , y) p ( x , y )= ∂x ∂ Z ( x , y) q ( x , y )= ∂y 2 2 2 2 √1+ p2+q2 ) (2.2.1) – компонента градиента поверхности по направлению x , q – компонента градиента по направлению y . Пусть на сцену падает паралленьный пучок света в следующем направлении { ( ps qs 1 √1+ p +q √ 1+ p +q √ 1+ p2s +q 2s cos τ sin θ p s ( x , y )= cos θ sin τ sin θ q s ( x , y )= cos θ ⃗s = ( s x s y s z ) = 2 s 2 s здесь θ – угол между осью z угол между осью x 2 s 2 s ) (2.2.2) и прямой до источника света, τ и проекцией на xy – прямой от объекта к источнику света. Тогда, если поверхность обладает ламбертовым законом рассеивания, для изображения B(x , y) справедливо: cos θ+ p sin θ+q sin τ sin θ √1+ p2+q2 – освещенность, которую создает источник света, ρ L B ( x , y )= A ρ L ( n⃗ , ⃗s )=A ρ L R ( p ,q )= A ρ L здесь A (2.2.3) – значение 30

альбедо. Относительно Z ( x , y ) уравнение (2.2.3) является нелинейным дифференциальным уравнением в частных производных с переменными коэффициентами. Если закон рассеивания света поверхности отличен от ламбертового, то правая часть уравнения (2.2.3) будет принимать более сложный вид. Для спекулярного рассеивания, согласно [35], общее выражение выглядит следующим образом: −β 2 2 2σ где (2.2.4) B ( x , y )= A ρ L ( n⃗ , ⃗s ) + A ρ SL e + A ρ SS δ ( θi−θr ) δ ( τ i−τ r ) β=arccos([n , s]) – угол между биссектрисой угла между прямыми до точки изображения b и до источника света и нормалью к поверхности, σ – значение ширины поглащаемой составляющей спекулярного рассеивания, θi , θr – углы между осью z и направлением на источник света и направлением зрения соответственно, x и проекцией на xy τi , τr – углы между осью прямой к источнику света и проекцией на xy направления зрения соответственно. В уравнении (2.2.4) третье слагаемое отвечает за отражаемую часть спекулярного рассеяния. Эта составляющая не равна нулю в достаточно узком диапазоне углов. Одним из самых простых методов считается метод Пентланда описанный в [36]. Исследование (2.2.3) заменяется исследованием линейной системы, которая с учётом (2.2.1), имеет вид: B(x , y) ∂Z ∂Z ~( B x , y )= −cosθ= cos τ sin θ+ sin τ sin θ A ρL ∂x ∂y (2.2.5) и в некотором смысле эквивалентна исходной. Далее для обеих сторон выполняется преобразование Фурье и выражается Фурье-образ Z : F z ( ε , η )= F~B ( ε , η ) 2iπ ( ε cos τ sin θ+η sin τ sin θ ) (2.2.6) Далее, если от (2.2.6) взять обратное преобразование Фурье, то получим искомую модель сцены. Существуют также более продвинутые методы, которые помогают избавиться от необходимости линеаризации (2.2.3), ярким примером является [37]. 31

2.3. Комбинирование подходов Идея комбинирования описанных выше подходов заключается в следующем: 1. Выполняется первоначальная реконструкция сцены одним из известных алгоритмов 2. В построенной модели, выделяются области для которых необходимо произвести уточнение 3. Для найденных областей производится реконструкция сцены другим алгоритмом 4. Результат реконструкции области совмещается с результатом реконструкции сцены Для построения первичной модели использовался алгоритм реконструкции сцены, основанный на декомпозиции матриц. Данный алгоритм был выбран по причине высокой точности при сравнительно невысокой сложности. На полученную на предыдущем шаге модель натягивается поверхность при помощи триангуляции Делоне [38]. Полигоны, площадь которых превышает некоторый заранее заданный порог помечаются как «подозрительные». Участок одного из изображений, полностью включающих данный полигон, будет реконструирован посредством алгоритма восстановления сцены по закраске. После реконструкции части сцены, границы которой взяты из полученной ранее модели, выполняется совмещение результатов. Так как реконструкция осуществляется с точностью до масштаба и поворота, на этом этапе осуществляется масштабирование и поворот реконструированной части сцены с целью минимизации расстояния между точками, формирующими реконструируемый полигон в исходной модели и соответствующими им точками в модели части сцены. 32

Глава 3. Результаты работы алгоритма В процессе исследования была создана программа реконструкции 3D сцен. Модуль реконструкции сцены методом, основанным на факторизации матриц, а также модуль совмещения результатов, написаны на языке С++, модуль восстановления сцены по закраске написан на языке MATLAB (код функции реконструкции глубины точек сцены приведен в приложении к работе, листинг 2). Взаимодействие между модулями осуществляется при помощи shell-скриптов. Структура программы подробно описана в пункте 1.1 и изображена на рис. 2. Входными данными являются файлы формата JPEG, который применяется для хранения фото и подобных им изображений. На выходе программа сохраняет реконструированное облако точек в файл формата PLY, в котором каждая точка имеет 6 параметров: по 3 на координаты в ДПСК и цвет точки в RGB модели. Для проверки работоспособности данной программы была сделана серия фотографий специально созданной сцены (ниже приведены некоторые снимки из коллекции). 33

В процессе работы программы с помощью метода, основанного на факторизации матриц, была создана первичная модель в виде облака точек: 34

После уточнения модели при помощи восстановления структуры по закраске Натягивание новой поверхности на уточненную модель: 35

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

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

Список литературы [1] B. K. P. Horn. Shape from Shading: A Method for Obtaining the Shape of a Smooth Opaque Object from One Vie w. http://people.csail.mit.edu/bkph/AIM/AITR-232-OPT.pdf [2] P.S. Tsai, M. Shah. Shape from shading with variable albedo. // Optical Engineering, April 1998, Vol. 37 No. 4, P. 121–1220. [3] R. Zhang, P.S. Tsai, J. E. Cryer, M. Shah. Shape from shading: A survey. // IEEE Transactions on Pattern Analysis and Machine Intelligence, August 1999, Vol. 21 Issue 8, P. 690–706. [4] A. Pentland. Shape information from shading: a theory about human perception // Second International Conference on Computer Vision, December 1988, P. 404–413. [5] R. Zhang, P.S. Tsai, J. E. Cryer, M. Shah. Analysis of shape from shading techniques. // IEEE Computer Society Conference on Computer Vision and Pattern Recognition, June 1994, P. 377–384. [6] P.S. Tsai, M. Shah. Shape from shading using linear approximation // Image and Vision Computing, October 1994, Vol. 12 Issue 8, P. 487–498. [7] Y. Xiong, S. Shafer. Depth from focusing and defocusing. http://www.cs.cmu.edu/~yx/papers/IUW93.ps.Z. [8] V. Roberto, A. Fusiello, E. Trucco. Experiments with a new area-based stereo algorithm // Lecture Notes in Computer Science, 1997, Vol. 1310, P. 669–676. [9] S.T. Bernard. A stochastic approach to stereo vision // Proceedings of the 5th National Conference on Artificial Intelligence, August 1986, P. 676–680. [10] A. Koschan, V. Rodehorst. Towards real-time stereo employing parallel algorithms for edge-based and dense stereo matching // Proceedings of the IEEE 39

Workshop on Computer Architectures for Machine Perception CAMP'95, September 1995, P. 234–241. [11] S. Roy, I. J. Cox. A maximum-flow formulation of the n-camera stereo correspondence problem // IEEE. Proceedings of International Conference on Computer Vision, January 1998, P. 492–499. [12] J. E. Cryer, P.S. Tsai, M. Shah. Integration of shape from shading and stereo // Pattern Recognition, January 1995, Vol. 28 Issue 7, P.1033–1043. [13] T. Kanade, M. Han. Scene reconstruction from multiple uncalibrated views // Technical report, The Robotics Institute, Carnegie Mellon University, January 2000. [14] A. Azarbayejani, T. Jebara, A. Pentland. 3d structure from 2d motion // IEEE Signal Processing Magazine, May 1999, Vol. 16, P. 66–84. [15] G. S. Bestor. Recovering Feature and Observer Position by Projected Error Refinement // PhD thesis, Computer Scince Department, University of Wisconsin - Madison, August 1998. [16] C. J. Poelman, T. Kanade. A paraperspective factorization method for shape and motion recovery // IEEE Transactions on Pattern Analysis and Machine Intelligence, March 1997, Vol. 19 Issue 3, P. 206–218. [17] J. Costeria, T. Kanade. A multi-body factorization method for motion analysis // Technical report, School of Computer Science, Carnegie Mellon University, September 1994. [18] C. Tomasi, T. Kanade. Shape and motion from image streams: a factorization method (orthographic method) // International Journal of Computer Vision, November 1992, Vol. 9 Issue 2, P. 137–154. [19] T. Morita, T. Kanade. A sequential factorization method for recovering shape and motion from image streams // IEEE Transactions on Pattern Analysis and 40

Machine Intelligence, August 2002, Vol. 19 Issue 8, P. 858–867. [20] M. Watanabe, S.K. Nayar, M. Noguchi. Real-time focus range sensor // IEEE. Proceedings of International Conference on Computer Vision, June 1998, P. 492–499. [21] T. Kanade, C. Tomasi. Shape and motion from image streams: a factorization method – part 3. Detection and tracking of point features. http://www.pnas.org/content/90/21/9795.full.pdf [22] S. Birchfield, C. Tomasi. Multiway Cut for Stereo and Motion with Slanted Surfaces // Proceedings of the Seventh IEEE International Conference on Computer Vision, September 1999, P. 489–495. [23] Н.В. Янова, Д.В. Юрин. Итеративный алгоритм восстановления трехмерных сцен, движения и фокусного расстояния камеры в перспективной проекции, основанный на факторизации матриц. http://graphicon2002.unn.ru/demo/2002/YanovaRe.pdf [24] C.B. Barber, D.P. Dobkin, H.T. Huhdanpaa, The Quickhull Algorithm for Convex Hulls // ACM Transactions on Mathematical Software, December 1996, Vol. 22, No. 4, P. 469–483. [25] J.R. Shewchuk. Triangle: Engineering a 2d quality mesh generator and delaunay triangulator // Applied Computational Geometry: Towards Geometric Engineering, May 1996, Vol. 1148, P. 203–222. [26] M. Bern, D. Eppstein. Mesh Generation and Optimal Triangulation. http://www.ics.uci.edu/~eppstein/pubs/BerEpp-CEG-95.pdf [27] F. Mokhtarian, A. Mackworth. Scale-Based Description and Recognition of Planar Curves and Two-Dimensional Shapes // IEEE Transactions on Pattern Analysis and Machine Intelligence, September 1986, Vol. 8 Issue 1, P. 34–43 41

[28] C. Harris, M. Stephens. A Combined Corner and Edge Detector // Proceedings of the 4th Alvey Vision Conference, 1988, P. 147–151. [29] W. Förstner. A framework for low-level feature extraction // Proceedings of the third European conference on Computer Vision, Vol. 2, 1994, P. 383–394. [ 3 0 ] T. Tomasi, C. Kanade. Detection and Tracking of Point Features. http://www.lira.dist.unige.it/teaching/SINA/slides-current/tomasi-kanadetechreport-1991.pdf [31] D. Lowe. Object recognition from local scale-invariant features. // Proceedings of the International Conference on Computer Vision, 1999, Vol. 2, P. 1150–1157. [32] G.H. Golub, C.E. Van Loan. Matrix Computations. The Johns Hopkins University Press, Baltimore, MD. 1989. [33] Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы. Построение и анализ. – М.: МЦНМО, 2000. 893 c. [34] C. Bron and J. Kerbosch. Algorithm 457: Finding All Cliques of an Undirected Graph // Communications of the ACM, September 1973, Vol. 16 Issue 9. P. 575–577. [35] K. Ikeuchi S, K. Nayar and T. Kanade. Surface reflection: physical and geometrical perspectives // IEEE Transactions on Pattern Analysis and Machine Intelligence, July 1991, Vol. 13 Issue 7. P. 611–634. [36] A. Pentland. Shape information from shading: a theory about human perception // Proceedings of International Conference on Computer Vision, December 1988, P 404–413. [37] B. K. P. Horn, M. J. Brooks. The Variational Approach to Shape from Shading. // Proceedings of the International Conference on Computer Vision, 1986, , Vol. 33, P. 174–208. [38] M. Bern, D. Eppstein. Mesh Generation and Optimal Triangulation. // 42

Computing in Euclidean Geometry, 1992, P. 23–90. 43

Приложение Листинг 1. Первичная реконструкция сцены и поиск положений камер в пространстве. 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: void ReRunSFM(double *S, double *U, double *V, double *W) { #ifdef RERUN_ADD_POINTS ComputeGeometricConstraints(); #endif int num_pts = (int) m_point_data.size(); int num_images = GetNumImages(); printf("[Initializing feature points...\n"); for (int i = 0; i < num_images; i++) { int num_keys = GetNumKeys(i); for (int j = 0; j < num_keys; j++) { GetKey(i,j).m_extra = -1; } } int num_init_cams = 0; int *added_order = new int[num_images]; int *added_order_inv = new int[num_images]; std::vector<ImageKeyVector> pt_views; camera_params_t *cameras = new camera_params_t[num_images]; printf("Setting up cameras\n"); for (int i = 0; i < num_images; i++) { printf("."); fflush(stdout); if (m_image_data[i].m_camera.m_adjusted) { m_image_data[i].LoadKeys(false, !m_optimize_for_fisheye); #ifdef RERUN_ADD_POINTS m_image_data[i].ReadKeyColors(); SetTracks(i); #endif added_order[num_init_cams] = i; added_order_inv[i] = num_init_cams; InitializeCameraParams(m_image_data[i], cameras[num_init_cams]); memcpy(cameras[num_init_cams].R, m_image_data[i].m_camera.m_R, sizeof(double) * 9); matrix_transpose_product(3, 3, 3, 1, m_image_data[i].m_camera.m_R, m_image_data[i].m_camera.m_t, cameras[num_init_cams].t); cameras[num_init_cams].t[0] *= -1.0; cameras[num_init_cams].t[1] *= -1.0; cameras[num_init_cams].t[2] *= -1.0; cameras[num_init_cams].f = m_image_data[i].m_camera.m_focal; cameras[num_init_cams].k[0] = m_image_data[i].m_camera.m_k[0]; cameras[num_init_cams].k[1] = m_image_data[i].m_camera.m_k[1]; SetCameraConstraints(i, cameras + num_init_cams); if (m_constrain_focal) { 44

62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: if (m_image_data[i].m_has_init_focal) { double diff = cameras[num_init_cams].f m_image_data[i].m_init_focal; if (fabs(diff) / m_image_data[i].m_init_focal < 0.4) { printf("Constraining focal " "length for camera %d\n", i); SetFocalConstraint(m_image_data[i], cameras + num_init_cams); } } } num_init_cams++; } else { added_order_inv[i] = -1; } } printf("\n"); printf("Setting up views...\n"); #ifndef RERUN_ADD_POINTS v3_t *init_pts = new v3_t[num_pts]; #else v3_t *init_pts = new v3_t[m_track_data.size()]; #endif v3_t *colors = new v3_t[num_pts]; for (int i = 0; i < num_pts; i++) { PointData &pt = m_point_data[i]; int num_views = pt.m_views.size(); // init_pts[i] = v3_new(pt.m_pos[0], pt.m_pos[1], -pt.m_pos[2]); init_pts[i] = v3_new(pt.m_pos[0], pt.m_pos[1], pt.m_pos[2]); colors[i] = v3_new(pt.m_color[0], pt.m_color[1], pt.m_color[2]); ImageKeyVector views; double *views_arr = new double[num_views]; int *perm = new int[num_views]; for (int j = 0; j < num_views; j++) { ImageKey ik = pt.m_views[j]; int v = ik.first; int k = ik.second; if (m_image_data[v].m_keys[k].m_extra != -1) { printf("Error! Already assigned this key " "[%d,%d] <- %d != %d!\n", v, k, m_image_data[v].m_keys[k].m_extra, i); } m_image_data[v].m_keys[k].m_extra = i; ik.first = added_order_inv[ik.first]; views_arr[j] = (double) v; views.push_back(ik); } qsort_ascending(); qsort_perm(num_views, views_arr, perm); ImageKeyVector views_sorted; for (int j = 0; j < num_views; j++) { views_sorted.push_back(views[perm[j]]); 45

131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148: 149: 150: 151: 152: 153: 154: 155: 156: 157: 158: 159: 160: 161: 162: 163: 164: 165: 166: 167: 168: 169: 170: 171: 172: 173: 174: 175: 176: 177: 178: 179: 180: 181: 182: 183: 184: 185: 186: 187: 188: 189: 190: 191: 192: 193: 194: 195: 196: 197: 198: 199: } pt_views.push_back(views_sorted); delete [] views_arr; delete [] perm; } CheckPointKeyConsistency(pt_views, added_order); #ifdef RERUN_ADD_POINTS AddAllNewPoints(num_pts, num_init_cams, added_order, cameras, init_pts, colors, 0.0, pt_views, 16.0, 2); #endif DumpOutputFile(m_output_directory, m_output_file, num_images, num_init_cams, num_pts, added_order, cameras, init_pts, colors, pt_views); RunSFM(num_pts, num_init_cams, 0, false, cameras, init_pts, added_order, colors, pt_views, 0.0 /*eps2*/, S, U, V, W); for (int i = 0; i < num_images; i++) { m_image_data[i].m_camera.m_adjusted = false; } printf("Focal lengths:\n"); for (int i = 0; i < num_init_cams; i++) { int img = added_order[i]; m_image_data[img].m_camera.m_adjusted = true; memcpy(m_image_data[img].m_camera.m_R, cameras[i].R, 9 * sizeof(double)); matrix_product(3, 3, 3, 1, cameras[i].R, cameras[i].t, m_image_data[img].m_camera.m_t); matrix_scale(3, 1, m_image_data[img].m_camera.m_t, -1.0, m_image_data[img].m_camera.m_t); m_image_data[img].m_camera.m_focal = cameras[i].f; printf(" [%d]: %0.3f\n", img, cameras[i].f); m_image_data[img].m_camera.Finalize(); } fflush(stdout); m_point_data.clear(); for (int i = 0; i < num_pts; i++) { if ((int) pt_views[i].size() == 0) continue; PointData pdata; pdata.m_pos[0] = Vx(init_pts[i]); pdata.m_pos[1] = Vy(init_pts[i]); pdata.m_pos[2] = Vz(init_pts[i]); pdata.m_color[0] = (float) Vx(colors[i]); pdata.m_color[1] = (float) Vy(colors[i]); pdata.m_color[2] = (float) Vz(colors[i]); #if 1 for (int j = 0; j < (int) pt_views[i].size(); j++) { int v = pt_views[i][j].first; 46

200: 201: 202: 203: 204: 205: 206: 207: 208: 209: 210: 211: 212: 213: 214: 215: 216: 217: 218: 219: 220: 221: 222: 223: 224: int vnew = added_order[v]; pdata.m_views.push_back(ImageKey(vnew, pt_views[i][j].second)); } #else pdata.m_views = pt_views[i]; #endif m_point_data.push_back(pdata); } DumpPointsToPly(m_output_directory, "points_readjusted.ply", num_pts, num_init_cams, init_pts, colors, cameras); if (m_output_file != NULL) { DumpOutputFile(m_output_directory, m_output_file, num_images, num_init_cams, num_pts, added_order, cameras, init_pts, colors, pt_views); } delete [] cameras; delete [] init_pts; delete [] added_order; delete [] added_order_inv; } Листинг 2. Функция вычисления глубины точек сцены по закраске. 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: function d = SFS(img, n, l) imgSize = size(img); P = img / max(max(img)); Px = imfilter(P, [-1 0 1]) / 2; Py = imfilter(P, [-1; 0; 1]) / 2; gt = zeros(imgSize); ft = zeros(imgSize); ft(Px >= max(max(Px)) / 2) = -2; ft(Px < min(min(Px)) / 2) = 2; gt(Py >= max(max(Py)) / 2) = 2; gt(Py < min(min(Py)) / 2) = -2; y=ft.^2+gt.^2; fs = ft; gs = gt; fs(y~=4) = 0; gs(y~=4) = 0; ker = [1 1 1; 1 0 1; 1 1 1] / 8; for i = 1 : n d = (-fs.^2 - gs.^2 + 4) ./ (fs.^2 + gs.^2 + 4); normal = 1./( fs.^2 + gs.^2 + 4 ).^2; fmid = imfilter(fs, ker); dif = P - d; f = (1/l) * fs.*normal.*dif; fs(ft==0) = fmid(ft==0) - f(ft==0); gmid = imfilter(gs, ker); g = (1/l) * gs .* normal .* dif; gs(gt == 0) = gmid(gt == 0) - g(gt == 0); end end 47

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв