Detecting Road Intersections from GPS Traces Using Longest Common Subsequence Algorithm
Detecting Road Intersections from GPS Traces Using Longest Common Subsequence Algorithm
复制标题
DOI：
10.3390/ijgi6010001
复制
发表时间：
2016-12
期刊：
影响因子：
--
通讯作者：
Xingzhe Xie;Wenzi Liao;H. Aghajan;P. Veelaert;W. Philips
中科院分区：
文献类型：
--
作者：
Xingzhe Xie;Wenzi Liao;H. Aghajan;P. Veelaert;W. Philips
交叉口是路网的重要组成部分，对道路规划和路径优化具有重要意义。现有方法大多将交叉口定义为道路使用者改变移动方向的位置，通过分析道路使用者的转向行为，从GPS轨迹中识别交叉口。然而，这些方法难以找到合适的运动方向变化阈值，导致无法检测到真实的交叉点或错误检测到虚假的交叉点。在本文中，十字路口被定义为连接三个或更多不同方向的路段的位置。我们建议通过查找GPS轨迹的公共子轨迹来检测该定义下的交集。我们首先使用动态规划方法检测每对GPS迹线之间的最长公共子序列（LCSS）。其次，我们将最长的非连续子序列划分为连续的子轨迹。公共子轨道的起点和终点作为连接点收集。最后，通过核密度估计（Kernel Density Estimation， KDE）从连接点检测出相交点。实验结果表明，我们提出的方法在f分数方面优于基于转折点的方法。
Intersections are important components of road networks, which are critical to both route planning and path optimization. Most existing methods define the intersections as locations where the road users change their moving directions and identify the intersections from GPS traces through analyzing the road users’ turning behaviors. However, these methods suffer from finding an appropriate threshold for the moving direction change, leading to true intersections being undetected or spurious intersections being falsely detected. In this paper, the intersections are defined as locations that connect three or more road segments in different directions. We propose to detect the intersections under this definition by finding the common sub-tracks of the GPS traces. We first detect the Longest Common Subsequences (LCSS) between each pair of GPS traces using the dynamic programming approach. Second, we partition the longest nonconsecutive subsequences into consecutive sub-tracks. The starting and ending points of the common sub-tracks are collected as connecting points. At last, intersections are detected from the connecting points through Kernel Density Estimation (KDE). Experimental results show that our proposed method outperforms the turning point-based methods in terms of the F-score.