Содержание к диссертации
Введение
1 Обзор, основные положения, требования 9
1.1 Анализ проблемы 9
1.2 Анализ существующих программных приложений 36
2 Калибровка изображений 43
2.1 Основные понятия 43
2.2 Метод калибровки изображений 56
3 Нахождение и сопоставление особенностей 78
3.1 Основные понятия 78
3.2 Метод сопоставления точечных особенностей 81
3.3 Метод сопоставления линий 89
4 Восстановление трехмерных сцен и объектов 107
4.1 Нахождение соответствий концевых точек на сопоставленных отрезках 107
4.2 Нахождение трехмерных координат концевых точек отрезков . 111
4.3 Нахождение дополнительных отрезков по первичной векторизации 114
4.4 Группировка и фильтрация отрезков 116
4.5 Построение и оптимизация полигонов 116
4.6 Объединение полученных полигонов в объекты(здания) 125
4.7 Сохранение полученной сцены в формате DirectX 126
Заключение 130
Литература 132
Приложение 141
- Анализ существующих программных приложений
- Метод калибровки изображений
- Метод сопоставления точечных особенностей
- Нахождение трехмерных координат концевых точек отрезков
Введение к работе
Актуальность работы
Создание трехмерных моделей реальных объектов и сцен по последовательности фотоизображений или видеоинформации и, в частности, разработка систем с использованием простых и доступных технических средств, таких как цифровые фотоаппараты и видеокамеры, без привлечения сложной и дорогостоящей техники (лазерные дальномеры, системы 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 работы в рецензируемых журналах, входящих в Перечень журналов ВАК.
Личный вклад автора.
Все результаты, составляющие основное содержание диссертации, получены автором самостоятельно. В работах [1, 2, 3] автору принадлежат алгоритмы сопоставления особенностей и калибровки и совместная с соавторами программная реализация. В работе [8] автору принадлежат методика и алгоритмы калибровки, алгоритмы сопоставления особенностей и метод реконструкции 3D объектов с его программной реализацией.
Структура и объем работы
Анализ существующих программных приложений
Photomodeler. Официальный сайт: http://www.photomodeler.com Данная программа позиционируется разработчиками как программа для трехмерной реконструкции на основе моделирования для точного измерения и визуализации ЗО-моделей в области машиностроения, архитектуры, кино, судебная медицина, и многих других.
Работа с программой начинается с загрузки фотоизображений объекта. Их должно быть как минимум два. Далее необходимо откалибровать камеру и изображения. Для калибровки камеры необходимо сфотографировать лист бумаги под углом в 45 градусов, а на полученном изображении выделить границы этого листа, по этим данным программа рассчитает фокус и центральную точку. Далее на загруженных изображениях находим угловые точки и связываем их гранями. Затем вручную устанавливаем сопоставления найденных точек на всех изображениях. Потом построенные грани объединяем в полигоны. Тектурирование происходит автоматически.
Привязку к физическим размерам объекта производим, выделяя любую грань и указывая ее длину в метрах, миллиметрах и т.д. Программа позволяет просматривать и сохранять полученные трехмерные объекты.
Вывод: это программа, предназначенная для реконструкции любых объектов, достаточно универсальна, но предполагает значительный объем ручной работы даже для объектов простой геометрической формы.
Для данного обзора использовались материалы сайта: http://www.photomodeler.com и демоверсия программы Photomodeler Pro 5.2.3.
Работа с программой начинается с загрузки изображений объекта. Их должно быть как минимум два, чтобы впоследствии их можно было откалибровать.
Далее надо отметить точечные особенности - соответствующие друг другу точки на изображениях. Это могут быть углы предметов, края рисунка и т.п. Таких точек должно быть минимум 7 на каждом изображении. Если точечные особенности хорошо распределены по сцене и отмечены достаточно точно, процесс калибровки запускается автоматически. Затем, если необходимо, можно вручную повысить точность калибровки, увеличив количество точечных особенностей. Полученные точки в трехмерном пространстве можно увидеть в любом из окон рабочей области.
Теперь можно задать систему координат, связанную со сценой, измерить углы и расстояния между объектами или их частями.
Основной этап работы с программой - моделирование. Можно создать один из 6 примитивов - плоскость, куб, цилиндр, сферу или диск - в зависимости от того, какой объект необходимо реконструировать. Исходный примитив привязывается к маркерам на изображении объекта.
Также можно создать отдельную грань или сетку из облака точек. С объектами можно выполнять различные операции — перемещать, вращать, масштабировать, соединять, разбивать. Можно работать не только с объектами, но и их гранями, ребрами, вершинами.
Что касается реконструкции более сложных тел вращения, а также, например, обобщенных цилиндров с постоянным радиусом сечения, с Image Modeler - это трудоемкий процесс. Аналогично, в случае с обобщенными коробками - параллелепипедами, у которых грани - произвольные линии -удобнее было бы воспользоваться реконструкцией по наброскам, а не подгонкой примитивов.
После того, как создан хотя бы один объект, его можно текстурировать. Для этого его необходимо выделить и указать, какие изображения будут использоваться для извлечения его текстуры. Использовать лучше всего только те изображения, где текстура выглядит наиболее четко и не загорожена другими объектами. Текстурировать можно и отдельные грани.
Для повышения точности калибровки камер кроме выделения соответствующих друг другу точек на разных изображениях и указания прямых углов можно отметить точки, принадлежащие одной плоскости -Оху, Oxz или Oyz. Также, если заранее известны какие-либо метрические данные о сцене - расстояния, длины, углы - то можно задать трехмерные координаты некоторых точек перед процессом калибровки. После процесса калибровки можно легко оценить ее точность.
Вывод: система, которая претендует на то, что может реконструировать/смоделировать практически все, вызывает большой интерес с точки зрения практики, но еще больший интерес она могла бы представлять, если бы она была дополнена методами реконструкции, более удобными для конкретных классов объектов.
Метод калибровки изображений
На этом этапе решаются две основные задачи - получение векторной основы опорных изображений и прослеживание точечных особенностей на всей последовательности используемых видов. Поскольку требования к векторной основе при калибровке и при 3D реконструкции сцены различаются, выполняется векторизация изображений в двух вариантах, чтобы наилучшим образом соответствовать цели ее использования.
При векторизации первого типа достаточно фильтрации «коротких» отрезков и спрямления ломаных, образующих прямолинейные отрезки. При векторизации второго типа (предназначенной для этапа реконструкции) дополнительно к фильтрации, отмеченной выше, обеспечивается: а) устранение разрывов в линиях; б) стыковка линий в угловых точках; в) сохранение главного направления линии на Т-образном пересечении линий. Получение субпиксельной точности формируемых отрезков обеспечивается применением метода наименьших квадратов к цепочке образующих точек(пикселей).
Алгоритм векторизации изображений имеет два основных режима, различающихся по назначению векторов: 1. Для обеспечения калибровки камеры; 2. Для выделения контуров (в конечном итоге ЗБ-каркасов) объектов. Основные этапы работы алгоритма: 1. Детектирование границ перепадов интенсивности и цвета на изображении (Edge detection); 2. Построение остова (скелета) границ перепадов; 3. Первоначальная «грубая» векторизация остова путем построения цепочек из групп связанных пикселов остова; 4. Более точная векторизация путем аппроксимации цепочек остова набором связанных отрезков (полилиний).
Для детектирования границ используется метод Canny[27]. Построение остова осуществляется методом послойного удаления.
Для калибровки камеры требуется выделения сравнительно длинных отрезков с высокой точностью аппроксимации. Для аппроксимации калибровочных отрезков используется метод наименьших квадратов. С помощью МНК производится поиск прямой, наилучшим образом соответствующий набору точек остова (рис. 2.10).
Эффективность активно развиваемых в последнее время методов 3D реконструкции сцен по последовательности некалиброванных видеоизображений в значительной степени определяется эффективностью методов калибровки изображений. Поскольку большой научно -практический интерес в настоящее время приобрела задача автоматической 3D реконструкции архитектурных сцен и создания виртуальных городов, значительная часть разрабатываемых методов калибровки ориентирована на использование специфики таких сцен (преимущественная параллельность и ортогональность пространственных линий объектов), которая реализуется в вычислении т.н. vanishing points (точек схода образов параллельных пространственных линий на 2D изображении). Знание точных значений трех vanishing points (vp) на изображении, отвечающих трем взаимно ортогональным направлениям в системе координат сцены, может существенно облегчить получение параметров калибровки. В частности, это позволяет определить ориентацию камеры по отношению к сцене. Однако и эта задача (определение vp) не является тривиальной, учитывая, что используемые линии несут ошибки предшествующего этапа векторизации исходных изображений. Хорошо известно, что методы оценки структуры и движения в целом очень чувствительны к ошибкам измерений. Поэтому самостоятельное значение приобрела и задача надежного определения vp, решению которой также посвящено много исследовательских работ. Другой важный аспект решения задачи калибровки - определение взаимного положения камер с оценкой эпиполярных ограничений и обеспечением метричности восстанавливаемой структуры (евклидовая с точностью до масштаба). Это требует надежного прослеживания точечных особенностей на последовательности видов. Дополнительная неопределенность возникает в предположении неизвестных параметров внутренней калибровки используемых камер (например, неизвестно фокусное расстояние).
В данной работе также предлагается метод определения неизвестных параметров калибровки (положение, ориентация и фокусное расстояние) фотоизображений по последовательности видов в контексте 3D реконструкции сцен городской обстановки. Метод ориентирован на автоматическую обработку и устойчивость к влиянию ошибок, связанных с векторизацией фотоизображений и прослеживанием точечных особенностей на видах. Отчасти он является развитием ранее реализованного метода калибровки, основанного на интерактивной привязке смежных видов к системе координат сцены[4]. Описываемый ниже метод опирается как на авторские, так и на известные современные методологические и алгоритмические решения, эффективность которых подтверждена в ряде опубликованных работ[2-5].
Отбор семейств отрезков. Для каждого полученного векторного изображения далее решается задача выделения трех семейств линий, соответствующих трем vp (отвечающим трем взаимно ортогональным направлениям в сцене). Делается это с помощью алгоритма RANSAC-типа, который вычисляет начальное приближение каждой из трех vp. Полученные при этом семейства отрезков предназначены для последующей работы оптимизационной схемы вычисления уточненных значений vp. Работа RANSAC-алгоритма организована следующим образом. Вначале оператор указывает на изображении две линии (для каждого из трех семейств) -представители семейства, задающие нужное направление, поскольку потенциально на изображении может быть много vp указанного типа (здания в сцене могут быть ориентированы произвольно по отношению друг к другу). Это необходимо также и для привязки трех смежных видов к одной и той же тройке ортогональных направлений в сцене (это единственное интерактивное вмешательство оператора во всей схеме калибровки, предполагается, что в дальнейшем будет решаться и задача автоматической классификации направлений, как, например, в [56]).
Метод сопоставления точечных особенностей
Основным требованием при решении задачи сопоставления точечных особенностей было обеспечение высокой скорости метода выделения точечных особенностей с приемлемыми для указанного приложения достоверностью и количеством сопоставлений. Результатом выполненной работы стал описываемый ниже метод, который обеспечивает устойчивое нахождение и отслеживание точечных особенностей на последовательностях больших по размеру изображений с высокой скоростью обработки. Схематично работа метода может быть представлена следующим образом: 1. Уменьшение разрешения изображения до разрешения 0,5 мегапикселя. 2. Выделение точечных особенностей на уменьшенном изображении с помощью метода, получившего название Difference-of-Gaussian (DoG) [53]. 3. Для полученных на предыдущей стадии точечных особенностей строятся так называемые дескрипторы[24, 53], инвариантные к повороту, изменению яркости и масштабу. 4. Нахождение соответствий между особенностями, путем сравнения их дескрипторов методом евклидового расстояния. 5. Перерасчет полученных соответствий с уменьшенных изображений на исходные. 6. Применение фильтра, позволяющего избавиться от большинства ложных сопоставлений. Главная особенность данного метода заключается в том, что, поскольку, большая часть вычислений проводится на изображениях с низким разрешением, время обработки уменьшается в несколько раз, по сравнению с тем, если бы вычисления производились на исходных изображениях. 3.2.1 Нахождение точечных особенностей В большинстве работ, посвященным выделению и отслеживанию точечных особенностей, например в[23, 57], рекомендуемый размер изображения в большинстве случаев лежит в диапазоне от 320 240 до 800 600 пикселей, и это не случайно. Так как сравнение точечных особенностей проводится по их окрестностям, а исходные изображения высокого разрешения больше подвержены цифровому шуму матрицы, то верные сопоставления имеют меньший коэффициент сходства, а при снижении проходного порога этого коэффициента в обработку попадает большое количество ложных сопоставлений. Также на больших изображениях приходится рассматривать физически более мелкие участки сцены, и при их сопоставлении также возникает большое количество ложных участков. Поэтому в данном методе первым шагом разрешение изображений уменьшается с исходного до 0,5 мегапикселей. Это позволяет, во-первых, уменьшить влияние шума на изображении, а во-вторых, позволяет рассматривать физически более крупные участки сцены. Например, на 5-мегапиксельном снимке участок 16x16 пикселей вокруг найденной особой точки соответствует размеру 30x30 сантиметров, а такой же участок на снимке размера 0,5 мегапикселей соответствует 100x100 сантиметров. Поэтому, наряду, с увеличением скорости обработки, уменьшение размера исходных снимков позволяют избавиться от большинства неоднозначностей сопоставления особенностей, при сохранении размера рассматриваемой окрестности особой точки, как показано на рис. 3.1.
Нахождение трехмерных координат концевых точек отрезков
Сопоставление свободных точек на сопоставленных отрезках. Свободными точками назовем такие точки, которые принадлежат только одному отрезку, т.е. не являются угловыми. На рис 4.5 видно, что точки р и и р 21 являются прообразами точек рги и р2], но им не соответствуют. Достроить отрезки, содержащие свободные точки до максимально видимой длины можно, опять же используя эпиполярные ограничения. Например, построим эпилинию / для точки р 2і отрезка (ри»Ри) по формуле (4.1) на левом изображении, и найдем пересечение полученной эпилинии с линией содержащей отрезок \p[vpr22), обозначим его р. Если отрезок (р,р22) длиннее отрезка (рг21,рГ22), то заменяем координаты точкир2] на координаты р. Иначе, строим эпилинию на левом изображении и ищем пересечении эпилинии с линией, содержащий соответствующий отрезок. Здесь есть одна крайняя ситуация, которую необходимо предусмотреть. В случае если эпилиния параллельна отрезку, с которым находится пересечение, то это пересечение будет на бесконечности. Поэтому необходимо проверить угол между эпилиниеи и отрезком и если он меньше определенного значения, то пересечение искать не будем. Для последовательности изображений рекуррентная схема достройки отрезков со свободными точками выглядит следующим образом: сначала достраиваем отрезки на первом изображении до максимально видимой длины, используя все изображения, затем на каждом последующем изображении достраиваем отрезки, используя данные только с первого изображения. Далее на втором изображении находим отрезки, отсутствующие на первом, и достраиваем их по вышеописанной схеме и т.д. При наличии откалиброванной пары изображений и сопоставленных точек проекций р и рг на эти изображения, задача восстановления точки р в трехмерном пространстве - это нахождение пересечения двух лучей, R = О р и Rr = Orpr. Но на практике эти лучи никогда не пересекаются (рис. 4.8) из-за погрешностей калибровки, неточных соответствий точек и т.д. Vі J Аналогичным образом найдем точку Р2, а точку Р найдем, усредняя координаты точек Р1 и Р2. Таким образом, определив трехмерные 113 координаты концевых точек каждого отрезка, получаем трехмерное положение этих отрезков в сцене. Как можно заметить из таблиц 3.2 и 3.3 число сопоставленных отрезков меньше, чем отрезков построенных в ходе векторизации изображений. Причинами являются неточная векторизация, зашумление изображений, перекрытие отрезков другими объектами и т.д., подробно об этом было сказано в главе 3. Еще одна причина, по которой такие отрезки не были сопоставлены, это то, что какой-то отрезок присутствует только на одном или двух видах, а на остальных он не наблюдаем. Часть из этих линий можно найти и использовать на этапе трехмерной реконструкции. Для этого попарно переберем все точки сопоставленных отрезков, и посмотрим, существует ли хоть в одном наборе исходных отрезков каждого изображения такой отрезок, который бы соединял эти две точки. Понятно, что при этом необходимо исключить из рассмотрения уже существующие сопоставленные отрезки. Если такой отрезок, соединяющий пару точек, найден, то добавляем его к общему списку сопоставленных отрезков на всех видах. Подобная ситуация рассмотрена на рис. 4.10.
Похожие диссертации на Построение пространственной модели городской обстановки по ограниченной некалиброванной последовательности фотоизображений
