- 學位論文
Map Matching for Low-Sampling-Rate GPS Trajectories by Exploring Real-time Moving Directions
Map Matching for Low-Sampling-Rate GPS Trajectories by Exploring Real-time Moving Directions
摘要
地圖匹配是一個將一連串的地理座標(例如： GPS 軌跡)匹配到地圖上的演算法。由於GPS 座標的誤差以及取樣頻率的限制， GPS 裝置所擷取到的位置資訊並不精確，因此造成使用者的位置在地圖上有偏差。此外，地圖匹配對於許多的應用來說是一個重要的預處理步驟，例如導航系統、車流量分析和自動駕駛汽車皆須使用地圖匹配後的GPS 資料。然而目前大部份的地圖匹配演算法只考慮GPS 點和道路的距離、道路網的拓樸以及道路的速度限制來決定匹配的結果，此外亦不能正確得處理接近路口處的座標匹配。有鑑於此，本研究針對低取樣頻率的GPS 軌跡提出了一個基於時空資訊與行進方向之地圖匹配演算法(Spatio-temporal-direction based matching algorithm, STD-matching)。此演算法結合(1)空間資訊與道路網拓樸、(2)道路的速度限制以及(3)使用者即時移動方向資訊，以獲得更正確的地圖匹配結果。此外，此研究中我們也同時實作GPS 集群、GPS 平滑化以及A∗ 最短路徑演算法來縮短地圖匹配時間。在實驗中我們與其他兩篇研究進行比較，而實驗結果顯示出我們的演算法在精確度上有較優異的表現。
並列摘要
Map matching is the process of matching a series of recorded geographic coordinates (e.g., a GPS trajectory) to a road network. Due to GPS positioning errors and the sampling constraints, the GPS data collected by the GPS device are not precise, and the location of a user can not always be correctly shown on the map. Therefore, map matching is an important preprocessing step for many applications such as navigation systems, traffic flow analysis, and autonomous cars. Unfortunately, most current map-matching algorithms only consider the distance between the GPS points and the road segments, the topology of the road network, and the speed constraint of the road segment to determine the matching results. Moreover, most current map-matching algorithms can not handle the matching problem at junctions. In this paper, we propose a spatio-temporal-direction based matching algorithm (STD-matching) for low-sampling-rate GPS trajectories. STD-matching considers (1) the spatial features such as the distance information and topology of the road network, (2) the speed constraints of the road network, and (3) the real-time moving direction which shows the movement of the user. Moreover, we also reduce the running time by performing GPS clustering, GPS smoothing, and the A* shortest path algorithms. In our experiments, we compare STD-matching with two baseline algorithms, the ST-matching algorithm and the stMM algorithm, using a real data set. The experiment results show that our STD-matching algorithm outperforms the two baseline algorithms in terms of matching accuracy.