Accelerating Point Cloud Sampling by Parallel Structure Deconstruction

doi:10.1109/TPDS.2025.3622691

Accelerating Point Cloud Sampling by Parallel Structure Deconstruction

2025-10-17

0

PRE

AI

DOI：10.1109/TPDS.2025.3622691

原文链接

原文求助

摘要

En 中文

点云处理是自动驾驶、机器人导航和3D重建等应用的基础。采样是点云处理中的关键过程，但由于计算资源有限，当前采样算法在边缘设备上的部署表现不佳。这源于三个主要原因。首先，采样的鲁棒性较弱；即使在去噪后，仍存在残留噪声，现有边缘采样方法难以忽略噪声采样节点。其次，缺乏结构化采样，流行的FPS算法倾向于覆盖全局信息，而未考虑针对特定结构的聚焦采样。第三，系统效率低下，传统的Farthest Point Sampling (FPS)和k-Nearest Neighbor Search (kNN)具有$O(n^{2})$的极差时间和空间复杂度，且并行性低，限制了系统吞吐量，尤其是在大规模点云处理中。为弥补这一差距，我们提出了一种基于并行图解构的新型点云采样算法DPS (Deconstruction-based Point Cloud Sampling)及其多尺度版本DPS_MS，具有更好的去噪效果。首先，在图构建阶段，我们采用多尺度图构建并增加预处理阶段以过滤部分噪声节点，降低噪声率。其次，在采样阶段，我们基于图节点的反向邻居计数将重要结构分为边缘节点和密集节点，并为其分配更高的采样权重以补充结构信息。最后，我们使用高度并行的局部敏感哈希算法加速邻居搜索并减少内存消耗，通过算法的综合并行化实现了数据级并行化。通过在分类和分割任务上的严格定性定量验证，我们证明DPS在保持精度的同时，相较于FPS算法将点云采样速度提升了22.08倍，实现系统吞吐量提升75.1倍，最大并行加速比为10.32x，并将Accuracy/FLOPs (M)比率提升至8.68。

Keyword:

Point cloud

kNN

FPS

parallel

Accelerating Point Cloud Sampling by Parallel Structure Deconstruction

摘要

期刊

机构

引用论文