一种大区域洪水淹没范围快速提取的分块种子蔓延算法
2015-03-22杨启贵王汉东
杨启贵， 王汉东
(长江水利委员会 长江勘测规划设计研究有限责任公司， 武汉 430010)
一种大区域洪水淹没范围快速提取的分块种子蔓延算法
杨启贵*， 王汉东
(长江水利委员会 长江勘测规划设计研究有限责任公司， 武汉 430010)
快速、准确的获取洪水淹没范围是洪灾损失评估和防洪决策的核心环节.常规种子蔓延算法由于存在大量的递归运算，效率不高且无法处理大区域海量地形数据.针对上述问题，提出了一种大区域洪水淹没范围快速提取的分块种子蔓延算法，将研究区域分成预先设定大小的块，种子蔓延以块为单位进行组织处理，块的数量远小于原始DEM格网单元的数量.该算法有效解决了常规种子蔓延算法递归运算层次过深的问题，可实现大区域海量数据在给定淹没洪水水位条件下的淹没区快速提取.
数字高程模型； 种子蔓延算法； 数据分块； 淹没分析
洪水淹没分析是水文预测预报、防洪调度以及洪涝灾害评估的一项重要内容，快速、准确、科学地获取淹没区范围是洪灾损失评估及防洪决策的核心环节[1].将GIS技术与水文水动力学模型相结合进行洪水淹没灾害评估，已成为防洪减灾领域的一个重要研究课题[2-13].基于DEM数据的洪水淹没分析包括两类方法：一类是结合水文水动力学模型构建洪水演进模型[6-12]，另一类是根据设定的静态水位面计算淹没范围[2-4，14-19].洪水演进模型可以较为精确地模拟洪水淹没过程，但是需要较多的水文水力学参数条件，建模过程复杂.基于给定静水位的洪水淹没分析是洪水淹没达到最终平衡状态的近似模拟，因其计算简单，能快速确定淹没范围和水深分布，因此得到广泛应用.静水位下洪水淹没分析主要分为两种情形[2-4]：第1种情形称为无源淹没，凡是高程值低于给定水位的点，皆计入淹没区，相当于整个区域均匀降水；第2种情形称为有源淹没，需要考虑水流连通性的问题，洪水只能淹没到它能流到的地方，相当于高发洪水向邻域泛滥.对于环形山洼地，第1种淹没计算可能导致环形山内外都形成淹没区，而在第2种情形中，外来的洪水若未及山顶，则只能在环形山外围形成环形淹没区，而环形山内部洼地不会被淹没.
有源淹没常用的算法是种子蔓延算法[2-4，14-19]，种子蔓延算法是一种基于区域空间特征的扩散探测算法，其核心思想是将给定的种子点赋予特定的属性，然后在区域上4方向或8方向扩散，求取满足给定条件且具有连通特性的点.利用种子蔓延算法计算淹没区，就是按给定水位条件，求取满足精度、连通性要求的点的集合，该集合给出的连续平面就是淹没区范围.种子蔓延算法主要采用递归的方式进行扩展探测，算法的效率受制于递归的层次，递归层次太深会导致算法效率降低，甚至导致程序崩溃，因此，无法提取大区域的洪水淹没区.降低递归层次是种子蔓延算法应用于大区域海量数据洪水淹没需要解决的关键问题.刘仁义等人采用“跳步探测”的方式，通过增加种子点探测步距来提高计算效率[3]；丁志雄等人预先划定大致的淹没范围，通过缩小研究区域来提高计算效率[4]；张煜、沈定涛等人针对海量地形数据，提出了基于数据压缩的淹没范围提取算法[14-15].增加探测步距其实是降低空间分辨率，即增加格网单元的尺寸，会降低分析结果的精度；预先判断洪水的大致淹没范围常常是比较困难的，特别是对于地势相对平坦的研究区域.本文从降低传统种子蔓延算法递归层次的问题出发，提出基于分块的种子蔓延算法，将研究区域分成小的块，在各个块上分别运用种子蔓延算法提取淹没区域，可有效降低算法执行过程中的递归层次.算法不受研究区域大小的限制，可用于提取大区域洪水淹没范围.
1 分块种子蔓延算法
1.1 算法基本思想
种子蔓延算法的递归层次与地形数据量有很大关系，随着DEM数据行列数的增大，种子蔓延算法的递归层次急剧增加.为了降低常规种子蔓延算法的递归层次，分块种子蔓延算法首先将研究区域划分成预先设定大小的块，递归运算只在块内进行.分块种子蔓延算法的基本思想如图1所示.
图1 分块种子蔓延算法基本思想Fig.1 The basic logic pattern of blocking seed spread algorithm
在对DEM数据进行分块处理时，可以根据计算机处理能力确定合适的块大小，块太小会导致数据块的数据量太多，影响计算处理效率；块太大，则有可能导致种子蔓延算法的递归层次太深，影响算法性能，一般情况下可以设定块的大小为128×128或256×256.
1.2 DEM数据分块组织
DEM数据分块可以采用灵活的策略，在DEM数据量不是很大的情况下，可以一次性读入DEM数据，然后在内存中进行分块；如果DEM数据量很大，达到GB级，则可以根据计算机硬件处理能力，分成多个可以一次性读入的小的数据文件，然后在内存中划分块.
块作为种子蔓延算法处理的基本单元，需要记录3类信息：一是块的编号、起始和终止行列号，用于定位和获取该块内各个DEM格网单元的高程信息；二是该块的种子单元链表，记录该块内进行种子蔓延计算的起始种子单元；三是块的8个邻接块编号，记录该块与相邻块的拓扑关系.块的数据结构如下：
struct DataBlock
{
int BlockID=0; //块编号
int SRow=0; //块起始行号
int SColumn=0; //块起始列号
int ERow=0; //块末行号
int EColumn=0; //块末列号
List
int BlockID_L=0; // 块的左邻接块编号
int BlockID_R=0; //块的右邻接块编号
int BlockID_T=0; //块的顶邻接块编号
int BlockID_B=0; //块的底邻接块编号
int BlockID_LT=0; // 块的左上邻接块编号
int BlockID_RT=0; // 块的右上邻接块编号
int BlockID_LB=0; // 块的左下邻接块编号
int BlockID_RB=0; // 块的右下邻接块编号
}
struct DataCell
{
int Row=0; //单元格行号
int Column=0; //单元格列号
}
1.3 种子块的生成
将洪水淹没种子点所在的块作为初始种子块，新的种子块从当前种子块的8邻接块中产生.
① 如果当前种子块提取的淹没区域没有达到块的边界，则当前种子块的邻接块均不能作为新的种子块，如图2所示.
② 如果当前种子块提取的淹没区域达到种子块的边界，则需要根据相邻边界单元格的高程及给定的洪水位，判断当前块的水流能否流向相邻的块.如果邻接块的边界单元格满足淹没条件，则该邻接块是下一个种子块，否则不是.如图3所示，块1是当前种子块，给定的洪水位是5，提取的淹没区域达到该块的边界，块3与块1的淹没区相邻，且相邻的单元格高程值为3，低于给定的洪水位，洪水可以从块1流向块3，则块3是下一个新的种子块；块2也与块1的淹没区相邻，但是相邻的单元格高程均高于给定的洪水位，说明洪水无法从块1流向块2，则根据块1的淹没计算结果不能将块2作为下一个种子块.
图2 没有达到种子块的边界，邻接块不能作为新的种子块Fig.2 The current seed block without neighboring seed blocks
图3 从当前种子块的邻接块产生新的种子块Fig.3 Finding the neighboring seed block of current seed block by using seed spread algorithm
新的种子块一旦确定，则边界上满足淹没条件的所有单元格均作为该块进行种子蔓延算法计算淹没范围的种子点.
1.4 种子块淹没范围计算处理策略
对于单个种子块来说，根据种子块的位置坐标读取该种子块各格网单元高程值；种子块结构体记录了该种子块的淹没种子点列表，因此可以采用种子蔓延算法快速计算得到该种子块的淹没范围.
可以采用两种策略来提取整个研究区域淹没范围，第1种策略是采用递归计算的方法，建立种子块队列，将淹没种子点所在的块作为初始种子块添加到种子队列.从种子队列中取出一个种子块进行计算，根据种子块的淹没计算结果产生新的种子块并添加到种子队列，依次递归进行，直到种子队列为空，计算得到的结果就是整个研究区域的淹没范围.算法计算流程如下：
(1)按照设定的块大小对研究区域DEM数据进行分块；
(2)构建种子块队列，并将种子点所在的块作为种子块添加到种子块队列；
(3)从种子块队列中取出种子块作为当前种子块，对当前种子块运用种子蔓延算法提取淹没区域；
(4)根据当前种子块淹没区域计算结果，搜寻新的种子块，并添加到种子块队列.新的种子块从与当前种子块相邻接的块中产生；
(5)判断种子块队列是否为空，如果不为空，则转到(3)，否则转到(6)；
(6)计算结束，提取所有块的淹没区域，得到整个研究区域的淹没范围.
算法总体流程如图4所示.
图4 基于递归计算的分块种子蔓延算法计算流程Fig.4 The blocking seed spread algorithm flowchart based on recursive calculation
第2种策略是预计算方法.第1步根据给定的洪水水位对所有的分块进行计算，提取每一个块内潜在的淹没区域；第2步检查潜在淹没区域的连通性，剔除无法连通的潜在淹没区域.淹没区域提取及连通性判断可采用四方向追踪法进行边界追踪[20]，算法计算流程如图5所示.
图5 基于块预计算的分块种子蔓延算法计算流程Fig.5 The blocking seed spread algorithm flowchart based on prior block calculation
如果整个区域淹没范围较小(如山谷陡峭狭窄地区)，很多块不需要计算，直接采用递归计算可以得到计算结果，处理简单，计算效率高；如果研究区域属于平坦地区(如平原或城市区域)，产生大范围的淹没，大多数块都会参与计算，则采用块预计算的处理策略可以提高计算效率.如果初始淹没种子点有多个，也可以直接采用块预计算的处理策略，保证每个块都可以处理到.在算法的实际应用中可以针对具体情况选用合适的处理策略.
2 分块种子蔓延算法在流域防洪调度三维仿真系统中的应用
流域防洪调度三维仿真系统以流域数字高程模型和高分辨率遥感影像为基础，利用三维GIS、虚拟现实、数据库技术构建流域防洪调度三维场景和综合数据管理平台，实现三维虚拟环境下的水库防洪调度仿真、洪水演进仿真、水库库容实时计算、水库下游河道洪水演进与淹没分析、工程监测信息查询、工程运行数据管理、工程图档管理、工程运行管理三维动态仿真等工程防洪及运行管理工作的数字化管理，达到优化防洪调度、降低防洪风险、提高管理水平的目的.乌江下游DEM数据包含网格的行列数为6479×3915，格网大小为30 m×30 m，图6是模拟乌江彭水水电站发生溃坝，最大洪峰水位267.79 m时，乌江下游的洪水淹没范围的计算结果.采用分块种子蔓延算法，设定数据分块大小为128×128，将整个DEM数据分成51×31块，洪水水位为267.79 m，淹没种子点为彭水水库坝址点(单种子点)，由于乌江两岸地形起伏大，淹没主要集中于沿江的狭小空间，故采用递归计算的处理策略计算分块淹没范围.
图6 乌江下游洪水淹没范围计算结果Fig.6 The flood submerge area of Wujiang River Downstream
3 结束语
快速获取洪水淹没范围对防洪减灾具有重要意义，针对常规种子蔓延算法递归层次深、易导致计算失败以及不能处理大范围淹没区域等问题，本文提出了改进的分块种子蔓延算法，并针对山谷狭窄区域和平坦区域，提出了两种淹没区域提取策略.在数据块上运行种子蔓延算法提取该块的淹没范围，针对每个DEM格网单元进行遍历判断，因此洪水淹没范围提取的精度主要取决于DEM数据的精度.数据分块是影响算法性能的一个重要因素，应选择合适数据分块尺寸，保证每个块上能高效运行种子蔓延算法，并使得块的数量尽可能小.算法采用C#语言实现，并在流域防洪调度三维仿真系统的洪水淹没分析模块中得到应用，实践表明，该算法不受研究区域范围限制，可以用于大区域淹没范围的快速提取.
[1] 江 岭， 汤国安， 王 春， 等. 基于FDEM的洪水淹没区精确快速提取[J]. 地球信息科学学报， 2013， 15(1):68-74．
[2] 郭利华， 龙 毅.基于DEM的洪水淹没分析[J].测绘通报， 2002(11):25-27．
[3] 刘仁义， 刘 南. 一种基于数字高程模型DEM的淹没区灾害评估方法[J]. 中国图像图形学报， 2001， 6A(2):118-122．
[4] 丁志雄， 李纪人， 李 琳. 基于GIS格网模型的洪水淹没分析方法[J]. 水利学报， 2004(6):56-60．
[5] 黄少华， 丁志良， 王汉东， 等. 基于三维GIS的水库洪水调度模拟系统研究[J]. 人民长江， 2013， 44(7):95-99．
[6] Reggiani P， Weerts A H. A bayesian approach to decision-making under uncertainty: an application to real-time Forecasting in the river rhine[J]. Journal of Hydrology， 2008， 356(1-2): 56-69．
[7] 谢俊举， 李亚琦. 基于洪水演进数值模拟的溃坝危害性快速评估[J].灾害学， 2011， 26(2): 31-34．
[8] Liang Qiuhua. Flood simulation using a well-balanced shallow flow model[J]. Journal of Hydraulic Engineering， 2010，136(9):669-675．
[9] 李致家， 张 珂， 姚 成. 基于GIS的DEM和分布式水文模型的应用比较[J].水利学报，2006，37(8):1022-1028．
[10] Hashemi B L，Mostafavi M A， Pouliot J. 3D Dynamic Simulation within GIS in Support of Disaster Management[C]. //Lecture Notes in Geoinformation and Cartography. Berlin:Springer Berlin Heidelberg， 2007:165-184．
[11] Van Der Knijff J M， Younis J， De Roo A P J. LISFLOOD: A GIS-based distributed model for river basin scale water balance and flood simulation[J]. Internaional Journal of Geographical Information Science，2010， 24(2): 189-212．
[12] 张秉仁， 邱殿明， 冯雨林. 面向地学过程的源发型洪水演进仿真技术[J].吉林大学学报:地球科学版， 2008， 38(5): 908-912．
[13] 李 辉， 黄进良， 王立辉， 等. GIS环境下基于GDEM的丹江口库区流域自动提取方法的研究[J].华中师范大学学报：自然科学版， 2011， 45(4): 655-658．
[14] 张 煜， 沈定涛， 叶 松， 等. 基于压缩的大地形数据分析方法研究[J]. 人民长江， 2014， 45(2): 60-62．
[15] 沈定涛， 王结臣， 张 煜， 等. 一种面向海量数字高程模型数据的洪水淹没区快速生成算法[J].测绘学报，2014， 43(6): 645-652．
[16] 张东华， 刘 荣， 张咏新， 等. 一种基于DEM的洪水有源淹没算法的设计与实现[J].华东理工大学学报：自然科学版,2009， 32(2): 181-184．
[17] 孙 海， 王 乘. 利用DEM的“环形”洪水淹没算法研究[J].武汉大学学报：信息科学版， 2009， 34(8):948-951．
[18] 陈 静， 袁思佳， 曾方敏. 三维虚拟地球中有源洪水淹没分析算法[J].武汉大学学报：信息科学版， 2014， 39(4): 492-495．
[19] 丁雨淋， 杜志强， 朱 庆， 等. 洪水淹没分析中的自适应逐点水位修正算法[J].测绘学报， 2013， 42(4): 546-553．
[20] 谢顺平， 都金康， 王腊春， 等. 基于游程编码的GIS栅格数据矢量化方法[J].测绘学报， 2004，33(4): 323-327．
A blocking seed spread algorithm for fast extracting flood submerged area based on massive DEM data
YANG Qigui, WANG Handong
(Changjiang Institute of Survey， Planning， Design and Research， Changjiang Water Resources Commission， Wuhan 430010)
Fast and accurate data extraction of flood submerged area is the key factor of flood disaster assessment and flood control policy. Because of its great amount of recursive processing， conventional seed spread algorithm has low efficiency and high deficiency in processing large area terrain data. This paper provides a new blocking seed spread algorithm which partitions the original terrain into small blocks with predesigned size. The recursive processing of algorithm is based on the predesigned blocks which are much fewer than the original terrain cells in amount; therefore this new algorithm improves data processing efficiency significantly. It is demonstrated that the proposed approach is able to be employed to extract flood submerged area of large terrain data with given flood water level fast and accurately．
Digital Elevation Model (DEM); seed spread algorithm; data partition; flood analysis
2015-04-03.
水利部科技推广计划项目(TG1418)；长江勘测规划设计研究有限责任公司自主科研项目(CX2013Z09).
1000-1190(2015)04-0603-05
TP391< class="emphasis_bold">文献标识码： A
A
*E-mail:yangqigui@cjwsjy.com.cn.
