基于改进RANSAC算法的车载LiDAR地面点云提取

李佳佳，李永强，杨亚伦

(河南理工大学 测绘与国土信息工程学院，河南 焦作 454003)

车载LiDAR作为近年来一种新兴的空间信息获取手段，能快速获取高精度的城市地理信息数据并应用于诸多领域[1-2]。车载LiDAR采集的城市三维信息包括行人、建筑物、汽车、杆状地物、地面等点云数据，其中地面点云均匀分布在整个道路场景中，是连接其他地物的主要枢纽。在特定的应用研究中，需要将地面点滤除以获取非地面点云数据。

目前地面点提取算法主要分为4类：①基于数学形态学的算法[3-6]。该方法首先对点云数据进行网格化，以任意一点为中心开w×w的窗口，通过腐蚀膨胀窗口内各点高程提取地面点云数据，但该算法针对起伏地形提取效果较差，自动化程度及对低矮地物的滤除效果欠佳。②基于坡度变化的算法[7-10]。该方法的核心思想为地面点与非地面点的坡度大于地面点间的坡度，计算各点与邻域点之间的坡度值和设定阈值进行对比，判定其是地面点还是非地面点。该算法具有较强的实用性，但需要人工输入多个阈值参数，阈值选择不当会影响提取精度，并且计算复杂度较高。③基于不规则三角网的算法[11-14]。该方法将点云空间划分为规则格网，选择格网中的最低点作为地面点并构建三角网，通过判断非地面点与所在三角形的距离和角度是否满足所设阈值进而提取地面点。该算法能有效提取地面点云，但针对密度较大的数据，三角网的构建过程较复杂，地面点提取效率低。④RANSAC算法[15-16]。该算法从点云数据中随机选取3个点，用这3个点拟合出一个平面模型，判断剩余点到拟合平面的距离与阈值的大小关系，采用迭代的方式直至拟合出一个最优平面模型，从而提取地面点，但算法存在提取结果稳定性差、精度低等问题。针对RANSAC算法的缺点，本研究对其进行改进，首先使用KD-Tree构建点云拓扑关系，计算点云法向量，根据法向量对地面点进行粗提取，然后利用高程阈值去除非地面点，最后用FPS算法获取种子点拟合平面实现地面点的精确提取。经实验验证，改进后的RANSAC算法提取结果更稳定、精度更高。

1 研究方法

RANSAC算法由 Fischler和Bolles于1981年最先提出，该算法通过迭代方式从一组包含异常点的数据中寻找最优的数学模型。利用该算法提取地面点时，随机选取3个点计算得到初始平面模型，计算点云中的点到初始平面模型的距离，小于阈值的判定为“内点”，大于阈值的判定为“外点”，计算“内点”在点云数据中的占比w(公式1)。此外，要保证k次迭代计算模型每次至少采样到一个“外点”去计算模型的概率P(公式2)。公式如下：

(1)

P=1-(1-wn)k。

(2)

迭代次数过少会造成拟合的平面模型不理想，导致提取的地面点不完整且精度较低，故可以设置最小迭代次数k(公式3)。为得到更可信的平面模型参数，在k值的基础上再加上其标准偏差S(k)(公式4)，得到最终的迭代次数E(k)(公式5)。通过不断迭代的方式，取w最大的模型为最优平面模型，利用该模型提取地面点云。公式如下：

(3)

(4)

E(k)=k+S(k)。

(5)

1.1 RANSAC算法改进

改进后的RANSAC算法首先计算点云法向量，根据法向量对地面点进行粗提取。遍历粗提取的地面点云求平均高程，将其作为阈值滤除较高的地物点得到地面点集。然后，从地面点集中随机选取1个点作为种子点，利用最远点采样(farthest point sampling，FPS)算法选取剩余2个种子点并拟合平面模型。遍历点云数据(除去随机采样的3个点)求每个点到拟合平面的距离d，将求出的距离d与预先设定的数据和平面模型间可接受的最大差值α进行比较。若点云到平面的距离大于α则判定该点为非平面点，若点云到平面的距离小于α则判定该点为平面点。遍历完所有点云数据之后，统计平面点的数量n，与预先设定的平面点阈值β进行对比。若n>β，则拟合出的平面模型为最优平面模型，可利用最优平面模型精确提取地面点。改进后的算法流程如图1所示。

图1 算法流程

1.2 点云法向量求解

首先求解点云法向量，根据法向量对地面点进行粗提取，使用KD-Tree将点云空间划分成不同区域，根据设置的邻域半径获取邻域点集P{(x1,y1,z1),(x2,y2,z2),…,(xn,yn,zn)}。利用公式(6)计算点集样本均值,之后计算点集协方差矩阵C，最后计算协方差矩阵C的特征值与特征向量，所求最小特征值对应的特征向量即该邻域点集的局部法向量，见公式(7)和(8)：

(6)

(7)

(8)

根据法向量提取地面点的具体步骤如下:①利用KD-Tree划分点云空间，设置邻域半径获取邻域点集；②计算点集样本均值；③计算点集协方差矩阵；④计算特征值与特征向量，获取点集法向量；⑤计算邻域点集法向量与竖直方向的夹角，与所设阈值对比，若夹角小于5°则判定为非地面点。重复②～⑤，直至遍历所有点。

1.3 高程滤波

由于利用法向量获取的地面点云中仍包含部分非地面点，故利用点云高程信息对地面点云进行二次提取。遍历点云数据获取每个点的高程值并将其存放在一个空列表中，求出点云数据的平均高程h,并将h作为第一次滤波的阈值。再次遍历所有点云数据，对比每个点的高程与阈值h的关系，若某点的高程大于h，则判定该点为非地面点，若小于h，则判定该点为地面点。通过点云的平均高程无法将非地面点完全滤除，故需要拟合出最优平面模型来提取更加精确的地面点云。

1.4 最远点采样

从点云中随机选取1个点作为种子点，利用FPS算法选取剩余2个种子点，过程如图2所示。假设数据集S={p1,p2,…,pn}中共有n个点，在S中随机选取1个点pi(图2中的白色点)作为第1个种子点；计算剩余n-1个点(图2中的黑色点)与白色点的距离，选择离pi最远的点pj作为第2个种子点，将pi与pj写入点集S1={pi,pj}；选取剩余n-2个点计算其与点集S1中每个点的距离, 将最短距离作为该点到点集的距离,可得到n-2个到点集的距离，选取最远的点pk作为第3个种子点写入点集S1,此时S1={pi,pj,pk}；利用点集S1中的种子点拟合平面模型，通过迭代的方式拟合出最优平面模型，从而精确提取地面点云数据。

图2 最远点采样

2 实验与分析

为验证本研究所提算法的有效性，利用SSW车载激光扫描系统采集道路场景点云数据。采集数据时，设置激光扫描系统点频为500 kHz，转速为100 r/s，点云扫描间隔为0.02 m。实验区为2019年10月12日于河南焦作采集的某道路场景，如图3所示。车载LiDAR扫描系统在获取点云数据时，受采集环境和设备自身的影响，获取的数据不可避免地包含噪声点和离群点，会影响后续点云处理，故需要将噪声点去除。去噪后实验区共有1 918 601个数据，主要包括路灯、行道树、低矮灌木、车辆、地面等。

图3 实验区

2.1 实验结果

本算法通过Python语言进行编程，利用Open3D对提取的地面点云进行可视化。利用KD-Tree组织点云数据，设邻域半径为0.1 m，邻域搜索最小数量为32，计算点云法向量。根据法向量提取地面点，计算点云平均高程，滤除部分非地面点，设模型概率P为0.99、最大迭代次数为500，拟合最优平面模型，精确提取地面点，提取结果如图4所示。图4(a)为RANSAC算法的提取结果，提取的地面点数量为1 313 679；图4(b)为改进后RANSAC算法的提取结果，提取的地面点数量为1 314 063。两种算法提取的地面点相差不多，但改进后的RANSAC算法提取的地面更加完整。

图4 提取结果

2.2 精度分析

提取地面点云的实验结果表明，改进后的RANSAC算法能够有效提取城市中道路场景地面点云数据，绝大部分行道树、路灯、汽车、低矮灌木被滤除干净，同时大部分地面细节特征被保留。为定量分析实验结果，本研究使用滤波误差评判提取的地面点云数据。滤波误差分为3种，包括一类误差、二类误差、总误差，这3种误差是国际摄影测量与遥感学会(ISPRS)建立的滤波效果评价体系。一类误差又称拒真误差，是指将地面点错分成地物点的误差；二类误差又称纳伪误差，是指将地物点错分成地面点的误差；总误差是将上述两种误差进行加权求和得到的误差。滤波误差如表1所示，其中a为地面点正确提取的数量，b为将地面点错分成地物点的数量，c为将地物点错分为地面点的数量，d为地物点分类正确的数量。

表1 滤波误差

本研究将实验区人工判读的分类结果作为准确值，其中地面点数量为1 313 498，地物点数量为605 103。本研究所提算法的精度评价结果如表2所示。

表2 精度评价结果

从表2中可以看出，两种算法的一类误差分别为4.04%、2.16%，改进后的算法比原算法低1.88个百分点，表明改进后的RANSAC算法(本算法)提取的地面点云更为准确；两种算法的二类误差分别为8.80%、4.79%，改进后的算法比原算法低4.01个百分点，表明本算法将地物点误判成地面点的数量更少。两种算法的总误差分别为5.54%、2.99%，改进后的算法比原算法低2.55个百分点，表明本算法提取的地面点云精度更高，提取结果更可靠。由此可知,改进后的算法一类误差、二类误差和总误差均低于原算法，表明本算法对道路场景中地面点云的提取具有较强的适用性。

2.3 稳定性分析

利用RANSAC算法提取地面点云，种子点选取具有随机性，使得提取结果不稳定，需要多次提取才能获得较为完整的地面点云。为验证改进后的RANSAC算法是否具有更强的稳定性，进行多次地面点提取实验并分析改进后算法的稳定性。共进行7次实验，每次设置相同的实验参数，以提取出的点云数量作为稳定性分析的评判依据，稳定性分析结果如表3所示。

表3 稳定性分析结果

为了更直观地对比两种算法的稳定性，用表3中两种算法提取的点云数量绘制折线图(图5)。RANSAC算法随机选取3个种子点拟合平面模型，提取的地面点云数量起伏较大，精度不稳定。改进后的RANSAC算法利用点云法向量和高程阈值对地面点粗提取，通过FPS算法增加了初始种子点为地面点的概率，提取的地面点云数量变化不大，同时精度稳定在98%，证明改进后的算法使得地面点提取结果更稳定。选取其中3组地面点提取结果并可视化，结果如图6与图7所示。图6为RANSAC算法提取结果，从(a)中可以看出提取的地面并不完整；(b)中提取的地面较为完整，同时大部分地面细节特征被保留下来，但存在较多的非地面点；(c)中提取的地面数据相对完整，地物点也较少。图7为改进后的RANSAC算法提取结果，可以看出提取的地面完整且稳定性更强。

图5 稳定性分析

图6 RANSAC算法提取结果

图7 改进后的RANSAC算法提取结果

3 结论

本研究以车载LiDAR采集的城市道路场景为研究对象，利用改进的RANSAC算法提取地面点云，实验结果表明改进后算法的一类误差为2.16%、二类误差为4.79%、总误差为2.99%，比原算法的误差低且精度更高。为验证改进后算法的稳定性，进行了7次地面提取实验，结果表明改进后算法的稳定性更强。