Region growing

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica sorgente]

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.

(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[modifica | modifica sorgente]

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 quaesti 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[modifica | modifica sorgente]

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 segmento del fulmine dallo sfondo. Si può in oltre 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 risultate 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 vogliamo ottenere. Alcuni esempi spesso utilizzati sono: livello di grigio (intensità media o varianza), il colore, e la struttura o la forma.

Esempio simulato[modifica | modifica sorgente]

Qui viene mostriato un semplice esempio di region growing:

La Figura 1 rappresenta l'immagine originale, in scala di grigi di un fulmine. La scala di grigi varia tra 0 a 255. Lo scopo qui è di applicare il region growing per separare la parte maggiormente chiara del fulmine. Pertanto, si sono selezionati i punti aventi un alto valore nella scala di grigi che è 255 come i punti seme mostrati nella Figura 2.

Dopo aver determinato i punti seme, bisogna determinare la soglia. Si ricorda che lo scopo è quello di discriminare la luce più forte nell'immagine. La Figura 3 è il risultato del region growing con un valore di soglia posto a 225 e il valore dei punti seme sempre a 255. Ciò vuol dire che solo i punti i cui valori nella scala di grigi sono al di sopra 225 sono rappresentati.

Se ampliamo l'intervallo di soglia, si ottiene un risultato che ha una superficie più grande della regione mostrata nella Figura 3; vedi la Figura

Possiamo osservare la differenza tra le ultime due immagini con un valore di soglia differente. Il metodo region growing offre la possibilità di separare la parte che vogliamo collegare.

Come si può vedere nella Figura 3, 4 e 5, il risultato segmentato in questo esempio sono seme collegati. Ciò significa che il risultato è cresciuto passando dai pixel seme alle regioni. Ed i punti non cresceranno se non sono collegati con i punti seme fin dall'inizio. Pertanto, si può dire che nella Figura 5 vi sono ancora molti punti aventi un valore sopra a 155, ma questi non vengono marcati nella Figura 5. Questa caratteristica assicura l'affidabilità della segmentazione e fornisce la capacità di resistere al rumore. Per questo esempio, questa caratteristica impedisce di tralasciare la parte oscura nell'immagine perché la parte chiara è sempre collegata ad un seme.

Vantaggi e svantaggi[modifica | modifica sorgente]

Vantaggi[modifica | modifica sorgente]

  • 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.
  • Sia 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[modifica | modifica sorgente]

  • 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.

Bibliografia[modifica | modifica sorgente]

  • 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.

Note[modifica | modifica sorgente]

  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.

Altri progetti[modifica | modifica sorgente]

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