IEEE Robotics & Automation Magazine - June 2012 - 84

coplanar. However, when the camera is calibrated, its six
degrees of freedom (DoF) motion can be inferred from a
minimum of five-point correspondences, and the first
solution to this problem was given in 1913 by Kruppa [37].
Several five-point minimal solvers were proposed later in
[38]-[40], but an efficient implementation, based on [39],
was found only in 2003 by Nister [41] and later revised in
[42]. Before that, the six- [43], seven- [44], or eight- solvers
were commonly used. However, the five-point solver has
the advantage that it works also for planar scenes. (Observe
that eight- and seven-point solvers work for uncalibrated,
perspective cameras. To use them also with omnidirectional cameras, the camera needs to be calibrated. Alternatively, n -point solvers for uncalibrated omnidirectional
cameras have also been proposed [45]-[47], where n
depends on the type of mirror or fish eye used. Lim et al.
[48] showed that, for calibrated omnidirectional cameras,
6 DoF motion can be recovered using only two pairs of
antipodal image points. Antipodal image points are points
whose rays are aligned but which correspond to opposite
viewing directions. They also showed that antipodal points
allow us to independently estimate translation and
rotation.)
Despite the five-point algorithm represents the minimal
solver for 6 DoF motion of calibrated cameras, in the last
few decades, there have been several attempts to exploit
different cues to reduce the number of motion parameters.
In [49], Fraundorfer et al. proposed a three-point minimal
solver for the case of two known camera-orientation

Number of RANSAC Iterations

1,000

Histogram Voting
One-Point
Two-Point
Five-Point

No. of Iterations

800
600
400
200
0

30 40 50 60 70 80
Fraction of Outliers
(No. of Outliers)/(No. of Points) (%)

Figure 7. Number of RANSAC iterations versus fraction of
outliers.

Table 1. Number of RANSAC iterations.

Number of points (s):

Number of iterations (N):

1,177

587

292

145

IEEE ROBOTICS & AUTOMATION MAGAZINE

JUNE 2012

angles. For instance, this can be used when the camera is
rigidly attached to a gravity sensor (in fact, the gravity vector fixes two camera-orientation angles). Later, Naroditsky
et al. [50] improved on that work by showing that the
three-point minimal solver can be used in a four-point
(three-plus-one) RANSAC scheme. The three-plus-one
stands for the fact that an additional far scene point
(ideally, a point at infinity) is used to fix the two orientation angles. Using their four-point RANSAC, they also
show a successful 6 DoF VO. A two-point minimal solver
for 6-DoF VO was proposed by Kneip et al. [51], which
uses the full rotation matrix from an IMU rigidly attached
to the camera.
In the case of planar motion, the motion model complexity is reduced to 3 DoF and can be parameterized with
two points as described in [52]. For wheeled vehicles, Scaramuzza et al. [9], [53] showed that the motion can be
locally described as planar and circular, and, therefore, the
motion model complexity is reduced to 2 DoF, leading to a
one-point minimal solver. Using a single point for motion
estimation is the lowest motion parameterization possible
and results in the most efficient RANSAC algorithm. Additionally, they show that, by using histogram, voting outliers
can be found in a small, single iteration. A performance
evaluation of five-, two-, and one-point RANSAC algorithms for VO was finally presented in [54].
To recap, the reader should remember that, if the
camera motion is unconstrained, the minimum number of
points to estimate the motion is five, and, therefore, the
five-point RANSAC (or the six-, seven-, or eight-point
one) should be used. Of course, using the five-point RANSAC will require less iterations (and thus less time) than
the six-, seven-, or eight-point RANSAC. A summary of
the number of minimum RANSAC iterations as a function
of the number of model parameters s is shown in Table 1
for the eight-, seven-, five-, four-, two-, one-point minimal
solvers. These values were obtained from (1), assuming a
probability of success P ¼ 99% and a percentage of outliers ¼ 50%.
Reducing the Iterations of RANSAC
As can be observed in Table 1, with P ¼ 99% and
¼ 50%, the five-point RANSAC requires a minimum of
145 iterations. However, in reality, the things are not
always so straightforward. Sometimes, the number of outliers is underestimated and using more iterations increases
the chances to find more inliers. In some cases, it can even
be necessary to allow for thousands of iterations. Because
of this, several works have been produced in the endeavor
of increasing the speed of RANSAC.
* The maximum likelihood estimation sample consensus [55] makes
the measurement of correspond2
1
ences more reliable and improves
16
7
the estimate of the hypotheses. The
progressive sample consensus [56]

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