Inferring Road Maps from Global Positioning System Traces

Abstract

As a result of the availability of Global Positioning System (GPS) sensors in a variety of everyday devices, GPS trace data are becoming increasingly abundant. One potential use of this wealth of data is to infer and update the geometry and connectivity of road maps through the use of what are known as map generation or map inference algorithms. These algorithms offer a tremendous advantage when no existing road map data are present. Instead of the expense of a complete road survey, GPS trace data can be used to generate entirely new sections of the road map at a fraction of the cost. In cases of existing maps, road map inference may not only help to increase the accuracy of available road maps but may also help to detect new road construction and to make dynamic adaptions to road closures—useful features for in-car navigation with digital road maps. In past research, proposed algorithms had been evaluated qualitatively with little or no comparison with prior work. This lack of quantitative and comparative evaluation is addressed in this paper with the following contributions: (a) a comprehensive survey of the current literature on map generation; (b) a description of the first method for the automatic evaluation of generated maps; (c) a qualitative, quantitative, and comparative evaluation of three reference algorithms; and (d) an open source implementation of each of the three algorithms, with a 118-h trace data set and ground truth map for unrestricted use by the automatic map generation community.

Get full access to this article

View all access options for this article.

References

Agamennoni

, Nieto

, and Nebot

Robust Inference of Principal Road Paths for Intelligent Transportation Systems. IEEE Transactions on Intelligent Transportation Systems, Vol. 12, No. 1, 2011, pp. 298–308.

BITS Networked Systems Laboratory. http://bits.cs.uic.edu/. Accessed July 22, 2011.

Edelkamp

, and Schrödl

Route Planning and Map Inference with Global Positioning Traces. In Computer Science in Perspective ( Klein

, Six

H.-W.

, and Wegner

, eds.), Vol. 2598 of Lecture Notes in Computer Science, Springer, Berlin, 2003, pp. 128–151.

Davies

J.J.

, Beresford

A.R.

, and Hopper

Scalable, Distributed, Real-Time Map Generation. IEEE Pervasive Computing, Vol. 5, No. 4, 2006, pp. 47–54.

Cao

, and Krumm

From GPS Traces to a Routable Road Map. Proc., 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, Wash., Association for Computing Machinery, New York, 2009, pp. 3–12.

Schroedl

, Wagstaff

, Rogers

, Langley

, and Wilson

Mining GPS Traces for Map Refinement. Data Mining and Knowledge Discovery, Vol. 9, No. 1, 2004, pp. 59–87.

Niehoefer

, Burda

, Wietfeld

, Bauer

, and Lueert

GPS Community Map Generation for Enhanced Routing Methods Based on Trace-Collection by Mobile Phones. Proc., 1st International Conference on Advances in Satellite and Space Communications, Colmar, France, IEEE, New York, 2009, pp. 156–161.

Mitchell

Machine Learning, 1st ed. McGraw-Hill Education, New York, 1997.

Scott

D. W.

Kernel Density Estimators. In Multivariate Density Estimation: Theory, Practice, and Visualization, John Wiley & Sons, Inc., Hoboken, N.J., 2008, pp. 125–193.

10.

Worrall

, and Nebot

Automated Process for Generating Digitised Maps Through GPS Data Compression. Proc., Australasian Conference on Robotics and Automation, Brisbane, Australia, Australian Robotics and Automation Association, Sydney, Australia, 2007.

11.

Guo

, Iwamura

, and Koga

Towards High Accuracy Road Maps Generation from Massive GPS Trace Data. Proc., International Geo science and Remote Sensing Symposium, Barcelona, Spain, IEEE, New York, 2007, pp. 667–670.

12.

Chen

, and Cheng

Roads Digital Map Generation with Multi-Track GPS Data. Proc., International Workshop on Education Technology and Training and International Workshop on Geoscience and Remote Sensing, Shanghai, China, Vol. 1, IEEE, New York, 2008, pp. 508–511.

13.

Shi

, Shen

, and Liu

Automatic Generation of Road Network Map from Massive GPS, Vehicle Trajectories. Proc., Conference on 12th International Intelligent Transportation Systems, St. Louis, Mo., IEEE, New York, 2009, pp. 1–6.

14.

Jang

, Kim

, and Lee

Map Generation System with Lightweight GPS Trace Data. Proc., 12th International Conference on Advanced Communication Technology, Gangwon-Do, South Korea, Vol. 2, IEEE, New York, 2010, pp. 1489–1493.

15.

Naver. http://dev.naver.com/openapi/apis/map/. Accessed Nov. 14, 2011.

16.

Piegl

, and Tiller

The NURBS Book, 2nd ed. Springer-Verlag, New York, 1997.

17.

NAVTEQ Maps and Traffic. http://www.navteq.com/. Accessed July 22, 2011.

18.

Wong

S. S. M.

Computational Methods in Physics and Engineering. World Scientific, Singapore, 1997.

19.

Hastie

, and Stuetzle

Principal Curves. Technical report 151. University of Washington, Seattle, 1988.

20.

Agamennoni

, Nieto

J.I.

, and Nebot

E. M.

Technical report: Inference of Principal Road Paths Using GPS Data. Technical report. Australian Centre for Field Robotics, University of Sydney, Australia, 2010. http://www-personal.acfr.usyd.edu.au/jnieto/Research-files/PRPInferenceReport2010.

21.

Khanna

Introduction to Particle Physics. Prentice-Hall, New Delhi, India, 2004.

22.

Hastie

, Tibshirani

, and Friedman

The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, New York, 2009.

23.

Leler

W. J.

Human Vision, Anti-Aliasing, and the Cheap 4000 Line Display. Proc., 7th Annual Conference on Computer Graphics and Interactive Techniques, Seattle, Wash., Association for Computing Machinery, New York, 1980, pp. 308–313.

24.

Yokoi

, Toriwaki

, and Fukumura

An Analysis of Topological Properties of Digitized Binary Pictures Using Local Features. Computer Graphics and Image Processing, Vol. 4, No. 1, 1975, pp. 63–73.

25.

Aurenhammer

Voronoi Diagrams—A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys, Vol. 23, No. 3, 1991, pp. 345–405.

26.

Conte

, Foggia

, Sansone

, and Vento

Thirty Years of Graph Matching in Pattern Recognition. International Journal of Pattern Recognition & Artificial Intelligence, Vol. 18, No. 3, 2004, pp. 265–298.

27.

Cormen

Introduction to Algorithms. MIT Press, Cambridge, Mass., 2001.

28.

Bunke

On a Relation Between Graph Edit Distance and Maximum Common Subgraph. Pattern Recognition Letters, Vol. 18, No. 8, 1997, pp. 689–694.

29.

Liu

Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data. Springer, New York, 2007.

30.

OpenStreetMap. http://www.openstreetmap.org/. Accessed July 22, 2011.

31.

Thiagarajan

, Sivalingam

, LaCurts

, Toledo

, Eriksson

, Madden

, and Balakrishnan

Proc., 7th ACM Conference on Embedded Networked Sensor Systems, Berkeley, Calif., Association for Computing Machinery, New York, 2009, pp. 85–98.