空間插值分析算法綜述①

李海濤,邵澤東

空間信息技術是自20世紀60年代以來逐漸發展起來的信息技術的總稱,用于獲取,管理和分析與地理位置相關的空間信息[1].它以人類的生活環境為主要研究對象,以遙感(Remote Sensing,RS)、全球定位系統GPS(Global Position System)和地理信息系統(Geographic Information System,GIS)技術為代表,它不僅是客觀數據的集合,而且是從收集、處理、測量和分析到地理空間數據和信息的管理、存儲、顯示和發布的整個信息流程.它具有客觀獲取、準確定位、靈活管理、空間分析和視覺表達的特點[1].

在空間數據中,具有不均勻位置分布的數據被稱為離散數據,在平面二維地理空間的定位中,離散數據的坐標由不規則分布的離散樣本的平面坐標實現.高程和屬性值通常用作第三維數據.空間插值則是一種通過這些離散的空間數據計算未知空間數據的方法.它是基于“地理學第一定律”的基本假設:空間位置上越靠近的點,具有相似特征值的可能性越大,而距離遠的點,其具有相似特征值的可能性越小[2].它通常用于將離散點的測量數據轉換為連續數據表面,以便于比較其他空間現象的分布情況.

空間插值分析算法的分類方式有多種:按插值的區域范圍分類,可以分為整體插值、局部插值、邊界內插法等[3]；整體插值是用研究區的所有采樣點進行全區特征擬合,在整體插值方法中,整個區域的數值會影響單個插值點的數值,同樣單個采樣點的數值的增加、減少或刪除對整個區域的特征擬合都有影響[3],代表性插值方法具有趨勢面分析插值方法等.局部插值是使用相鄰數據點來估計未知點的值,首先定義鄰域或搜索范圍,然后搜索屬于該區域的數據點,然后選擇可以表示此有限點空間變化的數學函數,最后通過計算為該鄰域或者該區域內的未知點賦值[3],代表插值方法有樣條函數插值法[4]、反距離權重插值法[5]、Kriging插值法[6]等.邊界內插規則假設值和屬性的任何變化發生在特定區域的邊界線上,并且邊界內屬性的變化是均勻和同質的,主要的插值法是泰森多邊形法.

按照插值的標準分類,可以分為確定性插值、地統計插值.確定性插值法主要采用數學工具,利用函數的方法來進行插值,這種方式用來研究某區域內部的相似性,其代表插值法有反距離加權插值法[7]等；地統計插值是基于空間自相關性的,由觀測數據產生具有統計關系的曲面,代表插值法是Kriging 插值法[7].

按插值的精度分類,可以劃分為精確插值、近似插值.精確插值生成包括所有觀測點的曲面,而近似插值生成不包含所有觀測點曲面[8].

隨著生產、研究應用的不斷深入,越來越多的插值算法被提出和不斷改進.本文將對適用性高、性能卓越、應用場景廣泛的泰森多邊形法、反距離權重插值法、樣條函數插值法與克里金插值法進行研究綜述,并對空間插值算法的未來的研究方向進行展望.

1 泰森(Thiessen)多邊形

荷蘭氣候學家Thiessen AH 提出泰森(Thiessen)多邊形法,根據離散分布的氣象站的降雨量來計算平均降雨量,所有相鄰氣象站以三角形連接,在三角形的每一邊作垂直平分線,因此氣象站周圍有幾個垂直平分線包圍的多邊形[8].用某多邊形內所包含的單獨的氣象站的降雨強度來表示該多邊形區域內的降雨強度,該多邊形稱為泰森多邊形.如圖1所示,圖中虛線形成的多邊形就是泰森多邊形,A、B、C、D 分別為離散觀測點,一個泰森多邊形內僅包含一個離散觀測點,泰森多邊形的每個頂點都是每個三角形的外接圓心[1].泰森多邊形也被稱為Voronoi 圖或dirichlet 圖[3].

圖1 泰森多邊形示意圖

泰森多邊形利用離散觀測點的值對該點所在的區域進行賦值,得到的結果往往是數值的變化只發生在多邊形的邊界上,而多邊形內部的數值則是均勻、同質的[9].其數學表達式為:

其中,Ve表示待插值點的距離,Vi表示i示點的離散觀測值.i點必須滿足如下條件:

其中,dij表示點i(xi,yi) 與點j(xj,yj)間的歐幾里德距離[8].

泰森多邊形的關鍵是將離散觀測點合理地連接到三角網絡中,即構造Delaunay 三角網絡[3].構建泰森多邊形步驟如圖2所示.

圖2 泰森多邊形創建流程

泰森多邊形反映了離散觀測點的空間控制范圍或者是勢力范圍,它適用于較小區域內、空間變異性不高的情況,距離近的點比距離遠的點更相似,比較符合人的邏輯思維[10].同時,它的實現不需要其他前提條件,效率高,方法簡單,但是受樣本觀測值的影響較大,沒有考慮空間因素、變量以及其他某些規律,只考慮距離因素,實際效果不是很理想.

泰森多邊形插值法也在進行不斷改進發展,其中自然鄰域法就是改進的一種,它的基本原理是在插值點創建一個新的多邊形,新多邊形與原始多邊形的重疊比例作為觀測點數值的權重,通過這種方式計算插值點的估計值[7].另外,劉金雅等人將泰森多邊形與最小累計阻力模型相結合[11],用于估算京津冀城市群生態系統服務價值；祁春陽等人將泰森多邊形與虛擬力算法、質心算法相結合,提出VFVP 算法策略來提高無線傳感網絡覆蓋率[12]；戚遠航等人提出了一種基于泰森多邊形的離散蝙蝠算法來解決多車場車輛路徑問題[13]；羅浩將泰森多邊形應用于人臉區域分割進行關鍵特征提取來實現人臉識別的新算法[14].

泰森多邊形適用于樣本點分布均勻的較小區域內空間變異性不明顯的場景,允許少量的數據缺失,它可應用于氣象降水、無線網絡規劃、計算機視覺等領域的定性分析、統計分析以及鄰近分析中,泰森多邊形算法正在更廣闊的應用于空間區域相關的新領域.

2 反距離權重插值(IDW)

反距離權重插值法[15]最初是由Shepard 提出,后來經過持續不斷的改進發展.它的最重要的一個假設就是觀測點對于插值點都會有局部影響,任意一個觀測點的值對插值點值的影響都是隨著距離的不斷增加而不斷減弱的[16],在估計插值點的值時,假設距離估計插

值點最近的N個觀測點對該插值點有影響,則這N個觀測點對插值點的影響與它們之間的距離成反比關系[17].因此更接近插值點的觀測點將被賦予的權重更大,而且權重的和為1.

IDW 的數學表達式:

其中,是點(x0，y0)處的估計值,Qi是估計插值點與觀測點相對應的權重系數,n表示插值點的個數[18].

權重系數Qi的計算是反距離加權算法的關鍵,通常由下式給出:

其中,n是已知觀測點的數量,f(dej)表示已知觀測點與插值點之間已知距離dej的權重函數,最常用的一種形式是:

其中,b是合適的常數.當b取值為1 或2 時,此時是反距離倒數插值和反距離倒數平方插值[17].

反距離權重插值作為一種全局插值算法,它的所有離散觀測點都將參與每一插值點數值的計算,同時,它也是一種精準插值,插值生成的曲面中的預測的觀測值與實測的觀測值完全一致.它綜合了基于泰森多邊形的自然鄰域法和多元回歸漸變方法的有點,不僅考慮了距離因子,還為鄰近插值點的離散觀測點根據距離分配權重,當出現各向異性時,還會考慮方向的權重.距離權重函數與從插值點到觀測點的距離次冪成反比,隨著觀測點與插值點之間距離的不斷擴大,權重呈現冪函數遞減趨勢[19].如表1所示.

表1 反距離權重插值與相關方法的比較

IDW 簡便易操作,不會出現無法解釋的無意義結果,即使觀測點數據集的變化波動很大也能夠得到一個比較合理的結果[17].但是,IDW 對權重函數的選擇特別敏感,權重函數存在細微差別對生成的結果會有較大的波動,而且易受觀測點數據集的影響,由于數據集的影響,可能存在孤立的分布模式,其中部分點數據高于其他周圍數據.

反距離權重算法的應用不斷發展,李正泉對IDW進行優化改進,在傳統IDW 算法的基礎上添加用于反映樣點方位的調和權重系數K,來減小或者克服樣點方位分布不均的問題[21]；王家潤提出了IDW 并行優化的線程任務分解模型[22],提升了硬件加速能力,降低了并行編程任務劃分難度；劉瑋將IDW 模型應用于鼠尾藻群體數量分布的計算且能夠反映鼠尾藻群體的空間分布[23].

反距離權重插值適用于表現出均勻分布而且足夠密集以反映局部差異的觀測點數據集的場景,提供合理的插值結果,它普遍適用于空氣質量、氣象、土壤等領域的研究,尤其適用于當某個現象呈現出局部變異性的情況.

3 樣條函數插值(Spline)

樣條函數S(x)是一個分段函數,在區間[a,b]是一個連續可微的函數,如圖3所示.

給定一組節點:

其中,S(x) 滿足在每個子區間[xi，xi+1](n=0,1,2,…,n-1) 上是次數不超過m的多項式且在區間上有m-1階連續導數,則稱S(x)是定義在[a，b]上的m次樣條函數[24].

樣條函數插值的目標是找到滿足最佳平滑原理的曲面,并使用樣本觀察點以最小化曲面曲率擬合平滑曲線[25].使用最小化表面總曲率的數學函數來估計插值點的值,從而在輸入點之后生成平滑表面.其表達式:

其中,是點(x0，y0)處的估計值,r是預測點與樣點之間的距離,n表示預測點的數量.

樣條函數主要劃分為規則樣條函數和張力樣條函數[4],兩類函數對比如表2所示.

對于規則樣條函數,R(ri)和T(x，y)表達式如下:

其中,c是實常數,a是線性方程系數,τ是權重系數,k0校正貝塞爾函數,ri是從插值點到觀測點的距離[4].

對于張力樣條函數,R(ri)和T(x，y)表達式如下:

其中,c為常數,a為線性方程系數,φ是權重系數,k0是改正后的貝塞爾函數,ri是插值點到觀測點的距離.

圖3 樣條函數示意

表2 兩類樣條函數的比較

樣條函數插值不斷改進發展,張海燕利用三次樣 條函數進行GNSS 高程擬合[26],具有很好的適應性；高茂庭提出了一種基于遺傳算法的B 樣條擬合算法[27],有效提高了精度并加快了收斂速度；胡蓉利用多親遺傳算法對B 樣條函數進行優化[28],實現玻璃搬運機器人軌跡的優化.

樣條函數插值速度快,且產生的視覺效果好,但樣條函數插值的誤差不能直接計算,適用于屬性值在短距離內變化不大的區域范圍,它廣泛應用于測繪、統計學、計算幾何等領域.

4 克里金(Kriging)插值算法

克里金插值算法也稱為空間自協方差最佳插值法[29],它是以南非礦業工程師Krige DG 的名字命名的一種最優內插法[30],以變異函數理論和結構分析為基礎[31],適用于區域化變量存在空間相關性,假設都是空間相關性且所有隨機誤差都具有二階平穩性.其表達式:

其中,是點(x0，y0)處的插值估計值,即z0=z(x0，y0).這里的 λ0是權重系數.它同樣是用空間上所有已知觀測點的數據加權求和來估計插值點的值.但權重系數不是距離的倒數,而是一組最佳系數,它們能夠滿足點(x0，y0)處的插值估計值與真實值的差最小,同時滿足無偏估計的條件:

這樣來看,插值點值的好壞完全取決于 λ0權重系數.所有類型的克里金插值法的權重系數必須都要滿足最優性和無偏性的條件[32].

當Zi的E(Zi)=m已知,則將這種克里金插值法成為簡單克里金插值法[33],此時簡單克里金的表達式為:

簡單克里金插值法的插值點的精度在很大程度上取決于m值的大小.

當Zi的E(Zi)為未知常數,則將這種克里金插值法成為普通克里金插值法[33],求解權重系數的表達式為:

以上方程組中,μ是拉格朗日乘子,協方差Cov(xi，yi)可用變異函數γ(xi，yi)表示[34]:

當Zi的E(Zi)=m(xi)時,即在插值區域內是非平穩的,協方差或變異函數已知,此時被稱為泛克里金插值法[35],m(xi)就是在這xi的期望值,即漂移.泛克里金插值法是一種地統計學方法,它考慮到了有漂移的無偏線性估計量[34].泛克里金插值方法求解權重系數的方程組的表達式:

當研究某一閾值特異值時需要一種非參數地統計學方法,稱之為指示克里金插值法[34],對于某一區域觀測值,任意指定已閾值z,引入指示函數l(x，z),表達式如下:

其變異函數表達式:

當已知任意區域二維概率分布時,對插值點的估計值的一種非線性地統計法稱之為析取克里金插值[36],它是一種非線性、最小方差的無偏估計方法,其表達式:

其中,fi(Zi)為未確定函數,根據Hermiet 多項式的正交性用于擬合法向變形函數以估計插值點的值.

當利用多個區域變量之間的互相關性,通過建立模型用觀測點的數據值對插值點數據值進行估計,被稱為協同克里金插值[37],這是一種多變量地統計學研究的基本方法,是基于協同區域化變量理論.協同區域化是指定義在同一空間域,并且在統計及空間位置上具有一定程度相關性的區域化變量.協同克里金插值表達式:

從表達式可以看出,協同克里金插值的估計量是K 個協同區域化變量的所有有效值的線性組合.

多種克里金插值法的比較如表3所示.

表3 多種克里金插值法的比較

克里金插值法也在不斷的發展,陳光使用NM 單純形算法對克里金變異函數模型進行改進優化[38],提高無線傳感器網絡的性能；顧軍華利用VIRE 算法和克里金插值實現室內的精確定位[39]；鄧岳川采用克里金插值法從空間分布的角度提出構建多路徑誤差的模型,實現對指定測區內的多路徑誤差的空間分布特征的探究[40].

克里金插值算法適用于樣本數據存在隨機性和結構性特征的場景,廣泛應用于各類觀測的空間插值,地面風場、降雨、土壤、環境污染等領域.

結合上述空間插值算法的原理及應用,總結了這些算法的逼近程度、處理速度、推算能力以及適應范圍[41],使用分值1～5 表示由弱到強,對比結果如表4所示.

表4 空間插值算法對比

5 結論

本文綜述了一系列的空間插值分析算法的插值原理和應用,經過幾十年的不斷發展,空間插值算法不斷完善,并逐漸趨于成熟,不斷被應用到土壤水質、海洋環境、地質勘探、空氣質量等諸多領域.雖然空間插值算法的應用領域廣闊,但是依然存在一些問題,空間插值算法未來的發展應當需要根據不同的應用場景不斷的進行研究優化與完善,不斷形成更加符合真實場景的空間插值算法.

首先,隨著空間插值分析算法的不斷發展以及機器學習的不斷發展,王輝贊等提出了支持向量機的克里金插值算法的在海洋數據方面的實驗[42],邱云翔提出的粒子群優化BP 神經網絡在降雨空間插值的應用[43],程家昌等人利用BP 神經網絡插值方法對研究區土壤的氮和磷進行空間插值預測,比傳統插值算法具有更強的的泛化能力[44],李純斌等人以BP 神經網絡和支持向量機模型為研究對象,構建降水量空間插值模型[45],大量的關于空間插值算法的新的探索已經廣泛展開,并在降雨降水、土壤勘測、海洋資料等應用鄰域取得了一定成果.未來可繼續在機器學習以及人工智能等方面促進空間插值算法的進一步研究.

其次,空間插值分析算法的不再是緊緊局限于傳統意義上的地理信息系統,國內外的研究者將空間插值的思想特性引入各行各業,體現著空間插值分析算法的作用與意義.未來可以在空間插值分析算法應用的各個方面不斷加深算法的適應性改進.

最后,所需要解決的實際問題大多都是離散型問題,空間插值分析算法需要根據實際情況進行建模分析、具體設計,然而算法的改進并不能保證獲得最好的結果,怎樣改進空間插值分析算法能夠獲得更優更合理的結果都需要進行深入的研究與探討.