EP08_01 — 🟢 Hamming Distance and Binary Descriptor Matching

8.14.1 EP08_01 🟢 Hamming Distance and Binary Descriptor Matching

ORB, used in Practical Project 1 of this chapter, describes the neighborhood of each keypoint as a sequence of bits — and, therefore, the comparison between two descriptors does not use the Euclidean distance of the k-NN from Chapter 7, but rather the Hamming distance: the number of positions in which the bits differ. Before calling cv2.BFMatcher(cv2.NORM_HAMMING), you were tasked with manually implementing this brute-force matching — the same step that, when executed internally by OpenCV, precedes the robust homography estimation by RANSAC.

8.14.1.1 📋 Implementation Guidelines

Quantities: Read the integers \(N\) and \(M\) — the number of descriptors extracted from image A and image B, respectively.
Descriptors from A: Read \(N\) lines, each containing a binary descriptor (a string of characters 0 and 1, all of the same length).
Descriptors from B: Read \(M\) lines, in the same format.
Threshold: Read the integer \(\tau\) — the maximum acceptable Hamming distance for a match to be considered valid.
Hamming Distance: For two binary descriptors \(a\) and \(b\) of the same length, \[ d_H(a, b) = \sum_{k} \mathbb{1}[a_k \neq b_k], \] i.e., the count of positions in which the bits differ.
Nearest-neighbor matching: For each descriptor \(a_i\) from A (\(i\) in reading order, starting at \(0\)), compute its Hamming distance to all descriptors from B and find the one with the smallest distance. In case of a tie between two or more descriptors from B with the same minimum distance, choose the one with the smallest index.
Threshold filtering: If the smallest distance found is \(\le \tau\), the match is valid; otherwise, \(a_i\) has no corresponding match.
Output: For each \(i\) from \(0\) to \(N-1\), in reading order, print a line: i j d if there is a valid match (where \(j\) is the index of the chosen descriptor from B and \(d\) its distance), or i -1 otherwise. At the end, print Total correspondências válidas: X.

8.14.1.2 📌 Computational Constraints

Same length: all descriptors (from A and B) have exactly the same number of bits.
Brute force: compare each descriptor from A to all those from B — no indexing or acceleration structure is required.
Tie-breaking by smallest index in B, and never by the reading order of A (which is already natural, since each \(a_i\) is handled independently).

8.14.1.3 🧠 Theoretical Foundation

Element	Role in ORB matching
Binary descriptor (BRIEF)	Each bit is the result of an intensity comparison between two pixels in the neighborhood
Hamming distance	Dissimilarity metric between binary strings; much faster to compute than the Euclidean distance (XOR operation + bit counting)
Nearest neighbor	Matching criterion: each point from A is paired with the point from B whose descriptor is most similar
Threshold \(\tau\)	Filters unreliable matches even before RANSAC — but, as discussed in the chapter, some incorrect matches still pass, requiring the robustness of RANSAC

8.14.1.4 📦 Input and Output Specification (VPL)

Input:

Line 1: Integers \(N\) and \(M\).
Next \(N\) lines: one binary descriptor per line (string of 0s and 1s).
Next \(M\) lines: one binary descriptor per line, in the same format.
Last line: Integer \(\tau\).

Output:

\(N\) lines, one per descriptor from A, in the format i j d or i -1.
Last line: Total correspondências válidas: X.

8.14.1.5 📌 Examples

Input	Output	Observation
3 3 10101010 11110000 00001111 10101011 00001110 11111111 2	0 0 1 1 -1 2 1 1 Total correspondências válidas: 2	The descriptor `11110000` has no match: its nearest neighbor is at distance 4, above the threshold \(\tau=2\).

🎮 Simulator EP08_01: Hamming Distance between Binary Descriptors 8-Bit Descriptors

Click any bit of the Descriptor B to flip it and watch the Hamming distance change in real time.

Descriptor A (Fixed)

Descriptor B (Click to Flip)

–

Figure 8.15: EP08_01 Simulator: Hamming Distance Between Two Binary Descriptors

%%writefile EP08_01.py
# Python code

Overwriting EP08_01.py

TestSuite("EP08_01.py").run()

✔️ EP08_01.cases already exists in casos/
📋 6 case(s) loaded from casos/EP08_01.cases

🔍 Testing Python: EP08_01.py
⚠️ EP08_01.py: Empty file (fewer than 3 lines). Tests skipped.