矢量数据压缩方法简介2010021979 钟亚平摘要：本文阐述了矢量空间数据压缩的概念， 评价矢量空间数据压缩方法的常用指标 对常见的适量空间数据压缩方法了介绍与评价，并对一些改进方法做了介绍关键词：矢量空间数据，压缩， DP算法引言WebGIS是通过In ternet为网络用户提供空间信息共享与分析的一种软件技术，是 GIS重要的发展方向之一然而，描述现实世界的空间数据量是具大的，面对如此海量 的空间数据，数据的存储及在有限网络宽带下的传输一直是限制 WebGIS应用的瓶颈之一对空间数据进行压缩，以减少存储空间和提高传输速率 另外由于应用的日益扩大，导致了多比例尺特征 GIS的需求，而目前建立多比例尺特征 GIS的常用方法是重复数字化，但这种方法耗资巨大，数据采集与建库工作繁重，数据不稳定因此，研究有效的 GIS数据简化压缩方法十分重要由于栅格数据的文件格式比较统一，而且其压缩技术 已经非常成熟，所以本文重点介绍矢量空间数据的压缩技术相关概念1、 矢量空间数据压缩GIS中的矢量数据可分为点状图形要素、线状图形要素、面状图形要素但从 压缩的角度来看，矢量数据的压缩主要是线状图形要素的压缩 ，因为点状图形要素可看成是特殊的线状图形要素， 面状图形要素的基础也是线状图形要素， 需要由一条或多条线状图形要素围成。
因此，线状图形要素的压缩就成为矢量数据压缩中最 重要的问题矢量数据压缩是从组成曲线的点集合 A中抽取一个子集B,用这个子集B在一定的精度范围内尽可能地反映原数据集合 A,而这个子集B的点数应尽可能少矢量数据压缩与化简的核心是在不扰乱拓扑关系的前提下对原始采样数据进行合 理的删减对矢量数据进行压缩除了能节约存贮空间， 加快网络传输速度之外， 其本质的原因在于原始的数据存在一定的冗余 这种数据冗余一方面是数据采样过程中不可避免产生的；另一方面是由于具体应用变化而产生， 比如大比例尺的矢量数据用于小比例尺的应用时，就会存在不必要的数据冗余因此应该根据具体应用来选择合 适的矢量数据压缩与化简算法2、 矢量数据压缩率与压缩误差压缩率和压缩误差是评价一个矢量数据压缩算法的基本要素分别以N和n表示矢量数据压缩前后的结点数 矢量数据压缩率为压缩后点的数量与压缩前点的数量之比，即n = (N-n) / N * 100%目前，描述压缩误差的方法主要有三种，分别是最大位移距离、位移距离之和 以及偏差面积假设压缩前的曲线为 Fs,…,Ft,压缩后的线段L最大位移距离是指压缩前曲线Fs,…,Ft上的点到压缩后线段 L的最大距离，通过最大位移距离可以控 制压缩后的曲线的位移偏差。
最大位移距离的具体计算公式为 ：o位移距离之和是指压缩前曲线 Fs,…,Ft上的点到压缩后线段 L的距离之和位移距离之和具体计算公式为：e（L） =-- 偏差面积是指偏差面积是指压缩前曲线 Fs,…,FW压缩后线段L组成封闭图形的面积偏差面积具体计算公式为：(0丿=Area( (F^ F胖 F J )矢量空间数据压缩方法分类对空间数据的压缩技术可分为无损压缩和有损压缩无损压缩算法又分为两种：一种是基于现在成熟的通用压缩算法比如 zip、rar等，但该方法没有考虑到矢量数据特有的特征，因此压缩比不高，很少单独使用；另一种是考虑到矢量数据本身的特征以及矢量数据的表达精度的有限性对存储的 数据类型进行处理来达到数据压缩的目的例如李青元等提出用 int甚至short型代替double和float型来存储空间坐标点以取得较高压缩比例的方法而有损压缩，特别是对矢量图形（如：Map Info的MID和基于XML的SVG矢量数据） 的有损压缩，近年来引起了不少学者的关注 目前，矢量数据压缩算法主要有：距离控制类算法，如垂距限值法、 Douglas—Peucker算法（Spliting算法）；角度控制类算法，如角度限值法；黄培之 1995年提出的具有预测功能的曲线矢量数据压缩方法；以及基于 小波技术的压缩方法。
另外基于文档模型的压缩也有不少文献讨论，比如基于 GML,基于XML四、 矢量空间数据压缩经典理论与方法1、垂距限值法与角度限值法这两种方法的大概思路为，计算某个点到它前后相邻两点所成直线的距离或角度， 如果大于某个阀值就保留，如果小于阀值则舍弃将这个过程应用于曲线除端点外的所 有点，最后的结果就是压缩后的曲线这两种方法确定点的保留取决于它两邻的两点，不利于整体的表现角度限值算法效率低，不常用垂距法可能因为线的反向而导致结果不一样 也有文献讨论将两种方法综合，即垂距与角度都满足条件时才保留点的压缩方法点冑丸干誕定的舉避・角度丸于mi建的幅盏2nK■輻小于3 去It■戲后豹2、Douglas-Peucker 算法（DP 算法）基本思想：首先确定曲线的最左边和最右边作为起始点 （对于闭曲线），对于开曲线可选择其两个端点作为起始点 然后找出位于两个端点之间的曲线离散点距这两个端点联机的最大距离点，如果该距离大于给定的精度限差，则该点被确定为保留点然后分别 再用已经得到的各相邻保留点为起始端点 ，用同样的方法对于他们之间的曲线上的离散点进行检测，确定下一批压缩后的保留点用上述方法反复进行 ，直至两端点之间的曲线离散点距两端点联机的距离的最大值小于给定的精度限差为止。
最后可得到满足给定精度限差的曲线压缩后的全部保留点原理图如下所示：该算法的特点是：具有平移、旋转的不变性 但该算法也存在以下不足：曲线压缩的精度一般用位移矢量和偏差面积来衡量， 在该算法中利用垂向距离作为约束条件来决定曲线上点的取舍可以控制位移矢量的大小，但无法有效地控制偏差面积的大小； DP算法中限差 D的设定还不能实现自动化，需要人为参与，而限差的设定直接影响压缩 的效果；对初始条件敏感，压缩结果可能在两多边形的公共边出现“裂缝”现象3、基于delaunay三角网的算法基本思想： 先根据所给出的组成曲线的点序列 ，建立delaunay三角形找出 3个顶点是线目标上连续的 3个点的三角形，把三角形的特征值小于一定阈值的那个三 角形的中间一顶点去掉（如右图所示） 该方法的最大好处是获得了线化的结构特征，同时保留了拓扑的一致性特征值的考虑因素有：面积、三角形边长、平均边长、 三角形角度、三角形宽度等Delaunay三角网综合模型，其工作量和计算量比较大，占用大量的计算机资源4、李青元等提出的压缩算法基本思想： 将矢量空间数据的坐标用 int型，甚至可以用 short型来代替传统的 double型或float型。
将地图坐标映射为 short型，其数据表示范围是 -32768至32767, 或0到65536用户在计算机上浏览地图，总是先显示全图，然后再逐级放大，若屏幕大小按 800*600 计算，则 short 表示的数据可以使 800*600 大小的全图放大 80 倍，而 仍然没有精度损失 其中用到一种“偏移量压缩”的方法， “偏移量压缩”的思想是： 地图映射到虚拟屏幕后，弧段只记录其起点 (X、y)的坐标•而其后续型值点的坐标可用相邻两点间 x、 y 的偏移量来表示．即弧段除起始点以外的其他后续点，用 2 个 byte 就可以表达一个坐标点5、 基于目标函数的最佳多边形拟合算法基本思想： 该算法的基本思想是从已给定的起始点出发 , 利用所构造的目标函数和 约束条件来对其后续节点进行测试 ,以获取压缩后的下一个保留点6、 基于小波的压缩方法基本模型：L2(r)看成是某地理空间在特定比例尺下的矢量地图数据模型， f(x)是其上各个图形要素， 那么 {Vm} 可以看成是基于此比例尺下原始矢量数据的多级压缩模型 可以认为原始矢量数据模型 L2(R)=V0,从V0出发，应用尺度函数可以表示出 V1 ,V2,…，Vm, V1, V2,…，Vm则可以看成是基于小波多尺度分析的原始矢量数据 V0的压缩结果，也就是矢量地图数据在各个层次上的近似表示。
运用小波技术对矢量数据进行压缩的结果对应于原始数据的低频部分， 压缩之后丢掉了原始数据的高频信息利用小波技术压缩矢量数据具有较好的效果，而且实现的效率较高，但也有如下 缺点： (1)利用二进制小波进行多级变换压缩矢量数据时将不可避免地产生误差积累，这样将导致压缩结果出现变形甚至错误； (2)B 样条小波适合用于等高线数据的压缩， 因为经过变换之后既可使地形特征保持得比较好，又可使变换后的等高线数据更加光 滑，但该方法也存在误差积累； (3)用多进制小波变换对矢量数据进行压缩不存在误差的积累， 但变换后的数据中的地性线大部分遭到了破坏， 因此在对数据进行压缩之前最 好先提取原始数据的地性线，压缩之后再插入，这样压缩的效果会更好五、 矢量空间数据压缩改进方法1 、 Douglas-Peucker 算法在无拓扑矢量数据压缩中的改进 传统Douglas-Peucker算法在对相邻多边形的公共边进行压缩时可能会出现"裂缝” 现象，而且有数据冗余，针对以上两个问题，该文献提出了公共边对象化 DP改进算法的实现首先，公共边对象化 DP改进算法的第一步是提取公共边，对于没有相邻关系的多 边形就没有必要提取了， 因此， 在提取公共边之前需要判断两个多边形有没有相交， 从 而提高算法的效率。
判断出来后， 接下来就要提取公共边了 提取公共边的过程实质上 就是字符串匹配的过程提取公共边后，采用 OOP技术，创建公共边类，每提取出一段公共边就用此公共边类将其实例化， 即创建了公共边对象， 并将此公共边的各种标记 信息初始化然后把对象存入动态数组当有此公共边的相应多边形 j 要压缩时，查看Compressed 标记是否为 true ，若是，则直接将压缩过的公共边替换多边形中的此段公 共边，再压缩j中的非公共边；若 Compressed标记为false,则分段压缩多边形j，并将 压缩 后 的 公 共边 坐 标存 入动态 数 组 ComCoordVector 中 ， 并修 改 对 象 中 相 应 的 Compressed」标记为 true当 Compressed」禾口 Compressed」者E为true 时，说明共用此 公共边的两多边形都压缩完了,可把此对象销毁 ,以减少空间算法流程如下所示：开始|取下一个多边形i构造啲最小外接MBRi取下一个多边 7Kj(j=i+l,.»,n)构造j的最小外接何RRj压缩i的非公共边已压缩公共边替换i中相应的公共边’若对象用i寸两次七则锥毀72、基于动态规划算法的矢量数据压缩改进算法普通的方法都是根据一定的限差条件， 对曲线上的数据点集进行取舍， 而没有考虑取舍后的曲线压缩结果是不是最优。
矢量数据压缩的优化算法一般有两种方式(假设原始曲线有 Nb个节点)：1) 给定矢量数据压缩误差 E,使得压缩后的曲线由 Nb个初始节点中最少的节点组成，也就是使矢量数据压缩率 n达到最高；2) 给定矢量数据压缩率 n，也就是相当于给定了压缩后曲线的节点数 Ne,在Nb个初始节点中找 Ne个节点，使得由这Ne个节点组成的曲线的压缩误差 E最小基本思想：设有一条曲线 F,有Nb个点， F=｛f1,f2,f3,…,fNb｝，压缩后为线F',根据压缩率n计算出剩下的点为 Ne个，即F' =｛f' 1,f' 2,f' 3,…,f' Ne｝且 f1=f' 1, fNb=f' Ne。