Journal of Geo-information Science >
A Cumulative Offset Based Real-time Compression of Line Vector Data
Received date: 2013-05-27
Revised date: 2013-09-25
Online published: 2014-03-10
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.
WANG Fei, ZENG Yan, ZHAO Xiaobo, LIU Yintian . A Cumulative Offset Based Real-time Compression of Line Vector Data[J]. Journal of Geo-information Science, 2014 , 16(2) : 173 -181 . DOI: 10.3724/SP.J.1047.2014.00173
[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.
/
| 〈 |
|
〉 |