MAPSTER

Overview

Creating and maintaining maps is both expensive and labor-intensive. As a result, maps often have poor coverage, or contain outdated information. For example, many villages in Indonesia are not covered by street maps. Below, the closest mapped roads (bottom, in black) to a village may be miles away:

Additionally, street map metadata, such as the number of lanes, speed limits, turn restrictions, and the positions of crosswalks and parking spaces, is often poor quality or completely missing. This metadata is crucial for navigation applications and autonomous vehicles.

Our goal in the Mapster project was to leverage GPS trajectories, satellite and aerial imagery, drone imagery, and other data sources to improve the accuracy and coverage of maps, and to reduce the delay between physical road network changes and updates to the map.

For a summary of all of our work, see our article in Communications of the ACM.

Projects

Capturing Road Topology

In many countries, street maps have poor coverage outside urban centers, and exhibit a long delay between road network modifications and map updates. By leveraging satellite imagery and GPS trajectories, we can automatically infer the road topology on a large-scale, thereby reducing the cost of tracing roads by hand. To this end, we developed RoadTracer, RoadRunner, and Sat2Graph.

RoadTracer infers road topology from satellite imagery via an iterative graph construction process for extracting graph structures from images. The road network is constructed by adding individual road segments one at a time, using a CNN to decide on the next segment to add given the portion of the road network constructed so far.

RoadRunner constructs road network maps from GPS trajectories via a highly accurate two-stage method. In the first stage, a novel approach generates a high precision map by incrementally following the flow of trajectories, using the connectivity between observations in each trajectory to correctly infer road segment connectivity. In the second stage, roads inferred by existing methods are merged into the map to improve recall without sacrificing precision.

Existing imagery-based road graph extraction solutions fall into two categories: (1) pixelwise segmentation-based approaches, which predict whether each pixel is on a road, and (2) graph-based approaches, which predict the road graph iteratively. We find that these two approaches have complementary strengths while suffering from their own inherent limitations. We developed Sat2Graph, which combines the advantages of the two prior categories into a unified framework. The key idea in Sat2Graph is a novel encoding scheme, graph-tensor encoding (GTE), which encodes the road graph into a tensor representation. GTE makes it possible to train a simple, non-recurrent, supervised model to predict a rich set of features that capture the graph structure directly from an image.

Machine-Assisted Map Editing

Despite over a decade of research in automatic map inference, systems that automatically construct road maps have not gained traction in OpenStreetMap and other mapping communities. High error rates makes straightforward integration of automatically inferred roads into the map impractical.

We built Machine-Assisted iD, where we extended the web-based OpenStreetMap editor, iD, with machine-assistance functionality. By tackling the addition of major, arterial roads in regions where existing maps have poor coverage, and the incremental improvement of coverage in regions where major roads are already mapped, MAiD substantially improves mapping productivity.

Road Attributes and Lane Topology

Details about roads like attributes and lane topology enrich maps and enable numerous new applications. For example, mapping the number of lanes on each road makes lane-to-lane navigation possible, where a navigation system informs the driver which lanes will diverge to the correct branch at a junction. Similarly, maps that incorporate the presence of bicycle lanes along each road enable cyclists to make more informed decisions when choosing a route. Additionally, maps with up-to-date road conditions and road types improve the efficiency of road maintenance and disaster relief.

Unfortunately, producing and maintaining digital maps with road attributes is tedious and labor-intensive. In response, we developed RoadTagger, which uses an end-to-end architecture that combines both Convolutional Neural Networks (CNNs) and Graph Neural Networks (GNNs) to automate the inference of road attributes from satellite imagery. We also developed Lane-Level Map Extraction, which accurately extracts lane topology from high-resolution aerial imagery.

Updating Maps

In practice, we would like to maintain and improve existing street maps rather than create entirely new maps from scratch -- new maps inferred from orthoimagery would lack street names, businesses, speed limits, and other useful metadata. Automatic map inference approaches like RoadTracer and Sat2Graph are only useful as a component of a map update system.

Since existing datasets focus on inferring maps from scratch rather than updating maps, we released a new dataset, MUNO21, that benchmarks machine learning methods for automatically updating and maintining digital map datasets. We then developed an end-to-end map update system to first process geospatial data sources to extract insights, and then leverage those insights to update and improve existing maps.

Drones for Real-Time Data

Small quadcopter drones hold the potential to enable real-time updates to high-definition street maps. However, fleets of drones are difficult to manage, and a complex process is needed to map from drone video to actionable information.

To address these issues, we developed two novel systems. BeeCluster is a drone orchestration system that provides a virtual drone abstraction and a predictive optimizer; it not only makes it easier to develop programs that manage many drones, but also optimizes drone routing to accelerate the completion of those programs through predictive modeling. SkyQuery focuses on video-based sensing from aerial drones, and provides an expressive, high-level programming language to make it straightforward for users to develop complex long-running sensing applications.

People