增強型矢量數據壓縮算法的設計與實現

摘要：首先論述了幾種傳統矢量數據壓縮算法，在分析各種算法單獨用于電子地圖壓縮時存在問題的基礎上提出一種矢量數據壓縮算法，并對其壓縮效果進行評價。

關鍵詞：矢量數據壓縮；壓縮算法；壓縮效果評價；地理信息系統

中圖分類號：TP331文獻標志碼：A

文章編號：1001-3695(2007)12-0393-03

自從數字地球^[1]的構想提出以來，數字地圖的應用越來越廣泛。特別是在導航領域中，數字地圖的應用已經不再局限于原先的車載系統和航海運輸等領域，在個人定位導航系統中的應用同樣隨處可見。然而，導航產品的這種微型化、高度集成化的趨勢勢必會導致其在運算處理能力、存儲能力等方面受到更多的限制。因此，對數字地圖也提出了更高的要求，要求數字地圖的存儲能夠更加高效、傳輸能夠更加迅速。與此同時，對數字地圖的高效存儲和快速傳輸都對數字地圖的高效壓縮提出了要求^[2]。

數字地圖按內部數據結構區分基本上可分為兩大類^[3]，即矢量結構和柵格結構。在表達不同的地理現象時，這兩種方法各有優缺點。柵格地圖的壓縮與圖像壓縮是類似的。圖像壓縮已有許多有效算法可利用。本文不對柵格地圖的壓縮作探討。矢量數據壓縮是從數據集S中抽出一個子集A，在一定的精度范圍內，要求這個子集所含的數據量盡可能少，并盡可能近似地反映S的原貌^[4]。目前，已經有很多成熟的矢量數據壓縮算法。由于將其單獨用于矢量電子地圖壓縮時會產生很多問題，必須研究一種新的矢量數據壓縮算法，使之能夠較好地對電子地圖進行壓縮。

3壓縮效果評價

壓縮的效果可以依據簡化后曲線的總長度、坐標平均值與原始曲線相應數據的對比來判別。原始曲線與簡化后曲線相應數據的差別越小，表示簡化后的曲線與原曲線越相似，逼真度越高。

為了對上述算法的效果進行評價，筆者在Windows XP平臺上，使用VC 6．0實現了這種新型的矢量數據壓縮算法。原始數據采用目前非常流行的MapInfo矢量數據，比例尺精度為1∶10 000；實驗數據采樣自武漢市和平大道上建設一路至建設十路這段曲線。根據應用需要和制圖比例尺要求，這里選擇閾值為2 m（即1∶10 000的電子地圖上面的0．2 mm），以此對應上述壓縮算法的限差。實驗結果如表1、圖7所示。

由表1可以看出，在應用本文論述的新型矢量數據壓縮算法或光欄法對曲線進行簡化后，曲線的長度和坐標平均值與原始曲線相應數據的差別最小，逼真度最好。然而從圖7可以看出，原始曲線在應用光欄法對曲線進行簡化后，彎曲特征點被舍去了，從而造成了地形的失真。應用本文的新型矢量數據壓縮算法對原始曲線進行簡化后，彎曲特征點仍然能夠被保留。此外，本文論述的新型矢量數據壓縮算法可以在電子地圖數字化時實時處理。由于其時間復雜度和空間復雜度在大多數情況下僅僅為O(n)（n為曲線節點的個數）^[8]，

壓縮的速度較快。

4結束語

本文的新型矢量數據壓縮算法可以有效彌補傳統算法的缺陷，特別是對電子地圖壓縮的處理更加有效。壓縮后的圖形逼真度較高、壓縮效果明顯、處理速度較快，為個人定位導航系統上電子地圖的壓縮提供了一條可行的途徑。

參考文獻：

[1]李德仁. 數字地球與3S技術[C]//中國地理信息系統協會論文集.北京: 中國地理信息系統協會， 1999：1-6.

[2]鐘尚平，高慶獅.一類矢量地圖的無損壓縮算法[J].系統仿真學報， 2004，16(10):2189-2194.

[3]鄔倫.地理信息系統—原理方法和應用[M].北京:科學出版社，2002：138－140.

[4]鄭海鷹.計算機地圖制圖[M]. 鄭州: 中國人民解放軍測繪學院出版社，1997：59-60.

[5]朱子豪.地理資訊系統技術[EB/OL].[2006-03].http://www.geog.ntu.edu.tw/course/gistech.

[6]DOUGLAS D H，PEUCKER T K.Algorithm for the reduction of the number of points required to represent a digitized line or its caricature[J].The Canadian Cartographer，1973，10(2):112－122.

[7]張宏.地理信息系統算法基礎[M].北京:科學出版社， 2006:120－124.

[8]劉曉紅，李樹軍.矢量數據壓縮的角度分段道格拉斯算法研究[J].四川測繪，2005，28(2):51-52.

[9]吳立新，史文中.地理信息系統原理與算法[M].北京:科學出版社， 2003:172－174.

[10]王凈，江剛武.無拓撲矢量數據快速壓縮算法的研究與實現[J].測繪學報，2003，32(2):173－177.

[11]BOUCHEHAM B， FERDI Y， BATOUCHE M C. Recursive versus sequential multiple error measures reduction: a curve simplification approach to ECG data compression[J].Computer Methods and Programs in Biomedicine，2006，81(2):162－173.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”