基于Morse理论的三角网格特征提取及简化研究

发布时间：2018-04-17 11:05

本文选题：Morse理论 + 三角网格　；参考：《中国矿业大学(北京)》2016年博士论文

【摘要】：现代空间数据采集技术,特别是激光雷达技术(Light Detection and Ranging,LiDAR)能够在短时间内获取海量的空间模型表面离散数据。但是,当我们面对越来越大的数据量,仅寄希望于提高计算机的运算速度、增大存储空间已经不能满足实际需求。选择合适的数据表达方式,在最大程度保存信息的前提下对其进行简洁、有效描述是目前亟待解决的问题之一。目前,在空间表面模型的表达方式中,传统的几何方法,如规则格网、等值线,特别是三角网格仍然占据主导位置,其能对空间表面模型的几何信息进行精确表达且便于计算与分析,但其数据量大、冗余数据多、计算复杂,且不能揭示模型表面的拓扑形态信息。作为一种紧致而简洁的模型表面拓扑表达方式,基于Morse理论拓扑表达能用少量特征点、特征线实现对空间模型表面突出特征的描述,且这些特征点符合欧拉公式,特征线或Morse(-Smale)复形能实现对模型表面的完全分割。因此,在三角网格上构建表面拓扑结构,实现模型几何表达向拓扑表达的转换,在计算机图形学、地学、空间信息科学,影像医学等领域得到越来越广泛的关注。但是由于数据的不确定性及算法本身存在的缺陷,基于Morse理论提取的拓扑特征往往含有大量的“伪特征”,并形成对模型表面的“过剖分”问题。另外,受限于特征提取的精度,目前基于Morse理论的拓扑分析仍然停留在定性分析阶段,其严重制约了拓扑表达在现实中的应用。因此,研究如何精确地识别出地形网格中的主要特征并建立多层次表达体系,对于数据的简化、交互式分析与可视化表达等,以及拓扑表达的定量计算至关重要。为此,本文致力于基于Morse理论的三角网格拓扑特征精确提取与简化研究,主要对海量三角网格构建、小尺度复杂地形以及三维表面模型拓扑特征提取及简化等所涉及的相关算法与关键技术进行了较深入的探讨。主要工作与成果如下:1)基础理论、现有研究成果及现存问题的梳理与总结介绍了本研究的理论依据经典Morse理论及关键点、关键线、Morse(-Smale)复形、持续值(Persistence)、拓扑简化等相关概念及它们之间的关系。根据现实应用需求,引出了经典Morse理论的两种离散化形式:离散Morse理论与分段线性Morse理论,其中对本研究利用的分段线性Morse理论进行了较为详细的阐述。在此基础上,深入分析了基于Morse理论的拓扑特征提取及简化研究进展,主要包括:特征点提取、关键线或Morse(-Smale)复形提取、拓扑简化。并总结归纳出目前研究成果存在的主要问题。最后,引出本文研究的主要内容及技术路线。2)提出了一种海量三角网格切块剖分算法三角网格是实现拓扑提取与表达的基础。为解决海量LiDAR点云三角网构建时时间与空间性能的矛盾问题,并针对基于三角网格分块构建表面拓扑形态模型的需要,提出一种三角网切块剖分算法。首先,利用基于格网的动态三角网生长算法构建分割墙(dewall),从点云上切割特定大小与形状的独立数据块,避免分治算法的深度递归与内存溢出;然后,运用分治算法对切块剖分,并给出了切块边界错误三角形删除算法;迭代上述过程完成三角网子网剖分,并依据非耦合区域分解模式的性质完成子网合并,同时引入流计算的思想,以进一步提高算法的空间性能。对算法的时间与空间性能进行了理论分析并进行了系统的实验验证,实验与分析表明:①运用切块策略避免了分治算法的深度递归与内存溢出,同时通过模拟流计算,算法获得了处理较大数据所需的优异空间性能。②算法不但保证了各切块剖分时具有分治算法的时间性能,并且算法的整体时间复杂度接近为o(nlog(δ)),优于非线性的分治算法,适合千万级以上lidar点云的处理。③算法最终构建的三角网为各子网简单相加的和,并且本算法中各子三角网之间的非耦合性质,为lidar点云分块进行拓扑特征的提取、表达与分析提供了数据结构支撑。3)设计与实现了小尺度地形拓扑特征的简化与精确提取算法morse理论是基于光滑流形提出的,目前基于morse理论的拓扑表达仍然停留在定性分析上,且使用的数据源多为大尺度或较为光滑的空间模型表面数据。lidar点云为小尺度地表形态信息的提取、表达提供了精确的数据源,并使拓扑表达由定性分析扩展到定量计算成为可能。但点云的高密度性与地形的分形特征,导致基于morse理论提取的特征点中含有大量的“伪特征”,并形成对地表的“过剖分”问题。为此,针对现有特征点重要性度量方法的片面性,基于三角形网格结构,首先通过定义特征点指数(fpi)等一系列概念,模拟特征点周围区域的地表形态,建立特征点重要性度量指标。并以此为基础,提出了地表重要特征点的精确提取、拓扑结构简化与多层次表达算法。fpi不仅能准确度量小尺度复杂地表特征点的重要性,并且特征点数量在fpi值各段分布比较均匀,便于建立拓扑特征的多层次表达体系。基于fpi的特征提取与简化算法在简化效果方面优于现有的“持续值(persistence)”法与自然法则法,其不仅可以有效剔除“伪特征点”,实现小尺度复杂地形的特征精确提取与多层次表达,且算法具有良好的重复性、抗噪性与鲁棒性。并且特征点的提取精度小于2倍点间距,能够满足一定精度要求的定量计算。基于提出的一系列特征点重要性评价指标,并提出特征点尺度的概念,通过计算不同三角网格上特征点之间的相似系数,实现了基于三角网格的特征点识别与同名点匹配。4)扩展了一种三维表面模型拓扑特征提取与简化新方法基于分段线性Morse函数的特征提取算法在由二维地表扩展到三维表面模型时,三角网格顶点的显著度度量指标由高程值变为曲率值、法向量改变值等顶点属性。基于这些属性提取的极大点、上升线与下降Morse复形为模型表面的显著特征,而对应的极小点、下降线与上升Morse复形均为无实际意义的错误特征。这不但降低了拓扑特征提取的时间效率,且无实际意义的错误特征将导致拓扑简化误差甚至错误。为此,本文首先提出一种基于三角网顶点法向量的特征点显著度度量方法,发展了以法向量变化量为点显著度度量指标的三维表面模型特征提取算法,该算法仅提取有现实意义的三维模型表面拓扑特征。然后基于“关键线持续值(Separatrix Persistence)”度量方法与对偶性Morse-Smale复形拓扑简化算法,推导了仅有下降Morse复形的单复形拓扑模型的拓扑简化算法。新的提取算法能有效识别与提取三维模型表面的拓扑特征,避免没有现实意义的拓扑特征的提取,大幅提高拓扑特征提取的效率。扩展的简化算法不但可以解决三维模型表面拓扑划分的“过剖分”问题,并且可以保持下降Morse复形的拓扑完整性,实现对三维模型表面的完全划分及拓扑特征的多层次表达。5)设计并开发了“基于Morse理论的三角网格拓扑特征提取及简化”实验原型系统采用C++语言,在Visual Studio2008集成环境下,选用开源的图形开发库OSG和微软基础类库MFC作为框架,将本文研究的有关算法与关键技术集成为原型系统。实验系统的主要功能包括:本研究所提出的各种算法和相关技术的实现、验证与分析;特征数量、误差分析等统计计算;离散点云的导入和拓扑模型的输出等。同时对实验系统中算法采用的关键数据结构作了较为详细的介绍。通过典型数据对实验系统及其有关算法的可行性、合理性、正确性和有效性进行了实验验证与分析。
[Abstract]:......
【学位授予单位】：中国矿业大学(北京)
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP391.41

【参考文献】