Graphics Reference
In-Depth Information
place of the second-moment matrix during the feature detection stage, we obtain
Hessian-Affine features
.
4.1.6
High-Speed Feature Detection
While the detectors in the previous sections were generally derived from principled
analysis of scale- and affine-invariance, they can also be somewhat computationally
intensive (e.g., due to the many Gaussian convolutions and eigenvalue compu-
tations). The feature detectors in this section are designed to be much faster,
rapidly processing image pixels to produce robustly repeatable corner- and blob-like
features.
4.1.6.1 FAST Corners
Rosten and Drummond [
400
] proposed a detection algorithm for what they called
FAST Corners
, where FAST stands for Features from Accelerated Segment Test.
Figure
4.13
illustrates the idea. A candidate pixel
p
is compared to a discretized circle
of pixels around it; if all the pixels on a contiguous arc of
n
pixels around the circle are
significantly darker or lighter than the candidate pixel, it is detected as a feature. In
the original algorithm, the circle contained sixteen pixels and an arc of
n
12 pixels
had to satisfy the brightness comparison. A series of tests can be performed to quickly
reject feature candidates; for example, three of the four pixels labeled 1, 5, 9 and 13
must pass the test for a corner to exist.
Rosten and Drummond [
401
] later extended the FAST idea using a machine learn-
ing approach that substantially improved the detector's performance and speed.
They created a ground-truth database of a large number of pixel patches labeled as
corners or not-corners, and learned the structure of a decision tree based on the
intensities of the sixteen surrounding pixels that was able to correctly classify all the
patches in this training set. This decision tree — basically a long list of if-then-else
statements —was then optimized into highly efficient code to produce an improved
=
16
12
15
3
14
4
5
6
p
13
12
11
7
10
9
8
(a)
(b)
Figure 4.13.
(a) An original image, (b) A zoomed-in image illustrating the candidate pixel
(labeled
p
) and the circle of pixels (labeled 1-16) used for the FAST corner test. In this exam-
ple, the twelve-pixel clockwise arc from 11 to 6 is substantially darker than the center pixel,
resulting in a FAST corner.
