一种结构化道路环境的障碍物检测方法*

王东生

（南京理工大学计算机科学与工程学院 南京 210094）

1 引言

无人驾驶系统中的核心任务之一是障碍物检测，激光雷达作为一种高精度距离传感器，具有探测范围广，受光照等环境因素影响小等优点［1］，被广泛应用于障碍物检测中。激光雷达获取的数据称为点云，基于点云进行障碍物检测是无人驾驶系统中的关键技术之一。

聚类算法能够将特征相近的数据聚为一类，可以用于从点云数据中提取障碍物。常见的聚类算法可以分为基于划分的聚类算法、基于网格的聚类算法、基于密度的聚类算法。K-Means算法是划分聚类算法的代表，该算法实现简单，运行速度快，但是需要预先给定聚类个数，且受噪声数据影响较大［2～4］。基于网格的聚类算法将数据空间划分为网格单元结构，再对网格进行计算和聚类，该类方法受网格划分精度影响较大，且需要进行特殊的边缘 处 理［5～8］。DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法是经典的基于密度的聚类算法，该方法不需要预先给出聚类个数，可以检测出任何形状的类别，同时可以检测出噪声数据［9～11］。

本文针对无人驾驶车辆行驶在结构化道路的场景，结合多线激光雷达的特点，提出了一种基于数据分布密度的加权RANSAC（Random Sample Consensus）直线检测算法以及一种基于动态阈值的DBSCAN（Dynamic Threshold Density-Based Spatial Clustering of Applications with Noise，DT-DBSCAN）聚类算法。实验表明，本文方法可以满足无人驾驶系统实时性的要求，经过改进后提高了检测的鲁棒性和准确率。

2 感兴趣区域提取

在结构化道路场景中，无人驾驶车辆行驶的感兴趣区域（Region of Interest，ROI）为道路区域，虽然激光雷达可以感知到道路区域以外的环境信息，但该信息对于无人驾驶系统意义不大。因此提取出感兴趣区域可以减少噪声的干扰，同时可以提升障碍物检测的速度。

2.1 多线激光雷达的数据分布

多线激光雷达在工作时向外界发射一簇具有固定垂直角分辨率的激光束，反射回来的激光经过处理即可获得外界环境信息。激光雷达的工作原理决定了点云数据的“近密远疏”性质，即同样大小的障碍物，在近处可以得到密集的点云数据，而在远处只能得到稀疏的点云数据。另一方面由于激光不具有穿透性，当近处的物体挡住了激光后，相同方向更远处的障碍物将不能被感知到，这也加剧了点云数据的“近密远疏”性质。

图1 点云数据的近密远疏性质

2.2 加权RANSAC直线检测算法

Hough 变换常用于检测二维图像中的直线，它将图像空间中的直线映射到参数空间，然后在参数空间检测直线，该方法的检测精度和检测速率受限于参数空间中角度的分辨率［12］，但难以应用于三维数据。RANSAC［13］（随机抽样一致性算法，Random Sampling Consensus）广泛应用于特征匹配、矩阵估计等计算机视觉领域［14］，具有极强的鲁棒性［15］，可用于直线检测［16］、平面检测［17］等。

结构化道路的道路边界具有重要意义，它限制了无人驾驶系统的可通行区域。本文结合激光雷达点云数据的分布特点，提出了改进的加权RANSAC直线检测算法。算法具体流程如下：

1）输入当前点云数据；

2）任意选取两个不同的点并确定一条直线L；计算与直线L距离小于D的点的个数N；

3）记录并更新N的最大值Nmax及对应的直线参数P；

4）Repeat；

5）输出最优的直线方程。

根据激光雷达点云数据的特性可知，近处的道路边界反射回来的点数量较多，远处的道路边界反射回来的点数量较少，数据分布不均匀。为了解决这个问题，本文改进了RANSAC直线检测算法中直线上的点的计算方法。原始的计算方法如下：

其中L为当前拟合的直线，D为判断点在直线上的阈值，pi代表点的坐标，F定义如下：

其中dis(L,pi)表示点到直线的距离。

上述计算方法中，没有考虑到数据分布不均的特性，近处的点和远处的点被同等对待，很有可能因为近处的点过于密集从而造成误判。改进的思路是利用数据分布的特性，密集区域内的数据对最终计数结果贡献应该稍低，而稀疏区域内的数据对最终计数结果贡献应该稍高，改进后的F定义如下：

其中O表示坐标原点，L为当前拟合的直线，D为判断点在直线上的阈值，pi代表点的坐标，dis(O,pi)表示两点之间的距离，W表示权重系数。

改进后的计算方法充分考虑了激光雷达点云数据分布不均的特性，在进行计数时，所有的点的计数贡献最大为1，最小为0，且密集区域内的数据贡献更小，稀疏区域内的数据贡献更大。

2.3 ROI提取

根据上述方法检测出道边后，可以从数据中提取出感兴趣区域。假设道边的直线方程为

则感兴趣区域内的点pi(xi,yi,zi)满足：

根据上式可以提取出感兴趣区域。

3 基于动态阈值的DBSCAN 障碍物检测方法

3.1 DBSCAN聚类方法

DBSCAN 是经典的聚类方法，该方法以密度为标准将数据划分为核心点、噪声点，再将距离较近的核心点聚集为一簇，同时将距离某一簇较近的噪声点加入该簇，作为该簇的边界点。该方法的优势在于不需要预先确定聚类的个数，同时可以发现任何形状的类，缺点是参数受实际场景影响较大。DBSCAN算法流程如下：

1）初始化参数扫描半径Eps，类别包含的最小点数MinPts；

2）以Eps为半径扫描点p的邻居点，根据邻居点的个数判断p为核心点还是边界点；

3）若p是核心点，记录p的邻居节点（距离小于Eps），称p和这些点直接密度可达；

4）重复2）、3）直到所有点被遍历；

5）对于每一个核心点，将该核心点和其直接密度可达的核心点聚为一类；

6）将距离小于Eps的类进行合并，直到所有的类都不能继续合并，即找到了所有的最大密度相连点集合；

7）将距离某一类距离小于Eps的噪声点加入该类，称为边界点；

8）输出所有的聚类结果。

3.2 DT-DBSCAN聚类方法

DBSCAN 算法中，Eps和MinPts的选取至关重要，原始的DBSCAN算法常根据实际应用场景选择固定的参数，该方法在数据分布较为均匀的情况下效果较好。当数据分布不均时，单一的参数无法作用于全局数据，在某些区域可以获得较好的检测效果，然而在另外一些区域检测效果往往较差。激光雷达点云数据正是分布不均匀的，如果使用单一的参数，难以同时保证远处、近处的检测效果。

针对该问题，本文结合激光雷达点云数据分布不均的特性，提出了基于动态阈值的DBSCAN的算法。该方法考虑了数据分布不均的情况，可以同时兼顾所有区域的检测效果。点pi(xi,yi,zi)处的参数取值为

其中pi(xi,yi,zi)表示当前点的坐标，WEps,WMinPts表示权重系数。

4 实验结果及分析

本节通过实验及分析，验证了改进后的RANSAC 直线检测算法的准确率优势和DT-DBSCAN算法在分布不均匀的数据中的优势。本文先在KITTI［18］道路数据集上进行实验，对多个场景进行感兴趣区域提取和障碍物检测，对比和分析了改进前后的检测性能与结果。然后还使用实际场景数据验证和评估算法性能。实验环境为Intel i5-9300H@2.4GHz，8G内存，Windows10操作系统。

4.1 KITTI数据集评估

KITTI数据集由德国卡尔斯鲁厄理工学院和丰田美国技术研究院联合主办，是经典的自动驾驶场景下的计算机算法评估数据集。该数据集包含市区、乡村和高速公路等场景采集的真实图像数据，可满足不同的测试要求。本文选取了不同场景下的数据进行直线检测与障碍物检测，并对比了改进前后的检测结果。

图2 给出了KITTI 数据集456 号场景下的直线检测结果，其中灰色线段代表改进前的原始RANSAC 直线检测算法结果，白色线段代表改进后的加权RANSAC 直线检测算法结果。该场景下感兴趣区域内障碍物较少，故激光雷达感知的道路边界信息较为完整。对比检测结果可以发现，原始的RANSAC 直线检测算法与实际道边位置偏差较大，加权RANSAC 直线检测算法得到结果更符合实际道边位置，误差更小。这是因为原始的RANSAC直线检测算法没有考虑点云数据分布不均的特性，近处的数据较多因此算法结果受近处数据影响较大，在远处出现偏差。改进后的加权RANSAC 直线检测算法考虑了数据分布不均的特性，取得了更好的检测结果，在远处的偏差更小。

图2 KITTI456直线检测结果对比

图3 给出了KITTI 数据集2345 号场景下的直线检测结果。其中灰色线段代表改进前的原始RANSAC 直线检测算法结果，白色线段代表改进后的加权RANSAC 直线检测算法结果。该场景下感兴趣区域内障碍物较多，故激光雷达感知的道路边界信息不完整，点云数据中表示道边的数据整体上更少。该场景中远处的数据更少，因此改进前后的算法检测结果相近。这表明了加权RANSAC 直线检测算法保留了RANSAC 直线检测算法的中心思想，在数据分布相对均匀的时候可以获得相近的结果，在数据分布不均的时候也可以获得更好的结果。

图3 KITTI2345直线检测结果对比

图4 和图5 分别给出了DBSCAN 算法和DT-DBSCAN 算法的检测结果，检测得到的障碍物由白色包围框给出定位。从图中可以看出，改进前后的算法在近处场景的检测结果相近，DBSCAN 算法没能检测出较远的障碍物，而DT-DBSCAN 算法检测出了远方的障碍物。在该场景中，道路左半部分有两辆车，右半部分有四棵树，它们均是感兴趣区域中的障碍物，无人驾驶车辆在行驶时需要避开。由于激光雷达点云数据分布的不均匀性，单一阈值无法很好地作用于整体数据，如果为了检测出远方的障碍物而放宽阈值限制，那么近处的单个障碍物可能会被分割为多个，近处的噪声也可能被误检测为障碍物，如果使用严格的阈值，远处的障碍物由于数据较少很可能无法被检测到。改进后的DT-DBSCAN 算法解决了上述问题，检测出了近处和远处的障碍物，效果优于DBSCAN算法。

图4 KITTI456改进前障碍物检测结果

图5 KITTI456改进后障碍物检测结果

4.2 实际场景数据评估

在实际公路场景中采集数据，以评估本文提出的障碍物检测方法。

由图6 可以看出，本文提出的方法在直线检测结果和障碍物检测结果中均优于改进前的算法，其中灰色直线和灰色框代表改进之前的检测结果，白色直线和白色框代表改进之后的检测结果，最近的障碍物距离为50m 远，最远的障碍物距离为180m远，因距离较远故图中显示的点云数据较为稀疏。改进之后的加权RANSAC 算法检测出的直线误差更小；改进之后的DT-DBSCAN 算法除了能够检测出近处的障碍物，甚至能够检测出了180m 外超远距离的障碍物。实验随机选取了多帧场景并统计了检测结果的误差，如表1、表2所示。

图6 实际场景检测结果对比

表1 改进前后的直线检测算法比较

表2 改进前后的障碍物检测算法比较

4.3 结果分析

由实验结果可知，本文提出的障碍物检测算法得到了很好的验证。加权RANSAC 直线检测算法克服了数据分布不均带来的问题，整体误差较小，而改进前的直线检测算法受近处数据影响较大，部分场景下在远处的检测结果误差很大，由表1 可知改进后的算法误差平均误差减小了0.27m。DT-DBSCAN 算法同时保证了近处和远处的聚类效果，近处的大目标和远处的小目标都能被检测到。经过多次实验验证，本文方法障碍物检测成功率86.8%，比改进前提高了15.4%，可以满足实际场景需求。

5 结语

针对结构化道路的无人驾驶场本文提出了一种障碍物检测方法，具体包括加权RANSAC直线检测算法与DT-DBSCAN 聚类算法。加权RANSAC直线检测算法在原有算法的基础上考虑了点云数据分布不均的特性，解决了检测结果受局部数据影响过大的问题。DT-DBSCAN 算法用于检测障碍物，该方法解决了DBSCAN 算法阈值单一的问题，考虑了数据的分布不均特性，在近处和远处都有较好的检测结果。本文的研究场景为结构化道路场景，场景特征比较明显，噪声较少，如何在半结构化道路甚至是非结构化道路中实现障碍物检测还需要进一步的研究。