Technical Summary: Beyond Chamfer Distance: Granular Order-aware Evaluation Metric For Online Mapping

Problem Statement

Online map estimation (OME) is critical for autonomous driving, aiming to replace costly pre-built high-definition (HD) maps with real-time predictions derived from onboard sensors. Current state-of-the-art (SOTA) methods predict map elements (e.g., lane dividers, road boundaries) as ordered sequences of points forming polylines and polygons. However, the prevailing evaluation framework relies on Chamfer Distance (CD) for geometric similarity and Average Precision (AP) for multi-instance scoring. The authors identify two fundamental shortcomings in this CD-AP paradigm:

1. Lack of Order Sensitivity and Metric Properties: CD operates on unordered point sets, ignoring the sequential structure inherent to polylines. It measures joint proximity rather than structural alignment, making it insensitive to point misordering. Furthermore, CD violates the triangle inequality, meaning it is not a proper metric. While Fréchet Distance (FD) is order-aware and a proper metric, it is a supremum-based measure that reflects only the worst-case error, making it overly sensitive to outliers and uninformative regarding the rest of the geometry.
2. Coarse Granularity and Hard Thresholding: AP converts similarity into binary True Positive (TP)/False Positive (FP) decisions based on fixed distance thresholds (e.g., 0.5m, 1.0m). This discards positional accuracy; a prediction 0.49m off and one 0.01m off contribute equally if both pass the threshold. Additionally, these thresholds are often too permissive for the safety-critical requirements of downstream planning and control. AP itself does not satisfy metric axioms, rendering it a non-principled comparison framework.

These limitations make it difficult to distinguish between methods that truly excel in geometric accuracy versus those that merely satisfy coarse detection criteria, and they fail to provide decomposed error analysis.

Methodology

The paper proposes a two-part framework to address these limitations, drawing inspiration from Generalized Optimal Sub-Pattern Assignment (GOSPA) metrics in multi-object tracking and Generalized Edit Distance (GED) in string matching.

1. Sequence Optimal Sub-Pattern Assignment (SOSPA)

For single-instance similarity, the authors introduce SOSPA, an order-aware metric adapted from GOSPA for finite point sequences.

• Definition: SOSPA finds an optimal assignment between two sequences $x$ and $y$ that respects the strictly increasing order of indices (ordered assignment). It minimizes a cost function comprising the $p$-th power of point-wise distances for matched pairs and a constant penalty $c^p/2$ for unmatched points (missed detections or false alarms).
• Order Awareness: Unlike GOSPA (which matches sets), SOSPA enforces that matched pairs $(i, j)$ must satisfy $i_1 < i_2 < \dots$ and $j_1 < j_2 < \dots$, preserving the geometric structure of polylines.
• Robustness: The cutoff cost $c$ prevents outliers from dominating the score and provides a physical interpretation (e.g., maximum tolerable lateral offset).
• Computation: The authors prove that SOSPA is equivalent to a minimum-cost trace problem in GED. This allows efficient computation using the Wagner–Fischer (WF) algorithm in $O(|x| \cdot |y|)$ time.
• Normalization: A normalized form $\bar{d}_{SOSPA}$ is defined to bound the metric in $[0, 1]$. For $p=1$, this normalized version satisfies all metric axioms (non-negativity, identity, symmetry, and triangle inequality).
• Polygons: For closed polylines (polygons), the metric is extended to handle cyclic shifts. The authors establish a lemma showing that optimizing over cyclic shifts of one sequence while fixing the other is sufficient, enabling efficient computation via Maes' algorithm in $O(|x||y| \log |y|)$.

2. Polyline Localisation and Detection (PLD)

For multi-instance evaluation, the authors propose PLD, derived from Probabilistic GOSPA (P-GOSPA).

• Formulation: PLD treats OME outputs as Multi-Bernoulli Random Finite Sets (MB RFS), where each prediction has an existence probability (confidence score). It replaces the hard TP/FP classification of AP with a soft assignment.
• Cost Function: The metric jointly minimizes:
  1. Geometric Error: A confidence-weighted SOSPA distance between matched elements.
  2. Detection Error: Penalties for missed instances, false alarms, and confidence mismatches between prediction and ground truth.
• Decomposition: PLD naturally decomposes into two interpretable components:
  • Localization Error ($e_{loc}$): Aggregated geometric error over matched pairs.
  • Detection Error ($e_{det}$): Penalties related to missed/false detections and confidence calibration.
• Metric Properties: When $p=1$, the normalized PLD satisfies metric axioms.

Key Contributions

1. SOSPA: An order-aware polyline similarity metric that satisfies metric axioms, offers fine-grained evaluation of matches/mismatches, and is robust to outliers.
2. Efficient Computation: Demonstration that SOSPA is equivalent to a GED minimum-cost trace problem, allowing $O(|x||y|)$ computation via WF algorithm, and derivation of a normalized metric form.
3. Cyclic Extension: Definition of cyclic SOSPA for polygons with a lemma enabling efficient computation via Maes' algorithm.
4. PLD Metric: A soft multi-instance metric that jointly quantifies detection and geometric accuracy, providing an inherent decomposition into localization and detection errors.
5. Benchmarking: Comprehensive evaluation of SOTA methods (MapTRv2, StreamMapNet, MapTracker) on nuScenes, demonstrating PLD's ability to rank methods while revealing performance bottlenecks invisible to mAP.

Results and Analysis

The authors benchmarked three SOTA OME methods on the nuScenes dataset using two evaluation ranges: near-field (R60) and long-range (R100).

• Ranking Consistency: Both CD-based mAP and PLD (mPLD) agreed on the relative performance ranking: MapTracker > StreamMapNet > MapTRv2. This confirms PLD captures essential performance differences.
• Granularity and Sensitivity:
  • In illustrative examples, CD-based mAP often assigned perfect scores (1.0) to predictions with significant geometric degradation (e.g., diagonal shifts, misordered points, or spurious points).
  • PLD correctly penalized these errors. For instance, in cases of misordered points, PLD detected the structural error (increasing the localization component) while CD-AP remained blind to it.
  • PLD provided a more nuanced view of partial matches, whereas CD-AP and FD-AP often resulted in binary 0/1 scores that obscured partial geometric accuracy.
• Error Decomposition Findings: The most significant finding from the PLD decomposition is that detection error dominates localization error across all methods and ranges.
  • The detection error component ($mDet.$) was found to be 2 to 4 times larger than the localization error ($mLoc.$).
  • This indicates that the primary bottleneck in current OME methods is detection capability (missing instances or false alarms), not the geometric precision of detected elements.
  • This trend is exacerbated at longer ranges (R100), where detection coverage becomes harder to maintain.
• Runtime: The evaluation time for mPLD was comparable to CD-based mAP (approx. 38 seconds for R60 with 64 workers), indicating the new metric does not incur a computational penalty.

Significance and Claims

The paper claims that the proposed framework addresses the "ill-suited" nature of CD for ordered sequences and the "coarse" nature of AP for geometric assessment. By introducing SOSPA and PLD, the authors provide:

• A principled, metric-based evaluation framework that satisfies mathematical axioms, ensuring consistent and intuitive comparisons.
• Fine-grained diagnostic capabilities through error decomposition, which reveals that current research progress is primarily hindered by detection failures rather than geometric inaccuracies—a nuance mAP fails to capture.
• A robust alternative to existing benchmarks that is sensitive to point ordering and outliers, better reflecting the requirements of downstream autonomous driving planning and control.

The authors conclude that while their framework focuses on geometry and does not yet capture instance-level topological structure (e.g., lane connectivity), it provides a necessary foundation for more rigorous evaluation of online mapping methods. They position PLD as a tool to support continued progress toward safer autonomous driving by accurately identifying performance bottlenecks.