jaybro / pico_tree

A C++ header only library for fast nearest neighbor and range searches using a KdTree. It supports interfacing with Eigen, OpenCV, and custom data types and provides optional Python bindings.

PicoTree

PicoTree is a C++ header only library with Python bindings for fast nearest neighbor searches and range searches using a KdTree. See the table below to get an impression of the performance provided by the KdTree of this library versus several other implementations:

	Build C++	Build Python	Knn C++	Knn Python
nanoflann v1.5.0	2.9s	...	3.2s	...
SciPy KDTree 1.11.0	...	4.5s	...	563.6s
Scikit-learn KDTree 1.2.2	...	6.2s	...	42.2s
pykdtree 1.3.7	...	1.0s	...	6.6s
OpenCV FLANN 4.6.0	1.9s	...	4.7s	...
PicoTree KdTree v0.8.3	0.9s	1.0s	2.8s	3.1s

Two LiDAR based point clouds of sizes 7733372 and 7200863 were used to generate these numbers. The first point cloud was the input to the build algorithm and the second to the query algorithm. All benchmarks were run on a single thread with the following parameters: max_leaf_size=10 and knn=1. A more detailed C++ comparison of PicoTree is available with respect to nanoflann.

Available under the MIT license.

Capabilities

KdTree:

• Nearest neighbor, approximate nearest neighbor, radius, box, and customizable nearest neighbor searches.
• Different metric spaces:
  • Support for topological spaces with identifications. E.g., points on the circle [-pi, pi].
  • Available distance functions: L1, L2Squared, LInf, SO2, and SE2Squared.
  • Metrics can be customized.
• Multiple tree splitting rules: kLongestMedian, kMidpoint and kSlidingMidpoint.
• Compile time and run time known dimensions.
• Static tree builds.
• Thread safe queries.
• Optional Python bindings.

PicoTree can interface with different types of points and point sets through traits classes. These can be custom implementations or one of the pico_tree::SpaceTraits<> and pico_tree::PointTraits<> classes provided by this library.

• Space type support:
  • std::vector<PointType>.
  • pico_tree::SpaceMap<PointType>.
  • Eigen::Matrix<> and Eigen::Map<Eigen::Matrix<>>.
  • cv::Mat.
• Point type support:
  • Fixed size arrays and std::array<>.
  • pico_tree::PointMap<>.
  • Eigen::Vector<> and Eigen::Map<Eigen::Vector<>>.
  • cv::Vec<>.
• pico_tree::SpaceMap<PointType> and pico_tree::PointMap<> allow interfacing with dynamic size arrays. It is assumed that points and their coordinates are laid out contiguously in memory.

Examples

• Minimal working example for building and querying a KdTree.
• Creating a KdTree and having it take the input by value or reference.
• Using the KdTree's search capabilities.
• Working with dynamic size arrays.
• Supporting a custom point type.
• Supporting a custom space type.
• Creating a custom search visitor.
• Saving and loading a KdTree to and from a file.
• Support for Eigen and OpenCV data types.
• Running the KdTree and KdForest on the MNIST and SIFT datasets.
• How to use the KdTree with Python.

Requirements

Minimum:

• A compiler that is compliant with the C++17 standard or higher.
• CMake. It is also possible to just copy and paste the pico_tree directory into an include directory.

Optional:

• Doxygen. Needed for generating documentation.
• Google Test. Used for running unit tests.
• Eigen. To run the example that shows how Eigen data types can be used in combination with PicoTree.
• OpenCV. To run the OpenCV example that shows how to work with OpenCV data types.
• Google Benchmark is needed to run any of the benchmarks. The nanoflann and OpenCV benchmarks also require their respective libraries to be installed.

Python bindings:

• Python. Version 3.7 or higher.
• pybind11. Used to ease the creation of Python bindings. Available under the BSD license and copyright.
• OpenMP. For parallelization of queries.
• numpy. Points and search results are represented by ndarrays.
• scikit-build. Glue between CMake and setuptools.

Build

Build with CMake:

$ mkdir build && cd build
$ cmake ../
$ cmake --build .
$ cmake --build . --target pico_tree_doc
$ cmake --install .

find_package(PicoTree REQUIRED)

add_executable(myexe main.cpp)
target_link_libraries(myexe PUBLIC PicoTree::PicoTree)

Install with pip:

$ pip install ./pico_tree

References

• J. L. Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, vol. 18, no. 9, pp. 509–517, 1975.
• S. Arya and D. M. Mount, Algorithms for fast vector quantization, In IEEE Data Compression Conference, pp. 381–390, March 1993.
• S. Maneewongvatana and D. M. Mount, It's okay to be skinny, if your friends are fat, 4th Annual CGC Workshop on Computational Geometry, 1999.
• S. Arya and H. Y. Fu, Expected-case complexity of approximate nearest neighbor searching, InProceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms, 2000.
• N. Sample, M. Haines, M. Arnold and T. Purcell, Optimizing Search Strategies in k-d Trees, In: 5th WSES/IEEE World Multiconference on Circuits, Systems, Communications & Computers (CSCC 2001), July 2001.
• A. Yershova and S. M. LaValle, Improving Motion-Planning Algorithms by Efficient Nearest-Neighbor Searching, In IEEE Transactions on Robotics, vol. 23, no. 1, pp. 151-157, Feb. 2007.
• M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry - Algorithms and Applications, Springer-Verlag, third edition, 2008.
• C. Silpa-Anan and R. Hartley, Optimised KD-trees for fast image descriptor matching, In CVPR, 2008.