下载文档原格式
矢量数据压缩方法
1. 矢量数据压缩方法之一是矢量数据简化。
在矢量数据中，点、线和面都可以通过简化算法进行压缩。
简化算法通过删除或合并冗余的几何信息来减少数据量，同时保持数据的整体形状和拓扑关系。
2. 矢量数据的压缩还可以使用线段压缩算法。
该方法通过将连续的线段近似为较短的线段，从而减少数据量。
常用的线段压缩算法包括Douglas-Peucker算法和Ramer-Douglas-Peucker算法。
3. 矢量数据的压缩方法还可以使用拓扑压缩。
拓扑压缩算法通过识别和编码拓扑关系来减少矢量数据的存储空间。
其中，常用的拓扑压缩算法包括基于格状编码的Quad-edge压缩算法和基于节点编码的Arc-node压缩算法。
4. 另外，矢量数据的压缩还可以采用编码压缩的方法。
编码压缩将矢量数据的几何信息和属性信息进行编码，从而减少数据的存储空间。
常见的编码压缩方法包括Huffman编码、Delta编码和LZW压缩算法。
总的来说，矢量数据的压缩方法可以通过简化、线段压缩、拓扑压缩和编码压缩等多种方法实现，根据不同的数据特点和压缩需求选择合适的方法。
文章编号:0494-0911(2010)04-0046-03中图分类号:P208 文献标识码:B矢量数据的优化压缩研究谭国律1,唐金秀2(1.上饶师范学院数学与计算机系,江西上饶334001;2.江西师范大学计算机信息工程学院,江西南昌330022)The Study for Optim ized Co m pression of V ector DataTAN G uo lv ,TANG Ji nx i u摘要:对于矢量数据,定义一种新的压缩误差,并在此压缩误差下,利用动态规划思想,讨论单实体和多实体矢量数据的压缩方法。
特别在多实体的矢量数据压缩中,使用由压缩率和压缩误差相结合的加权平均分配节点的方法。
实验结果表明,该压缩方法能够较好地反映矢量数据的性态,具有较高的压缩效率。
关键词:矢量数据;数据压缩;长度压缩误差;优化;动态规划收稿日期:2009-07-30作者简介:谭国律(1957)),男,江西余干人,教授,主要研究方向为计算机软件与理论。
一、引 言矢量数据是测绘领域中的重要数据,目前已有许多研究成果[1-2]。
矢量数据压缩问题是计算机图像处理中的重要问题。
是诸如G I S 、数字娱乐、数字地球、计算机自动制图、计算机图形学等学科中的一个常见问题。
矢量数据以线状图形为主要图形要素,经数字化后是由折线所组成,故矢量数据可由组成折线的所有顶点来描述。
矢量数据压缩是从组成曲线的顶点集合A 中抽取一个子集B,用这个子集B 在一定精度范围内尽可能地反映原数据集合A,而这个子集B 的点数应尽可能地少。
多年来,许多学者对矢量数据压缩做了大量深入的研究,提出了许多算法[3-4],如道格拉斯-普克(Doug las -Peucker)算法、垂距限值算法和光栏算法及角度限值算法等等。
这些算法都是非优化算法,仅仅根据一定的限差条件,对曲线上的数据点集进行取舍,而没有考虑取舍后的曲线压缩结果是不是最优。
文献[5-8]提出了利用动态规划算法解决矢量数据的优化压缩问题及改进算法。
矢量数据压缩的方法摘要：一、引言二、矢量数据压缩的原理1.矢量数据的特点2.压缩的必要性三、常见的矢量数据压缩方法1.轮廓压缩2.节点压缩3.颜色压缩四、压缩技术的应用领域五、我国矢量数据压缩技术的发展六、未来发展趋势与挑战七、总结正文：一、引言随着科技的飞速发展，地理信息系统（GIS）、计算机辅助设计（CAD）等应用日益普及，矢量数据在日常生活中的应用也越来越广泛。
然而，矢量数据往往具有数据量大、存储占用空间大的特点，给数据传输、存储和处理带来了一定的困扰。
为了降低矢量数据的存储和传输成本，提高数据处理效率，矢量数据压缩技术应运而生。
本文将对矢量数据压缩的原理、方法、应用领域以及我国矢量数据压缩技术的发展进行详细介绍。
二、矢量数据压缩的原理1.矢量数据的特点矢量数据由点、线、面等基本元素组成，具有独立性、无顺序性、可组合性等特点。
这些特点使得矢量数据在表示和处理时具有较高的灵活性。
2.压缩的必要性由于矢量数据量大，存储和传输成本高，直接影响了数据处理和应用的效率。
通过对矢量数据进行压缩，可以降低数据存储和传输的成本，提高数据处理速度，从而更好地满足实际应用需求。
三、常见的矢量数据压缩方法1.轮廓压缩轮廓压缩是通过简化矢量数据的几何形状，减少数据量的一种压缩方法。
常用的算法有Straight Line Approximation（SLA）和Quadtree（QT）等。
2.节点压缩节点压缩是通过对矢量数据进行节点合并、简化，减少节点数量从而实现数据压缩的方法。
常用的算法有Node-based Compression（NBC）和Delaunay Triangulation（DT）等。
3.颜色压缩颜色压缩是通过减少矢量数据中颜色的种类和数量，达到压缩目的的方法。
常用的算法有Color Quantization（CQ）和Color Reduction（CR）等。
四、压缩技术的应用领域矢量数据压缩技术在GIS、CAD、地图制图、遥感图像处理等领域具有广泛的应用。
![一种改进SVD分解的图像压缩算法[发明专利]](https://img.taocdn.com/s1/m/42f677e348649b6648d7c1c708a1284ac85005f6.png)
(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号 (43)申请公布日 (21)申请号 201810767898.3(22)申请日 2018.07.12(71)申请人 南京邮电大学地址 210023 江苏省南京市栖霞区栖霞街道广月路9-1号(72)发明人 闵莉花 李振华 卢畅 (74)专利代理机构 南京苏科专利代理有限责任公司 32102代理人 姚姣阳(51)Int.Cl.G06T 9/00(2006.01)(54)发明名称一种改进SVD分解的图像压缩算法(57)摘要本发明为解决图像压缩时的效率问题提出了一种改进SVD分解的图像压缩算法，其包括如下步骤：预处理原始图像矩阵A m ×n ；计算矩阵A T A 的特征值β1≥β2≥β3≥…≥βn ，特征值构成对角矩阵D；对应每个特征值求出特征向量并正交单位化得到v 1，v 2，v 3，…，v n ，并构成矩阵V；取m 和n中较小值记作r，取前r个特征值及其特征向量，求得奇异值置于原对角矩阵D，其余特征值置0；令矩阵U为m的全0方阵，并将其前r个列向量令为u i (i＝1,2,...,r)，且：确定需要的奇异值个数，令其为s(1≤s≤r)，对于矩阵U、D、V，分别取前s行和前s列构成新的矩阵U ′、D ′、V ′，做运算A ′＝D ′U ′V ′，得到恢复图像矩阵A ′；本发明提出的算法能够实现图像的快速高效压缩，在保持重构图像效果不变的同时缩短运算时间。
权利要求书2页 说明书5页 附图4页CN 109035349 A 2018.12.18C N 109035349A1.一种改进SVD分解的图像压缩算法，其特征在于，包括如下步骤：S1：预处理原始图像矩阵A m×n；S2：计算矩阵A T A的特征值β1≥β2≥β3≥…≥βn，其特征值构成对角矩阵D；S3：对应每个特征值求出特征向量并正交单位化得到v1，v2，v3，…，v n，根据所得到的特征向量v1，v2，v3，…，v n构成矩阵V；S4：取m和n中较小值记作r，取前r个特征值及其特征向量；S5：将S4中取得的前r个特征值开方运算得到奇异值σi：i＝(1,2,...,r)；S6：令D ii＝σi(i＝1,2,..,r),D ii＝0(r<i≤n)，重新构成矩阵D；S7：将S4中取得的前r个特征向量置于原矩阵V，其余向量置零向量，即V＝(v1 v2 … v r 0 … 0)n×n；S8：令矩阵U为m阶的全0方阵，并令其列向量为u i(i＝1，2，…，n)，且S9：确定需要的奇异值个数s(1≤s≤r)，对于矩阵U、D、V，分别取前s行和前s列构成新的矩阵U′、D′、V′；S10：做运算A′＝D′U′V′，得到恢复图像矩阵A′。
基于多实体的矢量数据压缩改进算法
陈飞翔;李华;于文洋
【期刊名称】《计算机工程与应用》
【年(卷),期】2008(044)019
【摘要】矢量数据压缩在地形环境仿真、制图综合、GIS等研究中具有重要作用,对增加移动设备的存储能力和提高矢量数据的网络传输效率来说是一项很重要的工作.根据动态规划算法理论、Douglas-Peucker算法和矢量数据的特点,提出了基于动态规划算法的矢量数据压缩的模型和改进方法,通过一条参考路径构造一奈带形成最小误差搜索范围,同时条带宽度可自适应调整.并将单一实体的优化压缩算法扩展为基于多实体的压缩算法,解决了图层压缩的全局优化问题.实验结果表明,该方法具有较高的效率,能够得到较小的压缩误差.
【总页数】3页(P200-202)
【作者】陈飞翔;李华;于文洋
【作者单位】北京林业大学,信息学院,北京,100083;国土资源部,土地整理中心,北京,100035;中国科学院,中国遥感卫星地面站,北京,100086
【正文语种】中文
【中图分类】TP391
【相关文献】
1.Douglas-Peucker算法在无拓扑矢量数据压缩中的改进 [J], 谢亦才;李岩
2.基于动态规划算法的矢量数据压缩改进算法 [J], 陈飞翔;周治武;张建兵
3.Douglas-Peucker算法在无拓扑矢量数据压缩中的新改进 [J], 谢亦才;林渝淇;李岩
4.一种改进的矢量曲线数据压缩算法 [J], 刘可晶
5.矢量数据压缩的Douglas-Peucker算法的实现与改进 [J], 杨得志;王杰臣;闾国年
因版权原因，仅展示原文概要，查看原文内容请购买。
２００７，４３（３４）１引言矢量数据压缩是地理信息系统ＧＩＳ、计算机自动制图、计算机图形学等学科中的一个常见问题。
矢量数据的压缩可以使移动设备（如ＰＤＡ、ＰｏｃｋｅｔＰＣ、Ｓｍａｒｔｐｈｏｎｅ等）存储更多的空间数据，压缩后的矢量数据也加快了其在无线网络上的传输速度。
ＧＩＳ中的矢量数据可分为点状图形要素、线状图形要说、面状图形要素，但从压缩的角度来看，矢量数据的压缩主要是线状图形要素的压缩，因为点状图形要素可看成是特殊的线状图形要素，面状图形要素的基础也是线状图形要素，需要由一条或多条线状图形要素围成。
因此，线状图形要素的压缩就成为矢量数据压缩中最重要的问题。
近２０年来，许多学者对矢量数据压缩这一课题做了大量深入地研究，提出了许多算法，如垂距限值法、角度限值法、光栏法、Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒ算法（Ｓｐｌｉｔｔｉｎｇ算法）等。
目前，Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒ算法是矢量数据压缩中一种较流行的算法，算法过程主要就是一个递归过程，它是Ｏ（ｎ２）的时间复杂度，同时，许多学者对此算法进行改进，提出了一些新的算法，如Ｓａａｌｆｅｌｄ和ＷｕＳｈｉｎ－ｔｉｎｇ等提出的改进方法能解决压缩后的曲线相交和自相交的问题，保持压缩前后曲线空间拓扑关系的一致性；Ｊ．ＨｅｒｓｈｂｅｒｇｅｒａｎｄＪ．Ｓｎｏｅｙｉｎｋ提高了算法的效率，使其时间复杂度由Ｏ（ｎ２）减少为Ｏ（ｎｌｏｇｎ）等。
以上这些算法都是非优化算法，仅仅根据一定的限差条件，对曲线上的数据点集进行取舍，而没有考虑取舍后的曲线压缩结果是不是最优。
对于矢量数据压缩的优化算法，一般有两种方式：假设原始曲线有Ｎｂ个结点，（１）给定矢量数据压缩误差Ｅ，使得压缩后的曲线由Ｎｂ个初始结点中最少的结点组成，也就是使矢量数据压缩率η达到最高；（２）给定矢量数据压缩率η，也就是相当于给定了压缩后曲线的结点数Ｎｅ，在Ｎｂ个初始结点中找基于ＧＡ的矢量数据压缩优化算法陈飞翔１，于文洋２，李华３ＣＨＥＮＦｅｉ－ｘｉａｎｇ１，ＹＵＷｅｎ－ｙａｎｇ２，ＬＩＨｕａ３１．北京林业大学信息学院，北京１０００８３２．中国科学院中国遥感卫星地面站，北京１０００８６３．国土资源部土地整理中心，北京１０００３５１．ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎ，ＢｅｉｊｉｎｇＦｏｒｅｓｔｒｙＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００８３，Ｃｈｉｎａ２．ＣｈｉｎａＲｅｍｏｔｅＳｅｎｓｉｎｇＳａｔｅｌｌｉｔｅＧｒｏｕｎｄＳｔａｔｉｏｎ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００８６，Ｃｈｉｎａ３．ＬａｎｄＣｏｎｓｏｌｉｄａｔｉｏｎａｎｄＲｅｈａｂｉｌｉｔａｔｉｏｎＣｅｎｔｅｒ，ｔｈｅＭｉｎｉｓｔｒｙｏｆＬａｎｄａｎｄＲｅｓｏｕｒｃｅｓ，Ｂｅｉｊｉｎｇ１０００３５，ＣｈｉｎａＥ－ｍａｉｌ：ｆｘｃｈｅｎ＠１２６．ｃｏｍＣＨＥＮＦｅｉ－ｘｉａｎｇ，ＹＵＷｅｎ－ｙａｎｇ，ＬＩＨｕａ．ＡｌｇｏｒｉｔｈｍｆｏｒｖｅｃｔｏｒｄａｔａｃｏｍｐｒｅｓｓｉｏｎｂａｓｅｄｏｎＧＡ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（３４）：１８５－１８７．Ａｂｓｔｒａｃｔ：Ｖｅｃｔｏｒｄａｔａｃｏｍｐｒｅｓｓｉｏｎｐｌａｙｓａｎｉｍｐｏｒｔａｎｔｒｏｌｅｉｎｔｈｅｒｅｓｅａｒｃｈｏｆｔｅｒｒａｉｎｅｎｖｉｒｏｎｍｅｎｔｓｉｍｕｌａｔｉｏｎ，ｉｎｔｅｇｒａｔｅｄｍａｐｐｉｎｇａｎｄＧＩＳ．Ｉｔｉｓａｖｅｒｙｉｍｐｏｒｔａｎｔｔａｓｋｆｏｒｔｈｅｉｎｃｒｅａｓｅｏｆｓｔｏｒａｇｅｃａｐａｃｉｔｙｏｆｍｏｂｉｌｅｅｑｕｉｐｍｅｎｔａｎｄｔｈｅｉｍｐｒｏｖｅｍｅｎｔｏｆｔｒａｎｓｍｉｓｓｉｏｎｅｆｆｉｃｉｅｎｃｙｏｆｖｅｃｔｏｒｄａｔａｏｎｎｅｔｗｏｒｋ．Ａｃｃｏｒｄｉｎｇｔｏｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｔｈｅｏｒｙ，Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒａｌｇｏｒｉｔｈｍａｎｄｖｅｃｔｏｒｄａｔａｃｈａｒａｃｔｅｒｉｓ－ｔｉｃｓ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓａｍｏｄｅｌａｎｄｍｅｔｈｏｄｏｆｖｅｃｔｏｒｄａｔａｃｏｍｐｒｅｓｓｉｏｎｂａｓｅｄｏｎＧＡ，ｅｎｃｏｄｅｓｆｏｒｔｈｅｎｏｄｅｏｆｃｕｒｖｅ，ａｎｄｃｏｍ－ｐｒｅｓｓｅｓｔｈｅｎｏｄｅｔｏｆｅｗｅｒｎｏｄｅｓｂｙｓｍａｌｌｅｒｅｒｒｏｒ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｉｓｍｅｔｈｏｄｃａｎｂｅｇｒｅａｔｅｒｃｏｍｐｒｅｓｓｉｏｎｒａｔｉｏｓ．Ｋｅｙｗｏｒｄｓ：ｖｅｃｔｏｒｄａｔａｃｏｍｐｒｅｓｓｉｏｎ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ；Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒａｌｇｏｒｉｔｈｍ摘要：矢量数据压缩在地形环境仿真、制图综合、ＧＩＳ等研究中具有重要作用，对增加移动设备的存储能力和提高矢量数据的网络传输效率来说是一项很重要的工作。
2．3矢量量化的相关概念102．4矢量量化的关键技术及技术指标13第三章矢量量化的算法研究163．1矢量量化码书设计算法的研究163．1．1经典的LBG算法163．1．2MD算法183．1．3码书设计算法比较193．2码字搜索算法203．2．1基于不等式的快速码字搜索算法203．2．2等均值等方差最近邻搜索算法213．3码字索引分配算法233．3．1BSA算法233．3．2禁止搜索码字索引算法25第四章矢量量化算法的实现264．1需求分析与整体设计264．1．1需求分析264．1．2整体设计264．2矢量量化算法的实现过程及说明274．2．1初始码书的生成274．2．2LBG矢量量化284．2．3矢量量化码字索引与恢复314．3实验结果及评价31第五章结论与展望34参考文献35致谢36附录37摘要伴随着通讯与信息科技的迅猛发展，数据压缩技术己经成为信息时代人们工作与科研的有力工具。
数据压缩技术，作为信息论研究中的一个重要课题，一直受到人们的广泛关注。
矢量量化技术作为数据压缩领域里的一个重要分支，以它压缩比高、编码速度快、算法简单清晰等良好的特性，在图像压缩等领域都已成为有力的手段和方法。
本文以矢量量化在静止图像方面的应用为研究目标，介绍了矢量量化的定义，基本理论、相关概念及发展现状，重点讨论研究了矢量量化的三大关键技术–码书生成和码字搜索和码字索引分配。
详细阐述了码书设计算法中的LBG算法和最大下降MD算法；快速码字搜索中的基于不等式快速码字搜所和码字索引分配中的BAS算法和禁止搜索码字索引算法等。
最后总结分析了现有典型的算法和改进算法并提出了自己的基于矢量量化算法的实现方法，编程实现了一个完整的数据压缩软件，取得了较好的效果。
关键词：数据压缩，矢量量化，LBGABSTRACT第一章绪论1．1课题的研究背景及意义1．1．1研究背景随着计算机和大规模集成电路的飞速发展，数字信号分析和处理技术得到很大发展，并已经广泛应用于通信、雷达和自动化等领域。
２００８，４４（１９）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用１引言矢量数据压缩是地理信息系统ＧＩＳ、计算机自动制图、计算机图形学等学科中的一个常见问题。
矢量数据的压缩可以使移动设备（如ＰＤＡ、ＰｏｃｋｅｔＰＣ、Ｓｍａｒｔｐｈｏｎｅ等）存储更多的空间数据，压缩后的矢量数据也加快了其在无线网络上的传输速度。
ＧＩＳ中的矢量数据可分为点状图形要素、线状图形要说、面状图形要素，但从压缩的角度来看，矢量数据的压缩主要是线状图形要素的压缩，因为点状图形要素可看成是特殊的线状图形要素，面状图形要素的基础也是线状图形要素，需要由一条或多条线状图形要素围成。
因此，线状图形要素的压缩就成为矢量数据压缩中最重要的问题。
对于单一的线状图形要素的压缩，近２０年来，许多学者做了大量深入的研究，提出了许多几何算法，如垂距限值法、角度限值法、光栏法、Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒ算法（Ｓｐｌｉｔｔｉｎｇ算法）等；也有学者提出用一些优化算法来解决优化压缩问题，如动态规划算法、图论法、遗传算法、禁忌搜索算法等。
但是，在多实体的线状图形要素的压缩方面还是研究的比较少，本文则将单一的线状图形要素的优化压缩扩展到多实体的优化压缩。
对于矢量数据压缩的优化算法，一般有２种方式：假设原始曲线有Ｎｂ个结点，（１）给定矢量数据压缩误差Ｅ，使得压缩后的曲线由Ｎｂ个初始结点中最少的结点组成，也就是使矢量数据压缩率η达到最高；（２）给定矢量数据压缩率η，也就是相当于给定了压缩后曲线的结点数Ｎｅ，在Ｎｂ个初始结点中找Ｎｅ个结点，使得由这Ｎｅ个结点组成的曲线的压缩误差Ｅ最小。
对于第（１）种方式，多实体的曲线压缩可以通过压缩误差Ｅ归并到单一曲线的压缩问题；而第（２）种方式则要复杂的多，因基于多实体的矢量数据压缩改进算法陈飞翔１，李华２，于文洋３ＣＨＥＮＦｅｉ－ｘｉａｎｇ１，ＬＩＨｕａ２，ＹＵＷｅｎ－ｙａｎｇ３１．北京林业大学信息学院，北京１０００８３２．国土资源部土地整理中心，北京１０００３５３．中国科学院中国遥感卫星地面站，北京１０００８６１．ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎ，ＢｅｉｊｉｎｇＦｏｒｅｓｔｒｙＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００８３，Ｃｈｉｎａ２．ＬａｎｄＣｏｎｓｏｌｉｄａｔｉｏｎａｎｄＲｅｈａｂｉｌｉｔａｔｉｏｎＣｅｎｔｅｒ，ｔｈｅＭｉｎｉｓｔｒｙｏｆＬａｎｄａｎｄＲｅｓｏｕｒｃｅｓ，Ｂｅｉｊｉｎｇ１０００３５，Ｃｈｉｎａ３．ＣｈｉｎａＲｅｍｏｔｅＳｅｎｓｉｎｇＳａｔｅｌｌｉｔｅＧｒｏｕｎｄＳｔａｔｉｏｎ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００８６，ＣｈｉｎａＥ－ｍａｉｌ：ｆｘｃｈｅｎ＠１２６．ｃｏｍＣＨＥＮＦｅｉ－ｘｉａｎｇ，ＬＩＨｕａ，ＹＵＷｅｎ－ｙａｎｇ．Ｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｆｏｒｖｅｃｔｏｒｄａｔａｃｏｍｐｒｅｓｓｉｏｎｂａｓｅｄｏｎｍｕｌｔｉｐｌｅｏｂｊｅｃｔｓ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００８，４４（１９）：２００－２０２．Ａｂｓｔｒａｃｔ：Ｖｅｃｔｏｒｄａｔａｃｏｍｐｒｅｓｓｉｏｎｐｌａｙｓａｎｉｍｐｏｒｔａｎｔｒｏｌｅｉｎｔｈｅｒｅｓｅａｒｃｈｏｆｔｅｒｒａｉｎｅｎｖｉｒｏｎｍｅｎｔｓｉｍｕｌａｔｉｏｎ，ｉｎｔｅｇｒａｔｅｄｍａｐｐｉｎｇａｎｄＧＩＳ．Ｉｔｉｓａｖｅｒｙｉｍｐｏｒｔａｎｔｔａｓｋｆｏｒｔｈｅｉｎｃｒｅａｓｅｏｆｓｔｏｒａｇｅｃａｐａｃｉｔｙｏｆｍｏｂｉｌｅｅｑｕｉｐｍｅｎｔａｎｄｔｈｅｉｍｐｒｏｖｅｍｅｎｔｏｆｔｒａｎｓｍｉｓｓｉｏｎｅｆｆｉｃｉｅｎｃｙｏｆｖｅｃｔｏｒｄａｔａｏｎｎｅｔｗｏｒｋ．Ａｃｃｏｒｄｉｎｇｔｏｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇａｌｇｏｒｉｔｈｍｔｈｅｏｒｙ，Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒａｌｇｏｒｉｔｈｍａｎｄｖｅｃｔｏｒｄａｔａｃｈａｒａｃｔｅｒｉｓｔｉｃｓ，ｔｈｅｐａｐｅｒｐｒｏｐｏｓｅｓａｍｏｄｅｌａｎｄｉｍｐｒｏｖｅｄｍｅｔｈｏｄｏｆｖｅｃｔｏｒｄａｔａｃｏｍｐｒｅｓｓｉｏｎｂａｓｅｄｏｎｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇａｌｇｏｒｉｔｈｍ，ａｎｄｅｘｔｅｎｄｓｔｈｉｓｔｏｔｈｅｃａｓｅｏｆｍｕｌｔｉｐｌｅｏｂｊｅｃｔｓ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｉｓｍｅｔｈｏｄｃａｎｂｅｓｍａｌｌｅｒｃｏｍｐｒｅｓｓｉｏｎｅｒｒｏｒｓ．Ｋｅｙｗｏｒｄｓ：ｖｅｃｔｏｒｄａｔａｃｏｍｐｒｅｓｓｉｏｎ；ｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇａｌｇｏｒｉｔｈｍ；ｍｕｌｔｉｐｌｅｏｂｊｅｃｔｓｃｏｍｐｒｅｓｓｉｏｎ摘要：矢量数据压缩在地形环境仿真、制图综合、ＧＩＳ等研究中具有重要作用，对增加移动设备的存储能力和提高矢量数据的网络传输效率来说是一项很重要的工作。
根据动态规划算法理论、Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒ算法和矢量数据的特点，提出了基于动态规划算法的矢量数据压缩的模型和改进方法，通过一条参考路径构造一条带形成最小误差搜索范围，同时条带宽度可自适应调整。
并将单一实体的优化压缩算法扩展为基于多实体的压缩算法，解决了图层压缩的全局优化问题。
实验结果表明，该方法具有较高的效率，能够得到较小的压缩误差。
关键词：矢量数据压缩；动态规划算法；多实体压缩ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２－８３３１．２００８．１９．０６２文章编号：１００２－８３３１（２００８）１９－０２００－０３文献标识码：Ａ中图分类号：ＴＰ３９１基金项目：国家科技支撑计划（ｔｈｅＮａｔｉｏｎａｌＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＳｕｐｐｏｒｔＰｒｏｇｒａｍｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．２００６ＢＡＤ２３Ｂ０２）。
作者简介：陈飞翔（１９７７－），男，博士，主要研究方向为ＭｏｂｉｌｅＧＩＳ；李华（１９７８－），女，工程师，主要研究方向为网络空间信息系统；于文洋（１９７４－），男，博士，助理研究员，主要研究方向为高性能地学计算。
收稿日期：２００８－０３－１７修回日期：２００８－０５－１９２００２００８，４４（１９）为要在多实体曲线中确定单一曲线的压缩后的结点数，它是一个全局最优的问题，本文主要研究第（２）种方式。
２单实体矢量数据压缩２．１问题的描述与分析设一条具有Ｎｂ个结点的曲线Ｆ：Ｆ＝｛ｆ１，ｆ２，…，ｆＮｂ｝＝｛（ｘ１，ｙ１），（ｘ２，ｙ２），…，（ｘＮｂ，ｙＮｂ）｝，给定了矢量数据压缩率η（０≤η≤１），即相当于给定了压缩后曲线的结点数Ｎｅ：Ｎｅ＝Ｎｂ×（１－η），其中Ｎｅ需要取整数，将曲线Ｆ压缩成具有Ｎｅ个结点的曲线Ｆ′，其中（Ｎｅ≤Ｎｂ），使其压缩误差Ｅ最小。
所以，压缩后的曲线Ｆ′可描述为：Ｆ′＝｛ｆ１′，ｆ２′，…，ｆＮｅ′｝，其中"ｆｓ′∈Ｆ，１≤ｓ≤Ｎｅ。
显然，Ｆ′是Ｆ的子集，曲线Ｆ′中的任何点都属于曲线Ｆ，而且对于曲线压缩时，曲线的起点和终点是要保留的，即ｆ１′＝ｆ１ｆＮｅ′＝ｆＮｂ$，矢量数据的压缩过程可以理解为：压缩后曲线Ｆ′的子线段（ｆｓ′，ｆｓ＋１′），（１≤ｓ＜Ｎｅ）由压缩前曲线Ｆ的部分曲线｛ｆｉ，…，ｆｊ｝，（１≤ｉ＜Ｎｂ，１＜ｊ≤Ｎｂ）压缩而成，其中：ｆｓ′＝ｆｉｆｓ＋１′＝ｆｊ$。
采用１．１节中介绍的位移距离之和Ｅ∑指标作为压缩误差评价标准。
设原始曲线Ｆ上点ｆｉ和点ｆｊ的连线的直线Ｔ为：ｙ＝ａｘ＋ｂ，原始曲线Ｆ上点ｆｉ和点ｆｊ之间的点ｆｋ（ｘｋ，ｙｋ）到直线Ｔ的距离ｄ：ｄ＝ｄ（ｆｋ，Ｔ）＝（ｙｋ－ａｘｋ－ｂ）２／（１＋ａ２）&，所以，将曲线Ｆ的部分曲线｛ｆｉ，…，ｆｊ｝，（１≤ｉ＜Ｎｂ，１＜ｊ≤Ｎｂ）压缩成曲线Ｆ′的子线段（ｆｓ′，ｆｓ＋１′），（１≤ｓ＜Ｎｅ）产生的压缩误差为：Ｅ∑（ｆｓ′，ｆｓ＋１′）＝Ｅ∑（ｆｉ，ｆｊ）＝ｊ－１ｋ＝ｉ＋１%（ｙｋ－ａｘｋ－ｂ）２／（１＋ａ２）&。
曲线Ｆ的压缩误差就是其所有部分曲线｛ｆｉ，…，ｆｊ｝，（１≤ｉ＜Ｎｂ，１＜ｊ≤Ｎｂ）的压缩误差的累计之和。
由于压缩后的曲线Ｆ′的子线段（ｆｓ′，ｆｓ＋１′），（１≤ｓ＜Ｎｅ）是由压缩前的曲线Ｆ的部分曲线｛ｆｉ，…，ｆｊ｝，（１≤ｉ＜Ｎｂ，１＜ｊ≤Ｎｂ）压缩而成，所以压缩误差可以表示为：Ｅ∑（Ｆ′）＝Ｎｅ－１ｓ＝１%Ｅ∑（ｆｓ′，ｆｓ＋１′）＝Ｎｅ－１ｓ＝１%ｊ－１ｋ＝ｉ＋１%（ｙｋ－ａｘｋ－ｂ）２／（１＋ａ２）&。
这个优化问题的最终求解问题就转变为：求压缩后的曲线Ｆ′，也就是曲线Ｆ′的Ｎｅ个结点，使压缩误差函数的取值最小：Ｅ∑（Ｆ′）＝ｍｉｎＮｅ－１ｓ＝１%Ｅ∑（ｆｓ′，ｆｓ＋１′）。
２．２问题的求解对于这个压缩误差函数的优化求解，首先定义一个不连续的２维状态空间Ω，建立压缩前曲线Ｆ的结点数Ｎｂ与压缩后曲线Ｆ′的子线段数的关系。
设压缩后曲线Ｆ′的子线段数为Ｈ（Ｈ＝Ｎｅ－１），则状态空间Ω为：Ω＝｛（ｎｂ，ｈ）：ｎｂ＝１，２，…，Ｎｂ；ｈ＝０，１，…，Ｈ｝。
空间Ω中的任何一个点（ｎｂ，ｈ）表示对具有ｎｂ个结点的曲线｛ｆ１，ｆ２，…，ｆｎｂ｝的优化压缩，压缩后的曲线有ｈ条子线段，即有ｎｅ＝ｈ＋１个结点。
所以，这个压缩优化问题的最终求解状态就是（Ｎｂ，Ｈ），压缩后的曲线Ｆ′可以理解为从状态（１，０）到状态（Ｎｂ，Ｈ）的一条路径Ｐ＝｛ｐ（０），ｐ（１），…，ｐ（Ｈ）｝。
空间Ω中，还需要定义状态（ｎｂ，ｈ）的代价函数Ｄ（ｎｂ，ｈ），它表示将具有ｎｂ个结点的曲线｛ｆ１，ｆ２，…，ｆｎｂ｝优化压缩成ｈ条子线段（ｎｅ个结点）的压缩误差。
求解这个最小误差的过程就是寻找一条从状态（１，０）到达（Ｎｂ，Ｈ）最优的路径，可以将这个状态空间Ω化简，由４个边界函数限制：Ｌ（ｈ）、Ｒ（ｈ）、Ｂ（ｎｂ）和Ｔ（ｎｂ）。
为了提高最小误差的搜索速度，本文在文献［２］的基础上提出了一种自适应修改搜索范围的改进算法。
步骤１通过Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒ算法快速计算出一条参考压缩路径Ｐ＝｛ｐ（０），ｐ（１），…，ｐ（Ｈ）｝，然后根据此参考路径Ｐ进行后续步骤的迭代求解，并且前一次的结果作为下一次迭代的参考路径。
步骤２构造最小误差的搜索空间Ω′，加快搜索速度。
因为在步骤一中已经计算出了一条参考路径，可以通过这一参考路径构造一个搜索条带，从而减少搜索空间。
因为路径中各点的拐角程度不同，即压缩度不同，所以搜索条带的宽度Ｗ可根据压缩度自适应变化。
改进的搜索空间Ω′的边界函数如下：Ｌ（ｈ）＝ｈ＋１ｈ＝０ｍａｘ｛ｈ＋１，ｈ＋（ｐ（ｈ）－ｐ（ｈ－１））×Ｈ／Ｎｂ｝ｈ＝１，２，…，$ＨＲ（ｈ）＝ｍｉｎ｛Ｎｂ，ｈ＋２×（ｐ（ｈ）－ｐ（ｈ－１））×Ｈ／Ｎｂ｝ｈ＝０，１，…，Ｈ－１Ｎｂｈ＝$ＨＢ（ｎｂ）＝０ｎｂ＝０ｈｎｂ＝Ｒ（ｈ－１）＋１，…，Ｒ（ｈ$）Ｔ（ｎｂ）＝ｍｉｎ｛Ｍ，ｈ＋２×（ｐ（ｈ）－ｐ（ｈ－１））×Ｈ／Ｎｂ－１｝ｎｂ＝Ｌ（ｈ），…，Ｌ（ｈ＋１）－１Ｈｎｂ＝Ｎ’)))()))*ｂ步骤３在搜索空间Ω′中运用动态规划算法求解。
