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

#include <Ransac.h>

Inheritance diagram for alvar::Ransac< MODEL, PARAMETER >:

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.
	Ransac (int min_params, int max_params)
	Initialize the algorithm.
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.
virtual	~Ransac ()
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.
virtual bool	doSupports (PARAMETER param, MODEL model)=0
	Computes how well a parameters supports a model.

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_params	is the minimum number of parameters needed to create a model.
max_params	is 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 ( ) [inline, virtual]

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
	)		`[inline, protected, virtual]`

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
	)		`[inline, protected, virtual]`

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
	)		`[protected, pure 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:

params	An array of pointers to sampled parameters (input data).
param_c	The number of parameter pointers in the params array.
model	Pointer to the model where to store the estimate.

template<typename MODEL , typename PARAMETER >

virtual bool alvar::Ransac< MODEL, PARAMETER >::doSupports	(	PARAMETER *	param,
		MODEL *	model
	)		`[protected, pure 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:

param	Pointer to the parameter to check.
model	Pointer 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:

params	Parameters that the model is estimated from (input data).
param_c	Number of elements in the params array.
support_limit	The search is stopped if a model receives more support that this limit.
max_rounds	How many different samples are tried before stopping the search.
model	The 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:

params	Parameters that the model is estimated from.
param_c	Number of parameters.
support_limit	The search is stopped is a model receives more support that this limit.
max_rounds	How many iterations of the refinement are run.
model	The estimated model that is refined.
inlier_mask	Byte 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:

Ransac.h

Public Member Functions

Protected Member Functions

Detailed Description

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

Constructor & Destructor Documentation

Member Function Documentation

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