，， ，，

(中國測繪科學(xué)研究院，北京 100830)

等高線是描述地球表面地理信息最直觀的方法之一，在地圖制圖中有著重要的應(yīng)用。等高線內(nèi)插是指在已知高程的兩條等高線之間，通過內(nèi)插方法自動生成與已知等高線相一致的新等高線[1]，其在制圖綜合、三維重建等領(lǐng)域具有廣泛的應(yīng)用，因此如何準確地內(nèi)插等高線具有重要的意義。

目前等高線數(shù)據(jù)的獲取方式分為兩種：遙感影像中獲取[2-3]和實地測量高程獲取。通過遙感數(shù)據(jù)提取的等高線一般都是連續(xù)且封閉的。但由于遙感數(shù)據(jù)分辨率所限，通過這種方式提取的等高線的等高距較大，不能滿足需求。除此之外，還有一部分通過實地測量的符合精度的等高線，但在實際的高程測量中，由于遇到建筑物不能實地測量等情況，繪制出的等高線是斷裂的，因此需要通過遙感數(shù)據(jù)提取的等高線人作內(nèi)插補充。

國內(nèi)外學(xué)者對等高線內(nèi)插進行了廣泛研究，為解決等高線內(nèi)插提供了思路和算法。目前內(nèi)插等高線有如下幾種方法：規(guī)則網(wǎng)格內(nèi)插、約束三角網(wǎng)內(nèi)插、輔助線內(nèi)插[4-7]等。對于馬鞍型地形，文獻[8]提出使用“搭橋法”的插值方法解決，即將多條同一高程的等高線用線連接起來，組成一條等高線，再用上述兩條等高線內(nèi)插等高線的算法插入所需要的等高線。但上述算法不適用于目前有部分斷裂等高線存在的情況，由于有一部分斷裂等高線的存在，在插值時需要考慮已有的等高線。對于馬鞍型地形的處理，傳統(tǒng)方法不能滿足當前插值的需要。如圖1 所示，若用“搭橋法”連接，則會出現(xiàn)與已有等高線不協(xié)調(diào)的情況。

綜上，目前的插值算法不能很好地解決與已有等高線的協(xié)調(diào)關(guān)系，因此本文提出一套基于相似度的自動內(nèi)插算法，通過等高線的相似度對參考等高線進行選擇，再進行插值，以滿足與已有等高線的協(xié)調(diào)關(guān)系。

1 相似性度量

由于空間距離無法考慮較長等高線的形狀，因此引入相似性度量。線狀要素可以看作是一組空間點集，線狀要素的幾何相似性可以看作空間點集的相似性[9]。空間點集相似運用了兩種重要的空間點集距離：Hausdorff距離[10]和Fréchet距離[11]。但由于Hausdorff距離沒有考慮點的順序，局限性較大[12-13]，因此有可能形狀差異很大的兩個幾何形狀，其Hausdorff距離卻很小，因此本文選用Fréchet距離作為相似度測量的方法。在計算時，真實的Fréchet距離即為線的連續(xù)Fréchet距離。但由于線要素是離散化的，無法計算線的連續(xù)Fréchet距離，因此，可以使用離散Fréchet距離對等高線相似度進行度量。離散Fréchet距離定義如下[14]：

給定一個有n個至高點的多邊形鏈P=〈p1,p2,…,pn〉，一個沿著P的k步，分割P的至高點成為k個不相交的非空子集{Pi}i=1,…,k(1≤k≤n)，使得Pi=〈pni-1+1,…,pni〉和0=n0

給定兩個多邊形鏈A=〈a1,a2,…,an〉，B=〈b1,b2,…,bn〉，一個沿著A和B的組合步為：一個沿著A的k步{Ai}i=1，…，k和一個沿著B的k步{Bi}i=1，…，k，使得1≤i≤k，或|Ai|=1，或|Bi|=1(表示Ai，Bi恰好包含一個至高點)。

一個沿著鏈A和B的組合步W={(Ai，Bi)}的花費為

則鏈A和B間的離散Fréchet距離為

2 等高線插值算法

等高線插值首先需要對首曲線和計曲線數(shù)據(jù)作節(jié)點加密，對于有多個插值參考線的情況，需要通過相似性度量選擇正確的參考等高線，最后根據(jù)參考等高線進行插值，從而對斷裂的等高線進行補充。插值算法的具體流程如下：

(1) 對首曲線和計曲線數(shù)據(jù)作節(jié)點加密。

(2) 判斷是否有多個參考等高線，若有，則根據(jù)Fréchet距離選擇相似性高的參考等高線。

(3) 用“最近點”的方式，通過上步選取的參考等高線對斷裂等高線進行插值。

2.1 節(jié)點加密

離散Fréchet距離衡量等高線的相似性時，若部分等高線的節(jié)點之間距離過大，線上的點較稀疏，在計算時會與真實Fréchet距離相差較大，不能準確地衡量相似度。圖2所示有兩條曲線〈a,b,c〉和〈d,e〉，它們之間連續(xù)的Fréchet距離就是從d到線段ab的距離，如圖2(a)中的虛線所示。

但由于線ef中節(jié)點較稀疏，計算得到的離散Fréchet距離為d(b,e)，遠大于真實的Fréchet距離。如圖2(b)中，對圖2(a)中線ef中節(jié)點進行加密，則離散Fréchet距離為d(b，h)，更接近真實的Fréchet距離，可以較為準確地判斷相似度。當曲線上的樣本點足夠多，離散Fréchet距離會無限接近連續(xù)Fréchet距離，但也會增加運算量。因此需要對等高線的節(jié)點進行適當加密以保證判斷的準確性。

2.2 基于相似度選擇參考等高線

對于鞍部等特殊地形中等高線參考線不確定的情況，需要基于相似度對參考等高線進行選擇，以保證插值的準確性。根據(jù)上文中所提到的線狀要素相似度的計算，基于離散Fréchet距離選擇與斷裂等高線有較高相似度的計曲線作為參考線。

在對線的相似性的判斷中，用全部斷裂等高線作相似度判斷是不準確的，因此需要對參考等高線作截斷。如圖3(a)所示，等高線1有A、B兩個端點，則在等高線2上的截斷線為ab。由于弧段AB與ab不相似，因此無法找到插值的參考等高線。

因此，選用斷裂處附近的一系列點而不是整條線作為相似度判定的依據(jù)比較合適?；陔x散Fréchet距離的計算方法，采用“部分”Fréchet距離計算方法，截取部分線作為相似度的判斷依據(jù)，而截取的長度則是判斷準確與否的關(guān)鍵。截取的線太長容易將不匹配的部分代入，求得的Fréchet距離變大。若截取的線太短則會失去Fréchet判斷的準確性。如圖3(b)所示，等高線1的部分與內(nèi)部環(huán)相似，若取等高線1中AB作截取，則截取的等高線過短，容易造成截取點數(shù)量不足而判斷錯誤，若截取部分為AC，則截取過長，形狀不同造成相似度判斷錯誤。因此需要選擇合適數(shù)量的點對等高線進行截取。

本文提出的解決方法是先選取相對少的點作判斷，避免選取的點過多，截取過長而導(dǎo)致相似度判斷錯誤。同時，為避免線的長度過短造成的Fréchet距離判斷不準確，可以在選取后對線的長度進行限制，若線的長度過短，則可以增加少量點數(shù)達到長度限制后再進行相似性的判斷。

圖4所示為完整等高線A、B、C，斷裂等高線D。D的端點為d1和d10，取部分線d1d5在B上截取，截取后的線為b1b4，在C上截取，截取后的線為c1c2。分別計算d1d5與b1b4、c1c2之間的離散Fréchet距離。經(jīng)過計算得到d1d5與b1b4的離散Fréchet距離為d(d1,b1)，d1d5與c1c2的離散Fréchet距離為d(d1,c2)。由于d(d1,b1)

2.3 等高線的內(nèi)插

根據(jù)上節(jié)中得到參考等高線，進而對斷裂等高線進行插值。由于斷裂等高線的存在，插值時需要考慮參考等高線與內(nèi)部已存在斷裂等高線的方向。延伸方向不同的等高線，插值的方向不同。判斷兩條等高線的延伸方向是否一致的方法如下：斷裂等高線B的兩個斷裂點為P1、P2，其中P1、P2分別對應(yīng)斷裂線的首、尾節(jié)點，對應(yīng)在完整等高線C上距離最近的兩個點Q1和Q2，計算得到等高線C上的序號Pi1，Pi2。如圖5所示，可得Pi1為5，Pi2為11。

同樣用此方法獲得P1、P2在等高線B上臨近的點P3、P4在等高線2的序號Pi3為4，Pi4為12。若Pi1=Pi3或Pi2=Pi4，則在等高線上對相應(yīng)的點繼續(xù)取下一個點，直到Pi1≠Pi3或Pi2≠Pi4。則若Pi1Pi4且Pi1>Pi2時，等高線B和等高線C延伸方向相同，則插值順序為Pi2、Pi2+1、…、Pi1-1，Pi1。反之，若Pi1>Pi3、Pi2Pi3、Pi2

計算連接順序后，即可通過點的坐標和這兩條等高線的高程進行插值，得到插值后的線。具體算法如下：

由上文中獲知插值順序和序號，對序號點進行插值，最后連接已有等高線的兩個端點。設(shè)這兩條等高線分別為等高線C和等高線A，設(shè)上步中求得的點順序為P1、P1+1、…、Pm，則從P1開始對等高線A上節(jié)點計算最近點R1，直到最后一個點為止。求得等高線3上的點序為R1、R2、…、Rm，并據(jù)此在等高線2、3間進行插值。連接的公式為

式中，hc為當前斷裂點的高程值；h1為等高線1的高程值；h2為等高線2的高程值；xn為點n的橫坐標；yn為點n的縱坐標。

3 試驗與分析

將本文的修復(fù)算法搭載到中國測繪科學(xué)研究院自主研發(fā)的縮編軟件平臺——WJ-Ⅲ無級地圖工作站上，開發(fā)環(huán)境為Microsoft Visual Studio 2010和C++編程語言，試驗測試環(huán)境為單臺PC機，系統(tǒng)版本為64位Windows 7操作系統(tǒng)，CPU為Intel Core i7-6700，主頻3.40 GHz，內(nèi)存(RAM)4 GB。

試驗數(shù)據(jù)為江蘇某地區(qū)的斷裂等高線數(shù)據(jù)，分為計曲線和首曲線兩個圖層，計曲線完整，首曲線部分斷裂。計曲線的基本等高距為25 m，首曲線的基本等高距為5 m。試驗結(jié)果見表1。

表1 試驗結(jié)果匯總

圖6為試驗結(jié)果，其中粗實線代表完整計曲線，細實線代表斷裂首曲線，虛線代表插值后的補充等高線。

從試驗結(jié)果可以看出，應(yīng)用相似度的等高線插值算法，其插值的正確比率在90%以上，精確度較高。尤其是在鞍部的插值，相較于空間距離度量，使用相似性度量的方法提升了正確率?；谧詣硬逯档慕Y(jié)果，再輔以少量的人工作業(yè)，即可將等高線插值完整。

4 結(jié) 語

本文對目前數(shù)據(jù)的等高線插值流程進行了討論。在準確性上，結(jié)合相似性判斷，減少了鞍部等復(fù)雜地形的插值錯誤，并通過試驗證明了方法的有效性和合理性。但在對等高線進行自動插值的過程中，還需要對部分情況進行人工處理，在今后的研究中可針對這個問題進行改進。