Apakah ada perbedaan antara algoritma pengisian Planchon & Darboux dan Wang dan Liu? Selain kecepatan?

Adakah yang bisa memberi tahu saya, berdasarkan pengalaman analitis yang sebenarnya, jika ada perbedaan antara kedua algoritma pengisian depresi ini, selain dari kecepatan mereka memproses dan mengisi depresi (tenggelam) dalam DEM?

Algoritma yang cepat, sederhana dan serbaguna untuk mengisi depresi model elevasi digital

Olivier Planchon, Frederic Darboux

dan

Metode yang efisien untuk mengidentifikasi dan mengisi depresi permukaan dalam model elevasi digital untuk analisis dan pemodelan hidrologi

Wang dan Liu

Terima kasih.

Dari sudut pandang teoretis, pengisian depresi hanya memiliki satu solusi, meskipun ada banyak cara untuk mencapai solusi itu, itulah sebabnya mengapa ada begitu banyak algoritma pengisian depresi yang berbeda. Oleh karena itu, secara teoritis DEM yang diisi dengan Planchon dan Darboux atau Wang dan Liu, atau algoritma pengisian depresi lainnya, harus terlihat sama setelahnya. Kemungkinan mereka tidak akan melakukannya dan ada beberapa alasan mengapa. Pertama, sementara hanya ada satu solusi untuk mengisi depresi, ada banyak solusi berbeda untuk menerapkan gradien pada permukaan datar dari depresi yang terisi. Artinya, biasanya kita tidak hanya ingin mengisi depresi, tetapi kita juga ingin memaksa mengalir ke permukaan depresi yang terisi. Itu biasanya melibatkan penambahan gradien yang sangat kecil dan 1) ada banyak strategi berbeda untuk melakukan ini (banyak di antaranya dibangun ke dalam berbagai algoritma pengisian depresi secara langsung) dan 2) berurusan dengan angka kecil seperti itu akan sering menghasilkan kesalahan pembulatan kecil yang dapat dimanifestasikan dalam perbedaan di antara DEM yang terisi. Lihatlah gambar ini:

Ini menunjukkan 'DEM perbedaan' antara dua DEM, keduanya dihasilkan dari sumber DEM tetapi satu dengan depresi diisi menggunakan algoritma Planchon dan Darboux dan yang lainnya dengan algoritma Wang dan Liu. Saya harus mengatakan bahwa algoritma pengisian depresi adalah alat dari dalam Whitebox GAT dan karena itu implementasi yang berbeda dari algoritma dari apa yang Anda jelaskan dalam jawaban Anda di atas. Perhatikan bahwa perbedaan dalam DEMs semuanya kurang dari 0,008 m dan bahwa mereka sepenuhnya terkandung dalam area depresi topografi (yaitu sel-sel grid yang tidak berada dalam depresi memiliki ketinggian yang persis sama dengan ketinggian DEM input). Nilai kecil 8 mm mencerminkan nilai kecil yang digunakan untuk menegakkan aliran pada permukaan datar yang ditinggalkan oleh operasi pengisian dan juga agak mungkin dipengaruhi oleh skala kesalahan pembulatan saat mewakili angka kecil tersebut dengan nilai floating point. Anda tidak dapat melihat dua DEM terisi yang ditampilkan pada gambar di atas, tetapi Anda dapat mengetahui dari entri legenda mereka bahwa mereka juga memiliki kisaran nilai ketinggian yang sama persis, seperti yang Anda harapkan.

Jadi, mengapa Anda mengamati perbedaan ketinggian di sepanjang puncak dan area non-depresi lainnya dalam DEM dalam jawaban Anda di atas? Saya pikir itu bisa benar-benar hanya sampai pada implementasi spesifik dari algoritma. Kemungkinan ada sesuatu yang terjadi di dalam alat untuk menjelaskan perbedaan itu dan itu tidak terkait dengan algoritma yang sebenarnya. Ini tidak mengherankan bagi saya mengingat kesenjangan antara deskripsi algoritma dalam makalah akademik dan implementasi aktual dikombinasikan dengan kompleksitas bagaimana data ditangani secara internal dalam GIS. Bagaimanapun, terima kasih telah mengajukan pertanyaan yang sangat menarik ini.

Bersulang,

John

Saya akan mencoba menjawab pertanyaan saya sendiri - dun dun dun.

Saya menggunakan SAGA GIS untuk menguji perbedaan dalam DAS terisi menggunakan alat pengisi berbasis Planchon dan Darboux (PD) mereka (dan alat pengisi berbasis Wang dan Liu (WL) untuk 6 DAS yang berbeda. (Di sini saya hanya menunjukkan kasus dua set hasil - mereka serupa di semua 6 DAS) saya katakan "berdasarkan", karena selalu ada pertanyaan apakah perbedaan disebabkan oleh algoritma atau implementasi spesifik dari algoritma.

DEM DAS dihasilkan dengan memotong data mosaisis NED 30 m menggunakan USGS yang disediakan shapefile DAS. Untuk setiap basis DEM, kedua alat itu dijalankan; hanya ada satu opsi untuk setiap alat, kemiringan minimum yang ditetapkan, yang ditetapkan di kedua alat menjadi 0,01.

Setelah daerah aliran sungai terisi, saya menggunakan kalkulator raster untuk menentukan perbedaan dalam kisi-kisi yang dihasilkan - perbedaan ini seharusnya hanya disebabkan oleh perilaku yang berbeda dari kedua algoritma.

Gambar yang mewakili perbedaan atau kurangnya perbedaan (pada dasarnya raster perbedaan yang dihitung) disajikan di bawah ini. Rumus yang digunakan dalam menghitung perbedaan adalah: (((PD_Filled - WL_Filled) / PD_Filled) * 100) - memberikan persentase perbedaan pada basis sel per sel. Sel-sel berwarna abu-abu menunjukkan perbedaan sekarang, dengan sel-sel yang lebih merah dalam warna menunjukkan peningkatan PD yang dihasilkan lebih besar, dan sel-sel yang lebih hijau dalam warna yang menunjukkan peningkatan WL yang dihasilkan lebih besar.

1st Watershed: Clear Watershed, Wyoming

Inilah legenda untuk gambar-gambar ini:

Perbedaan hanya berkisar dari -0,0915% hingga + 0,0910%. Perbedaan tampaknya difokuskan di sekitar puncak dan saluran aliran sempit, dengan algoritma WL sedikit lebih tinggi di saluran dan PD sedikit lebih tinggi di sekitar puncak terlokalisasi.

Clear Watershed, Wyoming, Zoom 1

Clear Watershed, Wyoming, Zoom 2

2nd Watershed: Winnipesaukee River, NH

Inilah legenda untuk gambar-gambar ini:

Sungai Winnipesaukee, NH, Zoom 1

Perbedaan hanya berkisar antara -0,333% hingga + 0,315%. Perbedaan tampaknya difokuskan di sekitar puncak dan saluran aliran sempit, dengan (seperti sebelumnya) algoritma WL sedikit lebih tinggi di saluran dan PD sedikit lebih tinggi di sekitar puncak terlokalisasi.

Sooooooo, pikiran? Bagi saya, perbedaan yang tampak sepele mungkin tidak akan memengaruhi perhitungan lebih lanjut; Adakah yang setuju? Saya memeriksa dengan menyelesaikan alur kerja saya untuk enam daerah aliran sungai ini.

Edit: Informasi lebih lanjut. Tampaknya algoritma WL mengarah ke saluran yang lebih sedikit berbeda, menyebabkan nilai indeks topografi yang tinggi (set data turunan akhir saya). Gambar di sebelah kiri di bawah ini adalah algoritma PD, gambar di sebelah kanan adalah algoritma WL.

Gambar-gambar ini menunjukkan perbedaan dalam indeks topografi di lokasi yang sama - daerah basah yang lebih luas (lebih banyak saluran - lebih merah, TI lebih tinggi) dalam gambar WL di sebelah kanan; saluran yang lebih sempit (lebih sedikit area basah - lebih sedikit merah, area merah lebih sempit, area TI bawah) di gambar PD di sebelah kiri.

Selain itu, di sini adalah bagaimana PD menangani (kiri) depresi dan bagaimana WL menanganinya (kanan) - perhatikan segmen oranye (indeks Topografi yang lebih rendah) yang melintasi lintas depresi pada output yang diisi WL?

Jadi perbedaannya, betapapun kecilnya, tampaknya mengalir melalui analisis tambahan.

Ini adalah skrip Python saya jika ada yang tertarik:

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

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

Pada level algoritmik, kedua algoritma tersebut akan menghasilkan hasil yang sama.

Mengapa Anda mungkin mendapat perbedaan?

Representasi data

Jika salah satu algoritme Anda menggunakan float(32-bit) dan yang lain menggunakan double(64-bit), Anda seharusnya tidak mengharapkan mereka untuk menghasilkan hasil yang sama. Demikian pula, beberapa implementasi mewakili nilai floating-point menggunakan tipe data integer, yang juga dapat menyebabkan perbedaan.

Penegakan Drainase

Namun, kedua algoritma akan menghasilkan area datar yang tidak akan mengalir jika metode lokal digunakan untuk menentukan arah aliran.

Planchon dan Darboux mengatasi ini dengan menambahkan sedikit kenaikan pada ketinggian bidang datar untuk menegakkan drainase. Seperti yang dibahas dalam Barnes et al. (2014) kertas "Sebuah penugasan yang efisien dari arah drainase di atas permukaan datar dalam model elevasi digital raster" penambahan penambahan ini sebenarnya dapat menyebabkan drainase di luar area datar untuk dialihkan secara tidak wajar jika kenaikannya terlalu besar. Solusi adalah menggunakan, misalnya, nextafterfungsi.

Pikiran Lainnya

Wang dan Liu (2006) adalah varian dari algoritma Priority-Flood, seperti yang dibahas dalam makalah saya "Priority-flood: Algoritma penambalan depresi dan penandaan DAS yang optimal untuk model elevasi digital" .

Priority-Flood memiliki kompleksitas waktu untuk data integer dan floating-point. Dalam makalah saya, saya mencatat bahwa menghindari menempatkan sel dalam antrian prioritas adalah cara yang baik untuk meningkatkan kinerja algoritma. Penulis lain seperti Zhou et al. (2016) dan Wei et al. (2018) telah menggunakan ide ini untuk lebih meningkatkan efisiensi algoritma. Kode sumber untuk semua algoritma ini tersedia di sini .

Dengan pemikiran ini, algoritma Planchon dan Darboux (2001) adalah kisah tentang tempat di mana sains gagal. Sementara Prioritas-Banjir bekerja dalam waktu O (N) pada data integer dan waktu O (N log N) pada data titik-mengambang, P&D bekerja dalam waktu O (N ^1.5 ). Ini diterjemahkan ke dalam perbedaan kinerja yang sangat besar yang tumbuh secara eksponensial dengan ukuran DEM:

Pada tahun 2001, Ehlschlaeger, Vincent, Soille, Beucher, Meyer, dan Gratin secara kolektif menerbitkan lima makalah yang merinci algoritma Priority-Flood. Planchon dan Darboux, dan pengulas mereka, melewatkan semua ini dan menemukan algoritma yang perintahnya lebih lambat. Sekarang tahun 2018 dan kami masih membangun algoritma yang lebih baik, tetapi P&D masih digunakan. Saya pikir itu disayangkan.