Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Walter Balzano » 10.Indicizzazione e recupero delle immagini


Indicizzazione e recupero delle immagini

  • Introduzione
  • Differenti approcci di Indicizzazione e Recupero
  • Tecniche Text-Based
  • Tecniche Color-Based
  • Miglioramenti delle tecniche di base
  • Retrieving basato sulla forma

Indicizzazione e recupero delle immagini (segue)

L’indicizzazione ed il recupero delle immagini costituisce un settore di ricerca in cui si sono raggiunti risultati molto importanti e avanzati.

I risultati ottenuti in questa di ricerca sono spesso sfruttati nei database relazionali di tipo commerciale.

Nell’indicizzazione e ricerca si distinguono 4 approcci diversi basati su:

  1. memorizzazione di attributi strutturati;
  2. riconoscimento degli oggetti;
  3. annotazioni libere;
  4. estrazione di Feature di basso livello.

1. e 3. rientrano nei metodi tradizionali; 2. e 4. fanno parte del “content-based image retrieval”.

Approcci utilizzati per l’indicizzazione.

Approcci utilizzati per l'indicizzazione.


Memorizzazione di attributi strutturati

La strategia di memorizzazione di attributi strutturati è fondata sulla memorizzazione di informazioni per ognuna delle immagini del D.B.M.S.:

  • nome del file;
  • data di creazione;
  • autore;
  • categoria dell’immagine;
  • soggetto;
  • ……

L’indicizzazione e la ricerca possono quindi essere effettuate con tecniche standard dei DBMS.

I limiti più evidenti di questa metodologia sono:

  • gli attributi possono non descrivere in maniera completa le immagini;
  • le query sono limitate ai soli attributi memorizzati.

Riconoscimento di oggetti

La strategia di riconoscimento degli oggetti è fondata su tecniche sofisticate di estrazione di feature e di algoritmi di riconoscimento degli oggetti presenti nella scena.

Caratteristiche principali:

  • sono computazionalmente molto pesanti;
  • richiedono algoritmi estremamente sofisticati;
  • godono di una buona prestazione solo per domini applicativi ristretti;
  • sono argomento di ricerca avanzata (Computer Vision).
Esempio di segmentazione.

Esempio di segmentazione.

Esempio di segmentazione.

Esempio di segmentazione.


Annotazioni libere (Text-based image retrieval)

Le immagini “annotate” sono descritte con testo libero (non controllato).

Le query sono nella forma di “parole chiave” o testo libero (con eventuale utilizzo di operatori booleani).

La ricerca usa gli algoritmi convenzionali di IR (Information retrieval) basati sulla ricerca di similarità tra query e testo descrittivo delle immagini.

Essendo una tecnica “manuale”, occorre notare che:

  • il testo deve essere il più possibile completo e consistente;
  • è necessario l’utilizzo di un dizionario per ricercare anche su sinonimi (uomo/donna/bambino = persona);
  • il testo introdotto potrebbe essere soggettivo; occorre utilizzare tecniche di relevance feedback.

Vantaggi: si possono “catturare” anche concetti di alto livello (cioè astratti) presenti nell’immagine (per es. una persona che sorride o che è triste).

Caratteristiche di basso livello

L’ estrazione di feature di basso livello è definita su tecniche di indicizzazione e ricerca basate sul contenuto (content-based).

Possono prendere in considerazione una o più delle seguenti caratteristiche:

  • colore;
  • forma;
  • texture;

Molti sistemi reali sono basati su tali metodi.

Colore, forma e texture di una immagine.

Colore, forma e texture di una immagine.


Algoritmi basati sull’analisi del colore

Ogni immagine è memorizzata assegnando ai pixel tre valori numerici ad ognuno dei canali di colore (ad esempio RGB).
Ogni canale è discretizzato in m intervalli (quantizzazione dei colori): il numero totale di combinazioni diverse (bins) è m3
(es: 16 intervalli di colore → 4096 bins).

Si definisce istogramma di colore: il vettore H(M) = (h1, h2, …, hj, …hn) in cui hj rappresenta il numero di pixel dell’immagine M che ricadono nel bin j.

Istogramma di colore.

Istogramma di colore.


Confronto degli istogrammi di immagini

Confronto istogrammi di immagine equalizzato in modi differenti.

Confronto istogrammi di immagine equalizzato in modi differenti.


Confronto degli istogrammi di immagini (segue)

Confronto istogrammi di immagine con diversa “palette”.

Confronto istogrammi di immagine con diversa “palette”.


Indicizzazione su istogramma di colore

Per ogni immagine si calcola l’istogramma di colore H(M) che verrà poi utilizzato come indice dell’immagine M.
Per la ricerca delle immagini nel DB serve definire una misura di distanza tra l’istogramma dell’immagine query e quelli delle immagini contenute nel database.

Date 2 immagini A e B, la misura di distanza più semplice è data da:

d (A,B) = \Sigma _{i=1}^n \arrowvert a_i - b_i \arrowvert

in cui ai e bi sono il numero pixel delle immagini A e B che ricadono nel bin i-esimo.

Esempi di calcolo della distanza

Esempio

Si supponga di avere 3 immagini 8×8 pixels aventi i seguenti istogrammi:
H1 = (8, 8, 8, 8, 8, 8, 8, 8 )
H2 = (7, 7, 7, 7, 9, 9, 9, 9)
H3 = (2, 2, 10, 10, 10, 10, 10, 10)

Quindi, le distanze tra le immagini sono rispettivamente:
d(H1, H2) = 1+1+1+1+1+1+1+1=8
d(H1, H3) = 6+6+2+2+2+2+2+2=24
d(H2, H3)= 5+5+3+3+3+1+1+1+1=23

Pertanto le immagini 1 e 2 sono più simili che 1 e 3 oppure 2 e 3.

Tale metodo di base è soggetto ad una serie di problemi e può fornire risultati fortemente incorretti se non si applicano delle varianti necessarie per trattare in maniera migliore l’informazione sul “colore”.

Istogramma del colore: problematiche

La discretizzazione dello spazio dei colori in classi (bins) non tiene conto della similarità dei colori: due bins adiacenti vengono considerati totalmente diversi; il posizionamento della linea di demarcazione tra i bins influisce fortemente sull’istogramma e sul calcolo della distanza.

La rappresentazione dei colori non e’ univoca; ma c’è dipendenza dal sistema di rappresentazione e dipendenza dal device.

Esempio:
Si supponga di avere due bin che rappresentano gli insiemi di colori 1-10 e 11-20 (in cui i colori con numeri vicini sono simili tra di loro). Quindi il colore 10 viene assegnato al bin 1, ed i colori 11 e 20 vengono assegnati al bin 2. Per paradosso il colore 11 viene considerato uguale al 20 ma diverso dal 10.

Metodi per superare tale problema:

  • distanza tra i bins;
  • istogramma cumulativo;
  • istogramma pesato percettivamente.
Errore di similitudine.

Errore di similitudine.

Errore di similitudine: esempi.

Errore di similitudine: esempi.


Distanza tra i bins

La distanza tra bins si definisce come misura di similarità (inverso della distanza) calcolata bin-per-bin. E’ quindi possibile definire l’istogramma Z di similarità tra due istogrammi X ed Y nel seguente modo:

\Arrowvert Z \Arrowvert = Z ^T AZ

in cui:

  • A è la matrice simmetrica di similarità dei colori in cui a(i,j) = a(j,i) = 1- d(ci,cj)/dmax;
  • d(ci,cj) è la distanza tra i colori in uno spazio di uniforme;
  • dmax è la distanza massima tra due colori.

Se due colori sono molto diversi d(ci,cj)  e’ prossima a dmax e a(i, j) è vicino allo 0 contribuendo al calcolo della similarità.

Istogramma cumulativo

L’istogramma cumulativo non considera la distanza tra i bin ma risolve parzialmente il problema creando delle classi cumulative.
Un istogramma cumulativo (Cumulative Histogram) per un’immagine M e’ definito da:

CH(M) = (ch_1, ch_2,...,ch_n)<br />

in cui

ch_i=\Sigma {_{j {\leq}i}}~~h_j

Per il calcolo della distanza si usa la normale distanza euclidea.
Prestazione: buona per valori b assi di i. Per valori alti non riflette la similarità tra i colori.

Istogramma.

Istogramma.

Istogramma cumulativo.

Istogramma cumulativo.


Limiti dell’approccio Color-Based

Relazioni spaziali: una limitazione dei sistemi di indicizzazione di immagini basate sui colori consiste nel fatto che generalmente vengono ignorate le relazioni spaziali tra i pixel (due immagini molto diverse potrebbero essere considerate uguali): per risolvere il problema si possono utilizzare tecniche che prevedono la suddivisione delle immagini in regioni più piccole e applicare la tecnica basandosi sugli istogrammi delle sotto-regioni corrispondenti delle immagini.

Mascheramento ad opera dello sfondo: gli istogrammi sono fortemente condizionati dalla presenza di grandi blocchi di colore omogeneo (per es. il background) che “mascherano” l’oggetto in primo piano. Soluzione: tecniche di segmentazione (automatiche o semiautomatiche) per suddividere le immagini in soggetto e sfondo.

Relazioni spaziani: analisi per sotto-regioni.

Relazioni spaziani: analisi per sotto-regioni.

Mascheramento del background.

Mascheramento del background.


Indicizzazione e ricerca basate sulla forma

L’indicizzazione basata su forma si basa su algoritmi di segmentazione delle immagini che sono in grado di suddividere una immagine in singoli oggetti attraverso metodi automatici o semiautomatici; i sistemi in tale ambito devono possedere le seguenti proprietà:

  • ogni forma deve avere una rappresentazione unica, invariante rispetto a traslazione, rotazione o scala;
  • forme simili devono avere una rappresentazione similare in modo tale che la ricerca possa essere basata sulla distanza tra la rappresentazione delle forme;
  • il processo di ricerca è spesso realizzato in modalità “query by example” e il sistema ritorna come risposta la forma che meglio approssima quella disegnata dall’utente.
Query by example: query grafica.

Query by example: query grafica.

Query by example: indipendenza dalle trasformazioni.

Query by example: indipendenza dalle trasformazioni.


Definizioni

Asse maggiore: segmento che congiunge i due punti della forma che sono più distanti fra di loro.
Asse minore: segmento perpendicolare all’asse maggiore e tale che il rettangolo il cui lati sono paralleli ai due assi racchiuda completamente l’intera forma.
Rettangolo di base: il rettangolo descritto nella precedente (esso coincide con il più piccolo rettangolo che contiene l’intera figura).
Eccentricità‘: rapporto tra la lunghezza dell’asse maggiore e la lunghezza dell’asse minore.

Le caratteristiche elencate possono essere considerate basilari in quanto forniscono una prima caratterizzazione delle forme e sono utilizzate per l’indicizzazione e la ricerca.

Immagine a bassa eccentricità.

Immagine a bassa eccentricità.

Immagine ad alta eccentricità.

Immagine ad alta eccentricità.


Descrizioni numeriche delle forme

Per la descrizione numerica delle forme sono state adottate molteplici strategie tra cui:

  • Metodi basati su formulazioni matematiche che descrivono un’immagine come funzione f(x,y) dove x e y sono le coordinate di un pixel:
    • momenti invarianti;
    • momenti centrali normalizzati.
  • Metodi che cercano di descrivere le forme mediante le coordinate dei punti che le definiscono:
    • metodo dei descrittori di Fourier;
    • istogramma dei lati significativi;
    • lista ordinata dei punti interessanti;
    • elastic template matching.

Una limitazione “classica” delle precedenti metodologie è dovuta al fatto che trattano con difficoltà l’invarianza rispetto alle traslazioni, rotazioni e cambiamenti di scala necessari per ottenere un buon sistema di indicizzazione e ricerca basato sulle forme.

Rappresentazione delle forme basata su regioni

La rappresentazione delle forme basata su regioni è una metodica semplice i cui risultati sono molto promettenti.

Data una forma F, la metodologia adottata è così descritta:

  • si sovrappone una griglia G che contenga completamente F;
  • per ogni cella Ci di G, se Ci ∩ G = Ø allora Ci = 0 altrimenti Ci = 1;
  • si ottiene una stringa binaria che rappresenta la forma leggendo gli 1 o 0 da sinistra a destra e dall’alto al basso.
Rappresentazione di una forma.
Fonte: “modificata da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”

Rappresentazione di una forma. Fonte: “modificata da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”


Normalizzazione rispetto alle rotazioni

Per ottenere l’invarianza rispetto alla rotazione, la forma viene ruotata in modo tale che il suo asse maggiore sia allineato con l’asse x (orizzontale). Il suddetto allineamento è ugualmente possibile ruotando tutto di 180° ed andrebbero quindi esaminati 2 casi.

Per evitare di raddoppiare le rappresentazioni di stringhe binarie, generalmente si preferisce, invece, di “raddoppiare” la query e cioè, in altre parole, si effettua una trasformazione sulla query stessa che viene riproposta quindi per la seconda volta.

Query1 = Riga1, Riga2, Riga3. Modificata da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.

Query1 = Riga1, Riga2, Riga3. Modificata da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.

Query2 = Riga3rev, Riga2rev, Riga1rev. Mod. da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.

Query2 = Riga3rev, Riga2rev, Riga1rev. Mod. da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.


Normalizzazione rispetto ai cambiamenti di scala

E’ possibile effettuare una normalizzazione di scala ridimensionando tutte le forme presenti nel DataBase in modo tale che abbiano tutte lo stesso asse maggiore (di numero di pixel). In altre parole, fissata la larghezza x di una forma è possibile che possa variare solo la sua altezza y (finché non se ne conosce anche l’eccentricità).

Il criterio di univocità di rappresentazione di una forma è pienamente determinato se:

  • viene fissata la CellSize (per es. 10×10 pixel);
  • si presume che l’asse maggiore sia univoco;
  • si effettuano le operazioni di normalizzazione di rotazione;
  • si effettuano le operazioni di normalizzazione di scala;
  • per ogni forma si conosce la sua eccentricità;

La coppia (Stringa_binaria; Eccentricità) determina univocamente la forma.

Calcolo della similarità

Il calcolo della similarità viene generalmente compiuto in 2 fasi.

Fase 1: Eccentricità molto diverse
Se due forme hanno eccentricità molto diversa tra di loro, allora non c’e alcun bisogno di calcolare la similarità in quanto possiamo assumere che, di conseguenza, le figure siano molto diverse.

Fase 2: Eccentricità uguale o simile
Se due forme hanno uguale eccentricità (e quindi la loro stringa binaria ha uguale lunghezza), la distanza tra di loro si calcola come numero di posizioni delle stringhe che hanno valore diverso

Esempio:
tra 1111111111100000 e

……1111111111111100 la distanza è 3

Se due forme hanno eccentricità diversa di poco, si possono aggiungere zeri alla stringa che descrive la forma più “bassa” e quindi applicare la distanza come sopra.

Immagini con diversa eccentricità.

Immagini con diversa eccentricità.


Forme speculari

Un tipo di normalizzazione “estesa” considera anche l’ulteriori trasformazioni che potrebbero riguardare una figura: una buona strategia di riconoscimento dovrebbe essere resistente anche rispetto alle trasformazioni di specularità orizzontale e verticale.

Anche in questo caso si preferisce non appesantire il database memorizzando 2 sequenze come indice della forma ma, piuttosto, è preferibile effettuare un maggior numero di ricerche applicando tali trasformazioni alla forma da ricercare (considerando anche la rotazione di 180°, ogni ricerca dovrà essere realizzata con 4 stringhe diverse).

Specularità verticale.
Fonte: “modificata da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”

Specularità verticale. Fonte: “modificata da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”


Riepilogo

Un sistema di indicizzazione e ricerca di forme basato su Regioni può essere realizzato in modo che sia invariante a rotazioni, traslazioni, scalatura e trasformazioni speculari, nel seguente modo:

  • si determinano gli assi maggiore e minore e l’eccentricità della forma;
  • si ruota la forma in modo che l’asse maggiore coincida con l’asse X;
  • si scala la forma in modo che l’asse maggiore abbia una lunghezza prefissata;
  • si sovrappone una griglia regolare alla forma;
  • si assegnano 1 e 0 alle celle e si calcola la stringa binaria scorrendo le celle del grigliato da sx a dx e dall’alto in basso.

L’indice della forma è costituito dalla stringa binaria e dal numero di celle che la forma occupa in direzione Y (le due informazioni sono memorizzate nel database come rappresentazione della forma stessa).

Durante la ricerca la forma da trovare è elaborata in modo analogo ottenendo 4 stringhe diverse (rotazione di 180° e 2 mirroring) e per ogni forma presente nel database che ha una eccentricità simile si calcola la distanza (si considera la distanza minima tra le quattro rappresentazioni della forma).

Metodi basati sulle texture

Texture Analysis: la Texture (detta anche tessellatura) descrive una “percezione” dell’immagine che è difficilmente descrivibile e riguarda aree caratterizzate da comuni caratteristiche di intensità e struttura

  • granularità (fine o grossa);
  • contrasto;
  • direzionalità (direzine dominante della texture);
  • regolarità;
  • ecc…

Ci sono esempi di sistemi reali che utilizzano una misurazione matematica (più o meno sofisticata) di tali concetti e la utilizzano per indicizzare e ricercare immagini.

Esempi di Textures.

Esempi di Textures.


Altre metodologie

La compressione di immagine sfrutta già caratteriste “intime” dell’immagine stessa. Proprio questi parametri di “sintesi” possono essere sfruttati per indicizzare l’immagine

Esempio:

  • i coefficienti DCT nella compressione JPEG;
  • i coefficienti Wavelet nella compressione Wavelet.

Memorizzazione basata su un modello descrittivo dell’immagine.

Esempio:

  • utilizzo delle tecniche di compressione FRATTALE.

Memorizzazione delle relazioni tra gli oggetti che sono presenti in una immagine. E’ simile all’utilizzo della informazione topologica nei GIS: tale relazione consente di inviare al sistema richieste quali:

“trova tutte le immagini contenenti un lago vicino ad una montagna”
oppure
“trova le immagini contenenti una autostrada sulla sinistra di una foresta”.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion