倾斜地面3D点云快速分割算法

张清宇，崔丽珍，李敏超，马宝良

(内蒙古科技大学 信息工程学院，内蒙古 包头 014010)

0 引言

近年来,随着自动驾驶领域的迅速发展,不断的探索与创新也产生了许多新的技术问题,尤其需要进一步提高对环境的可靠感知。目前,自动化车辆基本配备了激光雷达(LiDAR),用于提供大量精确的3D测量值。但是并非所有获得的信息都是“有效”的,必须区分相对于障碍物的测量和相对于地面的测量。尤其是在有坡度的地形,相对于平坦地形计算更困难。陈建等[1]利用地面二维激光雷达点云实现多车道车辆的检测。周梦飞等[2]利用3D点云感知周围环境和物体的属性特征,以实现点云分类。Thrun等[3]采用基于网格的方法,将网格划分为地面单元和非地面单元。Himmelsbach等[4]在柱坐标下处理点云,利用点的分布来拟合线段到点云,并设置坡度阈值。张子腾等[5]提出一种约束优化的定位方法。

在平坦地形中,常使用随机样本一致性(RANSAC)算法[6-7]将点以平面或直线的方式拟合到单个平面中,但是很少有地形是完全平坦的,因此需要对地面点进行优化处理。Zermas等[8]利用奇异值分解(SVD)和线束扫描法(SLR)聚类算法提取地面特征点,充分利用点云的结构分割地面点云。Nitsch等[9]使用当前点周围相邻的8个特征点计算点的法向量和质量值,使用基于距离的聚类算法对候选点进行分组并归为地面点。对于地面上诸如树木、车辆等障碍物的区分,Thrun等[3]将高程的点云划分为单元格,并计算其中的最大高度差,如果该差值超过设定的阈值,则单元格内的所有点都被视为障碍。Rieken等[10]将初始地面点投影到栅格地图中,存储每个单元的平均高度,利用中值滤波器平滑栅格地图中的高度并填补一些空的单元格。邹兵等[11]通过引入方差信息来减少栅格处理中对于传感器参数的依赖。Jiménez等[12]针对倾斜地形,利用马尔可夫随机场进行了障碍物的地面分类。此外还有地面辅助里程计的方法[13-15]来提高地面分割的精度,或在地面分割之前做预处理[16-17]来实现快速、鲁棒的地面分割。然而,由于LiDAR传感器本身的参数特性以及不同路况的特征信息,地面分割会对传感器产生依赖,且在倾斜路面会有特征点的缺失,在垂直方向不能够有效识别各障碍物。

针对这些问题,本文将对多组倾斜地形场景进行地面分割实验,利用LiDAR所提供的点云数据,先进行点云预处理,对于地面点云,将3D点云投影为2D点云,并进行直线拟合,然后利用栅格地图的方法来降低计算的复杂度,最终实现地面点云的分割。针对非地面的点云集合,首先利用SLR聚类算法处理,然后通过强度特征在垂直方向区分地面点与非地面点,并对扫描到的地面障碍物进行分类。

1 快速地面分割

利用简单的比较和局部直线拟合估计地平面点的方式来分割点云数据,避免了点云分割中建立复杂的邻域关系和提取复杂的点特征,减少了计算的复杂度。

1.1 局部地平面估计

图1 将3D空间划分为大小相等的扇形区域Fig.1 3D space divided into sectors of equal size

对于任意一个点p,到扇形区域的所属判定segment(pi)计算如下:

(1)

式中:atan 2(y,x)规定了平面的正x轴与p(x,y)之间的角度,并确保在(0,2π)。

1.2 3D点云投影为2D平面

为了应用直线提取的方式进行地面点分割,需要将3D的点云投影到2D平面计算。对于任意一个点pi∈P映射到容器(bin)中,用P表示映射到b的所有点的集合,即:

Ps={pi∈P|segment(pi)=s}。

(2)

图2 3D点云投影Fig.2 3D point cloud projection

最终得到了一组新的2D点P:

(3)

算法 1Extraction of lines for one segment Ss1:Ls=ϕ,c=0,Pl=ϕ2:for i=1 to B do3: if P′bSi≠ϕ then4: ifPl≥2 then5: (mc,bc)=fitline(Pl∪p′bSi)6: Ifmc≤Tm∧mc>Tmsmall∨bc≤Tb()∧fiterror(mc,bc,Pl∪p′bSi)≤TRMSEthen7: Pl=Pl∪p′bSi8: else9:(mc,bc)=fitline(Pl)10:Ls=Ls∪{(mc,bc)}11: c=c+112: Pl=ϕ13: i=i-1

1.3 直线拟合

对原型点的地面拟合采用直线拟合的方式,三维点p(x,y,z)在投影过程中获取的每个二维点对应的p(d,z),对每个segment拟合直线z=kd+b,其中k表示路面的坡度。基于拟合的直线来判断点到路面的高度,如果高度小于设定的阈值,则该点为路面点,否则为障碍物点;如果路面有坡度,则拟合的直线是分段的。不同系数的(k,d)代表不同坡度的路面。

当前segment中的容器获取到的第一个点line_start,即bin1,将其放入到current_line_points中,如果当前segment中的bins不包含点,则直接返回。从bin2开始判断是否进行拟合直线。然后通过计算cur_point与current_line_points最后一个值的距离,即bin2与bin1之间的距离,来判断两点是否为长直线,开始拟合直线并返回k与b,计算拟合直线的最大误差。具体的直线拟合流程如图3所示。

图3 直线拟合流程Fig.3 Flowchart of straight line fitting

2 基于栅格投影的地面点云分割算法

传统的基于栅格投影的地面分割算法通过计算栅格高度差或栅格单元的平均高度来实现地面点云的分割,然而LiDAR等传感器自身的参数会对平均高度的评价指标造成很大的影响,并且在有坡度的地形会出现欠分割现象,对于被遮挡的物体存在过分割现象,因此通过引入栅格单元点云高度的方差信息来解决栅格投影对于计算高度差或平均高度存在的问题,减轻算法对于传感器参数的依赖。

对于栅格单元ceil(i,j)的平均高度计算如下:

(4)

式中:(i,j)为栅格单元ceil(i,j)的行号与列号,number(·)为所求的栅格单元存储点云的数量,q为栅格单元中的ceil(i,j)点,hq为q点的h值。相较于平坦的地面,倾斜路面非地面部分的点云栅格单元平均高度较大。

对于栅格单元ceil(i,j)的高度差计算如下:

Hdiff(i,j)=hmax-hmin,

(5)

式中:hmax和hmin分别表示栅格单元ceil(i,j)高度的最大值和最小值。在平坦路面非地面点云的高度差一般较大。

栅格单元ceil(i,j)高度方差的计算如下:

(6)

σ2(i,j)可以反映栅格点云的高度分布,对于地面点云,栅格单元的高度方差较小;对于非地面点云,栅格单元的高度方差较大。

3 非地面点云的障碍物分类

3.1 算法总体框架

LiDAR所提供的点云数据除了地面点云,还包括垂直方向,扫描到的物体主要有建筑物、树木、汽车和行人等。

对于地面点云,首先进行点云数据预处理,将3D点云投影为2D点云,并进行直线拟合,然后利用栅格地图的方法,通过计算栅格高度差和栅格单元的平均高度,降低计算的复杂度,来实现地面点云的分割。对于非地面的点云集合,采用SLR聚类算法处理,通过设定强度特征阈值,在垂直方向区分地面点与非地面点,并对扫描到的地面障碍物进行分类,算法的总体框架如图4所示。

图4 算法总体框架Fig.4 Overall framework of the algorithm

3.2 SLR聚类算法

对于非地面点云集合,因为LiDAR扫描的区域有各种障碍物的遮挡等影响,会造成点云的缺失或稀疏,因此采用SLR聚类算法将非地面点云聚集,提高障碍物的识别精度与建图的准确性。在SLR中,所有相同水平角度发散出的点作为一个Scan-line,在单个Scan-line中,所有距离小于阈值的点分组在一起组成一个run。

SLR对第一个line,获取第一个line的runs,每个run都有不同的标签;SLR对第二个line,重复run segmenting,检查是否有新的run满足阈值定义的合并条件,如果满足合并条件,则将新的run与旧的合并,如果不满足阈值条件,则新的run获取新的标签,直到把所有的线都扫一遍。SLR聚类算法如图5所示。

图5 SLR聚类算法Fig.5 SLR clustering algorithm

相同颜色的点组成一个run,每一条线表示一个line。通过SLR聚类算法,解决了非地面点云的稀疏性问题,将特征点聚集,以便对障碍物的分类。SLR算法伪代码如算法2所示。

算法 2 SLR聚类伪代码Result: labels : labels of the non ground point1Initialization:2P : input point cloud3Nscanlines: number of scan lines4Thrun: threshold for points to belong in the same run5Thmerge: threshold to merge neighboring runs6newLabel=1: label identity7Main LOOP:8runsAbove=Find Runs(scanline1);9Fori=1:runsAbove do10 runsAbovei.label=newLabel;11 newLabel++;12end13fori=2:Nscanlines do14 runsCurrent=Find Runs(scanlinei);15Update Labels(runsCurrent,runsAbove);16 runsAbove=runsCurrent;

4 实验分析

本文算法采用的编程语言为C++,操作系统为Ubuntu18.04,实验环境依赖于ROS操作系统和点云库(PCL)。为了验证算法的实际效果,本文采用倾斜场景的KITTI数据集的点云数据进行实验,分别选取1、5、10 s处的地面分割效果与强度特征范围进行对比分析,算法地面点分割的效果用图表示,非地面点的障碍物区分由评价指标Intensitymax与Intensitymin表示。1 s时各算法的实时分割效果如图6所示。

(a)未经过处理的LiDAR点云

1 s为机器人刚行驶进圆形区域。相对于图6(a),图6(b)所示的经过滤波预处理的LiDAR点云去除了噪声的影响。图6(c)所示的快速地面分割后的点云摒弃了非地面的点云,对地面点进行了分割。与图6(c)相比,图6(d)中地面点云分割使用了栅格地图方法后能够获得更多有效的点。对非地面点进行SLR聚类算法处理后(图6(f))相对非处理非地面点云(图6(e)),能够使得非地面点的点云更聚集,更清晰地区分障碍,物并显示障碍物轮廓。

5 s时各算法的实时分割效果如图7所示。

(a)未经过处理的LiDAR点云

5 s时LiDAR经过圆形地形中间部分刚转向结束,考虑到传感器本身的抖动,会造成LiDAR点云数据的缺失。由于转向,图像左上角造成了一些点云的缺失,使用栅格图像的图7(d)相对图7(c)补偿了较多的点云,提高了地面分割的精确性。同样,对非地面点云进行SLR聚类算法处理后的图7(f)也较未处理的图7(e)在垂直方向有更多的特征点云,可以更好地识别障碍物。

10 s时各算法的实时分割效果如图8所示。

(a)未经过处理的LiDAR点云

10 s为机器人驶离圆形区域,在倾斜路面下坡的时刻。由图8(c)和图8(d)可知,在倾斜地形使用地面分割算法可以实现,相较于图8(e),经过SLR聚类算法处理后有更多的补偿点云,且能够清晰地显示汽车、树木等障碍物。

表1、表2、表3为1、5、10 s时刻分别在X、Y、Z方向点云对应强度特征值,强度值在设定阈值范围内即为有效点云。其中Velo表示未进行分割的原始LiDAR点云,Grid为栅格地图法分割后的地面点云,Fast为快速地面点云分割,SLR为经过聚类算法后处理后的非地面点云,obstacle为地面分割后添加未处理的非地面点云,Intensitymax与Intensitymin为强度的最大值与最小值。

表1 1、5、10 s时X方向对应强度特征值Tab.1 Corresponding strength characteristic values in X direction at 1, 5, 10 s

表2 1、5、10 s时Y方向对应强度特征值Tab.2 Corresponding strength characteristic values in Y direction at 1, 5, 10 s

表3 1、5、10 s时Z方向对应强度特征值Tab.3 Corresponding strength characteristic values in Z direction at 1, 5, 10 s

由表1、表2和表3可知,对于地面点云,使用栅格地图法相较快速地面分割算法具有更好的效果;对于非地面点云,使用SLR聚类算法处理后可以更好地实现障碍物识别。在倾斜地形,算法可以有效实现地面分割与非地面点的障碍物识别。

5 结束语

本文通过对不同倾斜地形场景进行地面分割实验,结果表明经过对原始LiDAR点云进行噪声等预处理后,去除了一些无效的点云。使用栅格地图的地面分割方法相较快速地面分割算法具有更好的地面分割效果,对非地面点进行SLR聚类算法处理后,补偿了LiDAR点云的稀疏分布,通过设置强度阈值特征,能够有效区分障碍物,并且在倾斜地形也能够取得良好的效果。