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. e 3. rientrano nei metodi tradizionali; 2. e 4. fanno parte del “content-based image retrieval”.
La strategia di memorizzazione di attributi strutturati è fondata sulla memorizzazione di informazioni per ognuna delle immagini del D.B.M.S.:
L’indicizzazione e la ricerca possono quindi essere effettuate con tecniche standard dei DBMS.
I limiti più evidenti di questa metodologia sono:
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:
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:
Vantaggi: si possono “catturare” anche concetti di alto livello (cioè astratti) presenti nell’immagine (per es. una persona che sorride o che è triste).
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:
Molti sistemi reali sono basati su tali metodi.
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.
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:
in cui ai e bi sono il numero pixel delle immagini A e B che ricadono nel bin i-esimo.
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”.
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:
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:
in cui:
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à.
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:
in cui
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.
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.
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à:
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.
Per la descrizione numerica delle forme sono state adottate molteplici strategie tra cui:
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.
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:
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.
Query2 = Riga3rev, Riga2rev, Riga1rev. Mod. da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.
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:
La coppia (Stringa_binaria; Eccentricità) determina univocamente la forma.
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.
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).
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:
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).
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
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.
La compressione di immagine sfrutta già caratteriste “intime” dell’immagine stessa. Proprio questi parametri di “sintesi” possono essere sfruttati per indicizzare l’immagine
Esempio:
Memorizzazione basata su un modello descrittivo dell’immagine.
Esempio:
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”.
1. Introduzione
2. Tipologia e formati dei dati MultiMediali. Il testo
3. Tipologia e formati dei dati MultiMediali. L'audio
4. Tipologia e formati dei dati MultiMediali. Grafica e video
5. Progetto di DB Multimediali
6. Indicizzazione e recupero dei documenti di testo
7. Indicizzazione e recupero dell'audio
8. Metodi di classificazione dell'audio
9. Colori
10. Indicizzazione e recupero delle immagini
11. Esempi reali di image retrieval
12. Video
13. Strutture dati efficienti per la ricerca della similarità - pa...
14. Strutture dati efficienti per la ricerca della similarità - pa...
15. Sistemi di supporto e misure di efficacia
17. Geographical Information System - parte prima
18. Geographical Information System -parte seconda
19. Geographical Information System - parte terza