楊 熙 黃健民(廣西師范大學(xué)計算機科學(xué)與信息工程學(xué)院 廣西 桂林 541004) (廣西師范大學(xué)虛擬現(xiàn)實重點實驗室 廣西 桂林 541001)

0 引 言

在計算機圖形學(xué)和幾何處理中，形狀對應(yīng)是最基本的問題之一，隨著微軟Kinect掃描儀、3D等技術(shù)的發(fā)展，在許多領(lǐng)域(如分子生物學(xué)、機械工程、醫(yī)學(xué)圖像分析)中形狀對應(yīng)越來越受到人們的重視，找到內(nèi)在的三維形狀之間的對應(yīng)關(guān)系可應(yīng)用于三維掃描對齊、紋理映射、形狀變形和動畫等[1]。

由于形狀具有較大的非剛性變形，使得尋找到一種較好的對應(yīng)具有很大的挑戰(zhàn)性，在過去的幾十年里，大量的研究學(xué)者致力于三維形狀的對應(yīng)關(guān)系。早期的形狀對應(yīng)方法側(cè)重于剛性形狀，而剛性形狀之間的轉(zhuǎn)換可以通過平移、旋轉(zhuǎn)和比例因子等參數(shù)來參數(shù)化，因此，這些參數(shù)可以通過迭代等優(yōu)化方法進行評估。隨著研究的深入，一大批學(xué)者開始把目光轉(zhuǎn)移到非剛體的形狀對應(yīng)，與剛性形狀對應(yīng)相比，建立非剛體形狀之間的對應(yīng)關(guān)系更具挑戰(zhàn)性。其中非剛性的形狀匹配可以表述為圖匹配問題，即點對點對應(yīng)，而等距屬性是尋找模型間對應(yīng)關(guān)系的一個重要依據(jù)[2]。文獻[3]通過尋找測地屬性來試圖建立對應(yīng)關(guān)系，但對于三維網(wǎng)格模型之間拓?fù)浣Y(jié)構(gòu)變化比較大的情況下，仍然不能取得讓人滿意的結(jié)果。文獻[4]提出了一種新的多維尺度分析算法(Multi-dimensional scale，MDS)，并將此算法與擴散距離相結(jié)合去解決測地距離對于拓?fù)浣Y(jié)構(gòu)變化較大而不能取得良好效果的問題。雖然結(jié)果令人滿意，但是該算法效率較低。Ovsjanikov等[5]提出了新的方法去解決三維網(wǎng)格模型的對應(yīng)問題，即通過拉普拉斯-貝爾特拉米算子嵌入譜空間，以簡化對應(yīng)關(guān)系去提高計算的效率，但嵌入對應(yīng)對于頂點數(shù)目比較多的模型會存在一定的誤差，不能達到精確的對應(yīng)。為了解決形狀對應(yīng)所存在的一系列問題，Sun等[6]提出了新的等距屬性，即熱核特征描述符(Heatkernel signatures，HKS)，它能夠賦予模型頂點一個特定的函數(shù)值，以覆蓋模型的整體，通過匹配對應(yīng)源模型與目標(biāo)模型之間不同部位的函數(shù)值以達到對應(yīng)匹配關(guān)系。但熱核特征對于模型的尺度變化比較敏感，具有不穩(wěn)定性。Aubry等[7]根據(jù)熱核特征也提出了一個相似的波核特征(Wave kernel signatures，WKS)，波核特征反映了三維網(wǎng)格模型上不同頂點作為量子能量的分布情況，每個頂點的波核特征對應(yīng)著這個量子的剩余能量以及量子對應(yīng)的能量等級，是對熱核特征的一種局部的補償。文獻[8]首次提出了函數(shù)映射(Functional maps，F(xiàn)M)理論，通過分別將源模型與目標(biāo)模型映射到譜空間去尋找真實的對應(yīng)關(guān)系，雖然能夠得到比較精準(zhǔn)的對應(yīng)關(guān)系，但卻解決不了模型自身的對稱性問題。文獻[9]提出了一種網(wǎng)格壓縮流形模式，可以壓縮模型的整體特征以獲得局部的支持，并且具有很好的噪聲干擾及對不同的拓?fù)浣Y(jié)構(gòu)很好的魯棒性，但是不能滿足精確的插值約束。隨后Houston等[10]提出了一種快速計算與自然排序的算法，通過對模態(tài)的改進，加快了模型的壓縮速度。文獻[11]通過改進函數(shù)映射理論，來重新計算三維網(wǎng)格模型的對應(yīng)關(guān)系，減少了點到點對應(yīng)關(guān)系的等距誤差。文獻[12]介紹了一種新的基于神經(jīng)網(wǎng)絡(luò)方法的密集形狀對應(yīng)，通過將對應(yīng)關(guān)系的計算直接作為學(xué)習(xí)過程的一部分，以達到端到端的培訓(xùn)并返回匹配結(jié)果。

為了有效解決同一種經(jīng)過非剛體變換模型之間的對應(yīng)問題，本文通過對參考文獻[6,9-10]的研究，將壓縮流形模式應(yīng)用到非剛體模型變換之間，并且取得了非常好的對應(yīng)局部壓縮部位，從而能夠根據(jù)壓縮特征函數(shù)設(shè)置不同的閾值，得到不同的壓縮部位，取得確定的壓縮局部頂點數(shù)量與位置，從而進行下一步的局部對應(yīng)匹配。在局部對應(yīng)匹配中，本文將離散化的壓縮流形基替換傳統(tǒng)的離散化拉普拉斯算子以改進熱核特征，改進之后的熱核特征與原來的相比在局部對應(yīng)上有更加明顯的效果。本文貢獻如下：(1) 將壓縮流形模式應(yīng)用到新的領(lǐng)域以解決非剛體模型之間的形狀對應(yīng)問題；(2) 解決了非剛體三維網(wǎng)格模型之間的局部特征提取問題；(3) 對熱核特征進行了改進，改進之后的效果明顯優(yōu)于之前。

1 拉普拉斯算子

拉普拉斯算子被定義為梯度(▽f)的散度(▽·f)，是一個二階微分算子。在n維歐幾里得空間中，拉普拉斯算子也可以推廣為定義在黎曼流形上的橢圓型算子，稱為Laplace-Beltrami算子。

Laplace-Beltrami算子[13]是拉普拉斯算子從平面空間到黎曼流形的一般化，在計算機圖形學(xué)中有著廣泛的用途，由于其具有良好的等距不變性，并對三維模型的網(wǎng)格面收斂，因此可以應(yīng)用到任意的三維模型上[14-15]。

三維網(wǎng)格模型是可以離散化的，根據(jù)已有的理論及定義在三維網(wǎng)格模型上的函數(shù)，可以得到一個線性的拉普拉斯-貝爾特拉米算子，根據(jù)算子可以構(gòu)建一個算子矩陣。本文在余切權(quán)重法的基礎(chǔ)之上，又多增加了一個三維網(wǎng)格模型的頂點面積，來構(gòu)造標(biāo)準(zhǔn)的拉普拉斯-貝爾特拉米算子[16]，即：

L=A-1W

(1)

式中：A是一個對角矩陣,A的對角元素Aii等于與頂點i相鄰的三角形面積之和的三分之一。

如圖1所示，頂點i的面積等于其周圍5個三角形面積之和的三分之一，其中每一個三角形面積的計算方法是根據(jù)向量積法求面積，即向量臨邊構(gòu)成的三角形面積等于向量臨邊構(gòu)成平行四邊形面積的一半。

W是一個對稱的稀疏矩陣，矩陣W的計算方法一般為余切權(quán)重法[13]，i、j分別為三維網(wǎng)格模型的頂點，如圖2所示。

其對應(yīng)的公式如下：

(2)

對得到的Laplace算子矩陣L進行特征分解，即可得到所需要的特征值和特征向量。

2 熱核特征

熱核特征描述符，又稱為HKS描述符，是用于非剛體網(wǎng)格模型形狀分析的特征描述子，屬于譜形狀分析方法。對于三維網(wǎng)格模型形狀上的每個點，HKS定義了它的特征向量用于表示點的局部和全局屬性。HKS[6]是基于熱核屬性提出來的，是基于拉普拉斯-貝爾特拉米算子的形狀描述符。通過計算模型上各點的熱量分布最大值，來得到模型表面的幾何特征[17]。

HKS是基于表面熱擴散的概念產(chǎn)生的，給定一個表面初始熱量分布為U0(X)。式(3)表示t時間內(nèi)熱量從x點轉(zhuǎn)移到y(tǒng)點所需要的熱量。

(3)

式中：Δ是一個拉普拉斯算子所構(gòu)成的矩陣；u(x,t)是點x在時間t的熱分布。

熱核對等距變化是不變的，而且對小的擾動穩(wěn)定。另外，熱核能完全等距表征一個形狀，并且隨著時間t的增加，就越能表示形狀的全局屬性。因為ht(x,y)為一個時間域內(nèi)的一對點(x,y)的定義，需要計算兩兩之間的數(shù)據(jù)，因此使用熱核直接作為特征將導(dǎo)致較高的復(fù)雜度。而HKS只考慮ht(x,y)，將其自身限制在時間域內(nèi)，在特定的條件下保留了熱核大部分屬性。對于黎曼流形M上的熱擴散方法如下：

(4)

式(4)的解可以表示為：

(5)

對熱核進行特征分解得到：

(6)

式中：λi和Φi是Δ的第i個特征值和特征向量。對于一個簡單的特征描述子，HKS將熱核限制到時間域內(nèi)，即：

(7)

熱核特征是會隨著時間的流逝而有所改變，時間的不同，熱核值也就不同。通常經(jīng)過一段時間之后，就可以得到三維網(wǎng)格模型的擴散信息以獲得模型的幾何信息[18]。然而，由于熱核特征方程是隨著時間變化的函數(shù)，時間不同，每個模型頂點的熱核特征值也不同。為了給每個模型一個準(zhǔn)確不變并且區(qū)分變化最大的頂點，需要找到一個有利的確定的時間，來有效區(qū)分模型的每個頂點，根據(jù)已有的理論及證明，將時間設(shè)定為0.01，這樣根據(jù)式(7)的熱核方程就可以給每個模型頂點一個確定的值。

由于熱核是模型的內(nèi)在屬性，對模型的等距等容變換具有尺度不變性，并且對畸變噪聲有良好的穩(wěn)定性。此外熱核特征也使得模型的頂點具有時域的多尺度特性，這些特性使得熱核特征可以成為非剛體模型對應(yīng)的有利依據(jù)。

3 壓縮流形模式

Ozolins等[17]提出了一種求一般微分算子壓縮特征函數(shù)的方法。為此，他們添加了一個稀疏誘導(dǎo)l1范數(shù)的變分公式，即給定一個參數(shù)μ∈R+控制稀疏，就會有：

〈φk,φj〉=δkj

(8)

式中：δkj是克羅內(nèi)克函數(shù)，這里用來加強特征函數(shù)的正交性。這些壓縮的特征函數(shù)被證明具有緊湊的支持：它們只在有限的區(qū)域是非零的。緊湊的大小可以由μ控制，一個較大的值會導(dǎo)致小地區(qū)的支持。為了計算壓縮流形基，將式(8)擴展到適用于三角形網(wǎng)格。這里要特別考慮面積矩陣D。沒有D，特征基不獨立于網(wǎng)格分辨率，三維網(wǎng)格的離散化如下：

s.t.ΦTDΦ=I

(9)

接下來使用乘法器(ADMM)的交替方向優(yōu)化求解，為了能夠有效地利用ADMM，需要對式(9)進行重新表述[9]：

s.t.Φ=S,Φ=E

(10)

注意這兩個獨立的耦合約束是如何迫使變量Φ等于S和E的，如果恰好滿足了這些約束，那么我們就又回到了式(9)。將原來的最小化問題重新表述使我們能夠應(yīng)用ADMM方法，為此引入了對偶變量U∈R2N×k，U=[UE,US]對應(yīng)于兩個輔助變量E和S。給定Φ的初始值，令E=S=Φ，U=0，然后該算法將迭代以下步驟求解：

(11)

(12)

(13)

(14)

4 壓縮局部的形狀對應(yīng)

4.1 壓縮三維網(wǎng)格模型

壓縮流形模式能夠自動識別網(wǎng)格的關(guān)鍵形狀特征。它們會自動將局限的局部區(qū)域分組，比如突出物并將脊線分為單獨的基函數(shù)。由于其獨特的空間局部性，它們對重要的幾何和拓?fù)湓肼?如局部掃描所產(chǎn)生的噪聲)具有很強的魯棒性。因此，CMB(Compressed manifold basis)可以作為魯棒形狀分析和匹配的工具。同時，CMB是正交基，可以重構(gòu)任意形狀上定義的函數(shù)，精度可達任意程度。因此，利用壓縮流形基壓縮三維網(wǎng)格的非剛體變換之間的特征表示，使得非剛體模型之間的壓縮部位相同，找到相同部位的相等頂點，可應(yīng)用于三維網(wǎng)格的局部對應(yīng)匹配。效果如圖3-圖5所示。

圖3 半人馬的局部壓縮對應(yīng)1

圖5 狼的不同位置的局部壓縮對應(yīng)

通過兩種不同動物的不同部位，可以看出，壓縮的部位是由φ和μ共同控制的，參數(shù)的不同，模型的壓縮部位就會不同。其中沒有顏色的部分特征函數(shù)無限接近于0，因此可以隨意按照自己的需求去壓縮任意局部(可以是一個手指的局部，例如圖4；也可以是手、手臂等)，之后對熱核特征的改進也是任意局部。

同時也可以通過設(shè)置不同的壓縮特征函數(shù)的大小，來截取相同部位的不同大小，一般設(shè)置特征函數(shù)的絕對值大于0.001以上。壓縮的大小范圍也是可以通過參數(shù)控制的，一般參數(shù)μ的值越大，壓縮的局部支持就會越小，當(dāng)μ等于0時，所有的特征函數(shù)為0。本文通過設(shè)置閾值的大小，得到具體的局部壓縮頂點的位置及個數(shù)以后，就可以進行接下來的局部對應(yīng)匹配。

4.2 改進HKS

熱核特征是三維網(wǎng)格模型的內(nèi)在屬性，對模型的等距等容變化具有尺度不變性。而HKS特征是由熱量在模型表面逐漸傳遞得到的，是構(gòu)成三維網(wǎng)格模型點信息的集合表現(xiàn)。HKS作為三維網(wǎng)格模型的特征選擇，其計算方式一般是通過相應(yīng)的離散化拉普拉斯-貝爾特拉米算子得到的，即首先計算三維網(wǎng)格模型的頂點面積和余切權(quán)重，通過頂點面積和余切權(quán)重構(gòu)建拉普拉斯算子，然后對拉普拉斯算子進行特征值和特征向量的分解，通過分解所得到的特征值與特征向量，一般選取前30～300之間的特征值及所對應(yīng)的特征向量，通過代入熱核特征的公式來計算相應(yīng)的熱核值。本文通過對熱核特征的學(xué)習(xí)與研究，利用離散化的壓縮流形模式去替換傳統(tǒng)離散化拉普拉斯算子以改進HKS,改進之后的熱核特征，在三維網(wǎng)格模型的形狀對應(yīng)匹配上有更加準(zhǔn)確的效果。局部壓縮對比圖如圖6-圖7所示。

(a) 原始 (b) 改進圖7 狼嘴巴的局部HKS

圖6、圖7的對比圖中，大部分的暗黑色為HKS設(shè)置為0的可視化，狼局部的高亮白色為正常的HKS計算及改進的計算對比顯示。可以看出，改進之后的HKS在局部的分層更加細(xì)膩，在更小的區(qū)域區(qū)分更加明顯(如圖7中：改進之前的HKS只有高亮白色到淡白色的潛在變化，而改進之后明顯出現(xiàn)了暗色系的淡黑色，層次上也是從高亮白色到淡黑色的漸變，細(xì)節(jié)分層明顯更加細(xì)膩)。因此通過對比圖的可視化，可以看出本文算法改進的可行性及魯棒性。

4.3 局部對應(yīng)匹配

由于局部壓縮以后，頂點數(shù)量比較少，因此本文就選用了熱核特征來尋找對應(yīng)的真實匹配。然而，由于熱核特征方程是隨著時間變化的函數(shù)，時間不同，每個模型頂點的熱核特征值也不同。為了有效區(qū)分模型的每個頂點，需要找到一個有利的確定的時間。根據(jù)文獻[6]已有的理論及證明，我們把時間t設(shè)定為0.01，這樣根據(jù)熱核方程式(7)，就可以給每個模型頂點一個確定的值，這同樣為模型的對應(yīng)匹配提供了有利的依據(jù)。具體步驟如下：

步驟1假設(shè)源模型為A，目標(biāo)模型為B，它們具有相同的頂點數(shù)N，以及面片數(shù)M。首先讀取模型各自的頂點信息與面片信息，根據(jù)頂點信息與面片信息，利用向量積(叉積)法計算三維模型每一個頂點相鄰的三角面片的面積之和的三分之一，即為每一個頂點所賦予的面積值，利用每一個頂點所賦予的面積值，構(gòu)建對角矩陣A，其中要對每一個模型的頂點面積進行標(biāo)準(zhǔn)化處理。然后根據(jù)式(2)計算各自的稀疏矩陣W，最后通過式(1)構(gòu)建拉普拉斯算子矩陣LA、LB，矩陣大小為N×N。

步驟2對各自的拉普拉斯矩陣LA、LB分別進行特征值與特征向量的分解，分解之后的特征值一般從大到小排序，其中每一個特征值都對應(yīng)一列的特征向量。本文選取前30個大于0的特征值以及所對應(yīng)的特征向量，用來計算三維網(wǎng)格模型的熱核特征值。

步驟3通過壓縮流形基壓縮不同的模型得到不同的壓縮部位，設(shè)置特征函數(shù)的閾值，截取相應(yīng)部分的頂點數(shù)量及位置。讀取相應(yīng)頂點的熱核特征來做具體的形狀對應(yīng)，對應(yīng)方法由大到小排序即可。

步驟4以壓縮流形基所優(yōu)化求解的特征值及其特征向量替換離散化的拉普拉斯算子以改進熱核特征，同樣讀取相應(yīng)頂點的熱核特征值以相同的方法進行局部的對應(yīng)匹配。

步驟5最后通過改進前后各自的匹配結(jié)果來評估效果的好壞。

本文中圖形的展示分別采用了稠密對應(yīng)以及稀疏對應(yīng)匹配，效果圖如圖8-圖12所示。

圖8 半人馬原始局部對應(yīng) 圖9 半人馬改進局部對應(yīng)

圖10 貓的原始局部對應(yīng) 圖11 貓的改進局部對應(yīng)

(a) 原始 (b) 改進圖12 狼的局部對應(yīng)

為了更加直觀地表現(xiàn)對比效果，圖中只有貓是稠密對應(yīng)，其他都為稀疏對應(yīng)。

4.4 實驗結(jié)果與分析

由于TOSCA模型庫中的模型給出了準(zhǔn)確的一一對應(yīng)關(guān)系，以及TOSCA模型庫中包含了動物和人類七種不同的模型，并且每一種模型都有不同的經(jīng)過非剛體變換之后所形成的不同姿態(tài)，因此本文隨機選取TOSCA模型庫中的模型對本文算法進行驗證，并與改進之后的算法進行對比實驗。

給定一種衡量模型對應(yīng)關(guān)系的準(zhǔn)確性評價標(biāo)準(zhǔn)。即給定源模型A和目標(biāo)模型B，由某一方法計算得到的對應(yīng)關(guān)系為f：A→B，而非剛體模型之間的準(zhǔn)確對應(yīng)關(guān)系為fture：A→B。對于源模型A上的任一點P，f(P)表示計算出的P點在目標(biāo)模型B上的對應(yīng)點，fture(p)表示P點在目標(biāo)模型B上的真實對應(yīng)點。那么可以用測地距離dN(f(p),fture(p))來表示P點對應(yīng)關(guān)系的準(zhǔn)確性，即在誤差允許的情況下，源模型與目標(biāo)模型之間的對應(yīng)匹配，其中Area(B)表示目標(biāo)模型的面積，公式如下：

(15)

由于本文壓縮頂點數(shù)量相較于整體而言比較少，因此，本文對比數(shù)據(jù)均采用真實的對比匹配，即在沒有測地誤差的情況下所表示的匹配率，實驗結(jié)果如表1所示。

可以看出，無論是不同模型之間壓縮相同的部位(例如貓的尾巴和狼的尾巴)，還是同一種模型壓縮不同的部位(例如狼的下巴及狼的尾巴)，改進之后的真實對應(yīng)匹配都要優(yōu)于之前。由此可以看出本文算法具有很好的魯棒性。同時，在非剛體模型之間壓縮模型的局部，本文算法能夠精準(zhǔn)地找到相同的壓縮頂點，從而能夠準(zhǔn)確地進行局部的對應(yīng)匹配。

5 結(jié) 語

本文提出的利用壓縮流形模式應(yīng)用于非剛體三維網(wǎng)格模型變換之間，解決了非剛體三維網(wǎng)格模型之間的形狀對應(yīng)問題。同時在現(xiàn)實運用中，對于非剛體模型的形狀對應(yīng)也并不一定需要整體的全部對應(yīng)，有的可能僅僅是需要對應(yīng)于某一局部，本文算法正好解決了這一問題，并且提高了算法的效率以及局部的精準(zhǔn)匹配。同時在匹配過程中改進了熱核特征，使其局部對應(yīng)效果更加突出。與已有算法相比，本文算法具有以下幾個優(yōu)點：(1) 本文算法在非剛體模型之間可以精確地確定某一部位的精準(zhǔn)頂點數(shù)量與位置，縮短了局部對應(yīng)的時間與效率，同時為局部對應(yīng)提供了一個新的解決思路；(2) 本文算法改進了熱核特征，為以后的整體對應(yīng)匹配埋下了伏筆。