三維網(wǎng)格分割的經(jīng)典方法

三維網(wǎng)格分割的經(jīng)典方法摘要：本文針對(duì)三維網(wǎng)格分割問(wèn)題，提出一個(gè)經(jīng)典的方法。該方法基于微分幾何和測(cè)地距離。在算法中，將面片類(lèi)型相同的頂點(diǎn)分割在一起。測(cè)地距離利用頂點(diǎn)之間的最短路徑表示，這里可以利用一些經(jīng)典的算法求最短路徑，如Dijkstra算法。但是當(dāng)網(wǎng)格的數(shù)量很多時(shí)，Dijkstra算法的效率很低。因此，此算法避免了在整個(gè)網(wǎng)格上應(yīng)用最短路徑算法，在局部網(wǎng)格中求最短路徑，從而減少了計(jì)算量。本文在人造物體的三維網(wǎng)格模型以及分子結(jié)構(gòu)中驗(yàn)證了該方法的有效性。關(guān)鍵字：幾何算法面片分割測(cè)地距離簡(jiǎn)介3D物體的三維網(wǎng)格表示法具有很多的應(yīng)用。例如，在圖像分析中，表示利用深度圖像重建的物體表面。此外，在復(fù)雜物體和場(chǎng)景的建模和可視化中也有廣泛的應(yīng)用。在網(wǎng)格面片的分析中，網(wǎng)格分割已經(jīng)成為一個(gè)關(guān)注的問(wèn)題。網(wǎng)格分割也就是將網(wǎng)格上相互接近并且具有相似曲率的頂點(diǎn)分成一組。網(wǎng)格分割在很多方面具有重要的應(yīng)用。特征提取，模型匹配等。Mangan和Whitaker提出三維網(wǎng)格分割的分水嶺算法。Razdan和Bae擴(kuò)展了此算法，將基于點(diǎn)元(voxel-based)和分水嶺算法相結(jié)合，來(lái)分割三角網(wǎng)格。這兩種方法在分割中都需要計(jì)算整個(gè)曲率，然后在局部曲率最小處建立初始分割。然而，在某些物體中，局部曲率的最小值是很難確定的。因此，在這里提出一個(gè)初始分割的新方法。在該算法中，應(yīng)用基于面片的類(lèi)型信息的網(wǎng)格區(qū)域增長(zhǎng)方法，對(duì)頂點(diǎn)進(jìn)行初始分割。利用高斯曲率和平均曲率對(duì)頂點(diǎn)所在的面片進(jìn)行分類(lèi)。這里利用離散微分幾何計(jì)算高斯曲率和平均曲率。通過(guò)本文提出的新方法來(lái)求得測(cè)地距離。文章結(jié)構(gòu)：第二部分，介紹網(wǎng)格面片的曲率分析和面片分類(lèi)。第三部分，詳述本文的分割算法。第四部分，實(shí)驗(yàn)以及其分割結(jié)果。第五部分，結(jié)論。2面片分析在面片分析中，首先計(jì)算高斯曲率和平均曲率，然后利用它們進(jìn)行面片分類(lèi)。頂點(diǎn)P0的高斯曲率K的計(jì)算公式如下：pA0A為相鄰三角形Ti(i=1,2,3,…)的面積總和。p為常量3。如圖1所示。

“4PlR)只i巳PlP3PqP4Figure1“4PlR)只i巳PlP3PqP4平均曲率定義為沿面法向方向的散度(divergence)，H=Vn。面片的平均曲率的法向量的計(jì)算公式如下［5、6、7］：1-Hn=2(cota+cot卩)(P-P)4AjjjijeN(i)其中，N⑴為頂點(diǎn)Pi的鄰接多邊形的集合。(Pj-Pi)為邊jaj和卩」分別為在N(i)中，邊e所對(duì)的兩個(gè)角。A為N(i)中所有三角型的面積總和。如圖2所示,ij頂點(diǎn)P.的平均曲率的近似表示。iPi.pj+iFigure2.ApproximationofmeancurvatureatvertexR利用高斯曲率和平均曲率對(duì)一個(gè)頂點(diǎn)所在的面片進(jìn)行分類(lèi)。面片的類(lèi)型T

的定義如下，T=1+3(1+sgn(H,8))+(1-sgn(k,e))其中sgn為分段函數(shù)(符號(hào)函數(shù))(atolerancesignumfunction),+1:X>8sgn(X,8)=<0:|x|<8-1:X<83網(wǎng)格分割算法設(shè)物體0的網(wǎng)格結(jié)構(gòu)為M,M由兩部分組成，V和E。V={v|i=1,...,N},ivE={e|i=1,.N},e={v,v},ieipq其中，V為頂點(diǎn)，1<p,q<N且p豐q，V是頂點(diǎn)集，E為連接頂點(diǎn)的邊的iv集合。N,N分別為M中頂點(diǎn)和邊的總數(shù)。ve在該方法中，定義了四種分割類(lèi)型：峰值類(lèi)型(peak-type)，凹值類(lèi)型(pit-type)，最小面片類(lèi)型(minimalsurface-type)，平面類(lèi)型(flat-type)。K>0K=0K<0H<0PeakT=1RidgeT=2SaddleRidgeT=3H=0noneT=4FlatT=5MinimalSurfaceT=6H>0PitT-7ValleyT=8SaddleValleyTable1.Surfacetypesandcurvaturesigns對(duì)峰面、脊面(ridge)、馬鞍面峰值(saddleridge)的相應(yīng)頂點(diǎn)進(jìn)行峰值類(lèi)型的分害0，對(duì)凹面、谷面(valley)、馬鞍凹面(saddlevalley)的相應(yīng)頂點(diǎn)作凹值類(lèi)型的分割，對(duì)最小面片的相應(yīng)頂點(diǎn)作最小面片類(lèi)型的分割，平面類(lèi)型的分割及對(duì)平面片的相應(yīng)頂點(diǎn)進(jìn)行操作。該方法分為三個(gè)階段：分害初始化，計(jì)算分害中心，頂點(diǎn)分害和分害合并。

3.1分割初始化這一步，初步形成上述四種類(lèi)型的分割。對(duì)于模型中其他類(lèi)型的相應(yīng)頂點(diǎn)并不考慮。本文應(yīng)用區(qū)域增長(zhǎng)法來(lái)完成分割初始化。圖3為分割初始化算法。算法中涉及了兩個(gè)函數(shù)，Segment_Initializing和Mesh_Growing。Segment_Initializing用來(lái)建立頂點(diǎn)分割集隊(duì)列元素（無(wú)ID號(hào)），然后迭代的調(diào)用Mesh_Growing函數(shù)對(duì)沒(méi)有分割的頂點(diǎn)進(jìn)行分割。Mesh_Growing函數(shù)自動(dòng)的尋找具有相同面片類(lèi)型的連通頂點(diǎn)。最后初始分割集的生成。每一個(gè)初始分割都包含具有任意一種面片的類(lèi)型的連通頂點(diǎn)。3.2分割中心的計(jì)算設(shè)S為包括N個(gè)頂點(diǎn)的集合（V）的初始分割。令vgV為S的中心頂kvkkckkk點(diǎn)。中心頂點(diǎn)設(shè)為：在集合V中，到所有頂點(diǎn)的平均測(cè)地距離最短。由于平均k距離和距離總和是可以等價(jià)的，中心點(diǎn)又可表示為，min{Yvv1}，vgV，ickikikkIH|表示測(cè)地距離。測(cè)地距離可以利用頂點(diǎn)的最短路徑來(lái)近似的表示。為了解決這個(gè)問(wèn)題，首先建立一個(gè)帶權(quán)矩陣，該矩陣既可以表示V中網(wǎng)格之間的聯(lián)系，也k可以表示相鄰頂點(diǎn)間的歐幾里得距離（即兩點(diǎn)間距離公式求得）。Av,vkikjk令A(yù)為V的NxN的帶權(quán)方陣，AL,v］為方陣AAv,vkikjkkkvkvkv,vgV。A的定義如下，ikjkkkAC,vL<kikjkvvI,if{v,v}gE

ikjkAC,vL<kikjk0,if{v,v}gEikjkg,otherwise其中，||為歐幾里得距離，E為邊的集合。對(duì)A利用Dijkstra算法求所有點(diǎn)對(duì)的最短路徑（測(cè)地距離）。此時(shí)所得到的方針A中元素均為最小值。中心頂點(diǎn)v滿(mǎn)足在矩陣A中縱行距離和以及橫行距kckk離和均最小。v={vImin工A[v,v]}ckckkikjk圖4為求圖的中心頂點(diǎn)的例子。

ABcDEFGHA1)1QQ11OQOQg□]0]]ODOCi■ZCiocCJI)]OO]OOocD11](J]]■DCi1E1oo■DO10■DO■DO1Fg?20]]OD0]]GOCOOO0■□Cl□CiJ〔）1|[]]]]I)ABcD丸口L2]B1<i1]C2L0]ABcD丸口L2]B1<i1]C2L0]D1L10E122]F2211G3J2H2i21￡12121]NEFGH￡]2712227122122li]L21a什221LL20i1Lfi21I*114i1i0IL1014in閱3.3分割在這一步，將未被分割的頂點(diǎn)v分割到距分割中心距離最小的分割集S中。ik由此，我們可以知道頂點(diǎn)分割集［i］中是無(wú)標(biāo)記的。圖5展示了v的分割算法。首i先建立一個(gè)集合D，D中存儲(chǔ)頂點(diǎn)v到它的相應(yīng)類(lèi)型的所有分割中心的歐幾里cci得距離。如果初始分割的類(lèi)型中，沒(méi)有滿(mǎn)足v的類(lèi)型，D為空。如果說(shuō)在網(wǎng)格i中，沒(méi)有凹值類(lèi)型的頂點(diǎn)，但具有低谷值類(lèi)型和馬鞍凹面類(lèi)型的頂點(diǎn)，在這種情況下，不需建立凹值類(lèi)型的初始分割集。但是稍后，需要為低谷值類(lèi)型和馬鞍凹面類(lèi)型的頂點(diǎn)新建立一個(gè)凹值類(lèi)型的分割。第二步，核對(duì)D。如果D為空，則新建立一個(gè)包括v的分割，然后將這個(gè)i分割添加到初始分割集中。如果D非空，我們繼續(xù)執(zhí)行下一步。第三步，選擇C一個(gè)距離域值dist_p,用于下一步中局部網(wǎng)格的生成。dist_p為Dc中第p個(gè)最短距離，p的初始值為1。p每次加一或減一。第四步，建立一個(gè)新的頂點(diǎn)集Vt，集合中的所有頂點(diǎn)到點(diǎn)v的距離都小于tidist_p。第五步，檢查Vt中局部網(wǎng)格的連通性。首先，創(chuàng)建Vt的鄰接矩陣來(lái)表示Vt中頂點(diǎn)的連通性。設(shè)v為集合Vt中的頂點(diǎn)，i=1,…,Nt，Nt為集合Vt中頂tittttt點(diǎn)的總數(shù)。令St為乂的NxN的鄰接矩陣，矩陣中元素的定義如下，TOC\o"1-5"\h\ztttt[1,if{v,v}eEA[v,v]斗ajt

tiyj[0,otherwise在A中以v為根結(jié)點(diǎn)，進(jìn)行深度優(yōu)先搜索。由此，可以得到與v相連通和tii非連通集合。在這兩個(gè)集合中分別可分割成中心頂點(diǎn)、以分割頂點(diǎn)、未分割頂點(diǎn)。然后，從Vt中刪除與v非連通的所有頂點(diǎn)。對(duì)于與v相連通的頂點(diǎn)集，檢查分tii割中心是否與v相連通。如果連通，則執(zhí)行第六步，否則更新p值重復(fù)第三步。i第六步，在頂點(diǎn)集Vt中應(yīng)用Dijkstra算法計(jì)算v與分割中心以及其他頂點(diǎn)的最短ti路徑。然后將v分割到與分割中心距離最小的分割集中。i所有的頂點(diǎn)分割完后，以分割中心為根結(jié)點(diǎn)，利用深度優(yōu)先搜索檢查是否所有的頂點(diǎn)都是連通的。非連通的頂點(diǎn)則從分割集中刪除。可能出現(xiàn)一種情況，某些頂點(diǎn)不屬于任何一個(gè)分割集。因此，我們利用網(wǎng)格增長(zhǎng)算法將相似類(lèi)型的頂點(diǎn)分成一組。若得到的分割集太小（過(guò)分割問(wèn)題），可以將這些小的分割集刪除掉，或者是將它與其鄰近的分割集相合并，但是要滿(mǎn)足合并的兩個(gè)分割集的整個(gè)曲率的差值應(yīng)小于一個(gè)閾值。一個(gè)分割的整個(gè)曲率即為該分割集中所有頂點(diǎn)曲率的平均值。4實(shí)驗(yàn)為了驗(yàn)證該方法的有效性，本文中進(jìn)行了蛋白質(zhì)三維網(wǎng)格模型和人工合成網(wǎng)格模型的分割。這里在蛋白質(zhì)結(jié)構(gòu)的三維體柱結(jié)構(gòu)中應(yīng)用themarchingcubealgorithm，對(duì)每種蛋白質(zhì)三維網(wǎng)格結(jié)構(gòu)的重構(gòu)。實(shí)驗(yàn)中建立了人造的模型，這些模型具有顯著的特征，例如，低谷面、峰面、馬鞍面，試驗(yàn)結(jié)果很容易的看出對(duì)這些特征的分割。本文利用圖形學(xué)建模軟件Maya來(lái)創(chuàng)建人造模型。圖3則標(biāo)明了每個(gè)模型的信息。圖6為蛋白質(zhì)分割的結(jié)果顯示。圖7為人造模型的分割結(jié)果顯示。對(duì)于每個(gè)模型，用不同的顏色表示不同的分割部分。從試驗(yàn)結(jié)果可以看出，采用本算法可以很準(zhǔn)確對(duì)