基于改进DBSCAN算法的激光雷达水面目标检测

叶 晟 徐海祥 冯 辉

(高性能船舶技术教育重点实验室1) 武汉 430063) (武汉理工大学船海与能源动力工程学院2) 武汉 430063)

0 引 言

激光雷达具有测量精度高、响应速度快、抗干扰能力强、对环境全向感知，可以得到障碍目标的深度信息等优点，因此被广泛应用于无人系统的感知领域，比如，无人机的道路勘测、地图绘制，无人车领域的道路检测、行人检测、车辆检测，无人艇自主靠离泊过程中对港口泊位的检测等[1].激光雷达目标检测可分为传统方法的目标检测和基于机器学习方法的目标检测，其关键就是激光雷达点云的聚类.常用的聚类方法主要有基于划分的方法，如K-Means算法[2-3]、基于(坡度、相似程度、曲率、曲面法向量等)区域增长的聚类算法[4-6]、基于空间距离远近的欧式聚类算法[7-9]、具有噪声的基于密度的聚类算法(density-based spatial clustering of applications with noise, DBSCAN)等.DBSCAN算法聚类时主要依靠数据的疏密程度对数据进行划分，可以发现不同形状的点云集合，对噪声点不敏感，无需事先确定障碍物个数，因此被广泛应用于激光雷达点云目标的检测.

夏鲁宁等[10]在DBSCAN的基础上提出了SA-DBSCAN聚类算法，通过k-dist图来选取邻域值ε，通过绘图求得噪声值曲线与坐标轴第一象限平分线的交点横坐标作为密度阈值Minpts.王光等[11]采用核密度估计确定邻域值ε和密度阈值Minpts的合理区间，通过分析数据局部密度特点确定簇数，然后根据合理区间内的参数值进行聚类.蔡怀宇等[12]利用在地面上反射的激光雷达扫描线的分布特点，将激光雷达高度视为单位1，从而建立了一个ε表对点云进行聚类.宫铭钱等[13]根据三维激光雷达对立体物体的相邻两次扫描结果，计算扫描线的间隔乘以Minpts从而建立ε表，对激光雷达目标检测.

文中提出了一种自适应参数的改进DBSCAN算法，在一定的密度阈值Minpts下，对每一个点云采取随距离自适应增大的邻域值ε，并设定一个合适的邻域下限，这样既保留了传统的DBSCAN在近距离点云聚类时的优点，又能对远距离的点云正确地聚类.通过实验对比了传统的DBSCAN算法和改进之后的DBSCAN算法对无人艇采集的障碍物点云数据聚类的性能.实验结果表明，改进之后的DBSCAN聚类算法，能够自适应地选取邻域值ε和密度阈值Minpts两个重要参数，对于无人艇采集的障碍物点云数据能够实现较好的聚类效果.

1 传统DBSCAN聚类算法

DBSCAN聚类算法针对的是点云的密度对点云进行聚类，其核心思想是根据点云的疏密程度，将点云密度超过密度阈值的点聚成类，将其他的低于密度阈值的点归类成噪声点.其主要步骤如下.

步骤1根据数据集特点选取合适的邻域值ε和密度阈值Minpts，把所有数据点标记为未处理.

步骤2随机的选择一个点Pi，对Pi的ε邻域内的点数进行统计.如果大于或等于Minpts，把Pi标记为核心点，并新建一个类别.以Pi为起点，寻找与Pi密度相连的点，找到密度相连点的最大集合.如果小于Minpts，把Pi标记为噪声点.

步骤3选择数据集中的另一个点，重复步骤2，直到所有的点标记为已处理.

传统的DBSCAN算法在应用于激光雷达水面目标检测时，有以下优缺点.

1)优点 ①可以对任意形状点集聚类，发现不同形状的目标 相较于K-means算法只能对凸数据集聚类、需要事先确定聚类目标个数的局限性，DBSCAN算法具有能够对不同形状的数据集聚类、无需事先确定障碍物个数的优点；②可以有效剔除数据集中的异常点，降低数据预处理的难度 在无人车应用中，在点云预处理时通常需要进行地面点云分割，以排除地面点云对目标检测的干扰.而水面点云反射较少，使用DBSCAN算法聚类时，可以将少量的水面点云视为噪声点进行剔除，不会对聚类结果造成影响，所以应用DBSCAN算法对水面激光雷达点云聚类时，无需进行水面点云分割，省去了复杂的点云预处理步骤；③近距离点云聚类效果好 激光雷达点云是一种密度随着距离逐渐减小的不均匀数据集.而近距离部分的点云数据比较稠密，点云分布相对均匀，使用传统DBSCAN算法聚类时，聚类效果好.

2)缺点 ①参数选择困难 邻域值ε和密度阈值Minpts的选取会相互影响，需要对其联合调参，不同的参数组合对最后的聚类结果有较大的影响；②近距离的相邻目标容易被欠分割 传统DBSCAN算法选择固定不变的邻域值ε和密度阈值Minpts，在物体距离很近时，容易将它们聚类成同一物体，出现欠分割；③远距离目标容易被漏检 传统的DBSCAN算法中，选取了一个固定的邻域值ε和密度阈值Minpts，对于离激光雷达较远的点云，这些点云明显更为稀疏，其密度小于密度阈值Minpts，不满足核心点的判定，因而容易被漏检.

2 改进DBSCAN聚类算法

针对传统DBSCAN算法在应用于激光雷达水面目标检测时的缺点，提出一种自适应参数的改进DBSCAN算法.其核心思想如下：在一定的Minpts下，对于激光雷达的每一个点云选择随距离自适应增大的邻域值ε，使得点云稀疏区域采用较大的邻域值ε，从而保证对远距离的点云完成聚类.设置一个邻域值下限，相当于对近距离点云使用传统DBSCAN算法聚类，这样保留了传统DBSCAN算法在近距离点云聚类上的优势.

图1为VLP-16激光雷达扫描线扫描示意图，激光雷达扫面线扫描到挡板上时，相邻的两根扫描线的距离并不是相同的，相邻两根扫描线的间距与扫描线ID密切相关.而且，在同一扫描线上时，距离激光雷达越远，点云越稀疏.因此，通过相邻扫描线间距以及点云到激光雷达的距离计算点云的邻域值ε.

图1 VLP-16激光雷达扫描线扫描示意图

为了计算每个点云的邻域ε，首先计算相邻扫描线的间距ε*，建立ε*列表：

以VLP-16激光雷达为例，设定激光雷达到挡板距离为单位1.已知VLP-16激光雷达水平放置时，每一条扫描线俯仰角从大到小排列为15°,13°,…,1°,-1°,…,-13°,-15°，见表1.

表1 扫描线ID与俯仰角对应关系

扫描线俯仰角与ID关系为

βi=17-2*i

(1)

式中：βi为扫描线俯仰角；i为扫描线ID.

相邻扫描线间隔ε*等于扫描线在挡板上的反射点高度的差值，计算公式为

(2)

对于激光雷达点云中的任意一点P(x,y,z)，其邻域值ε为

(3)

(4)

式中：λ为修正系数；ε*为相邻扫描线间隔；k为点P的扫描线ID；ε0为邻域值下限.

k可以通过求出点P与水平面夹角，查表1获得.λ为修正系数，与激光雷达类型有关，文中使用雷达为VLP-16激光雷达，取λ=1.3.ε0为邻域值下限，是一个固定的数值，其大小与激光雷达类型有关，可以通过统计近距离出现过分割或视为噪声的目标点云，计算其邻域值ε的最大值获得，取ε0=0.23.ε0的设置主要为了防止距离激光雷达较近的点云的邻域值过小，而导致点云被过分割或者被检测为噪声的情况.

统计数据集中每一个点ε邻域内包含点的数量，并用其期望作为密度阈值Minpts.

(5)

式中：Pi为点i的ε邻域内包含的点的个数；n为点云的总数.

改进的DBSCAN算法的流程图见图2.

图2 改进DBSCAN算法流程图

3 实验结果与分析

为了验证上述改进DBSCAN算法的有效性，使用无人艇采集的水面障碍物点云数据集为研究对象.以16 GB内存、i7-9750处理器、2.6 GHz主频的计算机作为实验平台，并在Matlab2019a上编程实现.通过两个不同场景，采用传统DBSCAN算法和改进DBSCAN算法分别对点云聚类，并分析比较实验结果.

图3为原始点云和提取感兴趣区域后的待处理点云，图4a)为取ε=1，Minpts=40的传统DBSCAN聚类结果，图4b)为未设置邻域值下限ε0的改进DBSACN聚类结果，图4c)为设置邻域值下限ε0的改进DBSCAN聚类结果.

图3 原始点云和提取感兴趣区域后的待处理点云

图4 传统和改进DBSCAN聚类结果

在该实验场景下，包含有6个离激光雷达较近的障碍物，分别为：(-6,4,:)附近的障碍物1，(-2,4,:)附近的皮划艇和划皮划艇的人作为障碍物2和3，在点(1,5,:)附近的障碍物4，在(2,5,:)附近的两个距离接近的障碍物5和6.

由图4a)可知:传统的DBSCAN聚类算法，检测了4个目标，将相邻的障碍物2和障碍物3聚成了同一个类，将相邻的障碍物5和障碍物6聚成了同一个类.主要是因为DBSCAN算法选择固定不变的邻域值ε和密度阈值Minpts，在物体距离很近时，容易聚类成同一物体，出现欠分割.

由图4b)可知:未加入邻域值下限的改进DBSCAN算法在对距离激光雷达很近的相邻目标2,3的检测中，将目标2,3中的大部分点云检测为噪声.这是因为离激光雷达很近的点的邻域值选取得过小，使得其邻域内点数明显少于密度阈值Minpts，因此被检测为噪声.

由图4c)可知:加入邻域值下限后的改进DBSCAN算法，检测了6个目标，把距离激光雷达较近的相邻障碍物2，3以及距离激光雷达较近的相邻障碍物5，6明显地分割开来.这是因为改进的DBSCAN算法，每一个点的邻域值ε是独立的，近距离点云的邻域值ε选取相对较小，所以能够区分距离激光雷达较近的相邻目标.

实验表明，设置一个良好的邻域值下限后的改进DBSCAN算法，可以减少距离激光雷达较近的目标被检测为噪声的情况.改进的DBSCAN算法相较于传统的DBSCAN算法，在距离激光雷达较近的目标检测中有分割优势，减少了相邻的目标欠分割的情况.

图5为原始和提取感兴趣区域后的待处理点云，图6a)为取ε=1，Minpts=40的传统DBSCAN聚类结果，图6b)为未设置邻域值下限ε0的改进DBSACN聚类结果，图6c)为设置邻域值下限ε0的改进DBSCAN聚类结果.

图5 原始点云和提取感兴趣区域后的待处理点云

图6 传统和改进DBSCAN聚类结果

在该实验场景下，包含有6个障碍物.分别为4个近距离障碍物：(0,0,:)附近的障碍物1，(-2,0,:)附近的障碍物2，(-2,5,:)附近的障碍物3，在点(-8,3,:)附近的障碍物4.以及2个远距离障碍物：在(10,20,:)附近的大障碍物5，在(8,20,:)附近的小障碍物6.

由图6a)可知，传统的DBSCAN算法检测了离激光雷达较近的障碍物1、2、3、4，将距离激光雷达较远的大障碍物5的大部分点云检测为噪声，将距离激光雷达较远的小障碍物6的全部点云检测为噪声.这是因为在传统的DBSCAN算法中，选取了一个固定的邻域值ε和密度阈值Minpts，当它满足近距离的激光雷达目标检测时，对于离激光雷达较远的点云，这些点云明显更为稀疏，其密度小于密度阈值Minpts，不满足核心点的判定，因而无法被检测，所以结果距离激光雷达较远大障碍物5上的大量点云被检测为噪声，距离激光雷达较远的小障碍物6的全部点云都被检测为噪声.

由图6b)可知，未设置邻域值下限ε0的改进算法，将距离激光雷达很近的障碍物1检测为噪声，其他障碍物的检测结果与设置邻域值下限ε0后的改进之后的DBSCAN算法一致.

由图6c)可知，设置邻域值下限ε0后的改进之后的DBSCAN算法，既检测了离激光雷达较近的障碍物1、2、3、4，又检测了离激光雷达较远的两个障碍物5,6.这是因为改进的邻域值ε选取是随着距离自适应增大的，在一定的密度阈值Minpts下，远距离目标采用更大的邻域值ε，在点的ε范围内可以包含更多的点数，使得远距离障碍物点云满足核心点的判定，从而被算法检测到.

实验表明，设置一个合适的邻域值下限后的改进DBSCAN算法，可以减少距离激光雷达较近的目标的点云被检测为噪声的情况.改进的DBSCAN算法相较于传统的DBSCAN算法，在距离激光雷达较远的目标检测中有很大优势，减少了距离激光雷达较远的目标被漏检的情况.

实验中，对无人艇采集的连续帧的障碍物点云数据进行了聚类，其平均结果见表2.

表2 传统DBSCAN与改进DBSCAN各项指标对比

虽然平均耗时对比传统DBSCAN有所增加，但是增幅不大，可以满足在工程上的应用.对比于传统DBSCAN聚类算法，改进DBSCAN算法的正确率明显大于传统的DBSCAN聚类算法，提高了21.21%，丢失率下降了9.09%，这说明改进DBSCAN算法比传统DBSCAN算法分割更为准确.改进DBSCAN算法错误分割率降低了12.12%，这说明改进DBSCAN算法相较于传统DBSCAN算法分割更为精细.

综上所述，改进的DBSCAN算法较传统DBSCAN聚类算法，在近距离的目标检测中，可以减少检测目标被欠分割的情况，在远距离的目标检测中，可以减少检测目标被漏检的情况.在激光雷达水面目标检测中，改进的DBSCAN算法相比于传统的DBSCAN算法检测效果更好.

4 结 束 语

文中以无人艇采集的水面障碍物点云数据为研究对象，针对传统DBSCAN算法对邻域ε、密度阈值Minpts两个参数选取困难的问题，以及采用固定的邻域值ε和密度阈值Minpts难以对全部数据实现良好聚类的问题，提出了一种自适应参数的改进DBSCAN算法，对每一个点云采取独立的ε进行聚类.改进的方法降低了参数选择的难度，可以减少近距离目标目标被欠分割的情况，可以防止远距离目标被漏检的情况.通过传统DBSCAN算法与改进DBSCAN算法的对比，验证了改进DBSCAN算法的有效性.