Chamfer Distance

La distanza di Chamfer misura quanto corrispondono due insiemi di punti; si calcola in base alla distanza tra ciascun punto e il suo vicino più prossimo nell'altro insieme. Valori inferiori indicano una maggiore corrispondenza. Nella visione artificiale, confronta nuvole di punti 3D, ovvero insiemi di coordinate spaziali campionate, e contorni di oggetti 2D. L'ordine dei punti è irrilevante e gli insiemi possono contenere numeri diversi di punti.

Le sue origini risalgono al chamfer matching, introdotto nel 1977 da H. G. Barrow, J. M. Tenenbaum, R. C. Bolles e H. C. Wolf per confrontare forme rappresentate da curve d'immagine. Nella progettazione CAD meccanica, uno smusso è un bordo inclinato le cui dimensioni descrivono una caratteristica fisica.

Come si calcola la distanza di Chamfer#

Per due insiemi di punti non vuoti, A e B, una definizione comune basata sulla distanza al quadrato prevede tre passaggi:

1. Per ogni punto di A, trova il vicino più prossimo in B, calcola il quadrato della distanza euclidea e fai la media di questi valori.
2. Ripeti da B ad A.
3. Somma le due medie direzionali.

La prima direzione penalizza i punti previsti lontani dalla superficie di riferimento; la direzione inversa penalizza le regioni di riferimento assenti dalla previsione. Si usa la stessa operazione di ricerca del vicino più prossimo alla base dei k vicini più prossimi, con un vicino per ogni query. L'implementazione della distanza di Chamfer di PyTorch3D supporta sia i calcoli bidirezionali sia quelli unidirezionali.

Le distanze al quadrato o non elevate al quadrato e le riduzioni tramite somma o media modificano il punteggio. Un'altra convenzione comune calcola la media delle due medie direzionali, ottenendo un valore pari alla metà della loro somma. Di conseguenza, la convenzione adottata per la distanza, le unità di coordinate e la normalizzazione fanno parte della definizione della metrica usata in un esperimento.

Questo calcolo in PyTorch usa torch.cdist per calcolare le distanze euclidee a coppie:

import torch

a = torch.tensor([[0.0, 0.0], [2.0, 0.0]])
b = torch.tensor([[0.0, 0.0], [3.0, 0.0]])

# Reduce squared distances in each nearest-neighbor direction.
distances = torch.cdist(a, b, p=2)
squared_distances = distances.square()
a_to_b = squared_distances.min(dim=1).values.mean()
b_to_a = squared_distances.min(dim=0).values.mean()
chamfer = a_to_b + b_to_a

print(f"Squared Chamfer distance: {chamfer.item():.2f}")

L'output è 1.00: ciascuna media direzionale è 0.50. Insiemi di punti identici producono zero.

La loss di Chamfer nell'addestramento dei modelli#

La loss di Chamfer è la distanza di Chamfer usata come funzione di perdita. Una rete neurale prevede coordinate dei punti e la retropropagazione fornisce gradienti che li spostano verso i punti di riferimento. La selezione del vicino più prossimo rende l'obiettivo differenziabile a tratti: nelle regioni in cui le assegnazioni rimangono fisse, le distanze al quadrato forniscono gradienti rispetto alle coordinate.

Un'applicazione fondamentale è Point Set Generation Network (PSGN) di Haoqiang Fan, Hao Su e Leonidas J. Guibas, presentata a CVPR 2017. Usa la distanza di Chamfer come obiettivo di addestramento per la ricostruzione 3D da una singola immagine, prevedendo la nuvola di punti di un oggetto a partire da una fotografia. Questo obiettivo basato su insiemi di punti consente l'apprendimento senza corrispondenze punto a punto predefinite.

Applicazioni nella ricostruzione e nella segmentazione#

Nella ricostruzione 3D, la distanza di Chamfer confronta superfici previste campionate con la geometria di riferimento. Supporta anche il fitting di mesh: i vertici vengono ottimizzati affinché i campioni della mesh si avvicinino ai campioni obiettivo. Nel fitting di una mesh da una sfera a un delfino, ottimizzare solo la loss di Chamfer produce una superficie irregolare; la regolarizzazione dei bordi, delle normali e del Laplaciano vincola la struttura locale della mesh.

Per la segmentazione di istanze, la distanza di Chamfer misura la discrepanza spaziale tra contorni campionati e previsti e contorni annotati. La segmentazione di YOLO26 di Ultralytics espone le coordinate dei poligoni tramite Masks.xy, fornendo insiemi di punti per la valutazione esterna dei contorni basata sulla distanza di Chamfer. A differenza dell'Intersection over Union, che si basa sull'area, la distanza tra i contorni esprime quanto sono lontani i bordi.

Misure correlate e interpretazione del punteggio#

Tre concetti correlati aiutano a chiarire cosa misura il punteggio:

• La distanza di Hausdorff usa la massima discrepanza tra vicini più prossimi, dando rilievo alla peggiore incongruenza tra contorni o superfici.
• La distanza Earth Mover individua un trasporto a costo minimo che preserva la massa tra distribuzioni, abbinando le assegnazioni tra gli insiemi di punti.
• La distanza di Chamfer sensibile alla densità tiene conto del campionamento locale non uniforme. Il Chamfer standard consente a molti punti di condividere lo stesso vicino più prossimo, quindi gli ammassi densi possono presentare errori ridotti nonostante l'uniformità di campionamento sia scarsa.

La densità di campionamento, l'allineamento e la preelaborazione dei dati influenzano quindi i confronti. La distanza non elevata al quadrato ha le stesse unità delle coordinate; quella al quadrato ha unità al quadrato. Convertire entrambe le nuvole da metri a centimetri moltiplica la distanza di Chamfer non elevata al quadrato per 100 e quella al quadrato per 10.000.