IEEE Robotics & Automation Magazine - June 2012 - 82

predicted region is then calculated as an error ellipse from the
uncertainty of the motion and that of the 3-D point.
Alternatively, if only the motion model is known but
not the 3-D feature position, the corresponding match can
be searched along the epipolar line in the second image.
This process is called epipolar matching. As can be
observed in Figure 5, a single 2-D feature and the two
camera centers define a plane in the 3-D space that intersect both images into two lines, called epipolar lines. An
epipolar line can be computed directly from a 2-D feature
and the relative motion of the camera, as explained in
Part I of this tutorial. Each feature in the first image has a
different epipolar line in the second image.
In stereovision, instead of computing the epipolar line
for each candidate feature, the images are usually rectified.
Image rectification is a remapping of an image pair into a
new image pair where epipolar lines of the left and right
images are horizontal and aligned to each other. This has
the advantage of facilitating image-correspondence search
since epipolar lines no longer have to be computed for each
feature: the correspondent of one feature in the left (right)
image can be searched across those features in the right
(left) image, which lie on the same row. Image rectification
can be executed efficiently on graphics processing units
(GPUs). In stereovision, the relative position between the
two cameras is known precisely. However, if the motion is
affected by uncertainty, the epipolar search is usually
expanded to a rectangular area within a certain distance
from the epipolar line. In stereovision, SSD, NCC, and
Census transform are the widely used similarity metrics
for epipolar matching [91].
Feature Tracking
An alternative to independently finding features in all candidate images and then matching them is to detect features in
the first image and, then, search for their corresponding
matches in the following images. This detect-then-track
approach is suitable for VO applications where images are
taken at nearby locations, where the amount of motion and
appearance deformation between adjacent frames is small.
For this particular application, SSD and NCC can work well.
However, if features are tracked over long image
sequences, their appearance can undergo larger changes.
X
~
p

Epipolar Plane
p
Epipolar Epipolar
Line
Line
Ck

Ck - 1
Tk, k - 1
Figure 5. Illustration of the epipolar constraint.

IEEE ROBOTICS & AUTOMATION MAGAZINE

JUNE 2012

In this case, a solution is to apply an affine-distortion
model to each feature. The resulting tracker is often called
KanadeLucasTomasi (KLT) tracker [12].
Discussion
SIFT Matching
For SIFT feature matching, a distance-ratio test was proposed by the authors initially, for use in place and object
detection [14]. This distance-ratio test accepts the closest
match (the one with minimum Euclidean distance) only if
the ratio between the closest and the second closest match is
smaller than a user-specified threshold. The idea behind this
test is to remove matches that might be ambiguous, e.g., due
to repetitive structure. The threshold for the test can only be
set heuristically and an unlucky guess might remove correct
matches as well. Therefore, in many cases, it might be beneficial to skip the ratio test and let RANSAC take care of the
outliers as explained in the "Outlier Removal" section.
Lines and Edgelets
An alternative to point features for VO is to use lines or
edgelets, as proposed in [27] and [28]. They can be used in
addition to points in structured environments and may
provide additional cues, such as direction (of the line or
edgelet), and planarity and orthogonality constraints. Contrary to points, lines are more difficult to match because
lines are more likely to be occluded than points. Furthermore, the origin and end of a line segment of edgelet may
not exist (e.g., occlusions and horizon line).
Number of Features and Distribution
The distribution of the features in the image has been found
to affect the VO results remarkably [1], [9], [29]. In particular, more features provide more stable motion-estimation
results than with fewer features, but at the same time, the
keypoints should cover the image as evenly as possible. To
do this, the image can be partitioned into a grid, and the feature detector is applied to each cell by tuning the detection
thresholds until a minimum number of features are found
in each subimage [1]. As a rule of the thumb, 1,000 features
is a good number for a 640 3 480-pixel image.
Dense and Correspondence-Free Methods
An alternative to sparse-feature extraction is to use dense
methods, such as optical flow [30], or feature-less methods
[31]. Optical flow aims at tracking, ideally, each individual
pixel or a subset of the whole image (e.g., all pixels on a
grid specified by the user). However, similar to feature
tracking, it assumes small motion between frames and,
therefore, is not suitable for VO applications since motion
error accumulates quickly. Another alternative is featureless motion-estimation methods, such as [31]: all the pixels
in the two images are used to compute the relative motion
using a harmonic Fourier transform. This method has the
advantage to work especially with low-texture images but

http://www.lines.An

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