基于Memoryless算法的河道水下地形模型簡化研究

陸 鳳，陳 莉，朱相丞

（1.南京市長江河道管理處，江蘇 南京 210011；2.漳州市測繪設計研究院，福建 漳州 363000）

隨著水下地形測繪技術的不斷發(fā)展，特別是多波束測深系統(tǒng)、水聲納系統(tǒng)與激光測深系統(tǒng)的應用，獲取海量河道地形數據逐漸成為常態(tài)。常見的河道水下地形數據類型包括水聲納掃測數據、河道斷面測量數據、等高線與河道深泓線、地理影像圖等。河道地形數據量的急劇增加，直接導致所構建的三維模型既精細又龐大，對計算機的存儲容量、傳輸效率、分析處理以及繪制速度等都提出了更高要求。

然而，高分辨率的地形三維模型并非總是必要的。在模型精確度與復雜度之間需要一個折中，即需對模型進行簡化，再用簡化后的模型代替原始模型。模型簡化是指在保持原始模型拓撲結構的前提下，利用適當的算法減少原始模型幾何要素數量的過程。模型簡化后可減少對硬盤和內存的需求、加速對形狀信息的計算，適當緩和海量數據與計算機軟硬件資源之間的矛盾。

早在20世紀70年代，就有學者開始討論網格模型的簡化問題。1976年，James Clark最先提出多分辨率模型的概念，而模型簡化是以多分辨率模型表示為基礎的[1]。20世紀90年代之后，網格模型簡化得到了深入研究，其中層次細節(jié)（LOD）模型以其普遍性和高效性得到了廣泛應用。LOD模型實質上就是按照一定的算法對原始模型進行簡化[2]。對網格模型簡化算法的分類有很多種，按照簡化時間可分為靜態(tài)和動態(tài)算法[3]。目前，靜態(tài)簡化算法主要包括頂點聚類法[4]、區(qū)域合并法[5]、重新布點法[6]和幾何元素刪除法[7]等；動態(tài)簡化算法包括層次模型生產算法[8]、漸進格網算法[9]、樹結構的LOD模型自動生產算法[10]等。一直以來，國內外學者主要研究地形簡化技術，而針對河道地形DEM簡化技術的研究相對較少。本文借鑒地形簡化技術，結合河道地形的自身特征，對河道模型簡化算法進行了研究；以河道水聲納掃測數據、斷面測量數據以及等高線數據所構建的河道地形DEM為研究對象，基于改進的Memoryless簡化算法，將河道地性線加入模型簡化約束條件中，實現了河道DEM地形模型在不同簡化比率下的簡化。

1 模型簡化原理與方法

1.1 河道地形DEM構建

Delaunay三角網（D-TIN）是目前地形TIN的主要生成方法。本文以逐點插入法構建D-TIN，以水下聲納掃測數據、等高線和斷面數據為數據源，在AutoCAD中利用ObjectARX技術構建河道D-TIN模型。首先對數據進行分析和處理；然后構建點集的外接多邊形，并剖分成多個三角形，形成初始的D-TIN；再將點集中未處理的點依次插入已存在的D-TIN中，并用局部優(yōu)化法則（LOP）對D-TIN進行優(yōu)化處理，直至所有點都插入完畢；最后刪除外接多邊形，完成河道地形DEM的構建。

1.2 河道地形地性線提取

水文分析是河道地形DEM分析的一個重要方面[11]。在進行河道地形簡化過程中，加入反映河道地形特征的地性線（分水線、匯水線）約束，能使簡化效果更加符合河道實際地形。從河道地形DEM中提取分水線的過程主要包括4個步驟[12]：水流方向計算；洼地處理；匯流累積量計算；提取匯流累積量為零的柵格，得到分水線。匯水線的提取也類似，只是對應的DEM采用反地形，即利用一個較大的數值減去原始DEM高程值，使原始DEM中的匯水線在反地形中變成分水線，再利用分水線的提取方法提取。本文利用ArcGIS的Hydrology功能模塊提取河道地形DEM的分水線和匯水線。

1.3 河道地形DEM簡化

幾何刪除法是目前應用最為廣泛的一種網格模型簡化方法[13]。其簡化原則為：盡可能保持原始模型的拓撲結構，逐漸刪除對模型幾何特征影響相對較小的幾何要素，并同步刪除包含該要素三角面；同時對刪除后產生的空洞進行局部三角化以保持拓撲結構，直至滿足用戶要求。幾何刪除法主要包括頂點刪除法[7]、邊折疊法[14]、三角形折疊法[15]等。

1.3.1 網格簡化Memoryless算法

Memoryless算法主要基于邊折疊法，其核心為：確定新頂點v的位置、邊權值以及選擇折疊順序。

圖1 新頂點v由3個平面的交點確定

河道地形DEM是非閉合的曲面，含有較多邊界邊要素，因此在Memoryless算法中添加保持邊界形狀的約束條件也是必須的。在邊界邊的局部區(qū)域應盡量保持相鄰邊界所對應的面積，并計算折疊邊界邊e之后對應的面積變化量。一般認為，網格模型的邊界邊是不在同一平面上的，因此選擇最小化面積向量模的平方和作為邊折疊后邊界最優(yōu)目標函數，計算公式為：

圖2中平面a2對應的是邊界面積保持約束的頂點集合，平面a3為邊界最優(yōu)對應的頂點集合，平面a1為體積保持約束的頂點集合，因平面a1平行于邊界三角形面，故未在圖中表示。

圖2 折疊邊界邊e后的新頂點v

2）邊權的確定和選擇。在邊折疊過程中，定權時應先判定是否為邊界邊，再對內部邊和邊界邊分別定權，區(qū)別處理。依據式（1）、（2），定義網格模型中三角形邊的邊權值等于體積和邊界最優(yōu)值的加權和，計算公式為：

式中，a+β=1。由于fv(v)為體積的平方和，fB(v)為面積的平方和，所以為了保證數量級的一致性，fB(v)需多乘上一個L(e)（邊e的長度）。當e為內部邊時，a取值為1，β取值為0，即無需添加邊界邊的面積約束權值；當e為邊界邊時，a、β取值根據實際需求進行調整，盡量達到對邊界邊延遲處理的效果。

選擇折疊邊時，先采用最小堆結構對所有邊權進行排序，然后在每次選擇時僅需直接從最小堆中取出第一個值對應的邊即可。

1.3.2 Memoryless改進算法

雖然Memoryless算法考慮得比較詳細，但是對一些特殊情況并沒有進行特別處理。本文針對以下兩種情況，對該算法進行改進。

1）折疊邊的一個頂點是邊界點、另一個頂點是內部點（圖3）。對這種特殊邊的判斷方法為：先判斷該折疊邊是否為邊界邊，若不是且邊的一個頂點是邊界點的，即符合該特殊處理條件。

圖3 特殊邊的折疊操作

2）折疊邊相鄰的頂點（幾近）共面或邊界邊（幾近）共線。這種情況下，函數fv和fB沒有唯一解，不能獲得新頂點的最佳位置，對于fv和fB較低的邊是不利的，因此需添加三角形形狀最優(yōu)化條件來約束。當fv和fB接近于0時，盡量使邊折疊操作后的三角形形狀趨于等邊三角形，避免狹長三角形（狹長三角形會造成陰影的不連續(xù)并降低渲染效率）。為了保證三角形的形狀質量，選取式（4）作為邊長最優(yōu)的目標函數。

在局部平面或趨于平面的情況下，該平面上新頂點位置的選擇對區(qū)域體積和面積總和是沒有影響的。通過最小化式（4），確保簡化后三角形模型的面積與周長的比率是最大的，以提高簡化后網格模型中三角形的形狀質量。最終定義的邊權函數公式為：

式中，a+β+γ=1。通過控制a、β、γ達到不同的簡化效果，若要更好地保留模型幾何特征，則適當增大a；若要得到平滑均勻的模型，則適當增加γ；特別的，若折疊邊e不是邊界邊，則取β=0。該邊權函數能較好地反映邊折疊后網格模型的局部幾何特征變化，并可通過調節(jié)相關系數，達到不同的簡化效果。

為了驗證Memoryless改進算法的有效性和簡化后模型形狀保持效果，利用某河道的局部掃測點數據對應的DEM進行實驗，如圖4所示。為了使對比結果清晰，式（5）中適當增大了γ，內部邊的3個邊權系數取值為α= 0 .60， β= 0 .00， γ=0.40，邊界邊的3個邊權系數取值為α= 0 .30， β= 0 .30， γ=0.40。

由圖4可知，當簡化比率高達98%時， Memoryless改進算法獲取的簡化模型仍能很好地保持河道邊界形狀，且更好地避免了狹長三角形。

圖4 河道地形模型簡化至98%效果對比圖（局部）

1.3.3 基于河道地性線的簡化流程

從河道某點水下地形斷面圖（圖5）可以看出，該處斷面最低點C相對于點A、B來說，周邊地勢較為平緩。在按照改進算法進行簡化時，點C及其周邊區(qū)域所對應的三角形邊將比點A、B處的更早被簡化，這將導致匯水線及其周邊的地形難以保持。同理，分水線附近的地形也可能存在類似情況。因此，需要在模型的簡化過程中加入匯水線、分水線約束條件，使地性線周邊的三角形邊延遲簡化，以此達到保持水下地形特征的目的。

圖5 河道某一點處的斷面圖

河道地形簡化后模型的誤差度量采用幾何誤差相似度。首先對簡化后的河道網格模型進行一定間距的采樣；然后計算簡化模型上這些采樣點與原始網格模型之間的歐氏距離d1、d2、…、dn；最后統(tǒng)計這些距離中的最大值dmax，并計算對應的中誤差值σ，作為河道地形DEM簡化后模型的誤差判定，其中，簡化具體流程如圖6所示。

圖6 河道地形DEM的簡化流程圖

圖7為截取模型簡化至97%的局部放大效果圖，在添加河道地性線（圖中較粗的虛線）后，可明顯看到在地性線左右兩側一定范圍內三角形分布較為密集，說明河道地形在地性線周邊的細節(jié)得到了較好保持。

圖7 有無地性線約束效果對比圖

2 實驗結果與分析

實驗過程中，需設定或輸入簡化停止參數，若簡化模型對應的值小于停止參數，則模型簡化程度已滿足需求，停止簡化；否則繼續(xù)簡化。根據所需簡化后網格模型的精度要求，本文采用簡化比率作為停止參數。簡化比率為簡化后模型折疊的邊數與原始模型的總邊數的比值，以百分比形式表示。

簡化過程中，為了較好地保持河道地形的幾何特征，控制邊權函數3個系數的取值為：邊界邊a=0.45，β=0.45， γ=0.10；非邊界邊 a=0.90， β=0， γ=0.10。根據不同數據來源，對Memoryless改進算法的簡化效果進行實驗。

1）實驗一：研究區(qū)域河道長度約為1.5 km，寬度約為85 m；數據來源為等高線和斷面點測量數據。簡化后部分河道地形模型局部效果如圖8所示，對應的相關數據如表1所示，可以看到，在河道中心部分，由于僅分布較少的斷面測量數據，當簡化比率達到95%時，中心位置地形變化較大；而靠近岸邊部分有等高線數據進行加密，河道模型的邊界形狀和地形特征均保持較好，與現實數據分布情況相符。同時，從表1的數據變化可以發(fā)現，簡化所用時間、模型誤差均隨模型簡化比率的增加而增大。

圖8 河道地形模型的簡化效果（實驗一）

表1 河道地形模型（等高線和斷面測量點）簡化相關數據表

2）實驗二：研究區(qū)域河道長度約為2.5 km，寬度約為80 m；數據來源為水下地形掃測數據（約22萬個點）。簡化后的部分河道地形模型局部效果如圖9所示，對應的相關數據如表2所示。

圖9 河道地形模型的簡化效果（實驗二）

結合表2數據可知，當簡化比率不高（30%、50%、70%等）時，地形模型的變化不明顯，故未在圖9中表示；當數據量較大時，經過Memoryless改進算法簡化后，河道地形模型不僅能很好地保持模型的邊界形狀，而且在簡化比率較高的情況下，仍能保留河道地形的局部細節(jié)特征。表2中的誤差數據變化說明簡化后的模型誤差隨著簡化比率的增加而增大；模型的中誤差均在cm級以內，最大誤差均在dm級內，是比較理想的。從文件大小變化可以發(fā)現，當可視化僅需較為粗糙的模型時，簡化后的模型能使存儲量大大降低，對應三角形的數目也隨之減少，從而提高顯示速度。

表2 河道地形模型（掃測數據）簡化相關數據表

3 結 語

首先在研究Memoryless算法的基礎上，結合河道地形DEM實際情況，對算法進行了改進，并將改進后的算法與原始算法的簡化成果進行了對比分析；然后在Memoryless改進算法中，增加了河道地性線約束，使得河道地形在地性線周圍的細節(jié)能夠得到較好保持；最后采用兩種不同來源的數據對基于地性線的Memoryless改進算法的簡化效果進行了實驗。結果表明，該算法簡化后地形模型效果良好，誤差在可接受的范圍內，同時也較好地保持了河道地形的幾何特征和細節(jié)信息。但本文研究的Memoryless算法屬于靜態(tài)簡化算法，其簡化后生成的模型在不同分辨率之間的切換變化不連續(xù)，將產生明顯的“跳躍”現象。為了解決這一問題，需對動態(tài)簡化算法展開進一步研究。