Chamfer Distance

• 別名: CD, chamfer loss
• カテゴリ: Sensing › Perception outputs
• タグ: point-cloud, loss-function, evaluation-metric, 3d-perception, deformable-objects

各点をもう一方の集合の最近傍と対応づけ、それらの距離を両方向で組み合わせることで求める、2 つの点集合の違いの尺度。

定義

Chamfer 距離（Chamfer distance）は、どの点がどの点に対応するかを知らなくても 2 つの点群を比較できる。1 つ目の集合の各点について、2 つ目の集合で最も近い点を見つけてその距離を記録し、次に 2 つ目の集合から 1 つ目の集合へ同じことを行い、2 つの方向の項を組み合わせる。よく使われる形式では、各方向で最近傍距離の二乗を平均し、その 2 つの平均を足し合わせるが、平均の代わりに総和をとるものや、二乗ではない通常の距離を使うものもある。名前は、1970 年代後半の画像解析手法で、距離変換を使ってエッジマップを比較した Chamfer マッチング（chamfer matching）に由来する。

両方の方向が重要である。予測から目標への測定は、予測したすべての点が目標の近くにあるかどうか（精度）を確かめ、目標から予測への測定は、目標のすべての部分が覆われているかどうか（完全さ）を確かめる。目標の 1 つの領域に縮退した予測は、1 つ目の方向ではよいスコアになるが、2 つ目の方向では悪いスコアになる。2 つの集合の点数が同じである必要はないので、センサデータとモデルの出力を比べるのに便利である。

Chamfer 距離は、k-d 木のような最近傍探索の構造を使うか、GPU 上の総当たりで安価に計算でき、点の位置についてほぼ至るところで微分可能である。そのため、点群生成や形状補完の学習損失として、また計画のコストとして広く使われている。主な弱点は、点がどう分布しているかを無視することであり、固まった点でも低い値になりうる。Earth mover's distance は、同じ大きさの集合の間で一対一の対応を求めることでこれに対処するが、計算コストは高くなる。また、距離しきい値における F-score がしばしば併せて報告される。Hausdorff 距離は関連する尺度で、平均ではなく最悪の最近傍距離をとる。

重要な理由

ロボティクスの多くの問題では、再構成した物体とスキャンの比較や、予測した変形物体と目標形状の比較のように、点の対応が存在しない形状を比べる必要がある。Chamfer 距離はこうした比較を高速かつ微分可能な形で評価できるため、学習損失としても計画のコストとしても登場する。

主な用途

• 点群再構成ネットワークや形状補完ネットワークの学習損失
• 変形物体を目標の形に成形するための計画コスト
• 3D 再構成とマッピングの評価指標
• 学習による粒子ベースの動力学モデルの訓練
• シミュレーターのキャリブレーションにおける、シミュレーションと観測の物体状態の比較

実際の使われ方

変形物体のマニピュレーションで、生地を成形するロボットは、現在の生地の点群を取得し、目標形状の点群をもっている。学習した動力学モデルが、候補となる各工具動作の後の生地の点を予測し、プランナーは各予測を目標との Chamfer 距離で評価して最良のものを実行する。両方の点群はまず固定数の点にダウンサンプリングされ、多くの場合は最遠点サンプリングが使われるので、コストを高速に計算でき、ステップ間でも比較できる。異なる定義の値は比較できないため、チームは二乗するかどうか、平均か総和かなど、使っている変種を正確に書き留めておく。

よくある誤解

• Chamfer 距離には標準的な式が 1 つある — 二乗距離か通常の距離か、平均か総和か、2 方向をどう組み合わせるかは論文によって異なるので、数値は同じ定義のもとでしか比較できない
• Chamfer 距離が低ければ点の分布も一致している — 点が表面にどう広がっているかは無視される。Earth mover's distance はこれに敏感である
• 一方向だけで十分である — 予測から目標への方向だけを測ると、目標の小さな部分だけをよく覆う予測が有利になってしまう

知っておくべき人

• 点群を扱う 3D 知覚と学習の研究者
• 変形物体に取り組むマニピュレーションの研究者
• 再構成の品質を評価するマッピングのエンジニア

関連技術

• Earth Mover's Distance
• Hausdorff 距離（Hausdorff Distance）
• F-score（3D 再構成、3D Reconstruction）
• k-d 木（k-d Tree）
• PointNet

関連用語

• Point Cloud
• Iterative Closest Point
• Forward Dynamics Model
• Neural Implicit Representation
• Farthest Point Sampling

関連プロジェクト

• 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