三维网格分割基础知识

三维网格分割基础知识三维网格分割及其相关基本概念特征描述符：用来描述图形几何特征的符号。如高斯曲率（GC）、外直径特征函数（SDF）、平均测地距离（AGD）、保角因子（CF）、图形文脉（SC），其中GC、AGD和CF描述三维网格的外部特征，而SDF和SC描述三维网格的内部特征。三维网格模型分割：简称网格分割，是指根据一定的几何及拓扑特征，将封闭的网格多面体依据其表面几何、拓扑特征、分解为一组数目有限、各自具有简单形状意义的、且各自连通的子网格片。三维网格模型分割应用领域：点云重建网格、网格简化、层次细节模型、几何压缩与传输、交互编辑、纹理映射、网格细分、几何变形、动画对应关系建立、局部区域参数化以及逆向工程、索引检索等。刚性：物体外部形状不随着移动等外界因素发生变化（如平移、旋转）非刚性：物体会在外界因素的影响下形状发生变化（如缩放）鲁棒性（robustness）：即稳健性，表征控制系统对特性或参数摄动的不敏感性。第二页，共13页。三维网格分割及其相关基本概念分割的一般过程第三页，共13页。表面测地线距离：是指三维模型的两个顶点在模型表面的最短距离，它不仅可以有效的克服三维模型噪声的干扰，而且与三维模型的坐标系方向无关。但不易计算，常用特征描述之间的欧氏距离代替。欧几里德距离：两个n维向量a(x11,x12,…,x1n)与

b(x21,x22,…,x2n)间的欧氏距离：

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

该准则不仅能够衡量类内样本间的相似程度,也能衡量类间样本间的相异程度。三维网格分割及其相关基本概念第五页，共13页。K-way分解：将网格S分解k个组成部分k个组成部分其中Binary分解：k-way分解中k=2，即分解成两部分三维网格分割及其相关基本概念第六页，共13页。三维网格分割经典聚类算法分割的本质是聚类：求解优化问题所有可能的近似求解方案,按照算法原理可分为区域生长算法、分层聚类、代聚类法、谱分析法、骨架抽取法等。区域生长法：选定不同区域的种子元素（如顶点、三角曲面片信息等），然后在种子区域的周围根据一定的生长规则进行区域生长，直到覆盖整个区域为止。优点：思想简单，实现速度快；缺点：易产生过分割。均值漂移(MS)：通过迭代搜索特征空间中样本点最密集的区域，搜索点沿着样本点密度增加的方向漂移到局部密度最大点。优点：该方法完全依靠特征空间中的样本点进行分析，无需先验知识，收敛速度快。第七页，共13页。算法步骤：(1)网格模型预处理；(2)计算网格每对面片的最短距离权值(3)为每一面片分配其属于每一个分割片的可能性值；(4)计算出一个模糊分解，使其分为三个部分（包括模糊部分);模糊聚类分割算法：2003年，Katz等人提出了模糊聚类的层次分解算法，将复杂模型进行由粗到精，得到分割片层次树，一层一层的处理，最终分割成边界线平滑、有意义的若干个较为简单的部分。层次树的根表示整个网络模型S。在每个节点，首先确定需要进一步分割为更精细分割片的数目，然后执行个K-way分割。优点：该算法可以得到有意义的部分子模型，且没有出现锯齿现象，算法也不会产生过分分割效果。三维网格分割经典聚类算法第八页，共13页。三维网格分割组合分割—子空间聚类子空间聚类的三维图形的组合分割：对于过分割图形，利用分组直接对原始补丁块进行分割，并且获得相应的对应关系。算法核心：获得亲和矩阵。子空间聚类：将高维数据集聚类成多个低维线性子空间，并且找到找到低维子空间相应的每个聚类点。具体实现步骤：第九页，共13页。三维网格分割组合分割—子空间聚类单特征组合分割：求解亲和矩阵可转化为如下优化问题：多特征组合分割：求解亲和矩阵可转化为如下优化问题：第十页，共13页。三维网格分割组合分割-亲和力聚合谱聚类亲和力聚合谱聚类（AASC）：寻求描述网格过分割面片多特征融合的亲和矩阵，利用谱聚类算法对所有补丁块进行一致分割。(b)SDFspace(c)GDspace(d)AGDspace(e)concatenated(f)Ourfused(g)Weights算法步骤利用标准切割将网格分割成补丁利用高斯核函数构造亲和矩阵获得所有补丁一致分割第十一页，共13页。三维网格分割组合分割-亲和力聚合谱聚类谱聚类划分数据到m个互不相交的类，寻找索引向量,满足亲和力聚合谱聚类实现过程：