With more and more vehicles equipped with GPS tracking devices, there is increasing interest in building and updating maps using vehicular GPS footprints or 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., 1 Hz. Typically these traces are purposely recorded by survey vehicles. In practice, however, commodity GPS devices have much 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 footprints 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 called RRA for recognizing urban roads with coarse-grained GPS footprints from probe vehicles moving in urban areas. The algorithm overcomes the challenges by pruning low quality GPS footprints, clustering GPS footprints on the same road segment and applying shape aware B-spline fitting. We have conducted empirical study with a real data set of GPS footprints and evaluation results demonstrate that our RRA algorithm achieves good performance. When there are 800 taxis and the time window for footprints collection is 2 hours, the coverage of roads for RRA is 60% and the rate of false positive is 5%, while the best alternative algorithm KDE Points can hardly recognize any road.
展开▼
