Pull to refresh

Make3D из одной фотографии, часть 2

Algorithms *


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

Публикация состоит из: Часть 1, Часть 2
Публикуется для утоления любопытства, с целью разоблачения магии дать понять как это устроено.



Содержание:


Часть первая (тут):
  • Краткое описание алгоритма
  • Список используемых теорий и алгоритмов
  • Модель Изинга или откуда взялась такая формула в MRF
  • Эффективная сегментация изображения на графах
  • Хотим 3D Модель и Расположение полигонов
  • Смотреть придется шире...
  • Монокулярные особенности изображения
  • Границы и преломления
  • MRF Input и Output
  • Что будет делать MRF? Цель: min(погрешность определения расстояния)
Часть вторая (текущая):
  • Wish list готов, запихаем его в Модель MRF
  • 1. Local features: Предварительное определение расстояния по локальным особенностям
  • 2. Connection: Соединение
  • 3. Co-planar: Копланарность
  • 4. Co-linear: Коллинеарность
  • Кратко про Обучение MRF
  • Кратко про Решение MRF
  • Исходный код и изученные параметры модели
  • Исполнение программы, тестирование
  • Итого
  • Немножко файлов



Wish list готов, запихаем его в Модель MRF


Для того чтобы смоделировать зависимость параметров плоскостей α, особенностей (features) самого изображения, и других свойств, таких как соединения, копланарность, и коллинеарность, по аналогии с функцией распределения Гиббса (Gibbs measure) в мультипликативной форме, модель MRF формулируется в следующем виде:

Функция распределения для MRF:

Функция распределения для MRF


В данной формуле: α_i представляют собой параметры плоскости для суперпикселя i. Для всех S_i точек i-ого суперпикселя x_(i,s_i) обозначает вектор особенностей (features) для точки s_i изображения. X_i={x_(i,s_i)∈R^524:s_i=1,…,S_i} обозначает множество всех особенностей (features) суперпикселя i. Аналогично, R_i={R_(i,s_i):s_i=1,…,S_i} обозначает множество всех лучей к суперпикселю i. Параметр υ представляет собой уровень доверия к расстоянию до суперпикселя, т.е. насколько мы уверенны в том расстоянии, которое модель предположила опираясь только на локальные особенности (features) изображения.

MRF будет «стягивать» в min кучу вышеперечисленных расстояний.
По аналогии с распределением Гиббса, MRF будет подыскивать состояние системы с наименьшим запасом энергии (в нашем случае – это будет «погрешность определения расстояний») – это наиболее вероятное состояние модели.





Теперь о типах расстояний подробнее…



1. Local features: Предварительное определение расстояния по локальным особенностям


В формуле MRF первый множитель f_1(.) представляет собой функцию моделирующую параметры плоскостей α_i в зависимости от особенностей (features) изображения x_(i,s_i). Пусть истинное расстояние до точки s_i, расположенной на i-ом суперпикселе, будет равно d_(i,s_i), тогда верно равенство: R_(i,s_i)^T α_i=1/d_(i,s_i), где R_(i,s_i) представляет собой луч, соединяющий точку наблюдения (camera center) с точкой s_i изображения. Тогда, если модель определила предварительное расстояние по локальным особенностям изображения (features) как d^_(i,s_i)=x_(i,s_i)^T θ_r, то относительная погрешность равняется:

Относительная погрешность:

Относительная погрешность


Pic.17 Погрешность определения расстояний по локальным признакам

Pic.17 Погрешность определения расстояний по локальным признакам


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

Минимизация локальной погрешности:

Минимизация локальной погрешности


Параметрами в данной модели являются θ_r∈R^524. В "Make3D" используются различные параметры для различных рядов изображения r=1,…,11 исходя из предположения, что фотоснимок, скорее всего, делался горизонтально и потому имеет различные статистические закономерности для различных частей изображения: вверху чаще всего будет небо или крыша, внизу изображения чаще всего будет газон или дорога. Параметры υ_i={υ_(i,s_i):s_i=1,…,S_i} представляют собой уровень доверия к предварительно определенному расстоянию d^_(i,s_i) до точки s_i.

Переменные υ_(i,s_i), т.е. уровни доверия к расстоянию до точки s_i, выставленному опираясь только на локальные свойства суперпикселя, изучаются предварительно по монокулярным особенностям изображения (monocular fetures), оценивая полученные результаты с использованием истинных расстояний (ground-truth) d_i до суперпикселя по формуле: |d_i-x_i^T θ_r |/d_i.

Второй множитель в формуле MRF f_2(.) представляет собой функцию, моделирующую отношения между параметрами плоскостей α_i и α_j для двух суперпикселей i и j. В свою очередь она раскладывается в произведение 3-х функций h_(s_i,s_j)(.), устанавливающих взаимосвязи различных типов: соединение, копланарность, коллинеарность для точек {s_i,s_j}, принадлежащих соответствующим суперпикселям.

Моделирование отношения суперпикселей:

Моделирование отношения суперпикселей




2. Connection: Соединение


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

Pic.18 Минимизация расстояния соединения

Pic.18 Минимизация расстояния соединения


Для расстояния от точки наблюдения (camera center) до точки s_i выполняется равенство R_(i,s_i)^T α_i=1/d_(i,s_i), аналогично для точки s_j выполняется R_(j,s_j)^T α_j=1/d_(j,s_j). Величина (R_(i,s_i)^T α_i-R_(j,s_j)^T α_j)d^ дает оценку расстояния (fractional distance) |(d_(i,s_i )-d_(j,s_j ) )/√(d_(i,s_i ) d_(j,s_j ) )| при d^=√(d^_(s_i ) d^_(s_j )), где d^_(s_i) и d^_(s_j) предварительные расстояния до соответствующих суперпикселей.

Минимизация в MRF проводится с использованием формулы:

Минимизация расстояния соединений

Стоит отметить, что если суперпиксели принадлежат различным объектам и точки s_i, s_j лежат на границе этих различных объектов, то y_ij=0 и «соединение», таким образом, не производится.



3. Co-planar: Копланарность


Выбираются 3 пары точек (s_i,s_j), 2 пары точек лежащие на границе соседних суперпикселей i и j, как и прежде, и третья пара s_i^'',s_j^'' точек, лежащая в центре соответствующего суперпикселя. Для того чтобы в восстановленной трехмерной модели сцены эти суперпиксели лежали в одной плоскости, если это имеет место в действительности, то в MRF минимизируется расстояние между плоскостями, на которых лежат точки s_i^'',s_j^'' вдоль одного луча.

Pic.19 Минимизация расстояния копланарных плоскостей

Pic.19 Минимизация расстояния копланарных плоскостей


Минимизация в MRF проводится с использованием формулы:

Минимизация расстояния копланарных плоскостей

И вычисляется произведение соответствующих погрешностей h_(s_i^'',s_j^'')(.)=h_(s_i^'' )(.)h_(s_j^'' )(.), следует отметить, что если два суперпикселя копланарны, то h_(s_i^'',s_j^'')=1. Если эти суперпиксели копланарны, но находятся на некотором расстоянии друг от друга, т.е. первые две пары точек лежат не на границы, а разнесены в пространстве, то эта метрика все равно будет работать.



4. Co-linear: Коллинеарность


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

Более детально, допустим два суперпикселя i и j лежат в плоскостях с соответствующими параметрами α_i и α_j, но также лежат вдоль одной прямой линии в двумерном изображении. Для точки s_j принадлежащей суперпикселю j, в MRF минимизируется оценка расстояния (fractional distance) вдоль луча R_(j,s_j) от точки s_j, до точки лежащей в плоскости суперпикселя i вдоль того же самого луча:

Pic.20 Минимизация расстояния коллинеарных плоскостей

Pic.20 Минимизация расстояния коллинеарных плоскостей


Минимизация расстояния коллинеарных плоскостей:

Минимизация расстояния коллинеарных плоскостей

И вычисляется произведение соответствующих погрешностей h_(s_i,s_j)(.)=h_(s_i )(.) h_(s_j )(.). Более подробно, для точки s_j верно равенство R_(j,s_j)^T α_j=1/d_(j,s_j) и R_(j,s_j)^T α_i=1/d_(j,s_j)^'. Таким образом, (R_(j,s_j)^T α_i-R_(j,s_j)^T α_j)d^ дает оценку расстояния (fractional) |(d_(j,s_j)-d_(j,s_j)^')/√(d_(j,s_j )d_(j,s_j)^')| при d^=√(d^_(j,s_j ) d^_(j,s_j)^'). В данном случае, y_ij характеризует не «вероятность» границы между этими суперпикселями, а устанавливается в зависимости от длины линии, вдоль которой лежат суперпиксели и ее кривизны.



Solution accepted


Кратко про Обучение MRF


Ввиду того, что определение точных параметров для всего пространства решений модели не представляется возможным, в «Make3D» авторы использовали MCL (Multi-Conditional Learning) для того, чтобы разбить задачу обучения на меньшие подзадачи для каждой плотности распределения. MCL позволяет оптимизировать графическую модель, представляя ее произведением нескольких условных вероятностей с граничными условиями, каждая из которых оперирует как общими параметрами из объединенной модели, так и собственным подмножеством переменных с заданными условиями.

Изучение параметров θ_r∈R^524 по заранее известным истинным расстояниям (ground-truth depths) d и определенным величинам y_ij∈[0,1] и υ_(i,s_i) происходит с максимизацией функции условной вероятности logP(α|X,υ,y,R;θ_r) как:

Изучение параметров

В формуле функция f_2(.) не зависит от параметра θ_r, таким образом, изучение этого параметра сводится к задаче минимизации L_1-нормы отклонений с использованием методов линейного программирования (LP):
Изучение параметров MRF



Кратко про Решение MRF


При построении трехмерной модели сцены по загруженной фотографии, оценивается и максимальная апостериорная вероятность (MAP) для параметров плоскостей α полигонов путем максимизации функции условной вероятности logP(α|X,υ,y,R;θ_r). Решение проводится для параметров α как для непрерывных величин. Таким образом, вычисляется:

Решение MRF

Ввиду того, что нормирующий множитель Z не зависит от параметра α

Окончательное решение MRF

K это количество суперпикселей в изображении; N(i) – это множество соседей i суперпикселя; B_ij множество точек, располагающихся на границе между суперпикселями i и j, через которые моделируется соединение (connectivity); C_j это центральная точка суперпикселя j, через которую моделируется коллинеарность (co-linearity) и копланарность (co-planarity); d^_(s_i,s_j)=√(d^_(s_i ) d^_(s_j)). Каждый элемент суммы представляет собой L_1-норму линейной функции от α, таким образом, решение сводится к задаче минимизации L_1-нормы отклонений. Используя замену переменных, поставленную задачу можно переписать в матричной форме:

Окончательное решение MRF


В данном случае, решение поставленной задачи находится с использованием методов линейного программирования (LP). В проекте «Make3D» применяется модифицированный метод Ньютона для эффективного нахождения Гессиана с учетом разреженности матриц.

Pic.21 Иллюстрация к нахождению минимума функции

Pic.21 Иллюстрация к нахождению минимума функции




Практическая реализация


Исходный код и изученные параметры модели


На официальном сайте проекта "Make3D" авторы выложили в открытый доступ исходный код метода для восстановления трехмерной модели сцены по одной фотографии. Часть проекта, связанная с обучением MRF в открытом доступе не предоставляется, но можно загрузить параметры уже обученной сети Маркова (MRF).
Параметры были получены путем проведения фотосъемок с использованием лазера, для измерения истинных расстояний (ground-truth). Разрешение полученных снимков расстояний составляет 55x305, разрешение фотоснимков, по которым проводилось обучение, составляет 2272x1704. Сеть MRF была обучена на 400 экземплярах пар снимков. Объем загружаемой базы параметров составляет приблизительно 150 Мб.
Исходный код представляет собой программы, написанные на языке MATLAB, в проекте так же используются сторонние разработки, написанные на языке C/C++, которые предварительно компилируются в MEX-файлы, для работы с ними из среды MATLAB.

Исполнение программы, тестирование


Проект запускался на ноутбуке с процессором Intel Core 2 Duo T7500 CPU (2.20 Ghz), с 2 GB RAM, под управлением операционной системы Microsoft Windows 7 Home Premium, внутри виртуальной машины VMWare Workstation 7.0.0 под операционной средой Linux Mint 8 Helena, версия ядра 2.6.31-generic, с выделенным объемом 1.7 GB RAM. Программы исполнялись в среде MATLAB R2009b (7.9.0.529 32-bit).
Обработка одной фотографии в среднем занимала 270-300 секунд, и использовало порядка 1 GB RAM в среде Linux. Полученный в результат файл VRML с расширением *.wrl, занимает в среднем 120-160 Кб. Просмотр *.wrl файлов выполнялось с использованием проигрывателя «Cortona3D Viewer».




Итого


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

Чтобы не получилась подобная статья по объему, на применении подобных алгоритмов я особо останавливаться не буду. В качестве одного из самых явных примеров: возьмем распространенные сервисы, такие как Google Street View или Bing Maps 3D, в которых уже доступны объемные изображения, но в основном только центральных улиц, остальная же часть местности, как правило, остается без внимания, не говоря уже о внутренних помещениях больших супермаркетов и складов. Придерживаясь концепции Web 2.0, в которой содержание для сервисов добавляют сами пользователи, Google и Microsoft уже разрабатывают продукты "SketchUp" и "3DVIA Shape" соответственно, чтобы пользователи могли самостоятельно строить трехмерные модели зданий, которые их окружают. В данном случае, проект наподобие «Make3D» мог бы гармонично вписаться в сервисы, для осуществления первичной обработки одной или нескольких фотографий объекта с обычного телефона, помогая выстроить предварительную трехмерную модель, и тем самым упростить пользовательский ввод.


Немного файлов


Если кому-нибудь захочется самому полетать в «3D модельке», а времени Цейтнот чтобы разбираться, то предлагаю ссылку на файлик с модельками из ролика. Там 10 моделей (фотки и *.wrl), весит весь файл ~11,1 Мб, с Вас только Cortona3D Viewer

Пока мой DropBox (подскажите, пожалуйста, нормальный Fileupload — перезалью)



P.S. Картинка с юмором, о причинах публикации данной простыни:

Чем больше знаем, тем меньше удивляемся

Начало статьи: Часть 1
Tags:
Hubs:
Total votes 108: ↑96 and ↓12 +84
Views 4.6K
Comments Comments 23