运用三维Douglas-Peucker算法提取DEM地形特征

朱雪坚，叶远智，汤国安

(1. 浙江省地理信息中心，浙江 杭州 310012; 2. 南京师范大学 虚拟地理环境教育部重点实验室，江苏 南京 210046)

一、前 言

地形特征的提取是近年研究的一个热点。利用Douglas-Peucker算法提取地形特征具有效率高、提取效果好等优点，因此，该算法广泛应用于矢量数据的压缩和自动综合中。根据算法针对的数据不同，可以将该算法分为两大类：二维Douglas-Peucker算法和三维Douglas-Peucker算法。文献[1—3]针对二维Douglas-Peucker算法的特点，对其判断条件等进行优化改进，加快了算法的效率，提高了筛选精度。在三维算法方面，费立凡等在二维Douglas-Peucker算法的基础上，将原来的基线换成基面，点到线的距离换成点到面的距离，从而实现了从二维到三维数据化简的扩展，以及该算法在DEM地形特征提取和地形自动综合中的应用[4-5]。

Douglas-Peucker算法从二维数据向三维数据化简扩展的两个关键是初始基面的选取和扫描方向的确定。对于海量的DEM离散数据而言，采用稍有差异的起始基面进行三维道格拉斯算法提取地形特征，在进行多次迭代后提取的地形特征点将趋于接近，其结果不会有很大差异，但在局部部分则存在明显差异。另外，不同的扫描方向对提取的地形特征点也有重要影响。本文在原有三维Douglas-Peucker算法的基础上，对初始基面、扫描方向等进行了改进与优化，并对提取DEM地形特征点的方法进行了探讨。

二、算法研究

1. 样区与数据

选择陕北黄土高原的黄龙山、绥德、神木3个不同的地貌类型区作为试验样区，分别代表了中山区、丘陵沟壑区、微丘区3种不同的地形复杂度。

以国家1∶1万DEM(5 m分辨率)数据为基本数据源。由于Douglas-Peucker算法针对的是散点数据，因此，将所有样区的DEM数据转换成含(X，Y，Z)三维坐标的散点数据，作为试验的原始数据(见表1)。

表1 试验样区数据

2. 算法改进

三维Douglas-Peucker算法涉及初始原点的选取和扫描方向的确定，不仅影响算法效率，而且影响提取结果。本文就这一问题探讨不同的初始基面及不同的扫描方向对地形特征点提取结果的影响程度。文献[4—5]中对三维Douglas-Peucker算法已有详细阐述，本文将着重阐述改进方面(如图1所示)。

图1 算法流程图

1) 初始基面。利用松弛原理人为选定原点、初始锚点和初始漂浮点，可以大大加快算法运行的效率。但若原点、初始锚点和初始漂浮点中含有无值点或全为无值点(ArcGIS中高程值为-9999的点)，原始算法将-9999认为是一个有效值参与计算，使得初始基面“远离”DEM地表，不具备足够的特征去“审视”整个DEM地表，从而不能提取令人满意的地形特征点。本试验通过改变原点、初始锚点和初始漂浮点的初始高程，模拟不同的初始基面对提取的地形特征点的影响。试验选用的3个初始基面分别为：高程全为0的平面，下文中称为0基面；高程全为该区域的平均高程，下文中称为均值面；高程分别为区域内的最小高程和平均高程，用以模拟地形走势的基面，下文中称为趋势面。以此实现初始基面向DEM地表逐步逼近的过程。对于每个基面，采用3、10、20三个域值分别进行提取。

2) 扫描方向。算法要依据一定的顺序对DEM数据进行有序扫描，而三维离散点是无序的。使用该算法进行地形特征提取时，须对三维离散点进行排序。而规则格网的DEM本身就具有行、列及对角线等方向，因此，文献[4—5]以规则格网DEM中原有的行、列两个方向为两次不同的扫描顺序，按照先行(列)后列(行)的顺序连续进行压缩，省掉了对三维离散点的排序过程，算法效率得到很大的提高。但是，行扫描获得的是地形纵向特征点，列扫描获得的是地形横向特征点，同理，正反对角线的扫描也存在相似的特点。由于地貌自相似性的存在，一定的区域地貌形态具有一定的方向性，当其与扫描方向之间存在一定的角度时，会导致某些重要的地形特征点在连续两次(或多次)扫描时被忽略，从而丢失了一些局部的重要地形特征点。因此，行、列两次扫描及正反对角线方向的扫描都应基于原始数据进行。

三、试验结果与分析

1. 基面的影响

本文分别利用0基面、均值面和趋势面提取地形特征点，提取后的数据量见表2。试验结果显示：0基面与均值面、趋势面提取后所得数据量差异较大，而均值面与趋势面之间的差异非常小。从图2(a)、图2(b)可以看出，与均值面相比，0基面丢失了大量的地形特征点，且在空间分布上，均值面所得的地形特征点分布更趋均匀和合理；图2(b)、图2(c)为均值面与趋势面之间的比较，可以发现，两者无论在所得到的地形特征点还是在空间分布上，基本上都一致。

以上试验结果显示，初始基面的选取对不同地貌类型提取的DEM地形特征点都有重要影响，当选取的初始基面“远离”整体DEM地表时，基面“审视”DEM全局特征的特点随之减弱，将会损失部分非常重要的地形特征点，而这部分地形特征点主要位于左下角区域。离左下角越远的区域，基面的影响越小，这就使得提取的地形特征点在空间分布上较不均匀，如选取0基面为初始基面对绥德样区进行提取时，提取得到的地形特征点呈现沿地形走势、高密低疏的特点；当初始基面的选取越来越逼近DEM所表示的地表时，将能消除初始基面对局部区域(尤其是左下角区域)的影响，使提取的地形特征点在空间分布上更趋均匀与合理。

表2 不同基面、阈值下提取地形特征点后的数据量 kB

图2 不同基面提取地形特征点结果对比(阈值为20)

2. 扫描方向的影响

分别用行、列、正对角线和反对角线4个扫描方向对原始DEM数据进行扫描。从图3中可以看出，行扫描得到的地形特征点基本上保留的是垂直方向上的，而损失了大量水平方向上的地形特征点；列扫描得到的地形特征点基本上保留的是水平方向上的，而损失了大量垂直方向上的地形特征点。当两者求并集后，绝大部分的地形特征均被很好地识别和保留。两对角线方向扫描数据与行列方向扫描数据提取的地形特征点结果呈现很大的不同，但与行列方向扫描类似，正对角线方向扫描数据得到的是呈现一定反对角线方向分布的特征点，而反对角线方向扫描数据得到的是呈现一定正对角线方向分布的特征点。

其原因为，在进行行扫描时，当点到面的最大距离小于给定的阈值时，删除点的方向是水平方向上的，因此水平方向上的特征点保留得较差；同理，进行列扫描时，垂直向上的特征点也保留得较差；基于与行列扫描同样原因，正对角方向扫描时，规则格网DEM中正对角方向同一列、相邻行之间的高程相似性可能会被强加的逻辑远离所掩盖，从而会丢掉一些行向本可保留的、有价值的点。在相同阈值下，反对角方向扫描的缺点也可类推。综上所述，基于DEM提取地形特征点，由于三维道格拉斯算法方向性问题的存在，单一的某个扫描方向并不能很好地提取地形特征点，需要对原始数据作多个方向扫描，并对各方向扫描结果进行并集处理，才能比较完整地提取地形特征点。

图3 不同扫描方向结果对比(阈值为20)

四、结束语

在黄龙山、绥德和神木3个样区的试验结果表明，0基面和均值面提取的地形特征点存在较大的差异，而均值面与趋势面几乎得到相同的结果，基本保留了地形特征点。因此，从地形简化程度及特征点保留等方面考虑，选取均值面或趋势面作为特征点选取的起始基面，都能比较完整地提取地形特征点。

基于三维Douglas-Peucker算法提取的地形特征点具有方向依赖性，文中以水平、垂直及两对角线4个方向为提取地形特征点的扫描方向。试验结果表明，仅考虑单一方向的扫描都不能很好地提取地形特征点，需要对多个扫描方向提取的地形特征点进行合并处理，才能比较完全地提取地形特征点。因此，在利用改进算法进行地形特征提取时，应进行多方向扫描，提取不同的地形特征点，之后求各个扫描结果的并集，才能更加完整地提取地形特征点，为以后的地貌综合做好准备。

参考文献：

[1] 刘晓红,李树军.矢量数据压缩的角度分段道格拉斯算法研究[J].四川测绘,2005,28(2):51-52.

[2] 杨得志,王杰臣,闾国年.矢量数据压缩的Douglas-Peucker算法的实现与改进[J].测绘通报,2002(7):18-22.

[3] REN Yingchao, YANG Chongjun, YU Zhanfu,et al.A Way to Speed Up Buffer Generalization by Douglas-Peucker Algorithm[C]∥Proceedings of IGARSS. Anchorage, AK:IEEE, 2004.

[4] 费立凡,何津,马晨燕,等.3维Douglas-Peucker算法及其在DEM自动综合中的应用研究[J].测绘学报,2006,35(3):278-284.

[5] 何津,费立凡.再论三维Douglas-Peucker算法及其在DEM 综合中的应用[J].武汉大学学报:信息科学版,2008,33(2):160-163.

[6] 闾国年,钱亚东,陈钟明.基于栅格数字高程模型提取特征地貌技术研究[J].地理学报,1998,53(6):562-569.

[7] DOUGLAS D H， PEUCKER T K.Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature [J].The Canadian Cartographer,1973,10(2):112-122.

[8] 朱红春,张友顺,汤国安,等.基于DEM的黄土地貌类型提取与制图—以黄土高原丘陵沟壑实验样区为例[J].地球信息科学,2003(4):110-113.