一種基于Fréchet距離的斷裂等高線內插算法

，， ，，

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

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

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

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

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

1 相似性度量

由于空間距離無法考慮較長等高線的形狀，因此引入相似性度量。線狀要素可以看作是一組空間點集，線狀要素的幾何相似性可以看作空間點集的相似性[9]?？臻g點集相似運用了兩種重要的空間點集距離：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 等高線插值算法

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

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

(2) 判斷是否有多個參考等高線，若有，則根據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 基于相似度選擇參考等高線

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

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

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

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

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

2.3 等高線的內插

根據上節(jié)中得到參考等高線，進而對斷裂等高線進行插值。由于斷裂等高線的存在，插值時需要考慮參考等高線與內部已存在斷裂等高線的方向。延伸方向不同的等高線，插值的方向不同。判斷兩條等高線的延伸方向是否一致的方法如下：斷裂等高線B的兩個斷裂點為P1、P2，其中P1、P2分別對應斷裂線的首、尾節(jié)點，對應在完整等高線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，則在等高線上對相應的點繼續(xù)取下一個點，直到Pi1≠Pi3或Pi2≠Pi4。則若Pi1Pi4且Pi1>Pi2時，等高線B和等高線C延伸方向相同，則插值順序為Pi2、Pi2+1、…、Pi1-1，Pi1。反之，若Pi1>Pi3、Pi2Pi3、Pi2

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

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

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

3 試驗與分析

將本文的修復算法搭載到中國測繪科學研究院自主研發(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，內存(RAM)4 GB。

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

表1 試驗結果匯總

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

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

4 結 語

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