三角网格的最短路径计算及对其分割

三角网格的最短路径计算及对其分割摘要对于人或者动物的模型来说，从视觉认知上将他们分解为头、身体和四肢，然后对其进行变形、拼接等操作。本文主要是应用k-means算法，从一个物体上分割出一个有意义的子部分。近年来，在计算机图形学中，将多边形网格分解为子网。本文提出了一种新的层次网格分割算法，在模型的深凹陷区域进行有意义分割。该算法还避免了过度分割和锯齿边界。关键词：k-means算法；层次网；分网ComputingandsegmentingTriangular

grid'sshortestpathAbstractForhumanoranimalmodels,thepeopleoften,decomposedintotheirhead,bodyandlimbsbytheirthevisualcognition，.thenbedeformed,splicingandotheroperations.Thispaperistoapplyk-meansalgorithm,separatingameaningfulSub-sectionfromanobject.Inrecentyears,incomputergraphics,polygonalmeshesaredecomposedintosub-meshes.Inthispaperweproposeanovelhierarchicalmeshdecompositionalgorithm.Ouralgorithmcomputesadecompositionintothemeaningfulcomponentsofagivenmesh,whichgenerallyreferstosegmentationatregionsofdeepconcavities.Thealgorithmalsoavoidsover-segmentationandjaggyboundariesbetweenthecomponents.Keywords:k-meansalgorithm;meshdecomposition;sub-meshes基于文献［1］的研究，图形分割的一个重要任务是计算三维网格模型的最短路径。本文应用单源Dijkstra算法和Floyd算法［2］。Dijkstra算法是从某个原点到其余各顶点的单源最短路径算法。主要特点是以起始点为中心向外层层扩展，知道扩展到终点为止。Floyd算法是求每对顶点之间的最短路径问题。基于图的带权邻接矩阵A=［a(i,j)］nXn,递归地进行n次更新，即由矩阵D(0)=A，按Dijkstra算法计算，构造出矩阵D(l)；又用同样地方法由D(1)构造出(2)；；最后又用同样的方法由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录任意两点间的最短路径。相关工作聚类分析指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。聚类与分类的不同在于，聚类所要求划分的类是未知的，分类是将数据分类到不同的类或者簇这样的一个过程，所以同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性。在数据分类中，常用的分类方法有多元统计中的系统聚类法、模糊聚类分析等。在模糊聚类分析中，首先要计算模糊相似矩阵，不同的模糊相似矩阵会产生不同的分类结果，即使采用相同的模糊相似矩阵，不同的阈值也会产生不同的分类结果。如何确定这些分类的有效性，便成为模糊聚类和模糊识别［3］研究中的一个重要问题。K-means算法属于聚类方法中的一种划分方法，该算法具有较好的可伸缩性和很高的效率,适合处理大文档集k-means算法接受输入量k；然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。k-means算法,首先从n个数据对象任意选择k个对象作为初始聚类中心，而对于所剩下其它对象，则根据它们与这些聚类中心的相似度(距离)，分别将它们分配给与其最相似的(聚类中心所代表的)聚类；然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值)。K-means特点：类内距离小，类间距离大。算法描述根据文献［1］，确定k值可满足下列三个条件之一：(a)使各类之间的距离小于一个给定的阈值；(b)使各类面片之间角度的最大值和最小值之差不大于1,以至于每个面片有相当稳定的曲率不配分解；(c)使各类平均距离的比率不超过一个给定的阈值。

面片之间的角距离是相邻面片f和f之间法向量的夹角；公式如下ijAng_Dist(a)二q(1—cosa)ijij当耳二1，凸凹两面角是没有差别的。由于凹面角是一个较好的边界参照，我们就计算凸面的反面。设定当0＜耳＜1时计算的是凸面角，当耳二1时计算的是凹面角。本文先计算面片间的测地距离[4]Geod(ff)和面片间的角度距离Ang_Dist(a)，再根i,jij据这两方面因素综合考虑，对图形进行分割。把相邻面片f和f之间的权值定义如下：ijWeight(dual(f),dual(f))=6-Geod(f'f+(1—8).Ang-如(駕)ijavg(Geod)avg(Ang_Dist)8g[0,1]实验本文根据k-means算法中的返回的信息，计算各聚类到各聚类中心点的距离和，比较各k值间的差值，寻找满足它们的差值首次幅度最大的k为本文所以的k值。为了验证本文方法，以具体模型(如图1)为例。先对其求最短路径。应用Dijikstra算法计算结果如图2；图1图2应用Floyd算法计算最短路径结果如图3；

图3再进行k-means聚类分割，用下面函数确定k值G(k)二min(Dist(REP,REP))i<kki分割结果如图4图4结论用Floyd求最短路径的时候，需要对每对顶点都求最短路径，这样在图形标出时会比较乱，所以将图形显示改为文本显示。本文图形的分割已基本达到要求，实验结果表明，对图形的分割还不够完善，需要进一步改进，应达到把头和尾也分割的效果。参考文献Hierarchica