Diapositiva 1

Annotazione Automatica di
materiale multimediale
Enver Sangineto,
Dipartimento di Informatica
[email protected]
Annotazione automatica

Estrarre automaticamente informazione
“semantica” da immagini, video o audio e
rappresentarla in forma:



testuale o
strutturata
Tipicamente si usano tecniche di machine
learning
p. 2
Annotazione automatica [2]


E’ una fase di pre-processing, precedente al
retrieval vero e proprio, che avviene con
metodi più “tradizionali” avvalendosi
dell’informazione estratta off-line
E’ simile alla “information extraction” nel caso
dei testi, in cui da un documento si ricava
informazione rappresentata poi in maniera
machine understandable
p. 3
Annotazione di documenti digitali:
OCR e Document Analysis



Un caso particolare di immagine è la
digitalizzazione di un documento di testo
Tecniche di Document Analysis permettono di
analizzare la struttura del documento al fine di
individuare le parti contenenti testo
Il testo può essere riconosciuto attraverso
Optical Character Recognition (OCR)
p. 4
Annotazione di immagini
(generiche)

L’ideale sarebbe poter disporre di un sistema
che riconosca i principali oggetti presenti in
un’immagine e li descriva tramite una lista di
keywords
p. 5
Annotazione di immagini [2]



E’ difficile stabilire a priori quali sono gli
oggetti importanti in una data immagine
Un tale sistema non sarebbe in grado di
estrarre significati più complessi (e.g. “Rabin e
Arafat si stringono la mano”…)
Tuttavia una lista degli oggetti (e.g., in primo
piano) sarebbe già un grosso passo in avanti
p. 6
Esempio

Annotazione 1: ci sono 3 esseri umani
 Annotazione 2: ci sono 3 esseri umani, Arafat,
Clinton e Rabin
p. 7
Problemi principali nel
riconoscimento di oggetti

La maggior parte dei problemi che un sistema
di object recognition deve affrontare sono
riconducibili a due problemi base:


Variabilità delle apparenze con cui l’immagine di
un oggetto può presentarsi sul piano di vista
La segmentazione della scena, ovvero
l’individuazione di quelle sotto-parti dell’immagine
che rappresentano l’oggetto cercato
p. 8
Variabilità [1]: cambiamento del punto di vista
p. 9
Michelangelo 1475-1564
Variabilità [2]: cambiamento delle condizioni di illuminazione
p. 10
Variabilità [3]: oggetti deformabili
Xu, Beihong 1943
p. 11
Variabilità [4]: variazione intra-classe
p. 12
Segmentazione [1]:
Occlusioni
p. 13
Magritte, 1957
Segmentazione [2]: separazione dallo sfondo
p. 14
Klimt, 1913
Modello statistico della variabilità



Ignoriamo il problema della segmentazione
Utilizziamo tecniche di machine learning per
definire modelli statistici della variabilità delle
apparenze
Due fasi: “Training” e “Classificazione” (o
“Test”)
p. 15
Categorizzazione tramite
apprendimento automatico

Suppongo di disporre, in fase di training, di un
insieme
T = {(I1, y1), …, (IN, yN)},
dove Ij è un’immagine e yj un’etichetta che
indica l’oggetto in essa contenuto:
yj {o1, …, om}
p. 16
Categorizzazione tramite
apprendimento automatico [2]


Utilizzo T off-line per addestrare un
classificatore statistico C (e.g., una rete
neurale, …)
On-line, uso C per classificare un’immagine
nuova I, non appartenente a T:
C(I) {o1, …, om}
p. 17
Categorizzazione tramite
apprendimento automatico [3]


Esistono molti approcci all’object recognition
che utilizzano tecniche di apprendimento
automatico
Essi si scontrano con i problemi di
segmentazione e variabilità visti prima
p. 18
Proprietà di invarianza delle feature


Maggiore è l’invarianza delle feature a
cambiamenti di apparenza, minore la
variabilità da rappresentare nel training set
Invarianze desiderabili:


Cambiamenti di punti di vista (rotazioni,
traslazioni, scalamenti)
Cambiamenti di illuminazione
p. 19
Features per immagini non
segmentate


Le feature globali sono inefficaci se l’oggetto
cercato non è separato dal background
L’orientazione corrente è utilizzare feature
locali che in genere dipendono sia dalla forma
che dalla texture dell’oggetto
p. 20
Scale Invariant Feature Transform
(SIFT) [Lowe]

L’estrazione delle SIFT da un’immagine è
composta da due fasi:


Individuazione di punti “stabili” a cambiamenti di
scala (detection)
Descrizione delle zone circostanti tali punti con il
descrittore SIFT (description)
[Lowe ] David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints,
Int. J. Comput. Vision, 60 (2), pp 91-110, 2004.
p. 21
Selezione di punti stabili a
cambiamenti di scala
Costruzione di una “piramide” di DoG
(Difference of Gaussians)
I punti stabili (e le relative scale) sono
scelti cercando punti di
massimo/minimo nella piramide
p. 22
Scelta della direzione dominante

Picchi dell’istogramma dell’orientazione del
gradiente
p. 23
Ese. di keypoints individuati tramite
SIFT detector
p. 24
Descrittore SIFT


L’intorno di ogni p.to stabile è descritto tramite
una griglia composta da 4 X 4 sotto-griglie
(nella figura è 2 X 2)
I vettori gradienti hanno un peso “gaussiano”
p. 25
Descrittore SIFT [2]

Ogni sottogriglia forma un istogramma delle
orientazioni del gradiente
p. 26
Descrittore SIFT [2]

Il descrittore è ottenuto concatenando il valore dei
4*4 istogrammi da 8 orientazioni l’uno (128 ele.)
 Alcune particolari normalizzazioni permettono di
ottenere un descrittore invariante per trasformazioni
affini della luce nell’area descritta
p. 27
SURF: speeded up robust features
[Bay et al]

Anche l’estrazione delle SURF è composta da
due fasi:


Detection e
Description
[Bay et al] Herbert Bay, Tinne Tuytelaars, Luc Van Gool, SURF: speeded up robust
features, ECCV, 2006.
p. 28
Selezione di punti stabili a
cambiamenti di scala

Applicando filtri a dimensione variabile cerco
dei “blob” presenti nell’immagine
p. 29
Scelta della direzione dominante



Altri filtri vengono utilizzati per calcolare le componenti dx e
dy del gradiente
Le risposte dx e dy vengono sommate in settori circolari
differenti per determinare un vettore rappresentativo del
settore
Il vettore più grande è la direzione dominante
p. 30
Descrittore SURF


Griglia 4 X 4
Ogni sotto-griglia ha 5 X 5 p.ti di
campionamento
p. 31
Descrittore SURF [2]

Per ogni p.to di campionamento calcolo dx e
dy utilizzando “Haar wavelets”
p. 32
Haar wavelets
p. 33
Immagine Integrale
p. 34
Calcolo delle Haar vawelets in
tempo costante
p. 35
Descrittore SURF [3]

Il descrittore finale è dato dalla
concatenazione di vc1, …, vc16 (64 ele.)
p. 36
Image categorization come text
categorization

Analogia con i documenti testuali:




documenti <-> immagini
concetti <-> classi di oggetti
keywords <-> (valori “prototipi” di) feature
spazio vettoriale <-> spazio delle frequenze delle
feature prototipe
p. 37
Bags of Words

Estraggo le feature da vari punti
dell’immagine, scegliendo:





I punti più salienti (tipo SIFT…), oppure
dei punti a caso, oppure
dei punti in una griglia fissa…
Conto la frequenza dei valori delle feature
estratte e classifico l’immagine in base alla
frequenza trovata
Tecnica simile alla rappresentazione di un
documento in uno spazio vettoriale
p. 38
Object
Bag of ‘words’
p. 39
immagine presa da: Tutorial CVPR 07

Costruzione vocabolario 
p. 40
Problema: mancanza di un
vocabolario simbolico


Un testo può essere visto come una stringa
composta da simboli base (le keywords)
Quale insieme di feature (e.g., particolari
valori di SIFT) scegliere nel caso visivo?
p. 41
Esempio: dimensionalità delle SIFT



Un descrittore SIFT è composto da 4*4
istogrammi da 8 orientazioni (128 elementi)
I valori del “bin” di ogni istogramma sono
normalizzati in [0, 255]
In totale 256128 possibili valori…
p. 42
Variabilità delle feature…




Se Si è un descrittore SIFT estratto dalla
pupilla dell’occhio di Marco in una foto
“indoor” e
Sj è stato estratto dalla stessa pulippa di
Marco “outdoor” (o in un giorno diverso)
Allora, tipicamente: Si ≠ Sj
I descrittori SIFT, per quanto invarianti, non si
comportano come simboli ripetibili!
p. 43
Bags of Words: testo vs immagini…


La maggiore differenza del BoW del caso
visivo rispetto a quello testuale è proprio la
mancanza di un “naturale” vocabolario
Idea: costruisco il vocabolario a partire da T
scegliendo dei valori prototipi
p. 44
Prototipi di feature: le “keywords”
discrete che mancavano



Suddivido i valori che può assumere una
feature in “tipi” diversi
Ogni tipo è rappresentato da un prototipo,
detto “word” per analogia al caso testuale
In sostanza, creando i tipi di feature, creo un
vocabolario di valori discreti
p. 45
Vector Quantization

Si tratta di un processo di vector quantization
con cui creo un dizionario (codebook o
codeword dictionary) per discretizzare i
possibili valori del feature space
p. 46
Es: estraggo le feature da un’img di training
p. 47
immagine presa da: Tutorial CVPR 07
Estraggo le feature da tutte le img di
training
…
p. 48
immagine presa da: Tutorial CVPR 07
Rappresentazione nel feature space dei valori
estratti dal training set
…
p. 49
immagine presa da: Tutorial CVPR 07
Costruisco il Codeword dictionary tramite clustering
p. 50
immagine presa da: Tutorial CVPR 07


Costruzione vocabolario
Rappresentazione delle immagini 
p. 51
Rappresentazione di un’immagine
nello spazio delle frequenze


Supponiamo che il dizionario (D) è composto
da n valori possibili D = {w1, …, wn}
Ogni wi è un’etichetta associata con un valore
prototipo pi del feature space
p. 52
Rappresentazione di un’immagine
nello spazio delle frequenze [2]


Da una generica immagine I estraggo un
insieme di feature locali {zi} (e.g., zi è il
descrittore SIFT estratto nel punto P di I)
Associo ogni zi con la “parola” wj più simile,
e.g., scegliendo j in modo da minimizzare:
pj = min pk Dist(zi, pk)
p. 53
Esempio
p. 54
Rappresentazione di un’immagine
nello spazio delle frequenze [3]

I è quindi rappresentata da x = (x1, …, xn)T,
dove:

xj= # { wj : Esiste zi associata con pj }
p. 55
frequency
Rappresentazione dell’immagine
…..
w1 w2 w3 w4 …
p. 56
immagine presa da: Tutorial CVPR 07
Effetti dell’uso del dizionario

Ho ridotto il numero dei possibili valori che
una feature può assumere da |Rk| a n
(n << |Rk| )


Cercare feature simili ai prototipi di base è più
stabile che cercare un determinato valore di
feature
Nello spazio delle frequenze (S = Rn) posso
applicare tecniche di classificazione simili a
quelle usate, ad ese., nel text categorization
p. 57



Costruzione vocabolario
Rappresentazione delle immagini
Classificazione 
p. 58
Ultimo passo: classificazione



Situazione: posso rappresentare un’immagine
I tramite un vettore di occorrenze di keywords
x
Obiettivo: dato x, voglio stabilire quale oggetto
è presente in I con minore probabilità di
sbagliarmi
Userò nuovamente T
p. 59
Ese: classificazione duale

T = {(I1, y1), …, (IN, yN)},
dove:
yj {“auto”, “non-auto”}
p. 60
Esempio di rappresentazione
grafica di T in Rn (n, m = 2)
p. 61
Esempio [2]

Rappresentazione (x) di una nuova immagine
(I)
p. 62
Teoria Decisionale Bayesiana


Data l’immagine x e m classi di oggetti C1, …
Cm, associare x alla classe più probabile
Scelgo Cj* tale che:
Notazione abbreviata:
p. 63
Esempio

Le probabilità sono stimate tramite training
p. 64
immagine presa da: Duda, Hart, Stork, Pattern Classification
Metodi discriminativi

Mirano a determinare i bordi di decisione
(superfici iper-dimensionali) che meglio
partizionano Rn rispetto alle classi d’interesse
p. 65
Bordi di decisione: ese.
monodimensionale
c2
c1
c2
c1
p. 66
Bordo di decisione: ese.
bidimensionale
p. 67
Esempi di classificatori
discriminativi






Reti neurali (ANN)
Support Vector Machines (SVM)
Decision Trees
K-Nearest Neighbor (k-NN)
Boosting
…
p. 68
Bags of Words: riassunto
1.
2.
3.
Scelta delle feature per rappresentare le img
e costruzione dello spazio delle feature F
Attraverso un training set di img e tecniche
di clustering, costruisco il dizionario D delle
feature scegliendo i prototipi di feature più
comuni (“words”)
Utilizzando D rappresento il training set di
img nello spazio delle frequenze (S) delle
words
p. 69
Bags of Words: riassunto [2]
4.
5.
6.
Utilizzo tecniche di classificazione in S per
costruire un classificatore statistico C
On-line, associo gli elementi di D ad una
nuova img (I) e ne conto la frequenza
Posso quindi rappresentare I in S e
utilizzare C per classificarla
p. 70
Annotazioni di video


Un video è una sequenza di immagini (frame),
per cui potrei applicare tecniche di image
classification (e.g., ai soli key frame)
Tuttavia si rileva normalmente più efficace
studiare approcci ad hoc per tipi di video
differenti (film, news, video sportivi, pubblicità,
…)
p. 71
Nei video sono spesso già presenti
alcune informazioni testuali


“Content independent-Metadata”: titolo,
autore, produttore, data..
Sottotitoli e trascrizioni degli autori
p. 72
Esempio: annotazione di video
sportivi

Annotare può significare riconoscere azioni di
gioco importanti (nel calcio, nel tennis, …) e
indicizzare i punti esatti in cui avvengono
p. 73
Esempio: annotazione di film



Riconoscere gli attori (face recognition)
Riconoscere il tipo di scena (allegra, triste,
drammatica, suspance, …) da alcune sue
caratteristiche come l’intensità luminosa o
della colonna sonora, …
…
p. 74
Annotazioni audio


E’ anzitutto necessario distinguere
(classificare…) le parti del file audio che
contengono una parte parlata da altri suoni o
musiche
Tecniche di speech recognition possono
quindi essere utilizzate per trasformare il
parlato in testo
p. 75
Annotazioni audio [2]


La qualità del riconoscimento può essere
elevata per sistemi speaker-dependent
Qualità accettabili ai fini del retrieval anche
per sistemi speaker-independent
p. 76
Alcuni riferimenti




Forsyth, Ponce, Computer Vision, a Modern
Approach 2003,
Duda, Hart, Stork, Pattern Classification (II
edition) 2001,
Bishop, Pattern Recognition and Machine
Learning, 2006
Fergus, Fei-Fei, Perona, Zisserman, Learning
Object Categories from Google’s Image
Search, ICCV 05
p. 77
Domande…
p. 78