TNI+VO · Exercice de Programmation

EP08_02 — 🟢 Homographie et RANSAC : Le vote par inliers

8.14.2 EP08_02 🟢 Homographie et RANSAC : Le vote par inliers

Le RANSAC, présenté dans la section « Modélisation mathématique : Homographie et RANSAC », répète un cycle de trois étapes — tirer un échantillon minimal, estimer un modèle candidat, et compter combien de correspondances sont cohérentes avec lui (les inliers) — en conservant à la fin le modèle le plus voté. L’étape d’estimation du modèle à partir de 4 points (étape 2) implique une algèbre linéaire qui sort du cadre de cet EP ; ici, vous recevez directement un ensemble d’homographies déjà candidates — comme si chacune avait été estimée à partir d’un échantillon aléatoire différent — et vous êtes chargé de reproduire exactement l’étape décisive de l’algorithme : appliquer chaque modèle à toutes les correspondances et compter ses inliers, en choisissant le gagnant.

8.14.2.1 📋 Directives d’implémentation

  1. Correspondances : Lire l’entier \(N\) puis \(N\) lignes contenant chacune quatre réels, \(x\ y\ x'\ y'\) — un point de l’image A et son correspondant (éventuellement incorrect) dans l’image B, exactement comme produit par l’étape de matching de l’EP08_01.
  2. Modèles candidats : Lire l’entier \(K\) (nombre d’homographies candidates) et le réel \(\varepsilon\) (seuil d’erreur de reprojection). Ensuite, lire \(K\) lignes, chacune avec neuf réels \(h_{11}\ h_{12}\ h_{13}\ h_{21}\ h_{22}\ h_{23}\ h_{31}\ h_{32}\ h_{33}\) — les éléments de la matrice \(H\) candidate, en ordre de lecture par ligne (row-major).
  3. Reprojection : Pour chaque correspondance \((x,y,x',y')\) et chaque modèle candidat \(H_k\), calculer le point projeté \[ \begin{bmatrix} \hat x \\ \hat y \\ \hat w \end{bmatrix} = H_k \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}, \qquad (\hat x / \hat w,\ \hat y / \hat w)\ \text{est le point projeté.} \]
  4. Erreur de reprojection : \(e = \sqrt{(\hat x/\hat w - x')^2 + (\hat y /\hat w - y')^2}\).
  5. Comptage des inliers : Une correspondance est un inlier du modèle \(H_k\) si \(e \le \varepsilon\).
  6. Sélection du meilleur modèle : Le modèle gagnant est celui ayant le plus grand nombre d’inliers ; en cas d’égalité, choisissez celui de plus petit indice \(k\) (le premier trouvé pendant le cycle itératif du RANSAC).
  7. Sortie : Pour chaque modèle \(k\) de \(0\) à \(K-1\), dans l’ordre de lecture, imprimer Modelo k: I inliers. À la fin, imprimer Melhor modelo: k_best com I_best inliers.

8.14.2.2 📌 Contraintes computationnelles

  • Comparaison inclusive : une erreur de reprojection exactement égale à \(\varepsilon\) compte comme inlier (\(e \le \varepsilon\)).
  • Sans estimation de \(H\) : les matrices sont déjà fournies prêtes — il n’est pas nécessaire (ni attendu) de résoudre un quelconque système linéaire.
  • Égalité résolue par le plus petit indice, reflétant le comportement naturel d’un algorithme itératif qui parcourt les modèles dans l’ordre et ne remplace le meilleur trouvé jusqu’alors que lorsqu’un nouveau modèle le dépasse strictement.

8.14.2.3 🧠 Fondement théorique

Élément Rôle dans le RANSAC
Échantillon minimal (4 paires) Suffisant pour déterminer les 8 degrés de liberté d’une homographie
Modèle candidat \(H_k\) Estimé à partir d’un échantillon minimal ; peut être bon ou mauvais, selon que l’échantillon contenait des outliers
Erreur de reprojection Mesure à quel point le modèle « prédit » chaque correspondance observée
Inlier vs. outlier Correspondances cohérentes avec le modèle gagnant (inliers) vs. les autres, typiquement des correspondances incorrectes du matching
Raffinement final En pratique, après avoir choisi le meilleur modèle, le RANSAC le recalcule en utilisant uniquement ses inliers — étape non exigée dans cet EP

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

Entrée :

  • Ligne 1 : Entier \(N\).
  • \(N\) lignes suivantes : quatre réels \(x\ y\ x'\ y'\).
  • Ligne suivante : Entier \(K\) et réel \(\varepsilon\).
  • \(K\) lignes suivantes : neuf réels (éléments de \(H_k\), row-major).

Sortie :

  • \(K\) lignes au format Modelo k: I inliers.
  • Dernière ligne : Melhor modelo: k_best com I_best inliers.

8.14.2.5 📌 Exemples

Entrée Sortie Observation
5
0 0 0 0
1 1 2 2
2 0 4 0
0 2 0 4
5 5 1 1
2 0.5
2 0 0 0 2 0 0 0 1
1 0 0 0 1 0 0 0 1		 Modelo 0: 4 inliers
Modelo 1: 1 inliers
Melhor modelo: 0 com 4 inliers		 Le Modèle 0 (échelle ×2) explique correctement 4 des 5 correspondances ; la 5ᵉ, \((5,5)\to(1,1)\), est un outlier qu’aucun des deux modèles n’explique bien.
🎮 Simulateur EP08_02 : RANSAC — Comptage des inliers Modèle : Échelle ×2
Le modèle candidat mappe (x,y) → à (2x,2y). Ajustez le seuil ε et observez quelles correspondances deviennent des inliers ou des outliers.
–
Figure 8.16: Simulateur EP08_02: RANSAC — Vote par Inliers entre Modèles Candidats 
%%writefile EP08_02.py
# Code Python
Overwriting EP08_02.py
TestSuite("EP08_02.py").run()
✔️ EP08_02.cases existe déjà dans casos/
📋 6 cas chargé(s) depuis casos/EP08_02.cases

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