Hamming Distance Matcher

You’re implementing brute-force feature matching for binary descriptors using Hamming distance plus Lowe’s ratio test. Conceptually, this is exactly how ORB/BRIEF/FREAK descriptors are typically matched in CV libraries: binary descriptors are compared bitwise, and nearest-neighbor matches are accepted only if the best match is clearly better than the second best (ratio test), which helps reject ambiguous or repetitive features.

Binary descriptors encode local image patterns as bit strings (e.g., 256 bits), where each bit is the result of a simple intensity comparison test around a keypoint. Matching then becomes efficient because Hamming distance can be computed with a fast XOR + popcount on machine words. The ratio test, introduced by Lowe in SIFT, generalizes here: even though SIFT uses Euclidean distance and ORB/BRIEF use Hamming, the idea is the same—features that have similarly good multiple matches are unreliable and should be discarded.

---

1. Background Knowledge

• Binary descriptors & Hamming distance A binary descriptor is a fixed-length bit vector, often represented as an array of bytes/ints. The Hamming distance between two descriptors $a$ and $b$ of the same length is:

$$d_H(a, b) = \sum_i (a_i \oplus b_i)$$

where $a_i \oplus b_i = 1$ if bits differ and $0$ otherwise, so $d_H$ counts differing bits.

• Nearest-neighbor matching Given two sets of descriptors $A = \{a_1,\dots,a_m\}$ and B = \{b_1,\dots,b_n\}$, a simple matcher finds, for each$a_i$, the **nearest neighbor** in$B$w.r.t. Hamming distance (and also the second nearest). This is usually done via a brute-force scan over all descriptors in$B$.

• Lowe’s ratio test for ambiguity Many keypoints may look similar (e.g., in repetitive textures). If the best and second-best matches have very similar distances, the match is ambiguous. Lowe’s ratio test keeps a match only if:

$$\frac{\text{best\_dist}}{\text{second\_best\_dist}} < \text{threshold}$$

Typical thresholds are around $0.7$–$0.8$ (problem may specify). This dramatically reduces false matches, at the cost of discarding some good ones.

---

2. Algorithm / General Approach

The standard pattern for binary descriptor matching with ratio test:

1. For each descriptor in A, compare it to all descriptors in B.
2. Compute Hamming distance for each pair using XOR + popcount over all words of the descriptor.
3. Track the smallest and second smallest distances for that query descriptor.
4. Apply ratio test: if best_dist / second_best_dist < threshold, accept the pair (index_in_A, index_of_best_in_B) as a match.
5. Collect all accepted matches into a list.

This is a brute-force $O(|A|\cdot|B|)$ NN search in Hamming space, which is acceptable for typical contest constraints unless the sets are huge.

---

3. Step-by-Step Strategy

Assume you have:

• A: list/array of descriptors, shape [NA][D]
• B: list/array of descriptors, shape [NB][D] Where each descriptor is a binary string stored as bytes/ints (e.g., vector<uint8_t> or vector<uint32_t>).

Step 1: Hamming distance function

Implement a function to compute Hamming distance between two descriptors:

• Represent each descriptor as an array of machine words (8-bit/32-bit/64-bit).
• For each word index k:
• xor_word = a[k] ^ b[k]
• count += popcount(xor_word) (use built-in bit-popcount if available).
• Return the total count.

Example in C++-like pseudocode:

int hammingDist(const uint8_t* a, const uint8_t* b, int bytes) {
 int dist = 0;
 for (int i = 0; i < bytes; ++i) {
 uint8_t x = a[i] ^ b[i];
 dist += __builtin_popcount((unsigned)x); // or custom popcount
 }
 return dist;
}