基于四线激光雷达的无人车障碍物检测算法
Obstacle Detection Algorithm for Driverless Vehicles Based on
Four-layer Lidars
WANG Hai1 ZHENG Zhengyang1 CAI Yingfeng2 CHEN Long2
1.School of Automotive and Traffic Engineering，Jiangsu University，Zhenjiang，Jiangsu，212013
2.Automotive Engineering Research Institute，Jiangsu University，Zhenjiang，Jiangsu，212013 Abstract： Aiming at the problems that the resolution capability of lidar scanning angle was not high enough，the remote point cloud was sparse and the target segmentation and clustering were not accurate， an obstacle detection algorithm was proposed based on four ⁃ layer lidars. After rasterization and filtering of raw radar data，clustering and segmentation of filtering results were performed. The clustering dis⁃ tance threshold was determined by the grid depth values，and the accurate clustering ranges were ob⁃ tained by connecting the connected region marking algorithm. The matching accuracy of clustering was further improved by matching the movement status informations of adjacent obstacles. The experimental results show that the proposed algorithm，compared with existing segmentation clustering algorithms， may obtain the information of obstacles on road accurately and prevent the over⁃segmentation effectively.
Key words： lidar；obstacle detection；grid map；clustering
0 引言
随着人工智能、传感器技术的不断发展，无人驾驶汽车取得了很大的进步。无人车作为轮式机器人的一种，不仅要求能实现自主安全驾驶，还需要保证乘员的舒适性。环境感知作为无人车体系结构的基础，其性能的优劣直接关系到能否达到安全驾驶的需求。环境感知常用的传感器有视觉传感器、激光传感器、惯性导航、GPS定位系统等。
收稿日期： 2017－12－15
基金项目：国家重点研发计划资助项目（ 2018YFB0105003）；国家自然科学基金汽车联合基金资助重点项目（ U1564201，U1664258， U1764257，U1762264）；国家自然科学基金资助项目（ 61601203， 61773184）；江苏省重点研发计划（产业前瞻与共性关键技术）资助项目（ BE2016149）
激光雷达由于其精度高，受环境影响较小，在无人驾驶汽车中得到了广泛应用。
目前，激光雷达数据处理主要分为两类：一种是直接基于点云的处理方式 ；另一种是基于栅
［］ 1⁃2格地图的处理方式 。栅格地图因其简单稳定，
［］ 3⁃8实时性好，故广泛用于无人车环境感知系统 。在
［］ 9行车过程中，一些噪声会对检测算法造成影响，所以需要对噪声进行滤除。激光雷达聚类算法是后续数据处理的基础，常用的聚类方法有基于K均值的聚类 、基于分层的聚类、基于密度的聚类、
［］ 10
基于网格的聚类 、基于神经网络的聚类、基于统
［］ 11计学的聚类和高维可视化数据聚类等。在激光雷达聚类算法方面，国内外学者提出了许多方法。甘志梅等 采用了基于固定距离阈值的聚类方
［］ 12
1 1 2 2
王 海 郑正扬 蔡英凤 陈 龙
1.江苏大学汽车与交通工程学院，镇江， 212013
2.江苏大学汽车工程研究院，镇江， 212013
摘要：针对雷达扫描角分辨能力不高，远处点云较稀疏，导致对目标的分割聚类不准确的问题，提出了一种基于四线激光雷达的障碍物检测算法。在对原始雷达数据进行栅格化及滤除之后，对滤波结果进行了聚类分割。依据栅格深度值确定聚类距离阈值，结合连通区域标记算法得到准确的聚类范围；通过匹配相邻障碍物运动状态信息，进一步提高聚类的准确率。实车实验表明，所提方法较已有的分割聚类算法，可以准确地得到路面障碍物信息，并能有效避免过分割现象。
关键词：激光雷达；障碍物检测；栅格地图；聚类
中图分类号： TP39
DOI：10.3969/j.issn.1004⁃132X.2018.15.017 开放科学(资源服务)标识码(OSID) ：
在数据采集阶段，本文采用创建多线程并建立网口通信来接收不同激光雷达所采集的数据。作为客户端，需要向各台激光雷达设备发送指令，完成其安装扫描参数和接收数据模式的设置。当接收到激光雷达数据后，通过产品说明书对其进行解析。激光雷达返回的每一帧数据都包含原始激光雷达点云的距离、回波宽度、扫描线数以及障碍物的距离、速度、大小、分类等信息。最后通过解析获得本文所需要的信息。 图1 激光雷达扫描范围示意图
Lidar scanning scope schematic diagram
图2 激光雷达安装示意图
Fig.2 Lidar installation schematic
1.2 激光雷达坐标系转换
车体坐标系是以车辆后轴中心为坐标原点，车辆的前进方向为xv轴，水平向左为yv轴，竖直向上为zv轴。激光雷达临时坐标系是以激光雷达的中心为坐标原点，水平向前为xL轴，水平向左为yL轴，垂直于oxLyL面向上为zL轴。本文采用一种分层转换四线激光雷达坐标的方法 ，首先通过几
［］ 14何关系，将三维扫描点坐标依据扫描角度值以及扫描层数投影至激光雷达临时坐标系oxLyL，再依据安装参数将坐标转化至车体坐标系。
2 激光雷达数据预处理
处理激光雷达数据大致可以分为两种方法：一种是直接对点云数据进行处理，另一种则是先将点云投影至栅格地图，再进行预处理、距离分割及检测。前者的优点在于可以相当完整地保留障碍物的轮廓信息，对外界的环境信息丢失较少，精度较高，但是多线激光雷达扫描返回的点云数量十分庞大，对计算资源有很高的要求，直接对激光雷达点云进行处理难以保证算法的实时性；而后者会丢失部分环境信息，使目标检测性能降低，但其处理速度较快，稳定性较好，适合运用于工程中。针对智能驾驶中需要实时准确地检测周围环境中的障碍物，本文采用栅格法来对激光雷达数据进行处理。
2.1 点云数据投影栅格地图以统一大小的网格来划分车辆周围
· ·
空间。本文建立的栅格地图大小为240×400格，单个栅格大小为20 cm×20 cm，包含了车前方80 m以内以及左右各12 m以内的范围。栅格地图法需判定每个栅格属性是否是占据的。IBEO ⁃ LUX⁃ 2010雷达可直接获得剔除路面点后的障碍物扫描数据点，将其向栅格地图投影，统计每个栅格内是否包含点云投影，若存在，则此栅格置为1，表示该栅格中存在障碍物，栅格为占用状态；反之，置为0，表示此栅格不存在障碍物，为非占用状态。
2.2 栅格滤波
在智能车行驶过程中，在车前方会不可避免地出现一些小飞虫或者是落叶等小物体，如果在环境感知环节没有将这些悬空小障碍排除，可能会发生误检而导致车辆停止，这样会对行车造成严重影响。这些悬空障碍物主要满足以下特征： ①车前方点云应是密集的，所以出现单个障碍栅格可能是小障碍物； ②障碍物应是悬空的，且该栅格内点云高度差比较小。
本文采取如下判别依据来排除悬空小障碍物。在车前方10 m范围内，在所有被检测到的障碍物栅格中，若其同时满足下述两种情况： ①周围7×7格范围内不存在其他障碍栅格； ②只存在中间2根扫描线扫描到的障碍物，而顶层及底层扫描线均未扫描到障碍物，则认为该障碍物为悬空小障碍物，将其排除并更新栅格地图，以防止因误检而导致车辆停止行驶。激光雷达滤波算法应要求严格，防止出现漏检而导致汽车碰撞障碍物；同时，一些漏检情况可以通过后续的雷达跟踪算法进行滤除。栅格滤波效果见图3。 （ a）滤波前 （ b）滤波后
图3 栅格滤波效果图
Fig.3 Grid filtering
数据聚类对障碍物进行分割聚类是对其识别跟踪的基础。由于激光雷达角分辨能力固定，所以在远处雷达的角分辨能力就会降低，这会导致一个障碍物可能会分解成多个离散的小块，无法对障碍物进行正确分割，以致后期对障碍物的检测和跟踪发生错误。所以，如何对雷达的点云数据进行准确聚类，分离提取不同的障碍物，是激光雷达点云数据处理的难点。单从空间上对激光雷达数据进· ·
3 行分割难以满足要求，因此本文在空间聚类的基础上，通过障碍物块的匹配对结果进行修正，得到修正后的聚类结果，具体流程图见图4。
图4 聚类跟踪流程图
Fig.4 The process of clustering and tracking
3.1 空间方式聚类
基于密度的聚类方法优点是能够发现任意形状的聚类；基于网格的聚类方法虽然降低了聚类精度，但减少了计算量，提升了实时性。由于在车辆周围环境建模中已经建立了环境栅格地图，故本文在处理一帧数据时采用网格聚类的方法，同时依据选取不同的距离阈值将障碍物离散的网格聚类在一起。
二值连通区域标记算法 广泛应用于计算机
［］ 15图像处理。在区域标记算法中，通过模板比较当前网格与邻域网格中像素是否相同，若相同，则将这些网格作为一个类连通在一起。邻域四连通及邻域八连通标记算法的模板见图5。 （ a）四连通标记 （ b）八连通标记
图5 四连通及八连通标记算法
Fig.5 Four-connected and eight-connected
labeling algorithm本文所提的聚类算法即为在普通区域标记算法的基础上，通过给定不同的距离阈值DT，求得栅格聚类阈值NT = ëDT Gû， G为栅格尺寸大小， ëû ·表示向下取整。扩展连通区域至( 2NT - 1 )× ( 2NT - 1 )大小，将此障碍物栅格对应扩展区域范围内的障碍物栅格点聚类为同一个障碍物，这样就能有效地将障碍物离散的部分归为同一类。图5b为扩展至5×5格大小区域示意图，在障碍点周围5×5格范围内存在其他障碍物点，就将其赋值为相同标记号。所以本算法最重要的是需要计算出基于各个已知障碍点的聚类距离阈值DT。SKRZYPCZYNSKI 等 和甘志梅等 采用
［］ 16 ［］ 12固定距离阈值的方法完成障碍物聚类；考虑到激
光雷达的数据特点，障碍物不同角度的外部轮廓扫描点的距离阈值应不同，周俊静 提出了一种
［］ 17自适应阈值的聚类算法。BORGES等 提出了
［］ 13一种根据深度值来确定距离阈值 DT的方法，见图6。DT的计算表达式如下：
sin ( Δϕ )
DT = rn + 3σ r （ 1） -1
sin ( λ - Δϕ )
式中， rn- 1为前一点的深度值； σr为激光雷达的测量误差； Δϕ为激光雷达的角度分辨能力；为阈值参数。λ
图6 文献［ 13 ］提出的距离阈值计算
Fig.6 Calculation of distance threshold
from literature ［］ 13
由式（ 1）可知， DT的值取决于阈值参数λ，因此应严格选择阈值参数，避免出现当2个障碍物的距离过近时，将两者检测为同1个物体而合并成1个障碍物，从而导致出现欠分割的情况。最终，得到了1张标注后的栅格地图。在标注地图中，属于相同障碍物块的网格标注为同一数字。采用上述聚类算法的优点在于： ①符合激光雷达出射激光束间的角度具有均匀分布的特性，远处障碍物离散的部分也能较好地聚类在一起； ②避免改变障碍物块的轮廓，导致其形状特征的改变。
3.2 聚类修正
在经过空间方式聚类之后，由于距离阈值参数选择较严格，离本车较远或呈一定扫描角度的属于同一障碍物的障碍物块仍可能没有聚类在一起，从而造成过分割，因此本文提出了一种匹配聚类修正算法。首先通过最近邻域跟踪算法，寻找k- 1时刻与k时刻空间聚类结果中距离最近的障碍物块i，将其配对得到匹配后的障碍物块列表Oclu。障碍物信息包含障碍物块中心位置、速度、运动方向、回波脉冲宽度均值等参数，计算表达式如下： vi = (- y i, y i, 1) +( xi, - xi, 1) /ΔT （ 2）
2 2 k k - k k -
y i, - y i, θi = arctan| | （ 3）
k k -1 xi, - xi,
k k -1
Ti =( Ti, + Ti, 1) /2 （ 4）
k k -
式中，（ xi, k， y i, k）、（ xi, - 1， y i, - 1）分别为k时刻和k- 1时刻第
k k i个障碍物块的中心坐标； Ti, 、Ti, -1分别为k时刻和k- 1
k k
时刻第i个障碍物块的激光回波脉冲宽度均值； ΔT为两帧 数据时间差， vi为障碍物块的速度； θi为障碍物块的运动方向； Ti为两匹配障碍物块的激光回波脉冲宽度均值。
获得障碍物块信息之后，对于整个列表Oclu中每2个障碍物块，通过上述4个参数来计算其相似度S（i,j），j为第j个障碍物块。当相似度大于相似度阈值ST时，判定这2个目标为同一物体的不同部分，相似度计算表达式如下：
a b
S ( i, j )= + + (- xi xj ) +( yi - yj ) (- vi vj )
2 2 2 c d
+ （ 5） (- θi θj ) (- Ti Tj )
2 2
其中，、、、abcd 4个权重值及相似度阈值ST均由实验测得。遍历整个障碍物块列表之后，合并障碍物块，得到障碍物列表Otrack。并将k时刻障碍物列表与k- 1时刻障碍物列表进行匹配跟踪，完成后续的目标跟踪预测。
4 实车实验与结果分析
为验证上述障碍物检测算法的准确性和有效性，对无人驾驶汽车在真实道路上获取的数据进行分析。实验平台为江苏大学自主研发的智能驾驶汽车平台，搭载了有IBEO⁃LUX⁃2010的四线激光雷达，同时使用行车记录仪记录了当前场景的视频信息，实验地点为苏州某高架道路。
将本文算法与上文提到的固定距离阈值下的八连通区域标记算法进行了对比，通过对263组目标车辆进行实验分析，障碍物目标的聚类分割准确率见表2。本文算法在距本车50 m范围内的聚类效果较好，能达到80%以上；但在更远处，由于参数选取较为严格，聚类效果变差。而八连通区域标记算法的聚类效果随着目标距离的增加，聚类效果显著变差。
表2 聚类算法比较
Tab.2 Comparison of clustering algorithms 70 17.5 65.0
图7为障碍物检测结果对比图，其中第一列为采用传统八连通区域标记算法聚类获得的障碍物图像，第二列为采用本文基于聚类分割算法所检测到的障碍物图像，第三列为行车记录仪视频信息，矩形框为障碍物的最小包含矩形框。
在场景1（图7a）中，本文算法能够完整地获得前方两车的外部轮廓，并未出现过分割现象，其中1车距本车48 m左右， 2车距本车56 m左右。而
· ·
滤除。
（ 3）在聚类过程中，提出了一种网格聚类与密度聚类相结合的方法。根据激光雷达扫描特性，通过深度值来确定距离阈值，并转化为栅格聚类阈值，最后通过相邻帧障碍物块的匹配对聚类结果进行修正。
（ 4）从实验结果中可以看出，该方法能准确地完成障碍物的检测工作，滤除噪声并减少了过分割现象的发生。后续研究将通过识别环节对障碍物离散的不同部分进行聚类，进一步提高检测的准确性。
参考文献：
［］ 1 QI C R，SU H，MO K，et al. PointNet：Deep Learning on Point Sets for 3D Classification and Segmentation ［］ C //IEEE Conference on Computer Vision and Pattern Recognition. Las Vegas，2016： 77⁃85.
MANDICI S， NEDEVSCHI S. Aggregate Road Surface Based Environment Representation Using Digital Elevation Maps ［］ C //IEEE International Conference on Intelligent Computer Communication and Processing. Beijing，2014：149⁃156.
［］ 3 THRUN S，MONTEMERLO M，DAHLKAMP H， et al. Stanley： the Robot that Won the DARPA Grand Challenge ［］ J . Journal of Field Robotics， 2006，23（9）：661⁃692.
［］ 4 FERGUSON D，DARMS M，URMSON C，et al. Detection，Prediction，and Avoidance of Dynamic Obstacles in Urban Environments ［］ C //IEEE Intel⁃ ligent Vehicles Symposium. Piscataway： IEEE， 2008：1149⁃1154.
PFAFF P，TRIEBEL R，BURGARD W. An Effi⁃ cient Extension to Elevation Maps for Outdoor Ter⁃ rain Mapping and Loop Closing ［］ J . The Internation⁃ al Journal of Robotics Research，2007，26（2）：217 ⁃ 230.
［］ 6 DOUILLARD B，UNDERWOOD J，MELKUMY⁃ AN N，et al. Hybird Elevation Maps：3D Surface Models for Segmentation ［］ C //IEEE / RSJ Interna⁃ tional Conference on Intelligent Robots and Sys⁃ tems. St. Louis：IEEE，2010：1532⁃1538.
［］ 7 KONRAD M，SZCZOT M，SCHÜLE F，et al. Ge⁃ neric Grid Mapping for Road Course Estimation ［］ C // Intelligent Vehicles Symposium（IV）. Baden⁃ baden，2011：851⁃856.
［］ 8 PETROVSKAYA A，THRUN S. Model Based Ve⁃ hicle Detection and Tracking for Autonomous Urban Driving ［］ J . Autonomous Robots，2009，26（2）：123 ⁃ 139. ［ 9 ］ 程健. 基于三维激光雷达的实时目标检测［ D. ］杭州：浙江大学， 2014.
CHENG Jian. 3D Lidar Based Real ⁃ time Objects Detection ［］ D . Hangzhou： Zhejiang University， 2014.
［］ 10 YIAKOPOULOS C T，GRYLLIAS K C，ANTO⁃ NIADIS I A.Rolling Element Bearing Fault Detec⁃ tion in Industrial Environments Based on a K ⁃ means Clustering Approach ［］ J . Expert Systems with Applications，2011，38（3）：2888⁃2911.
NG R T，HAN J. Efficient and Effective Clustering Methods for Spatial Data Mining ［］ C //Proc. of the 20th VLDB Conference. Santiago，2010：144 ⁃ 155.
［ 12 ］ 甘志梅，王春香，杨明. 基于激光雷达的车辆跟踪与识别算法［ J. ］ 上海交通大学学报， 2009，43（6）： 923⁃926.
GAN Zhimei，WANG Chunxiang，YANG Ming. A Method for Vehicle Tracking and Recognition Based on Scanning Laser Radar ［］ J . Journal of Shanghai Jiaotong University，2009，43（6）：923 ⁃ 926.
BORGES G，ALDON M. Line Extraction in 2D Range Images for Mobile Robotics ［］ J . Journal of Intelligent and Robotic Systems，2004，40：267 ⁃ 297.
［ 14 ］ 段建民，李龙杰，郑凯华. 基于车载4线激光雷达的前方道路可行驶区域检测［ J. ］汽车电子， 2016，28 （ 2）：55⁃61.
DUAN Jianmin，LI Longjie，ZHENG Kaihua. Pre⁃ ceding Drivable Area Detection Based on Four⁃lay⁃ er Laser Radar ［］ J . Automobile Technology，2016， 28（2）：55⁃61.
FORSYTH D A，PONCE J. Computer Vision：a Modern Approach ［］ M . Englewood: Prentice Hall Professional Technical Reference，2002. SKRZYPCZYNSKI P. Building Geometrical map of environment using IR range finder data ［］ C //In⁃ telligent Autonomous Systems. Karlsruhe，1995： 408⁃412.
［ 17 ］ 周俊静.基于激光雷达的智能车辆目标识别与跟踪［ D. ］北京：北京工业大学， 2014.
ZHOU Junjing. Research on Key Technology of Lidar Based Object Detection and Tracking for In⁃ telligent Vehicles ［］ D . Beijing：Beijing University of Technology，2014.
(编辑 胡佳慧) 作者简介：王海，男， 1983年生，副教授、博士。研究方向为自动驾驶汽车技术。获中国公路学会科学技术一等奖、教育部科技进步二等奖各1项。发表论文30余篇。E⁃mail：wanghai1019@163.com。