FAST Corner Detector

FAST (Features from Accelerated Segment Test) decides whether a pixel is a corner by looking only at the 16 pixels on a small circle around it. If a long enough run of contiguous circle pixels is all brighter than the center by a threshold, or all darker, the pixel is a corner. No derivatives, smoothing or eigenvalues are computed, and most pixels are rejected after a few comparisons: the learned FAST-9 tree asked 2.26 questions per pixel on average. Edward Rosten and Tom Drummond introduced the test in 2005 as part of a real-time tracker. In 2006 they generalized it to arcs of any length $n$, compiled it into a decision tree learned from example images, and found the 9-pixel arc (FAST-9) the most repeatable. In 2010, with Reid Porter, they turned the tree into a detector optimized directly for repeatability, FAST-ER. FAST is the detector inside ORB, which ORB-SLAM uses for every stage of a SLAM system.

Problem

A feature detector must find points that can be found again in another view, and in a live system it must do so for every frame. Gradient-based detectors such as the Harris corner detector compute and smooth products of derivatives at every pixel. Rosten and Drummond (2006) measured the cost on fields of PAL video ($768 \times 288$ pixels, about 500 features per field) on a 2.6 GHz Opteron: their Harris implementation took 24.0 ms per field, 120% of the time available at video rate, and SIFT’s difference-of-Gaussians detection 60.1 ms (301%), against 1.33 ms (6.65%) for the learned FAST-9 with non-maximum suppression (their Table 1). The aim was a detector that leaves most of the frame time for tracking, matching or mapping, without giving up repeatability.

Inputs and Outputs

• Input: a grayscale image, a threshold $t$ on intensity differences, and an arc length $n$ (9 to 16 for the 16-pixel circle).
• Output: a set of corner pixels, optionally with a score for each, used for non-maximum suppression and for keeping the strongest corners.

FAST gives no scale and no orientation. Each corner is a single pixel position at the resolution of the image it was run on.

Intuition

At a corner of a bright region on a dark background, most of a small circle around the corner point lies in the background. Seen from the corner pixel, a long arc of the circle is darker than the center; at the tip of a dark wedge it is brighter. Along a straight edge, roughly half the circle is brighter and half darker, and in a flat region the circle matches the center. Asking whether a long contiguous arc is all brighter or all darker therefore separates corners from edges and flat regions, using only comparisons of intensities.

The test is also cheap to reject. Most pixels lie in flat or weakly textured regions, and two opposite circle pixels that both match the center already rule out a long arc. The speed of FAST comes from deciding the test while reading as few circle pixels as possible.

Algorithm

The segment test (Rosten and Drummond, 2006, §2.1):

1. For a candidate pixel $p$ with intensity $I_p$, take the 16 pixels on a Bresenham circle of radius 3 around it, numbered 1 to 16 clockwise from the top.
2. Classify each circle pixel as darker, similar or brighter than $p$ by the threshold $t$.
3. Declare $p$ a corner if there are $n$ contiguous circle pixels (counting around the circle, so pixel 16 is adjacent to pixel 1) that are all brighter, or all darker.

The original high-speed test (2005) fixed $n = 12$. Then at least three of the four compass pixels 1, 5, 9 and 13 must be brighter, or three darker, for a corner to exist, so the detector examined those four first and ran the full test only on the survivors. On their video sequence, it examined 3.8 pixels per location on average.

The learned detector (2006, §2.2) replaces the hand-ordered test with a ternary decision tree:

1. Run the plain segment test for the chosen $n$ and a convenient threshold on training images, preferably from the target application, to label every pixel as corner or non-corner.
2. Each circle position $x$ splits the pixels into three sets by the state of $p \to x$ (darker, similar, brighter). Choose the position whose split gives the most information about the corner label, as in ID3.
3. Recurse on each of the three subsets until every subset is pure.
4. Convert the tree into nested if-then-else statements in C and compile it.

Non-maximum suppression (2006, §2.3): the segment test is a yes-or-no decision, so a score $V$ is computed for each detected corner, and corners with an adjacent corner of higher score are removed; the 2010 paper uses a $3 \times 3$ neighborhood.

Mathematical Formulation

States and the segment test

The 2006 paper defines the state of circle pixel $x$ relative to $p$ as

$$S_{p \to x} = \begin{cases} d, & I_{p \to x} \le I_p - t \quad \text{(darker)} \\ s, & I_p - t < I_{p \to x} < I_p + t \quad \text{(similar)} \\ b, & I_p + t \le I_{p \to x} \quad \text{(brighter)} \end{cases}$$

(their Eq. 5; the 2010 paper’s Eq. 8 is the same). The text of both papers describes the segment test with “brighter than $I_p$ plus a threshold”, which reads as a strict inequality; scikit-image 0.25.2 and OpenCV 4.14.0 both use strict inequalities, $I_{p \to x} > I_p + t$ and $I_{p \to x} < I_p - t$, and so does the example below. The two conventions differ only for differences exactly equal to $t$.

$p$ is a FAST-$n$ corner if, for some starting position $s$,

$$S_{p \to s} = S_{p \to s+1} = \dots = S_{p \to s+n-1} \in \{b, d\},$$

with positions taken modulo 16.

Training the tree

With $P$ the training pixels and $K_p$ the corner label, the tree is grown by ID3. For a set $Q$ with $c$ corners and $\bar c$ non-corners, the entropy is

$$H(Q) = (c + \bar c) \log_2 (c + \bar c) - c \log_2 c - \bar c \log_2 \bar c ,$$

and the position $x$ chosen at a node maximizes the information gain $H(P) - H(P_d) - H(P_s) - H(P_b)$ (2006, Eq. 6–7; 2010, Eq. 10–11). Recursion ends when a subset’s entropy is zero, which always happens because $K$ is an exact function of the data. Because the training images do not contain every possible ring, the 2006 tree is a slightly different heuristic from the segment test, which the authors accepted. The 2010 paper notes that the difference can be removed: there are $3^{16} = 43{,}046{,}721$ possible rings, and adding each to the training data with a low weight makes the learned detector compute the segment test exactly.

Corner scores

Several scores have been used for non-maximum suppression.

• The 2006 paper lists three intuitive choices (the largest $n$ for which $p$ is still a corner, the largest $t$, and the sum of absolute differences along the arc), rejects the first two as highly quantized, and uses a modified sum, the score $V$ of its Eq. 8, which the ORB article gives in full.
• The 2010 paper instead defines the corner strength as the largest $t$ for which $p$ is still detected (§III-C). Since detection is monotonic in $t$, it can be found by bisection, or by raising $t$ step by step until the decision tree’s path changes. With strict inequalities, the largest such $t$ has a closed form:

$$V_{\max t}(p) = \max_{\sigma \in \{+1, -1\}} \; \max_{s} \; \min_{0 \le k < n} \sigma \left( I_{p \to s+k} - I_p \right),$$

and $p$ is a corner at threshold $t$ exactly when $V_{\max t}(p) > t$ (our derivation; the example checks it pixel by pixel). OpenCV 4.14.0 computes this score for 8-bit images and stores the largest integer threshold at which the pixel is still a corner (cornerScore in fast_score.cpp).

• scikit-image 0.25.2’s corner_fast returns, for each detected pixel, the sum of $|I_{p \to x} - I_p|$ over all 16 circle pixels, not only those on the arc and without subtracting $t$ (_corner_fast_response in corner_cy.pyx). Its peaks are taken by a separate call to corner_peaks.

The three scores rank corners differently, so the corners that survive suppression differ between implementations even when the segment test agrees.

Why longer arcs miss obtuse corners

A wedge of angle $\theta$ with its tip at $p$ covers about $16\,\theta/360°$ of the circle pixels. A bright convex wedge ($\theta < 180°$) on a dark background is detected through its dark background arc, which is long enough when $16 (360° - \theta)/360° \ge n$, that is, $\theta \le 360° (1 - n/16)$; a reflex corner is detected through its bright arc when $\theta \ge 360°\, n/16$ (our reasoning). FAST-12 should therefore find corners up to $90°$ and from $270°$, and FAST-9 up to about $157.5°$ and from about $202.5°$. A straight edge never gives an arc of 9: the 16 circle pixels come in pairs opposite each other about $p$, and a straight line that leaves $p$ on its bright side can have at most one pixel of each pair strictly on its dark side, so the dark arc holds at most 8 pixels (our derivation). This matches the authors’ finding that for $n \le 8$ the detector starts to respond strongly to edges (2006, Fig. 6; 2010, Fig. 8, whose text calls FAST-8 and below edge detectors).

Parameters

• Threshold $t$. The only continuous parameter. It is absolute, in intensity units, so it controls both the number of corners and how much contrast a corner needs. OpenCV’s FastFeatureDetector defaults to 10 on 8-bit images, scikit-image’s corner_fast to 0.15 on images in $[0, 1]$. The FAST-ER tree was trained at $t = 35$ (2010, Table I). In the authors’ comparisons the threshold was varied to reach a given number of corners per frame, and the 2006 paper lists the dependence on a threshold among the detector’s disadvantages.
• Arc length $n$. $n = 9$ was the most repeatable in the authors’ tests (2006, Fig. 6A; 2010, Fig. 8), and $n = 12$ is the original detector. OpenCV’s 16-pixel detector supports only $n = 9$: it requires an arc longer than half the circle (count > K with $K = 8$ in fast.cpp). scikit-image accepts any $n$ and defaults to 12.
• Circle. The papers use the 16-pixel circle of radius 3. OpenCV also offers a 12-pixel circle of radius 2 with arcs of 7 (TYPE_7_12) and the 8 neighbors with arcs of 5 (TYPE_5_8), described in its documentation as the three neighborhoods “as defined in the paper”.
• Non-maximum suppression on or off, and the score used for it (above).

Complexity

The test reads at most 16 pixels per location, so the cost is linear in the number of pixels with a small constant, and most pixels exit early. The learned trees asked 2.26 questions per pixel on average for $n = 9$ and 2.39 for $n = 12$, against 2.8 for the hand-written detector (2006, §2.4); the 2005 paper reported 3.8 pixels examined per location for its hand-written FAST-12 on its own sequence. The cost also grows with the number of corners found, because corners need a full test and a score: the 2005 paper notes that speed is related to the number detected (its Fig. 11).

The 2010 paper timed detectors on a 3.0 GHz Pentium 4-D on two sequences: a training set of 101 high-definition fields of $992 \times 668$ pixels, also used to train the fast detectors and for profile-guided optimization, and a test set of 4,968 quarter-PAL frames of $352 \times 288$ pixels. The feature density was equivalent to about 500 per $640 \times 480$ frame, and the times include non-maximum suppression (its Table IV, which gives each rate as a share of the time budget of $640 \times 480$ video). On the test set FAST-9 processed 179 megapixels per second (5.15% of the budget); the learned FAST-12 154 (5.98%); the original hand-written FAST-12 82.2 (11.2%); FAST-ER 67.5 (13.7%); SUSAN 13.6 (67.9%); Harris 7.90 (117%); Shi–Tomasi 6.50 (142%); and difference of Gaussians 5.10 (179%). The figures in the paper’s abstract (under 5% for FAST, Harris 115%, SIFT 195%) are those of the training-set column. The 2010 version of FAST-9 also tests the first two pixels for a strip of pixels at once with vector instructions, by forcing the tree to ask the same second question on all three branches.

Implementation

The script below implements the segment test in NumPy, with the largest-$t$ score, and checks both against scikit-image’s corner_fast on every image it makes. It then measures four behaviors of the test.

• A. Wedges. A $33 \times 33$ image holds a wedge of angle $\theta$ (intensity 0.8 inside, 0.2 outside, area-sampled with $8 \times 8$ subsamples per pixel) with its tip at the center pixel, for $\theta = 15°, 30°, \dots, 345°$ and 24 orientations $15°$ apart, with $t = 0.1$. The detection rate is the fraction of orientations in which some pixel within 1.5 pixels of the tip passes the test. In brackets is the prediction of an ideal point-sampled wedge, in which a circle pixel counts as inside when its center is.
• B. Straight edges. A $41 \times 41$ step edge with the same intensities, at 36 orientations $5°$ apart and 4 subpixel offsets, for $n = 8$ to 12.
• C. The compass pixels. On scikit-image’s bundled rocket photograph, converted to grayscale, at $t = 0.08$: how many FAST-9 and FAST-12 corners have fewer than three, or fewer than two, of the compass pixels 1, 5, 9 and 13 on the corner’s side.
• D. Repeatability. Two copies of rocket with independent Gaussian noise of standard deviation $\sigma$ (5 noise pairs per $\sigma$), at three thresholds. Corners are kept by $3 \times 3$ non-maximum suppression on the largest-$t$ score (a pixel equal to the maximum of its neighborhood, ties kept). Repeatability follows Rosten et al. (2010, Eq. 12): the number of corners in the first copy with a corner in the second within 1.5 pixels, divided by the number in the first, summed over the pairs. The images differ only in noise, so the true correspondence is the identity.

Images are indexed by row and column; the rendering uses $x$ to the right and $y$ up from the center pixel, and the circle is numbered clockwise from the top, as in the papers’ Fig. 1. The script uses NumPy 2.3.5, SciPy 1.16.3 and scikit-image 0.25.2, and runs in about 35 seconds; nothing in it is random beyond the fixed seeds, and two runs printed identical output.

import os
os.environ["OMP_NUM_THREADS"] = "1"; os.environ["OPENBLAS_NUM_THREADS"] = "1"
import numpy as np
from scipy import ndimage
from skimage import data, color
from skimage.feature import corner_fast

# Bresenham circle of radius 3, numbered clockwise from the top (pixel 1 = index 0).
CIRCLE = [(-3, 0), (-3, 1), (-2, 2), (-1, 3), (0, 3), (1, 3), (2, 2), (3, 1),
          (3, 0), (3, -1), (2, -2), (1, -3), (0, -3), (-1, -3), (-2, -2), (-3, -1)]  # (dy, dx)
COMPASS = [0, 4, 8, 12]                                   # pixels 1, 5, 9, 13

def ring_stack(img):
    H, W = img.shape
    return np.stack([img[3 + dy:H - 3 + dy, 3 + dx:W - 3 + dx] for dy, dx in CIRCLE])

def arcs(on, n):
    """True where some n contiguous ring pixels (with wrap-around) are all on."""
    found = np.zeros(on.shape[1:], bool)
    for s in range(16):
        found |= np.all([on[(s + k) % 16] for k in range(n)], axis=0)
    return found

def segment_test(img, n, t):
    p, R = img[3:-3, 3:-3], ring_stack(img)
    out = np.zeros(img.shape, bool)
    out[3:-3, 3:-3] = arcs(R > p + t, n) | arcs(R < p - t, n)
    return out

def max_t_score(img, n):
    """Largest t for which the pixel is still a corner: max over arcs of the arc's smallest difference."""
    D = ring_stack(img) - img[3:-3, 3:-3]
    inner = np.full(D.shape[1:], -np.inf)
    for v in (D, -D):                                    # brighter arcs, darker arcs
        for s in range(16):
            m = v[s]
            for k in range(1, n):
                m = np.minimum(m, v[(s + k) % 16])
            inner = np.maximum(inner, m)
    score = np.full(img.shape, -np.inf)
    score[3:-3, 3:-3] = inner
    return score

mismatch = {"skimage": 0, "score": 0}
def detect(img, n, t):
    """Segment test, checked against scikit-image and against the score on every call."""
    mask = segment_test(img, n, t)
    mismatch["skimage"] += np.sum(mask != (corner_fast(img, n=n, threshold=t) > 0))
    mismatch["score"] += np.sum(mask != (max_t_score(img, n) > t))
    return mask

def render(inside_fn, size, ss=8, lo=0.2, hi=0.8):
    """Area-sampled two-level image: x right, y up, origin at the centre pixel."""
    c = size // 2
    g = (np.arange(size * ss) + 0.5) / ss - 0.5 - c
    X, Y = np.meshgrid(g, -g)
    cover = inside_fn(X, Y).reshape(size, ss, size, ss).mean(axis=(1, 3))
    return lo + (hi - lo) * cover

def longest_run(on):
    run = best = 0
    for v in np.r_[on, on]:
        run = run + 1 if v else 0
        best = max(best, run)
    return min(best, 16)

# ---------- A. wedges of angle theta, apex at the centre pixel ----------
thetas, phis, ns, t = np.arange(15, 360, 15), np.arange(0, 360, 15), [9, 10, 11, 12], 0.1
ring_angle = np.degrees(np.arctan2([-dy for dy, dx in CIRCLE], [dx for dy, dx in CIRCLE])) % 360
yy, xx = np.mgrid[-16:17, -16:17]
dist = np.hypot(yy, xx)
rate = {n: [] for n in ns}; pred = {n: [] for n in ns}; off_apex = {n: 0 for n in ns}
for th in thetas:
    hits = {n: 0 for n in ns}; phits = {n: 0 for n in ns}
    for ph in phis:
        img = render(lambda X, Y: (np.degrees(np.arctan2(Y, X)) - ph) % 360 < th, 33)
        inside = (ring_angle - ph) % 360 < th               # point-sampled ring at the apex
        for n in ns:
            m = detect(img, n, t)
            hits[n] += m[dist <= 1.5].any()
            off_apex[n] += m[dist > 3].sum()
            phits[n] += max(longest_run(inside), longest_run(~inside)) >= n
    for n in ns:
        rate[n].append(hits[n] / len(phis)); pred[n].append(phits[n] / len(phis))

print("A. wedge detection rate over 24 orientations (point-sampled prediction in brackets)")
print("theta  " + "".join(f"FAST-{n:<9d}" for n in ns))
for i, th in enumerate(thetas):
    print(f"{th:5d}  " + "".join(f"{rate[n][i]:.2f} [{pred[n][i]:.2f}]  " for n in ns))
for n in ns:
    r, p = np.array(rate[n]), np.array(pred[n])
    cross = lambda q: (thetas[(thetas < 180) & (q >= 0.5)].max(), thetas[(thetas > 180) & (q >= 0.5)].min())
    print(f"FAST-{n}: detected up to {cross(r)[0]} and from {cross(r)[1]} deg "
          f"(point-sampled {cross(p)[0]}/{cross(p)[1]}; 360(1-n/16) = {360*(1-n/16):.1f}), "
          f"rate(theta) = rate(360-theta): {np.array_equal(r, r[::-1])}, "
          f"detections > 3 px from the apex: {off_apex[n]}")

# ---------- B. straight edges ----------
print("B. straight edges, 36 orientations x 4 offsets")
for n in [8, 9, 10, 11, 12]:
    imgs_hit = total = 0
    for phi in np.arange(0, 180, 5):
        nx, ny = np.cos(np.radians(phi)), np.sin(np.radians(phi))
        for e in [0, 0.25, 0.5, 0.75]:
            m = detect(render(lambda X, Y: X * nx + Y * ny > e, 41), n, t)
            imgs_hit += m.any(); total += m.sum()
    print(f"FAST-{n:<2d}: images with a detection {imgs_hit:3d} / 144, detections {total}")

# ---------- C. the compass pixels on a real image ----------
rocket = color.rgb2gray(data.rocket())                  # 427 x 640, values in [0, 1]
print("C. high-speed test on rocket, t = 0.08")
p, R = rocket[3:-3, 3:-3], ring_stack(rocket)
for n in [9, 12]:
    bright, dark = arcs(R > p + 0.08, n), arcs(R < p - 0.08, n)
    passing = np.where(bright, (R[COMPASS] > p + 0.08).sum(0), (R[COMPASS] < p - 0.08).sum(0))
    c = passing[bright | dark]
    print(f"FAST-{n}: corners {c.size}, with < 3 compass pixels {np.sum(c < 3)}, with < 2 {np.sum(c < 2)}")

# ---------- D. repeatability against threshold and noise ----------
def keypoints(img, n, t):
    detect(img, n, t)                                    # checks only
    s = max_t_score(img, n)
    return (s > t) & (s == ndimage.maximum_filter(s, size=3))

print("D. repeatability on rocket, two noisy copies, 5 noise pairs: R [min-max per pair] (mean detections)")
print("sigma   t     " + "".join(f"FAST-{n:<22d}" for n in [9, 12]))
for sigma in [0, 0.01, 0.02, 0.04]:
    for thr in [0.04, 0.08, 0.16]:
        row = f"{sigma:<6} {thr:<5} "
        for n in [9, 12]:
            rep = det = 0; per_pair = []
            for k in range(5):
                A = rocket + sigma * np.random.default_rng(100 + k).normal(size=rocket.shape)
                B = rocket + sigma * np.random.default_rng(200 + k).normal(size=rocket.shape)
                kA, kB = keypoints(A, n, thr), keypoints(B, n, thr)
                r = np.sum(kA & ndimage.binary_dilation(kB, np.ones((3, 3))))
                rep += r; det += kA.sum(); per_pair.append(r / kA.sum())
            row += f"{rep / det:.3f} [{min(per_pair):.3f}-{max(per_pair):.3f}] ({det / 5:5.0f})  "
        print(row)

print(f"pixels where the hand test and skimage.corner_fast disagree: {mismatch['skimage']}; "
      f"where (score > t) and the test disagree: {mismatch['score']}")

A. wedge detection rate over 24 orientations (point-sampled prediction in brackets)
theta  FAST-9        FAST-10       FAST-11       FAST-12       
   15  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  
   30  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  
   45  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  
   60  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  
   75  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  
   90  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  0.33 [1.00]  
  105  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  0.00 [0.33]  
  120  1.00 [1.00]  1.00 [1.00]  0.17 [0.67]  0.00 [0.00]  
  135  1.00 [1.00]  0.33 [1.00]  0.00 [0.00]  0.00 [0.00]  
  150  1.00 [1.00]  0.00 [0.33]  0.00 [0.00]  0.00 [0.00]  
  165  0.33 [0.67]  0.00 [0.00]  0.00 [0.00]  0.00 [0.00]  
  180  0.00 [0.00]  0.00 [0.00]  0.00 [0.00]  0.00 [0.00]  
  195  0.33 [0.67]  0.00 [0.00]  0.00 [0.00]  0.00 [0.00]  
  210  1.00 [1.00]  0.00 [0.33]  0.00 [0.00]  0.00 [0.00]  
  225  1.00 [1.00]  0.33 [1.00]  0.00 [0.00]  0.00 [0.00]  
  240  1.00 [1.00]  1.00 [1.00]  0.17 [0.67]  0.00 [0.00]  
  255  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  0.00 [0.33]  
  270  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  0.33 [1.00]  
  285  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  
  300  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  
  315  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  
  330  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  
  345  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  1.00 [1.00]  
FAST-9: detected up to 150 and from 210 deg (point-sampled 165/195; 360(1-n/16) = 157.5), rate(theta) = rate(360-theta): True, detections > 3 px from the apex: 1040
FAST-10: detected up to 120 and from 240 deg (point-sampled 135/225; 360(1-n/16) = 135.0), rate(theta) = rate(360-theta): True, detections > 3 px from the apex: 936
FAST-11: detected up to 105 and from 255 deg (point-sampled 120/240; 360(1-n/16) = 112.5), rate(theta) = rate(360-theta): True, detections > 3 px from the apex: 808
FAST-12: detected up to 75 and from 285 deg (point-sampled 90/270; 360(1-n/16) = 90.0), rate(theta) = rate(360-theta): True, detections > 3 px from the apex: 680
B. straight edges, 36 orientations x 4 offsets
FAST-8 : images with a detection 112 / 144, detections 5968
FAST-9 : images with a detection   0 / 144, detections 0
FAST-10: images with a detection   0 / 144, detections 0
FAST-11: images with a detection   0 / 144, detections 0
FAST-12: images with a detection   0 / 144, detections 0
C. high-speed test on rocket, t = 0.08
FAST-9: corners 3548, with < 3 compass pixels 692, with < 2 0
FAST-12: corners 1983, with < 3 compass pixels 0, with < 2 0
D. repeatability on rocket, two noisy copies, 5 noise pairs: R [min-max per pair] (mean detections)
sigma   t     FAST-9                     FAST-12                    
0      0.04  1.000 [1.000-1.000] ( 3111)  1.000 [1.000-1.000] ( 2271)  
0      0.08  1.000 [1.000-1.000] ( 1512)  1.000 [1.000-1.000] ( 1019)  
0      0.16  1.000 [1.000-1.000] (  488)  1.000 [1.000-1.000] (  272)  
0.01   0.04  0.795 [0.789-0.801] ( 3486)  0.797 [0.794-0.799] ( 2501)  
0.01   0.08  0.849 [0.844-0.857] ( 1583)  0.849 [0.839-0.861] ( 1045)  
0.01   0.16  0.875 [0.856-0.891] (  484)  0.870 [0.847-0.886] (  276)  
0.02   0.04  0.528 [0.521-0.532] ( 6032)  0.542 [0.539-0.544] ( 3879)  
0.02   0.08  0.721 [0.703-0.735] ( 1817)  0.707 [0.702-0.713] ( 1199)  
0.02   0.16  0.770 [0.758-0.788] (  517)  0.759 [0.736-0.789] (  297)  
0.04   0.04  0.544 [0.540-0.550] (17561)  0.429 [0.425-0.430] (12247)  
0.04   0.08  0.392 [0.383-0.402] ( 4453)  0.382 [0.377-0.387] ( 2620)  
0.04   0.16  0.606 [0.589-0.619] (  662)  0.584 [0.559-0.614] (  379)  
pixels where the hand test and skimage.corner_fast disagree: 0; where (score > t) and the test disagree: 0

The hand-written test and scikit-image agree on every pixel of every image, and the largest-$t$ score reproduces the test exactly at every threshold used, so the measurements below are properties of the segment test itself rather than of one implementation.

Wedges. The detection rate falls from 1 to 0 as the wedge opens toward $180°$ and returns for reflex corners, and the boundary moves inward as $n$ grows: FAST-12 detects wedges up to $75°$ and from $285°$, FAST-9 up to $150°$ and from $210°$. Every measured boundary lies one $15°$ step inside the point-sampled prediction, which in turn is close to the $360°(1 - n/16)$ estimate. In our reading, area sampling gives the circle pixels crossed by the wedge’s sides, and the center pixel itself, intermediate values; a circle pixel that then differs from the center by less than $t$ breaks an arc that point sampling counts as complete. The consequence for right angles is stark: a $90°$ corner, the corner of a square, passes FAST-12 in only a third of the orientations here, while FAST-9 detects every corner up to $150°$. The rates are exactly symmetric, $\text{rate}(\theta) = \text{rate}(360° - \theta)$: the test is unchanged when intensities are inverted, and inverting the 0.2/0.8 rendering of a wedge gives the rendering of its complement. Across the 552 wedge images, 1,040 pixels farther than 3 pixels from the tip pass FAST-9, falling to 680 for FAST-12.

Edges. No straight edge produces a single FAST-9 to FAST-12 detection, as the pairing argument above requires, while FAST-8 fires in 112 of the 144 edge images. In these images, the step from 8 to 9 is where the segment test stops responding to edges.

Compass pixels. Every FAST-12 corner has at least three compass pixels on its side, so the 2005 rejection test is exact for $n = 12$. For FAST-9, 692 of the 3,548 corners, about one in five, have only two, and none has fewer: counting around the circle, an arc of 9 always contains at least two of the four and an arc of 12 at least three. A four-pixel test that demands three would discard a fifth of the FAST-9 corners here. The 2010 paper makes the same point: for $n < 12$ a corner may have only two of the four pixels brighter or darker, so the quick test rejects fewer candidates.

Repeatability. Without noise both copies are identical and repeatability is 1. Noise alone lowers it quickly: at $t = 0.08$ it falls from 0.849 at $\sigma = 0.01$ to 0.392 at $\sigma = 0.04$ for FAST-9. At $\sigma = 0.01$ and $0.02$, a higher threshold gives higher repeatability and fewer corners for both arc lengths, as planned. The planned repeatability hypothesis failed in part. Its claim that repeatability rises with $t$ at every noise level failed at $\sigma = 0.04$: there, $t = 0.04$ gives higher repeatability than $t = 0.08$ (0.544 against 0.392 for FAST-9, 0.429 against 0.382 for FAST-12). Its claim that repeatability falls as $\sigma$ rises also failed in one cell: FAST-9 at $t = 0.04$ rises from 0.528 at $\sigma = 0.02$ to 0.544 at $\sigma = 0.04$. In our reading, the printed counts explain both failures: at $\sigma = 0.04$ and $t = 0.04$ the noise itself passes the test, and FAST-9 marks 17,561 corners in a $427 \times 640$ image, about four times as many as at $t = 0.08$, so many corners find a partner within 1.5 pixels by chance. Rosten et al. make the corresponding point about the measure: the trivial detector that marks every pixel reaches 100% repeatability. They compare detectors at a given number of corners per frame. The FAST-9 and FAST-12 columns are close at $\sigma \le 0.02$ and FAST-9 is higher at $\sigma = 0.04$, but FAST-9 always finds more corners at the same threshold, so the columns do not compare the two at equal counts.

Evaluation

Rosten and Drummond chose repeatability as the criterion of detector quality, following Schmid, Mohr and Bauckhage as they describe it: a feature is repeated if the same scene point is detected again in another view. Their 2010 paper distinguishes three kinds of evaluation. Synthetic test images give exact ground truth but, in their view, do not generalize to natural images; system performance, such as tracking, tests usefulness but depends on the rest of the system; and repeatability is independent of later processing but rewards trivial detectors, since marking every pixel gives 100%.

Where Schmid et al. used planar scenes related by homographies, Rosten and Drummond used 3D surface models aligned to the images, so that corners of polyhedra, occlusions and T-junctions, and textures under non-affine warps, could be tested. Their datasets were a box of pasted photographs with strong perspective and radial distortion, a maze used in augmented reality, and a bas-relief scene modeled as a plane. Repeatability is plotted against the number of corners per frame (0 to 2,000 for a $640 \times 480$ image in 2010), with random points as a baseline, and a match allows an error of $\varepsilon$ pixels for imperfect alignment and models (5 pixels in 2010). The 2010 paper also used the ‘Oxford’ dataset, eight sequences of six images related by homographies, and summarized each curve by its area for 0 to 2,000 corners per frame.

Their main findings:

• FAST-9 is the most repeatable segment test. Among FAST-9 to FAST-16 it gave the highest repeatability, and below 9 the detector responds strongly to edges (2006, Fig. 6A; 2010, Fig. 8).
• Speed did not cost repeatability. In 2006, FAST outperformed Harris, Shi–Tomasi, difference of Gaussians, Harris–Laplace and SUSAN on their three datasets when more than about 200 corners per frame were needed. In the 2010 aggregate (Table III, area under the repeatability curves over all datasets except the noise test), the order was FAST-ER 1313.6, FAST-9 1304.57, difference of Gaussians 1275.59, Shi–Tomasi 1219.08, Harris 1195.2, Harris–Laplace 1153.13, FAST-12 1121.53, SUSAN 1116.79, random points 271.73.
• Noise is FAST’s weakness. The authors found FAST “not very robust to the presence of noise” and explain it by its design: it reads the fewest pixels possible and so averages out little noise. Difference of Gaussians was remarkably robust to added noise, which they explain as matched filtering.
• Low densities favor gradient detectors. Harris and Shi–Tomasi tended to be the most repeatable below about 100 corners per frame (2010).

FAST-ER

FAST-ER (Rosten, Porter and Drummond, 2010, §V) keeps the form of the detector, a ternary decision tree over intensity comparisons with the center, but drops the segment test as the definition of a corner and optimizes the tree for repeatability instead.

• Tree. Each node tests one of 48 offsets around the center (their Fig. 6), not only the 16-pixel circle. Each leaf is corner or non-corner, and a leaf on a “similar” branch of its parent is forced to be a non-corner, so the number of corners generally decreases as the threshold rises.
• Symmetry. The tree is applied 16 times, at four rotations $90°$ apart, with and without reflection and intensity inversion, and a pixel is a corner if any application says so.
• Cost. Simulated annealing minimizes

$$k = \left(1 + \left(\frac{w_r}{r}\right)^2\right) \left(1 + \frac{1}{N}\sum_{i=1}^{N} \left(\frac{d_i}{w_n}\right)^2\right) \left(1 + \left(\frac{s}{w_s}\right)^2\right),$$

where $r$ is the repeatability, $d_i$ the number of corners in frame $i$ of $N$, and $s$ the number of nodes in the tree (Eq. 13). The second and third factors stop the two degenerate solutions: detecting every pixel, which makes repeatability perfect, and a tree large enough to find one repeated feature per training image.

• Search. Random mutations replace a leaf by a small subtree, flip a leaf’s class, change a node’s offset, turn a node into a leaf, or copy one branch over another (a move suggested by FAST-9’s trees, where two of three subtrees are often identical); changes are accepted by the Boltzmann criterion under an exponential temperature schedule. The training set was only the first three images of the box dataset, at $t = 35$, with $w_r = 1$, $w_n = 3{,}500$, $w_s = 10{,}000$, 100 runs of 100,000 iterations each, taking about 200 hours on a 3 GHz Pentium 4 (Table I and §V-A).
• Compilation. Because 16 applications are slow, the best tree labels training data for a single tree learned by ID3, as for FAST-$n$; the result has about 30,000 non-leaf nodes.

In the 2010 tests FAST-ER had the best aggregate repeatability, and it greatly outperformed FAST-9 on the noise test, beating every other detector there for noise standard deviations below 7. The authors attribute this to the training parameters, which bias FAST-ER toward more corners at a given threshold, so that at a fixed number of corners its threshold is higher and noise matters less. Its repeatability also fell least as the number of corners per frame rose. It ran at 67.5 megapixels per second on the test set, about 38% of FAST-9’s rate, and in the authors’ words still much faster than all but FAST-$n$.

Properties and Behavior

• Intensity changes. The test compares differences with an absolute threshold, so adding a constant to the image changes nothing, while a change of contrast changes which corners pass. Inverting intensities swaps bright and dark arcs and leaves the detections unchanged, as the symmetric wedge rates above show.
• Rotation. The test is defined on a circle, but a Bresenham circle of 16 pixels is only approximately rotation-invariant, and detection of a given corner varies with its orientation, as the fractional rates near each boundary above show.
• Scale. FAST has one support size, a circle of radius 3, and no scale selection. Systems that need scale run it on each level of an image pyramid, as ORB does.
• Localization. A corner is a pixel; the papers’ evaluation leaves localization accuracy aside, noting that for most applications the presence or absence of useful corners is the limiting factor (2010, footnote 1).
• Clustering. The raw test fires on several adjacent pixels at a corner, the fourth weakness the 2006 paper lists, hence the score and non-maximum suppression.

Limitations

• Noise. Single-pixel comparisons average no noise, and the detector was not robust to high noise levels in the authors’ tests; FAST-ER reduces but does not remove the problem.
• Thin lines. The 2006 paper notes that FAST can respond to lines one pixel wide at certain angles, where the discrete circle misses the line.
• Threshold dependence. The number and quality of corners depend on $t$, which must be tuned or adapted per image or per image region.
• Corners only, at one scale. FAST does not find blobs and gives no scale or orientation; SIFT’s difference-of-Gaussians detector and ORB’s pyramid and intensity-centroid orientation add what FAST lacks, at extra cost.
• Learned for a domain. A FAST-$n$ tree learned only from example images can differ slightly from the segment test on rings the images do not contain, and FAST-ER’s tree was optimized on three training images.

Variants

• FAST-$n$ for $n = 9$ to 16 on the 16-pixel circle; FAST-9 and FAST-12 are the common choices, and OpenCV’s smaller circles give arcs of 7 of 12 and 5 of 8.
• FAST-ER (above), optimized for repeatability.
• AGAST. Mair, Hager, Burschka, Suppa and Hirzinger (2010) published a detector based on the accelerated segment test, which OpenCV implements as AgastFeatureDetector. In OpenCV 4.14.0 it offers four masks: OAST_9_16 (arcs of 9 on the 16-pixel circle, the default), AGAST_7_12d and AGAST_7_12s (arcs of 7 on two 12-pixel rings, one with offsets up to 3 pixels and one up to 2), and AGAST_5_8 (arcs of 5 on the 8 neighbors). Its score, like FAST’s in the 2010 paper, is the largest threshold at which a pixel is still a corner, found by bisection (agast_score.cpp), and its documentation states that a tree-optimized version for non-Intel platforms gives the same numerical results. The AGAST paper itself was not read for this article.
• oFAST in ORB. ORB runs FAST-9 on a pyramid, ranks corners by the Harris measure, and adds an orientation from the intensity centroid; the ORB article covers these steps, and ORB-SLAM’s grid with a per-cell threshold.
• Other scores, as above: the 2006 sum $V$, the largest $t$, and scikit-image’s sum over the whole circle.

Use

The 2006 paper describes the authors’ own use of the detectors for real-time tracking and augmented-reality label placement. Rosten’s project page lists, as of November 2026, the C reference implementation under the BSD licence (release 2.1 of 2009, described as stable rather than abandoned), a pure-Python version, MATLAB code that includes FAST-ER, the FAST-ER source, and FAST’s inclusion in OpenCV since 31 August 2009. In loop closure, Gálvez-López and Tardós replaced SIFT and SURF with FAST corners and BRIEF descriptors to cut the cost per image. Corners found by FAST are then described and matched as in feature matching, or followed between frames by feature tracking.