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

张春亢

贵州大学矿业学院，贵阳 550025

LiDAR等新技术能快速获取海量模型表面离散数据，面对这些数据，仅通过提高计算机性能已不能满足实际需求，选择合适的数据表达方式，对其进行简洁、有效描述是亟待解决的问题。传统的几何方法，如三角网格等能对空间表面模型的几何信息进行精确表达且便于计算与分析，但其数据量大、冗余多、计算复杂。基于Morse理论建立的拓扑表达，能用少量的数据实现对模型表面的描述，并揭示模型表面的拓扑形态。本文基于Morse理论，对表面模型拓扑特征的数据结构基础、拓扑特征提取与简化的理论与方法等进行了深入探讨。主要内容如下：

(1) 详述了经典Morse理论及关键点、关键线、Morse-Smale复形、拓扑简化等相关概念，引出了针对离散数据模型的经典Morse理论的两种离散化形式：离散Morse理论与分段线性Morse理论，并对分段线性Morse理论及其在地学中的应用进行了较为详细的阐述。

(2) 三角网格是实现拓扑特征提取的数据结构基础，针对拓扑特征提取与简化耗时长，而分块处理可以有效提高效率的问题，研究了海量三角网格的非耦合剖分方法。首先利用动态三角网生长算法构建分割墙(DeWall)，从点云上切割特定大小与形状的独立数据块，避免分治算法的深度递归；然后用分治算法对切块剖分，并给出了切块边界错误三角形删除算法；迭代上述过程完成三角网子网剖分，并依据非耦合区域分解模式完成子网合并；同时引入流计算的思想，进一步提高算法的空间性能。试验表明：①算法获得了优异空间性能，且算法的整体时间复杂度约为O(nlog(δ))，接近线性；②算法构建的各子三角网之间具有非耦合性质，为分块进行拓扑特征处理提供了算法支撑。

(3) 研究了小尺度地形拓扑特征的精确提取与简化算法。针对基于Morse理论提取的小尺度地形拓扑特征含有大量“伪特征”，并形成对地形的“过剖分”问题。首先通过定义特征点指数(FPI)等一系列概念，模拟特征点周围区域的地表形态，建立了特征点重要性度量指标。并以此为基础，提出了地表特征的精确提取与多层次表达算法。新算法可以有效剔除“伪特征”，实现小尺度复杂地形拓扑特征精确提取，且具有良好的抗噪性与稳健性，优于现有的Persistence法与自然法则法。

(4) 研究推导了三维表面模型拓扑特征提取与简化方法。基于Morse理论的特征提取算法在由二维扩展到三维表面模型时，提取的极大点与下降Morse复形为模型表面的有效特征，而极小点与上升Morse复形为无实际意义的错误特征，这不但降低了特征提取效率，且易导致简化误差。为此，推导了三维表面模型拓扑特征的提取方法，实现了针对三维表面模型的单复形拓扑模型提取。基于separatrix persistence度量方法与MS复形简化算法，推导了单复形拓扑模型的简化方法。试验表明：单复形模型能有效识别三维模型表面的拓扑特征，避免错误特征的提取，提高了效率；单复形简化方法可以有效去除“伪特征”，并且在简化过程中保持了复形的完整性与一致性。

(5) 设计开发了“基于Morse理论的三角网格拓扑特征提取及简化”试验系统，将论文研究的有关算法与模型集成为原型系统。通过典型数据对试验系统及相关算法与模型的可行性、正确性和有效性进行了验证。