Road recognition using coarse-grained vehicular traces

With more and more vehicles equipped with GPS tracking devices, there is increasing interest in building and updating maps using vehicular GPS traces. Most existing approaches for building maps rely on position traces from highly accurate positioning devices, which are sampled at a high frequency, e.g., every second. Typically these traces are recorded by survey vehicles. Commodity GPS devices are much more widespread, but have lower accuracy. In addition, the sampling frequency is low (at around once per minute) in order to reduce communication cost. Building maps from coarse-grained vehicular GPS traces is challenging due to the inherent noise in commodity GPS devices and the shape complexity of urban roads. In this paper, we propose a novel algorithm for recognizing urban roads with coarsegrained GPS traces from probe vehicles moving in urban areas. The algorithm overcomes the challenges by pruning low quality GPS traces, clustering GPS traces by road segments, and applying shape-aware B-spline fitting. We have conducted empirical study with a real data set of GPS traces from 2,300 taxis in Shanghai, China. Evaluation results demonstrate that our algorithm provides wide coverage, a low rate of false positives, and high accuracy. When there are 2,000 taxis and the time window for trace collection is 1.5 hours, the coverage of arterial roads is 93% and the rate of false positives is 5%. The roads recognized by our algorithm are more accurate than the roads on OpenStreetMap, a popular map editing website using GPS traces and satellite imagery.