EN中文

地理科学 >

2012 , Vol. 32 >Issue 10: 1236 - 1240

DOI: https://doi.org/10.13249/j.cnki.sgs.2012.010.1236

GIS中面积偏差控制下的矢量数据压缩算法

  • 米学军 ,
  • 盛广铭 ,
  • 张 ,
  • 婧 ,
  • 白焕新 ,
  • 侯伟
展开
  • 江南遥感应用研究所,上海 200436

作者简介：米学军(1969-),男（回族）,山东济阳人,硕士,工程师,主要研究方向为GIS与遥感技术应用。

收稿日期: 2012-03-22

  要求修回日期: 2012-07-10

  网络出版日期: 2012-10-20

基金资助

中国科学院重大碳专项项目（XDA05060400）资助

收起

A New Algorithm of Vector Date Compression Based On the Tolerance of Area Error in GIS

  • MI Xue-jun ,
  • SHENG Guang-ming ,
  • ZHANG Jing ,
  • BAI Huan-xin ,
  • HOU Wei
Expand
  • Institute of Remote Sensing Applications Southern Yangtze,Shanghai 200436,China

Received date: 2012-03-22

  Request revised date: 2012-07-10

  Online published: 2012-10-20

Copyright

本文是开放获取期刊文献，在以下情况下可以自由使用：学术研究、学术交流、科研教学等，但不允许用于商业目的.
Fold

摘要

地理信息系统对矢量数据进行处理和应用的过程中,数据压缩是一个必须解决的问题,而通常采用的两种经典曲线数据压缩法：垂距限值法和道格拉斯-普克算法,都存在线段空间偏移过大以及面积偏差不可控的问题。利用曲线空间直线拟合的方法对曲线段中心轴进行空间逼近,通过增加面积偏差限值,提出了面积偏差控制下的矢量数据压缩算法,并以上海市崇明县岛屿边界轮廓矢量为例对该算法进行了验证。试验表明该方法对于解决两种经典压缩算法线段空间偏移过大以及面积偏差不可控的问题效果明显。

关键词： 地理信息系统; 数据压缩; 垂距限值算法; 道格拉斯—普克算法; 直线拟合; 面积偏差限值

本文引用格式

米学军 , 盛广铭 , 张 , 婧 , 白焕新 , 侯伟 . GIS中面积偏差控制下的矢量数据压缩算法[J]. 地理科学, 2012 , 32(10) : 1236 -1240 . DOI: 10.13249/j.cnki.sgs.2012.010.1236

Abstract

：In GIS, vector data is the most commonly used data structure. Data compression is an issue in vector data processing and applications. In this paper,several commonly used algorithms of vector data compression are analyzed and a new efficient algorithm is proposed to resolve the problems of the classic algorithms. The Douglas-Peucker algorithm and the vertical distance tolerance algorithm are commonly used algorithms in vector data compression.The Douglas-Peucker algorithm have the advantage that it has invariance in translation and rotation, but at the same time the result has a big area error and there is a contradiction between the compression ratio and retention of feature points for the curvature change. The advantages of the vertical distance tolerance algorithm is fast, but the area error and the characteristics of the retention curve space are very poor. In this paper,a new algorithm is proposed which improved vertical distance tolerance algorithm and resolved the shortcomings of the Douglas-Peucker algorithm and the vertical distance tolerance algorithm.The basic idea of the new algorithm is based on the vertical distance tolerance algorithm which increase an area error tolerance by adopting the method of straight line fitting to approximate the axis of the polyline in order to resolve the problem of the area error and declination of segment in space. An experiment is included, which verified the new algorithm is efficient by the example of dealing with the boundary contour vector of Chongming Island, Shanghai. In the experiment ,the new algorithm has only 1 km2 error, but the classic algorithms has 6 km2 of the error. The most advantage of the new algorithms is that the area error can be controlled in a specified range. The experiments show that comparing with the two classic algorithms,the new algorithm has no substantial advantage in the compression ratio,but greatly improved the performance of two targets, area error and declination of segment in space. It proved that the new algorithm is efficient in the data procession which has high requirement in area accuracy and spatial characteristics such as the use of land resources.

Key words： GIS; data compression; the vertical distance tolerance algorithm; the Douglas-Peucker algorithm; straight line fitting; the tolerance of area error

地理信息系统已成为地学研究的有力工具,由于矢量数据在空间分析、地表模拟、检索查询等方面相比栅格数据具有很大的优势,因此地学研究过程中应用的栅格数据如遥感影像、扫描地形图等很多情况下需要进行矢量化处理,矢量数据已成为地理信息系统普遍利用的数据结构形式。地理信息系统对矢量数据进行处理和应用的过程中,数据压缩是一个必须解决的问题。利用现代数据采集系统量化如遥感影像屏幕数字化、地图扫描数字化、导航地理数据生产系统等生产的矢量数据产生大量的冗余点,如此庞大的坐标数据量如不采取数据压缩技术,整个系统在存储、读取、显示以及数据空间计算等操作方面将承受巨大压力,从而导致系统的失败。此外,随着处理空间数据的比例尺发生变化以及作为地理信息系统重要功能的制图综合,同样存在数据压缩的需要[1~3]。
目前,矢量数据压缩常用算法主要有垂距限值法、角度限值法、道格拉斯-普克算法、光栏法,以及黄培之1995年提出的具有预测功能的曲线矢量数据压缩等算法[4]等。以上算法中应用最为普遍的是道格拉斯-普克算法,此算法的优点是具有平移、旋转的不变性,给定曲线和限差后,抽样结果一致[5]。但这种算法同时存在较大的面积偏差以及压缩程度与保留曲率变化特征点的矛盾[6],近年来很多学者提出对道格拉斯-普克算法的改进算法[5~9],如文献[5]、[6]分别增加了径向距离约束和角度分段的条件,文献[7]采用总体最小二乘法对道格拉斯-普克算法进行了改进等,文献[8]、[9]采用了动态规划和直线拟合的方法,一定程度上解决了道格拉斯-普克算法的缺陷。垂距限值法早在1967年就有人提出,这种算法的优点是速度快,但缺点是面积偏差以及保留曲线空间特征方面效果都很差[10,11],这种算法的改进算法鲜有人研究。
空间数据是地学研究的重要依据,地理信息系统作为地学分析的有力工具,高精度的空间数据是一个必要条件[12]。道格拉斯-普克算法和垂距限值法的缺陷使其对于面积精度以及曲线空间特征要求较高的数据处理存在限制,如土地资源信息系统中的土地利用图、行政区划图、农作物估产信息系统中的农作物分布图以及森林覆盖等数据的处理。基于以上两种算法存在的缺陷,笔者对垂直限距法进行了改进,提出面积偏差控制下的线段动态拟合垂距限值法,有效解决了道格拉斯-普克算法和垂距限值法的缺陷,并以上海市崇明县岛屿边界轮廓矢量为例,对该算法进行了验证。

1 道格拉斯-普克算法与垂距限值法及其缺陷分析

1.1 矢量数据压缩效果评价指标

压缩比[8]：是指矢量数据压缩前的数据量与压缩后的数据量之比。
线段空间偏移[8]：是指压缩后新生成的线段与被压缩的曲线在空间的偏移量,被压缩曲线的空间位置可用该曲线的中心轴衡量。
面积偏差[8]：（正面积+负面积）/线段长度。线段长度是指压缩过程中新产生的线段;正面积设为新产生线段左方原始曲线与新线段围成的面积;负面积设为新产生线段右方原始曲线与新产生线段围成的面积。对于区域数据这是个重要指标。
压缩比是数据压缩算法的数量指标,追求较大的压缩比是进行数据压缩算法设计的根本出发点,线段空间偏移控制、面积偏差控制是数据压缩的质量指标,一个好的压缩算法应该是结合工作的实际需求,以上3个指标的最大限度的平衡。

1.2 道格拉斯-普克算法

该算法实现的过程是[5]：先将一条曲线首尾点连成一条直线,求其余各点到该直线的距离di,取其最大值dmax与规定的临界值Dε比较,若dmax < Dε,则将直线两端间各点全部舍去,否则将离该直线距离最大的点保留,并将原线条分成两部分,对每部分线条再实施该抽稀过程,直至结束,见图1。
Fig. 1 Sketch map of the the Douglas-Peucker algorithm

图1 道格拉斯-普克算法简化示意图

1.3 垂距限值法

垂距限值法与道格拉斯-普克算法的基本原理是一样的[12],但它不是从整体角度去考虑一条完整的曲线,而是从第一点开始依次筛选,即以第一点为起点,计算以第二点到第一点和第三点所构成的直线的距离d,如果该距离大于某一阈值Dε,则保留第二点,并以该点作为新的起点,计算第三点到第二点和第四点所构成的直线的距离,否则去掉第二点,仍以第一点为起点,计算原曲线上第三点到第一点和第四点所构成直线的距离。依此类推,直至曲线上最后一点,见图2。
Fig. 2 Sketch map of the vertical distance tolerance algorithm

图2 垂直限距算法简化示意图

1.4 缺陷分析

从前面道格拉斯-普克算法和垂距限值算法的简化示意图可看出（因本文重点不是讨论道格拉斯算法与垂距限值算法的区别,所以可假设存在特殊曲线的一段经过两种算法计算后产生相同结果[13]）：该示意图中的部分曲线ACEGHIB化简为线段AB（见图3）,其与原曲线围成区域的负面积远大于其与原曲线围成区域的正面积,即这个示例存在较大的负面积偏差。产生面积偏差的直接原因是新生成的线段AB与原曲线段中心轴A'B'存在空间偏移, 线段空间偏移与面积偏差互为原因、互为结果。而对一般矢量数据,这种情况也是普遍存在的,只不过偏差值或正或负。从道格拉斯-普克算法和垂距限值算法的原理可见,通过设定不同的限值D,线段的空间位移是可控的,而由此产生的面积偏差在一个区域上是不可控的[5],有可能局部面积偏差的累积产生一个较大的偏差值,特别是处理的面状地理数据对面积精度要求严格时,其面积偏差可能超出允许范围。
Fig. 3 Sketch map of the declination of segment in space and area error in the classic algorithm

图3 线段空间偏移与面积偏差示意图

针对以上两种算法存在的问题以及产生的原因,本文通过增加面积偏差限值条件,提出了面积偏差控制下的线段动态拟合算法。

2 面积偏差控制下的线段动态拟合矢量数据压缩法

2.1 基本思想与算法实现

面积偏差控制下的线段动态拟合法的基本思想是以垂直限距法为基础,对曲线段进行线段动态拟合,使新拟合线段最大程度在空间上逼近这个曲线段的中心轴,从而解决地理空间数据传统压缩算法产生的面积偏差以及线段的空间偏移过大的问题。其实现的具体步骤如下：
第一步：以垂距限值作为首要条件,计算垂距,取出需进行拟合的曲线段。
首先以常规垂距限值法计算取点（见图2）,在垂距限值的控制下,对于曲线段内可删除2个及以上连续点的曲线段的首尾点进行标记。图3可见：由曲线段ACEGHIB垂距限值的控制下得A、B为首尾两点,取得需进行拟合的的曲线段ACEGHIB。如果曲线段内仅仅可删除一个点或没有点可删除,按常规垂距限值法处理。
第二步：进行面积偏差控制下的曲线段直线动态拟合。
根据前面面积偏差公式,计算线段AB与曲线ACEGHIB围城的面积偏差
s=（S△ACD+S△EDF+S△FGH+S△HIB）/|AB| （1）
式中,S△EDF正值,其他为负值。如果s<Sε,线段AB作为曲线段ACEGHIB的压缩结果进行保留,中间点全部删除;如果 s>Sε,对线段AB进行空间动态平移和小角度旋转得A″B″,计算直线A″B″与曲线段ACEGHIB的交点坐标,进行面积偏差计算,反复平移不断拟合,直至满足s<Sε为止。线段A″B″作为曲线段ACEGHIB的压缩结果进行保留,原曲线段ACEGHIB全部删除。计算时需同时取得A点的前一点坐标与B点的后一点坐标,用于拟合计算直线与曲线段的交点A″点与B″点（见图3）。
第三步：以B''作为新的起点重复进行第一步与第二步的计算,直至整个曲线节点计算完毕。
从前面偏差计算公式可见,面积偏差值不是一个面积单位,而是长度单位,其几何意义可以理解为被压缩区段生成的线段与该曲线段中心轴的空间偏移量,值越小越逼近曲线段中心轴。只所以除以线段长度是为了控制单位长度内的面积偏差量的均匀性。

2.2 案例分析

选用比例尺1：10万的崇明县岛屿轮廓扫描矢量化图作为实例,分别采用垂距限值法和本文算法进行了压缩试验（垂距限值算法与道格拉斯算法在面积偏差方面无本质区别[8,9,13],仅采用其中一种算法试验）,垂距限值都设定为30 m,本文算法增加面积偏差限值,设定为5.0 m。图4为两种不同算法计算结果与原始数据对比图。
原始数据全部节点数11 901个,数据格式为Mapinfo的mif格式,数据量252 KB,岛屿区域面积为1 505 km2。垂距限值法压缩后,节点数为1 630个,数据量34.5 KB,压缩比为7.3,区域面积计算为1 549 km2 ;文中算法压缩后,节点数为1 653个,数据量35.1 KB,压缩比为7.2,区域面积计算为1 506 km2。
为清楚对比压缩效果,本文对局部进行放大。图5为两种不同算法的压缩效果与原始数据空间叠加局部放大图,表1显示局部放大区域不同曲线区段的两种算法下的面积偏差值,及空间偏移情况。
Fig. 4 Results comparison between the classic algorithm and the author′s

图4 基于两种不同方法的压缩效果对比

Fig. 5 Spatial overlay of among the original data , the classic algorithm and the author′s algorithm results in drawing of partial enlargement

图5 两种不同算法的压缩效果与原始数据空间叠加局部放大图

Table 1 Area error comparison between the classic algorithm and the author’s

表1 垂距限值法与本文算法的面积偏差值对比（m）

曲线段 垂距限值法 本文算法
面积偏差 空间偏移 面积偏差 空间偏移
2、3号节点间 11.97 明显偏移 5.0 无明显偏移
4、5号节点间 7.06 明显偏移 5.0 无明显偏移
5、6号节点间 12.34 明显偏移 5.0 无明显偏移
6、7号节点间 5.87 明显偏移 5.0 无明显偏移
7、8号节点间 0.18 无明显偏移 0.18 无明显偏移
8、9号节点间 4.5 无明显偏移 4.5 无明显偏移
10、11号节点间 3.45 无明显偏移 3.45 无明显偏移
12、13号节点间 10.06 明显偏移 5.0 无明显偏移
15、16号节点间 17.64 明显偏移 5.0 无明显偏移
从图5和表1可见,在压缩比这个指标上,文中算法与垂距限值法无实质差别;但在空间偏移这个指标上,文中算法相比垂距限值法有很大的改进,可以更好的逼近原始数据中心轴;在面积偏差的这个指标上,文中算法的曲线分段面积偏差大于设定值的已经被控制在设定值以内,面积偏差得到改善,而垂距限值法存在较大的面积偏差。从整个崇明县岛屿面积来看,文中算法面积产生近1 km2的误差,而垂距限值法产生6 km2的误差。由于面积偏差在不同的曲线分段存在正负,整个区域面积的误差与曲线的形态有直接关系,因此整个区域的面积误差不能完全说明算法的优劣,但文中算法对于面积的误差可以控制,而垂距限值法无法控制。
理论上,可通过设定更小的面积偏差限值,使压缩后的数据面积偏差值更小甚至为零;可通过设定较大的垂距限值提高压缩比。但对于实际工作来讲,由于要考虑压缩比、特征点保留、线段空间偏移等指标,不可能要求面积偏差为零,只要设定面积偏差在一个合理值即可。

3 结 论

土地利用、行政区划、农作估产以及森林覆盖等信息系统对于研究目标的面积精度以及曲线空间特征有较高要求。本文针对两种经典曲线压缩算法在这两个指标上存在的缺陷,通过增加面积偏差控制条件,对曲线段进行直线拟合,提出面积偏差控制下的矢量数据压缩算法。从算法的原理上以及崇明县岛屿轮廓扫描矢量化图作为实例的实验证明：该算法的压缩比指标相对于前面两种经典算法没有实质性的优势,但在改善面积偏差过大以及线段空间偏移这两个指标上效果明显：崇明县岛屿轮廓矢量化图压缩结果的曲线段无明显偏移、面积偏差控制在指定误差阈值以内,整个区域面积误差小于1 km2。由于在线段直线拟合过程中需要进行直线空间相交点方程的反复求解以及三角形或多边形面积计算,其计算量相对于前面两种经典算法大很多,但由于现在计算机速度的高速增长,计算量问题已经不会对现实工作产生实际影响。

The authors have declared that no competing interests exist.

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
黄杏元. 地理信息系统概论[M].高等教育出版社,1989.

[2]
刘兆礼. 遥感影像屏幕数字化高效方法研究[J].地理科学,1999,19(3):250~253.

[3]
赵斌. 导航地理数据生产系统及其关键技术研究[D].郑州:中国人民解放军信息工程大学,2007.

[4]
黄培之. 具有预测功能的曲线矢量数据压缩方法[J].测绘学报,1995,24(4):316~319.

[5]
杨得志,王杰臣,闾国年.矢量数据压缩的Douglas-Peucker算法的实现与改进[J].测绘通报,2002,(7):18~19.

[6]
刘晓红,李树军.矢量数据压缩的角度分段道格拉斯算法研究[J].四川测绘,2005,28(2):51~52.

[7]
杨云,孙群,朱长青.曲线数据压缩的总体最小二乘算法[J].西安电子科技大学学报,2008,35(5):946~950.

[8]
陈飞翔,周治武,张建兵.基于动态规划算法的矢量数据压缩改进算法[J].计算机应用,2008,28(1):168~170.

[9]
Jaafar J.Line Generalization: Least Square with Double Tolerance[C].Third International Conference on Management Information Systems Incorporating GIS & Remote Sensing. Southampton: Wessex Institute of Technology, 2002:135-144.

[10]
Hershberger J, Snoeyink J.An O (nlogn) implementation of the Douglas-Peucker algorithm for line simplification[C].Proceedings of the Tenth Annual Symposium on Computational Geometry,1994,(6):383-384.

[11]
Ramer U.An Iterative Procedure for the polygonal Approximation of Plane Curves[J]. Computer Graphics and Image Processing,1972,(1):244-256 .

[12]
杨海军,邵全琴.GIS 空间分析技术在地理数据处理中的应用研究[J].地球信息科学,2007,9(5):70~75.

[13]
彭认灿,董箭,郑义东,等. 垂距法与道格拉斯-普克法删除冗余顶点效率的比较[J].测绘通报,2010,(03): 66~67.

[14]
陈春,王野乔,薄立群,等.地理信息系统中矢量数据快速求交及其应用[J].地理科学,1990,10(2): 134~141.

Options
文章导航

/

〈 〉