template RANSAC class: RANSAC (RANdom SAmple Consensus) More...

Detailed Description

template<class ModelType>
class jafar::model3d::RANSAC< ModelType >

template RANSAC class: RANSAC (RANdom SAmple Consensus)

Definitions:

ModelType: Type of the searched model
Sample : a set of a few data points selected (randomly) from Data
DataLength : the number of available data points : We assume that the data in stored in std::vector<...>
SampleLength : the minimum number of data points required to define a model

This is an abstract class, so you MUST derive a class from it in which you overload these functions:

fitSampleModel(...)=0 : an abstract function
evaluateModel(...)
distance(...)=0
isDegenerate(...) can be overloaded if for instance a test of non degenerated sample can be added.(example: a three colinear points don't define a plane : this sample is degenerated).

Overload the folowing is optional:

generateSample(...) can be overloaded to change the methode of selecting samples: the default is using the function generateRandomSample() which use the template RandomIntTmplt see the implementation of generateRandomSample() for more infos.

Note:: the function 'Algorithm' is the core of this class

Refrence: M.A. Fischler and R.C. Bolles. Random sample consensus: A paradigm for model fitting with application to image analysis and automated cartography. Communications of the ACM, 24(6):381-395, 1981.

Author:: ayman.zureiki@laas.fr

Definition at line 60 of file ransac.hpp.

#include <ransac.hpp>

List of all members.

Public Member Functions
	RANSAC ()
	Default Constructor : you MUST call initialize before using the instance.
	RANSAC (unsigned int sample_length)
	Construct a RANSAC object that takes samples of size sample_length, returning at most max_models_per_sample models each time.
void	initialize (unsigned int sample_length)
	initialize the RANSAC instance with the given value
int	Algorithm (double inlying_data_fraction, ModelType &model, std::vector< bool > &inliers, unsigned int &nModelInlierNumber, double &dbModelScore)
	RANSAC Algorithm core, to be called by user.
virtual void	fitSampleModel (std::vector< unsigned int > &sample_data_indices, ModelType &model)=0
	Fit the model(s) for the given sample.
virtual bool	evaluateModel (const ModelType &model, std::vector< bool > &inlier, unsigned int &unInlierNumber, double &evaluate_score)
	Evaluate the goodness of a model.
virtual double	distance (const ModelType &model, unsigned int unIndex)=0
	Calculate the distance between the model and a data point.
virtual bool	isDegenerate (std::vector< unsigned int > &sample_data_indices)
	determine wether the selected sample can define a model or not
virtual bool	generateSample (std::vector< unsigned int > &sample_data_indices)
	pick a set of samples
bool	generateRandomSample (std::vector< unsigned int > &sampletable)
	Generate Sample Randomly.
void	setMaxIterationNumber (unsigned int unMaxIterationNumber)
	Set max number of Iterations.
void	fixIterationNumber (unsigned int uiIterationNumber)
	Fix the number of iterations.
void	setInlierNumberThreshold (unsigned int unInlierNumberThreshold)
	Set the Threshold of Inlier Number.
unsigned int	getInlierNumberThreshold ()
	Get the Threshold of Inlier Number.
void	setInlierDistanceThreshold (double dbInlierDistanceThreshold)
	Set the threshold of distance between a data point and the model to be an inlier.
double	getInlierDistanceThreshold ()
	Get the threshold of distance between a data point and the model to be an inlier.
void	setModelErrorThreshold (double dbModelErrorThreshold)
	Set the model error threshold.
double	getModelErrorThreshold ()
	Get the model error threshold.
Protected Attributes
unsigned int	m_unDataLength
	number of availables data elements == the size of _Data
unsigned int	m_unSampleLength
	The minimum number of data points in one sample required by fitSampleModel to fit a model.
jafar::jmath::RandomUIntVect *	m_pRandomUIntVect
unsigned int	m_unMaxIterationNumber
	Maximum Number of Iteration.
unsigned int	m_unFixedIterationNumber
	Fixed Iteration Number given by the user.
double	m_dbProbabilityOfGoodModel
	Probability of finding a good Model.
double	m_dbInlierDistanceThreshold
	Threshold of distance between a data point and a model to be an inlier.
unsigned int	m_unInlierNumberThreshold
	The minumum number of Inliers needed to define a good model.
double	m_dbModelErrorThreshold
	if the Model error is bigger than this error, it is not accepted
Static Private Member Functions
static int	ComputeIterationNumber (double inlying_data_fraction, double desired_prob_good, unsigned int sample_length)

Constructor & Destructor Documentation

template<class ModelType >

jafar::model3d::RANSAC< ModelType >::RANSAC ( )

Default Constructor : you MUST call initialize before using the instance.

default constructor is given to facilitate intanciating from this class but you must call initialize before using the instance, especially to provide the sample_length: the minimum number of data needed to define a model

Definition at line 336 of file ransac.hpp.

Member Function Documentation

template<class ModelType>

int jafar::model3d::RANSAC< ModelType >::Algorithm	(	double	inlying_data_fraction,
		ModelType &	model,
		std::vector< bool > &	inliers,
		unsigned int &	nModelInlierNumber,
		double &	dbModelScore
	)

RANSAC Algorithm core, to be called by user.

This function is the core of RANSAC algorithm and will be called by user to do the computation. On output, model is set to the best model found and inliers indicate which data were inliers to that model. The inlying_data_fraction is responsible for the maximal number of iterations taken from the data. The smaller the inlying_data_fraction, the more iterations are taken

Attention:: You have NOT to override this function in derived classes, unless you want to do modifications in the RANSAC _algorithm_ itself (to optimize it or to add some other test as the Testt(d,d), but usually you dont want to do this.) input : inlying_data_fraction expected inlier fraction output: model model inliers inlier flags

Returns:: -1: indicates an error: Object hasn't been initialized; -2: No model was found (failed); : otherwise number of iterations

The criteria for deciding the best model : 1. if the unInlierNumber is higher than the previous best, take it, 2. if the unInlierNumber is equal to the previous best, and the evaluate score is smaller than the previous best, take it.

Definition at line 379 of file ransac.hpp.

References JFR_PRECOND, and JFR_RUN_TIME.

template<class ModelType>

virtual double jafar::model3d::RANSAC< ModelType >::distance	(	const ModelType &	model,
		unsigned int	unIndex
	)		`[pure virtual]`

Calculate the distance between the model and a data point.

Ths function MUST be overloaded to fit to a distance between a model and a data point

Implemented in jafar::model3d::RansacLine2D, and jafar::model3d::RansacPlane.

template<class ModelType>

bool jafar::model3d::RANSAC< ModelType >::evaluateModel	(	const ModelType &	model,
		std::vector< bool > &	inlier,
		unsigned int &	unInlierNumber,
		double &	evaluate_score
	)		`[virtual]`

Evaluate the goodness of a model.

For the specified model, set

an inlierNumber indicating the number of data which are inliers to the given model,
the inlier flag for each datum to true if the datum is inlying
an evaluate score (typically the average residual) indicating the goodness of fit of the inliers - the Algorithm code requires a positive number where zero is a perfect model, larger positive scores mean a worse model.

If existing_model_flag is true, then the best inlier number so far is in unInlierNumber. The function can terminate early if it is not going to beat this.

Parameters:

model	(in) model to be evaluated
existing_model_flag	(in) if true the best accept_cout so far is given in unInlierNumber
unInlierNumber	(in/out) input: best accept_cout so far if existing_model_flag==true, output: number of inliers to the current model
inlier	(out) inlier[i] ==> datum i is inlying
evaluate_score	(out) a score for the model, 0 means ideal model, larger score means worse model

we have a good model if the inlier number is greater than the inlier number threshold and the model score is smaller than the model error threshold

Definition at line 515 of file ransac.hpp.

template<class ModelType>

virtual void jafar::model3d::RANSAC< ModelType >::fitSampleModel	(	std::vector< unsigned int > &	sample_data_indices,
		ModelType &	model
	)		`[pure virtual]`

Fit the model(s) for the given sample.

Returns:: the number of models found.

The sample_data_indices array will be of length sample_length, selecting the indices to be fit to from the subclass's data array.

Implemented in jafar::model3d::RansacLine2D, and jafar::model3d::RansacPlane.

template<class ModelType>

void jafar::model3d::RANSAC< ModelType >::fixIterationNumber ( unsigned int uiIterationNumber ) [inline]

Fix the number of iterations.

Explicitly fix the number of iterations to be done inside the 'Algorithm'. The value returned by ComputeIterationNumber() is ignored if this function is called with a strictly positive value uiIterationNumber. The 'Algorithm' will performs at most min(m_unMaxIterationNumber, uiIterationNumber) iterations. Can be used if one wants to temporary decrement the number of iterations to see if there is a significant changes in the model (of course there will be a gain in time)

Note:: To 'Unfix' the iteration Number you can call this function with the value 0.

Definition at line 233 of file ransac.hpp.

template<class ModelType >

bool jafar::model3d::RANSAC< ModelType >::generateRandomSample ( std::vector< unsigned int > & sampletable )

Generate Sample Randomly.

use a random selection of data point index to form a sample this function use the calss IntRandom class.

Parameters:

nIterationIndex is used only as a method to change the seed of the random class (see IntRandom class for more details)

Definition at line 564 of file ransac.hpp.

References JFR_PRECOND.

template<class ModelType >

bool jafar::model3d::RANSAC< ModelType >::generateSample ( std::vector< unsigned int > & sample_data_indices ) [virtual]

pick a set of samples

Override this to change the technique used to generate samples. By default, random sampling is assumed but implementations may wish to use other problem-specific sampling strategy.

Definition at line 557 of file ransac.hpp.

template<class ModelType >

void jafar::model3d::RANSAC< ModelType >::initialize ( unsigned int sample_length )

initialize the RANSAC instance with the given value

Needed especially when using default constructor -sample_length: the minimum number of data point needed to define a model

Definition at line 358 of file ransac.hpp.

template<class ModelType>

virtual bool jafar::model3d::RANSAC< ModelType >::isDegenerate ( std::vector< unsigned int > & sample_data_indices ) [inline, virtual]

determine wether the selected sample can define a model or not

The default implementation return false always. If implemented, this function should determine wether the selected sample can define a model or not

Returns:: true if the sample can't define a model otherwize false.

Author:: Ayman

Reimplemented in jafar::model3d::RansacLine2D, and jafar::model3d::RansacPlane.

Definition at line 186 of file ransac.hpp.

template<class ModelType>

void jafar::model3d::RANSAC< ModelType >::setMaxIterationNumber ( unsigned int unMaxIterationNumber ) [inline]

Set max number of Iterations.

Algorithm will stop after unMaxIterationNumber iterations, regardless of model quality. Then there is no garantee to find a model even if it exists, but it is necessary to avoid very long loops

Definition at line 216 of file ransac.hpp.

Member Data Documentation

template<class ModelType>

double jafar::model3d::RANSAC< ModelType >::m_dbInlierDistanceThreshold [protected]

Threshold of distance between a data point and a model to be an inlier.

if the distance (defined by the virtual function distance) between the model and the data point is less than this threshold, it is an Inlier, otherwise it is an Outlier.

Definition at line 307 of file ransac.hpp.

Referenced by jafar::model3d::RANSAC< Line2D >::getInlierDistanceThreshold(), and jafar::model3d::RANSAC< Line2D >::setInlierDistanceThreshold().

template<class ModelType>

double jafar::model3d::RANSAC< ModelType >::m_dbProbabilityOfGoodModel [protected]

Probability of finding a good Model.

This member will be used in ComputeIterationNumber to calculate the minimum number of iterations needed to have a solution with the probabily m_dbProbabilityOfGoodModel can be set close to 1 (of course between 0 and 1)

Definition at line 298 of file ransac.hpp.

template<class ModelType>

unsigned int jafar::model3d::RANSAC< ModelType >::m_unFixedIterationNumber [protected]

Fixed Iteration Number given by the user.

use this if you want to control yourself the number of iterations if it is given (!= 0) then the number of iterations will be min(m_unMaxIterationNumber, m_unFixedIterationNumber) and the function ComputeIterationNumber will not be used

Definition at line 289 of file ransac.hpp.

Referenced by jafar::model3d::RANSAC< Line2D >::fixIterationNumber().

template<class ModelType>

unsigned int jafar::model3d::RANSAC< ModelType >::m_unInlierNumberThreshold [protected]

The minumum number of Inliers needed to define a good model.

This member define the minimum number of inliers needed to define a good model. this must be defined by user depending on the model and a 'long experience'.

Definition at line 315 of file ransac.hpp.

Referenced by jafar::model3d::RANSAC< Line2D >::getInlierNumberThreshold(), and jafar::model3d::RANSAC< Line2D >::setInlierNumberThreshold().

template<class ModelType>

unsigned int jafar::model3d::RANSAC< ModelType >::m_unMaxIterationNumber [protected]

Maximum Number of Iteration.

this is the maximum number of iteration can be done inside the Algorithm function

Definition at line 280 of file ransac.hpp.

Referenced by jafar::model3d::RANSAC< Line2D >::setMaxIterationNumber().

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