EDI+VA · Esercizio di Programmazione

EP08_02 — 🟢 Omografia e RANSAC: Il Voto per Inlier

8.14.2 EP08_02 🟢 Omografia e RANSAC: Il Voto per Inlier

Il RANSAC, presentato nella sezione “Modellazione Matematica: Omografia e RANSAC”, ripete un ciclo di tre passaggi — selezionare un campione minimo, stimare un modello candidato e contare quante corrispondenze sono coerenti con esso (gli inlier) — conservando alla fine il modello più votato. La fase di stima del modello a partire da 4 punti (passo 2) coinvolge algebra lineare che esula dallo scopo di questo EP; qui ricevi direttamente un insieme di omografie già candidate — come se ciascuna fosse stata stimata da un campione casuale diverso — e sei incaricato di riprodurre esattamente il passo decisivo dell’algoritmo: applicare ogni modello a tutte le corrispondenze e contare i suoi inlier, scegliendo il vincitore.

8.14.2.1 📋 Linee Guida di Implementazione

  1. Corrispondenze: Leggere l’intero \(N\) e, successivamente, \(N\) righe con quattro reali ciascuna, \(x\ y\ x'\ y'\) — un punto dell’immagine A e il suo corrispondente (possibilmente errato) nell’immagine B, esattamente come prodotto dalla fase di matching dell’EP08_01.
  2. Modelli candidati: Leggere l’intero \(K\) (numero di omografie candidate) e il reale \(\varepsilon\) (soglia di errore di riproiezione). Successivamente, leggere \(K\) righe, ciascuna con nove reali \(h_{11}\ h_{12}\ h_{13}\ h_{21}\ h_{22}\ h_{23}\ h_{31}\ h_{32}\ h_{33}\) — gli elementi della matrice \(H\) candidata, in ordine di lettura per righe (row-major).
  3. Riproiezione: Per ogni corrispondenza \((x,y,x',y')\) e ogni modello candidato \(H_k\), calcolare il punto proiettato \[ \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{è il punto proiettato.} \]
  4. Errore di riproiezione: \(e = \sqrt{(\hat x/\hat w - x')^2 + (\hat y /\hat w - y')^2}\).
  5. Conteggio degli inlier: Una corrispondenza è un inlier del modello \(H_k\) se \(e \le \varepsilon\).
  6. Selezione del modello migliore: Il modello vincitore è quello con il maggior numero di inlier; in caso di pareggio, scegli quello con indice minore \(k\) (il primo trovato durante il ciclo iterativo del RANSAC).
  7. Output: Per ogni modello \(k\) da \(0\) a \(K-1\), nell’ordine di lettura, stampare Modello k: I inliers. Alla fine, stampare Modello migliore: k_best con I_best inliers.

8.14.2.2 📌 Vincoli Computazionali

  • Confronto inclusivo: un errore di riproiezione esattamente uguale a \(\varepsilon\) conta come inlier (\(e \le \varepsilon\)).
  • Senza stima di \(H\): le matrici sono già fornite pronte — non è necessario (né previsto) risolvere alcun sistema lineare.
  • Pareggio risolto con l’indice minore, riflettendo il comportamento naturale di un algoritmo iterativo che esamina i modelli in ordine e sostituisce il migliore trovato finora solo quando un nuovo modello lo supera strettamente.

8.14.2.3 🧠 Fondamenti Teorici

Elemento Ruolo nel RANSAC
Campione minimo (4 coppie) Sufficiente per determinare gli 8 gradi di libertà di un’omografia
Modello candidato \(H_k\) Stimato da un campione minimo; può essere buono o cattivo, a seconda che il campione contenesse outlier
Errore di riproiezione Misura quanto bene il modello “prevede” ogni corrispondenza osservata
Inlier vs. outlier Corrispondenze coerenti con il modello vincitore (inlier) vs. le altre, tipicamente corrispondenze errate del matching
Rifinitura finale In pratica, dopo aver scelto il modello migliore, il RANSAC lo ricalcola usando solo i suoi inlier — passo non richiesto in questo EP

8.14.2.4 📦 Specifica di Input e Output (VPL)

Input:

  • Riga 1: Intero \(N\).
  • Prossime \(N\) righe: quattro reali \(x\ y\ x'\ y'\).
  • Riga successiva: Intero \(K\) e reale \(\varepsilon\).
  • Prossime \(K\) righe: nove reali (elementi di \(H_k\), row-major).

Output:

  • \(K\) righe nel formato Modello k: I inliers.
  • Ultima riga: Modello migliore: k_best con I_best inliers.

8.14.2.5 📌 Esempi

Input Output Osservazione
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		 Modello 0: 4 inliers
Modello 1: 1 inliers
Modello migliore: 0 con 4 inliers		 Il Modello 0 (scala ×2) spiega correttamente 4 delle 5 corrispondenze; la 5ª, \((5,5)\to(1,1)\), è un outlier che nessuno dei due modelli spiega bene.
🎮 Simulatore EP08_02: RANSAC — Conteggio degli Inlier Modello: Scala ×2
Il modello candidato mappa (x,y) → in (2x,2y). Regola la soglia ε e osserva quali corrispondenze diventano inlier o outlier.
–
Figura 8.16: Simulatore EP08_02: RANSAC — Votazione per Inlier tra Modelli Candidati 
%%writefile EP08_02.py
# Codice Python
Overwriting EP08_02.py
TestSuite("EP08_02.py").run()
✔️ EP08_02.cases esiste già in casos/
📋 6 caso/i caricato/i da casos/EP08_02.cases

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