光电工程  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 结论