1 引言

在基于激光的无人驾驶和移动机器人应用中,动态场景下提取对象的能力十分重要。感知系统需要在动态环境下感知物体的移动,对图像或点云数据进行处理是分析的关键。在自主导航中,对三维激光雷达点云数据进行单个对象分离是无人驾驶和移动机器人的重要任务。在具有复杂交通环境的街道路面上,地图可能因为环境动态性质发生错误数据关联,无人驾驶车辆需要对周围环境进行推理,在扫描过程中会极大发生误差并进行错误配准,因此实现快速且鲁棒的3D稀疏点云分割与聚类非常重要。

基于三维激光雷达检测障碍的方法主要包括DBSCAN聚类算法^[1]、K-means聚类算法^[2]、欧氏聚类算法^[3]、利用深度图像进行聚类分析的算法^[4]等。其中,DBSCAN算法是一种基于密度的数据聚类算法,多用于数据挖掘和机器学习中,在进行点云处理时,此算法能够快速地对任意形状点云进行聚类,但内存资源消耗大,数据过多时对处理器要求很高。K-means聚类算法在数据量较大时仍能保持高准确性,但需要手动输入聚类数目K,由于路面情况较为复杂,K-means聚类算法难以达到实时性要求。欧氏聚类算法则对大多数据有通用性,点云分割的效果也良好,但是需要预设固定的距离阈值,因此该算法在三维激光雷达障碍物检测中精度较低。Vosselman等^[5]利用区域生长法和3D Hough变换技术来检测几何形状。Tarsha-Kurdi等^[6]通过比较Hough变换技术和RANSAC算法的结果来检测3D建筑点云中的屋顶平面,发现RANSAC算法更有效。Yu等^[7]提出了一种基于距离图像的分割算法,用于在城市场景中检测平面区域并同时将结果合并到标记的点云中。本文提出一种在同样计算条件下,对局部点云射线采用角度约束,对全局点云射线采用距离分割的改进欧氏聚类算法,该算法有效地解决了点云近密远疏特性导致分割成功率较低的问题。

2 地面-非地面分割

分割前需要从获得的点云数据中移除地面。简单的方法是将低于车辆高度的3D点移除,这种方式在一般场景中作用较大,但是在车辆的俯仰角、侧倾角不等于0或者地面并非完美的平面时误差较大,因此用RANSAC平面拟合方法进行改善^[8]。激光雷达交互软件会提供每条激光束的距离值、时间戳及光束角度。可以直接将这些数据转换为深度图像,图像的行数由垂直方向上光束的数量决定,例如,对于Velodyne激光雷达,有16线、64线、128线等。而图像的列数由激光每旋转360°得到的距离值产生。这种深度图像的每个像素存储了传感器到物体之间的距离,为了加速计算,可以将水平方向上的多个读数组合成一个像素。对于地面分割,提出三个假设:假设传感器安装在水平移动的基座上;假设地面的曲率很低;假设移动机器人或者车辆至少在深度图像最低像素上能观测到地面。

假设条件成立,将深度图看作矩阵,则第c列r行的像素值转化为角度R_r,c,这些角度表示连接两点的倾斜角度, αc-1r和R_r-1分别代表该行的相邻深度值,如图1所示。图2为真实场景激光扫描图,因此在已知连续垂直的两个单激光束的深度值下,可以使用三角规则计算角度α,表达式为

α=arctan(‖BC‖,‖AC‖)=arctan(Δz,Δx),(1)Δz=Rr-1,csinξa-Rr,csinξb,(2)Δx=Rr-1,ccosξa-Rr,ccosξb,(3)

式中:ξ_a和ξ_b分别为第r-1行和第r行激光束的垂直角;‖BC‖为两条相邻射线间的垂直距离。由于计算每个α时需要两个深度值,因此生成的角度图的行数比深度图的行数少1,所有的角度表示为在r行和c列坐标上的角度值。

图 1. 激光雷达扫描角度示意图

Fig. 1. Diagram of lidar scanning angle

下载图片 查看所有图片

图 2. 重叠的车辆与近距离的行人

Fig. 2. Overlapping vehicles and close pedestrians

下载图片 查看所有图片

基于随机采样一致性的RANSAC平面分割算法在点云数据处理中十分常用,其基本思想是根据一组包含噪声、外点等各种缺陷的样本数据集,估计出数学模型参数,同时得到有效的样本数据,结合深度图像的像素距离与平面拟合获得对应的非地面点云,如图3、4所示。

图 3. 路面点云

Fig. 3. Point cloud of road surface

下载图片 查看所有图片

图 4. 地面去除

Fig. 4. Ground removal

下载图片 查看所有图片

3 离散点去除

采用VoxelGrid方法对点云进行下采样,即减少点的数量,该方法的优势在于减少点云数据量的同时能保留点云形状特征,提高了配准精度。激光雷达通常会产生不均匀的点云数据,测量中的误差会产生稀疏的离散点使得结果不准确(例如,前后人物的错位使点云连接)。解决方法是对每个点的邻域进行统计分析,并修剪掉那些不符合标准的点。稀疏离群点移除方法计算输入数据中点到临近点的距离,再计算每个点到所有临近点的平均距离,假设结果是一个高斯分布,其形状由均值和标准差决定,平均距离在标准范围之外的点可被定义为离群点并从数据中去除。该方法用于检测并消除远离样本的异常值,同时能保护好样本点。由此可见,异常值和噪声数据是两种性质不同的点,由统计学方法可知:检测异常值时首先假设点云数据是正常数据并遵循一定的分布规律,然后统计点云数据的概率分布情况,选定该点云的生成模型,再修剪不符合指定标准的点。

1)基于正态分布的一元离群点检测:假设有n个点x₁,…,x_n,这n个点的均值μ和方差σ表示为

μ=∑i=1nxin,σ2=∑i=1n(xi-μ)2n。(4)

然后,对于数据点x,可以计算概率p(x)以确定x是否是异常值:

p(x)=∏j=1np(xj,μj,σj2)=∏j=1n12πσjexp-(xj-μj)22σj2,(5)

式中:i和j均为激光点云数目。

2)多元高斯分布的离群点检测:假设n维的数据集为x={x₁,…,x_n},则n维数据集的平均向量为

μ=[E(x1),…,E(xn)],(6)

式中:E(·)为期望值。数据集的n×n的协方差矩阵为

Σ=Cov(xi,xj)。(7)

对于点x,计算概率p(x)来判断x是不是一个异常值:

p(x)=1(2π)n2Σ12+exp-12(x-μ)TΣ-1(x-μ)。(8)

4 角度约束-局部分割

激光雷达的垂直分辨率对分割有着重要的影响。需要判断相邻点之间的距离和角度,同时也要判断该激光束是否被同一物体反射,为了解决激光束是否被同一物体反射的问题,采用基于角度约束的局部点云分割方法。首先,将激光雷达三维点云转为深度图像,深度图像的优点是可以明确邻域之间的关系,从而更容易对分割问题进行处理,使整体的计算速度提高。

图5是Velodyne激光雷达记录的场景,雷达显示此刻的环境信息,图5(a)显示行人位于两辆车的左前方。图6展示了位于O点的激光雷达所测量的两个任意点A、B,图中显示出OA和OB之间的位置关系。在一般情况下,假设A、B位于以O为圆心的坐标系中,将角度β定义为激光束与连接A和B线之间的夹角,S_AB为估计对象的表面,如果它们都属于同一对象,则可以基于角度β判断出是否为同一物体,结合统计滤波方式去除车/人、人/人、车/车等之间的离散点。

图 5. 行人与车辆位置。(a)射线图;(b)俯视图

Fig. 5. Location between pedestrians and vehicles. (a) Ray diagram; (b) top view

下载图片 查看所有图片

图 6. 角度示意图

Fig. 6. Diagram of angle

下载图片 查看所有图片

由图6可知OA和OB的距离值,将两次的测量值记为d₁和d₂,因此角度β的表达式为

β=arctan(‖BZ‖,‖ZA‖)=arctan(d2sinψ,d1-d2cosψ)。(9)

由图6可知,计算的是图像在行或列在相邻点A对点B(或者点B对点A)之间的夹角β,此时分为两种情况,一种是对应行方向的角度增量,另一种情况是对应列方向的角度增量。在对阈值为β的物体进行分割中,被扫描的物体实际可能为平面结构,例如相对于激光束方向,墙壁几乎平行、垂直、与激光束方向成一定的角度。在此情况下,β变化很小,因此物体可能会分成多个部分,这就意味着,若β<ψ,就难以判断两个点是否源自于同一物体或是位于与激光束平行的平面上,因此关键是对角度β进行求解。

5 欧氏聚类-全局分割

5.1 按距离分割点云

本实验采用Velodyne VLP-16线激光雷达,其有效测量距离为100 m,垂直视场角为30°,垂直角分辨率为2°,水平角分辨率为0.1°~0.4°,每秒可搜集30×10⁴点云数据,旋转一周射线数为900~3600。采用欧氏聚类方法实现分割,此方法最重要的参数是聚类半径阈值^[9]。点云具有近密远疏的特性,为了达到更好的聚类效果,在不同距离的区域使用不同聚类半径阈值,如图7所示。

图 7. 激光雷达分割示意图

Fig. 7. Diagram of lidar segmentation

下载图片 查看所有图片

划分激光雷达射线距离:D₁=15 m,D₂=30 m,D₃=45 m,D₄=60 m,命名为分割圈1,2,3,4,5。有效半径阈值设定为:r₁=0.5 m,r₂=1.0 m,r₃=1.5 m,r₄=2.0 m。有效点云到发射点的距离为

ddis=xcur2+ycur2,(10)

式中:x_cur+y_cur为每一个激光点的平面坐标。当距离大于80 m时,忽略该点或采用滤波去除。

5.2 聚类点云

聚类就是将没有任何结构的原始点云按照欧氏距离、颜色、曲率、法线方向等特征分割成一系列的点云簇,同一类点云簇的点云具有相似的特征,欧几里得聚类便是将欧氏距离相近的点聚在一起,是点云分割的常用算法^[10]。

完整点云虽然信息丰富,但同时也使聚类变得困难,难以区分地面点云与物体点云信息,不利于点云聚类。因此按距离分类为五个类别且对应5组设定有效半径阈值的点云,再比较原始距离与分割距离的关系,若实际距离小于最近有效划分距离,则将其归类于该平面,以此类推,将所有搜集到的点云数据划分到五个平面内,若点的距离在分割距离的第一个圈内,将该距离范围内的激光数据归类到该分割圈,以次类推。

6 实验验证及讨论

为验证所提算法效果,采用某品牌电控车装载的Velodyne激光雷达作为实验平台,如图8所示,该实验平台主要配备单目相机、GPS、激光雷达等传感器,实车数据采集实验在贵阳某城区展开,车速控制在25 km/h左右,激光雷达扫描频率设置为10 Hz,道路区域与非道路区域有明显分界,路面平整、无较大起伏。同时以8G内存、i5-9700H的计算机作为实验平台,并在ROS软件下进行编程,在不压缩分辨率的情况下,传统欧氏聚类算法和改进欧氏聚类算法分别耗时580 ms和380 ms左右。实验中分别使用传统欧氏聚类算法、最小二乘法及改进欧氏聚类算法进行数据处理、障碍物检测及聚类结果分析。

图 8. 实验平台。(a)电控车实车图;(b)电控设备

Fig. 8. Experimental platform. (a) Electric control car; (b) electric control equipment

下载图片 查看所有图片

6.1 Bounding Box

生成边界框的方法是沿x轴和y轴对点云进行界定。如图9所示,在框选点云时,只需考虑在xy平面上该分割物体横纵向距离的最大、最小值^[9]。物体的横向距离为x_n-x_n-1,纵向距离为y_n-y_n-1,这样可以最大化地将分割物体框定在一定范围。同时令空间中该聚类点云的最大高度为z_max。

图 9. Bounding Box原理

Fig. 9. Principle of Bounding Box

下载图片 查看所有图片

6.2 路面拟合分析与讨论

RANSAC法在拟合平面与处理异常值上有着很强的鲁棒性,考虑到算法的后续应用,去除地面是十分重要的一步。最小二乘法在设初值和求最优解时会出现多次误差。

图10为采用两种算法进行地面去除的情况,当车辆经过右侧一倾斜路面的转弯口时,由于前期在选取初值和拟合平面时有多重误差,最小二乘法产生欠拟合现象。而RANSAC算法在进行判定时将此斜面归类为地面,将其与地面一同去除,同时对右上角的行人保有完整性。地面分割结果如表1所示,倾斜地面出现7次。

图 10. 地面去除。(a)最小二乘法;(b) RANSAC算法

Fig. 10. Ground removal. (a) Least square method; (b) RANSAC algorithm

下载图片 查看所有图片

6.3 聚类效果分析与讨论

聚类效果是衡量算法有效性的标准之一。所提算法主要的改进有全局动态阈值分割和局部射线角度约束,因此对独立个体具有更好的区分性,如图11所示。

图11(a)为距离实验平台30 m左右处路边停放4辆汽车的射线图。图11(b)为传统欧氏聚类算法的聚类效果,传统欧氏聚类算法在全局设定初始阈值,初始阈值的设定保证了大多数物体具有原本形状,但未考虑点云近密远疏特性,由于车辆距离较近,车辆间点云扩散使二者车辆被当作一个物体,最后Bounding Box同时框选三辆车,这为后续检测带来一定干扰。图11(c)为改进欧氏聚类算法效果,由动态阈值可知,当D=30 m时,聚类阈值由r=1 m变为r=2 m且β<β_min,所提算法结合了局部角度约束的方法,同时对聚类效果进行筛选,最终进行正确的框选操作。大范围聚类如图12所示。

图 11. 局部聚类对比。(a)点云图;(b)传统欧氏聚类算法;(c)改进欧氏聚类算法

Fig. 11. Local cluster comparison. (a) Point cloud map; (b) traditional Euclidean clustering algorithm; (c) improved Euclidean clustering algorithm

下载图片 查看所有图片

图 12. 全局聚类对比。(a)原始点云;(b)传统欧氏聚类算法;(c)改进欧氏聚类算法

Fig. 12. Global cluster comparison. (a) Original point cloud; (b) traditional Euclidean clustering algorithm; (c) improved Euclidean clustering algorithm

下载图片 查看所有图片

实验过程中进行了连续帧数据包的测试,分别使用传统欧氏聚类算法、改进欧氏聚类算法对同一时间段的数据进行障碍物检测与识别,实验结果如表2~4所示。根据实验结果,在相同场景下,改进欧氏聚类算法的障碍物检测平均正检率约为85.36%,相较传统算法提高了16.17个百分点,可见误检率明显下降,但漏检率有所提高。经分析,漏检的障碍物大都出现在墙体、树体附近,改进欧氏聚类算法将此范围当作一个物体,所以漏检率有所提高。两种算法对移动车辆与行人都具有一定的检测能力且相差不大,传统欧氏聚类算法主要的缺陷体现在对静止物体、距离较近的物体、尺寸较小物体的检测中。

7 结论

在基于距离阈值的点云分割算法中,距离阈值是一个十分难以把握的量。由于点云具有近密远疏的性质,所以即便对不同距离采用不同的阈值也难以完全分割物体,欧氏聚类虽然实现简单且实时性快,但这同时也成为处理3D激光雷达点云数据的弊端。所提算法虽然能够增强点云的聚类,但是受非道路元素的影响颇大,可以采用高精地图彻底剔除不在可行驶区域上的点,这样不仅聚类的计算量更小,同时也能够排除很多障碍物的干扰。