Public Member Functions | Protected Member Functions | List of all members
alvar::Ransac< MODEL, PARAMETER > Class Template Referenceabstract

Implementation of a general RANdom SAmple Consensus algorithm. More...

#include <Ransac.h>

Inheritance diagram for alvar::Ransac< MODEL, PARAMETER >:
Inheritance graph
[legend]

Public Member Functions

int estimate (PARAMETER *params, int param_c, int support_limit, int max_rounds, MODEL *model)
 Estimates a model from input data parameters. More...
 
 Ransac (int min_params, int max_params)
 Initialize the algorithm. More...
 
int refine (PARAMETER *params, int param_c, int support_limit, int max_rounds, MODEL *model, char *inlier_mask=NULL)
 Iteratively makes the estimated model better. More...
 
virtual ~Ransac ()
 
- Public Member Functions inherited from alvar::RansacImpl
int estimateRequiredRounds (float success_propability, float inlier_percentage)
 How many rounds are needed for the Ransac to work. More...
 

Protected Member Functions

void _doEstimate (void **params, int param_c, void *model)
 
bool _doSupports (void *param, void *model)
 
virtual void doEstimate (PARAMETER **params, int param_c, MODEL *model)=0
 Creates a model estimate from a set of parameters. More...
 
virtual bool doSupports (PARAMETER *param, MODEL *model)=0
 Computes how well a parameters supports a model. More...
 
- Protected Member Functions inherited from alvar::RansacImpl
virtual void _doEstimate (int *params, int param_c, void *model)
 
virtual bool _doSupports (int param, void *model)
 
int _estimate (void *params, int param_c, int support_limit, int max_rounds, void *model)
 
int _estimate (int param_c, int support_limit, int max_rounds, void *model)
 
int _refine (void *params, int param_c, int support_limit, int max_rounds, void *model, char *inlier_mask=NULL)
 
int _refine (int param_c, int support_limit, int max_rounds, void *model, char *inlier_mask=NULL)
 
 RansacImpl (int min_params, int max_params, int sizeof_param, int sizeof_model)
 
 RansacImpl (int min_params, int max_params, int sizeof_model)
 
virtual ~RansacImpl ()
 

Additional Inherited Members

- Protected Attributes inherited from alvar::RansacImpl
void * hypothesis
 
int * indices
 
int max_params
 
int min_params
 
void ** samples
 
int sizeof_model
 
int sizeof_param
 

Detailed Description

template<typename MODEL, typename PARAMETER>
class alvar::Ransac< MODEL, PARAMETER >

Implementation of a general RANdom SAmple Consensus algorithm.

This implementation can be used to estimate model from a set of input data. The user needs to provide support methods to compute the best model given a set of input data and to classify input data into inliers and outliers.

For more information see "Martin A Fischler and Robrt 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" (http://portal.acm.org/citation.cfm?doid=358669.358692).

MODEL is the estimated model, for example endpoints of a line for line fitting.

PARAMETER is the input for model estimation, for example 2D point for line fitting.

MODEL must support an assigment operator.

The user needs to extend this class and provide two methods:

void doEstimate(PARAMETER** params, int param_c, MODEL* model);
bool doSupports(PARAMETER* param, MODEL* model);

Example: Fitting points to a line:

typedef struct Point { double x, double y; };
typedef struct Line { Point p1, p2; };
class MyLineFittingRansac : public Ransac<Line, Point> {
// Line fitting needs at least 2 parameters and here we want
// to support at most 16 parameters.
MyLineFittingRansac() : Ransac(2, 16) {}
void doEstimate(Point **points, int points_c, Line *line) {
if (points_c == 2) { return Line(*points[0], *points[1]); }
else { // compute best line fitting up to 16 points. }
}
bool doSupports(Point *point, Line *line) {
double distance = // compute point distance to line.
return distance < POINT_DISTANCE_LIMIT;
}
};
Point input[N_POINTS] = { .. };
Line line;
MyLineFittingRansac ransac;
// assuming 60% of inliers, run RANSAC until the best model is found with 99% propability.
int max_rounds = ransac.estimateRequiredRounds(0.99, 0.6);
int number_of_inliers = ransac.estimate(input, N_POINTS, N_POINTS, max_rounds, &line);
// lets make the estimate even better.
if (number_of_inliers > 0 && number_of_inliers < N_POINTS)
number_of_inliers = ransac.refine(input, N_POINTS, N_POINTS, 10, &line);
// you should keep track of the real percentage of inliers to determine
// the required number of RANSAC rounds.
double inlier_percentage = (double)number_of_inliers / (double)N_POINTS;

Definition at line 171 of file Ransac.h.

Constructor & Destructor Documentation

template<typename MODEL , typename PARAMETER >
alvar::Ransac< MODEL, PARAMETER >::Ransac ( int  min_params,
int  max_params 
)
inline

Initialize the algorithm.

Uses at least min_params and at most max_params number of input data elements for model estimation.

Must be: max_params >= min_params

Parameters
min_paramsis the minimum number of parameters needed to create a model.
max_paramsis the maximum number of parameters to using in refining the model.

Definition at line 225 of file Ransac.h.

template<typename MODEL , typename PARAMETER >
virtual alvar::Ransac< MODEL, PARAMETER >::~Ransac ( )
inlinevirtual

Definition at line 228 of file Ransac.h.

Member Function Documentation

template<typename MODEL , typename PARAMETER >
void alvar::Ransac< MODEL, PARAMETER >::_doEstimate ( void **  params,
int  param_c,
void *  model 
)
inlineprotectedvirtual

Wrapper for templated parameters.

Reimplemented from alvar::RansacImpl.

Definition at line 201 of file Ransac.h.

template<typename MODEL , typename PARAMETER >
bool alvar::Ransac< MODEL, PARAMETER >::_doSupports ( void *  param,
void *  model 
)
inlineprotectedvirtual

Wrapper for templated parameters.

Reimplemented from alvar::RansacImpl.

Definition at line 208 of file Ransac.h.

template<typename MODEL , typename PARAMETER >
virtual void alvar::Ransac< MODEL, PARAMETER >::doEstimate ( PARAMETER **  params,
int  param_c,
MODEL *  model 
)
protectedpure virtual

Creates a model estimate from a set of parameters.

The user must implement this method to compute model parameters from the input data.

Parameters
paramsAn array of pointers to sampled parameters (input data).
param_cThe number of parameter pointers in the params array.
modelPointer to the model where to store the estimate.
template<typename MODEL , typename PARAMETER >
virtual bool alvar::Ransac< MODEL, PARAMETER >::doSupports ( PARAMETER *  param,
MODEL *  model 
)
protectedpure virtual

Computes how well a parameters supports a model.

This method is used by the RANSAC algorithm to count how many parameters support the estimated model (inliers). Althought this is case specific, usually parameter supports the model when the distance from model prediction is not too far away from the parameter.

Parameters
paramPointer to the parameter to check.
modelPointer to the model to check the parameter against.
Returns
True when the parameter supports the model.
template<typename MODEL , typename PARAMETER >
int alvar::Ransac< MODEL, PARAMETER >::estimate ( PARAMETER *  params,
int  param_c,
int  support_limit,
int  max_rounds,
MODEL *  model 
)
inline

Estimates a model from input data parameters.

Randomly samples min_params number of input data elements from params array and chooses the model that has the largest set of supporting parameters (inliers) in the params array.

Note that this method always uses min_params number of parameters, that is, doEstimate method can be implemented to support only the minimum number of parameters unless refine method is used.

Parameters
paramsParameters that the model is estimated from (input data).
param_cNumber of elements in the params array.
support_limitThe search is stopped if a model receives more support that this limit.
max_roundsHow many different samples are tried before stopping the search.
modelThe estimated model is stored here.
Returns
the number of parameters supporting the model, or 0 if a suitable model could not be build at all.

Definition at line 250 of file Ransac.h.

template<typename MODEL , typename PARAMETER >
int alvar::Ransac< MODEL, PARAMETER >::refine ( PARAMETER *  params,
int  param_c,
int  support_limit,
int  max_rounds,
MODEL *  model,
char *  inlier_mask = NULL 
)
inline

Iteratively makes the estimated model better.

Starting with the estimated model, computes the model from all inlier parameters and interates until no new parameters support the model.

Note that this method uses up to max_params number of parameters, that is, doEstimate method must be implemented in such a way that it can estimate a model from a variable number of parameters.

Parameters
paramsParameters that the model is estimated from.
param_cNumber of parameters.
support_limitThe search is stopped is a model receives more support that this limit.
max_roundsHow many iterations of the refinement are run.
modelThe estimated model that is refined.
inlier_maskByte array where 1 is stored for inliers and 0 for outliers.
Returns
the number of parameters supporting the model.

Definition at line 275 of file Ransac.h.


The documentation for this class was generated from the following file:


ar_track_alvar
Author(s): Scott Niekum
autogenerated on Thu Jun 6 2019 19:27:24