PARP Research Group
| PARP Research Group |
Universidad de Murcia |
QVRANSAC< Element, Model > Class Template Reference
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Public Member Functions | |
| QVRANSAC (const int sampleSetSize, const int minInliers) | |
| Constructor for QVRANSAC class. | |
| virtual bool | fit (const QList< Element > &elementList, Model &model)=0 |
| Generate a model from a set of observations. | |
| virtual bool | test (const Model &model, const Element &element)=0 |
| Check if an observation fits in a model. | |
| void | addElement (const Element &element) |
| Adds a data sample to the observations set. | |
| const Model & | getBestModel () const |
| Gets the best model obtained in a search. | |
| const QList< Element > & | getBestInliers () const |
| Gets the data elements matching with the best model. | |
| int | getIterations () const |
| Gets the number of iterations performed in a search. | |
| bool | iterate (const int maxIterations) |
| Starts a RANSAC search. | |
Implementation of RANSAC, a robust statistical model fitting algorithm.
qvsampleconsensus.h qvmath/qvsampleconsensus.h RANSAC can be used for regression over sample data sets, containing a significant percentage of gross errors. The following image shows the result of using RANSAC to fit a linear model over a set of points in the bi-dimensional plane:
it is a more robust linear fitting than those performed by other common algorithms, such as least squares, because RANSAC can ignore a big amount of erroneous or not corresponding data elements.
The input to the RANSAC algorithm is a set S of observed data values, or elements, and a parametric model M which must be fitted to the observations. RANSAC looks randomly for subsets s S of a fixed size n, which gets a model M that fits better the whole data set S.
With each subset s, a model fitting is performed, obtaining the parameters for the model M that fit it best to the elements of the subset. If this succeeds, the algorithm counts the number of elements of the set S that fit with the new model.
After testing a fixed number k of random subsets, the algorithm stops, and returns the parameters of the model M that make it fit the most elements of S.
To create a RANSAC iterator, the class QVRANSAC should be extended, instantiating the Element and Model template parameters with the type or class for the observed data values, and the model, respectively. The following example defines a RANSAC iterator that will fit a line (represented as an object derived from class Line) over a set of points (represented as objects derived from class QPoint):
// We create the class for the fitting model class Line { [...] public: Line() { [...] }; Line(const QPoint, const QPoint) { [...] }; double distance(const QPoint) const { return [...]; } }; // And a subclass extending class QVRANSAC class myRANSAC: public QVRANSAC<QPoint, Line> { private: double maximalDistance; public: myRANSAC(const QList<QPoint> &observedPoints, const double maximalDistance): QVRANSAC< QPoint, Line>(2, 10), maximalDistance(maximalDistance) { foreach(QPoint point, observedPoints) addElement(point); } const bool fit(const QList<QPoint> &testInliers, Line &model) { model = Line(testInliers.first(), testInliers.last()); return true; }; const bool test(const Line &model, const QPoint &point) { return model.distance(point) < maximalDistance; }; };
The constructor should call QVRANSAC constructor, providing the size of the subsets n, and the minimum number of points that a model should fit, from the whole set S, to be considered a valid model. In this case, only 2 points are needed to create a line, and we will require 10 points fitting in the line to consider it a proper line.
Value maximalDistance will be used to establish the maximal distance between a point and a line, to consider that point as fitting in the line. The parameter observedPoints is the list of observed data values, points in this case. The constructor myRANSAC adds them to the RANSAC search using the function addElement.
Methods fit and test are declared as virtual in QVRANSAC, and must be implemented for class myRANSAC. Method fit must contain the code to generate a line model from a subset of the observed values s. Method test must be able to perform element-model fitting test. Once created the RANSAC class, extending class QVRANSAC, the search must be initiated:
[...] QList<QPoint> observedData; observedData.append(QPoint(10,20)); observedData.append(QPoint(20,50)); [...] int maxIterations = 100; myRANSAC samplerConsensus(observedData, 1.5); if (samplerConsensus.iterate(maxIterations)) { Line line = samplerConsensus.getBestModel(); std::cout << "Found regression line." << std::endl; } else std::cout << "A line couldn't be fitted to the data, in " << maxIterations << " iterations."; [...]
The iterate method starts a RANSAC search over of a maximum number of random subsets from S. It returns true when the search is successful, meaning that a line, closer than 1.5 units to at least 10 sample points from the observedData set was found by the algorithm, in exactly 100 tries. Else it will return false.
The maximum number of iterations (aka, number k of subsets of observedDatato test) should be small enough to stop the search if the probability of finding a good fitting subset s becomes low. It should be established upon the probability that a valid model would fit a random element of the set S.
Martin A. Fischler and Robert C. Bolles. Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. Comm. of the ACM 24: 381–395.
Definition at line 122 of file qvsampleconsensus.h.
| QVRANSAC< Element, Model >::QVRANSAC | ( | const int | sampleSetSize, | |
| const int | minInliers | |||
| ) | [inline] |
Constructor for QVRANSAC class.
Because QVRANSAC is a pure virtual class, this constructor should only be called from the constructor of its subclasses.
| sampleSetSize | size of the subsets s to be used for model fitting. | |
| minInliers | minimum number of sample data for a model to fit, to be considered a valid model. |
Definition at line 176 of file qvsampleconsensus.h.
| virtual bool QVRANSAC< Element, Model >::fit | ( | const QList< Element > & | elementList, | |
| Model & | model | |||
| ) | [pure virtual] |
Generate a model from a set of observations.
This method should be implemented by subclasses of QVRANSAC with the code to generate a model, from a set of sample data.
| elementList | list of test inliers. | |
| model | model to store parameters fitting the observed elements. |
Referenced by QVRANSAC< Element, Model >::iterate().
| virtual bool QVRANSAC< Element, Model >::test | ( | const Model & | model, | |
| const Element & | element | |||
| ) | [pure virtual] |
Check if an observation fits in a model.
This method should be implemented by subclasses of QVRANSAC with the code to check if a sample data fits in a generated model,
| element | element. | |
| model | model. |
Referenced by QVRANSAC< Element, Model >::iterate().
| void QVRANSAC< Element, Model >::addElement | ( | const Element & | element | ) | [inline] |
Adds a data sample to the observations set.
This method should be called before performing any search with the function iterate.
| element | element. |
Definition at line 201 of file qvsampleconsensus.h.
| const Model& QVRANSAC< Element, Model >::getBestModel | ( | ) | const [inline] |
Gets the best model obtained in a search.
This method should be called after performing a search with the function iterate.
the best model obtained in a search, after calling the init() method.
Definition at line 208 of file qvsampleconsensus.h.
| const QList<Element>& QVRANSAC< Element, Model >::getBestInliers | ( | ) | const [inline] |
Gets the data elements matching with the best model.
This method should be called after performing a search with the function iterate. It will return the data elements from the observations set, matching with the best model.
Definition at line 215 of file qvsampleconsensus.h.
| int QVRANSAC< Element, Model >::getIterations | ( | ) | const [inline] |
Gets the number of iterations performed in a search.
This method should be called after performing a search with the function iterate. It will return the number of random sets tested for model fitting in a RANSAC search.
Definition at line 222 of file qvsampleconsensus.h.
| bool QVRANSAC< Element, Model >::iterate | ( | const int | maxIterations | ) | [inline] |
Starts a RANSAC search.
This method will perform a random search over the elements of the observations set, to find a model that fits a given number of elements from that set, specified in the constructor of the RANSAC object.
Definition at line 231 of file qvsampleconsensus.h.