摘 要:矢量数据压缩对于gis数据的存储、网络传输以及在移动设备中的使用都具有重要意义。在此通过对曲线矢量数据特点的分析,提出基于整数小波变换的矢量数据压缩方法。压缩方案包括3个主要流程:矢量数据整型化。曲线矢量数据具有相邻坐标点间坐标值大小差别不大的特点,将坐标点间的差值转换为整型的偏移量,用偏移量表示矢量数据的坐标点,利用整数小波变换处理偏移量序列。实验表明,偏移量序列经过整数小波变换得到的小波系数序列在空间分布上更加集中,适合使用高效的编码压缩方法;对变换后的小波系数进行编码压缩。在此使用模糊c均值聚类字典法编码实现了曲线矢量数据的有损编码。通过实验和其他压缩算法结果的对比,该方法具有压缩比较高,失真小的特点。关键词:空间矢量数据; 整数小波变换; 模糊c均值聚类; 字典法编码; shp
method of curve vector data compression based on iwt and fcm
zhang jun-lan1, wang yi2
(1. college of information science and technology, beijing normal university, beijing 100875, china;
2. ocean university of china, qingdao 266003, china)
abstract: the vector data compression has great significance in gis data storage, network transmission and its application in mobile devices. a compression method based on the integer wavelet transform (iwt) and fuzzy c means (fcm) is proposed according to the analysis for the characteristic of curve vector data. the compressionscheme includes 3 steps: integer form of vector data, offset sequence processing with iwt and coding compression of transformed wavelet coefficients. the lossy coding of curve vector data was realized with the dictionary coding of fcm. compared with other algorithms, this method has the characteristics of high compression ratio and less distortion.keywords: spatial vector data; integer wavelet transform (iwt); fcm; dictionary encoding; shp
对矢量化后的地形图等进行压缩处理的过程称之为空间矢量数据的压缩。wWw.lw881.com地图数字化中矢量数据的压缩主要包括各种地形图要素的数据压缩。等高线是地图中最多的图形要素,所以对矢量化后的地图的数据压缩主要是对曲线的压缩,目前讨论最多的也是曲线矢量数据的压缩。在此针对矢量数据的压缩问题进行研究。
传统的矢量数据压缩方法的核心思想是从矢量数据的坐标点集中运用一定的算法抽取出最能体现矢量数据特征的子集。这类曲线矢量数据压缩算法主要有:垂距限值法、角度限值法、douglas-peucker算法(splitnig算法),以及黄培之提出的具有预测功能的曲线矢量数据压缩方法等[1-3]。
近年来,矢量数据的量化编码压缩算法的研究得到重视。钟尚平等[4]根据平面矢量地图文件的存储特性,有机结合“无附加码书”字典编码方法,可逆并显著地压缩了矢量地图。王立胜等[5]基于第二代小波变换理论实现了对空间矢量数据的无损压缩。黄越峰等提出了使用基于整数小波变换和ffep编码的曲线数据压缩方法[6]。kolesnikov等提出了链码方法用于矢量数据压缩[7]。
本文首次提出结合实际矢量数据文件的存储结构和曲线矢量数据的特性,将浮点型的矢量数据坐标值预处理成整型值表示的坐标值之间的偏移量。进而引入先进的整数小波变换对整型的偏移量序列进一步处理,分析变换后的小波系数的幅值,分布等特征后,采用了高效的基于模糊c均值聚类和字典法编码方案进行压缩存储。实验结果表明,本文的压缩方法能够达到较高的无损压缩比。
1 矢量数据的整型化
矢量数据文件一般包括表示数据属性和存储结构的元信息和实际图形的坐标点序列,其中浮点型坐标点序列占据了文件的绝大部分存储空间。对矢量数据文件进行压缩主要是对坐标点序列进行压缩。
对于二维的平面矢量数据,坐标点序列由x坐标序列和y坐标序列组成。由于使用浮点型表示,每个坐标值占用的存储空间为8个字节。本文使用的是基于整数小波变换的压缩方法,因此首先是将坐标点序列用整型数表示。
由于同一曲线和多边形实体的坐标点序列是密集的和顺序的,因此相邻点间的坐标值之差的变化范围很小,可以用整型数来表示。对于由n个点序列([xn,yn],n=0,1,2,…,n-1)表示的曲线或多边形实体,坐标值整型化为([x′n,y′n]n=0,1,2…n-1)过程如下:
步骤1: 记录x0, y0,令x0 ′ = 0,y0 ′ = 0。
步骤2: 对于n=1,2,…,n-1,x′n=xn-xn-1y′n=yn-yn-1。
步骤3: 已知xn的最高精度为10-p,yn的最高精度为10-q,则x′n=x′n×10p,y′n=y′n×10q。
2 整数小波变换及其在矢量数据压缩中的应用
2.1 整数小波变换
传统的小波变换又称为第一代小波变换,其变换过程主要是利用小波滤波器组对图像行列分别滤波,进行卷积运算,由于都是实数域的变换,即使待分析信号本身是整数序列,相应小波变换系数也是实数。由于数字图像一般都是用整数表示,非常希望有一种“整数-整数小波变换”,将整数序列映射为整数小波系数,并且这种映射是可逆的,具有这种性质的小波变换称为整数小波变换(iwt)。sweldens等提出的提升(lifting)小波变换方法是一种新的小波变换工具,利用它可以不采用傅里叶变换作为主要分析工具,能够很容易地构造一般的整数小波变换[8]。
2.2 整数小波变换在曲线矢量数据压缩中的应用
整数小波变换可以将数据的绝大部分能量压缩到低频系数中,只有少部分在高频系数中。利用整数小波变换的这个特性可以实现数据的压缩。近年来基于整数小波变换的图像压缩已经成为一个研究热点[9]。
为了直观说明整数小波系数分布的特点,本文对国家铁路线曲线矢量数据(shp格式)使用第1节中的整型化处理后,进行了两层整数小波变换分解,并对小波系数进行统计分析如图1所示。
图1 全国铁路线曲线矢量数据
经过对图2的数据点分布图和图3的整数小波系数分布图进行对比,可以发现数据点经整数小波变换后得到的小波系数在空间分布上聚集性更强,大量的幅值分布在零附近,达到了去相关的目的,适合于采用高效的编码压缩方法。
图2 整型化处理后的数据点分布图
图3 数据点经整数小波变换后的小波系数空间分布图
3 基于整数小波变换(iwt)和模糊k-均值聚类的编码压缩方案
3.1 压缩流程
使用iwt变换压缩曲线矢量数据的原理是通过iwt变换将空间域的坐标串变换为频率域的小波系数序列,对系数序列进行量化和编码获得压缩数据流。在使用iwt变换前,将同一条曲线或者多边形实体的矢量数据组成一个待压缩子块。对每个块中的x和y坐标序列使用第一节中整型化方法转化成整型的偏移量序列。对得到的整型偏移 量序列进行整数小波变换,得到小波系数序列。对小波系数进行编码,得到压缩后的矢量数据。压缩流程如图4所示。
图4 iwt曲线矢量数据压缩流程
3.2 整数小波系数编码
由2.2节的统计分析可知,曲线矢量数据经过整型化和整数小波变换处理后得到的整数小波系数在空间分布上非常集中,大量的幅值集中在零附近。本文针对这个特点,提出使用改进的一维模糊c-均值聚类算法对整数小波系数进行聚类,建立系数字典,将整数小波系数转换为其所属类均值对应的字典索引,从而实现快速高效的编码。
3.2.1 模糊c-均值聚类(fcm)
设{xi,i=1,2,…,n}是n个样本组成的样本集合,预定类别数目c,mi,i=1,2,…,c为每个聚类的中心,μj(xi)是第i个样本对于第j类的隶属度函数。用隶属度函数定义聚类损失函数lμ:
lμ = ∑cj = 1∑ni = 1[μj (xi )]bdi 2j (1)
式中:di j = xi -mj 为第i个样本与第j个聚类中心间的欧几里得距离;b∈(1,∞)是可以控制聚类结果模糊程度的常数。
模糊c-均值方法[10]要求每个样本对于各个聚类的隶属度之和为1。即要满足:
∑cj=1μj(xi)=1, i=1,2,…,n(2)
使用拉格朗日乘数法进行推导,可以得到使式(1)取极小值的必要条件:
mj=∑ni=1[μj(xi)]bxi/∑ni=1[μj(xi)]b(3)
μj (xi ) = 1/∑ck = 1(di j /dik )2/(b-1)(4)
由上述2个必要条件,模糊c-均值聚类算法是一个简单的迭代过程。算法步骤如下:
步骤1:设定聚类数目c和参数b。
步骤2:初始化各个聚类中心mi。
步骤3:根据式(4)计算隶属度函数。如果小于某个确定的阈值,或相对上次隶属度函数值的改变量小于某个阈值,算法停止。
步骤4:根据式(3)更新各类聚类中心。
3.2.2 使用fcm字典法对整数小波系数编码
分别取出x方向的部分小波系数和y方向的部分小波系数当做做样本集合,使用3.2.1中的fcm算法分别得到x方向和y方向上的若干个聚类中心。由于整数小波系数是一维的,因此使用的是计算速度和收敛速度都很快的一维形式的fcm。
建立由聚类中心和对应索引组成的字典。编码时,将小波系数转换成其所属聚类中心对应的字典索引。字典索引的编码长度由聚类数目决定,若聚类数目为2n,则索引的编码长度为n位。
4 实 验
实验数据采用了国家基础地理信息中心下载的
