it Region growing

Region growing (traducibile in italiano come "accrescimento delle regioni") è un semplice metodo di segmentazione di immagini basato su regioni. Viene anche considerato come un metodo basato sul singolo pixel poiché tale metodo comporta inizialmente la selezione dei punti seme.

Questo approccio alla segmentazione esamina i pixel adiacenti di punti iniziali, detti semi, e determina se i vicini di pixel possono essere aggiunti a tale regione. Il processo viene iterato, allo stesso modo come negli algoritmi di clustering di dati.

Segmentazione basata su regioni

L'obiettivo principale della segmentazione è di suddividere un'immagine in regioni. Alcuni metodi di segmentazione come quelli basati su di una "soglia" sono in grado di raggiungere questo obiettivo, andando a cercare i confini tra le varie regioni sulla base delle discontinuità nei livelli di grigio o nelle proprietà dei colori. La segmentazione basata su regioni è una tecnica per determinare la regione direttamente. La formulazione di base per la segmentazione basata su regioni è:

(a){\text{ }}\bigcup \nolimits _{i=1}^{n}{R_{i}=R.}

(b)R_{i}{\text{ è una regione connessa }},{\text{ i}}={\text{1}},{\text{ 2}},{\text{ }}...,{\text{n}}

(c){\text{ }}R_{i}\bigcap R_{j}=\varnothing {\text{ per ogni }}i=1,2,...,n.

(d)P(R_{i})=VERO{\text{ per }}i=1,2,...,n.

(e)P(R_{i}\bigcup R_{j})=FALSO{\text{ per ogni regione adiacente }}R_{i}{\text{ e }}R_{j}.

P(R_{i})

è un predicato funzionale definito sui punti nell'insieme

P(R_{k})

e

\varnothing

rappresenta l'insieme nullo.

(a) indica che la segmentazione deve essere completa, cioè, ogni pixel deve essere in una regione.

(b) richiede che i punti in una regione devono essere collegati in qualche modo predefinito.

(c) indica che le regioni devono essere disgiunte, questo indica la totale mancanza di pixel in comune fra due regioni.

(d) riguarda le proprietà che devono essere soddisfatte dai pixel in una regione segmentata. Ad esempio $P(R_{i})={\text{TRUE}}$ se tutti i pixel in $R_{i}$ hanno lo stesso livello di grigio.

(e) indica che la regione $R_{i}$ e $R_{j}$ sono differenti nel senso di predicato $P$ .

Concetto di base di punti seme

Il primo passo di un metodo di region growing è quello di selezionare un insieme di punti seme. La selezione di un punto seme è basata su alcuni criteri decisi dall'utente (ad esempio, pixel appartenenti ad un certo intervallo di livelli di grigio, pixel equidistanti su una griglia, ecc). Le regioni iniziali cominciano nella esatta posizione di questi semi.

Le regioni vengono quindi accresciute a partire da questi punti seme di altri punti adiacenti a seconda di un criterio di appartenenza alla regione. Il criterio potrebbe essere, ad esempio, l'intensità di pixel, il livello di grigio, o di colore.

Poiché le regioni crescono sulla base del criterio selezionato, le informazioni riguardanti l'immagine stessa diventano anche importanti. Ad esempio, se il criterio fosse di utilizzare un valore di soglia di un pixel, la conoscenza dell'istogramma dell'immagine risulterebbe comodo per determinare un valore di soglia adeguato al criterio utilizzato.

Un esempio molto semplice viene descritto qui di seguito. Se si considerano 4 pixel adiacenti al punto seme ed il criterio utilizzato sia quello del valore stesso del pixel, ovvero, esaminiamo i pixel adiacenti di punti seme. Se questi hanno lo stesso valore in intensità con i punti seme, li classifichiamo come i punti seme. Il processo viene iterato finché non ci sono cambiamenti in due fasi successive iterativi. Naturalmente, si possono utilizzare anche altri criteri, ma l'obiettivo principale rimane quello di classificare la somiglianza delle regioni nell'immagine.^[1]

Alcuni aspetti importanti

Possiamo quindi concludere diverse questioni importanti sul region growing:

1. L'opportuna scelta dei punti seme è importante: La selezione dei punti seme dipende dall'utilizzatore finale. Ad esempio, in un livello di grigio dell'immagine relativa al fulmine, si può desiderare di separare il fulmine dallo sfondo. Si può inoltre esaminare l'istogramma e scegliere i punti seme aventi un valore più alto di esso.

2. Maggiori informazioni, migliore sarà il risultato: Ovviamente, la connettività con pixel adiacenti risulta utile per determinare la soglia dei punti e dei semi.

3. Il valore, "superficie minima soglia": Nessuna regione nell'immagine risultante sarà inferiore a tale soglia.

4. La "somiglianza al valore di soglia": Se la differenza del valore del pixel o la differenza dei livelli di grigio di un insieme di pixel risulta inferiore al "valore di soglia di somiglianza", le regioni saranno considerate come una regione stessa.; I criteri di omogeneità o affinità che vengono selezionati sono importanti. Solitamente dipendono dall'immagine originale e dal risultato della segmentazione che si vuole ottenere. Alcuni esempi spesso utilizzati sono: livello di grigio (intensità media o varianza), il colore, e la struttura o la forma.

Vantaggi e svantaggi

Vantaggi

I metodi di region growing possono separare correttamente le regioni che hanno le stesse proprietà definite a priori.
I metodi di region growing sono in grado di fornire le immagini originali con margini netti e con risultati di segmentazione buoni.
Il loro concetto è semplice. Hanno solo bisogno di un numero ridotto di punti seme per rappresentare la proprietà che vogliamo e per poi crescere la regione.
Si ha la facoltà di determinare i punti seme ed i criteri che si vogliono implementare.
Si possono scegliere contemporaneamente criteri multipli.
Si comportano bene rispetto al rumore.

Svantaggi

Il calcolo è dispendioso, indipendentemente dal tempo.
La presenza di rumore o variazioni di intensità possono provocare buchi nell'immagine finale.
Questo metodo non potrebbe distinguere le ombreggiature nelle immagini reali.

In realtà il problema della presenza di rumore si può facilmente risolvere utilizzando apposite maschere per filtrare i buchi e/o i valori anomali. Pertanto, il problema del rumore si può anche ignorare. Concludendo, risulta evidente che il problema più grave nei metodi di region growing è il tempo che essi impiegano.

Note

^ (EN) CC Cheng, GJ Peng e WL Hwang, Pixel Connectivity, in IEEE transactions on image processing : a publication of the IEEE Signal Processing Society, vol. 18, n. 1, 2009, pp. 52–62, DOI:10.1109/TIP.2008.2007067, PMID 19095518. URL consultato il 16 febbraio 2009.

Bibliografia

Jian-Jiun Ding, The class of "Time-Frequency Analysis and Wavelet Transform", the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2007.
Jian-Jiun Ding, The class of "Advanced Digital Signal Processing", the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2008.
W. K. Pratt, Digital Image Processing 4th Edition, John Wiley & Sons, Inc., Los Altos, California, 2007
M. Petrou and P. Bosdogianni, Image Processing the Fundamentals, Wiley, UK, 2004.
R. C. Gonzalez and R.E. Woods, Digital Image Processing 2nd Edition, Prentice Hall, New Jersey, 2002.

Altri progetti

Wikimedia Commons contiene immagini o altri file su Region growing

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica

[1] (EN) CC Cheng, GJ Peng e WL Hwang, Pixel Connectivity, in IEEE transactions on image processing : a publication of the IEEE Signal Processing Society, vol. 18, n. 1, 2009, pp. 52–62, DOI:10.1109/TIP.2008.2007067, PMID 19095518. URL consultato il 16 febbraio 2009.

[1]