WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 | 3 | 4 |
Московский Государственный Университет им. М. В. Ломоносова на правах рукописи Лемпицкий Виктор Сергеевич МЕТОДЫ ТРЕХМЕРНОЙ РЕКОНСТРУКЦИИ НА ОСНОВЕ РАЗРЕЗОВ НА ГРАФАХ Специальность 05.13.11 ”Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей” АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва 2007 Работа выполнена на кафедре вычислительной математики механикоматематического факультета Московского Государственного Университета им.

М.В. Ломоносова.

Научный руководитель доктор физико-математических наук, профессор Михалев Александр Васильевич Официальные оппоненты доктор технических наук, профессор, член-корреспондент РАН Рябов Геннадий Георгиевич доктор физико-математических наук, старший научный сотрудник Галактионов Владимир Александрович Ведущая организация Научно-исследовательский институт системных исследований РАН (НИИСИ РАН) Защита диссертации состоится ” ” 2007 г. в час. на заседании диссертационного совета К 501.001.11 при Московском государственном университете имени М.В.Ломоносова по адресу:

119991, Москва, Ленинские горы, д.1, стр.4, Научно-исследовательский вычислительный центр МГУ им. М.В. Ломоносова (НИВЦ МГУ), конференц-зал.

С диссертацией можно ознакомиться в библиотеке НИВЦ.

Автореферат разослан ” ” 2007 г.

Ученый секретарь диссертационного совета к. ф.-м. н. Суворов В.В.

1 ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы работы.

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

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

Цели работы.

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

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

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

Научная новизна.

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

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

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

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

На защиту выносятся следующие основные результаты :

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

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

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

Практическая значимость работы.

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

• шумы и выбросы сканирования, пропуски (области отсутствия данных), существенные вариации плотности точечных измерений в случае реконструкции на основе трехмерных данных;

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

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

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

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

Результаты работы были представлены в ходе следующих докладов: на конференции IEEE Conference on Computer Vision and Pattern Recognition CVPR2007 (США, Миннеаполис, июнь 2007); на конференции European Conference on Computer Vision ECCV-2006 (Австрия, Грац, май 2006); на конференции British Machine Vision Conference BMVC-2006 (Великобритания, Эдинбург, сентябрь 2006); в виде публичной лекции Microsoft Research Public Lecture (Великобритания, Кембридж, декабрь 2006); на конференции “ГрафиКон-2005” (Академгородок, июнь 2005 г); на международном семинаре по компьютерной алгебре и информатике, посвященном 30-летию ЛВМ МГУ (Москва, ноябрь 2005); на семинаре по машинной графике и обработке изображений (ВМиК МГУ, Москва, март 2007); на семинаре “Научно-техническая визуализация” (НИВЦ МГУ, Москва, март 2007);

на заседании кафедры вычислительной математики механико-математического факультета МГУ (Москва, апрель 2007); в ходе “Ломоносовских чтений-2007” (МГУ, Москва, апрель 2007). Основные результаты работы изложены в восьми научных публикациях.

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

Диссертация состоит из введения, четырех глав, заключения и списка использованной литературы. Содержание работы изложено на 127 страницах. Список литературы содержит 97 наименований. В работе имеются 35 рисунков и 2 таблицы.

Благодарности.

Автор выражает огромную благодарность проф. А.В.Михалеву за осуществление научного руководства, проф. Ю.Ю. Бойкову за консультации и научное соруководство, с.н.с. Д. В. Иванову за поддержку и помощь в подготовке к защите. Автор также признателен с.н.с. Е. П. Кузьмину, асп. Э. Делонгу, проф. О.

Векслер, асп. О. Жуану, д-ру К. Ротеру за обсуждения и полезные комментарии.

СОДЕРЖАНИЕ РАБОТЫ Во введении обосновываются цели данной работы, ее актуальность, научная новизна и практическая значимость; дается краткий обзор методов геометрической реконструкции, а также областей применения минимальных разрезов на графах в компьютерном зрении. Также во введении кратко описывается структура работы.

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

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

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

Первая глава также носит обзорный характер и посвящена предшествующим работам. В данной главе дается формулировка задачи нахождения минимального разреза на графе, приведенная далее. Рассмотрим направленный граф G. Выделим из множества его вершин две и обозначим их S и T (в дальнейшем эти вершины называются терминалами или терминальными). Каждой дуге графа припишем действительный неотрицательный вес wi. Подобный граф с выделенными терминалами и взвешенными дугами называют сетевым графом. В дальнейшем под словом “граф” понимается сетевой граф. ST-разрезом графа (далее просто разрезом) называется такое разбиение множества всех вершин на два подмножества, что терминалы S и T находятся в разных подмножествах (называемых соответственно S-компонентой и T -компонентой разреза). Будем использовать обозначения VS и VT для обозначения компонент и [VS, VT ] для обозначения разреза. Для данного разреза назовем дугу разрезанной, если ее началом служит Рис. 1. Пример исходных данных для задачи, рассматриваемой в главе 2. Слева фото исходного объекта. В середине исходные данные в виде двух лазерных сканов. Стрелки показывают направления сканирования для точек каждого скана, используемое в последующих экспериментах в качестве грубой оценки нормали к поверхности. Справа увеличенное изображение набора точек, полученных в результате лазерного сканирования. Показан край поверхности (хорошо различимы шумы и выбросы).

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

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

Во второй главе рассматривается задача геометрической реконструкции на основе трехмерных измерений. Предполагается, что трехмерные данные заданы в виде набора слабоориентированных точечных измерений поверхности {Ai, nA }, i где Ai – положение точки в пространстве в мировой системе координат, а nA – i грубая, с точностью до 90 оценка внешней нормали к поверхности в этой точке. Подобные трехмерные данные могут быть получены в результате нескольких проходов лазерного сканирования с последующей регистрацией сканов (рис. 1) или других фотограмметрических процессов. Также предполагается задание в мировой системе координат ограничивающего параллелепипеда B, содержащего внутри себя искомую поверхность.

Задача геометрической реконструкции заключается в восстановлении внутри B на основе подобных данных поверхности (заданной, например, в виде треугольной сетки). Желательными свойствами метода реконструкции являются 1) устойчивость к шумам, выбросам и пропускам т.е. факторам, присущим большинству реальных наборов данных; 2) топологическая корректность, т.е. замкнутость (“водонепроницаемость”) поверхности; 3) возможность эффективной обработки данных высокого разрешения.

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

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

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

Pages:     || 2 | 3 | 4 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»