地球信息科学学报 ›› 2014, Vol. 16 ›› Issue (2): 173-181.doi: 10.3724/SP.J.1047.2014.00173

• 地球信息科学理论与方法 • 上一篇    下一篇

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

王飞1, 曾燕1, 赵小波2, 刘胤田1   

  1. 1. 成都信息工程学院智能信息处理实验室, 成都 610225;
    2. 海南椰岛(集团)股份有限公司, 海口 570100
  • 收稿日期:2013-05-27 修回日期:2013-09-25 出版日期:2014-03-10 发布日期:2014-03-10
  • 通讯作者: 刘胤田(1972- ),男,四川隆昌人,教授,研究方向为智能计算、信息集成与可视化。E-mail:liuyintian@cuit.edu.cn E-mail:liuyintian@cuit.edu.cn
  • 作者简介:王 飞(1989- ),男,江苏灌云人,硕士生,研究方向为GIS技术、数据挖掘。E-mail:467152455@qq.com
  • 基金资助:

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

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

WANG Fei1, ZENG Yan1, ZHAO Xiaobo2, LIU Yintian1   

  1. 1. Intelligent Information Processing Laboratory, Chengdu University of Information Technology, Chengdu 610225, China;
    2. HAINAN YEDAO GROUP CO. Ltd., Haikou 570100, China
  • Received:2013-05-27 Revised:2013-09-25 Online:2014-03-10 Published:2014-03-10
  • Contact: 10.3724/SP.J.1047.2014.00173 E-mail:liuyintian@cuit.edu.cn

摘要:

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

关键词: GPS, 弯曲极值点, 移动定位, 线路矢量数据压缩, 累积偏移实时压缩

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.

Key words: GPS, running fix, cumulative offset real-time compression, bending extreme points, line vector data compression