LiDAR Object Detection Based on Optimized DBSCAN Algorithm


In recent years, unmanned driving technology has developed rapidly, and obstacle detection has become an important research field in the unmanned environment sensing technology. It is very important to quickly and accurately detect the obstacle content in front of the vehicle, which is very important for the safe driving of the driverless smart car. Typical obstacle detections are divided into two main methods based on visual sensors and radar sensors. The detection method based on visual sensor is greatly affected by environmental factors, and it is difficult to obtain the depth information of the obstacle. However, the radar-based detection has been extensively studied because it is less susceptible to external environmental conditions and has stronger anti-interference performance, faster processing speed. People can directly obtain depth information of the environment through radar. 3D LiDAR is one of the important sensors for obstacle detection due to its high precision, high resolution and high reliability.

        In the obstacle detection method with LiDAR , point cloud clustering is a very important part in the detection process. The DBSCAN algorithm (Density-Based Spatial Clustering of Applications with Noise) is a classical density clustering algorithm, which does not need to know the number or the shape of clusters in advance. And this method can effectively identify noise points. However, the traditional DBSCAN algorithm is extremely sensitive to the input parameters ε and MinPts. If the parameters are not properly selected, the clustering effect will be adversely affected. The LiDAR output is a typical uneven data distribution. When using the traditional DBSCAN algorithm to cluster the lidar datawith fixed ε and MinPts values, there will always be some problems of missing or false detection of obstacles in some distance. The study of the DBSCAN algorithm presents new challenges that cannot meet the need for accurate detection of obstacles in unmanned applications.

       The research team of Professor Cai Huaiyu and Chen Xiaodong of Tianjin University relies on the Unmanned Cross-Disciplinary Research Platform of Tianjin University. They are committed to the research of environment-aware technology for intelligent driving vehicles. Based on the defects of the traditional DBSCAN algorithm, an optimized DBSCAN algorithm is developed. The invariant clustering radius parameter ε used in the traditional algorithm was no longer used in the clustering process, and the distance factor is introduced into the clustering parameter ε based on the distribution characteristics of the LiDAR scanning line to ensure the ε parameter can be adaptively adjusted corresponds to the density of the data points changes at different distances , which can finally improve the accuracy of clustering.

Fig.1 Lidar scan line

       Although the traditional DBSCAN algorithm can find clusters of arbitrary shapes and can effectively identify noise points, there are still some limitations: the algorithm uses uniform ε and MinPts in the whole clustering process. When the data distribution is relatively uniform, the clustering results will not have a large impact; however, if the data distribution is significantly uneven, the clustering effect will be greatly deviated. In this paper, based on the distribution characteristics of LiDAR scanning lines as shown in Figure 1, the ε* list is established. It can be seen that the space of the LiDAR scanning points increases with the increase of the detection distance. Therefore, this paper combines the height of the LiDAR from the ground and the elevation angle of the scanning line to calculate the distance between the projection points of two adjacent laser scanning lines to build ε* list.

       The distance to the z-axis of the LiDAR is calculated according to the coordinates of the three-dimensional space point. Then search corresponding εk*, εk+1* in the ε* list according to the calculation result. And finally according to the first-order linear interpolation method, the value of ε at an arbitrary point can be calculated. In order to verify the effectiveness of the proposed algorithm, the performance of the algorithm was tested using Velodyne 64 line LiDAR data from the Ford campus dataset. The experimental results are shown in Figure 2. The improved algorithm can simultaneously detect obstacles at different distances, resulting in a significant drop in the rate of missed detection.

(a)                                            (b)                                           (c)

Fig. 2 The experiment of multi-distance obstacle detection.

(a) Dataset scene; (b) Traditional DBSCAN algorithm; (c) Optimized DBSCAN algorithm

About the Group

Unmanned Vehicle Cross Research Center of Tianjin University was founded in March 2016, is multidisciplinary cross research platform composed of research teams from vehicle power, photoelectric engineering, image processing, machine learning, automatic control, mathematical optimization and nonlinear systems. The main research direction in intelligent driving including perception, planning, decision-making, control system design, core algorithm research and intelligent vehicle multidimensional test and evaluation technology, etc. As one of the core team in cross research center, research team led by Professor Cai Huaiyu , Chen Xiaodong from School of Precision Instruments & Opto-Electronics Engineering team main research direction for the opto-electric detection and imaging technology, responsible for environment perception hardware system design, sensor calibration, and obstacle detection and tracking algorithm research based on the lidar, visible/infrared cameras. The center has more than 20 professors, associate professors and lecturers, more than 60 doctoral and master's students, including 1 National Excellent Youth, 1 Young Yangtze River Scholar and 5 New Century Talents from the Ministry of Education. The center has published more than 160 SCI/EI papers and obtained more than 40 invention patents authorized by the state. Related research achievements have won the first prize of natural science of China society of electronics (ranked second), the third prize of Tianjin natural science and other awards. Participated in the "World Intelligent Driving Challenge" for two consecutive years, and won many awards, such as the excellence award of unmanned driving group cross-country race, the excellence award of urban block scene race, the best rural road access award, and the leading award of virtual scene group.


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