一种基于横向或纵向扫描线处理的填洼算法  

A sweep-line DEM depression-filling algorithm fit for CUDA based parallel calculation

作　　者：刘永和[1] 冯锦明[2] 邵月红[3] 徐精文[4] 

机构地区：[1]河南理工大学资源环境学院,河南焦作454000 [2]中国科学院东亚区域气候-环境重点实验室/全球变化东亚区域研究中心,中国科学院大气物理研究所,北京100029 [3]南京信息工程大学应用水文气象研究院,南京210044 [4]四川农业大学资源环境学院,四川雅安625014

出　　处：《测绘科学》2015年第2期145-149,共5页Science of Surveying and Mapping

基　　金：国家自然科学基金项目(41105074,41275108);中科院数字地球重点实验室开放基金项目(2011LDE010);河南理工大学博士基金项目(B2011-038)

摘　　要：针对传统Planchou&Darbous算法采用递归执行方式导致处理效率低下等问题,该文提出了一种适合基于CUDA的GPU并行执行的DEM洼地填充算法。此算法采用淹没-排水思路,多次推进式扫描完成排水;在串行执行和并行执行两种方式下,算法处理有所差异,其中串行算法代码更短;串行算法的时间复杂度为O(n),测试结果表明串行执行时快于Planchon&Darboux算法,且在CUDA环境下的并行执行用时不到串行执行用时的一半。算法思路简单,易于编程实现。A DEM depression-filling algorithm fit for CUDA based parallel calculation was proposed in the paper.Based on the idea of flooding and drainage paradigm introduced by Planchon and Darboux,this algorithm avoided the recursive drainage process of flood water by using multiple sweep-line drainage process.The algorithm is different from the serial processing and the parallel processing,and the program code for the serial processing is shorter comparatively.The time complexity of the serial processing algorithm is O（n）.Some tests indicated that the serial processing of the algorithm would be faster than the PlanchonDarboux algorithm,and the parallel processing of the algorithm in CUDA spent less than half of the time spent for serial processing on the same dataset.This new algorithm could be a very simple idea and easy to implement.

关 键 词：CUDA 并行计算 洼地填充算法 数字高程模型 水文模型 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]