org.openimaj.math.model.fit

Class RANSAC<I,D,M extends EstimatableModel<I,D>>

java.lang.Object

org.openimaj.math.model.fit.RANSAC<I,D,M>

Type Parameters:

I - type of independent data

D - type of dependent data

M - concrete type of model learned

All Implemented Interfaces:

ModelFitting<I,D,M>, RobustModelFitting<I,D,M>

public class RANSAC<I,D,M extends EstimatableModel<I,D>>
extends Object
implements RobustModelFitting<I,D,M>

The RANSAC Algorithm (RANdom SAmple Consensus)

For fitting noisy data consisting of inliers and outliers to a model.

Assume: M data items required to estimate parameter x N data items in total

1.) select M data items at random

2.) estimate parameter x

3.) find how many of the N data items fit (i.e. have an error less than a threshold or pass some check) x within tolerence tol, call this K

4.) if K is large enough (bigger than numItems) accept x and exit with success

5.) repeat 1..4 nIter times

6.) fail - no good x fit of data

In this implementation, the conditions that control the iterations are configurable. In addition, the best matching model is always stored, even if the fitData() method returns false.

Author:

Jonathon Hare (jsh2@ecs.soton.ac.uk)

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	RANSAC.BestFitStoppingCondition Stopping condition that allows the RANSAC algorithm to run until all the iterations have been exhausted.
static class	RANSAC.NumberInliersStoppingCondition Stopping condition that tests the number of matches against a threshold.
static class	RANSAC.PercentageInliersStoppingCondition Stopping condition that tests the number of matches against a percentage threshold of the whole data.
static class	RANSAC.ProbabilisticMinInliersStoppingCondition Stopping condition that tests the number of matches against a percentage threshold of the whole data.
static interface	RANSAC.StoppingCondition Interface for classes that can control RANSAC iterations

Field Summary

Fields

Modifier and Type	Field and Description
protected List<IndependentPair<I,D>>	bestModelInliers
protected List<IndependentPair<I,D>>	bestModelOutliers
protected DistanceCheck	dc
protected ResidualCalculator<I,D,M>	errorModel
protected boolean	improveEstimate
protected List<IndependentPair<I,D>>	inliers
protected M	model
protected List<? extends IndependentPair<I,D>>	modelConstructionData
protected int	nIter
protected List<IndependentPair<I,D>>	outliers
protected CollectionSampler<IndependentPair<I,D>>	sampler
protected RANSAC.StoppingCondition	stoppingCondition

Constructor Summary

Constructors

Constructor and Description
RANSAC(M model, ResidualCalculator<I,D,M> errorModel, DistanceCheck dc, int nIterations, RANSAC.StoppingCondition stoppingCondition, boolean impEst) Create a RANSAC object with uniform random sampling for creating the subsets
RANSAC(M model, ResidualCalculator<I,D,M> errorModel, DistanceCheck dc, int nIterations, RANSAC.StoppingCondition stoppingCondition, boolean impEst, CollectionSampler<IndependentPair<I,D>> sampler) Create a RANSAC object
RANSAC(M model, ResidualCalculator<I,D,M> errorModel, double errorThreshold, int nIterations, RANSAC.StoppingCondition stoppingCondition, boolean impEst) Create a RANSAC object with uniform random sampling for creating the subsets
RANSAC(M model, ResidualCalculator<I,D,M> errorModel, double errorThreshold, int nIterations, RANSAC.StoppingCondition stoppingCondition, boolean impEst, CollectionSampler<IndependentPair<I,D>> sampler) Create a RANSAC object

Method Summary

Modifier and Type	Method and Description
boolean	fitData(List<? extends IndependentPair<I,D>> data) Attempt to fit the given data to the model.
List<? extends IndependentPair<I,D>>	getInliers()
int	getMaxIterations()
M	getModel()
List<? extends IndependentPair<I,D>>	getModelConstructionData()
List<? extends IndependentPair<I,D>>	getOutliers()
boolean	isImproveEstimate()
int	numItemsToEstimate()
void	setImproveEstimate(boolean improveEstimate) Set whether RANSAC should attempt to improve the model using all inliers as data
void	setMaxIterations(int nIter) Set the maximum number of allowed iterations
void	setModel(M model) Set the underlying model being fitted
void	setModelConstructionData(List<? extends IndependentPair<I,D>> modelConstructionData) Set the data used to construct the model

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

model

protected M extends EstimatableModel<I,D> model

errorModel

protected ResidualCalculator<I,D,M extends EstimatableModel<I,D>> errorModel

dc

protected DistanceCheck dc

nIter

protected int nIter

improveEstimate

protected boolean improveEstimate

inliers

protected List<IndependentPair<I,D>> inliers

outliers

protected List<IndependentPair<I,D>> outliers

bestModelInliers

protected List<IndependentPair<I,D>> bestModelInliers

bestModelOutliers

protected List<IndependentPair<I,D>> bestModelOutliers

stoppingCondition

protected RANSAC.StoppingCondition stoppingCondition

modelConstructionData

protected List<? extends IndependentPair<I,D>> modelConstructionData

sampler

protected CollectionSampler<IndependentPair<I,D>> sampler

Constructor Detail

RANSAC

public RANSAC(M model,
              ResidualCalculator<I,D,M> errorModel,
              double errorThreshold,
              int nIterations,
              RANSAC.StoppingCondition stoppingCondition,
              boolean impEst)

Create a RANSAC object with uniform random sampling for creating the subsets

Parameters:

model - Model object with which to fit data

errorModel - object to compute the error of the model

errorThreshold - the threshold below which error is deemed acceptable for a fit

nIterations - Maximum number of allowed iterations (L)

stoppingCondition - the stopping condition

impEst - True if we want to perform a final fitting of the model with all inliers, false otherwise

RANSAC

public RANSAC(M model,
              ResidualCalculator<I,D,M> errorModel,
              DistanceCheck dc,
              int nIterations,
              RANSAC.StoppingCondition stoppingCondition,
              boolean impEst)

Create a RANSAC object with uniform random sampling for creating the subsets

Parameters:

model - Model object with which to fit data

errorModel - object to compute the error of the model

dc - the distance check that tests whether a point with given error from the error model should be considered an inlier

nIterations - Maximum number of allowed iterations (L)

stoppingCondition - the stopping condition

impEst - True if we want to perform a final fitting of the model with all inliers, false otherwise

RANSAC

public RANSAC(M model,
              ResidualCalculator<I,D,M> errorModel,
              double errorThreshold,
              int nIterations,
              RANSAC.StoppingCondition stoppingCondition,
              boolean impEst,
              CollectionSampler<IndependentPair<I,D>> sampler)

Create a RANSAC object

Parameters:

model - Model object with which to fit data

errorModel - object to compute the error of the model

errorThreshold - the threshold below which error is deemed acceptable for a fit

nIterations - Maximum number of allowed iterations (L)

stoppingCondition - the stopping condition

impEst - True if we want to perform a final fitting of the model with all inliers, false otherwise

sampler - the sampling algorithm for selecting random subsets

RANSAC

public RANSAC(M model,
              ResidualCalculator<I,D,M> errorModel,
              DistanceCheck dc,
              int nIterations,
              RANSAC.StoppingCondition stoppingCondition,
              boolean impEst,
              CollectionSampler<IndependentPair<I,D>> sampler)

Create a RANSAC object

Parameters:

model - Model object with which to fit data

errorModel - object to compute the error of the model

dc - the distance check that tests whether a point with given error from the error model should be considered an inlier

nIterations - Maximum number of allowed iterations (L)

stoppingCondition - the stopping condition

impEst - True if we want to perform a final fitting of the model with all inliers, false otherwise

sampler - the sampling algorithm for selecting random subsets

Method Detail

fitData

public boolean fitData(List<? extends IndependentPair<I,D>> data)

Description copied from interface: ModelFitting

Attempt to fit the given data to the model.

Specified by:

fitData in interface ModelFitting<I,D,M extends EstimatableModel<I,D>>

Parameters:

data - Data to be fitted

Returns:

true on success, false otherwise

getInliers

public List<? extends IndependentPair<I,D>> getInliers()

Specified by:

getInliers in interface RobustModelFitting<I,D,M extends EstimatableModel<I,D>>

Returns:

list of the inliers in the original data

getOutliers

public List<? extends IndependentPair<I,D>> getOutliers()

Specified by:

getOutliers in interface RobustModelFitting<I,D,M extends EstimatableModel<I,D>>

Returns:

list of the outliers in the original data

getMaxIterations

public int getMaxIterations()

Returns:

maximum number of allowed iterations

setMaxIterations

public void setMaxIterations(int nIter)

Set the maximum number of allowed iterations

Parameters:

nIter - maximum number of allowed iterations

getModel

public M getModel()

Specified by:

getModel in interface ModelFitting<I,D,M extends EstimatableModel<I,D>>

Returns:

the trained model object

setModel

public void setModel(M model)

Set the underlying model being fitted

Parameters:

model - the model

isImproveEstimate

public boolean isImproveEstimate()

Returns:

whether RANSAC should attempt to improve the model using all inliers as data

setImproveEstimate

public void setImproveEstimate(boolean improveEstimate)

Set whether RANSAC should attempt to improve the model using all inliers as data

Parameters:

improveEstimate - should RANSAC attempt to improve the model using all inliers as data

setModelConstructionData

public void setModelConstructionData(List<? extends IndependentPair<I,D>> modelConstructionData)

Set the data used to construct the model

Parameters:

modelConstructionData -

getModelConstructionData

public List<? extends IndependentPair<I,D>> getModelConstructionData()

Returns:

The data used to construct the model.

numItemsToEstimate

public int numItemsToEstimate()

Specified by:

numItemsToEstimate in interface ModelFitting<I,D,M extends EstimatableModel<I,D>>

Returns:

The minimum number of observations required to estimate the model.