三维网格分割中聚类分析技术综述

三维网格分割是计算机图形学的一个重要的研究方向,近年来不断涌现出各种新的分割技术.主要关注基于聚类分析的三维网格分割技术,介绍了三维网格分割的2种常见类型,并对分割技术所转化的数学问题进行阐述,总结了一系列常用的网格属性.依据算法类型将现有算法划分为5类,所基于的分割技术分别有区域生长、多源区域生长、层次聚类、迭代聚类以及谱聚类.针对不同的分割目标和所利用的网格属性,对各分类下的分割算法进行对比讨论;同时给出4种角度的评估准则,以展示不同应用场景下各类分割算法的优缺点,并指出了三维网格分割的发展趋势和应用方向.     

三维网格的边界强度分割算法

提出一种新的基于网格边界几何信息的快速分割算法,首先按照原始网格模型面片的拓扑关系建立对偶图,并根据网格面片的几何信息设定顶点权和边权;使用k-way 多级分割方法在对偶图上进行快速分割,得到预分割区域以及各分割区域的初始边界;然后定义分割片的特征边界和边界强度函数,用以表示各预分割区域边界上的形变模型;通过最小化形变模型的能量函数,推动初始边界向特征边界运动,最终得到符合最小值法则的有意义的子网格.实验结果表明,该算法快速有效,适用于各种局部边缘特点较显著的三角网格模型.     

一种基于交互式分割的部分模型检索方法

如何在三维模型库中,从相似或不同种类的模型中得到模型的局部匹配,实现部分模型的检索,已经成为一个具有挑战性的研究工作.目前,基于特征统计的方法虽实现较好的检索结果,但是不满足局部匹配,因而无法实现部分模型的检索;基于骨架提取和Reeb图的方法,虽满足局部的匹配,但是对三维模型的结构要求比较严格.为此,提出基于交互式分割的部分模型检索方法.首先采用交互式的分割方法,得到满足用户需求的部分模型,然后对于部分模型,利用形状分布方法提取部分模型的形状特征,利用PDF-L1标准得到部分模型的匹配度,从而实现部分模型的检索.实验结果表明,可得到较好的检索结果.     

三维网格的Mean Shift并行分割算法

为克服Mean Shift算法复杂度高、速度慢的缺点,提出了一种改进的三维网格模型Mean Shift并行分割算法.该方法基于Mean Shift的基本思想和GPU的高性能并行计算能力,基于离散测地距离的局部极值提取三维网格模型的显著特征点,自显著特征点开始并发执行Mean Shift算法,实现了有意义的分割.与同类算法相比,该算法提高计算运行效率、改善了分割效果.     

三角网格分割综述

三角网格分割是数字几何处理的重要问题之一,从分割驱动信号、分割类型、分割策略、算法复杂度、适用范围等方面对典型的网格分割算法如迭代聚类法、区域生长算法、分水岭算法、层次分解或合并法、谱分析法、骨架方法等进行了详细的比较和论述。并结合实际工作,对网格分割的研究趋势进行了展望。     

基于区域离散曲率的三维网格分水岭分割

针对离散曲率估计对噪声敏感且特征值计算量大的特点提出了基于区域离散曲率的三维网格分水岭分割算法。寻找三维模型显著特征点;对三维模型进行预分割,确定分割带;在分割带区域上计算离散曲度极值点,利用测地距离和曲度极值点对三维模型进行分水岭分割。算法在分割前无需进行网格去噪,实验结果证明,对主体分支明显的模型具有较高的分割边缘准确度和较快的分割速度。     

一种三维网格模型的数字水印算法

研究数字媒体版权保护问题,由于三维网格模型数据量大,传统数字水印算法不能很好解决水印的不可见性和抗攻击性之间矛盾,安全性不高。为了更好保护数字媒体版权,提出一种新的三维网格模型的数字水印算法。采用奇异值分解将三维水印信号分解,降低数据复杂度,然后采用零水印算法进行水印嵌入和检测。仿真结果表明,网络模型算法嵌入的水印信息不仅具有很好的不可见性,而且能够很好抵抗模型的平移、剪切、旋转、等比例缩放以及噪声攻击,算法执行效率较高,能够满足实时性要求高的数字媒体版权验证。     

勾画式交互的网格模型分割

提出一种基于区域增长的交互三维网格模型分割方法。在区域增长的基础上,首先由用户利用基于勾画的交互方式选定部分顶点作为目标和背景,其余顶点作为未知区域,利用区域增长的方法自动生成目标的边界,从而完成模型的分割。此方法中边界顶点分割结果的好坏直接影响到了最终的分割结果,因此,在利用区域增长方法形成边界时,将既与目标相邻又与背景相邻的顶点标记为特殊点,在其余未知部分分割完成之后,重新对特殊点进行一次区域增长算法。此时由于大部分顶点的状态已经确定,获得的边界将更为准确。实验表明分割结果有了很大程度的改进。     

基于网格Laplace的三维几何模型分割

模型分割是模型分析的重要方法和手段.针对已有网格分割算法对姿态敏感和计算速度慢的问题,提出了一种基于网格Laplace和k-means聚类的三维几何模型分割算法.通过网格Laplace将三维模型从空域嵌入到谱空间中进行分析,得到了模型的归一化形式,克服了姿态变化对分割结果的影响,并极大地减少了计算时间,获得了视觉上有意义的分割结果.实验结果表明,本算法能快速有效地实现网格模型的正确分割,并对模型姿态的变化有较好的鲁棒性.     

一种基于蚁群优化的网格分割方法

三维网格的理解是许多几何处理中亟待解决的重要问题,而网格分割是其中的关键步骤。为此,利用蚁群优化算法进行网格分割。将待分割网格的每个网格视为一个蚂蚁,通过蚁群优化迭代对每个网格的标签进行更新。随着蚁群优化的迭代,种子点的标签向外扩散,标签更新通过蚁群优化的更新机制进行并满足分割要求,直至达到迭代标准。蚁群优化完成后进行区域合并,将较小的区域合并成较大区域,最终完成分割。在Princeton网格数据集上的实验结果表明,与图分割方法相比,该方法能获得更高的正确率。     

基于Delaunay四面体剖分的网格分割算法

为了构建有意义曲面分片,提出一种基于Delaunay四面体剖分的网格分割算法.首先根据Delaunay四面体剖分得到多边形网格内部的四面体,求出每个面上反映网格内部信息的Delaunay体距离;然后对Delaunay体距离进行平滑处理,再对网格上面的Delaunay体距离进行聚类,用高斯混合模型对Delaunay体距离作柱状图的拟合,利用期望最大化算法来快速求得拟合结果;最后结合图切分技术,同时考虑聚类的结果、分割区域的边界平滑和视觉认知中的最小规则,得到最终的网格分割结果.实验结果表明,采用文中算法可以有效地实现有意义的网格分割.     

一种基于扩散几何的非刚体三维形状分割方法

三维形状分割是三维形状分析中的一个重要问题.为了使分割结果能适应非刚体丰富的姿态变化,提出一种基于扩散几何的三维网格分割方法.该方法采用波核特征的局部极值点作为非刚体网格模型表面的显著特征点;进而将显著特征点作为初始聚类中心,采用K-均值聚类算法来获得分割结果.实验结果表明,文中方法不仅对处于不同姿态的非刚体三维形状具有良好的分割一致性,而且对噪声、孔洞等具有较好的鲁棒性.     

遗传算法在三维网格模型数字水印中的应用

在数字水印的研究中,为保护版权信息特性,提高精确性和抗噪能力,提出了一种遗传算法的三维网格模型变换域盲水印算法。先将三维模型转化为二维数值矩阵,然后进行二维分块DCT变换生成系数矩阵,利用遗传算法寻找满足适应度函数的最佳嵌入系数,适应度函数使嵌入水印后的模型变形最小。并要嵌入矩阵的位置信息及相应的DCT系数,进行仿真。结果表明,算法可抵抗平移、旋转、各向一致缩放攻击、顶点重排序攻击、噪声攻击。证明对简化方法具有一定的鲁棒性,为设计提供参考。     

综合曲率约束的在线网格模型分割方法研究

针对现有三角网格模型块分割方法普遍存在计算复杂度高,无法体现工程意义,综合效果不理想,不满足Web环境下高效快速分割等问题,提出一种面向Web环境的简单高效的三角网格模型分割方法。根据高斯曲率和平均曲率特性划分出网格模型的凹区域,在凹区域中依据最小负曲率阈值提取凹特征区域,结合区域中心特征线提取方法以及边界线闭合和优化算法构造出闭合分割线,通过分割线将三角网格模型分割成有意义的分块。依托开源数字几何处理软件MeshLabJS,运用WebGL的几何处理及图形渲染功能,在普林斯顿标准数据集和COSEG形状数据集上进行算法测试,验证所提方法能够在Web环境下快速、高效、有意义地分割三维模型。     

基于K-means聚类方法的三维点云模型分割

提出采用K-means聚类分析方法对三维点云模型进行分割。论文指出,对于分布呈现类内团聚状三维点云模型,K均值聚类分割可以得到较好的结果。与三维网格模型的K均值聚类分割、点云模型的谱系聚类分割的实验结果比较证实了这一点。     

基于DFT的鲁棒三维网格模型数字水印算法

论文提出了一种基于离散傅立叶变换(DFT)的鲁棒三维网格数字水印嵌入算法,该算法首先将模型中心到顶点的长度进行DFT变换,然后通过修改DFT系数的模来嵌入水印。算法以全局特征作为嵌入对象,并且将1位水印信息分布到整个模型之中。实验结果表明该算法能够抵抗网格简化、加噪声、剪切等类型攻击以及它们的混合攻击,具有很好的鲁棒性。     

三维网格模型增量式聚类检索

针对大规模三维网格模型库中的形状检索问题,提出了基于增量式聚类的三维形状描述和检索方法。首先根据三维模型的曲率分布直方图提取特征点得到特征向量;然后根据特征向量描述建立模型库的关键词词典;在特征 匹配阶段基于增量聚类方法判断目标模型的特征向量是否属于某一个关键词,并根据增量聚类的结果更新检索关键词词典;最后匹配特征向量检索模型库中与目标模型形状相同和相近的三维网格模型。相关实验结果证明了该方法快速有效,具有较高的准确性。     

三维网格压缩方法综述

针对三维网格大数据量与三维图形引擎处理能力及网络带宽限制之间的矛盾,三维网格压缩编码技术提供了一系列解决方法。本文从静态压缩和递进网格两个角度分类,以拓扑信息驱动和几何信息驱动为两条主线,归纳比较了国内外近十年来三维网格压缩的各种方法,并给出其未采发展趋势。