Системы упрощения триангуляционной сетки для методов трехмерной реконструкции

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«Дальневосточный федеральный университет»

 

ШКОЛА ЕСТЕСТВЕННЫХ НАУК

 

Кафедра прикладной математики, механики, управления

и программного обеспечения

Тимошишина Алина Дмитриевна

 

 

СИСТЕМЫ УПРОЩЕНИЯ ТРИАНГУЛЯЦИОННОЙ СЕТКИ ДЛЯ МЕТОДОВ ТРЕХМЕРНОЙ РЕКОНСТРУКЦИИ

 

ДИПЛОМНАЯ РАБОТА по основной образовательной программе подготовки специалистов по направлению 010400 – прикладная математика и информатика

 

 

Студент гр. Б8426         ________________                                                                      (подпись) Научный руководитель ____ к.т.н.       ____                                                                     (должность,  ученое звание) _______________       _____А.П.Кудряшов_               (подпись)                                               (и.о.ф) «______»________________ 20    г.
Защищена в ГАК с оценкой ______________   Секретарь ГАК ____________     _________________            подпись                              И.О.Фамилия   «_____» ________________ 20   г.		«Допустить к защите» Заведующий кафедрой _д.ф.-м.н., профессор                                                                        ( ученое звание) ______________    ____А.А. Буренин_______               (подпись)                                                (и.о.ф) «______»________________ 20   г

 

 

 

г. Владивосток

20  _

 

Оглавление

 

0. Введение…………………………………………………………….………….2
1. Глава 1. Обзор, основные положения………………………..……..….…....6

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

1.2. Особенности и проблемы триангуляции………………………….…..11

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

2. Глава 2. Рассмотрение существующих методов оптимизации……..……16

2.1. Упрощение триангуляции…………………………………………..…..16

1. Алгоритмы триангуляции……………………………………….....16
2. Структуры данных триангуляции………………………………....21

2.2. Метод квадратичной ошибки Гарланда и Хекберта…………………..24

2.2.1. Основной алгоритм……..……………………………………….....24

2.2.2. Квадратичная ошибка…..……………………………………….....25

2.2.3. Интерпретация квадриков……………………………………........27

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

0. Глава 3. Практическая часть…………………………………………………29

3.1. Вводная часть…………………………………………………………….29

 3.2. Постановка задачи……………………………………………................29

 3.3. Оптимизация данных…………………………….………….………….31

 3.4. Методика упрощения триангуляционной сетки……………….…….33

 3.5. Пример оптимизации и упрощения…………………………….……..37

3.6. Выводы по главе………………………………………………….……..40

1. Заключение…………………………….….……………………..….….…….41
2. Литература……………………………………………………………………42

 

 

 

 

 

 

 

 

Введение

 

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

 

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

 

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

 

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

 

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

 

Цель работы

 

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

 

Для достижения указанной цели решаются следующие задачи:

 

• Анализ существующих методов и алгоритмов оптимизации 

     триангуляционной  сетки

•  Разработка методики структурирования  и оптимизации 

     полученных  данных сетки

•  Разработка методики упрощения ранее структурированной сетки

     полигонального  объекта

•  Программная реализация методов и алгоритмов

 

 

 

 

 

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

 

Приведённая работа состоит из введения, 3 глав, заключения и списка литературы. Содержание работы изложено на 38 страницах. Список литературы включает 15 наименований. В работе содержится 18 рисунков и 2 таблицы.

 

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

 

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

 

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

 

Сам процесс реконструкции может быть выполнен пассивными, либо активными методами. Активные методы активно взаимодействуют с восстанавливаемым объектом, механически или радиометрически. Простым примером механического подхода является применение глубиномера (или щупа) для измерения расстояния до вращающегося объекта, установленного на оборотный столик. Более часто применяемые, радиометрические методы, испускают излучение на объект, а затем замеряют его отраженную часть. Примерами могут служить движущиеся источники освещения, лазерные дальномеры и прочие методы трехмерного сканирования.

 

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

 

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

 

 

 

Рис. 1.1. Общая схема пассивной реконструкции трехмерных объектов

 

Рассмотрим пункты более подробно.

 

 

 

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

 

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

 

Отслеживание точечных особенностей

 

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

 

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

 

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

 

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

 

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

 

 

Триангуляция

 

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

 

Рис. 1.2. Триангуляция 100 точек на плоскости

 

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

 

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

 

 

 

 

Построение трехмерной модели

 

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

 

Текстурирование

 

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