James Biagioni
ABSTRACT
This paper describes a process for automatically inferring maps from large collections of opportunistically collected GPS traces. In this type of dataset, there is often a great disparity in terms of coverage. For example, a freeway may be represented by thousands of trips, whereas a residential road may only have a handful of observations. Additionally, while modern GPS receivers typically produce high-quality location estimates, errors over 100 meters are not uncommon, especially near tall buildings or under dense tree coverage. Combined, GPS trace disparity and error present a formidable challenge for the current state of the art in map inference. By tuning the parameters of existing algorithms, a user may choose to remove spurious roads created by GPS noise, or admit less-frequently traveled roads, but not both.
In this paper, we present an extensible map inference pipeline, designed to mitigate GPS error, admit less-frequently traveled roads, and scale to large datasets. We demonstrate and compare the performance of our proposed pipeline against existing methods, both qualitatively and quantitatively, using a real-world dataset that includes both high disparity and noise. Our results show significant improvements over the current state of the art.
- Bits Networked Systems Laboratory, http://bits.cs.uic.edu/. Accessed July 22, 2012.Google Scholar
- OpenStreetMap, http://www.openstreetmap.org/. Accessed July 22, 2012.Google Scholar
- G. Agamennoni, J. Nieto, and E. Nebot. Robust inference of principal road paths for intelligent transportation systems. Intelligent Transportation Systems, IEEE Trans., 12(1):298--308, March 2011. Google ScholarDigital Library
- J. Biagioni and J. Eriksson. Inferring Road Maps from GPS Traces: Survey and Comparative Evaluation. Transportation Research Record: Journal of the Transportation Research Board, 2012.Google Scholar
- J. Biagioni, T. Gerlich, T. Merrifield, and J. Eriksson. EasyTracker: Automatic Transit Tracking, Mapping, and Arrival Time Prediction Using Smartphones. In SenSys, pages 68--81. ACM, 2011. Google ScholarDigital Library
- L. Cao and J. Krumm. From gps traces to a routable road map. ACM GIS, pages 3--12, 2009. Google ScholarDigital Library
- C. Chen and Y. Cheng. Roads digital map generation with multi-track gps data. In ETT and GRS 2008., volume 1, pages 508--511, December 2008. Google ScholarDigital Library
- Y. Chen and J. Krumm. Probabilistic modeling of traffic lanes from gps traces. GIS, pages 81--88, New York, NY, USA, 2010. ACM. Google ScholarDigital Library
- J. J. Davies, A. R. Beresford, and A. Hopper. Scalable, distributed, real-time map generation. IEEE Pervasive Computing, 5:47--54, 2006. Google ScholarDigital Library
- D. Douglas and T. Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer, 10(2):112--122, 1973.Google ScholarCross Ref
- S. Edelkamp and S. Schrödl. Route planning and map inference with global positioning traces. In R. Klein, H.-W. Six, and L. Wegner, editors, Computer Science in Perspective, volume 2598 of LNCS, pages 128--151. Springer, 2003. Google ScholarDigital Library
- T. Guo, K. Iwamura, and M. Koga. Towards high accuracy road maps generation from massive gps traces data. In IGARSS 2007, pages 667--670, 2007.Google ScholarCross Ref
- S. Jang, T. Kim, and E. Lee. Map generation system with lightweight gps trace data. In ICACT, volume 2, pages 1489--1493, February 2010. Google ScholarDigital Library
- Q. Li, X. Bai, and W. Liu. Skeletonization of gray-scale image from incomplete boundaries. In ICIP 2008, pages 877--880, oct. 2008.Google ScholarCross Ref
- X. Liu, J. Biagioni, J. Eriksson, Y. Wang, G. Forman, and Y. Zhu. Mining Large-Scale, Sparse GPS Traces for Map Inference: Comparison of Approaches. In KDD. ACM, 2012. Google ScholarDigital Library
- F. Meyer. Topographic distance and watershed lines. Signal Processing, 38(1):113--125, 1994. Google ScholarDigital Library
- P. Newson and J. Krumm. Hidden markov map matching through noise and sparseness. GIS, 2009. Google ScholarDigital Library
- B. Niehoefer, R. Burda, C. Wietfeld, F. Bauer, and O. Lueert. Gps community map generation for enhanced routing methods based on trace-collection by mobile phones. In SPACOMM 2009, pages 156--161, July 2009. Google ScholarDigital Library
- S. Schroedl, K. Wagstaff, S. Rogers, P. Langley, and C. Wilson. Mining gps traces for map refinement. Data Mining and Knowledge Discovery, 9:59--87, 2004. Google ScholarDigital Library
- D. W. Scott. Kernel Density Estimators, pages 125--193. John Wiley and Sons, Inc., 2008.Google Scholar
- W. Shi, S. Shen, and Y. Liu. Automatic generation of road network map from massive gps, vehicle trajectories. In ITSC '09, pages 1--6, October 2009.Google ScholarCross Ref
- A. Steiner and A. Leonhardt. A Map Generation Algorithm using Low Frequency Vehicle Position Data. In 90th Annual Meeting of the Transportation Research Board, 2011. 17 pages.Google Scholar
- A. Thiagarajan, L. Sivalingam, K. LaCurts, S. Toledo, J. Eriksson, S. Madden, and H. Balakrishnan. Vtrack: Accurate, energy-aware road traffic delay estimation using mobile phones. In SenSys, 2009. Google ScholarDigital Library
- S. Worrall and E. Nebot. Automated process for generating digitised maps through gps data compression. In Australasian Conf. on Robotics and Automation, 2007.Google Scholar
- P. Yim, P. Choyke, and R. Summers. Gray-scale skeletonization of small vessels in magnetic resonance angiography. Medical Imaging, IEEE Transactions on, 19(6):568--576, June 2000.Google Scholar
- T. Y. Zhang and C. Y. Suen. A fast parallel algorithm for thinning digital patterns. Communications of the ACM, 27(3):236--239, Mar. 1984. Google ScholarDigital Library
Recommendations
From GPS traces to a routable road map
GIS '09: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information SystemsThis paper presents a method for automatically converting raw GPS traces from everyday vehicles into a routable road network. The method begins by smoothing raw GPS traces using a novel aggregation technique. This technique pulls together traces that ...
On vehicle tracking data-based road network generation
SIGSPATIAL '12: Proceedings of the 20th International Conference on Advances in Geographic Information SystemsRoad networks are important datasets for an increasing number of applications. However, the creation and maintenance of such datasets pose interesting research challenges. This work proposes an automatic road network generation algorithm that takes ...
Mining large-scale, sparse GPS traces for map inference: comparison of approaches
KDD '12: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data miningWe address the problem of inferring road maps from large-scale GPS traces that have relatively low resolution and sampling frequency. Unlike past published work that requires high-resolution traces with dense sampling, we focus on situations with coarse ...
Comments