三维网格分割的经典方法

三维网格分割的经典方法摘要：本文针对三维网格分割问题，提出一个经典的方法。该方法基于微分几何和测地距离。在算法中，将面片类型相同的顶点分割在一起。测地距离利用顶点之间的最短路径表示，这里可以利用一些经典的算法求最短路径，如Dijkstra算法。但是当网格的数量很多时，Dijkstra算法的效率很低。因此，此算法避免了在整个网格上应用最短路径算法，在局部网格中求最短路径，从而减少了计算量。本文在人造物体的三维网格模型以及分子结构中验证了该方法的有效性。关键字：几何算法面片分割测地距离简介3D物体的三维网格表示法具有很多的应用。例如，在图像分析中，表示利用深度图像重建的物体表面。此外，在复杂物体和场景的建模和可视化中也有广泛的应用。在网格面片的分析中，网格分割已经成为一个关注的问题。网格分割也就是将网格上相互接近并且具有相似曲率的顶点分成一组。网格分割在很多方面具有重要的应用。特征提取，模型匹配等。Mangan和Whitaker提出三维网格分割的分水岭算法。Razdan和Bae扩展了此算法，将基于点元(voxel-based)和分水岭算法相结合，来分割三角网格。这两种方法在分割中都需要计算整个曲率，然后在局部曲率最小处建立初始分割。然而，在某些物体中，局部曲率的最小值是很难确定的。因此，在这里提出一个初始分割的新方法。在该算法中，应用基于面片的类型信息的网格区域增长方法，对顶点进行初始分割。利用高斯曲率和平均曲率对顶点所在的面片进行分类。这里利用离散微分几何计算高斯曲率和平均曲率。通过本文提出的新方法来求得测地距离。文章结构：第二部分，介绍网格面片的曲率分析和面片分类。第三部分，详述本文的分割算法。第四部分，实验以及其分割结果。第五部分，结论。2面片分析在面片分析中，首先计算高斯曲率和平均曲率，然后利用它们进行面片分类。顶点P0的高斯曲率K的计算公式如下：pA0A为相邻三角形Ti(i=1,2,3,…)的面积总和。p为常量3。如图1所示。

“4PlR)只i巳PlP3PqP4Figure1“4PlR)只i巳PlP3PqP4平均曲率定义为沿面法向方向的散度(divergence)，H=Vn。面片的平均曲率的法向量的计算公式如下［5、6、7］：1-Hn=2(cota+cot卩)(P-P)4AjjjijeN(i)其中，N⑴为顶点Pi的邻接多边形的集合。(Pj-Pi)为边jaj和卩」分别为在N(i)中，边e所对的两个角。A为N(i)中所有三角型的面积总和。如图2所示,ij顶点P.的平均曲率的近似表示。iPi.pj+iFigure2.ApproximationofmeancurvatureatvertexR利用高斯曲率和平均曲率对一个顶点所在的面片进行分类。面片的类型T

的定义如下，T=1+3(1+sgn(H,8))+(1-sgn(k,e))其中sgn为分段函数(符号函数)(atolerancesignumfunction),+1:X>8sgn(X,8)=<0:|x|<8-1:X<83网格分割算法设物体0的网格结构为M,M由两部分组成，V和E。V={v|i=1,...,N},ivE={e|i=1,.N},e={v,v},ieipq其中，V为顶点，1<p,q<N且p丰q，V是顶点集，E为连接顶点的边的iv集合。N,N分别为M中顶点和边的总数。ve在该方法中，定义了四种分割类型：峰值类型(peak-type)，凹值类型(pit-type)，最小面片类型(minimalsurface-type)，平面类型(flat-type)。K>0K=0K<0H<0PeakT=1RidgeT=2SaddleRidgeT=3H=0noneT=4FlatT=5MinimalSurfaceT=6H>0PitT-7ValleyT=8SaddleValleyTable1.Surfacetypesandcurvaturesigns对峰面、脊面(ridge)、马鞍面峰值(saddleridge)的相应顶点进行峰值类型的分害0，对凹面、谷面(valley)、马鞍凹面(saddlevalley)的相应顶点作凹值类型的分割，对最小面片的相应顶点作最小面片类型的分割，平面类型的分割及对平面片的相应顶点进行操作。该方法分为三个阶段：分害初始化，计算分害中心，顶点分害和分害合并。

3.1分割初始化这一步，初步形成上述四种类型的分割。对于模型中其他类型的相应顶点并不考虑。本文应用区域增长法来完成分割初始化。图3为分割初始化算法。算法中涉及了两个函数，Segment_Initializing和Mesh_Growing。Segment_Initializing用来建立顶点分割集队列元素（无ID号），然后迭代的调用Mesh_Growing函数对没有分割的顶点进行分割。Mesh_Growing函数自动的寻找具有相同面片类型的连通顶点。最后初始分割集的生成。每一个初始分割都包含具有任意一种面片的类型的连通顶点。3.2分割中心的计算设S为包括N个顶点的集合（V）的初始分割。令vgV为S的中心顶kvkkckkk点。中心顶点设为：在集合V中，到所有顶点的平均测地距离最短。由于平均k距离和距离总和是可以等价的，中心点又可表示为，min{Yvv1}，vgV，ickikikkIH|表示测地距离。测地距离可以利用顶点的最短路径来近似的表示。为了解决这个问题，首先建立一个带权矩阵，该矩阵既可以表示V中网格之间的联系，也k可以表示相邻顶点间的欧几里得距离（即两点间距离公式求得）。Av,vkikjk令A为V的NxN的带权方阵，AL,v］为方阵AAv,vkikjkkkvkvkv,vgV。A的定义如下，ikjkkkAC,vL<kikjkvvI,if{v,v}gE

ikjkAC,vL<kikjk0,if{v,v}gEikjkg,otherwise其中，||为欧几里得距离，E为边的集合。对A利用Dijkstra算法求所有点对的最短路径（测地距离）。此时所得到的方针A中元素均为最小值。中心顶点v满足在矩阵A中纵行距离和以及横行距kckk离和均最小。v={vImin工A[v,v]}ckckkikjk图4为求图的中心顶点的例子。

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分割在这一步，将未被分割的顶点v分割到距分割中心距离最小的分割集S中。ik由此，我们可以知道顶点分割集［i］中是无标记的。图5展示了v的分割算法。首i先建立一个集合D，D中存储顶点v到它的相应类型的所有分割中心的欧几里cci得距离。如果初始分割的类型中，没有满足v的类型，D为空。如果说在网格i中，没有凹值类型的顶点，但具有低谷值类型和马鞍凹面类型的顶点，在这种情况下，不需建立凹值类型的初始分割集。但是稍后，需要为低谷值类型和马鞍凹面类型的顶点新建立一个凹值类型的分割。第二步，核对D。如果D为空，则新建立一个包括v的分割，然后将这个i分割添加到初始分割集中。如果D非空，我们继续执行下一步。第三步，选择C一个距离域值dist_p,用于下一步中局部网格的生成。dist_p为Dc中第p个最短距离，p的初始值为1。p每次加一或减一。第四步，建立一个新的顶点集Vt，集合中的所有顶点到点v的距离都小于tidist_p。第五步，检查Vt中局部网格的连通性。首先，创建Vt的邻接矩阵来表示Vt中顶点的连通性。设v为集合Vt中的顶点，i=1,…,Nt，Nt为集合Vt中顶tittttt点的总数。令St为乂的NxN的邻接矩阵，矩阵中元素的定义如下，TOC\o"1-5"\h\ztttt[1,if{v,v}eEA[v,v]斗ajt

tiyj[0,otherwise在A中以v为根结点，进行深度优先搜索。由此，可以得到与v相连通和tii非连通集合。在这两个集合中分别可分割成中心顶点、以分割顶点、未分割顶点。然后，从Vt中删除与v非连通的所有顶点。对于与v相连通的顶点集，检查分tii割中心是否与v相连通。如果连通，则执行第六步，否则更新p值重复第三步。i第六步，在顶点集Vt中应用Dijkstra算法计算v与分割中心以及其他顶点的最短ti路径。然后将v分割到与分割中心距离最小的分割集中。i所有的顶点分割完后，以分割中心为根结点，利用深度优先搜索检查是否所有的顶点都是连通的。非连通的顶点则从分割集中删除。可能出现一种情况，某些顶点不属于任何一个分割集。因此，我们利用网格增长算法将相似类型的顶点分成一组。若得到的分割集太小（过分割问题），可以将这些小的分割集删除掉，或者是将它与其邻近的分割集相合并，但是要满足合并的两个分割集的整个曲率的差值应小于一个阈值。一个分割的整个曲率即为该分割集中所有顶点曲率的平均值。4实验为了验证该方法的有效性，本文中进行了蛋白质三维网格模型和人工合成网格模型的分割。这里在蛋白质结构的三维体柱结构中应用themarchingcubealgorithm，对每种蛋白质三维网格结构的重构。实验中建立了人造的模型，这些模型具有显著的特征，例如，低谷面、峰面、马鞍面，试验结果很容易的看出对这些特征的分割。本文利用图形学建模软件Maya来创建人造模型。图3则标明了每个模型的信息。图6为蛋白质分割的结果显示。图7为人造模型的分割结果显示。对于每个模型，用不同的颜色表示不同的分割部分。从试验结果可以看出，采用本算法可以很准确对