於現今交通自動化系統中，道路偵測在相關應用當中佔了相當重要的角色，舉例來說，如異常駕駛偵測、最短路徑規劃、交通號誌時間最佳化等等。雖然現有的方法會提供一個平台，能夠讓使用者上傳自己的GPS軌跡資料，用來協助建立道路的架構，如OpenStreetMap、TomTom 以及Google Map。然而基於使用者隱私問題，大部分的使用者都不太願意提供長期軌跡資料。因此在我們的研究中，提出一個透過道路監視器進行道路偵測的新方法，使用該方法主要有以下理由 : (1) 無使用者隱私問題; (2) 容易從政府的角度去看; (3) 資料持續性更新。在監視器相關研究領域中，雖然有和我們研究相關的論文，因為使用情境的不同，因此它們的方法很難應用在我們的研究上。我們的目標主要從拍攝監視錄影器中，根據一系列移動物件軌跡，偵測道路結構，包含每條道路的中心方向以及道路形狀。在我們的觀察下，軌跡之間行為越相似，就有越大的機率行駛在同一條道路上，因此我們提出使用階層式分群(Hierarchical Clustering)的方法對擷取到的軌跡做分群來進行道路偵測。首先我們會先以尤拉距離(Euclidean Distance)的角度進行分群，並列出該方法缺點以及困難點，之後提出一個以向量(Vector-based)的角度下進行分群的方法來解決原先方法的問題。最後根據分群結果，建立路徑規則找出可能的直線以及轉彎的道路。在我們的實驗結果中，可以看出大部分的主要道路以及轉彎的道路都可以被偵測出來。

The road detection is the important component of some applications in intelligent transportation systems, such as detection of abnormal trajectories, shortest path recommendation, traffic light optimization, and so on. Although most of current approaches, such as OpenStreetMap, TomTom, and Google Map, use the GPS records, which offers the capability to update trajectories, so as to have the ability to build the road structure. However, this method has the problem of user privacy because not all users are willing to update their data. Therefore, in our research, we propose the novel method for road detection from the records of surveillance videos built on the roads. The reasons why we use those data are that (1) no user privacy problem; (2) easy view by government; (3) data update continuously. In the research field of surveillance videos, there are some papers related to our research, but their surveillance scenario is orthogonal to ours, so that their approaches are not suitable to our goal. The goal in our research is finding the road spatial structure in surveillance videos, including main direction and spatial regions of each road. In our observation, the trajectories with similar behavior have higher possibility to pass via the same road. Due to this observation, based on the list of trajectories retrieved from a video, we utilize the hierarchical clustering technique to perform road detection. First we apply the naïve approach of clustering framework with the matric of Euclidean Distance, and further purpose the vector-based hierarchical clustering to overcome problems appearing in the naïve solution. Finally, the path rule will be performed to find the possible turn road based on original trajectories. In our experimental results from 3 cases of real surveillance videos, it shows that main roads can be detected precisely and some turn roads are also able to be found.

[1] Weiming Hu, Xuejuan Xiao, Zhouyu Fu, Xie, D., Tieniu Tan & Maybank, S. (2006), “A system for learning statistical motion patterns,” Pattern Analysis and Machine Intelligence, IEEE Transactions, 28 (9) pp.1450~1464.
[2] Jing Yuan, Yu Zheng, Xing Xie & Guangzhong Sun (2013), “T-Drive: Enhancing Driving Directions with Taxi Drivers' Intelligence,” Knowledge and Data Engineering, IEEE Transactions, 25 (1) pp.220~232.
[3] As'ad Salkham, Raymond Cunningham, Anurag Garg & Vinny Cahill (2008), “A Collaborative Reinforcement Learning Approach to Urban Traffic Control Optimization,” Proceedings of the 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, 2 pp.560~566.
[4] Schlenoff, C., Balakirsky, S., Barbera, T., Scrapper, C., Ajot, J., Hui, E., & Paredes, M. (2004), “The NIST Road Network Database: Version 1.0,” National Institute of Standards and Technology (NIST) Internal Report 7136.
[5] http://www.openstreetmap.org.
[6] http://www.tomtom.com/.
[7] https://www.google.com/maps.
[8] Lili Cao & John Krumm (2009), “From GPS traces to a routable road map,” Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp.3~12.
[9] Yihua Chen & John Krumm (2010), “Probabilistic modeling of traffic lanes from GPS traces,” Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp.81~88.
[10] http://en.wikipedia.org/wiki/Global_Positioning_System.
[11] Huang, C.-R., Chung, P.-C., Yang, D.-K., Chen, H.-C. & Huang, G.-J. (2014), “Maximum a Posteriori Probability Estimation for Online Surveillance Video Synopsis,” Circuits and Systems for Video Technology, IEEE Transactions, 24 (8) pp.1417~1429
[12] Anik Saha, Dipanjan Das Roy, Tauhidul Alam & Kaushik Deb (2012), “Automated Road Lane Detection for Intelligent Vehicles,” Global Journal of Computer Science and Technology.
[13] Chun-Wei Lin, Han-Ying Wang & Din-Chang Tseng (2009), “A Robust Lane Detection and Verification Method for Intelligent Vehicles,” Intelligent Information Technology Application, 2009. IITA 2009. Third International Symposium, pp.521~524.
[14] Bing Yu & Weigong Zhang (2009), “A Robust Approach of Lane Detection based on Machine Vision,” Control, Automation and Systems Engineering, 2009. CASE 2009. IITA International Conference, pp.195~198.
[15] Borkar, A., Hayes, M. & Smith, M.T. (2012), “A Novel Lane Detection System With Efficient Ground Truth Generation,” Intelligent Transportation Systems, IEEE Transactions, 13 (1) pp.365~374.
[16] Chunzhao Guo, Mita, S. & McAllester, D. (2012), “Robust Road Detection and Tracking in Challenging Scenarios Based on Markov Random Fields With Unsupervised Learning,” Intelligent Transportation Systems, IEEE Transactions, 13 (3) pp.1338~1354.
[17] ZuWhan Kim (2008), “Robust Lane Detection and Tracking in Challenging Scenarios,” Intelligent Transportation Systems, IEEE Transactions, pp.16~26.
[18] Lloyd, S. (1982), “Least Squares Quantization in PCM," IEEE Transactions on Information Theory, 9 (1) pp. 129~137.
[19] Stephen C. Johnson (1967), “Hierarchical clustering schemes,” Journal Psychometrika, pp. 241~254.
[20] Muller, M. (2007), ”Dynamic Time Warping,” Information Retrieval for Music and Motion, Springer, ISBN 2007, pp. 69~84.
[21] Vlachos, M., Kollios, G. (2002), & Gunopulos, D., “Discovering Similar Multidimensional Trajectories,” Proceedings of ICDE, pp. 673~684.
[22] John Hershberger & Jack Snoeyink (1994), “An O(nlogn) implementation of the Douglas-Peucker algorithm for line simplification,” Proceedings of the tenth annual symposium on Computational geometry, pp. 383~384.
[23] Stefan Schroedl, Kiri Wagstaff, Seth Rogers, Pat Langley & Christopher Wilson, “Mining GPS Traces for Map Refinement,” Journal Data Mining and Knowledge Discovery, 9 (1) pp. 59~87.