I descrittori locali (capitolo 7) sono vettori di uno spazio N-dimensionale ad alta dimensionalità che riassumono le caratteristiche locali dei punti di interesse. Ai fini del riconoscimento siamo spesso interessati a ricercare in un database di grandi dimensioni le immagini simili a una query (query by example — lo stesso scenario dei sistemi CBIR del capitolo 5).
L'osservazione chiave: punti vicini nello spazio N-dimensionale delle feature corrispondono a contenuti locali simili. Se le immagini sono codificate con keypoint e descrittori locali, la ricerca può sfruttare la similarità tra descrittori… ma quanti confronti dobbiamo fare se abbiamo centinaia di immagini e in ciascuna rileviamo migliaia di punti di interesse? Per i documenti di testo il modo più efficiente per risalire a tutte le pagine che contengono un determinato termine è l'uso di un indice. È da questa analogia che nasce il Bag of Words.
Il metodo Bag of Words (BoW) si ispira alle tecniche di rappresentazione dei documenti testuali, che spesso codificano un documento tramite istogrammi in cui è riportato il numero di occorrenze dei termini che costituiscono il dizionario. Il modello BoW è stato proposto con l'obiettivo di rappresentare un'immagine tramite un dizionario visuale: l'idea di base è rappresentare un'immagine tramite un istogramma di occorrenze di alcune visual words che rappresentano specifiche caratteristiche locali dell'immagine.
Un oggetto viene rappresentato dal sacco di parole che lo descrive: l'ordine spaziale delle parole è perduto (è un bag, non una frase), ma la distribuzione delle occorrenze resta un descrittore potente — esattamente come nei testi, dove l'ordine delle parole può cambiare senza cambiare il senso del «sacco».
Mentre le parole testuali sono concetti «discreti», le parole visuali sono rappresentate da descrittori locali continui e di dimensionalità talvolta elevata. Per ottenere parole visuali discrete è necessario quantizzare i descrittori locali nello spazio delle feature: in questo modo ciascun nuovo descrittore può essere codificato in termini della regione (discretizzata) dello spazio delle feature alla quale appartiene.
I tipici passaggi per la costruzione del dizionario visuale:
Un'immagine può essere codificata in termini di parole visuali selezionando per ciascuna feature locale la parola ad essa più vicina nello spazio delle feature.
Ogni punto è un descrittore locale nello spazio delle feature (2D per semplicità). Le parole del dizionario sono i prototipi dei cluster (quadrati vermigli): ogni descrittore è codificato dalla parola più vicina. Muovi il nuovo descrittore (cerchio blu) e osserva la parola assegnata.
Il BoW si usa per la classificazione in due fasi distinte:
Nella fase di apprendimento si: 1) crea il dizionario visuale; 2) si costruisce la rappresentazione delle immagini di training (istogrammi di parole visuali); 3) si creano modelli / classificatori a partire da quelle rappresentazioni.
Nella fase di classificazione si: 1) calcola la rappresentazione dell'immagine da riconoscere (stesso dizionario, nuovo istogramma); 2) si confronta con i modelli; 3) si determina la classe di appartenenza.
Prima del calcolo dei descrittori vanno scelte le sottoregioni di interesse (patch). Due strategie opposte:
Il processo di estrazione delle feature prevede: localizzazione delle patch → eventuale normalizzazione → calcolo del descrittore (es. SIFT). Il processo viene ripetuto per una serie di immagini di training, ottenendo un insieme ampio di descrittori che saranno poi usati per la creazione del dizionario.
I descrittori estratti dal corpus di training vengono rappresentati nello spazio multidimensionale delle feature. Per la quantizzazione dello spazio si possono usare ad esempio tecniche di clustering e selezionare come parole i «prototipi» di ciascun cluster. Il dizionario è quindi un insieme finito di parole visuali; ogni nuovo descrittore viene codificato con la parola più vicina, e l'immagine diventa un istogramma di occorrenze: un descrittore di lunghezza fissa pari al numero di parole del dizionario.
Le due immagini condividono il dizionario (k parole). Ogni feature è colorata secondo la parola assegnata. Muovi la dissimilarità per avvicinare/allontanare la distribuzione delle parole della seconda immagine da quella della prima: l'intersezione degli istogrammi misura la similarità.
| Vantaggi | Svantaggi |
|---|---|
|
|
Possibili soluzioni al problema della distribuzione spaziale:
La suddivisione in sottoregioni è la stessa tecnica già incontrata per i color moments locali nel capitolo 4: l'istogramma globale perde l'informazione spaziale, e la soluzione è sempre partizionare l'immagine e confrontare le parti.
Perché con centinaia di immagini e migliaia di punti di interesse per immagine il confronto esaustivo tra tutti i descrittori è impraticabile. Come per i documenti di testo, si usa un indice: per le immagini è il dizionario delle visual words.
È una parola del dizionario visuale: rappresenta una specifica caratteristica locale dell'immagine. Poiché i descrittori locali sono vettori continui ad alta dimensionalità, le parole visuali si ottengono quantizzando lo spazio delle feature (es. con clustering, prendendo i prototipi dei cluster).
1) Creazione del corpus: selezione di un numero elevato di immagini di training; 2) quantizzazione dello spazio delle feature sulla base di informazioni statistiche (es. clustering). I prototipi dei cluster diventano le parole del dizionario.
Per ciascuna feature locale si seleziona la parola ad essa più vicina nello spazio delle feature; l'immagine diventa un istogramma di occorrenze delle parole del dizionario — un descrittore di lunghezza fissa, indipendente dal numero di feature rilevate.
Learning: creazione del dizionario visuale, rappresentazione delle immagini di training (istogrammi), creazione di modelli/classificatori. Classificazione: rappresentazione dell'immagine da riconoscere con lo stesso dizionario, confronto con i modelli, determinazione della classe di appartenenza.
Le feature sparse si estraggono solo in corrispondenza di punti di interesse (random o keypoint detector multipli); il dense sampling usa una griglia uniforme di patch su tutta l'immagine. In entrambi i casi il processo è: localizzazione delle patch → eventuale normalizzazione → calcolo del descrittore (es. SIFT).
Invarianza rispetto a variazioni geometriche, deformazioni e trasformazioni affini; rappresentazione compatta; descrittore di lunghezza fissa indipendentemente dal numero di feature; buona efficacia dimostrata sperimentalmente.
Svantaggi: background e foreground mischiati; la localizzazione delle patch non garantisce porzioni dell'oggetto; nessuna distribuzione spaziale. Soluzioni: inserire la posizione nei descrittori; suddividere in sottoregioni con un istogramma per ciascuna; verificare la consistenza spaziale delle corrispondenze dopo il matching.
Perché il numero di feature rilevate varia da immagine a immagine, ma l'istogramma ha sempre una dimensione pari al numero di parole del dizionario: le immagini sono rappresentate in uno spazio comune e confrontabili con le stesse metriche (es. intersezione di istogrammi, distanze).