Методы трехмерной реконструкции на основе разрезов на графах

• Автор: Лемпицкий, Виктор Сергеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 127 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

ГЛАВА 1. Разрезы на графах в компьютерном прении обзор

1.1. Минимальный разрез на граете

1.2. Разрезы па графах и глобальная оптимизация

1.3. Разрезы на графах и минимальные поверхности. Схема БойковаКолмогорова

ГЛАВА 2. Геометрическая реконструкция на основе трехмерных данных

2.1. Введение.

2.2. Существующие методы решения задачи

2.3. Вывод функционала.

2.3.1. Представление точечных данных.

2.3.2. Учет априорных предположений
2.3.3. Представление данных занятости
2.4. Глобальносуженная оптимизация
2.4.1. Лемма глобальной оптимальности сужения
2.4.2. Глобальносуженная оптимизация алгоритм
2.5. Практическая реализация и эксперименты
2.5.1. Иерархический алгоритм
2.5.2. Извлечение поверхности
2.5.3. Лазерное сканирование. Эксперименты.
2.5.4. Пассивное стерсосоиоставление. Эксперименты
2.5.5. Анализ численных характеристик
2.6. Заключение
ГЛАВА 3. Геометрическая реконструкция на основе наборов изображений
3.1. Введение
3.2. Существующие методы решения задачи
3.3. Вывод функционала
3.3.1. Ориентированная фотосостоятелыюсть
3.4. Формулировка функционала
3.5. Глобальная оптимизация
3.5.1. Дискретизация множества поверхностей
3.5.2. Построение графа
3.5.3. Выбор комплекса
3.6. Преодоление эффекта спрямления .
3.7. Результаты экспериментов
3.8. Заключение
ГЛАВА 4. Реконструкция текстур трехмерных моделей па основе наборов изображений
4.1. Введение и обзор предшествующих работ
4.2. Мозаичная сшивка на основе разреши па графах
4.2.1. Формулировка энергии
4.2.2. Оптимизация энергии.
4.3. Сглаживание швов
4.3.1. Сглаживание швов на многообразии.
4.3.2. Реализации на треугольной сетке
4.4. Результаты экспериментов
4.5. Заключение.
ЗАКЛЮЧЕНИЕ
БЛАГОДАРНОСТИ
ВВЕДЕНИЕ


Такие методы сводят оптимизационную задачу к эквивалентной задаче поиска минимального разреза на некотором графе, для которой существуют высокоэффективные алгоритмические решения . Впервые использование минимальных разрезов на графах в задаче компьютерного зрения было предложено в конце х Д. Григом и соавторами в для задачи обработки чернобелых 1битовых изображений. Возможно, изза невысокой актуальности рассмотренной задачи публикацияпрошла относительно незамеченной. Только но прошествии почти лег, в работах . Бойкова, О. Векслер, X. Ишикавы, Д. Гейгера, В. Колмогорова, а затем и многих других исследователей оптимизация энергии с помощью минимальных разрезов на графах была использована для решения более актуальных задач компьютерного зрения. Так, методы, основанные на такой оптимизации, были предложены для сегментации двух и трехмерных изображений , , 1б, стереосопоставления близких изображений в т. Отметим, что работы ,, , , , также производят реконструкцию двух или трехмерной поверхности в контексте задач сегментации, узкого стерео и пересечения нечетких силуэтов. При этом в данных работах использование минимальных разрезов па графах позволяет в каждом конкретном случае найти глобальный минимум функционала. Для более общих случаев, в работах , предложена схема для нахождения поверхностей, представляющих собой глобальные минимумы широкого класса непрерывных функционалов. Во всех этих работах непрерывные энергии аипроксими
руотся энергиями дискретных переменных дисщютгзация энергии после чего поиск минимума сводится к поиску минимального разреза на графе. Заметим, что для задач, в которых с помощью разрезов па графах удается находить не глобальные, а лишь локальные минимумы , , , такие минимумы на практике имеют гораздо меньшую энергию, чем минимумы, получаемые в результате локальной оптимизации. Теоретически в даны оценки сверху для энергии локальных минимумов, находимых с помощью разрезов на графах. Практически же было показано, что эти минимумы очень близки к глобальным, и зазор между ними и глобальными минимумами не сказывается на эмпирическом визуальном качестве соответствующих результатов . Результат оптимизации зависит только от формулировки дискретной энергии. Результат не зависит от начального приближения. Облегчен анализ и коррекция случаев неудачной работы неудачная работа всегда означает неудачный выбор энергии. Коррекция осуществляется перенастройкой параметров энергии. Методы оптимизации, основанные на разрезах па графах, также сравнивались со стохастическими методами оптимизации, такими как метод искусственного отжига англ. В результате сравнений было показано, что методы, использующие разрезы па графах, производят оптимизацию на несколько порядков быстрее . Отмстим, что многие методы, основанные па разрезах па графах, являются достаточно эффективными для применения в интерактивных системах , , . Отметим, что наряду с минимальными разрезами на рисках, ряд исследователей напр. Однако в виду отсутствия эффективных алгоритмов для вычисления таких разрезов, нормализованные разрезы получили в компьютерном зрении ограниченное распространение по сравнению с минимальными разрезами. В дальнейшем в работе рассматриваются именно минимальные разрезы на графах, причем слово минимальные зачастую опускается. Получение реалистичных виртуальных моделей путем трехмерной реконструкции моделей является высокоактуальиой проблемой, имеющей множество практических применений. Эвристические подходы к задачам трехмерной реконструкции в реальных условиях характеризуются низким качеством результатов и низкой стабильностью. Предложенные методы геометрической трехмерной реконструкции, основанные на энергетической оптимизации, добиваются лучших результатов. В то же время применение этими методами локальной непрерывной оптимизации приводит к проблеме застревания в многочисленных локальных минимумах энергий и зависимости от начального приближения. Методы дискретной оптимизации на основе разрезов на графах, предложенные для таких задач компьютерного зрения как сегментация, узкое стерео, сшивка плоских изображений и пр.