Трёхмерная реконструкция лица человека по его изображениям (1006006), страница 6
Текст из файла (страница 6)
В дальнейшем эталонную поверхность будемназывать шаблоном, а входную — целью или целевой поверхностью.Согласно [1], зарегистрировать цель относительно шаблона означаетнайти такое отображение шаблона на цель, которое значимым точкам шаблона сопоставляет таковые точки целевой поверхности. Различные методыпредлагают разные подходы к тому, как понимать это сопоставление.Пусть шаблон задан в виде множества вершин и множества рёбер ℰ: = (, ℰ).Поверхность-цель может быть задана в любой форме, допускающей нахождение для заданной точки пространства x ∈ R3 ближайшей к ней точкиy ∈ этой поверхности.Определение 29 Любое преобразование X : R3 → R3 назовём регистрацией.Каждая регистрация переводит вершины модели-шаблона в некоторыедругие точки из R3 : ′ = X()Можно искать преобразование X в ограниченном классе преобразований, что мотивирует следующие определения.Определение 30 Регистрация X называется жесткой (rigid), если она является преобразованием подобия:X(x) = Rx + tгде R – матрица поворота, – число, а t – вектор.42Определение 31 Регистрация, не являющаяся жесткой, называется нежесткой (non-rigid).В частности,Определение 32 Регистрация X называется аффинной (affine), если онаявляется аффинным преобразованием:X(x) = Ax + tгде A – произвольная матрица, а t – вектор.Если теперь задать функцию (X), оценивающую близость параметризованного шаблона ′ = (X(), ℰ) к целевой повехрности , то задачарегистрации сводится к поиску экстремума этой функции.Далее излагается два способа построения этой функции и методы поискаих экстремумов, отвечающие специфике задачи.1.2.4.2Алгоритмы итеративного поиска ближайших точек (IterativeClosest Points, ICP)Пусть целевая модель задана набором из своих точек-вершин: =y1 , .
. . , y .Центральная идея семейства алгоритмов ICP (Iterative Closest Point algorithm,алгоритмы итеративного поиска ближайших точек) — в следующем:а) на очередной итерации для каждой точки модели-шаблона ищетсяближайшая точка модели-целиб) затем для каждой точки шаблона ищется деформация (преобразованиепространства), приближающая эту точку к найденной на предыдущемшаге ближайшей точке цели.в) после чего начинается следующая итерацияВ зависимости от особенностей регистрируемых поверхностей на деформации накладываются различные ограничения, например:- деформациям соседних точек шаблона не дают сильно отличатьсядруг от друга43- деформации берутся из заданного класса (например, для поверхностейтвёрдых тел разумно использовать ортогональные преобразования)- могут быть учтены заранее известные соответствия между характерными точками шаблона и цели (в случае лица это антропометрическиеточки, такие, как уголки глаз, губ, кончик носа и т.д.)В работе [1] предложен вариант этого алгоритма, названный “Optimalstep non-rigid ICP”.
Алгоритм был создан для регистрации человеческих лицв рамках работы над базельской моделью. Согласно этой статье алгоритмпоказывает хорошие результаты на деформируемых поверхностях: высокоекачество регистрации, достаточно низкую чувствительность к начальномуприближению.Как ясно из названия, искомая регистрация является нежесткой. Приэтом позволяется регулировать “жесткость” деформации (понимаемую втом смысле, что преобразования для соседних вершин не должны сильноотличаться друг от друга).
Фраза “optimal step” (оптимальный шаг) означает, что на каждом шаге процедуры ICP найденная деформация являетсяоптимальной (для тех вершин, которые были зафиксированы перед началомшага).На очередной итерации для каждой вершины модели-шаблона x ∈ ищется аффинное преобразование X , сдвигающее её в сторону найденнойближайшей вершины. Это преобразование можно записать в виде матрицыX размеров 3 × 4 (вершины записываются в однородных координатах), аиз этих матриц составить матрицу X = (X1 .
. . X ) размеров 4 × 3 —это и будет регистрация. Таким образом, ищется нежесткая регистрация,локально в каждой точке являющаяся аффинной.Казалось бы, раз ищется преобразование одной точки, незачем использовать целую матрицу X , достаточно одного вектора. Однако вектор неописывает аффинное преобразование, и тогда мы теряем возможность сравнивать преобразования для соседних вершин. Поэтому, несмотря на избыточность в отношении вычислений (вместо трёх чисел нужно искать двенадцать), ищутся именно аффинные преобразования.Под расстоянием между точками понимается обычное евклидово рас-44стояние в R3 :⎯⎸ 3⎸∑︁(x, y) = ‖x − y‖ = ⎷ (x − y )3 ,=1а под расстоянием от точки до множества — нижняя грань расстояний отточки до точек множества:(x, ) = inf (x, y).y∈Предлагается целевая функция , состоящая из трёх слагаемых:а) компонент, учитывающий расстояния до выбранных ближайших точек (distance term) (X) =∑︁ 2 (X v , )v ∈где — вес вершины v , учитывающий надёжность найденной длянеё ближайшей точки (если ближайшая точка не найдена, вес равеннулю)б) компонент, учитывающий жесткость деформации (stiffness term):∑︁‖(X − X )G‖2 (X) ={,}∈ℰгде ‖‖ =√︁∑︀ ∑︀| |2 — фробениусова норма матрицы, G =diag(1, 1, 1, ), – “коэффициент жесткости”.в) компонент, учитывающий заранее отмеченные точки (landmark term):∑︁ (X) =‖X v − ‖2(v , )∈ℒгде ℒ – множество заранее установленных соответствий между точками шаблона и целиТаким образом, целевая функция принимает вид(X) = (X) + (X) + (X)где задаёт допустимость отклонения деформации от жесткой, а – важность или надёжность заранее установленных соответствий.45Если соответствия между вершинами шаблона и цели найдены, то первое слагаемое целевой функции перепишется через расстояние между точками (вместо расстояния между точкой и множеством):˜ (X) =∑︁ ‖X v − u ‖2 = ‖W(DX − U)‖2 ,v ∈где⎛⎜D=⎜⎝1W = diag(1 , .
. . , )⎞...(︁)︁⎟⎟ , U = 1 . . . ⎠Второе слагаемое (отвечающее за жесткость деформации) также можнопереписать в матричной форме. На модель-шаблон можно смотреть как нанеориентированный граф. Построим по нему ориентированный граф: множество его вершин совпадает с ℰ, а каждому ребру (v , v ) из ℰ соответствует одна из двух дуг: из v в v или обратно (как будет видно дальше,направление нам не важно). Обозначим через M матрицу инцедентностиего дуг и вершин:- в ней строк (по количеству рёбер в графе, представляющем модель)и столбцов (по количеству вершин),- дуге из v в v соответствует столбец, в котором -ый элемент равен-1, -ый элемент равен 1, а остальные равны нулю.Тогда stiffness term можно записать, использовав кронекерово произведение⊗ : (X) = ‖(M ⊗ G)X‖2Последнее слагаемое (отвечающее за заранее отмеченные точки) аналогично первому перепишем так: (X) = ‖D X − U ‖2где D – подматирца D: в ней оставлены строки, соответствующие вершинам, для которых указано соответствие, а U = (1 .
. . ) – матрица,составленная из соответствющих им вершин модели-цели.46Теперь можно записать всю целевую функцию в матричной форме:⃦⎛⎞⎛ ⎞⃦2⃦⃦0 ⃦⃦ M ⊗ G⎟⎜ ⎟⃦⃦⎜⎜ WD ⎟ X − ⎜ U ⎟⃦ = ‖AX − B‖2(X) = ⃦⃦⎝⎠⎝ ⎠⃦⃦⃦⃦DU ⃦Минимум получившейся квадратичной функции можно найти явно методом наименьших квадратов (см., например, [18]).
В работе [1] доказывается, что матрица A — полного ранга, и поэтому задача имеет единственноерешение.1.2.4.3Алгоритмы согласованного дрейфа точек (Coherent Point Drift,CPD)В работах [10] и [11] предлагается другой интересный алгоритм регистрации, в известном смысле обобщающий подход ICP.Одна из идей метода в том, что для каждой вершины шаблона x ∈ вместо единственной вершины цели y ∈ ищется набор весов (1 , .
. . , ), характеризующих близость этой вершины к вершинам целевой поверхности.Для поиска весов используется вероятностная интерпретация задачи: вершины шаблона считаются центрами гауссовских распределений, а вершиныцели — результатами измерений, порождаемых смесью этих распределений.Значения весов находятся с помощью EM-алгоритма, который описан ниже.Для различных классов искомой регистрации (жесткая, аффинная, нежесткая) удаётся аналитически преобразовать целевую функцию EM-алгоритма.Для нежесткой регистрации вводятся ограничения на деформацию, приводящие к дополнительному слагаемому (регуляризатору) в целевой функции.
Для уточнения формы регуляризатора привлекается теория согласованности движения (motion coherence theory, см. статьи [15], [14]), что и далоалгоритму его название.1Теория согласованности движения (motion coherence theory). Тео-рия разработана авторами Alan Yuille и Norberto Grzywacz для нужд оценки47движения методами машинного зрения.Изучается следующая задача. В произвольном пространстве движетсягруппа точек x1 , .
. . , x . Движение точек согласовано: хотя перемещениекаждой отдельной точки случайно, “как целое” точки движутся в согласии скаким-то законом. (Случайность перемещений отдельных точек может бытькак частью физических процессов задачи, так и ошибками измерений.) Требуется оценить этот закон по движению отдельных точек.Определение 33 Под движением понимается поле скоростей v : R3 → R3в той области пространства, где находятся отслеживаемые точки.Процедура делится на две стадии: измерительную (measuring) и сглаживающую (smoothing).
Предполагается, что каким-либо образом на первойстадии мы получаем оценки (V ), = 1, скоростей в точках x , = 1, ,где : R3 → R — какая-либо функция. Тогда на второй стадии мы ищемдвижение как функцию, минимизирующую следующий функционал:(v) =∑︁2( (V ) − (v(x))) + =1∫︁ ∑︁∞ ‖∇ v‖2=0Приводятся некоторые соображения о том, как должны быть выбраныкоэффициенты во втором слагаемом:- поскольку желаемое движение должно приближаться к нулю при удалении от области, где располагаются наблюдаемые точки, коэффициент 0 не равен нулю.- физический смысл старших производных ∇ v, > 1 — интенсивность взаимодействия точек на расстоянии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
