EP08_01 — 🟢 Distanza di Hamming e Corrispondenza di Descrittori Binari

8.14.1 EP08_01 🟢 Distanza di Hamming e Corrispondenza di Descrittori Binari

L’ORB, utilizzato nel Progetto Pratico 1 di questo capitolo, descrive l’intorno di ogni punto di interesse come una sequenza di bit — e, per questo, il confronto tra due descrittori non usa la distanza euclidea del k-NN del Capitolo 7, bensì la distanza di Hamming: il numero di posizioni in cui i bit differiscono. Prima di chiamare cv2.BFMatcher(cv2.NORM_HAMMING), ti è stato richiesto di implementare manualmente questa corrispondenza (matching) per forza bruta — la stessa fase che, eseguita internamente da OpenCV, precede la stima robusta dell’omografia tramite RANSAC.

8.14.1.1 📋 Linee Guida di Implementazione

Quantità: Leggere gli interi \(N\) e \(M\) — numero di descrittori estratti dall’immagine A e dall’immagine B, rispettivamente.
Descrittori di A: Leggere \(N\) righe, ciascuna contenente un descrittore binario (una stringa di caratteri 0 e 1, tutti della stessa lunghezza).
Descrittori di B: Leggere \(M\) righe, nello stesso formato.
Soglia: Leggere l’intero \(\tau\) — distanza di Hamming massima accettabile per considerare valida una corrispondenza.
Distanza di Hamming: Per due descrittori binari \(a\) e \(b\) della stessa lunghezza, \[ d_H(a, b) = \sum_{k} \mathbb{1}[a_k \neq b_k], \] cioè il conteggio delle posizioni in cui i bit differiscono.
Corrispondenza per vicino più prossimo: Per ogni descrittore \(a_i\) di A (\(i\) nell’ordine di lettura, a partire da \(0\)), calcola la sua distanza di Hamming da tutti i descrittori di B e trova quello con la distanza minima. In caso di parità tra due o più descrittori di B con la stessa distanza minima, scegli quello con indice minore.
Filtraggio tramite soglia: Se la distanza minima trovata è \(\le \tau\), la corrispondenza è valida; altrimenti, \(a_i\) non ha corrispondenza.
Output: Per ogni \(i\) da \(0\) a \(N-1\), nell’ordine di lettura, stampare una riga: i j d se esiste una corrispondenza valida (dove \(j\) è l’indice del descrittore di B scelto e \(d\) la sua distanza), oppure i -1 in caso contrario. Alla fine, stampare Total correspondências válidas: X.

8.14.1.2 📌 Vincoli Computazionali

Stessa lunghezza: tutti i descrittori (di A e di B) hanno esattamente lo stesso numero di bit.
Forza bruta: confronta ogni descrittore di A con tutti quelli di B — non è necessaria alcuna indicizzazione o struttura di accelerazione.
Pareggio risolto per indice minore in B, e mai per ordine di lettura di A (che è già naturale, poiché ogni \(a_i\) è trattato in modo indipendente).

8.14.1.3 🧠 Fondamenti Teorici

Elemento	Ruolo nella corrispondenza ORB
Descrittore binario (BRIEF)	Ogni bit è il risultato di un confronto di intensità tra due pixel dell’intorno
Distanza di Hamming	Metrica di dissimmetria tra stringhe binarie; molto più rapida da calcolare rispetto alla distanza euclidea (operazione XOR + conteggio dei bit)
Vicino più prossimo	Criterio di corrispondenza: ogni punto di A è accoppiato al punto di B con descrittore più simile
Soglia \(\tau\)	Filtra corrispondenze poco affidabili ancor prima del RANSAC — ma, come discusso nel capitolo, alcune corrispondenze errate passano comunque, richiedendo la robustezza del RANSAC

8.14.1.4 📦 Specifica di Input e Output (VPL)

Input:

Riga 1: Interi \(N\) e \(M\).
Prossime \(N\) righe: un descrittore binario per riga (stringa di 0 e 1).
Prossime \(M\) righe: un descrittore binario per riga, nello stesso formato.
Ultima riga: Intero \(\tau\).

Output:

\(N\) righe, una per descrittore di A, nel formato i j d o i -1.
Ultima riga: Total correspondências válidas: X.

8.14.1.5 📌 Esempi

Input	Output	Osservazione
3 3 10101010 11110000 00001111 10101011 00001110 11111111 2	0 0 1 1 -1 2 1 1 Total correspondências válidas: 2	Il descrittore `11110000` non trova corrispondenza: il suo vicino più prossimo è a distanza 4, superiore alla soglia \(\tau=2\).

🎮 Simulatore EP08_01: Distanza di Hamming tra Descrittori Binari Descrittori a 8 Bit

Clicca su qualsiasi bit del Descrittore B per invertirlo e osserva la distanza di Hamming cambiare in tempo reale.

Descrittore A (Fisso)

Descrittore B (Clicca per Invertire)

–

Figura 8.15: Simulatore EP08_01: Distanza di Hamming tra Due Descrittori Binari

%%writefile EP08_01.py
# Codice Python

Overwriting EP08_01.py

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

✔️ EP08_01.cases esiste già in casos/
📋 6 caso/i caricato/i da casos/EP08_01.cases

🔍 Test di Python: EP08_01.py
⚠️ EP08_01.py: file vuoto (meno di 3 righe). Test saltati.