，， ，，

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

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

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

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

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

1 相似性度量

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

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

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

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

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

2 等高線插值算法

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

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

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

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

2.1 節(jié)點(diǎn)加密

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

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

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

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

在對(duì)線的相似性的判斷中，用全部斷裂等高線作相似度判斷是不準(zhǔn)確的，因此需要對(duì)參考等高線作截?cái)?。如圖3(a)所示，等高線1有A、B兩個(gè)端點(diǎn)，則在等高線2上的截?cái)嗑€為ab。由于弧段AB與ab不相似，因此無(wú)法找到插值的參考等高線。

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

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

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

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

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

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

計(jì)算連接順序后，即可通過(guò)點(diǎn)的坐標(biāo)和這兩條等高線的高程進(jìn)行插值，得到插值后的線。具體算法如下：

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

式中，hc為當(dāng)前斷裂點(diǎn)的高程值；h1為等高線1的高程值；h2為等高線2的高程值；xn為點(diǎn)n的橫坐標(biāo)；yn為點(diǎn)n的縱坐標(biāo)。

3 試驗(yàn)與分析

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

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

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

圖6為試驗(yàn)結(jié)果，其中粗實(shí)線代表完整計(jì)曲線，細(xì)實(shí)線代表斷裂首曲線，虛線代表插值后的補(bǔ)充等高線。

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

4 結(jié) 語(yǔ)

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