在許多關於車輛安全的應用中，都需要車輛的軌跡資料，例如左轉輔助及前方碰撞警告。可惜的是，透過全球定位系統 (GPS) 收集到的車輛軌跡資料，受到 GPS 的限制或較低的取樣率影響，常常不夠準確。因此，如何清理並校正收集到的軌跡資料是一個重要的問題。而相較於其他的軌跡清理的研究，基於 HMM 的軌跡清理方式似乎較有希望達到效果。在此研究中，我們提出了使用三種不同的量測值來評估基於 HMM 的軌跡清理效能，分別是：Hausdorff 距離，Fréchet 距離以及 Average Fréchet 距離。在我們的實驗中，使用基於 HMM 的軌跡清理，並利用前面提出的三個量測值來找出對於這個基於 HMM 的軌跡清理最好的參數設定。

The vehicle trajectories are required in many vehicle safety applications, such as Left Turn Assist (LTA) and Front Collision Warning (FCW). Unfortunately, the vehicle trajectories collected by Global Positioning System are often inaccurate due to the limitation of GPS or low sampling rate. How to cleanse and calibrate the collected trajectory is therefore an important issue. The HMM based trajectory data cleansing seems to be promising among different research works of trajectory cleansing, but it does not provide adquate quantitative analysis to evaluate its performance. In this research, we propose to use three different distance measurements: Hausdorff distance, Fréchet distance, and Average Fréchet distance, to evaluate the performance of HMM based trajectory cleansing. In our HMM-based trajectory cleansing experiments, the three propose measurements are used to identify the best parameter settings for the HMM-based trajectory cleansing.

1 Introduction 1
2 Related Work 4
2.1 The Ratio of Exactly Match . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Similarities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Preliminary 7
3.1 OpenStreetMap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7
3.2 HMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7
3.3 HMM on Trajectory Data Cleansing . . . . . . . . . . . . . . . . . . . . . 9
3.4 Hausdorff Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10
3.5 Fréchet Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12
3.6 Average Fréchet Distance . . . . . . . . . . . . . . . . . . . . . . . . .13
4 Design 14
4.1 Trajectory Data Cleansing . . . . . . . . . . . . . . . . . . . . . . . . 14
4.1.1 Noise Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15
4.1.2 HMM Map Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . .17
4.1.3 A* Route Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2 Measurement Implementation . . . . . . . . . . . . . . . . . . . . . . . .23
4.2.1 Hausdorff Distance Measuring . . . . . . . . . . . . . . . . . . . . . .25
4.2.2 Fréchet Distance Measuring . . . . . . . . . . . . . . . . . . . . . . .27
4.2.3 Average Fréchet Distance Measuring . . . . . . . . . . . . . . . . . . .29
5 Performance 30
5.1 Data Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.2 Studied Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . .30
5.3 Cleansing Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
6 Conclusion 38
Reference 39

[1] Muhammad Alam, Joaquim Ferreira, and Jose Fonseca. Introduction to Intelligent Transportation Systems, pages 1-17. Springer International Publishing, Cham, 2016.
[2] Essam Algizawy, Tetsuji Ogawa, and Ahmed El-Mahdy. Real-time large-scale map matching using mobile phone data. ACM Trans. Knowl. Discov. Data, 11(4):52:1-52:38, July 2017.
[3] Helmut Alt and Michael Godau. Computing the frechet distance between two polygonal curves. Int. J. Comput. Geometry Appl., 5:75-91, 1995.
[4] Heba Aly and Moustafa Youssef. semmatch: Road semantics-based accurate map matching for challenging positioning data. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL '15, pages
5:1-5:10, New York, NY, USA, 2015. ACM.
[5] Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. On map-matching vehicle tracking data. In Proceedings of the 31st International Conference on Very Large Data Bases, pages 853{864. VLDB Endowment, 2005.
[6] OpenStreetMap contributors. Openstreetmap, 2016. [Online; accessed 16-March-2017].
[7] A. El-Rabbany. Introduction to GPS: The Global Positioning System. Artech House mobile communications series. Artech House, 2002.
[8] R. Elliott, L. Aggoun, and J. Moore. Hidden Markov models: estimation and control. Springer, 1995.
[9] M. Maurice Frechet. Sur quelques points du calcul fonctionnel. Rendiconti del Circolo Matematico di Palermo, 22(1):1-72, Dec 1906.
[10] F. Hausdor. Grundzuge der Mengenlehre. Leipzig Viet, 1914.
[11] Z. He, S. Xi-wei, L. Zhuang, and P. Nie. On-line map-matching framework for oating car data with low sampling rate in urban road networks. IET Intelligent Transport Systems, 7(4):404-414, December 2013.
[12] id, 2013. [Online; accessed 26-May-2019].
[13] Dirk Stocker Immanuel Scholz and other contributors. Josm, 2014. [Online; accessed 26-March-2019].
[14] Rahul Kala. 4 - advanced driver assistance systems. In Rahul Kala, editor, On-Road Intelligent Vehicles, pages 59-82. Butterworth-Heinemann, 2016.
[15] Sinn Kim and Jong-Hwan Kim. Adaptive fuzzy-network-based c-measure map-matching algorithm for car navigation system. IEEE Transactions on Industrial Electronics, 48(2):432-441, 2001.
[16] Yin Lou, Chengyang Zhang, Yu Zheng, Xing Xie, Wei Wang, and Yan Huang. Map-matching for low-sampling-rate gps trajectories. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS '09, pages 352-361, New York, NY, USA, 2009. ACM.
[17] Maps.me, 2011. [Online; accessed 26-March-2019].
[18] Paul Newson and John Krumm. Hidden markov map matching through noise and sparseness. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 336-343. ACM, 2009.
[19] Thomas Plotz and Gernot A. Fink. Markov models for oine handwriting recognition: A survey. Int. J. Doc. Anal. Recognit., 12(4):269-298, November 2009.
[20] L. R. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257-286, Feb 1989.
[21] Peter J. Rousseeuw and Christophe Croux. Alternatives to the median absolute deviation. Journal of the American Statistical Association, pages 1273-1283, 1993.
[22] Helmut Schmid and Florian Laws. Estimation of conditional probabilities with decision trees and an application to ne-grained pos tagging. In Proceedings of the 22Nd International Conference on Computational Linguistics - Volume 1, COLING '08, pages 777-784, Stroudsburg, PA, USA, 2008. Association for Computational Linguistics.
[23] F. Van Diggelen. Gnss accuracy: Lies, damn lies and statistics. GPS World, pages 26-32, 2007.
[24] Q. Wang, M. Sun, and K. Sakai. Trajectory data cleansing using hmm. In 2017 46th International Conference on Parallel Processing Workshops (ICPPW), pages 8-15, Aug 2017.
[25] Hong Wei, Yin Wang, George Forman, and Yanmin Zhu. Map matching: Comparison of approaches using sparse and noisy data. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL'13, pages 444-447, New York, NY, USA, 2013. ACM.
[26] Yifang Yin, Rajiv Ratn Shah, Guanfeng Wang, and Roger Zimmermann. Feature-based map matching for low-sampling-rate gps trajectories. ACM Trans. Spatial Algorithms Syst., 4(2):4:1-4:24, August 2018.
[27] Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing Xie, Guangzhong Sun, and Yan Huang. T-drive: Driving directions based on taxi trajectories. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 99-108. ACM, 2010.
[28] Ling Yuan, Dan Li, and Song Hu. A map-matching algorithm with low-frequency foating car data based on matching path. Eurasip Journal on Wireless Communications and Networking, 2018(1):146, 2018.
[29] W. Zeng and R. L. Church. Finding shortest paths on real road networks: The case for a*. Int. J. Geogr. Inf. Sci., pages 531-543, 2009.
[30] Yu Zheng. Trajectory data mining: An overview. ACM Trans. Intell. Syst. Technol., pages 29:1-29:41, 2015.