Robust model fitting. More...
#include <Ransac.hpp>
Collaboration diagram for TRTK::Ransac< T, DataType >:Classes | |
| class | Model |
| Interface class for models to be used with the Ransac class. More... | |
Public Types | |
| enum | Algorithm { RANSAC, RANSAC_BIGGEST_CONSESUS_SET, RANSAC_SMALLEST_RMSE } |
| enum | Error { NO_DATA_AVAILABLE, NO_MODEL_AVAILABLE, NOT_ENOUGH_DATA_POINTS, UNKNOWN_ALGORITHM, UNKNOWN_ERROR } |
Public Member Functions | |
| unsigned | compute () |
| Runs the model fitting algorithm. | |
| void | setAlgorithm (Algorithm algorithm=RANSAC) |
| Sets the algorithm used to compute the consensus set. | |
| void | setData (const std::vector< DataType > &data) |
| Sets the sample data. | |
| void | setErrorTolerance (T error_tolerance) |
| Sets the error tolerance. | |
| void | setMinimumSetSize (unsigned threshold) |
| Sets the minimal size a consensus set must have (not used by all alogrithms). | |
| void | setModel (Model &model) |
| Sets the model. | |
| void | setProbability (T probability) |
| Sets the probability that... | |
| void | setThreshold (unsigned threshold) |
| Sets a threshold... | |
| void | setTrials (unsigned number) |
| Sets the maximum number of attempts to find a consensus set. | |
Protected Member Functions | |
| unsigned | algorithmRansac () |
| RANSAC algorithm as described by Fischler and Bolles. | |
| unsigned | algorithmRansacBiggestConsensusSet () |
| Modified version of the RANSAC algorithm as described by Fischler and Bolles. | |
| unsigned | algorithmRansacSmallestRmse () |
| Modified version of the RANSAC algorithm as described by Fischler and Bolles. | |
Protected Attributes | |
| const std::vector< DataType > * | data |
| Model * | model |
| T | error_tolerance |
| unsigned | threshold |
| unsigned | trials |
| T | probability |
| unsigned | minimumSetSize |
| unsigned(Ransac::* | algorithm )() |
Robust model fitting.
| T | Scalar type (must be a floating point). |
| DataType | Type of the data points. |
The RANSAC algorithm works by taking initial data sets (where a set contains as few points as feasible, just to support the model) and by enlarging these sets with consistent data. Finally the bigest consensus set is taken and a new refined model is computed from these data points. This algorithm conform to the original algorithm described by Fischler and Bolles. However, this class also provides several variations of this algorithm.
All algorithms assume that there are two sources of error. First, measurement errors which in general are small and normally distributed; these average out while doing a regression analysis. Second, gross errors which are quite big and arbitrarily distributed. All algorithms assume that you define some error bound (which constitutes the deviation of a datum to an estimated model) which should be chosen such that all gross errors are neglected but as many as possible good points are taken into consideration. Since measurement errors are quite small, this is often easily possible.
If no maximum number of attempts (trials) to find a consensus set is given, it is automatically computed from the minimum number of samples needed to compute a model as well as from the probability (the default value is 0.2) that any selected data point for such a minimal set is within the given error tolerance. If no threshold is given, it is set to 8/10 of the size of data. The default algorithm is "RANSAC".
The class works according to the strategy pattern; the class as is constitutes the context and all models used form the strategies. A regression model (e.g. a line fitting model) must conform to a certain interfacen, namely Model. See the example below.
Example:
#include <iostream> #include <TRTK/Ransac.hpp> #include <TRTK/RansacModelFitLine.hpp> #include <TRTK/Tools.hpp> using namespace std; using namespace TRTK; using namespace TRTK::Tools; int main() { // Construct some points lying on a line and add some noise and outliers. vector<Coordinate<double> > points; double slope = 0.7; double y_intercept = -3; for (int i = -10; i < 10; ++i) { // Noisy measurement. double x = i + randn(0.0, 0.1); double y = i * slope + y_intercept + randn(0.0, 0.1); Coordinate<double> point(x, y); points.push_back(point); } for (int i = 0; i < 5; ++i) { // Gros outliers. double x = rand(-10.0, 10.0); double y = rand(-10.0, 10.0); Coordinate<double> point(x, y); points.push_back(point); } // Estimate the line parameters using ordinary least sqares. FitLine<double> fitLine; fitLine.setPoints(points); fitLine.compute(); cout << "Slope: " << fitLine.getSlope() << endl; cout << "Y-intercept: " << fitLine.getYIntercept() << endl; cout << "Direction Vector: " << fitLine.getDirectionVector() << endl; cout << "Distance from origin: " << fitLine.getDistanceFromOrigin() << endl; cout << "RMSE: " << fitLine.getRMS() << endl << endl; // Estimate the line parameters using RANSAC. Ransac<double> ransac; RansacModelFitLine<double> model; ransac.setModel(model); ransac.setData(points); ransac.setErrorTolerance(0.2); unsigned number_of_samples_used = ransac.compute(); cout << "Slope: " << model.getSlope() << endl; cout << "Y-intercept: " << model.getYIntercept() << endl; cout << "Direction Vector: " << model.getDirectionVector() << endl; cout << "Distance from origin: " << model.getDistanceFromOrigin() << endl; cout << "Number of samples used: " << number_of_samples_used << endl; cout << "RMSE: " << model.getRMS() << endl; return 0; }
Output:
Slope: 0.824709 Y-intercept: -2.97947 Direction Vector: (-0.771483, -0.63625) Distance from origin: 2.29861 RMSE: 2.27904 Slope: 0.691347 Y-intercept: -3.00877 Direction Vector: (-0.822562, -0.568676) Distance from origin: 2.4749 Number of samples used: 19 RMSE: 0.0712661
"Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography", Fischler and Bolles, 1981, Communications of the ACM
Definition at line 186 of file Ransac.hpp.
| enum TRTK::Ransac::Algorithm |
Definition at line 200 of file Ransac.hpp.
| enum TRTK::Ransac::Error |
Definition at line 207 of file Ransac.hpp.
| unsigned TRTK::Ransac< T, DataType >::algorithmRansac | ( | ) | [protected] |
RANSAC algorithm as described by Fischler and Bolles.
If a consensus set is found whose size is greater than a given threshold then this set is taken to compute a new model and the algorithm is terminated. Otherwise a new model is computed from the biggest consensus set found.
Definition at line 279 of file Ransac.hpp.
| unsigned TRTK::Ransac< T, DataType >::algorithmRansacBiggestConsensusSet | ( | ) | [protected] |
Modified version of the RANSAC algorithm as described by Fischler and Bolles.
A new model is always computed from the biggest consensus set.
Definition at line 383 of file Ransac.hpp.
| unsigned TRTK::Ransac< T, DataType >::algorithmRansacSmallestRmse | ( | ) | [protected] |
Modified version of the RANSAC algorithm as described by Fischler and Bolles.
The model with the smallest RMSE is taken. The consensus set must be bigger than a given threshold (see setMinimumSetSize()), otherwise no model is estimated (i.e. the algorithm returns 0).
Definition at line 477 of file Ransac.hpp.
| unsigned TRTK::Ransac< T, DataType >::compute | ( | ) |
Runs the model fitting algorithm.
If no maximum number of attempts (trials) to find a consensus set is given, it is automatically computed from the minimum number of samples needed to compute a model as well as from the probability that any selected data point for such a minimal set is within the given error tolerance. See the references for more details. If no threshold is given, it is set to 8/10 of the size of data.
| ErrorObj | If the regression model is not set, an error object is thrown and its error code set to NO_MODEL_AVAILABLE. |
| ErrorObj | If no data is given, an error obejct is thrown and its error code set to NO_DATA_AVAILABLE. |
| ErrorObj | If there are not enough data points to compute the model, an error object is thrown and its error code set to NOT_ENOUGH_DATA_POINTS. |
Definition at line 603 of file Ransac.hpp.
| void TRTK::Ransac< T, DataType >::setErrorTolerance | ( | T | error_tolerance ) |
Sets the error tolerance.
Sets the error tolerance for establishing the datum-model-compatibility, i.e. the amount of how much a data point is allowed to deviate from the model.
Definition at line 738 of file Ransac.hpp.
| void TRTK::Ransac< T, DataType >::setProbability | ( | T | probability ) |
Sets the probability that...
... any selected data point in a minimal set for computing the model is within the given error tolerance.
Definition at line 769 of file Ransac.hpp.
| void TRTK::Ransac< T, DataType >::setThreshold | ( | unsigned | threshold ) |
Sets a threshold...
... denoting a bound concerning the size of the consensus set after which some algorithms might stop looking for further consensus sets and instead use the current set to compute a new model.
Definition at line 784 of file Ransac.hpp.
Documentation generated by Doxygen
