Capitolo 1

Segmentazione di un’immagine ed

estrazione del contorno.

Il processo visivo che individua un oggetto all’interno di un’immagine, a livello percettivo, può avvenire in modo del tutto soggettivo. Esso può realizzarsi sia partendo da un punto particolare estendendosi fino all’individuazione del suo contorno, sia partendo dall’immagine completa con successive suddivisioni della stessa fino al raggiungimento di paricolari zone che, messe insieme, restituiscono l’oggetto fissato.

Simulando questo processo umano si sono sviluppati vari metodi per la segmentazione dell’immagine[5-15]. In generale non esiste nessuna tecnica migliore in assoluto delle altre, molto dipende anche dal tipo d’immagine che dobbiamo analizzare. Il più delle volte, la maggioranza dei ricercatori è portata a basarsi sull’elaborazione di diverse centinaia d’immagini e sul tempo di computazione che viene impiegato dalla varietà di algoritmi usati. Da ciò si possono ricavare delle osservazioni qualitative sui vantaggi e svantaggi di un metodo rispetto all’altro.

Il nostro particolare campo d’azione è formato da immagini di tipo medico e la tecnica che abbiamo adottato è un algoritmo di segmentazione, descritto in [14], che, partendo dall’immagine completa definisce per essa stessa e per ogni sua regione una funzione di valutazione basata sulla distribuzione delle varie tonalità di grigio.

Il processo di segmentazione, come già detto, è essenziale perché permette di individuare le varie regioni costituenti l’immagine TAC in esame. In tal modo, è possibile isolare l’oggetto attraverso l’operazione d’estrazione del contorno. Ciò avviene tramite un agoritmo di ricerca detto per 8-connesso[16], dove partendo da un punto qualsiasi dell’oggetto residente sul confine si scandiscono tutti i punti che definiscono il suo contorno. Il passo successivo consiste nell’approsimazione poligonale della forma[17-19], cioè una diminuzione del numero di punti del contorno che facilita il calcolo delle carattersitiche geo-morfologiche della forma in esame.

 

1.1 Quad-Tree come struttura per la risoluzione del problema.

La struttura fondamentale dell’algoritmo di segmentazione da noi usato è il Quad-Tree[14]. Questo è un albero avente come nodi regioni dell’immagine etichettate da un numero intero, correlato da una serie di informazioni quali il grado di entropia rispetto al nodo padre, ed altri attributi come le coordinate spaziali dello spigolo in alto a sinistra della sezione d’immagine, la sua grandezza in pixels ed un flag che denota l’appartenenza ad una lista contenente i nodi già scelti precedentemente per essere colorati (lista B-Closed). In particolare ogni nodo avrà quattro figli che rappresentano la suddivisione dell’immagine in quattro parti uguali. La radice del Quad-Tree è l’immagine completa stessa ed avrà grado di entropia uguale a zero, mentre le foglie sono rappresentate da aree di grandezza 2x2, visto che è inutile analizzare un singolo pixel. L’etichetta del nodo ci dà varie informazioni: si può evincere la profondità del nodo semplicemente contando il numero di cifre, perchè per ogni spostamento in basso dentro l’albero viene aggiunta all’etichetta una cifra da 1 a 4 rappresentante il figlio scelto (abbiamo scelto di numerare i figli da sinistra verso destra). In questo modo conoscendo l’etichetta, in sette passi al massimo, riusciamo a raggiungere il nodo da esaminare rendendo così logaritmico il tempo d’accesso a tutti i nodi. Nella figura 1.1 è dato un esempio visivo di un Quad-Tree.

1.2 Stuttura dell’algoritmo.

L’algoritmo di segmentazione può essere riassunto nei seguenti passi:

  1. Creazione del percorso ottimo.
  2. In questa fase partendo dalla radice del QuadTree scendiamo fino alle foglie, scegliendo passo dopo passo i nodi aventi grado di entropia minore e non appartenenti alla lista B-Closed.

  3. Scelta del nodo campione.
  4. A questo punto risaliamo verso la radice scegliendo tra i nodi appartenenti al percorso ottimo quello con grado di entropia minore definendo così il nodo campione da cui poi parte la ricerca vera e propria.

  5. Analisi dei nodi.
  6. Avendo come riferimento il nodo campione vengono valutati tutti i nodo dello stesso livello non appartenenti alla lista B-Closed, calcolando il grado di similitudine col nodo campione, e scegliendo i nodi con funzione di valutazione maggiore di una certa soglia rappresentata dal grado di entropia del nodo campione rispetto al nodo padre. Per completezza abbiamo creato due funzioni che analizzano sia i nodi connessi a quello campione sia la totalità dei nodi presenti nel livello. Infatti, nell’applicazione possiamo sia lanciare il processo di segmentazione completa dove il nodo campione viene scelto seguendo i passi precedenti, sia scegliere il nodo campione con relativa profondità, gestendo anche la soglia d’errore.

  7. Colorazione dei nodi simili al nodo campione.
  8. Tutti i pixels dei nodi prescelti nello stesso ciclo verranno quindi colorati con lo stesso colore. Vengono inoltre aggiornati i flags d’appartenenza alla lista B-Closed. Di solito il numero di colori che servono per completare una segmentazione di immagini di tipo medico si aggira intorno ai dieci-quindici. La classe contenente i colori usati durante la segmentazione ne contiene trenta.

  9. Iterazione dei passi 1,2,3,4 fino al coloramento dell’intera immagine.

Per ragioni del tutto pratiche abbiamo pensato di interrompere l’algoritmo quando il numero di pixels non colorati diventa minore di 3000.

1.3 Funzione di valutazione.

La funzione d’entropia scelta nel nostro caso si basa sull’analisi degli istogrammi[20]. Essa è strettamente legata sia al nodo per il quale si calcola la funzione sia al nodo di riferimento che, nel caso di creazione del percorso ottimo, è il nodo padre, mentre nel caso di ricerca di nodi simili, è il nodo campione dello stesso livello. In realtà per ogni porzione d’immagine viene creato l’istogramma delle tonalità di grigio: vale a dire un particolare grafico che ha sull’asse delle ascisse la tonalità di grigio e sull’asse delle ordinate il numero di occorrenze (diventate poi rapporto fra occorrenze e area) di pixels con la stessa tonalità di grigio.

Sia un istogramma. L’area del nodo può essere calcolata anche come:

Andiamo quindi a calcolarci il rapporto tra le occorrenza di ogni tonalità di grigio e l’area della sezione d’immagine:

Tramite un’algoritmo che controlla la varizione di crescenza e descrescenza di una funzione ci ricaviamo i sei picchi maggiori:

Applicando i precedenti passi a due nodi del Quad-Tree possiamo calcolare la loro funzioni di similitudine:

Siano i maggiori picchi di due nodi.

dove

I nodi scelti saranno quelli con grado di similitudine al nodo campione maggiore o uguale alla soglia d’errore stabilita precedentemente.

1.4 Estrazione del contorno.

L’algoritmo usato per ricavare il set di punti appartenenti al contorno dell’anomalia si basa sul concetto di ricerca per 8-connesso[16]. In effetti, partendo da un punto qualsiasi del contorno, , si procede con una ricerca del punto successivo nelle otto direzioni consentite. Tale procedimento è applicato, in senso orario, ad ogni punto, che si è determinato appartenente al contorno, finché non si giunge, nuovamente, al punto di partenza .

Un possibile algoritmo è il seguente:

INPUT: punto interno alla regione;

OUTPUT: insieme di punti appartenenti al contorno della regione;

Passo 1: sia il colore del punto ,

;

while il colore di curr è uguale a C

; ;

;

metti il punto nella catena dei punti del contorno.

Passo 2:

;

;

Passo 3:

Scandisci l’intorno 8-connesso di , partendo da e procedendo in senso orario fino a trovare il punto .

Passo 4:

Metti nella catena dei punti del contorno;

;

;

Passo 5:

Applica ricorsivamente i passi 3 e 4 fino a ritornare al punto di partenza del Contorno.

Tale algoritmo è lineare nel numero dei punti del contorno.

Sfortunatamente, la discretizzazione dell’oggetto per mezzo dell’estrazione del suo contorno non è sempre uniforme, in virtù di variazione nel device d’input, distorsione geometriche , ma soprattutto a causa della casualità con cui si "riconosce" il primo punto del contorno. Ciò comporta una fase, successiva, d’approssimazione poligonale non sempre univoca (in pratica il poligono approssimante la shape non ha sempre lo stesso numero di punti).

Per superare tale difficoltà, nell’algoritmo d’approssimazione si ordina la sequenza dei punti del contorno, prendendo come punto iniziale, quello più in basso a sinistra.

1.5 Approssimazione poligonale.

L’approssimazione poligonale di una curva digitalizzata bidimensionale è spesso una rappresentazione compatta ed effettiva di una curva per l’analisi di forme[17-19]. Tale rappresentazione facilita l’estrazione di caratteristiche numeriche per la descrizione o classificazione della data curva. Inizialmente, i principali algoritmi d’approssimazione poligonale erano basati su euristiche che portavano a tempi d’esecuzione elevati. In casi d’applicazioni in tempo reale, che richiedevano, quindi, tempi di risposta molto veloci, tali metodi risultavano obsoleti e poco efficienti.

L’algoritmo d’approssimazione poligonale da noi scelto, ed implementato, è ricavato dalle teorie di G. Papakonstatinou[19]. La ragione fondamentale di questa scelta è da riscontrare nel notevole vantaggio di avere, in output, un poligono approssimante la shape con il minimo numero di segmenti (proprietà non riscontrata nella visitazione di altri metodi analizzati in precedenza).

Tale algoritmo (OPLA-Optimal Peicewise Linear Approximation Algorithm) è, inoltre, applicabile sia nello spazio mono- sia bi-dimensionale.

Descrizione dell’algoritmo.

Per una giusta comprensione dell’algoritmo diamo alcune definizioni fondamentali

Definizioni 1.1:

Curva Digitale: una sequenza di punti campione {(x1,y1),….,(xn,yn)} dove (xi,yi) sono le coordinate dei punti campione i, 1£ i £ n.

e : un errore limite rappresentante la massima distanza euclidea permessa dai punti campione all’approssimazione dei segmenti.

Ci: il cerchio con centro (xi,yi) e raggio fissato che può essere scelto arbitrariamente.

ai(k): l’arco del cerchio, definito in figura 1.3, per un "punto sorgente" e un punto campione (xk,yx) ,i<k.

Ai(j): la parte comune di tutti gli ai(k), i+1 £ k £ j . Se non c’è nessuna parte in comune allora Ai(j)=nil.

Valid(i,p,j): è un predicato che assume valore vero se:

a) Ai(j) ¹ nil e

b) la linea [(xi,yi),(xp,yp)], p³ i+1 interseca Ai(j).

Ti : l’insieme {j, jÎ (i+1,s ], tale che valid (i,j,j)=vero} dove s è un indice tale che

Ai(s )¹ nil e Ai(s +1)=nil. (1)

d(i, j, e ): la "distanza" di un punto campione i dal punto campione j, i£ j cioè il minimo numero di segmenti approssimante i punti campione i,i+1,…,j dentro e . La distanza d(i, i, e ) è definita come zero.

Useremo di seguito, il termine "più lungo" con il seguente significato. Un segmento [(xi,yi),(xp,yp)] , con i<p, è più lungo del segmento [(xi, yi),(xq, yq)] , con i<q, se p>q.

Lemma 1.1

Se la distanza Euclidea di un punto campione (xk,yk) da una linea l= [(xi,yi),(xG ,yG )], con i < k < G , è minore di e allora la linea l interseca ai(k) e viceversa [19].

Teorema 1.1

L’indice G =Max(Ti ) definisce il più lungo segmento [(xi,yi),(xG ,yG )] approssimante il punto campione j, i £ j £ G ,tale che la distanza Euclidea è minore di e [19].

IL seguente algoritmo restituisce l’indice G dove il punto sorgente è i.

Algoritmo:

begin

G =i+1; j=i+1; Calcola Ai(j);

while j < n-1 do

begin

j=j+1;

Calcola Ai(j) e valid (i,j,j);

if Ai(j) = nil then return;

if valid(i,j,j) = true then G =j

end

end

Lemma 1.2.

Tutti i possibili segmenti partenti dal punto campione i che approssimano il punto campione j, i £ j £ n con distanza Euclidea minore di e , sono :

[(xi, yi),(xp, yp)] con pÎ Ti e Ti come definito in (1).

Lemma 1.3.

La distanza d(i, n, e ) di un punto campione i dall’ultimo punto campione n con un dato e è :

d(i, n, e )=Min(Di)+1 , con Di ={ d(j,n,e ), tale che jÎ Ti }. (2)

Descriveremo informalmente usando l’algoritmo precedente, un algoritmo per determinare la distanza d(i, n, e ), 1£ i£ n e una soluzione ottimale, basata sul lemma 1.2 e lemma 1.3.

Algoritmo OPLA:

begin

d(n,n,e )=0;

for i=n-1 step –1 until 1 do

begin

Calcola Ti { Ti come definito in (1)};

d(i,n,e )=Min(Di)+1 { Di come definito in (2)};

end;

k=1;c=1; e= d(1,n,e ); i=1;

while i<n do

begin

find Ti; k=k+1; e=e-1; G k=p; i=p;

{dove pÎ Ti e d(p,n,e ) =e }

end

end

L’algoritmo è basato sulla semplice idea che se conosciamo la distanza d(j, n, e ) per i£ j£ n allora per il lemma 1.2 e lemma 1.3 trova la distanza d(i-1, n, e ). La condizione iniziale è che d(n, n, e )=0.

Partendo dal punto iniziale p0 del contorno rappresentante l’oggetto da esaminare, si seleziona la coppia successiva di punti (p1, p2) e si disegna una circonferenza di centro p1 il cui raggio è l’errore e scelto. Si traccia, susseguentemente, un segmento dal punto p0 al punto p2 e si controlla se il segmento interseca la circonferenza di raggio e . Nel caso si verifichi quest’ipotesi, si applica il procedimento precedente per la terna p1, p2, p3 , altrimenti si sceglie p2 come punto feature (vertice del poligono) e si procede ad ispezionare la terna che ha come punto di partenza p2 stesso. Il ragionamento precedente viene ripetuto, iterativamente, finché non si raggiunge l’ultimo punto del contorno.

Il tempo richiesto per trovare la soluzione è inversamente proporzionale alla riduzione della curva digitalizzata. In particolare, esso è approssimativamente k volte maggiore del tempo richiesto per trovare una soluzione non ottima, dove k è :

 

Risultati sperimentali.

A causa della diversità delle shape contenute nel database, la soglia d’approssimazione (errore e ) varia in intervalli scelti empiricamente in funzione del numero di punti del contorno.

Inizialmente, si era pensato di associare un valore univoco alla soglia e , ma sperimentalmente si è potuto costatare che tale valore non era sufficientemente adatto a fornire un’approssimazione adeguata per ogni shape contenuta nel database.

In effetti, nella maggior parte dei casi, e soprattutto per shape con un numero di punti di contorno relativamente piccolo, si aveva una forma poligonale approssimata in maniera abbastanza grossolana.

 

Dalla figura 1.4 si evince chiaramente quanto detto sopra. Ciò potrebbe indurre a pensare di suddividere in due fasce le forme ricavate dalle immagini nel D.B., ma anche tale soluzione comporta diverse inefficienze. Infatti, oltre a quelle già sottolineate in precedenza, la più evidente consiste nell’avere rappresentazioni poligonali molto vicine alla shape originali e ciò risulta sconveniente se si vuole avere una semplificazione nello studio della forma stessa.

Attraverso diverse casistiche, si è giunti alla seguente suddivisione in intervalli:

Intervallo

(numero di punti del contorno)

Errore e

[50,170[

2.0

[170,250[

4.1

[250,550[

6.5

[550,750[

9.5

[750,+¥ [

14.5

Home