Chamfer Distance

Aussi appelé: CD, chamfer loss
Catégorie: Sensing › Perception outputs
Mots-clés: point-cloud, loss-function, evaluation-metric, 3d-perception, deformable-objects

Mesure de la différence entre deux ensembles de points, obtenue en associant chaque point à son plus proche voisin dans l'autre ensemble et en combinant ces distances dans les deux directions.

Définition

Distance de Chamfer (Chamfer distance) : mesure qui compare deux nuages de points sans avoir besoin de savoir quel point correspond à quel autre. Pour chaque point du premier ensemble, elle trouve le point le plus proche dans le second ensemble et enregistre la distance ; elle fait ensuite de même du second ensemble vers le premier, et combine les deux termes directionnels. Une forme courante moyenne les carrés des distances au plus proche voisin dans chaque direction et additionne les deux moyennes, mais d'autres somment au lieu de moyenner, ou utilisent les distances simples plutôt que leurs carrés. Le nom vient du chamfer matching, une technique d'analyse d'images de la fin des années 1970 qui comparait des cartes de contours à l'aide de transformées de distance.

Les deux directions comptent. Mesurer de la prédiction vers la cible vérifie que chaque point prédit se trouve près de la cible (précision) ; mesurer de la cible vers la prédiction vérifie que chaque partie de la cible est couverte (complétude). Une prédiction qui s'effondre sur une seule région de la cible obtient un bon score dans la première direction et un mauvais dans la seconde. Les deux ensembles n'ont pas besoin d'avoir le même nombre de points, ce qui rend la mesure pratique pour comparer des données de capteurs à des sorties de modèles.

La distance de Chamfer est peu coûteuse avec une structure de plus proches voisins comme un arbre k-d, ou par force brute sur GPU, et elle est différentiable par rapport aux positions des points presque partout ; elle est donc largement utilisée comme perte d'entraînement pour la génération de nuages de points et la complétion de formes, et comme coût de planification. Sa principale faiblesse est d'ignorer la répartition des points : des points agglutinés peuvent quand même donner une valeur faible. L'Earth mover's distance y remédie en trouvant un appariement un à un entre des ensembles de même taille, pour un coût de calcul plus élevé, et le F-score à un seuil de distance est souvent rapporté à côté. La distance de Hausdorff est une mesure apparentée qui prend la pire distance au plus proche voisin au lieu d'une moyenne.

Pourquoi c'est important

De nombreux problèmes de robotique consistent à comparer des formes entre lesquelles il n'existe aucune correspondance de points, comme un objet reconstruit et un scan, ou un objet déformable prédit et une forme cible. La distance de Chamfer offre un moyen rapide et différentiable de noter ces comparaisons, c'est pourquoi elle apparaît à la fois comme perte d'apprentissage et comme coût en planification.

Applications principales

Perte d'entraînement pour les réseaux de reconstruction de nuages de points et de complétion de formes
Coût de planification pour façonner des objets déformables vers une cible
Métrique d'évaluation pour la reconstruction 3D et la cartographie
Entraînement de modèles de dynamique appris à base de particules
Comparaison des états d'objets simulés et observés lors de l'étalonnage de simulateurs

En pratique

En manipulation d'objets déformables, un robot qui façonne de la pâte capture un nuage de points de la pâte actuelle et dispose d'un nuage de points de la forme cible. Un modèle de dynamique appris prédit les points de la pâte après chaque action d'outil candidate ; le planificateur note chaque prédiction par sa distance de Chamfer à la cible et exécute la meilleure. Les deux nuages sont d'abord sous-échantillonnés à un nombre fixe de points, souvent par échantillonnage par point le plus éloigné, pour que le coût soit rapide à calculer et comparable d'une étape à l'autre. L'équipe consigne exactement la variante utilisée, au carré ou non et moyenne ou somme, car des valeurs issues de définitions différentes ne peuvent pas être comparées.

Idées reçues

La distance de Chamfer a une formule standard unique — les articles diffèrent sur les distances au carré ou simples, la moyenne ou la somme, et la manière de combiner les deux directions, de sorte que les chiffres ne sont comparables qu'avec la même définition
Une faible distance de Chamfer signifie que les distributions de points concordent — elle ignore comment les points sont répartis sur la surface ; l'Earth mover's distance y est sensible
Une seule direction suffit — mesurer seulement de la prédiction vers la cible récompense une prédiction qui couvre bien une petite partie de la cible

Qui devrait le savoir

Chercheurs en perception 3D et en apprentissage qui travaillent avec des nuages de points
Chercheurs en manipulation qui travaillent sur les objets déformables
Ingénieurs en cartographie qui évaluent la qualité des reconstructions

Technologies associées

Earth Mover's Distance
Distance de Hausdorff (Hausdorff Distance)
F-score (reconstruction 3D) (F-score (3D Reconstruction))
Arbre k-d (k-d Tree)
PointNet

Termes associés

Projets associés

Open3D: Modern library for 3D point cloud processing, mesh operations, and 3D machine learning
PCL: Industry-standard C++ library for point cloud processing in robotics perception
OpenDroneMap: Open-source photogrammetry toolkit that turns drone images into maps and 3D models
LeGO-LOAM: Classic lightweight, ground-optimized lidar odometry and mapping baseline (IROS 2018)
libpointmatcher: Modular ICP library for 2D/3D point cloud registration and mapping
Patchwork++: Fast and robust ground segmentation for 3D LiDAR point clouds from KAIST