An Adjustable Farthest Point Sampling Method for Approximately-sorted Point Cloud Data
This work addresses a bottleneck in point cloud applications like PointNet++ for computer vision and robotics, offering a significant speed improvement with minimal performance loss, though it is incremental as it builds on existing FPS methods.
The paper tackles the inefficiency of Farthest Point Sampling (FPS) in point cloud processing by proposing an adjustable method (AFPS) with a nearest-point-distance-updating (NPDU) technique, achieving speedups of 22-30x and 34-280x respectively while maintaining comparable performance, such as only a 0.0035 drop in mIoU on ShapeNet part segmentation.
Sampling is an essential part of raw point cloud data processing such as in the popular PointNet++ scheme. Farthest Point Sampling (FPS), which iteratively samples the farthest point and performs distance updating, is one of the most popular sampling schemes. Unfortunately it suffers from low efficiency and can become the bottleneck of point cloud applications. We propose adjustable FPS (AFPS), parameterized by M, to aggressively reduce the complexity of FPS without compromising on the sampling performance. Specifically, it divides the original point cloud into M small point clouds and samples M points simultaneously. It exploits the dimensional locality of an approximately sorted point cloud data to minimize its performance degradation. AFPS method can achieve 22 to 30x speedup over original FPS. Furthermore, we propose the nearest-point-distance-updating (NPDU) method to limit the number of distance updates to a constant number. The combined NPDU on AFPS method can achieve a 34-280x speedup on a point cloud with 2K-32K points with algorithmic performance that is comparable to the original FPS. For instance, for the ShapeNet part segmentation task, it achieves 0.8490 instance average mIoU (mean Intersection of Union), which is only 0.0035 drop compared to the original FPS.