ICP
Besl & McKay 1992 · 論文
一行要約 — Iterative Closest Point (ICP) アルゴリズムを導入した論文であり、点対の距離を反復的に最小化することで3次元点集合を剛体的に位置合わせする基礎的な手法である。
問題
異なる視点やセンサーから取得された3次元形状の位置合わせは、物体認識、検査、再構成にとって不可欠である。従来の手法は手動で指定された対応関係や、形状のトポロジーに関する制約的な仮定を必要としていた。どの点がどの点に対応するかを知らずに、生の点データのまま自由形状の3次元データを位置合わせできる、汎用的で自動的な手法が必要とされていた。
手法とアーキテクチャ
ICPは2つのステップを交互に繰り返し、各ステップは位置合わせ誤差を減少させることしかできない。
- 最近点対応付け。 元集合内の各点について、現在の変換推定の下で目標集合内の最近点を見つける。未知のデータ対応関係は最近傍によって近似され、位置合わせが改善されるにつれて精度も向上する——手動での対応付けや特徴マッチングは不要である。
- 最適な剛体変換。 対応関係が与えられたとき、平均二乗誤差の目的関数
を最小化する回転と平行移動を計算する。これは、中心化された点集合の相互共分散行列のSVD、あるいは原論文で用いられた単位四元数法によって、閉形式で解ける。 3. 収束まで反復する。 変換を適用し、最近点対応関係を再計算し、平均二乗誤差の変化が閾値を下回るまで繰り返す。
両ステップとも誤差を減少させるため、この反復は平均二乗距離の局所最小値へ単調に収束する。
ICPが実際にどのように使われるかを決定づける、重要な特性と改良点を以下に示す。
- 局所収束のみ: ICPは適切な初期化を必要とする。大きなずれがあると誤った局所最小値に陥る。SLAMでは、この初期化は直前フレームの姿勢、等速運動モデル、あるいはcoarse-to-fineのピラミッドから得られる。
- 点-平面バリアント(Chen & Medioni 1992): 点対点の残差を、目標表面の法線を用いたに置き換えることで、平坦な領域が互いに滑るように動けるようになり、構造化されたシーンではるかに速く収束する——これはKinectFusionがフレーム対モデルトラッキングに用いるバリアントである。
- エンジニアリング的な手法群(Rusinkiewicz & Levoy 2001によるサーベイ): 最近傍探索のためのk-d木、サブサンプリング、距離/法線適合性による不良対応の除外、ロバストな重み付け。後発のバリアントには、Generalized ICP、trimmed ICP(部分的な重なり)、symmetric ICP、colored ICPなどがある。
実験結果
原論文であるTPAMI 1992は、幾何プリミティブ(球、円柱)と複雑な自由形状表面の位置合わせを示し、収束は典型的に10〜50回の反復以内であった。同時に、初期化への感度が記録されており、これは今日でもICPの主な失敗モードとなっている(全文は有料であり、結果は付随する書籍の章で要約されたものである——詳細な評価は原論文を参照)。ICPは3次元点群位置合わせの標準的なアルゴリズムとなった。ほぼすべての密なRGB-D SLAMシステムがトラッキングにICPバリアントを用いており、LiDAR SLAMにおけるスキャンマッチングの基礎でもあり、医療画像処理や産業検査にも広く普及した。
SLAMにおける意義
ICPは3D-3D位置合わせの基礎である。ほぼすべての密なRGB-D SLAMシステム(KinectFusion、ElasticFusion、InfiniTAM)は、入力される深度フレームとマップの間で何らかのICPバリアントを実行することでカメラを追跡する。LiDAR SLAMにおいても同様に中心的であり、そこでのスキャンマッチングは本質的にエンジニアリング的な改良を加えたICPである。ICP——そのコスト関数、閉形式解、そして失敗モード——を理解することは、レベル4全体でのフレーム対モデルトラッキングを理解するための前提条件である。