Résumé Technique : Au-delà de la Distance de Chamfer : Métrique d'Évaluation Granulaire et Sensible à l'Ordre pour la Cartographie en Ligne

Énoncé du Problème

L'estimation de cartes en ligne (OME) est cruciale pour la conduite autonome, visant à remplacer les cartes haute définition (HD) préconstruites et coûteuses par des prédictions en temps réel dérivées des capteurs embarqués. Les méthodes actuelles de l'état de l'art (SOTA) prédisent les éléments de la carte (par exemple, séparateurs de voie, limites de route) comme des séquences ordonnées de points formant des polylignes et des polygones. Cependant, le cadre d'évaluation dominant repose sur la Distance de Chamfer (CD) pour la similarité géométrique et la Précision Moyenne (AP) pour le score multi-occurrences. Les auteurs identifient deux lacunes fondamentales dans ce paradigme CD-AP :

1. Absence de Sensibilité à l'Ordre et de Propriétés Métriques : La CD opère sur des ensembles de points non ordonnés, ignorant la structure séquentielle inhérente aux polylignes. Elle mesure la proximité conjointe plutôt que l'alignement structurel, ce qui la rend insensible aux erreurs de réordonnancement des points. De plus, la CD viole l'inégalité triangulaire, ce qui signifie qu'elle n'est pas une métrique appropriée. Bien que la Distance de Fréchet (FD) soit sensible à l'ordre et une métrique appropriée, c'est une mesure basée sur le supremum qui ne reflète que l'erreur dans le pire des cas, la rendant excessivement sensible aux valeurs aberrantes et peu informative concernant le reste de la géométrie.
2. Granularité Grossière et Seuilage Rigide : L'AP convertit la similarité en décisions binaires Vrai Positif (VP)/Faux Positif (FP) basées sur des seuils de distance fixes (par exemple, 0,5 m, 1,0 m). Cela élimine la précision positionnelle ; une prédiction décalée de 0,49 m et une autre de 0,01 m contribuent de manière égale si toutes deux dépassent le seuil. De plus, ces seuils sont souvent trop permissifs pour les exigences de sécurité critiques de la planification et du contrôle en aval. L'AP elle-même ne satisfait pas aux axiomes de métrique, la rendant un cadre de comparaison non fondé sur des principes.

Ces limitations rendent difficile la distinction entre les méthodes qui excellent véritablement en précision géométrique et celles qui satisfont simplement des critères de détection grossiers, et elles échouent à fournir une analyse décomposée des erreurs.

Méthodologie

L'article propose un cadre en deux parties pour remédier à ces limitations, s'inspirant des métriques GOSPA (Generalized Optimal Sub-Pattern Assignment) dans le suivi multi-objets et de la Distance d'Édition Généralisée (GED) dans la correspondance de chaînes de caractères.

1. Attribution de Sous-Pattern Optimal de Séquence (SOSPA)

Pour la similarité d'instance unique, les auteurs introduisent le SOSPA, une métrique sensible à l'ordre adaptée du GOSPA pour les séquences de points finies.

• Définition : Le SOSPA trouve une affectation optimale entre deux séquences $x$ et $y$ qui respecte l'ordre strictement croissant des indices (affectation ordonnée). Il minimise une fonction de coût comprenant la puissance $p$ des distances point à point pour les paires appariées et une pénalité constante $c^p/2$ pour les points non appariés (détections manquées ou fausses alarmes).
• Sensibilité à l'Ordre : Contrairement au GOSPA (qui apparie des ensembles), le SOSPA impose que les paires appariées $(i, j)$ doivent satisfaire $i_1 < i_2 < \dots$ et $j_1 < j_2 < \dots$, préservant ainsi la structure géométrique des polylignes.
• Robustesse : Le coût de coupure $c$ empêche les valeurs aberrantes de dominer le score et fournit une interprétation physique (par exemple, décalage latéral maximal tolérable).
• Calcul : Les auteurs prouvent que le SOSPA est équivalent à un problème de trace de coût minimal dans la GED. Cela permet un calcul efficace utilisant l'algorithme de Wagner–Fischer (WF) en temps $O(|x| \cdot |y|)$.
• Normalisation : Une forme normalisée $\bar{d}_{SOSPA}$ est définie pour borner la métrique dans $[0, 1]$. Pour $p=1$, cette version normalisée satisfait tous les axiomes de métrique (non-négativité, identité, symétrie et inégalité triangulaire).
• Polygones : Pour les polylignes fermées (polygones), la métrique est étendue pour gérer les décalages cycliques. Les auteurs établissent un lemme montrant que l'optimisation sur les décalages cycliques d'une séquence tout en fixant l'autre est suffisante, permettant un calcul efficace via l'algorithme de Maes en $O(|x||y| \log |y|)$.

2. Localisation et Détection de Polylignes (PLD)

Pour l'évaluation multi-occurrences, les auteurs proposent le PLD, dérivé du GOSPA Probabiliste (P-GOSPA).

• Formulation : Le PLD traite les sorties OME comme des Ensembles Finis Aléatoires Multi-Bernoulli (MB RFS), où chaque prédiction possède une probabilité d'existence (score de confiance). Il remplace la classification VP/FP rigide de l'AP par une affectation douce.
• Fonction de Coût : La métrique minimise conjointement :
  1. Erreur Géométrique : Une distance SOSPA pondérée par la confiance entre les éléments appariés.
  2. Erreur de Détection : Pénalités pour les instances manquées, les fausses alarmes et les incohérences de confiance entre la prédiction et la vérité terrain.
• Décomposition : Le PLD se décompose naturellement en deux composantes interprétables :
  • Erreur de Localisation ($e_{loc}$) : Erreur géométrique agrégée sur les paires appariées.
  • Erreur de Détection ($e_{det}$) : Pénalités liées aux détections manquées/fausses et à l'étalonnage de la confiance.
• Propriétés Métriques : Lorsque $p=1$, le PLD normalisé satisfait les axiomes de métrique.

Contributions Clés

1. SOSPA : Une métrique de similarité de polyligne sensible à l'ordre qui satisfait les axiomes de métrique, offre une évaluation fine-granulaire des correspondances/non-correspondances et est robuste aux valeurs aberrantes.
2. Calcul Efficace : Démonstration que le SOSPA est équivalent à un problème de trace de coût minimal GED, permettant un calcul en $O(|x||y|)$ via l'algorithme WF, et dérivation d'une forme de métrique normalisée.
3. Extension Cyclique : Définition d'un SOSPA cyclique pour les polygones avec un lemme permettant un calcul efficace via l'algorithme de Maes.
4. Métrique PLD : Une métrique multi-occurrences douce qui quantifie conjointement la détection et la précision géométrique, fournissant une décomposition inhérente en erreurs de localisation et de détection.
5. Étalonnage : Évaluation complète des méthodes SOTA (MapTRv2, StreamMapNet, MapTracker) sur nuScenes, démontrant la capacité du PLD à classer les méthodes tout en révélant des goulots d'étranglement de performance invisibles pour le mAP.

Résultats et Analyse

Les auteurs ont étalonné trois méthodes OME SOTA sur l'ensemble de données nuScenes en utilisant deux plages d'évaluation : champ proche (R60) et longue portée (R100).

• Cohérence du Classement : Tanto le mAP basé sur la CD que le PLD (mPLD) s'accordaient sur le classement de performance relative : MapTracker > StreamMapNet > MapTRv2. Cela confirme que le PLD capture les différences de performance essentielles.
• Granularité et Sensibilité :
  • Dans des exemples illustratifs, le mAP basé sur la CD attribuait souvent des scores parfaits (1,0) à des prédictions avec une dégradation géométrique significative (par exemple, décalages diagonaux, points mal ordonnés ou points spurius).
  • Le PLD pénalisait correctement ces erreurs. Par exemple, dans les cas de points mal ordonnés, le PLD détectait l'erreur structurelle (augmentant la composante de localisation) tandis que le CD-AP restait aveugle à celle-ci.
  • Le PLD offrait une vue plus nuancée des correspondances partielles, tandis que le CD-AP et le FD-AP aboutissaient souvent à des scores binaires 0/1 qui obscurcissaient la précision géométrique partielle.
• Constats de Décomposition des Erreurs : La découverte la plus significative de la décomposition PLD est que l'erreur de détection domine l'erreur de localisation pour toutes les méthodes et toutes les plages.
  • La composante d'erreur de détection ($mDet.$) s'est avérée être 2 à 4 fois plus grande que l'erreur de localisation ($mLoc.$).
  • Cela indique que le principal goulot d'étranglement dans les méthodes OME actuelles est la capacité de détection (instances manquantes ou fausses alarmes), et non la précision géométrique des éléments détectés.
  • Cette tendance est exacerbée aux plus longues portées (R100), où le maintien de la couverture de détection devient plus difficile.
• Temps d'Exécution : Le temps d'évaluation pour le mPLD était comparable au mAP basé sur la CD (environ 38 secondes pour R60 avec 64 travailleurs), indiquant que la nouvelle métrique n'entraîne pas de pénalité computationnelle.

Importance et Revendications

L'article revendique que le cadre proposé adresse le caractère "mal adapté" de la CD pour les séquences ordonnées et le caractère "grossier" de l'AP pour l'évaluation géométrique. En introduisant le SOSPA et le PLD, les auteurs fournissent :

• Un cadre d'évaluation fondé sur des principes et métrique qui satisfait aux axiomes mathématiques, assurant des comparaisons cohérentes et intuitives.
• Des capacités de diagnostic à granularité fine grâce à la décomposition des erreurs, qui révèle que les progrès de la recherche actuels sont principalement entravés par des échecs de détection plutôt que par des imprécisions géométriques — une nuance que le mAP échoue à capturer.
• Une alternative robuste aux benchmarks existants, sensible à l'ordre des points et aux valeurs aberrantes, reflétant mieux les exigences de la planification et du contrôle de conduite autonome en aval.

Les auteurs concluent que, bien que leur cadre se concentre sur la géométrie et ne capture pas encore la structure topologique au niveau des instances (par exemple, la connectivité des voies), il fournit une base nécessaire pour une évaluation plus rigoureuse des méthodes de cartographie en ligne. Ils positionnent le PLD comme un outil pour soutenir la poursuite des progrès vers une conduite autonome plus sûre en identifiant avec précision les goulots d'étranglement de performance.