,

(中北大學 計算機與控制工程學院,太原 030051)

0 概述

近年來,隨著計算機圖形學、三維掃描設備技術(shù)的發(fā)展以及計算機硬件技術(shù)的提高,三維模型不僅在數(shù)量上有了飛躍性的增長,而且其應用越來越廣泛,應用領(lǐng)域涉及工業(yè)產(chǎn)品設計、虛擬現(xiàn)實、三維游戲、建筑物設計、影視動畫、醫(yī)學診斷和分子生物研究等方面?；谌S模型的幾何處理成為近年來計算機輔助設計和圖形學研究的熱點。但由于原始的三維點云模型缺乏足夠的結(jié)構(gòu)特征和語義信息,因此難以對其進行有效分割。

目前關(guān)于三維模型分割的研究較多。其中:文獻[1]對三維模型進行近似凸分解,通過貪心算法識別三維模型的凹區(qū)域,將其遞歸地分解成更凸的組件;文獻[2]提出一種通過貪心區(qū)域增長獲得弱凸組件的方法。這2種方法需要將三維點云模型轉(zhuǎn)化為網(wǎng)格模型,同時考慮形狀的體積。文獻[3]提出一種基于顯著性的迭代分割方法,通過突出程度、特征選擇和高斯映射將三維模型分割為小于閾值的組件。文獻[4]提出由測地距離的積分定義的連續(xù)函數(shù)檢測突出程度的方法。文獻[5]提出通過凹權(quán)重定義2個鄰接面間的距離,利用隨機游走方法把每個面分配給對應的種子點實現(xiàn)網(wǎng)格過分割,最終通過基于加權(quán)的公共邊界長度迭代合并相鄰部分。文獻[6-7]提出基于凹凸性和曲率的特征點確定方法。文獻[8]基于空間鄰域提出一種改進的模糊C均值算法。文獻[9]由過分割產(chǎn)生的塊之間幾何關(guān)系和凹權(quán)重構(gòu)建關(guān)聯(lián)矩陣,通過本征間隙標準確定分割數(shù)量,由節(jié)點集和節(jié)點域理論確定分割邊界進行三維模型的分割。文獻[10]提出一種計算封閉二維流形邊界上點云SDF值的方法,基于SDF值將三維模型分割成厚度相同的組件。文獻[11-12]提出基于體素特征的分割方法。文獻[11]首先將三維點云模型過分割為超體素,然后通過法向量夾角確定超體素之間的凹凸性,最后引入一種局部受限、有向的加權(quán)一致性算法確定切割平面。文獻[13-14]提出由凹凸信號確定凹特征點,然后通過區(qū)域中心線提取算法以及扇形探射線算法構(gòu)造閉合分割線的方法。

為進一步優(yōu)化三維點云模型的分割效果,本文提出一種基于弱凸性和顯著性的分割方法。首先利用相互可見性,通過譜聚類算法將模型過分割為弱凸塊;然后通過邊界強度和突出定義顯著性,選取有意義的弱凸塊;最后基于相互可見性和體積相似性對弱凸塊進行合并,得到有效的組件,并對最終結(jié)果進行評價。

1 基于顯著性和弱凸性的分割方法

如圖1所示,本文方法主要包括以下步驟:首先通過計算三維點云模型的法向量間夾角構(gòu)建關(guān)聯(lián)矩陣,利用譜聚類方法將點云過分割為弱凸塊(如圖1(b)所示);然后通過顯著性測試提取較小的突出部分和面積較小但邊緣特征點明顯的弱凸塊,對其他弱凸塊則利用Asafi定義的相互可見性[15]屬性合并為弱凸組件(如圖1(c)所示);最后根據(jù)SDF[16]定義體積相似性,合并弱凸組件和顯著性判定時提取的弱凸塊(如圖1(d)所示)。

圖1 本文方法各步驟示意圖

2 弱凸分解

弱凸分解與三維模型分割具有緊密關(guān)系。這2個問題都與“最小規(guī)則”有關(guān),其對三維點云模型分割以最小曲率線劃分,這意味著一個“子部分”可被看作是由近似凸的部分組成。本文通過譜聚類將三維點云模型過分割為弱凸塊,具體過程如下:

1)構(gòu)建關(guān)聯(lián)矩陣Wn×n(n為點云的數(shù)量),確定初始聚類數(shù)目為K,當點i與點j互為k近鄰點且兩點之間凹凸性判定為凸時,Wi,j=1,其他情況下為0。

2)計算對角矩陣Dn×n,對角線上的值為Wn×n矩陣中對應行的和。

3)計算拉普拉斯矩陣L=D-W并進行歸一化處理。

4)求解L的3K個特征值,按降序排序,并計算它們的均值λ,獲取其索引值i。選取特征值的區(qū)間為A=[i-(K+1)/2,i+(K-1)/2],同時求解對應于特征值的特征向量。

5)利用K-means++聚類算法將三維點云模型聚為K類,輸出K個弱凸塊P={P1,P2,…,PK}。

3 顯著性判定

三維點云模型通過弱凸分解產(chǎn)生的部分弱凸塊已經(jīng)具有意義,為防止其在后續(xù)相互可見性算法中被合并,檢測這些弱凸塊,并將其標記為S={S1,S2,…,St}。本節(jié)提出一種“視覺突出判定分割結(jié)果”的方案,其基于認知心理學中的“部分顯著性”理論。該理論認為“子部分”的顯著性通常由3個因素決定:邊界強度,突出,相對尺寸。本節(jié)通過突出和邊界強度判定顯著性,首先給出定量定義,然后描述它們在分割過程中的具體計算方法。

1)邊界強度:根據(jù)橫截性原理,組件邊界通常位于凹陷處。文獻[17]指出,邊界強度由法線轉(zhuǎn)向決定,如圖2所示,對于二維輪廓,分割邊界的兩側(cè)通常具有2條法線,并且它們之間的角度可以在某種意義上表示該邊界的強度。對于三維形狀,高斯曲率可用于測量組件邊界的強度。

圖2 法線變化決定邊界強度示意圖

圖3 邊界特征點選擇示例(人的眼睛)

2)突出:此因素描述組件從其主體突出的程度。對于二維模型輪廓,可以量化為組件的周長(不包括其底部)與其底部長度的比率。對于3D形狀,組件的底部為組件的邊界形成的表面。因此,三維模型組件的突起可以被量化為組件表面的面積與其底面的面積的比率或組件上點到底面的最大距離與底面最大擬合圓的半徑的比率。

通過弱凸塊輪廓上的點擬合平面檢測突出性。本文通過有向的加權(quán)一致性算法擬合平面,并通過S上點到擬合平面的最大距離判斷其突出性。典型的RANSAC算法可以平等地處理點云,根據(jù)“部分顯著性”理論,組件邊界通常位于凹陷處,為邊界點賦予權(quán)值,將凹點賦值為1,凸點賦值為0,將其擴展為加權(quán)的RANSAC算法。利用加權(quán)的RANSAC算法使擬合平面包含具有高權(quán)值的點,排除低權(quán)值的點。平面模型的得分通過下式得出:

(1)

其中,P為具有高權(quán)值點的集合,ωi為邊界點的高斯曲率。

令S為弱凸塊,計算S上點到擬合平面的最大距離d,并令r為擬合平面上最大包圍圓的半徑。如果d/r>ε2,則接受此弱凸塊,ε2=0.74。上述過程示例如圖4所示。

圖4 突出性選擇示例(人的耳朵)

通過顯著性判定可以選擇較小的突出部分和面積較小但邊緣特征點明顯的分割部分,防止其在后續(xù)的相互可見性合并算法中被合并。

4 區(qū)域合并

本節(jié)提出區(qū)域合并算法,首先給出相關(guān)定義。

定義1(相互可見性) 令S為弱凸塊上的隨機采樣點的集合,LLoS(S)為S中相互可見點的對數(shù)的集合。對于2個弱凸塊上的取樣點子集A、B包含于S,LLoS(A,B)為(i,j)的集合,其中i∈A,j∈B,且i、j是相互可見的。S的凸度等級定義為:

(2)

其中,|LLoS(S)|為S中可見對的數(shù)量,|S|為取樣點的數(shù)量。相互可見性定義示意圖如圖5所示,其中實線表示兩點可見,點劃線為不可見。

圖5 相互可見性定義示意圖

定義2(體積相似性) 給定2個相鄰的弱凸組件Ci和Cj,通過文獻[16]提出的形狀直徑函數(shù)計算其直方圖,然后利用EMD距離計算2個相鄰弱凸組件之間的相似性,具有高體積相似性的2個相鄰弱凸組件可能屬于相同的語義形狀部分,可以被合并。

ddist(Ci,Cj)=EEMD(hi,hj)

(3)

4.1 相互可見性合并

根據(jù)弱凸塊的相互可見性將弱凸塊聚類成較大的弱凸組件。目標是最小化所得到的組件的數(shù)量,同時保持組件內(nèi)相互可見性高于閾值θ。該閾值量化了允許合并的弱凸塊偏離完美凸度的程度。本文采用迭代合并方法,其中第1次迭代嚴格執(zhí)行弱凸塊之間的相互可見性,以下迭代逐漸放寬此約束。每次迭代根據(jù)弱凸塊的相互可見性以貪婪的方式合并多對相鄰的弱凸塊。

給定一組初始的弱凸塊P={P1,P2,…,Pn-t},根據(jù)相鄰塊之間的相互可見性合并獲得一組弱凸組件C={C1,C2,…,Cm},每個組件Ci對應于弱凸塊Pi。執(zhí)行合并迭代首先通過弱凸塊的相互可見性按照降序?qū)λ邢噜徑M件對進行排序;然后按照這個順序,對滿足于θ的Ci和Cj的所有成對組合進行合并。這種迭代方法的優(yōu)點在于:允許在早期的迭代中創(chuàng)建高度自我可見的組件,如果它們的更新的相互可見性允許,將進一步擴展并與其他組件融合。本文采用3次迭代:θ1=0.9,θ2=0.8,θ3=0.7。

4.2 體積相似性合并

在一些情況下,通過上述步驟形成的弱凸組件已經(jīng)具有意義。然而,對于結(jié)構(gòu)復雜的三維模型需要進一步對組件合并以達到接近語義的分割,在如圖6所示的手模型中,根據(jù)顯著性提取的中指上端部分,需要根據(jù)體積相似性進行進一步合并,相似性由基于形狀直徑函數(shù)的分量特征決定。

圖6 相似性合并示意圖

體積相似性合并過程如下:

1)給定一組弱凸組件C={C1,C2,…,Cn}={C1,C2,…,Cm,S1,S2,…,St},對于每個組件Ci,通過計算SDF值的直方圖確定體積特征。首先在每個Ci的表面上均勻采樣s個點,每個采樣點Pμ∈Ci形成具有角度α的錐體的尖端,方向為-n,其中nμ是Pμ的法線;然后計算落在圓錐體內(nèi)的射線段,利用Pμ的法線和射線之間的夾角的余弦加權(quán)這些射線段;最后選擇中位數(shù)作為該點的SDF值。當沒有這樣的射線落在該點的錐體內(nèi)時,該點被標記為平面。本文實驗中使用參數(shù)α=2π/18。

2)使用所有Pμ∈Ci的SDF值,創(chuàng)建一個直方圖,獲取Ci的體積分布。當Ci為平面或近似平面的情況下,Ci中的絕大多數(shù)點將被標記為沒有SDF值,由此產(chǎn)生的hi將被錯誤地判定為空,因此,將判定為空的組件標記為平面。然后將平面組件從下一個合并步驟中排除,并在稍后處理。

3)使用體積特征,根據(jù)式(2)計算所有成對弱凸組件之間的相似性,構(gòu)建距離矩陣D,同時考慮一對弱凸組件之間的接縫的凸度,用于選擇哪個相鄰組件是合并的最佳選擇。對于弱凸組件,利用k-nearest圖和邊界長度加權(quán)定義組件邊界的凸度:

(4)

(5)

5 實驗結(jié)果

在Windows系統(tǒng)上,以普林斯頓數(shù)據(jù)集為基準,通過文獻[18]提供的軟件進行評估、分析,為完整起見,本文同時增加COSEG數(shù)據(jù)集[19]和文獻[20]的數(shù)據(jù)集,實驗環(huán)境為Intel Core i3 3.3 GHz CPU,4 GB內(nèi)存。

本節(jié)評估并比較本文方法和Heterogeneous[9]、SDF[10]、Constraint Planar[11]、Convex-Concave[12]4種方法,評價指標為Rand指數(shù)、Hamming距離、分割差異性、全局與局部一致性誤差。其中:Rand 指數(shù)通過分析一對點在實際分割和基準分割中是否處于相同分割部分建立對模型分割結(jié)果的評價;Hamming 距離通過計算分割部分之間的漢明距離來定量計算整體區(qū)域差異;分割差異性通過計算邊界距離度量分割差異,具體通過計算實際分割邊界中的點與基準分割邊界中最近點的距離的和得到;全局與局部一致性差異用來測量分割結(jié)果層次的相似性和差異,全局一致性差異要求所有分割結(jié)果的細化方向相同,局部一致性差異則允許分割結(jié)果在不同方向細化。圖7顯示了上述4項指標的比較結(jié)果,圖8顯示了數(shù)據(jù)集中代表性模型的分割效果。實驗結(jié)果表明,本文提出的方法優(yōu)于無監(jiān)督方法,可以同時分割大的分支(胳膊、頭部)和小的細節(jié)部分(眼睛、指頭),提高了分割結(jié)果層次的相似性,同時對局部的表面擾動和非剛性變化的魯棒性較好。

圖7 分割評估結(jié)果

圖8 本文算法在3種數(shù)據(jù)集上的分割效果

6 結(jié)束語

本文基于顯著性和弱凸性提出一種新的三維點云模型分割方法。通過顯著性判定提取部分有意義的“子部分”,利用顯著性解決欠分割問題,通過相互可見性和體積相似性解決過分割問題,最終得到有效的分割結(jié)果。實驗結(jié)果表明,本文方法能夠有效提高分割質(zhì)量,但其不足之處是對于點云密度較小的模型得到的分割邊界質(zhì)量較差,需要通過重采樣獲取較好的結(jié)果。此外,其對于魚類等平滑模型缺乏清晰的幾何邊緣,分割效果也欠佳,下一步將針對上述問題對本文方法進行改進。

[1] LIEN J M,AMATO N M.Approximate convex decomposi-tion of polyhedra and its applications[J].Computer Aided Geometric Design,2008,25(7):503-522.

[2] KREAVOY V,DAN J,SHEFFER A,et al.Model composition from interchangeable components[C]//Proceedings of the 15th Pacific Conference on Computer Graphicsand Applications.Washington D.C.,USA:IEEE Press,2007:129-138.

[3] CHEN H K,HE Y D.A novel part-salience-based approach to fast iterative 3D mesh segmentation[C]//Proceedings of International Symposium on Computer.Washington D.C.,USA:IEEE Press,2016:311-314.

[4] AGATHOS A,PRATIKAKIS I,PERANTONIS S,et al.Protrusion oriented 3D mesh segmentation[J].Visual Computer,2010,26(1):63-81.

[5] LAI Y K,HU S M,MARTIN R R,et al.Rapid and effective segmentation of 3D models using random walks[J].Computer Aided Geometric Design,2009,26(6):665-679.

[6] 史皓良,吳祿慎,余喆琦,等.散亂點云數(shù)據(jù)特征信息提取算法[J].計算機工程,2017,43(8):279-283.

[7] 朱世松,樊菁芳,朱洪錦.基于輪廓特征點的重疊車輛檢測與分割[J].計算機工程,2016,42(7):244-250.

[8] 王禹君,周菊香,徐天偉.改進模糊C均值算法在民族服飾圖像分割中的應用[J].計算機工程,2017,43(5):261-267.

[9] THEOLOGOU P,PRATIKAKIS I,THEOHARIS T.Unsupervised spectral mesh segmentation driven by heterogeneous graphs[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2017,39(2):397-410.

[10] HUSKA M,MORIGI S.A meshless strategy for shape diameter analysis[J].Visual Computer,2017,33(3):303-315.

[11] SCHOELER M,PAPON J,WORGOTTER F.Constrained planar cuts-object partitioning for point clouds[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Washington D.C.,USA:IEEE Press,2015:5207-5212.

[12] 馬元魁,白曉亮.三角網(wǎng)格模型體素特征分割[J].計算機科學,2015,42(10):13-15.

[13] 王澤昊,黃常標,林忠威.三角網(wǎng)格模型的最小值邊界分割[J].計算機輔助設計與圖形學學報,2017,29(1):62-71.

[14] 董洪偉,李 重,周儒榮,等.基于凹凸信號的網(wǎng)格分割[J].計算機輔助設計與圖形學學報,2009,21(3):295-304.

[15] ASAFI S,GOREN A,COHEN-OR D.Weak convex decomposition by lines-of-sight[J].Computer Graphics Forum,2013,32(5):23-31.

[16] SHAPIRA L,SHAMIR A,COHEN-OR D.Consistent mesh partitioning and skeletonisation using the shape diameter function[J].Visual Computer,2008,24(4):249-259.

[17] HOFFMAN D D,SINGH M.Salience of visual parts[J].Cognition,1997,63(1):29-78.

[18] CHEN X,GOLOVINSKIY A,FUNKHOUSER T.A benchmark for 3D mesh segmentation[J].ACM Transactions on Graphics,2009,28(3):341-352.

[19] WANG Y,ASAFI S,KAICK O V,et al.Active co-analysis of a set of shapes[J].ACM Transactions on Graphics,2012,31(6):165.

[20] BENHABILES H,VANDEBORRE J P,LAVOUE G,et al.A framework for the objective evaluation of segmentation algorithms using a ground-truth of human segmented models[C]//Proceedings of IEEE International Conference on Shape Modeling and Applications.Washington D.C.,USA:IEEE Press,2009:36-43.