Есть ли разница между алгоритмами заполнения депрессии Планшона и Дарбу, Вана и Лю? Кроме скорости?

Может ли кто-нибудь сказать мне, основываясь на фактическом аналитическом опыте, есть ли разница между этими двумя алгоритмами заполнения депрессии, кроме скорости, с которой они обрабатывают и заполняют депрессии (стоки) в ЦМР?

Быстрый, простой и универсальный алгоритм для заполнения депрессий цифровых моделей рельефа

Оливье Планшон, Фредерик Дарбу

и

Эффективный метод идентификации и заполнения углублений поверхности в цифровых моделях рельефа для гидрологического анализа и моделирования

Ван и Лю

Спасибо.

С теоретической точки зрения заполнение депрессии имеет только одно решение, хотя может быть множество способов прийти к этому решению, поэтому существует так много разных алгоритмов заполнения депрессии. Следовательно, теоретически ЦМР, которая заполнена либо Планшоном и Дарбу, либо Ваном и Лю, либо любым другим алгоритмом заполнения депрессии, впоследствии должна выглядеть идентично. Вполне вероятно, что они не будут, однако есть несколько причин, почему. Во-первых, хотя существует только одно решение для заполнения впадины, существует множество различных решений для применения градиента на плоской поверхности заполненной впадины. То есть обычно мы не просто хотим заполнить депрессию, но мы также хотим заставить поток течь по поверхности заполненной депрессии. Обычно это включает в себя добавление очень маленьких градиентов и 1) существует множество различных стратегий для этого (многие из которых напрямую встроены в различные алгоритмы заполнения депрессии) и 2) работа с такими небольшими числами часто приводит к небольшим ошибкам округления, которые могут проявляться в различиях между заполненными ЦМР. Посмотрите на это изображение:

Он показывает «разность высот» между двумя матрицами высот, обе сгенерированы из исходной матрицы высот, но одна с депрессиями, заполненными с использованием алгоритма Планшона и Дарбу, а другая с алгоритмом Ван и Лю. Я должен сказать, что оба алгоритма заполнения депрессии были инструментами из Whitebox GAT и, следовательно, являются реализациями алгоритмов, отличными от того, что вы описали в своем ответе выше. Обратите внимание, что все различия в ЦМР меньше 0,008 м и что они полностью содержатся в областях топографических депрессий (т. Е. Ячейки сетки, которые не находятся в пределах депрессий, имеют точно такие же отметки, что и входная ЦМР). Небольшое значение 8 мм отражает крошечное значение, используемое для обеспечения потока на плоских поверхностях, оставленных после операции заполнения, и, вероятно, также несколько зависит от масштаба ошибок округления при представлении таких небольших чисел значениями с плавающей запятой. Вы не можете видеть две заполненные матрицы высот, показанные на рисунке выше, но вы можете сказать из их записей легенды, что они также имеют точно такой же диапазон значений высот, как и следовало ожидать.

Итак, почему вы наблюдаете разницу высот вдоль пиков и других областей без депрессии в ЦМР в своем ответе выше? Я думаю, что это может действительно сводиться только к конкретной реализации алгоритма. Вероятно, что-то происходит внутри инструмента, чтобы учесть эти различия, и это не связано с фактическим алгоритмом. Это не удивительно для меня, учитывая разрыв между описанием алгоритма в академической статье и его фактической реализацией в сочетании со сложностью того, как данные обрабатываются внутри ГИС. В любом случае, спасибо, что задали этот очень интересный вопрос.

Ура,

Джон

Я попытаюсь ответить на свой вопрос - Дун Дун Дун.

Я использовал SAGA GIS для изучения различий в заполненных водоразделах, используя их инструмент заполнения на основе Планшона и Дарбу (PD) (и их инструмент заполнения на основе Ван и Лю (WL) для 6 различных водосборов. (Здесь я показываю только два набора результатов). они были одинаковы для всех 6 водоразделов) Я говорю «на основе», потому что всегда возникает вопрос, связаны ли различия с алгоритмом или с конкретной реализацией алгоритма.

ЦМР для водораздела были получены путем вырезания мозаичных данных НЭД на 30 м с использованием предоставленных Геологической службой шейп-файлов водораздела. Для каждой базовой матрицы высот были запущены два инструмента; для каждого инструмента есть только одна опция - минимальный вынужденный уклон, который был установлен в обоих инструментах на 0,01.

После того, как водоразделы были заполнены, я использовал калькулятор растра, чтобы определить различия в результирующих сетках - эти различия должны быть связаны только с разным поведением двух алгоритмов.

Изображения, представляющие различия или отсутствие различий (в основном расчетный растр различий), представлены ниже. Формула, используемая для расчета различий, была: (((PD_Filled - WL_Filled) / PD_Filled) * 100) - укажите разницу в процентах для каждой ячейки. Клетки, окрашенные в серый цвет, теперь демонстрируют разницу, причем клетки имеют красный цвет, что указывает на то, что результирующее повышение PD, было больше, а клетки, имеющие зеленый цвет, указывают на то, что результирующее повышение WL было больше.

1-й Водораздел: Чистый Водораздел, Вайоминг

Вот легенда для этих изображений:

Разница только в диапазоне от -0,0915% до + 0,0910%. Различия, по-видимому, сосредоточены вокруг пиков и узких потоковых каналов, при этом алгоритм WL немного выше в каналах, а PD немного выше вокруг локализованных пиков.

Ясный Водораздел, Вайоминг, Zoom 1

Ясный Водораздел, Вайоминг, Zoom 2

2-й водораздел: Река Виннипсауки, Северная Каролина

Вот легенда для этих изображений:

Winnipesaukee River, NH, Zoom 1

Разница только в диапазоне от -0,323% до + 0,315%. Различия, по-видимому, сосредоточены вокруг пиков и узких потоковых каналов, при этом (как и раньше) алгоритм WL немного выше в каналах, а PD немного выше вокруг локализованных пиков.

Ооооооо, мысли? На мой взгляд, различия кажутся тривиальными, вероятно, не повлияет на дальнейшие вычисления; кто-нибудь согласен? Я проверяю, завершая мой рабочий процесс для этих шести водоразделов.

Изменить: дополнительная информация. Кажется, что алгоритм WL приводит к более широким менее четким каналам, вызывая высокие значения топографического индекса (мой окончательный набор производных данных). Изображение слева ниже - алгоритм PD, изображение справа - алгоритм WL.

Эти изображения показывают разницу в топографическом индексе в тех же местах - более широкие более влажные области (больше каналов - более красный, более высокий TI) на рисунке WL справа; более узкие каналы (менее влажная зона - менее красная, более узкая красная область, более низкая область TI) на рисунке PD слева.

Кроме того, вот как PD обрабатывал (слева) депрессию и как WL обрабатывал ее (справа) - обратите внимание на поднятый оранжевый (нижний топографический индекс) отрезок / линию, проходящий через депрессию в заполненном WL выходе?

Таким образом, различия, какими бы небольшими они ни были, похоже, просачиваются через дополнительный анализ.

Вот мой скрипт на Python, если кому-то интересно:

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

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

На алгоритмическом уровне оба алгоритма будут давать одинаковые результаты.

Почему вы можете получать различия?

Представление данных

Если один из ваших алгоритмов использует float(32-битный), а другой - double(64-битный), вы не должны ожидать, что они приведут к одинаковому результату. Аналогично, некоторые реализации представляют значения с плавающей запятой, используют целочисленные типы данных, что также может привести к различиям.

Дренажное принуждение

Однако оба алгоритма будут создавать плоские области, которые не будут сливаться, если для определения направлений потока используется локализованный метод.

Планшон и Дарбу решают эту проблему путем добавления небольшого приращения к высоте плоской области, чтобы обеспечить дренаж. Как обсуждалось в Barnes et al. (2014) в статье «Эффективное назначение направления дренажа над плоскими поверхностями в растровых цифровых моделях рельефа» добавление этого приращения может фактически привести к неестественному перенаправлению дренажа за пределы плоской области, если приращение слишком большое. Решение состоит в том, чтобы использование, например, в nextafterфункции.

другие мысли

Wang and Liu (2006) - это вариант алгоритма Priority-Flood, о котором говорилось в моей статье «Priority-flood: оптимальный алгоритм заполнения впадин и маркировки водоразделов для цифровых моделей рельефа» .

Приоритетный поток имеет временную сложность как для целых, так и для данных с плавающей точкой. В своей статье я отметил, что избегание размещения ячеек в очереди с приоритетами - хороший способ повысить производительность алгоритма. Другие авторы, такие как Zhou et al. (2016) и Wei et al. (2018) использовали эту идею для дальнейшего повышения эффективности алгоритма. Исходный код для всех этих алгоритмов доступен здесь .

Имея это в виду, алгоритм Планшона и Дарбу (2001) - это история места, где наука потерпела неудачу. Хотя Priority-Flood работает за O (N) время для целочисленных данных и O (N log N) для данных с плавающей запятой, P & D работает за O (N ^1.5 ) время. Это приводит к огромной разнице в производительности, которая растет в геометрической прогрессии с размером матрицы высот:

К 2001 году Ehlschlaeger, Vincent, Soille, Beucher, Meyer и Gratin совместно опубликовали пять работ, подробно описывающих алгоритм Приоритетного Потопа. Планшон и Дарбу и их рецензенты пропустили все это и изобрели алгоритм, который был на несколько порядков медленнее. Сейчас 2018 год, и мы все еще строим лучшие алгоритмы, но P & D все еще используется. Я думаю, что это неудачно.