データ分析基礎知識

“分析力をコアとするデータソリューションカンパニー”
株式会社ALBERTが、データ分析にまつわる基礎知識をわかりやすく解説します。

ICPアルゴリズムとは

3次元形状の計測が高速に行えるようになるとともに、計測されたデータの統合による3次元再構成、3次元化された形状の比較による検査、計測位置の軌跡推定、形状からのオブジェクトの認識、動作の推定、等々3次元データの活用は様々な分野に広がってきました。(表1)

 
表1. 3次元測距データ利用領域の例

 

本稿では、上記のような3次元データの活用で用いられる技術のうち、異なる位置から撮影した3次元点群同士の位置関係を推定し、点群の合成を行うアルゴリズムの一つであるICPマッチングアルゴリズムについて紹介します。

 

1. ICP ( Iterative Closest Point) アルゴリズムとは

3次元データの活用において、異なる位置から撮影した3次元点群同士の位置関係を推定し、点群の合成を行う処理を一般に「位置合わせ(registration, alignment, pose estimation, motion estimation)」と言います。ICPマッチングアルゴリズムとは、多数ある位置合わせアルゴリズムの一つです。ICPアルゴリズムでは、異なる位置から取得された次元点群 Ps, Pt が与えられた時、PsPt に位置合わせする回転行列Rと並行移動行列を求める事を目的とし、以下の手順で回転行列Rと並行移動行列Tを推定します。

1-1. 初期対応点の選択

最近傍検出アルゴリズム(k近傍法, KDTree, Octree等)を用いPsの各点Psi に最も近い点Ptjを対応させます。(図1)
また、ICPアルゴリズムでは2つの点群の初期位置が大まかに合っている必要があり、角度や位置の大きなズレに弱いことが知られています。

picture1
図1. ICPアルゴリズム 対応点検索 1回目

 

 

1-2. パラメータ の推定

1-1で定めた対応点同士の目的関数Eを定義し、Eが最も小さくなるRTを推定します。

picture2
図2. ICPアルゴリズム 1回目試行
(本例では4つの点が1つの点に対応しているため、R,Tで変換後はPt0Psの重心に来ています)

 

・手法1. point-to-point

対応点同士の距離の2乗の和が最も小さくなるようにRTを推定する手法です。

・手法2. point-to-plane

対応する点へのベクトルとPtの法線の内積が最も小さくなるようにRとTを推定する手法です。
※ほとんどの場合Ptの法線はPtとその近傍点から近似平面を求めることで推定します。

 

一般的にpoint-to-pointよりもpoint-to-planeの方が最適化の精度が良いことが知られています。 
※ただし法線情報が必要となるため、元データが単純な座標値から構成された点群だった場合、前処理として法線推定に計算時間がかかります。

 

1.3 移動後の対応点の選択

1-2で求まったRとTによってPsを移動させた後の各点に最も近いPtの対応点を選択します。(図3)

picture3
図3. ICPアルゴリズム対応点検索 2回目以降

 

 

1-4.  反復

以下のようにして反復します(図4)

【2回目試行】
(1-2)最近傍検索による対応点の選択を行います。

(1-3)目的関数最小化に基づいた初期ポジションからの移動を行います。
(初期ポジションからの移動の移動は行いません。)


【3回目試行】
(1-2)最近傍点検索による対応点の選択を行います。

(1-3)目的関数最小化に基づいた初期ポジションからの移動を行います。
 (初期ポジションからの移動の移動は行いません。)




図4. ICPアルゴリズム 反復試行

 

 

1-5.  収束判定

反復回数 k+1 回目反復回数 k 回目のEの差が、収束判定閾値よりも小さくなった場合終了とします。

 

実際に計測したデータを元にICPアルゴリズムを適用した場合、以下のようになります。


図5. ICPによる点群マッチング例
(本例では側面から計測した点群データと水平45度ずらした位置から計測した点群データを合成してウサギの像の3D点群モデルを作成しています)

 

 

2. ICPアルゴリズムの応用例

また、本稿で紹介したような位置推定アルゴリズム(ICPアルゴリズム)の発展形として、自動運転等で利用されるSLAMアルゴリズムが挙げられます。(図6)

SLAMでは移動しながら3次元センサーで点群を取得し、自己位置推定と周囲の環境地図作成を同時に行います。前者の自己位置推定にしばしば用いられるのがICPアルゴリズムで、この場合は作成された環境地図と新しく取得した点群の間でマッチングを行い、地図中の自己位置推定を行います。ループの処理など、蓄積した誤差を修正する処理もバックエンドで行われています。センシング技術の発展や価格動向、コンピューターの処理能力向上などの観点から、今後ますますICPなどのマッチングアルゴリズムが広く利用されていくことは間違いないでしょう。

picture6
図6. SLAM ICPアルゴリズムの応用例
※出典:Kitware LidarView github https://github.com/Kitware/LidarView/blob/master/Documentation/How-To-SLAM-With-Veloview.md

 

このページをシェアする
ALBERTは、日本屈指のデータサイエンスカンパニーとして、データサイエンティストの積極的な採用を行っています。
また、データサイエンスやAIにまつわる講座の開催、AI、データ分析、研究開発の支援を実施しています。

・データサイエンティストの採用はこちら
・データサイエンスやAIにまつわる講座の開催情報はこちら
・AI、データ分析、研究開発支援のご相談はこちら