顾及地形特征的LiDAR点云数据快速处理算法

卢维欣，万幼川，陈茂霖，秦家鑫，王思颖

（1.武汉大学 遥感信息工程学院，湖北 武汉 430079）

顾及地形特征的LiDAR点云数据快速处理算法

卢维欣1，万幼川1，陈茂霖1，秦家鑫1，王思颖1

（1.武汉大学 遥感信息工程学院，湖北 武汉 430079）

提出了一种基于地形特征的点云简化算法，首先根据图像学差分算子提取点云中的地形特征点，再以地形特征点作为种子点建立TIN模型进行迭代简化，并对算法中存在的计算效率低下的问题进行优化。采用两组数据进行算法有效性测试，并与经典的距离-高差简化算法结果进行对比。结果表明，该算法在地形复杂的区域有更好的简化效果。

点云；图像学；地形特征；数据简化

目前，国内外关于点云简化方面的研究多是针对逆向工程中较为规则平滑的点云数据[1-5]，而对地面点云数据的简化则研究较少，且各有不足[6-8]。本文提出了一种基于特征的点云迭代简化算法，该算法能有效减少点云冗余，并具有比较高的精度。

1 基于图像差分算子的地形特征点提取

将规则DEM视为栅格图像，将连续变化的山脊山谷线视为线特征，使用差分算子法进行特征提取，该算法使用一个2×2的窗口对DEM进行扫描，将窗口内最高点标记为山脊点，最低点标记为山谷点[9]。

为了实现上述算法，同时提高点云数据的处理效率，根据格网长度lgrid对整个测区进行二维划分，即

式中，（Xmax，Xmin）、（Ymax，Ymin）分别为测区的横纵坐标最大最小边值；M、N分别为格网的行列数；lgrid的大小与简化精度并无直接联系，但是适当选择格网长度能减少数据冗余并提高算法效率。

判断点云中每个离散点所在的网格，将格网中心点作为该格网的代表点，使用格网内所有点按距离倒数加权平均法[10]内插获取其高程，依次遍历所有格网可建立原始点云的概略DEM。根据概略DEM得到的山脊山谷点为一系列的格网，而非原始点云，根据山脊（山谷）点的局部最高（低）特性，对标记为山脊的格网选其中最高点作为山脊点，同样，标记为山谷的格网则选其中最低点。山脊线提取过程如图1所示。

图1 特征点提取过程

2 顾及特征的点云迭代简化

点云简化需满足在失真最小的情况下最大限度地减少数据量的原则，即在局部地形中起伏越大的点越有可能保留下来，而变化不明显的点则有可能被剔除。迭代简化是点云简化过程中常用的一种策略，本文提出一种基于特征的迭代简化思路：以初始特征点集建立TIN模型，将剩余的点分别在该模型中进行内插获取新的高程值并与原有的高程值进行比较得到高程差值Δh，将所有剩余点的Δh与点云简化所要求的精度mh进行比较，若均小于mh，则简化结束；否则将剩余点集中Δh最大的点加入特征点集并重新建网，迭代计算直至达到简化结束条件（如图 2）。算法以点云简化的精度作为迭代结束的阈值，最终得到的简化点集的精度即为简化所要求的精度。

图2 点云迭代简化切面图

迭代简化的算法保证了每次循环中所加入的均是最满足精度需求的点，能得到满足需求的结果点集，然而直接的迭代算法存在执行效率低下的问题。算法耗时主要体现在2个方面：① TIN模型内插时查找三角形；② 每次迭代则需重建一次Delaunay三角网。为此，分别提出以KD树辅助的三角形查找算法以及格网跳进算法来解决上述问题。

KD树是一种常用的点云组织结构，在点云邻域查找中起到了非常重要的作用。其特点在于树的每层都根据该层的分辨器对相应对象作出分枝决策。本文中采用二维KD树对三角网中每个三角形重心的平面坐标进行组织，每个节点中保存有该三角形在三角网中的索引号。在对待内插点进行搜索时，首先依据KD树搜索该点一定范围邻域内所有的三角形重心点，并根据向量叉积法[11]快速找到待定点所在的平面三角形，最后使用三角形插值法[10]计算待定点的内插高程值。

Delaunay三角剖分具有区域性的特性，即在新增、删除或移动某一顶点时只会影响邻近的三角形。根据这一特性，当若干个满足高差条件的点之间的距离足够远时，可同时加入到三角网中而互不影响，为了让每次进行判断的点满足距离条件，使用格网跳进的方式进行最佳点的查找（图3），将格网划分为4×4（或3×3、5×5等，按实际地形划分）的分格网并分别编号，编号相同的区域将在同一个TIN模型下进行判断，当所有同样编号区域判断完毕，即重新建网并跳转至下一编号相同区域；当对某一个格网进行判断时，只与当前格网内的点进行比较，若当前格网内并没有满足条件的点，则予以标记，之后不再判断。以KD树辅助的三角形搜索能大幅提高搜索速度，而且对简化结果并没有影响，而格网跳进的迭代算法会给数据带来少量冗余，但相比于其所带来的速度提升，是可以接受的。

图3 格网跳进搜索图（阴影部分将在同一模型下判断）

3 实验分析

本文选择了两组数据进行算法有效性的测试。实验区域内地形起伏明显，并滤去了植被和房屋，如图4所示。区域1为机载点云数据，范围为3 548 m× 1 405 m ，平均点距为 0.84 m；区域2为地面激光点云数据，范围为882 m×929 m ，平均点距为0.30 m。

图4 滤波后点云数据

区域1、2分别依据1∶2 000、1∶500的制图要求进行简化，根据制图精度要求[12]，将区域1与区域2的简化精度分别设置为1.0 m和0.5 m。简化时区域1格网间隔设为10 m，区域2设为2 m，简化结果与距离-高差算法结果进行对比，如图5所示。在简化程度大致相同的情况下，距离-高差算法简化得较为均匀，但对地形没有针对性。而本文算法则在地形变化剧烈的区域有明显加密。从图6的等高线局部细节显示来看，本文算法对地形变化的细节表达更有优势。

图5 区域1简化结果

图6 区域2简化结果

为了进一步说明本文算法对精度控制的效果，对算法进行精度检查，采用对所有原始点进行三角网内插的方法来检查简化精度，检查结果如表1所示。从结果来看，本文算法中误差小于预设精度的点均达到了99%以上，而距离-高差算法分别为92%和94%。从误差统计结果来看，相对于距离-高差算法，本文算法对山区地形的简化拥有更好的精度和稳定性。

4 结 语

根据山区地形的特点，提出一种依据精度要求的地面点云简化算法，并给出了具体的简化步骤与算法流程。实验结果表明，该算法能有效控制点云的简化精度，在保存了点云的地形特征信息的同时尽量避免冗余，并且算法中自定义阈值的选取问题，有效解决了之前算法中存在的不足，具有一定的实用价值。

[1] Pauly M, Gross M, Kobbelt L P. Efficient Simplification of Point-sampled Surfaces[C].Conference on Visualization, IEEE Computer Society,2002

[2] Xiwei P,Wenming H,Peizhi W, et al. Simplification of Scattered Point Cloud Based on Feature Extraction[C]. 3rd International Conference on. IEEE, 2009

[3] Song H, Feng H Y, Ouyang D. Automatic Detection of Tangential Discontinuities in Point Cloud Data[J]. Journal of Computing andInformation Science in Engineering, 2008, 8(2): 1-10

[4] Song H, Feng H Y. A Global Clustering Approach to Point Cloud Simplification with a Specified Data Reduction Ratio[J].Computer-aided Design, 2008, 40(3): 281-292

[5] Song H, Feng H Y. A Progressive Point Cloud Simplification Algorithm with Preserved Sharp Edge Data[J]. The International Journal of Advanced Manufacturing Technology, 2009, 45(5-6): 583-592

[6] LaFontaine P S. A Data Density Reduction Algorithm for Post-processed Airborne LiDAR Bathymetric Survey Data[D].University of Florida, 2000

[7] 刘庆元, 赵福生, 胡静波. 机载激光雷达数据简化算法的研究[J]. 测绘科学, 2010, 35(2): 90-92

[8] 徐景中, 万幼川, 张圣望. LiDAR 地面点云的简化方法研究[J].测绘信息与工程, 2008, 33(1): 32-34

[9] Peucker T K, Douglas D H. Detection of Surface-specific Points by Local Parallel Processing of Discrete Terrain Elevation Data[J].Computer Graphics and Image Processing, 1975, 4(4): 375-387

[10] 张祖勋, 张剑清. 数字摄影测量学[M]. 武汉：武汉大学出版社, 1997

[11] 庞明勇, 卢章平. 计算两凸多边形的并集多边形及其面积的计算机算法与实现[J]. 工程图学学报, 2004, 25(1): 90-94

[12] GB 15967-1995. 1∶500 、1∶1 000 、1∶2 000地形图航空摄影测量数字化测图规范[S].

P237.3

B

1672-4623（2015）04-0041-03

10.3969/j.issn.1672-4623.2015.04.015

卢维欣，硕士，主要研究方向为地面激光点云数据处理。

2014-09-30。

项目来源：国家高技术研究发展计划资助项目（2013AA122104-3）；博士点基金资助项目（20130141130003）。