CellNet: Inferring road networks from GPS trajectories

Abstract
In recent years, navigation and location based services (LBS) have seen a rise in development. For these applications to work reliably, it is important to have an up-to-date road network. We propose an automatic method to generate the road network using a GPS trajectory dataset. The method, entitled CellNet, works by first detecting the intersections (junctions) using a clustering-based technique and then creates the road segments in-between.

Datasets
We tested CellNet on the following datasets (click to download):

Ground truth for the two datasets was extracted from Open Street Map by manually selecting the segments where data is available (click to download):

Joensuu contains tracks of a single user (Pasi) from Mopsi collection during 16.11.2014 - 25.4.2015. This collection includes 102 routes in total but we extract only the 45 that are in Joensuu area by cropping the data to a square region covering most of downtown. Joensuu contains straight perpendicular roads in the center and more complex, curvy roads on the borders. The later are walking and cycling paths. The routes in Joensuu are collected while jogging, usually on the sides of the streets.
Chicago dataset was made publically available by Biagioni and Eriksson [2012]. It contains 889 routes of the campus shuttles in the University of Illinois at Chicago. The shuttles pass through major streets of the city. There are two areas that contain tall buildings which affect the GPS precision.

More statistics are given bellow:

	Joensuu	Chicago
Routes	109	889
Points	43,891	118,237
Total Length (km)	252	2,869
Average speed (km/h)	9.1	33.1
Median sampling rate (s)	2	4
Intersections	228	52
Road segments	357	76
Points per segment (average)	4.8	6.6
Area (km²)	2.8 × 2.2	4.5 × 2.5
Network Length (km)	55	61

Comparison
We evaluated CellNet and four other methods on their ability to extract intersections and road segments on the two datasets. The thumbnails bellow are links to an interactive evaluation tool. All these outputs can be also downloaded here.

1. CellNet

2. Jonathan Davies, Alastair R. Beresford and Andy Hopper. 2006. Scalable, distributed, real-time map generation. IEEE Pervasive Computing, 5(4), pp. 47-54.

3. Stefan Edelkamp and Stefan Schrödl. 2003. Route planning and map inference with global positioning traces. In Computer Science in Perspective, pp. 128-151.

4. Lili Cao and John Krumm. 2009. From GPS traces to a routable road map. In Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems, Seattle, Washington, USA, pp. 3-12.

5. James Biagioni and Jakob Eriksson. Map inference in the face of noise and disparity (2012). ACM SIGSPATIAL, 79-88.

Disclaimer: The data might contain copyrighted material and should not be used for any purpose other than data analysis for scientific research.

References:
James Biagioni and Jakob Eriksson. 2012. Inferring road maps from global positioning system traces: Survey and comparative evaluation. Transportation Research Record: Journal of the Transportation Research Board, (2291), pp. 61-71.

Related links
Mapconstruction website
Software and data provided by the University of Illinois at Chicago