Algoritma apa yang digunakan oleh alat ArcGIS Watershed?

10

Adakah yang tahu jenis algoritma apa yang digunakan dalam alat ArcGIS Watershed (dalam paket Spatial Analyst)?

Sangat sedikit informasi yang diberikan di situs web Esri ... tapi saya curiga ini mungkin semacam pencarian mendalam / luas.

Saya telah melihat halaman Bantuan Online ArcGIS ini:

Jadi ya, ia menggunakan aliran arah raster, tetapi algoritma apa yang digunakannya untuk melintasi raster?

Harap dicatat, saya tidak mencari jawaban di sepanjang baris 'itu menggunakan D8 ..' ... D8 sebenarnya bukan algoritma, tetapi model untuk membantu menentukan algoritma yang akan Anda gunakan. IE Anda bisa menerapkan skema D8 dalam algoritma pencarian kedalaman-pertama dan / atau algoritma pencarian luas-pertama

James
sumber
James, saya sedang mencoba untuk melakukan hal yang sama, yaitu, membuat aplikasi yang mengambil koordinat yang ditentukan dan memberi kita garis batas DAS. Saya menggunakan python. Mari kita bicara tentang kemajuan kita.
Saya juga menggunakan Python. Saya mulai dengan masalah yang lebih sederhana dalam menghitung grid arah aliran dan bergerak dari sana.
James

Jawaban:

6

Metode yang telah saya terapkan dalam beberapa bahasa dan percaya bahwa ESRI menggunakan (maaf, tidak ada referensi selain Jenson dan Domingue dikutip di tempat lain di halaman ini) adalah mulai pada sel "titik tuangkan" yang disediakan pengguna atau sel di tepi grid arah aliran (fdr), periksa delapan tetangganya untuk menemukan yang mana dari aliran langsung ke sel saat ini, dan menetapkan sel-sel tersebut ke arus "DAS" di grid output. Kemudian fungsi secara rekursif memanggil dirinya sendiri sekali untuk masing-masing tetangga yang masuk. Proses ini berulang sampai semua sel yang masuk habis untuk titik-tuangkan, dan kemudian akan diulang untuk semua titik-tuangkan.

Desain algoritma rekursif dapat menjadi sangat mahal karena akhirnya dapat mencoba untuk menyimpan banyak data dalam memori, harus menukar / halaman ke disk, dan karena itu umumnya menderita lambat lambat.

(lihat komentar whuber di bawah ini tentang berbagai metode rekursi, jika Anda akan RYO)

_____________ EDIT _____________

Gali kode C lama saya sebagai contoh (catatan: Meskipun sebagian besar pythoners mungkin ingin lari dari ruangan, seharusnya tidak terlalu buruk). Mungkin menarik untuk diilustrasikan. Walaupun saya baru sekarang akrab dengan rekursi mendalam-pertama vs kedalaman-pertama, saya berpikir bahwa rutinitas saya memang kedalaman-pertama (dan bahwa deskripsi bahasa alami saya di atas menyesatkan) berdasarkan posting stackoverflow ini (semoga @ whuber atau orang lain yang lebih pintar dari saya dapat konfirmasi / tolak).

Kode: penjelasan: idiradalah raster nilai arah aliran. offsetmerujuk ke sel tengah yang saat ini sedang dianalisis, dan offmemeriksa masing-masing tetangga sel itu. Ini memanggil fungsi lain does_it_flow_into_me,, yang mengembalikan boolean, apakah flowdir sel tetangga menunjuk ke sel saat ini. Jika benar untuk tetangga, maka kembalilah ke lokasi itu.

void shed(int init_x, int init_y, int basin_id){

int i, j, offset, off, flow_dir;

offset = ((init_y - 1) * nc) + (init_x - 1);
*(basin + offset) = basin_id;


/* kernel analysis */
for (i = -1; i <  2; i++) {
    for (j = -1; j <  2; j++) {
        if ((i) || (j)) {

            off = offset + (j * nc +  i);
            flow_dir = *(idir + off);


            if (does_it_flow_into_me(i,j,flow_dir)){
                shed(init_x+i, init_y+j,basin_id);
            }
        } /*not center */
    } /* do - j */
} /* do - i */
}
Roland
sumber
Anda menggambarkan rekursi pertama-lebarnya. Dengan tumpukan kecil Anda dapat menerapkan rekursi kedalaman-pertama yang efisien, yang membutuhkan sedikit memori. Masalah kinerja utama akan menyangkut DAS besar di mana ubin grid mungkin harus ditukar masuk dan keluar dari RAM berulang kali. Namun, sebagaimana dibahas dalam komentar untuk jawaban lain, masalah sebenarnya berkaitan dengan penanganan sel di mana tidak ada arah D8 yang ditentukan secara unik, terutama sel-sel yang terletak di dalam tambalan horizontal datar yang luas (seperti yang dibuat oleh rutinitas pengisian-tenggelam awal).
whuber
Jelas masalah sampah di-sampah keluar. Apa yang saya dan sebagian besar GIss lakukan tidak akan membersihkan input! Kedengarannya seperti saya harus mencari rekursi kedalaman-pertama untuk menaruh sedikit polish pada retas saya.
Roland
Saya tidak berpikir ini adalah sampah - ingat, terlepas dari bagaimana implementasinya dipecah, input asli adalah DEM itu sendiri daripada coding D8 seseorang - tapi itu jelas sebuah tantangan. Dunia nyata memiliki banyak tempat yang sangat datar sehingga arah alirannya sulit ditentukan: setiap kendaraan air statis adalah contoh yang baik. Akibatnya, Anda perlu menemukan outlet danau dan area datar lainnya dan Anda perlu mengatasi area datar yang memiliki banyak outlet. Ini membutuhkan pencarian non-lokal , yang sulit dilakukan.
Whuber
Saya mungkin bingung kalau begitu. Saya pikir kita sedang mendiskusikan help.arcgis.com/en/arcgisdesktop/10.0/help../index.html#//… , yang menggunakan flowdir sebagai input. Tidak ingin menarik kami ke dalam ilalang jika aku belum membaca sisanya dengan cukup cermat!
Roland
Tidak, saya pikir Anda benar: ketika saya membaca kembali pertanyaan itu, saya melihatnya berfokus secara khusus pada pemrosesan aliran arah raster sebagai input, daripada pada situasi yang lebih umum yang saya bayangkan. Jadi beri +1 pada jawaban Anda untuk mengatasinya secara langsung dan dengan wawasan dan petunjuk bermanfaat.
whuber
4

The ArcGIS bantuan mengatakan:

Daerah aliran sungai dapat digambarkan dari DEM dengan menghitung arah aliran dan menggunakannya dalam alat Daerah Aliran Sungai. Untuk menentukan area yang berkontribusi, raster yang mewakili arah aliran harus dibuat terlebih dahulu dengan alat Flow Direction.

Arah Aliran dihitung dari DEM menggunakan metode D8 , Di mana aliran diabstraksi dengan menghitung untuk setiap sel, yang mana dari 8 tetangga, air dari sel ini akan mengalir ke.

Ada banyak alternatif untuk D8, seperti Rho8, Froh8 & Stream Tubes, tetapi sebagian besar Perangkat Lunak GIS termasuk ArcGIS cenderung menggunakan D8, karena lebih sederhana, dan kurang intensif secara komputasi daripada yang lain.


Beberapa tahun yang lalu, saya mengerjakan proyek Delineasi Daerah Aliran Sungai, dan kami menghadapi beberapa masalah karena ArcGIS menggunakan metode D8. Dua masalah utama adalah

  • D8 hanya memungkinkan Uni Directional Flow. Air dapat mengalir hanya dalam satu arah dari satu sel.
  • Aliran aliran yang dihasilkan memiliki bias besar di sepanjang sumbu diagonal. Ini menimbulkan aliran tampak aneh.

Dari data kami, kami tahu bahwa dua masalah ini adalah masalah besar, jadi saya telah mengembangkan beberapa alat untuk menghasilkan arahan aliran menggunakan metode hybrid.

Salah satu tugas saya yang paling awal adalah merekayasa balik alat perhitungan Catchment. Saya menemukan bahwa itu secara logis cukup sederhana. Jika Anda ingin menemukan tangkapan untuk titik tertentu (juga disebut titik tuangkan), pertama-tama Anda menemukan sel tempat sel itu berada. Seringkali Anda akan mencoba untuk snap ke titik dengan akumulasi aliran tertinggi dalam toleransi yang diberikan.

Untuk sel ini, Anda akan menemukan semua sel di lingkungan yang berkontribusi padanya. Untuk setiap sel lingkungan ini, Anda menemukan sel yang berkontribusi padanya dan seterusnya. Anda melanjutkan proses berulang ini hingga Anda tidak menemukan sel baru. Saat itulah Anda telah mencapai garis punggungan atau batas daerah aliran sungai.

Saya menemukan bahwa kode sederhana saya yang melakukan ini untuk raster ASCII, memberikan output yang hampir sama jika dibandingkan dengan alat DAS ArcGIS. Kadang-kadang dulu ada perbedaan beberapa sel pada batas, jadi saya yakin bahwa ArcGIS mengikuti algoritma D8 yang tidak dimodifikasi.

Devdatta Tengshe
sumber
Terima kasih untuk penjelasannya. Tapi apa algoritma untuk menggunakan arah D8 untuk menemukan daerah aliran sungai? Silakan lihat komentar berikut jawaban dmahr .
whuber
Hai, terima kasih tetapi ini tidak benar-benar menjawab pertanyaan. Anda memukulnya dengan kalimat "Untuk sel ini Anda akan menemukan semua sel di lingkungan yang berkontribusi padanya. Untuk setiap sel lingkungan ini, Anda menemukan sel yang berkontribusi pada mereka dan seterusnya". Ada banyak algoritma berbeda untuk mengimplementasikan pencarian itu. Pertanyaannya adalah yang mana
James
4

Ini telah ditanyakan sebelumnya , meskipun mungkin dalam konteks yang sedikit berbeda. Semua alat geoproses dalam perangkat Hidrologi Analis Tata Ruang menggunakan model arah aliran D8 , seperti yang dinyatakan dalam halaman Cara Alir Arah Bekerja :

Ada delapan arah output yang valid terkait dengan delapan sel yang berdekatan di mana aliran bisa berjalan. Pendekatan ini umumnya disebut sebagai model aliran delapan arah (D8) dan mengikuti pendekatan yang disajikan dalam Jenson dan Domingue (1988).

Salinan kertas Jenson dan Domingue (1988) tersedia di sini .

Semua alat yang menggunakan raster Arah Aliran sebagai input menggunakan model arah aliran ini dengan asosiasi. Ini termasuk DAS, Akumulasi Aliran, Panjang Aliran, Isi, dll.

dmahr
sumber
Jadi saya kira akan mengikuti pertanyaan, bagaimana algoritma diubah untuk mengembalikan tangkapan?
James
Alat Watershed menavigasi raster arah aliran dari titik tuangkan. Ini kebalikan dari alat Akumulasi Aliran, kecuali bahwa alih-alih raster keluaran yang menggambarkan jumlah sel, itu melaporkan ID titik tuangkan.
dmahr
1
Ok, saya rasa saya harus sedikit lebih spesifik. Saya tahu konsep apa yang dilakukannya. Saya tidak tahu algoritma apa yang diterapkan. Yaitu saya menganggap itu adalah semacam algoritma pencarian, tetapi itu masih bisa; lebar-pertama, mendalam-pertama, iteratif-memperdalam mendalam-pertama dll ...
James
1
terima kasih dmahr. @whuber: Sejauh yang saya tahu, algoritma pencarian yang berbeda dapat memberikan hasil yang sedikit berbeda? Dan ya, menemukan algoritma generik bukanlah masalah, tetapi mempelajari bagaimana ESRI menangani area spesifik DAS (seperti bagian datar DTM) berguna.
James
1
James Harap edit pertanyaan Anda untuk memperjelas poin terakhir itu, sehingga utas ini berhenti mengumpulkan jawaban "itu D8" yang tidak berguna. (Apa yang membantu tentang komentar D8 adalah bahwa jika Anda menerima bahwa D8 mengarah ke grafik arah aliran yang unik, maka ada solusi unik yang benar untuk masalah penggambaran DAS, karena daerah aliran sungai adalah properti dari grafik itu sendiri. Dengan demikian jika ada ambiguitas apa pun yang harus ada di (a) definisi "batas air", (b) bagaimana arah D8 dihitung, atau (c) bagaimana sel horizontal (yaitu, tanpa arah D8 unik) ditangani.)
whuber
0

Untuk lebih memikirkan pertanyaan ini, saya menjalankan analisis DAS dalam busur: Saya mengambil DEM (diisi), menghitung arah aliran dan menempatkan beberapa titik yang sesuai dengan lokasi pada jaringan aliran yang sebelumnya dihitung. Saya menjalankan alat 'daerah aliran sungai' dan memberi saya beberapa bak air bagus, cukup banyak menutupi sebagian besar daerah 'hulu' yang tersisa (seperti yang Anda harapkan):

gambar DAS

Saya kemudian menyusun algoritma pencarian cepat dengan Python (seperti jawaban di atas), yang memeriksa grid arah aliran dan 'mengikuti' jalur aliran. Untuk setiap node, saya memeriksa 8 tetangga dan jika tetangga mengalir ke node saat ini, saya memanggil fungsi yang sama secara rekursif dengan simpul tetangga sebagai input.

Kode semu (ish):

class d8():
    def __init__(self, arr):
       self.catchment = set()
       self.arr = arr

    def search(self, node):
        """ Searches all neighbouring nodes to find flow paths """ 

        # add the current node to the catchment
        self.catchment.add(node)

        # search the neighbours, ignore ones we already visited
        for each_neighbour:
            if neighbour is in self.catchment:
               do nothing

            # if the neighbour flows into the current node, visit that neighbour
            elif neighbour_flows_into_me:
               self.search(neighbour)

Saya menjalankan fungsi itu menggunakan input grid arah aliran yang sama dan salah satu poin yang sama. Masalahnya adalah, di mana arc mengembalikan tangkapan sekitar 40000 sel untuk titik itu, algoritma saya hanya mengembalikan 72 sel.

Adakah yang tahu apa yang saya lakukan salah?

James
sumber