This class implements the Random Sample Consensus (RanSac) framework, a framework for robust parameter estimation. More...

#include <ransac.h>

Classes
class	SubSetIndexComparator

Static Public Member Functions
template<class Estimator , class S , class T >
static std::vector< const T * >	compute (S &parameters, std::vector< int > &inliers, const Estimator &paramEstimator, const std::vector< T > &data, double desiredProbabilityForNoOutliers, double maximalOutlierPercentage)
	Estimate the model parameters using the RanSac framework. More...

template<class Estimator , class S , class T >
static std::vector< const T * >	compute (S &parameters, const Estimator &paramEstimator, const std::vector< T > &data)
	Estimate the model parameters using the maximal consensus set by going over ALL possible subsets (brute force approach). More...

Static Private Member Functions
static unsigned int	choose (unsigned int n, unsigned int m)
	Compute n choose m [ n!/(m!*(n-m)!)]. More...

template<class Estimator , class T >
static void	computeAllChoices (const Estimator &paramEstimator, const std::vector< T > &data, int numForEstimate, short bestVotes, short curVotes, int &numVotesForBest, int startIndex, int n, int k, int arrIndex, int *arr)

template<class Estimator , class T , class S >
static void	estimate (const Estimator &paramEstimator, const std::vector< T > &data, int numForEstimate, short bestVotes, short curVotes, int &numVotesForBest, int *arr)

Detailed Description

This class implements the Random Sample Consensus (RanSac) framework, a framework for robust parameter estimation.

Given data containing outliers we estimate the model parameters using sub-sets of the original data:

Choose the minimal subset from the data for computing the exact model parameters.
See how much of the input data agrees with the computed parameters.
Goto step 1. This can be done up to (m choose N) times, where m is the number of data objects required for an exact estimate and N is the total number of data objects.
Take the largest subset of objects which agreed on the parameters and compute a least squares fit using them.

This is based on: Fischler M.A., Bolles R.C., ``Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography'', Communications of the ACM, Vol. 24(6), 1981.

Hartely R., Zisserman A., "Multiple View Geometry in Computer Vision"

The class template parameters are T - objects used for the parameter estimation (e.g. Point2D in line estimation, std::pair<Point2D,Point2D> in homography estimation). S - type of parameters (e.g. std::vector<double>).

Author: Ziv Yaniv

Small modifications by Pablo d'Angelo:

allow arbitrary parameters, not just vector<S>

Definition at line 75 of file ransac.h.

Member Function Documentation

unsigned int Ransac::choose	(	unsigned int	n,
		unsigned int	m
	)

inlinestaticprivate

Compute n choose m [ n!/(m!*(n-m)!)].

Definition at line 420 of file ransac.h.

Referenced by compute().

template<class Estimator , class S , class T >

std::vector< const T * > Ransac::compute	(	S &	parameters,
		std::vector< int > &	inliers,
		const Estimator &	paramEstimator,
		const std::vector< T > &	data,
		double	desiredProbabilityForNoOutliers,
		double	maximalOutlierPercentage
	)

static

Estimate the model parameters using the RanSac framework.

Parameters

parameters	A vector which will contain the estimated parameters. If there is an error in the input then this vector will be empty. Errors are: 1. Less data objects than required for an exact fit. The given data is in a singular configuration (e.g. trying to fit a circle to a set of colinear points).
paramEstimator	An object which can estimate the desired parameters using either an exact fit or a least squares fit.
data	The input from which the parameters will be estimated.
numForEstimate	The number of data objects required for an exact fit.
desiredProbabilityForNoOutliers	The probability that at least one of the selected subsets doesn't contains an outlier.
maximalOutlierPercentage	The maximal expected percentage of outliers.

Returns: Array with inliers

Definition at line 175 of file ransac.h.

References choose(), vigra_ext::log(), and vigra_ext::pow().

Referenced by HuginBase::RANSACOptimizer::findInliers().

template<class Estimator , class S , class T >

std::vector< const T * > Ransac::compute	(	S &	parameters,
		const Estimator &	paramEstimator,
		const std::vector< T > &	data
	)

static

Estimate the model parameters using the maximal consensus set by going over ALL possible subsets (brute force approach).

Given: n - data.size() k - numForEstimate

We go over all n choose k subsets n!

(n-k)! * k!

Parameters

parameters	A vector which will contain the estimated parameters. If there is an error in the input then this vector will be empty. Errors are: 1. Less data objects than required for an exact fit. The given data is in a singular configuration (e.g. trying to fit a circle to a set of colinear points).
paramEstimator	An object which can estimate the desired parameters using either an exact fit or a least squares fit.
data	The input from which the parameters will be estimated.
numForEstimate	The number of data objects required for an exact fit.

Returns: Array with inliers

NOTE: This method should be used only when n choose k is small (i.e. k or (n-k) are approximatly equal to n)

Definition at line 327 of file ransac.h.

References computeAllChoices().

template<class Estimator , class T >

void Ransac::computeAllChoices	(	const Estimator &	paramEstimator,
		const std::vector< T > &	data,
		int	numForEstimate,
		short *	bestVotes,
		short *	curVotes,
		int &	numVotesForBest,
		int	startIndex,
		int	n,
		int	k,
		int	arrIndex,
		int *	arr
	)

staticprivate

Definition at line 365 of file ransac.h.

References estimate().

Referenced by compute().

template<class Estimator , class T , class S >

void Ransac::estimate	(	const Estimator &	paramEstimator,
		const std::vector< T > &	data,
		int	numForEstimate,
		short *	bestVotes,
		short *	curVotes,
		int &	numVotesForBest,
		int *	arr
	)

staticprivate

Definition at line 387 of file ransac.h.

Referenced by computeAllChoices().

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

hugin_base/vigra_ext/ransac.h

Classes

Static Public Member Functions

Static Private Member Functions

Detailed Description

Member Function Documentation

We go over all n choose k subsets n!