自底向上的三维形状分割

发布时间：2017-04-11 12:11

  本文关键词：自底向上的三维形状分割，，由笔耕文化传播整理发布。

【摘要】：三维形状分割一直以来都是计算机图形学领域的基础性研究课题。一方面,三维形状分割可以被应用在参数化、纹理映射、重新网格化以及网格简化等纯几何分析和处理方面。当前,越来越多的研究者将研究重心从纯几何分析和处理转化到高层次的结构化分析和处理上,而三维形状的语义分割正是高层次形状分析与处理的基础。近些年来,多个三维形状的协同分割已经成为形状分析尤其是形状分割领域中的一个重要课题。这里,多个三维形状的协同分割指的是将一组属于同一类的三维形状一致分割成具有相互对应关系的语义部件。相对于单个三维形状,一组属于同一类的三维形状可以提供更多的信息,因而对一组三维形状进行协同分割所得到的结果将要优于对每个三维形状单独进行分割的结果。而这其中,最关键的问题是如何从一组三维形状中获取合适的信息用于协同分割。另一方面,如何将一个复杂的形状分解为一系列简单的形状是也一个重要的几何问题。其中主要的原因是,相对于复杂的形状,更容易对简单的形状进行计算和操作。本文要介绍的是金字塔分割问题,即希望将给定形状分割为最少的金字塔形的块。我们说一个形状是金字塔形的,如果它的边界上有一个平坦的底而且剩余的边界部分可以看成是这个底上的一个高度函数。三维形状的金字塔分割问题的研究价值主要体现在其在工业界的有效应用。对于一般的三维形状,用熔融沉积式三维打印机打印需要额外的支持材料。而支撑材料所带来的弊端主要是有两个方面：首先是材料的浪费；其次是这些支撑材料将很难从打印完成的模型中去除,特别是那种有镂空设计的三维形状。然而,金字塔形状是自稳定的,即在打印的时候不需要任何支撑材料,所以它是熔融沉积式三维打印机能处理的理想输入。另外,金字塔形状都是可以铸模的,沿反方向将金字塔形状从模具中取出将不会对模型造成任何损坏。本文围绕不同应用背景下的三维形状分割问题展开研究,主要研究成果与贡献包括：1.本文提出了一个全新的自底向上的算法,可以自动将属于同一个类的一组模型分割成带有语义的部件并同时建立这些部件之间的对应关系。从对网格表面进行的过分割开始,我们算法通过将这些过分割曲面片进行聚类得到了期望的语义分割以及对应关系。其中,核心思想是通过在曲面片上定义多种特征使得相似曲面片以较大概率落在特征空间的同一个子空间内,从而将曲面片的聚类问题转化为子空间聚类问题。实验结果显示,本算法具有很强的灵活性,对于不同的模型集都能得到较为理想的协同分割结果。2.在定义多个特征空间并对其上的信息进行融合时,传统的方法是将不同特征串连合并成一个特征之后直接进行聚类。我们则是通过在优化问题中加入一个惩罚函数来保证不同特征空间内的相似矩阵的稀疏相容性。通过求解这一优化问题,我们既可以找到相似性较大的曲面片对,又可以确定出对这一相似性判定起决定性因素的特征。由于在进行三维形状进行分析和处理时往往需要综合考虑其上多种特征,所以这种对多种特征进行融合的非传统方式,可应用在除形状分割以外的其他形状分析与处理的工作上。3.本文提出了一个全新的自底向上的算法,来解决三维形状的近似金字塔分割问题。精确金字塔分割问题是NP-难的,这里我们将这个问题转化为一个较为被大家熟知的精确覆盖问题。给定一个三维形状,我们首先在其内部采样,然后通过对这些采样点进行逐步聚类得到一系列不同程度的基本元,并进一步合并得到一组备选金字塔块。最终,我们将在这一组备选金字塔块上进行精确覆盖问题的求解从而得到最后的分割结果。实验结果表明,无论输入形状是二维的还是三维的,实心的还是中空的,我们算法都可以处理。我们在大量的数据集上对算法进行了测试与评价,证实了算法的有效性和普适性。4.类金字塔性是一个相对较新且没有被充分研究过的形状特性,除了三维打印,还和铸模等应用有紧密关系。通过本文对这一问题的探索,希望能够吸引更多研究者对这一特性进行更深层次的挖掘。再者,将形状分割问题转化为精确覆盖问题的关键是要构造出满足某一特定属性的形状内部的块。虽然本文所研究的是类金字塔性,但是这一问题转化的思路可以用于求解带有其他特性要求的形状分割问题。
【关键词】：形状分割 协同分割 语义分析 对应关系 三维打印 类金字塔性 自底向上算法 子空间聚类 精确覆盖
【学位授予单位】：浙江大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP391.41
【目录】：

• 致谢5-6
• 摘要6-8
• Abstract8-20
• 第一章 绪论20-28
• 1.1 研究背景20-23
• 1.2 相关工作23-25
• 1.2.1 单个模型的语义分割23-24
• 1.2.2 模型间的对应关系24-25
• 1.3 本文工作25-28
• 第二章 预备知识28-34
• 2.1 子空间聚类问题28-30
• 2.1.1 问题描述28
• 2.1.2 算法求解28-30
• 2.2 精确覆盖问题30-34
• 2.2.1 问题描述30-31
• 2.2.2 与形状分割的联系31-32
• 2.2.3 算法求解32-34
• 第三章 基于子空间聚类的三维形状集协同分割34-54
• 3.1 引言34-36
• 3.2 相关工作36-38
• 3.2.1 三维形状集的协同分割36-38
• 3.2.2 子空间聚类问题38
• 3.3 算法概述38-39
• 3.3.1 过分割38
• 3.3.2 特征描述子38-39
• 3.3.3 基于子空间聚类的协同分割39
• 3.4 分割算法39-44
• 3.4.1 单个特征空间上的协同分割40-41
• 3.4.2 多个特征空间上的协同分割41-44
• 3.5 实验结果44-53
• 3.5.1 测试数据集44-45
• 3.5.2 协同分割结果45-46
• 3.5.3 结果评价46-51
• 3.5.4 算法局限性51-53
• 3.5.5 算法性能53
• 3.6 本章小结53-54
• 第四章 基于精确覆盖的三维形状的近似金字塔分割54-88
• 4.1 引言54-57
• 4.2 相关工作57-61
• 4.2.1 凸性和凸分割58
• 4.2.2 单调多边形和单调折线58-59
• 4.2.3 可铸模性59-60
• 4.2.4 立体图和地形分割60
• 4.2.5 三维打印60-61
• 4.3 算法概述61-62
• 4.4 分割算法62-74
• 4.4.1 单元构建63-67
• 4.4.2 模块构建67-69
• 4.4.3 备选金字塔块构建69-71
• 4.4.4 近似金字塔分割71-73
• 4.4.5 扩展到三维73-74
• 4.5 实验结果74-84
• 4.5.1 参数设置74-75
• 4.5.2 分割结果75-78
• 4.5.3 数据统计78-79
• 4.5.4 分割块拼接79-81
• 4.5.5 二分金字塔形81
• 4.5.6 与贪婪算法比较81-82
• 4.5.7 与用户分割结果比较82-84
• 4.6 本章小结84-88
• 第五章 总结与展望88-92
• 5.1 工作总结88-89
• 5.2 究展望89-92
• 参考文献92-104
• 简历104-106
• 攻读博士期间已完成和发表的文章106

【共引文献】

中国期刊全文数据库 前10条

1 秦洋;王立宏;武栓虎;宋宜斌;;基于拉普拉斯矩阵的DNA序列集相似性分析[J];北京交通大学学报;2009年06期

2 孙轩;杨必胜;李清泉;;基于体元分析的三维建筑物模型结构化分割方法[J];测绘学报;2011年05期

3 徐天顺;;谱聚类算法研究[J];电脑知识与技术;2012年16期

4 陈姿羽;黄靖;李伟鹏;;一种改进的自适应谱聚类图像分割算法[J];南方医科大学学报;2012年05期

5 孔万增;孙志海;杨灿;戴国骏;孙昌思核;;基于本征间隙与正交特征向量的自动谱聚类[J];电子学报;2010年08期

6 钱鹏江;王士同;邓赵红;徐华;;基于最小包含球的大数据集快速谱聚类算法[J];电子学报;2010年09期

7 程学旗;沈华伟;;复杂网络的社区结构[J];复杂系统与复杂性科学;2011年01期

8 顾耀林;张丽娜;;基于连通性转换的三维多面体快速变形[J];工程图学学报;2007年02期

9 彭艳斌;艾解清;;基于谱聚类波段选择的高光谱图像分类[J];光电工程;2012年02期

10 卢志茂;徐森;刘远超;顾国昌;;使用“分裂-合并"策略改进文本聚类集成算法的研究[J];高技术通讯;2010年07期

中国重要会议论文全文数据库 前4条

1 ;A New Fast Metamorphosis Method of 3D Polyhedral Models[A];第十一届中国体视学与图像分析学术会议论文集[C];2006年

2 ;Fast mesh segmentation by approximated spherical patches[A];2009中国控制与决策会议论文集（2）[C];2009年

3 王小磊;张瑾;许洪波;;基于交互增强原理的多文档自动文摘算法[A];第四届全国学生计算语言学研讨会会议论文集[C];2008年

4 杨飞;周凡;王若梅;刘俪;罗笑南;;一种快速有效地基于区域增长的网格分割算法[A];第六届全国几何设计与计算学术会议论文集[C];2013年

中国博士学位论文全文数据库 前10条

1 徐森;文本聚类集成关键技术研究[D];哈尔滨工程大学;2010年

2 宋军;水交换模型的理论方法及应用研究[D];中国海洋大学;2010年

3 莫X;基于隐式函数的曲面重构方法及其应用[D];华中科技大学;2010年

4 陈禄;基于显式表达的高效网格形变技术[D];浙江大学;2011年

5 张冬梅;离散曲线曲面的形状优化算法研究[D];浙江大学;2010年

6 舒振宇;网格曲面的分割算法及其应用[D];浙江大学;2010年

7 陈伟;基于时序文本挖掘的新闻内容理解与推荐技术研究[D];浙江大学;2010年

8 钱鹏江;大规模数据集聚类方法研究及应用[D];江南大学;2011年

9 吕绍高;统计学习中回归与正则化谱聚类算法的研究[D];中国科学技术大学;2011年

10 赵亮;三维地震数据断层检测与建模方法研究[D];南京理工大学;2010年

中国硕士学位论文全文数据库 前10条

1 李静伟;基于共享近邻的自适应谱聚类算法[D];大连理工大学;2010年

2 张洋;视觉显著特征引导的网格有意义分割[D];大连理工大学;2010年

3 朱登奎;基于骨架图的曲面四边形剖分算法[D];大连理工大学;2010年

4 张琪;三维网格模型层次分割及骨架提取[D];辽宁师范大学;2010年

5 潘炯波;三维网格模型的骨架提取[D];辽宁师范大学;2010年

6 孙玉侠;数据挖掘中的谱聚类算法研究[D];中国海洋大学;2010年

7 肖东;基于聚类的CAD网格模型分割算法研究[D];浙江大学;2011年

8 刘X;三维形状画刷分割工具的研究[D];浙江大学;2010年

9 刘登志;人体角色的自动绑定与卡通运动[D];浙江大学;2011年

10 温程;并行聚类算法在MapReduce上的实现[D];浙江大学;2011年

  本文关键词：自底向上的三维形状分割，由笔耕文化传播整理发布。

本文编号：299069