FracGM

Official implementation of "FracGM: A Fast Fractional Programming Technique for Geman-McClure Robust Estimator." This work is accpeted for publication by IEEE Robotics and Automation Letters (RA-L). This library is written in Rust and we support Rust, C++, and Python interfaces.

About FracGM

FracGM is a fast and accurate algorithm for Geman-McClure robust estimation, which leverages fractional programming techniques. It exhibits fast convergence rate and well outlier rejection capability. In addition, the global optimality of the proposed solver can be guaranteed under given conditions.

For more, please refer to our paper:

• Bang-Shien Chen, Yu-Kai Lin, Jian-Yu Chen, Chih-Wei Huang, Jann-Long Chern, Ching-Cherng Sun, FracGM: A Fast Fractional Programming Technique for Geman-McClure Robust Estimator. IEEE Robotics and Automation Letters (RA-L), vol. 9, no. 12, pp. 11666-11673, Dec. 2024. (paper) (preprint) (code)

@article{Chen24FracGM,
  author={Chen, Bang-Shien and Lin, Yu-Kai and Chen, Jian-Yu and Huang, Chih-Wei and Chern, Jann-Long and Sun, Ching-Cherng},
  journal={IEEE Robotics and Automation Letters},
  title={FracGM: A Fast Fractional Programming Technique for Geman-McClure Robust Estimator},
  year={2024},
  volume={9},
  number={12},
  pages={11666-11673},
  doi={10.1109/LRA.2024.3495372}
}

Table of Contents

• FracGM
  • ⚙️ Setup
    • Prerequisites
    • Building FracGM
  • 🌱 Example Usages
  • ☕ Supplementary Materials
  • 🎁 Acknowledgement

⚙️ Setup

The following setup is tested in Ubuntu 22.04.

Prerequisites

# Rust
curl https://sh.rustup.rs -sSf | sh
# Use the following command to load the Rust environment in the same shell:
# . "$HOME/.cargo/env"            # For sh/bash/zsh/ash/dash/pdksh
# source "$HOME/.cargo/env.fish"  # For fish

# OpenBLAS (for ndarray-linalg)
sudo apt update
sudo apt install -y libopenblas-dev pkg-config libssl-dev cmake

# C++ (for maximum clique inlier selection)
sudo apt install -y g++

# (Optional) Setup the C++ wrapper
sudo apt install -y g++
python3 -m pip install meson ninja

# (Optional) Setup the Python wrapper
# python3 -m pip install virtualenv
# python3 -m virtualenv venv
# source venv/bin/activate
sudo apt install -y python3-pip python3-dev
python3 -m pip install numpy "maturin[patchelf]" rich

Building FracGM

git clone --recurse-submodules -j8 https://github.com/StephLin/FracGM.git
cd FracGM

# If you do not clone FracGM with --recurse-submodules option,
# you may need to run the following command.
git submodule update --init

# 🦀 Build FracGM with Native Rust support
cargo build --release --package fracgm

# 🥐 Build FracGM with C++ wrapper
python3 scripts/build_fracgm_cxx_library.py
# header files: ./fracgm-cxx/include
# library file: ./target/release/libfracgm_cxx.so

# 🐍 Build and install FracGM with Python wrapper
# (Notice: You should check the real path to the wheel file
#  e.g., ./target/wheels/fracgm-0.1.0-cp310-cp310-manylinux_2_34_x86_64.whl)
python3 scripts/build_fracgm_python_package.py
python3 -m pip install $(ls ./target/wheels/*.whl) --force-reinstall

🌱 Example Usages

• 🦀 Rust
• 🥐 C++
• 🐍 Python

☕ Supplementary Materials

• 📄 Appendix A. A simple example of FracGM with global optimal guarantees
• 📄 Appendix B. Tightness of linear relaxation
• 📄 Appendix C. Sensitivity of initial guess

🎁 Acknowledgement

The feature of maximum clique inlier selection (MCIS) refers to TEASER++'s implementation, which is under the MIT license. We modify the implementation to bundle with the FracGM Rust interface.