Inferring Directed Road Networks from GPS Traces by Track Alignment

ISPRS International Journal of Geo-Information - Tập 4 Số 4 - Trang 2446-2471
Xingzhe Xie1, Kevin Bing-YungWong2, Hamid Aghajan2,1, Peter Veelaert1, Wilfried Philips1
1TELIN-IPI-IMINDS, Ghent University, Sint-Pietersnieuwstraat 41, Ghent 9000, Belgium
2Ambient Intelligence Research (AIR) Lab, Department of Electrical Engineering, Stanford University, Stanford, CA 94305, USA

Tóm tắt

This paper proposes a method to infer road networks from GPS traces. These networks include intersections between roads, the connectivity between the intersections and the possible traffic directions between directly-connected intersections. These intersections are localized by detecting and clustering turning points, which are locations where the moving direction changes on GPS traces. We infer the structure of road networks by segmenting all of the GPS traces to identify these intersections. We can then form both a connectivity matrix of the intersections and a small representative GPS track for each road segment. The road segment between each pair of directly-connected intersections is represented using a series of geographical locations, which are averaged from all of the tracks on this road segment by aligning them using the dynamic time warping (DTW) algorithm. Our contribution is two-fold. First, we detect potential intersections by clustering the turning points on the GPS traces. Second, we infer the geometry of the road segments between intersections by aligning GPS tracks point by point using a “stretch and then compress” strategy based on the DTW algorithm. This approach not only allows road estimation by averaging the aligned tracks, but also a deeper statistical analysis based on the individual track’s time alignment, for example the variance of speed along a road segment.

Từ khóa


Tài liệu tham khảo

Biagioni, J., and Eriksson, J. (2012, January 7–9). Map inference in the face of noise and disparity. Proceedings of the 20th International Conference on Advances in Geographic Information Systems, Redondo Beach, CA, USA.

Schroedl, 2004, Mining GPS traces for map refinement, Data Min. Knowl. Discov., 9, 59, 10.1023/B:DAMI.0000026904.74892.89

Davics, 2006, Scalable, distributed, real-time map generation, IEEE Pervasive Comput., 5, 47, 10.1109/MPRV.2006.83

Cao, L., and Krumm, J. (2009, January 4–6). From GPS traces to a routable road map. Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, WA, USA.

Shi, W., Shen, S., and Liu, Y. (2009, January 4–7). Automatic generation of road network map from massive GPS, vehicle trajectories. Proceedings of the IEEE 12th International Conference on Intelligent Transportation Systems, St. Louis, MO, USA.

Sato, J., Takahashi, T., Ide, I., and Murase, H. (2006, January 20–24). Change detection in streetscapes from GPS coordinated omni-directional image sequences. Proceedings of the IEEE 18th International Conference on Pattern Recognition, Hong Kong, China.

Vlahogianni, 2005, Optimized and meta-optimized neural networks for short-term traffic flow prediction: A genetic approach, Transp. Res. Part C Emerg. Technol., 13, 211, 10.1016/j.trc.2005.04.007

Syberfeldt, A., and Persson, L. (2009, January 1–3). Using Heuristic Search for Initiating the Genetic Population in Simulation-Based Optimization of Vehicle Routing Problems. Proceedings of the Industrial Simulation Conference, EUROSIS-ETI, Loughborough, UK.

Schultes, D. (2008). Route Planning in Road Networks. [Ph.D. Thesis, Karlsruhe Institute of Technology].

Niehoefer, B., Burda, R., Wietfeld, C., Bauer, F., and Lueert, O. (2009, January 20–25). GPS community map generation for enhanced routing methods based on trace-collection by mobile phones. Proceedings of the IEEE 1st International Conference on Advances in Satellite and Space Communications, Colmar, France.

Kukko, 2007, Road environment mapping system of the Finnish Geodetic InstituteâĂŤFGI Roamer, Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci., 36, 241

Bellens, R., Vlassenroot, S., and Gautama, S. (2011, January 25). Collection and analyses of crowd travel behaviour data by using smartphones. Proceedings of the BIVEC-GIBET 5th Transport Research Day, Namur, Belgium.

Lee, 2013, Bicycle safety map system based on smartphone aided sensor network, Adv. Sci. Technol. Lett., 42, 38, 10.14257/astl.2013.42.09

Haklay, 2008, Openstreetmap: User-generated street maps, IEEE Pervasive Comput., 7, 12, 10.1109/MPRV.2008.80

Haklay, 2010, How good is volunteered geographical information? A comparative study of OpenStreetMap and Ordnance Survey datasets, Environ. Plan. B Plan. Des., 37, 682, 10.1068/b35097

Biagioni, 2012, Inferring road maps from global positioning system traces, Transp. Res. Rec. J. Transp. Res. Board, 2291, 61, 10.3141/2291-08

Zheng, Y., Li, Q., Chen, Y., Xie, X., and Ma, W.Y. (2008, January 21–24). Understanding mobility based on GPS data. Proceedings of the 10th International Conference on Ubiquitous Computing, Seoul, Korea.

Edelkamp, S., and Schrödl, S. (2003). Computer Science in Perspective, Springer.

You, 2014, Transit tomography using probabilistic time geography: Planning routes without a road map, J. Locat. Based Serv., 8, 211, 10.1080/17489725.2014.963180

Xie, X., Philips, W., Veelaert, P., and Aghajan, H. (2014, January 8–11). Road network inference from GPS traces using DTW algorithm. Proceedings of the IEEE 17th International Conference on Intelligent Transportation Systems (ITSC), Qingdao, China.

Liu, B. (2007). Web Data Mining, Springer.

Chen, C., and Cheng, Y. (2008, January 21–22). Roads digital map generation with multi-track gps data. Proceedings of the IEEE InternationalWorkshop on Education Technology and Training, 2008. and 2008 International Workshop on Geoscience and Remote Sensing, Shanghai, China.

Morris, S., Morris, A., and Barnard, K. (2004, January 7–11). Digital trail libraries. Proceedings of the 4th ACM/IEEE-CS Joint Conference on Digital Libraries, Tucson, AZ, USA.

Karagiorgou, S., and Pfoser, D. (2012, January 7–9). On vehicle tracking data-based road network generation. Proceedings of the 20th International Conference on Advances in Geographic Information Systems, Redondo Beach, CA, USA.

Berndt, D.J., and Clifford, J. (1994). Using Dynamic Time Warping to Find Patterns in Time Series, KDD.

Greenfeld, J.S. (2002, January 13–17). Matching GPS observations to locations on a digital map. Proceedings of the Transportation Research Board 81st Annual Meeting, Washington, DC, USA.

Calcagno, 2008, Geological modelling from field data and geological knowledge: Part I. Modelling method coupling 3D potential-field interpolation and geological rules, Phys. Earth Planet. Inter., 171, 147, 10.1016/j.pepi.2008.06.013

BITS Networked Systems Laboratory. Available online: http://bits.cs.uic.edu/.

OpenStreetMap. Available online: http://www.openstreetmap.org/.

Thông tin
Thông tin xuất bản

ISPRS International Journal of Geo-Information

Tập 4 Số 4

2446-2471

Thông tin tác giả