Trajectory similarity measurement algorithm based on three-dimensional space area division

doi:10.11772/j.issn.1001-9081.2023010077

Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (1): 318-323.DOI: 10.11772/j.issn.1001-9081.2023010077

Special Issue: 前沿与综合应用

• Frontier and comprehensive applications • Previous Articles Next Articles

Trajectory similarity measurement algorithm based on three-dimensional space area division

Kai XU¹, Qikai GAO²(), Ming YIN¹, Jingjing TAN³

^1.Shanghai International Shipping Institute （Shanghai Maritime University），Shanghai 200082，China
^2.College of Transport and Communications，Shanghai Maritime University，Shanghai 201306，China
^3.Shanghai Jizhi Shipping Development Company Limited，Shanghai 200082，China

Received:2023-01-31 Revised:2023-05-11 Accepted:2023-05-12 Online:2023-06-06 Published:2024-01-10
Contact: Qikai GAO
About author:XU Kai， born in 1983， Ph. D.， senior engineer. His research interests include port-related big data， Internet+， internet of things， informationization， blockchain.
YIN Ming， born in 1979， Ph. D.， professor. His research interests include international shipping management， port management， port and shipping policies.
TAN Jingjing， born in 1989， M. S. His research interests include port and shipping big data processing， machine learning.
Supported by:
National Social Science Foundation of China(20BJY177)

基于三维空间面积划分的轨迹相似性度量算法

徐凯¹, 高琦凯²(), 殷明¹, 谭京京³

^1.上海国际航运研究中心(上海海事大学), 上海 200082
^2.上海海事大学交通运输学院, 上海 201306
^3.上海汲致航运发展有限公司, 上海 200082

通讯作者: 高琦凯
作者简介:徐凯（1983—），男，上海人，高级工程师，博士，CCF会员，主要研究方向：港航相关的大数据、互联网+、物联网、信息化、区块链；
殷明（1979—），男，上海人，教授，博士，主要研究方向：国际航运管理、港口管理、港航政策、航运实务与法规；
谭京京（1989—），男，重庆人，硕士，主要研究方向：港航大数据处理、机器学习。
第一联系人：高琦凯（1999—），男，山东临沂人，硕士研究生，主要研究方向：港航大数据、轨迹分析；
基金资助:
国家社会科学基金资助项目(20BJY177)

Abstract

Abstract:

Aiming at the problem that most trajectory similarity measurement algorithms cannot distinguish the trajectories with opposite directions， a three-dimensional Triangulation Division （3TD） algorithm based on three-dimensional space area division was proposed. Firstly， the absolute time series of the trajectory set was transformed into the relative time series according to the time conversion rules of the 3TD algorithm. Then， in the three-dimensional space coordinate system composed of three elements of longitude， latitude， and time， the area between trajectories were divided into several non-overlapping triangles by partitioning rules， and the areas of the triangles were accumulated and the trajectory similarity was calculated. Finally， the proposed algorithm was compared with the Longest Common SubSequence （LCSS） algorithm and Triangle Division （TD） algorithm on the randomly sampled trajectory dataset collected from the ship Automatic Identification System （AIS）. Experimental results show that the accuracy of the 3TD algorithm reaches 100%. At the same time， the proposed algorithm can also maintain accurate measurement results and high operation efficiency on massive datasets and datasets with partial missing trajectory points， which can better adapt to the similarity measurement of divergent trajectories.

Key words: space-time trajectory, three-dimensional space, area division, similarity measurement, trajectory direction

摘要：

针对大部分轨迹相似性度量算法无法区分方向相反轨迹的问题，提出了一种基于三维空间面积划分的三维三角分割（3TD）算法。首先，按照3TD算法的时间转换规则将轨迹集的绝对时间序列转变为相对时间序列；然后，在由经度、纬度以及时间三要素构成的三维空间坐标系中，通过划分规则将轨迹间面积分割成若干互不重叠的三角形，累加三角形面积并计算轨迹相似度；最后，在从船舶自动识别系统（AIS）收集的随机采样轨迹数据集上，与最长公共子序列（LCSS）算法和三角分割（TD）算法等进行了对比实验。实验结果表明：3TD算法对实验数据集中异向轨迹识别精确度达到100%；同时该算法面对海量数据集以及轨迹点部分缺失的数据集时，也能维持准确的度量结果以及较高的运算效率，能更好地适应异向轨迹相似度量工作。

关键词: 时空轨迹, 三维空间, 面积划分, 相似性度量, 轨迹方向

CLC Number:

TP391

Kai XU, Qikai GAO, Ming YIN, Jingjing TAN. Trajectory similarity measurement algorithm based on three-dimensional space area division[J]. Journal of Computer Applications, 2024, 44(1): 318-323.

徐凯, 高琦凯, 殷明, 谭京京. 基于三维空间面积划分的轨迹相似性度量算法[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 318-323.

Figures/Tables 8

Fig. 1 TD algorithm to measure similarity between trajectories

Fig. 2 3TD algorithm to measure similarity between trajectories

Fig. 3 Convective trajectories in port area

Tab. 1 Results of similarity measurement of convective trajectories in port area

实验对象	不同轨迹相似性度量算法得到的相似度数值/%
实验对象	3TD算法	TD算法	LCSS算法
$P 1$ 与 $P 2$	95.61	95.77	95.87
$P 1$ 与 $P 3$	61.59	93.34	95.78

Tab. 1 Results of similarity measurement of convective trajectories in port area

实验对象	不同轨迹相似性度量算法得到的相似度数值/%
实验对象	3TD算法	TD算法	LCSS算法
$P 1$ 与 $P 2$	95.61	95.77	95.87
$P 1$ 与 $P 3$	61.59	93.34	95.78

Fig. 4 Trajectory similarity changing with random missing trajectory points

Tab. 2 Comparison of comprehensive running time among different algorithms

实验类型	不同相似性算法运行时间/s
实验类型	3TD算法	TD算法	LCSS算法
鲁棒性检验	0.019 0	0.016 5	0.745 0
异向轨迹识别检验	0.020 0	0.019 0	0.753 0

Fig. 5 Schematic diagram of complex divergent trajectories in port area

Tab. 3 Results of similarity measurement of complex divergent trajectories

实验对象	不同轨迹相似性度量算法得到的相似度数值/%
实验对象	3TD算法	TD算法	LCSS算法
$P 4$ 与 $P 7$	56.34	95.96	96.75
$P 5$ 与 $P 7$	75.65	97.16	97.77
$P 6$ 与 $P 7$	67.94	92.12	91.94

Tab. 3 Results of similarity measurement of complex divergent trajectories

实验对象	不同轨迹相似性度量算法得到的相似度数值/%
实验对象	3TD算法	TD算法	LCSS算法
$P 4$ 与 $P 7$	56.34	95.96	96.75
$P 5$ 与 $P 7$	75.65	97.16	97.77
$P 6$ 与 $P 7$	67.94	92.12	91.94

References 20

1	章永来，周耀鉴.聚类算法综述［J］.计算机应用， 2019， 39（7）： 1869-1882. 10.11772/j.issn.1001-9081.2019010174
	ZHANG Y L， ZHOU Y J. Review of clustering algorithms ［J］. Journal of Computer Applications， 2019， 39（7）： 1869-1882. 10.11772/j.issn.1001-9081.2019010174
2	杨威，龙华，邵玉斌，等.基于切比雪夫距离的密度计算与K-means的聚类方法研究［J］.通信技术， 2019， 52（4）： 833-838. 10.3969/j.issn.1002-0802.2019.04.010
	YANG W， LONG H， SHAO Y B， et al. Chebyshev distance-based density calculation and K-means clustering algorithm ［J］. Communications Technology， 2019， 52（4）： 833-838. 10.3969/j.issn.1002-0802.2019.04.010
3	周星星，吉根林，张书亮.时空轨迹相似性度量方法综述［J］.地理信息世界， 2018， 25（4）： 11-18. 10.3969/j.issn.1672-1586.2018.04.003
	ZHOU X X， JI G L， ZHANG S L. Overview of the similarity measurement methods for spatial-temporal trajectory ［J］. Geomatics World， 2018， 25（4）： 11-18. 10.3969/j.issn.1672-1586.2018.04.003
4	ZHOU C， LIU G， HUANG L， et al. Spatiotemporal Companion Pattern （STCP） mining of ships based on trajectory features ［J］. Journal of Marine Science and Engineering， 2023， 11（3）： No.528. 10.3390/jmse11030528
5	WANG X， XIAO Y. A deep learning model for ship trajectory prediction using Automatic Identification System （AIS） data ［J］. Information， 2023， 14（4）： No.212. 10.3390/info14040212
6	甄荣，邵哲平，潘家财.基于AIS数据的船舶行为特征挖掘与预测：研究进展与展望［J］.地球信息科学学报， 2021， 23（12）： 2111-2127. 10.12082/dqxxkx.2021.210495
	ZHEN R， SHAO Z P， PAN J C. Advance in character mining and prediction of ship behavior based on AIS data ［J］. Journal of Geo-Information Science， 2021， 23（12）： 2111-2127. 10.12082/dqxxkx.2021.210495
7	BIFARETTI A， PAVAN E， GRIGIONI G. Consumer attitudes and concerns about beef consumption in Argentina and other south American countries ［J］. Agriculture， 2023， 13（3）： No.560. 10.3390/agriculture13030560
8	WANG J， LIU X， JIANG L. Algorithm for automatic parting of injection mold based on solid parting method ［J］. The International Journal of Advanced Manufacturing Technology， 2023， 124（7/8）： 2059-2077. 10.1007/s00170-022-10599-0
9	ZHANG Q， ZHANG C， CUI L， et al. A method for measuring similarity of time series based on series decomposition and dynamic time warping ［J］. Applied Intelligence， 2023， 53（6）： 6448-6463. 10.1007/s10489-022-03716-9
10	ZHAO L， SHI G. A novel similarity measure for clustering vessel trajectories based on dynamic time warping ［J］. The Journal of Navigation， 2019， 72（2）： 290-306. 10.1017/s0373463318000723
11	SÁNCHEZ-HERE L F. Simplification and event identification for ais trajectories： the equivalent passage plan method ［J］. The Journal of Navigation， 2019， 72（2）： 307-320. 10.1017/s037346331800067x
12	吕一可，徐凯，黄振强.基于面积划分的轨迹相似性度量方法［J］.计算机应用， 2020， 40（2）： 578-583.
	LYU Y K， XU K， HUANG Z Q. Trajectory similarity measurement method based on area division ［J］. Journal of Computer Applications， 2020， 40（2）： 578-583.
13	ZHEN R， JIN Y， HU Q， et al. Maritime anomaly detection within coastal waters based on vessel trajectory clustering and Naïve Bayes classifier ［J］. The Journal of Navigation， 2017， 70（3）： 648-670. 10.1017/s0373463316000850
14	SHEN H， TANG H， YIN Y. A novel method for ship trajectory clustering ［J］. International Journal of Naval Architecture and Ocean Engineering， 2022， 14： No.100474. 10.1016/j.ijnaoe.2022.100474
15	WEI Z， XIE X， ZHANG X. AIS trajectory simplification algorithm considering ship behaviours ［J］. Ocean Engineering， 2020， 216： No.108086. 10.1016/j.oceaneng.2020.108086
16	包磊.基于聚类距离计算的船舶轨迹异常检测方法［J］.舰船电子工程， 2020， 40（9）： 56-61. 10.3969/j.issn.1672-9730.2020.09.014
	BAO L. A trajectory data anomaly detection method based on trajectory cluster distance ［J］. Ship Electronic Engineering， 2020， 40（9）： 56-61. 10.3969/j.issn.1672-9730.2020.09.014
17	李爽，史国友，高邈，等.基于改进谱聚类算法的航路辨识［J］.上海海事大学学报， 2019， 40（4）： 1-6.
	LI S， SHI G Y， GAO M， et al. Route identification based on improved spectral clustering algorithm ［J］. Journal of Shanghai Maritime University， 2019， 40（4）： 1-6.
18	张春玮，马杰，牛元淼，等.基于行为特征相似度的船舶轨迹聚类方法［J］.武汉理工大学学报（交通科学与工程版）， 2019， 43（3）： 517-521. 10.3963/j.issn.2095-3844.2019.03.028
	ZHANG C W， MA J， NIU Y M， et al. Clustering method of ship trajectory based on similarity of behavior pattern ［J］. Journal of Wuhan University of Technology （Transportation Science and Engineering）， 2019， 43（3）： 517-521. 10.3963/j.issn.2095-3844.2019.03.028
19	LIAN M， LIU R W， LI S， et al. An unsupervised learning method with convolutional auto-encoder for vessel trajectory similarity computation ［J］. Ocean Engineering， 2021， 225： No.108803. 10.1016/j.oceaneng.2021.108803
20	张萍，李必军，郑玲，等.一种基于改进LCSS的相似轨迹提取方法［J］.武汉大学学报（信息科学版）， 2020， 45（4）： 550-556.
	ZHANG P， LI B J， ZHENG L， et al. A similar trajectory extraction method based on improved LCSS ［J］. Geomatics and Information Science of Wuhan University， 2020， 45（4）： 550-556.

[1]	YANG Mengmeng, ZHANG Aihua. Fractal image compression based on gray-level co-occurrence matrix and simultaneous orthogonal matching pursuit [J]. Journal of Computer Applications, 2021, 41(5): 1445-1449.
[2]	HU Lihua, ZUO Weijian, NIE Yaoyao. Feature matching method based on weighted similarity measurement [J]. Journal of Computer Applications, 2021, 41(2): 511-516.
[3]	Yubin ZHOU, Hong XIAO, Tao WANG, Wenchao JIANG, Meng XIONG, Zhongtang HE. Health index construction and remaining useful life prediction of mechanical axis based on action cycle degradation similarity measurement [J]. Journal of Computer Applications, 2021, 41(11): 3192-3199.
[4]	Yike LYU, Kai XU, Zhenqiang HUANG. Trajectory similarity measurement method based on area division [J]. Journal of Computer Applications, 2020, 40(2): 578-583.
[5]	MA Weiping, LI Wenxin, SUN Jinchuan, CAO Pengxia. Binocular vision target positioning method based on coarse-fine stereo matching [J]. Journal of Computer Applications, 2020, 40(1): 227-232.
[6]	YAO Luji, ZHANG Li. Design and implementation of Chinese architecture history teaching system based on mixed reality technology [J]. Journal of Computer Applications, 2019, 39(9): 2689-2694.
[7]	FU Lidong, HAO Wei, LI Dan, LI Fan. Community dividing algorithm based on similarity of common neighbor nodes [J]. Journal of Computer Applications, 2019, 39(7): 2024-2029.
[8]	ZHANG Yonglai, ZHOU Yaojian. Review of clustering algorithms [J]. Journal of Computer Applications, 2019, 39(7): 1869-1882.
[9]	PENG Lei, YANG Xiuyun, ZHANG Yufei, LI Guangyao. Non-rigid point set registration based on global and local similarity measurement [J]. Journal of Computer Applications, 2019, 39(10): 3028-3033.
[10]	CHANG Bingguo, ZANG Hongying. Time series classifier design based on piecewise dimensionality reduction and updated dynamic time warping [J]. Journal of Computer Applications, 2018, 38(7): 1910-1915.
[11]	XU Su, ZHOU Yingyue. Non-local means denoising algorithm based on image segmentation [J]. Journal of Computer Applications, 2017, 37(7): 2078-2083.
[12]	SHI Lukui, ZHANG Yanru, ZHANG Xin. Trajectory data clustering algorithm based on spatio-temporal pattern [J]. Journal of Computer Applications, 2017, 37(3): 854-859.
[13]	YANG Jiahui, LIU Fangai. Collaborative filtering algorithm based on Bhattacharyya coefficient and Jaccard coefficient [J]. Journal of Computer Applications, 2016, 36(7): 2006-2010.
[14]	REN Xiuli, WANG Chong. Multi-path routing protocol based on three-dimensional space and regional co-evolution in wireless sensor network [J]. Journal of Computer Applications, 2015, 35(3): 610-614.
[15]	ZHANG Guanliang ZOU Huanxin LU Chunyan ZHAO Jian. Algorithm of point pattern matching based on quasi Laplacian spectrum and point pair topological characteristics [J]. Journal of Computer Applications, 2013, 33(06): 1686-1690.

Trajectory similarity measurement algorithm based on three-dimensional space area division

基于三维空间面积划分的轨迹相似性度量算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 20

Related Articles 15

Recommended Articles

Metrics