1 引言

城市道路环境以其复杂、多变、规模大等特点成为当前自动驾驶领域研究的热点和难点^[1-5]。在城市三维环境下,多线激光雷达(LiDAR)扫描通常会得到密度不均匀的点云数据集,并且传感器的局限性、采集设备的固有噪声、场景中物体表面的反射特性等会不可避免地使点云数据产生大量的离群点。噪声点的存在会严重影响后续点云的特征提取和特征匹配。因此,有必要对原始点云进行滤波操作,以获得适合进一步处理的精确点云。Fleishman等^[6]对双边滤波进行改进,并拓展到三维网格模型上,提出针对网格降噪的双边滤波算法,该算法通过对影响域和空间域赋予不同的权值函数来进行各向异性的去噪,具有良好的降噪效果,且能够保持点模型的几何特征,但不能很好地对离群点加以处理,易削去模型中最尖锐的部分。聂建辉等^[7]在分析点云离群点数据产生的原因后引入数据挖掘分类算法,将离群点分为远离群点和近离群点两类,并采用基于三维区域增长的方法识别远离群点,使用基于曲面变化度的局部离群系数方法识别近离群点,该算法可以有效识别离群点数据并进行去噪。李仁忠等^[8]提出一种基于方法库的点云模型去噪与精简算法,依据噪声点到模型主体的距离,利用统计滤波结合半径滤波去除大尺度噪声。苏本跃等^[9]用K-means聚类算法对点云进行聚类,根据点到聚类中心的欧氏距离和邻近点曲率变化判断每个类中的点是否为噪声点,进而去除大量外部噪声点。然而上述方法均不适用于大规模散乱点云(如城市环境)的去噪处理。

鉴于上述算法的局限性,本文提出了一种针对大规模散乱点云的去噪算法。该算法首先对三维LiDAR点云进行体素栅格划分,然后确定核心点、搜索栅格邻域、划分每个栅格的簇类,最终将目标点云聚类,使目标点云与离群点云分离,从而达到滤除离群噪点的目的。该算法在去除离群噪点和冗余信息、降低点云数量规模的同时还能保留点云的特征信息,不损坏点云的细节信息,提高了后续点云匹配的精确度,且缩短了匹配耗时。

2 基于密度的带噪声数据空间聚类算法

基于密度的带噪声数据空间聚类算法(DBSCAN)是第一个基于密度的聚类算法,由Ester等^[10]于1996年提出。该算法将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇,并可在存在噪声的数据中发现任意形状的聚类。该算法的显著优点是聚类速度快,且能有效处理噪声点。

DBSCAN算法的核心思想总结如下:

该算法有两个参数,即Eps和MinPts,其中Eps表示目标数据点搜索邻域的半径,MinPts表示最小邻域点数。在图1中,如果c点的Eps邻域至少有MinPts个点,则c被称为核心点。搜索区域中的点将重复聚类,直到仅剩下Eps邻域内点数小于MinPts的数据点。点b在点p的Eps邻域内,但点b的Eps邻域内的点数小于MinPts,因此,b点被标记为边界点(b不是核心点,但落在某个核心点的Eps邻域内)。点o的邻域点数少于MinPts,因此不能成为新的簇。

图 1. DBSCAN算法的核心思想

Fig. 1. Core idea of DBSCAN algorithm

下载图片 查看所有图片

3 基于体素栅格的快速密度聚类算法

密度聚类算法可以通过选择合适的阈值将目标点云与离群点分离,达到去除离群点的目的。在大规模散乱点云数据的处理中,由于噪声的数目、分布均未知,所以DBSCAN算法能够较好地应用在此类问题中。但是在DBSCAN算法和基于相对密度的聚类方法中,每个对象点必须与数据集中众多的其他对象点进行比较。为了降低执行时间成本,本研究对DBSCAN算法进行了改进,提出了一种基于体素栅格的快速密度聚类(VG-DBSCAN)算法,利用该算法对点云进行滤除离群噪点的处理。

VG-DBSCAN算法将三维点云数据按照维度划分为以体素栅格为单元的多个相邻的区间,创建一个由栅格单元组成的集合,以此来大幅减小每个对象在数据空间中邻域的搜索范围,只要考察当前对象的空间相邻栅格单元就能实现其邻域的搜索,快速发现各个聚类。VG-DBSCAN算法的具体步骤如下。

步骤1:划分体素栅格。如图2(a)所示,构建一个三维体素栅格,并将三维LiDAR点云数据的每个数据点划分给它所在的栅格单元。每个单元栅格的对角线长度是Eps,这意味着栅格单元的边长为 Eps/312,如图2(b)所示。如此设定单元格大小的

图 2. 划分三维体素栅格。(a)三维体素栅格;(b)体素单元格

Fig. 2. Dividing a three-dimensional voxel grid. (a) Three-dimensional voxel grid; (b) voxel cell

下载图片 查看所有图片

意义在于如果栅格内的点数大于MinPts,则能够直接将所有这些包含于该体素栅格单元的点标记为核心点。因为体素栅格内任意两点在栅格内的最大距离不大于Eps,所以如果体素栅格内有大于MinPts数量的数据点,那么单元格内任意点的Eps邻域至少包含MinPts个点。

在构建栅格之前,首先需要确定6个值,即三维点云数据X、Y、Z轴的最大坐标值和最小坐标值。通过这6个值和体素栅格的边长就可以确定栅格的行数n_rows、列数n_cols和层数n_lays,然后计算每个数据点所属的体素栅格。对于体素栅格边界上的点,将其分配在右上方的栅格中。如果有一个数据点正好位于栅格的最顶部或最右边体素栅格的边界上,这时应添加一个额外的行、列、层,用以囊括该点,以防止将其分配到栅格外部。

步骤2:确定核心点。该步骤将遍历所有的非空体素栅格。要查找栅格内的所有核心点,首先必须检查该单元格内的点数是否大于MinPts。如果是,则将所有这些点标记为核心点;如果不是,则必须检查该单元格内的每个点,并确定它是否为核心点。要确定点p(p∈C)是否是核心点,需要检查该点所在栅格的相邻栅格N_Eps(C)内的一些点。N_Eps(C)定义为某个体素栅格单元C及其相邻的栅格单元C'的集合,即N_Eps(C)={C,C'|dist(C,C')≤Eps}。

图3为体素栅格某层的二维示意图,可以看到:对于三维体素栅格,最多需要检查124个栅格单元。计算这些栅格中每个点与p之间的距离。当这些单元栅格内的所有点已被检查过,或者当发现p的Eps邻域内的点数大于等于MinPts时,终止查找。

图 3. 体素栅格某层的二维示意图

Fig. 3. Two-dimensional schematic of a layer of a voxel grid

下载图片 查看所有图片

步骤3:合并簇。如果两个不同单元中的两个核心点之间的距离小于等于Eps,则这两个点属于同一个簇。举个简单的例子,如图4所示,相邻的两个栅格单元中各含有4个数据点,假设MinPts=3,则两个栅格单元内的所有点都是核心点。如果a与b之间的距离小于等于Eps,则可以得出这8个点都属于同一个簇的结论。否则,划分为两个各含有4个点的簇。

图 4. 合并簇的简例

Fig. 4. Simplified example of a merged cluster

下载图片 查看所有图片

步骤4:确定边界点和离群噪点。这是VG-DBSCAN算法的最后一步,这一步通过遍历所有非核心点来完成。如果在N_Eps(C)中存在至少一个核心点,并且最靠近p的核心点属于簇clusters_1,则非核心点p是簇clusters_1的边界点。完成上述4个步骤之后,所有不是核心点或边界点的数据点都会被标记为离群噪点。

通过上述4个步骤可以快速聚类目标点云,使其与离群噪点分离,滤除被标记为离群噪点的数据点即达到了点云去噪的目的。

4 实验结果与分析

为了验证所提算法的正确性和有效性,采用Velodyne HDL-64E型64线LiDAR采集城市复杂动态环境下的三维点云数据,并将其作为研究对象。实验平台为Intel(R) Core(TM) i7-6700 CPU@3.40 GHz,16 GB随机存取存储器(RAM),Unbuntu 16.04操作系统,Qt Creator5.7开发环境,开发语言为C++。首先,选取连续1000帧经过地面分割处理的点云数据,这些点云中均含有大量的动静态障碍物,如机动车、非机动车、行人等,同时含有大量的离群点。然后,通过所提算法对点云进行滤除离群噪点处理,并与开源点云库PCL·1.8.1dev中具有代表性的统计滤波去噪算法和半径滤波去噪算法进行对比,实验结果如图5~9和表1所示。图5是一帧经过地面分割处理的原始三维点云数据,可以看出,原始点云数据分布稀疏杂乱且含有大量离群噪点。图6是统计滤波去噪算法的结果,该算法的主要参数是MeanK,用于确定平均距离估计时的最近邻点数。图7是半径滤波去噪算法的结果,该算法的主要参数是阈值MinNeighbors,该阈值是半径最近邻内所包含的最小点数。图8是所提算法对点云去噪处理的结果。参数MinPts与MeanK、MinNeighbors的含义基本类似,都是确定邻域内点云的数量,所以3种算法均以这一参数为变量进行了对比实验。结果显示,这3个参数设置过大都会对点云数据进行过度处理,即去除了部分小的障碍物,但参数在一定的范围内可以保证3种算法在去除离群噪点的同时保留障碍物的局部特征信息,并在一定程度上降低了点云的规模。图9(b)所示为图8(c)中的局部,可以看出:所提算法能够很好地聚类主要的目标物,使其与噪声点分离,并滤除这些离群噪点。

图 5. 原始点云

Fig. 5. Original point-cloud

下载图片 查看所有图片

图 6. 统计滤波去噪算法的结果。(a) MeanK=10; (b) MeanK=30; (c) MeanK=50

Fig. 6. Results using statistical outlier removal algorithm.(a) MeanK=10; (b) MeanK=30; (c) MeanK=50

下载图片 查看所有图片

图 7. 半径滤波去噪算法的结果。 (a) MinNeighbors=5; (b) MinNeighbors=10; (c) MinNeighbors=15

Fig. 7. Results using radius outlier removal algorithm. (a) MinNeighbors=5; (b) MinNeighbors=10; (c) MinNeighbors=15

下载图片 查看所有图片

图 8. VG-DBSCAN算法的去噪结果。(a) Eps=1, MinPts=10; (b) Eps=1, MinPts=15; (c) Eps=1, MinPts=20

Fig. 8. Denoising results using VG-DBSCAN algorithm. (a) Eps=1, MinPts=10; (b) Eps=1, MinPts=15; (c) Eps=1, MinPts=20

下载图片 查看所有图片

图 9. VG-DBSCAN算法去噪的局部效果。(a)去噪前;(b)去噪后

Fig. 9. Local denoising results using VG-DBSCAN algorithm. (a) Before denoising; (b) after denoising

下载图片 查看所有图片

表1统计了1000帧点云处理结果的平均水平,包括去噪前、后点云数量以及处理耗时这3个指标的平均值。从表1可以看出:3种算法在去噪前、后的点云数量上基本持平,但是处理时间相差悬殊,统计滤波去噪算法的耗时约为200 ms,并且耗时随着参数MeanK的增大而增大;半径滤波去噪算法的耗时约为470 ms,且耗时不会随着参数MinNeighbors的变化而发生明显变化;所提算法的耗时约为100 ms,耗时随参数MinPts的增大而增大,但增加幅度不大(与统计滤波去噪算法相比)。综上所述,相比于其他两种典型算法,所提算法在点云去噪、简化以及耗时方面均有优势。

为了验证所提算法对点云帧间匹配的改善效果,使用开源库PCL·1.8.1dev中的匹配算法——广义迭代最近点(GICP)算法对点云去噪处理前后的帧间匹配进行了对比实验。实验结果如图10和表2所示。将欧氏适应度^[11]作为点云匹配准确度的衡量标准,欧氏适应度为参与匹配的两帧点云中各对应点对之间欧氏距离的平方和。表2的数据表明,经过预处理的点云在规模上得到了大幅度简化,基本上滤除了所有的离群噪点,这使得帧间匹配的精确度提高了2倍,且匹配耗时仅为之前的1/3。

图 10. 去噪后点云帧间的匹配结果。(a)匹配前;(b)匹配后

Fig. 10. Point-cloud-matching results after denoising. (a) Before matching; (b) after matching

下载图片 查看所有图片

5 结论

提出了一种应用于城市复杂环境下散乱三维LiDAR点云的去噪算法——VG-DBSCAN算法。该算法采用点云三维体素栅格划分的形式对传统DBSCAN算法进行改进,将点云囊括进每个栅格中,创建一个由栅格单元组成的集合,以此来大幅减小每个对象在数据空间中邻域的搜索范围,实现点云的快速目标聚类,达到分离出离群噪点的目的。通过与点云处理开源库中具有代表性的统计滤波和半径滤波算法进行对比,证明了所提算法能够在保证点云三维几何特征的同时实时处理点云数据,而且可以有效识别并滤除点云中的离群噪点,在点云去噪、简化以及耗时方面均优于现有的典型算法。之后,采用该算法对帧间匹配前两帧点云进行去噪处理,实验结果证明了所提算法可以显著提高匹配的准确度并减少匹配耗时。综上,所提点云去噪算法可以实时为点云帧间匹配提供更优质的点云数据。