ドラえもん

プログラミング/画像情報処理

回転空間SO(3)の均等なサンプリング

・回転空間SO(3)の均等なサンプリング

 3次元回転における規則的サンプリングの生成問題は、生物学、科学、物理学などの多くのコンピュータサイエンスの分野において、基礎的な問題である。

 連続空間上の数値計算は、しばしばサンプリング集合の生成を必要とする。数値的な最適化や統合問題だけではなく、ロボットの動作計画における衝突回避経路の生成などの、技術的あるいは科学的な分野における様々な手法の性能は、サンプリングの質に大きく依存している。したがって、根本的なサンプリングの質が出来る限り良好であることは、非常に重要となる。

 通常、物体はある回転軸方向を中心にして回転を行うものと定義できる。下記の図1左は、回転軸方向の緯度経度によるサンプリングであるが、このサンプリングの仕方では北極南極点付近はサンプリング点が非常に密になってしまい、非常に無駄なサンプリングの仕方になってしまっていることがわかるだろう。

 

f:id:ikaros2015:20150121162809p:plain

 

 そこで、Anna Yershova らによる研究「 Generating Uniform Incremental Grids on SO(3) Using the Hopf Fribration  」では、この3次元回転の均等なサンプリングを実現している。彼らの研究では、3次元の回転を、四元数を用いて表している。彼らの研究のポイントは、Hopf Fibration の概念に基づき、先行研究である HEALPix を用いた2次元球面の等面積サンプリングと回転平面の等間隔サンプリングを組み合わせることで、3次元回転の均等なサンプリングを実現している点である。図2では、HEALPix を用いた2次元球面の等面積サンプリングとそれに対応する回転平面の等間隔サンプリングを示している。

f:id:ikaros2015:20150121165307p:plain

 

 ここで、彼らの研究のサンプリング効率を示す。図3では、図2左に示した2次元球面のサンプリングと、緯度・経度による2次元球面の通常のサンプリングを比較している。

f:id:ikaros2015:20150121165359p:plain

 

図3における2つの2次元球面のサンプリングを比べると、彼らの研究における2次元球面の等面積サンプリングは、サンプリング点を12点生成しているのに対し、通常の緯度・経度による等間隔サンプリングは、サンプリング点を約18点生成している。すなわち、彼らの研究における3次元回転の均等なサンプリングでは、サンプリング効率は約 12/18 = 2/3 まで抑えられている。

 また、彼らの3次元回転の均等サンプリングでは、回転のサンプリングを階層的に行うことができる。図4には、階層化されたサンプリング点が表されている。

f:id:ikaros2015:20150121165500p:plain

 

この構造を利用することにより、最適化問題などにおいて、粗い解像度から密な解像度へ最適な回転パラメータを高速に探索することが可能となる。

□ 英論文:Generating Uniform Incremental Grids on SO(3) Using the Hopf Fribration  

http://msl.cs.uiuc.edu/~yershova/journals/SO3-ijrr2009/author/main.pdf

□ 英論文:HEALPix:a framework for high-resolution discretization and fast analysis of data distributed on the sphere

http://web.ipac.caltech.edu/staff/fmasci/home/astro_refs/HEALPix.pdf

 

・回転空間SO(3)の均等なサンプリングのサンプルプログラム

 彼らは回転空間SO(3)の均等なサンプリングのサンプルプログラムを以下のサイトで公開している。プログラムは C/C++ で記述されており、サイトからダウンロードして使用することが可能なようである。  

□ サンプルプログラム配布サイト

http://msl.cs.uiuc.edu/~yershova/software/so3sampling/so3sampling.htm

 しかし、彼らの配布するサンプルプログラムでは、3次元の回転を階層的にサンプリングした際の、解像度レベル間でのサンプリング点の対応関係が出力されない。そこで、彼らのサンプルプログラムを改良したプログラムを以下に示す URL に保存する。

□ 改良版サンプルプログラム配布サイト

https://github.com/Jingasan/UniformSamplingOnSO3

 本プログラムは、彼らの研究によるサンプリング方法を改良して実装したものである。解像度レベルを指定し、プログラムを実行すると、各回転を表す四元数のパラメータ4個と次の解像度において近傍となる回転のID番号8個、各回転を表す角度のパラメータ4個と次の解像度において近傍となる回転のID番号8個が、それぞれエクセルファイルに出力される。