FEC：用于点云分割的快速欧几里德聚类方法

点云PCL博主

发布于 2022-12-27 18:08:37

1.4K0

发布于 2022-12-27 18:08:37

文章被收录于专栏：点云PCL点云PCL

文章：FEC: Fast Euclidean Clustering for Point Cloud Segmentation

作者：Yu Cao , Yancheng Wang , Yifei Xue, Huiqing Zhang and Yizhen Lao

编辑：点云PCL

来源：arXiv 2022

欢迎各位加入免费知识星球，获取PDF论文，欢迎转发朋友圈。文章仅做学术分享，如有侵权联系删文。未经博主同意请勿擅自转载。

公众号致力于分享点云处理，SLAM，三维视觉，高精地图相关的文章与技术，欢迎各位加入我们，一起交流一起进步,有兴趣的可联系微信：920177957。本文来自点云PCL博主的分享，未经作者允许请勿转载，欢迎各位同学积极分享和交流。

摘要

点云数据的分割在遥感、移动机器人或自动驾驶汽车等许多应用中至关重要，然而，由3D距离传感器捕获的点云通常是稀疏和非结构化的，这给实现有效分割带来了挑战，本文提出了一种计算量很小且点云实例分割快速的解决方案。这是一种新的快速欧几里德聚类（FEC）算法，该算法在现有工作中使用的聚类方案之上应用了逐点方案，该方法概念简单，且易于实现（在C++中为40行），与经典分割方法相比，实现快两个数量级速度，同时产生高质量的分割结果。

图1：所提出方法FEC对一个KITTI序列的无组织点云实例分割结果，该序列具有2700万个点，FEC优于现有的分割方法。

主要贡献

点云是包含大量3D点云的数据结构，通过使用激光雷达或2D图像获得，点云分割具有广泛的应用，从三维感知和遥感三维数据处理到虚拟现实中的三维重建，例如，机器人必须识别场景中的障碍物，以便能够在场景中进行交互和移动，实现这一目标需要区分不同的语义标签以及具有相同语义标签的各种实例，因此，有必要研究分割问题。

点云分割可分为三大类：

基于区域增长的方法，主要思想是分割具有均匀几何特性的点云，首先选择种子点，然后合并相邻点，如果它们在表面点属性（如方向、表面法线和曲率）方面具有相似性，然而，这些方法对初始种子的位置和边界附近法线和曲率的不准确估计非常敏感，这会导致过度分割或欠分割。
基于聚类的方法。聚类算法根据元素的相似性将元素划分为类别，可应用于点云分割。因此，K均值、均值漂移、DBSCAN和欧几里德聚类提取（EC）常被用于这项任务，尽管基于聚类的方法简单，但点云中每个点的高迭代率导致了高计算负担并降低了效率。
3.基于学习的方法其他当前方法直接在点云上使用深度学习或投影到二维图像中，以分割点云中的实例，基于深度学习的方法通常存在运行时间长和处理大规模点云的问题。

如表1所示，本文重点关注了最新点云分割方案的计算速度，本文的提出的分割过程分为两个步骤：（i）地面点移除和（ii）将剩余点聚类成有意义的集合。

本文提出的解决方案在合成数据和实际数据上进行了广泛测试，结果证明了我们的方法相对于现有技术的效率。快速分割将宝贵的硬件资源放置到其他流程程序中对计算要求更高的进程中。本文的贡献总结如下：

提出了一种新的欧几里德聚类算法，该算法针对现有工作中应用的聚类方案使用逐点聚类。
将所提出的快速欧几里得聚类算法应用于一般点云分割问题，实现了类似的质量，但比现有工作加快了100倍。代码（用C++、Matlab和Python实现）将在文章接受后公开。

主要内容

A.地面去除：地面上的点云构成了大部分输入数据，降低了计算速度，此外，地面数据影响分割质量，因为它改变了输入的连通性，因此，必须去除地面作为预处理，许多接地点提取方法，如基于网格的方法和平面拟合的方法，已在现有工程中使用，在本文中使用了cloth simulation filter来提取和滤除接地点云。

B.快速欧几里得聚类

与EC类似，我们使用欧几里得（L2）距离度量来测量无组织点云的接近度，并将相似性分组到同一聚类中，可以描述为：

算法1中描述伪代码步骤

用图2所示的示例进行演示，请注意，所提出的算法使用逐点方案，该逐点方案的输入编号顺序与EC和EG中使用的聚类方案相反，FEC易于部署，在C++中仅需40行代码。

图2：FEC应用到点云分割的示例，FEC利用具有点索引顺序的逐点方案

C.效率分析

在一些典型示例上分析了所提出的FEC算法在两种分割方法RG和EC上的运行时间，这一结果直观地解释了我们在实验中观察到的FEC相对于其他FEC具有显著的效率优势。

实验与结果

比较方法 :在我们的实验中，将提出的方法FEC和与五种最先进的点云分割解决方案进行比较：

•EC：在PCL库中实现的经典欧几里德聚类算法。

•RG：在PCL库中实现的基于区域增长的经典点云分割方案。

•SPGN：为小型室内场景设计的最新基于学习的方法。

https://github.com/laughtervv/SGPN

•VoxelNet：最近基于学习的方法，该方法学习体素的稀疏逐点特征，并使用3D卷积进行特征传播.

https://github.com/steph1793/Voxelnet

•LiDARSeg：大型室外LiDAR点云的最新实例分割。

https://github.com/feihuzhang/LiDARSeg

评估指标: 我们提供了三个指标来证明所提出的FEC在效率上优于基线，而不影响有效性。

平均精度：使用基于点的度量平均精度（AP）来评估分割质量，类似于COCO实例分割挑战复杂性：提供实际数据实验的运行时间和内存消耗，在具有32G RAM的Intel Core I9 CPU上运行了我们的方法，并将我们的方法与基于经典几何的方法EC和RG进行了比较，所有基于学习的方法、SPGN和体素网都在Nvidia 3090 GPU上进行了测试。

图4：EC、RG和FEC的运行时间，随着集群数量（a）、密度（b）、数量和密度（c）的双重混合以及每个点云集群的不均匀性（d）的增加。

图4（a）（c）中的结果表明，随着集群数量的增加，EC和RG的运行时间急剧增长，相比之下，FEC在所有配置中都运行得更快，在图4（b）（c）中，观察到类似的结果，即随着每个簇的密度（单位体积中的点数）的增加，FEC实现了比EC和RG快100倍的性能，通过模拟正态分布子簇数量的增加来改变每个点云簇的均匀性。图4（d）中的结果表明，点云簇的均匀性略微影响FEC，同时明显拖累EC和RG的运行时间。

使用KITTI真实点云数据集上测试了这三种方法，实践中有两种常见的分割风格，即类间分割（使用单类点云作为输入，例如汽车、建筑或树）和类内分割（使用多类点云为输入）.如表2、我们观察到，在所有配置中，与现有方法EC和RG相比，定量FEC实现了平均100倍的加速.

定性分割结果如图5和图6所示，它验证了我们的说法，即我们的方法和base方法在全局范围内提供了类似的分割质量，有趣的是，所提出的FEC在处理细节段时提供了更好的分割质量，此外，如表3所示. 证明我们的方法在不影响性能（质量）的情况下显著提高了效率

图6 KITTI点云数据集上EC、RG和FEC的定性分割结果

图6 KITTI点云数据集上EC、RG和FEC的定性分割结果

我们将FEC与三种最先进的基于深度学习的方法进行比较，例如分割或3D检测，即SGPN、VoxelNet和LiDARSeg，但需要注意的是，LiDARSeg处理单个激光扫描帧作为输入，所有这些帧都需要GPU进行训练和推理，而FEC仅使用CPU，为此，我们使用语义KITTI全景分割数据集训练了三种基于学习的方法，推理运行时间和分段AP的结果如表4所示，证明FEC仅通过CPU计算就能提供具有竞争力的质量和更快的速度。