Comments
Description
Transcript
複数の点群に対する位置合わせ手法の性能 比較 - 美濃研究室
特別研究報告書 複数の点群に対する位置合わせ手法の性能 比較 指導教員 美濃 導彦 教授 京都大学工学部情報学科 中井 康博 平成 24 年 2 月 2 日 i 複数の点群に対する位置合わせ手法の性能比較 中井 康博 内容梗概 リアルな CG 映像コンテンツの作成や，自動車事故の被害予測システムの開 発などへの利用を目的とし，実物を忠実に再現した 3 次元モデルに対する需要 が高まっている．実物体の 3 次元点群を精度よく計測できる手法の 1 つに，パ ターン光投影法がある．この手法では，実物体を複数方向からカメラで観測し， 三角測量の原理を用いて表面の三次元点群を獲得する．しかし，カメラで観測 できる部分しか点群を獲得できず，1 度では物体の全周を計測できないので，複 数の視点から計測を行う必要がある．こうして得られた複数の部分点群から 1 つの形状モデルを構築する際，計測時の視点の違いを補正するために，回転+ 並進で表される剛体変換を部分点群に施す．この処理を位置合わせ，剛体変換 を求めることを運動推定と呼ぶ．本研究では，全周点群を獲得するために，複 数の部分点群を精度よく位置合わせすることを目的とする． 本研究では，位置合わせの手法の 1 つとして ICP(Iterative Closest Point) ア ルゴリズムを用いる．ICP アルゴリズムは，入力として与えられる 2 つの点群 の位置合わせを自動で行う．一方の点群を構成する各点に対し，他方の点群に おける最近傍点を探索し，これらを仮の対応点とする．このような対応点間の 距離を最小化するような剛体変換を推定する．この対応点探索，剛体変換推定 を繰り返すことで，2 つの点群を位置合わせする運動を推定する． ICP アルゴリズムでは，2 つの点群を位置合わせする運動が大きい場合，適 切な初期値を設定しないと対応点探索がうまくいかず，運動推定が局所解に陥 り不安定になるという問題がある．そのため，本研究では運動する物体に対し て連続的に形状計測を行って点群の系列を獲得し，この系列内で隣接する点群 に対して位置合わせすることで，運動推定が局所解に陥ることを防ぐ． 複数の点群の位置合わせは，原理的には上述の隣接した 2 つの点群に対する 位置合わせを繰り返し行うことで実現できる．隣接する点群間で推定した剛体 変換を積算していくことで，隣接していない 2 つの点群同士でも位置合わせが 可能となる． 本研究では，これを隣接位置合わせと呼ぶ．隣接点群間での運動 推定では局所解の問題は起こりにくいが，この推定結果には微小な誤差が残っ ているため，変換の積算により誤差が蓄積するという問題がある．本研究では ii 位置合わせの順序を工夫し，蓄積した誤差を解消するような位置合わせをさら に行うことで精度の向上を試みる． 本研究では，逐次位置合わせと階層的位置合わせの 2 つを行う．逐次位置合 わせでは，複数ある点群のうち先頭 2 つの隣接点群にだけ ICP 位置合わせを行 ない，位置合わせした 2 つの点群を 1 つにまとめる．これにより位置合わせす べき点群の数は 1 つ減る．このような処理を，全ての点群が位置合わせされる まで繰り返す．この手法では，推定した剛体変換の積算を行わないため，誤差 の蓄積は抑えられると考えられる．しかし，位置合わせする点群を構成する点 の数は次第に増えていくため，位置合わせにかかる計算時間もそれに従い増え るという問題もある．もう一方の階層的位置合わせでは，複数ある点群を，先 頭から順に均等な個数の点群を含むブロックに分ける．各ブロックで，その先 頭の点群に位置合わせし，1 つの点群にまとめる．このような処理を，点群の 個数が一つになるまで階層的に行う． 以上のような位置合わせ手法の精度を定量的に評価するため，本研究では 2 つの実験を行った．1 つめの実験では，ICP による 2 つの点群間の運動推定の 安定性について，点群間の運動の大きさと位置合わせ精度との関係を分析した． その結果，隣接位置合わせにおいては，点群間の運動の回転成分が 1.2 °/frame から 1.8 °/frame 程度であれば安定な位置合わせが可能なことを定量的に判断 できた．2 つめの実験では，1 つ目の実験の結果に基づき，複数点群の位置合わ せについて，隣接位置合わせ・逐次位置合わせ・階層的位置合わせの 3 つの位置 合わせ手法を適用し，これらの精度と計算時間について性能比較を行った．複 数の ICP 位置合わせ結果について，その善し悪しを見ためで評価することはで きるが，定量的精度評価は容易でない．本研究では，計測物体にマーカを貼付 して物体の運動を計測し，これを用いて精度のよい位置合わせを実現する．こ れとの比較により，ICP 位置合わせの精度を定量的に評価する．以上の実験に より，隣接位置合わせを改良した逐次位置合わせ・階層的位置合わせの 2 つの 手法のうち，運動推定の精度のみでは逐次位置合わせが，運動推定の精度・計 算時間の両面を含めて考えると階層的位置合わせが優れているという結果が得 られた． iii Comparing performance among registration methods of multi-view Point Clouds Yasuhiro NAKAI Abstract 3D models are useful for making realistic CG contents and improving systems for prediction of traffic accident and so on. It is desirable that such 3D models are acquired from real objects. Range scanner is one of the accurate methods of capturing 3D shapes of a real object. Because this method is based on the principles of triangulation, we cannot acquire whole shapes, but only partial shape which is visible from single viewpoint. In order to capture whole shape, we need to capture the object from multiple viewpoints and align them appropriately. Such alignment is performed by estimating the optimal rigid transformations from the captured shapes. This process is called as registration, and estimating the rigid transformations as motion estimation. We aim to realize accurate registration for acquiring complete 3D model from captured shapes. ICP (Iterative Closest Point) algorithm is a well-known method of registration. ICP algorithm automatically performs registration for given pair of partial shape. Each shape generally consists of many points. This method makes correspondence of points between the shapes by finding closest point of one shape for each point of the other. Then this method estimates the rigid transformation that minimizes the sum of distance between corresponding points. By iteratively making correspondence and estimating rigid transformation, we can perform registration for given shapes. When the rigid transformation to be estimated is large, ICP algorithm requires good initial transformation or iterative improvement fails. In order to prevent such failure, we acquire sequence of partial shapes by capturing the slowly moving object, and we perform the registration for neighboring shapes. In order to align multiple partial shapes for acquiring whole one, we need to align every shape into common partial shape. In order to perform registration for pair of distant shapes, which are each shape and the common one, we repeatedly estimate the transformation for pair of adjacent shapes and accumu- iv late them for performing registration for pair of distant shapes. This method, we denote initial registration, can avoid to fail registration. However, since the transformations that are estimated between adjacent shapes have small error, it leads accumulated error in the registration for distant pair. In order to improve the accuracy, we propose methods of registration that remove the accumulated error by running thorough the registration. In this study, we used a method; sequential registration, and proposed another method; hierarchical registration. In sequential registration, we perform ICP registration for first two adjacent shapes in the sequence, and integrate them into one shape. This process decreases the number of shapes in the sequence one by one. We repeat this process until all the shapes in the sequence are integrated into one shape. Since this method does not accumulate rigid transformations, we can say that registration error is not accumulated. However, the number of points in the first shape increases in steps, thus the registration takes more computational cost. In hierarchical registration, we divide all shapes in turn into some blocks that include a certain number of shapes. In each block, we perform the initial registration and integrate them into one shape. We repeat this process until we acquire only one integrated shape. To evaluate the accuracy of these registration methods quantitatively, we performed two experiments. In first experiment, we investigate the relation between the stability of registration for two shapes and the amount of motion. In second experiment, we performed the registration methods for multiple shapes, and compared the accuracy and computational costs. We can evaluate the accuracy of them visually, but quantitative evaluation is difficult. In this study, we put fluorescent markers on the object and measure its rigid motion as groundtruth. By comparing the registration using the markers and ICP registration, we evaluate the accuracy of them quantitatively. Because of these experiments, we can say that sequential registration the best about the accuracy and hierarchical registration is the best about computational cost. 複数の点群に対する位置合わせ手法の性能比較 目次 第1章 はじめに 1 第2章 2 つの点群の位置合わせ 2 2.1 点群の獲得 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 運動が既知である場合の位置合わせ . . . . . . . . . . . . . . . . . . . . 4 2.3 点群の計測環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 第3章 位置合わせのための運動推定 6 3.1 マーカを利用する運動推定と位置合わせ . . . . . . . . . . . . . . . . . 6 3.2 ICP アルゴリズム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.3 2 つの運動推定における利点と問題点 . . . . . . . . . . . . . . . . . . . 10 第4章 複数の点群の位置合わせ 11 4.1 隣接位置合わせ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 逐次位置合わせ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.3 階層的位置合わせ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 第5章 位置合わせ手法の性能比較 18 5.1 位置合わせの正確さの指標 . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.2 離れた点群の位置合わせ誤差を比較 . . . . . . . . . . . . . . . . . . . . 19 5.3 3 つの ICP 位置合わせ手法の性能比較 . . . . . . . . . . . . . . . . . . 21 第6章 まとめ 26 謝辞 27 参考文献 27 第1章 はじめに 近年，実物を忠実に再現した 3 次元モデルに対する需要が高まっている．3 次 元モデルの利用により，リアルな CG 映像コンテンツの作成や，自動車事故の 被害予測システムの開発などが可能になる． 3 次元モデルを作成する方法の 1 つに，実物体の表面の形状をカメラで観測 し，3 次元モデルを自動的に再構成する方法がある．このとき，形状は三角測 量の原理により，3 次元空間上の複数の点として得られる．この複数の点の集 合は一般的に，点群と呼ばれる． 1 方向から物体を撮影した画像からでは物体の周囲の形状全てを計測できない ので，複数の視点から計測を行う必要がある．こうして得られた複数の部分形 状から 1 つのモデルを構築する際，計測時の視点の違いを補正するために，回 転+並進で表される剛体変換を施す．この処理を本研究では，位置合わせと呼 び，剛体変換を求めることを運動推定と呼ぶ．本研究では，複数の点群を精度 よく位置合わせすることを目的とする． 例えば物体表面にマーカを貼付すれば，そのマーカの位置変化を計測するこ とで，運動を推定することができる．この方法では，位置合わせする複数の点 群の他に，異なる時刻で計測した複数のマーカについて，対応付けを人手で与 えることが必要になる．このようなマーカを用いず，点群を直接用いて自動的 に運動推定を行う手法として ICP(Iterative Closest Point) アルゴリズム [4] が 提案されている． マーカによる位置合わせでは人手でマーカを対応付けており，正しい対応付 けを得て安定した運動推定を行うことができる．一方で，ICP アルゴリズムで は，多量の点からその対応付けを自動的に推定するため，対応付けが正しくな い場合，運動推定の結果が局所解に陥る．推定した運動が誤りである場合，そ れを用いて行った位置合わせもまた誤りとなる． ICP アルゴリズムの対応付けに関する問題を改善するための手法が，いくつ かの研究で提案されている [3][5][6]．これらの研究では，2 つの点群の位置合わ せを行う際に発生する, 位置合わせ誤差を縮小するための方法を提案している． 一方で，複数の点群の位置合わせをする際の運動推定の精度を向上させるた めの研究 [7] では，複数の点群を位置合わせする順序を工夫することにより誤差 を縮小している．いずれの研究においても，ICP アルゴリズムの対応付けの精 1 度を改善することが，運動推定の精度を上げるという成果を示している．しか しながら，実験に使う計測物体や計測環境・計測時の物体の運動など，様々な 実験の条件が異なり，各提案手法の優劣を厳密に判断する事は難しい． ゆえに，本研究では，複数の点群の位置合わせ手法について，同一の条件下 で実験を行い性能を比較する． 以下，2 章では，処理の対象とする点群の獲得方法と計測環境について，お よび，物体の運動が既知である場合における位置合わせの方法について説明す る．3 章では，2 個の点群を位置合わせする従来手法のうち，マーカを利用する 位置合わせとマーカレスな位置合わせの 2 つを紹介し，各手法の問題点と有用 性について述べる．4 章では，複数の点群を位置合わせするための複数の手法 について述べる．5 章では，4 章で説明する複数の位置合わせ手法を用いて，物 体の全周点群を獲得する実験を行った結果を示し，位置合わせの精度と計算時 間に関して比較を行う．6 章では，本研究のまとめを述べる． 第2章 2.1 2 つの点群の位置合わせ 点群の獲得 実物体からの 3 次元形状計測は受動型の計測と能動型の計測の 2 種類に分け られる [1]．能動型計測とは，特徴的な形状パターンや濃淡をもつ光などを，対 象に照射する手法のことを指す．照度差ステレオ法，アクティブステレオ法，パ ターン光投影法などがこれに当てはまる．逆に受動型とは，対象に対して通常 の照明などは行うが，計測の補助となる光や音波などを用いない計測のことを 言う．複数のカメラを用いて行う視体積交差法などがこれに当てはまる． 本研究では，能動的な計測のうち，実物体の画像から形状を獲得するための 方法として，凹凸面を含む物体の形状を高精度に獲得できるパターン光投影法 を用いる．パターン光投影法では計測する物体にパターン光を投射し，光が当 たった物体表面をカメラで撮影した画像を使い形状を獲得する．パターン光投 影法には，光切断法や空間コード化法 [1]，ワンショットスキャン法 [2] などが ある． 光切断法では，物体に一本のスリット状のレーザ光を照射し，その部分の形 状を獲得することができる．照射するレーザ光をずらしていきながら静止して いる物体を撮影して，レーザ光が当たっている部分を計測した形状を獲得する 2 ことができる．全周形状を得るには，このスリット光源の投影方向を少しずつ 変化させながら，測定対象全体にわたってスキャンして画像を獲得し，それら 全ての画像から三次元形状を三角測量の原理に基づき算出する必要がある． 一方，空間コード化法では，まったく同じ方向から，プロジェクタによりグレ イコードパターンを順に静止物体に投射する．グレイコードパターンとは，光 の通過部を 1，光が通過しない遮光部を 0 となるような 2 値化された複数枚のパ ターン光である．グレイコードパターンを投影された測定対象物の表面の濃淡 を計測し，スリット光の投射角度を特定することで，三角測量を行い 3 次元形 状を獲得する．たとえば，N 枚のパターン光では 2N のコードを表現できる．ゆ えに，この方法では少数回の撮影で広範囲の部分形状が獲得できる．光切断法 と空間コード化法では，物体とカメラの位置関係が不変でなければ，撮影画像 に映っている物体表面の形状を得ることは難しいが，近年提案されたワンショッ トスキャン法は 1 回の撮影を行うだけで物体表面の形状を獲得できるため，運 動中の物体を撮影する際にも有効である． ワンショットスキャン法において投射するパターン光は様々なものが考えら れるが，本研究では図 1 のような，デブルーイン系列に基づいた青と赤の直線 からなる密なパターンを用いる． (a) グリッドパターン (格子模様) (b) パターン光を投射された物体 図 1: パターン光投影法 まず，グリッドパターンを投射した物体の画像を取得する．次に，物体に映っ たグリッドパターンの，青線と赤線の交点を検出する．最後に，全ての交点に 対し三角測量を行い，計測物体の表面の形状を点群として獲得する．ワンショッ トスキャン法は一度の撮影で物体の形状の取得が可能であるため，運動中の物 3 体を瞬間的に撮影するのに適している．したがって，本研究ではワンショット スキャン法で物体の形状を計測する． 2.2 運動が既知である場合の位置合わせ ワンショットスキャン法により，運動中の物体を連続的に撮影することで，複 数の視点から計測した物体表面の点群を得ることができる．複数の視点から計 測した点群同士を位置合わせして 1 つの点群にまとめるには，図 2 のように，計 測時の視点の違いを補正するための剛体変換を求めることが必要である．剛体 変換を管理しながら物体を運動させる方法として，ターンテーブルが用いられ ることがある．この方法では，ターンテーブルに物体を載せ，指定した角度だ け回転させて点群を獲得する．この点群に，逆向きの回転を施すことで，回転 させる前に獲得したもう一方の点群に位置合わせすることができる． 図 2: 部分点群を位置合わせして全周点群獲得 2 つの点群を１つにまとめた点群を得るためには，適切な変換を施した一方 の点群をもう片方の点群に位置合わせすればよい．位置合わせに使う 2 つの点 群を S0 ,S1 とする．ここで，si は Si に含まれる点の総数を示す．(xi;l ,yi;l ,zi;l )(た だし，l=0,1,…,si -1) は Si に含まれる点の同次座標表現の座標値である． xi;0 xi;1 xi;2 · · · yi;0 yi;1 xi;2 · · · Si = z i;0 1 zi;1 xi;2 · · · 1 1 ··· xi;si −1 yi;si −1 zi;si −1 (1) 1 S1 を S0 に位置合わせするための変換 M1,0 は，次のような式で書ける．t1,0 4 は並進変換を表す 3 × 1 行列を示し，R1,0 は回転変換を表す 3 × 3 行列を示す． M1,0 R1,0 t1,0 = 0 1 (2) S1 に変換を施し S0 に位置合わせすることを考えると，位置合わせにより合 成された点群 Sall は次の式で表される． [ Sall = 2.3 ] (3) S0 M1,0 S1 点群の計測環境 ワンショットスキャンでの計測を実現するために計測環境を構築した．物体の 計測には，三角測量を可能とするために，複数台の計測用カメラと 1 台のプロ ジェクタを用いる（図 3）．プロジェクタからパターン光を投射し，毎秒 7.5fps で撮影可能なカメラ 10 台で，運動中の物体を撮影する．環境光，鏡面反射，拡 散反射の影響により，パターンを抽出する処理が失敗しないようにするため，撮 影は暗所で行う． (a) パターン光投射用プロジェクタ (b) 三次元計測用カメラ 図 3: 計測に使う機材 実際に計測物体として使用した 2 つの物体を図 4 に示す． ターンテーブルを用いて物体の運動を管理しながら計測すれば，運動推定を 行う必要がない．しかし，物体がターンテーブルと接している部分にはパター ン光を照射することができないため，ターンテーブルに置いた物体に回転を施 すだけでは，物体の表面全てから点群を得ることができない．ターンテーブル に接している部分にパターン光が当たるように物体を傾けると，ターンテーブ ルによる回転だけでなく他の剛体変換を物体に施すことになり，ターンテーブ 5 (a) 物体 A (b) 物体 B 図 4: 計測に用いる物体 ルでの運動を管理する意味がなくなる．物体の表面を遮蔽されることなく観測 し，かつ様々な方向から観測できるように物体を運動させる方法として，本研 究ではターンテーブルは用いず，物体を糸に吊るして運動させながら観測する． この方法をとると，運動を完全に管理することができなくなるので，運動を推 定する必要がある．したがって，第 3 章では，運動の推定の方法について説明 する． 第3章 3.1 位置合わせのための運動推定 マーカを利用する運動推定と位置合わせ 剛体の運動推定を行う方法にマーカを用いる手法がある．マーカとは物体の 位置を知るための特徴点である．この手法では，マーカの 3 次元座標をもとに 運動推定を行う． 剛体変換を推定したい 2 つの点群を S0 ,S1 とする．Si (i=0,1) 上にあるうち，1 つのマーカの 3 次元座標を，pmar =(xi ,yi ,zi ,1) で表すとする． i mar pmar を pmar に位置合わせするための変換 M1,0 は，2.2 項で述べたような，4 1 0 × 4 行列として定義することができ，以下の式が成り立つ． mar mar p1 = M1,0 pmar 0 (4) マーカ 1 つにつき，上の式が 1 つ定まる．これを満たす M mar を，2 つの点群 S0 ,S1 を一意に位置合わせするための剛体変換として求めるためには，上記のよ うなマーカの対応を取るための式が３つ必要となる． マーカが 1 点の場合は，マーカ点を中心とした全ての回転の自由度が残って しまう．マーカが 2 点である場合，2 点を結んだ軸周りの回転の自由度が残って 6 しまう．マーカを 3 点以上使用することではじめて，剛体変換を一意に求める ことができる．マーカの数が多ければ多いほど，運動推定は精度がよくなる． 本研究では，運動推定の精度を安定させるために 4 つのマーカを物体に貼付 し，全てのマーカを用いて誤差が最小となるような剛体変換を求める．マーカ の 3 次元座標は，三角測量によって獲得する． マーカを利用した計測の計測環境について説明する．マーカは物体に貼り付 けて使う特徴点であるため，貼り付けた部分が明確にわかるような特徴を持っ ている必要がある．通常マーカは，照明の付いた明るい環境で計測が行われる． しかし，ワンショットスキャンでの点群計測を同時に行うためには，パターン光 を照射する必要があるので，可視光の影響を受けにくい暗所でのマーカ観測を 行うことが望ましい．本研究では，この 2 つを両立させるため，暗所でも鮮明に 観測できるマーカとして緑色の蛍光シールを物体に貼り付けて計測を行う．ま た，蛍光シールを発光させるため，紫外線を放射するブラックライトを設置す る (図 5)．紫外線はカメラで観測されないため，ワンショットスキャンで照射し 図 5: 紫外線を放射するブラックライト ているパターン光にほとんど影響を及ぼさない．一方で，紫外線を蓄積した蛍 光マーカが励起作用によって放射した可視光はカメラで観測できる．したがっ て，マーカ観測とワンショットスキャンによる点群獲得を，同時に行うことが できる． ワンショットスキャンに使う 10 台のカメラは，全てプロジェクタとほぼ同じ 方向を向いており，パターン光が当たる面と反対側のマーカを観測できない．そ こで，これらのマーカを観測するために，2.3 節で三次元形状計測に用いる 10 台のカメラに 29 台のカメラを追加し，全部で 39 台のカメラを用いる．物体の 周囲のほぼ全方位から同期撮影をし，最低 2 台のカメラにマーカが映るように し，三角測量によりマーカを貼付した部分の三次元座標を獲得する． 7 このようにして獲得したマーカに対し，ある時刻に撮影したマーカが他の時 刻に撮影したどのマーカと対応しているのかわからないため，時間方向でのマー カ対応付けを人手で行う．マーカを使う位置合わせでは，対応付けの取れたマー カを使い，運動推定を行う． マーカによる位置合わせのアルゴリズムでは，運動推定を行うために，対応 付けを入力として与える必要がある．一方で，3.2 節で説明する ICP アルゴリ ズムでは，対応付けと運動推定をまとめて行うことができる． 3.2 ICP アルゴリズム ICP アルゴリズム (Iterative Closest Point Algorithm) はマーカレスな位置合 わせの代表的な手法の 1 つである．ICP アルゴリズムでは，2 つの点群間の最近 傍点を対応点として求め，その対応関係を用いて運動を推定する処理を繰り返 し行い，推定した運動をより正しい値に近づける．このうち，位置合わせの際 に基準とする点群をモデル点群，モデル点群に重なるように変換を施される点 群をデータ点群と呼び，モデル点群を sq 個の点の集合 SQ ，データ点群を sp 個 の点の集合 SP で表すことにする．また，SQ ，SP に含まれる点それぞれを，q 及び p と書くことにする．ICP アルゴリズムの手順について，次の 1 から 3 の 処理に分けて説明する． 1. 最近傍点を計算 SP 上のある点 p について，SQ の全ての点 q に対する距離を求め，2 点 q 及び p の距離が最短となるような組 (q，p) を，P 上の sp 個の点すべてに ついて求める．ICP アルゴリズムでは，こうして求めた最近傍点の組を位 置合わせにおける仮の対応点として用い，これらの点を近づける変換につ いて考える． 3 次元空間上の点 q，p を次のように同次座標系で定義する． [ q= ]T xq yq zq 1 [ ,p = ]T x p y p zp 1 (5) sp 組の点の組のうち l 個目の組を (ql ，pl ) とし，pl の最近傍点 ql を求め る．ql に近づけるために pl に施す変換を M icp とする．処理の最初では， M icp は得られていないことが多く，その場合 M icp には適当な初期値が設 定される．本実験では M icp の初期値として単位行列を用いる．ql を求める 8 計算式は次のようになる． ql = arg min ||q − M icp pl || q∈Q (6) 2.2 節で説明したように，変換 M icp は並進変換を表す 3 次元ベクトル ticp 及び，回転変換を表す 3 × 3 行列 Ricp を含む，4 × 4 行列である． M icp = R icp 0 icp t 1 (7) sp 組の点の組のうち，l 個目の組 (ql ，pl ) と表すと，変換 M icp を基に，sp 組の最近傍点間の距離の総和 d は d= sp ∑ ||ql − M icp pl || (8) l と書くことができる．sq ,sp が大きいほど，最近傍点の組を求めるための計 算時間は大きくなる． 2. 最近傍点を使った運動推定 最近傍点の組を作って最近傍点間の距離を小さくするような変換を繰返 し計算し，対応付けの精度を上げるというのが ICP アルゴリズムの基本的 な考え方である．p を q に近づけるような変換 M icp を推定する． M icp を新たな値に更新するための計算式は次のように書ける． M icp = arg min sp ∑ M ||ql − M pl || (9) l この式では，sp 個の最近傍点同士を近づけるための行列 M を設定し，p に 施した点 M pl と ql との距離の総和が最小となるような M を求める． 求めた最近傍点の組の中には，間違った対応付けが行われている組が含 まれている可能性がある．間違った対応付けの影響を抑えるための手法と して RANSAC がある．RANSAC は最近傍点の組からランダムに点の組を サンプルし，最小二乗法に当てはめることを繰返す．抽出したサンプルに 外れ値が含まれなければより確からしい推定が得られ，且つ外れ値の数が 全測定数に比べて少なければ推定される誤差範囲内により多くの測定値が 含まれる，正しい推定とみなす．これにより，外れ値が含まれないように， 運動推定に使う対応点をサンプルすることができる．本研究では RANSAC を用いて，誤りの対応付けを除き，運動推定が不適切な値に収束すること を防いでいる． 9 3. 収束判定 変換行列 M icp について，収束判定条件を満たしている場合は位置合わ せを終了し，収束判定条件を満たしていない場合は再度 1，2 の手順を繰り 返す． 本研究では，1，2 の計算を繰り返している回数が k 回であるとき，繰返 し計算による更新前の最近傍点の距離の総和 dk−1 と更新後の dk ，および収 束の閾値 δ を用いて，次のように収束条件を設定する． |dk − dk−1 | < δ (10) また，収束しない場合でも，ICP アルゴリズムの計算回数に上限を設け ることで計算を終了することができる． 3.3 2 つの運動推定における利点と問題点 まず，マーカを利用する運動推定に対して，ICP アルゴリズムが有利な点を 考える．マーカを利用する運動推定では，位置合わせを行うために対応付けが されたマーカの座標を入力として与える．一方で，ICP アルゴリズムでは対応 付け作業をプログラムがすべて自動で行うため，位置合わせを行うための入力 は位置合わせを施す 2 つの点群だけでよい． しかし，ICP アルゴリズムは自動的な対応付けを行うため，対応付けの正確 性が保証されないという問題がある．マーカ対応付けを人手で行う場合は，位 置合わせした結果を人の目で視覚的に判断する事で，対応付けに誤りを発見し て修正することが可能なので，最終的には対応付けを誤りのないものにするこ とができる．しかし，ICP アルゴリズムでの自動的な対応付けでは，いくつか の対応付けが誤りであってもそれを計算機が人のように視覚的に判断すること ができず，対応付けの解の正当性を保証できない．対応付けが正確なものでは なければ，正しい運動推定を行うことができない． 運動推定の解が局所解に落ちると，対応付けが正確でなくなる．局所解に落 ちる原因としては，以下の 2 つが挙げられる．第 1 に，変換の初期値が，適切 でないという理由である．ICP アルゴリズムにおいて変換の初期値が悪ければ， 点群同士の距離が離れたり，向きが大きく逸れたりして，点群同士の適切な最近 傍点の対応を取ることが難しくなる．第 2 に，2 つの形状を用意した際に，デー タ形状がモデル形状に一致する部分がほとんどない場合，対応付けが難しい．こ 10 れは例えば，点群を連続時間的に計測する際，物体の運動速度が速すぎること などが原因である．物体の運動が速いと，第 1 の原因と同様に，位置合わせす る点群同士の距離が離れたり，向きが大きく逸れたりして，点の対応付けが難 しくなる． また，形状全体の大きさと比較して表面の凹凸が極端に大きかったり小さかっ たりする形状は位置合わせが難しいという，形状依存性の問題がある．この問 題は，ICP アルゴリズムが形状の一致に頼る手法であるがゆえに発生している． これは，計測対象の形状に固有の問題であり，また対処も難しいため，本研究 では扱わないものとする． 一方，対応付けがほとんど正しく行われた場合でも，残されている問題があ る．ICP で求めている対応点は，マーカのような 1 対 1 の対応関係を持つわけ ではなく，最近傍点を便宜的に仮の対応点として設定しているにすぎない．完 全な 1 対 1 の対応点ではないため，どれだけ正確な対応付けに近くても位置合 わせの微小な誤差は残ると考えられる． 第4章 複数の点群の位置合わせ 2 つの点群の位置合わせでは，物体の表面の大部分を再現した形状を獲得す る事は難しく，全周形状を獲得することはできない．そのため，多数の計測に より複数の点群を獲得し，これらを位置合わせすることが必要である．第 4 章 では，2 つの点群を位置合わせする ICP アルゴリズムを応用して，複数の点群 を位置合わせする方法について説明する． 4.1 隣接位置合わせ 2.2 節で説明したように物体を糸で吊るし，物体に微小な運動を施しながら， 短い時間間隔で物体を計測して獲得した N 個の点群 S0 ,S1 ,…,SN の位置合わせ について考える．点群 Si に含まれる点の個数を si とすると，Si は 2.2 節の (1) 式と同様，以下のような行列として表現できる． 11 xi;0 xi;1 xi;2 · · · yi;0 yi;1 xi;2 · · · Si = zi;0 zi;1 xi;2 · · · 1 1 1 ··· xi;si −1 yi;si −1 zi;si −1 (11) 1 (a) 隣接点群同士の運動推定 (b) 最初の点群との運動推定 図 6: 運動推定する点群の選択 S0 ,S1 ,…,SN を位置合わせするには，N + 1 個の点群から N 個の運動を推定 する必要があるが，ICP アルゴリズムにより運動推定する点群の組の選び方は 色々考えられる．はじめに，図 6(b) のように，S0 をモデル点群に設定し，デー タ点群 S1 ,…,SN を位置合わせすることを考える．S0 と S1 のように時間的に隣 接している 2 つの点群同士ならば，対応付けの解が局所解に陥りにくく，ICP アルゴリズムにより正確な運動推定ができると期待される．しかし，S0 と Si に おいて (i ≫ 0) である場合，推定されるべき運動が大きく ICP アルゴリズムに おける点群の対応付けの解が局所解に陥りやすくなると考えられる．対応付け の解が局所解に陥ると，正確な運動推定が難しいため，ICP アルゴリズムを用 いる位置合わせでは図 6(b) のような点群の選択は適切でない．そこで，図 6(a) のように，S0 と S1 ，S1 と S2 ，…のように隣接するフレーム同士の剛体変換を 求めることを考える．点群の系列について，隣接する点群同士の比較において 推定すべき運動は，隣接しない 2 つの点群間の運動とは異なり微小であると考 えられるので，対応付けが局所解に陥りにくく運動推定の安定性が高いと考え られる．本研究では，複数の点群の位置合わせに対して図 6(a) のように点群の 12 組を選択し運動推定を行うことにする． S0 と S1 ，S1 と S2 ，…を用いて，位置合わせの基準とした点群 S0 に他の点 群 S1 ,…,SN を位置合わせする．まず，S0 と S1 を位置合わせする変換を求める． icp ICP アルゴリズムにより求めた変換であるため，M1,0 と表記することにする． icp icp icp icp S1 と S2 以下の組も同様に，変換行列 M1,0 ，M2,1 ，M3,2 ，…，MN,N −1 ，を求め る．S0 と Si の位置合わせは，Si と Si−1 に位置合わせを行い，その点群をさら に Si−2 に位置合わせを行う，という操作を S0 まで行うことで実現できる．す icp なわち，Si に施す変換行列 Mi,0 は，次式のように表せる． icp icp icp icp Mi,0 = M1,0 M2,1 ...Mi,i−1 (12) これを，S1 ,…,SN 全ての点群について行うことで S0 に位置合わせし，全周点群 を求めることができる．全周点群を Sall とすると，Sall の獲得は下記の計算式 で表される． icp icp SN ] , · · · , MN,0 Sall = [S0 , M1,0 (13) はじめの隣接フレーム位置合わせ計算により求めた変換だけを使い，全周形状 を獲得しているこの方法を，本研究では隣接位置合わせと呼ぶことにする（図 7） 次に，全周点群獲得にかかる計算時間のオーダについて考える．複数の点群 の位置合わせでは，ICP 位置合わせによる運動推定と，推定した運動を用いた 位置合わせをそれぞれ行うが，計算時間のほとんどを占めるのは ICP アルゴリ ズムによる点群同士の位置合わせ計算である．そのため，全周点群獲得までに ICP 位置合わせが行われた回数により，計算時間のオーダを見積もることがで きる．隣接位置合わせの場合，点群の組の個数は N − 1 個であるので，ICP 位 置合わせを N − 1 回行うことになる．S0 ,…,SN に含まれる点の数が全てほぼ同 icp 数であるとすると，Mi,i−1 を求める各 ICP 位置合わせの計算にかかる時間はほ ぼ同じであると考えられる．したがって，N 個の点群から全周点群を獲得する ために必要な，ICP 位置合わせの計算時間のオーダは O(N ) である． icp icp icp 次に，先ほどと同様に，変換行列 Mj,i =Mi+1,i …Mj,j−1 (0 ≤ i ≤ j ≤ N ) icp を定義する．Mj,i は，Si を Sj に位置合わせする変換である．図 6 のような隣 icp icp 接点群間の剛体変換 Mi+1,i ,…,Mj,j−1 を積算すると，j − i 回分の位置合わせ誤 icp icp 差が蓄積する．Si と Sj を変換 Mj,i で位置合わせした点群を Sj,i と定義する． 13 図 7: 隣接位置合わせ icp icp icp icp icp M1,0 ,M2,0 ,…,MN,0 を S1 ,…，SN に施した点群はそれぞれ S1,0 ,…，SN,0 と書ける． icp icp Sj,i (j ≫ i) は個々の変換の誤差が蓄積した変換 Mj,i を施した点群であるの で，隣接位置合わせにより物体の表面を忠実に再現した形状を得ることは難し icp icp い．この問題に対して，本研究では，点群 S0 および S1,0 ,…，SN,0 に対して再度 ICP 位置合わせを施し，蓄積した誤差を解消することを考える．隣接する点群 に隣接位置合わせにより運動を施し位置合わせした点群に，再度位置合わせを 施すと，推定すべき運動が先ほど行った推定よりも小さくなり，運動推定の解 が局所解に陥りにくくなるため，運動推定の精度が向上すると考えられる．ま た，どの点群同士をどの順番で位置合わせするかも，精度の向上に影響する．再 度位置合わせを行うことで，また点群をどの順番で位置合わせするかで，どの ように精度と計算時間が異なるのかを考える．従来手法の一つとして 4.2 節で 逐次位置合わせについて，本研究での提案手法として 4.3 節で階層的位置合わ せについて，それぞれ述べる． 4.2 逐次位置合わせ seq seq icp icp を S2,0 逐次位置合わせでは，S0 を S1,0 に位置合わせして S1,0 を獲得し，S1,0 seq に位置合わせして S2,0 を獲得する，という，複数ある形状のうち先頭の 2 つの seq を獲得するまで行う． 点群を位置合わせする計算を SN,0 逐次位置合わせの流れを図 8 に示す．隣接位置合わせでは，S0 と Sk (1 ≤ k ≤ icp icp icp N ) の位置合わせの場合，M1,0 M2,1 ...Mk,k−1 の積算により最大 k 個の変換の誤 差が蓄積していた．しかし，逐次位置合わせで S0 と Sk (1 ≤ k ≤ N ) の位置合 seq icp seq わせを行う場合，Sk−1,0 と Sk,0 を位置合わせする変換 Mk,0 の誤差のみ含まれ seq る．ただし，Mk,0 は，S0 から Sk−1 を位置合わせした 1 つの点群と，Sk とを， 位置合わせするための剛体変換である．したがって，逐次位置合わせの誤差は 隣接位置合わせの誤差よりも小さく，獲得される点群はより実物に近くなると 考えられる． 14 図 8: 逐次位置合わせ seq を獲得するための計算は次のように表される． このとき，全周点群 SN,0 seq icp seq icp seq icp SN ] S2 , ..., MN,0 S1 , M2,0 Sall = [S0 , M1,0 (14) 次に，逐次位置合わせで全周点群を獲得するまでに行う ICP 位置合わせの回 数について考える．逐次位置合わせでは，まず隣接位置合わせと同じように icp icp icp icp ,…,MN,N M1,0 −1 の N − 1 個の変換を求める．次に，点群 S1,0 ,…，SN,0 を求め seq seq のN −1個 ,…,MN,0 た後，S0 とこれらを逐次的に位置合わせするために M1,0 の変換を求める． icp icp ,…,MN,N M1,0 −1 を求める ICP 位置合わせについては，位置合わせする各点群 seq seq を求める ICP に含まれる点の個数はほぼ同数であったのに対し，M1,0 ,…,MN,0 seq seq seq 位置合わせでは，点群 S1,0 ，S2,0 ，…，SN,0 に含まれる点の個数が，先頭フレー ムの位置合わせを繰返すごとに S0 の点の個数の 2 倍，3 倍，…，N − 1 倍と増 えていく． ICP 位置合わせにおける計算は，対応点探索，運動推定，収束判定の 3 つに 分けられるが，点群が含む点の個数が多数である場合，計算時間のほとんどは 対応点探索が占める．対応点探索では，2 つの点群それぞれに含まれる点同士 の距離を全て求めているため，点群が保有する点の数に線型に比例して，ICP 位置合わせの計算時間が 2 倍，…，N − 1 倍と大きくなると考えられる． 15 したがって，全周点群を得るための計算時間のオーダは，O(N + ∑N −1 l=1 l) で ある．これを計算すると，およそ O(N 2 ) となる．したがって，逐次位置合わせ では，隣接位置合わせのおよそ N 倍の計算時間がかかる． 4.3 階層的位置合わせ 図 9: 階層的位置合わせ 逐次位置合わせでは，点群に含まれる点の数が多いほど位置合わせにかかる 計算が大きくなることがわかった．逐次位置合わせと同程度の精度をもつ運動 推定ができ，計算時間がより少ない位置合わせ法があれば有用である．このよ うな方法の 1 つとして，点群に含まれる点の増加による計算時間の増加を減ら し，効率的な位置合わせを実現する階層的位置合わせを，4.3 節において本研究 で提案する． 階層的位置合わせの様子を図 9 に示す．階層的位置合わせの説明を行うため icp に，隣接位置合わせによる S0 ，S1 ，…，SN の変換点群 S0 ，S1icp ，…，SN をそ hier と表記する．これらの点群を，一定の個数の点 れぞれ，S0hier ，S1hier ，…，SN 群で構成される複数のブロックに分けて，ブロックごとに位置合わせを行う．1 つのブロックに含まれる点群の個数を a(ただし，a ≦ N ) とする． 位置合わせによる a 個ずつの点の統合を f 段行ったとすると，全体で残る点 群の個数は aNf となる．この f を階層的位置合わせの段階数と呼び，af −1 個の点 16 群の位置合わせにより得られた点群を，f 段階目の点群と定義する．例えば，1 段階目の点群の個数は全部で N 個，2 段階目の点群の個数は全部で 階目の点群の個数は全部で N a2 N a 個，3 段 個，と表される． hier hier 各ブロックにおいて，a 個の点群 Sua−a ,…,Sua−1 を位置合わせして得られた hier 点群を Sua−1,ua−a と定義する．u は点群のブロック数を表す変数であり，f 段階 目の点群の個数 aNf 個を ua が超えることはないため，u= afN−1 を満たす正の整数 である． hier たとえば，1 段階目 (f =1) の N 個の点群の位置合わせは，S0hier ,…,Sa−1 を， hier (S0hier を位置合わせの基準として) 位置合わせした点群は，Sa−1,0 で表され，Sahier , hier …,S2a−1 を，(Sahier を位置合わせの基準として) 位置合わせした点群に，位置合 icp hier わせの基準が S0hier となるように変換 Ma,0 を施した点群は，S2a−1,a で表され る．このようにして，位置合わせの基準が S0hier である N a hier 個の点群 Sa−1,0 ，…， hier SN,N −(a−1) を獲得する． hier hier hier hier 2 段階目 (f =2) の点群 Sa−1,0 ，S2a−1,a ，…に対しても同様に，(Sa−1,0 ，S2a−1,a )， hier hier (S2a−1,a ，S3a−1,2a )，…のように，隣接点群同士の変換を ICP 位置合わせにより hier hier hier 求め，a 個の点群 Sua−1,(u−1)a ，S(u+1)a−1,ua ，…，S(u+a−1)a−1,(u+a−2)a を位置合わ hier せした点群 S(u+a−1)a−1,(u−1)a を求める．以下同様の位置合わせを繰返し，全周 hier 点群 SN,0 が得られた時点で位置合わせを終了する． 次に，階層的位置合わせにより全周点群を獲得するための計算時間のオーダ について考える．f 段階目の点群の数は N af −1 N af −1 個なので，ICP 位置合わせ回数は − 1 である．また，f 段階目の点群 1 個あたりに含まれる点の数は，1 段階 目の点群の af −1 倍である． f =loga N の時，全周点群を獲得できる．したがって，全周形状を獲得するた めの計算時間のオーダは次のように書ける． O( log aN ∑ ai−1 N ) (15) i=1 すなわち， aloga N − 1 N) a−1 − 1 として，両辺に a を底とする対数を施すと， O( x = aloga N (16) loga x + 1 = loga N (17) x=N −1 (18) 17 −1 したがって，計算時間のオーダは O( Na−1 N ) と書きなおせる．a=2 のとき，計 算時間のオーダは O(N (N − 1)) であり，逐次位置合わせと同等である．また， a ≧ 3 のとき，計算時間のオーダは逐次位置合わせの場合より小さくなる．し たがって，計算時間においては階層的位置合わせのほうが逐次位置合わせより 有利であると考えられる． 第5章 位置合わせ手法の性能比較 第 5 章では，第 4 章で述べた ICP アルゴリズムによる 3 つの位置合わせ法に ついて，運動推定の精度と，運動推定にかかる計算時間の比較実験を行う．5.1 節では各方法による統合形状の正確さの違いを評価するための方法について述 べる．5.2 節では， ．隣接位置合わせを用いて，ICP アルゴリズムによる 2 つの 形状間の運動推定の安定性について，形状間の運動の大きさと関係を分析した． 5.3 節では，隣接位置合わせ・逐次位置合わせ・階層的位置合わせの 3 つの位置 合わせ手法の精度と計算時間について性能比較を行った． 5.1 位置合わせの正確さの指標 ICP アルゴリズムにおける運動推定は，第 4 章で述べたように統合方法を様々 に変えることで，位置合わせ誤差の蓄積が少なくなり，運動推定の精度が変化 すると考えられる．そこで，運動推定の精度を定量的に評価するための指標に ついて考える． 位置合わせの正確さは，ICP アルゴリズムによって位置合わせした点群及び マーカによって位置合わせした点群の両方を利用して評価する．マーカによる 推定は ICP アルゴリズムによる推定と異なり，隣接していない点群同士の剛体 変換も局所解に陥ることなく，また誤差の蓄積もなく求めることができるため， ICP アルゴリズムを使う方法よりも誤差が小さいと考えられる．これを基準と して ICP アルゴリズムの各手法の性能を比較する． マーカよる位置合わせと ICP アルゴリズムによる位置合わせを比較する際， 単に変換行列の要素の値を直接比較しても，位置合わせへの影響を直接評価で きない．そこで，変換を施した点群同士で距離を評価することで，精度の比較 を行う． 具体的には，sp 個の点からなる点群の，l 番目 (l=1,…,sp ) の点 pl にマーカ位 18 置合わせによる変換 M mar を施した点群は M mar pl で書ける．同様に，l 番目の 点 pl に ICP 位置合わせによる変換 M icp を施した点群は．M icp pl で書ける． これらの点群は，変換前は全く同一の点群なので，剛体変換後も点群を構成 する点の数は同じである．変換後の点群について各点の距離を求めることで，位 置合わせの精度を評価することができる．点群を構成する全ての点について距 離を求め，平均値を位置合わせの誤差として計算する． これらを用いて，誤差 ϵ は次式で表される． ∑sp ϵ= l=1 ||M icp pl − M mar pl || sp (19) 誤差が小さいほど，誤差の蓄積が少なく精度が良い ICP アルゴリズム位置合 わせであると判断できる． 5.2 離れた点群の位置合わせ誤差を比較 ICP アルゴリズムは 3.3 節で述べたように，2 つの点群を位置合わせするため に必要な運動が大きいと，局所解に陥りやすくなる．局所解に陥れば運動推定 の精度が悪くなるため，ϵ の値によって局所解に陥ったかどうかを判定できる と考えられる．そこで，推定すべき運動の大きさと ϵ との関係を定量的に検証 する． 本実験では，位置合わせする 2 つの点群間の運動の大きさを変えて誤差を評 価する．まず，十分にゆっくり回転させた物体を計測し，点群の系列を得る．系 列から 2 つの点群を取り出し，ICP アルゴリズムによる位置合わせを行う．位置 合わせには，ICP アルゴリズムの実装として Point Cloud Library[8] を用いた． この時取り出す 2 つの点群 Si と Sj で，時間間隔 |i − j| を変えながら ICP の精 度を評価し，|i − j| と精度の関係を調べた．一般に運動は並進+回転の剛体変 換で表されるが，2.2 節で説明したように，本研究では計測物体を糸で吊るし， 回転に比べ並進がきわめて微小となるように，かつ等速運動に近くなるように 物体に運動を加えた．本実験では物体の運動の大きさを物体の回転の角速度で 近似して考える．物体 A では一周に 156 フレーム，物体 B では 105 フレームか かっていた．等速運動を仮定すれば，1frame あたり，ω=1.2 °，1.8 °回転して いることになる．これを用いると，物体 A では，kω =1.2 °，2.4 °，3.6 °，4.8 °，6.0 °，7.2 °/frame，物体 B では，kω =1.8 °, 3.6 °，5.4 °，3.6 °, 7.2 °，10.8 19 °/frame，(k=1,2,3,4,5,6) に設定することができ，各場合における位置合わせ誤 差 ϵ を，以下の手順で，全ての点群に対し求めた．具体的には，運動の大きさが kω の場合，(S0 ,Sk ),(S1 ,Sk+1 ),(S2 ,Sk+2 ),…のように点群の組を選び，それぞれ 剛体変換を求め，変換 1 つ分の誤差の大きさを算出した．(S0 ,Sk ),(S209 ,S209+k ) の 210 組に対する誤差の値について累積ヒストグラムをとり，物体 A・物体 B について，それぞれ図 11(a) と図 12(a) にまとめた． 物体 A では，1.2 °/frame の場合，誤差は 2.5 以下の点群が 150 個程度であり， 8 以上の誤差を持つ点群はみられない．誤差が 10 以上の点群は，2.4 °/frame で は 40 個程度，3.6 °/frame では 70 個程度，となり，これらの点群は運動推定が局 所解に陥っていると考えられる．さらに 4.8 °/frame，6.0 °/frame，7.2 °/frame， の場合には，より大きな誤差が生じることがわかる．物体 B では，1.8 °，3.6 °/frame の場合，誤差が 3 以下の点群が 160 個から 180 個程度であり，6 以上の 誤差を持つ点群はほとんど見られない．一方で，5.4 °，7.2 °，10.8 °/frame，では 210 個の点群のうち 4 以上の誤差を含む点群の割合が 1.8 °/frame，3.6 °/frame に比べ大きくなり，10 以上の誤差を含む変換が 20 個から 30 個程度見られる． 誤差の大きさは異なるものの，物体 A と同様に，物体の運動が大きいほど，位 置合わせの精度が悪くなる傾向が見られる． また，ICP アルゴリズムにおける運動推定のための繰返し計算回数も ICP ア ルゴリズムの精度に影響すると考えられる．計算時間の違いによる運動推定の 精度の差を比較するために，ICP アルゴリズム計算回数 Y を，10 回，20 回，30 回，40 回，50 回に設定し，同様に隣接位置合わせを施した際の，上記の繰り返 し計算回数それぞれの場合について，点群ごとの誤差との関係を，物体 A・物 体 B それぞれについて，累積ヒストグラムをとり，図 11(b)・図 12(b) に示す． また，物体 A の位置合わせ後の点群を図 10 に示す． 物体 B では計算回数が 10 回から 50 回の場合において，得られた結果に大き な差は見られず，運動推定の計算は 10 回から 20 回程度で収束していると考え られる．物体 A では，計算回数が 10 回の場合，20 回から 50 回の場合とは異な り，誤差が 5 から 10 の点群が 30 個程度みられるため，点群の収束が完了して おらず正しい運動推定結果が得られていないと考えられる．計算回数が 20 回の 場合，誤差が 5 以上の点群が 30 回から 50 回の場合よりも 10 個程度多く，微小 な位置合わせ誤差が残っているが，20 回，30 回，40 回，50 回の場合はほとんど 同じ結果が得られ，運動推定の計算が収束していると考えられる．この結果よ 20 り，物体 A の点群を収束させる ICP アルゴリズムでの繰返し計算回数は，高々 30 回であることがわかる．しかし，隣接位置合わせによる位置合わせが完了し ても，図 10(a) に示すマーカを利用する位置合わせに比べ，位置合わせ精度が 劣ることがわかる．これは，隣接位置合わせにおける誤差の蓄積による精度の 悪化であるため，点群間の運動の大きさや収束にかかる繰り返し計算回数を調 節するだけでは解決が難しい問題である．そこで，5.3 では，隣接位置合わせ・ 逐次位置合わせ・階層的位置合わせの 3 つの位置合わせ手法について，同一の 点群を用いて同一の繰返し計算回数を行った際の，位置合わせ精度及び計算時 間を比較する． (a) マーカ利用 (b) 計算回数 10 回 (c) 計算回数 20 回 (d) 計算回数 30 回 (e) 計算回数 40 回 (f) 計算回数 50 回 図 10: 収束計算回数による精度の違い (物体 A) 5.3 3 つの ICP 位置合わせ手法の性能比較 実験 1 の結果に基づき，運動推定が局所解に陥りにくくするために，実験 1 の 結果を考慮して，物体の運動速度を物体 A は 1.2 °/frame，物体 B は 1.8 °/frame， ICP アルゴリズムでの繰返し計算回数を 30 回にそれぞれ設定した．隣接位置合 わせ・逐次位置合わせ・階層的位置合わせそれぞれの位置合わせ手法について, 216 個の点群の位置合わせをそれぞれ行い，点群の系列と誤差との関係につい て，比較を行った．物体 A・物体 B それぞれに関して比較を行った結果を図 13 21 (a) 推定する運動の大きさによる誤差の違い (b) 収束計算回数による誤差の違い 図 11: 条件別の誤差の違い (物体 A) 22 (a) 推定する運動の大きさによる誤差の違い (b) 収束計算回数による誤差の違い 図 12: 条件別の誤差の違い (物体 B) 23 に示す．また，物体 A・B について，各手法により得られた物体の計測形状を それぞれ図 14，15 に示す． 階層的位置合わせでは，物体 A・物体 B それぞれに関して，216 個の点群す べてに関して隣接位置合わせよりも小さな誤差しかなく，運動推定の精度が向 上していることがわかる．一方，逐次位置合わせでは，物体 A では 60 個目の 点群のあたりで，他の 2 手法に比べ精度が急激に悪化している．物体 B では点 群番号が 10 個目のあたりから急激に位置合わせの精度が悪くなったがその後は 216 フレーム目まで誤差の増加しない位置合わせを行っていることが分かった． 物体 A・物体 B ともに，ある点群以降急激に位置合わせの精度が悪くなるのは， その点群を位置合わせするための運動推定が局所解に陥ってしまうためと考え られる．また，いったん局所解に陥ってしまうとその分の誤差が後の点群の位 置合わせにも引き継がれたままになってしまうため，後の点群の運動推定の精 度も悪くなると考えられる．ゆえに，逐次位置合わせでは，局所解に陥る回数 が多ければ隣接位置合わせよりも位置合わせの精度が悪くなることがあり得る． この結果より，逐次位置合わせは必ずしも隣接位置合わせよりも精度の良い位 置合わせができるとは限らない，不安定な位置合わせであることがわかる． また，216 個の点群の位置合わせにかかった計算時間を比較すると，物体 A・ 物体 B ともに，逐次位置合わせより階層的位置合わせのほうが大幅に計算時間 を縮小できていることがわかる．物体 A では，隣接位置合わせにかかる時間が 1 時間 30 分程度であった．計算時間のオーダを考えると，位置合わせする点群の 個数が 216 個なので，逐次位置合わせの計算時間は 216 倍程度になると考えら れるが，実際の結果は 4 倍の 5 時間 30 分程度にとどまっている．これは，Point CLoud Library 内のプログラムで，計算時間を減らす工夫をしているためであ ると考えられるが，その点については分析が十分にできていないため，今後の 課題として扱う．階層的位置合わせでも同様の工夫により，計算時間のオーダ より小さい計算時間になっていると考えられる． 表 1:物体 A の位置合わせにかかった計算時間 繰返し計算回数 30 回 隣接位置合わせ 逐次位置合わせ 階層的位置合わせ 1 時間 32 分 5 時間 25 分 2 時間 13 分 24 (a) 物体 A (b) 物体 B 図 13: 位置合わせ手法ごとの誤差の違い (a) 隣接位置合わせ (b) 逐次位置合わせ (c) 階層的位置合わせ 図 14: 3 種の ICP 位置合わせの精度の違い (物体 A) 25 (a) 隣接位置合わせ (b) 逐次位置合わせ (c) 階層的位置合わせ 図 15: 3 種の ICP 位置合わせの精度の違い (物体 B) 表 2:物体 B の位置合わせにかかった計算時間 繰返し計算回数 30 回 第6章 隣接位置合わせ 逐次位置合わせ 階層的位置合わせ 2 時間 30 分 7 時間 12 分 3 時間 10 分 まとめ 本研究では，ワンショットスキャン法により実物体の表面の形状を点の集合 である点群として獲得し，複数の点群を ICP アルゴリズムにより位置合わせし た．ICP アルゴリズムでは，2 つの点群の自動的な対応付けを行う際に，推定 すべき運動が大きいと対応付けが局所解に陥り，安定した運動推定を行えない という問題があった．この問題を解決するため，複数の点群から ICP 位置合わ せして剛体変換を獲得する点群を隣接点群同士に設定することで，対応付けが 安定するよう試みた． また，隣接点群を位置合わせするための剛体変換を用いて複数の点群を 1 つ の点群にまとめる際，隣接位置合わせを行うと誤差が大きく蓄積するという問 題があった．本研究では，逐次位置合わせや階層的位置合わせなどを行い，誤 差が蓄積した点群を再度位置合わせすることにより，誤差を縮小させようと試 みた． 誤差縮小による位置合わせ精度の向上を観察するため，本研究では 2 つの実 験を行った．1 つ目の実験では，ICP アルゴリズムの運動推定における繰返し 計算の回数を変えて複数の点群を統合することにより，運動推定の精度との関 係を調べた．また，点群間の運動の大きさを調節した複数の点群を位置合わせ 26 することで，対応付けが局所解に陥るような運動の大きさを判断した．2 つ目 の実験では，1 つ目の実験結果に基づき実験条件を設定して，隣接位置合わせ・ 逐次位置合わせ・階層的位置合わせの 3 つの位置合わせ手法により，同一の条 件下で複数の点群を位置合わせし，運動推定の精度と計算時間に関して性能の 比較を行った． 実験の結果，運動推定の精度だけを見た場合，逐次的位置合わせは，運動推 定が局所解に陥ることによる誤差が他の点群に引き継がれ，隣接位置合わせに 比べて推定の結果が必ずしも良い結果になるとは限らないことがわかった．一 方，階層的位置合わせでは，隣接位置合わせよりも誤差が小さい位置合わせを 安定して行えることがわかった．また，計算時間は逐次位置合わせよりも短縮 できることがわかった．今後の課題としては，隣接位置合わせ・階層的位置合 わせの運動推定の計算を並列化し，さらに計算時間を縮小し，計算時間の比較 を行うなどが考えられる． 謝辞 本研究を行うにあたり，熱心なご指導，多くのご教示を賜りました美濃導彦 教授に深く感謝致します．また，本論文をご査読いただき，本研究の進行に関 して数多くの有用な助言を与えてくださった舩冨卓哉助教に深く感謝致します． 最後に，本研究を進めるにあたり貴重なご意見と提供していただき，ご助力を 頂きました顔と手グループの皆様，並びに，美濃研究室の皆様に深く感謝致し ます． 参考文献 [1] 井口征士, 佐藤宏介: 三次元画像計測, 昭晃堂, pp. 80–91 (1990). [2] 大田雄也, 佐川立昌, 古川亮, 川崎洋, 八木康史, 浅田尚紀: Belief-Propagation による高密度なグリッドパターン検出及びデブルーイン系列を用いた高速 動物体のロバストな三次元計測手法, 電子情報通信学会論文誌. D, 情報・シ ステム, Vol. 93, No. 8, pp. 1544–1554 (2010). [3] Godin, G., Laurendeau, D. and Bergevin, R.: A Method for the Registration of Attributed Range Images, Int. Conf. on 3D Imaging and Modeling, Quebec, May 28 , pp. 179–186 (2001). 27 [4] Rusinkiewicz, S. and Levoy, M.: Efficient Variants of the ICP Algorithm, Third International Conference on 3D Digital Imaging and Modeling (3DIM) (2001). [5] Masuda, T. and Yokoya, N.: A robust method for registration and segmentation of multiple range images, Comput. Vis. Image Underst., Vol. 61, pp. 295–307 (1995). [6] Trucco, E., Fusiello, A. and Roberto, V.: Robust Motion and Correspondence of Noisy 3-D Point Sets with Missing Data (1999). [7] Masuda, T.: Registration and integration of multiple range images by matching signed distance fields for object shape modeling, Comput. Vis. Image Underst., Vol. 87, pp. 51–65 (2002). [8] Rusu, R. B. and Cousins, S.: 3D is here: Point Cloud Library (PCL), International Conference on Robotics and Automation, Shanghai, China (2011). 28