基于时间比率-航速-航向的船舶轨迹压缩方法

刘畅; 曹鲁芳; 杨雨露; 林彬; 张仕泽

doi:10.19818/j.cnki.1671-1637.2025.01.012

基于时间比率-航速-航向的船舶轨迹压缩方法

doi: 10.19818/j.cnki.1671-1637.2025.01.012

大连海事大学信息科学技术学院，辽宁大连 116026

基金项目:

国家自然科学基金项目 51939001

国家自然科学基金项目 62371085

中央高校基本科研业务费专项资金项目 3132023514

辽宁省教育厅高校基本科研项目 LJ212410151022

辽宁省教育厅高校基本科研项目 LJ212410151026

详细信息

作者简介:
刘畅(1976-)，女，辽宁大连人，大连海事大学副教授，工学博士，从事智能交通系统研究

中图分类号: U675.7
计量
- 文章访问数: 16
- HTML全文浏览量: 20
- PDF下载量: 6
- 被引次数: 0
出版历程
- 收稿日期: 2024-01-10
- 刊出日期: 2025-02-25

Ship trajectory compression method based on time ratio-speed-heading

School of Information Science and Technology, Dalian Maritime University, Dalian 116026, Liaoning, China

Funds:

National Natural Science Foundation of China 51939001

National Natural Science Foundation of China 62371085

Fundamental Research Funds for the Central Universities 3132023514

University Basic Scientific Research Project of Liaoning Provincial Department of Education LJ212410151022

University Basic Scientific Research Project of Liaoning Provincial Department of Education LJ212410151026

More Information

Corresponding author: LIU Chang(1976-), female, associate professor, PhD, liuchang@dlmu.edu.cn

Article Text (Baidu Translation)

摘要

摘要: 考虑船舶航迹中包含的时间、位置、航速与航向等信息，提出一种全面考虑时空运动特性的船舶轨迹压缩方法；针对船舶自动识别系统(AIS)数据中的对地航速和对地航向分别提出航速及航向压缩算法以提取轨迹运动数据；为保留时间信息和空间数据，引入时间比率算法；通过综合这3种算法，提出时间比率-航速-航向(TSH)压缩算法，并根据压缩率和长度损失率实现了TSH算法参数的自适应确定；为验证方法的有效性，以威海、老铁山和长江水域的AIS数据作为研究对象，与道格拉斯-普克(DP)算法、改进DP算法进行对比。试验结果表明：TSH算法能够更精细地提取船舶轨迹的特征点，从而保留时空和运动行为，其中，单条轨迹压缩结果显示，经TSH算法压缩后的轨迹与原始轨迹之间的豪斯多夫距离比DP算法和改进DP算法分别降低1.6和1.1倍，多属性对称分割路径距离(MSSPD)较改进DP算法降低1.9倍，更好地保留了船舶轨迹的原始特征；整体轨迹压缩结果显示，对于威海、老铁山和长江水域，TSH算法在豪斯多夫距离上较DP算法分别降低2.1、2.2和1.7倍，较改进DP算法分别降低1.4、1.5和1.1倍，在MSSPD指标上分别低于改进DP算法1.3、1.1和1.2倍，进一步证明TSH压缩算法对船舶航行行为保留的有效性。经验证，所提出的TSH算法在较高压缩率下展现出更好的轨迹重构能力。
- 船舶自动识别系统 /
- 船舶轨迹数据 /
- AIS数据 /
- 船舶轨迹压缩 /
- TSH算法 /
- TS算法
Abstract: By considering that the ship trajectory contains information such as time, position, speed, and heading, a ship trajectory compression method considering the spatiotemporal motion characteristics was proposed. For the ground speed and ground heading in the automatic identification system (AIS) data of ships, the speed-based (SP) and the heading-based (HD) compression algorithms were proposed to extract the trajectory motion data. To retain the time information and spatial data, the time-ratio (TR) algorithm was introduced. By integrating these three types of algorithms, the time ratio-speed-heading (TSH) compression algorithm was proposed, and the parameters of the TSH algorithm were adaptively determined according to the compression rate and length loss rate. To verify the effectiveness of proposed method, the AIS data of Weihai, Laotieshan, and Yangtze River waters were used as research objects and compared with the Douglas-Peucker (DP) algorithm and the improved DP algorithm. Experimental results show that the characteristic points of the ship trajectory can be more finely extracted by the TSH algorithm, thereby retaining the spatiotemporal and motion behavior. Among them, the single trajectory compression results show that the Hausdorff distance between the trajectories compressed by the TSH algorithm and the original trajectory is 1.6 and 1.1 times lower than those of the DP algorithm and the improved DP algorithm, respectively, and the multi-attribute symmetric segmentation path distance (MSSPD) is 1.9 times lower than that of the improved DP algorithm, which better retains the original characteristics of the ship trajectory. The overall trajectory compression results show that for Weihai, Laotieshan, and Yangtze River waters, the TSH algorithm is 2.1, 2.2, and 1.7 times lower than the DP algorithm in the Hausdorff distance and 1.4, 1.5, and 1.1 times lower than the improved DP algorithm, respectively. In the MSSPD index, it is 1.3, 1.1, and 1.2 times lower than the improved DP algorithm, respectively, which further proves the effectiveness of the TSH compression algorithm in retaining the ship navigation behavior. It is verified that the proposed TSH algorithm shows better trajectory reconstruction ability at a higher compression rate.
- ship automatic identification system /
- ship trajectory data /
- AIS data /
- ship trajectory compression /
- TSH algorithm /
- TS algorithm

HTML全文

图 1 SP算法原理

Figure 1. Principle of SP algorithm

下载: 全尺寸图片幻灯片

图 2 船舶航向

Figure 2. Ship heading

下载: 全尺寸图片幻灯片

图 3 HD算法原理

Figure 3. Principle of HD algorithm

下载: 全尺寸图片幻灯片

图 4 TR算法原理

Figure 4. Principle of TR algorithm

下载: 全尺寸图片幻灯片

图 5 TSH算法原理

Figure 5. Principle of TSH algorithm

下载: 全尺寸图片幻灯片

图 6 不同阈值下TR算法的压缩结果

Figure 6. Compression results of TR algorithm under different thresholds

下载: 全尺寸图片幻灯片

图 7 不同阈值下SP算法压缩后轨迹

Figure 7. Compressed trajectories of SP algorithm under different thresholds

下载: 全尺寸图片幻灯片

图 8 不同阈值系数下HD算法的结果

Figure 8. Results of HD algorithm under different threshold coefficients

下载: 全尺寸图片幻灯片

图 9 TSH算法流程

Figure 9. Flow of TSH algorithm

下载: 全尺寸图片幻灯片

图 10 压缩前后船舶轨迹

Figure 10. Ship trajectories before and after compression

下载: 全尺寸图片幻灯片

图 11 威海水域船舶轨迹

Figure 11. Ship trajectories in Weihai waters

下载: 全尺寸图片幻灯片

图 12 老铁山水域船舶轨迹

Figure 12. Ship trajectories in Laotieshan waters

下载: 全尺寸图片幻灯片

图 13 长江水域船舶轨迹

Figure 13. Ship trajectories in Yangtze River waters

下载: 全尺寸图片幻灯片

表 1 原始AIS数据

Table 1. Original AIS data

轨迹点	纬度/(°)	经度/(°)	对地航速/kn	对地航向/(°)
1	36.572 8	122.827 9	13.4	11.3
2	36.574 3	122.828 3	13.4	11.5
3	36.575 8	122.828 6	13.4	11.8
				
32	37.099 2	122.864 8	13.8	3.1
33	37.100 7	122.864 7	13.7	359.4
34	37.102 2	122.864 9	13.8	3.3
35	37.103 8	122.864 8	13.7	3.0
				
40	37.114 4	122.865 2	13.6	359.4
41	37.115 9	122.865 1	13.6	3.2

下载: 导出CSV

表 2 压缩算法对比

Table 2. Comparison of compression algorithms

压缩算法	时间复杂度	空间复杂度	考虑时间	考虑形状	考虑航速	考虑航向
TSH	O(n²)	O(n)	是	是	是	是
DP	O(n²)	O(n)	否	是	否	否
改进DP	O[n²+nlog₂(n)]	O[n+log₂(n)]	否	是	是	是
SSTC	O[n²+nlog₂(n)]	>O(n)	是	是	是	是

下载: 导出CSV

表 3 不同阈值下SP算法的压缩率

Table 3. Compression rates of SP algorithm under different thresholds

阈值/kn	0.05	0.10	0.15	0.20
压缩率/%	92.61	97.83	99.13	99.13

下载: 导出CSV

表 4 不同阈值系数下HD算法的豪斯多夫距离

Table 4. Hausdorff distances of HD algorithm under different threshold coefficients

阈值系数	1	2	3	4	5	6	7	8
豪斯多夫距离/10⁶ m	1.404	1.404	1.404	1.404	1.404	2.107	2.107	2.107

下载: 导出CSV

表 5 不同压缩算法压缩结果对比

Table 5. Comparison of compression results of different compression algorithms

压缩算法	压缩率/%	豪斯多夫距离/m	MSSPD/m
TSH	83.48	7.022 4×10⁵	1.016 3×10⁷
DP	94.78	1.115 7×10⁶
改进DP	82.17	7.854 3×10⁵	1.929 0×10⁷

下载: 导出CSV

表 6 预处理后船舶轨迹数据

Table 6. Ship trajectory data after pretreatment

水域	数据量	过滤后AIS数据	修复后AIS数据
威海	船舶数/条	47	47
威海	轨迹点数/个	30 900	31 150
老铁山	船舶数/条	86	86
老铁山	轨迹点数/个	67 482	67 981
长江	船舶数/条	272	272
长江	轨迹点数/个	89 610	91 040

下载: 导出CSV

表 7 不同水域轨迹压缩结果

Table 7. Trajectory compression results in different waters

水域	压缩结果	TSH算法	DP算法	改进DP算法
威海	平均压缩率/%	85.49	96.10	84.77
	总豪斯多夫距离/10⁷ m	2.523 1	5.377 9	3.555 9
	总MSSPD/10⁸ m	2.982 2		3.865 2
老铁山	平均压缩率/%	92.19	98.60	91.68
	总豪斯多夫距离/10⁷ m	4.010 0	8.905 2	5.863 1
	总MSSPD/10⁸ m	4.486 1		4.972 0
长江	平均压缩率/%	86.67	96.81	80.39
	总豪斯多夫距离/10⁷ m	5.337 1	8.852 2	5.660 1
	总MSSPD/10⁹ m	2.345 3		2.859 3

下载: 导出CSV

参考文献(30)

[1]	ROBARDS M D, SILBER G K, ADAMS J D, et al. Conservation science and policy applications of the marine vessel automatic identification system (AIS)—a review[J]. Bulletin of Marine Science, 2016, 92(1): 75-103.
[2]	CHENG Liang, YAN Zhao-jin, XIAO Yi-jia, et al. Using big data to track marine oil transportation along the 21st-century Maritime Silk Road[J]. Science China Technological Sciences, 2019, 62(4): 677-686. doi: 10.1007/s11431-018-9335-1
[3]	ZHOU Zheng, ZHANG Ying-jian, YUAN Xiao-yu, et al. Compressing AIS trajectory data based on the multi-objective peak Douglas-Peucker algorithm[J]. IEEE Access, 2023, 11: 6802-6821. doi: 10.1109/ACCESS.2023.3234121
[4]	TANG Chun-hua, WANG Han, ZHAO Jia-huan, et al. A method for compressing AIS trajectory data based on the adaptive-threshold Douglas-Peucker algorithm[J]. Ocean Engineering, 2021, 232: 109041. doi: 10.1016/j.oceaneng.2021.109041
[5]	FERREIRA M D, CAMPBELL J, PURNEY E, et al. Assessing compression algorithms to improve the efficiency of clustering analysis on AIS vessel trajectories[J]. International Journal of Geographical Information Science, 2023, 37(3): 660-683. doi: 10.1080/13658816.2022.2163494
[6]	HUANG Yu, LI Yan, ZHANG Zhao-feng, et al. GPU- accelerated compression and visualization of large-scale vessel trajectories in maritime IoT industries[J]. IEEE Internet of Things Journal, 2020, 7(11): 10794-10812.
[7]	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.
[8]	RONG H, TEIXEIRA A P, GUEDES SOARES C. Data mining approach to shipping route characterization and anomaly detection based on AIS data[J]. Ocean Engineering, 2020, 198: 106936. doi: 10.1016/j.oceaneng.2020.106936
[9]	YAN Zhao-jin, HE Rong, RUAN Xiao-guang, et al. Footprints of fishing vessels in Chinese waters based on automatic identification system data[J]. Journal of Sea Research, 2022, 187: 102255. doi: 10.1016/j.seares.2022.102255
[10]	WANG Si-wen, LI Ying, XING Hu. A novel method for ship trajectory prediction in complex scenarios based on spatio-temporal features extraction of AIS data[J]. Ocean Engineering, 2023, 281: 114846. doi: 10.1016/j.oceaneng.2023.114846
[11]	LEICHSENRING Y E, BALDO F. An evaluation of compression algorithms applied to moving object trajectories[J]. International Journal of Geographical Information Science, 2020, 34(3): 539-558. doi: 10.1080/13658816.2019.1676430
[12]	高邈, 史国友, 李伟峰. 改进的Sliding Window在线船舶AIS轨迹数据压缩算法[J]. 交通运输工程学报, 2018, 18(3): 218-227. doi: 10.3969/j.issn.1671-1637.2018.03.023 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. doi: 10.3969/j.issn.1671-1637.2018.03.023
[13]	ZHONG Yan-ling, KONG Jin-ling, ZHANG Ju-qing, et al. A trajectory data compression algorithm based on spatio-temporal characteristics[J]. PeerJ Computer Science, 2022, 8: e1112. doi: 10.7717/peerj-cs.1112
[14]	ZHU Fei-xiang, MA Zhi-hong. Ship trajectory online compression algorithm considering handling patterns[J]. IEEE Access, 2021, 9: 70182-70191. doi: 10.1109/ACCESS.2021.3078642
[15]	DOUGLASD H, PEUCKER T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica: The International Journal for Geographic Information and Geovisualization, 1973, 10(2): 112-122. doi: 10.3138/FM57-6770-U75U-7727
[16]	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
[17]	ZHANG Shu-kai, LIU Zheng-jiang, CAI Yao, et al. AIS trajectories simplification and threshold determination[J]. Journal of Navigation, 2016, 69(4): 729-744.
[18]	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.
[19]	LIU Jing-xian, Li Huan-huan, YANG Zai-li, et al. Adaptive Douglas-Peucker algorithm with automatic thresholding for AIS-based vessel trajectory compression[J]. IEEE Access, 2019, 7: 150677-150692.
[20]	WEI Zhao-kun, XIE Xin-lian, ZHANG Xiao-ju. AIS trajectory simplification algorithm considering ship behaviours[J]. Ocean Engineering, 2020, 216: 108086.
[21]	刘海砚, 郭漩, 刘俊楠. 时空和语义结合的船舶轨迹数据压缩方法[J]. 测绘学报, 2023, 52(11): 1974-1982. LIU Hai-yan, GUO Xuan, LIU Jun-nan. A vessel trajectory data compression method combining spatio-temporal and semantic features[J]. Acta Geodaetica et Cartographica Sinica, 2023, 52(11): 1974-1982.
[22]	马杰, 何沐蓉, 贾承丰, 等. 基于上下文自编码的船舶行为语义表征[J]. 交通运输工程学报, 2022, 22(4): 334-347. doi: 10.19818/j.cnki.1671-1637.2022.04.026 MA Jie, HE Mu-rong, JIA Cheng-feng, et al. Semantic representation of ship behavior based on context autoencoder[J]. Journal of Traffic and Transportation Engineering, 2022, 22(4): 334-347. doi: 10.19818/j.cnki.1671-1637.2022.04.026
[23]	YAN Zhao-jin, XIAO Yi-jia, CHENG Liang, et al. Exploring AIS data for intelligent maritime routes extraction[J]. Applied Ocean Research, 2020, 101: 102271.
[24]	ZHANG Ming-yang, KUJALA P, MUSHARRAF M, et al. A machine learning method for the prediction of ship motion trajectories in real operational conditions[J]. Ocean Engineering, 2023, 283: 114905.
[25]	MERATNIA N, DE BY R A. Spatiotemporal compression techniques for moving point objects[C]//Springer. Advance in Database Technology—EDBT 2004. Berlin: Springer, 2004: 765-782.
[26]	HANSUDDHISUNTORN K, HORANONT T. Improvement of TD-TR algorithm for simplifying GPS trajectory data[C]//IEEE. 2019 First International Conference on Smart Technology and Urban Development. New York: IEEE, 2019: 11-16.
[27]	刘畅, 张仕泽, 李倍莹, 等. 考虑对地航速和航向的船舶典型轨迹提取方法[J]. 交通运输系统工程与信息, 2022, 22(6): 114-123. LIU Chang, ZHANG Shi-ze, LI Bei-ying, et al. Typical ship trajectory extraction method considering ground speed and heading[J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(6): 114-123.
[28]	LIN Xue-lian, MA Shuai, JIANG Jia-hao, et al. Error bounded line simplification algorithms for trajectory compression: an experimental evaluation[J]. ACM Transactions on Database Systems, 2021, 46(3): 11.
[29]	YANG Jia-xuan, LIU Yuan, MA Ling-qi, et al. Maritime traffic flow clustering analysis by density based trajectory clustering with noise[J]. Ocean Engineering, 2022, 249: 111001.
[30]	LIU Chang, ZHANG Shi-ze, CAO Lu-fang, et al. The identification of ship trajectories using multi-attribute compression and similarity metrics[J]. Journal of Marine Science and Engineering, 2023, 11(10): 2005.