Online compression algorithm of AIS trajectory data based on improved sliding window
-
摘要: 分析了船舶AIS数据的时间序列特征与船舶操纵特性, 提出了改进的Sliding Window在线压缩算法; 计算了277艘船舶总计1 026 408个坐标点的AIS轨迹数据, 确定了合适的压缩阈值, 分析了距离阈值与角度阈值对算法压缩率的敏感程度; 根据压缩率图像的阶跃点, 推荐了高、中、低3个档位的距离阈值和1个角度阈值, 对比了Douglas-Peucker算法和改进Sliding Window算法的压缩率与压缩效率。试验结果表明: 随着压缩率的提高, 压缩后所剩下的点越来越少, 数据所保留下来的有用信息也越来越少; 压缩率与距离阈值、角度阈值均呈正比; 经量纲为1化处理的高、中、低档位压缩距离阈值分别为43%、38%、33%船长; 距离阈值为130m时, 角度阈值超过9°后压缩率平稳, 所以推荐角度阈值为9°, 与《海港总体设计规范》 (JTS 165—2013) 中风流压差角8°相接近; 随着距离阈值的增大, Douglas-Peucker算法和改进Sliding Window算法压缩率趋于相近, 当距离阈值为120 m时, Douglas-Peucker算法压缩率仅比改进Sliding Window算法高1.74%;在5种距离阈值的情况下, Douglas-Peucker算法运行所用的平均时间是改进Sliding Window算法的5.39倍; 随着数据量的增大, 2种算法压缩效率的差距更加明显。可见, 改进的Sliding Window算法能在降低压缩风险的同时大幅提高压缩效率, 可以在数据持续更新的状态下一直保持压缩状态, 与普通压缩模式相比, 系统所占用的资源更少, 处理效率更高, 可用于船舶轨迹数据处理、电子海图显示与对船舶关键行为特征提取等方面。Abstract: The time series characteristics of ship AIS data and ship maneuvering characteristics were analyzed. An improved sliding window online compression algorithm was proposed. The AIS trajectory data from 277 ships with a total of 1 026 408 coordinate points were calculated, and the appropriate compression thresholds were determined. The sensitivities of distance and angle thresholds to the compression rate of the algorithm were analyzed. According to the step points of the compression rate image, three distance thresholds of high, middle, and low levels, and one angle threshold were recommended. The compression rate and efficiency of the DouglasPeucker algorithm and improved sliding window algorithm were compared. Experimental result shows that with the improvement of the compression rate, the remaining points after compression and the useful information retained by the data become less. The compression rate is positively proportional to the distance threshold and angle threshold. The dimensionless compression distance thresholds of high, middle, and low levels are 43%, 38% and 33% of ship length, respectively. When the distance threshold is 130 mand the angle threshold is more than 9°, the compression rate becomes stable, so the recommend angle threshold is 9°, which is similar to 8°that is the pressure difference angle in Design Code of General Layout for Sea Ports (JTS 165—2013). With an increase in the distance threshold, the compression rates of the Douglas-Peucker and improved sliding window algorithms tend to be similar. When the distance threshold is 120 m, the compression rate of the Douglas-Peucker algorithm is only 1.74% higher than that of the improved sliding window algorithm. In the case of five distance thresholds, the average operating time of the Douglas-Peucker algorithm is 5.39 times that of the improved sliding window algorithm. With the increase of data volume, the compression efficiency difference between the two algorithms is more obvious. The improved sliding window algorithm can reduce the risk of data compression, simultaneously showing a substantial improvement in the efficiency of data compression, and the data can keep compression states under the continuously updated condition. Compared to the ordinary compression mode, the improved sliding window algorithm occupies less system resources, has higher processing efficiency, and can be applied to ship trajectory data processing, ECDIS display, and extraction of key behavioural features of ships.
-
图 2 改进的Sliding Window压缩算法流程
Figure 2. Flow of improved sliding window compression algorithm
图 8 压缩率与距离阈值、角度阈值的三维关系
Figure 8. 3Drelationship between compression ratio and distance threshold and angle threshold
图 9 距离阈值为130m时角度阈值与压缩率之间的关系
Figure 9. Relationship between angle threshold and compression ratio when distance threshold is 130m
图 10 角度阈值为15°时距离阈值与压缩率之间的关系
Figure 10. Relationship between distance threshold and compression ratio when angle threshold is 15°
图 13 采用改进Sliding Window算法压缩的AIS轨迹
Figure 13. AIS trajectory compressed by improved sliding window algorithm
图 14 采用Douglas-Peucker算法压缩后AIS轨迹
Figure 14. AIS trajectory compressed by Douglas-Peucker algorithm
-
[1] 魏照坤, 周康, 魏明, 等. 基于AIS数据的船舶运动模式识别与应用[J]. 上海海事大学学报, 2016, 37 (2): 17-22, 71. https://www.cnki.com.cn/Article/CJFDTOTAL-SHHY201602005.htmWEI Zhao-kun, ZHOU Kang, WEI Ming, et al. Ship motion pattern recognition and application based on AIS data[J]. Journal of Shanghai Maritime University, 2016, 37 (2): 17-22, 71. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-SHHY201602005.htm [2] 任亚磊. 基于AIS数据的船舶会遇特征研究[D]. 武汉: 武汉理工大学, 2013.REN Ya-lei. Study on ship encounters using AIS data[D]. Wuhan: Wuhan University of Technology, 2013. (in Chinese). [3] 江俊文, 王晓玲. 轨迹数据压缩综述[J]. 华东师范大学学报: 自然科学版, 2015 (5): 61-76. doi: 10.3969/j.issn.1000-5641.2015.05.005JIANG Jun-wen, WANG Xiao-ling. Review on trajectory data compression[J]. Journal of East China Normal University: Natural Science, 2015 (5): 61-76. (in Chinese). doi: 10.3969/j.issn.1000-5641.2015.05.005 [4] 张树凯, 刘正江, 张显库, 等. 基于Douglas-Peucker算法的船舶AIS航迹数据压缩[J]. 哈尔滨工程大学学报, 2015, 36 (5): 595-599. https://www.cnki.com.cn/Article/CJFDTOTAL-HEBG201505002.htmZHANG Shu-kai, LIU Zheng-jiang, ZHANG Xian-ku, et al. A method for AIS track data compression based on DouglasPeucker algorithm[J]. Journal of Harbin Engineering University, 2015, 36 (5): 595-599. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HEBG201505002.htm [5] 徐凯, 邱家瑜, 李燕. 一种加入时间维的船舶轨迹高效离线压缩算法研究[J]. 计算机科学, 2017, 44 (11A): 498-502. doi: 10.11896/j.issn.1002-137X.2017.11A.106XU Kai, QIU Jia-yu, LI Yan. Offline efficient compression algorithm for AIS data retains time elapsing dimension[J]. Computer Science, 2017, 44 (11A): 498-502. (in Chinese). doi: 10.11896/j.issn.1002-137X.2017.11A.106 [6] MERATNIA N, DE BY R A. Spatiotemporal compression techniques for moving point objects[J]. 2004, 2992: 765-782. [7] KELLARIS G, PELEKIS N, THEODORIDIS Y. Trajectory Compression under Network Constraints[J]. Lecture Notes in Computer Science, 2009, 5644: 392-398. [8] LU Cheng-jiao, CHEN Feng, XU Yong-zhi, et al. A trajectory compression algorithm based on non-uniform quantization[C]∥IEEE. 12th International Conference on Fuzzy Systems and Knowledge Discovery. New York: IEEE, 2015: 2469-2474. [9] DUTTA S, BHATTACHERJEE S, NARANG A. Towards"intelligent compression"in streams: a biased reservoir sampling based Bloom filter approach[C]∥ACM. 15th International Conference on Extending Database Technology, New York: ACM, 2012: 425-426. [10] 张达夫, 张昕明. 基于时空特性的GPS轨迹数据压缩算法[J]. 交通信息与安全, 2013, 31 (3): 6-9. doi: 10.3963/j.issn.1674-4861.2013.03.002ZHANG Da-fu, ZHANG Xin-ming. A spatiotemporal compression algorithm for GPS trajectory data[J]. Journal of Transport Information and Safety, 2013, 31 (3): 6-9. (in Chinese). doi: 10.3963/j.issn.1674-4861.2013.03.002 [11] JI Y, LIU H, LIU X, et al. A comparison of road-networkconstrained trajectory compression methods[C]∥IEEE. 22nd IEEE International Conference on Parallel and Distributed Systems. New York: IEEE, 2016: 256-263. [12] HAN Yun-heng, SUN Wei-wei, ZHENG Bai-hua. Compress: a comprehensive framework of trajectory compression in road networks[J]. ACM Transactions on Database Systems, 2017, 42 (2): 1-49. [13] 朱猛, 孙剑. 基于MBR的GPS轨迹数据压缩算法[J]. 信阳农林学院学报, 2016, 26 (1): 117-120, 123. https://www.cnki.com.cn/Article/CJFDTOTAL-XYNG201601037.htmZHU Meng, SUN Jian. GPS trajectory data compression algorithm based on MBR[J]. Journal of Xinyang College of Agriculture and Forestry, 2016, 26 (1): 117-120, 123. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XYNG201601037.htm [14] 吴家皋, 夏轩, 刘林峰. 基于MapReduce的轨迹压缩并行化方法[J]. 计算机应用, 2017, 37 (5): 1282-1286, 1330. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY201705011.htmWU Jia-gao, XIA Xuan, LIU Lin-feng. Parallel trajectory compression method based on MapReduce[J]. Journal of Computer Application, 2017, 37 (5): 1282-1286, 1330. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY201705011.htm [15] MUCKELL J, PATIL V, PING Fan. SQUISH: an online approach for GPS trajectory compression[C]∥ACM. 2nd International Conference on Computing for Geospatial Research and Applications. New York: ACM, 2011: 13-20. [16] 李浩, 黄艳, 马岩蔚. 基于三次多项式曲线的轨迹平滑压缩算法[J]. 组合机床与自动化加工技术, 2016 (6): 12-15. https://www.cnki.com.cn/Article/CJFDTOTAL-ZHJC201606004.htmLI Hao, HUANG Yan, MA Yan-wei. The smooth compression algorithm based on cubic polynomial curve[J]. Modular Machine Tooland Automatic Manufacturing Technique, 2016 (6): 12-15. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZHJC201606004.htm [17] 樊庆富, 张磊, 刘磊军, 等. 基于偏移量计算的在线GPS轨迹数据压缩[J]. 计算机工程与应用, 2017, 53 (8): 254-259. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201708046.htmFAN Qing-fu, ZHANG Lei, LIU Lei-jun, et al. Online GPS trajectory data compression based on offset calculation[J]. Computer Engineering and Applications, 2017, 53 (8): 254-259. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201708046.htm [18] HERSHKOVITS Y, ZIV J. On sliding window universal data compression with limited memory[J]. IEEE Transactions on Information Theory, 1998, 44 (1): 66-78. doi: 10.1109/18.650988 [19] CHEN Ye-hong, PARK P S, GAO Qian. An enhanced modelbased tracking algorithm with dynamic adjustment of learning parameters according to online performance evaluation[J]. Indian Journal of Science Technology, 2015, 8 (26): 1-6. [20] 丁振国. 船舶AIS数据云存储系统研究[J]. 浙江交通职业技术学院学报, 2016, 17 (1): 37-42. https://www.cnki.com.cn/Article/CJFDTOTAL-ZJZJ201601009.htmDING Zhen-guo. A Study on the cloud storage system of ship's AIS data[J]. Journal of Zhejiang Institute of Communications, 2016, 17 (1): 37-42. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZJZJ201601009.htm [21] 吴家皋, 刘敏, 韦光, 等. 一种改进的滑动窗口轨迹数据压缩算法[J]. 计算机技术与发展, 2015, 25 (12): 47-51. https://www.cnki.com.cn/Article/CJFDTOTAL-WJFZ201512011.htmWU Jia-gao, LIU Min, WEI Guang, et al. An improved trajectory data compression algorithm ofsliding window[J]. Computer Technology and Development, 2015, 25 (12): 47-51. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-WJFZ201512011.htm [22] 赵友桥, 王坚, 路松峰, 等. 一种后缀数组与滑动窗口结合的压缩算法[J]. 计算机工程与应用, 2012, 48 (15): 59-62. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201215014.htmZHAO You-qiao, WANG Jian, LU Song-feng, et al. A sliding window compression algorithm based on suffix array[J]. Computer Engineering and Applications, 2012, 48 (15): 59-62. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201215014.htm [23] KEOGH E, CHU S, HART D, et al. An online algorithm for segmenting time series[C]∥IEEE. 2001IEEE International Conference on Data Mining. New York: IEEE, 2001: 289-296. [24] INENAGA S, SHINOHARA A, TAKEDA M, et al. Compact directed acyclic word graphs for asliding window[J]. Lecture Notes in Computer Science, 2002, 2476: 310-324. [25] 王栩, 李建中, 王伟平. 基于滑动窗口的数据流压缩技术及连续查询处理方法[J]. 计算机研究与发展, 2004, 41 (10): 1639-1644. https://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ200410005.htmWANG Xu, LI Jian-zhong, WANG Wei-ping. Processing compressedsliding window continuous queries over data streams[J]. Journal of computer research and development, 2004, 41 (10): 1639-1644. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ200410005.htm [26] BELYAEV E, FORCHHAMMER S, LIU Kai. An adaptive multialphabet arithmetic coding based on generalized virtual sliding window[J]. IEEE Signal Processing Letters, 2017, 24 (7): 1034-1038. [27] 史国友, 朱公志, 王玉梅, 等. 恒向线主题直接正反解的高精度算法[J]. 大连海事大学学报, 2009, 35 (2): 5-9. https://www.cnki.com.cn/Article/CJFDTOTAL-DLHS200902002.htmSHI Guo-you, ZHU Gong-zhi, WANG Yu-mei, et al. High accurate algorithm for forward and inverse solution of rhumb line's problem[J]. Journal of Dalian Maritime University, 2009, 35 (2): 5-9. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-DLHS200902002.htm [28] 毕晓君, 樊松. 基于突变理论的图像边缘检测技术[J]. 应用科技, 2008, 35 (6): 1-6. https://www.cnki.com.cn/Article/CJFDTOTAL-YYKJ200806002.htmBI Xiao-jun, FAN Song. Edge detection based on catastrophic theory[J]. Applied Science and Technology, 2008, 35 (6): 1-6. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-YYKJ200806002.htm -
下载:
点击查看大图
图(14) / 表(2)
计量
- 文章访问数: 733
- HTML全文浏览量: 197
- PDF下载量: 887
- 被引次数: 0
