上海科技大学知识管理系统

Farthest Point Sampling (FPS) is a widely used uniform downsampling algorithm in point cloud object detection and classification. However, its high computational complexity and the large size of modern point clouds make real-time performance challenging. Existing FPS accelerators fail to fully optimize their algorithms and hardware architectures for large scale point clouds. In this paper, we propose FMS-FPS, an FPGA based Fast Multi-Stage FPS accelerator that incorporates three key innovations: First, we introduce a density-adaptive multi stage FPS algorithm that adaptively adjusts search strategies based on point cloud density. This approach reduces memory accesses by around 90% during coarse-grain sampling and computation time by around 50% during fine-grain sampling. Second, we design a high-efficiency reusable modular architecture that reuses a limited set of deeply pipelined hardware modules across all stages. This significantly reduces resource utilization while enabling highly parallel processing of large-scale point clouds. Third, we develop an ultra-low-latency neighboring voxel selector that employs a two-level compressed lookup table to reduce storage requirements by around 60% and achieve a one-clock-cycle latency for voxel selection. Additionally, a multi pointer FIFO mechanism ensures efficient processing of non empty voxels and eliminates redundant computations. Experi ments show that FMS-FPS achieves a runtime of 4.06 ms for 120K-point clouds in the KITTI dataset, providing a 340.2× speedup over GPU implementations. Compared to the state-of the-art ASIC accelerator, FuseFPS, FMS-FPS achieves 1.47× and 1.83× speedups for 16K and 120K-point clouds, respectively. To the best of our knowledge, FMS-FPS is the first FPS accelerator implemented on FPGA rather than in simulation.