Wasserscheide (Bildverarbeitung)

In der Geologie ist eine Wasserscheide eine Kluft, die benachbarte Einzugsgebiete trennt.

Wasserscheide durch Überflutungbearbeiten

Die Idee wurde 1979 von S. Beucher und C. Lantuéjoul eingeführt. Die Grundidee bestand darin, in jedem regionalen Minimum des Reliefs eine Wasserquelle zu platzieren, das gesamte Relief von Quellen zu überfluten und Barrieren zu bauen, wenn sich verschiedene Wasserquellen treffen. Die daraus resultierenden Barrieren bilden durch Überschwemmungen eine Wasserscheide. Eine Reihe von Verbesserungen, zusammen Priority-Flood genannt, wurden seitdem an diesem Algorithmus vorgenommen.

Wasserscheide nach topografischer Entfernungbearbeiten

Intuitiv fließt ein Wassertropfen, der auf ein topografisches Relief fällt, zum „nächsten“ Minimum. Das „nächste“ Minimum ist das Minimum, das am Ende des steilsten Abstiegspfades liegt. In Bezug auf die Topographie tritt dies auf, wenn der Punkt im Einzugsgebiet dieses Minimums liegt. Die vorherige Definition überprüft diese Bedingung nicht.

Wasserscheide nach dem Wassertropfen-Prinzipbearbeiten

Intuitiv ist die Wasserscheide eine Trennung der regionalen Minima, von denen ein Wassertropfen zu bestimmten Minima hinabfließen kann. Eine Formalisierung dieser intuitiven Idee wurde zur Definition eines Wendepunkts eines kantengewichteten Graphen bereitgestellt.

Inter-Pixel watershedbearbeiten

S. Beucher und F. Meyer führten eine algorithmische Inter-Pixel-Implementierung der Watershed-Methode ein, wobei das folgende Verfahren verwendet wurde:

1. Beschriften Sie jedes Minimum mit einem eindeutigen Etikett. Initialisieren Sie eine Menge S mit den beschrifteten Knoten.
2. Extrahieren Sie aus S einen Knoten x mit minimaler Höhe F, dh F(x) = min{F(y)|y ∈ S}. Weisen Sie die Beschriftung von x jedem nicht beschrifteten Knoten y neben x zu und fügen Sie y in S ein.
3. Wiederholen Sie Schritt 2, bis S leer ist.

Topologisches Einzugsgebietbearbeiten

Bisherige Begriffe konzentrieren sich auf Einzugsgebiete, nicht jedoch auf die Wassertrennlinie. Die topologische Wasserscheide wurde 1997 von M. Couprie und G. Bertrand eingeführt und profitiert von der folgenden grundlegenden Eigenschaft.Eine Funktion W ist genau dann ein Wendepunkt einer Funktion F, wenn W ≤ F ist und W den Kontrast zwischen den regionalen Minima von F beibehält; wobei der Kontrast zwischen zwei regionalen Minima M1 und M2 als die minimale Höhe definiert ist, auf die man klettern muss, um von M1 nach M2 zu gelangen. Ein effizienter Algorithmus wird in dem Papier detailliert beschrieben.

Watershed-Algorithmus

Verschiedene Ansätze können verwendet werden, um das Watershed-Prinzip für die Bildsegmentierung zu verwenden.

• Lokale Minima des Gradienten des Bildes können als Marker gewählt werden, in diesem Fall wird eine Übersegmentierung erzeugt und ein zweiter Schritt beinhaltet das Zusammenführen von Regionen.
• Marker based watershed Transformation verwendet spezifische Markerpositionen, die entweder explizit vom Benutzer definiert oder automatisch mit morphologischen Operatoren oder auf andere Weise bestimmt wurden.

Meyer’s flooding algorithmbearbeiten

Einer der gebräuchlichsten Wasserscheidenalgorithmen wurde von F eingeführt. Beginnend in den frühen 1990er Jahren, obwohl eine Reihe von Verbesserungen, kollektiv Priority-Flood genannt, seitdem an diesem Algorithmus vorgenommen wurden, einschließlich Varianten, die für Datensätze geeignet sind, die aus Billionen von Pixeln bestehen.

Der Algorithmus arbeitet mit einem Graustufenbild. Bei der sukzessiven Überflutung des Grauwertreliefs werden Wassereinzugsgebiete mit angrenzenden Einzugsgebieten angelegt. Dieser Überflutungsprozess wird auf dem Gradientenbild durchgeführt, d. H. Die Becken sollten entlang der Kanten austreten. Normalerweise führt dies zu einer Übersegmentierung des Bildes, insbesondere bei verrauschtem Bildmaterial, z.B. medizinische CT-Daten. Entweder muss das Bild vorverarbeitet werden oder die Regionen müssen anschließend anhand eines Ähnlichkeitskriteriums zusammengeführt werden.

1. Eine Reihe von Markern, Pixel, wo die Überschwemmung beginnen soll, werden ausgewählt. Jeder erhält ein anderes Etikett.
2. Die benachbarten Pixel jedes markierten Bereichs werden in eine Prioritätswarteschlange mit einer Prioritätsstufe eingefügt, die der Gradientengröße des Pixels entspricht.
3. Das Pixel mit der höchsten Prioritätsstufe wird aus der Prioritätswarteschlange extrahiert. Wenn die Nachbarn des extrahierten Pixels, die bereits beschriftet wurden, alle dieselbe Beschriftung haben, wird das Pixel mit ihrer Beschriftung beschriftet. Alle nicht markierten Nachbarn, die sich noch nicht in der Prioritätswarteschlange befinden, werden in die Prioritätswarteschlange gestellt.
4. Wiederholen Sie Schritt 3, bis die Prioritätswarteschlange leer ist.

Die nicht beschrifteten Pixel sind die Wasserscheidenlinien.

Beispiel für eine markergestützte Wasserscheidenumwandlung für eine Population von pharmazeutischen Pellets. Wasserscheidenlinien werden dem CT-Bildstapel schwarz überlagert .

Optimale Spannwaldalgorithmen (watershed cuts)Edit

Wassereinzugsgebiete als optimaler Spannwald wurden von Jean Cousty et al. Sie legen die Konsistenz dieser Wassereinzugsgebiete fest: Sie können äquivalent durch ihre „Einzugsgebiete“ (durch eine steilste Abstiegseigenschaft) oder durch die „Trennlinien“ definiert werden, die diese Einzugsgebiete trennen (durch das Wassertropfenprinzip). Dann beweisen sie durch einen Äquivalenzsatz ihre Optimalität in Bezug auf minimale Spannwälder. Anschließend führen sie einen linearen Zeitalgorithmus ein, um sie zu berechnen. Es ist anzumerken, dass ähnliche Eigenschaften in anderen Frameworks nicht verifiziert werden und der vorgeschlagene Algorithmus sowohl in der Theorie als auch in der Praxis der effizienteste vorhandene Algorithmus ist.

• Ein Bild mit zwei Markierungen (grün) und einer minimalen Spannweite, die anhand des Gradienten des Bildes berechnet wird.

• Ergebnis der Segmentierung nach Minimum Spanning Forest