際際滷

際際滷Share a Scribd company logo

Content-based Image Retrieval con Relevance Feedback

M
mrabbi
1 of 40
Downloaded 31 times
Random Walker for Content-Based Image Retrieval with Relevance Feedback Massimo Rabbi
Contenuti della presentazione Image Retrieval CBIR: content-based VS text-based Relevance Feedback Analisi del lavoro di tesi Formulazione graph-based Caso dellimage segmentation Random walker per limage retrieval Test sperimentali Conclusioni e sviluppi futuri
La ricerca di immagini 1/3 Che cos竪 lImage Retrieval? Perch辿 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
La ricerca di immagini 2/3 Come interrogare un sistema di IR? Query by example Query by sketch Query by text Alcune applicazioni Sistemi di ricerca per il web Sicurezza e biometria GIS Beni culturali Diagnostica medicale Giornalismo e pubblicit
La ricerca di immagini 3/3 Alcuni esempi:
CBIR: Ricerca su contenuti 1/3 Content-Based VS Text-Based: Impensabile annotazione manuale La stessa immagine ha significati diversi per persone diverse Diversi livelli di dettaglio per descrivere unimmagine Esempio: pascolo, mucche, pastore, persona, prato, montagna, alberi, animali
CBIR: Ricerca su contenuti 2/3 Concetto di informazione visuale visuale 竪 la query visuale 竪 il ragionamento che guida la similitudine visuali sono i criteri usati per lindicizzazione Il recupero delle immagini 竪 legato agli elementi percettivi usati per descrivere le immagini: features basate su colore, shape, texture etc. features complesse, vedi SIFT o GIST
CBIR: Ricerca su contenuti 3/3 Problemi e ambiti di ricerca aperti: la questione semantic gap domini delle immagini: narrow vs broad features e misure di similarit interazione dellutente Il semantic gap 竪 la fonte principale di problemi!
Relevance feedback Tecnica nata negli anni 60 nellambito del document retrieval e ripresa con interesse dalla comunit CBIR verso inizio-met anni 90 Metodo fondamentale per attaccare il problema del semantic gap. Concetto chiave di user-in-the-loop.
Temi del relevance feedback Modelli di feedback: positivo, positivo-negativo, positivo-neutro-negativo, grado di rilevanza Short-term VS Long-term learning. Query localizzate e uso di sotto-immagini. Incorporamento di metadati testuali. Tecniche per sfruttare le immagini non etichettate: semi-supervised learning e active learning Ricalcolo del query-point e feature re-weighting. Metodi kernel: approcci SVM-based. Metodi probabilistici.
Analisi del lavoro di tesi svolto Algoritmo di relevance feedback per limage retrieval, in particolare CBIR. Approccio graph-based: i nodi rappresentano le immagini; i pesi sugli archi rappresentano la similarit Concetto di base: random walker. Analogie con algoritmo gi esistente nel campo dellimage segmentation. Legami tra la teoria dei random walker su grafi, la teoria del potenziale nel discreto e i circuiti elettrici.
Formulazione graph-based 1/2 Input del sistema: grafo pesato , insieme di vertici , funzione Output del sistema: ranking vector Problema di ottimizzazione: con i vincoli: (a) (b)
Formulazione graph-based 2/2 Riscrivendo in forma matriciale: e pi湛 precisamente come: Derivando rispetto a : Risoluzione di un sistema di equazioni lineari nelle variabili .
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 di Markov time-reversible. Il random walk soddisfa infatti la cosiddetta Propriet di Markov: Dato un grafo indiretto , i pesi sugli archi indicano la probabilit di spostarsi verso il nodo vicino. Esempio di random walker: la navigazione di un utente nel web.
Ispirazione dallimage segmentation Algoritmo di image segmentation interattivo proposto da Leo Grady (2006). Limmagine 竪 un grafo i cui nodi sono i pixel. Dati un certo numero di pixel predefiniti dallutente (seeds) viene calcolata la probabilit che un random walker li raggiunga, partendo da uno qualsiasi dei pixel non etichettati. Ad ogni pixel viene assegnata letichetta con la probabilit pi湛 alta.
Ispirazione dallimage segmentation Algoritmo di image segmentation interattivo proposto da Leo Grady (2006). Limmagine 竪 un grafo i cui nodi sono i pixel. Dati un certo numero di pixel predefiniti dallutente (seeds) viene calcolata la probabilit che un random walker li raggiunga, partendo da uno qualsiasi dei pixel non etichettati. Ad ogni pixel viene assegnata letichetta con la probabilit pi湛 alta.
Il problema di Dirichlet Le probabilit del random walker possono essere ottenute risolvendo il problema di Dirichlet. La sua formulazione combinatoria 竪 la seguente: Riscrivendo otteniamo: Derivando rispetto a :
Analogia con i circuiti elettrici La soluzione al problema combinatorio di Dirichlet su un grafo arbitrario 竪 data esattamente dalla distribuzione dei potenziali elettrici sui nodi di un circuito. I resistori che collegano i nodi del circuito rappresentano linverso dei pesi (conduttanza). Le condizioni vengono imposte fissando il potenziale elettrico sui nodi specifici (seed).
Analogia con i circuiti elettrici La soluzione al problema combinatorio di Dirichlet su un grafo arbitrario 竪 data esattamente dalla distribuzione dei potenziali elettrici sui nodi di un circuito. I resistori che collegano i nodi del circuito rappresentano linverso dei pesi (conduttanza). Le condizioni vengono imposte fissando il potenziale elettrico sui nodi specifici (seed).
Random walker per limage 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: I round di feedback per popolare linsieme di seed.
Pseudo-codice dellalgoritmo
Codice Matlab dellalgoritmo
Test sperimentali Datasets 1/2 Wang Dataset 1000 immagini 10 categorie Oliva Dataset 2688 immagini 8 categorie
Test sperimentali Datasets 2/2 Custom-Caltech Dataset 4920 immagini 43 categorie
Test sperimentali Features 1/4 Color Histogram: rappresentazione della distribuzione del colore in unimmagine spazio dei colori HSV 8 intervalli per canale H e 4 per canale S vettore finale 32-D Color Histogram Layout: suddivisione dellimmagine in 4 parti feature Color Histogram applicata ad ogni sotto- immagine vettore finale 32-D (HxSxSub-img = 4x4x2)
Test sperimentali Feature 2/4 Color Moments: la distribuzione del colore come distribuzione di probabilit spazio dei colori HSV per ogni canale vengono estratti 3 color moment 1) mean, valore medio 2) deviazione standard, della distribuzione 3) skewness, grado di simmetria della distribuzione vettore finale 9-D
Test sperimentali Feature 3/4 Gray Level Co-Occurrence Matrix (GLCM): feature di tipo texture considera la relazione spaziale tra i pixel ecco perch辿 detta anche Gray Level Spatial Dependence Matrix vettore finale 20-D
Test sperimentali Feature 3/4 Gray Level Co-Occurrence Matrix (GLCM): feature di tipo texture considera la relazione spaziale tra i pixel ecco perch辿 detta anche Gray Level Spatial Dependence Matrix vettore finale 20-D
Test sperimentali Feature 4/4 Global scene (GIST): The gist is an abstract representation of the scene that spontaneously activates memory representations of scene categories (a city, a mountain, etc.) [cit.] tenta di dare una rappresentazione di immagini reali complesse usando le cosiddette Spatial Envelope properties individuare la shape-of-the-scene vettore finale 60-D
Test sperimentali Feature 4/4 Global scene (GIST): The gist is an abstract representation of the scene that spontaneously activates memory representations of scene categories (a city, a mountain, etc.) [cit.] tenta di dare una rappresentazione di immagini reali complesse usando le cosiddette Spatial Envelope properties individuare la shape-of-the-scene vettore finale 60-D
Test Sperimentali: Algoritmi e impostazioni 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.
Risultati Esempio di query Immagine di query Risultati dopo k-NN Risultati dopo 1 RF Risultati dopo 3 RF Risultati dopo 6 RF
Risultati - Precisione della ricerca (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.
Risultati Scelta delle features
Risultati Performance sui tempi (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.
Risultati Implementazione sparsa Feature usata: Color Moments. Random query: 500 query random su dataset Oliva. Dimensione scope: 20 elementi. Versione sparsa: regola di approssimazione k-nn con k = 20
Conclusioni Proposto un nuovo algoritmo per il CBIR con relevance feedback Bont dei risultati sperimentali ottenuti. Metodo semplice da implementare e parameter- free. Possibilit di utilizzo in versione sparsa con dataset pi湛 grandi. 11属 European Conference on Computer Vision (ECCV 2010) S. Rota Bul嘆, M. Rabbi, M. Pelillo Paper submitted.
Sviluppi futuri Modello di feedback: es. Query multi-immagine. Estendere la parte sperimentale: implementazione sparsa datasets features Implementazione di un sistema completo di IR.
The End Grazie per lattenzione! contatti: Massimo Rabbi massimo.rabbi@gmail.com http://www.securnetwork.net
Bibliografia

More Related Content

Content-based Image Retrieval con Relevance Feedback

  • 1. Random Walker for Content-Based Image Retrieval with Relevance Feedback Massimo Rabbi
  • 2. Contenuti della presentazione Image Retrieval CBIR: content-based VS text-based Relevance Feedback Analisi del lavoro di tesi Formulazione graph-based Caso dellimage segmentation Random walker per limage retrieval Test sperimentali Conclusioni e sviluppi futuri
  • 3. La ricerca di immagini 1/3 Che cos竪 lImage Retrieval? Perch辿 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
  • 4. La ricerca di immagini 2/3 Come interrogare un sistema di IR? Query by example Query by sketch Query by text Alcune applicazioni Sistemi di ricerca per il web Sicurezza e biometria GIS Beni culturali Diagnostica medicale Giornalismo e pubblicit
  • 5. La ricerca di immagini 3/3 Alcuni esempi:
  • 6. CBIR: Ricerca su contenuti 1/3 Content-Based VS Text-Based: Impensabile annotazione manuale La stessa immagine ha significati diversi per persone diverse Diversi livelli di dettaglio per descrivere unimmagine Esempio: pascolo, mucche, pastore, persona, prato, montagna, alberi, animali
  • 7. CBIR: Ricerca su contenuti 2/3 Concetto di informazione visuale visuale 竪 la query visuale 竪 il ragionamento che guida la similitudine visuali sono i criteri usati per lindicizzazione Il recupero delle immagini 竪 legato agli elementi percettivi usati per descrivere le immagini: features basate su colore, shape, texture etc. features complesse, vedi SIFT o GIST
  • 8. CBIR: Ricerca su contenuti 3/3 Problemi e ambiti di ricerca aperti: la questione semantic gap domini delle immagini: narrow vs broad features e misure di similarit interazione dellutente Il semantic gap 竪 la fonte principale di problemi!
  • 9. Relevance feedback Tecnica nata negli anni 60 nellambito del document retrieval e ripresa con interesse dalla comunit CBIR verso inizio-met anni 90 Metodo fondamentale per attaccare il problema del semantic gap. Concetto chiave di user-in-the-loop.
  • 10. Temi del relevance feedback Modelli di feedback: positivo, positivo-negativo, positivo-neutro-negativo, grado di rilevanza Short-term VS Long-term learning. Query localizzate e uso di sotto-immagini. Incorporamento di metadati testuali. Tecniche per sfruttare le immagini non etichettate: semi-supervised learning e active learning Ricalcolo del query-point e feature re-weighting. Metodi kernel: approcci SVM-based. Metodi probabilistici.
  • 11. Analisi del lavoro di tesi svolto Algoritmo di relevance feedback per limage retrieval, in particolare CBIR. Approccio graph-based: i nodi rappresentano le immagini; i pesi sugli archi rappresentano la similarit Concetto di base: random walker. Analogie con algoritmo gi esistente nel campo dellimage segmentation. Legami tra la teoria dei random walker su grafi, la teoria del potenziale nel discreto e i circuiti elettrici.
  • 12. Formulazione graph-based 1/2 Input del sistema: grafo pesato , insieme di vertici , funzione Output del sistema: ranking vector Problema di ottimizzazione: con i vincoli: (a) (b)
  • 13. Formulazione graph-based 2/2 Riscrivendo in forma matriciale: e pi湛 precisamente come: Derivando rispetto a : Risoluzione di un sistema di equazioni lineari nelle variabili .
  • 14. 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 di Markov time-reversible. Il random walk soddisfa infatti la cosiddetta Propriet di Markov: Dato un grafo indiretto , i pesi sugli archi indicano la probabilit di spostarsi verso il nodo vicino. Esempio di random walker: la navigazione di un utente nel web.
  • 15. Ispirazione dallimage segmentation Algoritmo di image segmentation interattivo proposto da Leo Grady (2006). Limmagine 竪 un grafo i cui nodi sono i pixel. Dati un certo numero di pixel predefiniti dallutente (seeds) viene calcolata la probabilit che un random walker li raggiunga, partendo da uno qualsiasi dei pixel non etichettati. Ad ogni pixel viene assegnata letichetta con la probabilit pi湛 alta.
  • 16. Ispirazione dallimage segmentation Algoritmo di image segmentation interattivo proposto da Leo Grady (2006). Limmagine 竪 un grafo i cui nodi sono i pixel. Dati un certo numero di pixel predefiniti dallutente (seeds) viene calcolata la probabilit che un random walker li raggiunga, partendo da uno qualsiasi dei pixel non etichettati. Ad ogni pixel viene assegnata letichetta con la probabilit pi湛 alta.
  • 17. Il problema di Dirichlet Le probabilit del random walker possono essere ottenute risolvendo il problema di Dirichlet. La sua formulazione combinatoria 竪 la seguente: Riscrivendo otteniamo: Derivando rispetto a :
  • 18. Analogia con i circuiti elettrici La soluzione al problema combinatorio di Dirichlet su un grafo arbitrario 竪 data esattamente dalla distribuzione dei potenziali elettrici sui nodi di un circuito. I resistori che collegano i nodi del circuito rappresentano linverso dei pesi (conduttanza). Le condizioni vengono imposte fissando il potenziale elettrico sui nodi specifici (seed).
  • 19. Analogia con i circuiti elettrici La soluzione al problema combinatorio di Dirichlet su un grafo arbitrario 竪 data esattamente dalla distribuzione dei potenziali elettrici sui nodi di un circuito. I resistori che collegano i nodi del circuito rappresentano linverso dei pesi (conduttanza). Le condizioni vengono imposte fissando il potenziale elettrico sui nodi specifici (seed).
  • 20. Random walker per limage 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: I round di feedback per popolare linsieme di seed.
  • 23. Test sperimentali Datasets 1/2 Wang Dataset 1000 immagini 10 categorie Oliva Dataset 2688 immagini 8 categorie
  • 24. Test sperimentali Datasets 2/2 Custom-Caltech Dataset 4920 immagini 43 categorie
  • 25. Test sperimentali Features 1/4 Color Histogram: rappresentazione della distribuzione del colore in unimmagine spazio dei colori HSV 8 intervalli per canale H e 4 per canale S vettore finale 32-D Color Histogram Layout: suddivisione dellimmagine in 4 parti feature Color Histogram applicata ad ogni sotto- immagine vettore finale 32-D (HxSxSub-img = 4x4x2)
  • 26. Test sperimentali Feature 2/4 Color Moments: la distribuzione del colore come distribuzione di probabilit spazio dei colori HSV per ogni canale vengono estratti 3 color moment 1) mean, valore medio 2) deviazione standard, della distribuzione 3) skewness, grado di simmetria della distribuzione vettore finale 9-D
  • 27. Test sperimentali Feature 3/4 Gray Level Co-Occurrence Matrix (GLCM): feature di tipo texture considera la relazione spaziale tra i pixel ecco perch辿 detta anche Gray Level Spatial Dependence Matrix vettore finale 20-D
  • 28. Test sperimentali Feature 3/4 Gray Level Co-Occurrence Matrix (GLCM): feature di tipo texture considera la relazione spaziale tra i pixel ecco perch辿 detta anche Gray Level Spatial Dependence Matrix vettore finale 20-D
  • 29. Test sperimentali Feature 4/4 Global scene (GIST): The gist is an abstract representation of the scene that spontaneously activates memory representations of scene categories (a city, a mountain, etc.) [cit.] tenta di dare una rappresentazione di immagini reali complesse usando le cosiddette Spatial Envelope properties individuare la shape-of-the-scene vettore finale 60-D
  • 30. Test sperimentali Feature 4/4 Global scene (GIST): The gist is an abstract representation of the scene that spontaneously activates memory representations of scene categories (a city, a mountain, etc.) [cit.] tenta di dare una rappresentazione di immagini reali complesse usando le cosiddette Spatial Envelope properties individuare la shape-of-the-scene vettore finale 60-D
  • 31. Test Sperimentali: Algoritmi e impostazioni 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.
  • 32. Risultati Esempio di query Immagine di query Risultati dopo k-NN Risultati dopo 1 RF Risultati dopo 3 RF Risultati dopo 6 RF
  • 33. Risultati - Precisione della ricerca (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.
  • 34. Risultati Scelta delle features
  • 35. Risultati Performance sui tempi (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.
  • 36. Risultati Implementazione sparsa Feature usata: Color Moments. Random query: 500 query random su dataset Oliva. Dimensione scope: 20 elementi. Versione sparsa: regola di approssimazione k-nn con k = 20
  • 37. Conclusioni Proposto un nuovo algoritmo per il CBIR con relevance feedback Bont dei risultati sperimentali ottenuti. Metodo semplice da implementare e parameter- free. Possibilit di utilizzo in versione sparsa con dataset pi湛 grandi. 11属 European Conference on Computer Vision (ECCV 2010) S. Rota Bul嘆, M. Rabbi, M. Pelillo Paper submitted.
  • 38. Sviluppi futuri Modello di feedback: es. Query multi-immagine. Estendere la parte sperimentale: implementazione sparsa datasets features Implementazione di un sistema completo di IR.
  • 39. The End Grazie per lattenzione! contatti: Massimo Rabbi massimo.rabbi@gmail.com http://www.securnetwork.net