一种LiDAR点云生成格网DEM的快速算法

李晓红

(山西省基础地理信息院，山西太原030001)

一、引 言

机载激光雷达(light detection and ranging，LiDAR)是一种快速获取高精度地面和地物三维信息的新技术。随着机载激光雷达技术的高速发展，获取的点云数据量越来越大。如何处理海量的点云数据，并从中提取有用的地形信息和地物信息，是当前急需解决的问题。

DEM有多种表现形式，其中TIN和规则格网DEM是两种重要的表达方式。从表达地形信息的角度而言，TIN模型的优点是它能以不同层次的分辨率来描述地形表面。规则格网则具有存储量小，数据结构简单，便于存储、管理及分析计算等优点，因此该数字地形模型得到了广泛的应用。规则格网文件结构相对简单，存储了格网点坐标的最大值、最小值、格网间距、格网点数及高程值。规则格网可以直接从离散采样点据插值得到，也可以通过不规则三角网(TIN)数据内插得到。本文提出一种将LiDAR点云数据构成TIN后快速内插生成规则格网DEM的算法。

二、DEM的生成方法

DEM可以通过摄影测量的方式生成[1]，但是通过先获取离散的高程点，再对均匀分布的格网点高程内插生成DEM的方式更为普遍。

插值可以分为整体插值、分块插值和逐点插值。整体内插是将整个地区采用高次多项式来表示。由于实际地形是复杂变化多样的，单用一个多项式难以表述实际地形，因此DEM内插中一般不采用整体函数内插。局部分块内插是将地形按照一定的规则进行分块，分块的大小可以根据地形的复杂程度来确定。对每一块区域采用单独的函数模型进行拟合内插，不同的分块单元可用不同的内插函数，常用的内插数函数有线性内插、双线性内插、多项式内插、样条函数、多层曲面叠加法等。逐点内插的本质也属于局部内插，但它与局部分块内插也有所不同，它是以内插点为中心，确定一个指定大小的范围，并通过这个范围内的点来选定合适的数学模型去拟合计算内插点的高程。因此，逐点内插的每个内插点都随着点的位置而变化，每个内插的数学模型也不一样，通常逐点内插比局部分块内插具有更高的精度。

综合考虑机载LiDAR点云滤波后数据特点、生成效率和精度，本文采用逐点内插方法生成DEM。差值算法采用距离倒数加权插值法，它的基本原理是：对于每一个插值点，可以设置一个距该点最近的指定半径的范围，落在该范围内的点都被定权参与该点插值的计算，具体的定权方式是与距离成反比，距离插值点越远的点赋予的权值越小，反之距离越近的点赋予的权值越大，如图1所示。利用TIN中Delaunay可以快速确定一个点一定邻域范围内的点，以提高生成DEM效率。

三、算法流程

LiDAR点云生成DEM算法主要分为3个步骤：

1．将原始点云文件转换为点云流文件

原始点云文件不能满足流算法的要求，需要将原始点云文件转换为点云流文件[2]。可根据点云数据内在的空间拓扑信息，将点云数据平均分块、排序插入标识后重新写入点云流文件，以便流处理算法能够应用。

图1 逐点内插法生成DEM

点云流文件的建立主要有3个步骤：

1)遍历原始点云文件，计算外包矩形，将外包矩形划分为2k×2k个分块矩形，构建四叉树。

2)遍历原始点云文件，计算每个分块中包含点云的数目。

3)再次遍历原始点云文件，对点云重新排序，并在每个区块的最后一点插入结束标识。

2．构建不规则三角网

采用改进后的逐点插入法[2]对点云流文件进行Delaunay三角剖分。从点云流文件中读取一个点时，采用逐点插入法进行Delaunay三角剖分，并更新当前的三角网链表(用于存储当前已经生成的三角网)。当从点云文件中读取到结束标识时，表明当前分块的点云已经遍历完毕，将四叉树(将所有分块作为叶节点构建)中的该分块标记为遍历完毕。判断当前三角网链表中的三角形是否处于固定状态(当遍历一个分块后，如果三角形的外包圆没有与未被遍历的分块相交时，认为该三角形处于固定状态)，如果处于固定状态，则输出到三角网文件，释放内存;如果处于活动状态(如果三角形的外包圆与未被遍历的分块相交，则认为三角形处于活动状态)，则继续保留在内存中，等待下一分块遍历完毕后继续判断，直到所有分块读取完毕，完成三角剖分。

3．插值生成规则格网DEM

与传统的DEM插值方法不同，本文所采用的插值方法不是依次寻找规则格网点的领域点进行内插，而是通过遍历三角网文件中的三角形，判断三角形是否包含规则格网点。如果包含规则格网点，则利用该三角形的3个顶点采用距离倒数加权插值法计算格网点高程，并将该格网点的行、列号及高程写入临时文件，释放内存。当三角网文件遍历完毕后，对生成的所有格网点临时文件重新组织排序，写入到统一的DEM格式文件中。这样做的优势是内存中既不保留三角网数据，也不保留生成的格网点数据，大大降低了程序内存的使用量。算法流程如图2所示。

图2 算法流程图

四、试验结果与分析

本文采用了大小为100 MB、包含300万个点的LiDAR数据进行试验，原始点云数据如图3所示。

图3 原始点云数据

首先将原始点云文件转换为点云流文件。从原始点云文件转换为点云流文件共耗时34 s，内存最大使用量2．5MB。

对点云流文件进行Delaunay三角剖分生成TIN，耗时9 s，内存最大使用量2．6MB。生成的TIN如图4所示。由于基于流的算法读入数据进行处理后马上释放内存，只保留很少一部分未固定的数据在内存中，所以内存的使用量非常小。

DEM生成参数进行设置如下：

1)采样间隔设置：设置采样间隔为5．0m。

2)TIN边长阈值：设置为50m(边长过长的三角形内插获得的高程值误差很大)。

3)BIL文件设置：高程所放比例为1．0。

图4 三角剖分后三角网数据

由TIN文件内插生成DEM共耗时3 s，内存最大使用量2．3 MB。DEM的内插同样采用基于流的算法，判断完输入三角形后立即释放内存，显著提高了算法效率，并减少了内存使用量。生成的规则格网DEM如图5所示。

图5 DEM生成渲染图

试验结果表明，采用本文算法生成规则格网DEM的效率非常高，内存使用量远远低于点云文件本身的大小，验证了流算法用于海量点云数据处理的有效性。同时，本文算法生成的DEM准确性非常高，并且能在多种复杂的地形中保持优良的性能。

五、结束语

本文提出了一种LiDAR点云快速生成DEM的算法，首先将海量点云数据分块，对每个分块分别采用改进的增量式Delaunay三角剖分算法构建不规则三角网;然后遍历三角网文件，找到被三角形包含的格网点，采用距离倒数加权插值法计算格网点高程，存入临时文件;最后，将所有临时文件排序生成规则格网DEM。采用基于流的处理算法，实现了点云分块处理，解决了普通计算机处理大数据量点云内存不足的问题。试验表明，该算法在处理大数据量点云时，效率高，内存占用率低，生成规则格网DEM的准确性也非常高，能够应用于实际生产应用中。

[1]MAUNE D F．Digital Elevation Model Technologies and Applications：The DEM Users Manual[M]．[S．l．]：ASPRS，2007．

[2]ISENBURG M，LIU Y，SHEWCHUK J，et al．Streaming Computation of Delaunay Triangulations[C]∥Proceedings of ACM SIGGRAPH 2006．New York：ACM，2006：1049-1056．

[3]ISENBURG M，LINDSTROM P．Streaming Meshes[C]∥Proceedings of IEEE Visualization．Minneapolis：IEEE Computer Society，2005：231-238．

[4]ISENBURGM，LIU Y，SHEWCHUK J，et al．Generating Raster DEM from Mass Points via TIN Streaming[C]∥Proceedings of GIScience’06．Berlin：[s．n．]，2006：186-198．

[5]ISENBURG M，LINDSTROM P，GUMHOLD S，et al．Large Mesh Simplification Using Processing Sequences[C]∥ Proceedings of the 14th IEEE Visualization．Washington DC：[s．n．]，2003．

[6]AGARWAL P K，ARGE L，DANNER A．From LiDAR to Grid DEM：A Scalable Approach[C]∥Proceedings of International Symposium on Spatial Data Handling．[S．l．]：[s．n．]，2006．

[7]CIGNONIP，MONTANIC，ROCCHINIC，et al．External Memory Management and Simplification of Huge Meshes[J]．IEEE Transactions on Visualization and Computer Graphics，2003，9(4)：525-537．

[8]AGARWAL P K，ARGE L，YIK．I/O-Efficient Construction of Constrained Delaunay Triangulations[C]∥Proceedings of the 13th European Symposium on Algorithms．Mallorca， Spain： Springer Verlag， 2005：355-366．