通过并行结构解构加速点云采样

《IEEE Transactions on Parallel and Distributed Systems》：Accelerating Point Cloud Sampling by Parallel Structure Deconstruction

点云采样在边缘设备应用中存在鲁棒性差、结构采样不足和效率低等问题。本文提出基于并行图分解的DPS采样算法，通过预处理降噪、结构分类采样和高效邻域搜索技术，实现采样速度提升22.08倍同时保持高精度。

　　

摘要：

点云处理在自动驾驶、机器人导航和3D重建等应用中至关重要。采样是点云处理中的关键步骤，但由于边缘设备计算资源有限，当前的采样算法在边缘设备上的性能较差。这主要源于三个原因：首先，采样方法的鲁棒性较弱；即使经过去噪处理，仍然存在残余噪声，现有的边缘采样方法难以忽略噪声节点。其次，缺乏结构性采样，像FPS这样的流行算法倾向于覆盖全局信息，而没有考虑针对特定结构的采样需求。第三，系统效率低下，传统的最近点采样（FPS）和k最近邻搜索（kNN）的时间和空间复杂度非常高（O(n^2)，且并行性低，这限制了系统吞吐量，尤其是在处理大规模点云时。为了解决这一问题，我们提出了一种基于并行图分解的新型点云采样算法DPS（Deconstruction-based Point Cloud Sampling）及其多尺度版本DPS_MS，该算法具有更好的去噪效果。首先，在图构建阶段，我们采用多尺度图技术并添加预处理步骤来过滤噪声节点，从而降低噪声率。其次，在采样阶段，我们根据图节点的逆邻居计数将重要结构分类为边缘节点和密集节点，并为它们分配更高的采样权重以补充结构信息。最后，我们使用高度并行的局部敏感哈希算法来加速邻居搜索并减少内存消耗。通过全面的算法并行化，实现了数据级别的并行处理。在分类和分割任务上的严格定性和定量验证表明，与FPS相比，DPS在保持准确性的同时，点云采样速度提高了22.08倍...

显示更多

引言

点云数据包含了丰富的几何和拓扑信息。如图1所示，在点云处理领域，常见的神经架构（如PointNet++ [39]和Dynamic Graph CNN (DGCNN) [2]）通常遵循以下步骤：输入原始点云、全局采样、任务采样、信息聚合和特征计算。与传统的2D数据不同，3D数据的计算瓶颈在于采样和聚合阶段[3]。能够高效地从这些大型数据集中采样对于简化后续处理和分析任务至关重要。图1。

现有的点云采样技术在应用于边缘设备时存在三个瓶颈：鲁棒性不足、结构缺陷以及性能低下。