IEEE Robotics & Automation Magazine - June 2012 - 83

is computationally extremely expensive (can take up to
several minutes), and the recovered motion is less accurate
than with feature-based methods.
Outlier Removal
Matched points are usually contaminated by outliers, that is,
wrong data associations. Possible causes of outliers are
image noise, occlusions, blur, and changes in viewpoint and
illumination for which the mathematical model of the feature detector or descriptor does not account for. For
instance, most of the feature-matching techniques assume
linear illumination changes, pure camera rotation and scaling (zoom), or affine distortion. However, these are just
mathematical models that approximate the more complex
reality (image saturation, perspective distortion, and motion
blur). For the camera motion to be estimated accurately, it is
important that outliers be removed. Outlier rejection is the
most delicate task in VO. An example VO result before and
after removing the outliers is shown in Figure 6.
RANSAC
The solution to outlier removal consists in taking advantage
of the geometric constraints introduced by the motion model.
Robust estimation methods, such as M-estimation [32], case
deletion, and explicitly fitting and removing outliers [33], can
be used but these often work only if there are relatively few
outliers. RANSAC [34] has been established as the standard
method for model estimation in the presence of outliers.
The idea behind RANSAC is to compute model
hypotheses from randomly sampled sets of data points and
then verify these hypotheses on the other data points. The
hypothesis that shows the highest consensus with the other
data is selected as a solution. For two-view motion estimation as used in VO, the estimated model is the relative
motion (R, t ) between the two camera positions, and the
data points are the candidate feature correspondences.

*
Algorithm 1. VO from
2-D-to-2-D correspondences.
1) Initial: let A be a set of N feature correspondences2) Repeat
2.1) Randomly select a sample of s points from A
2.2) Fit a model to these points
2.3) Compute the distance of all other points to this model
2.4) Construct the inlier set (i.e. count the number of points
whose distance from the model < d)
2.5) Store these inliers
2.6) Until maximum number of iterations reached
3) The set with the maximum number of inliers is chosen as a
solution to the problem
4) Estimate the model using all the inliers.

The number of subsets (iterations) N that is necessary
to guarantee that a correct solution is found can be computed by
N¼

log (1 À p)
,
log (1 À (1 À )s )

(1)

where s is the number of data points from which the model
can be instantiated, is the percentage of outliers in the
data points, and P is the requested probability of success
[34]. For the sake of robustness, in many practical implementations, N is usually multiplied by a factor of ten. More
advanced implementations of RANSAC estimate the fraction of inliers adaptively, iteration after iteration.
As observed, RANSAC is a probabilistic method and is
nondeterministic in that it exhibits a different solution on
different runs; however, the solution tends to be stable
when the number of iterations grows.

20
0
y (m)

Inlier points to a hypothesis are found by computing the
point-to-epipolar line distance [35]. The point-to-epipolar
line distance is usually computed as a first-order approximation-called Sampson distance-for efficiency reasons
[35]. An alternative to the point-to-epipolar line distance
is the directional error proposed by Oliensis [36]. The
directional error measures the angle between the ray of the
image feature and the epipolar plane. The authors claim
that the use of the directional error is advantageous for the
case of omnidirectional and wide-angle cameras but also
beneficial for the standard camera case.
The outline of RANSAC is given in Algorithm 1.

-20
-40
-60
-80
0

80 100 120 140
x (m)

Before Removing the Outliers
After Removing the Outliers
Figure 6. Comparison between VO trajectories estimated
before and after removing the outliers. (Photo courtesy of
Google Maps ' 2007 Google, ' 2007 Tele Atlas.)

Minimal Model Parameterizations
As can be observed in Figure 7, N is exponential in the
number of data point s necessary to estimate the model.
Therefore, there is a high interest in using a minimal
parameterization of the model. In Part I of this tutorial, an
eight-point minimal solver for uncalibrated cameras was
described. Although it works also for calibrated cameras,
the eight-point algorithm fails when the scene points are
JUNE 2012

IEEE ROBOTICS & AUTOMATION MAGAZINE

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - June 2012