Oriented FAST and Rotated BRIEF

Why Does This Exist?

SIFT and SURF matched well across rotation and scale but were slow and once carried patent risk, so phones and drones could not run them at frame rate. FAST corners were cheap to find yet had no orientation and no scale handling: rotate the image and every descriptor mismatched.

ORB (Rublee and colleagues, 2011) fused two cheap ideas into one free pipeline: multiscale oriented FAST for detection plus steered BRIEF for description. The pyramid adds coarse scale tolerance, the intensity centroid adds rotation, and binary strings add millisecond Hamming matching. That mix powers open-source SLAM and panorama demos to this day. The point-detection roots live in corner and keypoint detection; putting the points to work lives in feature matching. This page covers the pyramid, the compass and the bit strings.

The one idea you need first. A descriptor is a compact fingerprint per keypoint, and matching compares fingerprints instead of pixels. Binary fingerprints compare with Hamming distance, the count of differing bits, which hardware counts almost for free.

Think of It Like This

How It Actually Works

Pyramid detection with Harris ranking

Detection builds an image pyramid, meaning successively downscaled copies with a scale factor near $1.2$ across about $8$ levels. FAST corners (pixels much brighter or darker than most of a surrounding ring) run per level, survivors rank by Harris response (a corner-strength score that rejects edge-like replies), and the top $N$ points spread across levels are kept. The pyramid buys scale tolerance; the Harris cut keeps the points repeatable.

One compass direction per patch

Orientation comes from the intensity centroid. With patch moments $m_{10}$ (brightness-weighted horizontal offset), $m_{01}$ (vertical offset) and $m_{00}$ (total mass):

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

where $\theta$ is the angle from the patch center to its brightness centroid, and $\mathrm{atan2}$ is the quadrant-aware arctangent. Description then rotates a fixed set of $256$ pixel-pair tests by $\theta$ and stores each brighter-or-darker verdict as one bit, giving a $256$-bit rotated BRIEF string that turns with the image.

Worked numbers

Take a patch with moments $m_{10} = 1200$ and $m_{01} = 900$. Then $\theta = \mathrm{atan2}(900, 1200) = \arctan(0.75) \approx 36.87$ degrees: the compass points up and right, and all $256$ pair tests rotate by that angle before comparing. For matching, shrink to an $8$-bit toy: descriptor $a = 10110011$ against $b = 10010010$ differ in positions two and six only, so the Hamming distance is $2$. At full scale, true pairs differ in a few dozen of $256$ bits while random pairs average $256 \times 0.5 = 128$, so a threshold near $50$ plus a ratio test separates them cleanly.

Code

1import math2
3theta = math.degrees(math.atan2(900, 1200))4a, b = 0b10110011, 0b100100105ham = bin(a ^ b).count("1")6print(round(theta, 2), ham)7# -> 36.87 2

Watch Out For

The Quick Version

• Pyramid FAST plus Harris ranking gives fast multiscale corner points.
• The intensity centroid assigns one rotation $\theta = \mathrm{atan2}(m_{01}, m_{10})$ per point.
• Rotated BRIEF stores $256$ orientation-corrected bits per patch.
• Hamming distance compares thousands of fingerprints in milliseconds.
• A $36.87$-degree example and a $2$-bit toy distance show the full pipeline arithmetic.

What to Read Next

• Corner and Keypoint Detection
• Feature Matching Links Two Views
• Contours and Shape Analysis