GPS數(shù)據(jù)壓縮算法研究

(蘭州交通大學(xué)自動(dòng)化與電氣工程學(xué)院，甘肅 蘭州 730070)

0 引言

GPS定位系統(tǒng)是一種高精度、快速的連續(xù)定位系統(tǒng)。目前該系統(tǒng)已經(jīng)在車輛定位[1]、地殼運(yùn)動(dòng)監(jiān)測(cè)、變形監(jiān)測(cè)等諸多領(lǐng)域得到了廣泛使用。但該系統(tǒng)在測(cè)量時(shí)間較長(zhǎng)的情況下，獲得的觀測(cè)值數(shù)量巨大，觀測(cè)值的冗余度很高。此外，在GPS定位過程中會(huì)產(chǎn)生各種誤差[2]，使得測(cè)量數(shù)據(jù)中包含大量干擾信息，給后續(xù)數(shù)據(jù)的處理帶來諸多不便。雖然針對(duì)GPS觀測(cè)數(shù)據(jù)曾有學(xué)者提出了基于小波變換的壓縮算法[3]，但該算法的靈活性不夠，壓縮率也不高。因此，有必要對(duì)觀測(cè)數(shù)據(jù)進(jìn)行更有效的壓縮，以減輕后續(xù)數(shù)據(jù)處理的壓力。

小波變換具有良好的多分辨率分析能力和自適應(yīng)性，被廣泛應(yīng)用于信號(hào)分析[4-5],其提升格式既保持了第一代小波的特性，同時(shí)又克服了平移和伸縮的不變性。因此，本文以提升小波為算法基礎(chǔ)，結(jié)合Huffman編碼理論，借助Matlab軟件對(duì)GPS經(jīng)緯度數(shù)據(jù)進(jìn)行壓縮處理。試驗(yàn)表明，該算法具有壓縮算法簡(jiǎn)單、方案靈活、易于實(shí)現(xiàn)等特點(diǎn),重構(gòu)后的數(shù)據(jù)基本無信息損失，且壓縮比得到了有效提高。

1 提升小波變換

小波變換利用多分辨分析的概念對(duì)數(shù)據(jù)進(jìn)行處理，可以在一定程度上去除數(shù)據(jù)間的相關(guān)性，消除冗余信息，降低數(shù)據(jù)集的熵值，實(shí)現(xiàn)較高的壓縮比。提升小波采用簡(jiǎn)單的數(shù)乘運(yùn)算代替?zhèn)鹘y(tǒng)小波中的卷積運(yùn)算，計(jì)算過程可以完全在空間域中完成，變換過程簡(jiǎn)單，易于硬件實(shí)現(xiàn)。提升小波變換主要有以下3個(gè)步驟[6]。

split(cj)={ej-1，oj-1}

(1)

dj-1=oj-1-P(ej-1)

(2)

③ 更新：更新的目的是尋找一個(gè)更好的子集cj-1，使其保持某個(gè)標(biāo)量特性Q(·)(如消失矩、均值等)不變，即Q(cj-1)=Q(cj)。利用更新算子U，并借助預(yù)測(cè)得到的高頻信息dj-1可修正ej-1生成新的數(shù)據(jù)集cj-1，從而使cj-1保證cj的一些特征。更新過程如下：

cj-1=ej-1+U(dj-1)

(3)

重構(gòu)過程是提升過程的逆過程。小波提升方案的分解與重構(gòu)過程如圖1所示。

圖1 提升方案的分解與重構(gòu)過程

2 GPS數(shù)據(jù)壓縮方案

2.1 提升小波GPS數(shù)據(jù)分解

影響信號(hào)壓縮性能的主要因素有小波的對(duì)稱性、正交性、光滑度和正則性等[7]。采用不同的小波基對(duì)數(shù)據(jù)進(jìn)行處理得到的效果差別很大。Haar小波是正交小波，雖然光滑性很差，但通過提升格式，能夠提高其光滑性，并且提升后的Haar小波具有二階消失矩。根據(jù)GPS信號(hào)的特點(diǎn)，本文選用Haar小波作為變換過程的小波基。

2.2 小波系數(shù)編碼

在提升小波變換后需要對(duì)變換后的高低頻系數(shù)進(jìn)行編碼。Huffman編碼的基本原理是對(duì)出現(xiàn)概率大的數(shù)據(jù)用較短的碼字表示[8]，對(duì)出現(xiàn)概率小的數(shù)據(jù)用較長(zhǎng)的碼字表示，從而達(dá)到平均碼字長(zhǎng)度最小的目的。

① 將小波變換后的系數(shù)按其出現(xiàn)的概率大小，按遞減順序排列。

② 按照第一步所得的順序，將最小的兩個(gè)概率組合相加，然后把這個(gè)概率與其他概率降序排列，并重復(fù)該步驟，直到剩下一個(gè)信源符號(hào)且概率達(dá)到1.0為止。

③ 在合并概率的過程中，概率大的信源賦予碼字“1”，概率小的信源賦予碼字“0”，由此形成一棵完整的Huffman樹的結(jié)構(gòu)。碼字序列就構(gòu)成了符號(hào)的代碼。

④ 從樹根部開始，沿著樹枝順序?qū)懗龈餍〔ㄏ禂?shù)的編碼結(jié)果。

Haffman編碼如圖2所示，該樹右邊為根，左邊為7片葉子，P1～P6對(duì)應(yīng)每次排序后兩個(gè)最小概率組合相加后得到的概率。為了分配碼字，對(duì)每對(duì)字符任取上邊的一位為1，下邊的1位為0，得到碼字01、00、111、110、101、1001、1000。

圖2 Huffman編碼

Huffman編碼是可用二進(jìn)制位編碼平均碼長(zhǎng)最短的編碼，具有編碼簡(jiǎn)單、信息冗余量少、容易實(shí)現(xiàn)、編碼效率較高等特點(diǎn)。提升小波分解后得到的高頻系數(shù)的值絕大部分集中在零附近，因此利用Huffman編碼得到的編碼效果較好。

2.3 轉(zhuǎn)換數(shù)據(jù)存儲(chǔ)類型

Matlab數(shù)據(jù)類型中是沒有bit型的。經(jīng)Huffman編碼后的數(shù)據(jù)盡管都是0-1串，但每一個(gè)字符都占用8 bit存儲(chǔ)空間，直接存儲(chǔ)將占據(jù)很大的存儲(chǔ)空間。假設(shè)編碼數(shù)據(jù)為x=[123 234 212 231 152]，經(jīng)Huffman編碼的結(jié)果為1×11的二進(jìn)制字符串，最少也需要占用11×sizeof(uint8)=88 bit的存儲(chǔ)空間，而原數(shù)據(jù)需要的存儲(chǔ)空間為5×sizeof(uint8)=40 bit?？梢钥吹骄幋a后的數(shù)據(jù)完全沒有實(shí)現(xiàn)壓縮的目的。因此，需要對(duì)數(shù)據(jù)進(jìn)行進(jìn)一步處理。

本文采用的方法是將編碼后的小波系數(shù)(二進(jìn)制字符串)按照每8位一組進(jìn)行分組，將分組后的結(jié)果存儲(chǔ)為uint8型整數(shù)(即0～255之間)。按照該方法對(duì)示例進(jìn)行二次處理，得到1×2的uint8向量，占用的內(nèi)存空間為16 bit，壓縮比為88/16=5.5，較原編碼數(shù)據(jù)，進(jìn)一步節(jié)省了數(shù)據(jù)占用的存儲(chǔ)空間，提高了壓縮比。

2.4 壓縮性能評(píng)價(jià)指標(biāo)

壓縮比是衡量壓縮性能的標(biāo)準(zhǔn)之一。在數(shù)據(jù)壓縮技術(shù)中，一般將壓縮前信源符號(hào)的編碼比特?cái)?shù)與壓縮后的編碼比特?cái)?shù)之比來定義數(shù)據(jù)的壓縮比，即[9]：

(4)

式中：S為初始源數(shù)據(jù)所占用的空間，bit；Sc為壓縮后數(shù)據(jù)所占用的空間，bit；K為一個(gè)無量綱數(shù)，K值越大表明壓縮性能越好。

數(shù)據(jù)的壓縮性能不僅體現(xiàn)在壓縮比上，還體現(xiàn)在重構(gòu)信號(hào)與源數(shù)據(jù)信號(hào)的誤差上。有的壓縮方法盡管獲得的壓縮比很高，但是解壓縮重構(gòu)后的數(shù)據(jù)與源數(shù)據(jù)誤差較大。最令人滿意的壓縮效果是獲得最大的壓縮比和重構(gòu)信號(hào)與原始數(shù)據(jù)信號(hào)的誤差最小。為了評(píng)估重構(gòu)信號(hào)的質(zhì)量，可計(jì)算原始信號(hào)S(n)與重構(gòu)信號(hào)Sc(n)誤差均方值，誤差均方值越小，信號(hào)重構(gòu)的質(zhì)量越高。誤差均方值的計(jì)算表達(dá)式為[3]：

(5)

3 試驗(yàn)結(jié)果

為了驗(yàn)證本文算法的可行性，借助Matlab語言，對(duì)大小為65 408 bit的GPS經(jīng)度數(shù)據(jù)采用不同的壓縮算法進(jìn)行了結(jié)果對(duì)比。第一種方法為直接采用小波變換對(duì)數(shù)據(jù)進(jìn)行處理，使用ddencmp函數(shù)獲取信號(hào)壓縮閾值，采用wdencmp函數(shù)實(shí)現(xiàn)信號(hào)壓縮處理。第二種方法采用小波包變換對(duì)數(shù)據(jù)進(jìn)行壓縮處理[10]。本文方案為采用提升小波變換對(duì)數(shù)據(jù)進(jìn)行提升分解，對(duì)分解后的數(shù)據(jù)進(jìn)行Huffman編碼，并對(duì)編碼結(jié)果進(jìn)行進(jìn)一步處理，使數(shù)據(jù)轉(zhuǎn)換為uint8型并存儲(chǔ)。3種方案的壓縮結(jié)果如表1所示。

表1 3種壓縮方案的對(duì)比

從表1數(shù)據(jù)可以看出，與其他兩種方案相比，本文方案的壓縮比得到了很大提高，且重構(gòu)后的數(shù)據(jù)誤差很小，約為7.105 4×10-15，數(shù)據(jù)基本無信息損失。隨著數(shù)據(jù)量的加大，本文方案的優(yōu)勢(shì)會(huì)更明顯。

4 結(jié)束語

本文結(jié)合提升小波自身的優(yōu)勢(shì)，提出了一種基于提升小波變換的GPS數(shù)據(jù)壓縮算法。該方法采用提升小波變換對(duì)GPS數(shù)據(jù)進(jìn)行預(yù)測(cè)，采用Huffman編碼方式對(duì)預(yù)測(cè)結(jié)果進(jìn)行編碼，并對(duì)編碼后的數(shù)據(jù)進(jìn)行了存儲(chǔ)類型轉(zhuǎn)換，總壓縮比可達(dá)9.95∶1。采用該方法不僅能夠有效地壓縮數(shù)據(jù)量、剔除多余的相關(guān)信息、減輕后續(xù)數(shù)據(jù)處理的壓力，而且通過該方法重構(gòu)的數(shù)據(jù)能夠保留源數(shù)據(jù)的基本特征。此外，提升小波的變換在空間域內(nèi)進(jìn)行原址計(jì)算，可以提高計(jì)算效率，減少內(nèi)存花費(fèi)，便于硬件實(shí)現(xiàn)，因此具有實(shí)時(shí)實(shí)現(xiàn)的前景。

[1] 翟霞暉,唐明浩.基于ARM7的汽車導(dǎo)航定位與防盜系統(tǒng)[J].自動(dòng)化儀表，2007,28(3):30-33.

[2] 周立.GPS廣播星歷誤差影響診斷與預(yù)測(cè)模型研究[J].測(cè)繪科學(xué)，2005,30(4):37-38，42.

[3] 姚曉波,張建軍.基于小波變換的GPS數(shù)據(jù)壓縮研究[J].武漢理工大學(xué)學(xué)報(bào)：信息與管理工程版,2006，28(1):1-3.

[4] 陳鵬,李固,劉美全，等.電磁超聲檢測(cè)信號(hào)的小波自適應(yīng)閾值降噪研究[J].自動(dòng)化儀表,2012,33(8):9-11,17.

[5] Olkkonen H,Olkkonen J,Pesola P.Efficient lifting wavelet transform for microprocessor and VLSI applications[J].Signal Processing Letters,IEEE,2005,12(2):120-122.

[6] 周西峰,肖武,郭前崗.基于提升小波的超聲信號(hào)降噪方法[J].探測(cè)與控制學(xué)報(bào)，2012,34(4):43-46.

[7] 劉鳳陵.基于提升小波的地震勘探數(shù)據(jù)壓縮研究[D].青島:青島大學(xué),2012.

[8] Hsieh C,Huang S.Disturbance data compression of a power system using the Huffman coding approach with wavelet transform enhancement[J].IEEE Proceedings on Generation,Transmission and Distribution,2003,150(1):7-14.

[9] 趙林海,王永和.一種基于正交小波包技術(shù)的機(jī)車信號(hào)記錄器數(shù)據(jù)快速壓縮方法[J].鐵道學(xué)報(bào)，2009,31(6):102-106.

[10]張翠芳,朱莉娟.基于小波包最優(yōu)基的語音信號(hào)壓縮方法[J].數(shù)據(jù)采集與處理，2010,25(6)：746-750.