Capitolo 2

Estrazione delle caratteristiche geo-morfologiche e loro utilizzo.

 

 

Nel precedente capitolo abbiamo descritto l’algoritmo di segmentazione di un’immagine e l’estrazione del contorno con relativa approssimazione poligonale di una forma selezionata.

Una volta ottenuto il contorno approssimato possiamo procedere al recuprero delle caratteristiche geo-morfologiche. Questo processo ci permette di salvare nel database informazioni "confrontabili", in modo tale da poter decidere il grado di similitudine tra due forme.

Le caratteristiche geo-morfologiche possono essere raggruppate in tre tipi come descritto in figura 2.1.

 

 

2.1 Convessità

Prima di mostrare l’algoritmo usato per analizzare la convessità di un poligono diamo di seguito alcune definizioni.

Definizione 2.1.

Un poligono si dice Convesso se giace tutto da una stessa parte ottenuta prolungando ciascuno dei suoi lati, invece si dice Concavo se il prolungamento di qualcuno dei suoi lati lo divide in due o più parti (come mostrato in fig 2.2.(a) e 2.2.(b) ).

Rappresenteremo ogni oggetto in input come un insieme di punti {pi:pi=(xi,yi) con xi,yiÎ R}, e quindi il poligono P sarà descritto dalla sequenza dei vertici presi nell’ordine in cui compaiono sul perimetro di P.

Stabiliamo, inoltre, che la condizione necessaria affinché un poligono sia convesso è che esso sia un poligono semplice.

Un poligono è semplice se l’intersezione fra ogni coppia di lati del poligono è nulla. Esistono diverse euristiche per determinare la semplicità di un poligono, ma nel nostro caso di studio non è necessario applicarle in virtù del fatto che gli oggetti anomali analizzati forniscono sempre poligoni approssimati semplici.

Prodotti Incrociati.

Siano p1 e p2 due vettori, definiamo prodotto incrociato p1xp2 la superficie del parallelogramma formato dai punti (0,0), p1, p2 e p1+p2=(x1+x2,y1+y2).

Una definizione più formale ed utile, a livello algoritmico, è il determinante della matrice:

.

Se p1xp2 è positivo, allora p1 è disposto in senso orario rispetto a p2 relativamente alla origine (0,0); se il prodotto incrociato è negativo, allora p1 è in senso antiorario rispetto a p2. Le figure 2.3(a) e 2.3(b) mostrano le regioni orarie e antiorarie rispetto a un vettore p. Una condizione limite si verifica se il prodotto è zero; in questo caso i vettori sono collineari, orientati nella stessa o nell’opposta direzione. Per determinare se un segmento orientato p0 p1 è in senso orario rispetto a un segmento orientato p0 p2 relativamente al loro estremo in comune p0,si effettua semplicemente una traslazione in modo che p0 diventi l’origine. Cioè, se si denota con p1-p0 il vettore p¢ 1=( x¢ 1,y¢ 1), dove x¢ 1=x1-x0 e y¢ 1=y1-y0 e si definisce p2-p0 analogamente. Si può allora calcolare il prodotto incrociato

(p1-p0)x(p2-p0)=( x1-x0)( y2-y0)-( x2-x0)( y1-y0).

Se questo prodotto è positivo, allora p0 p1 è in senso orario rispetto a p0 p2,se è negativo esso è in senso antiorario.

Introduciamo, ora, un altro concetto fondamentale che ci permette di stabilire se due segmenti consecutivi p0p1 e p1p2 effettuano una svolta a sinistra o a destra nel punto

p1 ,cioè in quale senso gira l’angolo p0p1p2 .

Come mostrato nelle figure 2.4(a) e 2.4(b), basta controllare se il segmento orientato p0p2 è orario o antiorario rispetto al segmento p0p1 . . Per far ciò si calcola il prodotto incrociato (p2-p0)x(p1-p0). Se il prodotto incrociato è negativo, allora p0 p2 è antiorario rispetto a p0 p1, pertanto si effettua una svolta a sinistra di p1. Un prodotto incrociato positivo indica un orientamento orario e una svolta a sinistra di p1. Un prodotto incrociato uguale a 0 significa che i punti p0,p1 e p2 sono collineari.

Metodo dei prodotti incrociati.

Analizziamo adesso l’algoritmo da noi usato per valutare la convessità[21].

Consideriamo la sequenza di punti vertice di un poligono P presi in senso antiorario e sia p0 il punto iniziale di tale sequenza , allora :computato il prodotto incrociato fra i primi tre punti, partendo da p0, possiamo stabilire se la svolta che si effettua tra i primi due segmenti è a destra o a sinistra .Se la svolta è a sinistra (o a destra), affinché il poligono sia convesso risulta necessario che tutte le successive svolte siano effettuate a sinistra (o a destra), se c’è, invece, almeno una svolta a destra (0 a sinistra) allora il poligono è concavo.

· Considero i primi 3 vertici P0,P1,P2

· Computo il prodotto incrociato tra essi ( (p2-p0)x(p1-p0) ).

· Poiché la linea che congiunge p0 e p2 si trova alla sinistra di p1 ,allora la svolta è a sinistra.

· Ora, affinché il poligono sia convesso è necessario che tutte le svolte siano a sinistra .Di seguito, però, effettuando il prodotto incrociato tra i vertici p2,p3,p4 (vedi figura 2.5 (p4-p2)x(p3-p2)) e considerando la linea che collega i punti p2 e p4, posso notare che essa giace alla destra di p3 (vertice che determina la svolta) per cui la svolta è a destra. Possiamo infine affermare che il poligono è concavo.

Si è scelto di implementare quest’algoritmo per il minor tempo di computazione (O(n)) rispetto ad altri (O(n*log n)).

 

2.2 Calcolo dei momenti per i punti feature di una forma approssimata.

Una serie di attributi essenziali legati a forme 2D è collegata ai momenti[22-24], che possono rappresentare le caratteristiche globali più indicative di una forma, rappresentata da una sequenza di punti.

Diamo di seguito, alcune principali definizioni[22]:

Il momento di ordine (p, q) di una funzione continua 2D f(x, y) è definita come:

(1)

Similmente, il momento di ordine (p,q) di una forma digitale può essere definita come :

(2)

dove p(i, j) è l’array di occorrenze spaziali dei punti feature della forma approssimata.

Per comprendere meglio come vengono elaborati i momenti su di un poligono ci aiutiamo con la seguente figura 2D, S.

 

I punti corner della forma S sono (x1,y1),(x2,y2),…..,(xn,yn), girando intorno alla forma in senso antiorario. Un punto di essi è preso come punto iniziale.

Per mostrare come i momenti possono essere derivati da una lista di pixel corner, prima disegnamo linee per connettere i pixel corner all’origine, come illustrato in figura 2.6.

Come possiamo vedere, ogni due pixel corner vicini formano con l’origine una regione triangolare. Quindi, per una forma S con N punti corner, sono definiti esattamente N triangoli T1,T2,….,TN. Calcoliamo, ora, i momenti di tali triangoli.

Poiché, l’operazione di integrazione dell’eq. (1) è un’operazione lineare, i momenti dell’intera forma possono essere facilmente derivati come somma dei momenti dei triangoli.

Momenti di un triangolo

Sia T un triangolo che ha punti corner (a,b),(c,d) e (0,0). Si formano tre regioni quando disegniamo una linea per collegare (a,b) e (a,0) e un’altra per collegare (c,d) e (c,0). Sia a£ c.

La regione 1 è il triangolo con corner (0,0), (a,b) e (a,0).

La regione 2 è il trapezio con corner (a,0), (a,b), (c,d) e (c,0).

La regione 3 è il triangolo con corner (0,0), (c,d) e (c,0).

Il triangolo T è dato dall’unione della regione 1 e 2 e sottraendo la regione 3.

Quindi, il momento di ordine (p,q) di T può essere trovato sommando il momento di ordine (p,q) della regione 1 e quello di ordine (p,q) della regione 2 e sottraendo il momento di ordine (p,q) della regione 3 dalla somma .

Per la regione 1, i momenti sono:

; ; ;

(3)

; ; ;

Per la regione 2, i momenti sono:

;

;

;

I corrispondenti momenti per la regione 3 possono essere ottenuti dall’equazione (3) sostituendo a con c e b con d, poiché entrambe le regioni sono di tipo triangolo. Il momento di ordine (p, q) del triangolo T può essere trovato come:

Determinare la polarità dei triangoli.

Ora verrà associato ad ogni triangolo un valore di polarità che indicherà se il triangolo è dentro o fuori il contorno della forma. Questo perché, come vedremo dopo, i momenti della forma possono essere trovati sommando tutti i triangoli che cadono all’interno della forma e sottraendo dalla somma i momenti dei triangoli che si trovano all’esterno del contorno della forma.

Consideriamo un triangolo Ti definito dai punti corner (xi,yi), (xi+1,yi+1) e (0,0) con verso da (xi,yi) a (xi+1,yi+1) dato dalla direzione oraria stabilita per calcolare il segno "+1" al lato del segmento del contorno della forma.

 

 

 

Come illustrato in fig. 2.8, se l’angolo che forma l’asse x con la linea che è definita da (xi,yi) e (0,0) è maggiore o uguale all’angolo che forma l’asse x e la linea definita da

(xi+1,yi+1) e (0,0), allora il punto (0,0) è sul lato destro del segmento del contorno.

D’altra parte, se il primo angolo è minore del secondo angolo, il punto si trova sul lato sinistro del segmento del contorno.

Se i due angoli sono uguali, (0,0) giace sull’estensione del segmento. In questo caso, il valore del segno che noi associamo al triangolo non è importante, poiché la taglia (area) del triangolo è zero.

Esprimendo ciò sotto forma di formula, si ha:

Il modo con cui sono assegnati i segni ai triangoli è in accordo con il fatto che il contorno della forma è tracciato in senso orario.

Momenti della forma derivata dai momenti dei triangoli.

Il momento di ordine (p,q) della forma S è ora pronto da essere elaborato in accordo alla seguente equazione:

mpq,s = (4)

dove sign(i) è il segno associato con il triangolo Ti.

L’equazione (4) mostra che i momenti di S possono essere trovati aggiungendo e sottraendo i momenti dei triangoli con i loro valori di polarità.

Questo perché la forma S stessa può essere ricostruita aggiungendo e sottraendo triangoli.

Una dimostrazione formale dell’equazione è data dal seguente teorema:

Teorema 2.1: L’equazione (4) contiene i momenti esatti di una forma che è specificata da una lista di punti corner lungo il contorno della forma [22].

Inoltre, da tal equazione, si nota che la complessità del calcolo dell’area della forma è proporzionale al numero di punti corner del contorno in una data forma.

Caratteristiche geometriche della forma.

Ragionando in un dominio di applicazione discreto è possibile caratterizzare la forma di un oggetto usando i momenti misti.

Il momento di ordine (0,0) ci dà informazioni sulla taglia (area) della forma.

Centro di una forma :

Il centro di gravità o baricentro (cx,cy) di una forma S può essere trovato come:

Cx = ; Cy =

Momento Centrale :

Il momento centrale di ordine (p,q) di S è definito come:

In altre parole, i momenti centrali sono i momenti di una forma dove l’origine delle coordinate del sistema cartesiano sono state shiftate nel centro della forma. Può essere mostrato che m 00= m00 e m 01=m 10=0.Altri momenti centrali di ordine inferiore possono essere derivati dai momenti ordinari della forma.

m 11,s=

m 02,s=

m 20,s=

Orientazione della forma :

L’orientazione q s della forma S può essere calcolata dai momenti centrali sopra citati:

q s=

L’angolo q s definisce l’asse che passa attraverso il centro di S, quest’asse è chiamato asse maggiore della forma.

Momenti Massimi e minimi di inerzia :

L’inerzia minima Imin della forma S può essere calcolata come segue :

Imin =

La massima inerzia Imax è archiviata quando la forma ruota sull’asse minore, che è la

linea passante attraverso il centro di gravità della forma e perpendicolare all’asse maggiore :

Imax=

Spreadness ed elongazione :

Lo spreadness della forma ci dice quanto è compatta la forma

Spreadness =

ed il valore dell’elongazione riflette quanto la forma è elongata :

elongation =

La complessità di tale metodo è linearmente proporzionale al numero di punti corner del contorno della forma. Utilizzando l’algoritmo di approssimazione di Papakostantinou[19], che ci assicura il numero minimo di punti corner, il calcolo dei momenti verrà effettuato con complessità, in tempo, minima.

 

2.3 Misure di Simmetria.

La Simmetria è un’altra caratteristica importante nell’ambito del riconoscimento di forme. Esistono vari modi per determinare la simmetria di una forma, molti di questi agiscono, fondamentalmente, su domini di applicazione continui. Nel caso di domini discreti (come quello del nostro caso di studio) bisogna fare i conti con gli errori causati dal rumore presente nelle immagini digitali, perciò il campo si restringe a due metodologie concernenti il calcolo dei momenti invarianti o dei coefficienti di Fourier (D.F.T.). Quando, però, si tratta con forme costituite da un numero elevato di punti, il tempo di computazione dei coefficienti della D.F.T. risulta molto alto, e quindi da scartare a priori.

Intuitivamente, un metodo per stabilire una misura di simmetria è legato al concetto di Simmetria rotazionale di una forma S[25].

Data la sequenza di punti del contorno della forma S, si costruisce una sequenza di forme ruotate S3,S4,S5,… ruotando la forma degli angoli 3600/3, 3600/4, 3600/5 e si controlla se esiste una forma ruotata Sk coincidente con la forma di input S, in tal caso l’ordine di simmetria sarà k. Quest’approccio, che sembra facilmente implementabile, conduce ad una determinazione dell’ordine di simmetria non sempre univoco, in quanto possono esserci più forme ruotate che coincidono con S .

Per evitare tale problema si pone un limite sull’ordine di simmetria rotazionale Ns.

Tale algoritmo utilizza i tre momenti misti del secondo ordine M11 ,M02 , M20 per il calcolo della simmetria rotazionale come segue:

  1. Se M11=0 e M20-M02=0 allora si decide che la forma è asimmetrica;
  2. Altrimenti la forma S potrebbe essere rotazionalmente simmetrica;

La contraddizione di fondo in tale metodo è relativa al fatto che esso fornisce solo un ordine di simmetria rotazionale, quindi nel caso in cui la figura in esame è asimmetrica non viene restituito nessun valore ed il confronto con le altre forme presenti nel database non può essere effettuato.

Altre misure di simmetria coinvolgono i valori di media, mediana e scarto quadratico medio, propri della teoria della probabilità[26]. In particolare, si può introdurre un indice di asimmetria che stabilisce il grado di scostamento di una popolazione X dalla simmetria.

In tal senso, si è pensato di rappresentare il poligono approssimante attraverso la curva delle distanze dei punti features dal baricentro. Se tale curva ha una "coda" più lunga a destra rispetto al massimo centrale allora, la distribuzione è dotata di asimmetria positiva. Se si verifica il caso inverso, allora la distribuzione è asimmetricamente negativa .

 

Per curve simmetriche moda, mediana e media coincidono. Da tali considerazioni, si possono ricavare due misure di asimmetria, dette primo e secondo coefficiente di Pearson :

Asimmetria = =

Con s che indica lo scarto quadratico medio della distribuzione delle distanze euclidee.

Dalla figura 2.10 si può concludere che la misura fornita rispecchia la situazione reale in maniera abbastanza adeguata, infatti la forma quadrata e quella rettangolare sono senz’altro più simmetriche rispetto al poligono C. Tali coefficienti non potranno mai essere nulli nel caso di forme "perfettamente" simmetriche, in quanto il dominio di applicazione in cui ci muoviamo risulta essere discreto.

In base a considerazioni effettuate sulle dimensioni delle forme che possono essere estratte dalle immagini nel database, si è potuto costatare che qualsiasi sia la misura scelta per la rappresentazione dell’oggetto anomalo, essa deve mantenere il suo significato in qualunque caso; in particolare, ogni caratteristica, per un opportuno funzionamento della fase di recupero, deve essere invariante rispetto lo scaling.

 

2.4 Caratteristica di tessitura: la Densità.

La tessitura è legata strettamente alla distribuzione spaziale dell’intensità di un’immagine e della variazione dei toni discreti. In particolare, per piccole aree dell’immagine la tessitura è caratterizzata dalla variazione dei toni di grigio. La tessitura può essere descritta attraverso le misure d’uniformità, densità, intensità e direzionalità.

Metodi efficaci, per estrapolare caratteristiche di tessitura, includono i concetti di matrice di dipendenza dei livelli di grigio, che misura la dipendenza fra i livelli di grigio di coppie di punti secondo una determinata relazione spaziale, oppure dei descrittori di Fourier che analizzano lo spettro dell’immagine attraverso lo studio della stessa nel campo immaginario.

La strada da noi perseguita, si basa su misure statistiche della tessitura che includono l’utilizzo dei momenti relativi ai livelli di grigio presenti nella regione dell’immagine da analizzare (tipicamente, la varianza, la skewness e kurtosis).

Tale scelta, oltre ad essere una continuazione logica del discorso relativo alle caratteristiche relative alla shape, è la meno difficile da implementare e in ogni modo fornisce risultati paragonabili a quelli ottenuti con i descrittori di Fourier.

 

2.5 Tecniche di recupero per caratteristiche geo-morfologiche.

L’insieme di caratteristiche geometriche e morfologiche utilizzate per questa seconda fase della strategia di ricerca comprende: densità, uniformità, orientazione, simmetria rispetto al centroide, convessità, spreadness e area.

Tale insieme è stato scelto sulla base del lavoro di sperimentazione condotto nei precedenti lavori[27,28]; in tali lavori è, infatti, possibile trovare una trattazione dettagliata ed esaustiva delle problematiche relative alla scelta di tali caratteristiche, del loro significato semantico e dei metodi più efficienti per calcolarle. La scelta di un particolare set di features non deve, tuttavia, ritenersi vincolante in quanto la strategia di ricerca da noi proposta, così come la struttura del database da noi creato, sono flessibili e facilmente adattabili all’eventuale introduzione di nuove caratteristiche in aggiunta o in sostituzione di quelle già esistenti o di metodi più efficienti per calcolarle.

Il concetto di similitudine tra le immagini è espresso in termini della distanza euclidea, nello spazio delle caratteristiche, tra i punti che le rappresentano; in particolare, la similitudine tra due immagini è inversamente proporzionale alla loro distanza.

Più precisamente, data un’immagine query Q caratterizzata dal vettore di feature

(dq, uq, oq, cq, Sq, Spq, Aq)

 

il valore della distanza euclidea pesata e normalizzata:

(5)

 

 

dove:

(dim, uim, oim, cim, Sim, Spim, Aim)

è il vettore di caratteristiche geometrico-morfologiche associato all’immagine im, e Ri, per i Î {d, u, o, c, S, Sp, A}

è il range in cui possono variare i valori della caratteristica i.

Il valore ottenuto dal calcolo della distanza tra la query ed un immagine rappresenta un grado di similitudine associato ad essa. Basandosi su tale valore sarà facile fornire all’utente un ordinamento delle immagini dalla più simile alla meno simile rispetto alla query e sarà a lui lasciata la scelta di quante e quali vedere.

I passi seguiti da noi per la ricerca sono:

  1. Normalizzazzione dei valori delle caratteristiche.
  2. Per ogni caratteristica viene calcolato il valore normalizzato, cioè il rapporto tra il valore reale ed il valore massimo che essa può assumere. Il valore normalizzato sara quindi contenuto nell’intervallo [0,1].

    2. Impostazione del range di soddisfacibilità.

    A partire dalle caratteristiche geometrico-morfologiche della query, viene chiesto all’utente di specificare per ciascuna caratteristica di quanto vuole allontanarsi nella ricerca rispetto all’exact match, cioè di definire per ciascuna di esse un intervallo di ricerca intorno all’exact match. Per ogni caratteristica l’utente può fissare gli estremi inferiore e superiore dell’intervallo di ricerca compresi tra i valori minimi e quello massimi normalizzati che la caratteristica può assumere; cioè l’utente definisce i due valori in un range da 0 a 1.

    Così facendo, si possono tirare fuori dal set di risposta di base le immagini che non soddisfano tutti i criteri stabiliti restringendo il campo di applicazione della distanza euclidea al sottoinsieme di immagini per le quali il valore di ogni caratteristica cade nel range prescelto.

    Le impostazioni di default sono rappresentate da uno scarto di 0.2 sia per l’estremo inferiore che per quello superiore. Questi valori possono essere cambiati per ognuna delle caratteristiche dall’utente.

    E’ chiaro che se per una caratteristica i valori dei limiti inferiori e superiori sono rispettivamente 0 e 1, per quella caratteristica non verrà eseguito aclun filtro.

  3. Calcolo della distanza euclidea.

Una volta che i valori delle caratteristiche geo-morfologiche di un’immagine rientrano nel range di soddisfacibilità viene calcolata la distanza euclidea pesata come in formula (5).

Da notare che i pesi relativi alle singole caratteristiche sono stati consigliati dagli esperti del settore stesso. La caratteristica più importante, cioè quella che ha peso maggiore, è la densità, in quanto è l’unica a dare informazioni sulla profondità della malformazione. Seguono come importanza le caratteristiche legate alla forma dell’oggetto ed infine l’area, intesa come grandezza dell’anomalia.

Home