Chamfer Distance

Detto anche: CD, chamfer loss
Categoria: Sensing › Perception outputs
Tag: point-cloud, loss-function, evaluation-metric, 3d-perception, deformable-objects

Una misura di quanto differiscono due insiemi di punti, ottenuta associando ogni punto al suo vicino più prossimo nell'altro insieme e combinando quelle distanze in entrambe le direzioni.

Definizione

Distanza di Chamfer (Chamfer distance) confronta due nuvole di punti senza dover sapere quale punto corrisponde a quale. Per ogni punto del primo insieme, trova il punto più vicino nel secondo insieme e ne registra la distanza; poi fa lo stesso dal secondo insieme al primo e combina i due termini direzionali. Una forma comune fa la media delle distanze al quadrato dal vicino più prossimo in ciascuna direzione e somma le due medie, ma altre sommano anziché fare la media, o usano distanze semplici anziché al quadrato. Il nome viene dal chamfer matching, una tecnica di analisi delle immagini della fine degli anni Settanta che confrontava mappe dei bordi usando trasformate di distanza.

Entrambe le direzioni contano. Misurare dalla predizione al target verifica che ogni punto predetto si trovi vicino al target (accuratezza); misurare dal target alla predizione verifica che ogni parte del target sia coperta (completezza). Una predizione che collassa su una regione del target ottiene un buon punteggio nella prima direzione e un cattivo punteggio nella seconda. I due insiemi non devono avere lo stesso numero di punti, il che rende la misura comoda per confrontare dati di sensori con uscite di modelli.

La distanza di Chamfer è economica con una struttura per i vicini più prossimi come un k-d tree, o a forza bruta su GPU, ed è differenziabile rispetto alle posizioni dei punti quasi ovunque, per cui è molto usata come loss di addestramento per la generazione di nuvole di punti e il completamento di forme e come costo di pianificazione. Il suo punto debole principale è che ignora come sono distribuiti i punti: punti ammassati possono comunque dare un valore basso. La Earth mover's distance affronta questo problema trovando una corrispondenza uno a uno tra insiemi della stessa dimensione, a un costo computazionale più alto, e spesso le si affianca l'F-score a una soglia di distanza. La distanza di Hausdorff è una misura affine che prende la peggiore distanza dal vicino più prossimo invece di una media.

Perché è importante

Molti problemi di robotica richiedono di confrontare forme per cui non esiste una corrispondenza tra punti, come un oggetto ricostruito rispetto a una scansione, o un oggetto deformabile predetto rispetto a una forma target. La distanza di Chamfer offre un modo rapido e differenziabile per valutare questi confronti, ed è per questo che compare sia come loss di apprendimento sia come costo nella pianificazione.

Applicazioni principali

Loss di addestramento per reti di ricostruzione di nuvole di punti e di completamento di forme
Costo di pianificazione per modellare oggetti deformabili verso un target
Metrica di valutazione per la ricostruzione 3D e la mappatura
Addestramento di modelli dinamici appresi basati su particelle
Confronto tra stati di oggetti simulati e osservati durante la calibrazione dei simulatori

In pratica

Nella manipolazione di oggetti deformabili, un robot che modella un impasto acquisisce una nuvola di punti dell'impasto attuale e dispone di una nuvola di punti della forma target. Un modello dinamico appreso predice i punti dell'impasto dopo ogni azione candidata dell'utensile; il pianificatore valuta ogni predizione in base alla sua distanza di Chamfer dal target ed esegue la migliore. Entrambe le nuvole vengono prima sottocampionate a un numero fisso di punti, spesso con il campionamento del punto più lontano (farthest point sampling), così che il costo sia rapido da calcolare e confrontabile tra un passo e l'altro. Il team annota esattamente quale variante usa, al quadrato o no e media o somma, perché valori ottenuti con definizioni diverse non si possono confrontare.

Idee sbagliate comuni

La distanza di Chamfer ha un'unica formula standard — gli articoli differiscono su distanze al quadrato o semplici, media o somma, e su come si combinano le due direzioni, quindi i numeri sono confrontabili solo con la stessa definizione
Una distanza di Chamfer bassa significa che le distribuzioni dei punti coincidono — ignora come i punti sono distribuiti sulla superficie; la Earth mover's distance invece ne tiene conto
Basta una direzione — misurare solo dalla predizione al target premia una predizione che copre bene una piccola parte del target

Chi dovrebbe saperlo

Ricercatori di percezione 3D e apprendimento che lavorano con nuvole di punti
Ricercatori di manipolazione che lavorano con oggetti deformabili
Ingegneri di mappatura che valutano la qualità della ricostruzione

Tecnologie correlate

Earth Mover's Distance
Distanza di Hausdorff (Hausdorff Distance)
F-score (ricostruzione 3D)
k-d tree (k-d Tree)
PointNet

Termini correlati

Progetti correlati

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