Determinação da rede de drenagem em grandes terrenos armazenados em memória externa

Abstract

Este trabalho apresenta um algoritmo muito eficiente, chamado EMFlow, para o cál- culo da rede de drenagem em grandes terrenos armazenados em memória externa. A rede de drenagem retrata o caminho que a água segue através do terreno (direção de fluxo) e a quantidade de água que flui por cada célula do terreno (fluxo acumulado). Como é conhecido, devido ao rápido aumento da disponibilidade de dados de alta resolução da superfície terrestre, os algoritmos de memória interna não são capazes de processar de forma eficiente esse volume de dados na maioria dos computadores. Portanto, otimizar os algoritmos simultaneamente para a movimentação de dados e processamento tem sido um desafio para os sistemas de informação geográfica (SIG). O EMFlow calcula a direção de fluxo usando uma adaptação do método RWFlood que utiliza um processo de inundação para obtenção da direção de fluxo e o fluxo acumulado é calculado com base em um método bastante eficiente proposto por Haverkort e Janssen (2012). Para reduzir o número total de operações de entrada e saída, o EMFlow adota uma nova estratégia de subdivisão do terrenos em ilhas que são processadas separadamente e agrupa as células do terreno em blocos que são armazenados em uma estrutura de dados especial gerenciada como uma memória cache. O tempo de execução do EMFlow foi comparado com os dois mais recentes e eficientes métodos descritos na literatura: TerraFlow e r.watershed.seg e foi, em média, 27 vezes mais rápido que ambos. Como o processamento de grandes terrenos pode levar horas, essa melhora é muito significativa.

This work presents a very efficient algorithm, named EMFlow, and its implementa- tion to compute the drainage network on huge terrains stored in external memory. The drainage network of a terrain delineates the path that water flows through the terrain (the flow direction) and the amount of water that flows into each terrain cell (the flow accumulation). As it is known, due to the fast increase in the volume of high resolution terrestrial data available, the internal memory algorithms do not run well for huge terrains on most computers and, thus, optimizing the massive data processing algorithm simultaneously for data movement and computation has been a challenge for GIS (Geographic Information System). In EMFlow, the flow direc- tion is computed using an adaptation of method RWFlood which uses a flooding process to obtain this direction and the flow accumulation is computed based on a very fast method proposed by Haverkort and Janssen (2012). To reduce the total number of I/O operations, EMFlow adopts a new strategy to subdivide the terrains into islands which are processed separately and the terrain cells are grouped into blocks, which are stored in a special data structure managed as a cache memory. The EMFlow execution time was compared against the two most recent and most efficient published methods: TerraFlow and r.watershed.seg and it was, in average, 27 times faster than both methods. Since processing large datasets can take hours, this improvement is very significant.