陸 鳳，陳 莉，朱相丞

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

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

然而，高分辨率的地形三維模型并非總是必要的。在模型精確度與復(fù)雜度之間需要一個(gè)折中，即需對(duì)模型進(jìn)行簡化，再用簡化后的模型代替原始模型。模型簡化是指在保持原始模型拓?fù)浣Y(jié)構(gòu)的前提下，利用適當(dāng)?shù)乃惴p少原始模型幾何要素?cái)?shù)量的過程。模型簡化后可減少對(duì)硬盤和內(nèi)存的需求、加速對(duì)形狀信息的計(jì)算，適當(dāng)緩和海量數(shù)據(jù)與計(jì)算機(jī)軟硬件資源之間的矛盾。

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

1 模型簡化原理與方法

1.1 河道地形DEM構(gòu)建

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

1.2 河道地形地性線提取

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

1.3 河道地形DEM簡化

幾何刪除法是目前應(yīng)用最為廣泛的一種網(wǎng)格模型簡化方法[13]。其簡化原則為：盡可能保持原始模型的拓?fù)浣Y(jié)構(gòu)，逐漸刪除對(duì)模型幾何特征影響相對(duì)較小的幾何要素，并同步刪除包含該要素三角面；同時(shí)對(duì)刪除后產(chǎn)生的空洞進(jìn)行局部三角化以保持拓?fù)浣Y(jié)構(gòu)，直至滿足用戶要求。幾何刪除法主要包括頂點(diǎn)刪除法[7]、邊折疊法[14]、三角形折疊法[15]等。

1.3.1 網(wǎng)格簡化Memoryless算法

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

圖1 新頂點(diǎn)v由3個(gè)平面的交點(diǎn)確定

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

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

圖2 折疊邊界邊e后的新頂點(diǎn)v

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

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

選擇折疊邊時(shí)，先采用最小堆結(jié)構(gòu)對(duì)所有邊權(quán)進(jìn)行排序，然后在每次選擇時(shí)僅需直接從最小堆中取出第一個(gè)值對(duì)應(yīng)的邊即可。

1.3.2 Memoryless改進(jìn)算法

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

1）折疊邊的一個(gè)頂點(diǎn)是邊界點(diǎn)、另一個(gè)頂點(diǎn)是內(nèi)部點(diǎn)（圖3）。對(duì)這種特殊邊的判斷方法為：先判斷該折疊邊是否為邊界邊，若不是且邊的一個(gè)頂點(diǎn)是邊界點(diǎn)的，即符合該特殊處理?xiàng)l件。

圖3 特殊邊的折疊操作

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

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

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

為了驗(yàn)證Memoryless改進(jìn)算法的有效性和簡化后模型形狀保持效果，利用某河道的局部掃測(cè)點(diǎn)數(shù)據(jù)對(duì)應(yīng)的DEM進(jìn)行實(shí)驗(yàn)，如圖4所示。為了使對(duì)比結(jié)果清晰，式（5）中適當(dāng)增大了γ，內(nèi)部邊的3個(gè)邊權(quán)系數(shù)取值為α= 0 .60， β= 0 .00， γ=0.40，邊界邊的3個(gè)邊權(quán)系數(shù)取值為α= 0 .30， β= 0 .30， γ=0.40。

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

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

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

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

圖5 河道某一點(diǎn)處的斷面圖

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

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

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

圖7 有無地性線約束效果對(duì)比圖

2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

圖8 河道地形模型的簡化效果（實(shí)驗(yàn)一）

表1 河道地形模型（等高線和斷面測(cè)量點(diǎn)）簡化相關(guān)數(shù)據(jù)表

2）實(shí)驗(yàn)二：研究區(qū)域河道長度約為2.5 km，寬度約為80 m；數(shù)據(jù)來源為水下地形掃測(cè)數(shù)據(jù)（約22萬個(gè)點(diǎn)）。簡化后的部分河道地形模型局部效果如圖9所示，對(duì)應(yīng)的相關(guān)數(shù)據(jù)如表2所示。

圖9 河道地形模型的簡化效果（實(shí)驗(yàn)二）

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

表2 河道地形模型（掃測(cè)數(shù)據(jù)）簡化相關(guān)數(shù)據(jù)表

3 結(jié) 語

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