# _libnabo_ ^{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.

Supported OS And Architecture

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)

★ Version 1.1.0 Release Note

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

★ Contributing Instructions

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.

Docker images

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

Compilation

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.

Compilation options

libnabo provides the following compilation options, available through CMake:

• SHARED_LIBS (boolean, default: false): if true, build a shared library, otherwise build a static library

Documentation

You can generate the documentation by typing:

make doc

Prerequisites

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.

Add libnabo to your CMake project

find_package(libnabo REQUIRED)
target_link_libraries(example PUBLIC ${libnabo_LIBRARIES})
target_include_directories(example PUBLIC ${libnabo_INCLUDE_DIRS})

Usage

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 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.

Python bindings

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)"

Building

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.

Unit testing

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.

Citing libnabo

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}
}

License

libnabo is released under a permissive BSD license.

Changelog for package libnabo

1.1.1 (2024-03-19)

• Update README.md
• Set minimum required CMake version to 3.10.2
• (origin/dev-feat-integrate-norlab-build-system-library-and-implement-linabo-build-system-NMO-405) style: renamed [.*test_compilation.*]{.title-ref} services and target to [.*integration_test.*]{.title-ref} for clarity.
• doc(readme): mute ubuntu jammy from supported OS version until libpointmatcher build pass on jammy
• ci: drop ubuntu jammy from build matrix
• doc: add missing norlab light logo
• doc: add missing norlab light logo
• doc: update header with dynamic logo, fix hyperlink, add dockerhub badge and fix relative link
• doc(pull_request_template.md): fix typo
• doc(readme): add norlab logo to header and improve intro
• test: add release crawler script bats test
• build: add release crawler script and .env file
• doc(readme): update header
• build: update repo version format
• doc: clean pr comment
• feat: integrate norlab-build-system library and implement linabo-build-system [NMO-405]
• build: Added norlab-shell-script-tools submodule to repository [NMO-405]
• build: Added norlab-build-system submodule to repository [NMO-405]
• chore: added a code owner designation file, a pull request template and a conventional commit reference file
• Update README.md
• Update README.md with cmake guide
• Use CMakePackageConfigHelpers to generate config files. Fill libnabo_INCLUDE_DIRS and libnabo_LIBRARIES variables.
• Fix Cmake Syntax invoked by Nabo\'s version regex. Updated min cmake version to 3.8
• more robust extraction of version
• Remove dependency on grep + Improve findstr command
• Use findstr instead of grep on Windows
• Date range and catch-all for authors
• Upgrade all syntax to package format 3
• format \"3\" specifier for condition flag
• Keep catkin for ROS1
• Create LICENSE file based on BSD license as per package.xml
• catkin not required for pure cmake packages
• Added link to Rust version.
• Replace TABS with SPACES
• Automaticaly find eigen3
• Fix install-space include directories
• fix missing eigen headers in python module
• add complete cmake exported-targets usage example
• option to disable doxygen; cmake clean up
• better handling of STATIC build option
• modernize cmake to have exported targets
• Make library git submodule-friendly

1.0.7 (2019-02-07)

• Disabled cmake compile tests by default and on compilers that do not support them (#95)
• Fix Python 2 bindings support in CMake scripts (#90)
• Port libnabo to c++11 (#89)
• Remove register keyword in index_heap.h (#88)
• Fix compilation warning for MSVC (#85)
• Assert template type for invalid setters (#80)
• Return numerically maximal index (unsigned) or -1 (signed) for no match case (#79)
• Add generate step for \${PROJECT_BINARY_DIR}/libnaboConfig.cmake (#76)
• Removed compiler-specific flags for compilers that do not support them (#74)
• Added cmake_policy(SET CMP0054 NEW) (#73)
• Output compiler message with compile test fatal error in cmake (#72)
• Removed erroneous commas from test/CMakeLists.txt (#71)
• Removed fatal \",\" suffix from FATAL_ERROR in CMakeLists.txt (#70)
• Fixed regression concerning installed libnaboConfig.cmake (#65)
• Fix/relax compiler requirements (#63)
• Removed hard dependency on the doc target (#62)
• Install any.hpp (#61)
• Remove boost::any and boost:format dependencies (#59)
• Port the python bindings to python3 (#57)
• Added cmake switch to disable usage of OpenMP (#53)
• Zero copy for Eigen::Matrix3XT and Eigen::Map<const Eigen::Matrix3XT> (#43)
• Fix warnings and switch on Wextra (#42)
• Disallow instantiation with non dynamic matrices (#41)
• Update README.md
• Removed all code dealing with libnaboTargets.cmake (#32)
• Got rid of unused locally defined typedefs (#27)
• Contributors: David Landry, Hannes Sommer, Simon Lynen, Simon-Pierre Desch