RANSAC
Name
RANSAC
Purpose
RANSAC is an abbreviation for "RANdom SAmple Consensus". It is an
iterative method to estimate parameters of a mathematical model
from a set of observed data which contains outliers. It is a
non-deterministic algorithm in the sense that it produces a
reasonable result only with a certain probability, with this
probability increasing as more iterations are allowed. The
algorithm was first published by Fischler and Bolles in 1981.
A basic assumption is that the data consists of "inliers", i.e.,
data whose distribution can be explained by some set of model
parameters, and "outliers" which are data that do not fit the
model. In addition to this, the data can be subject to noise.
The outliers can come, e.g., from extreme values of the noise
or from erroneous measurements or incorrect hypotheses about the
interpretation of data. RANSAC also assumes that, given a
(usually small) set of inliers, there exists a procedure which
can estimate the parameters of a model that optimally
explains or fits this data (http://en.wikipedia.org/wiki/RANSAC).
Category
Statistics.
Calling Sequence
Result = $
RANSAC( data, $
fittingFunction, $
distanceFunction, $
minimumSamples, $
distanceThreshold )
Inputs
data
Data set for which you are trying to determine a
model. The data set is an array for which the
number of columns corresponds to the number of
dimensions in the data and the number of rows
represents the number of observations [d,npts].
fittingFunction
A string representing the name of the fitting
function to be used for the data. The calling
sequence parameters must be ( data, status ) where
a status of 1 represents a successful fit and a
status of 0 indicates that some error occurred.
distanceFunction
A string representing the name of the distance
function that determines the inlier points in the
data set (data) that fall within a specified
threshold distance (distanceThreshold) of the
model defined by the fit parameters (modelParameters).
This function returns the row indices of the
provided data array that are inliers for the model.
minimumSamples
The minimum number of points that are required to
fit the desired model.
distanceThreshold
The maximum distance a data point may be located
from the determined model to still be considered
an inlier.
Keyword Parameters
MAXIMUM_TRIALS
The maximum number of iteratons (default=1000).
MAXIMUM_ATTEMPTS
The maximum number of attempts that will be made
to fit a non-degenrate model for a particular set
of randomly selected points (default=100).
PROBABILITY_ERROR_FREE_SELECTION
The desired probability of choosing at least one
sample free from outliers (default=0.99)
INLIERS
An optionally returned array containing the row indices
corresponding to the rows of the provided data set
that represent the best set of inliers chosen from the
data set.
VERBOSE
If set, this routine will return diagnostic information.
WIDGETID
If set, this routine will return diagnostic information
to the provided widget element ID using the SET_VALUE
parameter and the WIDGET_CONTROL procedure.
Return Value
Result is an array containing the parameters of the best fit model
determined during the RANSAC process.
Side Effects
None
Requires
RANDOM_SAMPLE
Reference
Fischler, Martin A. and Robert C. Bolles, Random sample consensus:
A paradigm for model fitting with aplications to image analysis
and automated cartography, Transactions of ACM - Graphics and
Image Processing, Volume 24, Number 6, June 1981, pp. 381-395.
Modification History
Written by: Carl Salvaggio
September, 2008 Original code
October, 2008 Modified to work with GUI by adding WIDGET parameter
Disclaimer
This source code is provided "as is" and without warranties as to performance
or merchantability. The author and/or distributors of this source code may
have made statements about this source code. Any such statements do not
constitute warranties and shall not be relied on by the user in deciding
whether to use this source code.
This source code is provided without any express or implied warranties
whatsoever. Because of the diversity of conditions and hardware under which
this source code may be used, no warranty of fitness for a particular purpose
is offered. The user is advised to test the source code thoroughly before
relying on it. The user must assume the entire risk of using the source code.