GPS數據壓縮算法研究

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

0 引言

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

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

1 提升小波變換

小波變換利用多分辨分析的概念對數據進行處理，可以在一定程度上去除數據間的相關性，消除冗余信息，降低數據集的熵值，實現較高的壓縮比。提升小波采用簡單的數乘運算代替傳統小波中的卷積運算，計算過程可以完全在空間域中完成，變換過程簡單，易于硬件實現。提升小波變換主要有以下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，并借助預測得到的高頻信息dj-1可修正ej-1生成新的數據集cj-1，從而使cj-1保證cj的一些特征。更新過程如下：

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

(3)

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

圖1 提升方案的分解與重構過程

2 GPS數據壓縮方案

2.1 提升小波GPS數據分解

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

2.2 小波系數編碼

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

① 將小波變換后的系數按其出現的概率大小，按遞減順序排列。

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

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

④ 從樹根部開始，沿著樹枝順序寫出各小波系數的編碼結果。

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

圖2 Huffman編碼

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

2.3 轉換數據存儲類型

Matlab數據類型中是沒有bit型的。經Huffman編碼后的數據盡管都是0-1串，但每一個字符都占用8 bit存儲空間，直接存儲將占據很大的存儲空間。假設編碼數據為x=[123 234 212 231 152]，經Huffman編碼的結果為1×11的二進制字符串，最少也需要占用11×sizeof(uint8)=88 bit的存儲空間，而原數據需要的存儲空間為5×sizeof(uint8)=40 bit。可以看到編碼后的數據完全沒有實現壓縮的目的。因此，需要對數據進行進一步處理。

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

2.4 壓縮性能評價指標

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

(4)

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

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

(5)

3 試驗結果

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

表1 3種壓縮方案的對比

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

4 結束語

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

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

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

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

[4] 陳鵬,李固,劉美全，等.電磁超聲檢測信號的小波自適應閾值降噪研究[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].探測與控制學報，2012,34(4):43-46.

[7] 劉鳳陵.基于提升小波的地震勘探數據壓縮研究[D].青島:青島大學,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] 趙林海,王永和.一種基于正交小波包技術的機車信號記錄器數據快速壓縮方法[J].鐵道學報，2009,31(6):102-106.

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