Содержание к диссертации
Введение
Глава 1. Анализ задачи, методов и систем синтеза трехмерных моделей местности для транспортных тренажеров 12
1.1 Актуальность задачи автоматической реконструкции трехмерных моделей местности для транспортных тренажеров 12
1.2 Уровни детальности представления объектов 15
1.3 Системы реконструкции трехмерных сцен 18
1.4 Источники данных для реконструкции трехмерных сцен 22
1.5 Анализ методов и алгоритмов реконструкции трехмерных сцен по изображениям
1.5.1 Методы трехмерной реконструкции на основе одного изображения 28
1.5.2 Методы трехмерной реконструкции на основе стереоизображений 29
1.5.3 Методы трехмерной реконструкции на основе многовидового стерео 34
1.5.4 Методы трехмерной реконструкции на основе видеопоследовательности 34
1.5.5 Методы трехмерной реконструкции на основе априорной информации 35
Выводы по главе 1 37
Постановка задачи исследования 38
Глава 2. Разработка моделей и алгоритмов реконструкции трехмерных сцен на основе спутниковых изображений и априорной информации 39
2.1 Разработка моделей реконструируемых зданий 39
2.2 Разработка схемы процесса реконструкции 3D-моделей зданий на основе спутниковых снимков и априорной информации 43
2.3 Разработка алгоритма нахождения соответствий на изображениях на основе дескрипторов и графов 47
2.4 Разработка алгоритма вычисления карты высот по стереоизображениям на основе построчной минимизации энергии в пределах региона 53
2.5 Разработка алгоритма обнаружения зданий на спутниковых изображениях с использованием априорной информации 58
2.5.1 Использование цветовых инвариантов для выделения на изображениях областей растительности и теней 59
2.5.2 Разработка алгоритма группировки регионов для обнаружения объектов на основе априорной информации 63
2.5.3 Анализ формы и площади выделенных областей 67
2.6 Реконструкция трехмерных моделей зданий на основе спутниковых изображений и априорной информации 70
2.6.1 Разработка алгоритма выделения и генерализации контура здания 71
2.6.2. Разработка алгоритма декомпозиции контура здания 76
2.6.3 Разработка алгоритма реконструкции трехмерных моделей зданий на основе спутниковых изображений и априорной информации 79
Выводы по главе 2 86
Глава 3. Исследование алгоритмов реконструкции трехмерных сцен на основе спутниковых изображений и априорной информации 87
3.1. Исследование алгоритма нахождения соответствий на изображениях на основе дескрипторов и графов 87
3.2 Исследование алгоритма вычисления карты высот по стереоизображениям на основе построчной минимизации энергии в пределах региона 91
3.3 Исследование алгоритма обнаружения зданий на спутниковых изображениях с использованием априорной информации 95
3.4 Исследование алгоритмов реконструкции трехмерных моделей зданий на основе спутниковых изображений и априорной информации 98
Выводы по главе 3 101
Глава 4. Применение разработанных алгоритмов трехмерной реконструкции в системе транспортного тренажера 102
4.1 Структура системы реконструкции трехмерных сцен на основе спутниковых изображений и априорной информации 102
4.2 Методика реконструкции трехмерных сцен с использованием разработанной системы 105
4.3 Внедрение системы реконструкции трехмерных сцен 110
Выводы по главе 4 112
Заключение 113
Литература
- Уровни детальности представления объектов
- Разработка схемы процесса реконструкции 3D-моделей зданий на основе спутниковых снимков и априорной информации
- Исследование алгоритма обнаружения зданий на спутниковых изображениях с использованием априорной информации
- Методика реконструкции трехмерных сцен с использованием разработанной системы
Введение к работе
Актуальность работы. Одним из основных средств для подготовки профессионалов в сфере транспорта, армии, промышленности, спецслужб являются тренажеры. Главным предназначением тренажера является отработка навыков и приобретение опыта в искусственных условиях в результате неоднократных тренировок. Использование тренажеров позволяет ускорить процесс обучения, сократить материальные затраты, избежать внештатных ситуаций на начальном этапе обучения, смоделировать экстремальные условия, создавать которые в реальной обстановке опасно и неоправданно.
Тренажеры моделируют необходимый уровень подобия действий обучаемого в синтезируемой среде, которая получила название «виртуальной реальности». Основой всех систем виртуальной реальности является визуальное отображение трехмерных сцен. При помощи функции зрения человек получает до 85 % информации. Поэтому в тренажерно-обучающих системах важно обеспечить адекватное отображение визуальной обстановки, соответствующей реальным условиям процесса.
Создание трехмерных моделей местности для компьютерных тренажерно-обучающих систем является актуальной задачей в настоящее время. Основными характеристиками процесса создания трехмерных сцен для тренажеров различного назначения являются: реалистичность моделей, соответствие визуальной обстановке существующей местности, время и стоимость синтеза. Часто эти характеристики являются взаимоисключающими. В сложившейся ситуации возникла очевидная потребность в системах построения трехмерных моделей по изображениям, не требующих дорогостоящего оборудования, в которых взаимодействие с пользователем сводится к малому количеству простых операций.
Существенный вклад в развитие научных исследований в области трехмерной реконструкции внесли отечественные и зарубежные ученые: Конушин А.С., Лемпицкий В.С., Баринова О.А., Матвеев И.А., Фурсов В.А., Марр Д., Полефейс М., Шапиро Л., Форсайт Д., Циссерман А., Понс Ж., Харрис Ц., Хорн Б.К.П. и др.
В последнее время было разработано большое количество методов и систем реконструкции трехмерных моделей местности на основе изображений. Однако существующие системы часто требуют значительного участия оператора в процессе реконструкции; осуществляют построение только моделей, которые не обладают сложной геометрией в отличие от визуальной обстановки города; имеют высокую стоимость программного обеспечения, оборудования, исходных данных.
Создание системы трехмерной реконструкции городских сцен на основе спутниковых изображений высокого разрешения позволит снизить время генерации моделей и, следовательно, сократит затраты на разработку тренажерно-обучающих систем. Таким образом, создание системы трехмерной реконструкции для тренажеров транспортных средств является актуальной научно-технической задачей.
Объект исследования – системы синтеза компьютерных трехмерных моделей сцен для приложений виртуальной реальности.
Предмет исследования – модели и алгоритмы реконструкции компьютерных трехмерных сцен на основе спутниковых изображений для систем визуализации транспортных тренажеров.
Цель и задачи работы
Целью работы является разработка моделей и алгоритмов, позволяющих строить системы автоматической реконструкции трехмерных моделей городских сцен на основе спутниковых изображений высокого разрешения (соответствует п. 5 и п.7 паспорта специальности).
Для реализации поставленной цели необходимо решить следующие задачи:
провести обзор и анализ методов и систем синтеза трехмерных моделей местности;
разработать трехмерные модели зданий, которые будут реконструированы;
разработать и исследовать алгоритм нахождения соответствий на изображениях, позволяющий уменьшить количество «выбросов»;
разработать и исследовать алгоритм вычисления карты высот на основе стереоизображений, позволяющий обрабатывать области однородной закраски на снимках;
разработать и исследовать алгоритм обнаружения зданий на спутниковых изображениях;
разработать и исследовать алгоритмы трехмерной реконструкции зданий на основе спутниковых изображений;
реализовать систему реконструкции трехмерных моделей местности для транспортных тренажеров с использованием разработанных алгоритмов.
Научная новизна работы
В процессе проведенных исследований получены следующие новые результаты:
алгоритм нахождения соответствий на стереоизображениях, отличающийся от существующих подходов совместным использованием дескрипторов и графов и позволяющий уменьшить количество «выбросов»;
алгоритм вычисления карты высот по стереоизображениям на основе построчной минимизации энергии в пределах региона, отличающийся от существующих подходов предварительной сегментацией снимков и позволяющий обрабатывать слаботекстурированные области стереоизображений;
алгоритм обнаружения зданий на спутниковых изображениях с использованием априорной информации, отличающийся от существующих подходов совместным использованием данных о высоте, цвете, форме и площади проекций объектов и позволяющий выделять на снимках области зданий для трехмерной реконструкции;
алгоритмы трехмерной реконструкции моделей зданий на основе спутниковых изображений и априорной информации, отличающиеся от существующих подходов использованием геометрических гистограмм для распознавания изображений и позволяющие синтезировать трехмерные параметрические модели зданий уровня LOD2 по стандарту CityGML.
Теоретическая значимость
Теоретическая значимость заключается в расширении возможностей систем синтеза трехмерных сцен за счет автоматизации процесса реконструкции и повышения точности генерации объектов при использовании априорной информации. Предложенные алгоритмы могут быть использованы в системах компьютерного зрения с возможностью автоматического обнаружения, локализации и синтеза трехмерных объектов.
Практическая значимость
Практическая значимость работы заключается в применении разработанных подходов при синтезе трехмерных сцен для компьютерных тренажеров транспортных средств гражданского и военного назначения. Разработанные алгоритмы и программные модули системы реконструкции трехмерных сцен апробированы на АО «Муромское СКБ» (г. Муром), что подтверждается соответствующим актом. Также разработанные алгоритмы и программные модули используются в учебном процессе Муромского института (филиала) ВлГУ.
Методология и методы исследования
В работе использованы основные понятия теории алгоритмов, математического моделирования, спектральной теории графов, методы цифровой обработки изображений и распознавания образов, методы машинной графики и вычислительной геометрии.
Положения, выносимые на защиту:
алгоритм нахождения соответствий на изображениях на основе дескрипторов и графов;
алгоритм вычисления карты высот по стереоизображениям на основе построчной минимизации энергии в пределах региона;
алгоритм обнаружения зданий на спутниковых изображениях с использованием априорной информации;
-алгоритмы трехмерной реконструкции моделей зданий на основе спутниковых изображений и априорной информации;
-результаты экспериментальных исследований разработанных алгоритмов;
-система реконструкции трехмерных сцен на основе спутниковых изображений для тренажеров транспортных средств.
Степень достоверности результатов исследования обусловлена следующими положениями:
-результаты работы опубликованы в 9 журналах ВАК и обсуждались на 8 всероссийских и международных научно-технических конференциях;
сравнение полученных результатов с существующими подходами показывает преимущество разработанных алгоритмов. Результаты сравнения приведены с использованием тестовых и реальных изображений, графиков и гистограмм. Результаты работы подтверждаются изображениями синтезированных сцен;
установлено соответствие результатов диссертационной работы с данными карт и кадастровых планов г. Мурома;
-разработанные алгоритмы и программные модули апробированы и частично используются для реконструкции трехмерных сцен города в тренажерах транспортных средств, выпускаемых АО «Муромское СКБ» (г. Муром). Это подтверждается соответствующим актом внедрения;
-получено свидетельство о государственной регистрации программы для ЭВМ № 2015610051 от 12.01.2015 г. «Система синтеза трехмерных моделей местности на основе спутниковых и аэрофотоснимков»/ Тужилкин А.Ю., Захаров А.А., Жизняков А.Л.
Апробация результатов. Результаты работы получены автором при выполнении Гранта РФФИ № 16-37-00236-мол_а «Методы и алгоритмы автоматической реконструкции трехмерных моделей городских сцен на основе спутниковых изображений»; Гранта РФФИ № 15-07-01612-А «Методы и алгоритмы распознавания изображений на основе спектральной теории графов»;
Гранта РФФИ № 13-07-97523 р_центр_а «Разработка методов синтеза пространственной информации по видеоизображениям для задач визуального контроля технологических процессов в промышленности»; проекта № 2918 задания на выполнение государственных работ в сфере научной деятельности в рамках базовой части государственного задания Минобрнауки России «Теория и методы распознавания и синтеза пространственно-временной информации на основе синтаксического анализа изображений в системах технического зрения».
Диссертационная работа и отдельные ее части докладывались и обсуждались
на 16-ой международной конференции «Цифровая обработка сигналов и её
применение - DSPA-2014» (Институт проблем управления им. В.А. Трапезникова
(ИПУ РАН), г. Москва, 2014), на всероссийской межвузовской научной
конференции «Наука и образование в развитии промышленной, социальной и
экономической сфер регионов России» (МИ (ф) ВлГУ, г. Муром, 2014), на 16-ой
международной научно-технической конференции «Измерение, контроль,
информатизация» (АлтГТУ , г. Барнаул, 2015), на 12-ой международной
конференции «Pattern Recognition and Information Processing» (ОИПИ НАН
Беларуси, г. Минск, 2014), на 12-ой международной конференции «Оптико-
электронные приборы и устройства в системах распознавания образов, обработки
изображений и символьной информации. Распознавание – 2015» (ЮЗГУ, г. Курск,
2015), на 25-ой международной конференции «СВЧ-техника и
телекоммуникационные технологии» (КрыМиКо’2015) (СевГУ, 2015), на IX международной научно-технической конференции «Современные проблемы машиностроения» (ТПУ, г. Томск, 2015), на международной научно-технической конференции «International Conference on Industrial Engineering-2015» ( ЮУрГУ, г. Челябинск, 2015).
Система апробирована в АО «Муромское СКБ» (г. Муром) при реконструкции трехмерных сцен для тренажеров транспортных средств.
Публикации
По теме диссертации была опубликована 21 работа: 9 работ в журналах из перечня ВАК; 3 публикации в изданиях, входящих в реферативную базу SCOPUS; 1 монография; 7 тезисов докладов; 1 свидетельство о государственной регистрации.
Диссертационная работа включает введение, четыре главы, заключение, список литературы, включающий 149 наименований, приложения. Общий объем диссертации – 141 страница, таблиц 16, рисунков 52.
Личный вклад. Все выносимые на защиту результаты и положения, составляющие основное содержание диссертационной работы, разработаны и получены лично автором и при его непосредственном участии.
Уровни детальности представления объектов
Уровнями детальности (LOD – Level of Detail) называют степень подробности представления трехмерного объекта средствами компьютерной графики. В этом случае создаются несколько вариантов представления одного объекта с различными степенями детализации. Уровни детальности используют для универсального представления и хранения моделей местности. Ассоциацией OGC (Open Geospatial Consortium) разработан язык CityGML (City Geography Markup Language), который основан на XML-формате [84].
При помощи CityGML можно представлять структуру таких объектов, как здания, рельеф местности, растительность, дороги, мосты, туннели и т.д. CityGML определяет классы и отношения объектов, основываясь на их топологических, семантических и геометрических свойствах. Язык CityGML позволяет отображать объекты при помощи пяти уровней детальности (рис.1.1). LoD 0 LoD 1 LoD 2 LoD 3 Lod 4
Представления трехмерного объекта с помощью уровней детальности по стандарту CityGML Каждый уровень детальности определяет степень подробности представления объекта при помощи геометрии и текстур и используется в конкретных ситуациях (табл. 1.1). Использование уровней детальности позволяет постепенно уточнять геометрические и семантические свойства объектов.
Геометрическое представление Контур на плоскости Призма, полученная путем «выдавливания» проекции объекта Упрощенное представление геометрии Точнаявнешняямодель Точнаямодель,интерьер
Точность(положение/высота) 5 м 5м/ 5м 2м/ 2м 0.5 м/ 0.5 м 0.2 м/ 0.2 м
Форма крыши - Плоская Определены тип крыши и ориентация в пространстве Соответствие реальному объекту Соответствие реальному объекту
Отдельностоящиедеревья - - Прототипы объектов высотой более 6 м Прототипы объектов высотой более 2 м Соответствие реальному объекту
Растительный покров - 50 x 50 м 5 x 5 м 1 x 1 м 17
Уровень детальности LoD0 представляет объекты в виде контура на плоскости. Область объекта, описываемая контуром, принадлежит одной высоте.
Уровень детальности LoD1 представляет собой трехмерную модель, полученную путем операции вертикального «выдавливания» проекции объекта. Уровень LoD1 не имеет семантического структурирования.
Уровень детальности LoD2 отображает здания в упрощенном виде. Геометрия LoD2 описывается с помощью ограничивающих поверхностей. Уровень LoD2 может включать такие элементы, как стены, крыши, трубы. По сравнению с уровнем LoD1 представление объектов в LoD2 имеет геометрическое и семантическое описание.
Уровень детальности LoD3 представляет собой геометрически точную внешнюю оболочку. В LoD3 включена информация о дверных и оконных проемах, лестницах и т.д. На основе уровня LOD3 могут быть проанализированы пути эвакуации при чрезвычайных ситуациях, осуществлено планирование действий спецслужб.
Уровень детальности LoD4 расширяет предыдущий уровень путем описания интерьера. Уровень содержит информацию о помещениях, мебели, отопительных приборах.
Для моделей местности, используемых в тренажерах, в зависимости от требований можно использовать уровни LoD2 и LoD3. Следует отметить, что достаточно часто в тренажерных системах трехмерная модель местности должна соответствовать территории конкретного населенного пункта. Таким образом, важно смоделировать не только особенности геометрии и цвета отдельных объектов, но и общую трехмерную структуру, соответствующую географической карте. Подобные трехмерные модели местности конкретных населенных пунктов используются в автомобильных и авиационных тренажерах, тренажерах общественного транспорта и военной техники, тренажерах для полиции и МЧС. 1.3 Системы реконструкции трехмерных сцен
Конечной целью многих подходов является автоматизация процесса реконструкции трехмерных сцен. Однако на практике достичь полной автоматизации процесса проблематично. Существуют следующие системы создания трехмерных моделей местности с использованием различных технологий (табл. 1.2) [16, 34, 103, 123, 139]: - системы автоматизированного создания трехмерных моделей; - системы автоматической генерации трехмерных моделей.
Для создания трехмерных моделей объектов местности традиционно применяются системы трехмерного моделирования, позволяющие создавать геометрию при помощи типовых операций в автоматизированном режиме. К основным группам операций в CAD-системах относятся: функции создания базовых примитивов и булевы операции, 2.5D-моделирование, функции сопряжения и поднятия, функции моделирования границ, объектно-ориентированное моделирование. В подобных системах моделирование происходит в интерактивном режиме. Трехмерные модели зданий часто получают методом «выдавливания» контуров. Наложение текстур выполняется с использованием фотографий объектов. К наиболее известным системам геометрического моделирования относятся «3D StudioMax» («Autodesk», США), AutoCAD («Autodesk», США), «Компас» («Аскон», Россия). К достоинствам подхода относится: - возможность создания трехмерных моделей с высоким уровнем детализа ции (LoD4); - относительно невысокая стоимость систем геометрического моделирования. Недостатки автоматизированного моделирования: - высокая трудоемкость (недели и месяцы); - необходимость привлечения квалифицированных специалистов в области трехмерного моделирования.
Разработка схемы процесса реконструкции 3D-моделей зданий на основе спутниковых снимков и априорной информации
В общем виде построение трехмерной модели на основе спутниковых снимков состоит из следующих этапов [56]: - предварительная обработка снимков; - ориентирование снимков; - эпиполярная ректификация снимков; - построение цифровой модели местности; - ортокоррекция изображений; - трехмерная реконструкция объектов. Предварительная обработка снимков включает в себя радиометрическую кор рекцию искажений, вызванных разницей в чувствительности отдельных ПЗС датчиков.
Ориентирование снимков осуществляется в интерактивном режиме с использованием коэффициентов рационального многочлена (RPC – Rational Polynomial Coefficients) и наземных точек привязки (GCP – Ground Control Points) [66, 140]. Метод, основанный на коэффициентах рационального многочлена, был принят для обработки спутниковых данных в компаниях DigitalGlobe и GeoEye [41].
Коэффициенты рациональных полиномов (RPC) используются для строгого сенсорного ориентирования поставщиком данных, которое позволяет соотнести снимок и наземные координаты с помощью полиномов. Используются полиномы третьей степени, поэтому данные ориентирования можно представить с помощью 80 коэффициентов.
После получения изображений и RPС-коэффицинетов выполняется взаимное ориентирование снимков. Связующие точки для каждой пары измеряются вручную оператором. Общее правило для измерения связующих точек заключается в выборе точки на четко определенных участках местности (пересекающие линии, дорожные знаки и т. д.). Наземные точки привязки должны быть равномерно распределены на изображении.
Модель с использованием коэффициентов рационального многочлена и наземных точек привязки имеет вид: P1(X,Y,Z)- Pi3(X,Y,Z) Xti = ; 7-- = ; (2.6) Pi2(X,Y,Z) Pi4(X,Y,Z) Pn (X, Y, Z )=a1+ a2Y + a3X + a4Z + a5XY + a6YZ + a7XZ + a8Y2 + a9X2 + + a10Z2 + +a11XYZ + a12Y3 +a13YX2 + a14YZ2 + a15Y2 X + a16X3 + a17XZ2 + (2.7) + a18Y2Z + a19X2Z + a20Z3, где X--, Y-- - координаты изображения; X, Y, Z - координаты наземных точек привязки. При выполнении ректификации принимается, что эпиполярные линии параллельны между собой [86]. Для эпиполярной ректификации стререоизображений выполняется следующая последовательность действий. - находятся соответствия между особенностями изображений. При сопоставлении удаляются ложные соответствия, называемые «выбросами»; полученные соответствия отображаются линиями; к изображениям применяются аффинные преобразования для того, чтобы эпиполярные линии были ориентированы горизонтально.
Для нахождения преобразований используется фундаментальная матрица, которая содержит 5 ненулевых элементов [71]: где X и X - точки левого и правого изображений, между которыми найдено соот ветствие Параметры матрицы, находятся путем вычисления собственного вектора с наименьшим значением [86]: FAE = 0, E = (-d, c,0) и FA E = 0, E = (-b, a,0) (2.9) Полученные результаты используются для матриц поворота левого и правого изображений:
Построение цифровой модели местности осуществляется на основе стереоизображений. Основными проблемами при построении цифровой модели местности является низкая скорость существующих алгоритмов и некорректная обработка сла-ботекстурированных областей.
Ортокоррекция представляет преобразование снимка в ортогональную проекцию и устранение искажений, вызванных рельефом, условиями съемки и типом камеры. Ортокоррекция снимков осуществляется с использованием коэффициентов рационального многочлена и цифровой модели местности.
Трехмерная реконструкция объектов выполняется на основе данных цифровой модели местности и ортотрансформированных изображений.
Многие из этапов трехмерной реконструкции на данный момент выполняются в автоматизированном режиме или имеют некоторые недостатки при реализации. Предлагается разработать новые алгоритмы для трехмерной реконструкции сцен: - алгоритм нахождения соответствий на изображениях, позволяющий уменьшить количество ошибок при сопоставлении особенностей; - алгоритм вычисления карты высот на основе стереоизображений, позволяющий быстро обрабатывать области однородной закраски на снимках; - алгоритмы обнаружения зданий на спутниковых стереоизображениях; - алгоритмы трехмерной реконструкции моделей зданий уровня LOD2 на основе спутниковых изображений. Таким образом, предлагаемый процесс реконструкции трехмерных сцен для транспортных тренажеров будет иметь следующий вид (рис. 2.4.).
Исследование алгоритма обнаружения зданий на спутниковых изображениях с использованием априорной информации
Для выделения объектов необходимо сгруппировать регионы, имеющие определенные цветовые характеристики и значения высоты. На предыдущих этапах изображение было сегментировано на основе минимального покрывающего дерева. Каждому сегменту были присвоены следующие атрибуты: значение высоты, принадлежность к области растительности, к затененной области или остальным объектам сцены.
Следует отметить, что области растительности могут быть представлены деревьями, кустарниками и травяным покровом. При этом области травяного покрова имеют нулевую высоту. Здания имеют ненулевую высоту. Цветовые характеристики крыш зданий в большинстве случаев отличаются от цветовых характеристик растительности и теней. В данном случае подразумеваются, что здания не находятся в теневой области. Для уменьшения влияния теней на процесс реконструкции необходимо выбирать снимки с минимальной площадью областей затенения. Однако для реконструкции трехмерных моделей зданий на предварительном этапе необходимо исключить из рассмотрения области теней.
Разработанный алгоритм группировки регионов использует сегментацию на основе спектральной теории графов. Каждый регион имеет свой вес, определяемый цветовыми и трехмерными характеристиками. Изображение представляет собой неориентированный взвешенный граф, узлами которого являются сегменты изображения (рис. 2.13) [57].
Весами вершин графа являются числа, определяющие принадлежность к некоторому классу (табл. 2.2). Для разделения регионов на кластеры используется метод разрезов на графах. Преимуществом предлагаемого подхода по сравнению с известным методом нормализованных разрезов является высокая скорость обработки, так как в процессе сегментации участвуют не отдельные пиксели, а сегменты изображения [55, 146]. Ws(i,j) Ts 50 Сегментация на основе теории графов предоставляет широкие возможности для решения практических задач. Подходы на основе графов представляют элементы изображений в виде структур и позволяют более гибко осуществлять вычисления за счет использования информации о связях между объектами. Подобные методы сегментации изображений основаны на разбиении графа на подграфы, которые представляют собой некоторый объект на изображении.
Графы можно представить с помощью матрицы смежности, степенной матрицы и матрицы Лапласа. Матрица смежности взвешенного графа - это квадратная матрица W, в которой каждый элемент равен весу ребра, соединяющей ее вершины.
Также для задания графа используется матрица Лапласа, которая определяется следующим образом. Вначале строится степенная матрица D, диагональные элементы которой равны степеням вершин. Степень вершины dv равна сумме весов ребер w(u,v), инцидентных этой вершине. Ненормализованная матрица Лапласа L вычисляется по формуле: L = D -W [63, 76]. Для сегментации изображений предлагается использовать разрезы на графах [121].
Если множество вершин V неориентированного графа G разбито на два непересекающихся множества А и В (A V, В является дополнением А относительно V), то множество ребер графа G, одни концевые вершины которых лежат в А, а другие в В, называется разрезом графа.
Величина разреза графа G - это сумма весов всех ребер графа G между парами вершин и и v, одна из которых лежит в А, а другая в В: cut (А, В) = w(u,v), (2.33) иєА vsB где w(u,v) - вес ребра между вершинами и и v. Широко используются методы нормализованных разрезов графов. Величина нормализованного разреза в этом случае определяется следующим образом: cut(A,B) cut(A,B) Ncut(A,B) = Л , (2.34) assoc(A, V) assoc(B, V) где assoc(A, V)= w(u,v) - общий вес ребер между вершинами подграфа А и и=А v=V графа V; assoc(B, V) = w(u,v) - общий вес ребер между вершинами подграфа В и=В v=V и графа V. Нахождение минимума Ncut(A, В) может быть рассмотрено с использованием собственных значений на основе спектральной теории графов: yT(D-W)y min Ncut(A,B) = min ; (2.35) У Dy У є 1,-}; 0 b 1; ут D1 = 0, где D - степенная матрица графа; W - весовая матрица смежности графа, Однако данная задача являетcя NP-сложной. Поэтому для упрощения задачу сводят к нахождению собственных значений на основе выражения [121]: (D - W )у = XDy, (2.36) где Я - собственные значения. Пусть W є Rnxn весовая матрица смежности для п сегментов, где W описывает близость сегментов, описываемых мерами различия xt и х..
Алгоритм сегментации на основе спектрального разбиения графов имеет вид [146]. Шаг 1. Строится взвешенный граф на основе выделенных сегментов исходного изображения. Каждый регион на основе его отнесения к некоторому классу имеет меру различия xt. Шаг 2. Рассчитываются матрицы W и D : если и, v смежные вершины; (2.37) хi - X W(u,v) = ехр У 2 т2 0, в другом случае, где о - коэффициент, который регулирует степень взаимодействия между регионами. п Д.. = Х г/ . (2.38) 7=1 Шаг 3. Из выражения (D - W)у = ADy находятся собственные векторы с наименьшими собственными значениями. Шаг 4. На основе вектора со вторым наименьшим собственным значением вычисляется разрез графа. Шаг 5. Выполняется рекурсивное разбиение сегментированных областей. В разработанном алгоритме значение коэффициента а было установлено равным 50, так как мера различия между регионами находится в пределах от 10 до 50.
Методика реконструкции трехмерных сцен с использованием разработанной системы
Система реконструкции трехмерных моделей сцен разработана в среде программирования Visual Studio 10. Использована платформа PC с операционной системой Windows 7. При реализации системы был использован интерфейс прикладного программирования DirectX. Система реконструкции состоит из следующих компонентов: модуля эпиполярной ректификации, модуля вычисления цифровой модели местности, модуля обнаружения зданий, модуля распознавания крыш зданий, модуля трехмерной реконструкции (рис. 4.1) [56, 58].
Входными данными для системы являются спутниковые изображения высокого разрешения, параметрические модели крыш, база данных типовых текстур. Выходными данными системы являются трехмерные модели зданий уровня LOD2. Диалоговые окна разработанной системы приведены на рисунках 4.2-4.6.
Методика реконструкции трехмерных сцен с использованием разработанной системы Методика реконструкции трехмерных сцен с использованием разработанной системы включает в себя следующие этапы [56]: - ориентирование стереопары космических снимков; - формирование карты высот; - ортотрансформирование снимков; - выделение зданий и растительности на снимках; - реконструкция и размещение 3D-моделей зданий; - наложение текстур из базы данных системы на фасады реконструируемых зданий; - размещение 3D-моделей деревьев в областях, которые определены на этапе выделения объектов на изображениях; - проверка синтезированной сцены оператором и коррекция неправильно реконструируемых объектов.
Ориентирование и ортотрансформирование стереопары космических снимков выполняется с использованием системы ENVI (ITT Visual Information Solutions, США). Для ориентирования используются от 5 до 7 опорных точек. В системе ENVI вычисление диспаритета происходит с помощью корреляционной функции и скользящего окна размером от 5x5 до 15x15 пикселей. Поэтому вычисление карты высот осуществляется на основе разработанного алгоритма.
Для построения моделей местности в зависимости от требований предполагается использовать уровни LoD2 и LoD3. Таким образом, важно реконструировать общую трехмерную структуру, соответствующую географической карте. Так как по стереоснимкам невозможно получить модель уровня LOD3, то уровень LOD2 может быть «доработан» системой в соответствии с некоторой априорной информацией об объекте.
Параметрические модели используются для генерации и оценки гипотез о геометрии объектов. Гипотезы проверяются путем сравнения геометрии шаблонов с объектами, выделенными на спутниковых снимках. База данных параметризованных трехмерных моделей содержит шаблоны объектов и соответствующие им геометрические гистограммы. Параметризованные модели местности представляют собой совокупность примитивов, заданных узловыми точками, координаты которых могут быть рассчитаны в соответствии с определенными размерами. В этом случае особое значение приобретают параметры и взаимосвязь элементов.
Трехмерные модели местности описываются на основе граничного представления (Boundary representation). При этом подходе трехмерная модель состоит из элементов, которые создают границы объекта. Такими элементами являются поверхности, ребра, вершины. Одновременно хранится топологическая информация, которая показывает, как элементы связаны друг с другом.
На основе определенных параметров расположения, контура здания и формы крыши реконструируется геометрическая модель уровня LOD 2. Следует отметить, что с использованием спутниковых изображений невозможно определить параметры текстуры фасадов зданий. Поэтому при формировании моделей используется априорная информация (Табл. 4.1).
Высота здания Площадь здания Тип крыши Изображение фасада м 100 м Любая Панельный, кирпичный и оштукатуренный фасады 10 м Любая Любая Бревенчатый, кирпичный, оштукатуренный, сайдинговый фасады Подразумевается, что зданиям городской застройки, превышающим по высоте 10 м, соответствуют текстуры панельных, кирпичных и оштукатуренных фасадов. Зданиям, высота которых не превышает 10 м, соответствуют текстуры бревенчатых, кирпичных, оштукатуренных и сайдинговых фасадов. Создана база данных текстур на основе цифровых изображений фасадов зданий. Каждая текстура отнесена к кирпичному, панельному, сайдинговому, бревенчатому или оштукатуренному типу фасада. Таким образом, каждому типу здания соответствует несколько текстур. При выборе текстур на основе правил из таблицы 4.1. на каждую модель здания накладывается изображение. Каждому типу текстур соответствует несколько изображений. Изображения могут добавляться в базу данных.
После реконструкции зданий осуществляется размещение трехмерных моделей деревьев в соответствующих областях. На заключительном этапе проводится визуальная проверка сцены оператором. Происходит коррекция неправильно реконструируемых объектов. Коррекция может выполняться в любой доступной системе автоматизированного проектирования.
Была выполнена трехмерная реконструкция центра г. Мурома. Для реконструкции трехмерных сцен использовались стереоснимки спутника GeoEye1 (рис. 4.7). Стереопары получены с одного витка орбиты. Разрешение снимков составляет 0.5 м.