An Automatic Road Network Construction Method Using Massive GPS Trajectory Data
<p>The framework of the map auto-construction method. First, a constraint rule-based trajectory data preprocessing algorithm is used to remove noise, which includes a time threshold, space threshold, logic threshold, and redundancy elimination. Second, a road network construction algorithm is used to generate a digital map using processes of trajectory point clustering, trajectory direction estimation, and average speed calculation. Third, the performance of the method is examined by comparing the constructed map with the OpenStreetMap and calculating the F-score for comparison with typical existing methods.</p> "> Figure 2
<p>Road network construction process diagram. (<b>a</b>) The first trip is inserted, (<b>b</b>) the second trajectory is inserted and integrated with existing nodes, and (<b>c</b>) the third trip is inserted and the merging method is used according to the position of the point that is being inserted.</p> "> Figure 3
<p>Schematic of merging a point into an existing road network.</p> "> Figure 4
<p>Schematic for splitting a candidate edge into two more detailed edges.</p> "> Figure 5
<p>Schematic for determining a complex road network.</p> "> Figure 6
<p>Base map and snapshots for the preprocessing trajectory data from Beijing. (<b>a</b>) A base map from OpenStreetMap. (<b>b</b>) A visualization of 5.76 million raw trajectory data points using OpenCV. (<b>c</b>) A visualization of those trajectory data after time filter 0 s < Δt < 600 s. (<b>d</b>) A visualization of the trajectory data after preprocessing. As shown in the picture, our preprocessing algorithm can effectually remove noise.</p> "> Figure 7
<p>A detailed look at the processed trajectories. (<b>a</b>) A subarea of the base map from OSM, and (<b>b</b>) a snapshot of the processed trajectory. As shown in (<b>b</b>), there are many messy lines around road intersections, which require further processing to extract the real roads.</p> "> Figure 8
<p>Comparison of the constructed road network with the ground truth. The result is overlaid onto OpenStreetMap, which shows that the resulting map matches the base map very well. (<b>a</b>) The overall scenario; the constructed road network is represented as a green graph. (<b>b</b>) One subset area of the constructed road network in detail; the directions of the roads are expressed using black arrows.</p> "> Figure 9
<p>Comparison of the F-scores of our method vs existing methods using different matching thresholds during geometry sampling.</p> ">
Abstract
:1. Introduction
2. Literature Review
3. Methodology
3.1. Data Preprocessing Algorithm
- (1)
- If the time interval between two consecutive positioning measurements is Δt ≥ 600 s, then the trip is split into different trips. We chose 600 s as our threshold value because we found in analyzing all the time intervals between any two continuous position records in our experimental data that 93.97% of the time intervals are shorter than 90 s, 4.26% are longer than 600 s, and 2.04% are between 90 s and 600 s. A vehicle can travel a long distance in intervals that are longer than 600 s when the vehicle runs at a high speed, which can result in noise if we directly connect the initial and final positions for the time interval. We chose 600 s as the threshold to eliminate the 4.26% of edges that might be long-distance edges.
- (2)
- If the distance between two locations is Δd1 ≥ 2000 m, the trajectory is split into different trips. For our experimental data, the sampling interval of the experimental trajectory data is 90 s. We chose 2000 m as our threshold value because the maximum length between two consecutive points is 1980 m by precise calculation, as described above, and we loosen slightly the threshold.
- (3)
- If the maximum value of the distance between any two nodes in a trip is Δd2 < 200 m, the trip is deleted. We chose 200 m as our threshold value because we found that some trips in the experimental data involve roaming around small areas and the radii of these areas are less than 200 m. These areas may be informal car parks or gas stations. These trips do not contribute to the construction of the road network, but we can use them to extract POIs along the road in future work.
- (4)
- If two consecutive points are in the same position (here, if the distance between two points Δd3 < 5 m, we regard their locations as the same), only the first point in the trip is kept. In this way, we can eliminate data redundancy.
- (5)
- If the number of points in a trip, which is denoted by L, is less than 50, then the trip is deleted. In this way, we can eliminate certain invalid trips and speed up the processing. We chose 50 as the threshold because only 18% of all trips have greater than 50 points, but these contain approximately 80% of all positioning points.
Algorithm 1 Preprocessing raw trajectory data |
Input: Raw GPS trajectory data set C |
Output: Cleaned trajectory dataset T |
T = ∅; |
For each point in C do |
Trip = null; |
If distance interval between point and its previous point Δd1 < 5 m, then |
Continue; |
End if |
If time interval between point and its previous point Δt ≥ 600 s or Δt < 0 s or Δd1 ≥ 2000 m, then |
If length of the trip L < 50 then |
Trip = null; |
Continue; |
End if |
If maximum distance between any two points in a Trip Δd2 < 200 m, then |
Trip = null; |
Continue; |
End if |
Add Trip to T; |
End if |
Add point to Trip |
End For |
3.2. Road Network Construction Algorithm
Algorithm 2 Road network construction from dataset of trips |
Input: Dataset T after preprocessing of raw trajectory data |
Output: Directed graph G representing road network |
G = ∅; |
For each trip t in T do |
prevNode = null; |
For each node n in trips t do |
If n should be merged with the existing edge e G, then |
If n is near the complex road network then |
Split_threshold d = intersection_threshold |
Else: |
Split_threshold d = normal_threshold |
End if |
If short_projection_distance > d, then |
Add n to G, split the segment e by n, add the corresponding split_segment |
edges (i.e., in_node of e → n and n → out_node of e) to G |
Else: |
merge n with nearest graph node v G |
update the location of node v by considering the effect of n |
End if |
If prevNode ≠ null and there is no path in G from prevNode to n within less than 5 |
hops, then |
Add edge(prevNode → n) to G |
prevNode = n; |
End if |
Else |
Add node n to G; |
If prevNode ≠ null, then |
Add edge(prevNode → n) to G |
prevNode = n; |
End if |
End for |
End for |
4. Results of the Case Study of Beijing, China
4.1. Introduction of GPS Trajectory Data and Ground-Truth Map
4.2. Experiment Results and Discussion
- (1)
- Certain roads appear on the reference base map but not on the constructed map. This discrepancy occurs because the degree of overlay of the GPS trajectory data is limited, which means the experimental trajectory cannot reflect all the roads, especially certain footways through which vehicles cannot pass. Moreover, the experimental data are old; therefore, the constructed map does not reflect newly constructed roads.
- (2)
- The constructed map is more “dentate” than the reference base map because the density of points in the constructed road is too high. The density can be reduced by using a high splitting threshold value, although this shortcoming cannot be completely eliminated. A future research topic could be the further smoothing of the line segments.
- (3)
- The constructed map recognizes the overpass as an intersection because we model the road network as a planar graph. The precise extraction of information about complicated road networks, such as overpasses and intersections, could be further studied in the future.
- (4)
- There are many messy edges near complex roads, which do not reflect the intersections’ actual situations. It is difficult to extract a directly usable road network using an automatic method because of the inherent positioning error of GPS and the complexity of the roads. In the future, we may try to determine the rough shape of the intersection or train certain intersection models to alleviate the problem.
- (5)
- In some instances, adjacent intersections have merged into one because those roads are too close to each other. The problem can be addressed by adjusting the parameters of the projection distance Δh.
5. Conclusions and Future Work
Acknowledgments
Author Contributions
Conflicts of Interest
References
- El-Sheimy, N.; Schwarz, K.P. Navigating urban areas by VISAT—A mobile mapping system integrating GPS/INS/digital cameras for GIS applications. Navigation 1998, 45, 275–285. [Google Scholar] [CrossRef]
- Sghaier, M.O.; Lepage, R. Road Extraction From Very High Resolution Remote Sensing Optical Images Based on Texture Analysis and Beamlet Transform. IEEE J. Sel. Top. Appl. Earth Obs. Remote Sens. 2016, 9, 1946–1958. [Google Scholar] [CrossRef]
- Yuan, J.; Cheriyadat, A.M. Image driven GPS trace analysis for road map inference. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Orlando, FL, USA, 5–8 November 2013; pp. 480–483. [Google Scholar]
- Goodchild, M.F. Citizens as sensors: The world of volunteered geography. GeoJournal 2007, 69, 211–221. [Google Scholar] [CrossRef]
- Li, H.; Kulik, L.; Ramamohanarao, K. 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, Indianapolis, IN, USA, 24–28 October 2016; pp. 1523–1532. [Google Scholar]
- Qiu, J.; Wang, R. Road Map Inference: A Segmentation and Grouping Framework. ISPRS Int. J. Geo-Inf. 2016, 5, 130. [Google Scholar] [CrossRef]
- Zhou, Y.; Zhang, Y.; Ge, Y.; Xue, Z.; Fu, Y.; Guo, D.; Shao, J.; Zhu, T.; Wang, X.; Li, J. An efficient data processing framework for mining the massive trajectory of moving objects. Comput. Environ. Urban Syst. 2015, 61, 129–140. [Google Scholar] [CrossRef]
- Jiang, S.; Fiore, G.A.; Yang, Y.; Ferreira, J., Jr.; Frazzoli, E.; González, M.C. A review of urban computing for mobile phone traces: Current methods, challenges and opportunities. In Proceedings of the 2nd ACM SIGKDD International Workshop on Urban Computing, Chicago, IL, USA, 11 August 2013; p. 2. [Google Scholar]
- Woodard, D.; Nogin, G.; Koch, P.; Racz, D.; Goldszmidt, M.; Horvitz, E. Predicting travel time reliability using mobile phone GPS data. Transp. Res. Part C Emerg. Technol. 2017, 75, 30–44. [Google Scholar] [CrossRef]
- Kuntzsch, C.; Sester, M.; Brenner, C. Generative models for road network reconstruction. Int. J. Geogr. Inf. Sci. 2016, 30, 1012–1039. [Google Scholar] [CrossRef]
- Fang, W.; Hu, R.; Xu, X.; Xia, Y.; Hung, M.-H. A novel road network change detection algorithm based on floating car tracking data. Telecommun. Syst. 2016, 1–7. [Google Scholar] [CrossRef]
- Gonzalez, M.C.; Hidalgo, C.A.; Barabasi, A.-L. Understanding individual human mobility patterns. Nature 2008, 453, 779–782. [Google Scholar] [CrossRef] [PubMed]
- Kong, X.; Xu, Z.; Shen, G.; Wang, J.; Yang, Q.; Zhang, B. Urban traffic congestion estimation and prediction based on floating car trajectory data. Future Gener. Comput. Syst. 2016, 61, 97–107. [Google Scholar] [CrossRef]
- Tang, L.; Yang, X.; Kan, Z.; Li, Q. Lane-Level Road Information Mining from Vehicle GPS Trajectories Based on Naïve Bayesian Classification. ISPRS Int. J. Geo-Inf. 2015, 4, 2660–2680. [Google Scholar] [CrossRef]
- Zhou, Y.; Fang, Z.; Thill, J.-C.; Li, Q.; Li, Y. Functionally critical locations in an urban transportation network: Identification and space–time analysis using taxi trajectories. Comput. Environ. Urban Syst. 2015, 52, 34–47. [Google Scholar] [CrossRef]
- Li, H.; Kulik, L.; Ramamohanarao, K. Robust inferences of travel paths from GPS trajectories. Int. J. Geogr. Inf. Sci. 2015, 29, 2194–2222. [Google Scholar] [CrossRef]
- Qiu, J.; Wang, R. Inferring road maps from sparsely sampled GPS traces. J. Locat. Based Serv. 2016, 10, 111–124. [Google Scholar] [CrossRef]
- Ahmed, M.; Karagiorgou, S.; Pfoser, D.; Wenk, C. A comparison and evaluation of map construction algorithms using vehicle tracking data. GeoInformatica 2015, 19, 601–632. [Google Scholar] [CrossRef]
- Biagioni, J.; Eriksson, J. Map inference in the face of noise and disparity. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems, Redondo Beach, CA, USA, 6–9 November 2012; pp. 79–88. [Google Scholar]
- Davics, J.; Beresford, A.R.; Hopper, A. Scalable, distributed, real-time map generation. IEEE Pervasive Comput. 2006, 5, 47–54. [Google Scholar]
- Liu, X.; Biagioni, J.; Eriksson, J.; Wang, Y.; Forman, G.; Zhu, Y. 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, Beijing, China, 12–16 August 2012; pp. 669–677. [Google Scholar]
- Ahmed, M.; Wenk, C. Constructing street networks from GPS trajectories. In Algorithms–ESA 2012; Springer: Berlin/Heidelberg, Germany, 2012; pp. 60–71. [Google Scholar]
- Cao, L.; Krumm, J. From GPS traces to a routable road map. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, WA, USA, 4–6 November 2009; pp. 3–12. [Google Scholar]
- Ekpenyong, F.; Palmer-Brown, D.; Brimicombe, A. Extracting road information from recorded GPS data using snap-drift neural network. Neurocomputing 2009, 73, 24–36. [Google Scholar] [CrossRef]
- Niehöfer, B.; Burda, R.; Wietfeld, C.; Bauer, F.; Lueert, O. GPS community map generation for enhanced routing methods based on trace-collection by mobile phones. In Proceedings of the First International Conference on Advances in Satellite and Space Communications SPACOMM 2009, Colmar, France, 20–25 July 2009; pp. 156–161. [Google Scholar]
- Rogers, S.; Langley, P.; Wilson, C. Mining GPS data to augment road models. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, 15–18 August 1999; pp. 104–113. [Google Scholar]
- Xie, X.; Liao, W.; Aghajan, H.; Veelaert, P.; Philips, W. Detecting Road Intersections from GPS Traces Using Longest Common Subsequence Algorithm. ISPRS Int. J. Geo-Inf. 2016, 6, 1. [Google Scholar] [CrossRef]
- Karagiorgou, S.; Pfoser, D. On vehicle tracking data-based road network generation. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems, Redondo Beach, CA, USA, 6–9 November 2012; pp. 89–98. [Google Scholar]
- Fathi, A.; Krumm, J. Detecting road intersections from GPS traces. In Geographic Information Science; Springer: Berlin/Heidelberg, Germany, 2010; pp. 56–69. [Google Scholar]
- Biagioni, J.; Eriksson, J. Inferring Road Maps from Global Positioning System Traces Survey and Comparative Evaluation. Transp. Res. Rec. 2012, 2291, 61–71. [Google Scholar] [CrossRef]
- Edelkamp, S.; Schrodl, S. Route planning and map inference with global positioning traces. Comput. Sci. Perspect. 2003, 2598, 128–151. [Google Scholar]
- Zhang, L.; Thiemann, F.; Sester, M. Integration of GPS traces with road map. In Proceedings of the Second International Workshop on Computational Transportation Science, San Jose, CA, USA, 2 November 2010; pp. 17–22. [Google Scholar]
Algorithm Category | Representative Algorithms |
---|---|
Point clustering | Biagioni and Eriksson [19], Davies et al. [20], Edelkamp and Schrodl [31] |
Incremental trace insertion | Cao and Krumm [23], Ahmed and Wenk [22], Rogers and Langley [26], Zhang and Thiemann [32] |
Intersection linking | Karagiorgou and Pfoser [28], Fathi and Krumm [29] |
Vehicle ID | Time | Longitude | Latitude | Speed (m/s) | Direction (degree) |
---|---|---|---|---|---|
756,945 | 2012–11–30 19:17:05 | 116.4433975 | 39.9258118 | 26.00 | 170 |
… | … | … | … | … | … |
757,255 | 2012–11–30 19:23:05 | 116.4288635 | 39.9076500 | 2.00 | 208 |
757,255 | 2012–11–30 19:34:35 | 116.4233017 | 39.9000549 | 15.00 | 265 |
Property | Value |
---|---|
Number of nodes | 109,324 |
Number of road segments | 157,755 |
Average length of a road segment | 1380.12 m |
Average road speed | 8.32 km/h |
© 2017 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
Share and Cite
Zhang, Y.; Liu, J.; Qian, X.; Qiu, A.; Zhang, F. An Automatic Road Network Construction Method Using Massive GPS Trajectory Data. ISPRS Int. J. Geo-Inf. 2017, 6, 400. https://doi.org/10.3390/ijgi6120400
Zhang Y, Liu J, Qian X, Qiu A, Zhang F. An Automatic Road Network Construction Method Using Massive GPS Trajectory Data. ISPRS International Journal of Geo-Information. 2017; 6(12):400. https://doi.org/10.3390/ijgi6120400
Chicago/Turabian StyleZhang, Yongchuan, Jiping Liu, Xinlin Qian, Agen Qiu, and Fuhao Zhang. 2017. "An Automatic Road Network Construction Method Using Massive GPS Trajectory Data" ISPRS International Journal of Geo-Information 6, no. 12: 400. https://doi.org/10.3390/ijgi6120400
APA StyleZhang, Y., Liu, J., Qian, X., Qiu, A., & Zhang, F. (2017). An Automatic Road Network Construction Method Using Massive GPS Trajectory Data. ISPRS International Journal of Geo-Information, 6(12), 400. https://doi.org/10.3390/ijgi6120400