点云聚类算法：EuclideanClustering和Fast Euclidean Clustering

发表于 更新于 分类于 ， 阅读次数： Changyan：

前言

最近在项目中要用到点云聚类算法来分割点云。场景需求比较简单。点云间的间隔也足够大。开始以为应该是一个简单的算法，准确率和效率应该很容易满足。一开始使用PCL中的EuclideanClusterExtraction类，根据欧式距离进行聚类对点云分割。由于场景十分简单，所以分割效果可以满足。但是耗时却非常高。处理一个不到4w点的点云竟然耗时达到8s。后面从网上查到一个叫FastEulideanClustering - FEC的算法，虽然也是使用欧式距离进行分类，但是论文中与PCL中的EuclideanClustering相比在时间上快了几十倍。

这篇比较简单梳理一下EuclideanClustering(EC)和Fast Euclidean Clustering(FEC)的原理和两者的主要区别。同时，自己实现一个example,对比两者的耗时。同时把代码上传备份。

EuclideanClustering(EC)

详细说明可以参考PCL官方文档：EuclideanClusterExtraction

EC算法的原理十分简单，随机选一个点，在该点处画一个半径Radius的球，所有位于球中的点归结为该点同一类。然后再随机选一个未分类的点，重复上述过程，直到所有点都被分类。

为了加速，在PCL中一般会使用kdtree来加速搜索。

EC算法的具体步骤如下：

  1. 为点云\(P\)构建Kd-tree
  2. 为当前类设置一个队列\(Q\)
  3. 随机选一个点\(p\)，将其加入\(Q\),然后执行下面步骤
    • 对\(Q\)中的每个点\(p_i\)，执行下面步骤
      • 以\(p_i\)为中心，半径为\(Radius\)画一个球，找到所有位于球内的点\(P_i^k\)
      • 对于\(P_i^k\)中的每个点\(p_j\)，如果该点没有被分类，将其加入\(Q\)
    • 当\(Q\)中所有的点被处理完（\(Q\)为空），则该类结束
  4. 重复步骤2-3，直到所有点都被分类

EC算法和RegionGrowing以及DBSCAN的区别

RegionGrowing-Based（RG）方法

RG方法是一种基于区域的方法，它将点云分割为不同的区域，每个区域都有一个种子点。然后，通过将相邻的点添加到区域中来增长区域。这个过程一直持续到没有更多的点可以添加到区域中为止。这种方法的一个缺点是，它需要一个种子点，而且对于不同的种子点，可能会得到不同的结果。此外，RG方法一般会使用不同的规则来确定相邻点，比如法向量的角度，曲率等。

RG方法的第一步是先确定一个随机点集合。随机点集的确定可以依赖一些先验知识，来获得更好的结果。

DBSCAN方法

Density-based spatial clustering of applications with noise (DBSCAN) 其实从步骤来说跟EC方法十分类似。不过在做近邻搜索的时候，还会判断近邻点的数量，如果在半径\(Radius\)内的近邻点数量小于某个阈值，则认为该点为噪声点，不进行分类。这也是Density的含义。

具体的DBSCAN方法可以参考：DBSCAN

Fast Euclidean Clustering(FEC)

论文：FEC: Fast Euclidean Clustering for Point Cloud Segmentation 论文中的代码链接有误，应该是：unageek/fast-euclidean-clustering

FEC算法基本原理

FEC算法也是基于欧式距离进行聚合分类。与EC算法不同之处在于，EC算法最外层循环是类别，先处理完一个类别再处理下一个类别。在处理一个类别的过程中，同一个点可能会多次加入队列。而FEC算法的最外层循环是点，每个点只会被处理一次。这样可以减少很多重复的计算。

FEC算法的具体步骤如下：

FEC算法步骤

虽然论文说了一大堆，但是具体步骤还是论文里这张图描述得清楚

FEC算法步骤可视化

实际测试

代码

代码已经上传到github:zeal-up/PointcloudClustering 该仓库中包含了EC和FEC的实现代码，以及测试代码。主要测试两者的耗时对比

数据

代码中包含一个生成虚拟点云数据的脚本，生成的点云效果如下：

虚拟点云

同时，该仓库中也包含一个从激光雷达点云截取出的部分点云：

真实点云

测试结果

上述的两个点云案例都十分简单，分割明确。而且均是一个二分类问题。两个算法在分割效果上均正常。 上述生成的虚拟点云一共4w个点，真实点云大约有3w个点。

该真实点云的耗时比合成的点云在EC方法上的耗时要比合成的点云高很多，这点不清楚为什么。

对于该真实点云，EC方法耗时为：5414.84ms，FEC方法耗时为：36.761ms。可以看到FEC方法在耗时上比EC方法快了100倍以上。