基于形狀直徑函數(shù)的三維模型集一致性分割算法研究

賈暉 張建剛

摘要：為了有效提高對三維模型集進行一致性分割算法的準確率和效率，提出一種三維模型集一致性分割算法。該算法基于形狀直徑函數(shù)特征和譜聚類方法。首先計算模型各個面片的形狀直徑函數(shù)特征（SDF）特征;其次計算模型各面片之間的形狀相似性，形成相似性矩陣。最后采用譜聚類算法對模型集進行一致性分割。將本文算法與相關方法進行對比，實驗結果表明，本文算法能準確的對一致性分割數(shù)據(jù)集中的若干模型進行有意義的分割，使得分割部位具有一定的對應關系，且面片平均劃分準確率較好。

Abstract： In order to improve the accuracy and efficiency of the algorithm of 3D model set consistency segmentation， an algorithm of 3D model set consistency segmentation is proposed. This algorithm is based on Shape diameter function（SDF） and spectral clustering. At first， The face SDF characteristics of each models in the model set is extracted; and then The similarity between each face of the model is calculated， and the similarity matrix is formed. At last utilize the spectral clustering algorithm to segment the model set consistently. The algorithm in this paper is compared with the relevant methods， the experimental results show that the proposed algorithm can accurately segment several models in a consistent data set， make the segmentation parts have a certain correspondence， and the average segmentation accuracy is better.

關鍵詞：三維模型;一致性分割;形狀直徑函數(shù);譜聚類

Key words： 3D model;consistency segmentation;SDF;spectral clustering

中圖分類號：TP391? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2019）17-0277-03

1? 概述

三維模型有意義的分割是根據(jù)模型的幾何特征將模型分解成為有意義的連通子部分[1]。單個模型由于分割尺度的不同造成分割結果的不一致，難以實現(xiàn)模型重用。

近年來模型集的一致性分割成為研究熱點[2][3]。Van Kaick[4]提出了模型集一致性分割的定義。設模型集上有n個模型，構建模型集上各模型分割部位之間的關聯(lián)關系R。可以證明模型集上部位之間的關聯(lián)關系具有自反、對稱和傳遞性，是等價關系。三維模型集的一致性分割就是基于該等價關系進行的。與單個模型分割相比一致性分割的優(yōu)勢是由于所有模型有著相同的分割尺度，所以有利于分割結果的重用和比較。一致性分割算法更具有實用性，被廣泛應用于快速建模[5][6][7]及三維數(shù)字模型重建[8][9][10]。

在三維模型的一致性分割方法中，聚類算法是模型分割的主流方法。特征的選擇不能選用如曲率法線方向等表面特征，因為相似的部位可能會因為姿態(tài)的變化而有不同的表面特征，使得分割誤差增大，分割效果下降。

本文采用形狀直徑函數(shù)[11]（SDF）特征及譜聚類方法對整組模型集進行一致性分割。將三維模型看做帶權無向圖，面片看做圖的結點，面片與面片之間的特征相似性關系看做圖的邊。將面片的分割問題，看做圖的分割問題。首先提取模型集中各個模型面片的SDF特征，其次計算面片特征之間的相似性矩陣。最后采用譜聚類對三維模型進行分割。

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

形狀直徑函數(shù)（Shape Diameter Function SDF）最早由Shapira提出。該特征為模型的體特征，當模型變形時，曲率、法線方向、距離都會發(fā)生變化，但模型體積保持不變。適用于多個模型相似部位的特征劃分。

SDF特征的計算方法如下：

STEP1：從每個面片頂點以法線反方向為軸做圓錐。在圓錐內部，向法線反方向發(fā)射射線。

STEP2：計算射線平均長度、長度標準差和定義有效范圍。分別用rm、？滓和range表示。

STEP3：若 定義權重 是rj與圓錐軸的夾角。面片頂點的SDF值計算公式為：

STEP4：計算各面片重心點的SDF值，利用公式（2）對重心點的SDF值歸一化。其中？琢為歸一化參數(shù)。

其計算示意圖如圖1所示。SDF特征和模型的體積相關，與表面特征如曲率、法線方向等特征無關。特別是姿態(tài)不同而體積相似的模型。如臺燈模型集中各個臺燈具有不同的底座，連接桿和燈頭。各部位之間曲率特征不同但體特征相似。

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

本文研究一種一致性分割算法。該算法是基于譜聚類方法和形狀直徑函數(shù)特征的。譜聚類算法建立在譜圖理論之上，將待聚類模型視為帶權無向圖。圖的頂點為待聚類的面片，圖的邊權為面片之間的相似性關系，邊權矩陣被稱為相似性矩陣。利用譜圖理論分析該無向圖，找出分類結構。

3.1 相似性矩陣

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

wij為面片i和面片j的相似度。？滓I是SDF特征的尺度參數(shù)。

3.2 稀疏化

相似度計算可得三維模型中任意兩個三角面片的相似度。若模型集中所有面片的個數(shù)為n，則W為n×n維矩陣。此時圖為n個結點的完全圖。距離過大的面片屬于一個劃分的概率低。因此定義相似性計算距離ri，面片i到其它所有面片的測地距離，取其平均值確定相似矩陣的計算距離。 ，其中j=1…n。采用以下方法確定最終的相似性矩陣。d（i，j）為i面與j面的測地距離，以頂點間的測地距離的平均值來確定。

4? 實驗結果與分析

在Windows 上，實驗數(shù)據(jù)集采用一致性分割數(shù)據(jù)集（COSEG），該數(shù)據(jù)集中具有多個大類的三維模型集，如四足動物、椅子、工具、臺燈和酒杯等。每個模型集中又有若干個類似的三維模型。對三維模型的一致性分割提供很好的實驗數(shù)據(jù)。算法運行環(huán)境為Intel Core i9 7900X CPU， 8GB內存， Microsoft Visual Studio 2010。

對杯子，工具和臺燈模型集進行一致性分割。圖2為本文算法的分割結果。從實驗結果來看，面片被較準確的劃分到相應的部位上去。錯誤劃分的面片較少，劃分部位較為完整。并且同類模型的分割結果具有一定的對應關系。如臺燈模型的三分割中，模型被分成了燈頭，連桿和底座。分割中也存在一定的誤差，這跟模型的特征值計算誤差有關。實驗結果表明本文算法能準確高效的完成一致性分割。

圖3為本文算法與文獻[13]和文獻[14]的分割效果對比。文獻[13]采用AGD特征進行模型分割，能獲得一定的部位信息，但分割結果不夠準確。文獻[14]采用離散曲率作為主要特征，能提取模型表面凹區(qū)域分割線，需要進行下一步的區(qū)域劃分才能獲得準確的部位分割結果。并且這兩種算法都不能形成模型集上的一致性分割。本文算法不但能獲得較準確的分割結果，而且對于整組模型的分割部位具有一定的對應關系。本文的分割算法更加適合進行部位重用和快速建模前的預分割。

模型的噪聲對分割結果影響嚴重，在面片簡化的過程中，表面特征會發(fā)生顯著變化，但體特征則不會。本文算法與體特征相關，對于模型的簡化有很強的魯棒性。模型簡化不會對模型分割效果產(chǎn)生影響。

5? 總結

在本文算法中，首先計算模型集上各個三維模型的面片SDF值，作為特征向量;其次構建各個模型之間的相似性矩陣，根據(jù)距離越近屬于一個分塊的概率越高的原理對相似性矩陣稀疏化;最后利用譜聚類進行分割。實驗結果表明對一致性分割數(shù)據(jù)集中多個具有類似形狀的模型能夠實現(xiàn)有意義的一致性分割，且分割結果良好。

另外，需要繼續(xù)研究的問題是：分割部位數(shù)需要在算法執(zhí)行前人工設定，扔不能根據(jù)特征的取值范圍自動計算。對于體特征不明顯的模型算法得不到較好的分割結果。

參考文獻：

[1]Ngo D T ， Ostlund J ， Fua P . Template-Based Monocular 3D Shape Recovery Using Laplacian Meshes[J]. IEEE TPAMI， 2016， 38（1）：172-187.

[2]Kleiman Y， Fish N， Lanir J， et al. Dynamic maps for exploring and browsing shapes[J]. Computer Graphics Forum， 2013， 32（5）：187-196.

[3]Kalogerakis， Evangelos，Hertzmann， Aaron，Singh， Karan.

"Learning 3D mesh segmentation and labeling."[C]. ACM Siggraph. 2010.

[4]Oliver van Kaick，Hao Zhang，Ghassan Hamarneh et al. A Survey on Shape Correspondence[J]. Computer Graphics Forum， 2011， 30（6）：1681-1707.

[5]Averkiou M， Kim V G， Zheng Y， et al. ShapeSynth： Parameterizing model collections for coupled shape exploration and synthesis[J]. Computer Graphics Forum， 2014， 33（2）：125-134.

[6]Chaudhuri S， Koltun V. Data-driven suggestions for creativity support in 3D modeling[C]// Acm Siggraph Asia. 2010.

[7]Hang S， Maji S， Kalogerakis E， et al. Multi-view Convolutional Neural Networks for 3D Shape Recognition[C]// IEEE International Conference on Computer Vision. 2015.

[8]Kreavoy V， Dan J， Sheffer A. Model Composition from Interchangeable Components[C]. Conference on Computer Graphics & Applications. IEEE Computer Society， 2007：129-138.

[9]Mejia D ， Ruiz-Salguero O ， Cadavid C A . Spectral-based mesh segmentation[J]. International Journal on Interactive Design and Manufacturing， 2016：1-12.

[10]Lun Z， Gadelha M， Kalogerakis E， et al. 3D Shape Reconstruction from Sketches via Multi-view Convolutional Networks[J]. 2017.

[11]Shapira， Lior et al.Consistent mesh partitioning and skeletonisation using the shape diameter function. The Visual Computer 24.4（2008）：249-259.

[12]納躍躍，于劍.一種用于譜聚類圖像分割的像素相似度計算方法[J].南京大學學報（自然科學），2013，49（2）：159-168.

[13]Zhang， E. Feature-based surface parameterization and texture mapping. ACM Trans. Graphics 24.1（2005）：1-27.

[14]賈暉，耿國華，周明全，等.基于區(qū)域離散曲率的三維網(wǎng)格分水嶺分割[J].計算機工程與應用，2015，51（11）：182-186.

作者簡介：賈暉（1978-），女，陜西西安人，博士，講師，研究方向為三維數(shù)字幾何處理;張建剛（1977-），男，陜西西安人，碩士，高工，研究方向為智能信息處理。