research-article

Road Map Generation and Feature Extraction from GPS Trajectories Data

Authors:

Mousa Almotairi,

Bader AlshemaimriAuthors Info & Claims

IWCTS'19: Proceedings of the 12th ACM SIGSPATIAL International Workshop on Computational Transportation Science

Article No.: 2, Pages 1 - 10

https://doi.org/10.1145/3357000.3366140

Published: 05 November 2019 Publication History

Abstract

Road maps are important in our personal lives and are widely used in many different applications. Therefore, an up-to-date road map is essential. The huge amount of GPS data collected from moving objects provides an opportunity to generate an up-to-date road map. In this paper, we propose a novel method to generate road maps using GPS trajectories that is accurate with good coverage area, has a minimum number of vertices and edges, and several details of the road network. Our algorithm starts by identifying the locations of intersections using a line simplification algorithm with spatial-constraints and grid-based method. Then, it creates graph connectivity information to connect intersections and build road segments. In addition, our algorithm extracts road features such as turn restrictions, average speed, road length, road type, and the number of cars traveling in a specific portion of the road. To demonstrate the accuracy of our proposed algorithm, we conduct experiments using two real data sets and compare our results with two baseline methods. The comparisons indicate that our algorithm is able to achieve higher F-score in terms of accuracy and generates a detailed road map that is not overly complex.

References

[1]

Mahmuda Ahmed, Sophia Karagiorgou, Dieter Pfoser, and Carola Wenk. 2015. A comparison and evaluation of map construction algorithms using vehicle tracking data. GeoInformatica 19, 3 (01 Jul 2015), 601--632. https://doi.org/10.1007/s10707-014-0222-6

[2]

Mahmuda Ahmed and Carola Wenk. 2012. Constructing Street Networks from GPS Trajectories. In Proceedings of the 20th Annual European Conference on Algorithms (ESA'12). Springer-Verlag, Berlin, Heidelberg, 60--71. https://doi.org/10.1007/978-3-642-33090-2_7

Digital Library

[3]

James Biagioni and Jakob Eriksson. 2012. Inferring Road Maps from Global Positioning System Traces: Survey and Comparative Evaluation. Transportation Research Record 2291, 1 (2012), 61--71. https://doi.org/10.3141/2291-08arXiv:https://doi.org/10.3141/2291-08

[4]

James Biagioni and Jakob Eriksson. 2012. Map Inference in the Face of Noise and Disparity. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems (SIGSPATIAL '12). ACM, New York, NY, USA, 79--88. https://doi.org/10.1145/2424321.2424333

Digital Library

[5]

Kevin Buchin, Maike Buchin, David Duran, Brittany Terese Fasy, Roel Jacobs, Vera Sacristan, Rodrigo I. Silveira, Frank Staals, and Carola Wenk. 2017. Clustering Trajectories for Map Construction. In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL '17). ACM, New York, NY, USA, Article 14, 10 pages. https://doi.org/10.1145/3139958.3139964

Digital Library

[6]

Lili Cao and John Krumm. 2009. From GPS Traces to a Routable Road Map. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS '09). ACM, New York, NY, USA, 3--12. https://doi.org/10.1145/1653771.1653776

Digital Library

[7]

Chen Chen, Cewu Lu, Qixing Huang, Qiang Yang, Dimitrios Gunopulos, and Leonidas Guibas. 2016. City-Scale Map Creation and Updating Using GPS Collections. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '16). ACM, New York, NY, USA, 1465--1474. https://doi.org/10.1145/2939672.2939833

Digital Library

[8]

Sina Dabiri and Kevin Heaslip. 2018. Inferring transportation modes from GPS trajectories using a convolutional neural network. Transportation Research Part C: Emerging Technologies 86 (2018), 360--371. https://doi.org/10.1016/j.trc.2017.11.021

[9]

Douglas, David H, Peucker, and Thomas K. 1973. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: the international journal for geographic information and geovisualization 10, 2 (1973), 112--122.

[10]

Mahmoud Ezzat, Mahmoud Sakr, Rania Elgohary, and Mohammed Essam Khalifa. 2018. Building road segments and detecting turns from GPS tracks. Journal of Computational Science 29 (2018), 81--93. https://doi.org/10.1016/j.jocs.2018.09.011

[11]

Alireza Fathi and John Krumm. 2010. Detecting Road Intersections from GPS Traces. In Geographic Information Science, Sara Irina Fabrikant, Tumasch Reichenbacher, Marc van Kreveld, and Christoph Schlieder (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 56--69.

[12]

J. Huang, M. Deng, J. Tang, S. Hu, H. Liu, S. Wariyo, and J. He. 2018. Automatic Generation of Road Maps from Low Quality GPS Trajectory Data via Structure Learning. IEEE Access 6 (2018), 71965--71975. https://doi.org/10.1109/ACCESS.2018.2882581

[13]

Sophia Karagiorgou and Dieter Pfoser. 2012. On Vehicle Tracking Data-based Road Network Generation. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems (SIGSPATIAL '12). ACM, New York, NY, USA, 89--98. https://doi.org/10.1145/2424321.2424334

Digital Library

[14]

Sophia Karagiorgou, Dieter Pfoser, and Dimitrios Skoutas. 2013. Segmentation-based Road Network Construction. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL '13). ACM, New York, NY, USA, 460--463.

Digital Library

[15]

Hengfeng Li, Lars Kulik, and Kotagiri Ramamohanarao. 2016. Automatic Generation and Validation of Road Maps from GPS Trajectory Data Sets. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management (CIKM '16). ACM, New York, NY, USA, 1523--1532. https://doi.org/10.1145/2983323.2983797

Digital Library

[16]

Xuemei Liu, James Biagioni, Jakob Eriksson, Yin Wang, George Forman, and Yanmin Zhu. 2012. Mining Large-scale, Sparse GPS Traces for Map Inference: Comparison of Approaches. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '12). ACM, New York, NY, USA, 669--677. https://doi.org/10.1145/2339530.2339637

Digital Library

[17]

B. Niehöfer, R. Burda, C. Wietfeld, F. Bauer, and O. Lueert. 2009. GPS Community Map Generation for Enhanced Routing Methods Based on Trace-Collection by Mobile Phones. In 2009 First International Conference on Advances in Satellite and Space Communications. 156--161. https://doi.org/10.1109/SPACOMM.2009.31

[18]

OpenStreetMap. 2013. http://www.openstreetmap.org

[19]

Haizhong Qian and Yongmei Lu. 2017. Simplifying GPS Trajectory Data with Enhanced Spatial-Temporal Constraints. ISPRS International Journal of Geo-Information 6, 11 (2017). http://www.mdpi.com/2220-9964/6/11/329

[20]

Roger W Sinnott. 1984. Virtues of the Haversine. Sky and Telescope 68 (1984), 159.

[21]

Albert Steiner and Axel Leonhardt. 2011. Map generation algorithm using low-frequency vehicle position data. In TRB 90th Annual Meeting of the Transportation Research Board. Transportation Research Board, 1--17.

[22]

Stewart Worrall and Eduardo Nebot. 2007. Automated Process for Generating Digitised Maps through GPS Data Compression. (01 2007).

[23]

Xingzhe Xie, Wenzhi Liao, Hamid Aghajan, Peter Veelaert, and Wilfried Philips. 2017. Detecting Road Intersections from GPS Traces Using Longest Common Subsequence Algorithm. ISPRS International Journal of Geo-Information 6, 1 (2017). https://doi.org/10.3390/ijgi6010001

Cited By

He QXiao ZHuang ZYuan HSun L(2024)Orientation-Aware Multi-Modal Learning for Road Intersection Identification and Mapping2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10610015(16185-16191)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10610015
Stienen Vden Hertog DWagenaar Jde Zegher J(2024)Enhancing digital road networks for better transportation in developing countriesTransportation Research Interdisciplinary Perspectives10.1016/j.trip.2024.10121727(101217)Online publication date: Sep-2024
https://doi.org/10.1016/j.trip.2024.101217
Sasaki IArikawa MLu MSato R(2023)Mobile Collaborative Heatmapping to Infer Self-Guided Walking Tourists’ Preferences for GeomediaISPRS International Journal of Geo-Information10.3390/ijgi1207028312:7(283)Online publication date: 15-Jul-2023
https://doi.org/10.3390/ijgi12070283
Show More Cited By

Index Terms

Road Map Generation and Feature Extraction from GPS Trajectories Data
1. Information systems
  1. Information systems applications
    1. Spatial-temporal systems
      1. Geographic information systems
      2. Global positioning systems

Recommendations

MPRG: A Method for Parallel Road Generation Based on Trajectories of Multiple Types of Vehicles
Advances in Knowledge Discovery and Data Mining
Abstract
Accurate and up-to-date digital road maps are the foundation of many applications, such as navigation and autonomous driving. Recently, the ubiquity of GPS devices in vehicular systems has led to an unprecedented amount of vehicle sensing data for ...
Virtual running model for locating road intersections using GPS trajectory data
IMCOM '17: Proceedings of the 11th International Conference on Ubiquitous Information Management and Communication

Map construction from vehicle trajectories has been an active challenge topic due to the progress of positioning technologies and high cost of map constructions since last decades. In our work, we focus on road network generation from a massive GPS data ...
Estimating the Number of Lanes on Rapid Road Map Survey System Using GPS Trajectories as Collective Intelligence
NBIS '12: Proceedings of the 2012 15th International Conference on Network-Based Information Systems

Electronic maps on current car navigation system is updated after surveying works, generating and editing map data when a road is newly opened to traffic. Therefore, long time is needed to update the map is completed. Also, online map updating service ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

IWCTS'19: Proceedings of the 12th ACM SIGSPATIAL International Workshop on Computational Transportation Science

November 2019

89 pages

ISBN:9781450369671

DOI:10.1145/3357000

Editors:
Gautam Thakur
Oak Ridge National Laboratory, TN, USA
,
Jibonananda Sanyal
Oak Ridge National Laboratory, TN, USA

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSPATIAL: ACM Special Interest Group on Spatial Information

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

SIGSPATIAL '19

Sponsor:

SIGSPATIAL

SIGSPATIAL '19: 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 5, 2019

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 42 of 57 submissions, 74%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
331
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)9

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

He QXiao ZHuang ZYuan HSun L(2024)Orientation-Aware Multi-Modal Learning for Road Intersection Identification and Mapping2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10610015(16185-16191)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10610015
Stienen Vden Hertog DWagenaar Jde Zegher J(2024)Enhancing digital road networks for better transportation in developing countriesTransportation Research Interdisciplinary Perspectives10.1016/j.trip.2024.10121727(101217)Online publication date: Sep-2024
https://doi.org/10.1016/j.trip.2024.101217
Sasaki IArikawa MLu MSato R(2023)Mobile Collaborative Heatmapping to Infer Self-Guided Walking Tourists’ Preferences for GeomediaISPRS International Journal of Geo-Information10.3390/ijgi1207028312:7(283)Online publication date: 15-Jul-2023
https://doi.org/10.3390/ijgi12070283
Dax GWerner M(2021)Trajectory Similarity using Compression2021 22nd IEEE International Conference on Mobile Data Management (MDM)10.1109/MDM52706.2021.00035(169-174)Online publication date: Jun-2021
https://doi.org/10.1109/MDM52706.2021.00035

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents