先日社内の勉強会で，グローバル最適なIterative Closest Point(ICP)アルゴリズム”Go-ICP”について紹介しました．

ICPは有名なところではKinect Fusionなど，3次元点群のレジストレーションに広く用いられています．基本的には，最近傍点の対応付けと姿勢(並進と回転)の推定を順次繰り返していくことで，点群間の2乗誤差を最小にするような姿勢を見つけようとアルゴリズムです．

ICPは原理上，点群間の姿勢がある程度離れると局所解に陥ってしまい正しくレジストレーションできないという課題があります．

そこで，局所性を改善したアルゴリズム(SoftAssign など)や，ローカルな特徴(Spin Imageや4PCSなど)を用いて大域的にレジストレーションする手法など多様なアルゴリズムが提案されていますが，グローバル”最適”な点群のレジストレーションアルゴリズムはあまり提案されていませんでした．

2013 ICCV,2015 PAMIの論文でグローバル最適なICPアルゴリズムGo-ICPが発表されました．詳しくはスライドで解説していますが，Branch and Bound(分枝限定)とVoxel ICPの組み合わせで効率的にSE(3)の6自由度パラメータ空間から最適な解を探します．

著者のページにソースコードが公開されていますので簡単に試すことができます．公開されているソースはテキストファイルから点群データを読み込んで姿勢をテキストファイルで書き出す仕様になっていますが，外部ライブラリの依存がなく簡単にMatlabのmex関数を作成できますので，いろいろ点群を変えて試したい場合はmex化がオススメです．

記事一覧へ