A Fast Obstacle Detection Method by Fusion of Density-based Clustering and Region Growing Algorithms
LI Jiong1, ZHAO Kai2, ZHANG Zhichao2, ZHU Yuan2
1. Army Military Transportation University, Tianjin 300161, China; 2. Institute of Military Transportation, Army Military Transportation University, Tianjin 300161, China
李炯, 赵凯, 张志超, 朱愿. 一种融合密度聚类与区域生长算法的快速障碍物检测方法[J]. 机器人, 2020, 42(1): 60-70.DOI: 10.13973/j.cnki.robot.190202.
LI Jiong, ZHAO Kai, ZHANG Zhichao, ZHU Yuan. A Fast Obstacle Detection Method by Fusion of Density-based Clustering and Region Growing Algorithms. ROBOT, 2020, 42(1): 60-70. DOI: 10.13973/j.cnki.robot.190202.
摘要针对智能车在城市环境下采集的3维激光雷达点云中相邻障碍物难以区分、远距离检测易分裂以及小障碍物易漏检的问题，将密度聚类算法与区域生长算法融合，提出了一种鲁棒的障碍物快速检测方法．该方法首先利用区域生长算法对点云栅格完成第1次聚类并标记出可能含有更小障碍物的栅格，然后利用参数自适应的DBSCAN（density-based spatial clustering of applications with noise）对体积较大、可能包含多目标的障碍物检测结果进行细化，最后对已标记的栅格进行第2次区域生长聚类，完成小障碍物的检测．实验结果表明，本方法在城市环境下能够准确区分和检测出障碍物，检测准确率平均可达97%，平均耗时为13 ms．
Abstract：For the 3D point cloud collected by the LiDAR on the intelligent vehicle in urban environment, there exist some problems, for example that the adjacent obstacles are difficult to distinguish, the obstacles far away from the LiDAR are prone to split, and the small obstacles are easily missed. To solve these problems, a robust and fast obstacle detection method is proposed by combining the density-based clustering algorithm and the region growing algorithm. Firstly, the region growing algorithm is used to perform the first clustering of the point cloud grid and marks the grid which may contain smaller obstacles. Then, the parameter adaptive DBSCAN (density-based spatial clustering of applications with noise) algorithm is adopted to refine the detection results of large obstacles which may contain many objects. Finally, the marked grids are clustered by the region growing algorithm for the second time to complete the detection of small obstacles. The experimental results show that the proposed method can accurately distinguish and detect obstacles in urban environment. The detection accuracy is 97% on average, and the average time consumption is 13 ms.
[1] 赵凯,徐友春,李永乐,等.基于VG-DBSCAN算法的大场景散乱点云去噪[J].光学学报,2018,38(10):1028001-1-1028001-6.Zhao K, Xu Y C, Li Y L, et al. Large-scale scattered point-cloud denoising based on VG-DBSCAN algorithm[J]. Acta Optica Sinica, 2018, 38(10):1028001-1-1028001-6. [2] Azim A, Aycard O. Detection, classification and tracking of moving objects in a 3D environment[C]//IEEE Intelligent Vehicles Symposium. Piscataway, USA:IEEE, 2012:802-807. [3] Li Q H, Dai B, Fu H. LIDAR-based dynamic environmentmodeling and tracking using particles based occupancy grid[C]//IEEE International Conference on Mechatronics and Automation. Piscataway, USA:IEEE, 2016:238-243. [4] Vu T D, Burlet J, Aycard O. Grid-based localization and local mapping with moving object detection and tracking[J]. Information Fusion, 2011, 12(1):58-69. [5] 王任栋,徐友春,齐尧,等.一种鲁棒的城市复杂动态场景点云配准方法[J].机器人,2018,40(3):257-265.Wang R D, Xu Y C, Qi Y, et al. A robust point cloud registration method in urban dynamic environment[J]. Robot, 2018, 40(3):257-265. [6] Qi C R, Yi L, Su H, et al. PointNet++:Deep hierarchical feature learning on point sets in a metric space[C]//31st Annual Conference on Neural Information Processing Systems. San Diego, USA:Neural Information Processing Systems Foundation, 2017:5100-5109. [7] Qi C R, Su H, Mo K C, et al. PointNet:Deep learning on point sets for 3D classification and segmentation[C]//30th IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, USA:IEEE, 2017:77-85. [8] Yiakopoulos C T, Gryllias K C, Antoniadis I A. Rolling elementbearing fault detection in industrial environments based on a K-means clustering approach[J]. Expert Systems with Applications, 2011, 38(3):2888-2911. [9] Ng R T, Han J W. Efficient and effective clustering methods for spatial data mining[C]//20th International Conference on Very Large Data Bases. San Mateo, USA:Morgan Kaufmann, 1994:144-155. [10] Nurunnabi A, West G, Belton D. Outlier detection and robust normal-curvature estimation in mobile laser scanning 3D point cloud data[J]. Pattern Recognition, 2015, 48(4):1404-1419. [11] Ertöz L, Steinbach M, Kumar V. Finding clusters of differentsizes, shapes, and densities in noisy, high dimensional data[C]//3rd SIAM International Conference on Data Mining. Philadelphia, USA:Society for Industrial and Applied Mathematics Press, 2003:47-58. [12] Feng L, Liu K J, Tang F X, et al. GO-DBSCAN:Improvements of DBSCAN algorithm based on grid[J]. International Journal of Computer Theory and Engineering, 2017, 9(3):151-155. [13] Zaman F, Wong Y P, Ng B Y. Density-based denoising of pointcloud[M]//9th International Conference on Robotic, Vision, Signal Processing and Power Applications. Singapore:Spring-er, 2017:287-295. [14] 谢德胜,徐友春,王任栋,等.基于三维激光雷达的无人车障碍物检测与跟踪[J].汽车工程,2018,40(8):952-959.Xie D S, Xu Y C, Wang R D, et al. Obstacle detection and tracking for unmanned vehicles based on 3D laser radar[J]. Automotive Engineering, 2018, 40(8):952-959. [15] 苏本跃,马金宇,彭玉升,等.基于K-means聚类的RGBD点云去噪和精简算法[J].系统仿真学报,2016,28(10):2329-2334,2341.Su B Y, Ma J Y, Peng Y S, et al. Algorithm for RGBD point cloud denoising and simplification based on K-means clustering[J]. Journal of System Simulation, 2016, 28(10):2329-2334, 2341. [16] 苏志远,徐友春,李永乐.基于三维激光雷达的车辆目标检测方法[J].军事交通学院学报,2017,19(1):45-49.Su Z Y, Xu Y C, Li Y L. Vehicle targets detection method based on 3D Lidar[J]. Journal of Military Transportation University, 2017, 19(1):45-49. [17] 韩栋斌,徐友春,李华,等.基于手眼模型的三维激光雷达外参数标定[J].光电工程,2017,44(8):798-804.Han D B, Xu Y C, Li H, et al. Calibration of extrinsic parameters for three-dimensional lidar based on hand-eye model[J]. Opto-Electronic Engineering, 2017, 44(8):798-804. [18] 韩栋斌,徐友春,李华,等.无人车三维激光雷达反射强度校准[J].军事交通学院学报,2017,19(10):85-90.Han D B, Xu Y C, Li H, et al. Reflection intensity calibration of three-dimensional LIDAR on unmanned vehicle[J]. Journal of Military Transportation University, 2017, 19(10):85-90. [19] 陈文,岳惊涛,李华,等.基于图优化方法的点云三维环境重构[J].军事交通学院学报,2017,19(9):85-90.Chen W, Yue J T, Li H, et al. Three-dimensional reconstruction of point cloud based on graph optimization method[J]. Journal of Military Transportation University, 2017, 19(9):85-90. [20] 刘学柱.DPM模型参数对行人检测结果的影响研究[D].曲阜:曲阜师范大学,2017.Liu X Z. Study on the influence of DPM model parameters on pedestrian detection results[D]. Qufu:Qufu Normal University, 2017. [21] 刘家银,唐振民,王安东,等.基于多激光雷达与组合特征的非结构化环境负障碍物检测[J].机器人,2017,39(5):638-651.Liu J Y, Tang Z M, Wang A D, et al. Negative obstacle detection in unstructured environment based on multiple LiDARs and compositional features[J]. Robot, 2017, 39(5):638-651.
