賈暉 張建剛

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

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.

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

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

中圖分類號(hào)：TP391? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1006-4311（2019）17-0277-03

1? 概述

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

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

在三維模型的一致性分割方法中，聚類算法是模型分割的主流方法。特征的選擇不能選用如曲率法線方向等表面特征，因?yàn)橄嗨频牟课豢赡軙?huì)因?yàn)樽藨B(tài)的變化而有不同的表面特征，使得分割誤差增大，分割效果下降。

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

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

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

SDF特征的計(jì)算方法如下：

STEP1：從每個(gè)面片頂點(diǎn)以法線反方向?yàn)檩S做圓錐。在圓錐內(nèi)部，向法線反方向發(fā)射射線。

STEP2：計(jì)算射線平均長(zhǎng)度、長(zhǎng)度標(biāo)準(zhǔn)差和定義有效范圍。分別用rm、？滓和range表示。

STEP3：若 定義權(quán)重 是rj與圓錐軸的夾角。面片頂點(diǎn)的SDF值計(jì)算公式為：

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

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

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

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

3.1 相似性矩陣

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

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

3.2 稀疏化

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

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

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

對(duì)杯子，工具和臺(tái)燈模型集進(jìn)行一致性分割。圖2為本文算法的分割結(jié)果。從實(shí)驗(yàn)結(jié)果來看，面片被較準(zhǔn)確的劃分到相應(yīng)的部位上去。錯(cuò)誤劃分的面片較少，劃分部位較為完整。并且同類模型的分割結(jié)果具有一定的對(duì)應(yīng)關(guān)系。如臺(tái)燈模型的三分割中，模型被分成了燈頭，連桿和底座。分割中也存在一定的誤差，這跟模型的特征值計(jì)算誤差有關(guān)。實(shí)驗(yàn)結(jié)果表明本文算法能準(zhǔn)確高效的完成一致性分割。

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

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

5? 總結(jié)

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

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

參考文獻(xiàn)：

[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ì)算方法[J].南京大學(xué)學(xué)報(bào)（自然科學(xué)），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].計(jì)算機(jī)工程與應(yīng)用，2015，51（11）：182-186.

作者簡(jiǎn)介：賈暉（1978-），女，陜西西安人，博士，講師，研究方向?yàn)槿S數(shù)字幾何處理;張建剛（1977-），男，陜西西安人，碩士，高工，研究方向?yàn)橹悄苄畔⑻幚怼?/p>