libnabo is a fast K Nearest Neighbour library for low-dimensional spaces. It provides a clean, legacy-free, scalar-type–agnostic API thanks to C++ templates. Its current CPU implementation is strongly inspired by ANN, but with more compact data types. On the average, libnabo is 5% to 20% faster than ANN.
libnabo depends on Eigen, a modern C++ matrix and linear-algebra library. libnabo works with either version 2 or 3 of Eigen.
libnabo uses CMake as build system. The complete compilation process depends on the system you are using (Linux, Mac OS X or Windows). You will find a nice introductory tutorial in this you tube video: http://www.youtube.com/watch?v=CLvZTyji_Uw.
libnabo provides the following compilation options, available through CMake :
SHARED_LIBS (boolean, default:
true, build a shared library, otherwise build a static library
You specify them with a command-line tool,
ccmake, or with a graphical tool,
cmake-gui. Please read the CMake documentation for more information.
Under Unix, assuming that Eigen is installed system-wide, you can compile (with optimisation and debug information) and install libnabo in
/usr/local with the following commands run in the top-level directory of libnabo's sources:
These lines will compile libnabo in a
build sub-directory and therefore keep your source tree clean. Note that you could compile libnabo anywhere you have write access, such as in
/tmp/libnabo. This out-of-source build is a nice feature of CMake. If Eigen is not installed system-wide, you might have to tell CMake where to find them (using
You can generate the documentation by typing:
libnabo is easy to use. For example, assuming that you are working with floats and that you have a point set
M and a query point
q, you can find the
K nearest neighbours of
In this example,
M is an Eigen (refering to the software, not to the math) matrix (column major, float) and
q is an Eigen vector (float). The results
dists2 are Eigen vectors of indices and squared distances refering to the columns of
Here is a slightly more complex example:
Note that the matrix-based interface for query is more efficient than the vector-based one, because some sanity checks can be done only once. Therefore, if you have multiple points to query, we warmly suggest to pass them as a matrix instead of calling
knn() multiple times.
The following additional construction parameters are available in KDTREE_ algorithms:
unsigned): bucket size, defaults to 8
The distribution of libnabo integrates a unit test module, based on CTest. Just type:
...in the build directory to run the tests. Their outputs are available in the
Testing directory. These consist of validation and benchmarking tests. If ANN is detected when compiling libnabo,
test will also perform comparative benchmarks.
If you use libnabo in the academic context, please cite this paper that evaluates its performances in the contex of ICP:
Please use github's issue tracker to report bugs.
libnabo is released under a permissive BSD license.
libnabo differs from ANN on the following points:
only ANN_KD_SL_MIDPT splitting rules
do not store bounds in nodes (that is, I do it like in ANN's article instead of like in ANN's source code)