基于最长公共子序列的非同步相似轨迹判断

Computing Similar Measure between Two Asynchronous Trajectories Based on Longest Common Subsequence Method

针对非同步相似轨迹判断问题,提出了一种基于最长公共子序列理论的相似轨迹判断新算法。首先,求出查询轨迹线段与候选轨迹线段之间的距离;其次,利用最长公共子序列算法,计算两轨迹的最长公共子轨迹长度;最后,根据相似度门限,判断轨迹是否相似。数值实例验证了所提算法能够提高非同步轨迹的相似度。

For the problem of judging the asynchronous similar trajectory,a new algorithm for computing the similar trajectories is proposed based on the Longest Common Subsequence（ LCS） method. Firstly,the line segment distances,which are between line segments of the query trajectory and the line segments of the candidate trajectory,are computed by the line segment distance. Secondly,the length of the longest common sub-trajectory,which is between the query trajectory and the candidate trajectory,is computed by the LCS method. Finally,the similarity measure between two trajectories is computed and the similar trajectory is got. Simulation shows the new method can improve the similarity measure between two asynchronous trajectories.