Main Page | Modules | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages | Examples | Search for 

Ransac Class Reference

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

#include <ransac.h>

List of all members.

Static Public Member Functions

template<class Estimator, class S, class T>
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.
template<class Estimator, class S, class T>
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).

Static Private Member Functions

unsigned int choose (unsigned int n, unsigned int m)
 Compute n choose m [ n!/(m!*(n-m)!)].
template<class Estimator, class T>
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>
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: 1. Choose the minimal subset from the data for computing the exact model parameters. 2. See how much of the input data agrees with the computed parameters. 3. 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. 4. 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
)  [inline, static, private]
 

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

Definition at line 424 of file ransac.h.

Referenced by compute().

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. 2. 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 331 of file ransac.h.

References computeAllChoices().

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. 2. 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(), and vigra_ext::optimizeVignettingQuotient().

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
)  [static, private]
 

Definition at line 369 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
)  [static, private]
 

Definition at line 391 of file ransac.h.

Referenced by computeAllChoices().

The documentation for this class was generated from the following file:
Generated on Wed Jun 19 01:25:53 2013 for Hugintrunk by  doxygen 1.3.9.1