Random Walker for Content-Based Image Retrievalwith Relevance Feedback
Massimo Rabbi
Universita Ca’ Foscari di VeneziaDipartimento di Informatica
Laurea Specialistica in Informatica16 aprile 2010
Image Retrieval - La ricerca di immagini
• Perche cercare immagini?◦ Le immagini sono informazioni◦ Cataloghi pubblici e privati di foto/immagini
• Come cercare immagini?◦ Contenuto (Content-Based Image Retrieval)◦ Descrizione (Text-Based Image Retrieval)◦ Sistemi misti
• Possibili applicazioni◦ Sistemi di ricerca web◦ Sicurezza e biometria◦ Diagnostica medicale◦ GIS◦ Giornalismo e pubblicita◦ Beni culturali
2 of 20
CBIR - La ricerca basata sul contenuto
• Content-Based VS Text-Based
• Concetto di “informazione visuale”◦ visuale e la query◦ visuale e il ragionamento che guida la similitudine◦ visuali sono i criteri utilizzati per l’indicizzazione
• Elementi percettivi per “descrivere” l’immagine◦ features basate su colore, forma, texture, etc.◦ features complesse, vedi SIFT o GIST
• Problemi e ambiti di ricerca aperti:◦ la questione “semantic gap”◦ domini delle immagini: narrow VS broad◦ features e misure di similarita◦ interazione dell’utente
3 of 20
Relevance Feedback
• Tecnica nata negli anni ’60 nell’ambito del document retrieval eripresa con interesse dalla comunita CBIR verso inizio-meta anni’90.
• Metodo fondamentale per attaccare il problema del “semanticgap”.
• Concetto chiave di “user-in-the-loop”.
4 of 20
Analisi del lavoro di tesi svolto
• Algoritmo di relevance feedback per l’image retrieval, in particolareCBIR.
• Approccio graph-based:◦ i nodi rappresentano le immagini;◦ i pesi sugli archi rappresentano la similarita.
• Concetto di base: random walker.
• Analogie con algoritmo gia esistente nel campo dell’imagesegmentation.
• Legami tra la teoria dei random walk su grafi, la teoria delpotenziale nel discreto e i circuiti elettrici.
5 of 20
Formulazione basata sulla teoria dei grafi 1/2
• Input del sistema: grafo pesato G = (V ,E ,w), insieme di vertici
V(r)L ⊆ V , funzione Ψ : V → {0, 1}.
• Output del sistema: ranking vector x(r).
• Problema di ottimizzazione:
x(r) = arg minx
∑(i ,j)∈E
(xi − xj)2wij
• con i vincoli:
(a) 0 ≤ x(r)i ≤ 1, for all i ∈ V
(b) x(r)i = Ψ(i), for all i ∈ V
(r)L
6 of 20
Formulazione basata sulla teoria dei grafi 2/2
• Riscrivendo in forma matriciale:
x(r) = arg minx
x>Lx ,
con xi = Ψ(i) per tutti i ∈ V(r)L
• e piu precisamente come:
x(r) = arg minxU
[x>U x>M ]
[LUU LUM
LMU LMM
] [xU
xM
]• Derivando rispetto a xU :
LUUxU = −LUMxM
• Risoluzione di un sistema di equazioni lineari nelle variabili xU .
7 of 20
Random walk su grafi
• I grafi come struttura per rappresentare i dati di un problema.
• Un random walk su un grafo indiretto corrisponde ad una catena diMarkov time-reversible.
• Il random walk soddisfa infatti la cosiddetta Proprieta di Markov :
P (Xt+1|X0,X1, ...,Xt) = P (Xt+1|Xt) .
• Dato un grafo indiretto G = (V ,E ,w), i pesi sugli archi indicanola probabilita di spostarsi verso il nodo vicino.
• Esempio di random walker: la navigazione di un utente nel web.
8 of 20
Random walker per l’image segmentation
• Algoritmo per l’image segmentation interattivo introdotto da LeoGrady(2006).
• L’immagine e un grafo di pixel.
• Fondamenta nella teoria dei random walk su grafi.
• Input: un numero di pixel predefiniti dall’utente, chiamati seed.
• Output: immagine segmentata
9 of 20
Il problema di Dirichlet
• Le probabilita del random walker possono essere ottenuterisolvendo il problema di Dirichlet.
• La sua formulazione combinatoria e la seguente:
D[x] =1
2xT Lx =
1
2
∑eij∈E
wij (xi − xj)2
• Riscrivendo otteniamo:
D[xU ] =1
2
[xTM xT
U
] [LM BBT LU
] [xM
xU
]• Derivando rispetto a xU :
LUxU = −BTxM
10 of 20
Analogia tra seeded segmentation e circuiti elettrici
11 of 20
Random walker per l’image retrieval
• I nuovi nodi del grafo sono le immagini.
• Gli unici due seed necessari sono le categorie “rilevante” e “nonrilevante”.
• I pesi sugli archi rappresentano la similarita tra coppie di immagini:
wij = exp
(−||Ii − Ij ||
σ
)• I round di feedback per “popolare” l’insieme di seed.
12 of 20
Test sperimentali - Datasets
• Wang Dataset - 1000 immagini - 10 categorie
• Oliva Dataset - 2688 immagini - 8 categorie
• Custom-Caltech Dataset - 4920 immagini - 43 categorie
13 of 20
Test sperimentali - Features, algoritmi e impostazioni
• Features utilizzate:◦ Color Histogram 32-D◦ Color Histogram Layout 32-D◦ Color Moments 9-D◦ Gray Level Co-Occurrence Matrix 20-D◦ Global Scene (GIST) 60-D
• Algoritmi usati per i confronti:◦ Feature Re-Weighting◦ Relevance Score◦ Relevance Score Stabilized◦ Multiple Random Walk
• 8 round di feedback.
• Dimensioni dello scope: 20,30,40.
14 of 20
Test sperimentali - Precisione della ricerca
10
20
30
40
50
60
70
80
90
100
0 1 2 3 4 5 6 7 8
Pre
cisi
on (
%)
Feedback Rounds
RS RS-S
RW MRW
FR
(a) Wang Dataset
10
20
30
40
50
60
70
80
90
100
0 1 2 3 4 5 6 7 8
Pre
cisi
on (
%)
Feedback Rounds
RS RS-S
RW MRW
FR
(b) Oliva Dataset
10
20
30
40
50
60
70
80
90
100
0 1 2 3 4 5 6 7 8
Pre
cisi
on (
%)
Feedback Rounds
RS RS-S
RW MRW
FR
(c) Custom Caltech Dataset
• Feature usata: Color Histogram.
• Random query: 500 query per (a) e (b), 100 query (c).
• Dimensione scope: 20 elementi.
15 of 20
Test sperimentali - Scelta delle feature
10
20
30
40
50
60
70
80
90
100
0 1 2 3 4 5 6 7 8
Pre
cisi
on (
%)
Feedback Rounds
RS RS-S
RW MRW
FR
(a) Color Histogram
10
20
30
40
50
60
70
80
90
100
0 1 2 3 4 5 6 7 8
Pre
cisi
on (
%)
Feedback Rounds
RS RS-S
RW MRW
FR
(b) Color Histogram Layout
10
20
30
40
50
60
70
80
90
100
0 1 2 3 4 5 6 7 8
Pre
cisi
on (
%)
Feedback Rounds
RS RS-S
RW MRW
FR
(c) Color Moments
10
20
30
40
50
60
70
80
90
100
0 1 2 3 4 5 6 7 8
Pre
cisi
on (
%)
Feedback Rounds
RS RS-S
RW MRW
FR
(d) GLCM
10
20
30
40
50
60
70
80
90
100
0 1 2 3 4 5 6 7 8
Pre
cisi
on (
%)
Feedback Rounds
RS RS-S
RW MRW
FR
(e) GIST
16 of 20
Test sperimentali - Perfomance sui tempi
1e-05
0.0001
0.001
0.01
0.1
1
10
0 1 2 3 4 5 6 7 8
Ave
rage
tim
e pe
r ro
und
Feedback Rounds
RS RS-S
RW MRW
FR
(a) Wang Dataset
1e-05
0.0001
0.001
0.01
0.1
1
10
100
0 1 2 3 4 5 6 7 8
Ave
rage
tim
e pe
r ro
und
Feedback Rounds
RS RS-S
RW MRW
FR
(b) Oliva Dataset
0.001
0.01
0.1
1
10
100
1000
0 1 2 3 4 5 6 7 8
Ave
rage
tim
e pe
r ro
und
Feedback Rounds
RS RS-S
RW MRW
FR
(c) Custom Caltech Dataset
• Feature usata: Color Histogram.
• Random query: 500 query per (a) e (b), 100 query (c).
• Dimensione scope: 20 elementi.
17 of 20
Test sperimentali - Implementazione sparsa
10
20
30
40
50
60
70
80
90
100
0 1 2 3 4 5 6 7 8
Pre
cisi
on (
%)
Feedback Rounds
Original G Sparse G
(a) Precisione
0.001
0.01
0.1
1
0 1 2 3 4 5 6 7 8
Ave
rage
tim
e pe
r ro
und
Feedback Rounds
Original G Sparse G
(b) Tempi per round
• Feature scelta: Color Moments.
• Query random: 500 query random su dataset Oliva.
• Dimensione scope: 20 elementi.
• Versione sparsa: regola di approssimazione k-nn con k=20.
18 of 20
Conclusioni e sviluppi futuri
• Proposto un nuovo algoritmo per il CBIR con relevance feedback.
• Bonta dei risultati sperimentali ottenuti.
• Metodo semplice da implementare e parameter-free.
• Possibilita di utilizzo in versione sparsa in dataset piu grandi.
• 11th European Conference on Computer Vision (ECCV 2010) -S.Rota Bulo, M.Rabbi, M.Pelillo - Paper Submitted.
• Future works:◦ Modello di feedback: es. Ψ = {0, 0.5, 1}◦ Query multi-immagine.◦ Estendere la parte sperimentale: implementazione sparsa, datasets e
features.◦ Implementazione di un sistema completo di image retrieval.
19 of 20
Bibliografia
R. Datta, D. Joshi, J. Li, J.Z. Wang.Image retrieval: Ideas, influences, and trends of the new age.ACM Computing Surveys 40, 1-60, 2008.
M.S. Lew, N. Sebe, C. Djerba, R. Jain.Content-based multimedia information retrieval: State-of-the-art andchallenges.ACM Transactions on Multimedia Computing, Communications andApplications 2, 1-19, 2006.
L. Grady.Random Walks for Image Segmentation.IEEE Trans. on Pattern Analysis and Machine Intelligence, 1768-1783, 2006.
L. Lovasz.Random Walks on Graphs: A survery.
Combinatorics, Paul Erdos is Eighty (Vol. 2), 1-46, 1993.
20 of 20