点类几何数据无损压缩算法的研究

摘要:在对矢量图数据的存储特性进行深入研究的基础上,提出了综合运用通用无损数据压缩算法和几何压缩算法的两步压缩策略。根据矢量图数据中各几何图形要素的不同存储特点,特别是根据点类文件的特点,研究实现了有效的点类几何数据无损压缩算法。

关键词:无损压缩;压缩算法;几何数据

中图分类号:TP311文献标识码:A文章编号:1009-3044(2010)22-6211-02

The Questionnaire Inquired system"s Exploration of the Mid-semester Teaching Quality

DUAN Ran, ZHAO Rong

(Hubei University Computer Science, Xiaogan 432000, China)

Abstract: Based on synthetically analysis of development status on the compression algorithm of the vector data and the universal lossless data, elaborates the principle and methods of lossless data compression comprehensively, analyses their advaage and disadvantage.

Key words: lossless compression; compression algorithm; geometry compression

1 概要

数据压缩作为解决测绘领域对于矢量图数据信息存储和传输的支持技术越来越受到人们的重视。矢量数据描述物体特征越详细和准确,数据量越大,对于数据的传输、实时显示、存储管理和分析都带来很大困难。同时由于受数据不失真的严格要求,较低的压缩比和较慢的传输速度一直是困扰的一个难题。因此在存储空间和信道有限的条件下,如何高质、准确、有效地存储和传输矢量数据,是一个亟待解决的问题。因此矢量图数据中的几何数据的无损压缩是有效解决这一问题的主要技术途径。

2 数据压缩的简介

2.1 数据压缩的定义

文献[4]中指出,数据压缩,就是以最少的数码表示信源所发出的信号,减少容纳数据采样集合或给定消息集合的信号空间。

2.2 数据压缩的原理

数据压缩的基本原理在于很多信息的表达都存在着一定的冗余度,通过采用一定的编码方法和模型,可以降低这种冗余度。数据压缩是减少对存储空间和通道的压力、节省计算机处理时间的有效方法。

2.3 数据压缩的一般方法

数据压缩是用资格筛选法、信息量法或其他统计方法,把大量的原始数据或由存贮器取出来的数据转换为有用的、有条理的、精炼而简单的信息的过程。

3 几何数据无损压缩方法

矢量图数据是按坐标进行存储的,对按坐标存储的数据存在以下的压缩方法:

3.1 用整形数据表示

矢量图存储的坐标数据一般都是浮点型或双精度型,因此占用的存储结构比较大,相对而言传输的速度也比较慢。文献[14]中提到:在在各种十进制数据类型中,整数是一种占用较少存储空间和具有较快运算速度的数据类型,而且它能表示到一定的精度,可以表示0到2147483647(采用4Byte32位整数,对大多数数据存储和运算来说已经足够了)。根据这些特点,文中采用了整数来存储空间数据的策略。这种存储方式的优点是能够减少约1倍的存储空间。

3.2 用相对坐标表示

对于由整数表示的坐标数据,由于坐标是相邻存储的,所以各个坐标之间的差别不大,如果以4byte整数表示,这些差别多数情况下只有几十、几百,也就是说,如果只存储这些差别,即用相对坐标来存储的话,那么就可以只用一个字节表示,这样就可以减少3倍的存储空间,存储量为原来的1/3。

3.3 中心原点的选择

为将空间对象的坐标转换为整数,需要将空间数据小数点后部分变为整数,同时为减少存储量,采用取一个数据密集区中心为原点,进行偏移转换,再在此基础上进行压缩。

4 点类数据的压缩算法实现

由于点类文件中的坐标不具备区域单调性的特点,排列也无明显的顺序性,因此可以说一个点类文件是由许多无序的坐标点组成的。但我们可以从中发现就点类文件来说,其存储点类文件的相邻坐标的值差别不大,坐标通常在小数点后一位甚至两三位才有差别,因此还是有很大冗余的空间的。我们采用坐标排序与坐标偏移量相结合的方法来实现对其的几何压缩。具体方法是以一个点类文件为单位,将点类文件坐标序列按照从小到大的顺序进行重排,然后以相邻点间的偏移量代替原坐标序列,再分别求各点偏移量与总偏移量均值的差,将这个差值作为坐标序列最终的数据进行存储。同时,应考虑因点类文件坐标排序带来的属性文件中属性记录的重新排列问题。

4.1 点类坐标几何压缩算法步骤

点类坐标压缩算法步骤如下:

1) 在x坐标序列中,将x坐标值按照从小到大的顺序排列,同时y坐标序列各点位置也随x坐标的排序做相应变化。

2) 新x坐标序列中第l点坐标值不变,求其余各点与前一点的偏移量,各点偏移量均乘以106,并对其偏移坐标值以长整型来表示。

3) 在已随x坐标序列变化的y坐标序列中,第1点不变,从第2点起y值从小到大排序,此时x各点位置也随y各点做相应变化,记录排序后的y值跟排序前(即已随x坐标排序变化后的y坐标序列)的y值的映射关系。

4) 新y坐标序列中第l点与第2点坐标值不变,从第3点y值开始分别求各点与前一点y值的偏移量,除l、2点外其余各点偏移量均乘以106,并对其偏移坐标值以长整型来表示。

5) 分别求x总偏移量、y总偏移量的均值,然后求x、y各点偏移量与均值的差,作为最终的x、y序列坐标值,并分别记录x、y的均值。

4.2 点类坐标几何解压缩算法步骤

1) 将x的均值与除去第l点外的其余各点相加,将y的均值与除去第1、2点外的其余各点相加。

2) 除第1点外的x均乘以10-6,从第2点起,将偏移量与前一点的坐标值相加,作为该点的现坐标,得到恢复后的x坐标序列。

3) 除第1、2点外的y均乘以10-6,从第3点起,将偏移量与前一点的坐标值相加,作为该点的现坐标,得到排序后的y坐标序列。

4) 根据排序后的y值跟排序前(即己随x坐标变化后的y坐标序列)的y值的映射关系,将y坐标序列的各点调整到排序前y值的位置,即可得到恢复后的y坐标序列,此时x坐标序列也随y坐标序列做相同调整。

4.3 算法性能分析

我们以同一属性的一个点文件来分析。通常由于点类数据的坐标值精度比较高,一般都会精确到小数点后6位到8位,经过坐标排序后然后求相邻坐标的偏移量,可以使偏移量的值降低到较小的范围内,再用各点偏移量减去偏移量的均值,可进一步缩小数据量,这样点类数据文件的存储量可以有较大程度的压缩。由于各点间无逻辑上的联系,所以排序后不影响各点间的位置关系。但为保持x、y坐标的一一对应,需要记录排序后的y值跟排序前(即已随x序列排序变化后的y坐标序列)的y值的映射关系,同时需要记录x,y偏移量的均值,这是经过压缩后增加的码量,但该码量比较小。

所以该算法的坐标值码量是明显减少的。

5 结束语

在接下来的实验中,选择了10个坐标点进行了测试,测试结果可以看出,经过以上算法,x、y新序列的坐标值码量有了明显的减少。这里由于篇幅有限,没有将实验数据表列出。这种算法还可以推广到矢量图几何数据中的线、多边形类文件中。

参考文献:

[1] 杨建宁,杨崇峻,明东萍,等.WebGIS系统中矢量数据的压缩与化简方法综述[J].计算机工程与应用,2004(32):36-38.

[2] 骆新,陈睿.数据压缩实用技术[M].北京:学苑出版社,1993.

[3] 李青元,刘晓东,曹代勇.WebGIS矢量空间数据压缩方法探讨[J].中国图形图像学报,2001,6(12):1225-1229.

[4] 李琦,杨超伟,陈爱军.WebGIS中的地理关系数据库模型研究[J].中国图象图形学报,2000,5(2):119-123.