賈 暉，張建剛

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

1 概 述

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

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

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

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

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

2 形狀直徑函數(shù)

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

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

(1)

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

(2)

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

圖1 SDF特征值計(jì)算

圖2 SDF特征分布

3 基于SDF特征的譜聚類(lèi)分割算法

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

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

損失函數(shù)為：

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

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

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

圖3 算法步驟

3.1 相似性矩陣

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

(3)

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

得到的相似性矩陣為：

(4)

3.2 稀疏化

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

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

圖4 錯(cuò)分和測(cè)地距離

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

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

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

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

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

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

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

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

STEP3：求不鄰接頂點(diǎn)的最短路徑，定義鄰接矩陣G：

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

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

(5)

3.3 三維模型集譜聚類(lèi)分割算法

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

輸出：C組聚類(lèi)。

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

(6)

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

表1 實(shí)驗(yàn)?zāi)Ｐ图骄嫫瑒澐譁?zhǔn)確率

圖5為文中算法對(duì)六個(gè)模型集的分割結(jié)果?？梢钥闯?，文中算法能較準(zhǔn)確地得到模型的部位劃分，并且同類(lèi)模型的分割結(jié)果具有一定的對(duì)應(yīng)關(guān)系。如臺(tái)燈模型的三分割中，模型被分成了燈頭、連桿和底座。燭臺(tái)模型集的三分割中，所有的模型被分為火焰、蠟燭和底座。分割中也存在一定的誤差，這跟模型的特征值計(jì)算誤差有關(guān)。

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

5 算法分析

5.1 實(shí)驗(yàn)結(jié)果對(duì)比

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

圖6 算法比較

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

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

5.2 魯棒性分析

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

以7號(hào)臺(tái)燈模型為例，該模型頂點(diǎn)數(shù)為5 000個(gè)，面片數(shù)9 996個(gè)。對(duì)其進(jìn)行簡(jiǎn)化，結(jié)果見(jiàn)圖7(b)和圖7(c)。圖7(b)頂點(diǎn)2 865個(gè)，面片數(shù)5 726。圖7(c)頂點(diǎn)502個(gè)，面片數(shù)1 000個(gè)。對(duì)簡(jiǎn)化后模型應(yīng)用文中算法進(jìn)行三分割，如圖7所示。

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

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

6 結(jié)束語(yǔ)

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

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