-
摘要: 为了解决船舶轨迹数据的压缩问题, 提出了一种船舶轨迹在线压缩算法; 使用多次滑动推算船位判断方法清洗船舶轨迹, 使用在线有向无环图在干净轨迹上建立压缩路径树并输出采样点; 为了提高轨迹队列和路径树在内存中的查询速度, 使用哈希表对其进行管理; 为了验证提出算法的效果, 比较了真实船舶自动识别系统数据与方向保留算法、道格拉斯-普克算法的压缩时间和误差, 采用可视化方法分析了原始轨迹、清洗轨迹和压缩轨迹。试验结果表明: 在压缩时间方面, 方向保留算法和道格拉斯-普克算法的压缩时间分别约为提出算法的1.1、1.3倍, 说明提出的算法比其他2种算法的处理时间更短; 提出的算法在压缩过程中保留了时间信息, 平均同步欧氏距离误差在任何压缩率下都能保持在10 m以下, 最大同步欧氏距离误差在压缩率为1%时仅有127 m, 而其他2种算法的平均同步欧氏距离误差和最大同步欧氏距离误差不受控制, 会随机变化; 在垂直距离误差方面, 提出的算法与道格拉斯-普克算法在压缩率不小于5%的条件下, 都能保证垂直距离误差小于20 m, 而方向保留算法的垂直距离误差会随机变化; 在显示效果方面, 提出的算法能有效清除轨迹噪声点, 压缩轨迹能够较好地代表原始轨迹的宏观交通流情况。可见, 提出的算法能更高效地保留原始轨迹的形状和时间信息。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.
-
图 15 具有相同最大误差的压缩效果比较
Figure 15. Comparison of compression effects with same maximum error
表 1 不同压缩率的最大误差
Table 1. Maximum errors of different compression ratios
压缩率/% 1 10 30 60 90 最大误差/m DPTS算法 100 194 75 038 35 750 9 436 297 DP算法 30 523 24 614 7 323 4 795 866 本文算法 127 25 20 17 15 
下载: 导出CSV
-
[1] HAMMOND T R, PETERS D J. Estimating AIS coverage from received transmissions[J]. The Journal of Navigation, 2012, 65(3): 409-425. doi: 10.1017/S0373463312000057 [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. https://www.cnki.com.cn/Article/CJFDTOTAL-HEBG201803005.htmMOU 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). https://www.cnki.com.cn/Article/CJFDTOTAL-HEBG201803005.htm [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. doi: 10.1016/j.oceaneng.2018.12.019 [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. doi: 10.1016/j.oceaneng.2018.02.060 [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. doi: 10.1017/S0373463314000939 [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. doi: 10.1016/j.oceaneng.2018.08.005 [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. doi: 10.4028/www.scientific.net/AMM.694.59 [10] 张树凯, 刘正江, 张显库, 等. 基于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 Douglas-Peucker algorithm[J]. Journal of Harbin Engineering University, 2015, 36(5): 595-599. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HEBG201505002.htm [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. doi: 10.1017/S0373463315000831 [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. doi: 10.1016/j.eswa.2012.05.060 [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. doi: 10.1017/S037346331800067X [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. doi: 10.3969/j.issn.1671-1637.2018.03.023GAO 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). doi: 10.3969/j.issn.1671-1637.2018.03.023 [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. doi: 10.1109/JSEN.2019.2912688 [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. doi: 10.1007/s10707-013-0184-0 [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. doi: 10.1016/j.jss.2017.01.003 [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. doi: 10.14778/2536206.2536221 [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. doi: 10.1016/j.future.2016.09.019 [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. -
点击查看大图
图(15) / 表(1)
计量
- 文章访问数: 729
- HTML全文浏览量: 183
- PDF下载量: 723
- 被引次数: 0
