Chamfer Distance

Também chamado: CD, chamfer loss
Categoria: Sensing › Perception outputs
Tags: point-cloud, loss-function, evaluation-metric, 3d-perception, deformable-objects

Uma medida de quanto dois conjuntos de pontos diferem, obtida ao associar cada ponto ao seu vizinho mais próximo no outro conjunto e combinar essas distâncias nas duas direções.

Definição

Distância de Chamfer (Chamfer distance) compara duas nuvens de pontos sem precisar saber qual ponto corresponde a qual. Para cada ponto do primeiro conjunto, ela encontra o ponto mais próximo no segundo conjunto e registra a distância; depois faz o mesmo do segundo conjunto para o primeiro e combina os dois termos direcionais. Uma forma comum calcula a média das distâncias ao quadrado até o vizinho mais próximo em cada direção e soma as duas médias, mas outras somam em vez de calcular a média, ou usam distâncias simples em vez de ao quadrado. O nome vem do chamfer matching, uma técnica de análise de imagens do fim dos anos 1970 que comparava mapas de bordas usando transformadas de distância.

As duas direções importam. Medir da predição para o alvo verifica se cada ponto predito está perto do alvo (precisão); medir do alvo para a predição verifica se cada parte do alvo está coberta (completude). Uma predição que colapsa sobre uma região do alvo pontua bem na primeira direção e mal na segunda. Os dois conjuntos não precisam ter o mesmo número de pontos, o que torna a medida conveniente para comparar dados de sensores com saídas de modelos.

A distância de Chamfer é barata com uma estrutura de vizinhos mais próximos como uma árvore k-d, ou por força bruta em uma GPU, e é diferenciável em relação às posições dos pontos em quase toda parte, por isso é muito usada como loss de treinamento para geração de nuvens de pontos e completamento de formas e como custo de planejamento. Sua principal fraqueza é ignorar como os pontos estão distribuídos: pontos amontoados ainda podem dar um valor baixo. A Earth mover's distance resolve isso encontrando uma correspondência um a um entre conjuntos de mesmo tamanho, com custo computacional maior, e o F-score em um limiar de distância costuma ser relatado junto. A distância de Hausdorff é uma medida relacionada que usa a pior distância ao vizinho mais próximo em vez de uma média.

Por que importa

Muitos problemas de robótica envolvem comparar formas sem correspondência entre pontos, como um objeto reconstruído contra uma varredura, ou um objeto deformável predito contra uma forma-alvo. A distância de Chamfer oferece uma forma rápida e diferenciável de pontuar essas comparações, e é por isso que aparece tanto como loss de aprendizado quanto como custo em planejamento.

Principais aplicações

Loss de treinamento para redes de reconstrução de nuvens de pontos e de completamento de formas
Custo de planejamento para moldar objetos deformáveis em direção a um alvo
Métrica de avaliação para reconstrução 3D e mapeamento
Treinamento de modelos de dinâmica aprendidos baseados em partículas
Comparação de estados de objetos simulados e observados na calibração de simuladores

Na prática

Na manipulação de objetos deformáveis, um robô que modela massa captura uma nuvem de pontos da massa atual e dispõe de uma nuvem de pontos da forma-alvo. Um modelo de dinâmica aprendido prevê os pontos da massa após cada ação candidata da ferramenta; o planejador pontua cada predição pela distância de Chamfer até o alvo e executa a melhor. As duas nuvens são primeiro subamostradas para um número fixo de pontos, muitas vezes com amostragem do ponto mais distante (farthest point sampling), para que o custo seja rápido de calcular e comparável entre passos. A equipe registra exatamente qual variante usa, ao quadrado ou não e média ou soma, porque valores de definições diferentes não podem ser comparados.

Equívocos comuns

A distância de Chamfer tem uma fórmula padrão — os artigos diferem quanto a distâncias ao quadrado ou simples, média ou soma, e como as duas direções são combinadas, então os números só são comparáveis sob a mesma definição
Uma distância de Chamfer baixa significa que as distribuições de pontos coincidem — ela ignora como os pontos se espalham pela superfície; a Earth mover's distance é sensível a isso
Uma direção basta — medir apenas da predição para o alvo recompensa uma predição que cobre bem uma pequena parte do alvo

Quem deve saber

Pesquisadores de percepção 3D e aprendizado que trabalham com nuvens de pontos
Pesquisadores de manipulação que trabalham com objetos deformáveis
Engenheiros de mapeamento que avaliam a qualidade da reconstrução

Tecnologias relacionadas

Earth Mover's Distance
Distância de Hausdorff (Hausdorff Distance)
F-score (reconstrução 3D)
Árvore k-d (k-d Tree)
PointNet

Termos relacionados

Projetos relacionados

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