skip to content

Why must matching ORB descriptors use cv2.NORM_HAMMING rather than NORM_L2?

level: middleimportance: must knowfreq 68%

answer

  1. encoding decides the distance function
  2. bits versus magnitudes
  3. packed bytes are not numbers
  4. popcount is the reason it is fast
  5. WTA_K changes the answer

basics

~20 s

ORB emits binary descriptors — 256 comparison bits packed into 32 uint8 bytes — so distance means counting differing bits, which is what cv2.NORM_HAMMING does. NORM_L2 treats those packed bytes as numeric magnitudes, producing meaningless distances. SIFT's float32 vectors need NORM_L2.

solid answer

~50 s

The norm has to match how the descriptor encodes information. `cv2.ORB_create()` produces a `(N, 32)` uint8 array where each byte packs eight independent binary intensity comparisons; similarity is the number of bits that disagree, so `cv2.BFMatcher(cv2.NORM_HAMMING)` is correct and is also extremely fast via a popcount instruction. `cv2.SIFT_create()` produces a `(N, 128)` float32 gradient-histogram vector, where each dimension is a real magnitude and Euclidean distance is meaningful, so you pass `cv2.NORM_L2`. Applying L2 to ORB's packed bytes does not compare bits at all — byte 0b11111111 and 0b00000000 differ by 8 bits but by 255 in value, while 0b10000000 and 0b01111111 differ by 8 bits and by 1 in value — so the ranking is nonsense and matches look random. AKAZE's default MLDB descriptor is also binary and also takes Hamming. One wrinkle: if you build ORB with `WTA_K=3` or `4`, the descriptor is no longer a plain bit string and you must use `cv2.NORM_HAMMING2`.

code

python · 16 lines
python
import cv2
import numpy as np

a = np.zeros((240, 240), np.uint8)
cv2.rectangle(a, (60, 60), (180, 180), 255, -1)
cv2.circle(a, (120, 120), 30, 80, -1)
M = cv2.getRotationMatrix2D((120, 120), 12, 1.0)
b = cv2.warpAffine(a, M, (240, 240))

orb = cv2.ORB_create()
k1, d1 = orb.detectAndCompute(a, None)
k2, d2 = orb.detectAndCompute(b, None)
print(d1.dtype, d1.shape[1])           # uint8 32  -> binary, 256 bits

bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)
print(len(bf.match(d1, d2)))

go deeper

for a junior

Remember the pairing: ORB and other binary descriptors go with cv2.NORM_HAMMING, SIFT's float descriptors go with cv2.NORM_L2, and check des.dtype if you are unsure.

for a middle

Explain why packed bits are not magnitudes, with a concrete byte pair showing that equal Hamming distance can give wildly different L2 distance, and mention NORM_HAMMING2 for WTA_K above 2.

for a senior

Treat this as a silent-failure class: no exception is raised, so your defence is monitoring the post-RANSAC inlier ratio rather than the raw match count, and asserting descriptor dtype at pipeline boundaries.

for a principal

Own the encoding choice as an architecture decision — binary descriptors buy roughly an order of magnitude in memory and matching throughput at some accuracy cost, and that choice then constrains the index type, the norm and the storage format everywhere downstream.

## Two families of descriptor Every classical descriptor summarises the patch around a keypoint as a fixed-length vector, but there are two incompatible encodings. **Float descriptors** such as SIFT's are histograms. SIFT divides the oriented patch into a 4x4 grid, builds an 8-bin gradient-orientation histogram in each cell, and concatenates them into 128 float32 numbers. Each dimension is a magnitude on a continuous scale, so the natural comparison is Euclidean distance, `cv2.NORM_L2`. Storage is 128 x 4 = 512 bytes per keypoint. **Binary descriptors** such as ORB's rBRIEF are the outcome of a fixed set of pairwise pixel-intensity tests inside the patch: is point A brighter than point B, yes or no. ORB runs 256 such tests by default and packs the answers into 32 uint8 bytes. Nothing about a byte's numeric value is meaningful — it is a container for eight independent booleans. The natural comparison is how many of the 256 answers disagree, which is the Hamming distance, `cv2.NORM_HAMMING`. Storage is 32 bytes per keypoint, sixteen times smaller than SIFT. ## Why the wrong norm is silently wrong Hamming distance and Euclidean distance over packed bits are not merely different scalings of each other; they are uncorrelated. Consider two single-byte descriptors: - 0b11111111 versus 0b00000000: every bit disagrees. Hamming distance 8 — maximally different. L2 over byte values: 255. - 0b10000000 versus 0b01111111: every bit also disagrees. Hamming distance 8 — equally maximally different. L2 over byte values: 1, which reads as almost identical. So an L2 matcher on ORB descriptors will confidently rank a completely dissimilar pair as the nearest neighbour. The failure has no exception attached to it: you get a full list of `DMatch` objects with plausible-looking distances, the ratio test dutifully filters some, and RANSAC then fails to find a homography or, worse, locks onto a spurious one. This is the archetypal silent-wrong-answer bug in a matching pipeline. ## What each detector needs - `cv2.SIFT_create()` — float32, 128-D, use `cv2.NORM_L2`. - `cv2.ORB_create()` — uint8 binary, 32 bytes, use `cv2.NORM_HAMMING`. - `cv2.ORB_create(WTA_K=3)` or `WTA_K=4` — each element encodes the index of the brightest of three or four points rather than a single bit, so use `cv2.NORM_HAMMING2`, which compares in 2-bit groups. - `cv2.AKAZE_create()` with the default MLDB descriptor — binary, use `cv2.NORM_HAMMING`. AKAZE can be constructed with a float descriptor type instead, in which case L2 applies; the constructor argument decides. - `cv2.BRISK_create()` — binary, Hamming. When in doubt, print `des.dtype` and `des.shape[1]`: uint8 with a small width means binary and Hamming, float32 means L2. Do not infer it from the algorithm's reputation. ## The FLANN consequence The same split reaches the approximate matcher. `cv2.FlannBasedMatcher` is configured with an index type. The KD-tree index (`algorithm=1` in the index params dict) expects CV_32F data and will not accept ORB's uint8 array; the LSH index (`algorithm=6`, with `table_number`, `key_size` and `multi_probe_level`) is the one built for binary descriptors. The common workaround of casting ORB descriptors with `.astype(np.float32)` to force them through a KD-tree makes the code run, but it reintroduces exactly the numeric-magnitude fallacy above — the tree partitions on byte values, not bits. Use LSH, or use a brute-force Hamming matcher, which is fast enough for a few thousand descriptors because popcount is a single CPU instruction. ## Why this trade exists at all Binary descriptors were designed for the case where SIFT is too expensive: mobile and real-time pipelines. You give up some matching accuracy under large viewpoint or scale change, and you gain roughly an order of magnitude in both memory and matching throughput. Picking Hamming is not an incidental detail of that trade — it is the mechanism that makes the trade pay off, since counting disagreeing bits over 256 bits costs a handful of XOR and popcount operations against 128 float subtractions, squarings and a sum.

  • What changes if you construct ORB with WTA_K=4?
    Each descriptor element then encodes which of four sampled points is brightest, so it is a 2-bit symbol rather than a single independent bit. Plain Hamming over raw bits would double-count a single symbol disagreement, so OpenCV provides cv2.NORM_HAMMING2, which compares in 2-bit groups. Pass that to the matcher instead.
  • Can you feed ORB descriptors to cv2.FlannBasedMatcher?
    Yes, but only with an LSH index (algorithm 6, configured with table_number, key_size and multi_probe_level). The KD-tree index expects CV_32F data. Casting ORB's uint8 array to float32 to satisfy a KD-tree compiles and runs but partitions on byte magnitudes rather than bits, which reproduces the wrong-norm bug.
  • Why is a brute-force Hamming matcher often fast enough in practice?
    Because the distance is an XOR followed by a population count over 32 bytes — a couple of CPU instructions per comparison, against 128 float subtractions, squarings and a sum for SIFT. For a few thousand descriptors per image the quadratic brute-force cost stays in the sub-millisecond range, so an approximate index only earns its complexity at much larger scale.
  • How would you notice the wrong norm was used, given nothing raises?
    Watch the inlier ratio after RANSAC, not the raw match count. A correct pipeline on a genuinely overlapping pair typically retains a substantial fraction of matches as inliers; a wrong-norm pipeline returns plenty of matches whose inlier count collapses to near the four-point minimum, and findHomography either fails or produces a wildly distorted warp.

A binary descriptor is a 256-question yes/no answer sheet. Comparing two sheets means counting how many answers differ, not subtracting the two sheets' page numbers.

saying these in an interview costs you the question

  • Using NORM_L2 for ORB because it is the default
  • Casting binary descriptors to float32 to satisfy FLANN
  • Believing the byte value of a binary descriptor is meaningful
  • Assuming a wrong norm raises an error
  • Forgetting NORM_HAMMING2 when WTA_K is 3 or 4

context

resolving links…