EP08_01 — 🟢 Distance de Hamming et correspondance de descripteurs binaires

8.14.1 EP08_01 🟢 Distance de Hamming et correspondance de descripteurs binaires

L’ORB, utilisé dans le Projet Pratique 1 de ce chapitre, décrit le voisinage de chaque point d’intérêt comme une séquence de bits — et, par conséquent, la comparaison entre deux descripteurs n’utilise pas la distance euclidienne du k-NN du Chapitre 7, mais plutôt la distance de Hamming : le nombre de positions où les bits diffèrent. Avant d’appeler cv2.BFMatcher(cv2.NORM_HAMMING), vous avez été chargé d’implémenter manuellement cette correspondance (matching) par force brute — la même étape qui, exécutée en interne par OpenCV, précède l’estimation robuste de l’homographie par RANSAC.

8.14.1.1 📋 Directives d’implémentation

Quantités : Lire les entiers \(N\) et \(M\) — nombre de descripteurs extraits de l’image A et de l’image B, respectivement.
Descripteurs de A : Lire \(N\) lignes, chacune contenant un descripteur binaire (une chaîne de caractères 0 et 1, tous de même longueur).
Descripteurs de B : Lire \(M\) lignes, dans le même format.
Seuil : Lire l’entier \(\tau\) — distance de Hamming maximale acceptable pour considérer une correspondance valide.
Distance de Hamming : Pour deux descripteurs binaires \(a\) et \(b\) de même longueur, \[ d_H(a, b) = \sum_{k} \mathbb{1}[a_k \neq b_k], \] c’est-à-dire le nombre de positions où les bits diffèrent.
Correspondance par voisin le plus proche : Pour chaque descripteur \(a_i\) de A (\(i\) dans l’ordre de lecture, commençant à \(0\)), calculer sa distance de Hamming à tous les descripteurs de B et trouver celui de distance minimale. En cas d’égalité entre deux ou plusieurs descripteurs de B avec la même distance minimale, choisir celui de plus petit indice.
Filtrage par seuil : Si la distance minimale trouvée est \(\le \tau\), la correspondance est valide ; sinon, \(a_i\) n’a pas de correspondance.
Sortie : Pour chaque \(i\) de \(0\) à \(N-1\), dans l’ordre de lecture, imprimer une ligne : i j d s’il existe une correspondance valide (où \(j\) est l’indice du descripteur de B choisi et \(d\) sa distance), ou i -1 sinon. À la fin, imprimer Total correspondances valides : X.

8.14.1.2 📌 Contraintes computationnelles

Même longueur : tous les descripteurs (de A et de B) ont exactement le même nombre de bits.
Force brute : comparer chaque descripteur de A à tous ceux de B — aucune indexation ni structure d’accélération n’est nécessaire.
Départage par plus petit indice en B, et jamais par ordre de lecture de A (qui est déjà naturel, car chaque \(a_i\) est traité de manière indépendante).

8.14.1.3 🧠 Fondement théorique

Élément	Rôle dans la correspondance ORB
Descripteur binaire (BRIEF)	Chaque bit est le résultat d’une comparaison d’intensité entre deux pixels du voisinage
Distance de Hamming	Métrique de dissimilarité entre chaînes binaires ; beaucoup plus rapide à calculer que la distance euclidienne (opération XOR + comptage de bits)
Voisin le plus proche	Critère de correspondance : chaque point de A est apparié au point de B avec le descripteur le plus similaire
Seuil \(\tau\)	Filtre les correspondances peu fiables avant même le RANSAC — mais, comme discuté dans le chapitre, certaines correspondances incorrectes passent encore, exigeant la robustesse du RANSAC

8.14.1.4 📦 Spécification d’entrée et de sortie (VPL)

Entrée :

Ligne 1 : Entiers \(N\) et \(M\).
\(N\) lignes suivantes : un descripteur binaire par ligne (chaîne de 0 et de 1).
\(M\) lignes suivantes : un descripteur binaire par ligne, dans le même format.
Dernière ligne : Entier \(\tau\).

Sortie :

\(N\) lignes, une par descripteur de A, au format i j d ou i -1.
Dernière ligne : Total correspondances valides : X.

8.14.1.5 📌 Exemples

Entrée	Sortie	Observation
3 3 10101010 11110000 00001111 10101011 00001110 11111111 2	0 0 1 1 -1 2 1 1 Total correspondances valides : 2	Le descripteur `11110000` ne trouve pas de correspondance : son voisin le plus proche est à distance 4, au-dessus du seuil \(\tau=2\).

🎮 Simulateur EP08_01 : Distance de Hamming entre descripteurs binaires Descripteurs de 8 bits

Cliquez sur n'importe quel bit du Descripteur B pour l'inverser et observez la distance de Hamming changer en temps réel.

Descripteur A (Fixe)

Descripteur B (Cliquer pour inverser)

–

Figure 8.15: Simulateur EP08_01 : Distance de Hamming entre deux descripteurs binaires

%%writefile EP08_01.py
# Code Python

Overwriting EP08_01.py

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

✔️ EP08_01.cases existe déjà dans casos/
📋 6 cas chargé(s) depuis casos/EP08_01.cases

🔍 Test de Python : EP08_01.py
⚠️ EP08_01.py : fichier vide (moins de 3 lignes). Tests ignorés.