Skip to content

Python efficient farthest point sampling (FPS) library. Compatible with numpy.

License

Notifications You must be signed in to change notification settings

leonardodalinky/fpsample

Repository files navigation

fpsample

pypi package version badge python version badge license badge star badge

Python efficient farthest point sampling (FPS) library, 100x faster than pure Python implementation.

fpsample is coupled with numpy and built upon Rust pyo3 bindings.

Library for GPU is under construction. Any issues are welcome.

Installation

Install from PyPI

numpy>=1.16.0 is required. Install fpsample using pip:

pip install -U fpsample

Build from source

The library is built using maturin. Ensure you have maturin, rust and cargo installed.

Build the library and install using:

maturin develop --release

Usage

import fpsample
import numpy as np

# Generate random point cloud
pc = np.random.rand(4096, 3)
# sample 1024 points
fps_samples_idx = fpsample.fps_sampling(pc, 1024)

fps_npdu_samples_idx = fpsample.fps_npdu_sampling(pc, 1024)
# or specify the windows size
fps_npdu_samples_idx = fpsample.fps_npdu_sampling(pc, 1024, k=64)

fps_npdu_kdtree_samples_idx = fpsample.fps_npdu_kdtree_sampling(pc, 1024)
# or specify the windows size
fps_npdu_kdtree_samples_idx = fpsample.fps_npdu_kdtree_sampling(pc, 1024, k=64)

NOTE: NPDU method only gives sub-optimal answers. And it assumes that the points are approximately sorted or have dimensional locality. Otherwise, the result may be worse. Check the paper for details.

NPDU+KDTree method is more robust than NPDU method. It does not require the dimensional locality. But it is slightly slower than vanilla NPDU method. It is recommended to use NPDU+KDTree method in general cases.

Performance

Setup:

  • CPU: Intel(R) Core(TM) i9-10940X CPU @ 3.30GHz
  • RAM: 128 GiB
Method #samples #points Time
FPS 1024 4096 18.6 ms ± 0.17 ms
FPS+NPDU 1024 4096 3.68 ms ± 0.10 ms
FPS+NPDU+KDTree 1024 4096 13.10 ms ± 0.16 ms
FPS 4000 50,000 832 ms ± 9.01 ms
FPS+NPDU 4000 50,000 143 ms ± 1.98 ms
FPS+NPDU+KDTree 4000 50,000 294 ms ± 9.06 ms
FPS 50,000 100,000 22.1 s ± 207 ms
FPS+NPDU 50,000 100,000 3.35 s ± 66.8 ms
FPS+NPDU+KDTree 50,000 100,000 4.08 s ± 60.4 ms

Reference

The nearest-point-distance-updating (NPDU) heuristic strategy is proposed in the following paper:

@INPROCEEDINGS{9919246,
  author={Li, Jingtao and Zhou, Jian and Xiong, Yan and Chen, Xing and Chakrabarti, Chaitali},
  booktitle={2022 IEEE Workshop on Signal Processing Systems (SiPS)},
  title={An Adjustable Farthest Point Sampling Method for Approximately-sorted Point Cloud Data},
  year={2022},
  volume={},
  number={},
  pages={1-6},
  doi={10.1109/SiPS55645.2022.9919246}
}