cause the above heuristic to fail (for example, see Figure
1). It is our contention that averaging is not an appro-
priate technique to apply to an unverified data set.
In the following section we introduce the RANSAC
paradigm, which is capable of smoothing data that con-
tain a significant percentage of gross errors. This para-
digm is particularly applicable to scene analysis because
local feature detectors, which often make mistakes, are
the source of the data provided to the interpretation
algorithms. Local feature detectors make two types of
errors--classification errors and measurement errors.
Classification errors occur when a feature detector in-
correctly identifies a portion of an image as an occur-
rence of a feature. Measurement errors occur when the
feature detector correctly identifies the feature, but
slightly miscalculates one of its parameters (e.g., its image
location). Measurement errors generally follow a normal
distribution, and therefore the smoothing assumption is
applicable to them. Classification errors, however, are
gross errors, having a significantly larger effect than
measurement errors, and do not average out.
In the final sections of this paper the application of
RANSAC tO the location determination problem is dis-
cussed:
Given a set of "landmarks" ("control points"), whose locations are
known in some coordinate frame, determine the location (relative to
the coordinate frame of the landmarks) of that point in space from
which an image of the landmarks was obtained.
In response to a RANSAC requirement, some new
results are derived on the minimum number of land-
marks needed to obtain a solution, and then algorithms
are presented for computing these minimum-landmark
solutions in closed form. (Conventional techniques are
iterative and require a good initial guess to assure con-
vergence.) These results form the basis for an automatic
system that can solve the LDP under severe viewing and
analysis conditions. In particular, the system performs
properly even if a significant number of landmarks are
incorrectly located due to low visibility, terrain changes,
or image analysis errors. Implementation details and
experimental results are presented to complete our de-
scription of the LDP application.
II. Random Sample Consensus
The RANSAC procedure is opposite to that of conven-
tional smoothing techniques: Rather than using as much
of the data as possible to obtain an initial solution and
then attempting to eliminate the invalid data points,
RANSAC uses as small an initial data set as feasible and
enlarges this set with consistent data when possible. For
example, given the task of fitting an arc of a circle to a
set of two-dimensional points, the RANSAC approach
would be to select a set of three points (since three points
are required to determine a circle), compute the center
and radius of the implied circle, and count the number
of points that are close enough to that circle to suggest
their compatibility with it (i.e., their deviations are small
enough to be measurement errors). If there are enough
compatible points, RANSAC would employ a smoothing
technique such as least squares, to compute an improved
estimate for the parameters of the circle now that a set
of mutually consistent points has been identified.
The RANSAC paradigm is more formally stated as
follows:
Given a model that requires a minimum of n data points to instantiate
its free parameters, and a set of data points P such that the number of
points in P is greater than n [g(P) __- n], randomly select a subset SI of
n data points from P and instantiate the model. Use the instantiated
model M1 to determine the subset SI* of points in P that are within
some error tolerance of Ml. The set SI* is called the consensus set of
S1.
If g (SI*) is greater than some threshold t, which is a function of the
estimate of the number of gross errors in P, use SI* to compute
(possibly using least squares) a new model MI *.
If g (SI*) is less than t, randomly select a new subset $2 and repeat the
above process. If, after some predetermined number of trials, no
consensus set with t or more members has been found, either solve the
model with the largest consensus set found, or terminate in failure.
There are two obvious improvements to the above
algorithm: First, if there is a problem related rationale
for selecting points to form the S's, use a deterministic
selection process instead of a random one; second, once
a suitable consensus set S* has been found and a model
M* instantiated, add any new points from P that are
consistent with M* to S* and compute a new model on
the basis of this larger set.
The RANSAC paradigm contains three unspecified
parameters: (1) the error tolerance used to determine
whether or not a point is compatible with a model, (2)
the number of subsets to try, and (3) the threshold t,
which is the number of compatible points used to imply
that the correct model has been found. Methods are
discussed for computing reasonable values for these pa-
rameters in the following subsections.
A. Error Tolerance For Establishing Datum/Model
Compatibility
The deviation of a datum from a model is a function
of the error associated with the datum and the error
associated with the model (which, in part, is a function
of the errors associated with the data used to instantiate
the model). If the model is a simple function of the data
points, it may be practical to establish reasonable bounds
on error tolerance analytically. However, this straight-
forward approach is often unworkable; for such cases it
is generally possible to estimate bounds on error toler-
ance experimentally. Sample deviations can be produced
by perturbing the data, computing the model, and mea-
suring the implied errors. The error tolerance could then
be set at one or two standard deviations beyond the
measured average error.
The expected deviation of a datum from an assumed
model is generally a function of the datum, and therefore
the error tolerance should be different for each datum.
However, the variation in error tolerances is usually
383
Communications June
1981
of Volume 24
the ACM Number 6