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

潘 翔

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

0 引言

移動互聯網由于地理信息系統(Geographic Information System，GIS)的加入已發展成為一個全息位置服務(Location Based Services，LBS)的可視化時代，目前已廣泛應用于國土管理、城市規劃、交通運輸等各個領域［1］。移動GIS是一個物聯網(The Internet of things，IOT)熱點，催生了GIS技術創新與優化，ArcGIS、超圖等不斷地改進其抽稀算法，以高速的數據流轉與可視化信息交互適應隨時隨地的被標簽上LBS業務應用互聯互通［2］。

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

1 算法設計

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

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

圖1 算法框架

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

2 算法流程

2.1 數據切割與分層算法改進

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

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

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

2.2 算法實現

2.2.1 曲線距離度量

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

圖2 曲線距離度量示意

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

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

將向量OPi旋轉θ度，即相當于讓其與矩陣A右乘，設Pi的新坐標為(xi'，yi')，則有:

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

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

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

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

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

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

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

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

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

2.2.2 動態非線性閥值選取

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

對空間數據點的密集程度進行分級，分析每個數據塊中各相鄰點之間的間距，結合數據塊中數據點的個數，可以得到數據點的密集度。空間數據密集度可以表示為:

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

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

其中L為抽稀的目標層數(Ⅰ≤L≤Ⅳ)，εi為級數為Si進行L層抽稀的閥值。可見閥值的選取是非線性的，當同級別同層次抽稀時，閥值不變;但級別或層次有變化時，閥值會相應進行動態改變，以便適應不同的抽稀需求。

2.2.3 直線擬合

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

圖3 擬合前后效果對比

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

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

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

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

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

2.3 回溯與數據融合拼接

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

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

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

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

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

3 算法測試

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

圖4 算法仿真曲線圖

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

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

4 結束語

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

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

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

［3］盧銀宏，岳東杰.基于總體最小二乘的Douglas－Peucker算法在多波束測深數據抽稀中的應用［J］.水利與建筑工程學報，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］馮宇瀚，殷曉冬，王少帥，等.基于三角網構建海底DEM的抽稀算法［J］.海洋測繪，2012，32(6):33－35.

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