要約
大規模なシーンにおけるデータ取得は、通常、複数回のスキャンにわたって情報を蓄積する必要がある。一般的な手法として、反復最密点法（Iterative Closest Point: ICP）またはその変種を用いてスキャンペアを局所的に整合させる方法があるが、これはシーンが静止しており、スキャンペア間の動きが小さいことを前提としている。この制約により、複数のスキャンセッションや異なる取得モダリティ（例：ステレオ、深度スキャン）にわたるデータの蓄積が困難となる。一方で、スキャンが任意の初期姿勢にあっても対応できるグローバルな登録手法を用いることも可能である。現行の最先端グローバル登録手法である4PCSは、データポイント数に対して二次時間計算量を示すため、大規模環境の取得には著しく適用範囲が制限される。本研究では、線形時間（データポイント数に比例）で実行され、かつスキャンペア間の重複（未知）に基づいたアライメント問題の複雑さに応じて出力に敏感な最適なグローバル点群登録手法「Super 4PCS」を提案する。技術的には、本アルゴリズムを「インスタンス問題」として定式化し、スマートなインデキシングデータ構造を用いて効率的に解く。このアルゴリズムはシンプルでありながら、メモリ効率が高く、高速である。実験により、Super 4PCSは従来手法と比較して顕著な高速化を実現し、これまで不可能であったスケールのシーンを非構造的かつ効率的に取得することが可能となることを示した。研究用に完全なソースコードおよびデータセットは、http://geometry.cs.ucl.ac.uk/projects/2014/super4PCS/ にて公開されている。