Accelerating Point Cloud Sampling by Parallel Structure Deconstruction
- 17 October 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 37 (1) , 60-75
Abstract
Point cloud processing is fundamental to applications such as autonomous driving, robotic navigation, and 3D reconstruction. Sampling is a crucial process in point cloud processing, but current sampling algorithms perform poorly when deployed on edge devices due to limited computational resources. This stems from three main reasons. First, the robustness of sampling is weak; even after denoising, residual noise remains, and existing edge sampling methods struggle to ignore noisy sampling nodes. Second, there’s a lack of structural sampling, popular algorithms like FPS tend to cover global information without considering special structures for focused sampling. Third, system efficiency is poor, traditional Farthest Point Sampling (FPS) and k-Nearest Neighbor Search (kNN) have terrible time and space complexities of $O(n^{2})$ with low parallelism, limiting system throughput, especially for large-scale point cloud processing. To bridge this gap, we propose a novel point cloud sampling algorithm based on parallel graph deconstruction named DPS (Deconstruction-based Point Cloud Sampling) and its multi-scale version DPS_MS with better denoising effect. First, during graph construction, we employ multi-scale graphing and add a preprocessing stage to filter out some noise nodes, reducing the noise rate. Second, in the sampling stage, we categorize important structures into edge nodes and dense nodes based on the reverse neighbor count of graph nodes, assigning them higher sampling weights to supplement structural information. Finally, we use a highly parallel locality-sensitive hashing algorithm to accelerate neighbor search and reduce memory consumption, we achieved data-level parallelization through the comprehensive parallelization of our algorithm. Through rigorous qualitative and quantitative validation on classification and segmentation tasks, we demonstrate that DPS, while maintaining accuracy, increases point cloud sampling speed by 22.08 times compared to the FPS algorithm, the implementation achieved a 75.1-fold improvement in system throughput and a maximum parallel speedup of 10.32x, and improves the Accuracy/FLOPs (M) ratio to 8.68.
Keywords
Funding Information
- National NSF of China (62272393)
- National Key R&D Program of China (2024YFB4303700)
- Aeronautical Science Foundation of China (20240043053002)
- Fundamental Research Funds for the Central Universities (24GH0201339, WH00001161)
This publication has 37 references indexed in Scilit:
- FuseFPS: Accelerating Farthest Point Sampling with Fusing KD-tree Construction for Point Clouds2024
- PST-NET: Point Cloud Sampling via Point-Based Transformer2021
- ON THE COMPLEXITY OF CLASSIFYING LEBESGUE SPACESThe Journal of Symbolic Logic, 2020
- Massive Point Cloud Space Management Method Based on Octree-Like EncodingArabian Journal for Science and Engineering, 2019
- Learning to Sample2019
- PU-Net: Point Cloud Upsampling Network2018
- Can Gray Code Improve the Performance of Distributed Video Coding?IEEE Access, 2016
- 3D ShapeNets: A deep representation for volumetric shapes2015
- The farthest point strategy for progressive image samplingIEEE Transactions on Image Processing, 1997
- Peano1980