Gibt es einen Unterschied zwischen den Algorithmen zum Füllen von Depressionen mit Planchon & Darboux und Wang und Liu? Anders als Geschwindigkeit?

Kann mir jemand anhand der tatsächlichen analytischen Erfahrung sagen, ob es einen Unterschied zwischen diesen beiden Algorithmen zum Füllen von Depressionen gibt, abgesehen von der Geschwindigkeit, mit der sie Depressionen (Senken) in DEMs verarbeiten und füllen?

Ein schneller, einfacher und vielseitiger Algorithmus zum Füllen der Vertiefungen digitaler Höhenmodelle

Olivier Planchon, Frederic Darboux

und

Eine effiziente Methode zum Identifizieren und Füllen von Oberflächenvertiefungen in digitalen Höhenmodellen zur hydrologischen Analyse und Modellierung

Wang und Liu

Vielen Dank.

Aus theoretischer Sicht hat das Füllen von Depressionen nur eine Lösung, obwohl es zahlreiche Möglichkeiten gibt, zu dieser Lösung zu gelangen, weshalb es so viele verschiedene Algorithmen zum Füllen von Depressionen gibt. Daher sollte theoretisch ein DEM, das entweder mit Planchon und Darboux oder Wang und Liu oder einem der anderen Algorithmen zum Füllen von Depressionen gefüllt ist, danach identisch aussehen. Es ist jedoch wahrscheinlich, dass dies nicht der Fall ist, und es gibt einige Gründe dafür. Erstens gibt es zwar nur eine Lösung zum Füllen einer Vertiefung, aber viele verschiedene Lösungen zum Aufbringen eines Gradienten auf die flache Oberfläche der gefüllten Vertiefung. Das heißt, normalerweise möchten wir nicht nur eine Vertiefung füllen, sondern auch den Fluss über die Oberfläche der gefüllten Vertiefung erzwingen. Dies beinhaltet normalerweise das Hinzufügen sehr kleiner Gradienten und 1) es gibt viele verschiedene Strategien, um dies zu tun (von denen viele direkt in die verschiedenen Algorithmen zum Füllen von Depressionen eingebaut sind) und 2) der Umgang mit solch kleinen Zahlen führt oft zu kleinen Rundungsfehlern, die dazu führen können sich in Unterschieden zwischen gefüllten DEMs manifestieren. Schauen Sie sich dieses Bild an:

Es zeigt das 'DEM der Differenz' zwischen zwei DEMs, die beide aus dem Quell-DEM generiert wurden, aber eines mit Vertiefungen, die mit dem Planchon- und Darboux-Algorithmus gefüllt wurden, und das andere mit dem Wang- und Liu-Algorithmus. Ich sollte sagen, dass die Depressionsfüllungsalgorithmen beide Werkzeuge aus Whitebox GAT waren und daher andere Implementierungen der Algorithmen sind als die, die Sie in Ihrer obigen Antwort beschrieben haben. Beachten Sie, dass die Unterschiede in den DEMs alle weniger als 0,008 m betragen und vollständig in den Bereichen topografischer Vertiefungen enthalten sind (dh Gitterzellen, die sich nicht in Vertiefungen befinden, haben genau die gleichen Höhen wie das eingegebene DEM). Der kleine Wert von 8 mm spiegelt den winzigen Wert wider, der verwendet wird, um den Fluss auf den ebenen Flächen zu erzwingen, die durch den Füllvorgang zurückbleiben, und wird wahrscheinlich auch etwas von der Skala der Rundungsfehler beeinflusst, wenn solche kleinen Zahlen mit Gleitkommawerten dargestellt werden. Sie können die beiden gefüllten DEMs im obigen Bild nicht sehen, aber Sie können anhand ihrer Legendeneinträge erkennen, dass sie auch genau den gleichen Bereich von Höhenwerten haben, wie Sie es erwarten würden.

Warum sollten Sie in Ihrer obigen Antwort die Höhenunterschiede entlang von Gipfeln und anderen nicht depressiven Bereichen im DEM beobachten? Ich denke, es könnte wirklich nur auf die spezifische Implementierung des Algorithmus hinauslaufen. Im Tool ist wahrscheinlich etwas los, um diese Unterschiede zu berücksichtigen, und es hängt nicht mit dem tatsächlichen Algorithmus zusammen. Dies ist für mich angesichts der Lücke zwischen der Beschreibung eines Algorithmus in einer wissenschaftlichen Arbeit und seiner tatsächlichen Implementierung in Verbindung mit der Komplexität des internen Datenverarbeitungsprozesses in GIS nicht überraschend. Trotzdem danke, dass Sie diese sehr interessante Frage gestellt haben.

Prost,

John

Ich werde versuchen, meine eigene Frage zu beantworten - dun dun dun.

Ich habe SAGA GIS verwendet, um die Unterschiede in gefüllten Wassereinzugsgebieten mit ihrem auf Planchon und Darboux (PD) basierenden Füllwerkzeug (und ihrem auf Wang und Liu (WL) basierenden Füllwerkzeug für 6 verschiedene Wassereinzugsgebiete zu untersuchen. (Hier zeige ich nur zwei Ergebnissätze - Sie waren in allen 6 Wassereinzugsgebieten ähnlich. Ich sage "basiert", da immer die Frage besteht, ob Unterschiede auf den Algorithmus oder die spezifische Implementierung des Algorithmus zurückzuführen sind.

Wassereinzugsgebiets-DEMs wurden durch Abschneiden von Mosaik-NED-30-m-Daten unter Verwendung von USGS-bereitgestellten Wassereinzugsgebiets-Shapefiles erzeugt. Für jedes Basis-DEM wurden die beiden Tools ausgeführt. Für jedes Werkzeug gibt es nur eine Option, die minimale erzwungene Neigung, die in beiden Werkzeugen auf 0,01 eingestellt wurde.

Nachdem die Wassereinzugsgebiete gefüllt waren, habe ich den Rasterrechner verwendet, um die Unterschiede in den resultierenden Gittern zu bestimmen. Diese Unterschiede sollten nur auf das unterschiedliche Verhalten der beiden Algorithmen zurückzuführen sein.

Bilder, die die Unterschiede oder das Fehlen von Unterschieden darstellen (im Grunde das berechnete Differenzraster), sind unten dargestellt. Die Formel zur Berechnung der Differenzen lautete: (((PD_Filled - WL_Filled) / PD_Filled) * 100) - Geben Sie die prozentuale Differenz zellenweise an. Zellen mit grauer Farbe zeigen jetzt einen Unterschied, wobei Zellen mit roter Farbe anzeigen, dass die resultierende PD-Erhöhung größer war, und Zellen mit grünerer Farbe, was anzeigt, dass die resultierende WL-Erhöhung größer war.

1. Wasserscheide: Clear Watershed, Wyoming

Hier ist die Legende für diese Bilder:

Die Unterschiede reichen nur von -0,0915% bis + 0,0910%. Die Unterschiede scheinen sich auf Peaks und enge Stromkanäle zu konzentrieren, wobei der WL-Algorithmus in den Kanälen etwas höher und die PD in den lokalisierten Peaks etwas höher ist.

Klare Wasserscheide, Wyoming, Zoom 1

Klare Wasserscheide, Wyoming, Zoom 2

2. Wasserscheide: Winnipesaukee River, NH

Hier ist die Legende für diese Bilder:

Winnipesaukee River, NH, Zoom 1

Die Unterschiede reichen nur von -0,323% bis + 0,315%. Die Unterschiede scheinen sich auf Peaks und enge Stromkanäle zu konzentrieren, wobei (wie zuvor) der WL-Algorithmus in den Kanälen etwas höher und die PD in den lokalisierten Peaks etwas höher ist.

Sooooooo, Gedanken? Für mich scheinen die Unterschiede trivial zu sein und werden wahrscheinlich keine weiteren Berechnungen beeinflussen. stimmt jemand zu? Ich überprüfe, indem ich meinen Workflow für diese sechs Wassereinzugsgebiete abschließe.

Bearbeiten: Weitere Informationen. Es scheint, dass der WL-Algorithmus zu breiteren, weniger unterschiedlichen Kanälen führt und hohe topografische Indexwerte verursacht (mein endgültiger abgeleiteter Datensatz). Das Bild links unten ist der PD-Algorithmus, das Bild rechts ist der WL-Algorithmus.

Diese Bilder zeigen den Unterschied im topografischen Index an denselben Stellen - breitere feuchte Bereiche (mehr Kanal - röter, höherer TI) im WL-Bild rechts; schmalere Kanäle (weniger nasser Bereich - weniger roter, schmalerer roter Bereich, niedrigerer TI im Bereich) im PD-Bild links.

Außerdem erfahren Sie hier, wie PD mit einer Vertiefung umgegangen ist (links) und wie WL damit umgegangen ist (rechts).

Die noch so kleinen Unterschiede scheinen sich also durch die zusätzlichen Analysen zu ziehen.

Hier ist mein Python-Skript, wenn jemand interessiert ist:

#! /usr/bin/env python

# ----------------------------------------------------------------------
# Create Fill Algorithm Comparison
# Author: T. Taggart
# ----------------------------------------------------------------------

import os, sys, subprocess, time



# function definitions
def runCommand_logged (cmd, logstd, logerr):
    p = subprocess.call(cmd, stdout=logstd, stderr=logerr)
# ----------------------------------------------------------------------


# ----------------------------------------------------------------------
# environmental variables/paths
if (os.name == "posix"):
    os.environ["PATH"] += os.pathsep + "/usr/local/bin"
else:
    os.environ["PATH"] += os.pathsep + "C:\program files (x86)\SAGA-GIS"
# ----------------------------------------------------------------------


# ----------------------------------------------------------------------
# global variables

WORKDIR    = "D:\TomTaggart\DepressionFillingTest\Ran_DEMs"

# This directory is the toplevel directoru (i.e. DEM_8)
INPUTDIR   = "D:\TomTaggart\DepressionFillingTest\Ran_DEMs"

STDLOG     = WORKDIR + os.sep + "processing.log"
ERRLOG     = WORKDIR + os.sep + "processing.error.log"
# ----------------------------------------------------------------------


# ----------------------------------------------------------------------
# open logfiles (append in case files are already existing)
logstd = open(STDLOG, "a")
logerr = open(ERRLOG, "a")
# ----------------------------------------------------------------------


# ----------------------------------------------------------------------
# initialize
t0      = time.time()
# ----------------------------------------------------------------------


# ----------------------------------------------------------------------
# loop over files, import them and calculate TWI

# this for loops walks through and identifies all the folder, sub folders, and so on.....and all the files, in the directory
# location that is passed to it - in this case the INPUTDIR
for dirname, dirnames, filenames in os.walk(INPUTDIR):
    # print path to all subdirectories first.
    #for subdirname in dirnames:
        #print os.path.join(dirname, subdirname)

    # print path to all filenames.
    for filename in filenames:
        #print os.path.join(dirname, filename)
        filename_front, fileext = os.path.splitext(filename)
        #print filename
        if filename_front == "w001001":
        #if fileext == ".adf":


            # Resetting the working directory to the current directory
            os.chdir(dirname)

            # Outputting the working directory
            print "\n\nCurrently in Directory: " + os.getcwd()

            # Creating new Outputs directory
            os.mkdir("Outputs")

            # Checks
            #print dirname + os.sep + filename_front
            #print dirname + os.sep + "Outputs" + os.sep + ".sgrd"

            # IMPORTING Files
            # --------------------------------------------------------------
            cmd = ['saga_cmd', '-f=q', 'io_gdal', 'GDAL: Import Raster',
                   '-FILES', filename,
                   '-GRIDS', dirname + os.sep + "Outputs" + os.sep + filename_front + ".sgrd",
                   #'-SELECT', '1',
                   '-TRANSFORM',
                   '-INTERPOL', '1'
                  ]

            print "Beginning to Import Files"

            try:
                runCommand_logged(cmd, logstd, logerr)

            except Exception, e:
                logerr.write("Exception thrown while processing file: " + filename + "\n")
                logerr.write("ERROR: %s\n" % e)

            print "Finished importing Files"

            # --------------------------------------------------------------


            # Resetting the working directory to the ouputs directory
            os.chdir(dirname + os.sep + "Outputs")



            # Depression Filling - Wang & Liu
            # --------------------------------------------------------------
            cmd = ['saga_cmd', '-f=q', 'ta_preprocessor', 'Fill Sinks (Wang & Liu)',
                   '-ELEV', filename_front + ".sgrd",
                   '-FILLED',  filename_front + "_WL_filled.sgrd",  # output - NOT optional grid
                   '-FDIR', filename_front + "_WL_filled_Dir.sgrd",  # output - NOT optional grid
                   '-WSHED', filename_front + "_WL_filled_Wshed.sgrd",  # output - NOT optional grid
                   '-MINSLOPE', '0.0100000', 
                               ]

            print "Beginning Depression Filling - Wang & Liu"

            try:
                runCommand_logged(cmd, logstd, logerr)

            except Exception, e:
                logerr.write("Exception thrown while processing file: " + filename + "\n")
                logerr.write("ERROR: %s\n" % e)

            print "Done Depression Filling - Wang & Liu"


            # Depression Filling - Planchon & Darboux
            # --------------------------------------------------------------
            cmd = ['saga_cmd', '-f=q', 'ta_preprocessor', 'Fill Sinks (Planchon/Darboux, 2001)',
                   '-DEM', filename_front + ".sgrd",
                   '-RESULT',  filename_front + "_PD_filled.sgrd",  # output - NOT optional grid
                   '-MINSLOPE', '0.0100000',
                               ]

            print "Beginning Depression Filling - Planchon & Darboux"

            try:
                runCommand_logged(cmd, logstd, logerr)

            except Exception, e:
                logerr.write("Exception thrown while processing file: " + filename + "\n")
                logerr.write("ERROR: %s\n" % e)

            print "Done Depression Filling - Planchon & Darboux"

            # Raster Calculator - DIff between Planchon & Darboux and Wang & Liu
            # --------------------------------------------------------------
            cmd = ['saga_cmd', '-f=q', 'grid_calculus', 'Grid Calculator',
                   '-GRIDS', filename_front + "_PD_filled.sgrd",
                   '-XGRIDS', filename_front + "_WL_filled.sgrd",
                   '-RESULT',  filename_front + "_DepFillDiff.sgrd",      # output - NOT optional grid
                   '-FORMULA', "(((g1-h1)/g1)*100)",
                   '-NAME', 'Calculation',
                   '-FNAME',
                   '-TYPE', '8',
                               ]

            print "Depression Filling - Diff Calc"

            try:
                runCommand_logged(cmd, logstd, logerr)

            except Exception, e:
                logerr.write("Exception thrown while processing file: " + filename + "\n")
                logerr.write("ERROR: %s\n" % e)

            print "Done Depression Filling - Diff Calc"

# ----------------------------------------------------------------------


# ----------------------------------------------------------------------
# finalize
logstd.write("\n\nProcessing finished in " + str(int(time.time() - t0)) + " seconds.\n")
logstd.close
logerr.close

# ----------------------------------------------------------------------

Auf algorithmischer Ebene führen die beiden Algorithmen zu denselben Ergebnissen.

Warum könnten Sie Unterschiede bekommen?

Daten Präsentation

Wenn einer Ihrer Algorithmen float(32-Bit) und ein anderer double(64-Bit) verwendet, sollten Sie nicht erwarten, dass sie dasselbe Ergebnis liefern. In ähnlicher Weise stellen einige Implementierungen Gleitkommawerte dar, die ganzzahlige Datentypen verwenden, was ebenfalls zu Unterschieden führen kann.

Entwässerungsdurchsetzung

Beide Algorithmen erzeugen jedoch flache Bereiche, die nicht abfließen, wenn eine lokalisierte Methode zur Bestimmung der Strömungsrichtungen verwendet wird.

Planchon und Darboux begegnen diesem Problem, indem sie die Höhe des flachen Bereichs geringfügig erhöhen, um die Entwässerung zu erzwingen. Wie in Barnes et al. (2014) 's Artikel "Eine effiziente Zuordnung der Entwässerungsrichtung über ebene Flächen in digitalen Rasterhöhenmodellen" Die Hinzufügung dieses Inkrements kann tatsächlich dazu führen, dass die Entwässerung außerhalb eines flachen Bereichs unnatürlich umgeleitet wird, wenn das Inkrement zu groß ist. Eine Lösung besteht darin, z nextafter. B. die Funktion zu verwenden.

andere Gedanken

Wang und Liu (2006) sind eine Variante des Priority-Flood-Algorithmus, wie in meinem Artikel "Priority-Flood: Ein optimaler Algorithmus zum Füllen von Depressionen und zur Kennzeichnung von Wassereinzugsgebieten für digitale Höhenmodelle" beschrieben .

Priority-Flood weist Zeitkomplexitäten sowohl für Ganzzahl- als auch für Gleitkommadaten auf. In meinem Artikel habe ich festgestellt, dass das Vermeiden des Platzierens von Zellen in der Prioritätswarteschlange ein guter Weg ist, um die Leistung des Algorithmus zu steigern. Andere Autoren wie Zhou et al. (2016) und Wei et al. (2018) haben diese Idee genutzt, um die Effizienz des Algorithmus weiter zu steigern. Der Quellcode für all diese Algorithmen ist hier verfügbar .

In diesem Sinne handelt es sich bei dem Planchon and Darboux (2001) -Algorithmus um die Geschichte eines Ortes, an dem die Wissenschaft versagt hat. Während Priority-Flood bei ganzzahligen Daten in O (N) -Zeit und bei Gleitkommadaten in O (N log N) -Zeit arbeitet, arbeitet P & D in O (N ^1,5 ) -Zeit. Dies führt zu einem enormen Leistungsunterschied, der mit der Größe des DEM exponentiell zunimmt:

Bis 2001 hatten Ehlschlaeger, Vincent, Soille, Beucher, Meyer und Gratin gemeinsam fünf Artikel veröffentlicht, in denen der Priority-Flood-Algorithmus beschrieben wurde. Planchon und Darboux und ihre Gutachter haben all dies verpasst und einen Algorithmus erfunden, der um Größenordnungen langsamer war. Es ist jetzt 2018 und wir bauen immer noch bessere Algorithmen, aber P & D wird immer noch verwendet. Ich finde das unglücklich.