Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Giovanni Mettivier » 16.Region Growing


Region Growing

Mentre le tecniche di thresholding si basano sulla differenza tra l’intensità dei pixel, le tecniche di region growing cercano gruppi di pixel con intensità simili.
Si inizia con un pixel (o gruppo di pixel) che appartiene alla struttura di interesse, chiamato “seme” e si passa poi ad esaminare uno alla volta i pixel nel suo intorno (gli 8 connessi) che sono inclusi o esclusi dalla regione in base ad un criterio di omogeneità.
Se è un problema 3D, allora l’intorno è composto dai pixel 26-connessi, in questo modo la complessità del problema cresce esponenzialmente.
La ricerca continua fino a che nessun ulteriore pixel può essere aggiunto alla regione.

Region Growing (segue)

Il region growing trova applicazione in diverse aree di medical image processing, come ad esempio:

  • Segmentazione dei ventricoli nelle immagini cardiache;
  • Estrazione dei vasi sanguigni dai dati angiografici;
  • Estrazione delle superfici celebrali.

Region Growing (segue)

Nell’approccio più semplice, i valori dei pixel sotto test sono paragonati con il valore del pixel seme ed è stabilita una tolleranza all’interno della quale il valore del pixel test deve essere incluso.
Questo approccio, per essere realizzabile, richiede un elevato rapporto contrasto-rumore.
Uno svantaggio è che per immagini con varianza molto grande, il numero sarà sensibile alla posizione del seme.

Region Growing (segue)

Criteri di similarità o di omogeneità per la segmentazione possono tipicamente includere:

  • intensità media
  • varianza
  • struttura
  • forma
  • dimensione
  • parametri fisiologici

Region Growing (segue)

Segmentazione di una zona polmonare utilizzando il region growing.

Segmentazione di una zona polmonare utilizzando il region growing.


Region Growing (segue)

Confronto tra il metodo di thresholding (sinistra) e il region growing (destra).

Confronto tra il metodo di thresholding (sinistra) e il region growing (destra).


Metodo Hill Climbing

Una interessante modifica delle tecniche di region-growing è la tecnica Hill Climbing.
È tipicamente usata per rivelare piccoli dettagli come una micro-calcificazione nelle immagini mammografiche.
Essa si basata sul fatto che in una data immagine f(x,y), il bordo da segmentare è un contorno chiuso intorno a un pixel noto (x0,y0).

Metodo Hill Climbing (segue)

Fissato il pixel (x0,y0) viene identificato il pixel che fornisce la massima pendenza lungo una linea radiale. Questo pixel è considerato essere nel bordo. La ricerca è effettuata in 16 direzioni.

I punti del bordo sono usati come semi per il region growing come “constraints” spaziali.

Applicazione del metodo di Hill Climbing. Prima vengono trovati i 16 massimi sul bordo (alto, destra) e poi viene costruita la regione (basso).

Applicazione del metodo di Hill Climbing. Prima vengono trovati i 16 massimi sul bordo (alto, destra) e poi viene costruita la regione (basso).


Metodo Watershed

Il metodo Watershed interpreta le immagini come mappe d’altezza che sono formate da bacini e creste.

Rappresentazione di una immagine (sinistra) come una mappa d’altezza (destra).

Rappresentazione di una immagine (sinistra) come una mappa d'altezza (destra).


Metodo Watershed (segue)

Algoritmo Rainfall (pioggia)
Marca tutti i minimi locali.
Mette una goccia su ogni pixel non etichettato.
La goccia fluisce verso un minimo locale usando un gradiente discendente.
Assegna l’etichetta del minimo locale trovato al pixel di partenza della goccia.

Metodo Watershed (segue)

Algoritmo Flooding (inondazione)
Parte dal valore di intensità più piccolo ed aumenta di livello in livello fino all’inondazione del paesaggio.
Costruisce un bordo quando bacini separati si uniscono durante l’inondazione.
Rivela le regioni di merging ed eregge le diga settando il valore di grigio più alto.
Risultato: una regione per ogni minimo locale.

Rappresentazione del metodo flooding.

Rappresentazione del metodo flooding.


Metodo Watershed: Proprietà

Questi algoritmi forniscono sempre bordi chiusi intorno alle regioni ed ad ogni minimo locale corrisponde una regione.
Uno dei possibili problemi con questi algoritmi è la sovra-segmentazione. Per evitarla si ricorre allo smooting preliminare dell’immagine.
Altre possibilità per evitare la sovra-segmentazione sono l’impostazione della:

  • Minima profondità del bacino
  • Minima dimensione del bacino
Esempio di una immagine sovra-segmentata (sinistra) e di una immagini segmentata correttamente (destra).

Esempio di una immagine sovra-segmentata (sinistra) e di una immagini segmentata correttamente (destra).


Modelli

La Segmentazione può essere ottenuta anche attraverso l’uso di modelli.

  • Ricerca di forme, es. trasformata di Hough;
  • Modelli parametrici deformabili;
  • Atlas, es. atlante statistico.

Trasformata di Houge

Una volta definito uno spazio parametrico in base alle caratteristiche che devono essere rivelate, si effettua una trasformazione dei punti dell’immagine dalle coordinate cartesiane allo spazio parametrico.
L’insieme dei parametri deve essere scelto secondo le caratteristiche che devono essere rivelate, ad esempio:

  • Distanza dall’origine (r) e l’angolo dell’asse x (t) quando si cercano delle linee in 2D (spazio 2D per i nuovi parametri)
  • Coordinate del centro e raggio quando si cercano dei cerchi (spazio 3D per i nuovi parametri).

Trasformata di Houge (segue)

Per ogni punto nell’immagine originale, l’algoritmo:

  • considera ogni possibile valore della caratteristica attraverso questo punto;
  • trasforma la caratteristica nello spazio dei parametri;
  • aggiunge (scalata) il valore intensità al grafico dei parametri.

Risultato: per punti nelle coordinate originali -> Curve nello spazio dei parametri.
Punti appartenenti alla stessa caratteristica nell’immagine originale si trasformano in curve intersecanti nello spazio dei parametri -> clustering
Trasforma i clusters nelle coordinate originali per prendere le caratteristiche.

Trasformata di Houge (segue)

Applicazione della trasformata di Houge per trovare il centro 
dei dots presenti nell’immagine di partenza.

Applicazione della trasformata di Houge per trovare il centro dei dots presenti nell'immagine di partenza.


Modelli Parametrici

Modelli parametrici deformabili
La segmentazione attraverso un modello deformabile che rappresenta l’interfaccia tra sfondo e regione che dovrebbe essere segmentata.

Snakes

Esempio del funzinamento dell’algoritmo “snakes”.

Esempio del funzinamento dell'algoritmo “snakes”.


Snakes (segue)

Il metodo “snake” o inseguimento del bordo usa kernel per la rivelazione dei bordi per identificare un punto su un contorno.
I pixel 8 connessi sono poi valutati usando il kernel, e i pixel che forniscono la risposta più alta è definito come il pixel successivo sul bordo.
Il processo continua finché non è ottenuta una regione chiusa.

Snakes (segue)

Questi metodi richiedono regioni con bordi netti definiti da forti gradienti di intensità.
Si deve assicurare che le curve non si attraversano tra di loro.
Si deve evitare l’eccessivo smoothing nella riduzione del rumore.

Snakes (segue)

Metodi per l’inseguimento automatico del bordo rappresentano un approccio locale a quello che può essere un problema globale.
Gli osservatori possono “look ahead” per trovare pezzi di un bordo da includere in un contorno (raggruppamento).
Questo è difficile con algoritmi che cercano solo una piccola regione a un dato tempo.
Vuoti nei contorni (es. contrasto ridotto o artefatti) sono facilmente uniti dagli osservatori.

Snakes (segue)

Regioni adiacenti possono avere contorni che si toccano.
Un processo di inseguimento dei bordi possono proseguire lungo entrambi i bordi fino ad incontrare la biforcazione che fornisce un risultato sbagliato.
Bisogna definire chiaramente i criteri di stop, es. ritornare al punto di partenza.

Atals

Registrazione di un insieme di dati pre-segmentati (atlas) all’immagine attuale, es. registrazione per deformazione.
Mapping di etichette dall’atlante ad un insieme di dati.
Il processo di segmentazione è convertita in un processo di registrazione.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion