Multimedia Information
Retrieval
Enver Sangineto,
Dipartimento di Informatica
[email protected]
Problema

Nel Web e nei DB “locali” esiste molta informazione
non esclusivamente testuale:





audio (speech, musica…)
immagini,
video,
…
Come recuperare efficacemente materiale
multimediale?
p. 2
Esempi di applicazione

Web indexing:





Recupero di materiale multimediale dal Web,
Sistemi capaci di bloccare immagini pubblicitarie
oppure illegali/indesiderate
Trademark e copyright
Accesso ai musei
DB commerciali
p. 3
Esempi di applicazione [2]





Immagini satellitari (applicazioni militari,
government, …)
Immagini mediche
Entertainment
Criminal investigation
…
p. 4
Prima generazione di multimedia
information retrieval systems

Off-line: il materiale multimediale viene
associato con una descrizione testuale. Ese.:



Annotazione manuale (“content descriptive
metadata”)
Il testo che in una pagina Web circonda l’img
On-line: utilizzo di tecniche di IR testuali
basate sul “keyword match”
p. 5
p. 6
immagine presa da: A. Del Bimbo, Visual Information Retrieval
Limiti dell’approccio esclusivamente
testuale


L’annotazione manuale di grossi DB
multimediali è impensabile…
Non è facile descrivere verbalmente il
contenuto percettivo di un’immagine, di un
video o di un brano musicale…
p. 7
Esempi




Cercare una canzone conoscendone solo il
ritornello
Cercare una determinata azione in un video
sportivo
Cercare dipinti che hanno un determinato
dosaggio di colori
…
p. 8
Esempi [2]

Google Image può restituire fino ad un 85% di
documenti NON rilevanti anche per query semplici
(e.g., oggetti specifici) [1]

[1] Fergus, Fei-Fei, Perona, Zisserman, Learning Object Categories from
Google’s Image Search, ICCV 05
p. 9
Soluzioni in fase di ricerca…

Sistemi “Content Based”:

Si basano sul contenuto percettivo dell’oggetto
multimediale. Tipicamente:



utilizzano una query by example e
modellano direttamente la similitudine percettiva tra la
query e gli oggetti del DB
Sistemi di annotazione automatica:


Fase di pre-processing (“information extraction”):
viene estratta (in maniera automatica!)
informazione da elementi non testuali e
memorizzata sotto forma simbolica (e.g., testuale)
Il retrieval (on-line) avviene con tecniche
“tradizionali”
p. 10
Differenze rispetto all’IR Testuale…



Un problema comune a tutti i sistemi di
Multimedia IR è il trattamento di informazione
non simbolica
Un testo può essere visto come la
combinazione di elementi simbolici atomici (le
parole o token)
Un’immagine è una collezione di pixel e un
suono un’onda sonora…
p. 11
Cosa vedremo in queste tre lezioni…

Introduzione ai sistemi content based basati
su caratteristiche percettive quali:


Colore, movimento, suono, forma…
Sistemi di annotazione automatica
p. 12
Elementi tipici di un sistema di
Content Based Multimedia IR

Dal punto di vista dell’utente:



La query è un oggetto multimediale (e.g.,
un’immagine, un disegno, un elemento audio, …)
L’output è una lista di elementi ordinati in base
alla somiglianza percettiva con la query
Esistono strumenti opzionali di interazione per
visualizzare collezioni di immagini o fornire
feedback al sistema
p. 13
Esempio: query by image example
La query è
un particolare
p. 14
Query by image example [2]
Notate che query e
particolare possono
non essere identici.
Ad es. la query può
essere scelta da un’
immagine prima di
un restauro
p. 15
Query by image example (sketch)
[3]
p. 16
immagine presa da: A. Del Bimbo, Visual Information Retrieval
Elementi tipici di un sistema di
Content Based Multimedia IR [2]

Dal punto di vista del sistema:




Rappresentazione dell’oggetto multimediale (e.g.,
spazio delle feature)
Modellazione del concetto di similitudine
percettiva (e.g., attraverso appositi algoritmi di
matching)
Utilizzo di strutture dati particolari che permettano
un indexing efficiente dello spazio delle feature
Gestione dell’eventuale relevance feedback (non
verrà trattato…)
p. 17
Rappresentazione
p. 18
Rappresentazione tramite Feature di
un’immagine


Una feature è una rappresentazione, tramite
un vettore di valori numerici, di tutta o parte
dell’immagine
Se I' è una sottoparte dell’immagine I, allora
una feature f è t.c.:
f(I')  Rk,
f(I') = (v0, … vk-1)T,
k >= 1
p. 19
Feature per rappresentare
un’immagine [2]


In genere una feature è una caratteristica
facilmente misurabile dell’immagine
L’immagine in esame viene quindi descritta
usando i valori di un insieme di feature prescelte f1, …, fn
p. 20
Feature globali e locali

I' = I: feature globale
I'  I: feature locale

Feature locali:



È importante capire come selezionare le
sottoparti di I (I‘1, I‘2, …) da rappresentare
Più robuste ad occlusioni, parti mancanti,
separazione dal background
p. 21
Esempio: feature locale
fi(I')
I'
I
p. 22
immagine presa da: Tutorial CVPR 07
Alcuni semplici esempi di feature:
istogrammi dell’intensità di grigio

Istogramma dell’intensità dei pixel in I':




Divido il range [0, 255] in k bin
Assegno ogni pixel ad un bin: I(p) -> divk(I(p))
f(I') = (v0, …, vk-1)T, dove:
vi = # { p  I’ : divk(I(p)) = i}
p. 23
Alcuni semplici esempi di feature:
geometria facciale
f(I) = (d1 , d2 , d3 , d4)T
p. 24
Spazio delle Feature



Supponendo di utilizzare n features a valori in
R, I può essere rappresentata tramite il
vettore x(I) = (f1(I), …fn(I))T
x(I) è ottenuto concatenando il valore delle
singole feature
x(I) è un punto in Rn, detto spazio delle
feature
p. 25
Spazio delle Feature [2]

In generale, se:

allora: x(I) = (f1(I) T
Rn*k
fi(I)  Rk,
 … fn(I) T)T è un punto in
p. 26
Es.: Spazio delle Feature (R2)
p. 27
Spazio delle Feature [3]


E’ un concetto simile ma non identico allo
spazio vettoriale usato per rappresentare la
frequenza dei termini nei documenti testuali
E’ la rappresentazione dei dati più usata nei
vari sistemi content based (immagini, video,
audio) ma non è l’unica!
p. 28
Similitudine
p. 29
Similitudine percettiva



Nel text retrieval, la similitudine tra due
documenti può essere stimata in funzione dei
termini in comune
Ad esempio, rappresentando la frequenza dei
termini di un documento in un apposito spazio
vettoriale, la distanza tra punti in tale spazio
descrive la dissimilarità tra documenti
Lo spazio delle feature si comporta in maniera
analoga…
p. 30
Similitudine percettiva [2]


Nello spazio delle feature la differenza
percettiva tra I1 e I2 è proporzionale ad una
determinata misura di distanza (non
necessariamente Euclidea): dist(x(I1),x(I2))
Data la query Q, l’output del sistema è una
lista di immagini I1, I2, … ordinata
minimizzando:
I1 = minI dist(x(Q),x(I)), …
p. 31
Esempio (R2)
p. 32
Similitudine percettiva [3]

Altri algoritmi di matching fanno uso di
rappresentazioni più complesse o alternative
allo spazio delle feature e sono tipicamente
studiati ad hoc per il particolare sistema di
MIR
p. 33
Indexing
p. 34
Tecniche di Indexing


Problema: come indicizzare efficientemente
dei dati in uno spazio multidimensionale?
La maggior parte delle più comuni strutture
dati per la ricerca efficiente si basano su un
ordinamento totale dei valori rappresentati:



xi <= xj V xj <= xi (0 <= i,j <= N)
Ese.: nel caso delle keyword, l’ordine
alfabetico stabilisce un ordinamento totale del
vocabolario (e.g., negli inverted files)
In Rk ciò non è più vero
p. 35
Il k-d Tree


E’ una generalizzazione dell’albero di ricerca
binario in k dimensioni
Ad ogni livello dell’albero viene presa in
considerazione ciclicamente una delle k
feature
p. 36
Il k-d Tree [2]

Supponiamo di voler indicizzare un insieme di
punti multidimensionali:
P1, …, PN, Pi Rk, Pi =(xi1, …, xik)

Scelgo la prima dimensione (feature) e trovo il
valore L1, mediano rispetto a x11, …, xN1
p. 37
Il k-d Tree [3]




La radice dell’albero conterrà L1
Il sottoalbero sinistro (TL) conterrà i punti Pi
t.c. xi1 <= L1
Il sottoalbero destro (TR) gli altri
A livello 1 scelgo la seconda feature e,
separatamente per TL e TR, calcolo L2 e L3,
scelti in modo tale che:


L2 è mediano rispetto agli elementi xj12, xj22, …
di TL
L3 è mediano rispetto agli elementi di TR
p. 38
Il k-d Tree [4]


Dopo aver utilizzato la feature k-esima, ritorno
ciclicamente a considerare la prima feature
I punti sono associati alle foglie
p. 39
Esempio
p. 40
immagine presa da: Hemant M. Kakde, Range Searching using Kd Tree
Image, video e audio retrieval
p. 41
Retrieval by color: istogrammi di
colore

Istogramma dei colori di una parte
(eventualmente tutta) di immagine I':


Possibili rappresentazioni di un singolo pixel:
RGB, HSV, CIE LAB, …
Divido ogni canale in k bin:




f(I') = (r0,…, rk-1, g0, …, gk-1, b0, …, bk-1)T,
ri = # { p in I’: divk(R(p)) = i },
gi = # { p in I’: divk(G(p)) = i },
bi = # { p in I’: divk(B(p)) = i }
p. 42
Istogrammi di colore [2]

Oppure divido RGB in k3 bin:



f(I') = (z0,…, zh-1)T, h= k3
Se zi rappresenta i valori (i1, i2, i3), allora:
zi = # { p in I’: divk(R(p)) = i1 and divk(G(p)) = i2
and divk(B(p)) = i3 }
p. 43
Istogrammi di colore [3]: esempio
p. 44
immagine presa da: Wikipedia
Retrieval by texture
p. 45
Approccio statistico

Tamura features: analizzano la
distribuzione dell’intensità
locale dell’img al fine di
misurare caratteristiche
percettive della texture quali:
 Contrasto
 Granularità
 Direzionalità
p. 46
Esempio
field
residential
vegetation
p. 47
Approccio sintattico: grammatiche
visive

Ese. di regola di produzione per la
rappresentazione di texture (Rosenfeld):

Essa riassume le seguenti 4 regole:
p. 48
Video retrieval


Un video è semplicemente una sequenza di
molte immagini
Ogni immagine viene detta frame
p. 49
Componenti di un video


Frame: una singola immagine
Shot: Un sequenza di frame consecutivi
ripresi da una singola telecamera
 Scena: un insieme di shot consecutivi
che rispettano le 3 unità aristoteliche di
spazio, tempo e azione
p. 50
Segmentazione di una
videosequenza


Individuando gli “editing effects” (cuts,
dissolvenze, ….) tra uno shot e l’altro è
possibile suddividere (automaticamente) un
video in shot
Molto più difficile è individuare le scene
(concetto semantico)
p. 51
Tipi di ricerca per i video


I video possono essere rappresentati con dei
“key frame” rappresentativi di ogni shot
Un key frame è trattabile come una “still
image”:

Si applicano le tecniche viste per le immagini
(e.g., spazio delle feature, ricerca per colore,
texture, forma, ecc.)
p. 52
Tipi di ricerca per i video

Alternativamente, è possibile cercare in un
video informazione relativa al movimento
(e.g., una particolare traiettoria in un video
sportivo, …)
p. 53
Audio retrieval
Vari tipi di audio:
 Parlato:
 E’ possibile utilizzare tecniche di speech recognition per
trasformare l’audio in testo
 Suono:
 Un qualunque segnale audio con frequenze nel range
dell’udito umano (e.g., suoni prodotti da animali…)
 Musica:
 Si tiene conto dei diversi strumenti musicali utilizzati, dei
vari tipi di suoni prodotti, degli effetti musicali, ecc.
p. 54
Tipi di Query


Query by example: viene fornito/sintetizzato
un file audio chiedendo di recuperare audio
simili
Caso particolare, Query by humming:

l’utente accenna (vocalmente o anche
fischiando…) la melodia da cercare
p. 55
Rappresentazione e similitudine


Uno spazio delle feature può essere creato
utilizzando, ad ese., istogrammi ricavati dalla
rappresentazione spettrale del segnale
La similitudine percettiva in tal caso avviene
calcolando la distanza tra punti
multidimensionali come nel caso delle
immagini

Distanze tipiche: Euclidea, Mahalanobis, distanze
per istogrammi (Histogram Intersection, KullbackLeibler divergence, Chi-quadro, ecc.)
p. 56
Aspetti percettivi diversi possono essere combinati
p. 57
Alcuni riferimenti


A. Del Bimbo, Visual Information Retrieval,
Morgan Kaufmann Publishers, Inc. San
Francisco, California", 1999
Forsyth, Ponce, Computer Vision, a Modern
Approach 2003
p. 58
Alcuni riferimenti [2]

Smeulders et al., Content-Based Image Retrieval at
the End of Early Years, IEEE PAMI 2000
 Long et al., Fundamentals of Content-based Image
Retrieval, in: D. D. Feng, W. C. Siu, H. J. Zhang
(Ed.),Multimedia Information Retrieval &
Management-Technological Fundamentals and
Applications, Springer-Verlag, New York(2003)
 Foote et al., An Overview of Audio Information
Retrieval, ACM Multimedia Systems, 1998
 Hemant M. Kakde, Range Searching using Kd Tree,
2005
p. 59
Domande…
p. 60