全面准确的路网信息作为智慧城市的重要基础之一，在城市规划、交通管理以及大众出行等方面具有重要意义和价值。然而，传统的基于测量的路网数据获取方式往往周期较长，不能及时反映最新的道路信息。近几年，随着定位技术在移动设备的广泛运用，国内外学者在研究路网信息获取时逐渐将视野转向移动对象的轨迹数据中所蕴含的道路信息。当前，基于移动位置信息的路网生成和更新方法多是直接面向全部轨迹数据施加道路提取算法，在处理大规模轨迹或者大范围道路时，计算量极大。为此，本文基于轨迹地图匹配技术，提出一种采用“检查→分析→提取→更新”过程的螺旋式路网数据更新策略。其主要思想是逐条输入轨迹，借助HMM地图匹配发现已有路网中的问题路段，进而从问题路段周边局部范围内的轨迹数据中提取并更新相关道路信息。该方法仅在局部范围内利用少量轨迹数据来修复路网，避免了对整个轨迹数据集进行计算，从而有效减少了计算量。基于OpenStreetMap的武汉市区路网数据以及武汉市出租车轨迹数据的试验表明，本文提出的路网更新方法不仅可行，而且灵活高效。
The road network with complete and accurate information, as one of the key foundations of Smart City, bears significance in fields like urban planning, traffic managing and public traveling, et al. However, long manufacturing period of road network data, based on traditional surveying methods, often leaves it in an inconsistent state with the latest situation. Recently, positioning techniques ubiquitously used in mobile devices has been gradually coming into focus for domestic and overseas scholars. Currently, most of approaches, generating or updating road networks from mobile location information, are to compute with GPS trajectory data directly by various algorithms, which lead to expensive consumption of computational resources in case of mass GPS data covering large-scale areas. For this reason, we propose a spiral update strategy of road network data based on map-matching technology, which follows a “identify→analyze→extract→update” process. The main idea is to detect condemned road segments of existing road network data with the help of HMM for each trajectory input, as well as repair them, on the local scale, by extracting new road information from trajectory data.The proposed approach avoids computing on the entire dataset of trajectory data for road segments. Instead, it updates information of existing road network data by means of focalizing on the minimum range of potential condemned segments. We evaluated the performance of our proposals using GPS traces collected on taxies and OpenStreetMap(OSM) road networks covering urban areas of Wuhan City.
[1] EKPENYONG F, PALMER-BROWN D, BRIMICOMBE A. Extracting Road Information from Recorded GPS Data Using Snap-drift Neural Network[J]. Neurocomputing, 2009, 73(1-3): 24-36.
[2] CAO Lili, KRUMM J. From GPS Traces to a Routable Road Map[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Seattle, Washington: ACM, 2009: 3-12.
[3] HU Jiuxiang, RAZDAN A, FEMIANI J C, et al. Road Network Extraction and Intersection Detection from Aerial Images by Tracking Road Footprints[J]. IEEE Transactions on Geoscience and Remote Sensing, 2007, 45(12): 4144-4157.
[4] DAL POZ A P, ZANIN R B, DO VALE G M. Automated Extraction of Road Network from Medium-and High-Resolution Images[J]. Pattern Recognition and Image Analysis, 2006, 16(2): 239-248.
[5] BRVNTRUP R, EDELKAMP S, JABBAR S, et al. Incremental Map Generation with GPS Traces[C]//Proceedings of 2005 IEEE Conference on Intelligent Transportation Systems. Vienna: IEEE, 2005: 574-579.
[6] SCHROEDL S, WAGSTAFF K, ROGERS S, et al. Mining GPS Traces for Map Refinement[J]. Data Mining and Knowledge Discovery, 2004, 9(1): 59-87.
[7] EDELKAMP S, SCHRÖDL S. Route Planning and Map Inference with Global Positioning Traces[M]//KLEIN R, SIX H W, WEGNER L. Computer Science in Perspective. Berlin Heidelberg: Springer, 2003: 128-151.
[8] 唐炉亮, 刘章, 杨雪, 等. 符合认知规律的时空轨迹融合与路网生成方法[J]. 测绘学报. 2015, 44(11): 1271-1276. DOI: 10.11947/j.AGCS.2015.20140591. TANG Luliang, LIU Zhang, YANG Xue, et al. A Method of Spatio-temporal Trajectory Fusion and Road Network Generation Based on Cognitive Law[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(11): 1271-1276. DOI: 10.11947/j.AGCS.2015.20140591.
[9] ROGERS S, LANGLEY P, WILSON C. Mining GPS Data to Augment Road Models[C]//Proceedings of the fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego, California: ACM, 1999: 104-113.
[10] GUO Tao, IWAMURA K, KOGA M. Towards High Accuracy Road Maps Generation from Massive GPS Traces Data[C]//Proceedings of 2007 IEEE International Geoscience and Remote Sensing Symposium. Barcelona: IEEE, 2007: 667-670.
[11] KASEMSUPPAKORN P, KARIMI H A. A Pedestrian Network Construction Algorithm Based on Multiple GPS Traces[J]. Transportation Research Part C: Emerging Technologies, 2013, 26: 285-300.
[12] MURRAY C. Oracle Spatial and Graph Topology Data Model and Network Data Model Graph Developer's Guide, 12c Release 1 (12.1)[M]. 2013: 26-27.
[13] Wikipedia. Map Matching[EB/OL]. [2015-04-21]. http://en.wikipedia.org/wiki/Map_matching.
[14] JAWAD A, KERSTING K. Kernelized Map Matching for Noisy Trajectories[J]. Sig Spatial, 2010: 454-457.
[15] BERNSTEIN D, KORNHAUSER A. An Introduction to Map-matching for Personal Navigation Assistants[EB/OL]. [2002-06-19]. http://www.njtude.org/reports/mapmatchintro.pdf.
[16] KAPLAN E D, HEGARTY C J. Understanding GPS: Principles and Applications[M]. Boston: Artech House, 2006.
[17] OCHIENG W Y, QUDDUS M A, NOLAND R B. Map-matching in Complex Urban Road Networks[J]. Brazilian Journal of Cartography, 2004, 55(2): 1-14.
[18] YANG Dakai, CAI Baigen, YUAN Yifang. An Improved Map-matching Algorithm Used in Vehicle Navigation System[C]//Proceedings of 2003 IEEE Intelligent Transportation Systems. IEEE, 2003, 2: 1246-1250.
[19] RAYMOND R, MORIMURA T, OSOGAMI T, et al. Map Matching with Hidden Markov Model on Sampled Road Network[C]//Proceedings of the 21st International Conference on Pattern Recognition. Tsukuba: IEEE, 2012: 2242-2245.
[20] LOU Yin, ZHANG Chengyang, ZHENG Yu, et al. Map-matching for Low-sampling-rate GPS Trajectories[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Seattle, Washington: ACM, 2009: 352-361.
[21] GOH C Y, DAUWELS J, MITROVIC N, et al. Online Map-matching Based on Hidden Markov Model for Real-time Traffic Sensing Applications[C]//Proceedings of the 15th International IEEE Conference on Intelligent Transportation Systems. Anchorage: IEEE, 2012: 776-781.
[22] KAUFMAN L, ROUSSEEUW P J. Clustering by Means of Medoids[M]//DODGE Y. Statistical Data Analysis Based on the L1-Norm and Related Methods. Berlin Heidelberg: Springer, 1987: 405-416.
[23] LI Yang, HUANG Qixing, KERBER M, et al. Large-scale Joint Map Matching of GPS Traces[C]//Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Orlando, Florida: ACM, 2013: 214-223.
[24] KAUFMAN L, ROUSSEEUW P J. Finding Groups in Data: An Introduction to Cluster Analysis[M]. Hoboken: John Wiley & Sons, 1990: 68-123.
[25] 杜世宏, 杜道生, 樊红, 等. 基于栅格数据提取主骨架线的新算法[J]. 武汉测绘科技大学学报, 2000, 25(5): 432-436. DU Shihong, DU Daosheng, FAN Hong, et al. A New Raster-based Algorithm for Extracting Main Skeleton Line of Polygon[J]. Journal of Wuhan Technical University of Surveying and Mapping, 2000, 25(5): 432-436.
