A fast and simple algorithm for calculating flow accumulation matrices from raster digital elevation

doi:10.1007/s11707-018-0725-9

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 ZHOU^1,²(

), Hongqiang WEI², Suhua FU^3,⁴

¹. Center for Information Geoscience, University of Electronic Science and Technology of China, Chengdu 611731, China
². School of Resources and Environment, University of Electronic Science and Technology of China, Chengdu 611731, China
³. 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
⁴. 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 Author(s): 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:

https://academic.hep.com.cn/fesci/EN/10.1007/s11707-018-0725-9
https://academic.hep.com.cn/fesci/EN/Y2019/V13/I2/317

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

[1]	Emre ÇOLAK, Filiz SUNAR. Spatial pattern analysis of post-fire damages in the Menderes District of Turkey[J]. Front. Earth Sci., 2020, 14(2): 446-461.
[2]	Evangelin Ramani SUJATHA. A spatial model for the assessment of debris flow susceptibility along the Kodaikkanal-Palani traffic corridor[J]. Front. Earth Sci., 2020, 14(2): 326-343.
[3]	Bartłomiej SZYPUŁA, Małgorzata WIECZOREK. Geomorphometric relief classification with the k-median method in the Silesian Upland, southern Poland[J]. Front. Earth Sci., 2020, 14(1): 152-170.
[4]	Shifa MA, Feng LIU, Chunlei MA, Xuemin OUYANG. Integrating logistic regression with ant colony optimization for smart urban growth modelling[J]. Front. Earth Sci., 2020, 14(1): 77-89.
[5]	Mohammad Saeid MIRAKHORLO, Majid RAHIMZADEGAN. Evaluating estimated sediment delivery by Revised Universal Soil Loss Equation (RUSLE) and Sediment Delivery Distributed (SEDD) in the Talar Watershed, Iran[J]. Front. Earth Sci., 2020, 14(1): 50-62.
[6]	Hongchun ZHU, Yuexue XU, Yu CHENG, Haiying LIU, Yipeng ZHAO. Landform classification based on optimal texture feature extraction from DEM data in Shandong Hilly Area, China[J]. Front. Earth Sci., 2019, 13(3): 641-655.
[7]	Jianjun CAO, Guoan TANG, Xuan FANG, Jilong LI, Yongjuan LIU, Yiting ZHANG, Ying ZHU, Fayuan LI. Terrain relief periods of loess landforms based on terrain profiles of the Loess Plateau in northern Shaanxi Province, China[J]. Front. Earth Sci., 2019, 13(2): 410-421.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	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.
[13]	Ş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.
[14]	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.
[15]	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.

Viewed

Full text

Abstract

Cited

Shared

Discussed