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

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

КУДРЯШОВ Алексей Павлович

ПОСТРОЕНИЕ ПРОСТРАНСТВЕННОЙ МОДЕЛИ ГОРОДСКОЙ ОБСТАНОВКИ ПО ОГРАНИЧЕННОЙ НЕКАЛИБРОВАННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ФОТОИЗОБРАЖЕНИЙ

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

- з ДЕК 2009

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Владивосток - 2009

Работа выполнена в Учреждении Российской академии наук Институте автоматики и процессов управления ДВО РАН

Научный руководитель:

доктор технических наук Бобков Валерий Александрович

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

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

кандидат технических наук Долговесов Борис Степанович

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

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

Защита состоится " 22 " декабря 2009 года в 15 часов на заседании диссертационного совета Д 003.061.02 при Институте вычислительной математики и математической геофизики СО РАН по адресу: 630090, г. Новосибирск, проспект Академика Лаврентьева, 6.

С диссертацией можно ознакомится в библиотеке Учреждения Российской академии наук Института вычислительной математики и математической геофизики Сибирского отделения РАН.

Автореферат разослан «[§ » ноября 2009 г.

Ученый секретарь

диссертационного совета Д 003.061.02 при ИВМиМГ СО РАН, д.ф.-м.н.

С.Б. Сорокин

Общая характеристика работы

Актуальность работы

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

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

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

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

К настоящему времени уже достигнут значительный прогресс в решении указанной задачи и разработке прикладных программных систем. Вклад в теорию и практику создания систем реконструкции трехмерных сцен с использованием как фото- или видеоизображений, так и дополнительного оборудования связан с именами М. Pollefeys, А. Zisserman, А. Akbarzadeh, R. Yang, Р. Debevec и многих других. Существенные результаты в данной области получены в отечественных работах, выполненных в Институте прикладной математики РАН, Московском государственном университете, Московском физико-техническом институте и в др. организациях. Вместе с тем, существующие методы, алгоритмы и их программные реализации не в полной мере удовлетворяют основным требованиям, диктуемым практикой применения таких систем. К этим требованиям относятся: устойчивость к шумам и ошибкам измерений; геометрическая точность и качество визуализации создаваемых 3D моделей; степень автоматизации в процессе реконструкции и скорость обработки данных. Поэтому необходимы дальнейшие исследования, направленные на повышение эффективности разрабатываемых систем в рассматриваемой области.

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

Цель работы.

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

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

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

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

• разработка алгоритмов сопоставления отрезков на калиброванных, векторизованных изображениях.

• разработка алгоритмов построения 3D моделей объектов реальных городских сцен по набору фотоизображений и их программная реализация.

• разработка модели цифрового представления реконструируемых трехмерных объектов и средств конвертации данных в другие программные среды.

• разработка средств визуализации и редактирования получаемых трехмерных объектов.

• Программная реализация предложенных алгоритмов и методов.

Методы исследования.

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

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

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

2. Разработана новая методика и поддерживающие ее алгоритмы калибровки изображений, основанные на использовании вычисления точек схода (vanishing point), RANSAC-метода, методов нелинейной оптимизации и ограничений эпиполярной геометрии. Проведен анализ эффективности методики на реальных данных.

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

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

5. Разработан новый алгоритм полигональной реконструкции объектов городской обстановки по последовательности фотоизображений (видов).

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

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

особенностей на видах. Программные средства в целом могут использоваться в системах виртуальной реальности для реализации режима «виртуальной городской прогулки» и создания ЗБ моделей фрагментов городской обстановки по фотоизображениям.

Результаты диссертационной работы использовались в: а) учебном процессе ДВГУ (г. Владивосток); б) в Приморском аэрогеодезическом предприятии (г. Владивосток) для создания 30 моделей городской застройки в интересах МЧС.

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

Основные результаты работы докладывались и обсуждались на следующих конференциях и семинарах:

• на научных семинарах Института автоматики и процессов управления ДВО РАН в 2006 - 2009 гг.;

• на Дальневосточных математических школах-семинарах им. академика Е.В. Золотова, Россия, Владивосток, 2006,2008 гг.

• На 13-ой всероссийской конференции «Математические методы распознавания образов», Россия, Санкт-Петербург, 2007.

• На пятой Дальневосточной научно-практической конференции «Использование ГИС-технологий в Приморском крае», 2009.

Основные результаты работы изложены в 9 научных публикациях, в том числе 4 работы в рецензируемых журналах, входящих в Перечень журналов ВАК.

Личный вклад автора.

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

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

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

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

Во введении обосновывается актуальность темы, сформулированы цели и задачи диссертационной работы.

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

построения трехмерных объектов и сцен по изображениям. В самом общем виде она показана на рис. 1._

Получение изображений

Калибровка изображений

Л ^

Вычисление трехмерных координат сопоставленных особенностей

Построение 30 модели Рис. 1. Общая схема трехмерной реконструкции.

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

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

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

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

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

• Векторизация исходных снимков, основанная на применении модификации Canny фильтра с учетом тематического контекста и требований последующих этапов вычисления vp (vanishing points) и 3D реконструкции. На этом этапе решаются две основные задачи - получение векторной основы опорных изображений и прослеживание точечных особенностей на всей последовательности используемых видов. Поскольку требования к векторной основе при калибровке и при 3D реконструкции сцены различаются, векторизация изображений выполняется в двух режимах, чтобы наилучшим образом соответствовать цели ее использования. При векторизации первого типа достаточно фильтрации «коротких» отрезков и спрямления ломаных, образующих прямолинейные отрезки. При векторизации второго типа (предназначенной для этапа реконструкции) дополнительно к фильтрации, отмеченной выше, обеспечивается: а) устранение разрывов в линиях; б) стыковка линий в угловых точках; в) сохранение главного направления линии на Т-образном пересечении линий. Получение субпиксельной точности формируемых отрезков обеспечивается применением метода наименьших квадратов к цепочке образующих точек (пикселей). Также обеспечивается устранение радиальных оптических искажений.

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

• Применение RANSAC-алгоритма для выделения 3-х взаимно ортогональных семейств параллельных отрезков.

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

Определение взаимной ориентации камер. Задача получения внешней калибровки камер решается с использованием трех видов. Ее можно определить как нахождение матриц преобразования системы координат (СК) камеры 1-го вида в СК камеры 2-го вида (H]2) и в СК камеры 3-го вида (H)3). Матрицы ищутся с точностью до масштаба. Они представляются в виде:

где И - матрица вращения, I - вектор переноса СК.

Так как, матрицу вращения можно представить некоторым кватернионом, вместо матриц вращения будем использовать кватернионы. Поскольку вращение и перемещение камер не зависят друг от друга, задача разбивается на две последовательные: 1) определение кватернионов; 2) определение векторов переноса. Кватернионы и фокусы вычисляются из ур, соответствующих некоторой мировой системе координат (МСК). Если для двух видов известны фокусы и пары ур, соответствующие одной и той же МСК, то можно вычислить кватернион (вращение) из одного вида в другой.

Определение взаимного положения камер. Вектора переносов (^2, 12з, <31) определяются из соответствующих эпиполюсов. Вычисление эпиполюсов основывается на минимизации эпиполярных отклонений по множеству сопоставленных точек-особенностей (далее контрольных точек). Реализованы два варианта определения эпиполюсов: а) эпиполюсы определяются независимо для 3-х пар видов: 1-2, 2-3, 3-1. Для каждой пары используется нелинейная оптимизация. Неизвестными являются координаты эпиполюса (2 неизвестных). Целевая функция - эпиполярность - сумма квадратов углов между эпиполярными плоскостями П; и П,- по всем контрольным точкам (рк) между видами 1 и ^ б) определяются эпиполюсы для 3-х видов. Используется нелинейная оптимизация с нелинейными ограничениями. Неизвестными являются координаты эпиполюсов (6 неизвестных). Целевая функция - эпиполярность - сумма 3-х попарных целевых функций. Эксперименты показали, что оптимизация дает лучший результат при включении в число контрольных точек т.н. виртуальных точек. В качестве виртуальной точки рассматривается образ третьей камеры, видимый на двух остальных. Направления на него дают соответствующие эпиполюсы. Методика вычисления начального приближения эпиполюсов базируется на том, что: а) при известной взаимной ориентации двух камер и фокусах (используется кватернионы и фокусы, полученные на первом этапе) возможно построение эпилиний для сопоставленных точек на изображениях; б) правильные эпилинии пересекаются в одной точке - эпиполюсе. Поэтому усреднение облака точек, полученных на попарных пересечениях построенных эпилиний, дает нам начальное приближение эпиполюса.

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

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

Основным требованием при решении задачи сопоставления точечных особенностей было обеспечение высокой скорости метода выделения точечных особенностей с приемлемыми для указанного приложения

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

Схематично работа метода может быть представлена следующим образом:

1. Уменьшение разрешения изображения.

2. Выделение точечных особенностей на уменьшенном изображении с помощью метода, получившего название Difference-of-Gaussian (DoG).

3. Для полученных на предыдущей стадии точечных особенностей строятся так называемые дескрипторы, инвариантные к повороту и изменению яркости.

4. Нахождение соответствий между особенностями, путем сравнения их дескрипторов методом евклидового расстояния.

5. Перерасчет полученных соответствий с уменьшенных изображений на исходные.

6. Применение фильтра, позволяющего избавиться от большинства ложных сопоставлений.

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

Таблица 1. Сравнительные результаты работы предложенного алгоритма.

Сцена Разм ер изобр ажен ия Кол-во пар Ло жн ых Время (сек) Кол-во пар SIFT Ло жн ых Время (сек) Кол-во пар SURF Ло жн ых Время (сек)

ИАПУ 1 5 мп 151 3 27 184 2 147 204 3 112

ИАПУ 2 10 мп 192 2 52 417 2 286 452 5 167

Город 3 мп 127 1 18 104 1 67 118 2 42

Фунику лер 5 мп 183 4 26 202 2 154 211 3 110

Из таблицы видно, что предлагаемый алгоритм, в сравнении с алгоритмами SIFT и SURF, за счет меньшего количества сопоставлений, но

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

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

Оценка эффективности описанных алгоритмов проводилась на одной модельной и трех реальных сценах с использованием 3-х видов, полученных с помощью обычной цифровой фотокамеры. Векторизация и калибровка изображений выполнялась с помощью методики, описанной в главе 2. Полученная точность калибровки (средняя величина эпиполярного отклонения в пикселях для контрольных точек) для тестируемых реальных сцен: сцена «ИАПУ» - 5 (см. рис.2); сцена «Библиотека» - 2.3; сцена «Дом» -1.3. В первом эксперименте проверялась работа алгоритмов на изображениях со сравнительно небольшим количеством линий. Результаты этого вычислительного эксперимента для алгоритма сопоставления отдельных линий приведены в табл. 2.

Табл. 2. Алгоритм сопоставления линий

Сцена Число линий Сопоставлено Неправильных Эффективность

Модельная 21 21 0 1.000

ИАПУ 56 53 0 0.946

Библиотека 26 26 0 1.000

Дом 19 19 0 1.000

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

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

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

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

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

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

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

Для того чтобы иметь возможность редактировать полученные 3D модели в различных редакторах трехмерной графики (3d max, Maya и др.), полученная трехмерная сцена экспортируется в формат DirectX(.x). Текстурами для сцены являются сами фотоизображения сцены, текстурные координаты трехмерных точек являются координатами концевых точек сопоставленных и оптимизированных отрезков, спроецированных на исходные изображения.

На рис. 2 приведен пример реконструируемой трехмерной сцены.

i

Рис. 2. Исходные три снимка реальной сцены и построенная текстурированная модель.

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

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

Фотоснимки

Рис. 3. Структура и функционирование ПО.

Основные выводы и результаты, полученные в диссертации:

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

2. Разработана новая методика и оригинальная алгоритмическая база калибровки изображений, основанная на использовании присущей архитектурным сценам преимущественной параллельности ортогональности линий, RANSAC-метода, вычислении точек схода (vanishing point), применении методов нелинейной оптимизации и ограничений эпиполярной геометрии. Проведен анализ эффективности методики на реальных данных.

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

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

5. Реализован алгоритм рекуррентного восстановления трехмерных координат точек по протяженной последовательности фотоснимков.

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

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

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

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

В рецензируемых журналах из списка ВАК

1. В.А. Бобков, Ю.И. Роньшин, А.П. Кудряшов. Сопоставление линий по трем видам пространственной сцены// Информационные технологии и вычислительные системы, №2,2006, С. 71-78.

2. В.А. Бобков, Ю.И. Роньшин, А.П. Кудряшов. Идентификация линий по некалиброванным видам городской обстановки. Информационные технологии и вычислительные системы, №1,2007, С. 63-71.

3. Бобков В.А., Борисов Ю.С., Кудряшов А.П. Калибровка изображений городской обстановки, Информационные технологии и вычислительные системы, №1, 2009. с. 72-83.

4. Кудряшов А.П. Реконструкция трехмерных сцен городской обстановки. Информационные технологии, №7,2009. с. 63-68.

В других изданиях

5. Кудряшов А.П. Модификация кросскорреляционного метода. XXIV Дальневосточная математическая школа-семинар имени академика Золотова 2003, Владивосток, с. 80-81.

6. А.П. Кудряшов. Извлечение и сопоставление точечных особенностей. Электронный журнал "Исследовано в России", 2007, с. 1095-1104. http://zhumal.ape.relarn.ru/articles/2007/104.pdf

7. Кудряшов А.П. Идентификация линий по некалиброванным видам городской обстановки. XXX Дальневосточная математическая школа-семинар имени академика Золотова 2007, Владивосток, с. 46-47.

8. Бобков В.А., Борисов Ю.С., Кудряшов А.П. Реконструкция и визуализация городской обстановки по изображениям. 13-я Всероссийская конференция «Математические методы распознавания образов», 2007, с. 282-285.

9. Кудряшов А.П. Трехмерная реконструкция сцен городской обстановки по ограниченной, некалиброванной последовательности фотоизображений. XXXI Дальневосточная математическая школа-семинар имени академика Золотова 2008, Владивосток, с. 22.

Кудряшов Алексей Павлович

ПОСТРОЕНИЕ ПРОСТРАНСТВЕННОЙ МОДЕЛИ ГОРОДСКОЙ ОБСТАНОВКИ ПО ОГРАНИЧЕННОЙ НЕКАЛИБРОВАННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ФОТОИЗОБРАЖЕНИЙ

Автореферат

Подписано к печати 17.11.2009 Усл. печ. л. 0,8 Уч. изд. л. 0,7 Формат 60x84/16 Тираж 100 Заказ 63

Издано ИАПУ ДВО РАН. Владивосток, Радио,5 Отпечатано участком оперативной печати ИАПУ ДВО РАН. Владивосток, Радио, 5

ВВЕДЕНИЕ.

1 ОБЗОР, ОСНОВНЫЕ ПОЛОЖЕНИЯ, ТРЕБОВАНИЯ.

1.1 Анализ проблемы.

1.2 Анализ существующих программных приложений.

1.3 Выводы по главе.

2 КАЛИБРОВКА ИЗОБРАЖЕНИЙ.

2.1 Основные понятия.

2.2 Метод калибровки изображений.

2.3 Выводы по главе.'.

3 НАХОЖДЕНИЕ И СОПОСТАВЛЕНИЕ ОСОБЕННОСТЕЙ.

3.1 Основные понятия.

3.2 Метод сопоставления точечных особенностей.

3.3 Метод сопоставления линий.

3.4 Выводы по главе.

4 ВОССТАНОВЛЕНИЕ ТРЕХМЕРНЫХ СЦЕН И ОБЪЕКТОВ.

4.1 Нахождение соответствий концевых точек на сопоставленных отрезках.

4.2 Нахождение трехмерных координат концевых точек отрезков.

4.3 Нахождение дополнительных отрезков по первичной векторизации.

4.4 Группировка и фильтрация отрезков.

4.5 Построение и оптимизация полигонов.

4.6 Объединение полученных полигонов в объекты(здания).

4.7 Сохранение полученной сцены в формате DirectX.

4.8 Выводы по главе.

Актуальность работы

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

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

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

К настоящему времени уже достигнут значительный прогресс в решении указанной задачи и разработке прикладных программных систем. Вклад в теорию и практику создания систем реконструкции трехмерных сцен с использованием как фото- или видеоизображений, так и дополнительного оборудования связано с именами М. Pollefeys, A. Zisserman, A. Akbarzadeh, R. Yang, P. Debevec и многих других. Существенные результаты в данной области получены в отечественных работах, выполненных в Московском государственном университете и Московском физико-техническом институте. Вместе с тем существующие методы, алгоритмы и их программные реализации не в полной мере удовлетворяют основным требованиям, диктуемым практикой применения таких систем. К этим требованиям относятся: устойчивость к шумам и ошибкам измерений; геометрическая точность и качество визуализации создаваемых 3D моделей; степень автоматизации в процессе реконструкции и скорость обработки данных. Поэтому необходимы дальнейшие исследования, направленные на повышение эффективности разрабатываемых систем в рассматриваемой области.

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

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

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

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

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

• разработка алгоритмов сопоставления отрезков на калиброванных, векторизованных изображениях.

• разработка алгоритмов построения 3D моделей объектов реальных городских сцен по набору фотоизображений и их программная реализация.

• разработка модели цифрового представления реконструируемых трехмерных объектов и средств конвертации данных в другие программные среды.

• разработка средств визуализации и редактирования получаемых трехмерных объектов.

• Программная реализация предложенных алгоритмов и методов Научная новизна работы

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

• Разработана новая методика и поддерживающие ее алгоритмы калибровки изображений, основанные на использовании вычисления точек схода (vanishing point), RANSAC-метода, методов нелинейной оптимизации и ограничений эпиполярной геометрии. Проведен анализ эффективности методики на реальных данных.

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

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

• Разработан новый алгоритм полигональной реконструкции объектов городской обстановки по последовательности фотоизображений (видов).

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

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

Результаты диссертационной работы использовались в: а) учебном процессе ДВГУ (г. Владивосток); б) в Приморском аэрогеодезическом предприятии (г. Владивосток) для создания 3D моделей городской застройки в интересах МЧС.

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

Основные результаты работы докладывались и обсуждались на следующих конференциях и семинарах:

• на научных семинарах Института автоматики и процессов управления в 2006 - 2009 гг.;

• на Дальневосточных математических школах-семинарах им. академика Е.В. Золотова, Россия, Владивосток, 2006, 2008 гг.

• На 13-ой всероссийской конференции «Математические методы распознавания образов», Россия, Санкт-Петербург, 2007.

• На пятой Дальневосточной научно-практической конференции «Использование ГИС-технологий в Приморском крае» 2009. Основные результаты работы изложены в 9 научных публикациях, в том числе 4 работы в рецензируемых журналах, входящих в Перечень журналов ВАК.

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

Диссертация состоит из введения, 4 глав, заключения, списка литературы и приложения. Содержание работы изложено на 147 страницах (включая 7 страниц приложения). Список литературы включает 93 источника. В работе содержится 92 рисунка и 4 таблицы.

Основные выводы и результаты, полученные в диссертации:

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

2. Разработана новая методика и оригинальная алгоритмическая база калибровки изображений, основанная на использовании присущей архитектурным сценам преимущественной параллельности ортогональности линий, RANSАС-метода, вычислении точек схода (vanishing point), применении методов нелинейной оптимизации и ограничений эпиполярной геометрии. Проведен анализ эффективности методики на реальных данных.

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

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

5. Реализован алгоритм рекуррентного восстановления трехмерных координат точек по протяженной последовательности фотоснимков.

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

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

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

ЗАКЛЮЧЕНИЕ

1. В. А. Бобков, С. Б. Белов, В. П. Май, Е. В. Калачева, М.А. Морозов, Векторизация растровых изображений, Информационные технологии, N7, 1998, стр. 7-11.

2. Бобков В.А., Борисов Ю.С., Кудряшов А.П. Калибровка изображений городской обстановки, Информационные технологии и вычислительные системы, №1, 2009. с. 72-83.

3. Бобков В.А., Борисов Ю.С., Кудряшов А.П. Реконструкция и визуализация городской обстановки по изображениям. 13-я Всероссийская конференция «Математические методы распознавания образов», 2007, с. 282-285.

4. В.А. Бобков, Ю.И. Роныпин, А.П. Кудряшов. Идентификация линий по некалиброванным видам городской обстановки. Информационные технологии и вычислительные системы, №1, 2007, С. 63-71.

5. В.А. Бобков, Ю.И. Роныпин, А.П. Кудряшов. Сопоставление линий по трем видам пространственной сцены// Информационные технологии и вычислительные системы,№2, 2006, С. 71-78.

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

7. Кудряшов А.П. Идентификация линий по некалиброванным видам городской обстановки. XXX Дальневосточная математическая школа-семинар имени академика Золотова 2007 Владивосток, с. 46-47.

8. А.П. Кудряшов. Извлечение и сопоставление точечных особенностей. Электронный журнал "Исследовано в России", 2007, с. 1095-1104. http://zhurnal.ape.relarn.ru/articles/2007/104.pdf

9. Кудряшов А.П. Модификация кросскорреляционного метода. XXIV Дальневосточная математическая школа-семинар имени академика Золотова 2003, Владивосток, с. 80-81.

10. Кудряшов А.П. Реконструкция трехмерных сцен городской обстановки. Информационные технологии, №7, 2009. с. 63-68.

11. Кудряшов А.П. Трехмерная реконструкция сцен городской обстановки по ограниченной, некалиброванной последовательностифотоизображений. XXXI Дальневосточная математическая школа-семинар имени академика Золотова 2008. Владивосток, с. 22.

12. Н.В.Свешникова, Д.В.Юрин "Восстановление трехмерных сцен с помощью методов факторизации: принцип работы и оценка погрешностей " // В сб. Труды второй научной конференции СИМ'2005, Москва, Академия АйТи 19 мая 2005 г. -С.207-222. М.-.ИФТИ 2005.

13. Форсайт, Д. Понс, Жан. Компьютерное зрение. Современный подход.: Пер. с англ. М.: Издательский дом «Вильяме», 2004 - 928 с.

14. J.K. Aggarwal, l.S. Davis and W.N. Martin. Correspondence processes in dynamic scene analysis // Proc. of IEEE 69, pp. 562-572, 1981.

15. Baillard C. and Maitre H., 1999. 3D reconstruction of urban scenes from aerial stereo imagery: a focusing strategy. Computer Vision and Image Understanding, pp. 244-258.

16. С. Baillard and A. Zisserman. A plane-sweep strategy for the reconstruction of buildings from multiple images. In ISPRS Congress and Exhibition, 2000, pp. 105-112.

17. H.H. Baker, Т.О. Binford: "Depth from edge and intensity based stereo," Proc. seventh Int. joint Conf. Artif.Intell. pp. 632-636, 1981.

18. Basri, R., and Jacobs, D.W. 1997. Recognition using region correspondences. International Journal of Computer Vision, 25(2):145-166.

19. H. Bay, T. Tuytelaars, L.Gool. SURF: Speeded Up Robust Features, ECCV06, 2006, pp. 404-417.

20. S. Becker, N. Haala. Combined feature extraction for fa9ade reconstruction. ISPRS Workshop on Laser Scanning 2007 and SilviLaser 2007, Espoo, September 12-14, 2007.

21. Bruce D. Lucas and Takeo Kanade. An Iterative Image Registration Technique with an Application to Stereo Vision. International Joint Conference on Artificial Intelligence, pages 674-679, 1981.

22. J.Canny. A computational approach to edge detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6):679-698, 1986.

23. Cheng, Y. Q., Collins, R., Hanson, A. R., and Riseman, E. M., Triangulation without correspondences. Arpa Image Understanding Workshop, Monterey, CA, 1994.

24. R.T. Collins, "A space-sweep approach to true multiimage matching," in Int. Conf. on Computer Vision and Pattern Recognition, 1996, pp. 358-363.

25. C. Colombo, D. Comanducci, A. Del Bimbo, and F. Pernici, "Accurate Automatic Localization of Surfaces of Revolution for Self-Calibration and Metric Reconstruction," Proc. IEEE Workshop Perceptual Organization in Computer Vision, 2004, (on CD-ROM).

26. P. Debevec, С.J. Taylor, and J. Malik, "Modeling and rendering architecture from photographs: A hybrid geometry- and image-based approach," in SIGGRAPH, 1996, pp. 11-20.

27. Fabio R. 3D reconstruction of articulated objects from uncalibrated images, Proc. SPIE Vol. 4661, p. 148-156, 2002.

28. Faugeras, B. Mourrain, On the geometry and algebra of point and line correspondence between n images, Technical Report 2665, INRIA Sophia-Antipolis, 1995.

29. Faugeras, L. Robert, S. Laveau, G. Csurka, C. Zeller and Cyril Gauclin et Imad Zoghlami, 3D Reconstruction of Urban Scenes from Image Sequences, Computer Vision and Image Understanding (CVIU), 69, 3, pp. 292-309, March 1998.

30. M. Fischler and R. Bolles. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Communications of the Association for Computing Machinery, 24(6):381-395, 1981.

31. Fitzgibbon, A. W. and Zisserman, A. 1998. Automatic camera recovery for close or open image sequences. In Europ. Conf. Сотр. Vis., Freiburg, Germany, pp. 311-326.

32. Hailin Jin; Favaro, P.; Soatto, S. Real-time feature tracking and outlier rejection with changes inillumination. Computer Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference onVolume 1, Issue , 2001, pp. 684-689.

33. Goldgof, D.B., Hua Lee. Motion Analysis From Three-dimensional Profiles And The Applications. Signals, Systems and Computers, 1988. Twenty-Second Asilomar Conference onVolume 2, Issue , 1988 Page(s):950 954

34. D. Goldgof, H. Lee and T.S. Huang. Matching and motion estimation of three-dimensional point and line sets using eigen-structure without correspondences // Pattern Recognition, Vol. 25, №3, pp. 271-286, 1992.

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

36. Hartly R. In defence of 8-point algorithm, Proceedings of the International Conference on Computer Vision 1995, pp 1064 — 1070.

37. R. Hartley. Lines and Points in Tree Views — an Integrated Approach. Proc. ARPA Image Understanding Work Shop, Monterey, CA, 1994, pp. 10091016.

38. R. Hartley. Lines and Points in Tree Views and the trifocal tensor, International Journal of Computer Vision, 22(2), pp. 125-140, 1997.

39. Chia-Hoang Lee and Anupam Joshi. Correspondence problem in image sequence analysis // Pattern Recognition, Vol. 26, №1, pp. 47-61, 1993.

40. Z. Kim. Realtime road detection by learning from one example. In IEEE Workshop on Applications of Computer Vision, pp 455-460, 2005.

41. Z. Kim, Geometry of Vanishing Points and its Application to External Calibration and Realtime Pose Estimation, Institute of Transportation Studies, Research Reports, Paper UCB-ITS-RR-2006-5, July 1, 2006.

42. Reinhard Koch, Automatic Reconstruction of Buildings from Stereoscopic Image Sequences, Computer Graphics Forum, Volume 12 Issue3, Pages 339-350, 2008.

43. D. Leibowitz, A. Criminisi, and a. Zisserman. Creating architectural models from images. In Proceedings EUROGRAPHICS 1999, pp. 39-50.

44. H. C. Longuet-Higgins. A computer algorithm for reconstructing a scene from two projections. Nature 293: 133-135, 1981.

45. David G. Lowe Distinctive Image Features from Scale-Invariant Keypoints International Journal of Computer Vision, 60, 2 (2004), pp. 91-110.

46. Luong, Q.T., and Faugeras, O.D. 1996. The fundamental matrix: Theory, algorithms, and stability analysis. International Journal of Computer Vision, 17(1), pp. 43-76.

47. E. button, H. Maitre and J. Lopez-Krahe: Contribution to the determination of vanishing points using Hough transform. IEEE Transaction on Pattern Analysis andMachine Intelligence 16(4), 1994, pp. 430-438.

48. Matthew Antone and Seth Teller. Automatic Recovery of Relative Camera Rotations in Urban Scenes, in Proc. CvpR, pp.282-289, June 2000.

49. Mikolajczyk K. Detection of local features invariant to affine transformations, Ph.D. thesis, Institut National Polytechnique de Grenoble, France, 2002.

50. Mikolajczyk, K., Schmid, C.: Indexing based on scale invariant interest points. In:ICCV-2002. Volume 1. pp.525 -531.

51. M. Okutomi T. Kanade. A Multiple-Baseline Stereo. IEEE Pattern Analysis and Machine Intelligence, vol. 15(4), 1993, pp. 353-363.

52. M.Pollefey "Tutorial on 3d reconstruction" 2000 http://www.esat.kuleuven.ac.be/~pollefey/tutoriaI/

53. Pollefeys, M., Gool, L. V., Vergauwen, M., Cornelis, K., Verbiest, F. and Tops, J., 2003. Image-based 3d recording for archaeological field work. Computer Graphics and Applications 23(3), pp. 20-27.

54. M. Pollefeys, R. Koch, M. Vergauwen, A. A. Deknuydt, L. J. V. Gool. Three-dimentional Scene Reconstruction from Images. In Proc. SPIE-2000, Vol. 3958, pp. 215-226.

55. Rottensteiner, F. and Schulze, M., 2003. Performance evaluation of a system for semi-automatic building extraction using adaptable primitives. In: Proceedings of the ISPRS Workshop 'Photogrammetric Image analysis'. 2003, VOL 34; PART 3/W8, pp. 47-52.

56. Sato, Т.; Kanbara, M.; Yokoya, N.; Takemura, H. 3-D modeling of an outdoor scene by multi-baseline stereo using a long sequence of images. Pattern Recognition, 2002. Proceedings. 16th International Conference on Volume 3, Issue , 2002 Page(s): 581 584.

57. Sato T.;Kanbara M.;Yokoya N.;Takemura H. Dense 3-D Reconstruction of an Outdoor Scene by Hundreds-Baseline Stereo Using a Hand-Held Video Camera. International Journal of Computer Vision, Volume 47, Numbers 13, April 2002, pp. 119-129.

58. Sato, T. Kanbara, M. Yokoya, N. Outdoor scene reconstruction from multiple image sequences captured by a hand-held video camera. Multisensor Fusion and Integration for Intelligent Systems, MFI2003. pp. 113-118, 2003.

59. F. Schaffalitzky and A. Zisserman. Planar grouping for automatic detection of vanishing lines and points. IVC, 18(9):647-658, June 2000.

60. Schmid, C. and Zisserman, A., 1997. Automatic line matching across views. In: Proc. IEEE Conference on Computer Vision and Pattern Recognition, pp. 666-671.

61. С. Schmid , A. Zisserman, The Geometry and Matching of Curves in Multiple Views, Proceedings of the 5th European Conference on Computer Vision.Volume 40 , Issue 3 (December 2000) Pages: 199-233.

62. A. Shashua. Trilineriaty in Visual Recognition by Alignment // Proc. European Conference on Computer Vision, Springer-Verlag, 1994, pp. 479484.

63. J. Shi ,C. Tomasi, Good Features to Track, 1994 IEEE Conference on Computer Vision and Pattern Recognition (CVPR'94), 1994, pp. 593 600.

64. S. Sinha, J.-M. Frahm, and M. Pollefeys, "GPU-based Video Feature Tracking and Matching," Tech. Rep. TR06-012, University of North Carolina at Chapel Hill, May 2006.

65. Spetsakis M. Aloimonos Y. Structure from motion using line correspondence, International Journal of Computer Vision, 4(3), pp. 171183.

66. Sudipta N. Sinha, Jan-Michael Frahm, Marc Pollefeys and Yakup Gene, Feature Tracking and Matching in Video Using Programmable Graphics Hardware, submitted to Machine Vision and Applications, July 2006.

67. Sudipta N. Sinha, Jan-Michael Frahm, Marc Pollefeys and Yakup Gene, "GPU-Based Video Feature Tracking and Matching", EDGE 2006, workshop on Edge Computing Using New Commodity Architectures, Chapel Hill, May 2006.

68. Taillandier, F. and Deriche, R., 2002. Reconstruction of 3d linear primitives from multiple views for urban areas modelisation. InProceedings PCV02, Vol В, p. B-267.

69. Zhao Ting, David Dagan Feng and Tan Zheng, 3D Reconstruction of Single Picture, ACM International Conference Proceeding Series; Vol. 100, pp: 8386, 2004.

70. Carlo Tomasi and Takeo Kanade. Detection and Tracking of Point Features. Carnegie Mellon University Technical Report CMU-CS-91-132, April 1991.

71. B. Triggs. Autocalibration from planar scenes. In Proceedings of the 5th European Conference on Computer Vision (ECCV'98), pages 89-105, 1998.

72. B.Triggs. Matcing constraints and the joint image. -In International Conference on Computer Vision, pp. 338-343. 1995.

73. B.Triggs. The geometry of projective reconstruction: Matcing constraints and the joint image. Technical report, LIFIA, INRIA Rhone Alpes, 1,994.

74. Urban M. Pajdla T. Hlavac V. Projective reconstruction from multiple views. Technical report CTU-CMP-1999-5, CMP; FEL, CVUT, Praha, Chech Republic, 1999.

75. V. Vezhnevets, A. Konushin, A. Ignatenko. INTERACTIVE IMAGE-BASED URBAN MODELLING, Photogrammetric Image Analysis, 2007, pp.63-69.

76. Weng J. Huang T. Ahuja N. Motion and structure from line correspondence: closed-form solution, uniqueness, and optimization, IEEE Trans. Pattern Analysys and'Machine Intelligence, 14(3), pp. 318-336, 1992.

77. T. Werner, T. Pajdla, Martin Urban Toolbox for 3D Reconctruction from Uncalibrated 2D Views. Czech Technical University. Research report. 1999.

78. Wiengmann A. Wagner H. Kowarschik R. Human face .measurement bu projecting bandlimited random patterns. Opt.expr. 2006 V.14. pp. 76927698.

79. Marta Wilczkowiak, 3D Modelling From Images Using Geometric Constraints, Диссертация на соискание звания доктора математики и информатики, Франция, 2004.

80. C. Zach A. Klaus J. Bauer K. Karner. From Real Cities to Virtual Habitats. http://www.vrvis.at/TR/2002/TR VRVis 2002 009 Full.pdf, 2002.

81. Zisserman and R. Hartley. Multi View Geometry, chapter 10, pages 262294. Cambridge University Press, 2000. ISBN 0-521-62304-9.