Shape-based visual information retrieval Enver Sangineto


Download 445 b.
Sana14.08.2018
Hajmi445 b.


Shape-based visual information retrieval

  • Enver Sangineto

  • Dipartimento di Informatica sangineto@di.uniroma1.it


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



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



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



Ir: esempio



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



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





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



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…




Download 445 b.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2020
ma'muriyatiga murojaat qiling