基于多线激光雷达的道边检测算法

高栋南

摘要：为了让智能汽车辨识可行驶区域，道边检测是前提。使用多线激光雷达，通过对大量道边点数据进行分析，提出一种道边检测与跟踪算法。首先，通过分析扫描点特征，建立多阈值筛选算法，提取出有效道边点集；其次，采用基于K-means改进的聚类算法对有效道边点集进行聚类分析，得到左、右两侧的道边点集；最后，使用最小二乘法拟合得到左右道边。经过实际验证，该算法道边检测准确，处理每帧数据平均仅需34ms。

关键词：激光雷达；无人驾驶；道边检测；K-means算法；直线拟合

DOI：10.11907/rjdk.173108

中图分类号：TP306

文献标识码：A文章编号：1672-7800（2018）007-0023-04

Abstract：Asthepreconditionofautonomousdriving，roadedgedetectionwascrucialforintelligentvehiclestorecognizethefreedrivingspace.Byanalyzingplentyofroadedgepointdata，weproposeanewroadedgedetectionandtrackingalgorithm.Firstly，amulti-thresholdalgorithmwasusedtoextractvalidroadedgepointbyanalyzingthecharacteristicofscanningpoint.Secondly，animprovedalgorithmbasedonK-meansalgorithmwasusedtoclassifyroadedgeintorightandleftroadedgepoints.Finally，tworoadedgeswerefittedbyleastsquarealgorithm.Experimentalresultsshowedthatthealgorithmcanaccuratelydetectroadedge，whichonlycosts34mstoprocessonedataframe.

KeyWords：laserradar；autonomousdriving；roadedgedetection；K-meansalgorithm；linearfitting

0引言

如今，无人驾驶技术发展迅速，该技术为缓解交通拥堵、减少交通事故提供了解决方案，其中道边检测是无人驾驶技术的重要组成部分。激光雷达作为一种探测距离远、范围广，且测距准确的传感器，被应用于无人车辆道边检测。其中，基于多线激光雷达的道边检测成为道边检测的主要方式。

传统的道边检测算法原理简单，多层扫描点数据通过提取道边点呈直线排列特征，提取出有效道边点[1-2]，经过简单聚类后，拟合得到完整道边。不足之处在于，道路两侧的树木、墙面等干扰项生成的扫描点难以滤除[3]。此外，若不通过精确的聚类分析，难以清晰地将道边点分类为左道边点与右道边点。

本文提出一种新的道边检测方法，通过多阈值筛选方法排除上述干扰项影响，得到有效道边点集，并采用基于K-means的改进算法，对道边点集进行聚类，得到左、右道边点集。同时使用最小二乘法，对聚类后的道边点实现道边拟合。

1设备概述

本文选用IBEO-LUX2010四线激光雷达。该雷达拥有4条激光扫描线，扫描线之间的夹角为0.8°。雷达采用TOF算法（TimeofFlight）探测距离，通过直接测量以光速传播的激光脉冲从发射时刻到接收到回波信号时刻之间的时间得到目标距离。TOF算法原理简单，功耗小且量程远，仅用一次测量即可得到单点目标距离[4]。激光雷达的扫描频率为12.5Hz，水平扫描角度为-50°～35°。

激光雷达的4个扫描层从下到上分别用红、蓝、绿、黄表示，雷达安装位置与扫描层结构如图1所示。激光雷达坐标系如图2所示，以雷达自身作为坐标原点O，X轴代表坐标系横轴，水平向右；Z轴代表坐标系纵轴，方向向前；Y轴根据右手定则，方向竖直向上。实验部分三维点云以此坐标系构建。

2基于多线激光雷达的道边检测

2.1道边检测原理

城市环境中，大部分道路有著清晰的道边[5]，道路模型如图3所示。道边与路面相比，有显著的高度特征。其中虚线表示雷达的一条扫描线，道边上的扫描线由道边点组成，路面与人行道的扫描线由非道边点组成。

观察图3可知，只要找到道边点，即可拟合出完整的道边直线。

2.2多阈值筛选方法提取道边点

通过分析大量扫描点中的道边点数据，总结得到以下特征：①一条道边的道边点排列呈线性特征[6]，即可使用直线y=kx+b表示；②道边扫描点是一组连续的点，连续两点之间的距离与扫描频率有关，应该小于一个阈值；③道边点略高于地面，其高度介于一定范围之间；④道边长度满足一定距离，可理解为略大于或小于数据标定中的理论长度。依据上述道边点特征，处理步骤如下：

首先，道边点选取范围应在道边检测时数据标定的距离范围内，根据前面的标定确定道边检测的起始距离S1与终点距离S2，单位为m，即道边点距离必须符合阈值区间[S1，S2]。

其次，道边点的位置高于地面，介于道边上沿与道边下沿（地面）之间。通过引入高度信息进一步判断：根据雷达扫描线的俯仰角a计算求出扫描点的高度信息[7]，记作height，其大小应当满足阈值区间[h1，h2]，h1代表道边下边沿点高度，h2代表道边上边沿点高度（单位均为m）。利用阈值，可以有效剔除一些干扰点[8]，例如道边以上的树木和墙壁等扫描点。通过以上两个阈值条件筛选，得到初步的道边点。

最后，由初步道边点中的第一个点开始，按顺序依次选取n个点，连续两点的点间距要小于阈值Pd（单位：m），该阈值依据雷达扫描频率确定。建立该阈值以防止道边探测出现路口或岔口等干扰因素时[9]，可能出现点之间距离过大，从而被误判为一条完整道边的情况。若大于阈值Pd，则从不满足的点开始，迭代上述过程，直至找到彼此之间距离小于阈值的n个点，将此n个点作为一组点集保存，最终得到M组点集。

上述检测产生M组点集，每组有n个点。在每组点集的n个点中取第一个与最后一个扫描点建立直线y=kx+b，然后判断其余（n-2）个点到该直线的距离是否小于阈值Pld（单位：m），小于阈值则说明点距离直线非常近，可近似看作n点在同一条直线上。若小于阈值Pld，则保存这组点集；若大于阈值Pld，则摒弃该组点集，重新对下一组点集的n个扫描点迭代上述操作，直至M组点都处理完毕，得到符合要求的O组点集（O

对产生的O组点集，判断每一组对应直线的斜率是否属于阈值区间（K1，K2），若不属于该区间，则判定该组点无法构成道边直线，摒弃这组点集；若满足该区间，则保存这组点集[12]。迭代上述过程，直至O组点集都处理完毕，得到符合要求的P组点集（P

通过上述步骤，得到P组有效的道边点集。

2.3基于K-means的改进聚类算法

对上述得到的P组点集进行聚类，分为无人车辆左道边点与右道边点。K-means算法作为一种动态规划的聚类算法，具有计算速度快、消耗资源少的优点，其时间复杂度为O（nkt），其中k为聚类个数，t为聚类迭代次数，n为总样本数。算法基本流程如下：①首先给定样本聚类个数k；②根据给定的k，随机从样本中选取k个聚类中心点；③计算剩余每个样本到每个聚类中心点的欧式距离，将样本归为离其最近的中心点所在类；④重新计算k个类的中心点；⑤迭代执行②、③步，直至中心点不再变化或小于设定阈值，即中心点收敛，聚类结束。

使用K-means算法将有效道边点集聚类为左道边类与右道边类，共计两类，可以确定聚类个数为2，但由于初始选取聚类中心点是随机的，会导致聚类精度降低[10]。对于K-means算法的初始中心点选取作如下改进：先求出每个道边点之间的欧氏距离作为差异度，距离越大说明差异越大，反之，距离越小则说明越相似。

利用该差异度建立差异度矩阵。假设有n个道边点，生成n*n维的差异度矩阵M，矩阵中的元素为两个道边点距离，记作d（i，j），表示第i个到第j个道边点距离，矩阵公式如下：

遍历矩阵元素，找到最大的d（i，j），记作dmax，说明其构成的第i点与第j点差异性极大，即该两点距离最远，由于只存在左、右两类道边点，第i点与第j点一定是属于不同侧道边的两点，可以将第i点作为第一个初始聚类簇中心点，而第j点可作为第二个初始聚类簇中心点。选出两个初始聚类中心簇后，剩余聚类步骤与K-means算法相同。通过如上数据分割后，可以确保初始中心点的选择更具代表性。

为验证改进后的聚类精度变化，分别使用数据集Wine、Iris等对改进前的K-means算法与改进后的算法进行10次聚类测试，对聚类效果进行对比。数据集信息如表1所示，对比结果如表2、表3所示。

对聚类得到的左、右道边点采用最小二乘法分别进行拟合，得到两条完整道边所在直线的斜率与截距。最小二乘法通过最小化误差的平方和寻找数据的最佳函数匹配[11]，可以求得直线方程中的系数。计算公式如下：

其中n是该侧扫描点总数，xi、yi分别代表道边点在雷达坐标系的横、纵坐标。道边检测算法整体流程如图4所示。

3道边检测实验结果及分析

试验场景如图5所示，该场景左右两侧分别具有树木及墙面等干扰项。

图6是以雷达坐标系中的xOz平面建立的栅格地图，将雷达四层扫描原始数据点映射到栅格地图中，两条白色斜线形成的夹角代表雷达扫描区域。本文的道边检测算法仅使用最底层扫描点（红色扫描点）进行分析处理，最底层的原始数据点包含地面点、树木、墙壁等多个干扰点。

图7是使用道边检测算法后得到的图像，通过提取有效道边点，进一步进行聚类、直线拟合得到两条完整的道边直线，将道边映射在栅格地图上，用白色线段表示。其中实线部分代表实测道边点构成的道边，虚线为拟合补全得到的道边。实验证明，仅使用单层扫描点数据通过本文算法进行检测，结果较为准确。

分析检测算法对原始扫描点数据的处理过程，并比较处理结果：原始数据点云如图8所示，多阈值算法提取道边点处理结果如图9所示。道边点点云与原始数据点云相比，左、右侧的部分干扰点，以及地面点已被排除。通过观察图8中的点云分布，与图3中的道边线形状相符合。

得到有效道边点后，使用基于K-means的改进算法进行聚类，得到位于雷达两侧的左右侧道边点，再将这些点映射到栅格地图中，结果见图10所示。对聚类后的两类道边点进行直线拟合，得到完整道边。将两条完整道边映射到栅格地图中，处理结果如图11所示。

使用检测算法，对存在干扰项的1079帧扫描数据进行检测。通过验证检测得到的道边位置，获取最高与最低准确率，并求出平均准确率与处理每帧数据的平均消耗时间，算法检测效果如表4所示。

从处理数据的平均耗时与准确率可看出，该算法耗时较少，检测效果好，在试验场景存在干扰项的情况下，依然保持了较高准确率。

4结语

本文提出一种基于多线激光雷達的道边检测算法，首先使用多阈值筛选算法，较好地剔除了诸多干扰点；其次，使用基于K-means的改进聚类算法，精确地将道边点聚类为左右侧道边；最后，使用最小二乘法，拟合出完整道边。下一步工作可在利用道边信息分割出“可行驶区域”后，对该区域中的动态障碍物进行聚类、跟踪，提取障碍物相关信息。

参考文献：

[1]段建民.多线激光雷达在无人驾驶车中的环境感知[J].北京工业大学学报，2014，10（12）：1891-1898.

[2]杨象军.基于四线激光雷达的道路检测与跟踪[D].杭州：浙江大学，2013.

[3]ALOSHYNAV.基于多线激光雷达的道路和障碍物检测[D].北京：北京工业大学，2016.

[4]史鹏波.基于单线激光雷达的道路特征检测[D].南京：南京理工大学，2013.

[5]肖已达.基于激光雷达的道路可通行区域检测[J].机电一体化，2013，12（2）：62-70.

[6]ALBERTOB，PIETROC，MIRKOF.Thevislabintercontinentalautonomouschallenge：anextensivetestforaplatoonofintelligentvehicles[J].InternationalJournalofVehicleAutonomousSystems，2012，10（3）：147-164.

[7]崔佳超.无人驾驶智能车在动态环境中的避障方法[D].西安：西安工业大学，2015.

[8]辛煜.无人驾驶车辆运动障碍物检测、预测和避撞方法研究[D].合肥：中国科学技术大学，2014.

[9]王科.城市交通中智能车辆环境感知方法研究[D].长沙：湖南大学，2013.

[10]朱学葵，高美娟，李尚年.一种智能汽车的实时道路边缘检测算法[J].北京联合大学学报，2015，29（4）：1-7.

[11]田垅，刘宗田.最小二乘法分段直线拟合[J].计算机科学，2012，39（6）：482-486.

（责任编辑：黄健）