Методы трехмерной реконструкции на основе разрезов на графах тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Лемпицкий, Виктор Сергеевич

• Лемпицкий, Виктор Сергеевич
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Лемпицкий, Виктор Сергеевич

ВВЕДЕНИЕ

ГЛАВА 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. Анализ численных характеристик.

Введение диссертации (часть автореферата) на тему «Методы трехмерной реконструкции на основе разрезов на графах»

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

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

3.3.1. Ориентированная фотосостоятельпость . . . . . . 65

3.4. Формулировка функционала.69

3.5. Глобальная оптимизация . .70

3.5.1. Дискретизация множества поверхностей.72

3.5.2. Построение графа.74

3.5.3. Выбор комплекса .75

3.6. Преодоление эффекта спрямления.77

3.7. Результаты экспериментов.81

3.8. Заключение.84

ГЛАВА 4. Реконструкция текстур трехмерных моделей па основе наборов изображений 87

4.1. Введение и обзор предшествующих работ.88

4.2. Мозаичная сшивка на основе разрезов на графах.92

4.2.1. Формулировка энергии.93

4.2.2. Оптимизация энергии.95

4.3. Сглаживание швов.99

4.3.1. Сглаживание швов па многообразии.100

4.3.2. Реализация па треугольной сетке.101

4.4. Результаты экспериментов .104

4.5. Заключение.111

ЗАКЛЮЧЕНИЕ 112

БЛАГОДАРНОСТИ 117

ВВЕДЕНИЕ

Виртуальные трехмерные модели объектов используются во многих областях человеческой деятельности, таких как промышленный и архитектурный дизайн, компьютерные игры и кинематографические спецэффекты, виртуальные музеи-храпилища культурных артефактов, медицина и косметология, биоидентификация, видеотелекопферепции и пр. Создание реалистичных трехмерных моделей является, таким образом, вопросом высокой актуальности. В настоящее время, создание реалистичных моделей осуществляется, как правило, с помощью "ручного" кропотливого труда высококвалифицированных дизайнеров в интерактивных средах ЗД моделирования ['2, 1].

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

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

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

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

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

В качестве альтернативы эвристическим методам в конце 9U-X годов в работах О. Фожора, Р. Керивепа, О. Уайтекера [35, 94] для задач геометрической реконструкции были предложены методы, основанные па энергетической оптимизации. В общем виде, такие методы определяют на множестве; поверхностен внутри В некоторый.функционал (энергию), оценивающий качество поверхности относительно наблюдаемых данных. В результате оптимизации функционала находится поверхность, наилучшим (с точки зрения функционала) образом, объясняющая данные, которая и служит ответом к задаче восстановления поверхности. Помимо соответствия наблюдаемым данным, предлагаемые функционалы содержат регуляризирующие члены, что и обеспечивает устойчивость и высокое качество результатов таких методов при наличии шумов, выбросов и неопределенностей. Отметим, что в ряде работ (например [94]) подобный подход трактуется статистически: реконструкция па основе оптимизации регуляризироваииых функционалов представляется как нахождение поверхности максимальной апостериорной вероятности в рамках байесовского подхода.

Все функционалы, предложенные для восстановления поверхностей, являются певыпуклыми и содержат большое количество локальных минимумов. Как следствие, вопрос выбора численных методов оптимизации играет ключевую роль. В работах [35, 94], также как и во многих последующих [96, 81, 44, 77, 34], оптимизация осуществлялась с помощью различных схем градиентного спуска в пространстве поверхностей. Большинство методов используют для этого схему, основанную на уровневых функциях (англ. level sets) [72]. В этой схеме множество поверхностей аппроксимируется конечномерным линейным пространством (при этом размерность пространства достигает десятков миллионов). Оптимизация начинается с задания начального приближения, которое затем модифицируется последовательными локальными изменениями, определяемыми направлением вектора градиента функционала. В результате модификации оптимизационный алгоритм находит минимум функционала. Такой локальный {непрерывный) подход к оптимизации обладает следующими недостатками:

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

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

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

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

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

Впервые использование минимальных разрезов на графах в задаче компьютерного зрения было предложено в конце 80-х Д. Григом и соавторами в [40] для задачи обработки черно-белых (1-битовых) изображении. Возможно, из-за невысокой актуальности рассмотренной задачи публикация-прошла относительно незамеченной. Только по прошествии почти 10 лет, в работах Ю. Войкова, О. Векслер, X. Ишикавы, Д. Гейгера, В. Колмогорова, а затем и многих-других исследователей оптимизация энергии с помощью минимальных разрезов на графах была использована для решения более актуальных задач компьютерного зрения. Так, методы, основанные па такой оптимизации, были предложены для сегментации двух- и трехмерных изображении [18, 19, 16|, стереосоиоставлепия близких изображений в т.ч. стереопар (т.п. узкое стерео) [23, 43, 24, 53, 54, 80, 26, 73, 64], реконструкции на основе пересечения нечетких силуэтов [87], склейки изображений и "текстурного синтеза [58, 11[, обработки полутоповых изображений [24, 25, 64], определения оптического потка (нолей смещений) [25, 64[.

Отметим, что работы [43, 18, 19, 87, 26, 73] также производят реконструкцию двух или трехмерной поверхности в контексте задач сегментации, узкого стерео и-пересечения нечетких силуэтов. При этом в данных работах использование минимальных разрезов на графах позволяет в каждом конкретном случае найти глобальный минимум функционала. Для более общих случаев, в работах [20, 51] предложена схема для нахождения поверхностей, представляющих собой глобальные минимумы широкого класса непрерывных функционалов. Во всех этих работах непрерывные энергии аппроксимируются - энергиями дискретных переменных (дискретизация энергии) после чего поиск минимума сводится к поиску минимального разреза па графе.

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

Таким образом, но сравнению с локальными (градиентными) методами оптимизации, использование оптимизации па основе разрезов на графах обладает существенных преимуществ:

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

• Облегчен анализ и коррекция случаев неудачной работы: неудачная работа всегда означает неудачный выбор энергии. Коррекция осуществляется перенастройкой параметров энергии.

Методы оптимизации, основанные па разрезах на графах, также сравнивались со стохастическими методами оптимизации, такими как метод искусственного отжига (англ. simulated annealing), которые потенциально также способны находить глобальные минимумы энергии [38, 15]. В результате сравнений было показано, что методы, использующие разрезы■ на.графах, производят оптимизацию па несколько порядков быстрее [25[. Отметим, что многие методы, основанные на разрезах на графах, являются достаточно эффективными для применения в интерактивных системах [19, 49, 45].

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

Резюмируя.вышесказанное, можно утверждать, что:

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

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

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

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

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

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

Вклад работы заключается в следующем:

1. Представлен новый метод геометрической реконструкции на основе трехмерных данных. Новизна метода заключается в использовании глобальной оптимизации, основанной на разрезах на графах. В рамках нового метода нами, во-первых, предлагается новый непрерывный: функционал, выгодно отличающийся от функционалов в предшествующих работах простотой, универсальностью, и тем, что его глобальный минимум ие является нулевой поверхностью. Во-вторых, нами предлагается для этого функционала новую схему глобальной оптимизации, основанную на разрезах па графах, которая позволяет найти глобальный минимум функционала па более высоком разрешении {т.е. используя более аккуратное дискретное приближение непрерывной энергии), чем схема [51]. Данный метод был представлен нами в [G1, 10].

2. Представлен новый метод геометрической реконструкции на основе наборов фотографий. В данном случае новизна метода таклсе заключается в использовании глобальной оптимизации, основанной на разрезах на графах. Для этой задачи нами, во-первых, предлагается новый непрерывный функционал, который в отличие от функционалов в предшествующих работах не требует наличия текущего решения для обработки закрытий. Поскольку вводимый нами функционал не может быть оптимизирован с помощью схемы[51], нами используется новая схема для поиска глобалыю-мшшмалыюй-поверхности внутри ограничивающего параллелепипеда, основанная па разрезах на графах, дуальных к комплексам (в предшествующих работах [48, 26] схожие схемы были предложены для поиска глобально-минимальных графиков над плоскими сегментами). Данный метод был представлен нами в [65, 9, 22].

3. Представлен новый метод к реконструкции текстуры на основе набора изобра-жсиий. Основным вкладом в данном случае является адаптация новейших методов, предложенных для сшивки плоских изоб-ра-лсеиий в [58, 75, И], к задаче реконструкции текстуры трехмерной модели. В частности, нами предлагается функционал, схожий с предложенными в [58, 11] для сшивки плоских изображений. Полученный функционал оптимизируется с помощью алгоритма о расширения, предложенного в [23] для марковских случайных полей. Данный алгоритм, основанный на разрезах на графах, находит локальный минимум энергии со значением энергии близким к глобальному минимуму. Данный метод был представлен нами в [62].

На защиту, таким образом, выносятся следующие положения:

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

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

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

Отметим, что идея применения разрезов ■■на-графах в задачах геометрической- реконструкции вызвала одновременный интерес у целого ряда исследователей: практически одновременно с нашими работами ([9] 2005 г, [65, 22, 60J - 2006 г, [61J - 2007 г) были предложены ряд альтернативных методов ([85] - 2005 г, [93) - 2005 г, и развивающие те же идеи работы [37, 89, 41, 42] - 2006 г). В связи с этим важно подчеркнуть основное различие между методами, предлагаемыми нами, и методами, основанными па [85, 93]: последние требуют некоторого начального приближении к поверхности (либо предоставляемого пользователем, либо получаемого в результате эвристик), и производят поиск поверхности в окрестности данного приближения. По сути, также; как и методы, основанные па непрерывной оптимизации, данные методы оптимизируют функционал локально, что приводит к все тем же недостаткам: зависимости от начального приближения и пониженной устойчивости. В то же время, методы, предлагаемые нами и для геометрической реконструкции на основе трехмерных данных и для геометрической реконструкции па основе набора изображений, основаны па глобальной оптимизации, результаты которых не зависят от начальных приближений.

Работа организована-следующим образом. Диссертация состоит из введения, четырех глав, заключения и списка использованной литературы. Содержание работы изложено па 127 страницах. Список литературы содержит 97 наименований. В работе имеется 35 рисунков и 2 таблицы. После; Введении па-ми дается краткий обзор ряда основных понятий и результатов, касающихся минимальных разрезов па графах и их применении в задачах компьютерного зренши, в главе 1. Новый материал диссертации излагается в последующих главах 2, 3 и 4, которые посвящены соответственно задаче; ге;е)ме:трнче;ской ре;-коиструкции па основе трехмерных данных (глава 2), задаче; геометрической, реконструкции па основе наборов фотографий (глава 3) и задаче режешетрук

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Лемпицкий, Виктор Сергеевич

ЗАКЛЮЧЕНИЕ

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

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

• метода геометрической реконструкции на основе трехмерных данных,

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

• метода реконструкции текстур на основе наборов двумерных изображений.

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

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

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

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

3. В главе 4 для задачи реконструкции текстуры па основе набора изображений предлагается новый функционал, минимизация которого позволяет получить оптимизированную мозаику текстурных фрагментов. Для данной мозаики предлагаемый функционал учитывает как локальное качество текстурных фрагментов, так и различимость швов между фрагментами. (Локальная) минимизация функционала может быть осуществлена с помощью разрезов на графах (алгоритм а-расширеиия [23]). Результатом оптимизации являются текстуры-мозаики со степенью детализации, сравнимой с исходными фотографиями. При наличии остаточных швов, такие швы могут быть устранены с помощью функций-добавок.

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

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

5. В главе 3 предлагается новая схема глобальной оптимизации, позволяющая находить минимальные поверхности внутри заданного объема, соответствующие более широкому классу (функционалов, чем предложенная ранее схема Бойкова-Колмогорова (вместе с тем, необходимо отмстить, что во многом сходная схема дискретной глобальной оптимизации для задачи поиска функций с минимальным графиком над плоским сегментом была предложена в предшествующих работах [48, 26[). Примером функционала, оптимизируемого с помощью новой схемы, по не оптимизируемого с помощью схемы Бойкова-Колмогорова, служит функционал, предложенный в работе для геометрической реконструкции на основе набора изображений. Очевидный интерес представляет применение повой схемы к другим оптимизационным задачам, связанным как с трехмерной реконструкцией так и с другими приложениями компьютерного зрения.

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

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

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

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

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

БЛАГОДАРНОСТИ

Я хотел бы выразить искреннюю признательность проф. Александру Васильевичу Михалеву (Московский Государственный Университет) за осуществление научного руководства.

Я также хотел бы выразить огромную благодарность проф. Юрию Войкову (Университет Западного Онтарио). Исследования, в ходе которых были достигнуты результаты, представленные в главах 2 и 3, были проведены иод его соруководством в рамках сотрудничества между Московским Государственным Университетом и Университетом Западного Онтарио. Кроме того, необходимо заметить, что программная библиотека [21] для поиска минимальных разрезов на графах, разработанная проф. Войковым совместно с проф. Владимиром Колмогоровым (Университетский Колледж Лондона), интенсивно использовалась при практической реализации алгоритмов.

Я очень признателен с.п.с. к.ф.-м.н. Денису Владимировичу Иванову (Московский Государственный Университет) за поддержку и помощь в подготовке к защите.

Я благодарен с.п.с. Евгению Павловичу Кузьмину (Московский Государственный Университет), асп. Эндрю Делонгу, проф. Ольге Векслер, асп. Оливье Жуану (Университет Западного Онтарио), д-ру Карстеиу Ротеру (Исследовательская Лаборатория Микрософт- Кембридж) за обсуждения и дискуссии, позволившие выработать новые идеи и улучшить изложение материала.

Список литературы диссертационного исследования кандидат физико-математических наук Лемпицкий, Виктор Сергеевич, 2007 год

1. 3D Studio Мах. www.autodesk.com/3dsmax.

2. Autodesk Maya, www.autodesk.com/maya.

3. Boujou. http://www.2d3.com/.

4. Middlebury Multiview Stereo Page, http://vision.middlebury.edu/mview/.

5. PhotoModeler close-range photogranimetry software. http://www.photomodeler.com/.

6. Scanalyze: a system for aligning and merging range data. http: / / graphics.stanford.edu/software/scanalyze /.

7. The Stanford 3D scanning repository. http://graphics.stanford.edu/ data/3Dscanrep/.

8. Д. Роджерс. Алгоритмические основы машинной графики. Мир, Москва, 1989.

9. В. Лемиицкий. Решение задачи трехмерной реконструкции по изображениям при помощи разрезов на графах. In Тезисы международного семинара по компьютерной алгебре и информатике, pages 7-8, 2005.

10. В. Лемиицкий. Минимальные разрезы на сетевых подграфах. Успехи Математических Наук, 62(4):15-166, 2007.

11. И. A. Agarwala, М. Dontcheva, М. Agrawala, S. М. Drucker, A. Colburn, В. Curless, D. Salesin, and М. F. Cohen. Interactive digital photomontage. ACM Trans. Graphics (SIGGRAPH), 23(3):294-302, 2004.

12. B. Appleton and H. Talbot. Globally minimal surfaces by continuous maximal flows. IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), 28(1):106-118, 200G.

13. A. Baumberg. Blending images for texturing 3d models. In British Machine Vision Conference (BMVC), 2002.

14. F. Bernardini, I. M. Martin, and H. E. Rushmeier. High-quality texture reconstruction from multiple scans. IEEE Trans. Vis. Comput. Graph., 7(4):318-332, 2001.

15. J. Besag. On the statisical analysis of dirty pictures. Journal of the Royal Statistical Society, 48:259-302, 1986.

16. A. Blake, C. R.other, M. Brown, P. Perez, and P. H. S. Torr. Interactive image segmentation using an adaptive gmmrf model. In Proc. European Conf. Computer Vision (ECCV), volume 1, pages 428-441, 2004.

17. E. Boros and P. L. Hammer. Pseudo-boolean optimization. Discrete Applied Mathematics, 123:155-225, 2002.

18. Y. Boykov and M.-P. Jolly. Interactive organ segmentation using graph cuts. In Proc. International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI), pages 276-286, 2000.

19. Y. Boykov and M.-P. Jolly. Interactive graph cuts for optimal boundary and region segmentation of objects in n-d images. In Proc. IEEE International Conf. Computer Vision (ICCV), pages 105-112, 2001.

20. Y. Boykov and V. Kolmogorov. Computing geodesies and minimal surfaces via graph cuts. In Proc. IEEE International Conf Computer Vision (ICCV), pages 26-33, 2003.

21. Y. Boykov and V. Kolmogorov. An experimental comparison of min-cut/max-fiow algorithms for energy minimization in vision. IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), 26(9): 1124-1137, 2004.

22. Y. Boykov and V. Lempitsky. From photohulls to photofiux optimization. In Proc. British Machine Vision Conference (BMVC), pages 1149-1158, 2006.

23. Y. Boykov, O. Veksler, and R. Zabih. Markov random fields with efficient approximations. In Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), pages 648-655, 1998.

24. Y. Boykov, О. Veksler, and R. Zabih. Fast approximate energy minimization via graph cuts. In Proc. International Conf. Computer Vision (ICGV'), pages 377-384, 1999.

25. Y. Boykov, 0. Veksler, and R. Zabih. Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), 23(11):1222—1239, 2001.

26. C. Buehler, S. J. Gortlcr, M. F. Cohen, and L. McMillan. Minimal surfaces for stereo. In Proc. European Conf. Computer Vision (ECCV) (8), pages 885-899, 2002.

27. J. C. Carr, R. K. Beatson, J. B. Cherrie, T. J. Mitchell, W. R. Fright, В. C. McCallum, and T. R. Evans. Reconstruction and representation of 3d objects with radial basis functions. In ACM Trans. Graphics (SIGGRAPH), pages 67-76, 2001.

28. L. Cohen and I. Cohen. Finite element methods for active contour models and balloons from 2-D to 3-D. In Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), pages 592-598, 2002.

29. B. Curless and M. Levoy. A volumetric method for building complex models from range images. In ACM Trans. Graphics (SIGGRAPH), pages 303- 312, 1996.

30. P. E. Debevcc, C. J. Taylor, and J. Malik. Modeling and rendering architecture from photographs: A hybrid geometry- and image-based approach. In ACM Trans. Graphics (SIGGRAPH), pages 11-20, 1996.

31. Y. Duan, L. Yang, H. Qin, and D. Samaras. Shape reconstruction from 3d and 2d data using pde-based deformable surfaces. In Proc. European Conf. Computer Vision (ECCV), pages 238-251, 2004.

32. C. R. Dyer. Volumetric scene reconstruction from multiple views. In L. S. Davis, editor, Foundations of Image Understanding, pages 469-489. Kluwer, 2001.

33. E. S. Е. Ofck and M. Werman. Multiresolution textures from image sequences. IEEE Computer Graphics and Applications, 17(2): 18-29, 1997.

34. L. Ford and D. Fulkerson. Flows in Networks. Princeton University Press, 1962.

35. Y. Furukawa and J. Ponce. Carved visual hulls for image-based modeling. In Proc. European Conf. Computer Vision (ECCV), volume 1, pages 564-577, 2006.

36. S. Geman and D. Geinan. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Trans. Pattern Anal. Machine Intell. (PAMI), 6(6):721-741, Nov. 1984.

37. M. Goesele, B. Curless, and S. M. Seitz. Multi-view stereo revisited. In Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR) (2), pages 2402-2409, 2006.

38. D. Greig, B. Porteous, and A. Seheult. Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society, 51(2):271-279, 1989.

39. A. Hornung and L. Kobbelt. Hierarchical volumetric multi-view stereo reconstruction of manifold surfaces based on dual graph embedding. In Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), volume 1, pages 503-510, 2006.

40. A. Hornung and L. Kobbelt. Robust reconstruction of watertight 3d models from поп-uniformly sampled point clouds without normal information. In Eurographics Symposium on Geometry Processing, pages 41-50, 2006.

41. H. Ishikawa and D. Geiger. Occlusions, discontinuities, and epipolar lines in stereo. In Proc. European Conf. Computer' Vision (ECCV) (1), pages 232-248, 1998.

42. M. Kazhdan, M. Bolitho, and H. Hoppe. Poisson surface reconstruction. In Eurographics Symposium on Geometry Processing, pages 61-70, 2006.

43. R. Kimrnel and A. M. Bruckstein. Regularized laplacian zero crossings as optimal edge integrators. Intern. Journal of Computer Vision (IJCV), 53(3):225-243, 2003.

44. D. Kirsanov and S. J. Gortler. A discrete global minimization algorithm for continuous variational problems. Technical report, Harvard CS Technical Report TR-14-04, 2004.

45. P. Kohli and P. H. S. Torr. Effciently solving dynamic inarkov random fields using graph cuts. In Proc. International Conf. Computer Vision (ICCV), pages 922-929, 2005.

46. V. Kolmogorov. Convergent tree-rcweighted message passing for energy minimization. IEEE Trans. Pattern Analysis and Machine Intelligence (PAM1), 28(10): 1568-1583, 2006.

47. V. Kolmogorov and Y. Boykov. What metrics can be approximated by geo-cuts, or global optimization of length/area and flux. In Proc. IEEE International Conf. Computer Vision (ICCV), pages 564-571, 2005.

48. V. Kolmogorov and C. Rother. Minimizing non-subinodular functions with graph cuts a review. IEEE Trans. Pattern Analysis and Machine Intelligence (PA MI) (appear), 2007.

49. V. Kolmogorov and R. Zabili. Computing visual correspondence with occlusions via graph cuts. In Proc. International Conf. Computer Vision (ICCVI pages 508-515, 2001.

50. V. Kolmogorov and R. Zabih. Multi-camera scene reconstruction via graph cuts. In Proc. European Conf. Computer Vision (ECCV'), volume 3, pages 82-96, 2002.

51. V. Kolmogorov and R. Zabih. What energy functions can be minimized via graph cuts?. IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), 26(2):147-159, 2004.

52. K. N. Kutulakos. Approximate n-view stereo. In Proc. European Conf. Computer Vision (ECCV) (1), pages 67-83, 2000.

53. K. N. Kutulakos and S. M. Seitz. A theory of shape by space carving. In Proc. IEEE International Conf. Computer Vision (ICCV), pages 307-314, 1999.

54. V. Kwatra, A. Schodl, I. A. Essa, G. Turk, and A. F. Bobick. Graphcut textures: image and video synthesis using graph cuts. ACM Trans. Graphics (SIGGRAPH), 22(3):277—286, 2003.

55. A. Laurentini. The visual hull concept for silhouette-based image understanding. IEEE Trans. Pattern Analysis and Machine Intelligence (PAMII 16(2):150-162, 1994.

56. V. Lempitsky and Y. Boykov. Globally optimal shapes from points. Technical report, University of Western Ontario, Сотр. Sci. Tech. Report 671, 2006.

57. V. Lempitsky and Y. Boykov. Global optimization for shape fitting. In Proc. IEEE Conf Computer Vision and Pattern Recognition (CVPR), 8 p., 2007.

58. V. Lempitsky and D. Ivanov. Seamless mosaicing of image-based texture maps. In Proc. IEEE Conf Computer Vision and Pattern Recognition (CVPR), 6 p., 2007.

59. V. Lempitsky, D. Ivanov, A. Shokurov, Y. Fedotov, and Y. Kuzrnin. Imagicad: Experimental image based modeling system. In Graphicon, pages 29-34, 2005.

60. V. Lempitsky, C. Rother, and A.Blake. Logcut efficient graph cut optimization for markov random fields. In Proc. IEEE International Conf. on Computer Vision (ICCV), 8 p., 2007.

61. V. S. Lempitsky, Y. Boykov, and D. V. Ivanov. Oriented visibility for multiview reconstruction. In Proc. European Conf. Computer Vision (ECCV) (3), pages 226-238, 2006.

62. H. P. A. Lensch, W. Heidrich, and H.-P. Seidel. A silhouette-based algorithm for texture registration and stitching. Graphical Models, 63(4):245-262, 2001.

63. S. Li. Markov random field modeling in computer vision. Springer-Verlag, 1988.

64. H. Lombaert, Y. Sun, L. Grady, and C. Xu. A multilevel banded graph cuts method for fast image segmentation. In Proc. IEEE International Conf. Computer Vision (ICCV), pages 259-265, 2005.

65. W. E. Lorensen and H. E. Cline. Marching cubes: A high resolution 3d surface construction algorithm. In ACM Trans. Graphics (SIGGRAPH), pages 163-169, 1987.

66. T. Meltzer, C. Yanover, and Y. Weiss. Globally optimal solutions for energy minimization in stereo vision using reweighted belief propagation. In Proc. International Conf. Computer Vision (ICCV), pages 428-435, 2005.

67. W. Niein. Automatic reconstruction of 3d objects using a mobile camera. Image and Vision Computing, 17(2):125—134, 1999.

68. S. Osher and J. A. Sethian. Fronts propagating with curvature-dependent speed: Algorithms based on liamilton-jacobi formulations. Journal of Computation Physics, 79:12-49, 1988.

69. S. Paris, F. Sillion, and L. Quan. A surface reconstruction ■method using global graph cut optimization. In Proc. Asian Conf. of Computer Vision (ACCVI January 2004.

70. J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of plausible Inference. San Francisco, GA: Morgan Kaufmann, 1988.

71. P. Perez, M. Gangnet, and A. Blake. Poisson image editing. ACM Trans. Graphics (SIGGRAPH), 22(3):313-318, 2003.

72. F. H. Pighin, J. Hecker, D. Lischinski, R. Szeliski, and D. Salesin. Synthesizing realistic facial expressions from photographs. In ACM Trans. Graphics (SIGGRAPH), pages 75-84, 1998.

73. J.-P. Pons, R. Keriven, and 0. D. Faugeras. Modelling dynamic scenes by registering multi-view image sequences. In Proc. IEEE Conf. Computer-Vision and Pattern Recognition (CVPR), volume 2, pages 822-827, 2005.

74. C. Rocchini, P. Cignoni, C. Montani, and R. Scopigno. Multiple texture stitching and blending on 3d objects. In Rendering Techniques, pages 119 130, 1999.

75. C. R,other, V. Kolmogorov, V. Lempitsky, and M. Szummer. Optimizing binary mrfs via extended roof duality. In Proc. IEEE Conf Computer Vision and Pattern Recognition (CVPR), 8 p., 2007.

76. S. Roy and I. J. Cox. A maxiinum-flow formulation of the n-camera stereo correspondence problem. In Proc. International Conf Computer Vision (ICCV), pages 492-502, 1998.

77. P. Savadjicv, F. P. Ferric, and K. Siddiqi. Surface recovery from 3d point data using a combined parametric and geometric flow approach. In Workshop on Energy Minimization Methods in Computer Vision (EMMCVPR), pages 325-340, 2003.

78. S. Seitz, B. Curless, J. Diebel, D. Scharstein, and R. Szeliski. A comparison and evaluation of multi-view stereo reconstruction algorithms. In Proc. IEEE

79. Conf. Computer Vision and Pattern Recognition (CVPR), pages 519-528, 2006.

80. S. M. Seitz and C. R. Dyer. Photorealistic scene reconstruction by voxel coloring. In Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), page 1067, 1997.

81. J. Shi and J. Malik. Normalized cuts and image segmentation. In Proc. IEEE Conf Computer Vision and Pattern Recognition (CVPR), pages 731737, 1997.

82. S. N. Sinha and M. Pollefeys. Multi-view reconstruction using photo-coiisistency and exact silhouette constraints: A maximum-flow formulation. In Proc. International Conf. Computer Vision (ICCV), pages 349-356, 2005.

83. G. G. Slabaugh, W. B. Culbertson, T. Malzbender, and R. W. Schafer. A survey of methods for volumetric scene reconstruction from photographs. In Volume Graphics, 2001.

84. D. Snow, P. Viola, and R. Zabih. Exact voxel occupancy with graph cuts. In Proc. IEEE Conf Computer Vision and Pattern Recognition (CVPR), pages 345-353, 2000.

85. S. Tran and L. Davis. 3d surface reconstruction using graph cuts with surface constraints. In Proc. European Conf Computer Vision (ECCV), volume 2,pages 219-231, 2006.

86. G. Turk and M. Levoy. Zippered polygon meshes from range images. In ACM Trans. Graphics (SIGGRAPH), pages 311-318, 1994.

87. A.^Vasilevskiy and K. Siddiqi. Flux maximizing geometric flows. In Proc. IEEE International Conf Computer Vision (ICCV), 2001.

88. Т. Vetter and V. Blanz. Estimating coloured 3d face models from single images: An example based approach. In Proc. European Conf. Computer Vision (ECCV), volume 2, pages 499-513, 1998.

89. G. Vogiatzis, P. H. S. Torr, and R. Cipolla. Multi-view stereo via volumetric graph-cuts. In Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR) (2), pages 391-398, 2005.

90. R. Whitakcr. A level-set approach to 3d reconstruction from range data. Intern. Journal of Computer Vision (IJCV), 29(3):203-231, 1998.

91. R. Whitaker. Reducing aliasing artifacts in iso-surfaces of binary volumes. In Volume Visualization, pages 23-32, 2001.

92. H. Zhao, S. Osher, and R. Fedkiw. Fast surface reconstruction using the level set method. In VLSM, page 194, 2001.