使用Kdtree加速的DBSCAN进行点云聚类

作者：姜小明 @github

日期：2020-06-28

关键字：Kdtreee, DBSCAN, PCL, 点云

DBSCAN算法适用于点云聚类，但是3d点云数据一般较大，朴素的DBSCAN算法处理起来效率很低。对此，可以通过使用Kdtree检索临近点，从而加速DBSCAN算法。

1. DBSCAN

在点云数据分析中，我们经常需要对点云数据进行分割，提取感兴趣的部分。聚类是点云分割中的一类方法（其他方法有模型拟合、区域增长、基于图的方法、深度学习方法等）。DBSCAN 是一种基于密度的聚类算法，具有抗噪声、无需指定类别种数、可以在空间数据中发现任意形状的聚类等优点，适用于点云聚类。

1.1 概念

DBSCAN中为了增加抗噪声的能力，引入了核心对象等概念。

ε： 参数，邻域距离。

minPts： 参数，核心点领域内最少点数。

核心点： 在 $ϵ$ 邻域内有至少 $minPts$ 个邻域点的点为核心点。

直接密度可达： 对于样本集合 $D$，如果样本点 $q$ 在 $p$ 的 $ϵ$ 邻域内，并且 $p$ 为核心对象，那么对象 $q$ 从对象 $p$ 直接密度可达。

密度可达： 对于样本集合 $D$，给定一串样本点$p_1$, $p_2$, …, p n