基于SDF及K-M eans三維模型一致性分割算法?

賈 暉 張建剛

（1.西安郵電大學計算機學院 西安 710121）（2.西安熱工研究院有限公司電站信息及監控技術部 西安 710032）

1 引言

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

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

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

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

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

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

2 形狀直徑函數（SDF）

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

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

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

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

圖1 計算SDF特征值

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

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

3.1 顯著特征點

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

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

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

STEP2:定義顯著特征點數c，特征點集S。

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

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

圖2 特征點計算

3.2 K-M eans算法

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

輸出:c組聚類。

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

2）以特征點集S中的c個頂點對應的面片作為初始聚類中心: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)為聚類中心代表的劃分結果，否則k=k+1轉STEP3繼續執行。

4 實驗結果與分析

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

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

對模型集中每一個模型采用本文算法進行一致性分割，計算算法對每個模型劃分的準確程度，并用模型數量進行平均，得到了算法對整個模型集的面片平均劃分準確率。表1為本文算法應用式（3）計算的模型分割準確率的實驗數據。從數據顯示算法的面片平均劃分準確率較高，能夠實現模型集上的一致性分割。圖3為本文算法對三維模型的分割結果。

從圖3可以看出，分割部位具有一定的對應關系。四足動物五分割中，模型被分為頭、四足、身子、尾巴和耳朵。酒杯模型三分割中，模型被分為底座、手柄和杯口。工具模型的二分割中，模型被分為手柄和主體。臺燈模型三分割中，模型被分為燈、連接件和底座。由圖3可以得出，本文算法能夠對具有類似形狀特征的模型集進行一致性分割。有些部位的分割由于特征的計算誤差產生錯分，分割準確率見表1所示。

圖3 本文算法的分割結果

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

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

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

圖4 本文算法與其它方法的結果比較

5 結語

本文一致性分割算法共三個步驟，首先對網格模型中每一個三角面片計算SDF特征，其次選取顯著特征點作為K-Means算法的聚類迭代中心，最后對特征進行K-Means聚類。實驗結果證明本文算法能夠對擁有多個具有類似形狀模型的模型集進行有意義的一致性分割，且面片平均劃分準確率較好。

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