Inferring road maps from sparsely sampled GPS traces

We propose a novel segmentation-and-grouping framework for road map inference from sparsely sampled GPS traces. First, we extend Density-Based Spatial Clustering of Application with Noise with an orientation constraint to partition the entire point set of the traces into point clusters representing the road segments. Second, we propose an adaptive k-means algorithm that the k value is determined by an angle threshold to reconstruct nearly straight line segments. Third, the line segments are grouped according to the ‘Good Continuity’ principle of Gestalt Law to form a ‘Stroke’ for recovering the road map. Experimental results demonstrate that our algorithm is robust to noises and sampling rates. In comparison with previous work, our method has advantages to infer road maps from sparsely sampled GPS traces.