SpaceNet Road Detection and Routing Challenge Part II — APLS Implementation

Adam Van Etten
Nov 3, 2017 · 3 min read

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

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

2.1. Node Snapping

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

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

4. Conclusions

The DownLinQ

Welcome to the archived blog of CosmiQ Works, an IQT Lab

The DownLinQ

As of March 2021, CosmiQ Works has been folded into IQT Labs. An archive will remain here to showcase historical work from CosmiQ Works that took place July 2016 — March 2021.

Adam Van Etten

Written by

The DownLinQ

As of March 2021, CosmiQ Works has been folded into IQT Labs. An archive will remain here to showcase historical work from CosmiQ Works that took place July 2016 — March 2021.