GPS定位数据压缩算法的设计与实现-Read

1、GPS 定位数据压缩算法的设计与实现 摘要：为了解决嵌入式 GPS 车载系统 存储空间小、 GPS 定位数据量大的矛 盾，根据 GPS 定位数据的特点， 提出 了专用于 GPS 定全数据压缩的改进 型半字节压缩算法。该算法是一种在 原半字节压缩算法的基础上改进的算 法，经过实际测试， 压缩比可达 50%。 若将压缩预处理也折算法在内，总压 缩比可达 80%以上，为车载系统节省了大量的存储资源。除此之外，也缩短了GSM 信道的 占用时间，大大地缓解了向控制调度中心上传数据的压力。 嵌入式 GPS 车载系统般体积较小，无存储量大的硬盘等设备，系统程序、应用程序一般装 在 FLASH 或 ROM 中

2、。由于 FLASH 或 ROM 等存储介质的价格相对台式机上广泛使用的硬 盘、光盘等来说是非常昂贵的， 因此， 在开发嵌入式系统的软件产品时必须将软件所占的存 储空间限制在一定的范围内。 在 GPS 车载系统的研发过程中，主要需解决的问题是：车载系统为了实现自导航，必须存 储大量的 GPS 定位数据 （每天需要存储约 6MB ）；其二是这些数据还要通过 GSM 信道上传 到控制调度中心（若通过短信业务发送，每次160B，则需要每分上传 6 次）。无疑，数据压 缩是在不增加硬件成本的前提下，从软件的角度来充分发挥系统现有资源的有效办法。 数据压缩方法种类繁多， 可以分为无损压缩和有损压缩两大类。

3、 无损压缩利用数据的统计冗 余进行压缩。 数据统计冗余度的理论限制， 般为 2：1 到 5：1。这类方法广泛用于文本数据、 程序和特殊应用场合的图像数据 （如指纹图像、医学图像等） 的压缩。 有损压缩方法利用了 人类视觉对图像中的某些频率成分不敏感的特性， 允许压缩过程中的损失一定的信息。 虽然 不能完全恢复原始数据， 但是所损失的部分对理解原始图像的影响较小， 却换来了大得多的 压缩比。有损压缩广泛应用于语音、图像和视频数据的压缩。 决定。首先，用于嵌入 式系统的数据压缩方法 应是无损压缩方法。其 次，压缩代码和解码所 需的信息代码必须足够 短，否则就会失去压缩 才能进一步提高数 目前现在的

4、压缩算法很多， 但不能直接用于嵌入式系统当中， 这完全由嵌入式系统的特点所 的意义。 还有， 嵌入式系统的数据压缩必须结合具体的数据格式的特点， 据的压缩比。除此之外， 目前的压缩程序的启动执行必须人为干扰，不能自动执行，因为它 们是为文件系统设计的，而嵌入式系统的数据压缩必须能够自动执行。 1 GPS 数据格式 GPS OEM板由变频器、信号通道、微处理器和存储单元等组成。GPS OEM 板的型号甚多， 性能各异， 但大多采用美国国家海洋电子协会制定的 NMEA-0183 通信标准格式。 本系统选 择的是美国 SiRF 公司的 SiRFstarII OEM 板。 SiRFstarII OEM

5、 板语句的输入、输出是通过 RS232 串行接口完成的，其通信端口的数据格式应该设置为8个数据位、 1 个起始位和 1 个 停止位， 校验方式选为无奇偶校验， 波特率设置为 4800 波特。 NMEA-0183 通信标准的输出 数据采用的是 ASCII 码，其内容包含了纬度、经度、高度、速度、日期、时间、航向以及 卫星状况等信息，语句有六种，包括GGA ， GLL 、GSA、GSV、RMC 和 VTG 。对于不同 的用途， 选用的语句记录也不同， 例如嵌入式 GPS 车载系统的使用者只关心其日期和时间、 纠度、面速度信息，因而可以只选用 RMC 记录语句。一条 $GPRMC 语句包括 13 个

6、记录： 语句标识头、世界时间、定位状态、纬度、纬度方位、经度、经度方位、地面速度、地面路 GPS 定位数据压缩算法的设计与实现 线、日期、磁偏角、校验和和结束标记，它一共占用 70 个字节（其中还包括用于分隔记录 所使用的 11 个逗号），例如： $GPRMC,121530.998,A,4000.0162,N,11619.5476,E,0.00,240.81,160102,*3B 由此可见，从 SiRFstarII OEM 板接收下来的数据流是文本字符串，根据 GPS 数据格式的特 点，本设计中拟采用半字节法完成压缩及解压缩的任务。 该方法属于无损压缩技术， 其原理 是去除字节中的冗余位， 从

7、而达到压缩目的。 然而， 这种方法只适用于纯数字文本文件的压 缩，显然 GPS 定位数据并不是纯数字的，还必须在压缩前进行一下压缩预处理，最后再利 用半字节压缩算法完成数据的压缩。 2 压缩预处理 仔细观察以上各段数据记录， 可以发现语句之间的数据段还存在很多冗余。 除此之外， 这些 记录中所含的信息既有英文字符又有数字， 为了后续的压缩， 对语句中的各个记录应做如下 的预处理： 语句标识头（ ID ）：因为每个语句的标识头都一样，所以该记录段属地冗余信息，完全可 以去除，在解压缩时再在每个语句前加上该标识头即可。 世界时间（ UTC ）：该信息段以时、分、秒、毫秒的格式指示出当时世界时间。转

8、换为 1，定位数据也是每委 在解压缩时根据语句的指 以后的语句中的该信息全 北京时间还需要再加上 8 小时。 由于车载系统的定位数据的采集是以秒为单位的， 所以毫秒 量级的数据对本系统根本无用，是冗余信息，由于世界时间是按秒增 员长更新一次， 所以世界时间可以在程序的一开始采集记录一下， 针值再加上起始时间便可以复原， 因此该记录段在第一次存储后， 都是冗余信息。 定位状态（ A/V ）：占用 1 个字节，不进行预处理。由于车载系统处于的地方有可能收不 到卫星信号（如隧道中） ，致使定位信息无效，因此尽管该字段发生变化的概率较小，又与 其它信息段不相关，在此仍不能做预处理。 纬度：占用 9 个

9、字节，不进行预处理。 纬度：占用 10 个字节，不进行预处理。 经度指示器（ E/W ）：占一个字节，它指示出经度是东经，还是匹配。由于各个$GPRMC 语句中的该段信息在中国都是东径， 它是冗余信息， 因此也采取程序一开始存储一次的方法。 纬度指示器（ N/S）：占一个字节，各个 $GPRMC 语句中的该段信息完全一样，是冗余信 息，处理方法与上相同。 地面速度：占用 4 个字节，不进行预处理。 GPS 定位数据压缩算法的设计与实现 日期：占用 6 个字节，以日、月、年的格式显示，各个 $GPRMC 语句中的该段信息在 24 小时内完全一样， 是冗余信息， 采取程序一开始存储一次的方法， 以

10、后语句中的该段信息全 部废除。 校验和：占用 3 个字节，该数据完成校验后便弃之，不保留和进行压缩。 结束符合占用 2 个字节，只用来判断语句的有效数据范围， 其它记录段与本系统的设计无关 都不保留和进行压缩。 24 个字节，如图 1 所示。 3 改进型半字节压缩算法 文本数据的压缩的都是无损压缩技术， 即还原后的文件应该与源文件完全相 同。文本文件压缩的方法有很多种，如 HUFFMAN 编码、 算术编码和字节压缩 方法等。它们均是无损压缩方法，都适 用于文本数据的压缩。半字节压缩方法 是针对文本数据的特点所设计的，主要 是去除文本中的字节中的冗余位，从而 达到减少数据文件所占用的存储空间 的

11、目的。在数据压缩技术中，除压缩重 复字符外，还可以根据数据本身的特点 进行压缩。在计算机中，任何数据都是 以某种代码的方式存储的。在些文件 中，或许有一些代码具有某些相似之 处，我们可以根据代码的特点进行特定 的操作，压缩掉这些数据的相似部分， 或者说压缩掉这些数据的特征部分，半 字节压缩就是这样一种方法。半字节方 法主要用于纯数字的文本文件的压缩， 因为数字 0 9 的 ASCII 码的高四位都 一样，是冗余的，因此每一个数字完全 通过以上压缩预处理后，保留了四个数据记录，共占用 可以用低四位描述，即每个字节的八位编码可压缩为四位编码，压缩比理论上可趋近50%。 从图 1 中可以看出， 经过

12、预处理后的数据中， 包含的文本字节有： “0 9”十个数字符号， “A”、 “ V两”个英文大写字母和一个小数点 “ .符”号，共 13个字符。 “ A”、“ V”、“ .的”ASCII 码的高 四位显然与数字字节的不一样， 半字节压缩方法不能简单套用。 然而， 我们知道四位二进制 编码可区分 16 种状态，用来表示 13 种不同的字符是足够的。 压缩数据编码表如表 1 的慰，为了充分利用编码表中的状态，在原来 13 个字节的基础上又 新增添了两个字符 “B”和“W”，其四位编码分别为 1101 和 1110。这两个字符是在压缩预处理 过程中， 用来记录那些因语句校验和出错而舍弃的语句。 因为

13、每条语句的时间信息全部在预 处理阶段被舍弃， 在解压缩时要恢复时间值。 该值在正常情况下是根据时间的基数再加上语 句的计数值 （由于每秒接受到一条语句， 所以语句计数值就是以秒为单位的时间增量） 确定 的。当发生语句校验和出错时， 若处于定位有效状态， 则在定位状态记录上不填写 “A”字符， 而填写 “B”字符；若处在定位无效状态，则不填写 “V”字符，而填写 “W”字节。在以后解压缩 时，若检测到 “A”、 “V”字节，时间的还原按正常的算法进行；若检测到“B”、 “W”字符时， 进行的还原除了按正常的算法进行以外还要加上秒钟，这样才能确保时间能够正确的恢复， 这是因为 “B”、W 字节表示

14、上一条语句发生错误已经被丢弃，语句的压缩是非连续的，有 GPS 定位数据压缩算法的设计与实现 继句现象发生。 表 1 压缩数据编码表 预处理后所含的字符 ASCII 码 四位二制编码 备注 0 00110000 0000 1 00110001 0001 2 00110010 0010 3 00110011 0011 4 00110100 0100 5 00110101 0101 6 00110110 0110 7 00110111 0111 8 00111000 1000 9 00111001 1001 00101110 1010 A 01000001 1011 定位有效 B 01000010

15、 1101 定位有效， 秒值 1 V 01010110 1100 定位无效 W 01010111 1110 定位无效， 秒增 1 通过此编码表进行转换后，原来经过压缩预处理后的固定 24 个字节第的文本数据就可以减 小一半(压缩后为固定的 12 个字节长)，压缩比为 50%，若从未经过预处理的文本数据算 起，则压缩比可达到 80%。 由图 2 可知， 实现半字节压缩算法需要解决两上问题： 首先是压缩对象的计数； 其次是如何 把两个数字的低位合并到一个字节中。 后一个问题只要规定好压缩后的字节中奇数号字符的 四位编码与偶数号字符的四位编码的存放次序即可， 程序的实现非常简单， 在此我们规定编 号

16、是奇数的字符放在高四位， 编号为偶数的字符的编码放在低四位。 假设压缩前的数据流中 的前四个字节分别为 “1、 2、 3、4”则,压缩后的数据格式如图 3 所示。 半字节压缩中需要解决的首要问题是压缩对象的计数问题， 解决此问题的方法有两种： 一种 是半字节计数器( Half-Byte Counter )，另一种是全字节计数器( Full-Byte Counter )。不管那 一种方法，它们都要占用字节，再加上压缩标识也要占用字节，所以要影响数据的压缩比。 改进后的半字节压缩算法完全解决了此问题，因为GPS 定位数据经过压缩预处理后的数据 长度是固定的 24 个字节长，不是动态可变的，所以不需

17、要解决压缩对象的计数问题。一般 来说，任何一种压缩算法都需要用压缩指示字符作压缩数据的标识，压缩标识符越短越好， 因为过长会影响缩效果。然而，由于 GPS 定位数据中的所有字符都进行了编码处理，不存 在原样字符(不进行压缩的字符，在解压缩时原样输出) ，因此压缩标识完全可以省略，可 进一步提高数据的压缩比。压缩预处理程序框图和改进后的半字节压缩算法框图如图 4 所 示。 压缩文件包括解压缩所需的重要信息， 由释放参数信息和依次压缩了的定长数据块组成。 GPS 定位数据压缩算法的设计与实现 释放参照信息包含有解压缩所要使用的时间基数信息， 它通过语句计数器以及错误代码号可 以将时间还原。 除此之

18、外，释放参照信息还包括各个定长数据块在解压缩时所需的共同信息， 如 E/W 、 N/S、日期，压缩文件的格式如图 5 所示。 嵌入式系统的压缩是不需要人为干涉、 而自动实时完成的， 具体的实现方法是通过驻留内存 （单任务操作系统中，如 DSP）或作为一个后台任务（在多任务操作系统中，如Windows 中）对数据完成实时压缩或解压缩。 表2 改进型半字节压缩算法的测试结果 处理 文件大小（ B ） 预处理后 改进型半字节压缩 压缩比 1035k=69 15000 360KB+23B 180KB+23B 0.8260 103.5k=69 1500 36KB+23B 18KB+23B 0.8259 10.