1 引言

三维激光雷达以其测距精度高、探测范围大以及不受照明条件影响的优势,成为一种重要的环境主动感知技术,在无人车、移动机器人等领域得到广泛的应用^[1]。三维激光雷达产生的点云是海量、稀疏、无序的点集合,要实现对环境周围目标的识别,首先,最重要的一步是将点云聚类分离成独立的子集,每个子集与有物理意义的目标相对应,这种分割为后续目标识别及追踪提供了重要基础,其次,算法运行时间和分割效果直接影响到后续数据处理,但是普通的聚类算法无法满足点云分割实时性和准确性,因此研究一种快速、准确的高效分割方法很有必要。

目前,国内外对点云分割研究大致分为基于特征、基于地面投影及深度图三类。第一类研究直接在三维空间中构建复杂的特征,然后通过聚类算法对目标进行分割^[2-6],这类基于特征的方法虽然可以取得较好的分割效果,但计算时间往往很长。文献[ 4-5]中利用邻近点关系,提出了径向边界最近邻聚类算法,从某点出发不断迭代查询,因此算法实时性不好。DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法由于搜索临近点时间复杂度高,直接对点云目标进行分割的实时性并不高,为了提升速度,基于K维(KD)树结构的DBSCAN算法被提出,但建立KD树结构也同样复杂且耗时。第二类研究将点云投影至俯视平面,利用栅格高程图进行处理^[7-10],通过对单元格内测量值的最大高度差来判断单元格是否被占据,通过对占据的单元格进行聚类、特征提取来检测各种形状的障碍物,该类方法简单高效,但是栅格单元参数无法自适应调节,容易造成欠分割或者过分割,而且数据存储量巨大,不适合在工程应用。第三类研究基于三维激光雷达工作原理建立的深度图结构,将激光雷达旋转一周生成多条扫描线,利用扫描线构建二维深度图结构。文献[ 11]中提出深度图像与表面几何特征融合的分割方法,构造局部凸性特征,利用标记算法进行分割,但其局部凸性特征过于依赖点云法向量的精度,且每帧处理很耗时。

为了满足目标点云分割算法准确性和实时性的要求,本文提出一种基于深度图的点云目标快速分割(FS)方法,不同于传统的DBSCAN聚类分割方法,从深度图的角度对点云数据进行处理,保证算法的实时性。采用自适应参数的改进DBSCAN算法,搜索临近点,同时考虑欧氏距离和角度距离,大大减少了相邻目标欠分割的问题,并在公开的数据集上验证了算法的有效性。

2 基本原理

2.1 数据获取和深度图的建立

本文提出的点云目标分割方法分为3步操作进行,主要包括建立深度图、地面点云去除、非地面点云聚类分割。

无人车中常用的激光雷达为机械式激光雷达,其中由若干组可以旋转的激光发射器和接收器组成,每个发射器发射一条激光束,称之为扫描线。目前主要有16线、32线和64线激光雷达。激光雷达中的激光束是波长在900 nm左右的近红外光,可以通过发射激光探测信号直接获得周围一圈准确的三维空间信息。激光雷达的成像原理比较简单:发射器和接收器连接在一个可以旋转的机械结构上,某时刻发射器将激光发射出去,之后接收器接收返回的激光,最后计算激光与物体碰撞点到雷达原点的距离。

以美国Velodyne公司xx型16线激光雷达为例,该激光雷达共有16个激光器,每个激光器在垂直方向都有固定的俯仰角,两个相邻的激光器之间的垂直夹角为2°,每间隔时间Δt,激光发射器发射一次,雷达高速旋转一周,产生多条扫描线,称为一帧点云。每帧点云数据均在激光雷达的本地坐标下,称之为LiDAR坐标系,每帧点云数据大约包含了30万个点,规定第t帧点云P_t为

Pt=(p1,p2,…,pn),(1)

式中:n为点云数据点总数;p_i=(x_i,y_i,z_i)为第i(i=1,2,…,n)个数据点在LiDAR坐标系下的三维坐标。由于本算法是对每帧点云数据进行处理,所以不需要将LiDAR坐标转化为全局坐标。

点云数据转化为深度图,将三维空间中的点投影到可以展开的圆柱形表面上,使其平面化。深度图的每个像素点存储了目标到激光雷达的空间距离d,深度图行数R_r取决于激光器数目,深度图列数R_c取决于激光雷达水平角度分辨率。建立点云与深度图的映射关系如图1所示,图1(a)为某原始点云数据,图1(b)为深度图,图1(c)为对应摄像头所采集的图像。

图 1. 从点云到深度图的投影过程。(a)点云数据;(b)深度图;(c)场景图片

Fig. 1. Projection form point clouds to depth map. (a) Point clouds; (b) depth map; (c) scene image

下载图片 查看所有图片

点云的三维直角坐标点(x,y,z)可转化为深度图二维坐标点(r,c),转换公式为

r=[arcsin(z/d)]/h,(2)

c=arcsin⁡arcsinyxv,3

式中:x、y、z为点的三维坐标;d=x2+y2+z2;v为激光雷达垂直角度分辨率;h为激光雷达水平角度分辨率。

2.2 地面点云的去除

地面点云数据去除是减少数据量以及提高分割算法精度的有效手段,是点云滤波的一种方式,根据各种滤波算法理论背景,可以对这些算法进行分类, 如基于坡度、基于形态学、基于分割等^[12]。基于坡度的点云滤波方法^[13]原理简单,搜索临近点导致计算量和内存占用很大,同时算法严重依赖于阈值的设定。基于形态学的滤波方法^[14]主要通过设定高程阈值的方法实现地面点云的去除,这个方法虽然简单有效,但是无法处理起伏和有坡度的路面。基于分割的方法包括随机采样一致性法、地面分块直线拟合算法^[15]等,这类方法往往能够获得较好的点云滤波效果,但是算法实时性不高,在无人车领域中应用受限。本文基于深度图的角度阈值法有两点创新:1)结合深度图提升搜索速度,在深度图上数据点的邻接关系较为明确,所以可以快速地搜索到临近点;2)原理简单,便于操作实施。

基于深度图的角度阈值法实现地面点云去除。激光器扫描线在地面和障碍物间形成的角度值存在显著的不同,可作为分离地面点云的重要依据。如图2所示,相邻两个激光器的扫描线OA、OB与地面相交于A、B两个点,AC与BC垂直相交于C点。A、B两点对应于深度图中的深度值分别为R_r-1,c和R_r,c,其中R_r,c为第r行第c列的深度值;R_r-1,c为第r-1行第c列的深度值,深度图中B点的角度值记为 αr-1,cr,可表示为

αr-1,cr=arctanBC/AC,(4)

其中

AC=Rr-1,csina-Rr,csinb,(5)

BC=Rr-1,ccosa-Rr,ccosb,6

式中:a、b分别为相邻两个激光器的垂直角度值。利用(4)~(6)式进行计算,对深度图的每个像素点进行同样的处理,从而得出角度矩阵M,对应深度图中每个点的角度值。

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

Fig. 2. Scanning angle diagram of LiDAR

下载图片 查看所有图片

广度优先搜索(BFS)算法是一种图搜索算法。本文结合BFS算法和深度图的角度阈值法去除地面点云:从深度图的起始点出发,搜索起始点所有的相邻点,计算与相邻点的角度差值来实现对地面点云的标记,然后再从相邻点搜索,最终实现整个地面点云的去除,这本身是一种以BFS策略的方式来实现遍历深度图。

基于BFS的地面点云去除算法的伪代码框图如图3所示。考虑到实际应用中激光雷达最先扫描到地面,地面点云往往出现在深度图的底部,小于地面角度阈值的节点被标记为地面点,这样就不会误将垂直的物体(如墙体)标记为地面点云。遍历深度图的每一列(图3中第2行),从深度图的地面点出发(图3中第4行,深度图最底层角度值为M_(0,c)),遍历所有未被标记的像素点。若深度图某点M_(r,c)与邻居节点 M(rn,cn)的角度差值低于指定的阈值(实验中设定为5°),则与邻居节点标记同为地面点,通过BFS算法遍历整个深度图,直到所有的地面点都已经标记完成,最终实现对地面点云数据的去除。

图 3. 地面点云去除的伪代码框图

Fig. 3. Pseudo-code graph of removing ground points

下载图片 查看所有图片

2.3 基于改进DBSCAN算法对非地面点云目标分割

文献[ 16]中提出了一种FS方法,即通过扫描线中的角度差判断是否为同一目标,但是对于稀疏点云目标往往易出现过分割问题。

DBSCAN算法作为一种有代表性的基于密度的聚类算法^[17],它能够在有噪声的空间数据中发现任意形状的类,有距离半径参数(eps)e_ps和最小数目(MinPts)M_inPts这两个参数,用于表示数据的稠密性。只有满足在e_ps范围内有足够多的数目才能成为核心点。利用DBSCAN算法直接对三维点云数据进行处理时存在两种不足。一方面,三维点云数据稀疏无规律,基于点云原始数据分割方法对场景的约束较小,具有一定抗噪声、抗遮挡等能力,但一般要求点云有较高密度,且提取目标特征的计算量一般较大,涉及到大量的循环遍历和搜索,往往并不满足实时性的要求。另一方面,DBSCAN算法中e_ps固定不变,而激光雷达的点云数据密度会随着扫描的距离变化而变化,距离激光雷达越近则数据密度越高,越远则数据密度越低,对于不同密度分布时,聚类效果较差,比如增大e_ps参数近距离目标容易出现欠分割问题,减小e_ps参数远距离目标容易出现过分割问题。

针对激光雷达应用,并结合深度图和DBSCAN算法特点,本文提出基于深度图的自适应参数的改进DBSCAN算法,一方面深度图是结构化形式,很容易找到临近点,提高了搜索速度,在深度图上8邻域范围选取代表点,搜索时间大大缩短,效率更高。另一方面,激光雷达点云的数据密度会随着扫描的距离变化而变化,距离激光雷达越近的数据密度越高,距离激光雷达越远的数据密度越低,e_ps参数应随搜索点与激光雷达的距离变化而变化,不应是固定的参数,而应是自适应的参数,与扫描距离相关,距离越远参数应越大。

因此,将自适应参数e_ps定义为

eps=ρx2+y2+z2L+1,(7)

式中:L为聚类区域步长;ρ为聚类半径系数;(x,y,z)为该数据点在LiDAR坐标系下的三维坐标。

图4(a)为角度距离示意图,图中O点为激光雷达的位置,三维激光雷达旋转过程中扫描线OA、OB与物体相交于A、B两点,OA与AB之间的角度为β。点云目标分割的关键在于: 对于任意两个扫描点是否来自同一个目标。如图4(b)所示,两个相邻目标已被标注为不同的颜色,水平旋转的激光器扫描周围的物体时,在同一物体上留下了较大的角度,不同物体产生的角度较小,因此可以充分利用这一特性,大于角度阈值可认为这两点为同一物体。这一思想较好地处理了相邻目标欠分割的问题。OA与AB之间的角度β表示为

β=arctanBH/HA=arctan[(d2sinω)/(d1-d2cosω)],(8)

式中:d₂和d₁分别为扫描线OA、OB的距离;ω为扫描线OA与OB水平方向上的角度值。所提改进的DBSCAN算法在判断是否为核心点时不仅考虑了空间欧氏距离,还加入了角度距离。

图 4. 角度距离和激光扫描目标示意图。(a)角度距离;(b)激光器扫描相邻的两个目标

Fig. 4. Angle distance and laser scanning target diagrams. (a) angle distance; (b) laser scanning two adjacent targets

下载图片 查看所有图片

基于深度图和改进DBSCAN算法对非地面点云目标分割的伪代码框图如图5所示,遍历深度图还未被标记的点(图5中第5行,标记深度图中第r行第c列为L_c,r),在深度图8邻域范围搜索eps半径下邻居节点的数目,同时考虑与邻居点的空间距离和角度距离(图5中第21行)。

图 5. 基于深度图的DBSCAN伪代码框图

Fig. 5. Pseudo-code graph of depth image-based DBSCAN

下载图片 查看所有图片

3 实验分析与讨论

为了验证本文提出的点云分割方法的实时性和分割精度,以文献[ 18]公开的街道数据集作为算法的测试样本,实验数据采集于美国Velodyne公司HDL-64型激光雷达,其有64个激光器,工作频率为10 Hz,可以实现2°~-25°角度调节,提供极好的垂直视野,水平视野可达360°,计算所使用的电脑配置为:INTEL 3GHz i7-7700CPU,8 GB内存。编程环境为C++及OpenCV,并使用OpenGL进行显示。

在数据集中随机抽取200 frame激光雷达数据进行实验,地面点云去除的效果如图6所示,去除地面效果较明显。比较欧氏聚类、原始DBSCAN算法和本文提出的基于深度图的改进DBSCAN算法在时间效率和分割效果上的优劣。欧氏聚类算法是一种常用的聚类分割方法,主要思想是使用欧氏距离来度量不同点之间的远近,不同聚类簇间的距离很大,而同一聚类簇内数据点的距离较小。图7对比了欧氏聚类算法、原始DBSCAN算法和本文提出的基于深度图的改进DBSCAN算法在多帧点云数据上的时间效率。欧氏聚类算法和原始DBSCAN算法的平均运行时间分别为1510 ms 和4815 ms,本文提出的基于深度图的自适应DBSCAN算法的平均运行时间为101.7 ms,时间效率上有很大的提升,约为原始DBSCAN算法时间效率的48倍。同时,相对于传统聚类算法,基于深度图的改进DBSCAN算法在不同帧点云数据时间效率较为稳定,没有较大的起伏变化。针对海量点云数据进行聚类处理时,本文方法具有很大的优势,这对于对实时性和稳定性要求很高的智能汽车尤为重要。

图 6. 地面点云去除结果。(a)原始点云数据;(b)去除地面点云后

Fig. 6. Ground point cloud extraction result. (a) Original point cloud data; (b) ground point cloud extraction

下载图片 查看所有图片

图 7. 分割算法的时间效率对比

Fig. 7. Time consumption comparison of segmentation algorithms

下载图片 查看所有图片

为了对比非地面点云目标分割方法,选取FS算法进行对比。FS算法利用不同目标的角度差异实现对目标的分割,在对比实验中角度值设为10°,本文提出的方法设定M_inPts=2,如图8所示,不同的物体用不同的颜色来显示。FS算法较为依赖阈值参数的设定,图中将在激光雷达附近的两个相邻汽车分割成同一个目标,出现了欠分割问题,而本文提出的方法很好地分割了这两个相邻目标,自适应e_ps参数较好地避免了欠分割和过分割问题。为了进一步衡量分割算法的准确度,线下通过对激光雷达数据随机选取410个目标并进行人工标记,以此作为准确率A_cc计算的参考,准确分割的目标数量S₁占总目标数量S的比例为

Acc=S1S。(9)

图 8. 点云目标分割结果。(a)FS算法;(b)所提算法

Fig. 8. Point cloud target segmentation results. (a) FS algorithm; (b) proposed algorithm

下载图片 查看所有图片

分别通过两种算法进行处理,得出每种算法的S₁,计算这两种算法目标分割的准确率,最终本文提出的算法的准确率达到了85.02%,而FS算法的准确率只有74.4%,所提算法的准确率提高了约10%,能够有效地提高点云目标分割的准确度,取得了较好的效果。

4 结论

提出了一种基于深度图的三维激光雷达点云目标FS方法,通过角度阈值法去除地面点云,采用改进DBSCAN算法来改善固有参数的缺陷,同时考虑空间欧氏聚类和角度距离,较好地克服了相邻目标的欠分割问题,并结合深度图提升搜索速度,实时性进一步得到保障,最终实现对非地面点云目标的FS。通过实验进行验证,结果表明该方法的时间效率远高于原始DBSCAN算法,提高了约48倍,同时在分割效果上也优于其他方法,相较于FS算法,本文提出的方法在准确度提升了近10%,为点云目标的FS提供了一种新思路,是一种较为有效的方法。

点云目标分割研究目前大多数仍采取先地面点云去除再目标分割的处理方式,然而,地面点云去除操作很大程度上影响后续点云目标分割的准确度,对点云目标分割实现端到端处理是未来的研究方向。同时考虑到无人车在恶劣天气、雾霾等情况下。激光雷达自身工作特性,为了保证无人车较高的安全性要求,多种传感器相融合的处理方式可能是较为稳妥的方式。