三维网格分割--基础知识.ppt

1、,三维网格模型分割及其相关概念 三维网格模型分割经典聚类方法 三维网格模型组合分割,王茂正,三维网格分割及其相关基本概念,特征描述符：用来描述图形几何特征的符号。如高斯曲率（GC）、外直径特征函数（SDF）、平均测地距离（AGD）、保角因子（CF）、图形文脉（SC），其中GC、AGD和CF描述三维网格的外部特征，而SDF和SC描述三维网格的内部特征。,三维网格模型分割：简称网格分割，是指根据一定的几何及拓扑特征，将封闭的网格多面体依据其表面几何、拓扑特征、分解为一组数目有限、各自具有简单形状意义的、且各自连通的子网格片。,三维网格模型分割应用领域：点云重建网格、网格简化、层次细节模型、几何压缩

2、与传输、交互编辑、纹理映射、网格细分、几何变形、动画对应关系建立、局部区域参数化以及逆向工程、索引检索等。,刚性：物体外部形状不随着移动等外界因素发生变化（如平移、旋转） 非刚性：物体会在外界因素的影响下形状发生变化（如缩放） 鲁棒性（robustness）：即稳健性，表征控制系统对特性或参数摄动的不敏感性。,三维网格分割及其相关基本概念,分割的一般过程,表面测地线距离：是指三维模型的两个顶点在模型表面的最短距离，它不仅可以有效的克服三维模型噪声的干扰，而且与三维模型的坐标系方向无关。但不易计算，常用特征描述之间的欧氏距离代替。,欧几里德距离：两个n维向量a(x11,x12,x1n)与b(x2

3、1,x22,x2n)间的欧氏距离： 也可以用表示成向量运算的形式：,泥土移动距离（EMD）：用于求解某个特征空间两个多维分布之间相似性。给定两个直方图分布，一个分布t可以看做一堆泥土的集合，另一个分布g可以看做很多洞的集合，不同的土与洞之间的地面距离不同，从而EMD距离用来计算用土填满洞的最小工作量。,三维网格分割及其相关基本概念,基于图论的最优划分准则:就是使划分成的两个子图内部相似度最大, 子图之间的相似度最小。,N-cut：规范割集准则：,Shi 和 Malik 在2 00 0年根据谱图理论建立了 2 - w ay 划分的规范割目标函数( N cut ),该准则不仅能够衡量类内样本间的相

4、似程度, 也能衡量类间样本间 的相异程度。,三维网格分割及其相关基本概念,K-way 分解：将网格S 分解k 个组成部分k个组成部分 其中,Binary 分解：k-way 分解中 k=2，即分解成两部分,三维网格分割及其相关基本概念,三维网格分割经典聚类算法,分割的本质是聚类：求解优化问题所有可能的近似求解方案,按照算法原理可分为区域生长算法、分层聚类、代聚类法、谱分析法、骨架抽取法等。,区域生长法：选定不同区域的种子元素（如顶点、三角曲面片信息等），然后在种子区域的周围根据一定的生长规则进行区域生长，直到覆盖整个区域为止。优点：思想简单，实现速度快；缺点：易产生过分割。,均值漂移(MS)：通

5、过迭代搜索特征空间中样本点最密集的区域，搜索点沿着样本点密度增加的方向漂移到局部密度最大点。优点：该方法完全依靠特征空间中的样本点进行分析，无需先验知识，收敛速度快。,算法步骤： (1) 网格模型预处理； (2) 计算网格每对面片的最短距离权值 (3) 为每一面片分配其属于每一个分割片的可能性值； (4) 计算出一个模糊分解，使其分为三个部分（包括模糊部分);,模糊聚类分割算法：2003 年，Katz 等人提出了模糊聚类的层次分解算法，将复杂模型进行由粗到精，得到分割片层次树，一层一层的处理，最终分割成边界线平滑、有意义的若干个较为简单的部分。层次树的根表示整个网络模型 S。在每个节点，首先确

6、定需要进一步分割为更精细分割片的数目，然后执行个K-way 分割。优点：该算法可以得到有意义的部分子模型，且没有出现锯齿现象，算法也不会产生过分分割效果。,三维网格分割经典聚类算法,三维网格分割组合分割子空间聚类,子空间聚类的三维图形的组合分割：对于过分割图形，利用分组直接对原始补丁块进行分割，并且获得相应的对应关系。算法核心：获得亲和矩阵。,子空间聚类：将高维数据集聚类成多个低维线性子空间，并且找到找到低维子空间相应的每个聚类点。,具体实现步骤：,三维网格分割组合分割子空间聚类,单特征组合分割：求解亲和矩阵可转化为如下优化问题：,多特征组合分割：求解亲和矩阵可转化为如下优化问题：,三维网格分割组合分割-亲和力聚合谱聚类,亲和力聚合谱聚类（AASC）：寻求描述网格过分割面片多特征融合的亲和矩阵，利用谱聚类算法对所有补丁块进行一致分割。,算法步骤,利用标准切割将网格分割成补丁,利用高斯核函数构造亲和