Shape-based visual
information retrieval
Enver Sangineto
Dipartimento di Informatica
[email protected]
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
-1
-2
-1
0
0
0
Maschera per
Gx
1
2
1
1
0
-1
2
0
-2
Maschera per
Gy
1
0
-1
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
-1 0 1
-2 0 2
-1 0 1
Maschera per
contorni verticali
r |Gx|+|Gy| = 28
F = arctg(-13/15)
IGx(p)
1 2 1
0 0 0
-1 -2 -1
Maschera per
contorni orizzontali
IGy(p)
-1 0 1
-2 0 2
-1 0 1
-2 0 2
-6 0 14 Gx=15
-2 0 9
1 2 1
0 0 0
-1 -2 -1
2 10 2
0 0 0 Gy=-13
-2 -16 -9
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 reiterare 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…