|Table of Contents|

Compression algorithm of ship trajectory based on online directed acyclic graph(PDF)

《交通运输工程学报》[ISSN:1671-1637/CN:61-1369/U]

Issue:
2020年04期
Page:
227-236
Research Field:
交通信息工程及控制
Publishing date:

Info

Title:
Compression algorithm of ship trajectory based on online directed acyclic graph
Author(s):
ZHANG Yuan-qiang1; 2; 3;  SHI Guo-you1;  LI Song2
1. Navigation College, Dalian Maritime University, Dalian 116026, Liaoning, China; 2. Faculty of Maritime and Transportation, Ningbo University, Ningbo 315211, Zhejiang, China; 3. Australian Maritime College, University of Tasmania, Launceston TAS 7250, Tasmania, Australia
Keywords:
ship automatic identification system;  ship trajectory;  trajectory compression;  compression path tree;  compression ratio;  average synchronized Euclidean distance error
PACS:
U675.7
DOI:
10.19818/j.cnki.1671-1637.2020.04.019
Abstract:
To solve the problem of ship trajectory data compression, an online ship trajectory compression algorithm was proposed. An estimation method of multiple sliding reckoning the ship position was used to clean the ship trajectory, and the online directed acyclic graph was used to build the compression path tree on the clean trajectory and to output the sampling points. The Hash table was used to manage the trajectory queue and path tree in memory in order to improve their query speeds. To verify the effect of the proposed algorithm, the compression times and errors of real ship automatic identification system, direction-preserving algorithm and Douglas-Peucker algorithm were compared, and the original trajectory, clean trajectory and compression trajectory were analyzed by the visual method. Experiment result shows that in terms of the compression time, the compression times of direction-preserving algorithm and Douglas-Puck algorithm are about 1.1 and 1.3 times of the proposed algorithm, respectively, indicating that the execution time of the proposed algorithm is shorter than the other two algorithms. The proposed algorithm retains the time information in the compression process, and the average synchronized Euclidean distance error is less than 10 m at any compression rate. The maximum synchronized Euclidean distance error is only 127 m when the compression ratio is 1%, while the average synchronized Euclidean distance errors and the maximum synchronized Euclidean distance errors of the other two algorithms can not be controlled, and change randomly. In terms of perpendicular distance error, both the proposed algorithm and Douglas-Puck algorithm can guarantee that the perpendicular distance errors less than 20 m when the compression rate is not less than 5%, while the perpendicular distance error of direction-preserving algorithm changes randomly. In terms of display effect, the proposed algorithm can effectively remove the noise points of trajectory, and the compression trajectory can better represent the macroscopic traffic flow of original trajectory. Therefore, the proposed algorithm can preserve the shape and time informations of original trajectory more efficiently. 1 tab, 15 figs, 30 refs.

References:

[1] HAMMOND T R, PETERS D J. Estimating AIS coverage from received transmissions[J]. The Journal of Navigation, 2012, 65(3): 409-425.
[2] SHENG Pan, YIN Jing-bo. Extracting shipping route patterns by trajectory clustering model based on automatic identification system data[J]. Sustainability, 2018, 10(7): 1-13.
[3] 牟军敏,陈鹏飞,贺益雄,等.船舶AIS-轨迹快速自适应谱聚类算法[J].哈尔滨工程大学学报,2018,39(3):428-432.
MOU Jun-min, CHEN Peng-fei, HE Yi-xiong, et al. Fast self-tuning spectral clustering algorithm for AIS ship trajectory[J]. Journal of Harbin Engineering University, 2018, 39(3): 428-432.(in Chinese)
[4] ZHAO Liang-bin, SHI Guo-you. A trajectory clustering method based on Douglas-Peucker compression and density for marine traffic pattern recognition[J]. Ocean Engineering, 2019, 172: 456-467.
[5] ZHANG Shu-kai, SHI Guo-you, LIU Zheng-jiang, et al. Data-driven based automatic maritime routing from massive AIS trajectories in the face of disparity[J]. Ocean Engineering, 2018, 155: 240-250.
[6] LI Song, ZHOU Jiang-hua, ZHANG Yuan-qiang. Research of vessel traffic safety in ship routeing precautionary areas based on navigational traffic conflict technique[J]. The Journal of Navigation, 2015, 68(3): 589-601.
[7] PALLOTTA G, VESPE M, BRYAN K. Vessel pattern knowledge discovery from AIS data: a framework for anomaly detection and route prediction[J]. Entropy, 2013, 15(6): 2218-2245.
[8] ZHAO Liang-bin, SHI Guo-you. A method for simplifying ship trajectory based on improved Douglas-Peucker algorithm[J]. Ocean Engineering, 2018, 166: 37-46.
[9] ZHU Fei-xiang, MIAO Li-ming, LIU Wen. Research on vessel trajectory multi-dimensional compression algorithm based on Douglas-Peucker theory[J]. Applied Mechanics and Materials, 2014, 694: 59-62.
[10] 张树凯,刘正江,张显库,等.基于Douglas-Peucker算法的船舶AIS航迹数据压缩[J].哈尔滨工程大学学报,2015,36(5):595-599.
ZHANG Shu-kai, LIU Zheng-jiang, ZHANG Xian-ku, et al. A method for AIS track data compression based on Douglas-Peucker algorithm[J]. Journal of Harbin Engineering University, 2015, 36(5): 595-599.(in Chinese)
[11] ZHANG Shu-kai, LIU Zheng-jiang, CAI Yao, et al. AIS trajectories simplification and threshold determination[J]. The Journal of Navigation, 2016, 69(4): 729-744.
[12] VRIES G K D D, SOMEREN M V. Machine learning for vessel trajectories using compression, alignments and domain knowledge[J]. Expert Systems with Applications, 2012, 39(18): 13426-13439.
[13] SÁNCHEZ-HERES L F. Simplification and event identification for AIS trajectories: the equivalent passage plan method[J]. The Journal of Navigation, 2019, 72: 307-320.
[14] SINGH A K, AGGARWAL V, SAXENA P, et al. Performance analysis of trajectory compression algorithms on marine surveillance data[C]∥IEEE. 2017 International Conference on Advances in Computing, Communications and Informatics. New York: IEEE, 2017: 1074-1079.
[15] ZHENG Yu.Trajectory data mining: an overview[J]. ACM Transactions on Intelligent Systems and Technology, 2015, 6(3): 1-41.
[16] SUN Peng-hui, XIA Shi-xiong, YUAN Guan, et al. An overview of moving object trajectory compression algorithms[J]. Mathematical Problems in Engineering, 2016, 2016: 1-13.
[17] 高 邈,史国友,李伟峰.改进的Sliding Window在线船舶AIS轨迹数据压缩算法[J].交通运输工程学报,2018,18(3):218-227.
GAO Miao, SHI Guo-you, LI Wei-feng. Online compression algorithm of AIS trajectory data based on improved sliding window[J]. Journal of Traffic and Transportation Engineering, 2018, 18(3): 218-227.(in Chinese)
[18] GAO Miao, SHI Guo-you. Ship spatio temporal key feature point online extraction based on AIS multi-sensor data using an improved sliding window algorithm[J]. Sensors, 2019, 19: 1-17.
[19] KEOGH E,CHU S, HART D, et al. An online algorithm for segmenting time series[C]∥IEEE. 2001 IEEE International Conference on Date Ming. New York: IEEE, 2001: 289-296.
[20] MERATNIA N, DE BY R A. Spatio temporal compression techniques for moving point objects[C]∥Springer. Advances in Database Technology—EDBT 2004. Berlin: Springer, 2004: 765-782.
[21] MENG Qing-bin, YU Xiao-qiang, YAO Chun-long, et al. Improvement of OPW-TR algorithm for compressing GPS trajectory data[J]. Journal of Information Processing Systems, 2017, 13(3): 533-545.
[22] MUCKELL J, OLSEN P W J, HWANG J H, et al. Compression of trajectory data: a comprehensive evaluation and new approach[J]. Geoinformatica, 2014, 18(3): 435-460.
[23] CAO Wei-quan, LI Yun-zhao. DOTS: an online and near-optimal trajectory simplification algorithm[J]. Journal of Systems and Software, 2017, 126: 34-44.
[24] POTAMIAS M, PATROUMPAS K, SELLIS T.Sampling trajectory streams with spatiotemporal criteria[C]∥IEEE. 18th International Conference on Scientific and Statistical Database Management. New York: IEEE, 2006: 275-284.
[25] LONG C, WONG R C W, JAGADISH H V. Direction-preserving trajectory simplification[J]. Proceedings of the VLDB Endowment, 2013, 6(10): 949-960.
[26] DENG Ze, HAN Wei, WANG Li-zhe, et al. An efficient online direction-preserving compression approach for trajectory streaming data[J]. Future Generation Computer Systems, 2017, 68: 150-162.
[27] CHEN Min-jie, XU Man-tao, FRÄNTI P. A fast O(N) multiresolution polygonal approximation algorithm for GPS trajectory simplification[J]. IEEE Tansactions on Image Processing, 2012, 21(5): 2770-2785.
[28] WU Lin, XU Yong-jun, WANG Qi, et al. Mapping global shipping density from AIS data[J]. The Journal of Navigation, 2017, 70(1): 67-81.
[29] ZHAO Liang-bin, SHI Guo-you, YANG Jia-xuan. Ship trajectories pre-processing based on AIS data[J]. The Journal of Navigation, 2018, 71(5): 1210-1230.
[30] DOUGLAS D H, PEUCKER T K. Algorithm for the reduction of the number of points required to represent a digital line or its caricature[J]. Cartographer, 1973, 10: 112-122.

Memo

Memo:
-
Last Update: 2020-08-20