[机械自动化] 基于动态规划算法的矢量数据压缩改进算法

摘要:为了使移动设备存储大容量的矢量数据和提高矢量数据的网络传输效率，矢量数据压缩是一项很重要
的工作。提出了基于动态规划算法的矢量数据压缩的模型和改进方法，通过一条参考路径构造一条带形成最小误差
搜索范围，同时条带宽度可自适应调整。实验结果表明，该方法具有较高的效率，能够得到较小的压缩误差。
    关键词:矢量数据压缩;动态规划算法;Douglas-Peucker算法
   
Improved algorithm for vector data compression based on
dynamic programming
  CHEN
(1. College
Fei-xiang'，ZHOU Zhi-wu2, ZHANG Jian-bing
of Information, Beijing Forestry University,
2. National Geomatics Center of China; Beijing
Beijing 100083, China;
100044,以ina;
3. Department of Computer Science and Technology, China University of Petroleum, Beijing 102249, China)
Abstract: To increase the storage capacity of mobile equipment and improve the transmission efficiency of vector data on
network, this paper proposed a model
algorithm. This method constructed a
and improved method of vector data
smallest error range by a reference path,
mpression based on dynamic programming
  that can be adjusted automatically. The
experimental results show that this method is of higher compression ratio and smaller compression error.
    Key words: vector data compression; dynamic programming algorithm; Douglas-Peucker algorithm
0引言
    矢量数据压缩是地理信息系统GIS、计算机自动制图、计
算机图形学等学科中的一个常见问题。矢量数据的压缩可以
使移动设备(如PDA,Pocket PC, Smartphone等)存储更多的
空间数据，压缩后的矢量数据也加快了其在无线网络上的传
输速度。GIS中的矢量数据可分为点状图形要素、线状图形
要素、面状图形要素，但从压缩的角度来看，矢量数据的压缩
主要是线状图形要素的压缩，因为点状图形要素可看成是特
殊的线状图形要素，面状图形要素的基础也是线状图形要素，
需要由一条或多条线状图形要素围成。因此，线状图形要素
的压缩就成为矢量数据压缩中最重要的问题。
    近20年来，许多学者对矢量数据压缩这一课题做了大量
深人的研究，提出了许多算法，如垂距限值法、角度限值法、光
栏法、Douglas-Peucker算法(印litting算法)等，这些算法都是
非优化算法，仅仅根据一定的限差条件，对曲线上的数据点集
进行取舍，而没有考虑取舍后的曲线压缩结果是不是最优。
矢量数据压缩的优化算法一般有两种方式(假设原始曲线有
Nb个节点):1)给定矢量数据压缩误差E，使得压缩后的曲线
由Nb个初始节点中最少的节点组成，也就是使矢量数据压缩
率刀达到最高;2)给定矢量数据压缩率刀，也就是相当于给定
了压缩后曲线的节点数Ne，在Nb个初始节点中找Ne个节点，
使得由这Ne个节点组成的曲线的压缩误差E最小，本文研究
其中的第二种方式。文献[1〕提出了利用动态规划算法解决
矢量数据的优化压缩问题，但是此算法的时间复杂度为
0 (Nb?Ne )，空间复杂度为0 (NbNe )，不能满足网络实时压
缩、实时传输的需求。文献[2,3〕提出了改进算法，用一个搜
索条带代替全局搜索空间，提高了算法的效率，时间复杂度为
0[(Nb2W2)lNe]，其中W为搜索条带宽度，但是此改进算法
的条带宽度W需要人工设置，而且在迭代过程中W的值是固
定不变的，本文提出了一种自适应自动设置W的方法，从而
达到智能化、自动化的目的。
问题的描述与分析
1.1矢觅数据压缩率与压缩误差的定义
    压缩率和压缩误差是评价一个矢量数据压缩算法的基本
要素。对于矢量数据压缩率的定义很简单，一般采用压缩掉的
点的数量和压缩前点的数量的比值，即:
Nh一Ne
x 100%
    矢量数据压缩误差的定义要比压缩率的定义稍微复杂
些，当前主要有三种定义方法:最大位移距离、位移距离之和，
以及偏差面积。