graph-theoretic framework for robust pairwise data association

Overview

banner

CLIPPER: A Graph-Theoretic Framework for Robust Data Association

Data association is a fundamental problem in robotics and autonomy. CLIPPER provides a framework for robust, pairwise data association and is applicable in a wide variety of problems (e.g., point cloud registration, sensor calibration, place recognition, etc.). By leveraging the notion of geometric consistency, a graph is formed and the data association problem is reduced to the maximum clique problem. This NP-hard problem has been studied in many fields, including data association, and solutions techniques are either exact (and not scalable) or approximate (and potentially imprecise). CLIPPER relaxes this problem in a way that (1) allows guarantees to be made on the solution of the problem and (2) is applicable to weighted graphs, avoiding the loss of information due to binarization which is common in other data association work. These features allow CLIPPER to achieve high performance, even in the presence of extreme outliers.

This repo provides both MATLAB and C++ implementations of the CLIPPER framework. In addition, Python bindings, Python, C++, and MATLAB examples are included.

Citation

If you find this code useful in your research, please cite our paper:

  • P.C. Lusk, K. Fathian, and J.P. How, "CLIPPER: A Graph-Theoretic Framework for Robust Data Association," arXiv preprint arXiv:2011.10202, 2020. (pdf) (presentation)
@inproceedings{lusk2020clipper,
  title={CLIPPER: A Graph-Theoretic Framework for Robust Data Association},
  author={Lusk, Parker C and Fathian, Kaveh and How, Jonathan P},
  booktitle={IEEE International Conference on Robotics and Automation (ICRA)},
  year={2021}
}

Getting Started

After cloning this repo, please build using cmake:

$ mkdir build
$ cd build
$ cmake ..
$ make

Once successful, the C++ tests can be run with ./test/tests (if -DBUILD_TESTS=ON is added to cmake .. command).

Python Bindings

If Python bindings are built (see configuration options below), then the clipper Python module will need to be installed before using. This can be done with

$ cd build
$ make pip-install

# or directly using pip (e.g., to control which python version)
$ python3 -m pip install build/bindings/python # 'python3 -m' ensures appropriate pip version is used

Note: if using Python2 (e.g., < ROS Noetic), you must tell pybind11 to use Python2.7. Do this with adding the flag -DPYBIND11_PYTHON_VERSION=2.7 to the cmake .. command. You may have to remove your build directory and start over to ensure nothing is cached. You should see that pybind11 finds a Python2.7 interpreter and libraries.

A Python example notebook can be found in examples.

MATLAB Bindings

If MATLAB is installed on your computer and MATLAB bindings are requested (see configuration options below), then cmake will attempt to find your MATLAB installation and subsequently generate a set of MEX files so that CLIPPER can be used in MATLAB.

Note that in addition to the C++/MEX version of CLIPPER's dense cluster finder, we provide a reference MATLAB version of our projected gradient ascent approach to finding dense clusters.

Please find MATLAB examples here.

Configuring the Build

The following cmake options are available when building CLIPPER:

Option Description Default
BUILD_BINDINGS_PYTHON Uses pybind11 to create Python bindings for CLIPPER ON
BUILD_BINDINGS_MATLAB Attempts to build MEX files which are required for the MATLAB examples. A MATLAB installation is required. Gracefully fails if not found. ON
BUILD_TESTS Builds C++ tests OFF
ENABLE_MKL Attempts to use Intel MKL (if installed) with Eigen for accelerated linear algebra. OFF
ENABLE_BLAS Attempts to use a BLAS with Eigen for accelerated linear algebra. OFF

Note: The options ENABLE_MKL and ENABLE_BLAS are mutually exclusive.

These cmake options can be set using the syntax cmake -DENABLE_MKL=ON .. or using the ccmake . command (both from the build dir).

Performance with MKL vs BLAS

On Intel CPUs, MKL should be preferred as it offers superior performance over other general BLAS packages. Also note that on Ubuntu, OpenBLAS (sudo apt install libopenblas-dev) provides better performance than the default installed blas.

With MKL, we have found an almost 2x improvement in runtime over the MATLAB implementation. On an i9, the C++/MKL implementation can solve problems with 1000 associations in 70 ms.

Note: Currently, MATLAB bindings do not work if either BLAS or MKL are enabled. Python bindings do not work if MKL is enabled.

Including in Another C++ Project

A simple way to include clipper as a shared library in another C++ project is via cmake. This method will automatically clone and build clipper, making the resulting library accessible in your main project. In the project CMakeLists.txt you can add

set(CLIPPER_DIR "${CMAKE_CURRENT_BINARY_DIR}/clipper-download" CACHE INTERNAL "CLIPPER build dir" FORCE)
set(BUILD_BINDINGS_MATLAB OFF CACHE BOOL "")
set(BUILD_TESTS OFF CACHE BOOL "")
set(ENABLE_MKL OFF CACHE BOOL "")
set(ENABLE_BLAS OFF CACHE BOOL "")
configure_file(cmake/clipper.cmake.in ${CLIPPER_DIR}/CMakeLists.txt IMMEDIATE @ONLY)
execute_process(COMMAND "${CMAKE_COMMAND}" -G "${CMAKE_GENERATOR}" . WORKING_DIRECTORY ${CLIPPER_DIR})
execute_process(COMMAND "${CMAKE_COMMAND}" --build . WORKING_DIRECTORY ${CLIPPER_DIR})
add_subdirectory(${CLIPPER_DIR}/src ${CLIPPER_DIR}/build)

where cmake/clipper.cmake.in looks like

cmake_minimum_required(VERSION 3.10)
project(clipper-download NONE)

include(ExternalProject)
ExternalProject_Add(clipper
    GIT_REPOSITORY      "https://github.com/mit-acl/clipper"
    GIT_TAG             master
    SOURCE_DIR          "${CMAKE_CURRENT_BINARY_DIR}/src"
    BINARY_DIR          "${CMAKE_CURRENT_BINARY_DIR}/build"
    CONFIGURE_COMMAND   ""
    BUILD_COMMAND       ""
    INSTALL_COMMAND     ""
    TEST_COMMAND        ""
)

Then, you can link your project with clipper using the syntax target_link_libraries(yourproject clipper).


This research is supported by Ford Motor Company.

Owner
MIT Aerospace Controls Laboratory
see more code at https://gitlab.com/mit-acl
MIT Aerospace Controls Laboratory
Co-GAIL: Learning Diverse Strategies for Human-Robot Collaboration

CoGAIL Table of Content Overview Installation Dataset Training Evaluation Trained Checkpoints Acknowledgement Citations License Overview This reposito

Jeremy Wang 29 Dec 24, 2022
PassAPI is a password generator in hash format and fully developed in Python, with the aim of teaching how to handle and build

simple, elegant and safe Introduction PassAPI is a password generator in hash format and fully developed in Python, with the aim of teaching how to ha

Johnsz 2 Mar 02, 2022
Official implementation of "SegFormer: Simple and Efficient Design for Semantic Segmentation with Transformers"

SegFormer: Simple and Efficient Design for Semantic Segmentation with Transformers Figure 1: Performance of SegFormer-B0 to SegFormer-B5. Project page

NVIDIA Research Projects 1.4k Dec 31, 2022
Predicting Semantic Map Representations from Images with Pyramid Occupancy Networks

This is the code associated with the paper Predicting Semantic Map Representations from Images with Pyramid Occupancy Networks, published at CVPR 2020.

Thomas Roddick 219 Dec 20, 2022
Sleep staging from ECG, assisted with EEG

Sleep_Staging_Knowledge Distillation This codebase implements knowledge distillation approach for ECG based sleep staging assisted by EEG based sleep

2 Dec 12, 2022
The source codes for TME-BNA: Temporal Motif-Preserving Network Embedding with Bicomponent Neighbor Aggregation.

TME The source codes for TME-BNA: Temporal Motif-Preserving Network Embedding with Bicomponent Neighbor Aggregation. Our implementation is based on TG

2 Feb 10, 2022
Code for "Human Pose Regression with Residual Log-likelihood Estimation", ICCV 2021 Oral

Human Pose Regression with Residual Log-likelihood Estimation [Paper] [arXiv] [Project Page] Human Pose Regression with Residual Log-likelihood Estima

JeffLi 347 Dec 24, 2022
📝 Wrapper library for text generation / language models at char and word level with RNN in TensorFlow

tensorlm Generate Shakespeare poems with 4 lines of code. Installation tensorlm is written in / for Python 3.4+ and TensorFlow 1.1+ pip3 install tenso

Kilian Batzner 63 May 22, 2021
Practical Single-Image Super-Resolution Using Look-Up Table

Practical Single-Image Super-Resolution Using Look-Up Table [Paper] Dependency Python 3.6 PyTorch glob numpy pillow tqdm tensorboardx 1. Training deep

Younghyun Jo 116 Dec 23, 2022
Project looking into use of autoencoder for semi-supervised learning and comparing data requirements compared to supervised learning.

Project looking into use of autoencoder for semi-supervised learning and comparing data requirements compared to supervised learning.

Tom-R.T.Kvalvaag 2 Dec 17, 2021
Let Python optimize the best stop loss and take profits for your TradingView strategy.

TradingView Machine Learning TradeView is a free and open source Trading View bot written in Python. It is designed to support all major exchanges. It

Robert Roman 473 Jan 09, 2023
Add-on for importing and auto setup of character creator 3 character exports.

CC3 Blender Tools An add-on for importing and automatically setting up materials for Character Creator 3 character exports. Using Blender in the Chara

260 Jan 05, 2023
Fast and exact ILP-based solvers for the Minimum Flow Decomposition (MFD) problem, and variants of it.

MFD-ILP Fast and exact ILP-based solvers for the Minimum Flow Decomposition (MFD) problem, and variants of it. The solvers are implemented using Pytho

Algorithmic Bioinformatics Group @ University of Helsinki 4 Oct 23, 2022
Base pretrained models and datasets in pytorch (MNIST, SVHN, CIFAR10, CIFAR100, STL10, AlexNet, VGG16, VGG19, ResNet, Inception, SqueezeNet)

This is a playground for pytorch beginners, which contains predefined models on popular dataset. Currently we support mnist, svhn cifar10, cifar100 st

Aaron Chen 2.4k Dec 28, 2022
An implementation of DeepMind's Relational Recurrent Neural Networks in PyTorch.

relational-rnn-pytorch An implementation of DeepMind's Relational Recurrent Neural Networks (Santoro et al. 2018) in PyTorch. Relational Memory Core (

Sang-gil Lee 241 Nov 18, 2022
A small library for creating and manipulating custom JAX Pytree classes

Treeo A small library for creating and manipulating custom JAX Pytree classes Light-weight: has no dependencies other than jax. Compatible: Treeo Tree

Cristian Garcia 58 Nov 23, 2022
Pyramid Pooling Transformer for Scene Understanding

Pyramid Pooling Transformer for Scene Understanding Requirements: torch 1.6+ torchvision 0.7.0 timm==0.3.2 Validated on torch 1.6.0, torchvision 0.7.0

Yu-Huan Wu 119 Dec 29, 2022
A Python package for faster, safer, and simpler ML processes

Bender 🤖 A Python package for faster, safer, and simpler ML processes. Why use bender? Bender will make your machine learning processes, faster, safe

Otovo 6 Dec 13, 2022
DALL-Eval: Probing the Reasoning Skills and Social Biases of Text-to-Image Generative Transformers

DALL-Eval: Probing the Reasoning Skills and Social Biases of Text-to-Image Generative Transformers Authors: Jaemin Cho, Abhay Zala, and Mohit Bansal (

Jaemin Cho 98 Dec 15, 2022
EsViT: Efficient self-supervised Vision Transformers

Efficient Self-Supervised Vision Transformers (EsViT) PyTorch implementation for EsViT, built with two techniques: A multi-stage Transformer architect

Microsoft 352 Dec 25, 2022