地球信息科学理论与方法

基于累积偏移算法的线路矢量数据实时压缩

展开
  • 1. 成都信息工程学院智能信息处理实验室, 成都 610225;
    2. 海南椰岛(集团)股份有限公司, 海口 570100
王 飞(1989- ),男,江苏灌云人,硕士生,研究方向为GIS技术、数据挖掘。E-mail:467152455@qq.com

收稿日期: 2013-05-27

  修回日期: 2013-09-25

  网络出版日期: 2014-03-10

基金资助

国家自然科学基金项目(31071700);国家公益性行业(气象)科研项目(GYHY201306044、GYHY201306059);海口市重点科技计划项目(2012-027)。

A Cumulative Offset Based Real-time Compression of Line Vector Data

Expand
  • 1. Intelligent Information Processing Laboratory, Chengdu University of Information Technology, Chengdu 610225, China;
    2. HAINAN YEDAO GROUP CO. Ltd., Haikou 570100, China

Received date: 2013-05-27

  Revised date: 2013-09-25

  Online published: 2014-03-10

摘要

针对线路矢量数据实时采集和同步压缩应用需求,本文提出具有高压缩率、低失真度特点的累积偏移实时压缩算法(CORC Algorithm)。算法突出对弯曲极值点和距离偏移的感知,创新性地提出累积变向点和累积变向拐点的弯曲极值点探测方法,提出距离累积偏移临界点的线路偏移快速判断方法,从而有效提高算法对方向连续偏移的敏感度和对摇摆偏移的高压缩率,提高线路矢量数据实时压缩的高保真性。累积偏移实时压缩算法在高限差阈值情况下仍能有效发现各类弯曲极值点和距离累积偏移临界点,在O(N)时间复杂性和O(1)空间复杂性下取得高压缩率、低失真度的理想压缩效果,实现了线路采集的零延时同步压缩。应用定时、定距两种采集策略生成的线路矢量数据集,与垂距法(VD Algorithm)、分段道格拉斯-普克法(Subsection DP Algorithm)进行实时压缩性能实验对比,结果表明,累积偏移法作为实时压缩方法,与上述两种主流实时压缩算法相比,在压缩实时性、压缩率失真度平衡、限差阈值可控性3方面都具有明显的优越性。在同等压缩率情况下,累积偏移压缩算法失真度普遍降低达10%,且压缩率与失真度的平衡性受限差阈值取值和线路轨迹特征影响最小,可实现线路的定位采集、实时压缩、同步网络上传,在交通、旅游、探险搜救等领域的实时定位监控中具有广阔的应用前景。

本文引用格式

王飞, 曾燕, 赵小波, 刘胤田 . 基于累积偏移算法的线路矢量数据实时压缩[J]. 地球信息科学学报, 2014 , 16(2) : 173 -181 . DOI: 10.3724/SP.J.1047.2014.00173

Abstract

To satisfy the requirement of simultaneous compression along with real-time collection for line vector data, this work proposes an innovative algorithm with the characteristics of high compression rate and low distortion. Cumulative Offset Based Real-time Compression Algorithm (CORC-Algorithm) has outstanding performance in the perception of right direction and offset distance. CORC-Algorithm proposes fast discovery method of cumulative changeable point, cumulative changeable inflection point and cumulative offset distance critical point. The CORC-algorithm can also be efficient in discovering all types of bending extreme points and continuous offset extreme points even in the condition of high tolerance threshold. The algorithm has time complexity of O(N) and space complexity of O(1) when reducing compression distortion and completing the zero delay synchronization compression. By comparing with vertical distance algorithm and subsection Douglas Peucker compression algorithm, we focus on experiments by collecting line vector data at the timing and distance strategy with different tolerance threshold. The experiments show that CORC algorithm has great advantages in terms of real-time, compression and distortion by comparing with vertical distance algorithm and subsection Douglas Peucker compression algorithm. CORC-Algorithm can achieve the universal lower distortion under the same compression ratio. The maneuverability of CORC-Algorithm is effective and stable for having low effect of tolerance threshold. Because of its excellent performance in real-time compression, CORC-algorithm has a wide application in the real-time location monitoring field of traffic, tourism, adventure, rescue, and entertainment.

参考文献

[1] 王立胜,闵晓瑜,毕妤.一种面向移动用户的空间矢量数据压缩算法[J].控制理论与应用,2004,12(23):20-22.

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

[3] 陈飞翔.移动空间信息服务关键技术研究[D].北京:中国科学院遥感应用研究所,2006.

[4] 战伟宝.基于移动GIS/PDA空间数据无线通信关键技术研究[D].哈尔滨:哈尔滨理工大学,2008.

[5] 王进宝,刘正纲.曲线矢量数据压缩算法实现及评析[J].测绘与空间地理信息,2006,29(2):122-124.

[8] 余先川,张君兰,张立保.基于整数小波变换的空间矢量数据压缩方法[J].地球科学——中国地质大学学报,2011,36(2):381-385.

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

[10] 谢亦才,林渝淇,李岩.Douglas-Peucker算法在无拓扑矢量数据压缩中的新改进[J].计算机应用与软件,2010,27(1):141-144.

[11] 柯敏毅,王志国.移动GIS中的空间矢量数据压缩方法[J].地理空间信息,2007,5(1):24-26.

[12] 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. ACM, 1994.

[13] Agarwal P K, Har-Peled S, Mustafa N H, et al. Near-linear time approximation Aagorithms for curve simplification[J]. Algorithmica, 2005(42):203-219.

[14] Wu S T, Marque M R G. A non-self-intersection Douglas-Peucker algorithm[C]. IEEE Proceedings of the XVI Brazilian Symposiumon Computer Graphics and Image Processing (SIBGRAPI'03), 2003.

[15] 陈飞翔,于文洋,李华.基于GA 的矢量数据压缩优化算法[J].计算机工程与应用,2007,43(34):185-187.

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

[17] 陈飞翔,李华,于文洋.基于多实体的矢量数据压缩改进算法[J].计算机工程与应用,2008,44(19):200-202.

[18] Li Y J, Zhong E S. A new vector data compression approach for WebGIS[J]. Geo-spatial Information Science,2011,14(1):48-53.

[19] 刘可晶.一种改进的矢量曲线数据压缩算法[J].甘肃科学学报,2005,17(3):112-115.

[20] 翟战强,管华,王双婷.一种快速空间矢量数据压缩方法[J].计算机工程,2003,29(2):94-95.

[21] 马劲松,沈捷,徐寿成,等.利用Douglas-Peucker并行算法在多核处理器上实时综合地图要素[J].武汉大学学报·信息科学版,2011,36(12):1423-1426.

文章导航

/