王旭鵬，雷 航，劉 燕，桑 楠

(電子科技大學(xué) 信息與軟件工程學(xué)院，成都 261400)(*通信作者電子郵箱201211220104@std.uestc.edu.cn)

0 引言

近年來，隨著三維成像技術(shù)的快速發(fā)展，出現(xiàn)了大量的3D圖形數(shù)據(jù)。三維傳感器采集的數(shù)據(jù)是物體的三維幾何形狀信息，能夠使智能設(shè)備更好地感知和理解現(xiàn)實場景，在人機交互、虛擬現(xiàn)實、增強現(xiàn)實以及機器人等領(lǐng)域有廣泛的應(yīng)用。

計算三維幾何模型配準，就是擬合模型之間的映射關(guān)系，尤其是滿足結(jié)構(gòu)約束的兩個模型之間的匹配，是計算機視覺和計算機圖形學(xué)的基本任務(wù)，在三維重建、三維目標(biāo)識別和三維模型檢索等任務(wù)中得到了廣泛的應(yīng)用[1]。一個常見的映射關(guān)系是等距映射，在該映射下，兩點之間的測地線距離保持不變?，F(xiàn)實世界中存在著大量的非剛性變換(即近似的等距變換)，例如人體關(guān)節(jié)的運動等，因此，計算三維非剛性模型的配準具有非常重要的實際意義[2]。

三維幾何模型的剛性變換可以使用一個矩陣來表示，而模型的非剛性變換只能通過點的匹配來描述，因此，三維非剛性模型配準本質(zhì)上為組合優(yōu)化問題，復(fù)雜度較高[3]。同時，在現(xiàn)實場景中，三維幾何模型數(shù)據(jù)可能會受到各種干擾，例如等距變換、孔洞、小孔洞、尺度變換、局部尺度變換、重采樣、噪聲、散粒噪聲以及拓撲變換等，這就要求配準算法具有很強的魯棒性。

現(xiàn)有的方法主要利用特征點的匹配來解決三維非剛性模型的配準，并將其抽象描述為最小失真問題。文獻[4]基于模型在度量空間的表示，提出了推廣的多維尺度變換算法(Generalized Multi-Dimensional Scaling, GMDS)。首先將模型投影到基于測地線距離的度量空間中，然后通過計算模型之間失真最小的映射來完成模型的配準。文獻[5]基于模型的等角變換，提出了莫比斯投票算法。首先對三維網(wǎng)格模型上點的三元組做莫比斯變換，并計算每個點的形變能量函數(shù)，通過計算并統(tǒng)計每個匹配點對的投票數(shù)來完成模型的配準。文獻[6]首先利用熱核映射特征計算穩(wěn)定的匹配點對，然后使用熱核映射最優(yōu)化的方法迭代地增加匹配點的數(shù)目。文獻[7]首先計算模型的特征點，然后生成一系列的匹配點對，最后通過采用隨機采樣一致性方法(RANdom SAmple Consensus, RANSAC)計算點的匹配。文獻[8]引入了概率的方法，迭代地尋找匹配點對。為了解決最小失真問題，文獻[9-12]引入了貪婪算法。文獻[9]將模型投影到基于測地線距離的度量空間，選取極大值為特征點，然后使用貪婪算法計算匹配點對。文獻[10]首先使用高斯函數(shù)的差分和高斯函數(shù)直方圖來提取并描述模型的特征點，然后根據(jù)特征點之間的歐氏距離計算匹配點對。文獻[11]將點的匹配抽象描述為圖問題，首先利用雙向圖計算初始的匹配點對，然后使用貪婪算法增加并更新匹配點對。文獻[12]首先基于貪婪算法計算少量點的匹配，然后通過概率的方法將其推廣到整個模型。由于三維非剛性模型的配準本質(zhì)上為組合優(yōu)化問題，以上算法具有計算的復(fù)雜度高、精度較低、容易受噪聲干擾等缺點。

為了解決以上問題，本文提出了一個新的基于分層策略的三維非剛性模型配準算法。算法的主要思想是：對于兩個非剛性變換的模型，特征區(qū)域能夠穩(wěn)定地提取、描述并匹配，從而有效地縮小特征點匹配的搜索空間。據(jù)此，本文首先提出了一個三維幾何模型的樹形表示方法，其中，根節(jié)點為三維幾何模型，內(nèi)部節(jié)點為特征區(qū)域，葉節(jié)點為包含在相應(yīng)區(qū)域的特征點；然后，利用三維幾何模型的樹形表示，提出了一個新的基于分層策略的模型配準算法；最后在SHREC 2010模型配準數(shù)據(jù)集[13]上進行實驗，并對結(jié)果進行了詳細的分析和討論。

1 三維幾何模型的樹形表示

算法的主要思想是定義了三維幾何模型S的樹形結(jié)構(gòu)Tree(S),該結(jié)構(gòu)描述了模型的遞歸分解過程。

1.1 擴散幾何

將三維幾何模型S抽象定義為緊致的黎曼流形M,熱傳導(dǎo)方程描述了熱量在M上隨時間的變化過程，其定義為：

(1)

其中：u(x,t)表示t時刻M上的熱量分布函數(shù)，ΔM表示M的拉普拉斯貝爾特拉米算子，ΔM是拉普拉斯算子在黎曼流形上的推廣。

(2)

其中：λl和Φl分別表示ΔM的第l個特征值和特征函數(shù)。

熱核函數(shù)具有許多相關(guān)的特性，適用于三維非剛性模型的分析[15]。首先，熱核函數(shù)對模型的等距變換具有魯棒性，可以應(yīng)用于模型在不同姿態(tài)下的配準；其次，熱核函數(shù)對模型的局部擾動保持穩(wěn)定，因此，對模型一定程度的噪聲保持魯棒；最后，熱核函數(shù)能夠多尺度地描述一個特征點。當(dāng)t的取值較小時，K(x,y,t)描述了以點x為中心、尺度較小的局部曲面的幾何特征；局部曲面的尺度隨著t的增大而增加，K(x,y,t)描述點x的鄰域更加全局的幾何信息。

將熱核函數(shù)僅定義在時域t,得到K(x,x,t),稱為熱核簽名函數(shù)ADF(x,t)[15-16]，它描述了初始單位熱源位于點x,在經(jīng)歷時間t之后點x保留的熱量。熱核簽名函數(shù)繼承了熱核函數(shù)適用于三維非剛性模型分析的特性，被廣泛應(yīng)用于三維模型的局部特征描述、點的匹配[15]以及模型的全局描述[1]。

1.2 特征區(qū)域和特征點提取

對于黎曼流形M,首先使用熱核簽名函數(shù)ADF(x,t)計算其標(biāo)量域f:M→R,然后使用同源聚類算法(persistence-based clustering)[17]提取三維幾何模型S的特征區(qū)域R和特征點P。

1.2.1 同源聚類

定義函數(shù)f的水平集為Xα=f[α,∞),α∈(-∞,+∞)。 在α由+∞減小到-∞的過程中，會產(chǎn)生新的連通域C(xi)。C(xi)對應(yīng)著函數(shù)f的一個局部極大值xi,在連通域C(xi)出現(xiàn)時生成。對于某個α值(α=αi)，當(dāng)在兩個極大值點之間存在一條M上的路徑，路徑上所有的點滿足f(x)≥αi,則會發(fā)生連通域的合并。當(dāng)兩個分別對應(yīng)局部極大值為x1和x2(x1

同源持久圖將M在同源聚類過程中生成的連通域映射到二維平面中，橫坐標(biāo)為其消亡值αi,縱坐標(biāo)為其生成值xi。連通域的持久值Γ定義為Γ=xi-αi,是其映射在同源持久圖中的點(αi,xi)到直線x=y的豎直距離。每個連通域都與函數(shù)f的一個局部極大值相關(guān)，持久值Γ越大，其在同源一致圖中的映射點距離直線x=y越遠，區(qū)域的特征性越強；如果距離直線x=y較近，區(qū)域的顯著性較弱，則可視為拓撲噪聲，因此，可以使用平行于x=y的直線將特征區(qū)域和拓撲噪聲分離，它到直線x=y的距離稱為合并參數(shù)γ。

1.2.2 特征區(qū)域和特征點的提取

1.3 三維幾何模型的樹形表示

對于三維幾何模型S,計算其特征區(qū)域R和特征點P,然后定義其樹形結(jié)構(gòu)Tree(S)。

圖1 三維幾何模型的樹形表示

2 三維模型的分層配準算法

2.1 內(nèi)部節(jié)點的匹配

(3)

定義內(nèi)部節(jié)點匹配的優(yōu)化表達式為二次函數(shù)，如下：

(4)

其中：α、β和γ分別表示權(quán)重；dR(·,·)計算與特征區(qū)域?qū)?yīng)的局部極大值點之間的測地線距離；area(·)計算特征區(qū)域的面積；fR(·)表示內(nèi)部節(jié)點的特征描述，其定義如式(5)。

(5)

其中：pi為特征區(qū)域上C(xi)的點，HKS(·)計算點pi的熱核簽名值。

定義內(nèi)部節(jié)點匹配的目標(biāo)函數(shù)，如下：

x*=arg minF(I)

(6)

圖2 三維幾何模型的分層配準算法

2.2 葉節(jié)點的匹配

(7)

其中:α和β表示權(quán)重；dp(·,·)計算兩個特征點之間的測地線距離；fp(·)表示葉節(jié)點的特征描述，其定義如式(8)。

fp(pi)=WKS(pi)

(8)

其中，WKS(·)計算特征點pi的波動核簽名值[19]。

定義葉節(jié)點匹配的目標(biāo)函數(shù)，如下：

x*=arg minL(I)

(9)

2.3 三維模型的分層配準

對于兩個三維幾何模型S1和S2,分別計算其樹形結(jié)構(gòu)Tree(S1)和Tree(S2)。分層配準算法的主要思想是：對三維幾何模型的樹形結(jié)構(gòu)采用廣度優(yōu)先的匹配策略，從而降低了計算的復(fù)雜度，提高了匹配的效率。

葉節(jié)點的匹配在相應(yīng)的特征區(qū)域空間中搜索，減小了搜索空間。對于特征區(qū)域匹配對(ti,sj),根據(jù)目標(biāo)函數(shù)(9)計算其內(nèi)部特征點的匹配。

3 實驗結(jié)果和分析

3.1 數(shù)據(jù)集

將本文提出的三維非剛性模型分層配準(Hierarchical Shape Registration, HSR)算法在SHREC 2010配準數(shù)據(jù)集上做測試。數(shù)據(jù)集包含三類模型，每一類模型由一個空模型(null shape)及其經(jīng)過一系列變換得到的形變模型(transformed shape)組成。模型的變換包括：等距變換、孔洞、小孔洞、尺度變換、局部尺度變換、噪聲、重采樣、拓撲變化和散粒噪聲。每一種變換有五種等級，為每類空模型生成了45個形變模型。

采用文獻[13]中的方法對算法在數(shù)據(jù)集上的性能作定量分析。定義模型配準為形變模型T與空模型N之間點的匹配，如下：

(10)

其中：K為點的匹配數(shù)目，yi、xi分別代表形變模型和空模型上的特征點。模型配準的真實值包含在數(shù)據(jù)集中，因為空模型是對稱的，所以配準的真實值由兩部分組成：形變模型與空模型之間的匹配C1,形變模型與經(jīng)過對稱變換后的空模型之間的匹配C2。其定義如下：

(11)

(12)

定義模型配準優(yōu)劣的度量函數(shù)，如下：

(13)

采用文獻[13]中的方法，對SHREC2010數(shù)據(jù)集中的形變模型進行重采樣，每個模型具有10 000個頂點，模型配準將點映射到空模型上，算法性能的度量在空模型上進行計算。采用文獻[20]中的方法，計算拉普拉斯貝爾特拉米算子，使用300個特征值和相應(yīng)的特征函數(shù)來計算熱核簽名函數(shù)，設(shè)置時間參數(shù)t為0.1。采用集合搜索算法[21]計算同源聚類，合并參數(shù)γ設(shè)為0.05，用以提取三維幾何模型的特征區(qū)域和特征點。設(shè)置節(jié)點匹配的目標(biāo)函數(shù)(4)、(7)參數(shù)值分別為α=5×10-4,β=5×10-2,γ=1,并使用分支定界法尋找其最優(yōu)解。

3.2 定性分析

圖3展示了基于分層策略的三維非剛性模型配準算法在SHREC 2010數(shù)據(jù)集上的配準結(jié)果。

如圖3 (a)所示，本文提出的分層配準算法能夠準確地提取并匹配模型的特征點。這是因為熱核簽名函數(shù)對模型的非剛性變換具有魯棒性，同源聚類算法提取出的點和區(qū)域具有較大的持久值，含有豐富的幾何特征；同時，分層配準算法借助模型的樹形表示減小了特征點匹配的搜索空間，提高了配準的準確性。

如圖3(b)、(e)所示，算法對模型的噪聲和小的孔洞保持穩(wěn)定，這是因為熱核簽名函數(shù)對施加于模型一定程度的噪聲保持魯棒。

圖3 SHREC 2010數(shù)據(jù)集上三維幾何模型的配準

如圖3(f)所示，對三維幾何模型進行重采樣，分層配準算法能夠準確地完成非剛性模型的配準。這是因為重采樣不會影響熱核函數(shù)和同源聚類的計算，算法能夠穩(wěn)定地提取模型的特征點和特征區(qū)域，對模型進行樹形表示。

如圖3(g)、(h)所示，模型的尺度變換和局部尺度變換不會影響分層配準算法的性能，這是因為熱核函數(shù)具有尺度不變的特性。

如圖3(i)所示，在模型的拓撲變換下，三維非剛性模型分層配準算法的性能未受影響，這是因為模型拓撲的變換并未影響模型特征點和特征區(qū)域的提取。

如圖3(c)、(d)所示，對模型施加散粒噪聲或者孔洞，模型的配準失敗。這是因為散粒噪聲或孔洞的施加改變了模型的幾何特性，導(dǎo)致特征點和特征區(qū)域的提取失敗。

3.3 定量分析

將本文提出的分層配準算法與GMDS方法、博弈論方法進行對比分析，采用式(11)中的測地線距離誤差作為算法性能優(yōu)劣的判別準則，并對結(jié)果進行討論。如文獻[14]所述，博弈論方法能夠提取并匹配平均50個特征點，類似地，本文提出的分層配準方法能夠匹配大約65個特征點。

表1列出了本文提出的分層配準方法和博弈論方法、GMDS算法在不同的模型變換等級下，特征點匹配的平均測地線距離誤差。如表1所示，分層配準算法能夠顯著地減小特征點匹配的誤差，并且隨著等級的增加，三維非剛性模型配準的精度提升越發(fā)明顯。尤其值得指出的是，當(dāng)模型變換的等級大于4時， GMDS算法的誤差將近40，而分層配準算法的誤差低于8，是博弈論方法誤差的一半。

表2分別列出了本文提出的分層配準算法在SHREC 2010數(shù)據(jù)集上的平均測地線距離誤差。如表2所示，本文算法在所有的模型變換下都具有較小的誤差。

表1 三種算法在SHREC 2010數(shù)據(jù)集上的平均測地線距離誤差

表2 分層配準算法在SHREC 2010數(shù)據(jù)集上

在模型的等距變換、尺度變換、局部尺度變換、小孔洞和噪聲等情況下，特征點匹配的誤差在5左右，這是由熱核函數(shù)的特性決定的。熱核函數(shù)對模型的等距變換保持魯棒，具有尺度不變的特性，并對模型的局部擾動保持穩(wěn)定。

在對模型進行重采樣或者增加孔洞，算法的誤差增加，平均誤差在8左右，這是由特征點的缺失所造成的。

對模型施加散粒噪聲，本文提出的分層配準算法的誤差顯著增大，均大于10；同時，變換等級越大，誤差越高，由10增加到12。這是因為散粒噪聲為模型增加了很多大的突起，改變了模型的幾何特征。

在模型的拓撲變換下，算法的特征點匹配誤差均大于6，并且隨著變換等級的增加由6增大到8.45。這是因為分層匹配算法使用測地線距離計算模型配準的目標(biāo)函數(shù)，而模型的拓撲變換會影響測地線距離的計算。

3.4 運行時間分析

在64位Windows操作系統(tǒng)下，使用CPU為Intel Core-i7(3.40 GHz)，內(nèi)存為32 GB的計算機，分別測試GMDS方法、博弈論方法和本文提出的分層配準算法在shrec 2010數(shù)據(jù)集上的平均時間消耗，可知本文算法需要0.1 s來計算兩個三維模型之間的配準，與博弈論方法的35 s和GMDS方法的260 s相比，本文提出的方法大幅度地節(jié)省了模型配準的時間開銷。

4 結(jié)語

本文針對三維非剛性模型的配準問題，首先提出了三維模型樹形表示方法，并據(jù)此提出了一種新的基于分層策略的配準算法。實驗結(jié)果表明，本文所提出的方法計算復(fù)雜度低、精確度高，而且能夠?qū)Χ喾N模型數(shù)據(jù)的擾動保持魯棒，因此具有較高的推廣價值。