Technical Reports

HPL-2012-26

Click here for full text: PDF

Road Recognition using Coarse-grained Vehicular Traces

Liu, Xuemei; Zhu, Yanmin; Wang, Yin; Forman, George; Ni, Lionel M.; Fang Yu; Li Minglu
HP Laboratories

HPL-2012-26

Keyword(s): map building; GPS; road recognition

Abstract: 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 coarse-grained 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.

10 Pages

External Posting Date: February 21, 2012 [Fulltext]. Approved for External Publication
Internal Posting Date: February 21, 2012 [Fulltext]

Back to Index