Qual algoritmo é usado pela ferramenta ArcGIS Watershed?

10

Alguém sabe que tipo de algoritmo é usado na ferramenta ArcGIS Watershed (no pacote Spatial Analyst)?

Muito pouca informação é fornecida no site da Esri ... mas suspeito que possa ser algum tipo de pesquisa de profundidade / amplitude.

Eu olhei para estas páginas de Ajuda do ArcGIS Online:

Então, sim, ele usa a varredura da direção do fluxo, mas que algoritmo está sendo usado para atravessar a varredura?

Observe que não estou procurando respostas ao longo das linhas de 'ele usa D8 ..' ... D8 não é realmente um algoritmo, mas um modelo para ajudar a definir o algoritmo que você usaria. IE, você pode implementar o esquema D8 dentro de um algoritmo de busca em profundidade e / ou em algoritmo de busca em profundidade

James
fonte
James, estou tentando fazer a mesma coisa, ou seja, criar um aplicativo que tenha uma determinada coordenada e nos dê uma definição do divisor de águas. Eu estou usando python. Vamos falar sobre o nosso progresso.
Eu também estou usando Python. Estou começando com o problema mais simples de calcular uma grade de direção de fluxo e seguir em frente.
James

Respostas:

6

O método que eu implementei em alguns idiomas e acredito que o ESRI usa (desculpe, nenhuma referência além de Jenson e Domingue citadas em outras partes desta página) é começar em uma célula ou célula de "ponto de fluidez" fornecida pelo usuário na borda da grade de direção do fluxo (fdr), examine seus oito vizinhos para descobrir qual fluxo direto entra na célula atual e atribua essas células à "bacia hidrográfica" atual na grade de saída. Então a função se chama recursivamente uma vez para cada um dos vizinhos que estão entrando. Esse processo se repete até que todas as células de entrada estejam esgotadas para um ponto de fluidez e, em seguida, se repete para todos os pontos de fluidez.

O design do algoritmo recursivo pode ser bastante caro, pois pode acabar tentando armazenar muitos dados na memória, tendo que trocar / paginar no disco e, portanto, geralmente sofrer lentidão de E / S.

(veja o comentário do whuber abaixo sobre os diferentes métodos de recursão, se você quiser RYO)

_____________ EDITAR _____________

Desenterrei meu código C antigo como exemplo (observação: embora a maioria dos pythoners deseje correr da sala, não deve ser muito ruim). Pensei que poderia ser interessante ilustrar. Embora só agora eu esteja superficialmente familiar com recursão de amplitude versus profundidade, estou pensando que minha rotina é realmente profunda (e que minha descrição de linguagem natural acima foi enganosa) com base nessa postagem de stackoverflow (espero que @ whuber ou outra pessoa mais inteligente que eu possa confirmar / negar).

Código: explicação: idiré a varredura dos valores da direção do fluxo. offsetrefere-se à célula central que está sendo analisada no momento e offverifica cada um dos vizinhos dessa célula. Isso chama outra função, does_it_flow_into_meque retorna um valor booleano para determinar se o flowdir da célula vizinha aponta para a célula atual. Se verdadeiro para um vizinho, retorne para esse local.

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
fonte
Você descreve a primeira recursão em largura. Por meio de uma pilha pequena, você pode implementar uma recursão eficiente em profundidade, o que requer pouca memória. O principal problema de desempenho dizia respeito a grandes bacias hidrográficas onde os blocos da grade talvez precisassem ser trocados dentro e fora da RAM repetidamente. Conforme discutido nos comentários de outras respostas, o problema real é lidar com células em que não há direção D8 exclusivamente determinada, especialmente células localizadas dentro de extensas manchas horizontais planas (como as criadas por rotinas preliminares de preenchimento de coletor).
whuber
Definitivamente um problema de lixo dentro-lixo. O que eu e a maioria dos soldados fazemos não limpa a entrada! Parece que eu preciso procurar uma recursão profunda para colocar um pouco de polimento no meu hack.
Roland
Eu não acho que isso seja um lixo - lembre-se, independentemente de como a implementação está dividida, a entrada original é o próprio DEM, e não a codificação D8 de alguém - mas é definitivamente um desafio. O mundo real tem muitos lugares tão planos que é difícil determinar a direção do fluxo: qualquer corpo de água estático é um bom exemplo. Na verdade, você precisa encontrar pontos de venda de lagos e outras áreas planas e lidar com áreas planas que possuem várias saídas. Isso requer pesquisas não locais , difíceis de fazer.
whuber
Provavelmente estou confuso então. Eu estou pensando que estamos discutindo help.arcgis.com/en/arcgisdesktop/10.0/help../index.html#//… , que usa flowdir como entrada. Não quero nos puxar para o mato, se eu não tiver lido o resto o suficiente!
Roland
Não, acho que você está certo: ao reler a pergunta, vejo que ela se concentra especificamente no processamento da varredura da direção do fluxo como entrada, e não na situação mais geral que eu estava imaginando. Então, marque com +1 a sua resposta para abordá-la diretamente e com dicas e sugestões úteis.
whuber
4

A ajuda do ArcGIS diz:

As bacias hidrográficas podem ser delineadas a partir de um DEM, computando a direção do fluxo e usando-a na ferramenta Watershed. Para determinar a área de contribuição, uma varredura que representa a direção do fluxo deve primeiro ser criada com a ferramenta Direção do fluxo.

A direção do fluxo é calculada a partir do DEM usando o método D8 , onde o fluxo é abstraído calculando para cada célula, em qual de seus 8 vizinhos, a água dessa célula fluirá para.

Existem muitas alternativas ao D8, como Rho8, Froh8 e Stream Tubes, mas a maioria dos softwares GIS, incluindo o ArcGIS, tendem a usar o D8, pois é mais simples e menos computacionalmente do que outros.


Alguns anos atrás, eu estava trabalhando em um projeto de Delimitação de Bacias Hidrográficas e estávamos enfrentando vários problemas devido ao ArcGIS usando o método D8. Os dois principais problemas foram

  • D8 permite apenas fluxo direcional uni. A água pode fluir apenas em uma direção a partir de uma célula.
  • Os fluxos de corrente gerados tiveram um grande viés ao longo do eixo diagonal. Isso deu origem a fluxos estranhos.

A partir de Nossos dados, sabíamos que esses dois problemas eram grandes problemas, então eu desenvolvi algumas ferramentas para gerar direções de fluxo usando métodos híbridos.

Uma das minhas primeiras tarefas foi fazer engenharia reversa da ferramenta de cálculo de Captação. Eu achei que era logicamente bastante simples. Se você deseja encontrar a captação para um determinado ponto (também chamado de ponto de fluidez), primeiro você encontra a célula à qual ela pertence. Frequentemente, você tentará ajustá-lo ao ponto com o maior acúmulo de fluxo em uma determinada tolerância.

Nesta célula, você encontrará todas as células da vizinhança que contribuem para ela. Para cada uma dessas células da vizinhança, você encontra as células que contribuem para elas e assim por diante. Você continua esse processo iterativo até não encontrar novas células. É quando você alcança as cordilheiras ou o limite da bacia hidrográfica.

Eu descobri que meu código simples que fazia isso para rasters ASCII, produzia resultados quase semelhantes quando comparado à ferramenta Watershed do ArcGIS. Às vezes, costumava haver uma diferença de algumas células na fronteira, então estou convencido de que o ArcGIS segue um algoritmo D8 não modificado.

Devdatta Tengshe
fonte
Obrigado pela elaboração. Mas qual é o algoritmo para usar as direções D8 para encontrar bacias hidrográficas? Por favor, veja os comentários após a resposta do dmahr .
whuber
Oi, obrigado, mas isso realmente não responde à pergunta. Você encontra a frase "Para esta célula, você encontrará todas as células da vizinhança que contribuem para ela. Para cada uma dessas células da vizinhança, você encontrará as células que contribuem para elas e assim por diante". Existem muitos algoritmos diferentes para implementar essa pesquisa. A pergunta é qual deles
James
4

Isso já foi perguntado antes , embora talvez em um contexto ligeiramente diferente. Todas as ferramentas de geoprocessamento no conjunto de ferramentas Hidrológicas do Spatial Analyst usam o modelo de direção de fluxo D8 , conforme indicado na página Como a direção de fluxo funciona :

Existem oito direções de saída válidas relacionadas às oito células adjacentes nas quais o fluxo pode viajar. Essa abordagem é comumente referida como um modelo de fluxo de oito direções (D8) e segue uma abordagem apresentada em Jenson e Domingue (1988).

Uma cópia do artigo de Jenson e Domingue (1988) está disponível aqui .

Todas as ferramentas que usam rasters de direção de fluxo como entrada utilizam esse modelo de direção de fluxo por associação. Isso inclui a bacia hidrográfica, a acumulação de fluxo, o comprimento do fluxo, o preenchimento, etc.

dmahr
fonte
Então, suponho que seria uma sequência de perguntas, como esse algoritmo é alterado para retornar a bacia hidrográfica?
James
A ferramenta Watershed navega pela varredura da direção do fluxo a partir dos pontos de fluidez. É o inverso da ferramenta Acumulação de fluxo, exceto que, em vez da varredura de saída que descreve o número de células, ela reporta o ID do ponto de fluidez.
dmahr 27/01
1
Ok, acho que preciso ser um pouco mais específico. Eu conheço o conceito do que faz. Não sei qual algoritmo é implementado. Ou seja, suponho que seja algum tipo de algoritmo de pesquisa, mas ainda pode ser; em largura, profundidade, da iterativo aprofundamento em profundidade etc ...
James
1
obrigado dmahr. @whuber: Até onde eu sei, diferentes algoritmos de pesquisa podem fornecer resultados ligeiramente diferentes? E sim, encontrar um algoritmo genérico não é um problema, mas aprender como a ESRI lida com áreas específicas de bacias hidrográficas (como partes planas de um DTM) é útil.
James
1
James Por favor, edite sua pergunta para esclarecer esse último ponto, para que este tópico pare de coletar respostas "inúteis D8". (O que é útil nos comentários do D8 é que, se você aceitar que o D8 leva a um gráfico de direção de fluxo exclusivo, existe uma solução correta exclusiva para o problema de delimitação de bacias hidrográficas, porque as bacias hidrográficas são propriedades do próprio gráfico. Portanto, se houver Quaisquer ambiguidades em que elas estejam (a) na definição de "divisor de águas" (b) como as direções D8 são computadas ou (c) como as células horizontais (ou seja, sem uma direção D8 única) são manipuladas.)
whuber
0

Para refletir mais sobre essa questão, fiz uma análise de bacias hidrográficas em arco: fiz um DEM (preenchido), calculei a direção do fluxo e coloquei alguns pontos que correspondiam aos locais em uma rede de fluxos previamente calculada. Eu executei a ferramenta 'bacia hidrográfica' e ela me deu algumas bacias agradáveis, cobrindo praticamente a maior parte da área restante 'a montante' (como seria de esperar):

imagem da bacia hidrográfica

Codifiquei um algoritmo de pesquisa rápida em Python (como a resposta acima), que inspeciona a grade de direção do fluxo e 'segue' os caminhos do fluxo. Para cada nó, inspeciono os 8 vizinhos e, se um vizinho fluir para o nó atual, chamo a mesma função recursivamente com o nó vizinho que a entrada.

Código 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)

Eu executei essa função usando a mesma grade de entrada de direção de fluxo e um dos mesmos pontos. O problema é que, quando o arco retorna uma captação de cerca de 40000 células para esse ponto, meu algoritmo retorna apenas 72 células.

Alguém sabe o que estou fazendo de errado?

James
fonte