Shape-based visual information retrieval Enver Sangineto Dipartimento di Informatica...
-
Upload
bartolommeo-rubino -
Category
Documents
-
view
213 -
download
0
Transcript of Shape-based visual information retrieval Enver Sangineto Dipartimento di Informatica...
Shape-based visual information retrieval
Enver SanginetoDipartimento di Informatica
Recupero di immagini attraverso la forma
• In un’immagine, più che il colore o la texture, ciò che più caratterizza un oggetto è la sua forma
• I sistemi di Content Based Image Retrieval (CBIR) che trattano la forma accettano come query: – immagini d’esempio – disegni stilizzati (sketch)– …
Ese.: query by sketch
Pre-processing: estrazione dei bordi
• La forma di oggetto in un’immagine può essere data da:– la sagoma (e. g., i punti interni di un’img
binaria)– I bordi (interni e/o esterni)
Immagini binarie (semplice)
Immagine non binaria…
Estrazione dei contorni da immagini non binarie
• I contorni (bordi) interni e/o esterni di un oggetto sono normalmente contraddistinti da discontinuità luminose (transizione tra superfici diverse)
• Individuando le discontinuità (un cambiamento brusco dell’intensità di grigio dei pixel) è possibile rilevare i bordi e quindi la forma degli oggetti di un’immagine
Estrazione di contorni tramite operatori differenziali
• Un’immagine I può essere vista come una funzione a due variabili I(x,y): I: R2 -> R
• (sorvoliamo per ora sulla discontinuità di I)
Gradiente di un’immagine
• Il gradiente G di I nel punto (x,y) è:
• G(x,y) punta nella direzione di massima crescita di I in (x,y)
Rappresentazione alternativa
• Se:
• Allora:
• dove:– r(p) è l’intensità del gradiente in p e– φ(p) è la sua direzione
Interpretazione grafica del gradiente in un punto
Approssimazioni del gradiente
• Il gradiente può essere calcolato utilizzando delle maschere (operatori) con cui si effettua la convoluzione con I
• In pratica, le maschere sono delle matrici di coefficienti (e.g., 3X3) con cui pesare l’intensità dei pixel nell’intorno di p in una somma pesata che dà Gx(p) e Gy(p)
Operatore di Sobel
000
121
-1-2-1
Maschera per Gx
20-2
10-1
10-1
Maschera per Gy
Rappresentazioni del gradiente
• Iterando il processo per tutti i pixel p di I possiamo rappresentare i valori di G(p) (o D(p)) con nuove immagini:– Ir(p) = r(p)
– IGx(p) = Gx(p)
– IGy(p) = Gy(p)
Esempio 000
121
-1-2-1
Maschera per contorni verticali
20-2
10-1
10-1
Maschera per contorni orizzontali
IGx(p)
000
121
-1-2-1
20-2
10-1
10-1
000
2149
-2-6-2
100
-16
20-9
20-2
Gx=15
Gy=-13
r |Gx|+|Gy| = 28= arctg(-13/15)
IGy(p)
Ir: esempio
• Ir(p) = 0 <=> in un intorno di p, I è costante
Ir: esempio [2]
Ir: esempio [3]
Punti di “edge”
• Binarizzando opportunamente Ir è possibile ottenere una seconda immagine E, detta “edge map”
• E rappresenta i punti con gradiente più elevato in modulo, ovvero i punti di bordo (edge points) di I
Esempio
Esempio [2]
Shape Retrieval: Principali approcci
• Approccio statistico
• Approccio tramite template matching (deformabile)
Approccio statistico
• Si stabiliscono delle feature per rappresentare la forma degli oggetti tramite punti nello spazio delle feature Rn
• La distanza (e.g., Euclidea) tra punti in Rn corrisponde alla similarità percepita dall’utente
Ese. di feature (semplice)
• Data la sagoma (img binaria) di un’oggetto, calcolo:– L’area,– Il perimetro,– La “compattezza” (rapporto perimetro2 /
area),– …
Coefficienti di Fourier del bordo esterno
Esempio
Momenti digitali
• Supponiamo che S sia il risultato di una binarizzazione di I: S = {(x,y): I(x,y) < th}
• Per ogni coppia di interi non negativi (j,k), il momento digitale (j,k)-esimo di S è dato da:
• E’ facile constatare che M00(S) corrisponde all’area di S
Momenti digitali [2]
Vantaggi e svantaggi dell'approccio statistico
• Possibilità di indexing
• Dubbio potere discriminante (spesso le feature usate sono poco discriminanti)
• Gli oggetti devono essere completamente isolabili (problema di “segmentazione”)
Template Matching Deformabile
• Gli approcci di questo filone si basano sul tentativo di far allineare lo sketch disegnato dall'utente con (una porzione de-) l'immagine attualmente analizzata dal sistema
Template Matching Deformabile [2]
• L’ allineamento avviene deformando iterativamente lo sketch iniziale per adattarlo come se fosse un “elastico” ai bordi degli oggetti delle immagini in memoria
• Il processo iterativo termina:– quando si raggiunge una sovrapposizione
accettabile (successo), oppure: – quando il grado di deformazione supera un certo
valore massimo (fallimento)
Esempio
immagine presa da: Del Bimbo, Pala, Visual Image Retrieval by Elastic Matching of User Sketches, IEEE PAMI 1997
Esempio: Elastic Matching (Del Bimbo-Pala)
• Le immagini vengono inserite nel DB del sistema nella forma contenente solo gli edge (pre-processing)
• L'utente disegna il suo sketch usando un tool grafico e la sagoma finale viene rappresentata con una spline codificata mediante i suoi punti di controllo:
P = (p1, ..., pn), pi = (xi, yi)
Elastic Matching [2]
• Se la sovrapposizione tra i pixel dello sketch e quelli dei bordi dell'immagine candidata è elevata, la procedura termina qui
• Altrimenti, i vari pi vengono “perturbati” in modo da modificare lo sketch e re-iterare la comparazione
Misura di matching
• Più esattamente, la “bontà” del matching tra lo sketch P e l'immagine I è definita da:
M(P,I) = C(P,I) - D(P,I), dove:
• C() e D() sono delle funzioni, rispettivamente, del grado di sovrappozione e di deformazione dello sketch
• Il modo più semplice per ottenere C(P,I) è contando il numero di pixel dello sketch (definito da P) e dell’immagine che sono sovrapposti
Misura di matching [2]
D(P,I) = S(P,I) + B(P,I),
dove: S() e B() sono funzioni del grado di tensione e di curvatura dello sketch
immagine presa da: Del Bimbo, Pala, Visual Image Retrieval by Elastic Matching of User Sketches, IEEE PAMI 1997
Ricerca dei massimi della funzione di matching
Metodi iterativi
Metodo del gradiente ascendente
Elastic Matching: riassunto dell’algoritmo
• Per ogni immagine I del DB:– Proietto lo sketch fornito dall’utente su I
rappresentandolo tramite l’insieme P(0) dei punti di controllo di una spline
– Per ogni iterazione k: • Utilizzo il metodo del gradiente ascendente per calcolare
P(k+1) da P(k) • Mi fermo quando trovo un massimo locale M(P(h),I)
– Dal valore raggiunto M(P(h),I) decido se I contiene lo sketch oppure no
Elastic Matching: problemi aperti
• La convergenza dipende fortemente dalla soluzione iniziale P0: – non è invariante rispetto a roto-traslazioni e
cambiamenti di scala– segmentazione manuale di tutti i possibili oggetti
di interesse nelle immagini del DB (e.g., tramite il minimo rettangolo includente), oppure
– iterazioni successive del metodo per valori diversi di P0
Rettangolo Includente
immagine presa da: Del Bimbo, Pala, Visual Image Retrieval by Elastic Matching of User Sketches, IEEE PAMI 1997
Template matching deformabile: vantaggi e svantaggi
• No indexing
• Maggiore tolleranza ad occlusioni e sfondi non uniformi rispetto all’approccio statistico
• Problemi di segmentazione solo parzialmente risolti…
Considerazioni generali sui limiti dei sistemi content based (con
query by example)
• Tutta l’informazione che un sistema “content based” ha rispetto all’ “oggetto” cercato (e.g., una determinata forma visiva o segnale auditivo) deriva dalla query
Considerazioni generali sui limiti dei sistemi query by X [2]
• Per quanto sofisticato sia il sistema di rappresentazione o di matching è difficile distinguere le variazioni di forma “lecita” da quelle non lecite (rumore, altri oggetti…)
Considerazioni generali sui limiti dei sistemi query by X [3]
• Il cervello umano impara a distinguere la forma di un cavallo solo dopo averne visti diversi e in varie posizioni
• Prestazioni paragonabili per i sistemi artificiali sono probabilmente possibili solo mediante una fase di apprendimento automatico
Riferimenti
• Del Bimbo, Pala, Visual Image Retrieval by Elastic Matching of User Sketches, IEEE PAMI 1997
• 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)
• Smeulders et al., Content-Based Image Retrieval at the End of Early Years, IEEE PAMI 2000
Domande…