基于IWT和FCM的曲線矢量數據壓縮方法

摘 要:矢量數據壓縮對于GIS數據的存儲、網絡傳輸以及在移動設備中的使用都具有重要意義。在此通過對曲線矢量數據特點的分析，提出基于整數小波變換的矢量數據壓縮方法。壓縮方案包括3個主要流程:矢量數據整型化。曲線矢量數據具有相鄰坐標點間坐標值大小差別不大的特點，將坐標點間的差值轉換為整型的偏移量，用偏移量表示矢量數據的坐標點，利用整數小波變換處理偏移量序列。實驗表明，偏移量序列經過整數小波變換得到的小波系數序列在空間分布上更加集中，適合使用高效的編碼壓縮方法;對變換后的小波系數進行編碼壓縮。在此使用模糊C均值聚類字典法編碼實現了曲線矢量數據的有損編碼。通過實驗和其他壓縮算法結果的對比，該方法具有壓縮比較高，失真小的特點。關鍵詞:空間矢量數據; 整數小波變換; 模糊C均值聚類; 字典法編碼; SHP

中圖分類號:TN919-34文獻標識碼:A

文章編號:1004-373X(2010)22-0117-03

Method of Curve Vector Data Compression Based on IWT and FCM

ZHANG Jun-lan1， WANG Yi2

(1. College of Information Science and Technology， Beijing Normal University， Beijing 100875， China;

2. Ocean University of China， Qingdao 266003， China)

Abstract: The vector data compression has great significance in GIS data storage， network transmission and its application in mobile devices. A compression method based on the integer wavelet transform (IWT) and fuzzy C means (FCM) is proposed according to the analysis for the characteristic of curve vector data. The compressionscheme includes 3 steps: integer form of vector data， offset sequence processing with IWT and coding compression of transformed wavelet coefficients. The lossy coding of curve vector data was realized with the dictionary coding of FCM. Compared with other algorithms， this method has the characteristics of high compression ratio and less distortion.Keywords: spatial vector data; integer wavelet transform (IWT); FCM; dictionary encoding; SHP

對矢量化后的地形圖等進行壓縮處理的過程稱之為空間矢量數據的壓縮。地圖數字化中矢量數據的壓縮主要包括各種地形圖要素的數據壓縮。等高線是地圖中最多的圖形要素，所以對矢量化后的地圖的數據壓縮主要是對曲線的壓縮，目前討論最多的也是曲線矢量數據的壓縮。在此針對矢量數據的壓縮問題進行研究。

傳統的矢量數據壓縮方法的核心思想是從矢量數據的坐標點集中運用一定的算法抽取出最能體現矢量數據特征的子集。這類曲線矢量數據壓縮算法主要有:垂距限值法、角度限值法、Douglas-Peucker算法(Splitnig算法)，以及黃培之提出的具有預測功能的曲線矢量數據壓縮方法等[1-3]。

近年來，矢量數據的量化編碼壓縮算法的研究得到重視。鐘尚平等[4]根據平面矢量地圖文件的存儲特性，有機結合“無附加碼書”字典編碼方法，可逆并顯著地壓縮了矢量地圖。王立勝等[5]基于第二代小波變換理論實現了對空間矢量數據的無損壓縮。黃越峰等提出了使用基于整數小波變換和FFEP編碼的曲線數據壓縮方法[6]。Kolesnikov等提出了鏈碼方法用于矢量數據壓縮[7]。

本文首次提出結合實際矢量數據文件的存儲結構和曲線矢量數據的特性，將浮點型的矢量數據坐標值預處理成整型值表示的坐標值之間的偏移量。進而引入先進的整數小波變換對整型的偏移量序列進一步處理，分析變換后的小波系數的幅值，分布等特征后，采用了高效的基于模糊c均值聚類和字典法編碼方案進行壓縮存儲。實驗結果表明，本文的壓縮方法能夠達到較高的無損壓縮比。

1 矢量數據的整型化

矢量數據文件一般包括表示數據屬性和存儲結構的元信息和實際圖形的坐標點序列，其中浮點型坐標點序列占據了文件的絕大部分存儲空間。對矢量數據文件進行壓縮主要是對坐標點序列進行壓縮。

對于二維的平面矢量數據，坐標點序列由x坐標序列和y坐標序列組成。由于使用浮點型表示，每個坐標值占用的存儲空間為8個字節。本文使用的是基于整數小波變換的壓縮方法，因此首先是將坐標點序列用整型數表示。

由于同一曲線和多邊形實體的坐標點序列是密集的和順序的，因此相鄰點間的坐標值之差的變化范圍很小，可以用整型數來表示。對于由N個點序列([Xn，Yn]，n=0，1，2，…，N-1)表示的曲線或多邊形實體，坐標值整型化為([X′n，Y′n]n=0，1，2…N-1)過程如下:

步驟1: 記錄X0， Y0，令X0 ′ = 0，Y0 ′ = 0。

步驟2: 對于n=1，2，…，N-1，X′n=Xn-Xn-1Y′n=Yn-Yn-1。

步驟3: 已知Xn的最高精度為10-p，Yn的最高精度為10-q，則X′n=X′n×10p，Y′n=Y′n×10q。

2 整數小波變換及其在矢量數據壓縮中的應用

2.1 整數小波變換

傳統的小波變換又稱為第一代小波變換，其變換過程主要是利用小波濾波器組對圖像行列分別濾波，進行卷積運算，由于都是實數域的變換，即使待分析信號本身是整數序列，相應小波變換系數也是實數。由于數字圖像一般都是用整數表示，非常希望有一種“整數-整數小波變換”，將整數序列映射為整數小波系數，并且這種映射是可逆的，具有這種性質的小波變換稱為整數小波變換(IWT)。Sweldens等提出的提升(lifting)小波變換方法是一種新的小波變換工具，利用它可以不采用傅里葉變換作為主要分析工具，能夠很容易地構造一般的整數小波變換[8]。

2.2 整數小波變換在曲線矢量數據壓縮中的應用

整數小波變換可以將數據的絕大部分能量壓縮到低頻系數中，只有少部分在高頻系數中。利用整數小波變換的這個特性可以實現數據的壓縮。近年來基于整數小波變換的圖像壓縮已經成為一個研究熱點[9]。

為了直觀說明整數小波系數分布的特點，本文對國家鐵路線曲線矢量數據(SHP格式)使用第1節中的整型化處理后，進行了兩層整數小波變換分解，并對小波系數進行統計分析如圖1所示。

圖1 全國鐵路線曲線矢量數據

經過對圖2的數據點分布圖和圖3的整數小波系數分布圖進行對比，可以發現數據點經整數小波變換后得到的小波系數在空間分布上聚集性更強，大量的幅值分布在零附近，達到了去相關的目的，適合于采用高效的編碼壓縮方法。

圖2 整型化處理后的數據點分布圖

圖3 數據點經整數小波變換后的小波系數空間分布圖

3 基于整數小波變換(IWT)和模糊k-均值聚類的編碼壓縮方案

3.1 壓縮流程

使用IWT變換壓縮曲線矢量數據的原理是通過IWT變換將空間域的坐標串變換為頻率域的小波系數序列，對系數序列進行量化和編碼獲得壓縮數據流。在使用IWT變換前，將同一條曲線或者多邊形實體的矢量數據組成一個待壓縮子塊。對每個塊中的x和y坐標序列使用第一節中整型化方法轉化成整型的偏移量序列。對得到的整型偏移 量序列進行整數小波變換，得到小波系數序列。對小波系數進行編碼，得到壓縮后的矢量數據。壓縮流程如圖4所示。

圖4 IWT曲線矢量數據壓縮流程

3.2 整數小波系數編碼

由2.2節的統計分析可知，曲線矢量數據經過整型化和整數小波變換處理后得到的整數小波系數在空間分布上非常集中，大量的幅值集中在零附近。本文針對這個特點，提出使用改進的一維模糊c-均值聚類算法對整數小波系數進行聚類，建立系數字典，將整數小波系數轉換為其所屬類均值對應的字典索引，從而實現快速高效的編碼。

3.2.1 模糊c-均值聚類(FCM)

設{xi，i=1，2，…，n}是n個樣本組成的樣本集合，預定類別數目c，mi，i=1，2，…，c為每個聚類的中心，μj(xi)是第i個樣本對于第j類的隸屬度函數。用隸屬度函數定義聚類損失函數Lμ:

Lμ  = ∑cj = 1∑ni = 1[μj (xi )]bdi 2j (1)

式中:di j  = xi -mj 為第i個樣本與第j個聚類中心間的歐幾里得距離;b∈(1，∞)是可以控制聚類結果模糊程度的常數。

模糊c-均值方法[10]要求每個樣本對于各個聚類的隸屬度之和為1。即要滿足:

∑cj=1μj(xi)=1， i=1，2，…，n(2)

使用拉格朗日乘數法進行推導，可以得到使式(1)取極小值的必要條件:

mj=∑ni=1[μj(xi)]bxi/∑ni=1[μj(xi)]b(3)

μj (xi ) = 1/∑ck = 1(di j /dik )2/(b-1)(4)

由上述2個必要條件，模糊c-均值聚類算法是一個簡單的迭代過程。算法步驟如下:

步驟1:設定聚類數目c和參數b。

步驟2:初始化各個聚類中心mi。

步驟3:根據式(4)計算隸屬度函數。如果小于某個確定的閾值，或相對上次隸屬度函數值的改變量小于某個閾值，算法停止。

步驟4:根據式(3)更新各類聚類中心。

3.2.2 使用FCM字典法對整數小波系數編碼

分別取出x方向的部分小波系數和y方向的部分小波系數當做做樣本集合，使用3.2.1中的FCM算法分別得到x方向和y方向上的若干個聚類中心。由于整數小波系數是一維的，因此使用的是計算速度和收斂速度都很快的一維形式的FCM。

建立由聚類中心和對應索引組成的字典。編碼時，將小波系數轉換成其所屬聚類中心對應的字典索引。字典索引的編碼長度由聚類數目決定，若聚類數目為2n，則索引的編碼長度為n位。

4 實 驗

實驗數據采用了國家基礎地理信息中心下載的中國數字地理地圖數據SHP文件，包含中國國境線矢量數據，中國境內鐵路線、公路線、河流分布等矢量數據。采用本文的壓縮編碼方案和文獻11中直接對曲線矢量數據進行聚類法壓縮方式[11]進行壓縮實驗，得到的實驗結果如表1所示。

表1 實驗結果

實驗數據bou1_4p.shpHydl_4p.shprai_4m.shproa_4m.shp

原始數據大小 /KB1 041 910754584

直接聚類法

壓縮后大小/KB133.5115.2101.981.1

壓縮比7.87.97.47.2

均方誤差16171615

最大誤差30313329

本文算法

壓縮后大小/KB65.959.149.939.7

壓縮比15.815.415.114.7

均方誤差9.28.99.18.6

最大誤差22212019

實驗主要對比的性能指標:

(1) 壓縮比。原始矢量數據大小與壓縮編碼后的數據量的比值。

(2) 均方誤差(mean square error，MSE)和最大絕對誤差(maximum absolute error，MAE)。假設原始數據由M個點組成，每個點的值為Pi ，重建后的點為Pi′，那么MSE和MAE定義為:

MSE=1M∑M-1i=0(Pi-Pi′)2

MAE=max0≤i≤M-1{|xi-xi′|，|yi-yi′|}

實驗結果表明，使用本文的算法相比直接使用矢量數據的聚類算法能夠提高壓縮比并且能夠降低重建后的矢量數據的失真程度。

5 結 語

GIS地圖數據中的曲線或多邊形矢量數據，其坐標相鄰點間的坐標值之差的變化范圍很小，可以用整型數來表示，并且坐標點序列內部存在很大的相關性。因此，可以通過對浮點型的坐標點序列轉換成整型偏移量序列，再進行整數小波變換和采用合適的編碼壓縮方案進行此類矢量數據的壓縮。實驗結果表明，使用本文的基于整數小波變換的曲線矢量數據壓縮方案，可以達到較高的壓縮比和較小的失真。在實際GIS系統實時使用中，對壓縮解壓縮的速度也有很高的要求，如何在盡量不減少壓縮比的前提下最大化的降低計算的時間消耗有待進一步的研究。

參考文獻

[1]黃培之.具有預測功能的曲線矢量數據方法[J].測繪學報，1995，24(4):316-319.

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

[3]KOLESNIKOV A ，AKIMOV A. Distortion-constrained compression of vector maps[C]//Proceedings of the 2007 ACM Symposium on Applied computing. Seoul: ACM， 2007:8-12.

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

[5]王立勝，閔曉瑜.一種面向移動用戶的空間矢量數據壓縮算法[J].自動化技術與應用，2004，12(23):20-22.

[6]黃越峰，鐘耳順，郭會.移動計算環境中曲線數據實時壓縮方法[J].計算機輔助設計與圖形學學報，2009(21):88-93.

[7]AKIMOV A， KOLESNIKOV A， FRANTI P. Lossless compression of map contours by context tree modeling of chain codes[J].Pattern Recognition，2007，40(3):944-952.

[8]丁緒星.基于整數小波變換的圖像編碼研究與實現[D].南京:南京理工大學，2004.

[9]余先川，張立保，朱童，等.基于整數小波與提升框架的遙感圖像壓縮[J].光學學報:信息光學專刊，2009，29(12):221-224.

[10]BEZDEK J C， HATHAWAY R J， SABIN M J， et al. Convergence theory for fuzzy C-means:counter examples and repairs [J] .IEEE Tans. on Systems， Man and Cybern， 1987， 17 (5): 873-877.

[11]SHEKHAR S， HUANG Y， DJUGASH J， et al. Vector map compression:a clustering approach[C]//Proceedings of the 10th ACM International Symposium on Advances in Geographic Inform ation Systems. Mclean: ACM， 2002: 74-80.