一种基于地形特征的数字高程模型缩放方法

杨 威

(长春师范学院计算机科学与技术学院，吉林长春 130032)

数字高程模型（Digital Elevation Model，DEM）数据是描述地球形状的基础数据之一，它对三维地球的可视化，全球数据进行分析决策都有着非常重要的作用。DEM虽然实现了地形表面的数字化表达，但信息隐含，地形可读性较差，需要用显示设备将地形直观地表达出来。不同的显示设备有其不同的分辨率，而DEM数据的行数和列数是一定的，为了使相同的DEM数据能够在不同的显示设备上显示，需要对DEM进行缩小与放大。

目前，国内外对DEM数据进行缩小与放大的算法主要有顶点聚类（VertexClustering）算法[1]、区域合并(Region Merging)算法[2]、逐步求精法[3]、顶点删除 （VertexDecimation）算法[4]、边折叠 （Edge Collapse）算法[5]、三角形折叠（Triangle Collapse）简化算法[6]和小波分解法[7]等。本文提出了基于地形特征的DEM缩小与放大的概念，并对文献[8]中的方法进行改进，使其适合DEM数据的特点。同时文献[8]中并没有给出关于放大的一个系统化算法，针对DEM数据的特征给出一个具体的、可操作的放大算法。

1 背景

Shai Avidan与Ariel Shamir于2007年发表了接缝雕刻（Seam Carving）算法，能够选择性地从影像中较不重要的区域移除或增加像素，使得影像宽高比调整后仍能维持主要内容的比例。

2 本文的算法

2.1 能量路径

数字高程模型是通过有限的地形高程数据实现对地形曲面的数字化模拟或者说是地形表面形态的数字化表示。高程数据常常采用绝对高程或海拔（即从大地水准面起算的高度）。数学意义上的数字高程模型是定义在二维空间上的连续函数H＝D（x，y），其中表示（x，y）地形点的平面位置，H表示相应点的高程。D（x，y）在位置（x，y）的梯度向量为：

从向量分析中我们知道，梯度向量指向在位置（x，y）的D的最大变化率方向。

这个量给出了塄D方向上每增加单位距离后D（x，y）值增大的最大变化率。为了计算方便，对DEM数据逐点求偏导数和，并将它们相加，以检测出具有明显地形特征的边缘，能量函数如下：

3.2 缩小算法

缩小算法问题的关键是如何选择被移除的点，既然我们的目标是将DEM数据中与地形特征无关的背景点删除。如果只删除点，将破坏DEM数据的完整性，所以，为了保持DEM数据的完整性和连续性，我们将删除具有最小能量的行或列。为此，我们定义DEM数据中的能量路径。设D为n行m列的DEM数据，DEM数据中基于x方向（行，竖直方向）的能量路径定义如下：

其中，x是[1，…，n]→[1，…，m]的映射。PX表示DEM数据中从上到下的一条竖向路径，每行DEM数据中有且仅只有一个点，同理，若y是[1，…，m]→[1，…，n]的映射，DEM数据中基于y方向（列，水平方向）的能量路径为定义3。

定义3

我们的目标是求能量最小的路径。

能量最小的路径可以通过动态编程技术[9]求得。在删除能量路径时，按升序的顺序依次删除能量路径，达到所要求的行数和列数。缩小算法如下：(1)求出需要删除的列数removes。(2)计算能量矩阵Energy_Matrix。计算DEM数据中每点的能量值并存储在Energy_Matrix中。(3)循环，以1为步长，从1到removes，执行。第一，求出具有最小能量的一条路径；第二，删除具有最小能量的路径。

3.3 放大算法

放大算法如下：(1)求出需要增加的列数adds。(2)计算能量矩阵Energy_Matrix。计算DEM数据中每点的能量值并存储在Energy_Matrix中。(3)循环，以1为步长，从1到adds，执行。第一，计算adds条具有最小能量的路径；第二，分别计算adds条具有最小能量路径左右两边点的平均值并存在adds条新路径中；第三，将adds条新路径中增加到原始DEM中。

4 实验

我们选择GTOPO30作为我们的实验数据。研究地区DEM位于非洲东南部，东经20°到60°，南纬10°到60°之间。DEM数据中有750行600列，如图1所示。为了检验本文提出方法的性能，本文采用Visual C++6.0实现该方法，并与传统的缩放方法作比较。图2为对研究地区DEM使用传统缩放方法的效果图，图3为对研究地区DEM使用本文提出的缩放方法的效果图。

图1 研究地区DEM

图2 传统缩放方法

图3 本文提出的缩放方法

5 结论

从图2和图3可以看出，本文提出的方法比传统的缩放方法更加有效，而且为数字高程模型提供了更好的三维显示效果。

[1]Low K.L.,Tan T.S.Model simplification using vertex-clustering[C]//ACM Symposium on Interactive 3D Graphics’97.New York,USA,1997:75-82.

[2]Kalvin D.,Taylor R.H.Superfaces:polygonal mesh simplification with bounded error[J].Computer Graphics and Application,IEEE,1996,16(3):64-77.

[3]Heckbert P.S.,Garland M.Survey of polygonal surface simplification algorithm[C]//SIGGRAPH’97,1997.

[4]Ciampalini A.,Cignoni P.,Montani C.et al.Multiresolution decimation based on global error[J].The Visual Computer,1997,13(5):228-246.

[5]Hoppe H.,DeRose T.,Duchamp T.Mesh optimization[J].Computer Graphics,1993,27(1):19-26.

[6]Hamann B.A data reduction scheme for triangulated surfaces[J].Computer Aided Geometric Design,1994,11(2):197-214.

[7]DeRose T.,Lounsbery M.,Warren J.Multiresolution analysis for surfaces of arbitrary topological type[J].ACM Transactions on Graph-ics,1997,16(1):34-73.

[8]Avidan S.,Shamir A.Seam carving for content-aware image resizing[J].ACM Transactions on Graphics,2007,26(3):10.

[9]Lew A.,Mauch H.Dynamic Programming:A Computational Tool[M].Springer,2007.