11-05-2013, 12:17 PM
ORB: an efficient alternative to SIFT or SURF
[attachment=53741]
Abstract
Feature matching is at the base of many computer vision
problems, such as object recognition or structure from
motion. Current methods rely on costly descriptors for detection
and matching. In this paper, we propose a very fast
binary descriptor based on BRIEF, called ORB, which is
rotation invariant and resistant to noise. We demonstrate
through experiments how ORB is at two orders of magnitude
faster than SIFT, while performing as well in many
situations. The efficiency is tested on several real-world applications,
including object detection and patch-tracking on
a smart phone.
Introduction
The SIFT keypoint detector and descriptor [17], although
over a decade old, have proven remarkably successful
in a number of applications using visual features, including
object recognition [17], image stitching [28], visual
mapping [25], etc. However, it imposes a large computational
burden, especially for real-time systems such as visual
odometry, or for low-power devices such as cellphones.
This has led to an intensive search for replacements with
lower computation cost; arguably the best of these is SURF
[2]. There has also been research aimed at speeding up the
computation of SIFT, most notably with GPU devices [26].
In this paper, we propose a computationally-efficient replacement
to SIFT that has similar matching performance,
is less affected by image noise, and is capable of being used
for real-time performance. Our main motivation is to enhance
many common image-matching applications, e.g., to
enable low-power devices without GPU acceleration to perform
panorama stitching and patch tracking, and to reduce
the time for feature-based object detection on standard PCs.
Our descriptor performs as well as SIFT on these tasks (and
better than SURF), while being almost two orders of magnitude
faster.
Related Work
Keypoints FAST and its variants [23, 24] are the method
of choice for finding keypoints in real-time systems that
match visual features, for example, Parallel Tracking and
Mapping [13]. It is efficient and finds reasonable corner
keypoints, although it must be augmented with pyramid
schemes for scale [14], and in our case, a Harris corner filter
[11] to reject edges and provide a reasonable score.
Many keypoint detectors include an orientation operator
(SIFT and SURF are two prominent examples), but FAST
does not. There are various ways to describe the orientation
of a keypoint; many of these involve histograms of gradient
computations, for example in SIFT [17] and the approximation
by block patterns in SURF [2]. These methods are
either computationally demanding, or in the case of SURF,
yield poor approximations. The reference paper by Rosin
[22] gives an analysis of various ways of measuring orientation
of corners, and we borrow from his centroid technique.
Unlike the orientation operator in SIFT, which can have
multiple value on a single keypoint, the centroid operator
gives a single dominant result.
oFAST: FAST Keypoint Orientation
FAST features are widely used because of their computational
properties. However, FAST features do not have an
orientation component. In this section we add an efficientlycomputed
orientation.
Variance and Correlation
One of the pleasing properties of BRIEF is that each bit
feature has a large variance and a mean near 0.5. Figure 3
shows the spread of means for a typical Gaussian BRIEF
pattern of 256 bits over 100k sample keypoints. A mean
of 0.5 gives the maximum sample variance 0.25 for a bit
feature. On the other hand, once BRIEF is oriented along
the keypoint direction to give steered BRIEF, the means are
shifted to a more distributed pattern (again, Figure 3). One
way to understand this is that the oriented corner keypoints
present a more uniform appearance to binary tests.
Evaluation
We evaluate the combination of oFAST and rBRIEF,
which we call ORB, using two datasets: images with synthetic
in-plane rotation and added Gaussian noise, and a
real-world dataset of textured planar images captured from
different viewpoints. For each reference image, we compute
the oFAST keypoints and rBRIEF features, targeting 500
keypoints per image. For each test image (synthetic rotation
or real-world viewpoint change), we do the same, then perform
brute-force matching to find the best correspondence.
Conclusion
In this paper, we have defined a new oriented descriptor,
ORB, and demonstrated its performance and efficiency
relative to other popular features. The investigation of variance
under orientation was critical in constructing ORB
and de-correlating its components, in order to get good performance
in nearest-neighbor applications. We have also
contributed a BSD licensed implementation of ORB to the
community, via OpenCV 2.3.
[attachment=53741]
Abstract
Feature matching is at the base of many computer vision
problems, such as object recognition or structure from
motion. Current methods rely on costly descriptors for detection
and matching. In this paper, we propose a very fast
binary descriptor based on BRIEF, called ORB, which is
rotation invariant and resistant to noise. We demonstrate
through experiments how ORB is at two orders of magnitude
faster than SIFT, while performing as well in many
situations. The efficiency is tested on several real-world applications,
including object detection and patch-tracking on
a smart phone.
Introduction
The SIFT keypoint detector and descriptor [17], although
over a decade old, have proven remarkably successful
in a number of applications using visual features, including
object recognition [17], image stitching [28], visual
mapping [25], etc. However, it imposes a large computational
burden, especially for real-time systems such as visual
odometry, or for low-power devices such as cellphones.
This has led to an intensive search for replacements with
lower computation cost; arguably the best of these is SURF
[2]. There has also been research aimed at speeding up the
computation of SIFT, most notably with GPU devices [26].
In this paper, we propose a computationally-efficient replacement
to SIFT that has similar matching performance,
is less affected by image noise, and is capable of being used
for real-time performance. Our main motivation is to enhance
many common image-matching applications, e.g., to
enable low-power devices without GPU acceleration to perform
panorama stitching and patch tracking, and to reduce
the time for feature-based object detection on standard PCs.
Our descriptor performs as well as SIFT on these tasks (and
better than SURF), while being almost two orders of magnitude
faster.
Related Work
Keypoints FAST and its variants [23, 24] are the method
of choice for finding keypoints in real-time systems that
match visual features, for example, Parallel Tracking and
Mapping [13]. It is efficient and finds reasonable corner
keypoints, although it must be augmented with pyramid
schemes for scale [14], and in our case, a Harris corner filter
[11] to reject edges and provide a reasonable score.
Many keypoint detectors include an orientation operator
(SIFT and SURF are two prominent examples), but FAST
does not. There are various ways to describe the orientation
of a keypoint; many of these involve histograms of gradient
computations, for example in SIFT [17] and the approximation
by block patterns in SURF [2]. These methods are
either computationally demanding, or in the case of SURF,
yield poor approximations. The reference paper by Rosin
[22] gives an analysis of various ways of measuring orientation
of corners, and we borrow from his centroid technique.
Unlike the orientation operator in SIFT, which can have
multiple value on a single keypoint, the centroid operator
gives a single dominant result.
oFAST: FAST Keypoint Orientation
FAST features are widely used because of their computational
properties. However, FAST features do not have an
orientation component. In this section we add an efficientlycomputed
orientation.
Variance and Correlation
One of the pleasing properties of BRIEF is that each bit
feature has a large variance and a mean near 0.5. Figure 3
shows the spread of means for a typical Gaussian BRIEF
pattern of 256 bits over 100k sample keypoints. A mean
of 0.5 gives the maximum sample variance 0.25 for a bit
feature. On the other hand, once BRIEF is oriented along
the keypoint direction to give steered BRIEF, the means are
shifted to a more distributed pattern (again, Figure 3). One
way to understand this is that the oriented corner keypoints
present a more uniform appearance to binary tests.
Evaluation
We evaluate the combination of oFAST and rBRIEF,
which we call ORB, using two datasets: images with synthetic
in-plane rotation and added Gaussian noise, and a
real-world dataset of textured planar images captured from
different viewpoints. For each reference image, we compute
the oFAST keypoints and rBRIEF features, targeting 500
keypoints per image. For each test image (synthetic rotation
or real-world viewpoint change), we do the same, then perform
brute-force matching to find the best correspondence.
Conclusion
In this paper, we have defined a new oriented descriptor,
ORB, and demonstrated its performance and efficiency
relative to other popular features. The investigation of variance
under orientation was critical in constructing ORB
and de-correlating its components, in order to get good performance
in nearest-neighbor applications. We have also
contributed a BSD licensed implementation of ORB to the
community, via OpenCV 2.3.