I metodi region–based partono dal presupposto che all’interno di una regione i pixel vicini hanno valori di intensità simili; gli algoritmi, quindi, confrontano ciascun pixel con quelli del suo intorno, e se viene soddisfatto un certo criterio di similarità il pixel può essere annoverato tra quelli appartenenti alla regione.
Questo tipo di segmentazione può seguire due diversi approcci:
• bottom–up, in cui inizialmente ogni singolo pixel è considerato come un’unica regione a sé stante. Le regioni vengono, poi, accorpate tra loro fino a che non viene raggiunto il risultato richiesto;
• top–down, in cui l’intera immagine viene vista come un’unica regio- ne. Successivamente, vengono effettuate delle suddivisioni in maniera ricorsiva fino ad ottenere il risultato richiesto.
2.3.1 Region growing
Tra le segmentazioni di tipo bottom–up troviamo quelle che riguardano la crescita delle regioni (region growing). Questo tipo di tecnica raggruppa i pixel in regioni più grandi basandosi su dei criteri di crescita predefiniti.
L’idea alla base è quella di scegliere un insieme di punti seme (seed point, ognuno dei quali appartenente ad una diversa struttura nell’immagine) e poi far crescere le regioni aggiungendo a ciascun seme i pixel 8–connessi che soddisfano dei criteri di omogeneità (tra cui troviamo l’intensità). La crescita della regione si ferma quando non ci sono più pixel che possono
essere aggiunti. Spesso, però, la formulazione di una regola di stop per questo tipo di algoritmo può generare alcuni problemi di segmentazione, poiché i criteri di similarità scelti non tengono conto della storia legata alla crescita di ciascuna regione. È tuttavia possibile aggiungere dei criteri addizionali che utilizzino, ad esempio, le informazioni sulla forma e le dimensioni della struttura da estrarre (anche se questo presuppone una conoscenza a priori del modello) e/o sulla somiglianza tra il pixel candidato e i pixel aggiunti fino a quel momento (confrontando l’intensità del pixel candidato con l’intensità media dei pixel nella regione) [18].
Un grande svantaggio della tecnica di region growing è che il numero delle aree segmentate è sensibile alla posizione e al numero iniziale dei semi; inoltre la segmentazione dipende molto dall’ordine con cui l’algoritmo analizza i pixel dell’immagine. La scelta dei semi iniziali diventa, quindi, di fondamentale importanza: se una regione che si vuole segmentare non ha al suo interno un seed di partenza, non potrà essere segmentata come una singola regione poiché i pixel al suo interno verranno associati a regioni attigue (problemi di sotto–segmentazione). Analogamente, se i semi iniziali sono troppo numerosi è possibile che l’algoritmo vada a sovra–segmentare l’immagine.
Nell’ambito della diagnostica per immagini, le tecniche di region gro- wing sono spesso utilizzate per la segmentazione dei tumori e delle lesioni del cervello in MRI, o per la segmentazione delle ossa nella tomografia computerizzata [53].
2.3.2 Divisione e fusione delle regioni: metodo split and merge
Tra le tecniche di segmentazione top–down troviamo la divisione e fusione delle regioni (region splitting and merging). Questo metodo consiste nel frazionare l’immagine in un insieme di sotto–regioni disgiunte per poi unirle o dividerle ulteriormente nel tentativo di soddisfare dei criteri di omogeneità.
Utilizzando il formalismo introdotto nel Paragrafo 2.1, sia R l’intera immagine e Q un certo predicato da soddisfare. L’approccio per segmentare R è quello di suddividerla ricorsivamente in regioni quadrate sempre più piccole in modo che Q(Ri) = TRUE ∀i. Partendo, quindi, dall’intera
immagine R, se Q(R) = FALSE l’immagine viene suddivisa in quattro quadranti; se in uno di questi non si soddisfa il predicato Q viene effettuata un’ulteriore suddivisione del quadrante e così via. Questa divisione ricorsiva può essere riprodotta tramite una struttura ad albero (vedi Figura 2.2): ogni nodo contiene le informazioni relative a ciascun quadrante e i suoi figli rappresentano l’ulteriore suddivisione. Un nodo foglia è un quadrante sufficientemente uniforme da non richiedere successivi partizionamenti.
Se l’immagine venisse solo suddivisa si avrebbero regioni adiacenti di- sgiunte nonostante queste abbiano caratteristiche simili; è quindi richiesta una successiva fase di fusione delle regioni: sulla base dello stesso criterio
Figura 2.2: Operazione di suddivisione dell’immagine rappresentata da una struttura ad albero.
di similarità che ha generato la divisione, vengono fuse insieme solo quelle regioni i cui pixel soddisfano Q, ossia Q(Ri∪ Rj) =TRUE.
Uno dei problemi delle tecniche di region splitting and merging è che, a causa delle suddivisioni in quadranti, i bordi delle regioni individuate risultano squadrati e leggermente artificiali [21], e questo potrebbe causare degli inconvenienti nella segmentazione di immagini biomediche.
2.3.3 Trasformata watershed
Una tecnica di segmentazione region–based molto popolare, che fa uso sia di un approccio bottom–up che di uno top–down a seconda dell’algoritmo che viene utilizzato, è la trasformata watershed (letteralmente trasformata spartiacque).
Alla base della segmentazione con la trasformata watershed c’è l’idea che un’immagine a toni di grigio si possa rappresentare con un rilievo topografico dove i livelli di grigio di ogni pixel, f(x, y), vengono interpretati come altezze. Così una goccia d’acqua che cade sul rilievo topografico scorre lungo un percorso per raggiungere il bacino di raccolta dove c’è un minimo locale; possiamo pensare ai rilievi come a delle montagne dove si forma l’acqua che poi scorre giù fino al riempimento dei bacini idrografici, separati tra loro da una linea dello spartiacque. Allora, nell’ambito della segmentazione delle immagini, le linee dello spartiacque rappresentano i contorni degli oggetti da segmentare, che a loro volta sono identificati dai bacini.
La trasformata watershed è una tecnica di segmentazione molto usata anche su immagini biomediche grazie ai diversi vantaggi che offre: è un metodo semplice e intuitivo, è veloce e produce una buona separazione delle regioni dell’immagine anche con basso contrasto. Chiaramente non è esente da alcune problematiche, come la sovra–segmentazione (spesso la trasformata watershed utilizza le informazioni del gradiente per trovare i bacini e la segmentazione produce una miriade di piccole regioni, rendendo il risultato quasi inutilizzabile), la sensibilità al rumore e la difficoltà nell’individuare le regioni più piccole (lo smoothing associato alla stima del gradiente rende difficile individuare i bacini idrografici) [19].