09. Template Matching

Template Matching

[Slide](C:\UNI\Magistrale\visione\09_Template matching.pdf)

Indice

• Definizione e Tassonomia
• Valutazione delle Prestazioni
  • Precision e Recall
  • IoU Score
  • Curva ROC
• Template Matching Rigido su Correlazione
  • Sum of Squared Differences (SSD)
  • Cross-Correlation
  • Problemi e Approccio Multi-Risoluzione
• Template Matching Rigido su Feature
  • Dense Sampling e Descrittori Locali
  • Localizzatore di Viola e Jones
  • Histogram of Oriented Gradients (HoG)
• Trasformata di Hough
  • Hough per Rette
  • Hough per Circonferenze
  • Hough per Ellissi
• Template Matching Deformabile
  • Shape Learning

---

Definizione e Tassonomia

Definizione

Il template matching è il problema di localizzare un oggetto noto (descritto da un template $T$) all’interno di un’immagine $I$. L’output è una o più finestre di rilevamento che indicano posizione e dimensione dell’oggetto trovato.

Tassonomia:

Template Matching
├── Rigido (forma fissa)
│   ├── Pixel-based (correlazione, SSD)
│   ├── Feature-based (SIFT/SURF/HoG + distanza)
│   └── Hough transform (modelli parametrici)
└── Deformabile (forma variabile)
    ├── Free-form (contorni attivi, snakes)
    └── Parametrico (shape learning con KL)

---

Valutazione delle Prestazioni

Precision e Recall

Per valutare un sistema di localizzazione si confrontano le detection $d_i$ trovate dal sistema con le ground truth $g_j$ (annotazioni manuali).

Termine	Significato
TP (True Positive)	Detection corretta: il sistema ha trovato un oggetto che esiste
FP (False Positive)	Detection errata: il sistema ha segnalato un oggetto che non c’è
FN (False Negative)	Detection mancata: c’era un oggetto che il sistema non ha trovato

Le due metriche principali:

$P=\frac{TP}{TP+FP}R=\frac{TP}{TP+FN}$

• Precision $P$: fra tutte le detection del sistema, quante sono corrette?
• Recall $R$: fra tutti gli oggetti reali, quanti ne ha trovati il sistema?

Note

I due obiettivi sono in tensione: aumentare la sensibilità (trovare più oggetti) tende ad aumentare i falsi positivi, abbassando la precision. La soglia di classificazione permette di spostare l’equilibrio tra i due.

IoU Score

Per decidere se una detection $d_i$ è un TP o un FP si usa il Jaccard index (IoU — Intersection over Union):

$S(d_i,g_j)=\frac{\text{area}(d_i\cap g_j)}{\text{area}(d_i\cup g_j)}$

• $S=1$: sovrapposizione perfetta
• $S=0$: nessuna sovrapposizione
• Tipicamente si usa $S\ge 0.5$ come soglia per considerare una detection corretta

Curva ROC

La curva ROC (Receiver Operating Characteristic) mostra il trade-off tra errori al variare della soglia di decisione $t$:

• Asse X: False Positive Rate (FPR) — falsi allarmi
• Asse Y: False Negative Rate (FNR) — oggetti mancati

Abbassare la soglia $t$ riduce i FN ma aumenta i FP; alzarla fa il contrario. La curva ROC visualizza tutti i possibili trade-off.

---

Template Matching Rigido su Correlazione

L’approccio più diretto: si fa scorrere una finestra mobile sull’immagine e si misura la similarità tra il contenuto della finestra e il template.

Sum of Squared Differences (SSD)

$\text{SSD}(I,T_i)=\Vert I-T_i{\Vert }^2={\sum }_k(I[k]-T_i[k]{)}^2$

Misura la dissimilarità pixel per pixel. Valori bassi indicano buona corrispondenza. Il minimo globale corrisponde alla posizione più probabile dell’oggetto.

Cross-Correlation

$\text{CC}(I,T_i)=T_i^{\top }\cdot I={\sum }_k{T}_i[k]\cdot I[k]$

Misura la similarità come prodotto scalare tra il vettore template e il vettore immagine. Il massimo globale indica la posizione migliore.

Equivalenza

SSD e CC sono equivalenti quando i vettori sono normalizzati: $\text{SSD}=\Vert T{\Vert }^2+\Vert I{\Vert }^2-2\text{CC}$. Con norme costanti, minimizzare SSD equivale a massimizzare CC.

Problemi e Approccio Multi-Risoluzione

Problemi della correlazione:

• Complessità computazionale: $O(N^2\cdot M^2)$ dove $N\times N$ è l’immagine e $M\times M$ il template — costoso per immagini e template grandi
• Pattern deformabili: la correlazione assume un template rigido; oggetti con variazioni di forma non vengono rilevati

Approccio multi-risoluzione (piramide di risoluzioni):

1. Si costruisce una piramide gaussiana di $L$ livelli (ogni livello è un downsampling 2× del precedente)
2. Si esegue il matching alla risoluzione più bassa (veloce, approssimato)
3. Le posizioni candidate vengono raffinate alle risoluzioni superiori (coarse-to-fine)

Questo riduce drasticamente il costo computazionale mantenendo buona accuratezza.

---

Template Matching Rigido su Feature

Invece di confrontare direttamente i pixel, si estraggono descrittori locali e si confrontano in uno spazio di feature.

Dense Sampling e Descrittori Locali

Pipeline:

1. Si campiona l’immagine su una griglia uniforme (dense sampling)
2. Per ogni punto della griglia si calcola un descrittore locale (SIFT, SURF, HOG, Haar)
3. Si confrontano i descrittori della finestra di ricerca con quelli del template tramite distanza euclidea
4. La finestra con distanza minima è la detection

Vantaggio: i descrittori locali sono invarianti a piccole deformazioni, cambi di illuminazione e rotazioni — più robusti della correlazione pixel.

Localizzatore di Viola e Jones

Il localizzatore di Viola e Jones è il metodo classico per il rilevamento di volti in tempo reale. Combina tre ingredienti:

1. Haar-like features: maschere rettangolari binarie calcolate efficientemente tramite immagine integrale. Per una finestra 24×24 si ottengono ~49.000 feature candidate.

2. Boosting (AdaBoost): costruisce un classificatore robusto $F(x)$ come combinazione di molti classificatori deboli (uno per feature). AdaBoost seleziona iterativamente le feature più discriminative tra le ~49.000 disponibili.

3. Multiscale detection: la finestra di ricerca scorre sull’immagine a diverse scale. Per ogni finestra, si estraggono le Haar-like feature e si classifica (+1 face / -1 non-face).

In pratica: l’addestramento avviene su un dataset con esempi positivi (volti) e negativi (non-volti). Il classificatore impara quali Haar-like feature sono maggiormente discriminative per distinguere volti da sfondi.

Histogram of Oriented Gradients (HoG)

Definizione

L’HoG (Histogram of Oriented Gradients) è un descrittore proposto da Dalal e Triggs per la localizzazione di persone. Si basa sull’istogramma delle orientazioni del gradiente calcolato su sottoregioni dell’immagine.

Pipeline HoG:

Input (64×128) → Normalizzazione colore → Calcolo gradiente
→ Istogramma orientazioni per cella → Normalizzazione per blocchi
→ Concatenazione → Classificatore SVM → Persona / Non-persona

Dettagli costruttivi (per la finestra standard 64×128):

Componente	Dettaglio
Celle	8×8 pixel → 8×16 celle per finestra
Istogramma	9 bin di orientazione (0°–180°, unsigned) per cella
Blocchi	2×2 celle con overlap → 7×15 blocchi per finestra
Normalizzazione	Ogni blocco è normalizzato rispetto alla sua norma L2 (robustezza a variazioni di contrasto)
Descrittore finale	$7\times 15\times 4\times 9=3.780$ valori concatenati

Nota: il descrittore HoG è analogo a SIFT ma calcolato densamente su tutta la finestra anziché attorno a keypoint. Cattura la struttura locale degli edge, ed è robusto a piccole deformazioni geometriche.

Post-processing: si applica la soppressione dei non-massimi per ridurre i falsi positivi e unificare le detection multiple dello stesso oggetto.

---

Trasformata di Hough

Definizione

La trasformata di Hough è una tecnica per localizzare forme parametriche (rette, cerchi, ellissi) in un’immagine basandosi sul principio del voto: ogni pixel dell’immagine “vota” per tutte le forme compatibili con la sua posizione.

Meccanismo generale:

1. Si definisce uno spazio dei parametri del modello (es. $(m,c)$ per rette), discretizzato in un array di accumulatori
2. Si scansiona l’immagine: ogni pixel attivo vota per tutte le celle dello spazio dei parametri compatibili con esso
3. Al termine, i massimi dell’array corrispondono alle forme più probabilmente presenti nell’immagine

Efficienza

Nonostante la reputazione di costosa, la trasformata di Hough può essere resa efficiente usando il gradiente (per limitare i voti), l’aritmetica intera e il pre-calcolo — spesso più veloce della correlazione.

Hough per Rette

Una retta nel piano è descritta da $y=mx+c$. Lo spazio dei parametri è $(m,c)$, discretizzato in una matrice $A[m_1,\dots ,m_r][c_1,\dots ,c_s]$.

Algoritmo:

• Per ogni pixel attivo $(x,y)$: fissate $x$ e $y$, per ogni valore discreto $m_i$ si calcola $c_j=y-m_{i}x$ e si incrementa $A[m_i][c_j]$

Problema con $y=mx+c$: la pendenza $m$ va a infinito per rette verticali. Si usa quindi la parametrizzazione polare:

$\rho =x\cos \theta +y\sin \theta$

Lo spazio dei parametri diventa $(\rho ,\theta )$, che gestisce correttamente tutte le orientazioni. Ogni pixel attivo traccia una curva sinusoidale nello spazio $(\rho ,\theta )$; i punti collineari producono curve che si intersecano nello stesso punto.

Hough per Circonferenze

Una circonferenza è descritta da $r^2=(x-x_c{)}^2+(y-y_c{)}^2$.

• Raggio prefissato: lo spazio dei parametri è bidimensionale $A[x_c][y_c]$ — per ogni pixel si vota il centro compatibile
• Raggio variabile: lo spazio è tridimensionale $A[x_c][y_c][r]$ — complessità computazionale maggiore

Pipeline tipica: edge detection (Canny) → binarizzazione → trasformata di Hough → pick dei massimi.

Hough per Ellissi

Si sostituisce l’equazione dell’ellisse:

${\left(\frac{x-x_c}{a}\right)}^2+{\left(\frac{y-y_c}{b}\right)}^2=1$

I parametri sono 4 $(x_c,y_c,a,b)$ — spazio a 4 dimensioni. Per ottenere implementazioni efficienti è necessario adottare semplificazioni (es. fissare uno dei parametri o usare il gradiente per ridurre i voti).

---

Template Matching Deformabile

Gli oggetti reali non sono rigidi: la stessa classe di oggetti (es. una mano, un volto) può apparire in pose molto diverse. Il template matching rigido non è sufficiente.

Shape Learning

Definizione

Il shape learning (metodo di Cootes) è un approccio per apprendere un modello parametrico della forma di un oggetto a partire da esempi del training set, catturando le sue principali modalità di variazione.

Pipeline:

1. Si raccoglie un training set di immagini etichettate con poligonali che tracciano il contorno dell’oggetto, marcando i punti corrispondenti sempre nello stesso ordine
2. Si allineano le forme del training set (normalizzando posizione, scala, orientazione)
3. Si applica la trasformata KL (PCA) alle coordinate dei punti: si ottengono i modi di variazione principale — i gradi di libertà che catturano la maggior parte della variabilità della forma

Il modello risultante è parametrico con pochi gradi di libertà: tipicamente 5 modi principali sono sufficienti a descrivere la maggior parte delle variazioni.

Applicazione: dato il modello, si ottimizza sui parametri per fittare il contorno di un nuovo oggetto nell’immagine, partendo da una soluzione iniziale anche molto approssimata (convergenza robusta).

Esempi:

• Forma della mano: 18 immagini etichettate, 5 modi principali (KL) catturano la maggior parte delle pose possibili
• Caratteristiche del volto: 200 immagini etichettate con più poligonali (occhi, naso, bocca), stessa conclusione: 5 modi principali sufficienti