WWW.DISSERS.RU

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

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

Pages:     | 1 || 3 | 4 |

E(M) = (nM(S), v(X)) dS + · dS + -O(X) · dV. (1) M M int (M) Первый член (nM(S), v(X)) dS в (1) выражает наблюдаемые точечные данM ные и представляет собой поток через поверхность M векторного поля v(X), получаемого путем суммирования векторных полей, соответствующих отдельным сла боориентированным точкам: v(X) = - vA (X), где vA (X) представляет собой i i i векторное поле, сонаправленное с оценкой нормали nA, затухающее при удалении i 1 i от точки, например, по гауссовскому закону vA (X) = nA · exp(-||X-A ||2). Исi i пользование подобного члена для выражения точечных данных обосновано тем, что минимальные значения потока векторного поля -vA (X), соответствующего i отдельной точки, соответствуют поверхностям, проходящим максимально близко к Ai и имеющим в окрестности Ai ориентацию внешней нормали максимально близкую к nA.

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

Третий член -O(X) · dV в (1) представляет собой интеграл по внутint (M) ренности поверхности от пространственного потенциала -O(X), выражающего т.н. данные занятости, т.е. вероятностное предпочтение различных областей пространства быть внутри (O(X) > 0) или снаружи (O(X) < 0) поверхности. Подобные данные могут быть известны на основании пересечения силуэтов при пассивном стереосопоставлении, а также данных о незанятости пространства между сенсором сканера и поверхностью скана при лазерном сканировании. В случае отсутствия подобных данных O(X) полагается равным 0.

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

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

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

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

Лемма (глобальной оптимальности сужения): Пусть G – сетевой граф. Пусть GS, GT и B разбиение вершин G, такое что S B, T B. Пусть [BS, BT ] – минимальный разрез на подграфе B и пусть GS не соединен с T, GT не соединен с S, GT не соединен с GS, BS не соединен с GT, а BT не соединен с GS. Тогда [BS GS, BT GT ] минимальный разрез на G. Доказательство леммы опирается на дуальность минимального разреза и максимального потока в графе.

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

• Инициализируется разбиение G, G и B (при нахождении поверхностей, S T минимизирующих (1) для инициализации можно взять вершины, лежащие, соответственно, во внутренности, наружности, и возле границы относительно поверхности M0, найденной по схеме Бойкова-Колмогорова на низком разрешении).

• Вершины G, соединенные с T или G, а также вершины GT, соединенные S T с S, переводятся в B, что дает разбиение G0, G0 и B0.

S T • i = Цикл по i i i • Находится [BS, BT ] – минимальный разрез на Bi.

i i • Вершины BS, соединенные с Gi, и вершины BT, соединенные c Gi, перевоT S дятся в B, что дает разбиение Gi+1, Gi+1 и Bi+1.

S T • В случае отсутствия таких вершин (т.е. когда Bi = Bi+1), условия Леммы выполнены, и [BS GS, BT GT ] – минимальный разрез на G (алгоритм завершает работу).

• Иначе i = i+Поскольку на каждом шаге количество вершин в подграфе B возрастает, то алгоритм сходится за конечное число шагов. Временная эффективность алгоритма Рис. 2. Результаты применения метода к наборам лазерных сканов Стэнфордского Университета (показаны общие планы моделей и увеличенные фрагменты).

Пример исходных данных показан на рис. 1.

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

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

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

В третьей главе рассматривается задача геометрической реконструкции объекта на основе набора его фотоизображений. Предполагается наличие регистрации изображений, т.е. наличие мировой системы координат, для любой точки X которой известна проекция P ri(X) на i-ое изображение набора и цвет C(P ri(X)), соответствующий этой проекции (i = 1..N). Также предполагается задание в мировой системе координат ограничивающего параллелепипеда B. Подавляющее большинство существующих алгоритмов использует при работе понятие меры фотосостоятельности p(X), определяемой для каждой точки, как разность цветов {C(P ri(X))} ее проекций (вместо цветов могут использоваться более сложные описания окрестностей P ri(X)). Точки с малой мерой фотосостоятельностью, т.е. с близкими цветами проекций, с большей вероятностью лежат на трехмерной поверхности. При этом, при подсчете фотосостоятельности из набора {C(P ri(X))} должны исключаться цвета, соответствующие закрытиям, т.е.

случаям когда точка X заслонена на i-ом изображении более близкой частью поверхности.

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

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

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

p(X, n) = min Si (C(P ri(X)), C)2, (2) CRGB i, Si>где Si = limdS0 dSi – предел отношения ориентированной площади проекции dS участка на i-ое изображение dSi к площади участка dS при стремлении dS к нулю, C(P ri(X)) – цвет пикселя P ri(X), цвет C пробегает все цветовое пространство RGB, – некоторая метрика в пространстве RGB.

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

Функционал фотосостоятельности для всей поверхности M естественно определить как интеграл от фотосостоятельности по этой поверхности: E(M) = p(X, ndS) dS, где ndS внешняя нормаль к малому участку интегрирования M dS. Заметим, что в силу неотрицательности фотосостоятельности p(X, ndS), такой функционал имеет тривиальный глобальный минимум равный нулю (нулевая поверхность). В то же время расширенный функционал:

E(M) = p(X, ndS) dS + U(X) dV + (ndS, v(X)) dS (3) M int M M используемый в дальнейшем при реконструкции, в общем случае имеет нетривиальный глобальный минимум.

При этом, второй член в (3) U(X) dV представляет собой интеграл по int M внутренности поверхности от скалярного потенциала U(X), который аналогично предыдущей главе имеет смысл данных занятости, т.е. вероятностное предпочтение различных областей пространства быть внутри (U(X) < 0) или снаружи (U(X) > 0) поверхности. U(X) может быть основан на данных о силуэтах или на известных априори жестких условиях о занятости тех или иных областей, в отсутствие же таких сведений U(X) может быть взят постоянным (U(X) = < 0), что соответствует равномерному предпочтению точкам пространства находиться внутри поверхности.

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

Функционал (3) не принадлежит к множеству функционалов, глобальная оптимизация которого может быть сведена по схеме Бойкова-Колмогорова к поиску минимального разреза на графе-сетке. В связи с этим в главе 2 предлагается альтернативная схема дискретной глобальной оптимизации, применимая для более широкого класса функционалов, включающего и функционал (3). Заметим, что построенная на схожих идеях схема дискретной глобальной оптимизации Dij Fij Rj Ri Fji Vj Vi Dji а b c d Рис. 3. a – комплекс C задает разбиение ограничивающего объема B. Выделена одна из C-совместимых поверхностей. b – локальная структура комплекса. Две соседних клетки Ri и Rj разделены парой ориентированных граней Fij и Fji. c – локальная структура графа G дуальная к комплексу на рис. b). d – клетки предлагаемого трехмерного комплекса, полученные путем разбиения кубического вокселя. Выделена одна из клеток.

для задачи поиска функций с минимальным графиком над плоским сегментом G(f(x), f(x), x) dx minf была предложена в предшествующей работе RKirsanov and Gortler//Harvard Tech.Rep. 2004.

Pages:     | 1 || 3 | 4 |






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