SpaceNet Road Detection and Routing Challenge Part II — APLS Implementation

Road network mapping remains a signification challenge in many parts of the world. In fact, dozens of campaigns are currently open on the Humanitarian OpenStreepMap Team’s Tasking Manager for road mapping. Our previous post discussed the shortcomings of traditional pixel-based metrics, and introduced the data-agnostic Average Path Length Similarity (APLS) metric to evaluate road network proposals.

In this post we discuss some of the subtleties of comparing road network proposals to ground truth graphs. We also release the APLS code to encourage exploration by interested readers.

1. APLS Overview

Traditional methods for graph similarity matching tend to focus on the logical topology (connections between nodes) of the graph, whereas we care about both logical topology as well as the physical topology of the roads. As detailed in our previous post, this led us to develop the APLS metric that sums the differences in optimal path lengths between nodes in the ground truth graph G and the proposal graph G’. Missing paths in the graph are assigned the maximum proportional difference of 1.0. The APLS metric scales from 0 (poor) to 1 (perfect).

Equation 1. APLS metric. Node a’ is the node in the proposal graph G’ nearest the location of node a in the ground truth graph G. L(a,b) denotes a path distance in the ground truth graph G, and L(a’, b’) denotes the path length between the corresponding nodes in the proposal graph.

Inherent to this metric is the notion of betweenness centrality, or the number of times a node appears along the shortest paths between other nodes. Missing nodes of high centrality will be penalized much more heavily by the APLS metric than missing nodes of low centrality. This feature is intentional, as heavily trafficked intersections are much more important than cul-de-sacs for routing purposes.

While we developed the APLS metric as a means to score computer vision competitions, unlike pixel-based metrics the APLS metric is agnostic to data type; the APLS metric applies equally well to road network proposals derived from optical imagery, radar, GPS tracks, LIDAR, and/or hand-crafted labels.

2. Road Network Comparison Complications

A couple of complications arise when applying Equation 1 to compare road networks, both relating to the selection of control nodes. In this context, we define control nodes as road endpoints, intersections, or midpoints along routes of interest.

2.1. Node Snapping

Equation 1 is easy to apply if the proposal graph G’ has nodes coincident with the ground truth graph G. In practice, however, proposals will not align perfectly with ground truth graphs. Subsequently, we “snap” the control points of the ground truth graph onto the proposal graph. This is illustrated in Figure 1.

Figure 1. Node snapping procedure. A: Ground truth graph with control nodes. B: Proposal graph. C: Ground truth graph (orange) and ground truth control points (red) overlaid on proposal graph (grey). D: Same as graph C, but showing an 8 meter buffer (yellow) around the proposal graph. E: Ground truth control nodes are injected into the proposal graph at the nearest edge, except for nodes outside the buffer (grey). F: Final proposal graph with nodes injected at the appropriate location to compare to graph A.

2.2. Symmetric Comparisons

Once the ground truth to proposal node snapping procedure of Figure 1 is completed, optimal path lengths can be compared between proposal and ground truth nodes. In order to penalize spurious road proposals, one must also perform the inverse operation by snapping proposal control nodes onto the ground truth graph. This is illustrated in Figure 2.

Figure 2. Illustration of the need to apply Equation 1 symmetrically (i.e.: ground truth to proposal, and proposal to ground truth). A: Ground truth graph. B: Proposal graph with many short, spurious connections well outside the buffer. C: Proposal nodes snapped onto the ground truth graph; snapping proposal control points onto the ground truth graph and then computing the metric penalizes the many extraneous predictions (grey nodes).

3. APLS Code

The python code to compare ground truth and proposal graphs is available at https://github.com/CosmiQ/apls, along with standalone examples.

4. Conclusions

The upcoming SpaceNet roads competition will challenge contestants to extract road networks directly from satellite imagery, and proposals will be scored with the graph-theoretic APLS metric that is agnostic to input data type. In this post we expanded upon previous work to discuss some of the subtleties of comparing ground truth road graphs to proposal graphs, and illustrated that thoughtful selection of control nodes and symmetric evaluation addresses these subtleties. In preparation for the SpaceNet challenge we encourage the interested reader to explore the metric via the APLS github repository.