Existe uma diferença entre os algoritmos de preenchimento de depressão de Planchon & Darboux e Wang e Liu? Diferente de velocidade?

Alguém pode me dizer, com base na experiência analítica real, se existe uma diferença entre esses dois algoritmos de preenchimento de depressão, além da velocidade com que processam e preenchem depressões (sumidouros) nos DEMs?

Um algoritmo rápido, simples e versátil para preencher as depressões dos modelos de elevação digital

Olivier Planchon, Frederic Darboux

e

Um método eficiente para identificar e preencher depressões de superfície em modelos de elevação digital para análise e modelagem hidrológica

Wang e Liu

Obrigado.

Do ponto de vista teórico, o preenchimento da depressão tem apenas uma solução, embora possa haver inúmeras maneiras de chegar a essa solução, e é por isso que existem tantos algoritmos diferentes de preenchimento da depressão. Portanto, teoricamente, um DEM preenchido com o Planchon e Darboux ou com Wang e Liu ou qualquer outro algoritmo de preenchimento de depressão deve parecer idêntico posteriormente. É provável que eles não o façam, e existem algumas razões para isso. Primeiro, embora exista apenas uma solução para preencher uma depressão, existem muitas soluções diferentes para aplicar um gradiente na superfície plana da depressão cheia. Ou seja, geralmente não queremos apenas preencher uma depressão, mas também queremos forçar o fluxo sobre a superfície da depressão cheia. Isso geralmente envolve a adição de gradientes muito pequenos e 1) existem várias estratégias diferentes para fazer isso (muitas das quais estão embutidas nos vários algoritmos de preenchimento de depressão diretamente) e 2) lidar com números tão pequenos geralmente resulta em pequenos erros de arredondamento que podem manifestar-se em diferenças entre os DEMs preenchidos. Veja esta imagem:

Ele mostra o 'DEM da diferença' entre dois DEMs, ambos gerados a partir do DEM de origem, mas um com depressões preenchidas usando o algoritmo Planchon e Darboux e outro com o algoritmo Wang e Liu. Devo dizer que os algoritmos de preenchimento de depressão eram ferramentas do Whitebox GAT e, portanto, são implementações diferentes dos algoritmos do que o que você descreveu na sua resposta acima. Observe que as diferenças nos DEMs são todas inferiores a 0,008 me estão totalmente contidas nas áreas das depressões topográficas (ou seja, as células da grade que não estão dentro das depressões têm exatamente as mesmas elevações que o DEM de entrada). O pequeno valor de 8 mm reflete o pequeno valor usado para impor o fluxo nas superfícies planas deixadas para trás pela operação de enchimento e também é provavelmente afetado pela escala dos erros de arredondamento ao representar esses números pequenos com valores de ponto flutuante. Você não pode ver os dois DEMs preenchidos exibidos na imagem acima, mas pode-se dizer pelas entradas de legenda que eles também têm exatamente o mesmo intervalo de valores de elevação, como seria de esperar.

Então, por que você observaria as diferenças de elevação ao longo dos picos e outras áreas sem depressão no DEM em sua resposta acima? Eu acho que realmente poderia se resumir apenas à implementação específica do algoritmo. Provavelmente, algo está acontecendo dentro da ferramenta para explicar essas diferenças e isso não está relacionado ao algoritmo real. Isso não é tão surpreendente para mim, dada a diferença entre a descrição de um algoritmo em um artigo acadêmico e sua implementação real combinada com a complexidade de como os dados são tratados internamente no GIS. De qualquer forma, obrigado por fazer esta pergunta muito interessante.

Felicidades,

John

Tentarei responder minha própria pergunta - dun dun dun.

Usei o SAGA GIS para examinar as diferenças em bacias hidrográficas cheias, usando a ferramenta de preenchimento baseada em Planchon e Darboux (PD) (e a ferramenta de preenchimento baseada em Wang e Liu (WL) para 6 bacias hidrográficas diferentes. (Aqui, apenas mostro dois conjuntos de resultados - foram semelhantes em todas as 6 bacias hidrográficas) digo "com base", porque sempre há a questão de saber se as diferenças são devidas ao algoritmo ou à implementação específica do algoritmo.

Os DEMs das bacias hidrográficas foram gerados por recorte de dados de NED de 30 m em mosaico, usando USGS, fornecendo arquivos de formas da bacia hidrográfica. Para cada DEM base, as duas ferramentas foram executadas; há apenas uma opção para cada ferramenta, a inclinação mínima aplicada, que foi definida nas duas ferramentas como 0,01.

Depois que as bacias hidrográficas foram preenchidas, usei a calculadora raster para determinar as diferenças nas grades resultantes - essas diferenças só devem-se aos diferentes comportamentos dos dois algoritmos.

Imagens representando as diferenças ou a falta de diferenças (basicamente a varredura da diferença calculada) são apresentadas abaixo. A fórmula usada no cálculo das diferenças foi: (((PD_Filled - WL_Filled) / PD_Filled) * 100) - forneça a diferença percentual célula por célula. As células de cor cinza mostram agora a diferença, com as células de cor mais avermelhada indicando que a elevação de PD resultante foi maior e as células de cor mais verde indicando que a elevação de WL resultante foi maior.

1ª Bacia Hidrográfica: Clear Watershed, Wyoming

Aqui está a legenda para estas imagens:

As diferenças variam apenas de -0,0915% a + 0,0910%. As diferenças parecem estar focadas em picos e canais de fluxo estreitos, com o algoritmo WL um pouco mais alto nos canais e PD um pouco mais alto em torno dos picos localizados.

Clear Watershed, Wyoming, Zoom 1

Bacias Climáticas, Wyoming, Zoom 2

2nd Watershed: Rio Winnipesaukee, NH

Aqui está a legenda para estas imagens:

Winnipesaukee River, NH, Zoom 1

As diferenças variam apenas de -0,323% a + 0,315%. As diferenças parecem estar focadas em picos e canais de fluxo estreitos, com (como antes) o algoritmo WL um pouco mais alto nos canais e PD um pouco mais alto em torno dos picos localizados.

Tãããããão, pensamentos? Para mim, as diferenças parecem triviais provavelmente não afetam cálculos adicionais; alguém concorda? Estou verificando concluindo meu fluxo de trabalho para essas seis bacias hidrográficas.

Editar: Mais informações. Parece que o algoritmo WL leva a canais mais amplos e menos distintos, causando altos valores de índice topográfico (meu conjunto de dados derivado final). A imagem à esquerda abaixo é o algoritmo PD, a imagem à direita é o algoritmo WL.

Essas imagens mostram a diferença no índice topográfico nos mesmos locais - áreas mais úmidas (mais canal - mais vermelho, maior TI) na foto WL à direita; canais mais estreitos (menos área úmida - menos vermelho, área vermelha mais estreita, menor área de TI) na foto do PD à esquerda.

Além disso, aqui está como o PD lidou com (à esquerda) uma depressão e como o WL tratou (à direita) - observe o segmento / linha laranja aumentada (índice topográfico inferior) cruzando a depressão na saída preenchida pelo WL?

Portanto, as diferenças, por menores que sejam, parecem passar pelas análises adicionais.

Aqui está o meu script Python, se alguém estiver interessado:

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

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

No nível algorítmico, os dois algoritmos produzirão os mesmos resultados.

Por que você pode estar recebendo diferenças?

Representação de dados

Se um dos seus algoritmos usa float(32 bits) e outro usa double(64 bits), você não deve esperar que eles produzam o mesmo resultado. Da mesma forma, algumas implementações representam valores de ponto flutuante, usam tipos de dados inteiros, o que também pode resultar em diferenças.

Aplicação de Drenagem

No entanto, ambos os algoritmos produzirão áreas planas que não serão drenadas se um método localizado for usado para determinar as direções do fluxo.

Planchon e Darboux tratam disso adicionando um pequeno incremento à altura da área plana para reforçar a drenagem. Como discutido em Barnes et al. (2014) paper "Uma atribuição eficiente de direção de drenagem sobre superfícies planas em modelos de elevação digital raster", a adição desse incremento pode realmente fazer com que a drenagem fora de uma área plana seja reencaminhada de forma não natural se o incremento for muito grande. Uma solução é usar, por exemplo, a nextafterfunção.

outros pensamentos

Wang e Liu (2006) são uma variante do algoritmo Priority-Flood, como discutido no meu artigo "Priority-flood: Um ótimo algoritmo de preenchimento de depressão e de marcação de bacias hidrográficas para modelos de elevação digital" .

O Priority-Flood possui complexidades de tempo para dados inteiros e de ponto flutuante. No meu artigo, observei que evitar colocar células na fila de prioridade era uma boa maneira de aumentar o desempenho do algoritmo. Outros autores como Zhou et al. (2016) e Wei et al. (2018) usaram essa ideia para aumentar ainda mais a eficiência do algoritmo. O código fonte de todos esses algoritmos está disponível aqui .

Com isso em mente, o algoritmo de Planchon e Darboux (2001) é uma história de um local onde a ciência falhou. Enquanto o Priority-Flood trabalha em tempo O (N) em dados inteiros e tempo O (N log N) em dados de ponto flutuante, P&D trabalha em tempo O (N ^1,5 ). Isso se traduz em uma enorme diferença de desempenho que cresce exponencialmente com o tamanho do DEM:

Em 2001, Ehlschlaeger, Vincent, Soille, Beucher, Meyer e Gratin publicaram coletivamente cinco artigos detalhando o algoritmo Priority-Flood. Planchon e Darboux, e seus revisores, perderam tudo isso e inventaram um algoritmo que era de ordem de magnitude mais lenta. Agora é 2018 e ainda estamos construindo algoritmos melhores, mas o P&D ainda está sendo usado. Eu acho isso lamentável.