面向移動用戶的矢量地圖數據壓縮方法

陳志榮，尹天鶴，徐財江，周 峰（．寧波工程學院理學院，浙江寧波3506；．寧波市國土資源信息中心，浙江寧波35040）

?

面向移動用戶的矢量地圖數據壓縮方法

陳志榮1，尹天鶴1，徐財江2，周 峰1
（1．寧波工程學院理學院，浙江寧波315016；2．寧波市國土資源信息中心，浙江寧波315040）

摘 要：隨著第4代移動通信技術（4G）的普及以及4核和8核CPU手機的出現，無線網絡數據傳輸能力大幅提升，移動終端性能大為改善．移動用戶的廣泛參與使得地理信息的采集和上傳下載數據巨量，致使有限的帶寬傳輸速率與海量信息傳輸需求不匹配．針對移動用戶對空間數據的高壓縮率和高失真度容忍率的需求，提出了一種新的矢量地圖數據壓縮方法，通過去除冗余點、平移坐標軸和轉換數據類型3個步驟，可2次壓縮數據．測試結果顯示，該方法的綜合壓縮率接近70%，可有效降低無線網絡數據傳輸負荷，節約移動終端的存儲空間．

關 鍵 詞：數據壓縮；移動用戶；矢量地圖數據；位置服務

0 引 言

位置服務（location－based service，LBS）是指采用定位技術獲取用戶終端的位置信息，通過移動通信網絡，在電子地圖平臺的支持下為用戶提供定位、導航、查詢和識別等與空間位置相關的增值服務業務［1］．位置服務是高速移動互聯網技術與地理空間信息技術相結合的產物，它以移動通信技術為承載平臺，通過移動終端為廣大移動用戶提供信息類業務（如旅游、天氣、交通、問路、黃頁、廣告）、娛樂類業務、車輛調度業務、跟蹤類業務和急救類業務等各種基于位置的空間信息服務，被全球許多移動運營商和咨詢機構視為下一代移動網絡的核心業務．相對于普通電腦客戶端，移動終端是指借助無線網絡技術接入網絡的具有有限計算資源的設備［2］．在利用移動地理信息服務時，移動用戶不僅受到無線網絡帶寬窄和穩定性差的限制，也受到移動設備存儲空間小、顯示屏小且分辨率低和CPU計算能力弱的限制，從而對海量空間數據的存儲、傳輸、顯示和分析存在困難［3］．為使移動空間數據盡可能簡潔，空間數據的壓縮顯得尤為重要．

當前位置服務中的基礎地圖數據由道路、行政區劃、房屋、公交站點等點狀、線狀及面狀矢量數據構成．對移動空間信息服務中空間數據的壓縮，主要是對其中的矢量數據的壓縮．點狀圖形要素可以看成是特殊的線狀圖形要素，面狀圖形要素的基礎也是線狀圖形要素，由一條或多條線狀圖形要素圍成［4］．因此，線狀圖形要素的壓縮就成為矢量數據壓縮中最重要的問題．一般而言，矢量數據壓縮是從組成曲線的點集合A中抽取一個子集B，用這個子集B在一定的精度范圍內盡可能地反映原數據集合A，而這個子集B的點數應盡可能少［5］．當前矢量數據壓縮方法主要有距離控制類方法（如垂距限值法和曲線多邊形逼近算法，后者通常也稱Douglas－Peucker方法［6－8］）、角度控制類方法（如角度限值法［9］）以及基于小波技術的壓縮方法［10］等．近年來，矢量地圖數據壓縮方面的研究主要集中在Douglas－Peucker方法的完善和改進上，如尹路等［11］將空間對象間的拓撲關系因素添加到算法中，李帥等［12］提出一種改進的矢量曲線特征點提取方法．部分學者提出了一些新的矢量數據壓縮思路，如譚國律等［13］利用動態規劃思想，討論單實體和多實體矢量數據的壓縮方法；余先川等［14］利用整數小波變換方式處理坐標數據，實現了較高壓縮比的空間矢量數據無損壓縮；李青元等［15］提出了利用int甚至short型代替float和double型來存儲空間坐標點的方法，以取得較高壓縮比例．這些方法主要面向傳統的空間數據管理需求，對壓縮后的數據精度要求較高．隨著WebGIS（網絡地理信息系統）的廣泛應用和移動位置服務的逐漸深入，提出了有限帶寬場景下的矢量數據壓縮新需求，如趙艷偉等［16］提出因受到互聯網帶寬的限制，WebGIS數據傳輸效率低的問題；柯敏毅等［17］對主流的矢量地圖數據壓縮技術在移動GIS中應用的優缺點進行了分析與比較；秦斌等［18］針對移動GIS壓縮存儲和傳輸的要求，改進了Douglas－Peucker算法；陳濤等［19］針對嵌入式設備硬件條件的限制，對矢量和柵格地圖數據進行了LOD分層、壓縮、分塊和建立索引等一系列處理．這些方法雖部分解決了有限帶寬帶來的問題．然而，專門針對移動位置服務的空間數據壓縮方法的研究仍較少．

在移動位置服務中，由于受到移動終端屏幕尺寸、分辨率和存儲空間的限制，對數據壓縮的精度要求較低，而對壓縮量要求較高．總體而言，用戶對空間數據壓縮的需求有所變化（見圖1）．現有的矢量數據壓縮方法在一定程度上還有較大的改進空間．基于此，設計了一種面向移動用戶的矢量地圖數據壓縮方法，并進行了大規模的數據測試分析，驗證了該方法的有效性和可行性．

圖1　用戶對空間數據壓縮需求的變化Fig．1 Changes of users demand in the spatial data

1 壓縮方法設計

圍繞移動用戶對空間數據壓縮率要求高、失真度容忍率高的新需求，本方法通過去除冗余點、平移坐標軸、轉換數據類型3個步驟，分2次壓縮數據，盡最大可能提高矢量地圖數據的綜合壓縮率，壓縮流程如圖2所示．其中，去除冗余數據點和轉換數據類型，均為有損壓縮．

1．1 去除冗余數據點

空間數據在制作過程中，人工制圖或通過智能軟件自動提取遙感影像邊界時，不可避免會產生一些冗余數據，從而增大了地圖數據量．在移動位置服務中，去除冗余點是精簡數據的必要步驟．作為優選，本研究采用經典Douglas－Peucker方法進行冗余點去除．Douglas－Peucker方法一般以遞歸方式實現，為了提高算法效率，本文將采用非遞歸形式代替遞歸形式．其算法流程如圖3所示．

圖2　壓縮方法設計Fig．2 Compression method design

圖3　Douglas－Peucker算法的非遞歸形式Fig．3 Non recursive form of Douglas－Peucker algorithm

（1）確定矢量地圖數據曲線的始點和終點，按順序將矢量地圖數據中從始點到終點的所有數據點輸入數據源，同時確定誤差允許范圍dmax；

（2）計算經過始點和終點的直線方程y＝kx＋b，計算始點和終點之間各個點到直線y＝kx＋b的距離，選取與直線y＝kx＋b距離最大的點P，得最大距離hmax，其中k為直線的斜率，b為直線在縱坐標軸上的截距；

（3）如果hmax＜dmax，則刪除始點和終點之間的數據點，以直線y＝kx＋b代替整條弧線；如果hmax≥dmax，則P為保留點，利用同樣的方法對始點與P點之間的曲線、P點與終點之間的曲線上的數據點進行檢測，以確定下一批保留點，依此循環，直至兩端點之間曲線上的數據點與兩端點連線的距離最大值小于dmax為止．

1．2 坐標軸平移

空間數據的坐標值通常采用double精度的（x，y）存儲．一般情況下，同一個圖斑上的數據點坐標值差別最多從百位開始，如縣市行政邊界．移動用戶常用的位置服務以城市內服務為主，如興趣點搜索、導航等，這些服務所需用到的地圖數據（如居民區圖斑），其數據點間坐標值差別通常僅為小數點后面的數值．因此，可在1．1節得到的精簡后的線狀數據基礎上，對數據點進行坐標軸平移，進一步精簡數據，為二次壓縮做準備．具體步驟如下：

（1）分別比較剩下數據點的橫坐標和縱坐標，得到橫、縱坐標的最小值為Xmin、Ymin；

（2）以Xmin作為在x軸方向的平移距離，Ymin作為在y軸方向的平移距離，并以點（Xmin，Ymin）作為坐標原點，建立新的坐標系；

（3）計算剩下數據點平移至新坐標系后的新坐標，在該線狀數據中新建2個double型參數，分別記錄偏移量Xmin和Ymin用于解壓縮，double型參數為雙精度浮點型參數．

1．3 數據類型轉換

double類型采用64位內存空間存儲數據，而坐標軸平移之后，數據點的坐標值位數減少，有效位數通常在9位以內，存儲空間有較大浪費．作為替代，采用32位存儲空間的unsigned int32類型（以下簡稱int32型）存儲數據點坐標，可以實現存儲空間的二次壓縮，且精度損失不大．

在1．2節得到的平移后的線狀數據基礎上，首先對各數據點的新坐標值進行放大處理：比較各數據點平移后的新橫坐標值X和新縱坐標值Y，得到橫縱坐標的最大值Xmax和Ymax，將Xmax乘以10m，補足其為9位數，再將其他數據點的新橫坐標值X乘以10m，同理將Ymax乘以10n，補足其為9位數，再將其他數據點的新縱坐標值Y乘以10n；在該線狀數據中新建2個int32型參數，分別記錄放大量m和n用于解壓縮，其中m和n均為正整數，int32型參數為32位整數型參數．

將放大后的線狀數據點的坐標類型由double型強制轉換為int32型，以減少數據點坐標記錄所占用的存儲空間．最后將int32型數據點集合，以及上述步驟的偏移量Xmin和Ymin、放大量m和n合并記錄為壓縮后的矢量地圖數據．

2 數據壓縮測試

2．1 樣本數據選取

為了驗證所設計的壓縮方法的可行性，選取某縣市行政區圖形作為樣本數據進行壓縮測試，其空間數據占52．8MB，對應樣本數據中的．shp文件．

數據繪制示例如圖4所示，從中可以看出，部分數據存在明顯冗余．因圖4右下角多邊形數據量較大，為便于測試，本文將以該圖形為例，詳細介紹壓縮測試過程．該圖形由96個數據點構成，每個數據點double精度的（x，y）存儲坐標值，始點P1坐標為（636 037．847 235，3 313 442．795 090），終點P96坐標為（636 037．843 345，3 313 442．789 755）．

圖4　樣本數據繪制示例Fig．4 Examples of sample data plotting

2．2 壓縮測試

2．2．1 Douglas－Peucker方法初次壓縮

采用Douglas－Peucker方法對矢量數據進行壓縮，首先要確定限差dmax的值，其實這也是圖形壓縮率的一個體現．限差越大，表明允許的誤差越大，圖形的失真度就越高．本文選取了0．5，1，1．5，2四種不同的限差，分別對樣本數據進行壓縮測試，結果如圖5所示，頂點數分別為原始圖形的29．2%，24．0%，20．8%，19．8%．可見壓縮過程對于減少原始數據點的數量效果明顯．隨著限差的不斷增大，圖形逐漸失真，特別是多邊形拐角處．為盡可能保留數據信息，本研究選用的冗余點限差為0．5，對原始數據文件進行壓縮，壓縮后文件大小為31．3MB，壓縮率為40．7%．

2．2．2 坐標軸平移

在初次壓縮得到的精簡的線狀數據基礎上，對剩余數據點進行坐標軸平移：

（1）分別比較剩余28個數據點的橫坐標和縱坐標，得到橫坐標最小值Xmin為635 889．373 510，縱坐標最小值Ymin為3 313 138．687 620；

（2）以635 889．373 510作為x軸方向的平移距離，3 313 138．687 620作為y軸方向的平移距離，并以點（635 889．373 510，3 313 138．687 620）為原點，建立新的坐標軸；

（3）依次計算28個數據點在新坐標軸中的坐標值，記錄其新坐標值數據為data X1（double［］）和dataY1（double［］）．

圖5　4種限差的壓縮效果Fig．5 Compression effects of four kinds of limits

2．2．3 二次壓縮

首先，在平移后的線狀數據基礎上，對各數據點的坐標值進行放大處理：

（1）比較各數據點平移后的橫坐標和縱坐標值，得橫坐標的最大值Xmax為205．900 290，縱坐標的最大值Ymax為304．107 470；

（2）對橫坐標的最大值205．900 290以及縱坐標的最大值304．107 470乘以106補足其為9位數，則放大量m與n為6；

（3）對平移后的各數據點的橫坐標和縱坐標值分別乘以106，記錄放大后28個數據點的橫坐標和縱坐標值分別為data X2（double［］）和dataY2 （double［］）．

其次，將放大后的線狀數據點的橫坐標data X2 （double［］）和縱坐標值dataY2（double［］）由double型強制轉換為int32型dataFX（int32［］）和dataFY （int32［］），從而減少數據占用的存儲空間．

最后，將偏移量635 889．373 510以及3 313 138．687 620，放大量6和6，以及最終得到的int32型數據點集合，合并記錄到壓縮后的矢量地圖數據文件中，從而實現對矢量地圖數據的壓縮．

對初次壓縮后的數據文件進行二次壓縮，壓縮后文件大小為16．0MB，綜合壓縮率達到了69．7%，壓縮效果明顯．

2．3 結果分析

為了比較解壓縮后圖像的失真情況，對解壓縮后的圖形和原始圖形進行疊加分析．如圖6所示，藍色為原始圖形，紅色為解壓縮后的圖形．可以看出圖形發生錯位的地方非常有限，在移動終端屏幕尺寸小、分辨率有限的情況下，已能滿足移動用戶的需求．

圖6　解壓縮后的圖形與原始圖形疊加分析Fig．6 Overlay analysis of the original and decompressed graphics

利用本壓縮方法，分別對大小為34．7，79．5，49．8MB的線（面）狀數據文件進行壓縮測試，綜合壓縮率分別達到了63．8%，72．1%，66．9%，平均壓縮率接近70%．

本方法在實現較高壓縮率的同時，在實際使用過程中還有一些需要完善的地方，分析如下：

（1）Douglas－Peucker方法剔除了冗余點的限差dmax，其取值應考慮移動用戶實際需求的動態比例尺大小，比例尺越大，dmax取值應越小，二者的對應關系尚需深入研究；

（2）在服務器中預生成各常用限差值dmax的金字塔級緩存數據，當位置服務請求地圖數據時，可結合移動用戶實際需求的比例尺來調用，提高服務效率；

（3）由于int32類型存儲值最大為4 294 967 295，因此坐標值最大只能放大為9位數．對于坐標值跨度較大的圖斑，如太湖邊界，數據類型轉換后小數位數據將舍棄較多，精度損失較大；

（4）對于精度要求較高的圖層，如國境線，不宜采用本方法．

3 結 論

針對移動用戶對地圖數據壓縮率要求高、失真率容忍度高的特點，設計了一種面向移動用戶的矢量地圖數據壓縮方法．首先利用矢量數據壓縮方法有效去除了冗余數據點，獲得精簡的線狀數據，在此基礎上對精簡后的線狀數據進行坐標平移，并放大各數據點的坐標值，進而強制將各數據點的數據類型由double型轉換為int32型，實現二次壓縮．本方法充分考慮移動用戶的需求特點，在移動用戶可接受的精度范圍內，最大限度地提高了矢量地圖數據壓縮率，有效減少了無線網絡在數據傳輸時的負荷，節約了移動終端存儲空間．

參考文獻（References）：

［1］ 李德仁，李清泉，謝智穎，等．論空間信息與移動通信的集成應用［J］．武漢大學學報：信息科學版，2002，27 （1）：l－6．LI Deren，LI Qingquan，XIE Zhiying，et al．The technique integration of the spatial information and mobile communication［J］．Geomatics and Information Science of Wuhan University，2002，27（1）：1－6．

［2］ 成建國，任福．移動環境中空間信息服務模式研究［J］．地理信息世界，2006，6（3）：57－60．CHENG Jianguo，REN Fu．Geographic information service model in mobile context［J］．Geomatics World， 2006，6（3）：57－60．

［3］ 張海堂，張永生，羅睿，等．移動GIS中點要素信息自適應服務技術研究［J］．計算機輔助設計與圖形學學報，2005，17（6）：1167－1172．ZHANG Haitang，ZHANG Yongsheng，LUO Rui，et al．Adaptive service of point features in mobile GIS［J］．Journal of Computer Aided Design ＆Computer Graphics，2005，17（6）：1167－1172．

［4］ 陳飛翔．移動空間信息服務關鍵技術研究［D］．北京：中國科學院遙感應用研究所，2006．CHEN Feixiang．Research on Key Technologies for Mobile Spatial Information Services［D］．Beijing：Institute of Remote Sensing Applications，CAS，2006．

［5］ 黃培之．具有預測功能的曲線矢量數據壓縮方法［J］．測繪學報，1995，24（4）：316－320．HUANG Peizhi．Vector data compression with prediction function［J］．Acta Geodaetica et Cartographica Sinica，1995，24（4）：316－320．

［6］ RAMER U．An iterative procedure for the polygonal approximation of plane closed curves［J］．Computer Graphics and Image Processing，1972，1（3）：244－256．

［7］ PAVLIDIS T，HOROWITZ S L．Segmentation of plane curve［J］．IEEE Trans Computers，1974，23：860－870．

［8］ 楊得志，王杰臣，閭國年．矢量數據壓縮的Douglas－Peucker算法的實現與改進［J］．測繪通報，2002（7）：18－19，22．YANG Dezhi，WANG Jiechen，LYU Guonian．Study of realization method and improvement of Douglas－Peucher algorithm of vector data compressing［J］．Bulletin of Surveying and Mapping，2002（7）：18－19，22．

［9］ 劉曉紅，李樹軍．矢量數據壓縮的角度分段道格拉斯算法研究［J］．四川測繪，2005，28（2）：51－52．LIU Xiaohong，LI Shujun．Study on subsection Douglas algorithm with the goniometry in generalization［J］．Surveying and Mapping of Sichuan，2005，28（2）：51－52．

［10］ 王玉海，朱長青．多進制小波在矢量地圖數據壓縮中的應用［J］．測繪科學，2003，28（3）：66－68．WANG Yuhai，ZHU Changqing．The vector relief data compression based on the multi－band wavelet［J］．Science of Surveying and Mapping，2003，28（3）：66－68．

［11］ 尹路，周初陽．基于Douglas－Peucker的矢量數據壓縮算法［J］．科技創新導報，2014，14：248．YIN Lu，ZHOU Chuyang．Vector data compression algorithm based on Douglas－Peucker［J］．Science and Technology Innovation Herald，2014，14：248．

［12］ 李帥，方源敏，喜文飛．基于無拓撲矢量曲線的快速壓縮算法［J］．科學技術與工程，2011，11（18）：4324－4327．

［13］ 譚國律，唐金秀．矢量數據的優化壓縮研究［J］．測繪通報，2010（4）：46－48，51．TAN Guolyu，TANG Jinxiu．The study for optimized compression of vector data［J］．Bulletin of Surveying and Mapping，2010（4）：46－48，51．

［14］ 余先川，張君蘭，張立保．基于整數小波變換的空間矢量數據壓縮方法［J］．中國地質大學學報，2011，36 （2）：381－385．YU Xianchuan，ZHANG Junlan，ZHANG Libao．Spatial vector data compression method based on integer wavelet transform［J］．Journal of China University of Geosciences，2011，36（2）：381－385．

［15］ 李青元，劉曉東，曹代勇．WebGIS矢量空間數據壓縮方法探討［J］．中國圖象圖形學報，2001（12）：1225－1229．LI Qingyuan，LIU Xiaodong，CAO Daiyong．Research in Web GIS vector spatial data compression methods［J］．Journal of Image and Graphics，2001（12）：1225－1229．

［16］ 趙艷偉，程振林，董慧，等．WebGIS多層次矢量數據壓縮方法及仿真實現［J］．系統仿真學報，2012，24（6）：1259－1264．ZHAO Yanwei，CHENG Zhenlin，DONG Hui，et al．Method of multilevel vector data compression for Web GIS［J］．Journal of System Simulation，2012，24（6）：1259－1264．

［17］ 柯敏毅，王國治．移動GIS中的空間矢量數據壓縮方法［J］．地理空間信息，2007，5（1）：24－26．KE Minyi，WANG Guozhi．Vector data compression of mobile GIS［J］．Geospatial Information，2007，5（1）：24－26．

［18］ 秦斌．移動GIS中矢量數據壓縮及傳輸問題研究［D］．昆明：昆明理工大學，2010．QIN Bin．Research on Vector Data Compression and Transmission in Mobile GIS［D］．Kunming：Kunming University of Science and Technology，2010．

［19］ 陳濤，翟京生，陳雙軍，等．嵌入式GIS中基于LOD的地圖數據組織模型設計［J］．測繪科學技術學報，2011，28（5）：374－377．CHEN Tao，ZHAI Jingsheng，CHEN Shuangjun，et al．Design of map data model based on LOD in embedded GIS［J］．Journal of Geomatics Science and Technology，2011，28（5）：374－377．

Vector data compression method for mobile users

CHEN Zhirong1，YIN Tianhe1，XU Caijiang2，ZHOU Feng1（1．College of Science，Ningbo University of Technology，Ningbo 315016，Zhejiang Province，China；2．Ningbo Municipal Information Center of Land and Resources，Ningbo 315040，Zhejiang Province，China）

Journal of Zhejiang University（Science Edition），2016，43（1）：045－050

Abstract：With the popularization of fourth generation（4G）mobile communication technology and the four／eightcore mobile phones，the data transmission capacity on the wireless network and the performance of mobile terminal are substantially improved．Mobile users are widely involved in making geographic information acquisition，upload and download．However，the requirements of data transmission will reach an unprecedented level，and are incompatible with the limited bandwidth．To meet with the new requirements of the higher compression rate and precision tolerance for spatial data，a vector data compression method is designed independently．Removing redundant points，parallel moving coordinate axis and data type conversion are used as three steps in the method to realize double compression．The tests reveal that the comprehensive compression rate of this method is close to 70%．It has effectively reduced the data transmission pressure in the wireless network，and has saved the memory space of mobile terminal．

Key Words：data compression；mobile user；vector map data；location－based service

作者簡介：陳志榮（1981－），女，博士，副教授，主要從事移動地理信息系統理論與應用研究，E－mail：chenzr29＠foxmail．com．

基金項目：國家自然科學基金資助項目（40901241，Q15D010011）；浙江省自然科學基金資助項目（Y5090377，Q15D010011）；浙江省科技廳／公益技術應用研究項目（2014C31076）．

收稿日期：2014－12－20．

DOI：10．3785／j．issn．1008－9497．2016．01．008

中圖分類號：P 208

文獻標志碼：A

文章編號：1008－9497（2016）01－045－06