NorLab TeamCity GUI
(VPN/intranet access) •
norlabulaval
(Docker Hub)
libnabo is a fast K Nearest Neighbour library for low-dimensional spaces.
libnabo 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.
Dependencies:
- libnabo depends on Eigen, a modern C++ matrix and linear-algebra library.
- libnabo works with either version 2 or 3 of Eigen.
- libnabo also optionally depends on Boost, a C++ general library, for Python bindings.
Credit:
- libnabo was developed by Stéphane Magnenat as part of his work at ASL-ETH
- libnabo is now maintained by NorLab
If you are interested in a pure-Rust version, check that repository out.
libnabo is tested on our build system under the following architecture and OS:
- x86 and arm64/v8
- Ubuntu bionic (18.04) and focal (20.04)
Note:
- libnabo reportedly works on MacOs OsX (latest) and Windows (latest)
This release of libnabo introduces the integration of norlab-build-system (NBS) as a git submodule for codebase development and testing.
Execute the following to clone the repository with its submodule:
git clone --recurse-submodules https://github.com/norlab-ulaval/libnabo.git
If libnabo was previously cloned, execute the following to fetch its new submodule
git submodule update --remote --recursive --init
See contributing_instructions.md
for instructions related to bug reporting, code contribution and for setting up
the libnabo-build-system
on your workstation to speed up your local development workflow.
Run the following commands to pull and run libnabo in a docker container
docker pull norlabulaval/libnabo:latest-ubuntu-focal
docker run -it --rm norlabulaval/libnabo:latest-ubuntu-focal
See available libnabo image tags on dockerhub.
To install docker related dependencies on ubuntu, execute the following
cd ./build_system/nabo_utility_script
# Execute docker tools install script i.e. docker daemon, docker compose, docker buildx
bash nabo_install_docker_tools.bash
For conveniences, you can use the provided build script for Unix
bash libnabo_dependencies_installer.bash
# Use the --help flag to see the list of optional flag
bash libnabo_installer.bash [<optional flag>]
If you want more control, you can follow these commands:
SRC_DIR=`pwd`
BUILD_DIR=${SRC_DIR}/build
mkdir -p ${BUILD_DIR} && cd ${BUILD_DIR}
cmake ${SRC_DIR}
cmake --build ${BUILD_DIR}
sudo cmake --build ${BUILD_DIR} --target install
These lines will compile libnabo in a build
sub-directory and install it system-wide.
To uninstall libnabo, simply run sudo make uninstall
from your build directory.
libnabo provides the following compilation options, available through CMake:
SHARED_LIBS
(boolean, default:false
): iftrue
, build a shared library, otherwise build a static library
You can access on https://norlab-ulaval.github.io/libnabo/. Alternatively, you can generate it locally by typing:
make doc
If your operating system does not provide it, you must get Eigen, and Boost if you want to build the Python bindings. Eigen only needs to be downloaded and extracted.
find_package(libnabo REQUIRED)
target_link_libraries(example PUBLIC ${libnabo_LIBRARIES})
target_include_directories(example PUBLIC ${libnabo_INCLUDE_DIRS})
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 q
in M
:
#include "nabo/nabo.h"
using namespace Nabo;
using namespace Eigen;
...
NNSearchF* nns = NNSearchF::createKDTreeLinearHeap(M);
const int K = 5;
VectorXi indices(K);
VectorXf dists2(K);
nns->knn(q, indices, dists2, K);
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). Note that M
must stay alive throughout the use of libnabo, otherwise the results of knn
are undefined.
The results indices
and dists2
are Eigen vectors of indices and squared distances refering to the columns of M
.
See examples/trivial.cpp
for a compilable version of this example, and examples/usage.cpp
for a slightly more complex example involving multi-point queries.
Running make doc
in your build directory will generate a browsable documentation in doc/html
.
The main page doc/html/index.html
contains a detailed overview of the usage of libnabo.
You can find a complete CMake integration example in examples/libnabo-cmake-example to see how to look for, and link against this library.
libnabo includes python bindings that are compiled if Python is available.
The resulting module is called pynabo, you can see an example in python/test.py
.
You can find more information in the docstring-based documentation:
python -c "import pynabo; help(pynabo.NearestNeighbourSearch)"
The Python bindings can be generated for Python 2 or Python 3.
To specify the version of the interpreter to use when building the bindings, set the PYTHON_VERSION_MAJOR
and PYTHON_VERSION_MINOR
variables.
For example if you have both Python 2.7 and 3.5 installed, you could ask CMake to generate Python 3 bindings by using the following command.
cmake -DPYTHON_VERSION_MAJOR=3 -DPYTHON_VERSION_MINOR=5 ..
On Debian-based distributions you may also need the -DPYTHON_DEB_INSTALL_TARGET
option enabled.
The distribution of libnabo integrates a unit test module, based on CTest. Just type:
make test
...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 or FLANN are detected when compiling libnabo, make 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:
@article{elsebergcomparison,
title={Comparison of nearest-neighbor-search strategies and implementations for efficient shape registration},
author={Elseberg, J. and Magnenat, S. and Siegwart, R. and N{\"u}chter, A.},
journal={Journal of Software Engineering for Robotics (JOSER)},
pages={2--12},
volume={3},
number={1},
year={2012},
issn={2035-3928}
}
libnabo is released under a permissive BSD license.