何 姣， 王 偉

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

0 引 言

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

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

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

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

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

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

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

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

／ ／使用動態(tài)地圖服務(wù)創(chuà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ù)通常存在大量的頂點，設(shè)備加載地圖時，繪制大量的點將消耗較長時間，影響地圖響應(yīng)速度。 在嵌入式GIS 系統(tǒng)中，由于嵌入式設(shè)備自身的數(shù)據(jù)存儲量小、CPU 運行速度低的特點，對地圖數(shù)據(jù)進行壓縮是提高設(shè)備運行速度的有效方法。 矢量數(shù)據(jù)壓縮是一種有損壓縮，通過刪除冗雜的數(shù)據(jù)點來簡化地圖，既能保持圖像的基本特性又能簡化數(shù)據(jù)量，提高設(shè)備運行速度。

3.1 垂距限值法

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

3.2 道格拉斯－普克法

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

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

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

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

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

3.3.1 算法思想

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

3.3.2 算法實現(xiàn)

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

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

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

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

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

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

（7）計算相鄰3 個點連接而成的兩條直線的斜率，

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

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

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

4 試驗結(jié)果

試驗采用的嵌入式設(shè)備主要配置參數(shù)為：ITOP 4412 嵌入式開發(fā)平臺、微處理器芯片三星Exynos 4412、電源管理芯片S5M8767 、64 位雙通道DDR3、EMMC 存儲芯片、USB 接口擴展器（USB3505）以及4 組板對板連接器組成。 在嵌入式設(shè)備中實現(xiàn)新型的矢量數(shù)據(jù)壓縮算法，文中采用Android5.0 操作系統(tǒng)、Android studio 應(yīng)用開發(fā)平臺、Java 語言編程。試驗數(shù)據(jù)來源于MapInfo 矢量數(shù)據(jù)，比例尺精度1 ∶10 000，電子地圖距離0.2 mm，將ε 值設(shè)置為0.2 mm，θ 值設(shè)置為1。 研究區(qū)域為安順市平壩區(qū)白云鎮(zhèn)小河村馬尾松林區(qū)，其經(jīng)緯度坐標為：（106°15′8′～106°15′49′E，26°19′00′～26°19′32′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 可見，新型算法的曲線長度和坐標平均值與原始曲線最接近。從算法復雜度上來看，新型算法的算法復雜度為o（2n － 1），遠低于道格拉斯－普克法算法復雜度o（n3）。 算法復雜度越低，運算速度越快。 新型的矢量數(shù)據(jù)壓縮算法從壓縮后矢量數(shù)據(jù)還原度和算法速度上都優(yōu)于道格拉斯－普克算法。

5 結(jié)束語

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