移動GIS多層空間非線性抽稀回溯算法分析

潘 翔

(廣西經(jīng)濟管理干部學(xué)院 計算機系，廣西 南寧 530007)

0 引言

移動互聯(lián)網(wǎng)由于地理信息系統(tǒng)(Geographic Information System，GIS)的加入已發(fā)展成為一個全息位置服務(wù)(Location Based Services，LBS)的可視化時代，目前已廣泛應(yīng)用于國土管理、城市規(guī)劃、交通運輸?shù)雀鱾€領(lǐng)域［1］。移動GIS是一個物聯(lián)網(wǎng)(The Internet of things，IOT)熱點，催生了GIS技術(shù)創(chuàng)新與優(yōu)化，ArcGIS、超圖等不斷地改進其抽稀算法，以高速的數(shù)據(jù)流轉(zhuǎn)與可視化信息交互適應(yīng)隨時隨地的被標(biāo)簽上LBS業(yè)務(wù)應(yīng)用互聯(lián)互通［2］。

移動GIS的移動性、實時性要求其能夠高效、準(zhǔn)確地加載地圖。DP算法(Douglas－Peucker)［3］、基于三角網(wǎng)的抽稀方法［4］、金字塔切片構(gòu)建算法［5］等從閥值比較與判斷空間數(shù)據(jù)點取舍、保留地形特征、解決可視高度調(diào)整顯示問題等方面實現(xiàn)了抽稀，但各有不同程度無法滿足實時數(shù)據(jù)處理需求的問題。針對系列算法存在的缺點，設(shè)計一種GIS多層空間非線性數(shù)據(jù)抽稀算法，能夠按步長、線段長度、垂距等定義抽稀因子，減少數(shù)據(jù)中的冗余，在相鄰的抽取點間以直線連續(xù)或曲線擬合、瓦片數(shù)據(jù)回溯融合的方式，加快地圖的在線加載速率。

1 算法設(shè)計

移動GIS多層空間非線性抽稀回溯算法是根據(jù)移動互聯(lián)網(wǎng)應(yīng)用特點，在GIS引擎提供API數(shù)據(jù)接口，運用非線性數(shù)學(xué)模型建立一種針對數(shù)據(jù)源類型結(jié)合業(yè)務(wù)數(shù)據(jù)類型(道路、河流、橋梁、綠地、建筑物等)多級擴展細分圖層進行分層抽稀、瓦片數(shù)據(jù)回溯的數(shù)據(jù)融合與加載方法。算法的核心是改進的非線性抽稀，根據(jù)GIS數(shù)據(jù)源類型劃分基礎(chǔ)層，在各層采用以步長、線段長度、垂距為抽稀因子的旋轉(zhuǎn)坐標(biāo)軸方法對曲線上各空間數(shù)據(jù)點到水平軸的距離進行度量，對距離小于閥值的數(shù)據(jù)點進行直線擬合，用擬合直線代替待刪數(shù)據(jù)點與保留點相連，在此過程中閥值的選取是動態(tài)非線性的，避免因為閥值的區(qū)分度太低而造成抽稀失真。

非線性抽稀回溯算法可分為準(zhǔn)備階段和抽稀回溯階段，準(zhǔn)備階段有三個過程:一是對原始地圖空間數(shù)據(jù)進行切割，并記錄已切割好的數(shù)據(jù)塊各頂點坐標(biāo)值;二是根據(jù)地圖可以將加載的各類數(shù)據(jù)源分為N個基礎(chǔ)層:Ⅰ層、Ⅱ?qū)印璑層(II≤N≤X);三是對原始數(shù)據(jù)進行分層抽稀，抽稀率最低的是第Ⅰ層，依次遞增，最高的是第N層。將這N個基礎(chǔ)層的第一次抽稀結(jié)果作為下一個階段的輸入，為二次抽稀與回溯計算閥值依據(jù)。算法框架如圖1所示。

圖1 算法框架

多層空間非線性抽稀回溯算法抽稀階段是根據(jù)實際加載地圖時所調(diào)用的圖層數(shù)量及其對應(yīng)的圖層編號換算成對應(yīng)的層次，對其上一鄰層進行二次抽稀，同時對其下一鄰層進行回溯，再將抽稀與回溯結(jié)果進行數(shù)據(jù)融合與瓦片數(shù)據(jù)拼接存儲。算法過程假設(shè)經(jīng)過對具體圖層的轉(zhuǎn)換和計算，得到層數(shù)為n(i＜n＜i+1，其中i為某個基礎(chǔ)層，i+1為與其相鄰的下一基礎(chǔ)層)，介于i層與i+1層之間，于是對i層進行第二次抽稀，同時采用反距離加權(quán)插值法對i+1層進行回溯，最后將抽稀和回溯的結(jié)果做數(shù)據(jù)融合處理，把各個處理好的空間數(shù)據(jù)塊重新以瓦片形式拼接存儲。

2 算法流程

2.1 數(shù)據(jù)切割與分層算法改進

GIS地圖的總體數(shù)據(jù)量非常龐大，直接對原始空間數(shù)據(jù)進行抽稀將會使矢量計算初始化過程非常緩慢［6］。因此，在抽稀前首先對空間數(shù)據(jù)進行非線性切割，使用二維表格記錄切割好的每個數(shù)據(jù)塊各個頂點的坐標(biāo)值，用于在抽稀后對空間數(shù)據(jù)塊進行瓦片拼接還原。

為了在任意業(yè)務(wù)需求下都能夠快速顯示數(shù)據(jù)，采取分層策略。分層以數(shù)據(jù)源類型和業(yè)務(wù)數(shù)據(jù)類型為依據(jù)，如建筑物數(shù)據(jù)(點數(shù)據(jù))，道路數(shù)據(jù)、河流數(shù)據(jù)(線數(shù)據(jù))，綠地、地塊數(shù)據(jù)(面數(shù)據(jù))。將具備最少數(shù)據(jù)的圖層設(shè)置為Ⅰ層，最多數(shù)據(jù)的圖層設(shè)置為N層，N的取值根據(jù)圖層總數(shù)的大小而定，最高不超過X層。將中間的部分圖層均勻設(shè)置為Ⅱ、Ⅲ、…、N－1層?？梢奍層的抽稀率最低，保留的數(shù)據(jù)點最多;N層的抽稀率最高，保留的數(shù)據(jù)點最少。N個層次的抽稀結(jié)果將會作為其他圖層的抽稀，以及非線性閥值和空間數(shù)據(jù)反距離加權(quán)插值實現(xiàn)回溯算法的依據(jù)。

切割后針對不同的層次空間數(shù)據(jù)分別進行抽稀，采用改進的非線性抽稀算法:首先進行曲線距離度量，以曲線兩端連線方向作為橫軸，對原坐標(biāo)系進行旋轉(zhuǎn)，利用旋轉(zhuǎn)的角度快速計算出曲線上各個數(shù)據(jù)點到新的橫軸之間的距離;然后進行動態(tài)非線性閥值選取，根據(jù)相鄰空間數(shù)據(jù)點之間的間距與數(shù)據(jù)總數(shù)可以計算出每個數(shù)據(jù)塊的密集度，將所有密集度進行分級，設(shè)定最低為0級，最高為10級，結(jié)合要抽稀的目標(biāo)層數(shù)進行閥值選取，除了0級I層和10級N層的閥值需要進行實驗選取以外，其余閥值均通過計算得到;最后進行直線擬合，將度量出來的各個距離與對應(yīng)閥值進行對比，判斷出保留點與待剔除點，將相鄰保留點之間的待剔除點用直線進行擬合，即各待刪點到該直線的距離之和最小;將所有擬合直線與保留點相連，即為曲線抽稀結(jié)果，并直接為回溯提供依據(jù)。

2.2 算法實現(xiàn)

2.2.1 曲線距離度量

在原始空間矢量數(shù)據(jù)中建立x、y坐標(biāo)，之后在算法曲線的兩個端點之間設(shè)定一條連線建立曲線距離度量。以該連線作為新的橫軸，建立新的直角坐標(biāo)系。新的坐標(biāo)系根據(jù)空間數(shù)據(jù)選取值是在舊的坐標(biāo)系基礎(chǔ)上進行了θ角度旋轉(zhuǎn)，原點為O，兩個端點分別為P1和PM，曲線上的點可表示為Pi和Pj(1≤i≤M，1≤j≤M)。曲線度量新的坐標(biāo)軸表示為x'Oy'，如圖2所示。

圖2 曲線距離度量示意

非線性抽稀曲線度量依據(jù)幾何原理旋轉(zhuǎn)角度正弦、余弦，判斷了新象限與距離，設(shè)定步驟如下:

Step1:計算點Pi在新坐標(biāo)系下的坐標(biāo)(xi'，yi')。根據(jù)幾何原理，得到旋轉(zhuǎn)角度θ的正弦、余弦值:

將向量OPi旋轉(zhuǎn)θ度，即相當(dāng)于讓其與矩陣A右乘，設(shè)Pi的新坐標(biāo)為(xi'，yi')，則有:

Step2:根據(jù)(xi'，yi')的值可以判斷點Pi在新坐標(biāo)系下的象限，從而得到Pi到x'軸的距離li。

(1)當(dāng) x'i＞0，y'i＞0，Pi屬于第Ⅰ'象限，此時 li=+x'i－ xN/cosθ

(2)當(dāng) x'i＜0，y'i＞0，Pi屬于第Ⅱ'象限，此時 li=－x'i

(3)當(dāng) x'i＜0，y'i＜0，Pi屬于第Ⅲ'象限，此時 li=－x'i+xN/cosθ

(4)當(dāng) x'i＞0，y'i＜0，Pi屬于第Ⅳ'象限，此時 li=

Step3:計算點Pi的相鄰點Pi+1在新坐標(biāo)系下的坐標(biāo)(xi+1'，yi+1')。令△P為兩個相鄰點之間的直線向量，則其在新坐標(biāo)系下表示為△P'。有:

Step4:重復(fù)Step2的步驟，得到Pi+1到x'軸的距離li+1。

Step5:重復(fù)Step3和Step4的步驟，得到曲線上所有點到x'軸的距離。

上述進行曲線距離度量的方式充分利用了前一個點的計算結(jié)果，除了第一個點的距離計算稍微復(fù)雜以外，后續(xù)計算比較簡單，避免了傳統(tǒng)的距離計算需要反復(fù)開方的方式，降低了算法的復(fù)雜度，提高了算法的效率。

2.2.2 動態(tài)非線性閥值選取

移動GIS多層空間抽稀曲線上各數(shù)據(jù)點的距離度量出來后，將依次與閥值進行對比，距離大于閥值的將保留，距離小于閥值的將被剔除?？梢婇y值的大小決定了空間數(shù)據(jù)點是否會被剔除:閥值太大會造成大量數(shù)據(jù)被刪除，其中很有可能包括GIS熱點數(shù)據(jù);閥值太小則會造成冗余數(shù)據(jù)沒有被刪除，抽稀效果不好。考慮到移動GIS地圖中不同的區(qū)域熱點數(shù)據(jù)的密集程度不同，且經(jīng)過分層后，每一層的抽稀程度也有區(qū)別，因此采用動態(tài)非線性閥值選取方式，最大程度保留有用數(shù)據(jù)，剔除冗余數(shù)據(jù)。

對空間數(shù)據(jù)點的密集程度進行分級，分析每個數(shù)據(jù)塊中各相鄰點之間的間距，結(jié)合數(shù)據(jù)塊中數(shù)據(jù)點的個數(shù)，可以得到數(shù)據(jù)點的密集度?？臻g數(shù)據(jù)密集度可以表示為:

其中Dij(x)為編號第ij號的空間數(shù)據(jù)塊數(shù)據(jù)密集度，N為該數(shù)據(jù)塊中相鄰數(shù)據(jù)對的個數(shù)，d(xi，xi+1)為相鄰數(shù)據(jù)對之間的間距，M為該數(shù)據(jù)塊中數(shù)據(jù)點總個數(shù)。將密集度最高的數(shù)據(jù)塊設(shè)為10級，密集度最低的數(shù)據(jù)塊設(shè)為0級，則其余數(shù)據(jù)塊的級數(shù)表示為:

將數(shù)據(jù)塊的級數(shù)與要抽稀的層數(shù)之和作為選定閥值的依據(jù)，首先對0級數(shù)據(jù)塊Ⅰ層抽稀目標(biāo)進行閥值選取，根據(jù)大量實驗結(jié)果得到最合適的閥值ε1;再對10級數(shù)據(jù)塊Ⅳ層抽稀目標(biāo)進行閥值選取，得到閥值εN(N為數(shù)據(jù)塊總個數(shù))。剩余級別與層數(shù)結(jié)合所選取的閥值將以ε1和εN作為參考依據(jù)，計算公式如下:

其中L為抽稀的目標(biāo)層數(shù)(Ⅰ≤L≤Ⅳ)，εi為級數(shù)為Si進行L層抽稀的閥值。可見閥值的選取是非線性的，當(dāng)同級別同層次抽稀時，閥值不變;但級別或?qū)哟斡凶兓瘯r，閥值會相應(yīng)進行動態(tài)改變，以便適應(yīng)不同的抽稀需求。

2.2.3 直線擬合

經(jīng)過閥值對比后，GIS待剔點理應(yīng)被刪掉。然而，非性線GIS抽稀與回溯若直接將保留點用直線連接，將導(dǎo)致剔除點所在的區(qū)域誤差較大，因此采用直線擬合的方式對所有待刪點的整體進行逼近。擬合前后的效果如圖3所示。

圖3 擬合前后效果對比

選取各點的距離最大值lmax與給定閥值ε進行比較。若lmax＜ε，則將該點記為Qi，否則保留該點的記法。被保留記法的點將曲線分成了兩部分，分別對這兩部分重復(fù)上述操作，直到將曲線上所有的數(shù)據(jù)點重新處理。

經(jīng)過處理的數(shù)據(jù)點分為保留點集合P和待刪點集合Q。設(shè)兩個相鄰保留點之間的待刪點集合為Q1，Q2…QN，分別將待刪點Qi(1≤i≤N)集合進行直線擬合，方法如下。

設(shè)待刪點集合 Qi中各點的坐標(biāo)分別為(x1'，y1')、(x2'，y2')…(xM'，yM')，其幾何中心點坐標(biāo)為:

設(shè)u為矩陣XTX最小特征值所對應(yīng)的特征向量，則=λu(λ為令的最后一個值為－1的常量)時，目標(biāo)函數(shù)F(X，Y)取值最小。

將各個相鄰保留點之間的待刪點全部進行直線擬合后，選取抽稀層數(shù)與閥值最佳值，使各段擬合直線與保留點連接起來，刪除待刪點，獲得曲線抽稀結(jié)果，并為高層的空間數(shù)據(jù)回溯提供反距離加權(quán)插值依據(jù)。

2.3 回溯與數(shù)據(jù)融合拼接

在移動GIS多層空間矢量抽稀過的數(shù)據(jù)，可能會有數(shù)據(jù)抽稀過多或過少的情況，為保證抽稀算法的精確度，在上一鄰層抽稀的同時依托曲線度量、動態(tài)非線性閥值與直線擬合的最優(yōu)計算進行下一鄰層的數(shù)據(jù)回溯。此時并非將數(shù)據(jù)還原為原始數(shù)據(jù)，而是將其還原到目標(biāo)圖層的層次(介于標(biāo)準(zhǔn)層次之間)。采用空間數(shù)據(jù)反距離加權(quán)插值對高層數(shù)據(jù)進行回溯。

選取圓形作為搜索區(qū)域，半徑為R。設(shè)S為數(shù)據(jù)塊面積，M為數(shù)據(jù)塊在該層的數(shù)據(jù)點總數(shù)，Mmin為搜索區(qū)域內(nèi)數(shù)據(jù)點最少的點數(shù)，則存在πR2=SMmin/M。設(shè)MR為以搜索半徑為R的搜索區(qū)域內(nèi)的數(shù)據(jù)點數(shù)，已知數(shù)據(jù)點為 Pi(xi，yi)(1≤i≤MR)，則待插點 Pj(xj，yj)的計算公式如下:

式中γ取值為0至5的整數(shù)，dij為已知點Pi到待插點Pj的距離。

同一個空間數(shù)據(jù)塊經(jīng)過抽稀與回溯后，將抽稀結(jié)果與回溯結(jié)果進行融合，目的是提高數(shù)據(jù)保真度，同時實現(xiàn)以瓦片數(shù)據(jù)形式存儲，減少矢量高能耗計算，提升移動GIS加載速度。融合過程可簡單描述如下:設(shè)GIS抽稀結(jié)果數(shù)據(jù)集為 V{v1，v2，…，vN}，回溯結(jié)果數(shù)據(jù)集為 B{b1，b2，…，bN};初始化令結(jié)果集 R=V，依次取出集合B中的元素與集合V中的元素進行匹配，若發(fā)現(xiàn)無匹配的數(shù)據(jù)項，則證明該元素是被誤刪的數(shù)據(jù)，將其加入集合R中，反復(fù)上述步驟直到集合B中的最后一個元素匹配完畢;得到的結(jié)果集R即為對該數(shù)據(jù)塊進行某層次抽稀的最終結(jié)果。

GIS圖層按照切割時所記錄的頂點坐標(biāo)值進行掃描匹配，對數(shù)據(jù)塊進行拼接與瓦片數(shù)據(jù)存儲，完成整個抽稀與回溯過程。

3 算法測試

算法測試采用仿真測試和ArcGIS引擎實際開發(fā)測試兩種形式，對單次抽稀算法和多層抽稀回溯算法進行對比。其中單次抽稀算法包括DP算法、垂距限值法、金字塔切片法、線段過濾法。同時使用ArcGIS Runtime SDK for Andriod應(yīng)用開發(fā)工具包，對各類單次抽稀算法和多層空間非線性抽稀回溯算法進行編程實現(xiàn)，同時編寫一段檢測代碼測試每個算法的性能指標(biāo)。首先使用MATLAB對各算法理論進行仿真，理想條件下多層空間非線性抽稀回溯算法與各個單次抽稀算法的仿真曲線如圖4所示，算法加載時間與處理能力對比如圖5所示。

圖4 算法仿真曲線圖

圖5 算法加載時間與處理能力仿真對比圖

圖4表明抽稀后的數(shù)據(jù)以使用多層空間非線性抽稀回溯算法與原數(shù)據(jù)的擬合程度最高，圖5表明同樣的數(shù)據(jù)量，抽稀回溯算法所采用的加載時間最短，除了剛開始對基礎(chǔ)層的抽稀耗時較多外，后續(xù)的數(shù)據(jù)量增大并不會對加載時間造成太大影響。加載速度的提高得益于抽稀回溯數(shù)據(jù)融合與拼接瓦片數(shù)據(jù)存儲，極大減少了矢量計算所耗費的資源。

4 結(jié)束語

移動GIS多層空間非線性抽稀回溯算法是在移動互聯(lián)網(wǎng)、北斗衛(wèi)星導(dǎo)航、GPS等物聯(lián)網(wǎng)技術(shù)進一步高精度融合，交通、物流、生活應(yīng)用GIS移動化趨于普適而提出的一種疊加于多業(yè)務(wù)功能的空間數(shù)據(jù)抽稀算法。它通過動態(tài)非線性閥值的選取、原數(shù)據(jù)的直線擬合等對遠程加載GIS空間數(shù)據(jù)進行分層抽稀，減少數(shù)據(jù)流量與提高加載速度。算法進行多層數(shù)據(jù)空間二次抽稀與回溯，將抽稀結(jié)果和回溯結(jié)果進行融合與拼接，采用瓦片數(shù)據(jù)形式存儲，保證最終抽稀效果最大程度保留原始數(shù)據(jù)，提升加載速度。實驗表明從加載時間、抽稀率和還原率等方面，該算法都優(yōu)于傳統(tǒng)的單次抽稀算法，能很好地滿足移動GIS的應(yīng)用需求。

［1］李曉軍，吳金輝，吳嘯，等.基于Android的移動監(jiān)察GIS平臺研發(fā)與分析［J］.測繪通報，2012(10):637－639.

［2］潘翔.基于GIS的交通物流預(yù)警圖像傳輸優(yōu)化［J］.河池學(xué)院學(xué)報，2014，34(2):65－70.

［3］盧銀宏，岳東杰.基于總體最小二乘的Douglas－Peucker算法在多波束測深數(shù)據(jù)抽稀中的應(yīng)用［J］.水利與建筑工程學(xué)報，2012，10(2):4－5.

［4］Shen Yunzhong，Li Bofeng，Chen Yi.An iterative solution of weighted total least－ squares adjustment［J］.Journal of Geodesy，2010，85(4):229－238.

［5］馮宇瀚，殷曉冬，王少帥，等.基于三角網(wǎng)構(gòu)建海底DEM的抽稀算法［J］.海洋測繪，2012，32(6):33－35.

［6］龔健雅，李小龍，吳華意.實時GIS時空數(shù)據(jù)模型［J］.測繪學(xué)報，2014.43(3):226－232，275.