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).
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.
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.
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.
