vikds 5 июн 2010 в 13:56

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

12 мин

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

Публикация состоит из: Часть 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
Исходный код и изученные параметры модели
Исполнение программы, тестирование
Итого
Немножко файлов

Краткое описание алгоритма

Изображение разбивается на суперпиксели (superpixel), небольшие сегменты изображения, схожие по текстуре. Однородные предметы и даже ровные поверхности, как правило, разбиваются на несколько суперпикселей, но, тем не менее, суперпиксели лежат целиком в рамках одного предмета или поверхности, если поверхность имеет ярко выраженную границу.

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

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

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

Pic.1 Результат обработки фотографии в Make3D

Список используемых теорий и алгоритмов

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

Сегментация изображения для разбиения изображения на суперпиксели
Применение фильтров к изображению для выявления монокулярных признаков
Случайные поля Маркова (MRF) для моделирования монокулярных признаков и взаимного расположения различных частей изображения
Выделение контуров и границ на изображении (edge detection)
Элементы вычислительной геометрии, линейного программирования и др…

Модель Изинга или откуда взялась такая формула в MRF

Можно быстро пролистать, это просто пояснение, почему в MRF и в "Make3D" формула так выглядит. В общем, исторически так сложилось…

Прототипом Марковской послужила модель Изинга (Ising model), поэтому начнем с нее. Это математическая модель статистической физики, предназначенная для описания намагничивания материала.

В физической модели Изинга каждой вершине кристаллической решётки сопоставляется число, называемое спином и численное обозначаемое как "+1" или "−1", определяющее направление спина: "вверх" или "вниз". Спин – это собственный момент импульса элементарных частиц, имеющий квантовую природу и не связанный с перемещением частицы как целого.

Pic.2 Одномерная модель Изинга

Рассмотрим простейший одномерный случай, когда узлы кристаллической решетки располагаются вдоль одной прямой. Модель описывает распределение вероятностей в пространстве

всех возможных конфигураций вещества ω=(ω_0,ω_1,…,ω_n)

, где

– количество элементарных частиц, $ω_i={+1,-1}$ спин i-ой частицы. Такое распределение называется случайным полем – это случайная функция, заданная на множестве точек многомерного пространства. P(ω)

= насколько вероятно, что вещество будет находиться в состоянии, когда все узлы имеют спины равные ω=(ω_0,ω_1,…,ω_n)

Каждому из 2^n

возможных вариантов расположения спинов

, приписывается энергия, получающаяся из попарного взаимодействия спинов соседних атомов и внешнего поля:

Полная энергия системы в модели Изинга:

В формуле первая сумма берется по всем парам соседних узлов, и равняется энергии взаимодействия спинов узлов. Изинг упростил модель, принимая в расчет взаимодействие только между соседними узлами, располагающимися в непосредственной близости. Постоянная обменного взаимодействия J является характеристикой рассматриваемого материала и описывает энергию взаимодействия спинов. Если J>0, то описывает энергию притяжения ферромагнетика (attractive case), когда соседние узлы решетки стараются выстроиться в одном направлении, т.е. коллинеарно, при значениях J<0 описывает энергию отталкивания антиферромагнетика (repulsive case), когда соседние узлы решетки пытаются выстроиться в противоположных направлениях, т.е. компланарно. Вторая сумма описывает влияние внешнего магнитного поля интенсивности H, где m – характеризует магнитные свойства вещества.

В случае, когда J>0, то первая сумма будет минимальной, в случае, когда все узлы кристаллической решетки будут выстроены в коллинеарном направлении. Вторая же сумма достигает минимума, когда направление спинов узлов кристаллической решетки совпадает с направлением действия внешнего поля H.

На мы-то из физики знаем, что любая система, выведенная из состояния равновесия, стремится в состояние с наименьшим запасом энергии. Поэтому рано или поздно, модель «успокоится» и займет положение, в котором суммарная энергия U(ω)

будет равна наименьшей величине (min). Это будет наиболее вероятным ее состоянием ( P(ω)

– max).

Распределение вероятностей в пространстве

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

Распределение в модели Изинга:

где k постоянная Больцмана, T температура вещества, Z=∑_ωe^(-1/kT U(ω))

нормирующая величина.
Нам эти величины не понадобятся, важно, что формула имеет этот вид и работает с начала 19 столетия.

Для более удобной формы записи распределения вероятностей в модели сопоставим каждому i-ому узлу решетки его (личную) собственную полную энергию:

Собственная энергия узла модели Изинга:

Функция распределения Гиббса (Gibbs measure) интересна с двух позиций. Первая имеет отношение к энтропии, что вероятно и привело к ее широкому использованию в статистических исследованиях.

Pic.3 Двумерная модель Изинга

Второе важное свойство распределения в такой форме, с точки зрения теории вероятности, следующее. Пусть N_j

это множество всех соседей узла j, т.е. множество узлов в непосредственной близости. Тогда:

Свойство Марковского типа:

Это свойство носит название свойства Марковского типа. Вероятность того, что спин в точке ω_j

обращен в сторону a, при заданных спинах во всех остальных узлах кристаллической решетки, равна вероятности, в которой учитываются только спины в соседних узлах ω_k,k ∈ N_j

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

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

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

Модель в мультипликативной форме:

На практике основной целью применения случайного поля Маркова является обнаружение наиболее вероятной конфигурации

случайного поля ω: w*=argmaxw(P(w))

.

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

Теперь у нас есть формула, на ее основе будет строиться модель MRF для «Make3D»…

Эффективная сегментация изображения на графах

A picture is worth a thousand words:

Пример сегментации с различными параметрами

Эти большие одноцветные участки и есть суперпиксели, в терминологии авторов «Make3D». Более подробно в доступной форме изложено в статье "Эффективная сегментация изображений на графах".

Хотим 3D Модель и Расположение полигонов

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

Pic.4 Расположение и ориентация суперпикселя

Более формально, трехмерное расположение полигона будет определяться плоскостью, заданной параметрами α∈R^3

. Для любой точки q∈R^3

, принадлежащей этой плоскости α, выполняется равенство α^T q=1

. Кратчайшее расстояние от точки наблюдения, точки из которой был произведен фотоснимок, до плоскости вдоль опущенного на нее перпендикуляра равняется: 1/|α|. Нормальный вектор α=α/|α|

однозначно определяет ориентацию плоскости в пространстве.

Если нам дан единичный вектор R_i

(называемый лучем R_i

), соединяющий точку наблюдения (camera center) с произвольным пикселем i на изображении, принадлежащим плоскости α, то расстояние от точки наблюдения до этого пикселя i находится по формуле: d_i=1/(R_i^T α)

. Так же будет определяться расстояние до суперпикселя.

Смотреть придется шире…

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

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

Поэтому в модели MRF учитываются не только локальные монокулярные признаки (monocular cue), но и относительную взаимосвязь различных частей изображения:

Локальные особенности (local features): локальные особенности суперпикселя, монокулярные, во многом влияют на его положение и ориентацию в пространстве
Соединения (connections): за исключением границ различных объектов, наиболее вероятно, что соседние суперпиксели соединены на границах и в трехмерном пространстве
Копланарность (co-planarity): если соседние пиксели обладают схожими монокулярными особенностями (feature), и не имеют ярко выраженных границ (edge) между ними, то наиболее вероятно, что они лежат в одной и той же плоскости
Коллинеарность (co-linearity): длинные прямые линии, наиболее вероятно, так же будут длинными прямыми линиями и в трехмерноми пространстве

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

Но прежде чем перейти к модели MRF… что же такого интересного нашли авторы во всего лишь одной фотографии?

Особенности изображения

Для каждого суперпикселя в алгоритме вычисляется кортеж особенностей (features), для того, чтобы выявить монокулярные признаки (monocular cues), упомянутые прежде, а так же вычисляются особенности для определения границ и преломления суперпикселей (объектов на изображении). Для того чтобы алгоритм сделать более устойчивым и гибким, чтобы он смог восстановить сцену по произвольному фотоснимку, не обязательно подобному тем, на которых проводилось обучение модели, вычисляется относительно большое количество особенностей (features).

Монокулярные особенности изображения

Для каждого суперпикселя i, вычисляются статистические особенности имеющие отношение к текстуре изображения, форме и положению. В проекте «Make3D» используется 17 фильтров F_n (x,y)

, где n=1,…,17:

9 масок Laws для вычисления средней интенсивности изображения (averaging), выявления пятен (spot detection) и границ (edge detection)
6 масок для выявления ориентированных границ (oriented edge detection), повернутых на (30°×k), k=0,…,5 градусов
2 цветовых канала в Cb и Cr в YCbCr формате

Pic.5 Маски, применяемые в Make3D

Pic.6 Два канала цвета Cb и Cr

В результате применения фильтров к суперпикселю i изображения I(x,y) формируется 34-мерный вектор особенностей, вычисляемый как E_i (n)=∑_((x,y)∈S_i)|I(x,y)*F_n (x,y) |^k

E_i (n)=∑_((x,y)∈S_i)|I(x,y)*F_n (x,y) |^k

, где k={2,4}, что соответствует энергии (energy) и эксцессу (kurtosis). Это дает по 34 значения для каждого суперпикселя. Дополнительно для суперпикселя i вычисляется 14 особенностей имеющих отношение к его положению на фотоснимке и форме, наподобие:

Pic.7 Особенности расположения суперпикселя

В проекте "Make3D" учитываются не только особенности отдельного суперпикселя, а так же принимается в расчет «контекст» в виде, особенностей (features) 4-х самых больших соседних суперпикселей, и данная операция повторяется в 3-х различных масштабах. Таким образом, каждый суперпиксель содержит дополнительно информацию и об изображении вокруг него, что приводит к более качественным результатам, чем если ограничиться только локальными особенностями суперпикселя. В конечном итоге с каждым суперпикселем ассоциируется вектор, который содержит 34*(4+1)*3+14=524 элемента, т.е. x∈R^524

Pic.8 Особенности каждого суперпикселя рассматриваются в контексте

Pic.9 Выделение особенностей изображения на различных масштабах

Pic.10 На одном уровне, каждый суперпиксель соединяется с 4 max соседями

Границы и преломления

Для определения границ используются параметры $y_ij∈{0,1}$ определяющие наличие границы между двумя суперпикселями ("edgel"). В виду того, что определение границ происходит, как правило, неточно, то в модели используются не дискретные величины, а более «мягкие» условия для y_ij∈[0,1]

. Более формально, равенство y_ij

=0 означает наличие границы объектов (occlusion boundary) или перегиба (unfold) между суперпикселями i и j, а y_ij

=1 означает отсутствие, т.е. суперпиксели лежат на плоской поверхности.

Pic.11 Выделение границ изображения (edge detection) – edgels

Pic.12 Edge detection

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

В этой работе был предложен подход для определения границы объектов (edge detection), с использованием обучения учитывающего освещение, цвет и текстуру участков изображения. Воспользовавшись их результатом, в «Make3D» величина y_ij

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

особенности (features) пары суперпикселей i и j
параметр модели (после обучения)

Если два соседних суперпикселя на изображении обладают резко различающимися особенностями (features), то человек скорей всего тоже будет их воспринимать как два различных объекта. Таким образом, граница между двумя суперпикселями с резко различающимися особенностями с большой вероятностью представляет собой границу объектов (occlusion boundary) или перегиб (unfold). Для выяснения насколько сильно отличаются особенности двух суперпикселями i и j в «Make3D» проводится 14 различных сегментаций изображения: для 2-х различных масштабов и с 7 различными наборами параметров сегментации для выявления особенностей текстуры, цвета и границ.

Pic.13 Пример сегментации одного изображения с различными параметрами

Pic.14 y — 14-мерные вектора различия суперпикселей при различных сегментациях

В полученном после сегментации 14-мерном векторе ϵ_ij

каждый элемент ${ϵ_ij_k}$ представляет собой признак: полпали ли оба суперпикселями i и j в один и тот же сегмент при выполнении i-ой сегментации. Ведь два суперпикселя, которые оказались в одних и тех же сегментах во всех 14 случаях, наиболее вероятно будут копланарными или соединены между собой. Выводы о наличии границ между суперпикселями, сделанные на основе множественной сегментации, являются более надежными, чем при единственной сегментации. Этот вектор ϵ_ij

является входным параметром при определении «мягкой» границы y_ij∈[0,1]

между двумя суперпикселями i и j.

Pic.15 Параметр y (справа), указывающий наличие или отсутствие границы

MRF Input и Output

Теперь можно подвести промежуточный итог:
В модели MRF участвует 5 типов параметров. Входными являются:

Переменные X, имеющие отношение к вычисленным особенностям (features) изображения
Переменные θ, вычисленные эмпирическим путем (параметры обученной модели)

При расчете так же учитываются так же условные параметры (conditioned):

Параметры υ представляет собой «уровень доверия» (confidence) к расстоянию до объекта, вычисленному опираясь только на локальные свойства участка изображения
Параметры y указывают наличие или отсутствие четкой границы между объектами на изображении. Эти параметры используются при выявлении копланарности и соединений суперпикселей

Высчитываемыми в MRF параметрами являются:

Параметры α, задающие расположение и ориентацию плоскостей в пространстве, на которых и располагаются полигоны в трехмерной модели

Pic.16 Модель MRF объединяет в себе все особенности изображения, для нахождения 3D

Что будет делать MRF? Цель: min(погрешность определения расстояния)

При построении трехмерной модели сцены относительная погрешность определения расстояния является наиболее значимой. Для истинного расстояния (ground-truth depth)

и оцененного в модели

, относительная ошибка определяется как ((d^-d))/d=d^/d-1

. Таким образом, модель MRF будет построена с целью минимизации этой величины.

Продолжение: тут

Теги:

Хабы:

Алгоритмы

Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку