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_inLORansacOptionsto0.
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.h can 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 examples subdirectory. They require compilation, which can easily be done via CMake:
mkdir build
cd build/
cmake ../
make
We 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 two dependencies:
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.txt with opengv/CMakeLists.txt and 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::Matrix<double, 3, 4> describing 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::Vector3d describing 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 Model instances. In the case of 2D line fitting, this could be a std::vector<Eigen::Vector3d> storing line representations. In the case of absolute pose estimation, this could be a std::vector<Eigen::Matrix<double, 3, 4>, Eigen::aligned_allocator<Eigen::Matrix<double, 3, 4>>. Note that in the later case, Eigen requires the use of its aligned_allocator to ensure alignment for vectorization (see here for details). This requirment is what prevents us from directly using std::vector<Model> in RansacLib.
The ModelVector class 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 Solver class implements all functionality to estimate and evaluate minimal models. In addition, a Solver instance 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_sample_size() const;
// 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<int>& 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<int>& 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<int>& 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 Solver class 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 const and do not alter the state of the solver. This is a deliberate design choice: the Solver class 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.
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},
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 withnum_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}
}
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.