Need help with RansacLib?

Click the “chat” button below for chat support from the developer who created it, or find similar developers for support.

151 Stars 17 Forks BSD 3-Clause "New" or "Revised" License 98 Commits 2 Opened issues

Template-based implementation of RANSAC and its variants in C++

Readme

This library provides a template-based, header-only implementation of RANSAC and some of its variants. It is designed to be easily integrated into projects by keeping dependencies small while making it easy to combine it with (minimal) solvers.

Currently, the following RANSAC-variants are implemented
* LO-MSAC as described in *Lebeda, Matas, Chum, Fixing the Locally Optimized RANSAC, BMVC 2012*: RANSAC with local optimization (LO) and a truncated quadratic scoring function (as used by MSAC, described in *Torr, Zisserman, Robust computation and parametrization of multiple view relations, ICCV 1998*).
* MSAC with a non-linear refinement of each so-far best minimal model. To use MSAC instead of LO-MSAC, set

num_lo_steps_in

LORansacOptionsto

0. * HybridRANSAC as described in

RansacLib is header-only library, so no compilation is required. If you want to use the library in your project, simply include the directory into which you installed the library (such that

RansacLib/ransac.hcan be found from the path).

Besides the actual library, we also provide examples that illustrate how to use RansacLib. These examples can be found in the

examplessubdirectory. They require compilation, which can easily be done via CMake:

mkdir build cd build/ cmake ../ makeWe currently provide two examples: *

line_estimationshows how to implement a solver for 2D line fitting and integrate it into RansacLib. *

camera_pose_estimationshows how to implement a solver for absolute pose estimation of calibrated cameras and how to integrate it into RansacLib.

Other examples provides in

examples/are used for internal testing and can be safely ignored.

There are currently three dependencies: * Eigen * OpenGV * Ceres Solver

**Important**: Eigen requires alignment of certain types when vectorization is used. OpenGV uses vectorization to accelerate some computations. As such, it is critical to compile the examples that depend on OpenGV with exactly the same optimization flags as OpenGV. This should be ensured at the moment for Unix-based systems (Linux, Mac OS X), but we did not test it under Windows. If you are experiencing problems at run-time or during compilation, please compare

examples/CMakeLists.txtwith

opengv/CMakeLists.txtand if nessecary add additional flags to

examples/CMakeLists.txt.

RansacLib uses templates to enable easy integration of novel solvers into RANSAC. More precisely, three classes need to be defined:

class Model,

class ModelVector,

class Solver. These classes are explained in more detail in the following:

A class that describeds the model computed by your minimal solver. In the case of a solver for calibrated absolute pose estimation, this could for example be an

Eigen::Matrixdescribing the rotation and translation that transforms from the global to the local camera coordinate system. In the case of 2D line fitting, this could be an

Eigen::Vector3ddescribing the three parameters of an implicit line representation. The class must have a default constructor and assignments via the operator

=must be possible.

A class that contains multiple

Modelinstances. In the case of 2D line fitting, this could be a

std::vector<:vector3d>storing line representations. In the case of absolute pose estimation, this could be a

std::vector<:matrix>, Eigen::aligned_allocator<:matrix>>. Note that in the later case, Eigen requires the use of its

aligned_allocatorto ensure alignment for vectorization (see here for details). This requirment is what prevents us from directly using

std::vectorin RansacLib.

The

ModelVectorclass needs to implement the operator

[]such that a call

[i]returns the i-th model stored in a class instance. In addition, the class must have a default constructor and assignments via the operator

=must be possible.

The

Solverclass implements all functionality to estimate and evaluate minimal models. In addition, a

Solverinstance can provide functionality for the creation of model hypotheses from non-minimal samples and (non-linear) refinement of a model hypotheses. The following shows the how to implement a solver (see also the examples provided with RansacLib): ``` class MySolver { public: // Returns the number of data points required by a minimal solver. int min

// Returns the number of data points required by a non-minimal solver for
// the problem. This number should be larger than 0, even if your class
// does not implement a non-minimal solver to avoid trying to generate
// samples of size 0 inside RANSAC.
int non*minimal*sample_size() const;

// Returns the number of data points stored in the solver. int num_data() const;

// A call to the minimal solver implemented inside the solver. The input
// is a set of indices between 0 and num*data() - 1 that form the random
// minimal sample drawn by RANSAC. sample.size() is guaranteed to be
// min*sample_size(). The function is responsible for running the minimal
// solver on these selected data points. The estimated models are returned
// in models and the function returns the estimated number of models.
int MinimalSolver(const std::vector& sample,
ModelVector* models) const;

// A call to a non-minimal solver implemented in the class. This function
// is called during local optimization to generate a non-minimal sample from
// the inliers of the best model found so far. The input contains a list of
// indices of the data points that should be used to generate the non-minimal
// sample. It is assumes that the non-minimal solver provides at most one
// model, which is returned in model. The function returns 1 if a model could
// be estimated and 0 otherwise.
// This function has to be implemented, but could simply always return 0.
// In this case, local optimization becomes ineffective as no new models are
// created and refined. However, the best model estimated from a minimal sample
// is still refined.
// sample.size() is guaranteed to be non*minimal*sample_size() or larger.
int NonMinimalSolver(const std::vector& sample,
Model* model) const;

// Evaluates a given model on the i-th data point and returns the squared // error of that correspondence wrt. the model. double EvaluateModelOnPoint(const Model& model, int i) const;

// Performs least squares refinement of a given input Model model. On return, // model contains the refined model. sample contains the indices of the data // points that should be used to refine the model. // This function has to be implemented, but can simply be empty. In this case // the input model is left unaltered and no refinement occurs. Not implementing // this function will decrease the effectiveness of local optimization and RANSAC. void LeastSquares(const std::vector& sample, Model* model) const; }; ```

**Important**: RansacLib does not use a class that encapsulates the input data, e.g., 2D points for 2D line fitting or 2D-3D matches for absolute pose estimation. This is a deliberate design choice: some solvers might require additional data (for example, a solver that computes poses for multi-camera rigs might need a mapping from 2D-3D matches to cameras in the rig) in some very specific form. We thus decided to make the

Solverclass directly responsible for handling all data, including the input correspondences, rather than trying to constantly expand a data class to fit additional needs.

**Important**: Note that all mandatory functions defined above are

constand do not alter the state of the solver. This is a deliberate design choice: the

Solverclass also encapulates the input data, e.g., 2D-3D matches for absolute pose estimation. This data should not be altered by the solver. We thus pass the solver into RANSAC as

const Solver& solver. We acknowledge that this could potentially be restricting in some cases and are open to suggestions on how to guarantee that the input data is not altered while allowing the solver to change its internal state.

The Hybrid RANSAC implementation requires the use of a

HybridSolverrather than the

Solverclass. As with the

Solverclass, the

HybridSolverclass implements all functionality to estimate and evaluate minimal models. In addition, it provided additional functionality to enable the use of multiple minimal solvers inside RANSAC. Note that the class does not provide a non-minimal solver implementation as of now (due to the ambiguity in how to define a non-minimal solver for different types of data). The following shows the how to implement a solver (see also the examples provided with RansacLib): ``` class MyHybridSolver { public: // Returns the number of minimal solvers. int num

// Returns the number of data points required by each minimal solver.
// Note that even if solver i does not require data of a certain type, the
// corresponding entry in min*sample*sizes[i] still needs to be set to 0.
void min*sample*sizes(std::vectorstd::vector<int>* min*sample*sizes) const;

// Returns the number of data types stored in the solver.
int num*data*types() const;

// Returns the number of data points stored in the solver for each type of
// data.
void num*data(std::vector* num*data) const;

// Returns the prior probabilities for all solvers.
void solver*probabilities(std::vector* solver*probabilites) const;

// A call to one of the minimal solvers implemented inside the solver. The
// input are multiple sets of indices, each between 0 and
// num*data[solver*idx] - 1 that form the random minimal sample drawn by
// HybridRANSAC. In addition, the index solver*idx of the minimal solver
// selected by HybridRANSAC is provided as input. The overall size of the
// sample is guaranteed to be sample*sizes[solver*idx]. The function is
// responsible for running the solver*idx-th minimal solver on these
// selected data points. The estimated models are returned in models and
// the function returns the estimated number of models.
int MinimalSolver(const std::vectorstd::vector<int>& sample,
const int solver_idx, ModelVector* models) const;

// Evaluates a given model on the i-th data point of the t-th data type // and returns the squared error of that correspondence wrt. the model. double EvaluateModelOnPoint(const Model& model, int t, int i) const;

// Performs least squares refinement of a given input Model model. On // return, model contains the refined model. sample contains the indices // of the data points that should be used to refine the model. // This function has to be implemented, but can simply be empty. In this case // the input model is left unaltered and no refinement occurs. Not implementing // this function will decrease the effectiveness of local optimization and RANSAC. void LeastSquares(const std::vectorstd::vector<int>& sample, Model* model) const; }; ```

RansacLib is licensed under the BSD 3-Clause license. Please see License for details.

If you are using RansacLib, please consider adding the name of your project / company (and a link to your / your project's webpage) to the list of projects using RansacLib below.

If you are using the library for (scientific) publications, please cite the following source:

@misc{Sattler2019Github, title = {{RansacLib - A Template-based *SAC Implementation}}, author = {Torsten Sattler and others}, URL = {https://github.com/tsattler/RansacLib}, year = {2019} }Please cite also the original publications of the different methods: * When using the

LocallyOptimizedMSACimplementation in ransac.h, please cite

@inproceedings{Lebeda2012BMVC, title = {{Fixing the Locally Optimized RANSAC}}, author = {Karel Lebeda and Jiri Matas and Ondrej Chum}, booktitle = {British Machine Vision Conference (BMVC)}, year = {2012} }* When using the

LocallyOptimizedMSACimplementation in ransac.h with

num_lo_steps_set to 0, please cite

@inproceedings{Torr1998ICCV, title = {{ Robust computation and parametrization of multiple view relations}}, author = {Phil H. S. Torr and Andrew Zisserman}, booktitle = {International Conference on Computer Vision (ICCV)}, year = {1998} }* When using the

LocallyOptimizedHybridMSACimplementatio in ransac.h, please cite

@inproceedings{Camposeco2018CPVR, title = {{Hybrid Camera Pose Estimation}}, author = {Federico Camposeco and Andrea Cohen and Marc Pollefeys and Torsten Sattler}, booktitle = {Conference on Computer Vision and Pattern Recognition (CVPR)}, year = {2018} }and the paper by Lebeda et al.

Contributions to RansacLib, e.g., bug reports, improvements, or bug fixes, are very welcome. Please use Github's issues and pull request functionality to contribute.

When contributing, please adhere to Google's C++ Style Guide.

- Active Search v1.1 uses RansacLib instead of its original RANSAC implementation. Code for Active Search will become available here.
- radialpose is an implementation of minimal solvers for absolute camera pose estimation for images with radial distortion.