Продолжение статьи про проект 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:
В данной формуле:
представляют собой параметры плоскости для суперпикселя i. Для всех 
точек i-ого суперпикселя 
обозначает вектор особенностей (features) для точки 
изображения. 
обозначает множество всех особенностей (features) суперпикселя i. Аналогично, 
обозначает множество всех лучей к суперпикселю i. Параметр υ представляет собой уровень доверия к расстоянию до суперпикселя, т.е. насколько мы уверенны в том расстоянии, которое модель предположила опираясь только на локальные особенности (features) изображения.MRF будет «стягивать» в min кучу вышеперечисленных расстояний.
По аналогии с распределением Гиббса, MRF будет подыскивать состояние системы с наименьшим запасом энергии (в нашем случае – это будет «погрешность определения расстояний») – это наиболее вероятное состояние модели.
Теперь о типах расстояний подробнее…
1. Local features: Предварительное определение расстояния по локальным особенностям
В формуле MRF первый множитель
представляет собой функцию моделирующую параметры плоскостей в зависимости от особенностей (features) изображения . Пусть истинное расстояние до точки , расположенной на i-ом суперпикселе, будет равно 
, тогда верно равенство: 
, где 
представляет собой луч, соединяющий точку наблюдения (camera center) с точкой изображения. Тогда, если модель определила предварительное расстояние по локальным особенностям изображения (features) как 
, то относительная погрешность равняется:Относительная погрешность:
Pic.17 Погрешность определения расстояний по локальным признакам
Таким образом, с целью минимизации относительной погрешности по всем точкам
-ого суперпикселя, в модели MRF зависимость расстояний до суперпикселей и локальных особенностей (features) изображения моделируется формулой:Минимизация локальной погрешности:
Параметрами в данной модели являются
. В "Make3D" используются различные параметры для различных рядов изображения r=1,…,11 исходя из предположения, что фотоснимок, скорее всего, делался горизонтально и потому имеет различные статистические закономерности для различных частей изображения: вверху чаще всего будет небо или крыша, внизу изображения чаще всего будет газон или дорога. Параметры 
представляют собой уровень доверия к предварительно определенному расстоянию 
до точки .Переменные
, т.е. уровни доверия к расстоянию до точки , выставленному опираясь только на локальные свойства суперпикселя, изучаются предварительно по монокулярным особенностям изображения (monocular fetures), оценивая полученные результаты с использованием истинных расстояний (ground-truth) 
до суперпикселя по формуле: 
.Второй множитель в формуле MRF
представляет собой функцию, моделирующую отношения между параметрами плоскостей и 
для двух суперпикселей i и j. В свою очередь она раскладывается в произведение 3-х функций 
, устанавливающих взаимосвязи различных типов: соединение, копланарность, коллинеарность для точек 
, принадлежащих соответствующим суперпикселям.Моделирование отношения суперпикселей:
2. Connection: Соединение
Выбираются 2 пары точке
, 
, лежащие на границе соседних суперпикселей i и j. Для того чтобы в восстановленной трехмерной модели сцены эти суперпиксели были соединены, если они соединены в действительности, то в MRF минимизируется расстояние между этими точками.Pic.18 Минимизация расстояния соединения
Для расстояния от точки наблюдения (camera center) до точки
выполняется равенство , аналогично для точки выполняется 
. Величина 
дает оценку расстояния (fractional distance) 
при 
, где 
и 
предварительные расстояния до соответствующих суперпикселей.Минимизация в MRF проводится с использованием формулы:
Стоит отметить, что если суперпиксели принадлежат различным объектам и точки
, лежат на границе этих различных объектов, то 
=0 и «соединение», таким образом, не производится.3. Co-planar: Копланарность
Выбираются 3 пары точек (
,), 2 пары точек лежащие на границе соседних суперпикселей i и j, как и прежде, и третья пара 
точек, лежащая в центре соответствующего суперпикселя. Для того чтобы в восстановленной трехмерной модели сцены эти суперпиксели лежали в одной плоскости, если это имеет место в действительности, то в MRF минимизируется расстояние между плоскостями, на которых лежат точки вдоль одного луча.Pic.19 Минимизация расстояния копланарных плоскостей
Минимизация в MRF проводится с использованием формулы:
И вычисляется произведение соответствующих погрешностей
, следует отметить, что если два суперпикселя копланарны, то 
=1. Если эти суперпиксели копланарны, но находятся на некотором расстоянии друг от друга, т.е. первые две пары точек лежат не на границы, а разнесены в пространстве, то эта метрика все равно будет работать.4. Co-linear: Коллинеарность
Допустим, два суперпикселя i и j лежат вдоль одной длиной прямой на фотоснимке. В трехмерном пространстве бесконечное число прямых можно спроецировать на эту прямую в двумерном. Тем не менее, длинная прямая на фотоснимке с большой долей вероятности так же будет длиной прямой и в пространстве. Поэтому в модели "Make3D" также минимизируется отклонение точки из суперпикселя j от прямой, проходящей через плоскость, в которой лежит суперпиксель i.
Более детально, допустим два суперпикселя i и j лежат в плоскостях с соответствующими параметрами
и , но также лежат вдоль одной прямой линии в двумерном изображении. Для точки принадлежащей суперпикселю j, в MRF минимизируется оценка расстояния (fractional distance) вдоль луча 
от точки , до точки лежащей в плоскости суперпикселя i вдоль того же самого луча:Pic.20 Минимизация расстояния коллинеарных плоскостей
Минимизация расстояния коллинеарных плоскостей:
И вычисляется произведение соответствующих погрешностей
. Более подробно, для точки верно равенство и 
. Таким образом, 
дает оценку расстояния (fractional) 
при 
. В данном случае, характеризует не «вероятность» границы между этими суперпикселями, а устанавливается в зависимости от длины линии, вдоль которой лежат суперпиксели и ее кривизны.Solution accepted
Кратко про Обучение MRF
Ввиду того, что определение точных параметров для всего пространства решений модели не представляется возможным, в «Make3D» авторы использовали MCL (Multi-Conditional Learning) для того, чтобы разбить задачу обучения на меньшие подзадачи для каждой плотности распределения. MCL позволяет оптимизировать графическую модель, представляя ее произведением нескольких условных вероятностей с граничными условиями, каждая из которых оперирует как общими параметрами из объединенной модели, так и собственным подмножеством переменных с заданными условиями.
Изучение параметров
по заранее известным истинным расстояниям (ground-truth depths) 
и определенным величинам ![y_ij∈[0,1]](https://habr.com/images/px.gif#%3D%22http%3A%2F%2Fimg267.imageshack.us%2Fimg267%2F6086%2Fform31ysoftbelong.png%22 "y_ij∈[0,1]")
и происходит с максимизацией функции условной вероятности 
как:
В формуле функция
не зависит от параметра 
, таким образом, изучение этого параметра сводится к задаче минимизации 
-нормы отклонений с использованием методов линейного программирования (LP):
Кратко про Решение MRF
При построении трехмерной модели сцены по загруженной фотографии, оценивается и максимальная апостериорная вероятность (MAP) для параметров плоскостей α полигонов путем максимизации функции условной вероятности
. Решение проводится для параметров α как для непрерывных величин. Таким образом, вычисляется:
Ввиду того, что нормирующий множитель Z не зависит от параметра α
K это количество суперпикселей в изображении; N(i) – это множество соседей i суперпикселя;
множество точек, располагающихся на границе между суперпикселями i и j, через которые моделируется соединение (connectivity); 
это центральная точка суперпикселя j, через которую моделируется коллинеарность (co-linearity) и копланарность (co-planarity); 
. Каждый элемент суммы представляет собой -норму линейной функции от α, таким образом, решение сводится к задаче минимизации -нормы отклонений. Используя замену переменных, поставленную задачу можно переписать в матричной форме:
В данном случае, решение поставленной задачи находится с использованием методов линейного программирования (LP). В проекте «Make3D» применяется модифицированный метод Ньютона для эффективного нахождения Гессиана с учетом разреженности матриц.
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
