Il termine template matching è molto generico nell'ambito del pattern recognition, ma normalmente fa riferimento alla «ricerca» di un template T all'interno di un'immagine I, con l'obiettivo di determinare se I contiene l'oggetto (match) e in quale posizione T appare nell'immagine. La tassonomia vista a lezione distingue i rigid template matching dai deformable template matching, e per ciascuno le tecniche principali:
In un sistema di localizzazione di oggetti è necessario misurare:
I principali indicatori sono:
Precision = TP / (TP + FP) Recall = TP / (TP + FN)con TP = true positive, FP = false positive, FN = false negative. Per decidere se un oggetto localizzato d_i corrisponde a un oggetto del ground truth g_j, lo score associato al matching tra i due è l'intersezione su unione:
S(d_i, g_j) = area(d_i ∩ g_j) / area(d_i ∪ g_j)Può essere necessario un algoritmo di assegnamento che ottimizzi le coppie (d_i, g_j) sulla base del relativo score. False e mancate localizzazioni sono spesso legate tra loro e funzioni dei parametri di tolleranza del sistema: rendendo il sistema meno tollerante ai falsi aumenta la probabilità di perdere oggetti genuini; rendendolo più tollerante aumenta la probabilità di localizzare qualche falso. Le prestazioni al variare della tolleranza si sintetizzano nella curva ROC (Receiver Operating Characteristic), che traccia i due tassi di errore (FPR e FNR) al variare della soglia.
Regola direttamente TP, FP e FN, oppure muovi la tolleranza del sistema: più tolleranza → più oggetti trovati ma anche più falsi (FPR cresce, FNR cala). Il grafico mostra il punto (FNR, FPR) corrente, come nella curva ROC delle slide.
Un approccio molto usato per la localizzazione di oggetti si basa sull'analisi delle immagini con una finestra mobile che viene fatta scorrere sull'immagine e confrontata di volta in volta con i diversi template degli oggetti da ricercare (es. pedoni e macchine in una scena). Il template T è costituito da un oggetto rigido (normalmente una piccola immagine in formato raster):
Il confronto tra sottoimmagine e modello si basa su apposite feature (es. intensità, descrittori SIFT). Per decidere se un oggetto è presente si impone una soglia alla similarità tra le feature della sottofinestra e il modello; è possibile che lo stesso oggetto venga localizzato in più posizioni adiacenti, per cui serve una fase di post-processing (es. fusione, soppressione dei non massimi).
Immagini e template sono definiti, per semplicità di notazione, come vettori 1-dimensionali ottenuti disponendo in sequenza le righe delle corrispondenti matrici 2-dimensionali. Nell'approccio correlation-based, una misura intuitiva di diversità tra I e un'istanza T_i è la Sum of Squared Differences (SSD):
SSD(I, T_i) = ‖I − T_i‖² = (I − T_i)ᵀ (I − T_i) = ‖I‖² + ‖T_i‖² − 2·T_iᵀ IQuando i termini ‖I‖² e ‖T_i‖² sono costanti, minimizzare il primo termine corrisponde a massimizzare la Cross-Correlation (CC) tra I e T_i:
CC(I, T_i) = T_iᵀ I = Σ_k T_i[k] · I[k]In alcuni casi la cross-correlation non è una misura robusta e diventa necessario applicare delle normalizzazioni: ciò accade in particolare quando I e T_i non sono costanti, ad esempio cercando lo stesso template su immagini diverse, oppure con istanze dello stesso template diverse tra loro per numero di pixel e luminosità media.
L'immagine contiene un oggetto (rettangolo scuro con nucleo chiaro) in posizione nota. Sposta la finestra con i cursori: la SSD è minima (e la CC massima) quando la finestra coincide con l'oggetto. Premi «Trova il minimo» per lanciare la ricerca esaustiva.
Per ridurre la complessità si segue la ricerca su una gerarchia crescente di risoluzioni: viene creata una piramide di risoluzioni, ad esempio dimezzando la risoluzione a ogni livello. La ricerca viene eseguita inizialmente sulla risoluzione più bassa; ai livelli successivi vengono analizzate solo le istanze promettenti (la cui correlazione al livello inferiore eccedeva una soglia, tenuta piuttosto bassa per evitare false reiezioni). Così si esegue una scrematura ai livelli iniziali e si perfeziona la localizzazione (filtrando le false accettazioni) ai livelli successivi. L'approccio multirisoluzione viene usato anche per localizzare oggetti a scale diverse.
Per la rappresentazione dei template e delle singole patch è possibile usare dei descrittori locali (es. SIFT, SURF, HOG, Haar) associati a punti distribuiti uniformemente sull'immagine (dense sampling). Il confronto tra descrittori può essere effettuato sommando o mediando le distanze euclidee calcolate tra descrittori di punti corrispondenti: se la distanza ottenuta è inferiore alla soglia prefissata, l'oggetto si considera localizzato. L'esempio visto a lezione è la localizzazione dei prodotti in un ambiente di vendita: un'immagine campione viene confrontata con le foto dei prodotti presenti in assortimento.
Questa è l'applicazione diretta dei descrittori del capitolo 7: il template rigido non è più un raster di intensità, ma un insieme di descrittori locali, e la «similarità» diventa una distanza media nel loro spazio.
Data una singola immagine o una sequenza video, la localizzazione del volto deve rilevare la presenza di uno o più volti e localizzarne la posizione. È necessaria l'indipendenza rispetto a: posizione, orientazione, scala ed espressione del volto; e a fattori esterni quali illuminazione o sfondo complesso. L'approccio: analizzare sottofinestre consecutive (sovrapposte) dell'immagine in input e valutare per ciascuna se appartiene alla classe dei volti («volto o non volto?»).
Il localizzatore di Viola e Jones [VJ01] è uno dei più robusti ed efficienti allo stato dell'arte: l'addestramento è molto lento (può richiedere giorni), ma la procedura di localizzazione è molto efficiente (funzionamento real-time). Si crea un classificatore inizialmente addestrato mediante multiple istanze della classe da individuare (esempi positivi) e varie istanze di esempi negativi (immagini che non contengono alcun oggetto della classe). Durante il training vengono estratte diverse caratteristiche dagli esempi e selezionate quelle particolarmente discriminanti; questa informazione è racchiusa nei parametri del modello statistico. Se il classificatore addestrato non trova un oggetto presente (miss) o ne indica erroneamente la presenza (false alarm), si può ricalibrare l'addestramento aggiungendo gli esempi corrispondenti (positivi o negativi) al training set.
Le tre componenti del metodo:
La localizzazione è effettuata facendo scorrere sull'immagine una finestra di ricerca (di dimensioni variabili), estraendo le feature presenti nella finestra e classificando la finestra come volto o non volto.
HoG è un descrittore molto noto, proposto per la localizzazione di persone. Si basa su una finestra mobile applicata all'immagine in tutte le possibili posizioni e a diverse scale. La pipeline, a partire dall'immagine in input (sottoregione riscalata a 64 × 128):
I descrittori delle sottofinestre vengono concatenati e il descrittore globale viene usato per la classificazione tramite SVM. Viene infine applicata una soppressione dei non massimi per semplificare l'output e ridurre il numero di falsi positivi.
Alcune forme si lasciano descrivere da modelli parametrici: la linea y = m·x + c, la circonferenza r² = (x − x_c)² + (y − y_c)², l'ellisse (x−x_c)²/a² + (y−y_c)²/b² = 1. La trasformata di Hough sfrutta i parametri per localizzare queste forme anche da edge e punti sparsi:
Sebbene sia ritenuta da alcuni computazionalmente molto costosa, con l'uso del gradiente, il calcolo in aritmetica intera, il pre-calcolo dei valori e approcci multi-risoluzione si ottengono implementazioni molto efficienti — più efficienti della correlazione.
Ogni retta nel piano x, y è descritta da y = m·x + c: lo spazio dei parametri (m, c) viene discretizzato in un array bidimensionale A[m₁…m_r][c₁…c_s]. Durante la scansione ogni pixel attivo (x, y) individua una retta nello spazio dei parametri: per ogni valore discreto di m_i si determina il corrispondente c_j e si incrementa A[m_i][c_j]. Al termine, i massimi di A denotano le rette candidate. Nella pratica si preferisce la parametrizzazione in coordinate polari:
ρ = x·cos θ + y·sin θperché la discretizzazione di (m, c) comporta problemi per le rette verticali o quasi verticali (m infinita). L'esempio a lezione: gradiente (Sobel) → binarizzazione (soglia globale) → le 30 rette più probabili localizzate con la trasformata di Hough.
Per una circonferenza di raggio prefissato r è costante e l'array degli accumulatori è bidimensionale A[x_c₁…x_cr][y_c₁…y_cs]. Se si vogliono tutte le circonferenze con raggio in un range prefissato, lo spazio (x_c, y_c, r) viene discretizzato in un array tridimensionale, con complessità ovviamente superiore. Nell'approccio base per le ellissi si sostituisce l'equazione dell'ellisse a quella del cerchio: i parametri però sono 4 (x_c, y_c, a, b) e per implementazioni efficienti servono semplificazioni.
I punti blu giacciono su una retta (con rumore), i vermigli sono outlier. Ogni punto vota una sinusoide nello spazio (ρ, θ); il cursore fa votare progressivamente più punti e il picco dell'accumulatore individua la retta (in coordinate polari).
Spesso risulta complicato fornire espressioni analitiche di un template e altrettanto difficile definire precisamente le trasformazioni che mappano un oggetto nelle sue possibili deformazioni. I metodi di shape learning hanno come obiettivo l'apprendimento della forma di un oggetto e delle sue possibili variazioni a partire da un insieme di esempi.
Nel metodo di Cootes [Coot00] il template viene modellato da poligonali; durante l'addestramento gli esempi nel training set sono allineati (manualmente) sulla base di punti notevoli. I molteplici gradi di libertà dati dalla mobilità spaziale dei punti corrispondenti nei diversi pattern di esempio vengono fortemente ridotti (trasformata KL) per ottenere un modello parametrico con pochi gradi di libertà — la stessa idea dei sottospazi KL del relevance feedback del capitolo 5. Il modello converge a partire da una soluzione iniziale anche «molto imprecisa».
Gli esempi visti a lezione: la forma della mano (18 immagini etichettate con una poligonale, marcando i punti corrispondenti sempre nello stesso ordine — i 5 «modi di variazione principali» della KL gestiscono gran parte delle variazioni) e le caratteristiche interne del volto (200 immagini etichettate con più poligonali, stesso criterio).
La ricerca di un template T all'interno di un'immagine I, con l'obiettivo di determinare se I contiene l'oggetto (match) e in quale posizione T appare nell'immagine.
Rigid template matching: pixel-based (dominio spaziale o delle frequenze), local descr. based, Hough transform. Deformable template matching: free-form deformable (analytic-form based, transformation based) e parametric deformable (shape learning).
Precision = frazione di oggetti localizzati che sono rilevanti: TP/(TP+FP). Recall = frazione di oggetti rilevanti che sono stati localizzati: TP/(TP+FN). I tre tipi di errore: false positive (oggetto non corretto localizzato), false negative o drop/miss (oggetto presente non localizzato), e la precisione di localizzazione (accuracy).
Con l'intersezione su unione: S(d_i, g_j) = area(d_i ∩ g_j) / area(d_i ∪ g_j). Può servire un algoritmo di assegnamento che ottimizzi le coppie (d_i, g_j) sulla base del relativo score.
False e mancate localizzazioni sono legate tra loro: rendendo il sistema meno tollerante ai falsi aumenta la probabilità di perdere oggetti genuini; rendendolo più tollerante aumenta la probabilità di localizzare falsi. Le prestazioni al variare della tolleranza si sintetizzano nella curva ROC.
Il template T (oggetto rigido, piccola immagine raster) viene sovrapposto a I in tutte le posizioni (X e Y) e, se serve, ruotato e scalato (istanze T_i). Per ogni istanza si calcola la similarità massimizzando la correlazione con la porzione coperta; una soglia decide la presenza dell'oggetto; un post-processing (fusione, soppressione dei non massimi) elimina le localizzazioni adiacenti duplicate. Attenzione agli effetti di bordo se il template è più grande dell'immagine.
SSD(I, T_i) = ‖I‖² + ‖T_i‖² − 2·T_iᵀ I: quando ‖I‖² e ‖T_i‖² sono costanti, minimizzare la SSD equivale a massimizzare la cross-correlation CC = Σ_k T_i[k]·I[k]. La CC va normalizzata quando I e T_i non sono costanti (template cercato su immagini diverse, istanze con numero di pixel o luminosità media diversi).
Complessità computazionale: cresce linearmente con le istanze e i pixel, quindi in modo quadratico rispetto al lato — quasi sempre inapplicabile in real-time. Difficile gestione dei pattern deformabili: servono invarianza per posizione, rotazione, scala e aspect ratio (enorme numero di istanze), gestione delle variazioni di colore (es. operare sugli edge) e delle deformazioni locali.
Si crea una piramide di risoluzioni (es. dimezzando la risoluzione a ogni livello). La ricerca parte dalla risoluzione più bassa; ai livelli successivi si analizzano solo le istanze promettenti (correlazione al livello inferiore sopra una soglia bassa, per evitare false reiezioni): scrematura ai livelli iniziali, perfezionamento e filtraggio delle false accettazioni ai successivi. Serve anche per localizzare oggetti a scale diverse.
Template e patch vengono rappresentati con descrittori locali (SIFT, SURF, HOG, Haar) su punti distribuiti uniformemente (dense sampling); il confronto somma o media le distanze euclidee tra descrittori di punti corrispondenti; se la distanza è sotto soglia, l'oggetto è localizzato.
Classificatore addestrato su esempi positivi e negativi; tre componenti: Haar-like feature, classificazione con boosting (combinazione di classificatori semplici), multiscale detection con finestra scorrevole. Addestramento lento (giorni), localizzazione real-time. Miss o false alarm si correggono aggiungendo gli esempi corrispondenti al training set (ricalibrazione).
Immagine riscalata a 64 × 128 → normalizzazione del colore → calcolo del gradiente → istogramma per ciascuna cella 8 × 8 (8 × 16 celle, simile a SIFT) → normalizzazione degli istogrammi in blocchi 2 × 2 con overlap (7 × 15 blocchi) → descrittore globale classificato con SVM → soppressione dei non massimi per ridurre i falsi positivi.
Si definisce uno spazio dei parametri discretizzato in un array di accumulatori; ogni pixel attivo vota per le celle corrispondenti alle soluzioni compatibili; le celle con più voti indicano le soluzioni più probabili. Per le rette si usa la forma polare ρ = x·cosθ + y·sinθ (la forma (m, c) fallisce sulle rette verticali). Le circonferenze usano accumulatori 2D (raggio fisso) o 3D (raggio in range); le ellissi hanno 4 parametri e richiedono semplificazioni.
È l'apprendimento della forma di un oggetto e delle sue variazioni dagli esempi. Cootes modella il template con poligonali; gli esempi del training set sono allineati manualmente su punti notevoli (sempre nello stesso ordine); la trasformata KL riduce i gradi di libertà a pochi «modi di variazione principali», ottenendo un modello parametrico che converge anche da una soluzione iniziale molto imprecisa. Esempi: forma della mano (18 immagini) e caratteristiche interne del volto (200 immagini).