Time-optimized Evacuation Scenarios Via Satellite Imagery

Recent research in road network extraction (1, 2, 3) has chipped away at the ever challenging task of identifying routable networks from overhead imagery. The recent SpaceNet 5 Challenge further pushed the envelope by extracting not only routable networks, but travel time estimates for each detected roadway. Unsurprisingly, all recent advances (including SpaceNet 5) leverage deep learning networks in various ways, necessitating graphical processing units (GPUs) to train these networks in reasonable timeframes.

This prompts an important question: must dedicated hardware always be used to extract high quality road networks from remote sensing imagery, or is this task possible with nothing but a laptop and some open source code? In this blog we show that modest hardware (i.e. a MacBook Pro) is indeed sufficient to run a highly performant model. In the sections below, we walk the reader through a recent open-source self-contained tutorial that demonstrates how to build a time-weighted road graph and analyze evacuation scenarios in a previously unseen city.

1. Introduction

In previous posts (e.g. 4, 5, 6) we discussed in great detail the challenges of road network extraction from remote sensing imagery. Accordingly, we skip a lengthy treatment of rationale and complications, and mention just a few points:

1. Time-optimized routing (rather than simple geometric routing) is critical for most scenarios (see Figure 1).
2. Commercial products (i.e. Google Maps, Apple Maps) often rely upon cell phone GPS pings and infrequently updated imagery for determining real-time routing; in a dynamic scenario (e.g.: natural disaster) existing road networks may be out of date, and cell towers may be down. Furthermore, the underlaying data is proprietary, further complicating use by practitioners.
3. Open source offerings such as OpenStreetMap (OSM) are great resources, though have limitations. The crowd-sourced nature of OSM means that updating maps can take significant time. For example, it took the Humanitarian OpenStreetMap Team (HOT) over two months to fully map Puerto Rico after Hurricane Maria in 2017, even with thousands of volunteers. Furthermore, OSM road metadata that can be used to optimize routing is often missing, and road centerline label quality is inconsistent (see Figure 2).

Figure 1. Left: Typical road extraction algorithms provide only geometric distance as an option for optimal routing. Right: Incorporating speed limit information in the graph yields very different optimal path when optimizing by travel time.

Figure 2. OSM labels over a portion of Shanghai, colored by the ‘maxspeed’ tag. The vast majority of roads have no indicated speed limit.

2. Algorithmic Approach

The City-scale Road Extraction from Satellite Imagery (CRESI) algorithm served as the algorithmic baseline for the SpaceNet 5 Challenge. While challenge participants managed to improve the performance of the CRESI baseline by about 5%, we will use the original CRESI model for this exercise, as it has by far the fastest runtime and is designed to scale to arbitrarily large images.

SpaceNet imagery and trained model weights are part of the Registry of Open Data on AWS, and can be downloaded for free. Therefore all you need to run this tutorial is an AWS account, and Docker installed on your local machine. We refer readers to Part 1 of the tutorial to quickly set up the CRESI environment.

3. Test Data

For this exercise, we’ll explore a subset of SpaceNet Area of Interest (AOI) #10: Dar Es Salaam. This city was withheld for testing purposes in SpaceNet 5, meaning that the pre-trained model has not been trained on this city whatsoever. Though CRESI readily scales to regions of arbitrary size, we clip the image somewhat to ease in visualizing the output. The testing region considered here still encompasses 11.7 square kilometers and over 130 million pixels.

Figure 3. Test region of Dar Es Salaam.

4. Road Network Prediction

Inference can be invoked simply by calling a single command which will will execute the CRESI multi-step process sequentially:

./test.sh configs/dar_tutorial_cpu.json

For this blog, we will briefly summarize each step, please refer to the tutorial for more details.

4.A. Deep learning Model Inference and Mask Stitching

To begin, we apply the trained deep learning model to our testing imagery. First, we tile the imagery into manageable sizes (~400 x 400 meters or 1300 x 1300 pixels), since the entire 130 million pixel image will far exceed available memory on non-supercomputers. These mask tiles are subsequently stitched back together (see Figure 4). Many road extraction algorithms end here once a road pixel mask has been produced. We still have a few more steps to go, however.

Figure 4. Stitched (aggregate) prediction mask for our test image.

4.B. Skeletonization and Graph Creation

We subsequently refine and cleanse the aggregate output mask, then compute the image skeleton, extract the graph from this skeleton, and compute geographic coordinates from the image metadata. These steps yield a road graph, as in Figure 5.

Figure 5. Predicted road network graph.

4.C. Speed Estimates

The final step is to use the information encoded in the multi-channel prediction masks, in combination with the graph created from the previous steps, to infer road speed and travel time (Figure 6).

Figure 6. Speed estimation procedure: Left: Sample multi-class prediction mask; the speed (r) of an individual patch (red square) can be inferred by measuring the signal from each channel. Right: Computed road graph; travel time (∆t) is given by speed (r) and segment length (∆l).

Inference is rapid, with all steps taking <20 minutes even without a GPU. The output is NetworkX graph structure that contains speed / travel time information for each roadway, which we illustrate in Figures 7 and 8.

Figure 7. Inferred road network, colored by inferred road speed, with speed increasing from yellow (15 mph) to red (65 mph).

Figure 8. Inferred road network, colored by inferred road speed, with speed increasing from yellow (15 mph) to red (65 mph), overlaid on the test image.

5. Routing

We can use the final road network to quickly compute optimal routes between nodes of interest. Furthermore, we have flexibility in how we define “optimal” — either distance traveled or total travel time is possible.

Let us assume a situation where we have a known asset position (“source”) and we want to evacuate to the northeast (“target”). Computing optimal routes in this scenario can be accomplished via commands similar to the following:

import networkx as nx
dl, path_0 = nx.single_source_dijkstra(G, source, target,   
                                       weight=’length’)
dt, path_1 = nx.single_source_dijkstra(G, source, target, 
                                       weight=’time’)

Plotting the two different optimal routes we compute from the command above yields Figure 9.

Figure 9. Optimal paths between nodes of interest, with a weight of length (Left), and time (Right).

Clearly, the optimal route is very different when weighting by time rather than distance, underscoring the need to incorporate speed estimates into road graphs.

6. Conclusions

In this blog showed how to extract a road network graph with speed / travel time estimates directly from satellite imagery using only open source data and code. Inference is relatively rapid, running at 0.7 square kilometers per minute even on a CPU. GPU inference times would be a minimum of 20X faster. Even for a city unseen during training (Dar Es Salaam), the CRESI algorithm manages to return a road network that is sufficiently complete to be routable. We showed how to compute optimal routes, and demonstrated the importance of routing using speed versus geometric distance. We encourage interested parties to investigate new testing regions, compute new routes, and dive deeper into the intricacies of road network extraction and routing by exploring the tutorial this blog is based upon.