Quel algorithme est utilisé par l'outil ArcGIS Watershed?

10

Quelqu'un sait-il quel type d'algorithme est utilisé dans l'outil ArcGIS Watershed (dans le package Spatial Analyst)?

Très peu d'informations fournies sur le site Web d'Esri ... mais je soupçonne qu'il peut s'agir d'une sorte de recherche approfondie / étendue.

J'ai consulté ces pages d'aide d'ArcGIS Online:

Alors oui, il utilise le raster de direction de flux, mais quel algorithme utilise-t-il pour parcourir le raster?

Veuillez noter que je ne cherche pas de réponses du type «il utilise D8 ..» ... D8 n'est pas vraiment un algorithme, mais un modèle pour aider à définir l'algorithme que vous utiliseriez. IE, vous pouvez implémenter le schéma D8 dans un algorithme de recherche en profondeur d'abord et / ou un algorithme de recherche en largeur

James
la source
James, j'essaie de faire la même chose, c'est-à-dire créer une application qui prend une coordonnée déterminée et nous donne une délimitation du bassin versant. J'utilise python. Parlons de nos progrès.
J'utilise également Python. Je commence par le problème plus simple de calculer une grille de direction d'écoulement et de continuer à partir de là.
James

Réponses:

6

La méthode que j'ai implémentée dans plusieurs langues et que ESRI utilise (désolé, pas de références autres que Jenson et Domingue citées ailleurs dans cette page) est de commencer à partir d'une cellule "pour-point" fournie par l'utilisateur ou d'une cellule au bord de la grille de direction du flux (fdr), examinez ses huit voisins pour trouver lequel de ces flux directs dans la cellule actuelle et affectez ces cellules au "bassin versant" actuel dans la grille de sortie. Ensuite, la fonction s'appelle récursivement une fois pour chacun des voisins entrants. Ce processus se répète jusqu'à ce que toutes les cellules entrantes soient épuisées pour un point d'écoulement, puis se répétera pour tous les points d'écoulement.

La conception de l'algorithme récursif peut être assez coûteuse car elle peut finir par essayer de conserver beaucoup de données en mémoire, devoir échanger / paginer sur le disque, et donc généralement subir des ralentissements d'E / S.

(voir le commentaire de whuber ci-dessous sur les différentes méthodes de récursivité, si vous allez RYO)

_____________ MODIFIER _____________

Dug out mon ancien code C à titre d'exemple (note: Bien que la plupart des pythoners puissent vouloir s'exécuter à partir de la salle, cela ne devrait pas être trop mauvais). J'ai pensé qu'il pourrait être intéressant d'illustrer. Bien que je ne sois que superficiellement familier avec la récursion en largeur par rapport à la profondeur en premier, je pense que ma routine est en effet la profondeur d'abord (et que ma description en langage naturel ci-dessus était trompeuse) basée sur cette publication stackoverflow (espérons-le @ whuber ou une autre personne plus intelligente que moi peut confirmer / nier).

Code: explication: idirest le raster des valeurs de direction du flux. offsetfait référence à la cellule centrale en cours d'analyse et offvérifie chacun des voisins de cette cellule. Cela appelle une autre fonction, does_it_flow_into_mequi retourne un booléen indiquant si le fluxdir de la cellule voisine pointe vers la cellule actuelle. Si cela est vrai pour un voisin, récursivement à cet endroit

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
la source
Vous décrivez une récursion étendue. Au moyen d'une petite pile, vous pouvez implémenter une récursion efficace en profondeur d'abord, qui nécessite peu de mémoire. Le principal problème de performance concernerait les grands bassins versants où les tuiles de la grille pourraient devoir être échangées à plusieurs reprises dans la RAM. Comme discuté dans les commentaires d'autres réponses, le vrai problème concerne la gestion des cellules où il n'y a pas de direction D8 déterminée de manière unique, en particulier les cellules situées dans de vastes zones horizontales plates (telles que celles créées par les routines préliminaires de remplissage des puits).
whuber
Certainement un problème de garbage in-garbage out. Ce que moi et la plupart des GIs ne nettoierons pas l'entrée! On dirait que j'ai besoin d'aller chercher la récursion en profondeur pour mettre un peu de poli sur mon hack.
Roland
Je ne pense pas que ce soit une ordure - rappelez-vous, quelle que soit la façon dont l'implémentation est décomposée, l'entrée d'origine est le DEM lui-même plutôt que le codage D8 de quelqu'un - mais c'est certainement un défi. Le monde réel a de nombreux endroits si plats que la direction de l'écoulement est difficile à déterminer: tout plan d'eau statique en est un bon exemple. En effet, vous devez trouver des exutoires de lacs et d'autres zones plates et vous devez faire face à des zones plates qui ont plusieurs exutoires. Cela nécessite des recherches non locales , ce qui est difficile à faire.
whuber
Je suis probablement confus alors. Je pense que nous discutons help.arcgis.com/en/arcgisdesktop/10.0/help../index.html#//… , qui prend flowdir comme entrée. Je ne veux pas nous entraîner dans les mauvaises herbes si je n'ai pas lu le reste assez attentivement!
Roland
Non, je pense que vous avez raison: en relisant la question, je vois qu'elle se concentre spécifiquement sur le traitement du raster de direction de flux en entrée, plutôt que sur la situation plus générale que j'envisageais. +1 à votre réponse pour y avoir répondu directement et avec des conseils perspicaces et utiles.
whuber
4

L' aide d'ArcGIS indique:

Les bassins versants peuvent être délimités à partir d'un MNT en calculant la direction du flux et en l'utilisant dans l'outil Bassin versant. Pour déterminer la zone de contribution, un raster représentant la direction du flux doit d'abord être créé avec l'outil Direction du flux.

La direction du flux est calculée à partir du DEM à l'aide de la méthode D8 , où le flux est abstrait en calculant pour chaque cellule, laquelle de ses 8 voisins, l'eau de cette cellule va s'écouler.

Il existe de nombreuses alternatives à D8, telles que Rho8, Froh8 et Stream Tubes, mais la plupart des logiciels SIG, y compris ArcGIS, ont tendance à utiliser D8, car il est plus simple et moins intensif en calcul que les autres.


Il y a quelques années, je travaillais sur un projet de délimitation de bassin versant et nous étions confrontés à plusieurs problèmes dus à l'utilisation d'ArcGIS par la méthode D8. Les deux principaux problèmes étaient

  • D8 autorise uniquement l'écoulement unidirectionnel. L'eau ne peut s'écouler que dans une direction à partir d'une cellule.
  • Les flux de flux générés avaient un énorme biais le long de l'axe diagonal. Cela a donné naissance à des flux étranges.

D'après nos données, nous savions que ces deux problèmes étaient de gros problèmes, alors j'avais développé des outils pour générer des directions de flux à l'aide de méthodes hybrides.

L'une de mes premières tâches a été de désosser l'outil de calcul du bassin versant. J'ai trouvé que c'était logiquement assez simple. Si vous souhaitez trouver le bassin versant pour un point donné (également appelé point d'écoulement), vous devez d'abord trouver la cellule à laquelle il appartient. Souvent, vous essaierez de l'enclencher au point avec l'accumulation de débit la plus élevée dans une tolérance donnée.

Pour cette cellule, vous trouverez toutes les cellules du quartier qui y contribuent. Pour chacune de ces cellules de voisinage, vous trouvez les cellules qui y contribuent et ainsi de suite. Vous poursuivez ce processus itératif jusqu'à ce que vous ne trouviez aucune nouvelle cellule. C'est alors que vous avez atteint les lignes de crête ou la limite du bassin versant.

J'ai trouvé que mon code simple qui faisait cela pour les rasters ASCII, donnait une sortie presque similaire par rapport à l'outil Watershed d'ArcGIS. Parfois, il y avait une différence de quelques cellules sur la frontière, donc je suis convaincu qu'ArcGIS suit un algorithme D8 non modifié.

Devdatta Tengshe
la source
Merci pour l'élaboration. Mais quel est l'algorithme pour utiliser les directions D8 pour trouver des bassins versants? Veuillez consulter les commentaires qui suivent la réponse de dmahr .
whuber
Salut, merci, mais cela ne répond pas vraiment à la question. Vous l'avez frappé avec la phrase "Pour cette cellule, vous trouverez toutes les cellules du quartier qui y contribuent. Pour chacune de ces cellules du quartier, vous trouvez les cellules qui y contribuent et ainsi de suite". Il existe de nombreux algorithmes différents pour implémenter cette recherche. La question est laquelle
James
4

Cette question a déjà été posée , mais peut-être dans un contexte légèrement différent. Tous les outils de géotraitement de l'ensemble d'outils hydrologiques de Spatial Analyst utilisent le modèle de direction d'écoulement D8 , comme indiqué dans la page Fonctionnement de la direction d'écoulement :

Il existe huit directions de sortie valides relatives aux huit cellules adjacentes dans lesquelles le flux pourrait se déplacer. Cette approche est communément appelée modèle d'écoulement à huit directions (D8) et suit une approche présentée dans Jenson et Domingue (1988).

Une copie de l'article de Jenson et Domingue (1988) est disponible ici .

Tous les outils qui utilisent des rasters de direction de flux en entrée utilisent ce modèle de direction de flux par association. Cela comprend notamment le bassin versant, l'accumulation de débit, la longueur du débit, le remplissage, etc.

dmahr
la source
Je suppose donc qu'une question de suivi serait: comment cet algorithme est-il modifié pour renvoyer le bassin versant?
James
L'outil Bassin versant remonte le raster de direction d'écoulement à partir des points d'écoulement. C'est l'inverse de l'outil Flow Accumulation, sauf qu'au lieu du raster en sortie décrivant le nombre de cellules, il rapporte l'ID du point d'écoulement.
dmahr
1
Ok, je suppose que je dois être un peu plus précis. Je connais le concept de ce qu'il fait. Je ne sais pas quel algorithme est implémenté. C'est-à-dire que je suppose qu'il s'agit d'une sorte d'algorithme de recherche, mais il pourrait toujours l'être; largeur d'abord, profondeur d'abord, approfondissement itératif en profondeur etc ...
James
1
merci dmahr. @whuber: Pour autant que je sache, différents algorithmes de recherche pourraient donner des résultats légèrement différents? Et oui, trouver un algorithme générique n'est pas un problème, mais apprendre comment ESRI gère les zones spécifiques aux bassins versants (comme les parties plates d'un MNT) est utile.
James
1
James Veuillez modifier votre question pour clarifier ce dernier point, afin que ce fil cesse de collecter des réponses "c'est D8" sinon inutiles. (Ce qui est utile dans les commentaires du D8, c'est que si vous acceptez que le D8 mène à un graphique de direction d'écoulement unique, il existe une solution correcte unique au problème de délimitation du bassin versant, car les bassins versants sont des propriétés du graphique lui-même. toute ambiguïté dans laquelle ils doivent se situer (a) la définition de «bassin versant», (b) comment les directions D8 sont calculées, ou (c) comment les cellules horizontales (c'est-à-dire sans direction D8 unique) sont gérées.)
whuber
0

Pour réfléchir davantage à cette question, j'ai effectué une analyse des bassins versants en arc: j'ai pris un DEM (rempli), calculé la direction du flux et placé quelques points qui correspondaient à des emplacements sur un réseau de cours d'eau précédemment calculé. J'ai exécuté l'outil `` bassin versant '' et cela m'a donné quelques jolis bassins, couvrant à peu près la plupart des zones restantes `` en amont '' (comme vous vous en doutez):

image de bassin versant

J'ai ensuite codé un algorithme de recherche rapide en Python (comme la réponse ci-dessus), qui inspecte la grille de direction du flux et «suit» les chemins du flux. Pour chaque nœud, j'inspecte les 8 voisins et si un voisin se jette dans le nœud actuel, j'appelle récursivement la même fonction avec le nœud voisin en entrée.

Pseudo (ish) code:

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)

J'ai exécuté cette fonction en utilisant la même grille d'entrée de direction de flux et l'un des mêmes points. Le problème est que, lorsque l'arc renvoie un bassin versant d'environ 40000 cellules pour ce point, mon algorithme ne renvoie que 72 cellules.

Quelqu'un sait ce que je fais mal?

James
la source