City-Scale Map Creation and Updating using GPS Collections

ABSTRACT

Applications such as autonomous driving or real-time route recommendations require up-to-date and accurate digital maps. However, manually creating and updating such maps is too costly to meet the rising demands. As large collections of GPS trajectories become widely available, constructing and updating maps using such trajectory collections can greatly reduce the cost of such maps. Unfortunately, due to GPS noise and varying trajectory sampling rates, inferring maps from GPS trajectories can be very challenging. In this paper, we present a framework to create up-to-date maps with rich knowledge from GPS trajectory collections. Starting from an unstructured GPS point cloud, we discover road segments using novel graph-based clustering techniques with prior knowledge on road design. Based on road segments, we develop a scale- and orientation-invariant traj-SIFT feature to localize and recognize junctions using a supervised learning framework. Maps with rich knowledge are created based on discovered road segments and junctions. Compared to state-of-the-art methods, our approach can efficiently construct high-quality maps at city scales from large collections of GPS trajectories.

References

1. Ahmed, M., Karagiorgou, S., Pfoser, D., and Wenk, C. (2014). A comparison and evaluation of map construction algorithms. CoRR, abs/1402.5138.
2. Ahmed, M. and Wenk, C. (2012). Constructing street networks from gps trajectories. In Epstein, L. and Ferragina, P., editors, Algorithms ESA 2012, pages 60--71.
3. Biagioni, J. and Eriksson, J. (2012a). Inferring road maps from gps traces: Survey and comparative evaluation. In Transportation Research Board, 91st Annual.
4. Biagioni, J. and Eriksson, J. (2012b). Map inference in the face of noise and disparity. ACM SIGSPATIAL '12, pages 79--88.
5. Cao, L. and Krumm, J. (2009). From gps traces to a routable road map. ACM SIGSPATIAL '09, pages 3--12.
6. Chang, C.-C. and Lin, C.-J. (2011). LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology.
7. Chen, D., Guibas, L. J., Hershberger, J., and Sun, J. (2010). Road network reconstruction for organizing paths. SODA '10, pages 1309--1320.
8. Davies, J., Beresford, A., and Hopper, A. (2006). Scalable, distributed, real-time map generation. Pervasive Computing, IEEE, 5(4):47--54.
9. Edelkamp, S. and Schrödl, S. (2003). Computer Science in Perspective: Essays Dedicated to Thomas Ottmann, pages 128--151. Springer Berlin Heidelberg, Berlin, Heidelberg.
10. Eppstein, D. and Goodrich, M. T. (2008). Studying (non-planar) road networks through an algorithmic lens. ACM SIGSPATIAL '08.
11. Fathi, A. and Krumm, J. (2010). Detecting road intersections from gps traces. GIScience'10, pages 56--69, Berlin, Heidelberg.
12. Goh, C., Dauwels, J., Mitrovic, N., Asif, M., Oran, A., and Jaillet, P. (2012). Online map-matching based on hidden markov model for real-time traffic sensing applications. In ITSC, pages 776--781.
13. HERE 360 (2015). the official here blog. http://360.here.com/2015/06/04/what-do-android-ios-and-wp-here-maps-update/.
14. Kaplan, E. and Hegarty, C. (2006). Understanding GPS: Principles and Applications. Artech House mobile communications series.
15. Liu, C., Zhang, K., Xiong, H., Jiang, G., and Yang, Q. (2014). Temporal skeletonization on sequential data: Patterns, categorization, and visualization. KDD '14, pages 1336--1345.
16. Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. Int. J. Comput. Vision, 60(2):91--110.
17. OpenStreetMap (2016). http://openstreetmap.org.
18. Wang, S., Wang, Y., and Li, Y. (2015a). Efficient map reconstruction and augmentation via topological methods. In Proceedings of the 23th International Conference on Advances in Geographic Information Systems.
19. Wang, Y., Yuan, N. J., Lian, D., Xu, L., Xie, X., Chen, E., and Rui, Y. (2015b). Regularity and conformity: Location prediction using heterogeneous mobility data. KDD '15, pages 1275--1284. ACM.
20. Wang, Y., Zheng, Y., and Xue, Y. (2014). Travel time estimation of a path using sparse trajectories. In KDD '14. ACM.
21. Wei, L.-Y., Zheng, Y., and Peng, W.-C. (2012). Constructing popular routes from uncertain trajectories. KDD '12. ACM.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Supervised learning

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry