Binary Descriptors

A binary descriptor describes the neighbourhood of a keypoint with a string of bits, each the answer to a yes-or-no question about the image there, most often “is the smoothed intensity at point $a$ lower than at point $b$?”. Two descriptors are compared by the Hamming distance, the number of bits in which they differ, which a processor computes with an XOR and a population count. Binary descriptors trade some distinctiveness for speed and memory: a 256-bit string takes 32 bytes, and comparing two of them costs a few machine instructions, where a SIFT descriptor holds 128 numbers compared by a Euclidean distance. BRIEF (Calonder, Lepetit, Strecha and Fua, 2010) compares random point pairs; ORB added orientation and learned tests, BRISK and FREAK use fixed patterns of concentric rings, and later work learned the tests or the whole binary code from data. The feature descriptors article places the family among other descriptors; this article covers what the members share, how they differ, how they are matched in practice and what the number of bits buys.

Definition

A binary descriptor is a function that maps an image and a keypoint to a fixed-length bit string $\mathbf{b} \in \{0, 1\}^n$, where each bit is computed by a fixed binary test on the image region around the keypoint, and where descriptors are compared by the Hamming distance. The tests are usually comparisons of two smoothed intensities at fixed offsets from the keypoint, measured in a frame given by the keypoint’s position and, where the method provides them, its scale and orientation. Learned binary descriptors replace the comparisons with thresholded functions of the patch, such as boosted combinations of gradient features, but keep the bit string and the Hamming distance.

Intuition

A single comparison of two intensities says very little: whichever point is brighter, half of all patches would agree. Hundreds of comparisons at different places, however, form a fingerprint. Two views of the same scene point answer most questions the same way, because a change of brightness or contrast moves both intensities of a pair together and leaves their order alone. Two different scene points agree on about half the questions by chance, like two strings of coin tosses. Matching is therefore a matter of counting disagreements: a few for the same point, about $n/2$ for different points.

Three things decide how well the fingerprint works. Each comparison must be stable: if the two intensities are nearly equal, noise flips the answer, which is why every method smooths the image before comparing. Each comparison must be informative, answering 1 for about half of all keypoints rather than nearly always 0. And the comparisons must be different from each other: a hundred questions that all ask, in effect, “is the left side darker than the right?” carry the information of one. The members of the family differ mainly in where they place the comparisons and how they choose them.

Formal Definition

Let $S_\sigma I$ denote the image smoothed at scale $\sigma$ and let $(\mathbf{x}_i, \mathbf{y}_i)$, $i = 1, \ldots, n$, be fixed offsets in the keypoint’s frame. BRIEF-style descriptors set

$$b_i = \begin{cases} 1 & \text{if } S_\sigma I(\mathbf{k} + \mathbf{x}_i) < S_\sigma I(\mathbf{k} + \mathbf{y}_i), \\ 0 & \text{otherwise,} \end{cases}$$

for a keypoint at $\mathbf{k}$; ring patterns such as BRISK and FREAK give each sample point its own smoothing scale. The ORB article gives BRIEF’s sampling distribution and how ORB steers and learns the tests. The normalized Hamming distance between descriptors $\mathbf{a}$ and $\mathbf{b}$ is

$$h(\mathbf{a}, \mathbf{b}) = \frac{1}{n} \sum_{i=1}^{n} a_i \oplus b_i ,$$

and similarity and distance measures covers it as a metric.

Expected distances. Suppose bit $i$ equals 1 for a fraction $\mu_i$ of keypoints. For two descriptors of unrelated keypoints whose bits are independent, the bits differ with probability $2\mu_i(1 - \mu_i)$, the relation Balntas, Tang and Mikolajczyk (2015) use to tie a test’s variance to the distances it produces. The mean non-matching distance is $\frac{1}{n}\sum_i 2\mu_i(1-\mu_i)$, at most $1/2$, reached when every test splits the keypoints evenly. For two views of the same point, bit $i$ flips with some probability $q_i$ that grows as the two compared intensities get closer relative to noise, and the mean matching distance is $\frac{1}{n}\sum_i q_i$.

Distinctiveness and the number of bits. A convenient summary of how well matching and non-matching distances separate is the sensitivity index

$$d' = \frac{\bar h_{\text{non-match}} - \bar h_{\text{match}}}{\sqrt{\tfrac{1}{2}\left(\operatorname{Var} h_{\text{non-match}} + \operatorname{Var} h_{\text{match}}\right)}} .$$

If the $n$ bits were independent, both means would stay fixed as bits are added while both standard deviations shrink as $1/\sqrt{n}$, so $d'$ would grow as $\sqrt{n}$, by a factor of $\sqrt{2}$ per doubling (our derivation). Correlated bits grow the spread less: the biometrics article describes how Daugman measured this for iris codes by the number of independent coin tosses that would give the observed spread of non-matching distances,

$$n_{\text{eff}} = \frac{\bar h (1 - \bar h)}{\operatorname{Var} h}, \quad h \text{ over non-matching pairs},$$

which he called degrees of freedom. The same statistic applies to any binary descriptor.

A bound for ring patterns. BRISK and FREAK compute all their bits from comparisons among a fixed set of $k$ smoothed sample values (60 for BRISK, 43 for FREAK in OpenCV’s patterns). Without ties, every outcome of every pairwise comparison is determined by the ranking of the $k$ values, so such a descriptor can take at most $k!$ distinct values and carries at most $\log_2 k!$ bits of information, however many pairs it uses: about 272 bits for 60 points and 175 for 43 (our reasoning). BRIEF’s random pairs touch up to $2n$ different points, so no such bound applies to it at $n = 512$.

Properties

Photometric invariance. A comparison between two smoothed intensities of the same patch is unchanged when the patch’s intensities are multiplied by a positive gain and shifted by an offset, since smoothing is linear and both values change alike (our reasoning; the ORB article makes the same point). No normalization step is needed, unlike for raw patches. A nonlinear monotonic change, such as a gamma curve, preserves the order of single pixels exactly but the order of smoothed averages only approximately. Large lighting changes that are not monotonic over the patch, such as moving shadows or specular highlights, change the answers.

Geometric invariance by the frame. A test has no invariance of its own to rotation or scale: it compares fixed offsets. BRIEF uses an upright frame and fails under in-plane rotation, as the ORB article shows. ORB, BRISK and FREAK estimate an orientation and rotate the sampling pattern before testing, and BRISK and FREAK scale the pattern with the keypoint’s scale. The descriptor is then as invariant as the orientation and scale estimates are accurate, as for gradient-histogram descriptors.

Noise and smoothing. Smoothing protects the comparisons: averaging over a region of $m$ pixels divides the noise standard deviation by $\sqrt{m}$, and the ORB example shows that dropping the box smoothing costs a quarter to a third of the correct matches. Ring patterns smooth more at larger radii. In OpenCV’s code, BRISK’s smoothing scale at a ring of radius $r$ with $N$ points is $1.3\, r \sin(\pi/N)$, proportional to the spacing of the points on the ring, and FREAK’s is half the ring radius, so its receptive fields overlap; both evaluate the smoothed values as box averages on an integral image, falling back to bilinear interpolation of single pixels when the scale is below half a pixel.

Bits are not independent. Tests that share a sample point, or sample nearby points of a smooth image, give correlated answers. Correlation lowers $n_{\text{eff}}$ and slows the growth of distinctiveness with $n$. This is why ORB and FREAK select their tests for variance and low correlation instead of using all candidate pairs, and why doubling the bit count of a random-pair descriptor gains much less than $\sqrt{2}$ in practice, as the example below shows.

Cost. A descriptor of $n$ bits needs $n$ comparisons of precomputed smoothed values. A Hamming distance between 256-bit strings is four 64-bit XORs and population counts. Trzcinski, Christoudias, Fua and Lepetit (2013) measured 0.32 µs per BRIEF distance against 33.2 µs per SIFT distance on 100,000 pairs on an Intel i7 laptop CPU with the POPCOUNT instruction (their Fig. 6), with floating-point descriptors stored as unsigned characters for a fair comparison.

The Family

BRIEF: random pairs

BRIEF compares smoothed intensities at point pairs drawn once, at random, and reused for every keypoint. The ORB article describes its sampling strategies, the Gaussian pattern it adopted, its smoothing and its bit lengths of 128, 256 and 512, and the rotation failure that ORB’s steering addresses. Two implementations differ in detail. OpenCV’s BriefDescriptorExtractor compares $9 \times 9$ box sums from an integral image inside a $48 \times 48$ patch and offers 16, 32 or 64 bytes. scikit-image 0.25.2’s BRIEF smooths the image with a Gaussian (σ = 1 by default), draws pairs from a Gaussian with standard deviation $S/5$ for a patch of side $S = 49$, discards samples that fall outside the patch, and accepts other lengths, 256 by default, with 128, 256 and 512 named in its docstring as the sizes the BRIEF authors recommend; its pairs are fixed by a seed, so descriptors are comparable only when extracted with the same seed.

The choice of pairs matters more than it appears. Balntas et al. (2015) drew five sets of Gaussian BRIEF tests with different random seeds and found that the 95% error rate on single classes of the Trevi patch set varied strongly between sets, one set being best on one class and worst on another (their Fig. 2), which led them to adapt the tests to each patch, described below.

BRISK: concentric rings, short and long pairs

BRISK (Leutenegger, Chli and Siegwart, 2011) is a detector and descriptor. OpenCV’s implementation, which carries a copyright notice of the authors’ laboratory at ETH Zurich and calls itself the reference implementation, defines the default sampling pattern as 60 points: one at the centre and rings of 10, 14, 15 and 20 points at radii $0.85 \times (2.9, 4.9, 7.4, 10.8)$ pixels for a keypoint of base size, scaled with the keypoint. The 1,770 point pairs split by length. The 870 long pairs, more than 8.2 units apart, estimate the orientation: each contributes the intensity difference of its two points times the direction between them divided by its squared length, a local gradient, and the orientation is the angle of the sum. The 512 short pairs, closer than 5.85 units, form the descriptor after the pattern is rotated by that orientation, one bit per pair, set when one point of the pair is brighter than the other, in a fixed order. The pairs in between are not used. The detector, which OpenCV parametrizes by a detection threshold for AGAST, a variant of the FAST corner detector, and a number of octaves, finds keypoints in a scale space and assigns them a scale, so the descriptor’s pattern grows with the keypoint.

FREAK: a retina-like pattern and selected pairs

FREAK (Alahi, Ortiz and Vandergheynst, 2012) is a descriptor only, used with any detector. OpenCV’s header describes it as inspired by the human retina and its bits as a cascade of binary strings. Its implementation, from the authors’ laboratory at EPFL, places 43 points: seven rings of six points, staggered by half a step from ring to ring, and one at the centre, with radii shrinking towards the centre and each point smoothed over a region proportional to its ring radius, so the sampling is dense and fine near the centre and coarse and overlapping at the edge. The 43 points give 903 pairs. A selectPairs routine computes all 903 bits on training keypoints, orders the pairs by how close their mean is to 0.5, and adds them greedily, skipping any pair whose correlation with an already selected one reaches a threshold (0.7 by default), until 512 are chosen; the default 512 pairs ship as a list. Orientation comes from 45 pairs of points on the same rings, in the same way as BRISK’s long pairs. This is the same variance-and-correlation criterion that ORB’s rBRIEF uses, applied to a fixed pattern instead of to all pairs of sub-windows.

Selecting and learning tests

Selection by variance and low correlation produces a fixed set of tests chosen on a training set, a global choice. BOLD (Balntas et al., 2015) adds a per-patch step. Offline, it ranks pixel-pair tests on a grid of patch locations ($32 \times 32$ in their example) by variance over many patches and keeps a fixed number, for example 512, whose mutual correlation stays below a threshold such as 0.2, following ORB’s greedy procedure. Online, it applies each test to a few synthetic affine warps of the patch, done by transforming the test locations through lookup tables rather than warping the image, and marks as valid only the tests whose answer does not change. On average about half the tests survived per patch (their Fig. 5). Two descriptors are compared by a masked Hamming distance, the disagreements among each descriptor’s valid tests divided by their number and summed over both. On Yosemite patches the overlap between matching and non-matching distance distributions fell from about 14% with the global tests to 9.75% with the per-patch masks; the figure caption gives 13.97% for the first value and the text 13.95%.

Learned descriptors go further and learn what each bit measures. BinBoost (Trzcinski et al., 2013) makes each bit the sign of a boosted combination of gradient-orientation weak learners pooled over learned regions, trained on matching and non-matching patch pairs so that successive bits correct each other’s errors. OpenCV’s contrib module also ships BEBLID and TEBLID, whose header describes them as boosted (BEBLID) or triplet-trained (TEBLID) binary descriptors built from differences of mean grey values in image regions, trained on the Liberty patch set, with 256 or 512 bits; and LATCH, which its header describes as learned comparisons of triplets of small patches. DeepBit (Lin, Lu, Chen and Zhou, 2016) trains a neural network without labels to output binary codes under three criteria: small quantization loss, evenly distributed codes and uncorrelated bits.

Matching in Practice

Brute force. For a few thousand keypoints, exhaustive matching is fast: $N_1 N_2$ Hamming distances, each a handful of XOR and population-count instructions. OpenCV and scikit-image (match_descriptors with metric="hamming") both provide it with an optional cross-check that keeps only mutual nearest neighbours. Lowe’s ratio test can be applied as for float descriptors, and feature matching covers both filters. A practical difference from floating-point descriptors is that Hamming distances are integers between 0 and $n$, so ties are common, and a strict “nearest is closer than second-nearest” rule rejects them.

Indexing. For large databases, the bits themselves are hash keys: locality-sensitive hashing for the Hamming distance simply samples bits, and ORB’s authors used multi-probe LSH over their learned tests, whose even bit statistics give evenly filled buckets (described in the ORB article). FLANN adds hierarchical clustering trees for binary descriptors, and the approximate nearest-neighbour search article covers the trade-offs. For place recognition, binary descriptors are quantized into a vocabulary of binary words; DBoW2 does this for BRIEF and ORB, as described under loop closure.

Thresholds. Because the non-matching distance concentrates near $n/2$ with a spread set by $n_{\text{eff}}$, a fixed Hamming threshold can work within one descriptor and one kind of imagery. It does not transfer between descriptors of different lengths or bit statistics, and the ratio test is less sensitive to that (our reasoning).

Evaluation

Results depend heavily on the protocol, and published comparisons disagree. The HPatches authors (Balntas, Lenc, Vedaldi and Mikolajczyk, 2017) list contradictory published conclusions about the same descriptors on the same Oxford benchmark, among them BRISK against SIFT and ORB against BRIEF (their Table 1), and attribute them to unstated choices such as the feature detector.

On the Brown et al. patch data used by BinBoost, matching and non-matching patch pairs are scored by the 95% error rate, the false-positive rate at which 95% of matching pairs are accepted. Trained on Notre Dame and tested on Yosemite, Trzcinski et al. reported 54.96% for BRIEF (256 bits) and 73.21% for BRISK (512 bits), both with the authors’ implementations, against 29.15% for SIFT and 18.97% for 64-bit BinBoost (their Fig. 7 and Table 1). They counted floating-point descriptors at one byte per dimension (128 bytes for SIFT), stating that this quantization was reported to suffice for SIFT. With as few as 16 bits, BinBoost matched the next best binary descriptor in their comparison, BGM, whose length the text gives as 128 bits while their Table 1 and Fig. 7 list it at 64 bits (8 bytes); BinBoost’s own error stopped improving at about 64 bits (their Figs. 3 and 5).

HPatches evaluates 256-bit BRIEF, ORB and BinBoost against SIFT on patches from 116 image sequences; each value is the mean of six runs per task, three levels of geometric noise each under two experimental settings (their Fig. 4, mean average precision):

Descriptor	Patch verification	Image matching	Patch retrieval
BRIEF (256 bits)	58.07%	10.50%	16.03%
ORB (256 bits)	60.15%	15.32%	18.85%
BinBoost (256 bits)	66.67%	14.77%	22.45%
SIFT (128 floats)	65.12%	25.47%	31.98%

The binary descriptors were not post-processed, while SIFT and the learned float descriptors were also tested with ZCA whitening and power-law normalization, which raised them further. The authors concluded that binary descriptors were competitive only in patch verification and fell well behind SIFT in matching and retrieval, and that they may still be the best choice where speed and compactness matter more than accuracy.

Examples

The script below measures what bit count and sampling pattern buy, on patches whose correspondences are known exactly. Each scene is a dead-leaves image: 20,000 opaque disks with random grey levels in $[0, 1]$ and radii between 2 and 48 pixels with density proportional to $r^{-3}$, later disks covering earlier ones, rendered analytically with $4 \times 4$ supersampling at $384 \times 384$ pixels. The first view adds Gaussian noise of standard deviation 0.05. The second view renders the same scene through a known transform, multiplies it by a gain of 0.7, adds 0.1 and fresh noise of 0.05. Two conditions are compared: photometric, with no geometric change, and viewpoint, with the affine map $\mathbf{x}' = A(\mathbf{x} - \mathbf{c}) + \mathbf{c}$, $A = \begin{pmatrix} 1.08 & 0.06 \\ 0 & 0.96 \end{pmatrix}$, about the image centre $\mathbf{c}$ ($x$ is the column, $y$ the row). Each scene has 300 keypoints at random positions, not detected corners, so that the measurement concerns the descriptor alone. Their true positions in the second view are rounded to the nearest pixel, and no descriptor is rotated or rescaled.

All three patterns have the same support, a radius of 24 pixels:

• BRIEF-like: 512 Gaussian pairs drawn exactly as scikit-image’s BRIEF draws them for a 49-pixel patch, on the image smoothed with a Gaussian of σ = 2. The script checks its hand-written tests against scikit-image’s bit for bit.
• BRISK-like: OpenCV’s default 60-point pattern and its 512 short pairs, scaled so that the outer ring plus its smoothing scale reaches 24 pixels.
• FREAK-like: OpenCV’s 43-point pattern and its default list of 512 pairs, scaled the same way.

The ring patterns use Gaussian smoothing with each point’s scale and bilinear sampling, where OpenCV uses box averages, and no orientation is estimated. Shorter descriptors of 128 and 256 bits are nested random subsets of the 512 tests; for FREAK the prefixes of its default list, in the order OpenCV stores it, are printed as well. The float comparison at equal bytes projects the mean-subtracted, unit-norm $49 \times 49$ patch of the σ = 2 image onto its first 4, 8 or 16 principal components (16, 32 or 64 bytes as float32; principal component analysis learned on 2,000 patches of a separate scene), compared by Euclidean distance; the full normalized patch of 2,401 floats is a reference.

Four measures use all 300 matching and $300 \times 299$ non-matching pairs of each scene: $d'$ as defined above; FPR95, the share of non-matching pairs at or below the distance that accepts 95% of matching pairs; nearest-neighbour accuracy, the share of keypoints whose true partner is strictly closer than every other keypoint of the second view (ties count as failures); and, for binary descriptors, $n_{\text{eff}}$. The table gives means over scenes 0 to 4 and the range of $d'$. The script uses NumPy 2.3.5, SciPy 1.16.3 and scikit-image 0.25.2, runs in about 15 seconds, and two runs printed identical output.

import os
for v in ("OMP_NUM_THREADS", "OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS"):
    os.environ[v] = "1"                       # one BLAS thread, before NumPy loads
import sys
from math import lgamma, log
import numpy as np
from scipy import ndimage
import skimage.feature

SIZE, SS, HALF = 384, 4, 24                   # image size, supersampling, support radius
C = np.array([SIZE / 2, SIZE / 2])            # transforms act about the image centre

# ---------- scene: dead leaves (occluding disks, radius density ~ r^-3) ----------
def dead_leaves(seed, n=20000, rmin=2.0, rmax=48.0, lo=-60, hi=SIZE + 60):
    rng = np.random.default_rng(seed)
    u = rng.random(n)
    r = (rmin**-2 - u * (rmin**-2 - rmax**-2)) ** -0.5
    return rng.uniform(lo, hi, (n, 2)), r, rng.random(n)    # centres (x, y), radii, grey

def render(scene, A=np.eye(2)):
    """Render the scene seen through x' = A (x - c) + c, painting later disks on top."""
    centres, radii, grey = scene
    Ainv, smax = np.linalg.inv(A), np.linalg.norm(A, 2)
    img = np.full((SIZE * SS, SIZE * SS), np.nan)
    g = (np.arange(SIZE * SS) + 0.5) / SS - 0.5           # supersample centres, pixel units
    for (dx, dy), r, v in zip(centres, radii, grey):
        cx, cy = A @ (np.array([dx, dy]) - C) + C
        h = r * smax + 1
        c0, c1 = np.searchsorted(g, [cx - h, cx + h])
        r0, r1 = np.searchsorted(g, [cy - h, cy + h])
        if c0 >= c1 or r0 >= r1:
            continue
        X, Y = np.meshgrid(g[c0:c1] - C[0], g[r0:r1] - C[1])
        sx = Ainv[0, 0] * X + Ainv[0, 1] * Y + C[0] - dx       # scene offset from disk centre
        sy = Ainv[1, 0] * X + Ainv[1, 1] * Y + C[1] - dy
        win = img[r0:r1, c0:c1]
        win[sx**2 + sy**2 <= r**2] = v
    uncovered = np.isnan(img).mean()
    img = np.nan_to_num(img, nan=0.5)
    return img.reshape(SIZE, SS, SIZE, SS).mean(axis=(1, 3)), uncovered

def view(scene, A, gain, offset, noise, noise_seed):
    img, _ = render(scene, A)
    rng = np.random.default_rng(noise_seed)
    return gain * img + offset + rng.normal(0, noise, img.shape)

# ---------- three sampling patterns (offsets in pixels, x = column, y = row) ----------
def brief_pairs(n=512, patch=49, seed=1):
    """Gaussian pairs drawn exactly as scikit-image's BRIEF(mode='normal') draws them."""
    rng = np.random.default_rng(seed)
    s = np.array((patch / 5.0) * rng.standard_normal(n * 8), dtype=np.int32)
    s = s[(s < patch // 2) & (s > -(patch - 2) // 2)]
    return s[:n * 2].reshape(n, 2), s[n * 2:n * 4].reshape(n, 2)   # (row, col) offsets

def brisk_pattern():
    """OpenCV's default BRISK pattern: 60 points on 4 rings plus the centre."""
    f = 0.85
    radii, counts = [0.0, 2.9 * f, 4.9 * f, 7.4 * f, 10.8 * f], [1, 10, 14, 15, 20]
    pts, sig = [], []
    for r, n in zip(radii, counts):
        s = 1.3 * 0.5 if r == 0 else 1.3 * r * np.sin(np.pi / n)
        for k in range(n):
            a = 2 * np.pi * k / n
            pts.append((r * np.cos(a), r * np.sin(a))); sig.append(s)
    pts, sig = np.array(pts), np.array(sig)
    i, j = np.tril_indices(len(pts), -1)               # all pairs with j < i
    d = np.linalg.norm(pts[i] - pts[j], axis=1)
    short = d < 5.85                                    # descriptor pairs
    long_ = d > 8.2                                     # orientation pairs (not used here)
    scale = HALF / (np.linalg.norm(pts, axis=1) + sig).max()   # outer extent -> HALF
    return pts * scale, sig * scale, np.c_[i[short], j[short]], long_.sum()

# OpenCV's default FREAK pairs: indices into the 903 pairs (i, j < i) in OpenCV's order.
FREAK_DEF_PAIRS = [int(k) for k in """
404 431 818 511 181 52 311 874 774 543 719 230 417 205 11 560 149 265 39 306 165 857
250 8 61 15 55 717 44 412 592 134 761 695 660 782 625 487 549 516 271 665 762 392
178 796 773 31 672 845 548 794 677 654 241 831 225 238 849 83 691 484 826 707 122
517 583 731 328 339 571 475 394 472 580 381 137 93 380 327 619 729 808 218 213 459
141 806 341 95 382 568 124 750 193 749 706 843 79 199 317 329 768 198 100 466 613 78
562 783 689 136 838 94 142 164 679 219 419 366 418 423 77 89 523 259 683 312 555 20
470 684 123 458 453 833 72 113 253 108 313 25 153 648 411 607 618 128 305 232 301 84
56 264 371 46 407 360 38 99 176 710 114 578 66 372 653 129 359 424 159 821 10 323
393 5 340 891 9 790 47 0 175 346 236 26 172 147 574 561 32 294 429 724 755 398 787
288 299 769 565 767 722 757 224 465 723 498 467 235 127 802 446 233 544 482 800 318
16 532 801 441 554 173 60 530 713 469 30 212 630 899 170 266 799 88 49 512 399 23
500 107 524 90 194 143 135 192 206 345 148 71 119 101 563 870 158 254 214 276 464
332 725 188 385 24 476 40 231 620 171 258 67 109 844 244 187 388 701 690 50 7 850
479 48 522 22 154 12 659 736 655 577 737 830 811 174 21 237 335 353 234 53 270 62
182 45 177 245 812 673 355 556 612 166 204 54 248 365 226 242 452 700 685 573 14 842
481 468 781 564 416 179 405 35 819 608 624 367 98 643 448 2 460 676 440 240 130 146
184 185 430 65 807 377 82 121 708 239 310 138 596 730 575 477 851 797 247 27 85 586
307 779 326 494 856 324 827 96 748 13 397 125 688 702 92 293 716 277 140 112 4 80
855 839 1 413 347 584 493 289 696 19 751 379 76 73 115 6 590 183 734 197 483 217 344
330 400 186 243 587 220 780 200 793 246 824 41 735 579 81 703 322 760 720 139 480
490 91 814 813 163 152 488 763 263 425 410 576 120 319 668 150 160 302 491 515 260
145 428 97 251 395 272 252 18 106 358 854 485 144 550 131 133 378 68 102 104 58 361
275 209 697 582 338 742 589 325 408 229 28 304 191 189 110 126 486 211 547 533 70
215 670 249 36 581 389 605 331 518 442 822
""".split()]

def freak_pattern():
    """OpenCV's FREAK pattern: 43 points on 7 staggered rings of 6 plus the centre."""
    n = [6, 6, 6, 6, 6, 6, 6, 1]
    bigR, smallR = 2 / 3, 2 / 24
    u = (bigR - smallR) / 21
    radius = [bigR, bigR - 6 * u, bigR - 11 * u, bigR - 15 * u, bigR - 18 * u,
              bigR - 20 * u, smallR, 0.0]
    sigma = [r / 2 for r in radius[:7]] + [radius[6] / 2]
    pts, sig = [], []
    for ring in range(8):
        for k in range(n[ring]):
            a = 2 * np.pi * k / n[ring] + np.pi / n[ring] * (ring % 2)
            pts.append((radius[ring] * np.cos(a), radius[ring] * np.sin(a)))
            sig.append(sigma[ring])
    pts, sig = np.array(pts), np.array(sig)
    all_pairs = [(i, j) for i in range(1, 43) for j in range(i)]   # 903, OpenCV's order
    pairs = np.array([all_pairs[k] for k in FREAK_DEF_PAIRS])
    return pts * HALF, sig * HALF, pairs, len(all_pairs)            # outer extent r + sigma = 1



# ---------- descriptors ----------
def brief_bits(img, kp, pairs, sigma=2.0):
    sm = ndimage.gaussian_filter(img, sigma, mode="reflect", truncate=4.0)
    p1, p2 = pairs
    a = sm[kp[:, :1] + p1[None, :, 0], kp[:, 1:] + p1[None, :, 1]]
    b = sm[kp[:, :1] + p2[None, :, 0], kp[:, 1:] + p2[None, :, 1]]
    return a < b

def ring_bits(img, kp, pattern, ge):
    pts, sig, pairs = pattern[:3]
    vals = np.empty((len(kp), len(pts)))
    for s in np.unique(sig):                            # one blur per receptive-field size
        sm = ndimage.gaussian_filter(img, s, mode="reflect")
        idx = np.flatnonzero(sig == s)
        rows = kp[:, :1] + pts[None, idx, 1]
        cols = kp[:, 1:] + pts[None, idx, 0]
        vals[:, idx] = ndimage.map_coordinates(sm, [rows.ravel(), cols.ravel()],
                                               order=1).reshape(rows.shape)
    a, b = vals[:, pairs[:, 0]], vals[:, pairs[:, 1]]
    return a >= b if ge else a > b                      # FREAK uses >=, BRISK uses >

def patches(img, kp, sigma=2.0):
    sm = ndimage.gaussian_filter(img, sigma, mode="reflect", truncate=4.0)
    off = np.arange(-HALF, HALF + 1)
    P = sm[kp[:, 0, None, None] + off[:, None], kp[:, 1, None, None] + off[None, :]]
    P = P.reshape(len(kp), -1)
    P = P - P.mean(1, keepdims=True)
    return P / np.maximum(np.linalg.norm(P, axis=1, keepdims=True), 1e-12)

# ---------- distances and measures ----------
def hamming(B1, B2):
    p1, p2 = np.packbits(B1, axis=1), np.packbits(B2, axis=1)
    return np.bitwise_count(p1[:, None, :] ^ p2[None, :, :]).sum(axis=2) / B1.shape[1]

def euclid(F1, F2):
    F1, F2 = F1.astype(np.float64), F2.astype(np.float64)   # stored as float32, summed in float64
    D = (F1**2).sum(1)[:, None] + (F2**2).sum(1)[None, :] - 2 * F1 @ F2.T
    return np.sqrt(np.maximum(D, 0))

def measures(D, binary):
    m = np.diag(D)
    nm = D[~np.eye(len(D), dtype=bool)]
    dprime = (nm.mean() - m.mean()) / np.sqrt((nm.var() + m.var()) / 2)
    fpr95 = np.mean(nm <= np.quantile(m, 0.95, method="higher"))
    offd = np.where(np.eye(len(D), dtype=bool), np.inf, D)
    nn = np.mean(m < offd.min(axis=1))                 # strict: ties count as failures
    neff = nm.mean() * (1 - nm.mean()) / nm.var() if binary else np.nan
    return dprime, fpr95, nn, neff

# ---------- set-up ----------
BRISK, FREAK = brisk_pattern(), freak_pattern()
P1, P2 = brief_pairs()
pick = np.random.default_rng(7).permutation(512)       # nested random subsets of 512 tests
CONDITIONS = {
    "photometric": dict(A=np.eye(2), gain=0.7, offset=0.1, noise=0.05),
    "viewpoint": dict(A=np.array([[1.08, 0.06], [0.0, 0.96]]), gain=0.7, offset=0.1, noise=0.05),
}
N_KP = 300

def keypoints(seed, A):
    rng = np.random.default_rng(1000 + seed)
    xy = rng.uniform(56, SIZE - 56, (N_KP, 2))          # true positions (x, y), image 1
    xy2 = (xy - C) @ A.T + C                            # true positions, image 2
    to_rc = lambda p: np.rint(p[:, ::-1]).astype(int)    # nearest pixel, (row, col)
    return to_rc(xy), to_rc(xy2)

def pca_basis(k_max=16):
    train, _ = render(dead_leaves(99))                  # a separate training scene
    rng = np.random.default_rng(99)
    kp = rng.integers(HALF + 1, SIZE - HALF - 1, (2000, 2))
    P = patches(train + rng.normal(0, 0.05, train.shape), kp)
    P = P - P.mean(0)
    return np.linalg.svd(P, full_matrices=False)[2][:k_max]

def describe(img, kp, basis):
    """All descriptors of one image at its keypoints: name -> (array, binary?, bytes)."""
    out = {}
    bb = brief_bits(img, kp, (P1, P2))
    rb = ring_bits(img, kp, BRISK, ge=False)
    fb = ring_bits(img, kp, FREAK, ge=True)
    for n in (128, 256, 512):
        out[f"BRIEF-like {n}"] = (bb[:, pick[:n]], True, n // 8)
        out[f"BRISK-like {n}"] = (rb[:, pick[:n]], True, n // 8)
        out[f"FREAK-like {n}, random subset"] = (fb[:, pick[:n]], True, n // 8)
        out[f"FREAK-like {n}, list order"] = (fb[:, :n], True, n // 8)
    P = patches(img, kp)
    for k in (4, 8, 16):
        out[f"PCA float {k}"] = ((P @ basis[:k].T).astype(np.float32), False, 4 * k)
    out["full patch float"] = (P.astype(np.float32), False, 4 * P.shape[1])
    return out

def run(seeds):
    basis = pca_basis()
    res = {c: {} for c in CONDITIONS}
    for seed in seeds:
        scene = dead_leaves(seed)
        img1, unc = render(scene)
        img1 = img1 + np.random.default_rng(500 + seed).normal(0, 0.05, img1.shape)
        for cname, cond in CONDITIONS.items():
            kp1, kp2 = keypoints(seed, cond["A"])
            img2 = view(scene, cond["A"], cond["gain"], cond["offset"], cond["noise"], 600 + seed)
            d1, d2 = describe(img1, kp1, basis), describe(img2, kp2, basis)
            for name in d1:
                a, binary, nbytes = d1[name]
                D = hamming(a, d2[name][0]) if binary else euclid(a, d2[name][0])
                res[cname].setdefault(name, []).append((nbytes,) + measures(D, binary))
    return res

def report(res, seeds):
    for cname, rows in res.items():
        print(f"\n{cname}: mean over scenes {seeds[0]}-{seeds[-1]} (d' range in brackets)")
        print(f"{'descriptor':34}{'bytes':>6}{'d-prime':>18}{'FPR95':>8}{'NN acc':>8}{'n_eff':>7}")
        for name, vals in rows.items():
            v = np.array(vals)
            ne = "" if np.isnan(v[0, 4]) else f"{v[:, 4].mean():7.0f}"
            print(f"{name:34}{v[0, 0]:6.0f}{v[:, 1].mean():7.2f} [{v[:, 1].min():.2f}-{v[:, 1].max():.2f}]"
                  f"{v[:, 2].mean():8.3f}{v[:, 3].mean():8.3f}{ne}")

if __name__ == "__main__":
    seeds = [int(s) for s in sys.argv[1:]] or [0, 1, 2, 3, 4]
    print(f"BRISK-like: {len(BRISK[0])} points, {len(BRISK[2])} short pairs, {BRISK[3]} long pairs, "
          f"log2(60!) = {lgamma(61) / log(2):.0f} bits")
    print(f"FREAK-like: {len(FREAK[0])} points, {FREAK[3]} pairs, {len(set(FREAK_DEF_PAIRS))} in the "
          f"default list, log2(43!) = {lgamma(44) / log(2):.0f} bits")
    # Check: the hand-written BRIEF agrees bit for bit with scikit-image's.
    img, unc = render(dead_leaves(seeds[0]))
    kp, _ = keypoints(seeds[0], np.eye(2))
    ext = skimage.feature.BRIEF(descriptor_size=512, patch_size=49, mode="normal", sigma=2, rng=1)
    ext.extract(img, kp)
    mine = brief_bits(img, kp, (P1, P2))
    print(f"scene {seeds[0]}: uncovered share {unc:.5f}; skimage BRIEF keeps {ext.mask.sum()} of {N_KP} "
          f"keypoints, differing bits {np.sum(ext.descriptors != mine[ext.mask])}")
    # Check: an identical second view gives zero matching distance for every descriptor.
    basis = pca_basis()
    d1 = describe(img, kp, basis)
    d2 = describe(view(dead_leaves(seeds[0]), np.eye(2), 1.0, 0.0, 0.0, 0), kp, basis)
    worst = max(np.diag(hamming(d1[k][0], d2[k][0]) if d1[k][1] else euclid(d1[k][0], d2[k][0])).max()
                for k in d1)
    print(f"identical view: largest matching distance over all descriptors {worst:.1e}")
    report(run(seeds), seeds)

BRISK-like: 60 points, 512 short pairs, 870 long pairs, log2(60!) = 272 bits
FREAK-like: 43 points, 903 pairs, 512 in the default list, log2(43!) = 175 bits
scene 0: uncovered share 0.00151; skimage BRIEF keeps 300 of 300 keypoints, differing bits 0
identical view: largest matching distance over all descriptors 6.8e-08

photometric: mean over scenes 0-4 (d' range in brackets)
descriptor                         bytes           d-prime   FPR95  NN acc  n_eff
BRIEF-like 128                        16   5.84 [4.61-6.83]   0.005   0.965     27
BRISK-like 128                        16   6.12 [5.16-6.95]   0.002   0.969     28
FREAK-like 128, random subset         16   4.37 [3.90-4.77]   0.008   0.949     14
FREAK-like 128, list order            16   3.96 [3.52-4.31]   0.027   0.927     12
BRIEF-like 256                        32   6.22 [4.82-7.38]   0.002   0.972     31
BRISK-like 256                        32   6.54 [5.50-7.45]   0.001   0.975     32
FREAK-like 256, random subset         32   4.53 [4.04-4.97]   0.008   0.959     15
FREAK-like 256, list order            32   4.32 [3.81-4.71]   0.016   0.956     13
BRIEF-like 512                        64   6.32 [4.84-7.56]   0.004   0.971     33
BRISK-like 512                        64   6.67 [5.55-7.63]   0.001   0.980     34
FREAK-like 512, random subset         64   4.66 [4.12-5.12]   0.006   0.964     15
FREAK-like 512, list order            64   4.66 [4.12-5.12]   0.006   0.964     15
PCA float 4                           16   4.07 [3.98-4.18]   0.000   0.985
PCA float 8                           32   5.81 [5.50-5.98]   0.000   0.989
PCA float 16                          64   8.12 [7.38-8.63]   0.000   0.989
full patch float                    9604  12.72 [10.96-13.99]   0.000   0.989

viewpoint: mean over scenes 0-4 (d' range in brackets)
descriptor                         bytes           d-prime   FPR95  NN acc  n_eff
BRIEF-like 128                        16   5.17 [4.23-5.98]   0.008   0.950     27
BRISK-like 128                        16   5.43 [4.53-6.09]   0.002   0.957     28
FREAK-like 128, random subset         16   4.07 [3.72-4.42]   0.014   0.929     14
FREAK-like 128, list order            16   3.69 [3.32-4.01]   0.027   0.901     11
BRIEF-like 256                        32   5.56 [4.48-6.45]   0.005   0.961     31
BRISK-like 256                        32   5.86 [4.89-6.64]   0.001   0.970     32
FREAK-like 256, random subset         32   4.22 [3.84-4.61]   0.008   0.950     14
FREAK-like 256, list order            32   4.02 [3.63-4.38]   0.013   0.947     13
BRIEF-like 512                        64   5.67 [4.54-6.65]   0.005   0.964     33
BRISK-like 512                        64   6.01 [4.97-6.87]   0.001   0.973     34
FREAK-like 512, random subset         64   4.34 [3.91-4.75]   0.008   0.955     15
FREAK-like 512, list order            64   4.34 [3.91-4.75]   0.008   0.955     15
PCA float 4                           16   3.78 [3.69-3.91]   0.001   0.907
PCA float 8                           32   5.24 [4.97-5.41]   0.000   0.971
PCA float 16                          64   7.08 [6.49-7.51]   0.000   0.980
full patch float                    9604   9.63 [8.54-10.44]   0.000   0.984

The checks come first. The pattern counts reproduce OpenCV’s: 512 short and 870 long pairs among BRISK’s 60 points, and 512 distinct pairs out of FREAK’s 903. The hand-written BRIEF agrees with scikit-image’s on every bit of all 300 keypoints, and on an identical second view every descriptor gives a matching distance of zero up to rounding, so the comparisons below measure the descriptors, not an error in the set-up.

More bits help little here. For every pattern and in both conditions, $d'$ rises from 128 to 256 to 512 bits, as the plan expected, but by factors of about 1.02 to 1.09 per doubling, far below the $\sqrt{2}$ that independent bits would give. The last column says why: the non-matching distances of 512-bit BRIEF-like descriptors spread like those of about 33 independent bits, and FREAK-like descriptors like about 15. In our reading, dead-leaves patches are made of a few uniform regions, so many tests compare the same two leaves and repeat each other; a random 128-bit subset already samples most of the distinct comparisons a patch offers.

The pattern matters more than the length. The BRISK-like pattern is slightly ahead of the BRIEF-like pairs at every length and in both conditions, and gains at least as much from 256 to 512 bits: about 2.0% in $d'$ against 1.6% for BRIEF-like under the photometric change, and 2.6% against 2.0% under the viewpoint change (our arithmetic from the table). The hypothesis written before the run, that the ring patterns would gain less from extra bits than random pairs because their bits come from only 60 or 43 values, therefore failed for BRISK-like and for FREAK-like alike, in both conditions: all three gained a few per cent, and the FREAK-like random subsets gained more than BRIEF-like. The other part of that hypothesis, that $n_{\text{eff}}$ at 512 bits would order BRIEF-like above BRISK-like above FREAK-like, also failed, since BRISK-like (34) is slightly above BRIEF-like (33) in both conditions; only FREAK-like is clearly lowest. Its $n_{\text{eff}}$ of about 15 is far below the $\log_2 43! \approx 175$ bound, so the bound is not what limits it; in our reading, its large, overlapping receptive fields make neighbouring samples similar, so many of its comparisons are close calls or repeat each other. Prefixes of FREAK’s default list are less distinctive than random subsets of the same size at 128 and 256 bits in both conditions; that list comes with OpenCV and was not chosen on these images, and on these patches its first tests are not the most useful. At 512 bits the two FREAK variants contain the same tests and print identical values, as they must.

Floats of equal size. In both conditions, at 16 and 32 bytes, the BRIEF-like and BRISK-like descriptors separate matches better than the 4- and 8-component PCA floats; the FREAK-like descriptor does so only at 16 bytes with a random subset, and falls below PCA at 32 bytes. At 64 bytes, 16 principal components beat every binary descriptor in both conditions. The hypothesis that every binary descriptor would beat the float of equal bytes therefore holds only in part, for the smaller budgets and the better patterns. The comparison counts four bytes per float; at the one byte per dimension that Trzcinski et al. assumed, the floats would be four times shorter still. The full patch, at 9,604 bytes, has by far the largest $d'$ under the photometric change, as the plan expected for a descriptor that keeps every pixel, and also under the viewpoint change.

Viewpoint. The affine change lowers $d'$ for every descriptor. The drop is about 10% for the BRIEF-like and BRISK-like descriptors at 512 bits, about 7% for FREAK-like and 13% for 16-component PCA, and 24% for the full patch, which compares pixels at fixed positions and suffers most from their displacement. The hypothesis that the FREAK-like pattern, with the coarsest smoothing, would lose less than the BRIEF-like pairs held at every length, though it remained the least distinctive pattern in absolute terms.

Two measures saturate. FPR95 is at most 0.027 and nearest-neighbour accuracy between 0.90 and 0.989 for every descriptor, so on this data they barely separate descriptors that $d'$ separates clearly: a set of 300 keypoints is easy to match even with 128 bits. Even the full patch does not reach an accuracy of 1. In our reading, some keypoints fall inside a leaf larger than the descriptor’s support, where the patch holds nothing but noise, so no descriptor of it can find its partner; the script does not print how many such keypoints there are.

Common Misconceptions

• “Binary descriptors are invariant to illumination.” A test is unchanged by a gain and an offset of the whole patch, and by a monotonic change only approximately once intensities are smoothed. Shadows across the patch, saturation and changes that reverse local contrast flip tests. The HPatches authors reported that image-matching results on sequences with photometric changes were consistently lower than on sequences with viewpoint changes.
• “More bits are always better.” Extra tests add information only if they are stable and not redundant. In the example, doubling from 256 to 512 bits raised $d'$ by a few per cent, and BinBoost’s error stopped improving at about 64 learned bits.
• “A 256-bit descriptor carries 256 bits of information.” Correlated tests carry less, measured here by $n_{\text{eff}}$; and a descriptor built from comparisons among $k$ sample values cannot carry more than $\log_2 k!$ bits, however many pairs it uses.
• “Binary means less accurate than float.” At equal storage, a binary descriptor can separate matches better than a float descriptor compressed to the same number of bytes, as at 16 and 32 bytes in the example, and learned binary codes such as BinBoost reported lower error than SIFT on Brown et al.’s patches. On HPatches, however, the binary descriptors fell well behind SIFT in matching and retrieval.
• “The Hamming distance is only for intensity comparisons.” It applies to any bit string; the census transform used in stereo matching and the iris codes of biometrics are compared the same way, though they are not keypoint descriptors.

Where It Is Used

• Real-time SLAM and visual odometry, where ORB descriptors serve tracking, mapping and relocalization in ORB-SLAM, and where BRIEF descriptors in DBoW2 detect loops, as in visual–inertial odometry systems.
• Place recognition and loop closure with vocabularies of binary words, which index binary descriptors as bag of visual words indexes SIFT.
• Mobile and embedded matching, panorama stitching and augmented reality, where memory and matching time are scarce.
• Large-scale matching, where short codes make databases small and Hamming distances cheap, with hashing or tree indexes for search.
• Benchmarks and baselines: BRIEF and BRISK served as baselines in BinBoost’s evaluation, and BRIEF and ORB in HPatches’.