Bag of Words
[Slide](C:\UNI\Magistrale\visione\10 - Bag of Words.pdf)
Indice
Il Problema dell’Indicizzazione
I descrittori locali (SIFT, SURF, ORB…) sono vettori in uno spazio -dimensionale che riassumono le caratteristiche locali di punti di interesse. Punti vicini in questo spazio corrispondono a contenuti visivi simili.
Ai fini del riconoscimento di immagini vogliamo spesso fare ricerca per similarità (query by example): data un’immagine query, trovare le immagini più simili in un database di grandi dimensioni.
Il problema di scala
Se un database contiene migliaia di immagini e ciascuna ha migliaia di keypoint, il confronto diretto tra tutti i descrittori è computazionalmente proibitivo. Serve un meccanismo di indicizzazione efficiente — analogo all’indice analitico di un libro, che permette di risalire subito alle pagine contenenti un certo termine senza leggerlo tutto.
Bag of Words (BoW)
Analogia con i Documenti Testuali
Nei sistemi di information retrieval testuali, un documento è spesso rappresentato come un istogramma di occorrenze delle parole del dizionario (ignorando l’ordine delle parole — da qui il nome “bag”). Due documenti sono simili se i loro istogrammi sono simili.
In pratica: un articolo di economia sarà caratterizzato da parole come trade, surplus, yuan, mentre un articolo di neuroscienze da brain, retinal, cortex. L’istogramma cattura il “contenuto” del documento in modo compatto.
Idea e Costruzione del Dizionario Visuale
Definizione
Il modello Bag of Words rappresenta un’immagine tramite un istogramma di occorrenze di visual words — parole visive discrete che corrispondono a caratteristiche locali tipiche dell’immagine.
Il passaggio chiave è la quantizzazione: i descrittori locali sono continui e ad alta dimensionalità, ma per costruire un istogramma servono simboli discreti. Si raggruppa quindi lo spazio delle feature in regioni, e ogni regione diventa una “parola” del dizionario visuale.
In pratica: pensa alle visual words come a “mattoncini visivi” ricorrenti — spigoli a 45°, texture granulosa, cerchi chiari su sfondo scuro. Il BoW di un’immagine conta quante volte compaiono questi mattoncini.
Pipeline BoW
Fase 1 — Localizzazione delle Feature
Per ogni immagine del training set si estraggono le patch locali secondo una delle seguenti strategie:
| Strategia | Descrizione |
|---|---|
| Sparse (keypoint detector) | Solo nei punti di interesse rilevati (Harris, SIFT, SURF…) — compatta ma dipende dal detector |
| Dense sampling | Griglia uniforme sull’immagine — più completo, non perde regioni senza keypoint |
| Random | Posizioni casuali — semplice, talvolta efficace |
| Keypoint detector multipli | Combinazione di più detector per massima copertura |
Per ogni patch estratta si calcola un descrittore (tipicamente SIFT), ottenendo così un insieme di vettori -dimensionali.
Fase 2 — Creazione del Dizionario Visuale
Dopo aver estratto i descrittori da tutto il corpus di training:
- Si proiettano tutti i descrittori nello spazio delle feature -dimensionale
- Si applica un algoritmo di clustering (tipicamente k-means) per raggruppare i descrittori in cluster
- Il centroide (prototipo) di ogni cluster diventa una visual word del dizionario
Il risultato è un dizionario di parole visive che partizionano lo spazio delle feature. La scelta di è un iperparametro: dizionari piccoli sono generici, dizionari grandi sono più discriminativi ma più costosi.
Note
I centroidi del clustering corrispondono intuitivamente a “patch tipiche” ricorrenti nel corpus: in un dataset di aerei e moto, un cluster potrebbe corrispondere a “bordo curvo metallico” e un altro a “ruota”.
Fase 3 — Rappresentazione delle Immagini
Data un’immagine (di training o di test):
- Si estraggono le feature locali (come in Fase 1)
- Per ogni descrittore si trova la visual word più vicina nel dizionario (nearest neighbor nello spazio delle feature)
- Si costruisce l’istogramma di occorrenze: il bin conta quante feature dell’immagine sono state assegnate alla parola
Il risultato è un vettore di lunghezza fissa — la rappresentazione BoW dell’immagine — indipendentemente da quante feature conteneva.
Immagine → [estrazione feature] → [assegnazione a visual word] → [istogramma K-dim]
Fase 4 — Classificazione
Learning:
- Si costruisce il dizionario visuale dal corpus di training
- Si rappresentano tutte le immagini di training come vettori BoW
- Si addestra un classificatore (es. SVM) sui vettori BoW etichettati
Classificazione di una nuova immagine:
- Si rappresenta l’immagine come vettore BoW usando il dizionario già costruito
- Si confronta il vettore con i modelli appresi dal classificatore
- Si assegna la classe di appartenenza più probabile
Vantaggi e Svantaggi
| Dettaglio | |
|---|---|
| Invarianza | Grazie ai descrittori locali (SIFT/SURF), la rappresentazione BoW eredita invarianza a variazioni geometriche, deformazioni e trasformazioni affini |
| Compattezza | L’immagine è ridotta a un vettore di valori — molto compatto rispetto ai pixel o ai descrittori raw |
| Lunghezza fissa | Il vettore BoW ha sempre dimensione , indipendentemente dal numero di feature rilevate nell’immagine — fondamentale per i classificatori |
| Efficacia empirica | Buoni risultati sperimentali in task di classificazione e retrieval |
Limiti
- Background/foreground mescolati: le feature estratte da sfondo e soggetto vengono trattate allo stesso modo — il BoW non distingue cosa appartiene all’oggetto di interesse
- Nessuna garanzia di copertura: le tecniche di localizzazione delle patch non garantiscono che le feature ricadano sull’oggetto cercato
- Perdita dell’informazione spaziale: l’istogramma ignora dove nell’immagine si trovano le visual words — due immagini con le stesse parole in posizioni diverse hanno lo stesso BoW
Soluzioni possibili alla perdita spaziale:
- Inserire nei descrittori informazioni sulla posizione assoluta
- Suddividere l’immagine in sottoregioni e costruire un istogramma per ciascuna (spatial pyramid)
- Dopo il matching verificare la consistenza spaziale delle corrispondenze (es. con RANSAC)