楊 威

(長春師范學院計算機科學與技術(shù)學院，吉林長春 130032)

數(shù)字高程模型（Digital Elevation Model，DEM）數(shù)據(jù)是描述地球形狀的基礎(chǔ)數(shù)據(jù)之一，它對三維地球的可視化，全球數(shù)據(jù)進行分析決策都有著非常重要的作用。DEM雖然實現(xiàn)了地形表面的數(shù)字化表達，但信息隱含，地形可讀性較差，需要用顯示設(shè)備將地形直觀地表達出來。不同的顯示設(shè)備有其不同的分辨率，而DEM數(shù)據(jù)的行數(shù)和列數(shù)是一定的，為了使相同的DEM數(shù)據(jù)能夠在不同的顯示設(shè)備上顯示，需要對DEM進行縮小與放大。

目前，國內(nèi)外對DEM數(shù)據(jù)進行縮小與放大的算法主要有頂點聚類（VertexClustering）算法[1]、區(qū)域合并(Region Merging)算法[2]、逐步求精法[3]、頂點刪除 （VertexDecimation）算法[4]、邊折疊 （Edge Collapse）算法[5]、三角形折疊（Triangle Collapse）簡化算法[6]和小波分解法[7]等。本文提出了基于地形特征的DEM縮小與放大的概念，并對文獻[8]中的方法進行改進，使其適合DEM數(shù)據(jù)的特點。同時文獻[8]中并沒有給出關(guān)于放大的一個系統(tǒng)化算法，針對DEM數(shù)據(jù)的特征給出一個具體的、可操作的放大算法。

1 背景

Shai Avidan與Ariel Shamir于2007年發(fā)表了接縫雕刻（Seam Carving）算法，能夠選擇性地從影像中較不重要的區(qū)域移除或增加像素，使得影像寬高比調(diào)整后仍能維持主要內(nèi)容的比例。

2 本文的算法

2.1 能量路徑

數(shù)字高程模型是通過有限的地形高程數(shù)據(jù)實現(xiàn)對地形曲面的數(shù)字化模擬或者說是地形表面形態(tài)的數(shù)字化表示。高程數(shù)據(jù)常常采用絕對高程或海拔（即從大地水準面起算的高度）。數(shù)學意義上的數(shù)字高程模型是定義在二維空間上的連續(xù)函數(shù)H＝D（x，y），其中表示（x，y）地形點的平面位置，H表示相應(yīng)點的高程。D（x，y）在位置（x，y）的梯度向量為：

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

這個量給出了塄D方向上每增加單位距離后D（x，y）值增大的最大變化率。為了計算方便，對DEM數(shù)據(jù)逐點求偏導數(shù)和，并將它們相加，以檢測出具有明顯地形特征的邊緣，能量函數(shù)如下：

3.2 縮小算法

縮小算法問題的關(guān)鍵是如何選擇被移除的點，既然我們的目標是將DEM數(shù)據(jù)中與地形特征無關(guān)的背景點刪除。如果只刪除點，將破壞DEM數(shù)據(jù)的完整性，所以，為了保持DEM數(shù)據(jù)的完整性和連續(xù)性，我們將刪除具有最小能量的行或列。為此，我們定義DEM數(shù)據(jù)中的能量路徑。設(shè)D為n行m列的DEM數(shù)據(jù)，DEM數(shù)據(jù)中基于x方向（行，豎直方向）的能量路徑定義如下：

其中，x是[1，…，n]→[1，…，m]的映射。PX表示DEM數(shù)據(jù)中從上到下的一條豎向路徑，每行DEM數(shù)據(jù)中有且僅只有一個點，同理，若y是[1，…，m]→[1，…，n]的映射，DEM數(shù)據(jù)中基于y方向（列，水平方向）的能量路徑為定義3。

定義3

我們的目標是求能量最小的路徑。

能量最小的路徑可以通過動態(tài)編程技術(shù)[9]求得。在刪除能量路徑時，按升序的順序依次刪除能量路徑，達到所要求的行數(shù)和列數(shù)?？s小算法如下：(1)求出需要刪除的列數(shù)removes。(2)計算能量矩陣Energy_Matrix。計算DEM數(shù)據(jù)中每點的能量值并存儲在Energy_Matrix中。(3)循環(huán)，以1為步長，從1到removes，執(zhí)行。第一，求出具有最小能量的一條路徑；第二，刪除具有最小能量的路徑。

3.3 放大算法

放大算法如下：(1)求出需要增加的列數(shù)adds。(2)計算能量矩陣Energy_Matrix。計算DEM數(shù)據(jù)中每點的能量值并存儲在Energy_Matrix中。(3)循環(huán)，以1為步長，從1到adds，執(zhí)行。第一，計算adds條具有最小能量的路徑；第二，分別計算adds條具有最小能量路徑左右兩邊點的平均值并存在adds條新路徑中；第三，將adds條新路徑中增加到原始DEM中。

4 實驗

我們選擇GTOPO30作為我們的實驗數(shù)據(jù)。研究地區(qū)DEM位于非洲東南部，東經(jīng)20°到60°，南緯10°到60°之間。DEM數(shù)據(jù)中有750行600列，如圖1所示。為了檢驗本文提出方法的性能，本文采用Visual C++6.0實現(xiàn)該方法，并與傳統(tǒng)的縮放方法作比較。圖2為對研究地區(qū)DEM使用傳統(tǒng)縮放方法的效果圖，圖3為對研究地區(qū)DEM使用本文提出的縮放方法的效果圖。

圖1 研究地區(qū)DEM

圖2 傳統(tǒng)縮放方法

圖3 本文提出的縮放方法

5 結(jié)論

從圖2和圖3可以看出，本文提出的方法比傳統(tǒng)的縮放方法更加有效，而且為數(shù)字高程模型提供了更好的三維顯示效果。

[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.