賈 暉 張建剛

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

1 引言

近年來，由于三維掃描和三維建模技術(shù)的大量應(yīng)用，三維模型的數(shù)量呈指數(shù)級增長。使得基于三維網(wǎng)格的幾何處理成為重要研究熱點。特別是快速建模、模型理解和三維數(shù)字重建。三維模型分割就是以上熱點問題的基礎(chǔ)研究方向。三維模型分割是根據(jù)模型的幾何特征將模型分解成為一組數(shù)目有限、各自具有簡單形狀意義且各自連通的子部分［1］。

模型集一致性分割是指同時對一組形狀相關(guān)但姿態(tài)有差異的三維模型集進行分割，得到語義相關(guān)分割結(jié)果的分割方法［2］。一致性分割算法能得到同尺度的分割結(jié)果，算法具有實用性，被廣泛應(yīng)用于快速建模［3～5］及三維數(shù)字模型重建［6～8］。

現(xiàn)有的分割方法中，文獻［9～11］采用離散曲率作為特征對三維模型進行分割。由于曲率是曲面的幾何性質(zhì)，由于噪聲的存在，三角網(wǎng)格頂點的離散曲率計算精度不夠，在很大程度上影響網(wǎng)格分割算法效果。

文獻［12］采用平均測地距離（AGD）對模型進行分割。AGD特征具有尺度不變性，能很好地衡量模型中每一點的孤立程度。然而該特征無法精確描述模型的部位特征，特別是對一個具有相似形狀的模型集。

絕大多數(shù)算法都是采用了聚類的方法。而聚類算法可分為有監(jiān)督聚類算法和無監(jiān)督聚類算法兩類。算法中所采用的形狀描述子大多都基于模型的表面特征如曲率、法線方向、平均測地距離等特征來描述模型之間的形狀特征并對模型集進行分割。有監(jiān)督的算法能獲得較好的分割結(jié)果，然而設(shè)計訓(xùn)練集需要大量的時間，而且需要大量的人工參與。而模型表面特征如曲率，測地距離，法線方向等容易因為類似模型的不同姿態(tài)的變化而發(fā)生顯著變化，使其喪失模型間形狀可比性。因而采用表面特征不利于在具有形狀相似而姿態(tài)存在差異的模型集上進行一致性分割。

本文提出一種采用形狀直徑函數(shù)［13］（SDF）特征的無監(jiān)督模型集進行一致性分割算法。SDF特征不是模型的表面特征而是基于模型體特征的形狀特征。它具有當(dāng)模型姿態(tài)發(fā)生變形時，同一部位的特征值基本保持不變的特點。非常適用于具有不同姿態(tài)但形狀相似的模型之間的部位相似性計算。首先提取模型集中各個模型的SDF特征，其次K-Means算法對三維模型集中的各個模型進行聚類分割。為了提高K-Means算法的實現(xiàn)效率，用顯著特征點作為初始迭代的中心。實驗證明將本文算法應(yīng)用于COSEG［14］模型集中能較高效、準(zhǔn)確地實現(xiàn)模型集的一致性分割。

2 形狀直徑函數(shù)（SDF）

形狀直徑函數(shù)（SDF）最早由Shapira在研究模型分割和骨架提取時提出。

SDF特征的計算方法如下:對于三角面片上的每一個頂點，從該頂點以法線反方向為軸做圓錐。在圓錐內(nèi)部，從頂點向三角面片的另一側(cè)發(fā)射射線。如圖1所示。對于每一條射線計算發(fā)出頂點到與另一側(cè)面片交點之間的射線長度。設(shè)ri是第i條射線的長度，且i=[1…n]。射線的平均長度為，射 線 長 度 標(biāo) 準(zhǔn) 差 為 σ=。定義標(biāo)準(zhǔn)差的有效范圍為。如果 rj∈range ，則保留，否則將該射線刪除。對于每一條范圍內(nèi)的射線 rj∈range，定義權(quán)重 ωj，且 ωj=1/αj，αj是 rj與圓錐軸的夾角。頂點的SDF值計算公式為

M是落在range范圍內(nèi)的射線的數(shù)量，取射線與圓錐夾角的倒數(shù)作為參數(shù)是希望射線在每個單位面積內(nèi)均勻出現(xiàn)。大的夾角出現(xiàn)的頻率較高，所以具有較小的權(quán)重。每個三角面片的SDF值的計算方法是首先使用式（1）計算各面片重心點的SDF值，其次使用式（2）進行歸一化，獲得面的SDF值，其中α為歸一化參數(shù)。

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

圖1 計算SDF特征值

3 基于SDF的K-M eans分割算法

本文采用K-Means算法對模型進行聚類分割。K-Means算法具有實現(xiàn)簡單，且算法的時間復(fù)雜度接近于線性的優(yōu)點。但是K-Means算法聚類中心的選取是隨機選取的，而聚類中心對分割結(jié)果及迭代次數(shù)具有巨大影響。本文首先計算模型的顯著特征點，用顯著特征點作為分割的聚類中心，求得模型集的分割結(jié)果。

3.1 顯著特征點

定義模型距離重心最遠的點為顯著特征點。代表了分割的部位。求取顯著特征點的好處是能大大減少K-Means算法的迭代次數(shù)，且特征點數(shù)由人工定義，提高分割的準(zhǔn)確性。

定義顯著特征點集為S，具體的計算步驟為

STEP1:求模型集中每個模型的重心點坐標(biāo)v(x,y,z)。

STEP2:定義顯著特征點數(shù)c，特征點集S。

STEP3:對于每個三維模型M，求對偶圖形M'，所有分割的計算在M'上進行。將對面的分割轉(zhuǎn)化為對頂點的分割。計算v1=m in(D(vi,v))，其中vi為M'中各點，v1為重心點v距離三維模型各點歐式距離最近頂點，代表三維模型的主體部分。

STEP4:計算d(vi,v1)，求點云中其它點到v1的測地距離，取距離最大的前c-1個，加入到特征點集S中，代表三維模型的部位劃分部分。圖2為各模型的特征點結(jié)算結(jié)果示意圖。

圖2 特征點計算

3.2 K-M eans算法

輸入:待分割三維模型M'，特征點集S，聚類數(shù)c。

輸出:c組聚類。

1）根據(jù)式（2）計算 M'中所有面的SDF特征值F={f1,f2,…fm}。m為三角網(wǎng)格的面片數(shù)。

2）以特征點集S中的c個頂點對應(yīng)的面片作為初始聚類中心:O1(1)，O2(1)，…Oc(1)。其中Oi(k)代表在第k次迭代中第i個聚類中心。

3）計算F中各面片SDF特征值與聚類中心SDF特征值的歐式距離，將每個面片歸到最近的類中。

4）計算Oi(k)中所有面片SDF特征平均值，將得到的平均值作為這一類新的聚類中心Oi(k+1)。

5）對于所有的 i=1…c，如果 Oi(k)=Oi(k+1)則輸出O1(k)，O2(k)，…Oc(k)為聚類中心代表的劃分結(jié)果，否則k=k+1轉(zhuǎn)STEP3繼續(xù)執(zhí)行。

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

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

以統(tǒng)計數(shù)據(jù)來評價分割的好壞，文獻［11］定義了面片劃分的準(zhǔn)確程度的算法，用劃分正確面積與模型總面積的比值來計算。式（3）中l(wèi)是分割算法得到面片的劃分，t是面片真實的劃分。由ai代表面片 i的面積，δ(li=ti)的取值是當(dāng) li=ti時δ(li=ti)=1，即為面片劃分正確的次數(shù)。

對模型集中每一個模型采用本文算法進行一致性分割，計算算法對每個模型劃分的準(zhǔn)確程度，并用模型數(shù)量進行平均，得到了算法對整個模型集的面片平均劃分準(zhǔn)確率。表1為本文算法應(yīng)用式（3）計算的模型分割準(zhǔn)確率的實驗數(shù)據(jù)。從數(shù)據(jù)顯示算法的面片平均劃分準(zhǔn)確率較高，能夠?qū)崿F(xiàn)模型集上的一致性分割。圖3為本文算法對三維模型的分割結(jié)果。

從圖3可以看出，分割部位具有一定的對應(yīng)關(guān)系。四足動物五分割中，模型被分為頭、四足、身子、尾巴和耳朵。酒杯模型三分割中，模型被分為底座、手柄和杯口。工具模型的二分割中，模型被分為手柄和主體。臺燈模型三分割中，模型被分為燈、連接件和底座。由圖3可以得出，本文算法能夠?qū)哂蓄愃菩螤钐卣鞯哪Ｐ图M行一致性分割。有些部位的分割由于特征的計算誤差產(chǎn)生錯分，分割準(zhǔn)確率見表1所示。

圖3 本文算法的分割結(jié)果

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

將本文算法與文獻［9］、文獻［12］和文獻［15］方法進行對比。文獻［15］采用傳統(tǒng)K-Means聚類算法進行分割。傳統(tǒng)K-Means算法簡單、執(zhí)行速度快，但是聚類中心隨機選擇，一旦初始聚類中心選擇不好則迭代時間長，很難達到理想的分割效果。

最常用的表面特征就是曲率特征和平均測地距離特征。文獻［9］采用曲率特征進行分割。曲率能較好地反應(yīng)三維曲面在局部的彎曲程度，但離散曲率的計算容易受到噪聲的干擾，且類似形狀模型若有姿態(tài)的變化則會造成曲率的不同，不利于產(chǎn)生一致性分割結(jié)果。文獻［12］提出的AGD特征不能很好的實現(xiàn)完整部位的分割。圖4為本文算法的分割結(jié)果與文獻［9］算法和文獻［12］算法的分割結(jié)果對比。從比較結(jié)果來看，本文算法的一致性分割結(jié)果更為準(zhǔn)確。

圖4 本文算法與其它方法的結(jié)果比較

5 結(jié)語

本文一致性分割算法共三個步驟，首先對網(wǎng)格模型中每一個三角面片計算SDF特征，其次選取顯著特征點作為K-Means算法的聚類迭代中心，最后對特征進行K-Means聚類。實驗結(jié)果證明本文算法能夠?qū)碛卸鄠€具有類似形狀模型的模型集進行有意義的一致性分割，且面片平均劃分準(zhǔn)確率較好。

另外，工作中如下兩點還需要繼續(xù)研究:首先分割部位的數(shù)量需要人為設(shè)定，還不能實現(xiàn)完全無監(jiān)督的模型分割；其次SDF特征為體特征，但對于同一模型具有類似體特征的部位不能很好地區(qū)分。未來的主要研究方向為采用多特征來提高分割的準(zhǔn)確性，并實現(xiàn)必要的特征優(yōu)化。