淺析基于IWT和FCM的曲線矢量數(shù)據(jù)壓縮方法(全文)

精品文檔-下載后可編輯淺析基于IWT和FCM的曲線矢量數(shù)據(jù)壓縮方法(全文)摘要:矢量數(shù)據(jù)壓縮對于gis數(shù)據(jù)的存儲、網(wǎng)絡(luò)傳輸以及在移動設(shè)備中的使用都具有重要意義。在此通過對曲線矢量數(shù)據(jù)特點(diǎn)的分析,提出基于整數(shù)小波變換的矢量數(shù)據(jù)壓縮方法。壓縮方案包括3個主要流程:矢量數(shù)據(jù)整型化。曲線矢量數(shù)據(jù)具有相鄰坐標(biāo)點(diǎn)間坐標(biāo)值大小差別不大的特點(diǎn),將坐標(biāo)點(diǎn)間的差值轉(zhuǎn)換為整型的偏移量,用偏移量表示矢量數(shù)據(jù)的坐標(biāo)點(diǎn),利用整數(shù)小波變換處理偏移量序列。實驗表明,偏移量序列經(jīng)過整數(shù)小波變換得到的小波系數(shù)序列在空間分布上更加集中,適合使用高效的編碼壓縮方法;對變換后的小波系數(shù)進(jìn)行編碼壓縮。在此使用模糊c均值聚類字典法編碼實現(xiàn)了曲線矢量數(shù)據(jù)的有損編碼。通過實驗和其他壓縮算法結(jié)果的對比,該方法具有壓縮比較高,失真小的特點(diǎn)。關(guān)鍵詞:空間矢量數(shù)據(jù);整數(shù)小波變換;模糊c均值聚類;字典法編碼;shp

methodofcurvevectordatacompressionbasedoniwtandfcm

zhangjun-lan1,wangyi2

(1.collegeofinformationscienceandtechnology,beijingnormaluniversity,beijing100875,china;

2.oceanuniversityofchina,qingdao266003,china)

abstract:thevectordatacompressionhasgreatsignificanceingisdatastorage,networktransmissionanditsapplicationinmobiledevices.acompressionmethodbasedontheintegerwavelettransform(iwt)andfuzzycmeans(fcm)isproposedaccordingtotheanalysisforthecharacteristicofcurvevectordata.thecompressionschemeincludes3steps:integerformofvectordata,offsetsequenceprocessingwithiwtandcodingcompressionoftransformedwaveletcoefficients.thelossycodingofcurvevectordatawasrealizedwiththedictionarycodingoffcm.comparedwithotheralgorithms,this?method?hasthecharacteristicsofhighcompressionratioandlessdistortion.keywords:spatialvectordata;integerwavelettransform(iwt);fcm;dictionaryencoding;shp

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

傳統(tǒng)的矢量數(shù)據(jù)壓縮方法的核心思想是從矢量數(shù)據(jù)的坐標(biāo)點(diǎn)集中運(yùn)用一定的算法抽取出最能體現(xiàn)矢量數(shù)據(jù)特征的子集。這類曲線矢量數(shù)據(jù)壓縮算法主要有:垂距限值法、角度限值法、douglas-peucker算法(splitnig算法),以及黃培之提出的具有預(yù)測功能的曲線矢量數(shù)據(jù)壓縮方法等[1-3]。

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

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

1矢量數(shù)據(jù)的整型化

矢量數(shù)據(jù)文件一般包括表示數(shù)據(jù)屬性和存儲結(jié)構(gòu)的元信息和實際圖形的坐標(biāo)點(diǎn)序列,其中浮點(diǎn)型坐標(biāo)點(diǎn)序列占據(jù)了文件的絕大部分存儲空間。對矢量數(shù)據(jù)文件進(jìn)行壓縮主要是對坐標(biāo)點(diǎn)序列進(jìn)行壓縮。

對于二維的平面矢量數(shù)據(jù),坐標(biāo)點(diǎn)序列由?x坐標(biāo)序列和y坐標(biāo)序列組成。由于使用浮點(diǎn)型表示,每個坐標(biāo)值占用的存儲空間為8個字節(jié)。本文使用的是基于整數(shù)小波變換的壓縮方法,因此首先是將坐標(biāo)點(diǎn)序列用整型數(shù)表示。

由于同一曲線和多邊形實體的坐標(biāo)點(diǎn)序列是密集的和順序的,因此相鄰點(diǎn)間的坐標(biāo)值之差的變化范圍很小,可以用整型數(shù)來表示。對于由n個點(diǎn)序列([xn,yn],n=0,1,2,…,n-1)表示的曲線或多邊形實體,坐標(biāo)值整型化為([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整數(shù)小波變換及其在矢量數(shù)據(jù)壓縮中的應(yīng)用

2.1整數(shù)小波變換

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

2.2整數(shù)小波變換在曲線矢量數(shù)據(jù)壓縮中的應(yīng)用

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

為了直觀說明整數(shù)小波系數(shù)分布的特點(diǎn),本文對國家鐵路線曲線矢量數(shù)據(jù)(shp格式)使用第1節(jié)中的整型化處理后,進(jìn)行了兩層整數(shù)小波變換分解,并對小波系數(shù)進(jìn)行統(tǒng)計分析如圖1所示。

圖1全國鐵路線曲線矢量數(shù)據(jù)

經(jīng)過對圖2的數(shù)據(jù)點(diǎn)分布圖和圖3的整數(shù)小波系數(shù)分布圖進(jìn)行對比,可以發(fā)現(xiàn)數(shù)據(jù)點(diǎn)經(jīng)整數(shù)小波變換后得到的小波系數(shù)在空間分布上聚集性更強(qiáng),大量的幅值分布在零附近,達(dá)到了去相關(guān)的目的,適合于采用高效的編碼壓縮方法。

圖2整型化處理后的數(shù)據(jù)點(diǎn)分布圖

圖3數(shù)據(jù)點(diǎn)經(jīng)整數(shù)小波變換后的小波系數(shù)空間分布圖

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

3.1壓縮流程

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

圖4iwt曲線矢量數(shù)據(jù)壓縮流程

3.2整數(shù)小波系數(shù)編碼

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

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

設(shè)?{xi,i=1,2,…,n}是n個樣本組成的樣本集合,預(yù)定類別數(shù)目c,mi,i=1,2,…,c為每個聚類的中心,μj(xi)是第i個樣本對于第j類的隸屬度函數(shù)。用隸屬度函數(shù)定義聚類損失函數(shù)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,∞)是可以控制聚類結(jié)果模糊程度的常數(shù)。

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

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

使用拉格朗日乘數(shù)法進(jìn)行推導(dǎo),可以得到使式(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:設(shè)定聚類數(shù)目c和參數(shù)b。

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

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

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

3.2.2使用fcm字典法對整數(shù)小波系數(shù)編碼

分別