Spartiacque (elaborazione delle immagini)

In geologia, uno spartiacque è una divisione che separa i bacini idrografici adiacenti.

Spartiacque per allagamentomodifica

L’idea è stata introdotta nel 1979 da S. Beucher e C. Lantuéjoul. L’idea di base consisteva nel posizionare una fonte d’acqua in ogni minimo regionale nel rilievo, per inondare l’intero rilievo dalle fonti e costruire barriere quando diverse fonti d’acqua si incontrano. L’insieme risultante di barriere costituisce uno spartiacque dalle inondazioni. Un certo numero di miglioramenti, collettivamente chiamati Priority-Flood, sono stati apportati a questo algoritmo.

Spartiacque per distanza topograficamodifica

Intuitivamente, una goccia d’acqua che cade su un rilievo topografico scorre verso il minimo “più vicino”. Il minimo “più vicino” è quello minimo che si trova alla fine del percorso di discesa più ripida. In termini di topografia, ciò si verifica se il punto si trova nel bacino idrografico di quel minimo. La definizione precedente non verifica questa condizione.

Spartiacque dal principio della goccia d’acquamodiFica

Intuitivamente, lo spartiacque è una separazione dei minimi regionali da cui una goccia d’acqua può fluire verso minimi distinti. Una formalizzazione di questa idea intuitiva è stata fornita per definire uno spartiacque di un grafico ponderato per i bordi.

Inter-pixel watershedEdit

S. Beucher e F. Meyer hanno introdotto un’implementazione algoritmica inter-pixel del metodo watershed, data la seguente procedura:

1. Etichettare ogni minimo con un’etichetta distinta. Inizializza un set S con i nodi etichettati.
2. Estrai da S un nodo x di altitudine minima F, vale a dire F(x) = min{F(y)|y} S}. Attribuire l’etichetta di x a ciascun nodo non etichettato y adiacente a x e inserire y in S.
3. Ripetere il passaggio 2 fino a quando S è vuoto.

Spartiacque topologicomodifica

Le nozioni precedenti si concentrano sui bacini idrografici, ma non sulla linea di separazione prodotta. Lo spartiacque topologico è stato introdotto da M. Coutrie e G. Bertrand nel 1997 e beneficia della seguente proprietà fondamentale.Una funzione W è uno spartiacque di una funzione F se e solo se W ≤ F e W conserva il contrasto tra i minimi regionali di F; dove il contrasto tra due minimi regionali M1 e M2 è definito come l’altitudine minima a cui si deve salire per andare da M1 a M2. Un algoritmo efficiente è dettagliato nel documento.

Algoritmo spartiacque

Diversi approcci possono essere impiegati per utilizzare il principio spartiacque per la segmentazione delle immagini.

• I minimi locali del gradiente dell’immagine possono essere scelti come marcatori, in questo caso viene prodotta una sovra-segmentazione e un secondo passaggio comporta la fusione delle regioni.
• La trasformazione dello spartiacque basata su marker utilizza posizioni specifiche di marker che sono state definite esplicitamente dall’utente o determinate automaticamente con operatori morfologici o altri modi.

Algoritmo di inondazione di Meyer

Uno degli algoritmi di spartiacque più comuni è stato introdotto da F. Meyer nei primi anni 1990, anche se un certo numero di miglioramenti, collettivamente chiamati Priority-Flood, da allora sono stati fatti a questo algoritmo, comprese le varianti adatte per set di dati costituiti da trilioni di pixel.

L’algoritmo funziona su un’immagine in scala di grigi. Durante le successive inondazioni del rilievo di valore grigio, vengono costruiti bacini idrografici con bacini idrografici adiacenti. Questo processo di allagamento viene eseguito sull’immagine del gradiente, cioè i bacini dovrebbero emergere lungo i bordi. Normalmente questo porterà ad una sovra-segmentazione dell’immagine, specialmente per materiale immagine rumoroso, ad esempio dati medici della TAC. O l’immagine deve essere pre-elaborata o le regioni devono essere unite sulla base di un criterio di somiglianza in seguito.

1. Viene scelto un insieme di marcatori, i pixel in cui deve iniziare l’allagamento. A ciascuno viene data un’etichetta diversa.
2. I pixel vicini di ciascuna area contrassegnata vengono inseriti in una coda di priorità con un livello di priorità corrispondente alla grandezza del gradiente del pixel.
3. Il pixel con il livello di priorità più alto viene estratto dalla coda di priorità. Se i vicini del pixel estratto che sono già stati etichettati hanno tutti la stessa etichetta, il pixel viene etichettato con la loro etichetta. Tutti i vicini non contrassegnati che non sono ancora nella coda di priorità vengono inseriti nella coda di priorità.
4. Ripeti il passaggio 3 fino a quando la coda di priorità non è vuota.

I pixel non etichettati sono le linee spartiacque.

Esempio di trasformazione dello spartiacque supportata da marcatori per una popolazione di pellet farmaceutici. Le linee di spartiacque sono sovrapposte in nero sulla pila di immagini CT .

Algoritmi di spanning ottimale della foresta (tagli di spartiacque)Modifica

Spartiacque come foresta di spanning ottimale sono stati introdotti da Jean Cousty et al. Stabiliscono la consistenza di questi bacini idrografici: possono essere definiti in modo equivalente dai loro “bacini idrografici” (attraverso una proprietà di discesa più ripida) o dalle “linee divisorie” che separano questi bacini idrografici (attraverso il principio della goccia d’acqua). Quindi dimostrano, attraverso un teorema di equivalenza, la loro ottimalità in termini di foreste minime. In seguito, introducono un algoritmo di tempo lineare per calcolarli. Vale la pena notare che proprietà simili non sono verificate in altri framework e l’algoritmo proposto è l’algoritmo esistente più efficiente, sia in teoria che in pratica.

• Un’immagine con due marcatori (verde) e una foresta di Spanning minima calcolata sul gradiente dell’immagine.

• Risultato della segmentazione per foresta minima di Spanning