基于嵌入式GIS 的矢量地圖數(shù)據(jù)處理技術(shù)研究

何 姣， 王 偉

（貴州電子科技職業(yè)學(xué)院 電氣工程系， 貴州 貴安新區(qū)550003）

0 引 言

隨著社會(huì)科技的發(fā)展，嵌入式設(shè)備已深入生活，成為必不可少的生活?yuàn)蕵吩O(shè)備。 地圖在嵌入式設(shè)備上的使用也越來越廣泛，地理信息系統(tǒng)技術(shù)（GIS）將地圖柵格數(shù)據(jù)、矢量數(shù)據(jù)和空間數(shù)據(jù)庫融合在一起，是地圖使用中信息最全面、應(yīng)用最廣泛的技術(shù)［1－3］。 目前PC 端的地理信息系統(tǒng)技術(shù)已非常成熟，而嵌入式設(shè)備處理器運(yùn)行速度慢、存儲(chǔ)空間有限，使得GIS 在嵌入式設(shè)備上的應(yīng)用受到了一定限制。 隨著人們生活中需求的數(shù)據(jù)量增多，嵌入式設(shè)備上的地圖加載速度越慢，常常出現(xiàn)卡頓、空白區(qū)等現(xiàn)象。 為加快嵌入式GIS 地圖數(shù)據(jù)的訪問和獲取更優(yōu)的地圖顯示，許多學(xué)者對地圖矢量數(shù)據(jù)處理進(jìn)行了研究，提出了消息調(diào)度模型［4］、分區(qū)索引［5］、數(shù)據(jù)壓縮［3］等研究方法。 這些技術(shù)在一定程度上改善了地圖矢量數(shù)據(jù)加載速度，但仍不能滿足社會(huì)發(fā)展中數(shù)據(jù)量不斷增大的應(yīng)用要求。 在硬件一定的條件下，可通過提高矢量地圖數(shù)據(jù)處理技術(shù)、提高數(shù)據(jù)壓縮量、運(yùn)算速度等方式來改善GIS 在嵌入式設(shè)備上的應(yīng)用。 垂線距離法和道格拉斯－普克法是矢量數(shù)據(jù)壓縮算法中的經(jīng)典，能夠?qū)崿F(xiàn)一定的矢量數(shù)據(jù)壓縮。 垂線距離法對矢量數(shù)據(jù)的壓縮程度低，并且容易失真；道格拉斯－普克法壓縮程度較好，能夠保持圖像基本特征，但運(yùn)算復(fù)雜度太高，有可能因?yàn)橹行狞c(diǎn)選擇不當(dāng)，引起矢量數(shù)據(jù)整體偏離，造成嚴(yán)重失真［4－6］。

為了提高GIS 矢量地圖在嵌入式設(shè)備上的運(yùn)行，本文從改變數(shù)據(jù)結(jié)構(gòu)、提出新的矢量數(shù)據(jù)壓縮算法兩方面進(jìn)行了研究。 為進(jìn)一步提高數(shù)據(jù)壓縮程度、降低算法運(yùn)算復(fù)雜度、避免中心點(diǎn)選取不正確引起整體圖像失真等現(xiàn)象，提出了一種新型的矢量數(shù)據(jù)壓縮算法。

1 改變地理坐標(biāo)數(shù)據(jù)精度

通常，地理坐標(biāo)數(shù)據(jù)采用雙精度（double）數(shù)據(jù)類型進(jìn)行存儲(chǔ)，該數(shù)據(jù)類型占用8 字節(jié)（64 位）空間。 而3.8 英寸的液晶顯示屏僅可以顯示240?320分辨率的圖像［6］，也就意味著對一張圖進(jìn)行縮放，最多能夠達(dá)到1 ∶1000 00。double 數(shù)據(jù)類型小數(shù)點(diǎn)后保留15 位數(shù)字，遠(yuǎn)遠(yuǎn)超過嵌入式屏幕分辨率能夠達(dá)到的要求。 因此，設(shè)計(jì)地理數(shù)據(jù)為double 數(shù)據(jù)類型，只是占用了嵌入式設(shè)備的內(nèi)存空間而沒有實(shí)際用處。 而單精度（float）數(shù)據(jù)類型僅占用4 個(gè)字節(jié)（32 位），小數(shù)點(diǎn)后保留6 位有效數(shù)字，完全能夠滿足屏幕最大縮放比例要求。 將地理坐標(biāo)數(shù)據(jù)的數(shù)據(jù)類型改為float 型，相當(dāng)于將數(shù)據(jù)存儲(chǔ)空間壓縮至1／2，既能滿足坐標(biāo)精度要求，又能有效節(jié)約嵌入式設(shè)備的存儲(chǔ)空間，提高嵌入式設(shè)備應(yīng)用程序處理速度，提高地圖顯示優(yōu)化效果。

2 地理數(shù)據(jù)圖層管理

與PC 端相比較，嵌入式設(shè)備具有屏幕分辨率低、處理器響應(yīng)速度慢、內(nèi)存空間小等特點(diǎn)。 一般情況下，在發(fā)布GIS 系統(tǒng)地圖時(shí)常選擇使用矢量地圖，將地圖分成“瓦片”數(shù)據(jù)進(jìn)行存儲(chǔ)。 在有限的屏幕范圍內(nèi)顯示地圖，首先加載粗大數(shù)據(jù)，當(dāng)用戶對地圖進(jìn)行放大時(shí)，加載更多詳細(xì)數(shù)據(jù)，當(dāng)用戶對地圖進(jìn)行縮小時(shí)，釋放掉多余數(shù)據(jù)，加載更多地圖瓦片。 設(shè)計(jì)空間地理數(shù)據(jù)庫中的地理要素進(jìn)行分層管理，文中以貴州省平壩區(qū)馬尾松森林環(huán)境監(jiān)測地圖為例。 地圖用于森林環(huán)境監(jiān)測系統(tǒng)，傳感器節(jié)點(diǎn)所在位置是最受關(guān)注的對象，放在第一圖層，默認(rèn)打開地圖時(shí)加載第一圖層矢量數(shù)據(jù)。 其余矢量數(shù)據(jù)，如：“小班”、“小班控制點(diǎn)”、 “路徑數(shù)據(jù)集”、“村”等要素放在優(yōu)先級低的圖層。 當(dāng)用戶對選定區(qū)域進(jìn)行放大時(shí)顯示，縮小時(shí)關(guān)閉的情況下，利用加載這部分?jǐn)?shù)據(jù)的空間資源，加載緩存更多地圖瓦片數(shù)據(jù)，等待新的用戶指令。

將空間數(shù)據(jù)庫中的地理要素進(jìn)行圖層管理，能夠避免浪費(fèi)嵌入式存儲(chǔ)空間和消耗CPU 運(yùn)行時(shí)間。除了將圖層設(shè)置顯示優(yōu)先級外，可以在地圖顯示View 上創(chuàng)建圖層按鈕控件，在相應(yīng)的Fragment 上使用PopupMenu 創(chuàng)建按鈕。 用戶可以自由選擇加載需要的要素圖層。 使用PopupMenu 開發(fā)組件創(chuàng)建自定義菜單，將菜單設(shè)置為全部可選。 當(dāng)選定需要的圖層要素時(shí)，將加載相應(yīng)的要素圖層，其效果如圖1 所示。

功能實(shí)現(xiàn)的主要代碼如下：

／ ／使用動(dòng)態(tài)地圖服務(wù)創(chuàng)建一個(gè)動(dòng)態(tài)地圖圖層

圖1 顯示或隱藏要素圖層Fig.1 Show or hide feature layers

mMapImageLayer ＝newArcGISMapImageLayer（String URL）；

mMapImageLayer.setOpacity（0.5f）；／ ／設(shè)置圖層透明度

mMap.getOperationalLayers（）.add（mMapImage Layer）；／ ／添加為可操作圖層

mLayers＝mMapImageLayer.getSublayers（）；／ ／獲取要素服務(wù)子圖層

3 矢量數(shù)據(jù)壓縮算法

矢量地圖數(shù)據(jù)的線面數(shù)據(jù)通常存在大量的頂點(diǎn)，設(shè)備加載地圖時(shí)，繪制大量的點(diǎn)將消耗較長時(shí)間，影響地圖響應(yīng)速度。 在嵌入式GIS 系統(tǒng)中，由于嵌入式設(shè)備自身的數(shù)據(jù)存儲(chǔ)量小、CPU 運(yùn)行速度低的特點(diǎn)，對地圖數(shù)據(jù)進(jìn)行壓縮是提高設(shè)備運(yùn)行速度的有效方法。 矢量數(shù)據(jù)壓縮是一種有損壓縮，通過刪除冗雜的數(shù)據(jù)點(diǎn)來簡化地圖，既能保持圖像的基本特性又能簡化數(shù)據(jù)量，提高設(shè)備運(yùn)行速度。

3.1 垂距限值法

曲線為一群點(diǎn)組成，從曲線的一端開始取點(diǎn)，連續(xù)取出三個(gè)點(diǎn)，計(jì)算中間點(diǎn)到兩端點(diǎn)連成的直線距離，若距離小于限定值ε，d ＜ε 則舍去中間點(diǎn)，d ≥ε 則保留中間點(diǎn)［7］。

3.2 道格拉斯－普克法

道格拉斯－普克法的基本思路是連接每一條曲線的首尾兩端，求出曲線上所有點(diǎn)到這條線段的距離，找出最大距離dmax并設(shè)定閾值ε。 若最大距離dmax小于閾值ε，則舍去這條線上的中間點(diǎn)，若最大距離dmax大于閾值ε，則將這條線以該點(diǎn)分為兩部分，分別對這兩個(gè)部分重復(fù)進(jìn)行上述過程［8］，如圖2所示。

圖2 垂距限值法Fig.2 Vertical distance limit method

道格拉斯－普克法能夠較好的保持曲線的基本特征，設(shè)置的閾值越小，曲線的還原性越高。 道格拉斯－普克法運(yùn)算過程中的遞歸運(yùn)算方法，使得數(shù)據(jù)運(yùn)算量過大，數(shù)據(jù)壓縮率降低。 設(shè)置閾值大，運(yùn)算量小，還原度不高。 并且，如果其中有一個(gè)點(diǎn)出現(xiàn)偏差將會(huì)導(dǎo)致后續(xù)所有計(jì)算都偏離原來的方向，引起圖像的嚴(yán)重失真［9－10］。

綜上所述，文中采用一種新型的矢量數(shù)據(jù)壓縮算法。 基于道格拉斯－普克法的分割思想，采用垂線距離法取出特征點(diǎn)，用相鄰三個(gè)特征點(diǎn)連接直線形成夾角斜率，判斷特征點(diǎn)的有效性，以有效特征點(diǎn)分割曲線，重復(fù)上訴過程，最終有效特征點(diǎn)組成壓縮后的圖像。 新型的矢量數(shù)據(jù)壓縮算法能達(dá)到降低運(yùn)算量，避免圖像整體走向失真的目的。

3.3 一種新型的矢量數(shù)據(jù)壓縮算法

3.3.1 算法思想

為了進(jìn)一步提高矢量數(shù)據(jù)壓縮算法的準(zhǔn)確度和降低道格拉斯－普克法的運(yùn)算復(fù)雜度，文中提出一種新的算法。 該算法的基本思想是：求出曲線上到端點(diǎn)直線垂線距離最大的點(diǎn)和距離，通過計(jì)算，取垂線距離以2 的n 次方遞減的方法求出特征點(diǎn)，用相鄰三個(gè)特征點(diǎn)連接直線形成夾角斜率判斷特征點(diǎn)的有效性，以有效特征點(diǎn)分割圖像。 重復(fù)上述步驟，最終求出曲線上所有滿足條件的點(diǎn)，組成壓縮后的圖像。

3.3.2 算法實(shí)現(xiàn)

（1）設(shè)定一個(gè)垂線距離限定值ε，斜率限定值θ。

（2） 一條曲線連接首尾兩端點(diǎn)為一條直線l，求曲線上所有點(diǎn)到該直線l 的距離，找出最大距離D，并保留此點(diǎn)。

（3） 以直線l 作為x 軸，其垂線為y 軸。 向y 軸正負(fù)兩個(gè)方向作距離為D／2 的直線l 的平行直線l1／2和l－1／2，取出交點(diǎn)。

（4） 以l1／2為例，判斷直線l1／2與曲線的交點(diǎn)個(gè)數(shù)N，若N ＝0，說明y 軸正方向上曲線不存在與直線l 距離大于D／2 的點(diǎn)，若N ＝1，說明y 軸正方向上曲線存在一個(gè)與直線l 距離等于D／2 的點(diǎn)。 若N ≥2，說明y 軸正方向上曲線存在多個(gè)與直線l 距離大于D／2 的點(diǎn)。

（5） 分別以直線l1／2和l－1／2作為x 軸，以l1／2為例，若步驟4 中直線l1／2與曲線交點(diǎn)個(gè)數(shù)N ≤1，則只向直線l1／2作為x 軸的y 軸負(fù)方向作距離為D／4 的平行線。 再重復(fù)步驟4。 若步驟4 中直線l1／2與曲線交點(diǎn)個(gè)數(shù)N ＞1 則需向y 軸正負(fù)兩個(gè)方向作距離為D／4 的平行線。 重復(fù)步驟4.

（6） 按照距離以2 的n 次方遞減的方式重復(fù)步驟3 － 5，直到D／2n ≤ε 時(shí)結(jié)束，取出的點(diǎn)的位置保持不變。

（7）計(jì)算相鄰3 個(gè)點(diǎn)連接而成的兩條直線的斜率，

斜率差Δk，若Δk ≥θ，則保留中間點(diǎn)作為分割點(diǎn)，反之舍棄。

（8）以分割點(diǎn)進(jìn)行切割曲線，將曲線分為若干段，重復(fù)以上步驟2～7，直到步驟2 中取到的最大距離D ＜ε，結(jié)束數(shù)據(jù)壓縮。 算法執(zhí)行過程如圖3 所示。

圖3 道格拉斯－普克法Fig.3 Douglas puck method

4 試驗(yàn)結(jié)果

試驗(yàn)采用的嵌入式設(shè)備主要配置參數(shù)為：ITOP 4412 嵌入式開發(fā)平臺(tái)、微處理器芯片三星Exynos 4412、電源管理芯片S5M8767 、64 位雙通道DDR3、EMMC 存儲(chǔ)芯片、USB 接口擴(kuò)展器（USB3505）以及4 組板對板連接器組成。 在嵌入式設(shè)備中實(shí)現(xiàn)新型的矢量數(shù)據(jù)壓縮算法，文中采用Android5.0 操作系統(tǒng)、Android studio 應(yīng)用開發(fā)平臺(tái)、Java 語言編程。試驗(yàn)數(shù)據(jù)來源于MapInfo 矢量數(shù)據(jù)，比例尺精度1 ∶10 000，電子地圖距離0.2 mm，將ε 值設(shè)置為0.2 mm，θ 值設(shè)置為1。 研究區(qū)域?yàn)榘岔樖衅綁螀^(qū)白云鎮(zhèn)小河村馬尾松林區(qū)，其經(jīng)緯度坐標(biāo)為：（106°15′8′～106°15′49′E，26°19′00′～26°19′32′N）。 試驗(yàn)結(jié)果如表1 所示。

圖4 新型矢量數(shù)據(jù)壓縮算法示意Fig.4 A new algorithm of vector data compression

表1 壓縮后曲線與原始曲線對比Tab.1 Comparison between compressed curve and original curve

由表1 可見，新型算法的曲線長度和坐標(biāo)平均值與原始曲線最接近。從算法復(fù)雜度上來看，新型算法的算法復(fù)雜度為o（2n － 1），遠(yuǎn)低于道格拉斯－普克法算法復(fù)雜度o（n3）。 算法復(fù)雜度越低，運(yùn)算速度越快。 新型的矢量數(shù)據(jù)壓縮算法從壓縮后矢量數(shù)據(jù)還原度和算法速度上都優(yōu)于道格拉斯－普克算法。

5 結(jié)束語

文中提供的新型矢量數(shù)據(jù)壓縮算法，彌補(bǔ)了道格拉斯－普克算法復(fù)雜度高、失真較大的不足。 經(jīng)新型的矢量數(shù)據(jù)算法壓縮后，結(jié)果更逼近原始矢量數(shù)據(jù)。 由此可見，本文提出的算法復(fù)雜度低、運(yùn)算速度快、適合在嵌入式設(shè)備上運(yùn)行。