Dense Non-rigid Surface Registration Using High-Order Graph Matching

一.摘要 ? ? ? 提出高階圖匹配方程來(lái)解決非剛性表面配準(zhǔn)問(wèn)題，單階項(xiàng)描述了幾何和外觀相似性（曲率和紋理），高階項(xiàng)對(duì)內(nèi)部嵌入能量（intrinsic embedding energy）進(jìn)行建模。 ? ? ? 三個(gè)創(chuàng)新點(diǎn)： ? ? ? 1、將3D表面配準(zhǔn)轉(zhuǎn)化為圖匹配問(wèn)題，結(jié)合了幾何外觀相似性和內(nèi)在信息； ? ? ? 2、用高階圖匹配算法解決了非凸優(yōu)化問(wèn)題； ? ? ? 3、有效的兩級(jí)優(yōu)化算法，限制了稠密表面配準(zhǔn)的搜索空間。 二、引言 ? ? ? 問(wèn)題中往往有局部的高維度的自由形變，為了解決這個(gè)問(wèn)題，多種現(xiàn)有方法是通過(guò)將表面嵌入到一個(gè)保持地線或角度的正則域中來(lái)獲得密集點(diǎn)的對(duì)應(yīng)關(guān)系。這種嵌入需要一組初始的特征對(duì)應(yīng)或邊界條件。但上述方法難以找到可靠的特征對(duì)應(yīng)點(diǎn)和連續(xù)的邊界條件。為了解決這個(gè)問(wèn)題，[34]考慮了一種優(yōu)先級(jí)驅(qū)動(dòng)的策略，在等距假設(shè)的基礎(chǔ)上尋找稀疏特征的對(duì)應(yīng)關(guān)系。在[22]中引入了一種Mobius投票方案，在兩個(gè)稀疏特征集之間尋找對(duì)應(yīng)關(guān)系。但稠密配準(zhǔn)效果不好。此外，由于大多數(shù)表面形變不是等距的，僅考慮內(nèi)在信息會(huì)引入誤差，考慮外在相似性也很重要。 ? ? ? ?近年來(lái)，圖匹配成為一個(gè)建立特征對(duì)應(yīng)的有效框架，結(jié)合了表面相似性和幾何兼容性。以往已將其應(yīng)用于圖像特征。僅考慮單階匹配，即指派問(wèn)題。對(duì)于二階匹配問(wèn)題（pairwise matching ），[28]提出采用雙分解方法，這對(duì)于求解非凸能量函數(shù)很有用。對(duì)于高階匹配問(wèn)題，以往包括概率超圖、張量度量，當(dāng)能量函數(shù)為凸時(shí)優(yōu)化效果較好，非凸未知。 ? ? ?圖匹配已經(jīng)成功應(yīng)用于二維圖像，但三維表面不能再歐幾里得二維域內(nèi)表示，所以兩點(diǎn)的距離無(wú)法以封閉形式計(jì)算。根據(jù)單值化理論，任何3D 表面可以被保形映射到2D域。?然而，這種保形映射并不是唯一的。通過(guò)Mobius變換可以捕捉到保角映射集合。在將拓?fù)涞谋砻娴葍r(jià)于球體的情況下，至少需要三個(gè)對(duì)應(yīng)關(guān)系來(lái)確定一個(gè)唯一的保形映射，可以以封閉形式計(jì)算，這就可以將圖匹配應(yīng)用于表面配準(zhǔn)。由于Mobius變換是通過(guò)在曲面上固定任意三個(gè)點(diǎn)來(lái)唯一確定的，所以我們可以通過(guò)高階圖的相互作用來(lái)有效地模擬嵌入的能量。 ? ? ?思路：曲率和紋理等測(cè)量方法描述幾何和外觀相似性，高階圖相互作用對(duì)內(nèi)部嵌入能量建模。這些度量是在一個(gè)高階圖匹配框架中使用的，該框架使用偽布爾公式以有效的方式解決。這種方法將高階項(xiàng)降低為二次項(xiàng)[15]，并基于雙分解技術(shù)得到近似最優(yōu)解。最后，提出了一種通過(guò)候選選擇和局部圖匹配來(lái)約束搜索空間的層次算法，該算法允許以子頂點(diǎn)精度實(shí)現(xiàn)稠密的表面配準(zhǔn)。 三、數(shù)學(xué)方程 ? ? ? ? 通過(guò)對(duì)方程的全局優(yōu)化實(shí)現(xiàn)，方程包括形變消耗和匹配消耗。能解決含有部分重疊的非等距表面配準(zhǔn)問(wèn)題。由于這種高階圖匹配具有非凸能量函數(shù)，一般很難直接用[13]等現(xiàn)有技術(shù)來(lái)求解。本文采用偽布爾公式將高階項(xiàng)減少到二次項(xiàng)。因此，基于dual分解技術(shù)可以得到全局最優(yōu)或近似最優(yōu)解。 1、偽布爾方程 ? ? ? ?? 大多數(shù)算法選擇松弛求解，這里將其降為二階項(xiàng)
這樣高階圖匹配問(wèn)題變?yōu)閭尾紶杻?yōu)化問(wèn)題：
? ? ? ?因?yàn)檎禂?shù)θ∞編碼匹配約束,能量函數(shù)5非凸,一般來(lái)說(shuō)這是一個(gè)np難問(wèn)題。偽布爾公式的優(yōu)點(diǎn)是，理論上任何高階項(xiàng)都可以簡(jiǎn)化為一個(gè)二次項(xiàng)。本文采用靈活的雙分解技術(shù)，得到近似最優(yōu)解。
2、勢(shì)函數(shù) ? ? ? ?僅考慮一階三階項(xiàng) （1）一階勢(shì) ? ? ? ?旋轉(zhuǎn)圖像 （2）高階勢(shì) ? ? ? ? ? 根據(jù)單值化定理，任何三維表面都可以被展平到一個(gè)規(guī)范的2D域，因此，每個(gè)特征點(diǎn)在復(fù)平面上都有一個(gè)參數(shù)坐標(biāo)。這種保角映射的靈活性在于可以用一個(gè)Mobius變換來(lái)表示，這個(gè)變換可以通過(guò)固定表面上的任意三個(gè)點(diǎn)來(lái)唯一地確定。我們基于Mobius變換計(jì)算兩個(gè)triplets之間的匹配分值作為的變形誤差。
? ? ? ? ?僅考慮Mobius變換會(huì)導(dǎo)致等距模糊。因而再考慮表面的高斯分布。高斯映射被定義為平面上每個(gè)點(diǎn)上的法線到單位球的映射，表達(dá)了外部幾何信息。每個(gè)triplets?都有方向，當(dāng)且僅當(dāng)兩個(gè)triplets的法線有相同的符號(hào)，他們的方向才相同。如下： ?3、優(yōu)化和計(jì)算復(fù)雜度 ? ? ? ?對(duì)偶分解是將原問(wèn)題分解成幾個(gè)容易解決的子問(wèn)題。 ? ? ? ?theta代表單、雙、三階項(xiàng)的權(quán)重向量；I代表子問(wèn)題的集合； ? ??rou代表每個(gè)子問(wèn)題的權(quán)重。原問(wèn)題可以這樣解決：更新每個(gè)子問(wèn)題σ的參數(shù)θσ,對(duì)偶問(wèn)題的能量增加。 ? ? ? ?同時(shí)有以下分解約束： ? ? ? ? 我們把原問(wèn)題分解成三個(gè)子問(wèn)題： （1）僅考慮單階項(xiàng)的線性問(wèn)題，即線性指派問(wèn)題； （2）高階偽布爾子問(wèn)題通過(guò)將高階項(xiàng)降為二階項(xiàng)，可以用QPBO算法求解； （3）將原表面分為小區(qū)域的局部子問(wèn)題可以用窮舉法在每個(gè)小區(qū)域內(nèi)尋找最優(yōu)解； 四、稠密表面配準(zhǔn) ?? ?1 ? 兩級(jí)優(yōu)化策略：稀疏特征匹配+稠密點(diǎn)匹配 ? ? ? ?由于初始特征點(diǎn)是在網(wǎng)格邊緣的頂點(diǎn)和中間點(diǎn)選擇的，如果網(wǎng)格分辨率較低，匹配結(jié)果可能是不可靠的。為了解決上述問(wèn)題，我們考慮了由不同的Mobius變換引起的所有正形映射，它們由兩個(gè)表面之間的每三個(gè)對(duì)應(yīng)關(guān)系決定，用于密集點(diǎn)匹配。 ? ??? ? Candidate Voting(候選投票): 在稀疏階段計(jì)算出了兩個(gè)表面間的稀疏對(duì)應(yīng)點(diǎn)，由于表面形變不是等距的，我們提出基于莫爾比斯變換的投票策略來(lái)彌補(bǔ)近似誤差。給定任意三個(gè)對(duì)應(yīng)點(diǎn)對(duì)，莫爾比斯變換都可以以封閉形式計(jì)算。所以S1上任一點(diǎn)都會(huì)映射到S2上一個(gè)不同的候選位置。因此通過(guò)考慮特征對(duì)應(yīng)的所有可能的變換，可以得到原表面到目標(biāo)表面的所有候選對(duì)應(yīng)關(guān)系。 ? ? ? ?Candidate clustering（候選聚類）：S2上的投票候選點(diǎn)是通過(guò)對(duì)齊三個(gè)對(duì)應(yīng)關(guān)系得到的，該匹配能量中存在莫爾比斯代價(jià)，因此該代價(jià)越低且曲率和紋理越接近，兩個(gè)點(diǎn)匹配的可能性越大。因此定義每個(gè)候選匹配點(diǎn)的可能性：

2 局部高階圖匹配 ? ? ? ? 新目標(biāo)是為每個(gè)稠密點(diǎn)尋找一個(gè)好的局部匹配位置，該問(wèn)題類似于高階圖匹配問(wèn)題。由于候選投票策略已經(jīng)去除了由莫爾比斯變換導(dǎo)致的模糊，現(xiàn)在僅需要考慮基于紋理和幾何相似性的匹配代價(jià)，以及方向連續(xù)性。在單值化域內(nèi)，每個(gè)三角形和他的匹配三角形應(yīng)該有相同的方向，即無(wú)翻轉(zhuǎn)。
? ? ? 并不能保證每個(gè)點(diǎn)都有至少一個(gè)匹配點(diǎn)，因此，我們刪除沒(méi)有任何匹配的候選點(diǎn)，并通過(guò)Delaunay三角測(cè)量算法在單值化域中獲得對(duì)S1剩余點(diǎn)的三角剖分。 ? ? ? 假設(shè)S1上每個(gè)點(diǎn)p只能有最多一個(gè)候選點(diǎn)，則有如下約束： ? ? ? 這樣，可用上述優(yōu)化算法解決這個(gè)問(wèn)題。 ? ? ? 與高階圖匹配算法相比，我們的局部圖匹配算法的一個(gè)主要優(yōu)點(diǎn)是，每個(gè)點(diǎn)的匹配候選數(shù)通常小于6，因此，變量的數(shù)量非常小。在局部地匹配n個(gè)點(diǎn)時(shí)，只有O(n)個(gè)變量和O(n)個(gè)三階項(xiàng)，因?yàn)槊芗c(diǎn)在平面參數(shù)域中是三角化的。

總結(jié)

以上是生活随笔為你收集整理的表面配准论文1--基于高阶图匹配方法的稠密表面配准的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。