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

Московский Государственный Университет им М В Ломоносова

Д/-

на правах рукописи

Лемпицкий Виктор Сергеевич

МЕТОДЫ ТРЕХМЕРНОЙ РЕКОНСТРУКЦИИ НА ОСНОВЕ РАЗРЕЗОВ НА ГРАФАХ

Специальность 05 13 11 — "Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей"

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2007

003158810

Работа выполнена на кафедре вычислительной математики механико-математического факультета Московского Государственного Университета им М В Ломоносова

Научный руководитель

Официальные оппоненты

Ведущая организация —

доктор физико-математических наук, профессор Михалев Александр Васильевич

доктор технических наук, профессор, член-корреспондент РАН Рябов Геннадий Георгиевич

доктор физико-математических наук, старший научный сотрудник Галактионов Владимир Александрович

Научно-исследовательский институт системных исследований РАН (НИИСИ РАН)

Защита диссертации состоится 2007 г в

час на заседании диссертационного совета К 501 001 11 при Московском государственном университете имени M В Ломоносова по адресу

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

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

¿Г" емп*bSi

Автореферат разослан :

Ученый секретарь диссертационного совета

к ф -м н

2007 г

-Л

Суворов В В

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

• задача реконструкции текстур на основе наборов изображений Научная новизна

Представлен новый метод геометрической реконструкции на основе трехмерных данных Новизна метода заключается в использовании глобальной оптимиза-

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

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

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

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

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

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

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

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

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

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

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

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

Результаты работы были представлены в ходе следующих докладов на конференции IEEE Conference on Computer Vision and Pattern Recognition CVPR-2007 (США, Миннеаполис, июнь 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 таблицы

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

Первая глава также носит обзорный характер и посвящена предшествующим работам В данной главе дается формулировка задачи нахождения минимального разреза на графе, приведенная далее Рассмотрим направленный граф С? Выделим из множества его вершин две и обозначим их 5 и Т (в дальнейшем эти вершины называются терминалами или терминальными) Каждой дуге графа припишем действительный неотрицательный вес ги, Подобный граф с выделенными терминалами и взвешенными дугами называют сетевым графом В дальнейшем под словом 'граф" понимается сетевой граф БТ-разрезом графа (далее просто разрезом) называется такое разбиение множества всех вершин на два подмножества, что терминалы 5 и Т находятся в разных подмножествах (называемых соответственно Б-компонентой и Т-компонентой разреза) Будем использовать обозначения Ус, и Уг для обозначения компонент и [У^, Ут] для обозначения разреза Для данного разреза назовем дугу разрезанной, если ее началом служит

Рис. 1. I Зрим ер исходных данных для задачи, рассматриваемой в главе 2. Слева фото чехолного объекта. В середине исходные данные й виде двух лазерных ска-нон. Стрелки показывают напрйШёицМ сканирвванЪвЦ для точек каждого скака, исполняемое и последующих экспериментах и качестве грубой оценки нормали к поверхности, Справа увеличенное изображение набора точек, полученных и ре-ЗЩьтате лазерного сканирования. Показан край поверхности (хорошо различимы шумы и выбросы).

вершина из У^-, а конном вершина из \'т. Наконец, весом, рщжш назовем сумму весов всех разрезанных дуг. Существование высокоэффективных алгоритмов нахождения разреза с минимальным весом ('Минимального разреза) обуславливает широкое использование минимальных разрезов па графах ¡5 вычислительной математике вообще и I! компьютерном зрении к частности.

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

Во второй главе рассматривается задача геометрической реконструкции па основе трехмерных измерений. Предполагается, что трехмерные данные заданья в впле набора слпб(юри£нтиро(1аппш: точечных измерении поверхности {.4,. н,1г}, где А, положение точки в пространстве в мировой системе координат, Щ Ил, грубая* с точностью до 90° оценка внешней нормали к поверхности в этой точке. Подобные трехмерные данные могут быть подучены В результате нескольких

]

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

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

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

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

Первый член /д{(пм(3), у(Х)) сЬБ в (1) выражает наблюдаемые точечные данные и представляет собой поток через поверхность М векторного поля ь(Х), получаемого путем суммирования векторных полей, соответствующих отдельным слабоориентированным точкам ь(Х) = — гДе ^а,{Х) представляет собой

ЛУ (1)

векторное поле, сонаправленное с оценкой нормали па,, затухающее при удалении от точки, например, по гауссовскому закону va,(X) = па, ехр(— ) Ис-

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

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

близкую К ПАг

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

Третий член — 0{Х) dV в (1) представляет собой интеграл по внут-

ренности поверхности от пространственного потенциала —О(Х), выражающего т н данные занятости, т е вероятностное предпочтение различных областей пространства быть внутри (О(Х) > 0) или снаружи (О(Х) < 0) поверхности Подобные данные могут быть известны на основании пересечения силуэтов при пассивном стереосопоставлении, а также данных о незанятости пространства между сенсором сканера и поверхностью скана при лазерном сканировании В случае отсутствия подобных данных О(Х) полагается равным 0

Таким образом, функционал (1) позволяет выразить трехмерные данные разнообразного происхождения и является достаточно универсальным Важной его особенностью является нетривиальность (отличие от нуля) глобального минимума В предшествующих работах (Boykov Y and Kolmogorov V // CVPR 2003, ICCV 2005) было показано, что непрерывный функционал вида (1) может быть аппроксимирован дискретным функционалом, соответствующим весам разрезов на специально построенном графе-сетке, нетерминальные вершины которого расположены в узлах прямоугольной решетки, заполняющей ограничивающий па-

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

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

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

Работа схемы опирается на Лемму глобальной оптимальности сужения, дающая достаточные условия для совпадения минимальных разрезов на графе и его (сетевом) подграфе В дальнейшем, два подграфа сетевого графа назовем непересекающимися, если множества их вершин не пересекаются Будем также отождествлять поднабор вершин графа С? и подграф, состоящий из этих вершин и соединяющих их ребер (с весами), имеющихся в графе (3 Два непересекающихся подграфа (набора вершин) и (?2 будем называть соединенными, если в исходном графе существует дуга с ненулевым весом, соединяющая вершину из С^ с вершиной из Сг

Лемма (глобальной оптимальности сужения) Пусть С? - сетевой граф Пусть С^, От и В — разбиение вершин О, такое что 5 € В, Т 6 В Пусть [Вз, Вт] -минимальный разрез на подграфе В и пусть С?,? не соединен с Т, От не соединен с Б, не соединен с Вз не соединен с От, а Вт не соединен с <?5 Тогда [Дд и (?5, Вт и От] — минимальный разрез на С Доказательство леммы опирается па дуальность минимального разреза и максимального потока в графе

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

• Инициализируется разбиение (Зу и В* (при нахождении поверхностей, минимизирующих (1) для инициализации можно взять вершины, лежащие, соответственно, во внутренности, наружности, и возле границы относительно поверхности Мо, найденной по схеме Войкова-Колмогорова на низком разрешении)

• Вершины соединенные с Т или а также вершины От, соединенные с 5, переводятся в В, что дает разбиение и В0

• 1 = 0 Цикл по г

• Находится [Вд,Вт\ ~ минимальный разрез на В1

• Вершины Вг3, соединенные с 01т, и вершины В1Т, соединенные с Ог3, переводятся в В, что дает разбиение б^-1, О1^1 и Вг+1

• В случае отсутствия таких вершин (т е когда Вг = В'+1), условия Леммы выполнены, и [Вз и Оя, Вт и £>т] - минимальный разрез на О (алгоритм завершает работу)

• Иначе I = 1+1

Поскольку на каждом шаге количество вершин в подграфе В возрастает, то алгоритм сходится за конечное число шагов Временная эффективность алгоритма

Рис. 2. Результаты применения метода к наборам лазерных сканов СтэнфЬрд-ского Университета (показаны общие планы моделей и увеличенные фрагменты); Пример исходных данных показан на рис. 1.

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

Защищающая часть главы 2 посвящена описанию результатов экспериментов на реальных наборах данных. В частности, в главе рассматриваются стандартные наборы лазерных с капов Стэнфордекого университета (рис, 2), а также наборы трехмерных данных, полученные в результате пассивного сте реосо п оставлен на изображений (для подобных .чанных также приводятся количественные оценки качества реконструируемых поверхностей). Кроме того, в отдельном эксперименте рассматривается искусственно модифицированный набор данных лазерного сканирования с существенной (50-к ратной) вариацией плотности Точек. Также производится экспериментальное сравнение с другими современными методами трехмерной реконструкции (Пуассон о вс ко Й реконструкцией и методом, использующим "локалыю'-сужсиныс разрезы на графах), демонстрирующее преимущество Предлагаемого метода на рассмотренных наборах данных.

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

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

В третьей главе рассматривается задача геометрической реконструкции объекта на основе набора его фотоизображений Предполагается наличие регистрации изображений, т е наличие мировой системы координат, для любой точки X которой известна проекция Ргг(Х) на г-ое изображение набора и цвет С{Рг1{Х)), соответствующий этой проекции (г = 1 ТУ) Также предполагается задание в мировой системе координат ограничивающего параллелепипеда В Подавляющее большинство существующих алгоритмов использует при работе понятие меры фотосостоятельности р{Х), определяемой для каждой точки, как разность цветов {С(Ргг(Х))} ее проекций (вместо цветов могут использоваться более сложные описания окрестностей Ргг(Х)) Точки с малой мерой фотосостоятельностью, тес близкими цветами проекций, с большей вероятностью лежат на трехмерной поверхности При этом, при подсчете фотосостоятельности из набора {С(Ргг(Х))} должны исключаться цвета, соответствующие закрытиям, т е случаям когда точка X заслонена на г-ом изображении более близкой частью поверхности

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

суженные разрезы) существенным образом зависит от наличия качественного начального приближения

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

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

р(Х,п)=сш ]Г 95гР(С(Ргг(Х)),С)2, (2)

i,dS,>0

где дБг = hmd5_>o - предел отношения ориентированной площади проекции участка на г-ое изображение dS, к площади участка dS при стремлении dS к нулю, С(Ргг(Х)) - цвет пикселя Рг,(Х), цвет С пробегает все цветовое пространство RGB, р - некоторая метрика в пространстве RGB

Обработка закрытий в (2) достигается за счет рассмотрения изображений только с положительной ориентированной площадью проекции dSt > 0 Это соответствует очевидному соображению, что для плоского участка, принадлежащего поверхности (такого что п совпадает с внешней нормалью), изображения с точками съемки, расположенными "за"плоским участком (в полупространстве {А\(А — X, п) < 0}) рассматриваться при подсчете фотосостоятельности не должны Подобный подход к обработке закрытий является точным в случае реконструкции выпуклых объектов и приближенным в общем случае

Функционал фотосостоятельности для всей поверхности М естественно определить как интеграл от фотосостоятельности по этой поверхности Е(М) =

¡мр{Х,п(1з) (¿Б, где п^з — внешняя нормаль к малому участку интегрирования ¿Б Заметим, что в силу неотрицательности фотосостоятельности р{Х плз), такой функционал имеет тривиальный глобальный минимум равный нулю (нулевая поверхность) В то же время расширенный функционал

Е(М) = [ р(Х,п<18)с1Б+ [ ЩХ)бУ+ [ А(п(13,и(Х))йБ (3) Jм о 1'пf м -1М

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

При этом, второй член в (3) § ^ м и(X) <1V представляет собой интеграл по внутренности поверхности от скалярного потенциала и(Х), который аналогично предыдущей главе имеет смысл данных занятости, т е вероятностное предпочтение различных областей пространства быть внутри (11{Х) < 0) или снаружи (и(Х) > 0) поверхности и{Х) может быть основан на данных о силуэтах или на известных априори жестких условиях о занятости тех или иных областей, в отсутствие же таких сведений и(Х) может быть взят постоянным (1/(Х) = (3 < 0), что соответствует равномерному предпочтению точкам пространства находиться внутри поверхности

Третий член в (3) /м Х(щз, д,Б представляет собой поток через поверх-

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

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

X X

t \ / ♦

t У + х \ * fvC 3'*/ / 4

* Л \ t

ab cd

Рис 3 а - комплекс С задает разбиение ограничивающего объема В Выделена одна из С-совместимых поверхностей b - локальная структура комплекса Две соседних клетки Яг и Rj разделены парой ориентированных граней Fl3 и Fn с ~ локальная структура графа G дуальная к комплексу на рис b) d - клетки предлагаемого трехмерного комплекса, полученные путем разбиения кубического вокселя Выделена одна из клеток

для задачи поиска функций с минимальным графиком над плоским сегментом /ПсВ2 G(/(z), V/(x), г) da: —» mm/ была предложена в предшествующей работе Kirsanov and Gortier//Harvard Tech Rep 2004

В рамках предлагаемой схемы ограничивающий параллелепипед В разбивается на многогранные клетки Ri, R2, Rk (рис За) Будем считать, что каждая пара соседних клеток R, и R, разделена парой ориентированных многоугольных граней — грань F7J отделяет Rj от i?j, грань FJt отделяет Дг от R3 (рис ЗЬ) Пользуясь терминологией из алгебраической геометрии, будем называть описанную структуру из клеток и разделяющих их граней комплексом

Для данного комплекса С, введем понятие С-совместимой поверхности (рис За) поверхность М совместима с С (С-совместима) если внутренность М есть объединение клеток комплекса, т е int М = U/t=i q Rik В таком случае сама поверхность М состоит из граней, отделяющих клетки, не принадлежащие int М, от клеток, принадлежащих mt М, те М — U#to nt M,R}cext М ^rj

Для данного С предлагаемая схема дискретной оптимизации производит перебор по множеству С-совместимых поверхностей При условии, что множество С-совместимых поверхностей достаточно плотно во множестве всех поверхностей, глобальный минимум на множестве С-совместимых поверхностей, полученный перебором, будет близок к глобальному минимуму на всем множестве поверхностей

Заметим, что значение функционала Е(М) на С-совместимой поверхности может быть подсчитано как

[ p(X,ndS)dS+ I U{X)+divv{X)dV = YL J2

■>M JmtM R,cmt M RjCert M В.,ant M

где и>г] = f р(Х, пи) dS — "плата' за включение FtJ в поверхность М, иц = К,

J U{X) + divv(x) dV — "плата" за включение R, в int M

Проблема нахождения оптимальной С-совместимой поверхности может быть сведена к поиску минимального разреза на графе G, описываемом ниже Нетерминальные вершины и соединяющие их дуги графа G составляют граф дуальный к ориентированному комплексу С (рис Зс) для каждой клетки Дг из С, в G добавляется вершина Уг, для каждой ориентированной грани F%1 из С, в G добавляется дуга DjjlV^Vj, которой приписывается вес и)п Терминальные вершины <9 и Т соединяются дугами S—*V,j и Vt—>Т с каждой нетерминальной вершиной Уг Данным дугам приписываются веса 0 и ц в случае шг > 0, или — шг и 0, если шг < О

При такой конструкции графа каждой С-совместимой поверхности M поставлен в однозначное соответствие разрез См = [{К|Д( С int M}, С ext M}] В работе показывается, что вес разреза равен значению (3) на соответствующей С-совместимой поверхности с точностью до аддитивной константы, не зависящей от разреза Следовательно, нахождение минимального разреза на графе G, дает точный минимум на множестве С-совместимых поверхностей Подобная минимальная поверхность и служит ответом к задаче геометрической реконструкции

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

j - * * i Щ ti

[v *f >

I1 SU

Рис. 4. Результат реконструкции при помощи предлагаемого метода для набора "Верблюд" (16 фотографии). Показаны фотографии н изображения модели.

Заметим, что при вычислении фотосоетоятельностл для конечно-малых участков вместо (2) используется мера фотосостоятельностй:

(X,n,dS)= miii У dS, min ||С(У)-С[|а,

CGIICB VcrlAI " v '

i.dSi>0

YedM,

(4)

где dS Площадь плоского участка, г/Л/, проекция участка на изображение i, dS¡ ориентированная площадь что и проекции, С(У') цвет пикселя У. пробегающего все пиксели проекции d,M¡, цвет С пробегает все цветовое пространство RGB. Отметим, что внутренний минимум в (4) позволяет избегать ошибок дискретизации, что особенно существенно При работе с комплексами малого пространственного разрешения и или высокой детализации текстур сцепы. Кроме того, для эффективности подсчета внешний минимум по пространству RGB может■ быть заменен минимумом но множеству пветов проекций {С(/5Г|(Х)), С(Рг2(Х)),... С(Ргх(Х))} (предполагается, что хотя бы один из

цветов этого множества окажется близким к цвету поверхности С -- argmin).

пан

Завершающая часть главы 3 посвящена описанию экспериментов на реальных наборах фотоизображений, состоящих из IÜ-.'ЗО изображений. По результатам экспериментов моЖно сделать gbi вод о способности предлагаемого метода реконструировать геометрию сцены с достаточной точностью, даже при наличии закрытии, летекстурироваипых областей поверхности, бл и кующих поверхностей. Экспериментально показывается превосходс тво предлагаемого метода по сравнению с методом пространственного вырезания. В то же время, необходимо отметить, что

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

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

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

Предшествующие подходы к сшивке текстурных фрагментов основаны на различных алгоритмах смешивания фрагментов, осуществляя смешивание фрагментов с непрерывно-меняющимися весами или локальное смешивание в окрестности швов между фрагментами Главным недостатком предшествующих методов является то, что при наличии геометрических несоответствий, смешивание приводит к раздвоению деталей (англ ghosting) и их размытию (англ blurring)

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

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

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

Рассмотрим треугольную сетку с гранями Р\, Рк, и набор текстурных

фрагментов Р1, Р2 Рм, каждый из которых является проекцией одного из исходных изображений на поверхность модели Теь стпурная мозаика определяется вектором М = {тьтг, , тк} 6 {О ЛГ}ЛГ, предписывающим текстурирование грани с помощью фрагмента Р™г Качество мозаики определяется двумя факторами Во-первых, желательно чтобы грань Рг была текстурирована с помощью фрагмента, где ее проекция на изображение имеет максимальное качество (разрешение) Во-вторых, когда соседние грани Рг и ^ текстурируются с помощью разных фра1 ментов (тп, ф щ), то между гранями возникает шов Визуальная различимость швов мозаики является вторым фактором, влияющим на качество мозаики Чтобы учесть эти два фактора, вводится энергия, описывающая качество М, состоящая из 2 членов

£(М) = Е0( М) + \ЕЬ (М) (5)

Первый член £д(М) в (5) соответствует качеству фрагментов Предположим, что качество текстурирования грани Р, фрагментом Р3 задается значением иг'г,

в lj с (1

Рис. 5. а Текстурный фрагмент, -.задающий тексту риро&ан ие части геометрической модели. Ь Неоиткмизированная (жадная) текстурная мозаика (слева структура мозаики, цвет соответствует выбору фрагмента, справа - сама текстуру). с То же для мозаики, оптимизированной с помощью разрезов на графах-, ci Сравнение увеличенных фрагментов.

принимающим меньшие значения дли сочетаний с лучшим качеством. Если хотя бы часть грани лежит за границей фрагмента, то wj полагается равным ça. Для прочих фрагмеитий, возможны разный подходы к вычислению w¡. (например, icj вычисляется на основе угла между направлением на точку съемки и иормалыо к грани: w¡ = вгп'2ф+ ,9, где в настраиваемый параметр).

Второй член £\,(М} в (5) соответствует различимости швов. Пусть две соседних rpttiftf f] И F, имеют общее ребро e,j, Тогда различимость шип между F, и F, естественным образом определяется как интегральная разность цветов между фрагментами вдоль ребра: = J. d(Pr,nr (X ), Pr,,^ ( A'}) dX, где Prr оператор проекции из трехмерного пространства на г, и d(-, ■) метрика в цве-

гл ni,,mj ,, /

■юном пространстве, Очевидно, если гп. — т.. то щ — U (что соответствует отсутствию шва В этом месте).

Если jV обозначает множество пар соседних гранен, то второй член в (ó) может быть записан как jS.s'(M) = ¡}^аг V}u ■ и вся чнергия (5) записывается как:

Е(М) = Х>Г+ V (С)

'=i {iJïeY

Оптимизация подобных энергий возникает в рамках задач о нахождении наиболее вероятных состояний (попарных) марковских случайных полей (МСП), причем в рассматриваемом случае узлы МСП соответствуют граням модели, переменные узлов соответствуют номерам фрагментов тг, а графическая структура МСП задается сеткой М Хотя задача нахождения глобального минимума (6) является ЫР-полной, в предшествующих работах для подобных энергий предложен основанный на разрезах на графах алгоритм а-расширения (Воукоу, Уек&1ег^аЬгк//ТРАМ1,23(11),2001), находящий локальные минимумы, на практике (для подобных энергий) имеющие энергию близкую к глобальному минимуму В работе доказывается применимость алгоритма а-расширения к энергии (6) После этого, демонстрируется, что подобная МСП-оптимизация приводит к визуально-лучшим результатам по сравнению с неоптимизированной (жадной) мозаикой М = {тг| т, = а^гшп, ад^} (рис 5)

Оптимизация мозаики существенно снижает различимость швов, но не гарантирует их полной невидимости Поэтому на втором этапе требуется дополнительная обработка текстуры, гарантирующая бесшовную сшивку текстурных фрагментов, результатом которой является текстура, не имеющая разрывов цветовой функции на швах (в работе также обсуждается связь между предлагаемой процедурой и Пуассоновским сглаживанием, предложенным в предшествующих работах для плоских изображений) Рассмотрим гладкое ориентируемое многообразие М Пусть / кусочно-непрерывная функция на М, и пусть Df — подмногообразие коразмерности 1, образованное точками разрыва f Функция-добавка д определяется как кусочно-непрерывная функция, непрерывная в тех же точках, что и /, определенная с точностью до аддитивной константы, удовлетворяющая

д = агЕппп / (VЪ)ЧХ, з г \д]\х = ~[/]\х> УХ € (7)

■1 м\о{

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

я Ь с (I

Рис. 6. Сглаживание швов для текстурной мозаики; а геометрическая модель, Ь модель с текстурной мозаикой (стрелками выделены швы), с вычислимая функция-добавка, с! модель с: нанесенной бесшовной текстурой, включающей функцию-добавку.

ляетеи всюду непрерывной функцией па М. Заметим, что в силу первого условия (7), добавление функции-добавки к / оказывает минимальный эффект на мелкие детали f.

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

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

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

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

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

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

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

Основные положения работы изложены в следующих публикациях

1 V Lempitsky and Y Boykov Global Optimization for Shape Fitting //In Proc IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (ISBN 1-4244-1180-7), Minneapolis, USA, June 2007, 8 p

2 V Lempitsky and D Ivanov Seamless Mosaicmg of Image-Based Textuie Maps //In Pioc IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (ISBN 1-4244-1180-7), Minneapolis, USA, June 2007, 6 p

3 V Lempitsky, Y Boykov, D Ivanov Oriented visibility for Multiview Reconstruction //In Proc Euiopean Conference on Computer Vision (ECCV), vol 3 (Springer Lecture Notes m Computer Science vol 3953, ISBN 3-540-338365), pp 225-237, Giaz, Austria, May 2006

4 Y Boykov and V Lempitsky Fiom Photohulls to Photoflux Optimization /'/In Proc British Machine Vision Conference (BMVC) (ISBN 1-904410-14-6), vol 3, pp 1149-1158, Edinburgh, UK, Septembei 2006

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

6 Жислина В Г, Иванов Д В , Курякин В Ф , Лемпицкий В С , Мартынова Е М , Родюшкин К В , Фирсова Т В , Хропов А А , Шокуров А В Создание персонифицированных моделей головы и их анимация по цифровым фотографиям и видео //Программирование РАН, 30(5), 2004, стр 5-24

7 V Lempitsky, D Ivanov, A Shokuiov, Ye Fedotov and Ye Kuzmin ImagiCAD Experimental Image Based Modeling System //In Pioc "GiaplnCon'' conf, Novosibnsk, Russia, June 2005, pp 29-34

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

Заказ № 201/09/07 Подписано в печать 21 09 2007 Тираж 70 экз Уел пд 1,5

^ - ООО "Цифровичок", тел (495) 797-75-76, (495) 778-22-20 'TV^ www cfr ru, e-mail info@cfr ru

ВВЕДЕНИЕ

ГЛАВА 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] для поиска минимальных разрезов на графах, разработанная проф. Войковым совместно с проф. Владимиром Колмогоровым (Университетский Колледж Лондона), интенсивно использовалась при практической реализации алгоритмов.

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

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

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.