Jakiego algorytmu używa narzędzie ArcGIS Watershed?

10

Czy ktoś wie, jakiego rodzaju algorytmu używa narzędzie ArcGIS Watershed (w pakiecie Spatial Analyst)?

Bardzo mało informacji podanych na stronie Esri ... ale podejrzewam, że może to być jakieś wyszukiwanie głębokości / szerokości.

Przejrzałem strony pomocy ArcGIS Online:

Więc tak, wykorzystuje raster kierunku przepływu, ale jakiego algorytmu używa do przechodzenia przez raster?

Uwaga: nie szukam odpowiedzi w stylu „używa D8 ...”… D8 nie jest tak naprawdę algorytmem, ale modelem pomagającym zdefiniować algorytm, którego należy użyć. IE można zaimplementować schemat D8 w algorytmie przeszukiwania w pierwszej kolejności i / lub w algorytmie przeszukiwania w pierwszej kolejności

James
źródło
James, staram się zrobić to samo, tj. Stworzyć aplikację, która przyjmuje określoną współrzędną i daje nam przełomowe określenie. Używam pytona. Porozmawiajmy o naszych postępach.
Używam również Pythona. Zaczynam od prostszego problemu obliczenia siatki kierunków przepływu i przejścia stamtąd.
James

Odpowiedzi:

6

Metodą, którą wdrożyłem w kilku językach i uważam, że używa ESRI (przepraszam, brak odniesień innych niż Jenson i Domingue cytowane w innym miejscu na tej stronie) jest rozpoczęcie od dostarczonej przez użytkownika komórki lub komórki „punktu krzepnięcia” na krawędzi siatki kierunku przepływu (fdr), zbadaj jej ośmiu sąsiadów, aby dowiedzieć się, który z nich wpływa bezpośrednio do bieżącej komórki, i przypisz te komórki do bieżącego „zlewu” w siatce wyjściowej. Następnie funkcja rekurencyjnie wywołuje się raz dla każdego z napływających sąsiadów. Proces ten powtarza się, aż wszystkie napływające komórki zostaną wyczerpane dla punktu krzepnięcia, a następnie powtórzy się dla wszystkich punktów krzepnięcia.

Algorytm rekurencyjny może być dość kosztowny, ponieważ może skończyć się próbą przechowywania dużej ilości danych w pamięci, konieczności zamiany / stronicowania na dysk, a zatem generalnie występuje spowolnienie operacji we / wy.

(patrz komentarz Whubera poniżej na temat różnych metod rekurencji, jeśli zamierzasz RYO)

_____________ EDYCJA _____________

Odkopałem mój stary kod C jako przykład (uwaga: chociaż większość pythonerów może chcieć uruchomić z pokoju, nie powinno być tak źle). Pomyślałem, że warto to zilustrować. Chociaż dopiero teraz pozornie zaznajomiłem się z rekurencją w pierwszej kolejności w stosunku do głębokości pierwszej, myślę, że moja rutyna jest naprawdę w pierwszej kolejności (i że mój opis języka naturalnego powyżej wprowadzał w błąd) w oparciu o ten komunikat o przepełnieniu stosu (mam nadzieję, że @ whuber lub inna osoba mądrzejsza ode mnie może potwierdzić / odmówić).

Kod: wyjaśnienie: idirjest rastrem wartości kierunku przepływu. offsetodnosi się do komórki centralnej, która jest obecnie analizowana, i offsprawdza każdego z sąsiadów tej komórki. does_it_flow_into_meWywołuje to inną funkcję, która zwraca wartość logiczną określającą, czy katalog przepływu sąsiedniej komórki wskazuje na bieżącą komórkę. Jeśli to prawda dla sąsiada, wróć do tej lokalizacji.

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
źródło
Opisujesz pierwszą rekurencję. Za pomocą małego stosu można zaimplementować wydajną rekurencję z głębokością pierwszą, która wymaga niewiele pamięci. Główny problem z wydajnością dotyczyłby dużych zlewisk, w których płytki siatki mogły być wielokrotnie wymieniane z RAM. Jednak, jak omówiono w komentarzach do innych odpowiedzi, prawdziwy problem dotyczy radzenia sobie z komórkami, w których nie ma jednoznacznie określonego kierunku D8, szczególnie komórki leżące w rozległych płaskich łatach poziomych (takich jak te utworzone przez wstępne procedury wypełniania zlewu).
whuber
Zdecydowanie problem śmieci w śmieciach. To, co ja i większość GIssów nie wyczyści danych wejściowych! Wygląda na to, że muszę poszukać pierwszej rekurencji, aby polerować mój hack.
Roland
Nie sądzę, że to śmiecie - pamiętaj, bez względu na to, jak implementacja jest zepsuta, oryginalnym wejściem jest sam DEM, a nie czyjeś kodowanie D8 - ale to zdecydowanie wyzwanie. W prawdziwym świecie jest wiele miejsc, które są tak płaskie, że trudno jest określić kierunek przepływu: każdy statyczny zbiornik wodny jest dobrym przykładem. W rezultacie musisz znaleźć ujścia jezior i innych płaskich obszarów i poradzić sobie z płaskimi obszarami, które mają wiele ujść. Wymaga to wyszukiwania nielokalnego , co jest trudne.
whuber
Prawdopodobnie wtedy jestem zdezorientowany. Myślę, że omawiamy help.arcgis.com/en/arcgisdesktop/10.0/help../index.html#//… , który przyjmuje dane wejściowe flowdir. Nie chcę wciągać nas w chwasty, jeśli nie przeczytam wystarczająco dokładnie reszty!
Roland
Nie, myślę, że masz rację: kiedy ponownie czytam pytanie, widzę, że koncentruje się ono w szczególności na przetwarzaniu rastra kierunku przepływu jako danych wejściowych, a nie na bardziej ogólnej sytuacji, którą sobie wyobrażałem. Daj +1 do swojej odpowiedzi, aby odpowiedzieć na nią bezpośrednio i uzyskać wgląd oraz pomocne wskazówki.
whuber
4

Pomoc ArcGIS mówi:

Obszary wodne można wyznaczyć z DEM, obliczając kierunek przepływu i używając go w narzędziu Watershed. Aby określić obszar przyczyniający się, należy najpierw utworzyć raster reprezentujący kierunek przepływu za pomocą narzędzia Kierunek przepływu.

Kierunek przepływu jest obliczany z DEM przy użyciu metody D8 , gdzie przepływ jest pobierany poprzez obliczenie dla każdej komórki, do którego z 8 sąsiadów, woda z tej komórki przepłynie.

Istnieje wiele alternatyw dla D8, takich jak Rho8, Froh8 i Stream Tubes, ale większość oprogramowania GIS, w tym ArcGIS, zwykle używa D8, ponieważ jest prostsze i mniej intensywne obliczeniowo niż inne.


Kilka lat temu pracowałem nad projektem Watershed Delineation i napotkaliśmy kilka problemów związanych z ArcGIS przy użyciu metody D8. Dwa główne problemy to

  • D8 pozwala tylko na przepływ jednokierunkowy. Woda może wypływać tylko w jednym kierunku z jednej komórki.
  • Generowane przepływy strumieniowe miały ogromne odchylenie wzdłuż osi ukośnej. Dało to początek dziwnie wyglądającym strumieniom.

Na podstawie naszych danych wiedzieliśmy, że te dwa problemy były dużymi problemami, dlatego opracowałem narzędzia do generowania kierunków przepływu przy użyciu metod hybrydowych.

Jednym z moich najwcześniejszych zadań było odtworzenie narzędzia do obliczania Zlewni. Odkryłem, że było to logicznie proste. Jeśli chcesz znaleźć zlewnię dla danego punktu (zwaną także temperaturą krzepnięcia), najpierw znajdź komórkę, do której należy. Często będziesz próbował przyciągnąć go do punktu o największej akumulacji przepływu w danej tolerancji.

Dla tej komórki znajdziesz wszystkie komórki w sąsiedztwie, które się do niej przyczyniają. Dla każdej z tych sąsiednich komórek znajdziesz komórki, które się do nich przyczyniają i tak dalej. Kontynuujesz ten iteracyjny proces, dopóki nie znajdziesz żadnych nowych komórek. Wtedy osiągniesz linię grzbietu lub granicę zlewni.

Odkryłem, że mój prosty kod, który zrobił to dla rastrów ASCII, dał prawie podobny wynik w porównaniu do narzędzia Watershed ArcGIS. Czasami istniała różnica kilku komórek na granicy, więc jestem przekonany, że ArcGIS stosuje niezmodyfikowany algorytm D8.

Devdatta Tengshe
źródło
Dziękuję za opracowanie. Ale jaki jest algorytm używania kierunków D8 w celu znalezienia zlewni? Zobacz komentarze po odpowiedzi dmahr .
whuber
Cześć, dziękuję, ale tak naprawdę to nie odpowiada na pytanie. Uderzasz go zdaniem „Dla tej komórki znajdziesz wszystkie komórki w sąsiedztwie, które się do niej przyczyniają. Dla każdej z tych komórek sąsiedztwa znajdziesz komórki, które się do nich przyczyniają i tak dalej”. Istnieje wiele różnych algorytmów do realizacji tego wyszukiwania. Pytanie, które z nich
James
4

Zostało to już wcześniej zadane , choć może w nieco innym kontekście. Wszystkie narzędzia geoprzetwarzania w zestawie narzędzi hydrologicznych programu Spatial Analyst korzystają z modelu kierunku przepływu D8 , jak podano na stronie Jak działa kierunek przepływu :

Istnieje osiem prawidłowych kierunków wyjściowych dotyczących ośmiu sąsiednich komórek, do których może przepływać przepływ. Takie podejście jest powszechnie określane jako ośmiokierunkowy (D8) model przepływu i jest zgodne z podejściem przedstawionym w Jenson i Domingue (1988).

Kopia pracy Jensona i Domingue (1988) jest dostępna tutaj .

Wszystkie narzędzia, które wykorzystują rastry kierunku przepływu jako dane wejściowe, wykorzystują ten model kierunku przepływu przez skojarzenie. Obejmuje to między innymi wododział, akumulację przepływu, długość przepływu, wypełnienie itp.

dmahr
źródło
Podejrzewam więc, że pytanie brzmi: w jaki sposób algorytm jest zmieniany, aby zwrócić zlewnię?
James
Narzędzie Watershed porusza się w górę rastra kierunku przepływu od punktów płynności. Jest to odwrotność narzędzia Flow Accumulation, z tą różnicą, że zamiast wyjściowego rastra opisującego liczbę komórek, podaje on identyfikator punktu krzepnięcia.
dmahr
1
Ok, chyba muszę być bardziej konkretny. Znam pojęcie tego, co robi. Nie wiem, jaki algorytm jest zaimplementowany. Tzn. Zakładam, że jest to jakiś algorytm wyszukiwania, ale nadal może być; szerokość pierwsza, głębokość pierwsza, głęboka iteracyjna głębia pierwsza itd ...
James
1
dzięki dmahr. @whuber: O ile mi wiadomo, różne algorytmy wyszukiwania mogą dawać nieco inne wyniki? I tak, znalezienie ogólnego algorytmu nie stanowi problemu, ale przydatne jest nauczenie się, jak ESRI obsługuje obszary specyficzne dla działów wodnych (takie jak płaskie części DTM).
James
1
James Edytuj swoje pytanie, aby wyjaśnić ten ostatni punkt, aby ten wątek przestał zbierać bezużyteczne odpowiedzi „to D8”. (Co jest pomocny o komentarzach D8 jest to, że jeśli przyjąć, że D8 prowadzi do unikalnej wykresie kierunku przepływu, to nie jest wyjątkowy poprawne rozwiązanie zlewni problemu rozgraniczenia, ponieważ zlewnie są właściwości samego wykresu. Tak więc, jeśli istnieją wszelkie niejasności, w których muszą leżeć (a) definicja „przełomu”, (b) sposób obliczania kierunków D8 lub (c) sposób obsługi komórek poziomych (tj. bez unikalnego kierunku D8).)
whuber
0

Aby zastanowić się więcej nad tym pytaniem, przeprowadziłem analizę łuku: wziąłem (wypełniony) DEM, obliczyłem kierunek przepływu i umieściłem kilka punktów odpowiadających lokalizacjom w poprzednio obliczonej sieci strumieniowej. Uruchomiłem narzędzie „zlewu” i dało mi to kilka fajnych basenów, pokrywających prawie całą pozostałą część „w górę rzeki” (jak można się spodziewać):

obraz zlewni

Następnie kodowałem algorytm szybkiego wyszukiwania w Pythonie (podobnie jak powyższa odpowiedź), który sprawdza siatkę kierunku przepływu i „podąża” ścieżkami przepływu. Dla każdego węzła sprawdzam 8 sąsiadów i jeśli sąsiad wpada do bieżącego węzła, wywołuję tę samą funkcję rekurencyjnie z sąsiednim węzłem jako wejściem.

Kod pseudo (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)

Uruchomiłem tę funkcję, używając tej samej siatki wejściowej kierunku przepływu i jednego z tych samych punktów. Problem polega na tym, że gdy łuk zwraca w tym punkcie zasięg około 40000 komórek, mój algorytm po prostu zwraca 72 komórki.

Czy ktoś wie, co robię źle?

James
źródło