摘 要

机载LiDAR系统可实现主动对地测量，获取高精度的地形数据数字产品。本文主要研究利用LiDAR数据进行地形数据表达，首先对机载LiDAR系统的组成以及原理进行分析，然后对标准LAS格式的LiDAR数据文件进行解析和读取。接着通过两种不同的Delaunay剖分算法对地形数据进行几何描述以实现对表面几何信息进行精确地存储、计算、表达与分析。但由于这种方法并不能直接揭示标量场表面的拓扑信息和形态结构，且带有大量的数据冗余以及复杂的计算过程，具有较大局限性；因此通过基于离散莫尔斯理论的拓扑结构对地形数据进行了拓扑描述，实现对表面离散数据进行有效简化，为了降低离散的地形数据中噪音和伪特征点的影响，还介绍并推导了一种基于持续值的简化算法。为建立拓扑结构的多层次表达体系打下基础。

关键词：LiDAR系统；Delaunay三角剖分；离散莫尔斯理论；多分辨表达

Abstract

The airborne LiDAR is a comprehensive system for active measurements that can captures high-precision terrain data. This paper first analyzes the composition and the principle of airborne LiDAR system, and then parses and reads the LiDAR data files in the standard LAS format. The terrain data is geometrically described by two different Delaunay splitting algorithms in this paper to accurately store, calculate, express and analyze the surface geometry information. However, it can not directly reveal the topological information and morphological structure of the scalar field surface, and has a lot of data redundancy and complex calculation process, which has certain limitations; Then the topological data based on the discrete Morse theory is used to describe the topographic data, which effectively simplifies the surface discrete data. In order to reduce the influence of noise and pseudo feature points in discrete terrain data, a simplified algorithm has been introduces. To lay the foundation for the simplification of the topology and the multi-level expression.

Key Words：Airborne LiDAR system；Delaunay triangulation；discrete morse theory; Multi-resolution expression

目 录

第1章 绪论 1

1.1 研究背景与研究意义 1

1.2 研究现状 1

1.3 研究方案 2

1.4 设计的主要内容与章节安排 4

第2章 LiDAR地形数据解析 5

2.1 LiDAR系统组成与基本原理 5

2.1.1 LiDAR系统组成 5

2.1.2 激光扫描测距系统原理与激光扫描方式 6

2.1.3 对地定位原理 7

2.2 LAS文件格式 8

2.2.1 公共头 8

2.2.2 变长记录 9

2.2.3 点集记录 9

2.3 LAS数据解析器设计 9

2.3.1 内存映射文件 10

2.3.2 实验设计与实验结果分析 11

第3章 地形数据的Delaunay三角面片构建 12

3.1 基本概念 12

3.2 算法原理 13

3.2.1 随机增量法 13

3.2.2 分治法 15

3.3 实验设计与实验结果分析 17

3.4 地形数据Delaunay三角面片渲染与多视角多比例显示 18

3.4.1 开源工具：Qt与VTK 19

3.4.2 可视化平台设计思路与效果展示 20

第4章 基于离散莫尔斯理论的地形数据表达 24

4.1基本概念 24

4.1.1 莫尔斯理论 24

4.1.2离散莫尔斯理论 26

4.2 IA：对TIN进行编码 27

4.2.1 OFF文件格式 27

4.2.2 IA的编码方式 27

4.3 提取莫尔斯复形 28

4.4 拓扑简化算法 29

4.4.1 i-消除（i-cancellation） 29

4.4.2 简化算法 30

4.5 算法流程以及效果展示 31

第5章 总结与展望 33

5.1 工作总结 33

5.2 工作展望 33

参考文献 34

致 谢 36

第1章 绪论

1.1 研究背景与研究意义

机载LiDAR(Light Detection and Ranging)是一套可实现主动对地测量的综合系统，激光脉冲经地面反射后被机载LiDAR系统接收，可获取高精度数字产品，是一种对传统摄影测量技术在数据获取及自动化处理方面的重要补充。在遥感测图、地形测绘、环境监测、三维城市建模、地球科学等领域具有极为广泛的应用和发展前景。与其他技术相比有：自动化程度高、受天气等外界因素影响小、数据产品生产周期短和数据精度高等优势，是目前最先进的获取地形表面三维空间信息和影像的航空遥感系统^[1]。利用机载LiDAR数据进行地形表面高精度三维重建^[2]，应用不同理论和数据结构进行地形数据的多层次和多分辨率表达，具有重要意义。

地形表面模型的描述形式主要有两种：几何描述和拓扑描述。几何描述方法中的不规则三角网格表达方法，能对地形表面的信息进行存储、计算、表达与分析，是一种占据主导地位的几何描述方式，但这种表达方法并不能表现出标量场表面的拓扑结构和形态信息；拓扑描述通过关键点与关键网格等地形显著特征来描述表面形状，提供了一种紧致的分析、理解和可视化模型表面分析方法^[3]，基于莫尔斯理论提取的关键点符合欧拉公式，构建的关键网络和Morse-Smale复形符合拓扑一致性，能够实现对模型表面进行完全分割并对全局结构进行统一地表达、分析与模型表面尤其是多维模型表面结构的可视化。将离散标量场表面上的三角网格转换为拓扑结构，建立拓扑结构的简化与多层次表达体系，对于离散地形数据的噪音去除、数据压缩和多分辨率表达是一项具现实意义的研究课题^[4]。

1.2 研究现状

不规则三角网（TIN）是在基于莫尔斯理论的拓扑研究常用的数据结构。是一系列不交叉、互不重叠相互连接的三角形，可以精确地描述地形等模型表面。作为TIN的一种特殊形式，Delaunay三角网因符合空外接圆最大最小角等准则，不仅在各个领域应用广泛，而且是基于莫尔斯理论的拓扑研究中最常用的数据结构。俄国数学家为了解决对离散点进行剖分的问题上个世纪四十年代提出了Delaunay三角剖分的基本概念，相应的剖分算法也同时被提出。上世纪八十年代后，由于计算机技术的迅猛发展，大规模计算和图像显示问题得到了有效的解决。三角剖分技术得到了快速发展，三角剖分技术在最近几十年被广泛地应用到多个领域。众多研究者都对Delaunay三角网的构建进行了细致的研究：其中，刘学军^[5]等人对逐点插入算法进行了较为全面的阐述；刘士和^[6]等人利用排序过程替代了传统Bowyer算法中的搜索过程；胡金星^[7]等人在分治算法的基础上，按照逆序对每个格网块采用基于自适应格网划分的分割-归并算法进行三角剖分；而浦浩^[8]和刘少华^[9]等人则在三角形查找和插入点定位方法进行研究，解决了效率问题，张咏^[10]在浦浩等人的算法的基础上构建出了一种鲁棒性较高的定位算法。近年来也出现了一些改进的算法，主要是对传统算法的时间效率的优化，如快速插入算法、合成算法，大量的不同于经典算法基本思想的算法也不断出现：如扫描线、贪心和凸壳等方法。

上世纪七十年代开始，学者们对基于莫尔斯的拓展理论进行了大量的研究并应用于诸多领域，代表性的有三种：基于分段线性的莫尔斯理论^[11]，但是由于其中的每一种关键线或莫尔斯复形构建算法，均是针对某一维度或某一类的复形，不可以根据任意维度进行拓展；基于分水岭的方法，这种方法并不能直接提取Morse-Smale复形，是通过分别提取上升与下降的莫尔斯复形，叠加生成Morse-Smale复形，计算表明，此方法构建的Morse-Smale复形，其结构一般不同于基于高程数值函数构建的Morse-Smale复形；基于离散莫尔斯理论的莫尔斯复形构建过程不仅独立于维数和描述流形的复形，适合拓扑表达在多维度和更高维数模型方面的应用。拓扑简化不但是实现数据压缩与多层次表达的有效方法，并且可以消除模型表面的噪声，解决模型表面过剖分的问题；目前对拓扑简化研究都集中在利用简化操作算子对拓扑结构进行简化与多层次表达^[12]。代表性的有两种：一种是基于MIG（Morse Incidence Graph）的拓扑简化操作算子，另一种为基于Forman梯度的拓扑操作算子，基于MIG的拓扑简化操作算子易于理解与实现，在拓扑简化中应用较多。

1.3 研究方案

本课题实现的基本思路和技术路线可用下图表示：