Programming for Beginners Programming for everyone!

Rigid-ICP法の概要

点群あるいは、メッシュ等で表された形状同士の位置を揃える、という問題は非常に一般的な問題で、形状処理やコンピュータ・ビジョンの分野で広く研究されている。なお、以下では剛体変換による位置揃え、すなわちRigid-ICPのことを単にICPと呼ぶこととする。

点群同士の位置を揃えるという問題は、古くは1987年にArunらによって研究1などが代表的だが、ICPという言葉が初めて登場したのは1992年のBeslらの研究であるとされている2。Beslらの手法では、剛体変換に含まれる回転を四元数を用いて表し、それに並進を表す3次元ベクトルを加えた合計7次元のベクトルを未知数として、最適な剛体変形を求めるという問題を解いている。

いずれの場合も、二つの点群が与えられた場合に、それらの位置を揃えるのに最適な剛体変換を何らかの方法で求める、ということが主眼であり、ICP法は特にその処理を繰り返すことで、位置揃えの精度を高めている。

今、位置揃えの目的位置を表す点群を$\mathcal{U} = \{ \mathbf{u}_j \}_{j=1}^M$、移動を伴って位置揃えされる点群を$\mathcal{X} = \{ \mathbf{x}_i \}_{i=1}^N$とする。この場合、ICP法のステップは上記の最適な剛体変換を求めるステップを以下の要領で繰り返される。

  1. 各$\mathbf{x}_i$について$\mathcal{U}$の中で最も位置が近い点を取り出し、それを$\mathbf{p}_i$とする。
  2. $\mathbf{x}_i$を$\mathbf{p}_i$へと移動するのに必要な剛体変換を何らかの方法で求める (特異値分解, 非線形最適化など)。
  3. 求めた剛体変換で$\mathbf{x}_i$の位置を更新し、移動量が十分に小さくなるまで1-2の処理を繰り返す。

これらをプログラムとして実装するため、以降ではまずk-d木を用いた最近傍点の探索について見ていく。また、上記の処理でポイントとなるのはどのように点同士の近さを定義するかとどのように剛体変形を求めるかの2点であるので、今回は、距離の近さを単純なユークリッド距離としたPoint-to-Point ICPと、点群に法線方向が与えられている場合に、その法線方向に沿った距離を用いるPoint-to-Plane ICPの2種類について見ていくことにする。

Point-to-Point ICPでは、上記のArunらの論文で紹介されている特異値分解を用いた剛体変換の求め方を利用する。一方でPoint-to-Plane ICPではその距離の定義の違いから特異値分解を利用できないため、ICPの繰り返し計算の各ステップで与えられる剛体変換の回転成分が微小であると仮定し、一般的な線形変換で近似するLinearized Rotationを用いる。

また、今回解説するPoint to Point ICPならびにPoint to Plane ICPの説明にあたっては以下のGitHubならびに、日本語の解説記事を参考にしたので、より詳しい説明が知りたい場合には目を通してみると良い。

参考文献

  1. Arun et al., “Least-Squares Fitting of Two 3-D Point Sets,” PAMI, 1987. ↩

  2. Besl and McKey, “A Method for Registration of 3-D Shapes,” PAMI, 1992. ↩

comments powered by Disqus