基于譜聚類三維模型集一致性分割算法

賈 暉，張建剛

(1.西安郵電大學 計算機學院，陜西 西安 710121；2.西安熱工研究院有限公司 電站信息及監(jiān)控技術(shù)部，陜西 西安 710032)

1 概 述

三維模型分割是根據(jù)模型的幾何特征將模型分解成為一組數(shù)目有限、各自具有簡單形狀意義且各自連通的子部分[1]。單個模型由于分割尺度的不同造成分割結(jié)果的不一致,難以實現(xiàn)模型重用。模型集一致性分割是指同時對一組形狀相關(guān)但姿態(tài)有差異的三維模型集進行分割，得到語義相關(guān)分割結(jié)果的分割方法[2]。一致性分割算法能得到同尺度的分割結(jié)果,算法具有實用性,在快速建模[3-5]及三維數(shù)字模型重建中應用廣泛[6-8]。

文獻[9]提出了基于網(wǎng)格Laplace和K-Means聚類的三維幾何模型分割算法，得到模型的歸一化形式，用K-Means算法進行聚類，克服了由于姿態(tài)變化對模型分割的影響，減少了分割時間，得到了有意義的分割結(jié)果。然而分割邊界不夠整齊，存在K-Means算法的所有問題。文獻[10]提出一種基于蟻群優(yōu)化的網(wǎng)格分割方法，將待分割網(wǎng)格的每個三角面片視為一個螞蟻，通過蟻群優(yōu)化迭代對分割標簽進行更新，直到達到分割條件實現(xiàn)網(wǎng)格分割。由于蟻群算法具有潛在的平行處理特性，能在一定程度上加快分割速度。然而蟻群算法收斂速度較慢，容易陷入局部最優(yōu)解，造成過分割現(xiàn)象。文獻[11]提出基于Laplace 譜嵌入和Mean Shift聚類的網(wǎng)格一致性分割算法。為了減少姿態(tài)變化對三維網(wǎng)格模型的影響，將模型轉(zhuǎn)化成高維譜域中的標準型,并用Mean Shift算法進行聚類,獲取模型的分割部位。該算法對于有明顯分支結(jié)構(gòu)的模型分割效果較好，但Mean Shift聚類中迭代初始點隨機選擇，不利于形成較好的分割結(jié)果。

以上算法都是無監(jiān)督的自動聚類算法，除此之外也有采用半監(jiān)督的方法來實現(xiàn)模型分割。文獻[12]提出了一種基于半監(jiān)督K均值聚類和帶狀區(qū)域增長的三維網(wǎng)格模型層次分割算法，首先提取顯著特征點來代表模型的主要分支，利用半監(jiān)督K均值聚類對模型進行預分割，最后利用離散高斯曲率逼近，采用帶狀推進區(qū)域增長法對模型進行精細化分割。

從以上的分析得出，聚類算法是模型分割的主流方法。監(jiān)督性聚類算法結(jié)果較準確，但卻需要大量的人工參與，并未成為分割方法的主流。而聚類算法中的半監(jiān)督聚類和無監(jiān)督聚類算法應用最為廣泛。算法中所采用的形狀描述子大多都基于模型的表面特征(如曲率、法線方向、平均測地距離[13](AGD)等)描述模型之間的形狀，并對模型進行分割。而模型的表面特征容易因為類似模型的不同姿態(tài)的變化而發(fā)生顯著變化，并且它們的計算容易產(chǎn)生誤差，使其喪失模型間形狀可比性。因而采用表面特征不利于在具有形狀相似而姿態(tài)存在差異的模型集上進行一致性分割。

文中研究模型集上的一致性分割。采用形狀直徑函數(shù)[14](SDF)特征及譜聚類方法對整組模型集進行一致性分割。將三維模型看作帶權(quán)無向圖，面片看作圖的節(jié)點，面片與面片之間的特征相似性關(guān)系看作圖的邊。將面片的分割問題，看作圖的分割問題。首先提取模型集中各個模型面片的SDF特征；其次計算面片特征之間的相似性矩陣，用測地距離進行相似性矩陣稀疏化；最后采用譜聚類對三維模型進行分割。

2 形狀直徑函數(shù)

形狀直徑函數(shù)最早由Shapira在研究模型分割和骨架提取時提出。該特征不是模型的表面特征而是基于模型體特征的形狀特征，具有當模型姿態(tài)發(fā)生變形時，同一部位的特征值基本保持不變的特點，非常適用于具有不同姿態(tài)但形狀相似的模型之間的部位相似性計算。

如圖1所示，SDF特征的計算方法如下:對于三角面片上的每一個頂點，從該頂點以法線反方向為軸做圓錐。在圓錐內(nèi)部，從頂點向三角面片的另一側(cè)發(fā)射射線。計算射線的平均長度rm和長度標準差σ，定義有效射線的范圍range。對于每一條范圍內(nèi)的射線rj∈range,定義權(quán)重ωj=1/αj,αj是rj與圓錐軸的夾角。頂點的SDF值計算公式為：

(1)

每個三角面片的SDF值的計算方法是首先利用式1計算各面片重心點的SDF值，其次利用式2進行歸一化，獲得面的SDF值。其中α為歸一化參數(shù)。

(2)

SDF值在模型的變形中基本保持不變，因為SDF的定義跟模型的體相關(guān)而與表面特征無關(guān)。同樣，不同模型的類似部位同樣也具有相似的SDF值，因為類似部位具有相似的體特征，如牛的腿和狗的腿體特征相似。如圖2所示。SDF特征對平移、旋轉(zhuǎn)、簡化、姿態(tài)變化具有很好的魯棒性，可使用SDF值對同一模型的不同變形以及相似的模型進行一致性分割。

圖1 SDF特征值計算

圖2 SDF特征分布

3 基于SDF特征的譜聚類分割算法

文中提出一種基于譜聚類的三維模型集一致性分割算法。譜聚類算法建立在譜圖理論之上,定義圖G=,其中V表示事物，E表示連接事物之間的邊。邊上帶有權(quán)重，表示對應兩個事物間具有的某種關(guān)系。將圖G劃分成若干個子圖，使得子圖之間節(jié)點的交集為空集。在劃分過程中，約束條件為被“截斷”的線的權(quán)重和最小，即“損失函數(shù)”最小。譜聚類方法常常應用于圖像分割中，通過最小化損失函數(shù)來實現(xiàn)。

在圖G=中，圖G中的n個節(jié)點用V={v1,v2,…,vn}表示，G中的m條邊用E={e1,e2,…,em}表示，wij為vi到vj邊的權(quán)重值。若G被分成了G1和G2兩個子圖，定義q=[q1,q2,…,qn]是一個n維向量，用于表示劃分方案。則

損失函數(shù)為：

其中，W為鄰接矩陣，即節(jié)點之間的相似性關(guān)系；D為對角矩陣。

文中將譜聚類應用于三維模型集的一致性分割。將待聚類模型視為帶權(quán)無向圖。圖的頂點為待聚類的面片，圖的邊權(quán)為面片之間的相似性關(guān)系，邊權(quán)矩陣被稱為相似性矩陣。利用譜圖理論分析該無向圖，找出分類結(jié)構(gòu)。

在多種聚類方法中譜聚類是最好的無監(jiān)督聚類算法之一。譜聚類方法有兩個優(yōu)勢：譜聚類具有能在任意形狀的樣本空間上聚類且收斂于全局最優(yōu)解的優(yōu)點，不像K-means聚類要求樣本空間是凸集；只要相似性矩陣是稀疏的，即使對于高維數(shù)據(jù)，譜聚類算法的執(zhí)行效率也非常高。算法步驟如圖3所示。

圖3 算法步驟

3.1 相似性矩陣

模型面片之間的相似度計算結(jié)果將顯著影響譜聚類算法的準確性和有效性。面片距離越近，屬于一類的概率越高，距離越遠，屬于一類的概率越低。模型體特征越接近，屬于一類的概率越高，體特征差異越大，屬于一類的概率越低。參考圖像分割中計算像素的相似度方法[15]，采用式3計算面片之間的相似度：

(3)

其中，wij為面片i和面片j的相似度；σI為SDF特征的尺度參數(shù)。

得到的相似性矩陣為：

(4)

3.2 稀疏化

相似度計算可得三維模型中任意兩個三角面片的相似度。若模型中所有面片的個數(shù)為n，則W為n×n維矩陣。任意兩個面片之間都能計算相似性，此時圖為n個節(jié)點的完全圖。對完全圖進行簡化才能提高其可分性。

SDF特征描述模型體特征。然而，有些不同部位卻有著相似的體特征。如圖4(a)的小狗模型，尾巴和腿SDF特征類似。在實驗中，如果直接用式4進行聚類，則會產(chǎn)生大量的錯分，使得尾巴和腿被分為一類。根據(jù)常識，距離越近屬于一個劃分的概率越高。因此，可根據(jù)距離信息，將相似性矩陣進行優(yōu)化。

圖4 錯分和測地距離

為了提高分割的準確度，將完全圖中距離過大的面片間的相似性關(guān)系去掉，只考慮在一定測地距離范圍內(nèi)的形狀相似性，使得相似性矩陣稀疏化。這樣既能提高譜聚類的準確性，又能提高計算效率。

測地距離最早用于大地測量，又叫做大地線或者短程線。在三維網(wǎng)格模型上，研究網(wǎng)格頂點或者面片之間的最短距離，稱為離散測地距離。測地距離的計算分為精確計算和近似計算兩種。應用于三維模型分割中的測地距離計算，大多是近似計算。因為精確計算耗費大量時間，而近似計算耗費時間較小，當網(wǎng)格數(shù)量很多時，時間復雜度較低，而計算精度也能滿足分割要求，體現(xiàn)出較大的優(yōu)越性。

有許多經(jīng)典的求解三維網(wǎng)格上近似測地距離的算法，如Kanai[16]提出的基于帶權(quán)無向圖的三角網(wǎng)格測地距離估算算法等。在Kanai的算法中，三角網(wǎng)格模型被表示為帶權(quán)無向圖，邊權(quán)用鄰接頂點之間的歐氏距離表示。首先利用Dijkstra算法計算帶權(quán)圖上兩點間的最短路徑，其次以最短路徑上的節(jié)點為基礎，尋找路徑上節(jié)點的一鄰域構(gòu)建新的帶權(quán)無向圖，在新圖中重復使用Dijkstra算法求解最短路徑。算法迭代執(zhí)行，直到滿足終止條件。該算法對測地距離的計算較快，但是在網(wǎng)格節(jié)點很多的情況下，反復迭代使用Dijkstra算法的時間也很長。

為了能夠快速求得三維網(wǎng)格模型中任意兩點之間的測地距離，文中對Kanai提出的算法進行簡化?；卩徲騼?nèi)歐氏距離是測地距離的近似值的思想，在一個帶權(quán)無向圖中，通過鄰域內(nèi)的最短距離來估算測地距離。這種估計能夠達到三維模型分割所要求的計算精度，同時也縮短了計算時間。

圖4(b)中a,b,c為曲面上的三個點，這三個點在不同的三角網(wǎng)格上。gab和gbc分別表示節(jié)點a與b之間的測地距離。dab，dbc和dac分別表示節(jié)點a，b和c兩兩之間的歐氏距離。從圖中可以得出頂點之間的測地距離可由歐氏距離近似計算得到，gab≈dab，gbc≈dbc，gac≈dab+dbc。設三維模型上所有頂點的集合為V，非鄰接點的測地距離由以下步驟計算：

STEP1：對三角網(wǎng)格中的每個頂點vi尋找鄰接頂點集合Z(vi)，且

Z(vi)=vj|vj∈Vandvjis neighbor ofvi

STEP2：在三角網(wǎng)格上計算任意兩個鄰接頂點間的歐氏距離d(vi,vj)，vj∈Z(vi)。

STEP3：求不鄰接頂點的最短路徑，定義鄰接矩陣G：

將計算不相鄰兩點間的測地距離問題變?yōu)樵跓o向帶權(quán)圖上求任意兩點間的最短距離問題。利用Dijkstra算法求任意兩點vi與vj的最短距離，即為vi與vj的近似測地距離D(vi,vj)。

定義相似性計算距離ri，面片i到其他所有面片的測地距離，取其平均值確定相似矩陣的計算距離。ri=mean(D(fi,fj))，其中j=1,2,…,n。D(fi,fj)為i面與j面的測地距離，以面片頂點間的測地距離的平均值來確定。采用以下方法確定最終的相似性矩陣。

(5)

3.3 三維模型集譜聚類分割算法

輸入：三維數(shù)據(jù)集，相似性矩陣W，聚類數(shù)C；

輸出：C組聚類。

(1)根據(jù)相似性矩陣W計算對角矩陣D,Dii=wi1+wi2+…+win。計算拉普拉斯矩陣L=D-W。

(2)尋找Lu=λDu的特征值λ2,λ3,…,λc+1以及相應的特征向量e2,e3,…,ec+1，則fi為[e2,e3,…,ec+1]中的第i行。

(3)使用K-means算法基于f1,f2,,fC進行聚類分割，將W分割為C組。

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

在Windows上，采用一致性分割數(shù)據(jù)集(COSEG)進行實驗，算法運行環(huán)境為Intel Core i3 3.3 GHz CPU,4 GB內(nèi)存。開發(fā)平臺為Microsoft Visual Studio 2010，圖形庫為OpenGL。COSEG數(shù)據(jù)集是具有多個大類的三維模型集，每個模型集中又有若干個類似的三維模型。

以統(tǒng)計數(shù)據(jù)來評價分割效果。文獻[17]定義了面片劃分的準確程度的算法，用劃分正確面積與模型總面積的比值來計算。式6中l(wèi)是分割算法得到面片的劃分，t是面片真實的劃分。由ai表示面片i的面積，δ(li=ti)的取值是當li=ti時δ(li=ti)=1，即為面片劃分正確的次數(shù)。

(6)

對四足動物、杯子、工具、臺燈、椅子以及燭臺模型集進行一致性分割，計算算法對每個模型劃分的準確程度，并用模型數(shù)量進行平均，得到算法對整個模型集的面片平均劃分準確率。表1為文中算法對六個模型集的實驗數(shù)據(jù)。不同的模型集的平均面片劃分準確率不同。最高的是工具模型集和臺燈模型集，準確率都達到了90%；最差的是椅子模型集，準確率達到67%。整體來看，算法的面片平均劃分準確率較高，能夠較準確地實現(xiàn)模型集分割。

表1 實驗模型集平均面片劃分準確率

圖5為文中算法對六個模型集的分割結(jié)果。可以看出，文中算法能較準確地得到模型的部位劃分，并且同類模型的分割結(jié)果具有一定的對應關(guān)系。如臺燈模型的三分割中，模型被分成了燈頭、連桿和底座。燭臺模型集的三分割中，所有的模型被分為火焰、蠟燭和底座。分割中也存在一定的誤差，這跟模型的特征值計算誤差有關(guān)。

圖5 文中算法的分割結(jié)果

5 算法分析

5.1 實驗結(jié)果對比

圖6為文中算法與文獻[13]和文獻[18]的分割效果對比。文獻[13]采用AGD特征進行模型分割。AGD又稱為平均測地距離，是模型的表面特征。網(wǎng)格中某個點的AGD特征含義是曲面上所有點到該點測地距離之和與曲面面積的比值。該特征能夠表示網(wǎng)格中某個節(jié)點的孤立程度，并且AGD特征的局部極大值體現(xiàn)了模型的末端位置。AGD特征還具有尺度不變性。使用AGD特征進行聚類，能獲得一定的部位信息。但從實驗結(jié)果看，分割結(jié)果不夠準確。熨斗的手把和熨斗沒有完全分開，錯分率較高。

圖6 算法比較

文獻[18]采用離散曲率作為主要特征。曲率表示曲面的彎曲程度，一般在光滑曲面上計算，在三維網(wǎng)格中需要估算離散曲率。物體的部位分割線往往出現(xiàn)在模型的凹區(qū)域。模型某點處的凹凸性取決于該點的高斯曲率K和平均曲率H。通過K和H的正負值來判定曲面的凹凸性，從而提取模型表面凹區(qū)域分割線。從實驗得出，分割線的提取并未完成區(qū)域分割，并且劃分部位沒有明確的語義含義，需要進行下一步的區(qū)域劃分和合并才能獲得準確的部位分割結(jié)果。

文獻[13]和文獻[18]的分割方法都使用了模型的表面特征。表面特征對噪聲敏感，隨著計算誤差的變化分割結(jié)果差異較大；并且這兩種算法都不能形成模型集上的一致性分割，對同類模型分割結(jié)果沒有對應關(guān)系。文中算法不但能獲得較準確的分割結(jié)果，而且對于整組模型的分割部位具有一定的對應關(guān)系。因此，文中算法更加適合進行部位重用和快速建模前的預分割。

5.2 魯棒性分析

模型噪聲對分割效果影響嚴重，在對模型簡化的過程中，曲率、距離等幾何特征發(fā)生了巨大變化。三維模型的面片質(zhì)量對模型分割有著很大的干擾。經(jīng)過不同簡化處理的模型，大大考驗分割的穩(wěn)定程度。因此有必要對算法在不同簡化程度下的魯棒性進行分析和討論。

以7號臺燈模型為例，該模型頂點數(shù)為5 000個，面片數(shù)9 996個。對其進行簡化，結(jié)果見圖7(b)和圖7(c)。圖7(b)頂點2 865個，面片數(shù)5 726。圖7(c)頂點502個，面片數(shù)1 000個。對簡化后模型應用文中算法進行三分割，如圖7所示。

圖7 簡化模型的分割結(jié)果

從分割結(jié)果可以看出，隨著模型的簡化，文中分割算法的分割質(zhì)量并未明顯下降。因此文中分割算法不但具有較高的準確度，對于模型簡化也具有較好的穩(wěn)定度。

6 結(jié)束語

文中提出的一致性分割算法首先對選定模型集上的所有三維模型進行SDF特征計算；其次構(gòu)建相似性矩陣，并用測地距離對相似性矩陣進行稀疏化；最后采用譜聚類對模型集進行分割。實驗結(jié)果表明，該算法能夠?qū)碛卸鄠€具有類似形狀模型的模型集進行有意義的一致性分割，面片平均劃分準確率較好，并且對于模型簡化具有較好的分割穩(wěn)定度。

另外，在如下兩方面還需要繼續(xù)研究：文中需要人工的設定聚類數(shù)量C，不能夠根據(jù)特征值的變化范圍自動確定模型集的分割數(shù)；該算法對特定模型能得到較好的結(jié)果，但對于體特征不明顯的模型不能得到較好的結(jié)果，如椅子模型。今后要針對體特征不明顯的模型研究通用的模型分割算法。