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

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

作　　者：徐凯[1] 高琦凯 殷明[1] 谭京京 XU Kai;GAO Qikai;YIN Ming;TAN Jingjing(Shanghai International Shipping Institute(Shanghai Maritime University),Shanghai 200082,China;College of Transport and Communications,Shanghai Maritime University,Shanghai 201306,China;Shanghai Jizhi Shipping Development Company Limited,Shanghai 200082,China)

机构地区：[1]上海国际航运研究中心(上海海事大学),上海200082 [2]上海海事大学交通运输学院,上海201306 [3]上海汲致航运发展有限公司,上海200082

出　　处：《计算机应用》2024年第1期318-323,共6页journal of Computer Applications

基　　金：国家社会科学基金资助项目(20BJY177)。

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]