点云学习笔记24：加速的DBSCAN聚类算法，Kdtree在其中的作用

点云学习笔记24——使用Kdtree加速的DBSCAN进行点云聚类

• ​​1. DBSCAN概述​​

• ​​DBSCAN算法描述:​​
• ​​计算步骤​​

• ​​算法原理​​
• ​​源码实战​​
• ​​效果图​​

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

1. DBSCAN概述

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

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。

DBSCAN中的几个定义：

• Ε邻域：给定对象半径为Ε内的区域称为该对象的Ε邻域；
• 核心对象：如果给定对象Ε邻域内的样本点数大于等于MinPts，则称该对象为核心对象；
• 直接密度可达：对于样本集合D，如果样本点q在p的Ε邻域内，并且p为核心对象，那么对象q从对象p直接密度可达。
• 密度可达：对于样本集合D，给定一串样本点p1,p2….pn，p= p1,q= pn,假如对象pi从pi-1直接密度可达，那么对象q从对象p密度可达。
• 密度相连：存在样本集合D中的一点o，如果对象o到对象p和对象q都是密度可达的，那么p和q密度相联。

可以发现，密度可达是直接密度可达的传递闭包，并且这种关系是非对称的。密度相连是对称关系。DBSCAN目的是找到密度相连对象的最大集合。

DBSCAN算法描述:

输入: 包含n个对象的数据库，半径e，最少数目MinPts;
输出:所有生成的簇，达到密度要求。

• (1)Repeat
• (2)从数据库中抽出一个未处理的点；
• (3)IF抽出的点是核心点 THEN 找出所有从该点密度相连的对象，形成一个簇；
• (4)ELSE 抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一个点；
• (5)UNTIL 所有的点都被处理。
  DBSCAN对用户定义的参数很敏感，细微的不同都可能导致差别很大的结果，而参数的选择无规律可循，只能靠经验确定。

计算步骤

DBScan需要二个参数： 扫描半径 (eps) 和 最小包含点数(minPts)。 任选一个未被访问(unvisited)的点开始，找出与其距离在eps之内(包括eps)的所有附近点。

• 如果 附近点的数量 ≥ minPts，则当前点与其附近点形成一个簇，并且出发点被标记为已访问(visited)。 然后递归，以相同的方法处理该簇内所有未被标记为已访问(visited)的点，从而对簇进行扩展。
• 如果 附近点的数量 < minPts，则该点暂时被标记作为噪声点。
• 如果簇充分地被扩展，即簇内的所有点被标记为已访问，然后用同样的算法去处理未被访问的点。

算法原理

源码实战

​​https://github.com/JaminJiang/dbscan_kdtree​​

码云地址：
​​​https://gitee.com/qitiandashengdiyun/dbscan_kdtree_1​​

cd build/
cmake .. 
make -j8
./pcl_cluster

效果图

源码：
​​​https://github.com/JaminJiang/dbscan_kdtree​​