随着三维采集设备的不断更新迭代及图形生成技术的发展,大量的三维几何模型被构造出来.传统的曲面造型已远远不能满足需要,以网格、点云为代表的离散表示方法得以迅速发展,新的学科分支——数字几何处理也应运而生.三维模型的分割,是将三维模型分解成不同的部分,这些部分往往包含了一定的语义信息,符合人类视觉认知.三维模型分割在数字几何处理中居于重要地位,为三维模型的后续处理,如检索、建模、变形等提供了先验知识.在三维模型的离散表示中,网格既包含模型的位置信息也包含了一定的拓扑结构信息.因此网格分割问题也引发了众多研究者的兴趣.经过几十年的发展,网格分割经历了从手工分割到自动分割、从基于几何特征到基于语义特征、从按经验生成特征到数据驱动生成特征、从单分割到协同分割的发展历程.从方法上讲,网格分割大致分为三种:基于空间几何特征的方法、基于图表示的方法和数据驱动的方法.基于空间几何特征的方法是直接在三维网格上利用几何特征进行分割.这些方法的优点是所使用的分割方法简单、明了,但是通常分割效果不是很理想,容易出现过分割、边界不光滑等问题,总是需要增加后续处理过程.例如合并相邻小区域,边界优化等.基于图表示的分割方法目前常用的是谱方法.谱方法将网格表示成图,然后将图节点映射到谱空间中,在谱空间中进行分解或聚类,映射回网格后得到网格的分割结果.数据驱动的方法通过学习人工标注的分割标签来训练分类器得到分割结果.由于学习了人类的意思表达,这些方法通常能得到较好的分割结果,但是它们需要大量的人工输入和复杂的训练过程.本文主要研究基于图表示的三维网格分割方法.相比于直接在三维网格上进行分割,谱方法能更好地确定分割区域或分割边界.而同数据驱动方法相比,谱方法则不需要那么多的人工标注.谱方法普遍存在的问题是难以确定谱表示的维数,也就是使用多少特征向量.而且由于谱映射是对于l2模的极小化,得到的特征向量都是光滑的,这使得对于点所属部分以及不同部分之间分割边界的确定面临困难.本文提出了两种不同的谱分割方法,分别解决上述的两个问题.论文首先提出一种基于Fiedler残差的网格分割方法.常用的谱方法通常面临的问题是选择多少特征向量对节点进行特征映射,为了解决这个问题,本方法只选用一个特征向量:Fiedler向量.Fiedler向量的变化能反映图的基本结构,我们定义了 Fiedler残差的概念并通过Fiedler残差来寻找图连接稀疏的区域,这些区域就是包含分割边界的区域.相比于其他递归分割中每次只能分出两个部件的方法,本方法在一次递归中可以找到尽可能多的分割边界,不降低分割质量的前提下大大提高了运行效率,减少了运行时间.之后论文提出一种基于半监督的全变差图聚类的网格分割方法.针对上一方法仍然需要递归分割的问题,我们使用多个特征向量对图节点进行多维谱表示,并用特征间隙来确定特征向量的个数.然后通过与无权图Laplace矩阵的Fiedler向量的比较,来确定一些网格点的标签,并将其作为后续半监督多类全变差图聚类的指导点,指导确定其他点的标签.由于特征向量是由最小化l2模得到的,都很光滑,直接用于聚类不利于确定节点的聚类标签.全变差图聚类通过最小化隶属度函数的梯度的l1模,得到变化尖锐的隶属度函数,更便于确定节点所属的聚类,得到光滑的分割边界.协同分割是指分割并识别出同一类物体的不同三维模型的有相似语义或功能的部分.协同分割结合了多个三维模型,比单独模型的分割具有更丰富的信息,也更具挑战性.目前存在的协同分割方法都是通过图结构来表示多个三维模型之间的联系,这种联系通过对齐或特征相似性得到.然后利用图因子分解的方法得到图节点的向量表示,聚类得到分割结果.由于图因子分解只能保持图节点的一阶近似度,所以对图的结构要求比较严格,进而对几何特征的选择依赖性很强.这些方法大多依赖于基于对齐或朝向的特征,而对齐或朝向的计算是相对复杂的.论文提出一种基于深度游走的三维网格协同分割方法.深度游走是一种基于随机游走的图表示方法.通过对随机游走生成概率的优化,深度游走得到的图节点表示保持了节点的社群特性,也就是高阶的近似度,对于稀疏的图结构也有很好的表达.本方法通过多角度稀疏图重建得到一个稀疏的图结构,然后引进深度游走的图表示方法,得到的图节点表示能反映节点更大范围的邻域相似性,使协同分割不再依赖于对齐或朝向和复杂的图结构也能得到很好的分割效果.上述方法能得到与数据驱动的方法相当的效果,甚至在有些模型上的效果更好,而且在计算效率上要大大高于数据驱动的方法.深度游走的图表示方法很容易使用到深度学习方法上,这为我们下一步在深度学习分割方法上的研究打下了良好的基础.论文将三种层层递进的图表示方法引入三维网格的分割问题.从图节点的一维谱表示到多维谱表示再到基于随机游走的表示,这些表示方法对图节点近似度的保持逐步提高,引入分割问题后从不同的方面解决了存在的一些问题,改善了分割结果,提高了运算效率.