Fast and Binary: SURF, BRIEF, ORB, and LBP

The Need for Speed: Real-Time Features

In the last guide we built the SIFT descriptor: a 128-number floating-point vector per keypoint, computed from oriented gradient histograms. It is wonderfully robust — but look at the cost. Every keypoint needs a Gaussian-blurred image pyramid, gradient magnitudes and orientations everywhere, and then a 128-D float vector. Matching two images means comparing thousands of these vectors with Euclidean (L2) distance, each comparison touching 128 floats. That is fine for a single photo on a laptop. It is a disaster when a phone, a drone, or a robot must do this 30+ times per second.

Real-time vision — visual SLAM (a robot mapping a room while tracking its own pose), augmented reality (anchoring a virtual object to a moving camera view), and mobile apps — simply cannot afford SIFT's float-heavy compute and matching. This guide develops two big ideas to fix that. Idea 1: approximate the expensive Gaussian/derivative machinery with cheap box filters and integral images — this gives us the SURF descriptor. Idea 2: throw out float vectors entirely and describe a keypoint as a binary string of yes/no tests, compared by Hamming distance in a few CPU instructions — this gives us BRIEF, the ORB descriptor, and LBP.

1. Integral images — a precomputation trick that makes the sum over any rectangle cost just four lookups (the engine behind SURF and face detection).
2. SURF — speeds up SIFT's detector and descriptor with box filters; still a float vector (64-D), so still uses L2 distance. Optimizes compute speed.
3. BRIEF — the first binary descriptor: a string of intensity-comparison bits. Tiny memory, blazing-fast matching, but not rotation-invariant.
4. ORB — fixes BRIEF: adds a fast corner detector and orientation so it survives rotation, all patent-free. The real-time workhorse.
5. LBP — a different flavour of binary code aimed at texture and faces, summarized as a histogram of per-pixel codes.

Integral Images: Box Sums in O(1)

Before SURF makes sense we need one beautiful, reusable trick: the integral image (also called a summed-area table). The problem it solves: many algorithms repeatedly ask 'what is the sum of pixel values inside this rectangle?' Doing that the obvious way costs one addition per pixel, so a big box is slow and you pay again for every box. The integral image lets you answer any rectangle sum in constant time — four lookups — no matter how large the rectangle. The same trick reappears in the famous Viola–Jones face detector, so it is worth truly understanding.

Each integral-image entry stores the sum of every pixel above-and-to-the-left of it (inclusive).

Read it like this: II(x,y) is the integral image at column x, row y. The right side sums the original image I(x',y') over every pixel whose column x' is ≤ x and whose row y' is ≤ y — i.e. the whole rectangle from the top-left corner down to (x,y). You never compute that sum from scratch; you build the table in one pass with the recurrence II(x,y) = I(x,y) + II(x−1,y) + II(x,y−1) − II(x−1,y−1) (the last term cancels the doubly-counted overlap). Take a concrete 4×4 image (rows top to bottom): row1 = [3 1 4 1], row2 = [5 9 2 6], row3 = [5 3 5 8], row4 = [9 7 9 3]. Running the recurrence gives the integral image: row1 = [3 4 8 9], row2 = [8 18 24 31], row3 = [13 26 37 52], row4 = [22 42 62 80]. Sanity check: the bottom-right entry, 80, equals the sum of all 16 pixels (9+22+21+28 = 80).

The sum over the rectangle with top-left corner (x0,y0) and bottom-right corner (x1,y1) — four lookups, any size.

This is inclusion–exclusion. II(x1,y1) is the big block from the origin down to the rectangle's far corner — but it includes a strip above the rectangle and a strip to its left that we do not want. Subtract II(x0−1,y1) (everything left of the rectangle) and II(x1,y0−1) (everything above it). Those two strips overlap in the top-left region, which we just subtracted twice, so we add back II(x0−1,y0−1) once. Let us recover the inner 2×2 block (rows 2–3, columns 2–3) of our example. Brute force: pixels 9+2+3+5 = 19. By the formula, with (x0,y0)=(2,2) and (x1,y1)=(3,3): II(3,3) − II(1,3) − II(3,1) + II(1,1) = 37 − 13 − 8 + 3 = 19. Identical — and we touched exactly four numbers, not the whole rectangle. That O(1) box-sum is precisely what makes the SURF descriptor fast, as we see next.

SURF: Speeded-Up SIFT

The SURF descriptor (Speeded-Up Robust Features) is SIFT's fast cousin: same overall recipe — detect blob-like keypoints across scale, then describe each with a gradient-based vector — but every expensive step is replaced by something an integral image can evaluate in O(1). The result keeps most of SIFT's robustness at a fraction of the compute. The trick is to stop computing exact Gaussian-derivative responses and instead approximate them with crude box filters, which are nothing but a few rectangle sums.

Recall from Guide 2 that a blob is a roughly circular bright/dark region, found where the second-derivative response (the Hessian) peaks at the right scale. SURF detects keypoints as maxima of an approximated Hessian determinant. SIFT built a whole Gaussian image pyramid to reach larger scales (repeatedly blurring and downsampling). SURF instead keeps the image fixed and grows the filter: because box filters are evaluated by integral-image lookups, a 9×9 filter and a 27×27 filter cost exactly the same — four lookups per box. Connect this straight back to blob detection: same idea (Hessian-of-Gaussian blobs), drastically cheaper machinery.

SURF's blob response: the determinant of the box-filter-approximated Hessian.

The Hessian is the matrix of second derivatives; its determinant is large where the image curves strongly in two directions at once — exactly a blob. Here D_xx is the box-filter approximation of the second derivative in the horizontal direction, D_yy in the vertical, and D_xy the mixed (diagonal) second derivative — each computed as a small pattern of rectangle sums via the integral image. The weight w ≈ 0.9 corrects for the error of replacing smooth Gaussian derivatives with blocky boxes, so the approximate determinant still tracks the true one. When det(H_approx) is a local maximum in both space and scale, you have a SURF keypoint. The crucial payoff: because D_xx, D_yy, D_xy are just resizable box filters, reaching a larger scale means enlarging the box — not rebuilding a blurred image pyramid. That single substitution is most of SURF's speedup.

For the descriptor, SURF mirrors SIFT but stays box-filter-cheap. Around each keypoint it lays a square region (rotated to the keypoint's dominant orientation) and splits it into a 4×4 grid of 16 sub-regions. In each sub-region it samples Haar-wavelet responses — which are again just box filters measuring intensity change in x and y, computed by integral-image lookups — and accumulates four numbers: Σdx, Σdy, Σ|dx|, Σ|dy|. That is 16 sub-regions × 4 values = a compact 64-D vector (half of SIFT's 128). It is still floating-point, so matching uses L2 distance, but it is computed and compared roughly twice as fast as SIFT.

BRIEF: Describing with Yes/No Tests

SURF made the float descriptor smaller and faster, but it is still a float vector. BRIEF (Binary Robust Independent Elementary Features) asks a bolder question: what if a descriptor were just a list of yes/no answers? Around a keypoint, fix a pattern of pixel pairs in advance. For each pair, ask one simple question — 'is pixel A darker than pixel B?' — and record a single bit: 1 for yes, 0 for no. Stack those bits into a string. With 256 pairs you get a 256-bit descriptor, which is only 32 bytes per keypoint. Compare that to SIFT's 128 floats (512 bytes): a 16× memory cut, before we even talk about speed.

One binary test per pixel-pair; the descriptor d is the string of n such bits.

Unpack it: p is the image patch around the keypoint; a and b are two fixed sample locations inside it (chosen once, e.g. by a random Gaussian pattern, and reused for every keypoint). I(a) and I(b) are the (smoothed) intensities at those points. The test τ outputs 1 when a is darker than b, else 0. The full descriptor d is the ordered tuple of n such tests, e.g. n = 256, so d is a 256-bit string. The pattern is identical for all keypoints, which is what makes two descriptors directly comparable bit-by-bit. (Note: BRIEF blurs the patch first so single-pixel noise does not flip a bit.)

Hamming distance: XOR the two bit strings, then count the 1s.

To compare two binary descriptors d1 and d2 you use Hamming distance: the number of positions where their bits differ. The symbol ⊕ is bitwise XOR, which produces a 1 in exactly the positions where the two strings disagree; popcount (population count) then counts those 1s. The magic is the hardware: XOR-ing 256 bits is a handful of 64-bit machine words, and most CPUs have a single popcount instruction, so an entire descriptor comparison is a few instructions. Contrast that with L2 distance over 128 floats — 128 subtractions, 128 multiplications, and a sum, all in floating point. Binary matching is often an order of magnitude faster and uses far less memory bandwidth, which is exactly why it unlocks real-time video.

ORB: Oriented FAST + Rotated BRIEF

BRIEF is tiny and fast, but it has a glaring flaw: tilt the camera and the fixed pixel-pair pattern points at different content, so the bits scramble — it is not rotation-invariant. The ORB descriptor (Oriented FAST and Rotated BRIEF) fixes exactly this, and as a bonus it is completely patent-free (unlike SIFT and SURF historically). ORB has become the practical, free workhorse of real-time vision. It combines a fast corner detector with a steerable version of the BRIEF descriptor.

The detector is FAST (Features from Accelerated Segment Test). For a candidate pixel, look at the ring of 16 pixels on a small circle (radius 3) around it. If a contiguous arc of, say, 9 of those 16 are all brighter than the center plus a threshold (or all darker than center minus threshold), it is a corner. A clever shortcut tests just pixels 1, 5, 9, 13 first and rejects most flat patches instantly — that is what makes FAST fast. FAST alone gives lots of corners but no quality ranking, so ORB scores each with the Harris corner detector response and keeps the strongest. To handle scale, it runs FAST on an image pyramid (the same coarse-to-fine idea from Guide 2).

Now the rotation fix. To give each keypoint an orientation, ORB uses the intensity centroid: imagine the bright pixels in the patch as having mass, find their balance point, and the direction from the patch center to that balance point is the keypoint's angle. Then ORB rotates the entire BRIEF sampling pattern by that angle before running the tests, so the same physical structure is sampled the same way no matter how the camera is rotated.

Patch orientation from image moments via the intensity centroid.

Here m_pq is an image moment of the patch: sum over all patch pixels of x^p · y^q · I(x,y), where x and y are pixel coordinates (measured from the patch center) and I(x,y) is intensity. Three moments matter. m00 = Σ I is the total intensity (total 'mass'). m10 = Σ x·I and m01 = Σ y·I are intensity-weighted sums of the x- and y-coordinates. The centroid C divides each by m00 to get the average position weighted by brightness — the patch's 'center of mass'. The orientation θ = atan2(m01, m10) is simply the angle of the vector from the patch center to that centroid (atan2 returns the correct angle in all four quadrants). Steer every BRIEF pair by θ — rotate each sample point by θ around the center — and the bit string becomes rotation-invariant. ORB also uses rBRIEF: instead of random pairs, it learns from training data a set of 256 tests that are high-variance (informative) and low-correlation (non-redundant), making the descriptor more discriminative. This combination is what powers systems like ORB-SLAM, which tracks a camera through the world in real time on ordinary hardware.

Local Binary Patterns: Texture in a Byte

The Local Binary Pattern (LBP) is binary like BRIEF, but aimed at a different job. BRIEF and ORB describe sparse keypoints for matching across views. LBP instead describes texture — the fine structure of a surface (fabric, bark, skin) — and is famous for face recognition. The idea: at every pixel, compare its ring of neighbors to itself, turn those comparisons into a binary number (one code per pixel), and then summarize a whole region by the histogram of these codes. The descriptor is not the codes themselves but how often each code occurs — which is why it captures the statistical 'feel' of a texture rather than a single point.

The LBP code at one pixel: threshold each neighbor against the center, then read the bits as a binary number.

Decode it: g_c is the center pixel's intensity. g_p (for p = 0…P−1) are the P neighbors sampled on a circle of radius R around it — for example P = 8 neighbors at radius R = 1 is just the 3×3 ring. The step function s(z) outputs 1 if the neighbor is greater than or equal to the center, else 0. Each neighbor thus contributes one bit, and we weight bit p by 2^p and sum, turning the ring of comparisons into a single integer code (0–255 when P = 8 — exactly one byte). Notice it compares relative brightness, so adding a constant to the whole patch (a lighting change) leaves the code unchanged: LBP is invariant to monotonic intensity shifts, which is gold for real-world lighting.

# Worked 3x3 LBP example, P = 8, R = 1.
# Patch (center g_c = 50), neighbors read clockwise from top-left:
#   80  99  11
#   84  50  20
#   12  33  70
g_c = 50
# order p = 0..7 : TL, T, TR, R, BR, B, BL, L
neighbors = [80, 99, 11, 20, 70, 33, 12, 84]
bits = [1 if g >= g_c else 0 for g in neighbors]   # -> [1,1,0,0,1,0,0,1]
code = sum(b * (2 ** p) for p, b in enumerate(bits))
print(code)        # 1 + 2 + 16 + 128 = 147
# As a byte (b7..b0) = 1001 0011 = 147

Per the example, neighbors ≥ 50 give bits (p0…p7) = 1,1,0,0,1,0,0,1, and the weighted sum 2^0 + 2^1 + 2^4 + 2^7 = 1 + 2 + 16 + 128 = 147 — one byte describing the local micro-texture around that pixel. Now sweep this over a region and build a histogram with 256 bins counting how many pixels produced each code: that histogram is the LBP texture descriptor (and a face is described by concatenating histograms from a grid of facial cells). Two refinements you will meet: uniform LBP keeps only codes with at most two 0↔1 transitions around the ring (these capture edges, spots, and corners and cover most real patterns) and lumps the rest into one bin, shrinking 256 bins to 59; rotation-invariant LBP rotates each code to its smallest value so the descriptor does not change when the texture spins.

Choosing a Descriptor: A Practical Map

You now have a toolbox of four fast alternatives plus the SIFT baseline. The right choice depends on a handful of axes: how fast each is to compute, how fast to match, how much memory it costs, how robust/accurate it is, and — critically — which distance metric it requires. Float descriptors live in Euclidean space and use L2 distance; binary descriptors live in bit-space and use Hamming distance. Pick the wrong metric and matching silently fails.

Descriptor | Type   | Compute | Matching     | Memory       | Distance | Rotation | Best for
-----------|--------|---------|--------------|--------------|----------|----------|------------------------
SIFT       | float  | slow    | slow         | 128 floats   | L2       | yes      | max accuracy, offline
SURF       | float  | medium  | medium       | 64 floats    | L2       | yes      | speed/accuracy balance
BRIEF      | binary | fast    | very fast    | 32 bytes     | Hamming  | NO       | upright, controlled view
ORB        | binary | fast    | very fast    | 32 bytes     | Hamming  | yes      | real-time, mobile, SLAM
LBP        | binary | fast    | histogram    | small hist.  | chi-sq.  | variant  | texture, face recognition

Concrete guidance: reach for the SIFT descriptor when accuracy is everything and you compute offline (image stitching of a fixed dataset, 3D reconstruction, benchmarks). Reach for the ORB descriptor for anything real-time, mobile, or embedded — it is the default for SLAM and AR because it is fast, rotation-invariant, and patent-free. Use the SURF descriptor as a middle ground when you want more accuracy than ORB but more speed than SIFT and licensing is not a concern. Use the plain BRIEF descriptor only when you can guarantee an upright, roughly fixed viewpoint (e.g. a fixed scanner) and want the absolute minimum cost. And use the local binary pattern when the task is texture classification or face recognition rather than point matching.

We now have detectors (corners, blobs) and descriptors (SIFT, SURF, BRIEF, ORB, LBP) — the full vocabulary for turning an image into a set of comparable fingerprints. But a descriptor is only useful once you actually match it across images and reject the inevitable bad matches. That is exactly the next guide: matching strategies (brute-force and approximate nearest neighbor), the ratio test, RANSAC to find a geometrically consistent set of matches, and finally stitching images together into a panorama. Everything you chose here — float vs binary, L2 vs Hamming — feeds directly into how that matching is done.