brief descriptor

BRIEF, Binary Robust Independent Elementary Features, introduced by Michael Calonder and colleagues in 2010, was the descriptor that showed you can describe an image patch with a string of single bits and still match reliably, opening the era of fast binary descriptors. The idea is almost startlingly simple: pick a fixed set of pixel-pair locations inside a patch, and for each pair write down a single bit that says whether the first pixel is brighter than the second. Concatenate those bits and you have the descriptor. There is no histogram, no gradient, no normalization, just a few hundred brightness comparisons.

To make this work in practice, the patch is first smoothed (typically with a small Gaussian or box blur) because raw pixel comparisons are extremely sensitive to noise, and a single noisy pixel could flip many bits. The set of pixel-pair locations is chosen once, in advance, by sampling from a distribution concentrated near the patch centre, and the same pattern is used for every keypoint. A typical BRIEF descriptor uses 256 comparisons, giving a 256-bit (32-byte) string, though 128-bit and 512-bit variants exist. The descriptor is therefore both tiny to store and trivial to compute.

The killer advantage is matching speed. Two binary descriptors are compared by Hamming distance, the number of bit positions at which they differ, which a modern CPU computes with an exclusive-or followed by a population-count instruction, processing 64 bits at a time. Comparing two 256-bit descriptors thus takes a handful of machine instructions, orders of magnitude faster than the floating-point Euclidean distance between two 128-dimensional SIFT vectors. This is what made real-time matching on modest hardware feasible.

BRIEF's honest limitation is that, as defined, it is not invariant to rotation or scale: rotate the patch and the fixed comparison pattern no longer samples corresponding pixels, so the bit string changes and matches fail. It is therefore best paired with a detector that supplies a canonical orientation and scale. This is exactly the gap ORB filled by steering the BRIEF pattern with a keypoint orientation (rotated BRIEF) and learning a decorrelated pattern. Later binary descriptors such as BRISK and FREAK refined the sampling pattern further. BRIEF remains the conceptual ancestor of all of them and an excellent choice when patches are already roughly aligned, as in frame-to-frame tracking.