Existe-t-il une différence entre les algorithmes de remplissage de dépression Planchon & Darboux et Wang et Liu? Autre que la vitesse?

Quelqu'un peut-il me dire, sur la base d'une expérience analytique réelle, s'il existe une différence entre ces deux algorithmes de remplissage de dépression, autre que la vitesse à laquelle ils traitent et remplissent les dépressions (puits) en DEM?

Un algorithme rapide, simple et polyvalent pour combler les dépressions des modèles d'élévation numériques

Olivier Planchon, Frédéric Darboux

et

Une méthode efficace pour identifier et combler les dépressions de surface dans les modèles d'élévation numériques pour l'analyse et la modélisation hydrologiques

Wang et Liu

Merci.

D'un point de vue théorique, le remplissage de dépression n'a qu'une seule solution, bien qu'il puisse y avoir de nombreuses façons d'arriver à cette solution, c'est pourquoi il existe tant d'algorithmes de remplissage de dépression différents. Par conséquent, théoriquement, un DEM qui est rempli soit de Planchon et Darboux, soit de Wang et Liu, ou de l'un des autres algorithmes de remplissage de dépression, devrait par la suite être identique. Il est probable qu'ils ne le feront pas cependant et il y a plusieurs raisons. Tout d'abord, bien qu'il n'y ait qu'une seule solution pour combler une dépression, il existe de nombreuses solutions différentes pour appliquer un gradient sur la surface plate de la dépression remplie. Autrement dit, en général, nous ne voulons pas seulement remplir une dépression, mais nous voulons également forcer l'écoulement sur la surface de la dépression remplie. Cela implique généralement l'ajout de très petits gradients et 1) il existe de nombreuses stratégies différentes pour ce faire (dont beaucoup sont intégrées directement dans les divers algorithmes de remplissage de dépression) et 2) le traitement de ces petits nombres entraînera souvent de petites erreurs d'arrondi qui peuvent se manifester par des différences entre les DEM remplis. Jetez un oeil à cette image:

Il montre le «DEM de différence» entre deux DEM, tous deux générés à partir du DEM source mais l'un avec des dépressions remplies à l'aide de l'algorithme Planchon et Darboux et l'autre avec l'algorithme Wang et Liu. Je dois dire que les algorithmes de remplissage de dépression étaient tous deux des outils de Whitebox GAT et sont donc des implémentations différentes des algorithmes que ce que vous avez décrit dans votre réponse ci-dessus. Notez que les différences dans les DEM sont toutes inférieures à 0,008 m et qu'elles sont entièrement contenues dans les zones de dépressions topographiques (c'est-à-dire que les cellules de grille qui ne sont pas dans les dépressions ont exactement les mêmes élévations que le DEM d'entrée). La petite valeur de 8 mm reflète la petite valeur utilisée pour imposer l'écoulement sur les surfaces planes laissées par l'opération de remplissage et est également probablement quelque peu affectée par l'échelle des erreurs d'arrondi lors de la représentation de si petits nombres avec des valeurs à virgule flottante. Vous ne pouvez pas voir les deux DEM remplis affichés dans l'image ci-dessus, mais vous pouvez dire à partir de leurs entrées de légende qu'ils ont également exactement la même plage de valeurs d'élévation, comme vous vous y attendez.

Alors, pourquoi observeriez-vous les différences d'altitude le long des pics et d'autres zones non dépressives dans le DEM dans votre réponse ci-dessus? Je pense que cela ne peut vraiment se résumer qu'à l'implémentation spécifique de l'algorithme. Il y a probablement quelque chose à l'intérieur de l'outil pour expliquer ces différences et cela n'est pas lié à l'algorithme réel. Ce n'est pas si surprenant pour moi étant donné l'écart entre la description d'un algorithme dans un article académique et sa mise en œuvre réelle combinée à la complexité de la façon dont les données sont traitées en interne dans le SIG. Quoi qu'il en soit, merci d'avoir posé cette question très intéressante.

À votre santé,

John

Je vais essayer de répondre à ma propre question - dun dun dun.

J'ai utilisé SAGA GIS pour examiner les différences entre les bassins versants remplis en utilisant leur outil de remplissage basé sur Planchon et Darboux (PD) (et leur outil de remplissage basé sur Wang et Liu (WL) pour 6 bassins versants différents. (Ici, je ne montre que deux séries de résultats - ils étaient similaires dans les 6 bassins versants), je dis «basé», car il y a toujours la question de savoir si les différences sont dues à l'algorithme ou à la mise en œuvre spécifique de l'algorithme.

Les MNT des bassins versants ont été générés en découpant les données NED mosaïques de 30 m à l'aide des fichiers de formes des bassins versants fournis par l'USGS. Pour chaque DEM de base, les deux outils ont été exécutés; il n'y a qu'une seule option pour chaque outil, la pente forcée minimale, qui a été définie dans les deux outils à 0,01.

Une fois les bassins versants remplis, j'ai utilisé la calculatrice raster pour déterminer les différences dans les grilles résultantes - ces différences ne devraient être dues qu'aux comportements différents des deux algorithmes.

Des images représentant les différences ou l'absence de différences (essentiellement le raster de différence calculé) sont présentées ci-dessous. La formule utilisée pour calculer les différences était la suivante: (((PD_Filled - WL_Filled) / PD_Filled) * 100) - donne le pourcentage de différence cellule par cellule. Les cellules de couleur grise montrent maintenant une différence, avec des cellules de couleur plus rouge indiquant que l'élévation PD résultante était plus grande, et des cellules de couleur plus verte indiquant l'élévation WL résultante était plus grande.

1er bassin versant: bassin versant clair, Wyoming

Voici la légende de ces images:

Les différences ne varient que de -0,0915% à + 0,0910%. Les différences semblent se concentrer autour des pics et des canaux de flux étroits, avec l'algorithme WL légèrement plus élevé dans les canaux et PD légèrement plus élevé autour des pics localisés.

Bassin versant clair, Wyoming, Zoom 1

Bassin versant clair, Wyoming, Zoom 2

2e bassin versant: rivière Winnipesaukee, NH

Voici la légende de ces images:

Rivière Winnipesaukee, NH, Zoom 1

Les différences ne varient que de -0,323% à + 0,315%. Les différences semblent se concentrer autour des pics et des canaux de flux étroits, avec (comme précédemment) l'algorithme WL légèrement plus élevé dans les canaux et PD légèrement plus élevé autour des pics localisés.

Sooooooo, des pensées? Pour moi, les différences semblent minimes ne sont probablement pas susceptibles d'affecter d'autres calculs; quelqu'un est d'accord? Je vérifie en complétant mon flux de travail pour ces six bassins versants.

Modifier: Plus d'informations. Il semble que l'algorithme WL mène à des canaux moins distincts et plus larges, provoquant des valeurs d'index topographiques élevées (mon jeu de données dérivé final). L'image de gauche ci-dessous est l'algorithme PD, l'image de droite est l'algorithme WL.

Ces images montrent la différence d'index topographique aux mêmes endroits - des zones plus humides et plus larges (plus de canal - plus rouge, TI plus élevé) dans le pic WL à droite; canaux plus étroits (zone moins humide - moins rouge, zone rouge plus étroite, TI inférieur dans la zone) dans la photo PD à gauche.

De plus, voici comment PD a géré (à gauche) une dépression et comment WL l'a gérée (à droite) - remarquez le segment / ligne orange surélevé (indice topographique inférieur) traversant la dépression dans la sortie remplie de WL?

Par conséquent, les différences, si minimes soient-elles, semblent se répercuter sur les analyses supplémentaires.

Voici mon script Python si quelqu'un est intéressé:

#! /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

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

Au niveau algorithmique, les deux algorithmes produiront les mêmes résultats.

Pourquoi pourriez-vous avoir des différences?

Représentation des données

Si l'un de vos algorithmes utilise float(32 bits) et un autre double(64 bits), vous ne devez pas vous attendre à ce qu'ils produisent le même résultat. De même, certaines implémentations représentent des valeurs à virgule flottante utilisant des types de données entiers, ce qui peut également entraîner des différences.

Application du drainage

Cependant, les deux algorithmes produiront des zones planes qui ne s'écouleront pas si une méthode localisée est utilisée pour déterminer les directions d'écoulement.

Planchon et Darboux résolvent ce problème en ajoutant un petit incrément à la hauteur de la zone plate pour imposer le drainage. Comme discuté dans Barnes et al. (2014), article "Une affectation efficace de la direction du drainage sur des surfaces planes dans les modèles d'élévation numériques raster", l'ajout de cet incrément peut en fait provoquer un reroutage anormal du drainage en dehors d'une zone plane si l'incrément est trop grand. Une solution consiste à utiliser, par exemple, la nextafterfonction.

d'autres pensées

Wang et Liu (2006) est une variante de l'algorithme Priority-Flood, comme discuté dans mon article "Priority-flood: Un algorithme optimal de remplissage de dépression et d'étiquetage des bassins versants pour les modèles numériques d'élévation" .

Priority-Flood présente des complexités temporelles pour les données entières et à virgule flottante. Dans mon article, j'ai noté qu'éviter de placer des cellules dans la file d'attente prioritaire était un bon moyen d'augmenter les performances de l'algorithme. D'autres auteurs tels que Zhou et al. (2016) et Wei et al. (2018) ont utilisé cette idée pour augmenter encore l'efficacité de l'algorithme. Le code source de tous ces algorithmes est disponible ici .

Dans cette optique, l'algorithme de Planchon et Darboux (2001) est l'histoire d'un lieu où la science a échoué. Alors que Priority-Flood fonctionne en temps O (N) sur les données entières et en temps O (N log N) sur les données à virgule flottante, P&D fonctionne en temps O (N ^1.5 ). Cela se traduit par une énorme différence de performances qui augmente de façon exponentielle avec la taille du DEM:

En 2001, Ehlschlaeger, Vincent, Soille, Beucher, Meyer et Gratin avaient collectivement publié cinq articles détaillant l'algorithme Priority-Flood. Planchon et Darboux, et leurs critiques, ont raté tout cela et ont inventé un algorithme qui était plus lent de plusieurs ordres de grandeur. Nous sommes maintenant en 2018 et nous construisons toujours de meilleurs algorithmes, mais P&D est toujours utilisé. Je pense que c'est malheureux.