RootBA: Square Root Bundle Adjustment

Project Page | Paper | Poster | Video | Code

Table of Contents

• RootBA: Square Root Bundle Adjustment
• Table of Contents
• Citation
• Dependencies
  • Installing dependencies on Linux
  • Installing depedencies on macOS
• Building
  • CMake Options
  • Running Unit Tests
• BAL Problems
• Testing Bundle Adjustment
  • Visualization of BAL Problems
  • Running Bundle Adjustment
  • Config Options
  • Visualization of Results
  • Batch Evaluation
• Repository Layout
  • Code Layout
• License

Citation

If you find our work useful in your research, please consider citing:

@inproceedings{weber2023poba,
 author = {Simon Weber and Nikolaus Demmel and Tin Chon Chan and Daniel Cremers},
 title = {Power Bundle Adjustment for Large-Scale 3D Reconstruction},
 booktitle = {IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
 year = {2023}
}

@inproceedings{demmel2021rootba,
 author = {Nikolaus Demmel and Christiane Sommer and Daniel Cremers and Vladyslav Usenko},
 title = {Square Root Bundle Adjustment for Large-Scale Reconstruction},
 booktitle = {IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
 year = {2021}
}

Note: This repository contains the code for the CVPR'21 Square Root BA paper, as well as the CVPR'23 Power Bundle Adjustment paper. This README describes the implementation and tools in this repository as well as the tutorial for reproducing the RootBA paper results. There is a dedicated self-contained tutorial for reproducing the PoBA results.

Dependencies

The following describes the needed dependencies in general, followed by concrete instructions to install them on Linux or macOS.

Toolchain

• C++17 compiler
• CMake 3.13 or newer

Included as submodule or copy

See the external folder and the scripts/build-external.sh script.

The following libraries are submodules:

• Eigen
• Sophus
• ceres-solver
• basalt-headers
• Pangolin
• clipp
• {fmt}
• toml11
• visit_struct
• cereal
• abseil-cpp
• wise_enum
• enum-flags
• nameof
• googletest

Some external libraries have their source copied directly as part of this repository, see the external/download_copied_sources.sh script:

• nlohmann/json
• magic_enum
• pprint

Externally supplied

The following dependencies are expected to be supplied externally, e.g. from a system-wide install:

• TBB

  Note: You can control the location where TBB is found by setting the environment variable TBB_ROOT, e.g. export TBB_ROOT=/opt/intel/tbb.

• glog
• BLAS and LAPACK routines are needed by SuiteSparse, and optionally used by Eigen and Ceres directly for some operations.

On UNIX OSes other than macOS we recommend ATLAS, which includes BLAS and LAPACK routines. It is also possible to use OpenBLAS. However, one needs to be careful to turn off the threading inside OpenBLAS as it conflicts with use of threads in RootBA and also Ceres. For example, export OPENBLAS_NUM_THREADS=1.

MacOS ships with an optimized LAPACK and BLAS implementation as part of the Accelerate framework. The Ceres build system will automatically detect and use it.

Python

Python dependencies are needed for scripts and tools to generate config files, run experiments, plot results, etc. For generating result tables and plots you additionally need latexmk and a LaTeX distribution.

Developer Tools

These additional dependencies are useful if you plan to work on the code:

• ccache helps to speed up re-compilation by caching the compilation results for unchanged translation units.
• ninja is an alternative cmake generator that has better parallelization of your builds compared to standard make.
• clang-format version >= 10 is used for formatting C++ code.
• clang-tidy version >= 12 is used to style-check C++ code.
• yapf is used for formatting Python code.

There are scripts to help apply formatting and style checks to all source code files:

• scripts/clang-format-all.sh
• scripts/clang-tidy-all.sh
• scripts/yapf-all.sh

Installing dependencies on Linux

Ubuntu 20.04 and newer are supported.

Toolchain and libraries

# for RootBA and Ceres
sudo apt install \
    libgoogle-glog-dev \
    libgflags-dev \
    libtbb-dev \
    libatlas-base-dev \
    libsuitesparse-dev
# for Pangolin GUI
sudo apt install \
    libglew-dev \
    ffmpeg \
    libavcodec-dev \
    libavutil-dev \
    libavformat-dev \
    libswscale-dev \
    libavdevice-dev \
    libjpeg-dev \
    libpng-dev \
    libtiff5-dev \
    libopenexr-dev

To get a recent version of cmake you can easily install it from pip.

sudo apt install python3-pip
python3 -m pip install --user -U cmake

# put this in your .bashrc to ensure cmake from pip is found
export PATH="$HOME/.local/bin:$PATH"

Note: If you run this in a plain Ubuntu docker container you might need to install some additional basic packages (which should already be installed on a desktop system):

sudo apt install git-core wget curl time software-properties-common

Python (optional)

Other python dependencies (for tools and scripts) can also be installed via pip.

python3 -m pip install --user -U py_ubjson matplotlib numpy munch scipy pylatex toml

For generating result tables and plots you additionally need latexmk and a LaTeX distribution.

sudo apt install texlive-latex-extra latexmk

Developer tools (optional)

For developer tools, you can install ninja and ccache from apt:

sudo apt install ccache ninja-build

You can install yapf from pip:

python3 -m pip install --user -U yapf

For clang-tidy you need at least version 12, so even on Ubuntu 20.04 you need to get it from the llvm website:

wget -O - https://apt.llvm.org/llvm-snapshot.gpg.key | sudo apt-key add -
sudo add-apt-repository "deb http://apt.llvm.org/$(lsb_release -sc)/ llvm-toolchain-$(lsb_release -sc)-12 main"
sudo apt update
sudo apt install clang-tidy-12

On Ubuntu 20.04 and above, clang-format from apt is recent enough (we require at least version 10):

sudo apt install clang-format

Installing depedencies on macOS

We support macOS 10.15 "Catalina" and newer.

Note: We have not yet tested this codebase on M1 macs.

Toolchain and libraries

Install Homebrew, then use it to install dependencies:

brew install cmake glog gflags tbb suitesparse
brew install glew ffmpeg libjpeg libpng libtiff

Python (optional)

Python dependencies (for tools and scripts) can be installed via pip after installing python 3 from homebrew.

brew install python bash gnu-getopt
python3 -m pip install --user -U py_ubjson matplotlib numpy munch scipy pylatex toml

For generating result tables and plots you additionally need latexmk and a LaTeX distribution.

brew install --cask mactex

Developer tools (optional)

Developer tools can be installed with homebrew.

brew install ccache ninja clang-format llvm yapf

Building

Build dependencies

./scripts/build-external.sh [BUILD_TYPE]

You can optionally pass the cmake BUILD_TYPE used to compile the third party libraries as the first argument. If you don't pass anything the deafult is Release. This build script will use ccache and ninja automaticaly if they are found on PATH.

Note: The build-external.sh build script will init, synchronize and update all submodules, so usually you don't have to worry about submodules. For example, you don't have to run git submodule update --recursive manually when the submodules were updated upstream, as long as you run the build-external.sh script. But there is a small caveat, should you ever want to update a submodule yourself (e.g. update Eigen to a new version). In that case you need to commit that change before running this script, else the script will revert the submodule back to the committed version.

Build RootBA option a)

Use the build script.

./scripts/build-rootba.sh [BUILD_TYPE]

You can optionally pass the cmake BUILD_TYPE used to compile RootBA as the first argument. If you don't pass anything the default is Release. The cmake build folder is build, inside the project root. This build script will use ccache and ninja automaticaly if they are found on PATH.

Build RootBA option b)

Manually build with the standard cmake workflow.

mkdir build && cd build
cmake ..
make -j8

The cmake project will automatically use ccache if it is found on PATH (unless you override by manually specifying CMAKE_C_COMPILER_LAUNCHER/CMAKE_CXX_COMPILER_LAUNCHER). To use ninja instead of make, you can use:

cmake .. -G Ninja
ninja

CMake Options

You can set the following options when calling cmake. For setting option OPTION to a value of VALUE, add the command line argument -DOPTION=VALUE to the cmake call above.

• ROOTBA_DEVELOPER_MODE: Presets for convenience during development. If enabled, the binaries are not placed in the cmake's default location in the cmake build folder, but instead inside the source folder, in <PROJECT_ROOT>/bin. Turn off if you prefer to work directly in multiple build folders at the same time. Default: ON
• ROOTBA_ENABLE_TESTING: Build unit tests. Default: ON
• ROOTBA_INSTANTIATIONS_DOUBLE: Instantiate templates with Scalar = double. If disabled, running with config option use_double = true will cause a runtime error. But, disabling it may reduce compile times and memory consumption during compilation significantly. While developing, we recommend leaving only one of ROOTBA_INSTANTIONS_DOUBLE or ROOTBA_INSTANTIATIONS_FLOAT enabled, not both. Default: ON
• ROOTBA_INSTANTIATIONS_FLOAT: Instantiate templates with Scalar = float. If disabled, running with config option use_double = false will cause a runtime error. But, disabling it may reduce compile times and memory consumption during compilation significantly. While developing, we recommend leaving only one of ROOTBA_INSTANTIONS_DOUBLE or ROOTBA_INSTANTIATIONS_FLOAT enabled, not both. Default: ON
• ROOTBA_INSTANTIATIONS_STATIC_LMB: Instatiate statically sized specializations for small sized landmark blocks. If disabled, all sizes use the dymanically sized implementation, which depending on the problem, might have slightly higher runtime (maybe around 10%). But, disabling it might reduce compile times and memory consumption during compilation significantly. We recommend turning this off during development. Default: ON
• BUILD_SHARED_LIBS: Build all rootba modules as shared libraries (see the cmake documentation). Default: ON

Running Unit Tests

Unit tests are implemented with the GoogleTest framework and can be run with CMake's ctest command after compilation.

cd build
ctest

BAL Problems

In the "Bundle Adjustment in the Large" (BAL) problem formulation cameras are represented as world-to-cam poses and points as 3D points in world frame, and each camera has its own set of independent intrinsics, using the "Snavely projection" function with one focal length f and two radial distortion parameters k1 and k2. This is implemented in the BalProblem class. Besides the BAL format, we also implement a reader for "bundle" files, but the internal representation is the same.

Note: In our code we follow the convention that the positive z-axis points forward in camera vi