Metodi con la trasformata Watershed

Segmentazione con la distance transform

Il seguente algoritmo esegue la segmentazione di un’immagine, seguendo il metodo descritto nel paragrafo 2.3.1.

f= imread( ’image.jpg’); g = im2bw(f,graythresh(f)); gc = ~g; D = bwdist(gc); L = watershed(-D); w = L==0; g2 = g&~w;

Acquisita l’immagine di input, la si converte in binaria tramite la sogliatura col valore graythresh(f). Successivamente si applica la distance transform (con la funzione D = bwdist(gc)) all’immagine gc, che ´e la complementare di quella sogliata. Calcolata la watershed transform all’immagine -D, si de- terminano le linee ”spartiacque” e le si sovrappone all’input, ottenendo i risultati riportati nella figura 3.13.

Come prevedibile, la funzione watershed ha prodotto troppe linee di cresta. Segmentazione con il gradiente

Per ridurre l’effetto dell’oversegmentation si pu´o provare ad applicare la trasformazione watershed all’immagine del gradiente. Il seguente algoritmo determina il gradiente con le approssimazioni di Sobel e, infine, calcola la segmentazione.

f= imread( ’image.jpg’); h = fspecial(’sobel’);

(a) Distance transform (b) Watershed ridgelines (c) Output finale

(d) Distance transform (e) Watershed ridgelines (f) Output finale

Figura 3.13: Output della segmentazione watershed con la distance transform fd = double(f);

g = sqrt ( imfilter(fd,h,’replicate’).^2 + imfilter(fd,h’,’replicate’).^2 ); L = watershed(g);

wr = L==0;

La figura 3.14 riporta i risultati di questi passaggi.

Le immagini (a), (b) e (c) mostrano i gradienti, le altre presentano le ridge- lines individuate. I risultati ottenuti sono totalmente insoddisfacenti: nel caso pi´u semplice, (d), le circonferenze pi´u piccole sono rappresenate da un groviglio di quadratini, nel secondo esempio si intravede solo la sagoma del piede e di poche ossa, mentre nell’ output (f) non si distingono elementi al- l’interno.

(a) (b) (c)

(d) (e) (f)

Figura 3.14: Immagini dei gradienti e output della segmentazione con le ridgelines

Come gi´a spiegato nel paragrafo 2.3.2, conviene smussare l’immagine del gradiente, aggiungendo all’algoritmo i seguenti passaggi.

g2 = imclose ( imopen(g,ones(3,3)),ones(3,3) ); L2 = watershed(g2);

wr2 = L2==0; f2 = f;

f2(wr2) = 255;

In particolare, l’ultimo comando permette di visualizzare l’immagine origi- naria con le linee bianche sovrapposte. Ad ogni modo, gli output mostrati nella figura 3.15 sono migliori, ma non ancora ottimi.

(a) (b) (c)

(d) (e) (f)

Figura 3.15: Output della segmentazione e sovrapposizioni con l’input Nelle immagini (a) e (d) si vede un netto miglioramento, mentre con gli input pi´u complicati la correzione continua a non fornire i risultati desiderati. Chiaramente, il problema dell’oversegmentation ´e proporzionale alla difficolt´a di segmentazione dell’immagine.

Segmentazione con i marcatori

Questa procedura ´e stata sviluppata per ridurre l’oversegmentation dei risultati precedenti. Applicando la funzione

rm = imregionalmin (g);

dell’IPT all’immagine del gradiente precedentemente calcolata, si evidenziano tutti i punti di minimo locale dell’immagine. Se si considera il caso ”inter- medio” della TAC, per esempio, si vede bene che l’abbondante presenza di

questi punti produce tanti piccoli e fitti ”bacini di raccolta”, che evidenziano zone di irrelevante importanza.

Figura 3.16: Regional minima dell’input

La funzione imextendedmin (f, h) dell’IPT elimina i minimi in eccesso, determinando gli insiemi di punti, il cui valore ´e inferiore a quello dei pixel circostanti di una certa quantit´a h. Dunque la sintassi

im = imextendedmin(f,2);

determina i marcatori interni dell’immagine originale.

Successivamente si cercano i marcatori esterni, identificandoli come punti intermedi tra i minimi: per farlo, si calcola la watershed transform della trasformata delle distanze, applicata all’immagine coi marcatori interni.

Lim = watershed ( bwdist(im) ); em = Lim==0;

Ottenuti tutti i marcatori, li si utilizza per modificare il gradiente, con la procedura della minima imposition, implementata dal comando

dove im|em ´e un’immagine binaria, i cui pixel di sfondo marcano le po- sizioni dei minimi locali dell’immagine di output. Ora si esegue la trasforma- ta sul nuovo gradiente g2 e si predispone l’output con l’immagine originale sovrastata dalle righe ottenute.

L2 = watershed(g2); f2 = f;

f2( L2==0 ) = 255; Eccone i risultati grafici:

(a) Marcatori interni (b) Marcatori esterni

(c) Gradiente col minima imposi- tion

(d) Risultato finale

Figura 3.17: Output della segmentazione e sovrapposizione con l’input La segmentazione con la trasformata watershed, cos´ı articolata, fornisce risultati migliori. Dallo sfondo spariscono quasi tutte le ridgelines, che non

corrispondevano ad alcun elemento nell’immagine, mentre restano numerose quelle nell’area interna al piede. In verit´a, qui non determinano con esattezza la forma delle ossa, n´e tantomeno si concentrano in prossimit´a dei contorni.

In questa dissertazione si sono analizzate diverse tecniche di estrazione dei contorni e di segmentazione delle immagini digitali a toni di grigio.

Il filtraggio con una maschera rileva molto bene i bordi degli oggetti e non ´e particolarmente sensibile al rumore delle immagini, per´o lascia molto spesso contorni aperti ed incompleti, cos´ı come non si presta particolarmente per immagini piene di linee sottili. Al contrario, operatori come quello di Sobel, di Canny e l’LoG sono maggiormente influenzabili dal rumore e, per questo, hanno pi´u frequentemente problemi di oversegmentation. D’altra parte, restituiscono contorni molto precisi, chiusi e nitidi.

Per quanto riguarda le tecniche di segmentazione, il metodo della sogliatu- ra ´e quello computazionalmente pi´u semplice e veloce, che permette di ot- tenere risultati apprezzabili. Eventualmente settando un confacente valore di soglia, si possono ricavare output decorosi anche da immagini ”difficili”, con molte sfumature di grigio.

La segmentazione region-based ´e generalmente poco sensibile al rumore del- l’input. Inoltre, ´e sufficiente settare accuratamente i due parametri che carat- terizzano l’algoritmo della region growing, per ottenere output significativi dove le linee siano ben definite e le sfumature di grigio ben distinte. Meno comprensibili sono i risultati del metodo splitting and merging, poich´e ab- bassando il parametro di soglia si ottiene un’immagine pi´u nitida ma meno contrastata e troppo scura.

Infine, la segmentazione con la trasformata watershed ha evidenziato il pre- visto problema dell’oversegmentation, che ´e stato in parte ridotto, passo a passo, con i metodi successivamente elaborati.

Comunque, il problema della segmentazione non ha una soluzione che sia in assoluto preferibile alle altre, perch´e dipende dalle caratteristiche di ogni singolo input. Infatti, se le immagini binarie sono facili da elaborare, sia quelle ricche di sfumature (come la risonanza magnetica del cervello) che quelle costiuite da tratti e linee sotitli (come quella del testo) comportano maggiori difficolt´a, anche di diversa natura.

[1] Gonzalez, Woods and Eddins, Digital Image Processing Using MATLAB, Prentice Hall, 1st edition, 2004.

[2] http://www.imageprocessingplace.com/

[3] The MathWorks, Image Processing Toolbox, User’s guide, Version 4. [4] John F. Canny, ”A Computational Approch for Edge Detection”, in

IEEE Transactions Pattern Analysis and Machine Intelligence, IEEE Computer Society, pp. 679-698, 1986.

[5] Nobuyuki Otsu, ”A Threshold Selection Method from Gay-Lvel Hist- grams”, in IEEE Transactions on Systems, Man, and Cybernetics, IEEE Computer Society, pp.62-66, 1979.

[6] Harry L. Van Trees, Detection, Estimation and Modulation Theory, part I, Wiley-Interscience Pubblication, 1968.

[7] Luc Vincent and Pierre Soille, ”Watersheds in Digital Spaces: An Ef- ficient Algorithm Based on Immersion Simulations”, in IEEE Trans- actions Pattern Analysis and Machine Intelligence, IEEE Computer Society, pp. 583-598, 1991.