Road Map Generation and Feature Extraction from GPS Trajectories Data

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.