Alternating scanning orders and combining algorithms to improve the efficiency of flow accumulation calculation

CORC > 成都山地灾害与环境研究所 > 中国科学院水利部成都山地灾害与环境研究所 > 数字山地与遥感应用中心

	Alternating scanning orders and combining algorithms to improve the efficiency of flow accumulation calculation
	Yao, Yuanzhi1,2 ; Shi, Xun 3
刊名	INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE
	2015-07-03
卷号	29 期号:7 页码:1214-1239
关键词	terrain analysis geocomputation digital elevation or terrain models
ISSN号	1365-8816
通讯作者	Xun Shi
英文摘要	Conventionally, a raster operation that needs to scan the entire image employs only one scanning order (i.e., single scanning order (SSO)), and the scan usually runs from upper left to lower right and row by row. We explore the idea of alternately applying multiple scanning orders (MSO) to raster operations that are based on the local direction, using the flow accumulation (FA) calculation as an example. We constructed several FA methods based on MSO, and compared them with those widely used methods. Our comparison includes experiments over digital elevation models (DEMs) of different landforms and DEMs of different resolutions. For each DEM, we calculated both single-direction FA (SD-FA) and multi-direction FA (MD-FA). In the theoretical aspect, we deducted the time complexity of an MSO sequential algorithm (MSOsq) for FA based on empirical equations in hydrology. Findings from the experiments include the following: (1) an MSO-based method is generally superior to its counterpart SSO-based method. (2) The advantage of MSO is more significant in the SD-FA calculation than in the MD-FA calculation. (3) For SD-FA, the best method among the compared methods is the one that combines the MSOsq and the depth-first algorithm. This method surpasses the commonly recommended dependency graph algorithm, in both speed and memory use. (4) The differences between the compared methods are not sensitive to specific landforms. (5) For SD-FA, the advantage of MSO-based methods is more obvious in a higher DEM resolution, but this does not apply to MD-FA.
WOS标题词	Science & Technology ; Social Sciences ; Technology ; Physical Sciences
类目[WOS]	Computer Science, Information Systems ; Geography ; Geography, Physical ; Information Science & Library Science
研究领域[WOS]	Computer Science ; Geography ; Physical Geography ; Information Science & Library Science
关键词[WOS]	DIGITAL ELEVATION MODELS ; DIRECTION ALGORITHM ; EXTRACTION ; NETWORKS ; PATHS ; AREA
收录类别	SCI ; SSCI
原文出处	http://www.tandfonline.com/doi/full/10.1080/13658816.2015.1027209#abstract
语种	英语
WOS记录号	WOS:000359723200007
内容类型	期刊论文
源URL	[http://ir.imde.ac.cn/handle/131551/8023]
专题	成都山地灾害与环境研究所_数字山地与遥感应用中心
作者单位	1.Chinese Acad Sci, Inst Mt Hazards & Environm, Chengdu, Peoples R China 2.Auburn Univ, Sch Forestry & Wildlife Sci, Auburn, AL 36849 USA 3.Dartmouth Coll, Dept Geog, Hanover, NH 03755 USA
推荐引用方式 GB/T 7714	Yao, Yuanzhi,Shi, Xun. Alternating scanning orders and combining algorithms to improve the efficiency of flow accumulation calculation[J]. INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE,2015,29(7):1214-1239.
APA	Yao, Yuanzhi,&Shi, Xun.(2015).Alternating scanning orders and combining algorithms to improve the efficiency of flow accumulation calculation.INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE,29(7),1214-1239.
MLA	Yao, Yuanzhi,et al."Alternating scanning orders and combining algorithms to improve the efficiency of flow accumulation calculation".INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE 29.7(2015):1214-1239.