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.