�ݺ�ߣ

Random Walker for Content-Based Image Retrieval
with Relevance Feedback

Massimo Rabbi

Universit` Ca’ Foscari di Venezia
a
Dipartimento di Informatica

Laurea Specialistica in Informatica
16 aprile 2010

Image Retrieval - La ricerca di immagini
• Perch` cercare immagini?
e
◦ 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 pubblicit`
a
◦ Beni culturali

2 of 20

CBIR - La ricerca basata sul contenuto

• Content-Based VS Text-Based
• Concetto di “informazione visuale”
◦ visuale ` la query
e
◦ visuale ` il ragionamento che guida la similitudine
e
◦ 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 similarit` a
◦ interazione dell’utente

3 of 20

Relevance Feedback
• Tecnica nata negli anni ’60 nell’ambito del document retrieval e
ripresa con interesse dalla comunit` CBIR verso inizio-met` anni
a a
’90.
• Metodo fondamentale per attaccare il problema del “semantic
gap”.
• 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 particolare
CBIR.
• Approccio graph-based:
◦ i nodi rappresentano le immagini;
◦ i pesi sugli archi rappresentano la similarit`.
a
• Concetto di base: random walker.
• Analogie con algoritmo gi` esistente nel campo dell’image
a
segmentation.
• Legami tra la teoria dei random walk su graﬁ, la teoria del
potenziale nel discreto e i circuiti elettrici.

5 of 20

Formulazione basata sulla teoria dei graﬁ 1/2

• Input del sistema: grafo pesato G = (V , E , w ), insieme di vertici
(r )
VL ⊆ V , funzione Ψ : V → {0, 1}.
• Output del sistema: ranking vector x(r ) .
• Problema di ottimizzazione:

x(r ) = arg min (xi − xj )2 wij
x
(i,j)∈E

• con i vincoli:
(r )
(a) 0 ≤ xi ≤ 1, for all i ∈ V
(r ) (r )
(b) xi = Ψ(i), for all i ∈ VL

6 of 20

Formulazione basata sulla teoria dei graﬁ 2/2

• Riscrivendo in forma matriciale:
x(r ) = arg min x Lx ,
x
(r )
con xi = Ψ(i) per tutti i ∈ VL

• e pi` precisamente come:
u
LUU LUM xU
x(r ) = arg min [xU xM ]
LMU LMM xM
xU

• Derivando rispetto a xU :
LUU xU = −LUM xM
• Risoluzione di un sistema di equazioni lineari nelle variabili xU .

7 of 20

Random walk su graﬁ

• I graﬁ come struttura per rappresentare i dati di un problema.
• Un random walk su un grafo indiretto corrisponde ad una catena di
Markov time-reversible.
• Il random walk soddisfa infatti la cosiddetta Propriet` di Markov :
a

P (Xt+1 |X0 , X1 , ..., Xt ) = P (Xt+1 |Xt ) .

• Dato un grafo indiretto G = (V , E , w ), i pesi sugli archi indicano
la probabilit` di spostarsi verso il nodo vicino.
a
• 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 Leo
Grady (2006).
• L’immagine ` un grafo di pixel.
e
• Fondamenta nella teoria dei random walk su graﬁ.
• Input: un numero di pixel predeﬁniti dall’utente, chiamati seed.
• Output: immagine segmentata

9 of 20

Il problema di Dirichlet
• Le probabilit` del random walker possono essere ottenute
a
risolvendo il problema di Dirichlet.
• La sua formulazione combinatoria ` la seguente:
e
1 1
D[x] = xT Lx = wij (xi − xj )2
2 2
eij ∈E

• Riscrivendo otteniamo:

1 T LM B xM
D[xU ] = x xT
2 M U BT LU xU

• Derivando rispetto a xU :

LU xU = −B T xM
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 “non
rilevante”.
• I pesi sugli archi rappresentano la similarit` tra coppie di immagini:
a

||Ii − Ij ||
wij = exp −
σ
• 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

100 100 100
RS
90 90 90 RS-S
RW
80 80 80 MRW
FR
Precision (%)

Precision (%)

Precision (%)
70 70 70
60 60 60
50 50 50
40 40 40
RS RS
30 RS-S 30 RS-S 30
RW RW
20 MRW 20 MRW 20
FR FR
10 10 10
0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8
Feedback Rounds Feedback Rounds Feedback Rounds

(a) Wang Dataset (b) Oliva Dataset (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
100 100 100
90 90 90
80 80 80
Precision (%)

Precision (%)

Precision (%)
70 70 70
60 60 60
50 50 50
40 40 40
RS RS RS
30 RS-S 30 RS-S 30 RS-S
RW RW RW
20 MRW 20 MRW 20 MRW
FR FR FR
10 10 10
0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8

(a) Color Histogram (b) Color Histogram Layout (c) Color Moments
100 100
90 90
80 80
Precision (%)

Precision (%)
70 70
60 60
50 50
40 40
RS RS
30 RS-S 30 RS-S
RW RW
20 MRW 20 MRW
FR FR
10 10
0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8
Feedback Rounds Feedback Rounds

(d) GLCM (e) GIST
16 of 20

Test sperimentali - Perfomance sui tempi

10 1000
100 RS
RS-S
RW
1 10 100 MRW
Average time per round


FR
0.1 1 10

0.1
0.01 1
0.01
0.001 0.1
0.001
RS RS
0.0001 RS-S RS-S 0.01
RW 0.0001 RW
MRW MRW
FR FR
1e-05 1e-05 0.001
0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8

(a) Wang Dataset (b) Oliva Dataset (c) Custom Caltech Dataset

• Feature usata: Color Histogram.
• Random query: 500 query per (a) e (b), 100 query (c).

17 of 20

Test sperimentali - Implementazione sparsa
100 1
90

80
Precision (%)

70 0.1
60
50
40 0.01
30
20 Original G Original G
Sparse G Sparse G
10 0.001
0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8
Feedback Rounds Feedback Rounds

(a) Precisione (b) Tempi per round

• Feature scelta: Color Moments.
• Query random: 500 query random su dataset Oliva.
• 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.
• Bont` dei risultati sperimentali ottenuti.
a
• Metodo semplice da implementare e parameter-free.
• Possibilit` di utilizzo in versione sparsa in dataset pi` grandi.
a u
• 11th European Conference on Computer Vision (ECCV 2010) -
S.Rota Bul`, M.Rabbi, M.Pelillo - Paper Submitted.
o

• 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

��ǲ��ﬁa

R. Datta, D. Joshi, J. Li, J.Z. Wang.
Image retrieval: Ideas, inﬂuences, 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 and
challenges.
ACM Transactions on Multimedia Computing, Communications and
Applications 2, 1-19, 2006.
L. Grady.
Random Walks for Image Segmentation.
IEEE Trans. on Pattern Analysis and Machine Intelligence, 1768-1783, 2006.
L. Lov´sz.
a
Random Walks on Graphs: A survery.
Combinatorics, Paul Erd¨s is Eighty (Vol. 2), 1-46, 1993.
o

20 of 20

�ݺ�ߣ

Tesi specialistica Informatica

More Related Content

Tesi specialistica Informatica