Chamfer Distance

Auch genannt: CD, chamfer loss
Kategorie: Sensing › Perception outputs
Schlagwörter: point-cloud, loss-function, evaluation-metric, 3d-perception, deformable-objects

Ein Maß dafür, wie verschieden zwei Punktmengen sind, bestimmt, indem jeder Punkt seinem nächsten Nachbarn in der anderen Menge zugeordnet und diese Abstände in beiden Richtungen kombiniert werden.

Definition

Chamfer-Distanz (Chamfer distance) vergleicht zwei Punktwolken, ohne wissen zu müssen, welcher Punkt welchem entspricht. Für jeden Punkt der ersten Menge sucht sie den nächstgelegenen Punkt der zweiten Menge und notiert den Abstand; dann tut sie dasselbe von der zweiten zur ersten Menge und kombiniert die beiden Richtungsterme. Eine verbreitete Form mittelt die quadrierten Nächster-Nachbar-Abstände in jeder Richtung und addiert die beiden Mittelwerte, andere summieren statt zu mitteln oder verwenden einfache statt quadrierter Abstände. Der Name stammt vom Chamfer Matching, einer Bildanalysetechnik der späten 1970er-Jahre, die Kantenbilder mithilfe von Distanztransformationen verglich.

Beide Richtungen zählen. Die Messung von einer Vorhersage zu einem Ziel prüft, dass jeder vorhergesagte Punkt nahe am Ziel liegt (Genauigkeit); die Messung vom Ziel zur Vorhersage prüft, dass jeder Teil des Ziels abgedeckt ist (Vollständigkeit). Eine Vorhersage, die auf einen Bereich des Ziels zusammenfällt, schneidet in der ersten Richtung gut und in der zweiten schlecht ab. Die beiden Mengen müssen nicht dieselbe Zahl von Punkten haben, was das Maß bequem macht, um Sensordaten mit Modellausgaben zu vergleichen.

Die Chamfer-Distanz ist mit einer Nächster-Nachbar-Struktur wie einem k-d-Baum oder per Brute Force auf einer GPU günstig zu berechnen, und sie ist bezüglich der Punktpositionen fast überall differenzierbar, daher wird sie häufig als Trainingsverlust für Punktwolkengenerierung und Formvervollständigung sowie als Planungskosten verwendet. Ihre Hauptschwäche ist, dass sie ignoriert, wie die Punkte verteilt sind: Verklumpte Punkte können dennoch einen niedrigen Wert ergeben. Die Earth Mover's Distance behebt das, indem sie eine Eins-zu-eins-Zuordnung zwischen gleich großen Mengen findet, bei höherem Rechenaufwand, und der F-Score bei einem Abstandsschwellwert wird oft zusammen damit angegeben. Die Hausdorff-Distanz ist ein verwandtes Maß, das statt eines Mittelwerts den schlechtesten Nächster-Nachbar-Abstand nimmt.

Warum es wichtig ist

Viele Robotikprobleme erfordern den Vergleich von Formen, zwischen denen keine Punktkorrespondenz existiert, etwa eines rekonstruierten Objekts mit einem Scan oder eines vorhergesagten verformbaren Objekts mit einer Zielform. Die Chamfer-Distanz bietet einen schnellen, differenzierbaren Weg, solche Vergleiche zu bewerten, weshalb sie sowohl als Lernverlust als auch als Kostenfunktion in der Planung auftaucht.

Wichtige Anwendungen

Trainingsverlust für Netze zur Punktwolkenrekonstruktion und Formvervollständigung
Planungskosten zum Formen verformbarer Objekte in Richtung eines Ziels
Bewertungsmetrik für 3D-Rekonstruktion und Kartierung
Training gelernter partikelbasierter Dynamikmodelle
Vergleich simulierter und beobachteter Objektzustände bei der Kalibrierung von Simulatoren

In der Praxis

Bei der Manipulation verformbarer Objekte erfasst ein Roboter, der Teig formt, eine Punktwolke des aktuellen Teigs und verfügt über eine Punktwolke der Zielform. Ein gelerntes Dynamikmodell sagt die Teigpunkte nach jeder Kandidaten-Werkzeugaktion vorher; der Planer bewertet jede Vorhersage nach ihrer Chamfer-Distanz zum Ziel und führt die beste aus. Beide Wolken werden zuerst auf eine feste Zahl von Punkten heruntergerechnet, oft mit Farthest Point Sampling, sodass die Kosten schnell zu berechnen und zwischen den Schritten vergleichbar sind. Das Team hält genau fest, welche Variante es verwendet, quadriert oder nicht und Mittelwert oder Summe, denn Werte aus verschiedenen Definitionen lassen sich nicht vergleichen.

Häufige Missverständnisse

Die Chamfer-Distanz hat eine Standardformel — Arbeiten unterscheiden sich bei quadrierten oder einfachen Abständen, Mittelwert oder Summe und darin, wie die beiden Richtungen kombiniert werden, daher sind Zahlen nur unter derselben Definition vergleichbar
Eine niedrige Chamfer-Distanz bedeutet, dass die Punktverteilungen übereinstimmen — sie ignoriert, wie die Punkte über die Oberfläche verteilt sind; die Earth Mover's Distance ist dafür empfindlich
Eine Richtung genügt — nur von der Vorhersage zum Ziel zu messen, belohnt eine Vorhersage, die einen kleinen Teil des Ziels gut abdeckt

Wer das wissen sollte

Forschende in 3D-Wahrnehmung und Lernen, die mit Punktwolken arbeiten
Forschende in der Manipulation, die an verformbaren Objekten arbeiten
Kartierungsingenieure, die die Rekonstruktionsqualität bewerten

Open Source Robotics