﻿ 基于优化DBSCAN算法的激光雷达障碍物检测
 光电工程  2019, Vol. 46 Issue (7): 180514      DOI: 10.12086/oee.2019.180514

1. 天津大学精密仪器与光电子工程学院，天津 300072;
2. 天津大学光电信息技术教育部重点实验室，天津 300072

LiDAR object detection based on optimized DBSCAN algorithm
Cai Huaiyu1,2, Chen Yanzhen1,2, Zhuo Liran1,2, Chen Xiaodong1,2
1. School of Precision Instrument and Opto-Electronics Engineering, Tianjin University, Tianjin 300072, China;
2. Key Laboratory of Opto-Electronics Information Technology of Ministry of Education, Tianjin University, Tianjin 300072, China
Abstract: In the process of obstacle detection based on LiDAR, the traditional DBSCAN clustering algorithm can't achieve good clustering for both short-range and long-distance targets because of the uneven distribution of data density, resulting in missed detection or false detection. To solve the problem, this paper proposed an optimized DBSCAN algorithm which improves the adaptability under different distance by optimize the selection method of neighborhood radius. According to the distribution of the lines scanned by LiDAR, the distance between two adjacent scan lines is determined and an improved neighborhood radius list is established. Then the neighborhood radius will be searched in the list based on the coordinated values of each scan point. Finally, linear interpolation method is used to obtain the corresponding neighborhood radius. The experimental results based on Ford dataset prove that compared with the traditional DBSCAN algorithm, the proposed algorithm can effectively improve the accuracy of obstacle detection and adapt to the target clustering operation under different distances. The positive detection rate of obstacle detection is increased by 17.52%.
Keywords: obstacle detection    clustering    DBSCAN algorithm    neighborhood radius

1 引言

2 障碍物检测方法

 图 1 障碍物检测流程 Fig. 1 Flow chart of obstacle detection
2.1 道路边界检测

2.2 感兴趣(ROI)区域数据提取

 $A = \{ P|P \in {\rm{ left\_border右侧数据 \} ,}}$ (1)
 $B = \left\{ {P|P \in {\rm{ right \_ border }}} \right.左侧数据\} ,$ (2)

 ${R_{{\rm{ROI}}}} = A \cap B。$ (3)
2.3 地面拟合

 ${{\mathit{\boldsymbol{a}}}}x + {{\mathit{\boldsymbol{b}}}}y + {{\mathit{\boldsymbol{c}}}}z = d,$ (4)

 ${{\mathit{\boldsymbol{a}}}}{}^2 + {{{\mathit{\boldsymbol{b}}}}^2} + {{{\mathit{\boldsymbol{c}}}}^2} = 1,$ (5)

d为坐标原点到该平面的距离。利用最小二乘法可以计算出参数abcd的值。

 ${{\mathit{\boldsymbol{a}}}}{x_i} + {{\mathit{\boldsymbol{b}}}}{y_i} + {{\mathit{\boldsymbol{c}}}}{z_i} = {d_i}。$ (6)

2.4 传统DBSCAN聚类算法

1) 算法对输入参数ε和MinPts极其敏感，如果参数选取不当，对聚类效果会产生不良影响；

2) 算法在整个聚类过程中使用了统一的ε和MinPts，该方式在数据分布比较均匀时，对聚类结果不会产生很大影响；但如果数据分布明显不均匀时，会使聚类效果出现较大偏差[23-24]

2.5 优化DBSCAN聚类算法

 图 2 激光雷达扫描线 Fig. 2 LiDAR scan line

ε*列表的建立方法是：假设激光雷达共有n条扫描线，如图 2所示。当激光雷达原点距地平面高度为h时，扫描线的俯仰角构成集合$\alpha = \{ {\alpha _i}\} (i = 1,2,...,n)$，激光扫描线投射点到O点的径向距离构成集合$r = \{ {r_i}\} (i = 1,2,...,n)$，相邻两条激光扫描线投射点的距离构成集合$\varepsilon = \{ {\varepsilon _i}\} (i = 1,2,...,n - 1)$r$\varepsilon$对应元素满足${r_i} = h/\tan ({\alpha _i})(i = 1,2,...,n)$${\varepsilon _i} = {r_{i + 1}} - {r_i}\;\;(i = 1,2,...,n - 1) h=1，则集合r修改为\{ 1/\tan ({\alpha _i})\} (i = 1,2,...,n)，记作r*；对应的集合ε修改为\{ r_{i + 1}^* - r_i^*\} \begin{array}{*{20}{c}} {(i = 1,2,...,n - 1)} \end{array}，记作ε*；至此，ε*列表建立完成。 ε*列表使用方法：假设存在一个三维空间点P(x,y,z)，到z轴的距离{r_P} = \sqrt {{x^2} + {y^2}} ，对应的r_P^* = \sqrt {{{(x/z)}^2} + {{(y/z)}^2}} ；在r*列表中寻找r_k^*$$r_{k + 1}^*$，使得$r_k^* \leqslant r_P^* \leqslant r_{k + 1}^*$，在ε*列表中存在对应的$\varepsilon _k^*$$\varepsilon _{k + 1}^*$。根据一阶线性插值法，则任意点$P(x,y,z)$处的ε值为

 $\varepsilon = \frac{{\varepsilon _{k + 1}^* - \varepsilon _k^*}}{{r_{k + 1}^* - r_k^*}}{r_P}。$ (7)
3 实验结果分析

 图 3 道路边界检测结果 Fig. 3 Road-boundary detection result

ROI区域提取和地面拟合结果分别如图 4图 5所示。其中地面拟合阈值$\Delta d$设置为0.05 m。经过上述处理，ROI区域和地面数据点云已经被提取出来，以便减小后续处理的数据量，并剔除地面数据对障碍物检测造成的影响。

 图 4 ROI区域数据提取结果 Fig. 4 Data extraction of ROI

 图 5 地面拟合结果 Fig. 5 Ground fitting

 图 6 双距离障碍物检测实验。(a)双距离障碍物数据采集场景；(b)激光点云图；(c)传统DBSCAN算法聚类效果；(d)优化DBSCAN算法聚类效果 Fig. 6 The experiment of double-distance obstacle detection. (a) Dataset scene of two distance obstacle; (b) LiDAR points cloud; (c) Traditional DBSCAN algorithm; (d) Optimized DBSCAN algorithm

 图 7 三距离障碍物检测实验。(a)数据采集场景；(b)传统DBSCAN聚类算法效果；(c)优化DBSCAN聚类效果 Fig. 7 The experiment of three-distance obstacle detection. (a) Dataset scene; (b) Traditional DBSCAN algorithm; (c) Optimized DBSCAN algorithm

 图 8 多种距离障碍物检测实验。(a)数据采集场景；(b)传统DBSCAN聚类算法效果；(c)优化DBSCAN聚类效果 Fig. 8 The experiment of multi-distance obstacle detection. (a) Dataset scene; (b) Traditional DBSCAN algorithm; (c) Optimized DBSCAN algorithm

 连续帧数 300 500 800 检测结果 正检 误检 漏检 正检 误检 漏检 正检 误检 漏检 传统DBSCAN算法 209 27 87 346 41 139 539 69 253 优化DBSCAN算法 253 42 13 438 59 21 695 97 41
4 结论

 [1] Kostavelis I, Nalpantidis L, Gasteratos A. Supervised traversability learning for robot navigation[C]//Proceedings of the 12th Annual Conference on Towards Autonomous Robotic Systems, 2011: 289-298. [2] Lin C, Song W Q, Qin J F. Improved method of obstacle detection based on V-disparity[J]. Science Technology and Engineering, 2014, 14(1): 86-90. 林川, 宋伟奇, 覃金飞. 基于V-视差的障碍物检测改进方法[J]. 科学技术与工程, 2014, 14(1): 86-90 [Crossref] [3] Jazayeri A, Cai H Y, Tuceryan M, et al. Vehicle detection and tracking in car video based on motion model[J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(2): 583-595. [Crossref] [4] Zeng L N. Research on obstacle detection and identification for on-board vision systems[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2016. 曾丽娜.车载视觉系统中障碍物检测与识别方法研究[D].南京: 南京航空航天大学, 2016. [Crossref] [5] Wan Z T. Research on LADAR based road and obstacles detection[D]. Changsha: National University of Defense Technology, 2010. 万忠涛.基于激光雷达的道路与障碍检测研究[D].长沙: 国防科学技术大学, 2010. [Crossref] [6] Himmelsbach M, Hundelshausen F V, Wuensche H J. Fast segmentation of 3D point clouds for ground vehicles[C]//Proceedings of 2010 IEEE Intelligent Vehicles Symposium, 2010: 560-565. [7] Moras J, Cherfaoui V, Bonnifait P. Credibilist occupancy grids for vehicle perception in dynamic environments[C]//Proceedings of 2011 IEEE International Conference on Robotics and Automation, 2011: 84-89. [8] Wu W M, Huang H K. A DP-DBScan clustering algorithm based on differential privacy preserving[J]. Computer Engineering and Science, 2015, 37(4): 830-834. 吴伟民, 黄焕坤. 基于差分隐私保护的DP-DBScan聚类算法研究[J]. 计算机工程与科学, 2015, 37(4): 830-834 [Crossref] [9] Azim A, Aycard O. Layer-based supervised classification of moving objects in outdoor dynamic environment using 3D laser scanner[C]//Proceedings of 2014 IEEE Intelligent Vehicles Symposium, 2014: 1408-1414. [10] Zhou S G, Zhou A Y, Cao J. A data-partitioning-based DBSCAN algorithm[J]. Journal of Computer Research and Development, 2000, 37(10): 1153-1159. 周水庚, 周傲英, 曹晶. 基于数据分区的DBSCAN算法[J]. 计算机研究与发展, 2000, 37(10): 1153-1159 [Crossref] [11] Kong D, Sun L, Wang J Q, et al. Road boundary identification algorithm based on 3D LIDAR point cloud[J]. Journal of Guangxi University (Natural Science Edition), 2017, 42(3): 855-863. 孔栋, 孙亮, 王建强, 等. 基于3D激光雷达点云的道路边界识别算法[J]. 广西大学学报(自然科学版), 2017, 42(3): 855-863 [Crossref] [12] Guan C H, Chen Y D, Chen H Y, et al. Improved DBSCAN clustering algorithm based vehicle detection using a vehicle-mounted laser scanner[J]. Journal of Beijing Institute of Technology, 2010, 30(6): 732-736. 关超华, 陈泳丹, 陈慧岩, 等. 基于改进DBSCAN算法的激光雷达车辆探测方法[J]. 北京理工大学学报, 2010, 30(6): 732-736 [Crossref] [13] Yu Y F, Zhou A W. An improved algorithm of DBSCAN[J]. Computer Technology and Development, 2011, 21(2): 30-33, 38. 于亚飞, 周爱武. 一种改进的DBSCAN密度算法[J]. 计算机技术与发展, 2011, 21(2): 30-33, 38 [Crossref] [14] Kaempchen N, Buehler M, Dietmayer K. Feature-level fusion for free-form object tracking using laserscanner and video[C]//Proceedings of the IEEE Proceedings. Intelligent Vehicles Symposium, 2005: 453-458. [15] Chavez-Garcia R O, Burlet J, Vu T D, et al. Frontal object perception using radar and mono-vision[C]//Proceedings of 2012 IEEE Intelligent Vehicles Symposium, 2012: 159-164. [16] Birant D, Kut A. ST-DBSCAN: an algorithm for clustering spatial-temporal data[J]. Data & Knowledge Engineering, 2007, 60(1): 208-221. [Crossref] [17] Guo C Z, Sato W, Han L, et al. Graph-based 2D road representation of 3D point clouds for intelligent vehicles[C]//Proceedings of 2011 IEEE Intelligent Vehicles Symposium, 2011: 715-721. [18] Barzohar M, Cooper D B. Automatic finding of main roads in aerial images by using geometric-stochastic models and estimation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18(7): 707-721. [Crossref] [19] Hu S X. Study on the vehicle front pedestrian detection based on 3D laser scanner[D]. Changchun: Jilin University, 2011. 胡顺玺.基于三维激光扫描仪的车辆前方行人检测研究[D].长春: 吉林大学, 2011. [Crossref] [20] Feng S R, Xiao W J. An Improved DBSCAN clustering algorithm[J]. Journal of China University of Mining & Technology, 2008, 37(1): 105-111. 冯少荣, 肖文俊. DBSCAN聚类算法的研究与改进[J]. 中国矿业大学学报, 2008, 37(1): 105-111 [Crossref] [21] Zhou J, Cheng L, Bischof W F. Online learning with novelty detection in human-guided road tracking[J]. IEEE Transactions on Geoscience and Remote Sensing, 2007, 45(12): 3967-3977. [Crossref] [22] Yu Z W, Wang D X, You J, et al. Progressive subspace ensemble learning[J]. Pattern Recognition, 2016, 60: 692-705. [Crossref] [23] Li L J. Research on technology of road information extraction based on four-layer laser radar[D]. Beijing: Beijing University of Technology, 2016. 李龙杰.基于四线激光雷达的道路信息提取技术研究[D].北京: 北京工业大学, 2016. [Crossref] [24] Yu C H, Liu J L. Obstacle detection based on a four-layer laser radar in cross-country[J]. Journal of Nanjing University of Science and Technology, 2006, 30(5): 618-621, 625. 于春和, 刘济林. 越野环境下基于四线激光雷达的障碍检测[J]. 南京理工大学学报, 2006, 30(5): 618-621, 625 [Crossref]