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

0 引言

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

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

1 提升小波變換

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

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

(1)

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

(2)

③ 更新：更新的目的是尋找一個更好的子集cj-1，使其保持某個標量特性Q(·)(如消失矩、均值等)不變，即Q(cj-1)=Q(cj)。利用更新算子U，并借助預(yù)測得到的高頻信息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ù)分解

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

2.2 小波系數(shù)編碼

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

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

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

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

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

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

圖2 Huffman編碼

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

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

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

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

2.4 壓縮性能評價指標

壓縮比是衡量壓縮性能的標準之一。在數(shù)據(jù)壓縮技術(shù)中，一般將壓縮前信源符號的編碼比特數(shù)與壓縮后的編碼比特數(shù)之比來定義數(shù)據(jù)的壓縮比，即[9]：

(4)

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

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

(5)

3 試驗結(jié)果

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

表1 3種壓縮方案的對比

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

4 結(jié)束語

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

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

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

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

[4] 陳鵬,李固,劉美全，等.電磁超聲檢測信號的小波自適應(yīng)閾值降噪研究[J].自動化儀表,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] 周西峰,肖武,郭前崗.基于提升小波的超聲信號降噪方法[J].探測與控制學(xué)報，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ù)的機車信號記錄器數(shù)據(jù)快速壓縮方法[J].鐵道學(xué)報，2009,31(6):102-106.

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