PDF: 《FuseFPS: Accelerating Farthest Point Sampling with Fusing KD-tree Construction for Point Clouds》
一、背景故事
点云分析已成为各种应用中嵌入式和移动平台的关键工作负载。最远点采样（FPS）是点云处理中一项基础且广泛使用的核心算法。然而，大量的外部存储器访问使得FPS成为实时点云处理的性能瓶颈。尽管基于桶的最远点采样能显著减少点采样阶段不必要的存储器访问，但KD树构建阶段却成为执行时间的主要瓶颈。在本文中，我们提出了FuseFPS，一种基于桶的最远点采样的架构与算法协同设计。
二、核心思想
FuseFPS的核心思想是高效融合KD树构建阶段和点采样阶段(边采样边构建树)。为实现这一目标，我们首先提出了一种硬件友好的采样驱动KD树构建算法。该算法在点采样过程中逐步构建KD树，进一步减少了内存访问。此外，该算法利用算术平均值将点云分割成桶，这对加速器而言更具硬件友好性。随后，我们为基于桶的最远点采样设计了一款高效的加速器，名为FuseFPS。FuseFPS能够以较低的硬件成本卸载整个内核。详细实验表明，与最先进的加速器QuickFPS相比，FuseFPS在速度和功率效率方面分别实现了约4.3倍和6.1倍的提升。
三、相关细节
3.1 算法流程
3.2 和QuickFPS流程对比
四、效果
