データ分析基礎知識
“分析力をコアとするデータソリューションカンパニー”
株式会社ALBERTが、データ分析にまつわる基礎知識をわかりやすく解説します。
“分析力をコアとするデータソリューションカンパニー”
株式会社ALBERTが、データ分析にまつわる基礎知識をわかりやすく解説します。
3次元形状の計測が高速に行えるようになるとともに、計測されたデータの統合による3次元再構成、3次元化された形状の比較による検査、計測位置の軌跡推定、形状からのオブジェクトの認識、動作の推定、等々3次元データの活用は様々な分野に広がってきました。（表1）
本稿では、上記のような3次元データの活用で用いられる技術のうち、異なる位置から撮影した3次元点群同士の位置関係を推定し、点群の合成を行うアルゴリズムの一つであるICPマッチングアルゴリズムについて紹介します。
3次元データの活用において、異なる位置から撮影した3次元点群同士の位置関係を推定し、点群の合成を行う処理を一般に「位置合わせ（registration, alignment, pose estimation, motion estimation）」と言います。ICPマッチングアルゴリズムとは、多数ある位置合わせアルゴリズムの一つです。ICPアルゴリズムでは、異なる位置から取得された次元点群 Ps, Pt が与えられた時、PsをPt に位置合わせする回転行列Rと並行移動行列を求める事を目的とし、以下の手順で回転行列Rと並行移動行列Tを推定します。
最近傍検出アルゴリズム(k近傍法, KDTree, Octree等)を用いPsの各点Psi に最も近い点Ptjを対応させます。（図1）
また、ICPアルゴリズムでは２つの点群の初期位置が大まかに合っている必要があり、角度や位置の大きなズレに弱いことが知られています。
1-1で定めた対応点同士の目的関数Eを定義し、Eが最も小さくなるRとTを推定します。
対応点同士の距離の2乗の和が最も小さくなるようにRとTを推定する手法です。
対応する点へのベクトルとPtの法線の内積が最も小さくなるようにRとTを推定する手法です。
※ほとんどの場合Ptの法線はPtとその近傍点から近似平面を求めることで推定します。
一般的にpoint-to-pointよりもpoint-to-planeの方が最適化の精度が良いことが知られています。
※ただし法線情報が必要となるため、元データが単純な座標値から構成された点群だった場合、前処理として法線推定に計算時間がかかります。
1-2で求まったRとTによってPsを移動させた後の各点に最も近いPtの対応点を選択します。（図3）
以下のようにして反復します（図4）
【2回目試行】
(1-2)最近傍検索による対応点の選択を行います。
↓
(1-3)目的関数最小化に基づいた初期ポジションからの移動を行います。
(初期ポジションからの移動の移動は行いません。)
↓
【3回目試行】
(1-2)最近傍点検索による対応点の選択を行います。
↓
(1-3)目的関数最小化に基づいた初期ポジションからの移動を行います。
(初期ポジションからの移動の移動は行いません。)
↓
・
・
・
反復回数 k+1 回目反復回数 k 回目のEの差が、収束判定閾値よりも小さくなった場合終了とします。
実際に計測したデータを元にICPアルゴリズムを適用した場合、以下のようになります。
また、本稿で紹介したような位置推定アルゴリズム（ICPアルゴリズム）の発展形として、自動運転等で利用されるSLAMアルゴリズムが挙げられます。（図6）
SLAMでは移動しながら3次元センサーで点群を取得し、自己位置推定と周囲の環境地図作成を同時に行います。前者の自己位置推定にしばしば用いられるのがICPアルゴリズムで、この場合は作成された環境地図と新しく取得した点群の間でマッチングを行い、地図中の自己位置推定を行います。ループの処理など、蓄積した誤差を修正する処理もバックエンドで行われています。センシング技術の発展や価格動向、コンピューターの処理能力向上などの観点から、今後ますますICPなどのマッチングアルゴリズムが広く利用されていくことは間違いないでしょう。
