基于三角形驱动的机载LiDAR数据栅格化算法

张 春 亢，赵 学 胜，钟 新 科

(1.中国矿业大学(北京)地球科学与测绘工程学院，北京 100083； 2．中国科学院地理科学与资源研究所，北京 100101)



基于三角形驱动的机载LiDAR数据栅格化算法

张 春 亢1，赵 学 胜1，钟 新 科2

(1.中国矿业大学(北京)地球科学与测绘工程学院，北京 100083； 2．中国科学院地理科学与资源研究所，北京 100101)

针对基于TIN的机载LiDAR点云数据插值为GRID过程中，大量TIN数据I/O操作导致的栅格化效率下降问题，提出了基于三角形驱动的点云栅格化流式算法:以基于直线正负区判别原理的TIN向GRID转换新算法为基础，通过遍历三角形模拟流计算实现三角形生成、三角形插值为GRID以及内存释放，有效避免了TIN数据的I/O操作，并可以提高内存利用率。试验表明：流式算法显著提高了点云栅格化效率，为海量点云的栅格化及并行计算提供了一种算法支撑。

机载LiDAR点云；栅格化；I/O操作；流计算；三角形驱动

作为一种高精度、高密度、快速获取地面三维信息的有效手段，机载LiDAR已成为生成数字地面模型(DTM)的重要工具[1]。而作为DTM的两种主要表达方式，规则格网(GRID)相对于不规则三角网(TIN)具有数据结构简单、存储量小、分析与计算方便等优点[2]。将LiDAR点云栅格化，不但便于其管理与表达，也为其滤波与应用创造了条件，但在栅格化大量LiDAR点云的过程中，因数据的I/O操作时间超过CPU计算时间而成为制约转换效率的瓶颈[3-5]。在实现较大数据量的点云直接插值为GRID时，只需将点云以一定的数据结构进行划分重组，即可提高I/O操作的效率，实现点云向GRID的高效转换[4，5]。与直接插值方法相比，利用点云生成TIN，然后将TIN内插为GRID具有更高的精度和效率[2]。传统TIN插值为GRID通常采用对生成的TIN数据进行分块并建立索引，然后逐个判断待插值格网节点在哪个三角形中，进而计算格网点属性值的插值策略[6]。因此，在实现基于TIN的点云数据插值为GRID时，需首先将点云剖分为TIN并进行存储，然后完成TIN向GRID转换。这种基于格网节点驱动的分步转换方法虽然易于理解与实现，但转换过程中涉及中间数据TIN的I/O操作。离散点的数量m(m≥3)与其所构建的三角形数量n满足条件[7]：m-2≤n≤2m-5。实验发现，当m较大时，n逼近2m，并且TIN复杂的数据结构决定其数据量要远大于离散点本身的数据量，所以点云数据比较大时，对计算机内存也有较高要求。通过上述分析，本文引入流计算的思想，以TIN向GRID转换新算法为基础，对基于TIN的点云栅格化流程进行了改造，以避免TIN数据的I/O操作，提高栅格化效率及内存利用率。

1 基于三角形驱动的流式算法

1.1 算法原理

流式算法的基本思想为：利用逆向思维，依据直线正负区判别原理，提出一种新的TIN向GRID转换算法，使构成TIN的每个三角形能够独立地实现其内格网节点判断及其属性值的计算;同时引入流计算的思想，实现三角形的构建、三角形插值为GRID和内存的释放在三角形驱动下，以流水线的形式进行组合，从而避免TIN数据的I/O操作并提高内存的利用率。流式算法步骤如下：1)对于点云数据，利用Delaunay三角网构建算法生成一个三角形T;2)利用本文提出的基于直线正负区判别原理的TIN向GRID转换算法,对三角形T所包含的格网节点进行判断与插值;3)存储完成插值的格网节点属性值，释放三角形T和格网节点所占用的内存资源;4)重复步骤1-3，直至TIN构建完成，实现所有三角形包含的格网节点的判断与插值;5)对未包含在任何三角形内的格网节点赋予一个特定属性值，算法结束。

在流式算法的实现过程中，Delaunay三角网构建算法需要选用三角网生长算法或分治算法，以便在TIN构建过程中不间断地释放符合Delaunay三角网准则、不需再优化的三角形，从而形成数据流。本文详细阐述基于直线正负区判别原理的TIN向GRID转换算法。

1.2 基于直线正负区判别原理的TIN向GRID转换算法

存在一直线，假定直线两边分别为该直线的正区与负区，有如下公式：

(1)

其中：A=(y2-y1)/(x2-x1)，B=(x2y1-x1y2)/(x2-x1)，(x1,y1)、(x2,y2)为直线上两点坐标。对于任意一点P(x,y)，可利用下式判断该点处于直线的正区或负区：

(2)

由式(1)、式(2)可知：平面内两点的表达式同号时，则两点位于直线段的同侧；表达式异号时，两点位于直线段的异侧。

依据上述直线正负区判别原理，TIN向GRID转换算法描述如下：1)如图1，对于构成TIN的一个三角形ABC，根据其顶点坐标，计算其顶点在x与y方向上坐标的最大(小)值xmax(xmin)、ymax(ymin)；2)根据xmin、xmax、ymin、ymax与格网大小，计算格网的起始行Ymin和终止行Ymax以及起始列Xmin和终止列Xmax，则直线x=Xmin、x=Xmax、y=Ymin和y=Ymax相交构成矩形EFGH，计算矩形内格网节点的坐标值；3)将三角形的3个顶点A、B、C与三角形的三边AB、AC、BC组成三组点线数据A、BC，B、AC和C、AB，对于需要判断的格网节点P，当点P与三组点线数据中的点相对于该组中的线段运用式(1)与式(2)计算的值都同号时，则点P在三角形ABC内，否则，点P在三角形外；4)根据三角形顶点的坐标及其属性值内插三角形内格网节点的属性值；5)重复步骤1-4，遍历TIN中的三角形，实现TIN向GRID的转换。

图1 三角形插值为格网节点示意

2 实验与分析

2.1TIN向GRID转换算法实验与分析

实验环境为Intel(R)Pentium(R)DCPU(3.40GHz)，1G内存。图2为本文算法的测试效率，其格网分辨率约1.6个节点/三角形。文献[6]与本文算法效率对比见表1。分析可知：本文算法的时间复杂度为O(n)，n为构成TIN的三角形个数；本文算法比传统算法在效率上有明显的提高，当点云数量或格网分辨率增大时，效率优势更加突出。因此，在算法效率与时间复杂度方面，本文算法更适合海量点云的处理。

图2 TIN向GRID转换效率

点数(个)三角形数(个)行列数(行数×列数)本文算法所用时间(s)文献[6]算法所用时间(s)843816754800×6000．22．310986218043200×24003．372．5

2.2 流式算法实验与分析

表2为流式算法测试结果，其中TIN的生成利用文献[8]提出的分治算法。作为对比，测试了基于格网节点驱动的分步转换算法的时间，包括TIN的生成、TIN的I/O操作与TIN插值为GRID三部分时间。由测试结果可知：1)TIN的I/O操作占用了分步转换算法消耗的大部分时间，严重制约了转换算法的效率，可见，避免TIN的I/O操作对于提高点云栅格化效率意义重大；2)因避免了TIN的I/O操作，流式算法在效率上比分步转换算法有了显著提高；3)相比于分步测试中TIN构建与TIN插值为GRID的时间和，流式算法多消耗了部分时间，这些时间主要用于内存空间的申请与释放。另外，因文献[8]是一种分治算法，其递归的特性使其对内存空间要求较高，无法对更大数据量的机载LiDAR点云进行处理。

表2 流式算法测试结果

并行计算是处理海量空间数据的有效方法[3,5]，串行算法并行化的一个难点在于任务分解。分步算法在进行并行化时任务分解较困难，流式算法基于三角形驱动的转换方式使任务分解相对简单，点云的栅格化并行处理也易于实现。

3 结论

流计算是避免I/O操作的一种有效方式，本文针对基于TIN的点云栅格化方法存在的缺陷，对栅格化过程进行了改进,即通过遍历三角形模拟流计算，有效避免了TIN数据的I/O操作，提高了内存利用效率，实现了大量点云的快速栅格化。下一步将着重研究兼顾算法时间和空间性能的 Delaunay三角网剖分算法，用于海量点云数据的栅格化流式处理及并行计算。

[1] KOBLER A,PFEIFER N,OGRINC P,et al.Repetitive interpolation:A robust algorithm for DEM generation from Aerial Laser Scanner data in forested terrain[J].Remote Sensing of Environment,2007,108(1):9-23.

[2] 李志林,朱庆.数字高程模型[M].武汉:武汉测绘科技大学出版社,2000.34-59.

[3] 宋效东,刘学军,汤国安,等.DEM与地形分析的并行计算[J].地理与地理信息科学,2012,28(4):1-7.

[4] AGARWAL P K,ARGE L,DANNER A.From point cloud to grid DEM:A scalable approach[A].The 12th International Symposium on Spatial Data Handing[C].2006.771-788.

[5] GUAN X F,WU H Y.Leveraging the power of multi-core platform for large-scale geospatial data processing:Exemplified by generating DEM from massive LiDAR point clouds[J].Computers & Geosciences,2010,36(10):1276-1282.

[6] 吴飞,吴凡.TIN向规则格网DEM转换的快速算法[J].测绘科学,2005,30(4):76-77.

[7] 章孝灿,黄智才,戴企成,等.GIS中基于拓扑结构和凸壳技术的快速TIN生成算法[J].计算机学报,2002，25(11):1212-1218.

[8] 胡金星,潘懋,马照亭,等.高效构建Delaunay三角网数字地形模型算法研究[J].北京大学学报(自然科学版),2003,39(5):736-741.

2014-06-16；

2014-08-19

高等学校博士学科点专项科研基金项目(20130023110001)

张春亢(1984-)，男，博士研究生，主要研究方向为LiDAR数据处理及应用。E-mail：chkang.chd@163.com

10.3969/j.issn.1672-0504.2015.01.026