ORB

ORB (Oriented FAST and Rotated BRIEF) detects keypoints and describes each with a 256-bit binary string. It finds corners with the FAST segment test on an image pyramid, keeps the strongest by the Harris measure, gives each an orientation from the intensity centroid of its patch, and describes it with BRIEF intensity comparisons rotated to that orientation, using a set of 256 comparisons chosen by a learning step to be uncorrelated. Descriptors are compared by the Hamming distance, the number of differing bits. Ethan Rublee, Vincent Rabaud, Kurt Konolige and Gary Bradski of Willow Garage introduced ORB at ICCV 2011 as a fast alternative to SIFT and SURF, released it in OpenCV 2.3 under a BSD licence, and noted that it was free of the licensing restrictions of SIFT and SURF. ORB-SLAM later used it for every stage of a SLAM system. The 2011 paper received the PAMI Technical Committee’s Helmholtz Prize in 2021, a test-of-time award.

Problem

Matching local image features between images underlies structure from motion, visual odometry, panorama stitching and object detection. SIFT matches well but costs too much for real-time systems and for phones without a GPU, which is the motivation the ORB authors give. Two fast building blocks already existed. FAST finds corners with a few intensity comparisons per pixel, and BRIEF describes a patch with a few hundred comparisons and is matched with bit operations. Neither handles rotation: FAST gives no orientation, and BRIEF’s matching falls off after an in-plane rotation of 10 to 15 degrees. FAST also gives no reliable measure of corner strength and responds along edges. ORB adds the missing pieces: a ranking, an orientation, a descriptor that follows the orientation, and a choice of tests that keeps the bits informative after steering.

Inputs and Outputs

• Input: a grayscale image and a target number of keypoints $N$ (500 by default in OpenCV and scikit-image).
• Output: up to $N$ keypoints, each with a position, a pyramid level (scale), an orientation $\theta$ and a Harris score, and for each a 256-bit descriptor, stored as 32 bytes.

Intuition

A corner seen at a pixel is a place where a ring of pixels around it is mostly brighter or mostly darker than the center. Checking a ring of 16 pixels is much cheaper than computing gradients, so FAST tests that. Many ring tests also fire along edges and in clusters, so ORB uses the Harris measure only to rank the few thousand FAST candidates and keep the best $N$.

To describe a corner independently of rotation, ORB needs an angle that rotates with the image. The center of mass of the patch’s intensities usually lies off the corner point, toward the bright side; the direction from the corner to that centroid turns exactly as the patch turns. ORB measures the description in a frame aligned with that direction.

The description itself is a list of yes-or-no questions: is the smoothed intensity at point $a$ less than at point $b$? Each answer is one bit. Rotating the point pairs by $\theta$ before asking makes the answers rotation-invariant. Steering has a side effect, however: once all corners are seen in a common orientation, many questions give the same answer for most corners and carry little information. ORB therefore picks its 256 questions by a greedy search for ones whose answers split the training keypoints about evenly and do not repeat each other.

Algorithm

For each level of an image pyramid:

1. Detect. Run the FAST-9 segment test with a threshold low enough to give more than the target number of candidates.
2. Rank. Compute the Harris response at each candidate, sort, and keep the best.
3. Orient. Compute the moments of intensity in a circular patch around each keypoint and set $\theta$ to the direction from the keypoint to the intensity centroid.
4. Describe. Smooth the level, rotate the 256 learned test pairs by $\theta$ (in steps of $12°$, looked up in a precomputed table), and record one bit per pair.

Then keep the $N$ best keypoints over all levels and match descriptors between images by Hamming distance, by brute force for small sets or with locality-sensitive hashing for large databases.

Mathematical Formulation

FAST: the segment test

FAST (Features from Accelerated Segment Test) examines the 16 pixels on a Bresenham circle of radius 3 around a candidate pixel $p$ with intensity $I_p$. Rosten and Drummond introduced it in 2005, declaring $p$ a corner if at least 12 contiguous pixels on the circle are all brighter than $I_p + t$ or all darker than $I_p - t$ for a threshold $t$. Requiring 12 allowed a quick rejection: of the four pixels at the compass points, at least three must pass for a corner to exist. Their 2006 paper generalized the arc length to $n$ and replaced the hand-written test with a decision tree, learned with ID3 from detections on training images, that at each step examines the circle pixel giving the most information about whether $p$ is a corner; they found $n = 9$ the most repeatable and reported that for $n \le 8$ the detector starts to respond strongly to edges. FAST-9, the variant ORB uses, therefore means an arc of 9 contiguous pixels on the 16-pixel circle. The ORB paper describes it as “circular radius of 9”, which conflicts with the definition in Rosten and Drummond’s papers; the circle has radius 3.

The segment test is a yes-or-no decision, so non-maximum suppression needs a separate score. Rosten and Drummond used

$$V = \max\left( \sum_{x \in S_{\text{bright}}} \left| I_{p \to x} - I_p \right| - t, \; \sum_{x \in S_{\text{dark}}} \left| I_p - I_{p \to x} \right| - t \right),$$

where $I_{p \to x}$ is the intensity of circle pixel $x$, $S_{\text{bright}}$ holds the circle pixels at least $I_p + t$ and $S_{\text{dark}}$ those at most $I_p - t$ (their Eq. 8). The typesetting leaves open whether $t$ is subtracted once or from each term; the example below subtracts it from each term. The feature detection article compares FAST with gradient-based detectors.

Harris ranking and the pyramid

FAST gives no measure of how corner-like a detection is, and the ORB authors found large responses along edges. For a target of $N$ keypoints they set the FAST threshold low enough to obtain more than $N$, ordered the candidates by the Harris response $R = \det M - k (\operatorname{trace} M)^2$ of the Harris corner detector, and kept the top $N$. FAST also has no scale, so ORB runs it on each level of an image pyramid. The paper’s benchmarks used five levels a factor of $\sqrt{2}$ apart. OpenCV and scikit-image default to eight levels a factor of 1.2 apart. OpenCV divides the requested number of features among the levels in a geometric series, keeps twice each level’s quota after FAST, and re-ranks with the Harris response computed over a $7 \times 7$ block with $k = 0.04$ (OpenCV 5.0.0 source).

Orientation by the intensity centroid

ORB takes the orientation from the intensity centroid, one of several corner-orientation measures compared by Rosin. The moments of a patch are

$$m_{pq} = \sum_{x, y} x^p y^q \, I(x, y),$$

with $x$ and $y$ measured from the keypoint, and the centroid is $C = (m_{10}/m_{00}, \, m_{01}/m_{00})$. The orientation is the angle of the vector from the keypoint to $C$,

$$\theta = \operatorname{atan2}(m_{01}, m_{10}).$$

The ORB authors restricted $x$ and $y$ to a disk of radius $r$ rather than a square, so that the region itself does not change under rotation, with $r$ equal to the patch size (15 pixels for a $31 \times 31$ patch in OpenCV and scikit-image). Rosin’s method includes a correction for corners darker than their background; ORB drops it, since the measured angle rotates consistently with the image whether the corner is light or dark. The measure is unstable when $|C|$ is close to zero, which the authors found rare at FAST corners. In their simulation of rotated patches with added noise, the centroid recovered the rotation with a smaller standard deviation of angle error than the largest gradient or a SIFT-like histogram of gradient directions with $10°$ bins (their Fig. 2; figure numbers here follow the authors’ copy of the paper from the Willow Garage website).

Under a rotation $\mathbf{R}_\alpha$ of the image about the keypoint, the first moments rotate as a vector, so $\theta$ becomes $\theta + \alpha$. This is the property the descriptor relies on; it holds exactly only for the continuous image and a circular region, and pixel sampling, noise and keypoint position errors perturb it.

BRIEF tests

BRIEF, by Calonder, Lepetit, Strecha and Fua (2010), describes a smoothed patch $\mathbf{p}$ with binary tests

$$\tau(\mathbf{p}; \mathbf{x}, \mathbf{y}) = \begin{cases} 1 & \text{if } \mathbf{p}(\mathbf{x}) < \mathbf{p}(\mathbf{y}), \\ 0 & \text{otherwise}, \end{cases} \qquad f_n(\mathbf{p}) = \sum_{1 \le i \le n} 2^{\,i-1} \, \tau(\mathbf{p}; \mathbf{x}_i, \mathbf{y}_i),$$

where $(\mathbf{x}_i, \mathbf{y}_i)$ are $n$ fixed pairs of points in the patch. The feature descriptors article places BRIEF among other descriptors; the details ORB inherits are these. Each test looks at single pixels, so it is sensitive to noise, and BRIEF smooths the patch first: Calonder et al. found recognition rates roughly constant for Gaussian smoothing levels between 1 and 3 and used 2, with a $9 \times 9$ kernel (their text calls these values variances, while their Fig. 1 labels them $\sigma$). Of five ways of drawing the pairs, drawing both points independently from an isotropic Gaussian with $\sigma^2 = S^2/25$ for an $S \times S$ patch had a small advantage in most of their tests, and they used it. They studied $n = 128$, 256 and 512 bits.

The ORB authors start from $n = 256$ pairs drawn from a Gaussian distribution, a pattern the learned pairs below replace, and smooth by comparing $5 \times 5$ sub-window sums computed with an integral image, inside a $31 \times 31$ patch. OpenCV instead blurs each pyramid level with a $7 \times 7$ Gaussian of $\sigma = 2$ before computing descriptors (OpenCV 5.0.0 source).

Steered BRIEF

Collect the test points in a $2 \times n$ matrix $\mathbf{S} = (\mathbf{x}_1, \ldots, \mathbf{x}_n)$ (and likewise for the second points of the pairs). With the keypoint orientation $\theta$, steered BRIEF uses the rotated points

$$\mathbf{S}_\theta = \mathbf{R}_\theta \mathbf{S}, \qquad g_n(\mathbf{p}, \theta) = f_n(\mathbf{p}) \big|_{(\mathbf{x}_i, \mathbf{y}_i) \in \mathbf{S}_\theta}.$$

ORB quantizes $\theta$ to multiples of $2\pi/30$ ($12°$) and precomputes the 30 rotated patterns, so steering costs a table lookup. As long as $\theta$ is consistent across views, the same physical tests are applied to the same corner. OpenCV 5.0.0 and scikit-image 0.25.2 do not quantize: they rotate each test point by the continuous angle and round it to the nearest pixel (source of each).

Variance, correlation and the learned tests

A test is most informative when it answers 1 for about half of all keypoints: a bit with mean $\mu$ has variance $\mu(1 - \mu)$, largest at $\mu = 0.5$. Tests should also be uncorrelated, so that each bit adds information. Over 100,000 keypoints, the ORB authors found that unsteered BRIEF bits had means near 0.5 but that steering spread the means away from 0.5 (their Fig. 3), since once oriented, corners present a more uniform appearance to the tests. A principal component analysis showed that both versions were correlated, with nearly all the variance in the first 10 to 15 components, and that steered BRIEF had lower eigenvalues and so was less discriminative (Fig. 4). They concluded that BRIEF had depended on the random orientations of keypoints for its good behavior.

To restore variance and reduce correlation, they searched for a new set of tests. They extracted about 300,000 keypoints from images of the PASCAL VOC 2006 set (presumably oriented, though §4.3 does not say so) and enumerated all tests between pairs of non-overlapping $5 \times 5$ sub-windows of the $31 \times 31$ patch, 205,590 tests in all. Then:

1. Run every test on all training patches and order the tests by the distance of their mean from 0.5.
2. Put the first test in the result set.
3. Take the next test; discard it if its absolute correlation with any test already in the result exceeds a threshold, otherwise add it.
4. Repeat until 256 tests are chosen; if the list runs out first, raise the threshold and start again.

The result is called rBRIEF. Its PCA eigenvalues are higher and fall off more slowly than those of steered BRIEF (Fig. 4), and its learned tests are visibly more varied in position and direction than the high-variance unlearned ones (Fig. 6). The 256 learned pairs ship with OpenCV as a table annotated with each test’s mean and correlation, and scikit-image uses the same pairs: its data file is identical to OpenCV’s table (our element-by-element comparison).

Matching

Two descriptors $\mathbf{a}, \mathbf{b} \in \{0, 1\}^{256}$ are compared by the Hamming distance, the population count of $\mathbf{a} \oplus \mathbf{b}$; for 256 bits that is four 64-bit XORs and four bit counts, far cheaper than a floating-point distance. Similarity and distance measures covers the distance and its properties, and feature matching the strategies built on it, such as mutual (cross-checked) nearest neighbors and the ratio test.

For large databases, the authors used locality-sensitive hashing. For binary descriptors the hash function is simply a subset of the bits: descriptors sharing the same sub-signature fall in the same bucket, and a query is compared only with the members of its buckets in several tables. They used multi-probe LSH (Lv et al., 2007), which also checks buckets near the query’s, so that fewer tables, and so less memory, reach the same accuracy. Less correlated bits partition the data more evenly: rBRIEF gave far more uniform bucket sizes than BRIEF or steered BRIEF (Fig. 10), and in their speed–accuracy comparison LSH over rBRIEF was faster than FLANN kd-trees over SIFT, while steered BRIEF was much slower because of its uneven buckets (Fig. 11). This is the second purpose of the learned tests: they make binary descriptors indexable as well as distinctive.

Parameters

• Number of features (nfeatures in OpenCV, n_keypoints in scikit-image, default 500): the $N$ kept after Harris ranking. ORB-SLAM extracts 1,000 for images from $512 \times 384$ to $752 \times 480$ pixels and 2,000 for KITTI’s $1241 \times 376$.
• Scale factor and number of levels (OpenCV scaleFactor 1.2 and nlevels 8; scikit-image downscale and n_scales, same defaults): the scale range covered and how finely it is sampled. OpenCV’s documentation warns that a factor of 2 degrades matching dramatically, while a factor near 1 needs more levels and is slower.
• FAST threshold (OpenCV fastThreshold 20 on 8-bit intensities; scikit-image fast_threshold 0.08 on images scaled to $[0, 1]$) and arc length (scikit-image fast_n, default 9): lower thresholds give more candidates for the Harris ranking to choose from, at more cost.
• Harris $k$ (0.04 in both libraries): the edge-rejection constant of the Harris measure. OpenCV’s scoreType can rank by the FAST score instead, which its documentation describes as slightly less stable and a little faster.
• Patch size and border (OpenCV patchSize and edgeThreshold, both 31): the descriptor’s support, and the margin in which no keypoints are detected; the documentation says the two should roughly match.
• WTA_K (OpenCV, default 2): the number of points per test. With 3 or 4, each test reports which of the points is brightest as a 2-bit code, compared with a 2-bit Hamming distance (NORM_HAMMING2).

Complexity

FAST costs a bounded number of comparisons per pixel; the 2006 decision tree asked 2.26 questions per pixel on average for $n = 9$. The Harris response is needed only at the candidates. Orientation needs one pass over a disk of about 700 pixels per keypoint, and the descriptor needs 256 comparisons of box sums, each a few integral-image lookups. Matching $N_1$ against $N_2$ descriptors by brute force costs $N_1 N_2$ Hamming distances. On a single thread of a 2.8 GHz Intel i7, the authors measured 4.43 ms for the pyramid, 8.68 ms for oFAST and 2.12 ms for rBRIEF on a $640 \times 480$ frame, and, for roughly 1,000 features on 24 PASCAL images of that size, 15.3 ms per frame for ORB against 217.3 ms for SURF and 5,228.7 ms for SIFT. The paper’s wording varies: two orders of magnitude faster than SIFT in the abstract, almost two in the introduction and over two in the benchmark section; the measured ratio is about 340 (our arithmetic).

Implementation

The script below implements the core of ORB in NumPy and SciPy on rendered scenes. Each scene is 40 random convex polygons of random gray level on a smooth background, rendered with $4 \times 4$ supersampling at $256 \times 256$ pixels, with Gaussian noise of standard deviation 0.02 on a $[0, 1]$ scale. The second image renders the same scene rotated about the image center, with fresh noise, so the true position of every point is known. The script detects 200 keypoints per image with the FAST-9 segment test, non-maximum suppression on the score $V$ and Harris ranking, at a single pyramid level, and orients them by the intensity centroid. It then describes them in four ways: unsteered BRIEF with a fixed random Gaussian pattern; steered BRIEF with the same pattern and 30 discrete angles; steered tests with the learned rBRIEF pairs; and the learned pairs without the $5 \times 5$ box smoothing. Matching is mutual nearest neighbors in Hamming distance, and a match counts as correct if it lands within 3 pixels of the true position. As a cross-check, it runs scikit-image’s ORB at one pyramid level on the same images. The loop covers five scenes (seeds 0 to 4) and six rotations, and the script also reports the orientation error at keypoints detected at the same scene point in both images, and the bit statistics of each descriptor over all rotated images. It uses NumPy 2.3, SciPy 1.16 and scikit-image 0.25.2, runs in about 20 seconds, and nothing in it is random beyond the fixed seeds; two runs printed identical output.

import os
import numpy as np
from scipy import ndimage
import skimage.feature

# ---------- synthetic scene: random convex polygons, rendered at any rotation ----------
def make_scene(seed, n_shapes=40, size=256):
    rng = np.random.default_rng(seed)
    shapes = []
    for _ in range(n_shapes):
        k = rng.integers(3, 6)                       # triangles to pentagons
        center = rng.uniform(30, size - 30, 2)
        radius = rng.uniform(8, 22)
        angles = np.sort(rng.uniform(0, 2 * np.pi, k))
        verts = center + radius * np.c_[np.cos(angles), np.sin(angles)]
        shapes.append((verts, rng.uniform(0.1, 0.9)))
    return shapes

def render(shapes, alpha_deg, noise_seed, size=256, ss=4, noise=0.02):
    """Render the scene rotated by alpha about the image center, 4x4 supersampled."""
    a = np.deg2rad(alpha_deg)
    R = np.array([[np.cos(a), -np.sin(a)], [np.sin(a), np.cos(a)]])
    c = np.array([size / 2, size / 2])
    g = (np.arange(size * ss) + 0.5) / ss - 0.5
    X, Y = np.meshgrid(g, g)                         # x = column, y = row
    Xs = np.cos(a) * (X - c[0]) + np.sin(a) * (Y - c[1])    # scene coordinates
    Ys = -np.sin(a) * (X - c[0]) + np.cos(a) * (Y - c[1])
    img = 0.5 + 0.1 * np.sin(Xs / 40.0) * np.cos(Ys / 55.0)  # smooth background
    for verts, value in shapes:
        v = (verts - c) @ R.T + c                    # rotated vertices
        inside = np.ones_like(X, dtype=bool)
        for i in range(len(v)):                      # convex polygon: all half-planes
            (x0, y0), (x1, y1) = v[i], v[(i + 1) % len(v)]
            inside &= (x1 - x0) * (Y - y0) - (y1 - y0) * (X - x0) >= 0
        img[inside] = value
    img = img.reshape(size, ss, size, ss).mean(axis=(1, 3))
    return img + np.random.default_rng(noise_seed).normal(0, noise, img.shape)

# ---------- oFAST: FAST-9 segment test, non-maximum suppression, Harris ranking ----------
CIRCLE = [(0, 3), (1, 3), (2, 2), (3, 1), (3, 0), (3, -1), (2, -2), (1, -3),
          (0, -3), (-1, -3), (-2, -2), (-3, -1), (-3, 0), (-3, 1), (-2, 2), (-1, 3)]

def fast_score(img, t, n=9):
    H, W = img.shape
    p = img[3:-3, 3:-3]
    ring = np.stack([img[3 + dy:H - 3 + dy, 3 + dx:W - 3 + dx] for dy, dx in CIRCLE])
    score = np.zeros(img.shape)
    for sign in (1, -1):                             # brighter arc, then darker arc
        d = sign * (ring - p)                        # > t means "on the arc"
        on = d > t
        found = np.zeros(p.shape, dtype=bool)
        for s in range(16):                          # any n contiguous (with wrap-around)
            found |= np.all([on[(s + k) % 16] for k in range(n)], axis=0)
        v = np.where(on, d - t, 0).sum(axis=0)       # Rosten & Drummond score V
        score[3:-3, 3:-3] = np.maximum(score[3:-3, 3:-3], np.where(found, v, 0))
    return score

def harris(img, k=0.04):
    Ix = ndimage.gaussian_filter(img, 1.0, order=(0, 1))
    Iy = ndimage.gaussian_filter(img, 1.0, order=(1, 0))
    A, B, C = (ndimage.gaussian_filter(q, 2.0) for q in (Ix * Ix, Iy * Iy, Ix * Iy))
    return A * B - C**2 - k * (A + B) ** 2

def ofast(img, n_keep=200, t=0.05, border=20):
    V = fast_score(img, t)
    peaks = (V > 0) & (V == ndimage.maximum_filter(V, size=3))
    peaks[:border], peaks[-border:], peaks[:, :border], peaks[:, -border:] = 0, 0, 0, 0
    rc = np.argwhere(peaks)
    R = harris(img)[rc[:, 0], rc[:, 1]]
    rc = rc[np.argsort(-R)[:n_keep]]                 # keep the n_keep best Harris scores
    # Orientation by intensity centroid in a disk of radius 15.
    yy, xx = np.mgrid[-15:16, -15:16]
    disk = xx**2 + yy**2 <= 15**2
    theta = np.empty(len(rc))
    for i, (r, c) in enumerate(rc):
        patch = img[r - 15:r + 16, c - 15:c + 16] * disk
        theta[i] = np.arctan2((yy * patch).sum(), (xx * patch).sum())   # atan2(m01, m10)
    return rc, theta

# ---------- BRIEF, steered BRIEF (30 discrete angles), Hamming matching ----------
def brief(img, rc, theta, pattern, steer, box=5):
    sm = ndimage.uniform_filter(img, size=box)       # each test compares box means
    bins = np.round(theta / (2 * np.pi / 30)) * (2 * np.pi / 30) if steer else 0 * theta
    bits = np.empty((len(rc), len(pattern)), dtype=bool)
    for i, ((r, c), a) in enumerate(zip(rc, bins)):
        ca, sa = np.cos(a), np.sin(a)
        x0, y0, x1, y1 = pattern.T
        X0 = np.rint(ca * x0 - sa * y0).astype(int); Y0 = np.rint(sa * x0 + ca * y0).astype(int)
        X1 = np.rint(ca * x1 - sa * y1).astype(int); Y1 = np.rint(sa * x1 + ca * y1).astype(int)
        bits[i] = sm[r + Y0, c + X0] < sm[r + Y1, c + X1]
    return np.packbits(bits, axis=1)                 # 256 bits -> 32 bytes

def match(d1, d2):
    D = np.bitwise_count(d1[:, None, :] ^ d2[None, :, :]).sum(axis=2)   # Hamming
    j = D.argmin(axis=1)
    i_back = D.argmin(axis=0)
    keep = i_back[j] == np.arange(len(d1))           # mutual nearest neighbours
    return np.flatnonzero(keep), j[keep]

def to_rotated(rc, alpha_deg, size=256):
    """Where a (row, col) point of the upright image lands in the rotated one."""
    a = np.deg2rad(alpha_deg)
    x, y = rc[:, 1] - size / 2, rc[:, 0] - size / 2
    return np.c_[np.sin(a) * x + np.cos(a) * y, np.cos(a) * x - np.sin(a) * y] + size / 2

# Random BRIEF pattern (Gaussian, sigma^2 = S^2/25 for S = 31), fixed seed;
# the learned rBRIEF pairs are the 256 that OpenCV and scikit-image ship.
rng = np.random.default_rng(0)
random_pattern = np.clip(np.rint(rng.normal(0, 31 / 5, (256, 4))), -13, 13).astype(int)
learned_pattern = np.loadtxt(os.path.join(os.path.dirname(skimage.feature.__file__),
                                          "orb_descriptor_positions.txt"), dtype=int)

angles = [0, 10, 20, 45, 90, 180]
methods = ["BRIEF", "steered BRIEF", "steered rBRIEF", "rBRIEF, no box", "skimage ORB"]
results = {m: np.zeros((5, len(angles))) for m in methods}
orient_err = []
bits = {m: [] for m in methods}
for seed in range(5):
    shapes = make_scene(seed)
    img1 = render(shapes, 0, noise_seed=100 + seed)
    rc1, th1 = ofast(img1)
    for ai, alpha in enumerate(angles):
        img2 = render(shapes, alpha, noise_seed=200 + seed)
        rc2, th2 = ofast(img2)
        truth = to_rotated(rc1, alpha)
        # Orientation check: keypoints detected at the same scene point in both images.
        dist = np.linalg.norm(truth[:, None] - rc2[None], axis=2)
        i, j = np.nonzero(dist < 1.5)
        e = np.angle(np.exp(1j * (th2[j] - th1[i] - np.deg2rad(alpha))))
        orient_err.extend(np.rad2deg(np.abs(e)))
        for name, pattern, steer, box in [("BRIEF", random_pattern, False, 5),
                                          ("steered BRIEF", random_pattern, True, 5),
                                          ("steered rBRIEF", learned_pattern, True, 5),
                                          ("rBRIEF, no box", learned_pattern, True, 1)]:
            d2 = brief(img2, rc2, th2, pattern, steer, box)
            bits[name].append(np.unpackbits(d2, axis=1))
            m1, m2 = match(brief(img1, rc1, th1, pattern, steer, box), d2)
            ok = np.linalg.norm(truth[m1] - rc2[m2], axis=1) < 3
            results[name][seed, ai] = ok.sum()
        # Cross-check: scikit-image's ORB (deterministic), one pyramid level like ours.
        o1 = skimage.feature.ORB(n_keypoints=200, fast_threshold=0.05, n_scales=1)
        o2 = skimage.feature.ORB(n_keypoints=200, fast_threshold=0.05, n_scales=1)
        o1.detect_and_extract(img1); o2.detect_and_extract(img2)
        mm = skimage.feature.match_descriptors(o1.descriptors, o2.descriptors,
                                               metric="hamming", cross_check=True)
        t1 = to_rotated(o1.keypoints[mm[:, 0]], alpha)
        ok = np.linalg.norm(t1 - o2.keypoints[mm[:, 1]], axis=1) < 3
        results["skimage ORB"][seed, ai] = ok.sum()

print("correct matches (of 200 keypoints): mean over 5 scenes [min-max]")
print("rotation".ljust(16) + "".join(f"{a:>13}" for a in angles))
for name in methods:
    r = results[name]
    print(name.ljust(16) + "".join(f"{m:6.0f} [{lo:.0f}-{hi:.0f}]".rjust(13)
                                   for m, lo, hi in zip(r.mean(0), r.min(0), r.max(0))))
oe = np.array(orient_err)
print(f"orientation error at repeated keypoints (n={len(oe)}): "
      f"median {np.median(oe):.1f} deg, 90th percentile {np.percentile(oe, 90):.1f} deg, "
      f"share above 6 deg {np.mean(oe > 6):.2f}")
for name in methods[:3]:
    B = np.vstack(bits[name]).astype(float)          # all descriptors of the rotated images
    C = np.abs(np.corrcoef(B.T))[~np.eye(256, dtype=bool)]
    print(f"{name:15} bits: mean |p - 0.5| = {np.abs(B.mean(0) - 0.5).mean():.3f}, "
          f"mean |correlation| = {C.mean():.3f}")

correct matches (of 200 keypoints): mean over 5 scenes [min-max]
rotation                    0           10           20           45           90          180
BRIEF              127 [115-138]   105 [97-115]    57 [49-64]      1 [1-3]      0 [0-0]      0 [0-0]
steered BRIEF      107 [102-117]    98 [86-108]    98 [92-106]    90 [78-102]   106 [101-113]   110 [101-119]
steered rBRIEF     109 [102-118]   102 [88-113]   101 [90-109]    94 [83-103]   104 [95-116]   110 [103-122]
rBRIEF, no box      80 [73-87]    69 [61-78]    68 [57-79]    64 [59-74]    73 [66-83]    79 [74-92]
skimage ORB         70 [63-78]    65 [51-73]    60 [54-63]    59 [51-70]    72 [66-78]    72 [65-81]
orientation error at repeated keypoints (n=3843): median 2.4 deg, 90th percentile 10.1 deg, share above 6 deg 0.21
BRIEF           bits: mean |p - 0.5| = 0.009, mean |correlation| = 0.208
steered BRIEF   bits: mean |p - 0.5| = 0.221, mean |correlation| = 0.137
steered rBRIEF  bits: mean |p - 0.5| = 0.077, mean |correlation| = 0.134

Unsteered BRIEF is the best descriptor when nothing rotates, holds up at $10°$, loses more than half its correct matches at $20°$ and fails completely from $45°$ on, the pattern Calonder et al. and the ORB authors reported for BRIEF. Steering makes the count nearly independent of rotation: the mean stays between about 90 and 110 correct matches at every angle, and no scene falls below 78. The price is visible at $0°$, where steered descriptors find about 20 fewer correct matches than plain BRIEF. The orientation line suggests why, in our reading: one keypoint in five has an orientation error above $6°$, half the $12°$ step between steering angles, so the two views often select neighboring patterns and some tests change. The smaller counts at $45°$ than at $90°$ and $180°$ fit the geometry: the image is rotated about the point $(128, 128)$, so a rotation by a multiple of $90°$ maps pixel centers onto pixel centers and both views sample the scene alike, while $45°$ resamples it.

The box filter matters as much as the steering. Comparing single pixels instead of $5 \times 5$ means costs about a quarter to a third of the correct matches at every angle; averaging 25 pixels divides the noise standard deviation by 5, and noise of 0.02 is enough to flip tests between nearby pixels of similar intensity. scikit-image’s ORB at one level behaves like the variant without the box: in version 0.25.2 it compares single pixels of each pyramid level with its tests rotated by the continuous angle, and the first level is the input image itself, unsmoothed (source and documentation of that version). Its counts are also flat across rotation, which confirms the steering in an independent implementation.

The bit statistics reproduce, on synthetic data, the effect that motivated rBRIEF. Over the rotated images, the bits of unsteered BRIEF have means within 0.01 of 0.5 on average, because the keypoints present the tests in all orientations. Steering moves the means about 0.22 away from 0.5, so many tests answer the same way for most corners; the learned pairs bring them back to within about 0.08. In this example the learned pairs do not reduce correlation below that of the steered random pattern, and they give no clear gain in exhaustive matching. They were selected on keypoints from natural photographs, not polygons, and their main benefit in the paper showed in hash-table search, which this example does not run.

Properties and Behavior

• Rotation. Invariance is as good as the orientation estimate, and the estimate is good at well-defined corners: in the authors’ rotation tests with noise, ORB performed best, with over 70% inliers, while BRIEF fell off after about $10°$ (their Fig. 7). Keypoints with nearly symmetric patches, where $|C|$ is small, have unstable orientations.
• Noise. The authors found ORB less affected by Gaussian noise than SIFT: SIFT’s inlier rate fell by about 10% with each increase of 5 in the noise level on an 8-bit scale, while rBRIEF’s fell much more slowly (Fig. 8). The smoothing of the tests is what protects the descriptor; the FAST detector itself is not robust to noise, as Rosten, Porter and Drummond note, because it looks at only a few pixels.
• Illumination. A test compares two smoothed intensities of the same patch, so its outcome is unchanged by a positive gain and an offset applied to the whole patch (our reasoning). The FAST threshold $t$ is absolute, so a contrast change alters which corners are detected.
• Scale. The pyramid gives invariance only in steps of the scale factor and over the range of levels, and the descriptor’s $31 \times 31$ support covers more of the scene at coarser levels. The authors wrote that they had not adequately addressed scale invariance.
• Viewpoint. Nothing in ORB models affine distortion; on their planar real-image sets, ORB was about as accurate as SIFT and SURF on a textured indoor set of magazines (36.2% inliers, against 38.3% for SURF and 34.0% for SIFT) and better on an outdoor scene, labelled “Boat” in their table (45.8%, against 28.6% and 30.2%).
• Distribution. Keypoints concentrate in textured regions. Applications that need coverage, such as ORB-SLAM, divide each level into a grid and adapt the FAST threshold per cell.

Limitations

• Coarse scale invariance and no affine invariance, as above.
• Corners only: FAST and Harris ignore blob-like structure, which SIFT’s difference-of-Gaussians detector captures. The ORB authors cite Calonder et al. for the observation that blob-detection keypoints like SIFT’s do better on graffiti-type images; the BRIEF paper itself attributes BRIEF’s weaker Graffiti results to the rotation in that set and to large uniform areas that favor gradient-histogram descriptors.
• A 256-bit descriptor of a $31 \times 31$ patch is less distinctive than SIFT’s gradient histograms under large viewpoint and illumination changes, as the feature descriptors article discusses.
• The learned tests were selected on one image collection, PASCAL VOC 2006 photographs; how well they transfer to other imagery is an empirical question.
• Many parameters interact (threshold, levels, scale factor, number of features, patch size), and the defaults differ between implementations, so results are not directly comparable across libraries.

Use in SLAM

ORB-SLAM (Mur-Artal, Montiel and Tardós, 2015) uses ORB for tracking, mapping, relocalization and loop closing. The authors required features that take much less than 33 ms per image, which they wrote excluded SIFT (about 300 ms), SURF (about 300 ms) and A-KAZE (about 100 ms), and rotation invariance for place recognition, which excluded BRIEF. They extract FAST corners at 8 pyramid levels with a scale factor of 1.2, 1,000 corners for images of $512 \times 384$ to $752 \times 480$ pixels and 2,000 for KITTI, spread over a grid that aims for at least five corners per cell, and compute the orientation and descriptor on the corners kept. Each map point stores one representative descriptor, the one with the smallest Hamming distance to all its other observations. Loop detection and relocalization use a bag of binary words built on ORB descriptors (DBoW2), and matches are filtered by an orientation consistency test that requires a coherent rotation among all correspondences. On the NewCollege sequence, ORB extraction took a median of 11.1 ms per frame on an Intel Core i7-4700MQ. The SLAM article describes the system’s threads, covisibility graph and successors, and bag of visual words covers the place-recognition index.

Variants

• FAST-ER (Rosten, Porter and Drummond, 2010) optimizes a detector of the same family for repeatability rather than speed; in their tests it outperformed FAST-9 under added noise.
• Multi-point tests. OpenCV’s WTA_K option compares three or four points per test and records the index of the brightest, as above.
• Ranking by the FAST score instead of Harris, offered by OpenCV as a faster option.
• Grid-distributed ORB, as in ORB-SLAM, which trades some keypoint strength for coverage of the image.
• Other binary descriptors, such as BRISK and FREAK, sample intensities on fixed patterns of concentric rings and estimate orientation from them; they are compared with ORB in feature descriptors.