三维网格分割的经典方法

三维网格分割的经典方法三维网格分割的经典方法 摘要：摘要： 本文针对三维网格分割问题，提出一个经典的方法。该方法基于微分几 何和测地距离。在算法中，将面片类型相同的顶点分割在一起。测地距离利用顶 点之间的最短路径表示，这里可以利用一些经典的算法求最短路径，如 Dijkstra 算法。但是当网格的数量很多时，Dijkstra 算法的效率很低。因此，此算法避免 了在整个网格上应用最短路径算法，在局部网格中求最短路径，从而减少了计算 量。 本文在人造物体的三维网格模型以及分子结构中验证了该方法的有效性。 关键字：关键字：几何算法 面片分割测地距离 简介简介 3D 物体的三维网格表示法具有很多的应用。例如，在图像分析中，表示利 用深度图像重建的物体表面。此外， 在复杂物体和场景的建模和可视化中也有广 泛的应用。在网格面片的分析中，网格分割已经成为一个关注的问题。网格分割 也就是将网格上相互接近并且具有相似曲率的顶点分成一组。 网格分割在很多方 面具有重要的应用。特征提取，模型匹配等。 Mangan 和 Whitaker 提出三维网格分割的分水岭算法。 Razdan 和 Bae 扩展了 此算法，将基于点元（voxel-based）和分水岭算法相结合，来分割三角网格。这 两种方法在分割中都需要计算整个曲率，然后在局部曲率最小处建立初始分割。 然而，在某些物体中，局部曲率的最小值是很难确定的。因此，在这里提出一个 初始分割的新方法。 在该算法中， 应用基于面片的类型信息的网格区域增长方法，对顶点进行初 始分割。 利用高斯曲率和平均曲率对顶点所在的面片进行分类。这里利用离散微 分几何计算高斯曲率和平均曲率。通过本文提出的新方法来求得测地距离。 文章结构：第二部分，介绍网格面片的曲率分析和面片分类。第三部分，详 述本文的分割算法。第四部分，实验以及其分割结果。第五部分，结论。 2 2 面片分析面片分析 在面片分析中， 首先计算高斯曲率和平均曲率， 然后利用它们进行面片分类。 顶点 P0的高斯曲率 K 的计算公式如下： K   A  2 i， A A i ，， ii A 为相邻三角形 Ti( i =1，2，3，…)的面积总和。为常量 3。如图1 所示。  平均曲率定义为沿面法向方向的散度（divergence） ，H  n。面片的平均 曲率的法向量的计算公式如下[5、6、7]： 1  Hn  4A jN (i)  (cot j  cot j )(P j  P i ) 其中，N(i)为顶点 Pi 的邻接多边形的集合。( Pj-Pi)为边e ij ， j 和 j 分别为 在 N(i)中， 边e ij 所对的两个角。 A 为 N(i)中所有三角型的面积总和。 如图 2 所示， 顶点 Pi的平均曲率的近似表示。 利用高斯曲率和平均曲率对一个顶点所在的面片进行分类。面片的类型T 的定义如下， T 13(1sgn(H,))(1sgn(k,)) 其中sgn为分段函数（符号函数）(a tolerance signum function)， 1: x   sgn(x,) 0: x  1: x    3 3 网格分割算法网格分割算法 设物体 O 的网格结构为 M，M 由两部分组成，V 和 E。 V {v i |i 1,,N v }, E {e i |i 1,N e },e i {v p ,v q }, 其中，v i 为顶点，1 p,q  N v 且p  q，V 是顶点集，E 为连接顶点的边的 集合。N v ,N e 分别为 M 中顶点和边的总数。 在该方法中，定义了四种分割类型： 1.峰值类型（peak-type） ， 2.凹值类型（pit-type） ， 3.最小面片类型（minimal surface-type） ， 4.平面类型（flat-type） 。 对峰面、脊面(ridge)、马鞍面峰值(saddle ridge)的相应顶点进行峰值类型的 分割，对凹面、谷面(valley)、马鞍凹面(saddle valley)的相应顶点作凹值类型的分 割， 对最小面片的相应顶点作最小面片类型的分割，平面类型的分割及对平面片 的相应顶点进行操作。该方法分为三个阶段： a)分割初始化， b)计算分割中心， c)顶点分割和分割合并。 3.13.1 分割初始化分割初始化 这一步， 初步形成上述四种类型的分割。 对于模型中其他类型的相应顶点并 不考虑。本文应用区域增长法来完成分割初始化。图 3 为分割初始化算法。算法 中涉及了两个函数，Segment_Initializing 和 Mesh_Growing。Segment_Initializing 用来建立顶点分割集队列元素（无ID 号） ，然后迭代的调用Mesh_Growing 函数 对没有分割的顶点进行分割。Mesh_Growing 函数自动的寻找具有相同面片类型 的连通顶点。 最后初始分割集的生成。 每一个初始分割都包含具有任意一种面片 的类型的连通顶点。 3.23.2 分割中心的计算分割中心的计算 设S k 为包括N vk 个顶点的集合（V k ）的初始分割。令v ck V k 为S k 的中心顶 点。中心顶点设为：在集合V k 中，到所有顶点的平均测地距离最短。由于平均 距离和距离总和是可以等价的，中心点又可表示为，min{ i v ck v ik }，v ik V k ， 表示测地距离。 测地距离可以利用顶点的最短路径来近似的表示。为了解决这 个问题，首先建立一个带权矩阵，该矩阵既可以表示V k 中网格之间的联系，也 可以表示相邻顶点间的欧几里得距离（即两点间距离公式求得） 。 令A k 为V k 的N vk  N vk 的带权方阵，A k  v ik ,v jk 为方阵 A k 的元素，其中 v ik ,v jk V k 。A k 的定义如下， A k v ik ,v jk  v ik v jk ,if{v ik ,v jk }E  0,if{v ik ,v jk }E  ,otherwise  其中，||为欧几里得距离，E 为边的集合。 对A k 利用 Dijkstra 算法求所有点对的最短路径（测地距离） 。此时所得到的 方针A k 中元素均为最小值。 中心顶点v ck 满足在矩阵A k 中纵行距离和以及横行距 离和均最小。 v ck {v ck | minA k [v ik ,v jk ]} 图 4 为求图的中心顶点的例子。 3.33.3 分割分割 在这一步，将未被分割的顶点v i 分割到距分割中心距离最小的分割集S k 中。 由此，我们可以知道顶点分割集[i]中是无标记的。图5 展示了v i 的分割算法。首 先建立一个集合 Dc，Dc中存储顶点v i 到它的相应类型的所有分割中心的欧几里 得距离。如果初始分割的类型中，没有满足v i 的类型，Dc为空。如果说在网格 中，没有凹值类型的顶点，但具有低谷值类型和马鞍凹面类型的顶点，在这种情 况下，不需建立凹值类型的初始分割集。但是稍后，需要为低谷值类型和马鞍凹 面