平原地区机载激光雷达数据的抽稀算法分析

，，， ，

(1. 中科遥感科技集团有限公司, 天津 300384； 2. 国家测绘地理信息局重庆测绘院, 重庆 401120； 3. 吉林省航测遥感院, 吉林 长春 130051)

机载激光雷达(LiDAR)是获取高精度地形数据的新型测量手段，可以快速获取大面积高密度、高精度的三维点云数据，LiDAR数据拥有的高精度和高密度使其在生成地貌数据方面的应用得到飞速的发展和广泛的应用，可用于数字高程模型制作、城市三维建模、灾害环境监测等方面[1-3]。然而，高密度的数据导致数据量的大幅增加，几千米的航带，其点云量就达数千万[4]，给等值线生成带来了诸多不便，在等值线生成过程中，并无需全部表达所获取的数据信息，仅需表达相应地貌特征所需要的数据点信息[5]，符合相应的地形地貌精度要求，特别是在地势较平坦的平原地区。

在实际情况中，采样地形的LiDAR数据越密集，生成的精度越高、等值线越逼真，但是在《机载激光雷达数据获取技术规范》中没有将地形类型和采样密度相匹配，只规定点云数据的最大点间距不能大于1/2 DEM格网间距，若按此要求执行，在平原地区获取的点云数据会存在大量的冗余数据。有的地区兼顾大比例尺测绘需要，按照1∶2000要求获取点云数据制作等值线， 如此标准分幅的图幅数据量更大，对设备的要求更高，需要超高性能设备才能完成生产作业。同时由地面点云数据生成的等值线往往呈锯齿状，有许多独立的闭合环和曲折转弯，在平原地区尤为突出；点云数据的平均坡度值也异常的高，平原地区的地面TIN模型也是如此，给平原地区生产等值线造成很大的困难[6]。

由于机载激光雷达数据的水平采样距离相对于垂直方向精度较低，因此激光雷达存在很多噪点，要获得锯齿较少的等值线和更合理的坡度，必须去除点云数据中的噪点，同时还要最大可能地保留真实信息。因此，如何根据地形类别及特征要素对地形数据抽稀，获得合理的、适于等值线生成的点云地形数据集，具有重要意义[7]。点云数据抽稀的主要目的是优化采样密度和数据精度，以此得到符合要求的高精度DEM和等值线。在海量的点云数据中，如何能够把地形要素特征点保留下来，剔除冗余的噪声点，提高等值线生产效率和数据质量，是当前面临的重要问题[8]。

本文通过对几种抽稀算法的对比分析，结合平原地区激光点云的生产应用，总结出最优的、能够满足实际需求的抽稀算法，解决点云生产中的关键问题，提升生产效率，从而有利于点云数据的推广和应用。

1 LiDAR数据抽稀算法

目前国内外关于LiDAR数据抽稀的算法按照其核心原理主要有系统抽稀、格网抽稀、TIN抽稀、坡度抽稀等算法。

1.1 系统抽稀

系统抽稀是按照固定间隔对数据点随机抽稀。对于一个大样本N，首先确定抽样间隔，比如每10个点作为一个抽样间隔，然后在这10个样本点中随机选择一个样本数据点。这种数据抽稀算法主要优势是处理速度快，可以用来做快速显示和缩略图，适合于分析数据覆盖范围，制作区域快视图；但是没有顾及地形地貌特征信息[9]，如在TerraScan软件中数据抽稀就采用该方法调用点云数据。

1.2 格网抽稀

格网抽稀是利用输入的采样间隔构建虚拟格网，然后按照处理规则只保留虚拟格网内一个点云数据点(规则如最低值、均值或最高值等)。其中虚拟格网的大小要依据数据点的密度和数据成果要求来设定，如果数据点的密度达到每平方米几个点，则可以设定格网大小为1 m或更小。这种算法比较简单高效，但无法顾及点云数据的地形地貌特征信息，这将在一定程度上降低数据的精度。随着压缩程度的增加，特征点被删除的可能性也会增加，会丢失许多关键点数据。这种方法一般只应用于对精度要求较低的工程项目，或者对点云数据初步抽稀[10]。

1.3 TIN抽稀

TIN抽稀算法的原理是利用点云数据建立不规则三角网模型，分析判断相邻面的法线来确定点云点剔除还是保留。在平坦区域上点云数据点构成的三角网包含信息量最少，三角形构成面的法线向量趋近于平行，即法线向量的夹角越小地貌特征越一致，利用三角网的这个性质可以实现对点云数据的抽稀。该算法能够较好地保留地形特征点，但是在判断一点是否剔除时，需查找包含该点的三角面，在判断不同三角面之间的夹角时，在一定程度上会降低数据处理的速度[11-13]。

1.4 坡度抽稀

首先利用点云数据构建TIN，在生成的TIN数据点中读入第一个数据点，查找该点相邻的三角形，计算每个三角面的坡度，求得这些三角面的平均坡度，依此确定坡度抽稀阈值，并求得最大坡度和最小坡度之差，即最大坡度差，通过最大坡度差与坡度抽稀阈值进行比较确定此点是否为特征地形点。该算法能够较好地保留地形特征点，但坡度阈值确定时存在一定的不确定性，尤其是确定数据坡度临界值时存在较大不确定性，会在一定程度上影响点云数据质量和数据处理速度[14]。

2 基于约束TIN节点的抽稀法

以上几种算法中,系统抽稀和格网抽稀算法不能很好地保留地形特征信息,在一定程度上会降低点云数据精度。而基于TIN的抽稀算法和坡度抽稀算法,对于不同的地形采用动态阈值,能取得显著的效果,也能更好地保留地形特征点，但是也难以得到理想的抽稀结果。

2.1 约束TIN节点

为了实现对平原地区点云数据的抽稀,本文提出基于约束TIN节点的抽稀算法。采用点云数据和特征数据构建TIN，利用约束条件判断某个点云数据是否保留，通过剔除该点再构建TIN，判断其点位置的内插值与源值的差值是否小于相应地形的容差，如果满足要求就剔除该点，否则保留该点；在数据处理过程中特征数据始终参与构TIN，新构TIN网不能穿越特征要素，约束数据保证关键地形特征精度[15]。

由于地形地貌复杂多变，在一幅图内也会变化多样,按照坡度不同，可将地形分成平原、丘陵、山地及高山地，根据地形类别的中误差要求设置不同地貌的抽稀容差，详见表1，每类地形的容差按照1/3的中误差进行取值，这样既能更好地抽稀，又能保证数据精度。

表1 地形高程中误差和容差分类

数学模型算法如下：

(1) 读入所有点，生成TIN，依据地形类别确定容差值。

(2) 在TIN中读入TIN网中第一个点P，找到与P点相关的三角形的节点，如图1所示。

(3) 利用找到的节点重新构TIN，并提取P点在新TIN中的线性内插值P′。

(4) 计算P′与P的高程差值，与容差值对比，大于容差值保留，小于容差值则剔除，如图2所示。

(5) 继续遍历所有TIN网中的点云数据，直到判断完成为止。

(6) 判断涉及递归运算，同时要考虑特征约束线的三角网。

特征约束线是对地形要素进行强制约束，点云构TIN不能跨越特征线，但是必须与特征线构成网，即点云与约束线相邻的点必须一起构成三角网。图3(a)是原始TIN数据，图3(b)是在抽稀中未考虑约束要素，图3(c)是经过本文方法抽稀后的TIN数据，在特征线位置处会出现错误，在后期补上约束线也会损失跨越特征线的点信息。

2.2 约束TIN节点算法的优化

在采用约束TIN节点算法时，每个点云的取舍均按照约束值判断，但是存在剔除后在原TIN的内部插值高程变形超过约束值数倍的情况，内部变形如图4所示，图4(a)粗线网是原始点云的点构网，图4(b)细线网是抽稀后点云的点构网，图4(c)是二者的叠加图，图4(a)圆点处的点云(高程值：129.749 m)被抽稀掉，在图4(b)圆点处内插值为129.586 m，两次点值较差为0.163 m，然而在图4(a)、(b)中三角形处，高程值分别是129.828 m和128.877 m，较差为0.951 m，超过附近点限差的5倍。

为了解决上述问题，在点云点的抽稀过程中，通过增加虚拟格网约束点的方式保证点云数据抽稀的精度，确定点云剔除还是保留，算法流程如图5所示。虚拟格网间距的设置根据成果精度要求确定，在删减过程中动态计算原值和新内差值的较差，超限则放入保留点数据集，如图2所示，图中黑点即为虚拟格网点。

为了提高运算速度，在剔除过程中只删减三角形，不作增加处理；在第一次处理完成后，利用保留的点重新优化构建三角网，对剔除的点进行二次判断，确认是否剔除；如果超限则补回到保留点中，并增加三角网，这样既能保证处理精度，又能提高运算效率[16-17]。

3 抽稀方法应用分析

3.1 试验区介绍

为了满足实际生产的需要，选取任务区的部分激光点云数据进行试验测试。试验测区为地势整体平缓，主要分为松辽河间过渡带风沙覆盖的平原、风沙覆盖的倾斜平原、松嫩盐渍化发育的低平原和松嫩湖沼漫布的低平原，地貌破碎复杂，盐碱地貌随处可见，属于平原地区，试验参数按照平原执行。试验数据的点云间距约1.2 m，测区总面积5500 km2，典型地貌如图6所示。

3.2 精度评估分析方法

(1) 为了更好地分析验证各种抽稀算法，分别对系统抽稀、格网抽稀和TIN抽稀作基本分析，对坡度抽稀算法和约束TIN节点抽稀法进行重点分析。

(2) 采用ArcGIS 10.1软件平台完成数据成果测试、分析；数据样本为随机抽取的一幅具有水域特征线的数据，1∶1万原始点云中地面点数据为5 346 712个点。

(3) 所使用的LiDAR点云是经过质检部门验收合格的点云数据， 使用分类好的点云数据作为基准数据，利用基准数据的地面点构建TIN，然后按照2 m格网间距线性内插生成DEM数据，行列数为(1851,2001)，总共点数为3 703 851个，全部为分析检测点，以此为标准值完成抽稀精度评定。

(4) 采用各种方法抽稀后的点云数据集构TIN，然后按照相同范围、相同格网间距、相同采样方法内插生成新的DEM数据。

(5) 利用栅格数据计算工具，使用标准DEM数据与各类抽稀方法生成的新DEM数据作差，生成差值栅格数据，如图7所示。

(6) 利用栅格分类工具，对新的栅格数据按照5类进行统计分析，分类统计内容见表2，使用差值结果直接统计分析，不采用标准差和中误差公式计算分析。

表2 分类统计

3.3 试验精度分析

3.3.1 系统抽稀

系统抽稀是不确定性抽稀，按抽稀后的保留点数计算，分别保留到85%、75%、50%和43%的程度计算分析，也就是抽稀掉15%、25%、50%和57%。表3显示了保留点密度与标准段数据精度的关系。

表3 系统抽稀保留率与数据精度的关系

在试验数据保留率84.2%的测试中，最大偏差点分别为-1.569 85和1.945 12；保留率74.5%的测试中最大偏差点分别为-1.572 85和1.963 4；保留率50.5%的测试中最大偏差点分别为-1.579 67和1.752 27；保留率43.2%的测试中最大偏差点分别为-1.779 61和1.952 12；从表3中可以看出保留率越小两端所占比例越高，分布在-0.2～0.20 m区间比例越小，整体效果较差。

3.3.2 格网抽稀

分别保留85%、75%、50%和40%的程度计算分析。在试验数据保留率85.9%的测试中最大偏差点分别为-1.150 25和0.949 936；保留率72.6%的测试中最大偏差点分别为-1.671 38和1.351 34；保留率50.1%的测试中最大偏差点分别为-1.910 63和2.120 69；保留率41.5%的测试中最大偏差点分别为-2.010 64和2.530 65；从表4中50%以上保留率在高精精度范围内的点最多。

表4 格网抽稀保留率与数据精度的关系

3.3.3 TIN抽稀

分别保留55%、42%、35%和16%的程度计算分析。在数据试验中保留率55.7%的测试中最大偏差点分别为-0.950 24和0.849 936；保留率42.1%的测试中最大偏差点分别为-0.971 051和0.982 042；保留率35.6%的测试中最大偏差点分别为-1.271 06和1.152 04；保留率15.8%的测试中最大偏差点分别为-1.510 64和1.630 65；从表5中35%以上保留率在高精精度范围内的点最多。

表5 TIN抽稀保留率与数据精度的关系

3.3.4 坡度抽稀算法

试验经原始数据抽稀后，保留65%、50%、41%和25%的程度，保留率和高程比率分布见表6。

在数据试验中保留率65.0%的测试中最大偏差点分别为-1.132 31和0.947 453；保留率50.2%的测试中最大偏差点分别为-1.347 01和1.252 32；保留率40.9%的测试中最大偏差点分别为-1.645 52和1.368 91；保留率25.1%的测试中最大偏差点分别为-2.110 03和1.941 36；从表6中41%以上保留率在高精精度范围内的点最多。

表6 坡度抽稀算法保留率与数据精度的关系

3.3.5 约束TIN节点抽稀法

试验经原始数据抽稀后，分别抽稀保留65%、50%、41%和25%的程度，保留率和高程比率分布见表7。在数据试验中保留率65.1%的测试中最大偏差点分别为-0.312 37和0.287 413；保留率50.3%的测试中最大偏差点分别为-0.327 61和0.310 02；保留率41.3%的测试中最大偏差点分别为-0.347 05和0.332 32；保留率25.3%的测试中最大偏差点分别为-0.349 01和0.341 27；从表7中可以看出保留率在41%以上，精度分布最好。

表7 约束TIN节点抽稀法保留率与数据精度的关系

3.4 抽稀方法比较

通过试验各种抽稀方法，结果表明无论数据抽稀到何种程度,都会有一些高程信息会丢失,抽稀的目标是最大限度地降低数据的密度而损失最小的精度。采用一种合适的抽稀方法可以使试验区域的数据在保留率达到41%时,其高程内插精度仍能好于20 cm，高程中误差能控制几厘米内[18]。

为了能够更好地说明各种抽稀算法对基础点云精度的影响,将以上5种抽稀算法的保留率与-0.2～0.20 m的精度汇集到一个图中,如图8所示。

4 约束TIN节点抽稀算法的建立与应用

4.1 抽稀法的应用

采用约束TIN节点抽稀算法完成某试验测区5500 km2的机载雷达数据制作DEM和等值线，作业单元为1∶10 000标准分幅数据，单幅数据量大的达到10 GB、小的也有0.4 GB，数据抽稀完后一般在0.5 GB左右，这样标准配置计算机都能满足满幅作业，避免了拆分再合并的复杂工作。

本文项目成果要求制作DEM和等值线，在生产过程中考虑到生产精度和运算速度等因素，充分分析各种算法的优缺点，采用组合抽稀方式进行数据处理，首先采用高效的格网最低点抽稀算法完成概略抽稀，网格抽稀间距为0.75 m，每幅图的数据量大约为1.2 GB；然后采用约束TIN节点抽稀算法完成精细化抽稀，高程限差设置为0.10 m，处理完成后每幅数据量为0.4 GB大小，保留率为34%，压缩率为66%。数据生产完成后进行外业实地符合性高程精度检查，见表8，利用数据分别生成2 m×2 m和5 m×5 m格网间距的DEM，利用外业检测数据计算中误差，2 m×2 m的精度都优于5 m×5 m的精度，中误差都优于0.20 m；5 m×5 m格网间距的DEM精度最大为0.20 m，图幅都优于0.20 m，最好精度达到0.08 m。

表8 外业实地符合性高程中误差

4.2 抽稀算法探讨

基于原始点云数据生成的三角网和等值线均有坡度值大、抖动和气泡比较多的特点，无意义的噪声数据也较多，单独几个点就会有等值线反映出来；点云数据经过两种方法抽稀后生成的DEM数据和等值线数据噪声明显减少，效果对比如图9所示。

因此，各种抽稀算法和优化约束TIN节点抽稀法的组合应用能达到事半功倍的理想效果。

5 结 语

本文提出了约束TIN节点抽稀法，其既能很好地保留局部地形特征，又能保证整体的地貌特征；既能实现点云数据超强压缩，又能保证它的高精度。本文算法优势在于引入高度差约束，并充分利用TIN构网优势，补充虚拟格网控制精度优化算法，组合传统算法并能深化应用，尤其在平原地区地貌数据生产项目中的应用，充分体现了算法的高压缩、高去噪特点。

本文算法解决了点云冗余数据的剔除，提高了计算速度和工作效率，让处理大数据量点云数据变为可能，解决了逐块处理的痛点，实现了整幅完整作业，同时实现了点云噪声和高植被点云自动滤波，消除了DEM和等值线数据中的噪声。

本文算法经过大范围制作DEM和等值线数据的实际应用，充分验证了算法的实用性和可行性。点云数据抽稀或去噪是生产各种测绘产品的必经阶段，高度精准抽稀为点云数据制作DEM和等值线产品奠定了良好的数据基础，为全国性推广点云数据制作DEM和等值线提出可行性方法[19]。

今后，将在平原测区的生产实践基础上进一步完善验证丘陵地、山地的各种参数和算法，然后再展开地形地貌的平滑算法，为基于激光雷达数据制作高质量的等值线提供更优的解决方案。