Please wait a minute...

Frontiers of Earth Science

Front. Earth Sci.    2019, Vol. 13 Issue (2) : 317-326     https://doi.org/10.1007/s11707-018-0725-9
RESEARCH ARTICLE |
A fast and simple algorithm for calculating flow accumulation matrices from raster digital elevation
Guiyun ZHOU1,2(), Hongqiang WEI2, Suhua FU3,4
1. Center for Information Geoscience, University of Electronic Science and Technology of China, Chengdu 611731, China
2. School of Resources and Environment, University of Electronic Science and Technology of China, Chengdu 611731, China
3. State Key Laboratory of Soil Erosion and Dryland Farming on the Loess Plateau, Institute of Soil and Water Conservation, Chinese Academy of Sciences, Yangling 712100, China
4. Faculty of Geographical Science, Beijing Normal University, Beijing 100875, China
Download: PDF(1355 KB)   HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

Calculating the flow accumulation matrix is an essential step for many hydrological and topographical analyses. This study gives an overview of the existing algorithms for flow accumulation calculations for single-flow direction matrices. A fast and simple algorithm for calculating flow accumulation matrices is proposed in this study. The algorithm identifies three types of cells in a flow direction matrix: source cells, intersection cells, and interior cells. It traverses all source cells and traces the downstream interior cells of each source cell until an intersection cell is encountered. An intersection cell is treated as an interior cell when its last drainage path is traced and the tracing continues with its downstream cells. Experiments are conducted on thirty datasets with a resolution of 3 m. Compared with the existing algorithms for flow accumulation calculation, the proposed algorithm is easy to implement, runs much faster than existing algorithms, and generally requires less memory space.

Keywords flow accumulation      flow direction      DEM      GIS     
Corresponding Authors: Guiyun ZHOU   
Just Accepted Date: 01 November 2018   Online First Date: 03 December 2018    Issue Date: 16 May 2019
 Cite this article:   
Guiyun ZHOU,Hongqiang WEI,Suhua FU. A fast and simple algorithm for calculating flow accumulation matrices from raster digital elevation[J]. Front. Earth Sci., 2019, 13(2): 317-326.
 URL:  
http://journal.hep.com.cn/fesci/EN/10.1007/s11707-018-0725-9
http://journal.hep.com.cn/fesci/EN/Y2019/V13/I2/317
Service
E-mail this article
E-mail Alert
RSS
Articles by authors
Guiyun ZHOU
Hongqiang WEI
Suhua FU
Symbol Description
FlowDir The input flow direction matrix
FlowAccu The output flow accumulation matrix
NextCell(c) A function returning a Boolean value. If the input cell c drains towards the outside of the DEM or it drains to a NODATA cell, the function returns a false value. Otherwise, the function returns a true value and cell c is updated as the downstream cell to which it drains
NIDP The matrix giving the number of immediately adjacent cells that flow into each cell
c, n Cells in matrices
Tab.1  Symbols used in the pseudocodes
Fig.1  Algorithm 1: compute the NIDP matrix from FlowDir matrix.
Fig.2  Algorithm 2: compute the FlowAccu matrix from FlowDir matrix using Wang’s algorithm.
Fig.3  Algorithm 3: compute the FlowAccu matrix from the FlowDir matrix using the BTI-based algorithm.
Fig.4  Algorithm 4: compute the FlowAccu matrix from FlowDir matrix using the recursive algorithm.
Fig.5  Algorithm 5: compute the FlowAccu matrix from the FlowDir matrix using the proposed algorithm.
Fig.6  A worked example of the proposed algorithm. (a) A 3×4 DEM with flow directions. (b) Initial NIDP matrix. (c) The flow accumulation matrix is initialized with one. (d) Cells H, D, C, and F are processed during the first round of tracing. The NIDP value of F is decreased by 1 and F is treated as an interior cell hereafter. (e) Cells J, I, E, and A are processed during the second round of tracing. The NIDP value of A is decreased by 1 and A is treated as an interior cell hereafter. (f) Cells L, K, G, F, B, and A are processed during the third round of tracing. The flow accumulation values of all cells are calculated after the tracing.
Fig.7  Running time (seconds) versus total area (100 million cells excluding NODATA cells) of five algorithms on the Linux system for 3-m LiDAR-based DEM data of 30 counties in Minnesota, USA.
Fig.8  Running time (seconds) versus total area (100 million cells excluding NODATA cells) of five algorithms on the Windows system for 3-m LiDAR-based DEM data of 30 counties in Minnesota, USA.
1 LArge, J Chase, PHalpin, LToma, J Vitter, DUrban, RWickremesinghe (2003). Efficient flow computation on massive grid terrain datasets. GeoInformatica, 7(4): 283–313
https://doi.org/10.1023/A:1025526421410
2 RBai, T Li, YHuang, JLi, G Wang (2015). An efficient and comprehensive method for drainage network extraction from DEM with billions of pixels using a size-balanced binary search tree. Geomorphology, 238: 56–67
https://doi.org/10.1016/j.geomorph.2015.02.028
3 RBarnes (2017). Parallel non-divergent flow accumulation for trillion cell digital elevation models on desktops or clusters. Environ Model Softw, 92: 202–212
https://doi.org/10.1016/j.envsoft.2017.02.022
4 RBarnes, C Lehman, DMulla (2014). An efficient assignment of drainage direction over flat surfaces in raster digital elevation models. Comput Geosci, 62: 128–135
https://doi.org/10.1016/j.cageo.2013.01.009
5 B PBuchanan, G N Nagle, M T Walter (2014). Long-term monitoring and assessment of a stream restoration project in central New York. River Res Appl, 30(2): 245–258
https://doi.org/10.1002/rra.2639
6 YChoi (2012). A new algorithm to calculate weighted flow-accumulation from a DEM by considering surface and underground stormwater infrastructure. Environ Model Softw, 30(0): 81–91
https://doi.org/10.1016/j.envsoft.2011.10.013
7 T GFreeman (1991). Calculating catchment area with divergent flow based on a regular grid. Comput Geosci, 17(3): 413–422
https://doi.org/10.1016/0098-3004(91)90048-I
8 SFu, B Liu, HLiu, LXu (2011). The effect of slope on interrill erosion at short slopes. Catena, 84(1–2): 29–34
https://doi.org/10.1016/j.catena.2010.08.013
9 JGarbrecht, L W Martz (1997). The assignment of drainage direction over flat surfaces in raster digital elevation models. J Hydrol (Amst), 193(1–4): 204–213
https://doi.org/10.1016/S0022-1694(96)03138-1
10 S KJenson, J O Domingue (1988). Extracting topographic structure from digital elevation data for geographic information system analysis. Photogramm Eng Remote Sensing, 54(11): 1593–1600
11 LJiang, G Tang, XLiu, XSong, J Yang, KLiu (2013). Parallel contributing area calculation with granularity control on massive grid terrain datasets. Comput Geosci, 60: 70–80
https://doi.org/10.1016/j.cageo.2013.07.003
12 FNardi, S Grimaldi, MSantini, APetroselli, LUbertini (2008). Hydrogeomorphic properties of simulated drainage patterns using digital elevation models: the flat area issue. Hydrol Sci J, 53(6): 1176–1193
https://doi.org/10.1623/hysj.53.6.1176
13 A DNobre, L A Cuartas, M Hodnett, C DRennó, GRodrigues, ASilveira, MWaterloo, SSaleska (2011). Height above the nearest drainage – A hydrologically relevant new terrain model. J Hydrol (Amst), 404(1–2): 13–29
https://doi.org/10.1016/j.jhydrol.2011.03.051
14 J FO’Callaghan, D MMark (1984). The extraction of drainage networks from digital elevation data. Comput Vis Graph Image Process, 28(3): 323–344
https://doi.org/10.1016/S0734-189X(84)80011-0
15 LOrtega, A Rueda (2010). Parallel drainage network computation on CUDA. Comput Geosci, 36(2): 171–178
https://doi.org/10.1016/j.cageo.2009.07.005
16 C ZQin, L Zhan (2012). Parallelizing flow-accumulation calculations on graphics processing units—From iterative DEM preprocessing algorithm to recursive multiple-flow-direction algorithm. Comput Geosci, 43: 7–16
https://doi.org/10.1016/j.cageo.2012.02.022
17 PQuinn, K Beven, PChevallier, OPlanchon (1991). The prediction of hillslope flow paths for distributed hydrological modelling using digital terrain models. Hydrol Processes, 5(1): 59–79
https://doi.org/10.1002/hyp.3360050106
18 CSu, W Yu, CFeng, CYu, Z Huang, XZhang (2015). An efficient algorithm for calculating drainage accumulation in digital elevation models based on the basin tree index. IEEE Geoscience and Remote Sensing Letters, 12(2): 424–428
https://doi.org/10.1109/LGRS.2014.2345561
19 LWang, H Liu (2006). An efficient method for identifying and filling surface depressions in digital elevation models for hydrologic analysis and modelling. Int J Geogr Inf Sci, 20(2): 193–213
https://doi.org/10.1080/13658810500433453
20 YWang, Y Liu, HXie, ZXiang (2011). A quick algorithm of counting flow accumulation matrix for deriving drainage networks from a DEM. In: Proceedings on the Third International Conference on Digital Image Processing
21 DYamazaki, C A Baugh, P D Bates, S Kanae, D EAlsdorf, TOki (2012). Adjustment of a spaceborne DEM for use in floodplain hydrodynamic modeling. J Hydrol (Amst), 436–437: 81–91
https://doi.org/10.1016/j.jhydrol.2012.02.045
22 YYao, X Shi (2015). Alternating scanning orders and combining algorithms to improve the efficiency of flow accumulation calculation. Int J Geogr Inf Sci, 29(7): 1214–1239
https://doi.org/10.1080/13658816.2015.1027209
23 HZhang, Q Yang, RLi, QLiu, D Moore, PHe, C JRitsema, VGeissen (2013). Extension of a GIS procedure for calculating the RUSLE equation LS factor. Comput Geosci, 52: 177–188
https://doi.org/10.1016/j.cageo.2012.09.027
24 GZhou, Z Sun, SFu (2016). An efficient variant of the priority-flood algorithm for filling depressions in raster digital elevation models. Comput Geosci, 90: 87–96
https://doi.org/10.1016/j.cageo.2016.02.021
Related articles from Frontiers Journals
[1] Xin YANG, Jiaming NA, Guoan TANG, Tingting WANG, Axing ZHU. Bank gully extraction from DEMs utilizing the geomorphologic features of a loess hilly area in China[J]. Front. Earth Sci., 2019, 13(1): 151-168.
[2] Xiaoping LIU, Shuli CHEN, Li ZHUO, Jun LI, Kangning HUANG. Multi-sensor image registration by combining local self-similarity matching and mutual information[J]. Front. Earth Sci., 2018, 12(4): 779-790.
[3] Bilaşco ŞTEFAN, Roşca SANDA, Fodorean IOAN, Vescan IULIU, Filip SORIN, Petrea DĂNUŢ. Quantitative evaluation of the risk induced by dominant geomorphological processes on different land uses, based on GIS spatial analysis models[J]. Front. Earth Sci., 2018, 12(2): 311-324.
[4] Parham PAHLAVANI, Behnaz BIGDELI. A mutual information-Dempster-Shafer based decision ensemble system for land cover classification of hyperspectral data[J]. Front. Earth Sci., 2017, 11(4): 774-783.
[5] Chong PENG, Hao XIAO, Yu LIU, Jingjing ZHANG. Economic structure and environmental quality and their impact on changing land use efficiency in China[J]. Front. Earth Sci., 2017, 11(2): 372-384.
[6] Ştefan BILAŞCO, Corina GOVOR, Sanda ROŞCA, Iuliu VESCAN, Sorin FILIP, Ioan FODOREAN. GIS model for identifying urban areas vulnerable to noise pollution: case study[J]. Front. Earth Sci., 2017, 11(2): 214-228.
[7] Jianqi ZHUANG,Jianbing PENG,Javed IQBAL,Tieming LIU,Na LIU,Yazhe LI,Penghui MA. Identification of landslide spatial distribution and susceptibility assessment in relation to topography in the Xi’an Region, Shaanxi Province, China[J]. Front. Earth Sci., 2015, 9(3): 449-462.
[8] Qing GU,Jun LI,Jinsong DENG,Yi LIN,Ligang MA,Chaofan WU,Ke WANG,Yang HONG. Eco-environmental vulnerability assessment for large drinking water resource: a case study of Qiandao Lake Area,China[J]. Front. Earth Sci., 2015, 9(3): 578-589.
[9] Yue LIU,Qiuming CHENG,Qinglin XIA,Xinqing WANG. The use of evidential belief functions for mineral potential mapping in the Nanling belt, South China[J]. Front. Earth Sci., 2015, 9(2): 342-354.
[10] Yingzhi LIN,Xiangzheng DENG,Xing LI,Enjun MA. Comparison of multinomial logistic regression and logistic regression: which is more efficient in allocating land use?[J]. Front. Earth Sci., 2014, 8(4): 512-523.
[11] Huan LI,Dingyi XU,Yan ZHAO. Peatland area change in the southern Altay Mountains over the last twenty years based on GIS and RS analysis[J]. Front. Earth Sci., 2014, 8(4): 558-563.
[12] Maotian LI,Jianzhong GE,Jens KAPPENBERG,Dagmar MUCH,Ohle NINO,Zhongyuan CHEN. Morphodynamic processes of the Elbe River estuary, Germany: the Coriolis effect, tidal asymmetry and human dredging[J]. Front. Earth Sci., 2014, 8(2): 181-189.
[13] Murugesan BAGYARAJ, Thirunavukkarasu RAMKUMAR, Senapathi VENKATRAMANAN, Balasubramanian GURUGNANAM. Application of remote sensing and GIS analysis for identifying groundwater potential zone in parts of Kodaikanal Taluk, South India[J]. Front Earth Sci, 2013, 7(1): 65-75.
[14] Prabin KAYASTHA. Application of fuzzy logic approach for landslide susceptibility mapping in Garuwa sub-basin, East Nepal[J]. Front Earth Sci, 2012, 6(4): 420-432.
[15] Hualin XIE, Chih-Chun KUNG, Yuluan ZHAO. Spatial disparities of regional forest land change based on ESDA and GIS at the county level in Beijing-Tianjin-Hebei area[J]. Front Earth Sci, 2012, 6(4): 445-452.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed