基于GA的矢量数据压缩优化算法_陈飞翔

２００７，４３（３４）１引言矢量数据压缩是地理信息系统ＧＩＳ、计算机自动制图、计算机图形学等学科中的一个常见问题。

矢量数据的压缩可以使移动设备（如ＰＤＡ、ＰｏｃｋｅｔＰＣ、Ｓｍａｒｔｐｈｏｎｅ等）存储更多的空间数据，压缩后的矢量数据也加快了其在无线网络上的传输速度。

ＧＩＳ中的矢量数据可分为点状图形要素、线状图形要说、面状图形要素，但从压缩的角度来看，矢量数据的压缩主要是线状图形要素的压缩，因为点状图形要素可看成是特殊的线状图形要素，面状图形要素的基础也是线状图形要素，需要由一条或多条线状图形要素围成。

因此，线状图形要素的压缩就成为矢量数据压缩中最重要的问题。

近２０年来，许多学者对矢量数据压缩这一课题做了大量深入地研究，提出了许多算法，如垂距限值法、角度限值法、光栏法、Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒ算法（Ｓｐｌｉｔｔｉｎｇ算法）等。

目前，Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒ算法是矢量数据压缩中一种较流行的算法，算法过程主要就是一个递归过程，它是Ｏ（ｎ２）的时间复杂度，同时，许多学者对此算法进行改进，提出了一些新的算法，如Ｓａａｌｆｅｌｄ和ＷｕＳｈｉｎ－ｔｉｎｇ等提出的改进方法能解决压缩后的曲线相交和自相交的问题，保持压缩前后曲线空间拓扑关系的一致性；Ｊ．ＨｅｒｓｈｂｅｒｇｅｒａｎｄＪ．Ｓｎｏｅｙｉｎｋ提高了算法的效率，使其时间复杂度由Ｏ（ｎ２）减少为Ｏ（ｎｌｏｇｎ）等。

以上这些算法都是非优化算法，仅仅根据一定的限差条件，对曲线上的数据点集进行取舍，而没有考虑取舍后的曲线压缩结果是不是最优。

对于矢量数据压缩的优化算法，一般有两种方式：假设原始曲线有Ｎｂ个结点，（１）给定矢量数据压缩误差Ｅ，使得压缩后的曲线由Ｎｂ个初始结点中最少的结点组成，也就是使矢量数据压缩率η达到最高；（２）给定矢量数据压缩率η，也就是相当于给定了压缩后曲线的结点数Ｎｅ，在Ｎｂ个初始结点中找基于ＧＡ的矢量数据压缩优化算法陈飞翔１，于文洋２，李华３ＣＨＥＮＦｅｉ－ｘｉａｎｇ１，ＹＵＷｅｎ－ｙａｎｇ２，ＬＩＨｕａ３１．北京林业大学信息学院，北京１０００８３２．中国科学院中国遥感卫星地面站，北京１０００８６３．国土资源部土地整理中心，北京１０００３５１．ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎ，ＢｅｉｊｉｎｇＦｏｒｅｓｔｒｙＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００８３，Ｃｈｉｎａ２．ＣｈｉｎａＲｅｍｏｔｅＳｅｎｓｉｎｇＳａｔｅｌｌｉｔｅＧｒｏｕｎｄＳｔａｔｉｏｎ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００８６，Ｃｈｉｎａ３．ＬａｎｄＣｏｎｓｏｌｉｄａｔｉｏｎａｎｄＲｅｈａｂｉｌｉｔａｔｉｏｎＣｅｎｔｅｒ，ｔｈｅＭｉｎｉｓｔｒｙｏｆＬａｎｄａｎｄＲｅｓｏｕｒｃｅｓ，Ｂｅｉｊｉｎｇ１０００３５，ＣｈｉｎａＥ－ｍａｉｌ：ｆｘｃｈｅｎ＠１２６．ｃｏｍＣＨＥＮＦｅｉ－ｘｉａｎｇ，ＹＵＷｅｎ－ｙａｎｇ，ＬＩＨｕａ．ＡｌｇｏｒｉｔｈｍｆｏｒｖｅｃｔｏｒｄａｔａｃｏｍｐｒｅｓｓｉｏｎｂａｓｅｄｏｎＧＡ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（３４）：１８５－１８７．Ａｂｓｔｒａｃｔ：Ｖｅｃｔｏｒｄａｔａｃｏｍｐｒｅｓｓｉｏｎｐｌａｙｓａｎｉｍｐｏｒｔａｎｔｒｏｌｅｉｎｔｈｅｒｅｓｅａｒｃｈｏｆｔｅｒｒａｉｎｅｎｖｉｒｏｎｍｅｎｔｓｉｍｕｌａｔｉｏｎ，ｉｎｔｅｇｒａｔｅｄｍａｐｐｉｎｇａｎｄＧＩＳ．Ｉｔｉｓａｖｅｒｙｉｍｐｏｒｔａｎｔｔａｓｋｆｏｒｔｈｅｉｎｃｒｅａｓｅｏｆｓｔｏｒａｇｅｃａｐａｃｉｔｙｏｆｍｏｂｉｌｅｅｑｕｉｐｍｅｎｔａｎｄｔｈｅｉｍｐｒｏｖｅｍｅｎｔｏｆｔｒａｎｓｍｉｓｓｉｏｎｅｆｆｉｃｉｅｎｃｙｏｆｖｅｃｔｏｒｄａｔａｏｎｎｅｔｗｏｒｋ．Ａｃｃｏｒｄｉｎｇｔｏｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｔｈｅｏｒｙ，Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒａｌｇｏｒｉｔｈｍａｎｄｖｅｃｔｏｒｄａｔａｃｈａｒａｃｔｅｒｉｓ－ｔｉｃｓ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓａｍｏｄｅｌａｎｄｍｅｔｈｏｄｏｆｖｅｃｔｏｒｄａｔａｃｏｍｐｒｅｓｓｉｏｎｂａｓｅｄｏｎＧＡ，ｅｎｃｏｄｅｓｆｏｒｔｈｅｎｏｄｅｏｆｃｕｒｖｅ，ａｎｄｃｏｍ－ｐｒｅｓｓｅｓｔｈｅｎｏｄｅｔｏｆｅｗｅｒｎｏｄｅｓｂｙｓｍａｌｌｅｒｅｒｒｏｒ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｉｓｍｅｔｈｏｄｃａｎｂｅｇｒｅａｔｅｒｃｏｍｐｒｅｓｓｉｏｎｒａｔｉｏｓ．Ｋｅｙｗｏｒｄｓ：ｖｅｃｔｏｒｄａｔａｃｏｍｐｒｅｓｓｉｏｎ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ；Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒａｌｇｏｒｉｔｈｍ摘要：矢量数据压缩在地形环境仿真、制图综合、ＧＩＳ等研究中具有重要作用，对增加移动设备的存储能力和提高矢量数据的网络传输效率来说是一项很重要的工作。

根据遗传算法理论、Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒ算法和矢量数据的特点，提出了基于ＧＡ的矢量数据压缩的模型和方法。

通过对构成曲线的结点进行二进制编码，以压缩后结点数较少和误差较小为优化目标，并利用Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒ算法控制选择、变异和交叉的有效性，所得最优解中值为１的基因对应压缩后的曲线结点。

实验结果表明，该方法能够得到较大的压缩率。

关键词：矢量数据压缩；遗传算法；Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒ算法文章编号：１００２－８３３１（２００７）３４－０１８５－０３文献标识码：Ａ中图分类号：ＴＰ３０１基金项目：国家科技支撑计划（Ｎｏ．２００６ＢＡＤ２３Ｂ０２）。

作者简介：陈飞翔（１９７７－），男，博士，讲师，主要研究方向为ＭｏｂｉｌｅＧＩＳ；于文洋（１９７４－），男，博士，助理研究员，主要研究方向为高性能地学计算；李华（１９７８－），女，工程师，主要研究方向为网络空间信息系统。

ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用１８５２００７，４３（３４）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用Ｎｅ个结点，使得由这Ｎｅ个结点组成的曲线的压缩误差Ｅ最小。

本文研究其中的第一种方式。

２问题的描述２．１矢量数据压缩的定义矢量数据压缩是从组成曲线的结点集合Ａ中抽取一个子集Ａ′，这个子集Ａ′在一定的精度范围内尽可能的反映原数据集合Ａ，而这个子集Ａ′的数量应尽可能的精简。

也就是说，对于给定曲线Ａ：Ａ＝｛ａ１，ａ２，…，ａｎ｝，（ｎ∈Ｚ，ｎ＞１），压缩后的曲线Ａ′：Ａ′＝｛ａ′１，ａ′２，…，ａ′ｍ｝，（ｍ∈Ｚ，１＜ｍ≤ｎ），其中#ａ′ｔ∈Ａ，（１≤ｔ≤ｍ）。

２．２优化问题描述设一条具有Ｎｂ个结点的原始曲线Ｆ：Ｆ＝｛ｆ１，ｆ２，…，ｆＮｂ｝＝｛（ｘ１，ｙ１），…，（ｘＮｂ，ｙＮｂ）｝，给定了矢量数据压缩误差Ｅ，求解问题就是求压缩曲线Ｆ′，并使曲线的压缩率η最大，即曲线Ｆ′组成的结点数最少，也就是Ｎｅ取最小值。

设压缩后的曲线Ｆ′可描述为：Ｆ′＝｛ｆ′１，ｆ′２，…，ｆ′Ｎｅ｝，其中#ｆ′ｓ∈Ｆ，１≤ｓ≤Ｎｅ。

显然，Ｆ′是Ｆ的子集，曲线Ｆ′中的任何结点都属于曲线Ｆ，而且对于曲线压缩时，曲线的起点和终点是要保留的，即：ｆ′１＝ｆ１ｆ′Ｎｅ＝ｆＮｂ$所以，矢量数据的压缩过程可以理解为：压缩后曲线Ｆ′的子线段（ｆ′ｓ，ｆ′ｓ＋１），（１≤ｓ＜Ｎｅ）由压缩前曲线Ｆ的部分曲线｛ｆｉ，…，ｆｊ｝（１≤ｉ≤Ｎｂ，１≤ｊ≤Ｎｂ）压缩而成，其中：ｆ′ｓ＝ｆｉｆ′ｓ＋１＝ｆｊ$设原始曲线Ｆ上结点ｆｉ和结点ｆｊ的连线的直线Ｑ为：ｙ＝ａｘ＋ｂ，原始曲线Ｆ上结点ｆｉ和结点ｆｊ之间的结点ｆｋ（ｘｋ，ｙｋ）到直线Ｑ的距离ｄ：ｄ＝ｄ（ｆｋ，Ｑ）＝（ｙｋ－ａｘｋ－ｂ）２／（１＋ａ２）%，根据问题的描述可知：ｄ≤Ｅ。

３问题的求解遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ＧＡ）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是由美国Ｍｉｃｈｉｇａｎ大学的ＪｏｈｎＨｏｌｌａｎｄ教授于１９７５年首先提出的，是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。

由于遗传算法采用了随机优化技术，且对所要求解的问题无连续性、无可微性等要求，有较大的概率求得全局最优解，因此，遗传算法为矢量数据压缩的全局优化问题的解决提供了一条新的途径。

根据ＧＡ的原理，用ＧＡ解决矢量数据压缩优化问题必须有以下步骤：步骤１编码设计。

确定编码方法，将问题参数编码形成染色体，也就是一个基因串。

步骤２初始化。

生成初始群体。

步骤３定义适应度函数。

提供适应度评估检测的依据，需要计算每个染色体的适应度，选择适应度最大的个体。

步骤４遗传操作。

共包含３种操作：选择、交叉、变异。

选择操作就是选择适应度大的染色体进入群体中；交叉操作就是从群体中选择两个染色体，按一定概率交换它们的基因信息以产生新的染色体；变异操作就是按一定概率改变染色体的一个或几个基因信息，保证算法具有全局搜索能力。

通过这３种操作产生新的一代群体。

步骤５控制参数。

包括染色体数目、交叉概率、变异概率。

如果是最优解，则结束，否则转入步骤４继续。

３．１染色体编码步骤１根据矢量数据压缩的定义，压缩过程就是从原始曲线的结点中保留一部分结点，删除一部分结点，基于这一考虑，染色体可采用二进制编码。

染色体的长度Ｌ为原始曲线Ｆ的结点总数，每一位基因表示对应的一个结点，基因的取值为１时表示压缩后该结点被保留，取值为０时表示压缩后该结点被删除，压缩后的曲线Ｆ′就是就是基因值为１对应的结点的连线。

根据对优化问题的描述可知，压缩过程中曲线的首尾结点是必须保留的，所以染色体的第一个基因值和最后一个基因值都必须是１。

假设原始曲线Ｆ为｛ｆ１，ｆ１，…，ｆ１０｝，染色体的编码长度就应该是１０（Ｌ＝１０）。

如果在染色体空间进行遗传优化后的取值为１１０００１０１０１，则压缩的曲线Ｆ′由５个结点组成：Ｆ′＝｛ｆ′１，ｆ′２，ｆ′３，ｆ′４，ｆ′５｝＝｛ｆ１，ｆ２，ｆ６，ｆ８，ｆ１０｝。

染色体用Ｔ表示，染色体对应的曲线则为：Ｆ＝Ｇ（Ｔ）。

群体是染色体的集合：Ｐ＝｛Ｔｉ｜ｉ＝１，２，…，Ｍ｝，其中Ｍ表示群体的规模，即染色体的数目。

３．２适应度函数根据对优化问题的描述，搜索的最终目标是压缩率最高，即压缩后曲线Ｆ′的结点数Ｎｅ最少，转换到遗传空间进行分析，则是染色体中基因值为１的最少。

染色体Ｔ中基因值为１的总和用Ｓ（Ｔ）表示。

所以最优的染色体应该是Ｓ（Ｔ）最小，根据遗传算法最优的染色体应该具有最大的适应度函数值，因此适应度函数可以定义为：Ｒ（Ｔ）＝１／Ｓ（Ｔ）。

３．３局部搜索策略本算法中引入了文献［６］中提出的局部搜索策略以保证染色体满足压缩误差要求。

在遗传过程中，设某一代群体中的一个染色体个体为Ｔ，将此染色体译码到搜索空间，即：Ｆ′＝Ｇ（Ｔ）＝｛ｆ′１，ｆ′２，…，ｆ′Ｎｅ｝＝｛ｆｇ１，ｆｇ２，…，ｆｇｎ｝依次从Ｆ′中取相邻的两结点ｆｇｉ，ｆｇ（ｉ＋１）这两结点连接形成的直线Ｑ为：ｙ＝ａｘ＋ｂ，结点ｆｇｉ和结点ｆｇ（ｉ＋１）之间的结点ｆｋ（ｘｋ，ｙｋ）到直线Ｑ的距离ｄｋ：ｄｋ＝ｄ（ｆｋ，Ｑ）＝（ｙｋ－ａｘｋ－ｂ）２／（１＋ａ２）%，其中ｇｉ≤ｋ≤ｇ（ｉ＋１），找出ｄｋ的最大值ｄｍａｘ，结合Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒ算法的基本思想，调整染色体第ｋ个基因的取值：Ｂ（Ｔ，ｋ）＝０；ｄｍａｘ≤Ｅ１；ｄｍａｘ＞$Ｅ这个调整过程其实是Ｄｏｕｇｌａｓ－Ｐｅｕｃｋｅｒ算法逆过程，保证了所有舍去的结点精度满足要求。