段建民，王昶人，任 璐，刘 丹
（北京工业大学 信息学部，北京100124）
为了提取无人驾驶车前方可行驶区域信息，提出了一种基于多层激光雷达可行驶区域信息提取算法。首先，根据雷达返回数据的特征结合数据区间密度分布获得路沿点集，并利用基于加权欧氏距离KNN改进的OPTICS算法对得到的路沿点聚类。然后，使用最小二乘法拟合出两侧路沿。最后，通过改进的OPTICS算法将路面上的障碍物点云进行聚类，并通过计算得到障碍物的位置、距离、尺寸等信息。利用数据区间密度分布法提取路沿点不受障碍物以及路面点的影响，而改进的OPTICS算法则不再受Eps的约束，并且可以准确分辨出噪点，解决了障碍物信息由于噪点而提取不准确的问题。实车实验证明了算法的有效性和实时性。
无人驾驶车；多层激光雷达；可行驶区域；数据密度分布；OPTICS算法
中图分类号：TN958.98
文献标识码：A
DOI：10.16157/j.issn.0258-7998.170392
中文引用格式：段建民，王昶人，任璐，等. 基于多层激光雷达的可行驶区域信息提取算法[J].电子技术应用，2017，43(10)：78-82.
英文引用格式：Duan Jianmin，Wang Changren，Ren Lu，et al. Algorithm of driving area information extraction based on multi-layer lidar[J].Application of Electronic Technique，2017，43(10)：78-82.
0 引言
随着社会的不断发展，世界各国越来越多的学者开始对无人驾驶进行研究[1-2]，其中雷达技术更得到广泛关注。文献[3]利用路沿点数据斜率一致特性对路沿点进行提取，但该算法容易受路面点和障碍物点的影响并且要分层处理，所以准确性和实时性都不能达到要求。文献[4]利用激光雷达返回高度数据的跳变提取路沿点，这种方法受障碍物影响很不稳定。而对于聚类算法，由于激光雷达数据主要是成簇出现的，所以基于密度的聚类方法适合于激光雷达数据，其中OPTICS算法是典型的基于密度的聚类方法。文献[5]利用结果序列重组织策略对OPTICS算法进行改进，但是在实际应用中，对于激光雷达数据点突然出现的噪点无法区分，导致障碍物提取效果不准确。
本文首先利用数据区间密度分布提取路沿点并通过最小二乘法拟合出路沿区分可行驶区域，然后在可行驶区域中利用改进的OPTICS算法对返回数据进行实时聚类。最后通过实车实验验证提出算法的有效性与实时性。
1 激光雷达数据预处理
1.1 激光雷达数据分析
本文应用德国IBEO公司生产的IBEO LUX 2010型四线激光雷达，该型号的雷达较单线激光雷达具有数据量大、检测精度高、探测距离远等优势[6]。其主要参数如表1所示。
四线雷达返回的信息主要包含序号、扫描层数、距离以及位置坐标信息。其特性分析如下：
(1)激光雷达是自左向右扫描的，每一帧返回的数据量基本相近；
(2)激光雷达返回的数据是根据前方场景的变化而变化的，每个障碍物的扫描点的数目及形状不一；
(3)当激光雷达扫描到路沿时返回的数据特点是x轴坐标稀疏，y轴坐标紧密排列。
1.2 数据预处理
为了检测车辆前方的可行驶区域以及障碍物的信息，将激光雷达安放在车辆前方正中间的位置，根据以往经验，雷达的安装高度设定为0.846 m。安装位置示意图如图1所示。
2 激光雷达数据处理方法
2.1 一维数据区间密度分布
假设(x1，y1)，(x2，y2)，(x3，y3)，，(xn，yn)，n∈R为雷达返回路沿点数据，根据其特性，其中某一维数据D={y1，y2，y3，，yn}，n∈R是基本相近的，数据区间概率密度分布即雷达返回的数据落在某个区间[ω，ξ]的密度，其公式为：
式中，ω和ξ为某个区间的两个端点，num(yi)为落在某个区间数据的个数，分母为数据个数之和；P为在某个区间数据个数占总体的概率。若将整体的数据分为j个区间，则其概率的总和为1。
2.2 OPTICS算法
OPTICS[7-9](Order Point to Identify the Cluster Structure)算法是一种基于密度的聚类算法。此算法是DBSCAN算法的扩展，对数据对象集中的数据进行排序，输出一个有序的对象列表(cluster-ordering)，在这个列表中包含了用来提取聚类的所有信息，即对数据对象进行分类。以下是OPTICS算法中引入的两个定义[10]：
定义1 核心距离(core-distance)
假设点P包含m个邻近的最小半径为min-distance(P)，那么P点的核心距离就可以定义为：
定义2 可达距离(reach-distance，RD)
假设P是点o邻近点之一，那么P与o相关的可达距离定义式为：
传统的OPTICS聚类方法实现步骤如图2所示，OPTICS算法的优点是对输入参数不敏感，但是输入Eps与实际Eps差距较大时，聚类效果依然被影响，而且该算法对于噪点也不能区分。
2.3 基于加权欧氏距离的KNN图
在实际的雷达数据中对雷达数据进行数据密度分布计算后提取各个峰值区域的点集，计算其横、纵坐标的方差值，就可以计算出数据点间的加权欧氏距离。
KNN即将实际雷达扫描到的数据点按照加权欧氏距离求取其距离矩阵Distk*k，然后将Distk*k中每一维按照升序排列形成sort(Distk*k)，最后将sort(Distk*k)中的每一维数据绘制成KNN图。
2.4 最小二乘法拟合
本文根据实验道路特性，由于实验道路两侧路沿点多呈线性分布，因此，使用最小二乘法对道路两侧提取的路沿点进行线性拟合。最小二乘法[12-14]是一种数学优化方法，它通过最小化误差的平方和寻找数据的最佳函数匹配。其针对线性拟合常用的表达式为y=kx+h，以下则是参数k和h的求解公式：
式中，n表示待拟合的点的个数，(xi，yi)为待拟合点的坐标值，k为斜率，h为截距。
3 可行驶区域信息提取方法
3.1 基于加权欧氏距离改进的OPTICS算法
传统的OPTICS算法虽然能克服其他传统聚类算法的一些问题[15]，但其自身仍然有一些不足之处，如OPTICS在实际的筛选核心点的过程中是通过选取合适的Eps来确定核心点的位置，而由于Eps选取不当引入噪点，这样大大降低了算法对噪点的敏感程度，使得聚类不准确。另外，如果盲目选择Eps的范围，同样影响聚类效果。
为了改进OPTICS的不足之处，本文提出了基于加权欧氏距离KNN改进的OPTICS算法，此算法不需要输入参数Eps，而是通过数据点间加权欧氏距离升序排序形成一个k-最近邻图(KNN)来确定聚类结果以及区分噪点。具体步骤如图3所示。
根据图3所示，改进的OPTICS算法不需要选取Eps就可以直接进行聚类。在流程图中基于加权欧氏距离KNN分离噪点的具体步骤如下：
(1)求取每类数据点中每个点之间的加权欧式距离，形成距离矩阵Distk*k；
(2)将距离矩阵中各维度距离按照升序排序，形成sort(Distk*k)；
(3)由于噪点与其他点的距离大于一个阈值，所以就要判定这个点与其他点之间距离最小距离是否大于threshold，若大于，则该点为噪点。
3.2 基于一维数据区间密度分布的路沿提取算法
通过对激光雷达返回的点云数据分析可知，在点云中包含有路面点、两侧路沿点、周围花草景物点以及障碍物点。设定k个等距区间[ω，ξ]，在此区间中利用式(2)求取雷达数据点在每个区间的密度。以横轴零为分界点，提取出两侧密度最大值及次大值所在区间。由经验知，路面点与路沿点高度差大约为20 cm，根据此高度差可消除路面点。得到路沿点后，将路沿点使用改进的OPTICS算法进行聚类，最后利用最小二乘法拟合得到路沿，并计算得到路沿信息。
3.3 可行驶区域内障碍物信息提取
通过得到的路沿信息，可判定出路面的路宽度。若假设左右路沿点的范围分别为[a，b]和[c，d]，则根据横向定界及式(8)得到可行驶区域的范围：
式中，Croad为可行驶区域，Cnoise为周围环境。
根据无人驾驶车辆宽度信息和提取出可行驶区域的宽度信息结合，其表达式为：
提取出可行驶区域后，剩下的点为障碍物以及噪点。障碍物点主要有：行人、机动车、自行车等。障碍物的主要属性信息表示为距离、角度、中心点等。利用改进的OPTICS算法将可行驶区域内的障碍物进行聚类，并提取出每类障碍物的距离、角度以及障碍物中心点x、y、z坐标值。通过类内计算得到障碍物的长度、宽度、距离、角度以及速度等信息。
4 实车实验结果
4.1 实验条件及平台
本文实验平台为BJUT-IV(Beijing University of Technology Intelligent Vehicle)自主研发的无人驾驶车，在车辆的前端正中的位置安装IBEO-LUX四线激光雷达来采集实验数据。雷达安装高度为0.846 m。实验的场景为校园内道路，如图4所示。
4.2 可行驶区域路沿提取实验结果
可行驶区域路沿提取实验结果如图5所示。
图4左侧为实验场景1，道路条件为无车辆通过。图5(b)为原始数据点，原始数据点中包含路沿点、路面点，及周围的树木、铁网。图中雷达数据点分为4层，由图中箭头所指的点表示。图5(a)为雷达返回数据坐标y值的数据密度分布直方图，其中以零为分界点，4个范围中靠近零的两个区间为路沿点区间，而另外两个区间为球场边界。根据密度直方图可以清晰地分析出左侧路沿点所在范围[-3.92，-3.7]，右侧路沿点范围为[6.4，6.8]。通过对区间密度的选取，就得到了如图5(c)所示的情况，图中的两列点则为通过基于一维数据区间密度提取出的结果。图5(d)是将提取出的路沿点通过基于加权欧式距离的KNN改进的OPTICS算法进行聚类，图中椭圆形框是为了清楚表示两类的聚类结果。最后通过最小二乘法将两侧提取出的路沿点进行线性拟合，结果如图5(e)所示。提取出的路沿结果显示，道路的宽度为10.48 m，车辆左侧与路沿距离为6.64 m，车辆右侧与路沿距离为3.83 m。在实际的实验场景中通过测量得到实际的道路宽度约为10.5 m，提取结果与实际宽度仅差0.02 m，路面宽度信息检测率为99.8％，符合实际应用需要。
4.3 可行驶区域障碍物提取实验结果
可行驶区域障碍物提取结果如图6所示，图4右侧为实验场景2，场景中有行人和汽车。图6(a)为第47帧加权欧氏距离KNN图，图中稀疏部分为文中提到的噪点，其他部分为聚类效果。图6(b)为车辆行驶过程中第47帧数据利用传统OPTICS算法检测出路面的障碍物的情况。从图中可以看出，由于在雷达扫描过程中第3层数据出现噪点，所以影响了聚类效果，导致聚类准确性降低。而图6(c)为第47帧数据利用基于加权欧氏距离的KNN改进OPTICS算法的效果，算法可以避免路面噪点的影响，而且可以对障碍物准确的聚类，并且通过计算可以得到障碍物的主要属性，检测到行人的长度length=0.1 m，宽度为width=0.3 m，检测到车辆的长度为length=3.3 m，宽度为width=1.7 m，包括雷达距离前方障碍物的距离，检测结果与实际测量尺寸基本相符，满足了检测要求。
图6(d)为第45帧传统OPTICS算法检测结果，图中将路面噪点当作障碍物，影响了聚类准确性。图6(e)为第45帧数据利用改进OPTICS算法，效果良好。通过以上实验结果可以证明，本文提出的可行驶区域提取算法的有效性与实时性都得到提高。
5 结束语
本文提出的可行驶区域信息提取算法包括可行驶区域路沿提取和障碍物提取，在路沿提取中，利用一维数据区间密度分布对雷达数据进行界定，并通过界定范围提取路沿点，这种方法根据数据密度提取路沿点排除了路面障碍物对路沿点提取的影响，并且对多层数据同时处理，减少了复杂度。通过基于加权欧氏距离的KNN改进OPTICS算法将路面上的障碍物点云进行聚类，并通过计算得到障碍物的位置、距离、尺寸等信息。改进的OPTICS算法则不再受Eps的约束，而且可以准确分辨出噪点，增加了障碍物提取的准确性。提出的算法可以有效感知无人驾驶车辆前方可行驶区域的信息，为无人驾驶决策层提供有效信息，同时也提高了无人驾驶车的安全性。
参考文献
[1] DAHLKAMP H，KAEHLER A，BRADSKI G.Self-supervised monocular road detection in desert terrain[C].Proceedings of Robotics：Science and Systems.Philadelphia：MIT Press，2006：115-121.
[2] 王欣，李高，朱万力，等.并联混合动力汽车能量管理建模及优化研究[J].控制工程，2014(3)：357-360.
[3] 杨象军.基于四线激光雷达的道路检测与跟踪[D].杭州：浙江大学，2013．
[4] 刘梓，唐振民，任明武.基于3D激光雷达的实时道路边界检测算法[J].华中科技大学学报(自然科版)，2011(S2)：351-354.
[5] 曾依灵，许洪波，白硕.改进的OPTICS算法及其在文本聚类中的应用[J].中文信息学报，2008(1)：51-55，60.
[6] 庄秀华.基于单线激光雷达的障碍物检测与跟踪研究[D].长沙：湖南大学，2014.
[7] 党秋月，陆月明.基于OPTICS可达图的自动识别簇方法[J].计算机应用，2012(S2)：19-21，47.
[8] 王品，黄焱.改进的OPTICS算法在调制识别中的应用[J].计算机工程与应用，2011(16)：141-143.
[9] 孙天宇，孙炜，薛敏.OPTICS聚类与目标区域概率模型的多运动目标跟踪[J].中国图像图形学报，2015(11)：1492-1499.
[10] 陈燕俐，洪龙，金达文，等.一种简单有效的基于密度的聚类分析算法[J].南京邮电学院学报，2005(4)：24-29.
[11] 段建民，李龙杰，郑凯华.基于车载4线激光雷达的前方道路可行驶区域检测[J].汽车技术，2016(2)：55-62.
[12] 邹乐强.最小二乘法原理及其简单应用[J].科技信息，2010(23)：282-283.
[13] 丁克良，沈云中，欧吉坤.整体最小二乘法直线拟合[J].辽宁工程技术大学学报(自然科学版)，2010(1)：44-47.
[14] 程玉民.移动最小二乘法研究进展与述评[J].计算机辅助工程，2009(2)：5-11，20.
[15] 段建民，郑凯华，李龙杰，等.基于多层激光雷达的道路信息提取算法[J].控制工程，2016(4)：468-473.
