Building road segments and detecting turns from GPS tracks

With the wide spreading of geo-aware mobile applications, huge amounts of user-contributed GPS trajectories become available with different levels of accuracy. Constructing road maps from such datasets is one important benefit from this data, and it is required for many applications. There are some challenges related to the inaccuracies incurred on real datasets, such as missing GPS signals, low sampling rate and bad driving behaviour. In this paper, we present a new preprocessing algorithm to address the problems of GPS data. Additionally, we present a clustering-based technique to extract the road map from GPS tracks. Firstly, the tracks are simplified in order to extract road turns and remove the noise data. Then, we adjust the points of the simplified tracks to solve the problems caused by the low sampling rate by moving them closer to the positions of the real turns. Afterwards, a progressive clustering is applied to extract turns and intersections. Finally, we connect them to build the road segments. To ensure the accuracy of our results, we compare the proposed technique with two of the best state-of-the-art methods using a small-scale dataset with inconsistent sampling rate. Another experiment is conducted by extracting a part of the road segments of Egypt using a large-scale dataset with more than 12 million GPS points that are captured with high sampling rate. Experimental results show that our proposed technique exceeds the other methods with regard to F-measure.