グラフィカルモデルと点パターンマッチング

この論文では、任意の次元のユークリッド空間における剛体点パターンマッチング問題に対する新たな解決策を示します。剛体運動を仮定していますが、ジッタは許可されています。ノイズのない場合に最適な解を見つけることが保証されている非反復的な多項式時間アルゴリズムを提案します。まず、点パターンマッチングを重み付きグラフマッチング問題としてモデル化し、重みはノード間のユークリッド距離に対応します。その後、グラフマッチングをグラフィカルモデルにおける最大確率構成を見つける問題として定式化します。グラフの剛性の議論を用いることで、スパースグラフィカルモデルがノイズのない場合に完全に接続されたモデルと同等の結果をもたらすことを証明します。これにより、多項式時間で実行され、ノイズのない点集合間の厳密なマッチングに対して理論的に最適なアルゴリズムを取得することが可能になります。不正確なマッチングに対しても、同じアルゴリズムを適用して近似最適解を見つけることができます。私たちのアプローチによって得られた実験結果は、特に異なるサイズのパターンをマッチングする際に、現在の手法に対して精度の向上を示しています。