基于车载16线激光雷达的障碍物检测方法

孔德明，段呈新，巴特·古森斯，王书涛

(1.燕山大学 电气工程学院，河北省 秦皇岛 066004；2.根特大学 通信与信息处理系，比利时 根特B-9000)

1 引 言

对周围环境的可靠感知是汽车辅助驾驶系统的重要任务，能准确检测行驶区域内障碍物目标既是辅助驾驶的基础，更是实现环境感知的前提[1]。在障碍物检测技术中，视觉相机和激光雷达都是较为常见的传感器[2]。与视觉相机相比，激光雷达不仅能够迅速获取大规模三维点云数据，提供环境的精确几何信息，并对光照强度变化、天气条件具有很强的鲁棒性，因此在障碍物检测任务中得到了广泛应用。基于激光雷达的障碍物检测可从单帧点云中区分不同障碍物所包含的点云数据，为后续的分类、跟踪等任务提供支持[3]。

目前，激光雷达障碍物检测主要有基于深度学习[4,5]和基于聚类[6]两种方式。其中基于深度学习的方法虽然检测精度高，但训练周期长且训练数据难以获取，算法设计难度大；而聚类方法因其强稳定性与实时性，广泛应用于检测任务。国内外学者对激光雷达聚类检测算法进行了大量研究，一般可分为基于特征、基于地面投影两类[7]。第一类研究直接以点云的三维空间特征进行聚类，该方法可以取得较好的聚类效果，但往往耗费时间较长。如李永强等[8]提出了一种改进的K均值聚类检测算法，段建民等[9]利用改进的密度聚类算法检测汽车前方区域障碍物，但以点出发迭代查询的时间复杂度高，这类方法更适用于少线束激光雷达数据；Sun Z等[10]采用固定距离阈值的方法完成多线雷达障碍物目标聚类，运算速度仍相对较慢。第二类研究将点云投影至俯视平面，以二维网格为单元进行障碍物的聚类检测，简单且高效，但其检测结果过于依赖网格参数设置。如娄新雨等[11]采用改进的二维网格空间方式聚类，以动态距离阈值快速聚类障碍物，但网格参数无法自适应调节，远距离障碍物检测准确率不高；谢德胜等[12]基于二维网格的八邻域拓展进行障碍物聚类，该方法耗时短，但网格划分过大容易造成多障碍物目标误检；为减小网格参数影响，Börcs A等[13]采用多级网格聚类形式，在粗网格聚类结果上划分子网格检测障碍物，实验证明该算法实时性较高且具有一定鲁棒性。

综合来看，网格处理方式更能满足多线激光雷达数据障碍物检测的需求，但最佳网格分辨率难以确定，导致检测结果存在一定的误差。此外，原始雷达数据存在噪声，点云分布不均匀，造成例如目标轮廓缺失、形变等情况发生，严重破坏了障碍物目标的几何特性[13]，这导致单帧点云的检测结果准确率不足，稳定性仍有待提高。

针对上述存在问题，为了提高16线激光雷达点云数据中障碍物目标检测准确率，本文基于网格聚类的分析策略对障碍物检测算法进行了优化设计。不同于传统网格聚类，该算法在快速去除地面点及高结构物体的基础上建立两级网格结构，以粗网格聚类结果为中心，依据分布离散度自适应的确定子网格分辨率，获取稠密子网格最大连通分量得到精确检测结果，并结合相邻时刻障碍物的状态信息对该结果进行修正，提高检测稳定性。实验表明:该算法能有效抑制道路中其余物体点云干扰，同时改进的网格聚类算法能大大缓解相邻障碍物过分割、稀疏障碍物欠分割问题，实现障碍物的准确检测。

2 基本原理

本文提出的基于参数自适应网格聚类的障碍物检测算法分为以下4步进行操作:地面点去除、高结构物体提取、基于自适应网格的目标聚类和检测结果修正。其中障碍物泛指在道路区域内出现的例如车辆、行人等可能会对车辆行驶造成障碍的特定物体[14]。然而原始扫描数据中不可避免的会包含大量除障碍物以外的其他点云信息，如地面、建筑物等，这将严重影响算法速度及精度，需预先进行滤除。

2.1 地面点去除

地面点云数据去除作为点云滤波的方式之一，是减少数据量及提高聚类检测精度的有效手段。由于道路环境中存在具有小坡度或不平整的地面，无法直接采用设定高度阈值的基于形态学的滤波方法[15]实现地面点的有效去除。然而，基于分割的随机抽样一致性算法(random sample consensus,RANSAC)作为一种从样本集中拟合数学要素的常用方法，高效且鲁棒性好，因此在多种道路地面的适应度更广，但仍存在垂直物体(如建筑立面)干扰。为提高地面点检测精度，本文结合规则八叉树算法与RANSAC算法去除地面点。

规则八叉树利用编码将点云空间划分为指定边长的三维子立方体网格[16]，是一种描述三维空间的树状数据结构。由于原始点云数据中含有大量干扰点云如灰尘、多路径反射等粗差点[17]，通过规则八叉树对点云预处理可在保证各点空间联系的前提下去除粗差点，过滤大部分建筑物、植被等非地物点，降低数据量。对处理后的点云数据采用RANSAC算法估计地面参数，可极大的避免建筑立面或粗差点干扰。从点云中去除地面点的流程如图1所示。

图1 从点云中去除地面点的流程Fig.1 The process of removing ground point from point cloud

具体步骤如下:

步骤1:对图1(a)中原始点云数据Pi(i∈1,2,…,n)建立规则八叉树网格Tj(j∈1,2,…,n)如图1(b)所示，为数据的后续处理构建快速索引结构。

步骤2:定义固定距离空间内临近点数量小于一定阈值的点为粗差点。测定局部空间Tj内点云数量，若小于阈值，则认为三维网格Tj内点云为粗差点簇剔除[18]。

步骤3:考虑到实际应用中激光雷达扫描情况，地面点存在于点云数据底层，标记各垂直区域内高度最小的网格为地面候补网格T如图1(c)中橙色网格所示。这样可有效排除立面及其他物体点云干扰，减小数据量。

步骤4:提取T中点云构建集合S，采用RANSAC算法，从集合S中不断随机抽取点构建平面方程并估计平面模型参数，找到满足阈值的最佳模型平面点，标记为地面点如图1(d)所示。

2.2 高结构物提取

对去除地面点后的点云进行高结构物提取。高结构物体是指如交通标志、建筑立面、路灯、树木等高度较高的行驶区域外对象。采用二维网格为基础单元统计高程信息，设定高度阈值为约束条件，快速区分目标类型提取高结构物，以排除干扰。

投影点云至XOY二维水平面，划分该平面为m个边长L的规则二维网格Grid，gi∈Grid(i∈1，2,…,m)。依据坐标将点云Pi依次划分入各网格gi内，记录各网格中点的最大高程值Hmax=max(Pi)、最大高度差Hc=max(Pi)-min(Pi)及点云数目Ng信息，并将Ng小于阈值(选取4个点)的网格划分为无效网格去除。若网格内点的高程值Hmax大于预定义值，或最大高度差Hc大于阈值，则认为该网格属于高结构物，提取该网格及其内部点云。点云中高结构物体提取效果如图2所示，图2(a)为去除地面点后的点云数据；图2(b)为从点云中提取的高结构物包括物建筑立面、路灯等。

图2 点云中高结构物体提取效果Fig.2 Extraction effect of tall structure objects in point cloud

2.3 自适应网格聚类

在滤除了道路中其他物体点云干扰后，对剩余点云进行聚类。由于16线激光雷达的分辨率随着距离的增加而降低，导致点云数据分布稀疏不均，采用传统固定分辨率的网格无法准确聚类障碍物。分辨率过大会导致近距离网格内包含多个障碍物目标无法区分；分辨率过小易造成远距离稀疏障碍物过分割，且处理时间变长。为解决上述缺陷，本文建立两级网格结构优化聚类算法，一方面，粗分辨率网格适用于对环境中候选障碍物对象的大小、位置进行粗略估计；另一方面，细分粗网格为密集子网格，可有效计算障碍物子空间点云特征，从而得到准确检测结果；此外，本文对文献[13]中多级网格聚类算法进行优化，针对不同空间特征的障碍物，采用自适应方法确定子网格分辨率，提高适应性与检测准确率。自适应网格聚类流程如图3所示。

图3 自适应网格聚类流程图Fig.3 Multilevel adaptive clustering flowchart

具体处理过程如下:

(1)粗网格聚类

使用第2.2节中的初始分割结果，将剩余网格作为粗网格聚类区域。依次访问粗网格单元gi的3×3邻域网格grj(j∈1,2,…8)，以gi与相邻grj的最大高程差H(gi,grj)=|Hmax(gi)-Hmax(grj)|为合并指标，若H小于预定义值，则认为gi和grj属于相同的候选障碍物h，记录h中的点云数量N。

(2)计算标准化离散度

选用点云数N初判断，若N大于阈值，则该候选障碍物h可能包含多个物体，提取h进行子网格细分。以提取的h为中心，引入标准化离散度作为子网格分辨率参数的评价指标[19]。首先计算h第n维数据的离散度Fn，再利用h每一维度点云数据分布的总体标准差与均值的偏离程度描述，计算公式为

Fn=Tn/Cn

(1)

式中:Tn为候选障碍物h第n维数据的总体标准差；Cn为第n维数据的均值。

候选障碍物h标准化离散度F的形式化定义[19]为

(2)

式中:m=3代表障碍物h点的维度；F与离散程度成反比关系，F的值越小，则h离散程度越大。

(3)自适应划分子网格

充分考虑h的分布情况，建立标准化离散度F和子网格划分比例因子W之间的函数关系为

(3)

式中Nh为候选障碍物h的点云数量。

将(3)式中对应的比例因子W作为确定子网格分辨率的判定依据，即将粗网格划分为边长Ls=L/W的子网格gc，图4为子网格划分示意图。

图4 子网格划分示意图Fig.4 Schematic diagram of sub grid division

(4)基于网格密度聚类获取障碍物目标

图5为依据上述步骤聚类得到的相邻障碍物结果。传统网格密度聚类结果均包含了相邻多障碍物目标，但根据自适应网格算法可识别出低密度子网格区域(加黑方框)，得到准确的多障碍物目标检测结果。

图5 相邻障碍物聚类结果Fig.5 Clustering results of adjacent obstacles

2.4 检测结果修正

由于障碍物目标h′大部分处于遮挡状态，形态轮廓扫描不完整，仅依据单帧点云的自适应网格聚类结果可能会造成误检。本文改进了文献[11]中的方法，将k时刻障碍物h′与k-1时刻聚类结果中距离最近的障碍物目标hk匹配，通过计算障碍物包围盒信息的相似度修正聚类所得的检测结果。

首先拟合障碍物的包围盒矩形，利用矩形中心点(x0,y0)表示障碍物，并获得障碍物旋转角度θ。由于障碍物目标大部分具有初始位姿，直接计算或依据最小包围盒无法正确描述其空间特征，因此在最小面积矩形区域基础上，采用L形包围盒[20]的方式拟合。

L形包围盒拟合的基本思想是遍历矩形的所有可能方向并找到包含所有点云的矩形。依据h′中的点到矩形边长距离将点分为P、Q两类，以点到边长的平方误差为目标函数，取最小平方误差为最佳结果，如式(4)。

subject toP∪Q={1,2,…,m},

c1,c2∈R,0°≤θ<90°

(4)

式中:xi、yi为第i个点云的X、Y轴坐标值；θ为包围盒旋转角度；c1、c2是由θ确定的两个正交边上点的投影;R为实数集。

包围盒高度由h′中点云数据Ph的最大高度差Hh=max(Ph)-min(Ph)确定。图6为车辆障碍物的两种包围盒拟合结果，图6(a)为最小包围盒拟合结果，错误估计了车辆的旋转角度以及中心点，而图6(b)的L形包围盒拟合结果则准确表示了车辆特征信息。

图6 包围盒拟合Fig.6 Enclosure box fitting

统计k时刻障碍物h′以及k-1时刻距离最近的匹配目标hk的特征信息，其中包括:中心坐标(x0,y0)、旋转角度θ、运动速度v，计算公式[11]为

(5)

式中:(x0i,y0i)为k时刻第i个障碍物h′的中心坐标；(x0j,y0j)为k-1时刻与h′匹配的第j个障碍物hk的中心坐标；Δt为两帧数据的时间差。

通过以上信息特征来计算两物体相似度Rs，表达式[11]为

(6)

式中:vi、θi和vj、θj分为h′、hk的运动速度和旋转角度；C1～C3代表3种信息的权重值。

当相似度大于阈值时，判定相邻时刻的匹配目标对为同一障碍物。

3 实验及分析

本文所用验证数据集是在比利时普通城市道路环境开展的实验得到的，道路区域具有丰富地物目标且行人稀少，路面较为平整、没有较大的起伏。选用Velodyne公司的VLP-16型16线激光雷达检测环境点云数据。

为验证本文基于自适应网格聚类算法的检测效果，与现有文献[13]中多级网格聚类算法进行对比分析。选取30组宽阔、狭窄、十字路口街道内道路环境数据，分别采用2种算法对障碍物进行检测。其中特别针对不同距离的多障碍物、稀疏障碍物场景进行重点分析研究。检测结果如图7和图8所示，障碍物成独立块状形态，不同包围盒模型代表不同类簇，灰色为地面点及其他地物。

图7 近距离多障碍物聚类结果Fig.7 Clustering result of near distance multi-obstacles

图8 远距离稀疏障碍物聚类结果Fig.8 Clustering result of distance sparse obstacles

文献[13]中选用固定比例因子W=3划分子网格。在16线激光雷达点云数据中，由于扫描所得数据点较少且分布稀疏不均，固定比例因子易造成子网格密度特征不准确进而影响检测结果。如图7(a)所示，标记的相邻多车辆障碍物由于子网格均满足高密度阈值(灰色方框)，故误检为一类；而依据本文方法判断其粗聚类结果分布离散程度小，自适应选取细分比例因子W=4，细分后的子网格识别出了低密度分割线(加黑方框)，并利用前一时刻结果修正，准确检测两类障碍物如图7(b)所示。

在远距离稀疏车辆障碍物场景中，标识出的点云由于子网格划分过小导致低密度网格(加黑方框)出现，将该障碍物误检为两类如图8(a)所示；本文方法判断其分布离散程度大，划分较大子网格，并结合k-1时刻与其匹配障碍物的状态信息，准确检测该稀疏障碍物如图8(b)所示。

图9为不同环境下，基于自适应网格聚类算法、结合相邻数据修正后的检测结果，图中采用盒模型表示检测所得的障碍物。观察可知，在不同环境与距离下，本文算法都能对车辆行驶道路中障碍物进行较准确的检测。

为了进一步衡量算法的准确度，采用准确率作为评价指标对障碍物检测结果进行定量评价。人工标记30组道路中301个障碍物，作为准确率P计算的参考，文献[7]对P进行了描述。

P=As/A

(7)

式中:As为准确分割的障碍物数目；A为障碍物总数目。

图9 4类场景下障碍物检测结果Fig.9 Detection result of obstacles in four scenes

分别通过2种算法进行准确统计计算，得出障碍物检测的准确率P，见表1。

表1 障碍物检测准确率Tab.1 Accuracy of obstacles detection (%)

由表1数据可知:与文献[13]中的算法相比，本文算法的检测准确率更高，障碍物检测更加完整。3种道路下本文算法的准确率均得到了提升，检测准确率整体提高了5%。

4 结 论

针对16线激光雷达数据中障碍物目标误检率较高的问题，提出一种基于自适应多级网格聚类的障碍物检测方法:快速去除地面点与高结构物；根据粗网格聚类结果空间分布情况，建立分布离散度和子网格细分比例因子之间的对应关系，自适应确定子网格分辨率并获取稠密子网格最大连通区域；结合相邻时刻特征信息修正结果，完成障碍物的准确检测，检测准确率达91%。

对不同道路场景的16线车载点云数据进行实验，实验结果表明:在近距离密集与远距离稀疏点云环境下均可进行障碍物的准确检测。解决了传统聚类易造成的障碍物目标欠分割或过分割问题，改善了因激光雷达分辨率随距离变化的点云稀疏不均导致的检测不准确情况。并与改进的网格聚类方法进行了对比，进一步验证了本文方法的有效性。