LiDAR object detection based on optimized DBSCAN algorithm

Cai Huaiyu; Chen Yanzhen; Zhuo Liran; Chen Xiaodong

doi:10.12086/oee.2019.180514

Article navigation > Opto-Electronic Engineering > 2019 Vol. 46 > No. 7 > 180514

Next Article Previous Article

Cai Huaiyu, Chen Yanzhen, Zhuo Liran, et al. LiDAR object detection based on optimized DBSCAN algorithm[J]. Opto-Electronic Engineering, 2019, 46(7): 180514. doi: 10.12086/oee.2019.180514

Citation:

Cai Huaiyu, Chen Yanzhen, Zhuo Liran, et al. LiDAR object detection based on optimized DBSCAN algorithm[J]. Opto-Electronic Engineering, 2019, 46(7): 180514. doi: 10.12086/oee.2019.180514

LiDAR object detection based on optimized DBSCAN algorithm

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

Fund Project: Supported by Tianjin Science and Technology Plan Fund (17ZXRGGX00140)

More Information

Corresponding author: Chen Yanzhen, E-mail: cyz123@tju.edu.cn

Received Date 08 October 2018

Revised Date 10 January 2019

Published Date 01 July 2019

Abstract

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%.
- obstacle detection /
- clustering /
- DBSCAN algorithm /
- neighborhood radius

FullText(HTML)

References

[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. Google Scholar
[2]	林川, 宋伟奇, 覃金飞.基于V-视差的障碍物检测改进方法[J].科学技术与工程, 2014, 14(1): 86-90. doi: 10.3969/j.issn.1671-1815.2014.01.018 CrossRef Google Scholar 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. doi: 10.3969/j.issn.1671-1815.2014.01.018 CrossRef Google Scholar
[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. doi: 10.1109/TITS.2011.2113340 CrossRef Google Scholar
[4]	曾丽娜.车载视觉系统中障碍物检测与识别方法研究[D].南京: 南京航空航天大学, 2016. Google Scholar Zeng L N. Research on obstacle detection and identification for on-board vision systems[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2016.http://cdmd.cnki.com.cn/Article/CDMD-10287-1016926236.htm Google Scholar
[5]	万忠涛.基于激光雷达的道路与障碍检测研究[D].长沙: 国防科学技术大学, 2010. Google Scholar Wan Z T. Research on LADAR based road and obstacles detection[D]. Changsha: National University of Defense Technology, 2010.http://cdmd.cnki.com.cn/Article/CDMD-90002-1011279781.htm Google Scholar
[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. Google Scholar
[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. Google Scholar
[8]	吴伟民, 黄焕坤.基于差分隐私保护的DP-DBScan聚类算法研究[J].计算机工程与科学, 2015, 37(4): 830-834. doi: 10.3969/j.issn.1007-130X.2015.04.033 CrossRef Google Scholar 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. doi: 10.3969/j.issn.1007-130X.2015.04.033 CrossRef Google Scholar
[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. Google Scholar
[10]	周水庚, 周傲英, 曹晶.基于数据分区的DBSCAN算法[J].计算机研究与发展, 2000, 37(10): 1153-1159. Google Scholar 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. Google Scholar
[11]	孔栋, 孙亮, 王建强, 等.基于3D激光雷达点云的道路边界识别算法[J].广西大学学报(自然科学版), 2017, 42(3): 855-863. Google Scholar 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. Google Scholar
[12]	关超华, 陈泳丹, 陈慧岩, 等.基于改进DBSCAN算法的激光雷达车辆探测方法[J].北京理工大学学报, 2010, 30(6): 732-736. Google Scholar 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. Google Scholar
[13]	于亚飞, 周爱武.一种改进的DBSCAN密度算法[J].计算机技术与发展, 2011, 21(2): 30-33, 38. doi: 10.3969/j.issn.1673-629X.2011.02.008 CrossRef Google Scholar Yu Y F, Zhou A W. An improved algorithm of DBSCAN[J]. Computer Technology and Development, 2011, 21(2): 30-33, 38. doi: 10.3969/j.issn.1673-629X.2011.02.008 CrossRef Google Scholar
[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. Google Scholar
[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. Google Scholar
[16]	Birant D, Kut A. ST-DBSCAN: an algorithm for clustering spatial-temporal data[J]. Data & Knowledge Engineering, 2007, 60(1): 208-221. Google Scholar
[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. Google Scholar
[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. doi: 10.1109/34.506793 CrossRef Google Scholar
[19]	胡顺玺.基于三维激光扫描仪的车辆前方行人检测研究[D].长春: 吉林大学, 2011. Google Scholar Hu S X. Study on the vehicle front pedestrian detection based on 3D laser scanner[D]. Changchun: Jilin University, 2011.http://cdmd.cnki.com.cn/Article/CDMD-10183-1011099654.htm Google Scholar
[20]	冯少荣, 肖文俊. DBSCAN聚类算法的研究与改进[J].中国矿业大学学报, 2008, 37(1): 105-111. doi: 10.3321/j.issn:1000-1964.2008.01.021 CrossRef Google Scholar Feng S R, Xiao W J. An Improved DBSCAN clustering algorithm[J]. Journal of China University of Mining & Technology, 2008, 37(1): 105-111. doi: 10.3321/j.issn:1000-1964.2008.01.021 CrossRef Google Scholar
[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. doi: 10.1109/TGRS.2007.900697 CrossRef Google Scholar
[22]	Yu Z W, Wang D X, You J, et al. Progressive subspace ensemble learning[J]. Pattern Recognition, 2016, 60: 692-705. doi: 10.1016/j.patcog.2016.06.017 CrossRef Google Scholar
[23]	李龙杰.基于四线激光雷达的道路信息提取技术研究[D].北京: 北京工业大学, 2016. Google Scholar Li L J. Research on technology of road information extraction based on four-layer laser radar[D]. Beijing: Beijing University of Technology, 2016.http://cdmd.cnki.com.cn/Article/CDMD-10005-1016785513.htm Google Scholar
[24]	于春和, 刘济林.越野环境下基于四线激光雷达的障碍检测[J].南京理工大学学报, 2006, 30(5): 618-621, 625. doi: 10.3969/j.issn.1005-9830.2006.05.019 CrossRef Google Scholar 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. doi: 10.3969/j.issn.1005-9830.2006.05.019 CrossRef Google Scholar

Overview

Overview

Overview: Obstacle detection is one of important research fields of intelligent vehicle environment perception technology. It is important for vehicles driving to detect the obstacles quickly and accurately. There are two main types of obstacle detection methods: based on visual sensors and based on LiDAR sensors. Since the latter method has the characteristics of no-susceptible to environmental impact, strong anti-interference, high ranging accuracy and etc, it is widely studied and applied in obstacle detection. Cluster analysis is one of the most commonly methods in LiDAR detection. Among them, DBSCAN algorithm is widely used because it can obtain clusters of arbitrary shape without knowing the number of classes in advance and can also identify noise points effectively. In order to detect obstacles quickly and accurately, this paper proposed an optimized DBSCAN algorithm which improves the adaptability under different distance by optimize the selection method of neighborhood radius. The procedure of obstacle detection in this paper includes four steps: road boundary detection, ROI region data extraction, ground data removal and optimized DBSCAN algorithm clustering. Firstly, use the characteristic that the structured road boundary point has obvious elevation mutation than the ground point, detect the local Z-value abrupt changing point and use the least square method to fit out the road boundary. Then, according to road boundary, extract the data of the inside area (the ROI area) of the road boundary. Next, fit the ground plane in ROI area and remove them from ROI. Finally, use optimized DBSCAN algorithm to handle the data in ROI after boundary detecting and removing. The Ford Campus dataset which is acquired by the University of Michigan and Ford Motor Company is used to test the performance of the optimized DBSCAN algorithm. The experiments were performed on a computer with 4 GB memory and 3 GHz clock frequency, and programmed on MATLAB. The experiment results show that the effect of the optimized DBSCAN algorithm is significantly improved for both short-range and long-range targets. Compared with the traditional DBSCAN algorithm, the positive detection rate of obstacle detection improves and the false detection rate reduced significantly. Since some false detections caused by road boundary detection error, we can improve the accuracy of boundary detection by multi-sensors fusion in the future. Considering the driving environment of the unmanned vehicle, multi-sensors fusion can be applied to the algorithm, and the robustness and stability of the algorithm will be further improved.