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
Fasi tipiche di un sistema di
CBIR tramite forma
• Estrazione dei punti dell’oggetto/i che
rappresentano:
– I punti interni della sagoma oppure:
– I bordi (interni e/o esterni)
• Rappresentazione dei punti estratti
• Matching tra la rappresentazione della
query e quelle del DB
Binarizzazione dell’immagine per
estrarre la sagoma degli oggetti
Distribuzione bimodale dei livelli
di grigio
Possibili approcci:

Soglia costante

Soglia dinamica
Binarizzazione a soglia
costante
• È la soluzione più semplice
 y(x) = 0 se x < S
 y(x) = 255 altrimenti
 il problema è la scelta della soglia (threshold) S
Esempio
Esempio Vela
Soglia = 140
Esempio Orso
Estrazione di contorni tramite
operatori differenziali
• Ricerca di discontinuità (un
cambiamento brusco dell’intensità di
grigio dei pixel)
• Il problema può essere affrontato
tramite l'analisi della derivata
• I punti di bordo sono:
– i massimi (minimi) della derivata prima o
– lo zero della derivata seconda
Operatori differenziali
• f(x) è l'intensità dell'immagine
Gradiente
• Un’immagine I può essere vista come
una funzione a due variabili I(x,y)
• In tal caso la derivata è un vettore
(gradiente), composto da:
– Intensità (G)
– 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
Convoluzione tramite maschera
• La convoluzione nel
discreto avviene su un
supporto limitato nello
spazio (template)
• Può essere
considerata una
finestra che si muove
sull'immagine
Operatori differenziali
• Gli operatori differenziali nel discreto
sono realizzati tramite maschere a
somma nulla:
– l'applicazione a una regione uniforme deve
dare risultato zero
Operatore di Sobel
-1
-2
-1
0
0
0
1
2
1
Maschera per
contorni verticali
1
0
-1
2
0
-2
1
0
-1
Maschera per
contorni orizzontali
Operatore di Sobel
-1 0 1
-2 0 2
-1 0 1
1 2 1
0 0 0
-1 -2 -1
Il colore indica il modulo del risultato
Operatore di Sobel
-1 0 1
-2 0 2
-1 0 1
Maschera per
contorni verticali
G |Gx|+|Gy| = 28
F = arctg(-13/15)
Vengono create due
nuove immagini
1 2 1
0 0 0
-1 -2 -1
Maschera per
contorni orizzontali
-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
Esempi
Punti di “edge”
• Binarizzando opportunamente
l’immagine gradiente di I è possibile
estrarre i punti con gradiente più elevato
in modulo, ovvero i punti di bordo (edge
points)
Esempio
Similitudine tra forme diverse:
problemi
• Cercare una corrispondenza (matching)
tra la forma della query e quella degli
oggetti del DB è difficile per almeno 2
motivi:
– Elevata variabilità della forma degli oggetti
– Problema della segmentazione
Elementi di variabilità della forma
• Punti di vista differenti,
• Forme diverse all’interno della stessa
classe,
• Oggetti deformabili,
• …
Esempio
Segmentazione
• Normalmente l’oggetto (gli oggetti)
cercato/i occupano una parte minoritaria
dell’immagine
• Selezionare tale parte può essere molto
difficile (soluzioni naive sono
esponenziali)
Esempio
Principali approcci di
rappresentazione e matching
• 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
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 sono poco discriminanti)
• Gli oggetti devono essere
completamente isolabili (segmentazione
perfetta)
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 e
l'immagine è definita da:
M(P) = C(P) - D(P), 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) è contando il numero di
pixel dello sketch (definito da P) e dell’immagine che sono
sovrapposti
Misura di matching [2]
D(P) = S(P) + B(P),
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))
– Dal valore raggiunto M(P(h)) 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
• 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 content based [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 content based [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…