(57)【要約】【課題】  カメラを移動しながら撮影した画像列だけを用いて、カメラ運動と物体の３次元形状を高精度かつ効率よく復元すること。【解決手段】  初期推定において、画像１から画像ｋまでに共通に現れる特徴点系列（Ｓ１２）に対して退化基準値を計算し（Ｓ１３）、退化基準値が閾値を超えた場合（Ｓ１４でＹｅｓ）にｋを初期推定に用いる適切な画像枚数として、カメラ運動と物体形状を求める。また、より精度を高めるために、特徴点系列（Ｓ１２）に対してロバスト推定を用いてカメラ運動と物体形状の解候補となる部分集合ｇｉとその復元基準値を求め（Ｓ１５）、復元基準値が閾値を越えたｇｉに対して退化基準値を計算し（Ｓ１６）、退化基準値が閾値を超えた場合（Ｓ１７でＹｅｓ）にｋを初期推定に用いる適切な画像枚数とし、スコア最良のｇｉをカメラ運動と物体形状を求めるための特徴点系列として採用する。【選択図】図２
2006252275.tif 000002
【特許請求の範囲】
【請求項１】
カメラを移動しながら撮影した画像列からカメラ運動と物体の３次元形状を復元するカメラ運動・物体形状復元システムであって、
入力した画像から特徴点を抽出して画像間での対応づけを行ない、該対応づけられた特徴点を特徴点記憶手段に記憶する特徴点抽出・追跡手段と、
初期値ｋを与え、入力した最初の画像からｋ番目の画像までの特徴点を前記特徴点記憶手段から読み出して、前記特徴点から基礎方程式行列を生成し、該基礎方程式行列の特異値を求めて該特異値から退化基準値を計算し、該退化基準値が所定の閾値を超えない場合はｋを増やしながら退化基準値の計算を繰り返し、該退化基準値が前記閾値を超えた場合には、前記最初の画像からｋ番目の画像までの特徴点からカメラの初期姿勢及び物体の特徴点の３次元位置を求めてそれぞれカメラ運動記憶手段及び３次元形状記憶手段に記憶する初期推定手段と、
前記カメラ運動記憶手段に記憶しているカメラ姿勢と前記３次元形状記憶手段に記憶している物体形状とを読み出すカメラ運動・物体形状読出手段と
を備えることを特徴とするカメラ運動・物体形状復元システム。
【請求項２】
請求項１に記載のカメラ運動・物体形状復元システムであって、
さらに、前記初期推定手段の処理後に、ｋ＋１番目の画像から最後の画像まで順に、現在の画像のカメラ姿勢を求めて前記カメラ運動記憶手段に記憶するカメラ姿勢推定と、特徴点の３次元位置を求めて前記３次元形状記憶手段に融合する物体形状復元とを交互に繰り返し行なう逐次推定手段
を備えることを特徴とするカメラ運動・物体形状復元システム。
【請求項３】
請求項１又は２に記載のカメラ運動・物体形状復元システムにおいて、
前記初期推定手段は、前記最初の画像からｋ番目の画像までの特徴点からロバスト推定によりカメラ運動と物体形状の復元に用いる特徴点の部分集合を求め、前記特徴点の部分集合から基礎方程式行列を生成し、該基礎方程式行列の特異値を求めて該特異値から退化基準値を計算し、該退化基準値が所定の閾値を超えない場合はｋを増やしながら退化基準値の計算を繰り返し、該退化基準値が前記閾値を超えた場合には、前記特徴点の部分集合からカメラの初期姿勢及び物体の特徴点の３次元位置を求めてそれぞれカメラ運動記憶手段及び３次元形状記憶手段に記憶すること
を特徴とするカメラ運動・物体形状復元システム。
【請求項４】
請求項３に記載のカメラ運動・物体形状復元システムにおいて、
前記初期推定手段は、前記特徴点の部分集合が複数求められた場合には、各部分集合について復元基準値を求め、該復元基準値と前記退化基準値とから計算されるスコアが最良である前記部分集合からカメラの初期姿勢及び物体の特徴点の３次元位置を求めてそれぞれカメラ運動記憶手段及び３次元形状記憶手段に記憶すること
を特徴とするカメラ運動・物体形状復元システム。
【請求項５】
請求項３又は４に記載のカメラ運動・物体形状復元システムにおいて、
前記初期推定手段は、前記特徴点の部分集合を求める前に、前記最初の画像からｋ番目の画像までの特徴点から退化基準値を求め、該退化基準値が所定の閾値を超えない場合はｋを増やしながら退化基準値の計算を繰り返し、該退化基準値が前記閾値を超えた場合に前記特徴点の部分集合を求めること
を特徴とするカメラ運動・物体形状復元システム。
【請求項６】
請求項２〜５のいずれかに記載のカメラ運動・物体形状復元システムにおいて、
前記逐次推定手段における物体形状復元は、現在の画像の特徴点と、前記特徴点記憶手段に記憶されている過去の各時点での画像の対応する特徴点とでそれぞれ３次元復元を行なってその共分散行列を求め、該共分散行列の値が最小かつ所定の閾値未満である３次元復元結果を該特徴点の３次元位置として前記３次元形状記憶手段に融合すること
を特徴とするカメラ運動・物体形状復元システム。
【請求項７】
請求項１〜６のいずれかに記載のカメラ運動・物体形状復元システムの機能をコンピュータ・システムに構成させるためのカメラ運動・物体形状復元プログラム。
【請求項８】
請求項１〜６のいずれかに記載のカメラ運動・物体形状復元システムの機能をコンピュータ・システムに構成させるためのカメラ運動・物体形状復元プログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、カメラを移動させながら撮影した画像列からカメラ運動及び物体形状を同時に復元するシステムに関するものである。
【背景技術】
【０００２】
カメラの画像列から物体の３次元形状を復元する手法として、エピポーラ幾何に基づく手法や因子分解法がある。両手法とも、画像間で特徴点を対応づけ、その特徴点の画像上の位置から、カメラの３次元運動（並進と回転）と物体の３次元形状を推定する。ここで、物体の３次元形状は、３次元空間に復元された特徴点の集合で表される。特徴点の抽出と対応づけは、例えば、非特許文献１で提案されているように、画像エッジのコーナ点や交差点に相当する特徴を抽出し、現画像での特徴点の近傍領域とよくマッチする領域を次画像から所定の範囲内で探索することで実現する。
エピポーラ幾何に基づく手法では、２枚の画像間で、カメラの位置姿勢、画像特徴点の位置、および、３次元特徴点の位置の間に成り立つ基礎方程式を８点以上の特徴点について並べた連立方程式を解いて基礎行列を求め、それをもとにカメラ運動と物体形状を復元するのが一般的である（非特許文献２  ２６２〜２６５頁）。
また、因子分解法では、カメラモデルとして弱透視投影などの線形モデルを仮定し、画像特徴点を並べた計測行列を特異値分解によってカメラ運動行列と物体形状行列に分解し、座標軸の直交制約を用いてユークリッド復元を行うのが一般的である（非特許文献３）。
【０００３】
しかしながら、上述の従来技術による方法は、エピポーラ幾何に基づく手法でも、因子分解法でも、カメラ運動の並進成分が対象物体までの距離に対して小さいと、復元結果が不安定になるという問題がある。たとえば、並進成分が０の場合は、退化が起きて、原理的に解は得られない。現実の画像では、画像特徴点抽出の誤差などの影響により完全な退化はおきず、物体形状が平面上に押しつぶされたような復元像が得られる。並進成分が０ではないが微小な場合も、程度は異なるが同様の現象が起こる。本明細書では、この場合も含めて退化と呼ぶ。
図５に退化の例を示す。図５（ａ）は、復元に用いる画像列の中の画像の一例である。（ａ）に示す対象物体は直角に交わった雑誌であり、カメラは雑誌を正面に見ながら横方向に動いて画像列を撮影した。画像上の白い点が抽出された特徴点である。図５（ｂ）および（ｃ）は、対象物体（雑誌）を横から見た視点で表示した復元結果であり、図５（ｂ）は、カメラ運動の並進成分が小さい場合の復元結果を示す図であり、５１０で示す矢印はカメラ視線の方向、５２０で示されている点が物体形状の復元結果である。図５（ｃ）は、並進成分が大きい場合の復元結果を示す図であり、５３０で示す矢印はカメラ視線の方向、５４０で示されている点が物体形状の復元結果である。本来は、図５（ｃ）のように、直角に交わった平面上に復元点が並ぶはずであるが、図５（ｂ）では、並進成分が小さいため、全特徴点が同一平面上に並んで復元されている。
【０００４】
このような退化に対処するには、カメラ運動の並進成分が十分大きくなるように画像列を撮影するか、あるいは、画像列の中から並進成分が大きくなる画像群を選択する必要がある。人間が介在するシステムでは、人間が目で見て画像を選択すればよいが、適切な画像枚数を選ぶには手間がかかる。また、移動ロボットにカメラを搭載したシステムで形状復元を行う場合には、システムが自動で適切な画像を選択する機構が必要になる。
この問題に対処する１つの方法として、カメラ運動の並進成分と対象物体までの距離を他のセンサを用いて測定する方法が考えられる。たとえば、特許文献１では、加速度センサなどでカメラの並進成分を測定し、また、距離センサを用いて物体までの距離を測定した結果を用いて、ノイズの影響が小さい、高精度な形状復元を行っている。しかし、この方法は、加速度センサや距離センサなど、カメラ以外のセンサを用いるため、装置が大がかりになるという問題がある。また、適用できる距離範囲が、距離センサの仕様に限定されるという問題もある。
一方、画像だけから退化を検出する方法として、画像特徴点の集合がエピポーラ幾何に従うか平面ホモグラフィに従うかの選択基準を評価して、平面ホモグラフィに従う場合に退化が起きていると判定する手法が非特許文献４で提案されている。また、この基準を用いて、十分な並進量が得られる画像間隔を選択する方法が非特許文献５で提案されている。
しかし、この方法では、エピポーラ幾何の他に平面ホモグラフィの計算も必要であり、特に、画像特徴点の誤差に対処するためにロバスト推定を行うと、エピポーラ幾何と平面ホモグラフィのそれぞれでロバスト推定が必要になり、処理時間が多くかかるという問題があった。
【０００５】
【特許文献１】特開平１１−０６３９４９「３次元形状復元装置及び方法」
【非特許文献１】J. Shi and C. Tomasi: “Good Features to Track,” Proceedings of International Conference on Computer Vision and Pattern Recognition, pp. 593-600, 1994.
【非特許文献２】R. Hartley and A. Zisserman: “Multiple View Geometry in Computer Vision,” Cambridge University Press, 2000.
【非特許文献３】C. Tomasi and T. Kanade: “Shape and Motion from Image Streams under Orthography: A Factorization Approach,” International Journal of Computer Vision, Vol.9, No.2, pp.137-154, 1992.
【非特許文献４】P. H. S. Torr, A. W. Fitzgibbon, and A. Zisserman: “The Problem of Degeneracy in Structure and Motion Recovery from Uncalibrated Image Sequences,”International Journal of Computer Vision, Vol. 32, No. 1, pp. 27-44, 1999.
【非特許文献５】D. Nister: “Reconstruction from Uncalibrated Sequences with a Hierarchy of Trifocal Tensors,” Proceedings of European Conference on Computer Vision, pp.649-663, 2000.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明の課題は、カメラ（以下、画像入力装置を総称してカメラと呼ぶ）を移動しながら撮影した画像列からカメラ運動と物体の３次元形状を同時に復元する際に、カメラからの画像列だけを用いて精度の高いカメラ運動及び物体形状の復元を効率よく実現することができる復元システムを構築することである。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明は、カメラを移動しながら撮影した画像列からカメラ運動と物体の３次元形状を復元するカメラ運動・物体形状復元システムであって、入力した画像から特徴点を抽出して画像間での対応づけを行ない、該対応づけられた特徴点を特徴点記憶手段に記憶する特徴点抽出・追跡手段と、初期値ｋを与え、入力した最初の画像からｋ番目の画像までの特徴点を前記特徴点記憶手段から読み出して、前記特徴点から基礎方程式行列を生成し、該基礎方程式行列の特異値を求めて該特異値から退化基準値を計算し、該退化基準値が所定の閾値を超えない場合はｋを増やしながら退化基準値の計算を繰り返し、該退化基準値が前記閾値を超えた場合には、前記最初の画像からｋ番目の画像までの特徴点からカメラの初期姿勢及び物体の特徴点の３次元位置を求めてそれぞれカメラ運動記憶手段及び３次元形状記憶手段に記憶する初期推定手段と、前記カメラ運動記憶手段に記憶しているカメラ姿勢と前記３次元形状記憶手段に記憶している物体形状とを読み出すカメラ運動・物体形状読出手段とを備えることを特徴とする。
上記のカメラ運動・物体形状復元システムは、さらに、前記初期推定手段の処理後に、ｋ＋１番目の画像から最後の画像まで順に、現在の画像のカメラ姿勢を求めて前記カメラ運動記憶手段に記憶するカメラ姿勢推定と、特徴点の３次元位置を求めて前記３次元形状記憶手段に融合する物体形状復元とを交互に繰り返し行なう逐次推定手段を備えていてもよい。
前記初期推定手段は、前記最初の画像からｋ番目の画像までの特徴点からロバスト推定によりカメラ運動と物体形状の復元に用いる特徴点の部分集合を求め、前記特徴点の部分集合から基礎方程式行列を生成し、該基礎方程式行列の特異値を求めて該特異値から退化基準値を計算し、該退化基準値が所定の閾値を超えない場合はｋを増やしながら退化基準値の計算を繰り返し、該退化基準値が前記閾値を超えた場合には、前記特徴点の部分集合からカメラの初期姿勢及び物体の特徴点の３次元位置を求めてそれぞれカメラ運動記憶手段及び３次元形状記憶手段に記憶することとしてもよい
前記初期推定手段は、前記特徴点の部分集合が複数求められた場合には、各部分集合について復元基準値を求め、該復元基準値と前記退化基準値とから計算されるスコアが最良である前記部分集合からカメラの初期姿勢及び物体の特徴点の３次元位置を求めてそれぞれカメラ運動記憶手段及び３次元形状記憶手段に記憶してもよい。
前記初期推定手段は、前記特徴点の部分集合を求める前に、前記最初の画像からｋ番目の画像までの特徴点から退化基準値を求め、該退化基準値が所定の閾値を超えない場合はｋを増やしながら退化基準値の計算を繰り返し、該退化基準値が前記閾値を超えた場合に前記特徴点の部分集合を求めてもよい。
前記逐次推定手段における物体形状復元は、現在の画像の特徴点と、前記特徴点記憶手段に記憶されている過去の各時点での画像の対応する特徴点とでそれぞれ３次元復元を行なってその共分散行列を求め、該共分散行列の値が最小かつ所定の閾値未満である３次元復元結果を該特徴点の３次元位置として前記３次元形状記憶手段に融合してもよい。
上述したカメラ運動・物体形状復元システムの機能をコンピュータ・システムに構成させるためのカメラ運動・物体形状復元プログラムやそのプログラムを記録した記録媒体も本発明である。
【発明の効果】
【０００８】
本発明のカメラ運動及び物体形状の復元システムによれば、人間からの指示や従来技術のようなカメラ以外のセンサ等を必要とせずに、カメラからの画像列だけを用いて、カメラ運動の並進成分が十分大きく確保できる画像枚数を自動的に選択し、精度の高いカメラ運動及び物体の３次元形状の復元を効率よく実現することができる。
このような本発明の復元システムは、移動ロボット、あるいは、自動車や飛行機などの移動機構にカメラを搭載して得た画像列から自動的にカメラ運動と物体形状を復元し、復元したカメラ運動や３次元物体形状を読み出して利用する場合等に、非常に有効である。また、３次元物体として環境全体を対象とすることで、環境の３次元マップを復元し、その環境マップやカメラ運動を読み出して利用する場合等にも有用である。
【発明を実施するための最良の形態】
【０００９】
以降、本発明のカメラ運動及び物体形状の復元システムの実施形態の一例を、図面を参照しながら詳細に説明する。なお、ここでは、画像入力装置全般を指して「カメラ」と呼ぶものとする。
まず、（１）本実施形態のカメラ運動及び物体形状の復元システムの処理の概要を説明し、次に、（２）本実施形態の復元システムで用いる新しい手法である基線長選択方法（復元に適切な画像枚数を決定する方法）について詳細に説明する。最後に、（３）本実施形態の復元システムを用いて実験を行なった結果を示す。
【００１０】
（１．カメラ運動及び物体形状の復元システムの処理の概要）
まず、本実施形態のカメラ運動及び物体形状の復元システムの処理の概要を説明する。例として、ここではパーソナルコンピュータなどのコンピュータに本発明の復元システムを構築し、カメラで撮影した画像列を該コンピュータに入力して、入力した画像列から自動的にカメラ運動及び対象物体の３次元物体形状を復元する場合を想定して説明する。例えば、上述したようなカメラを搭載した移動ロボットの内部に本発明の復元システムを構築し、記憶した３次元物体形状やカメラの動き（ロボットの動き）を読み出して利用することができる。
本実施形態では、オドメトリなどの内界センサを用いずに、標準的なレンズをつけた単眼カメラで撮影した画像列からカメラ姿勢を推定し、同時に３次元物体形状を復元する。３次元物体形状は画像から抽出した特徴点を３次元に復元した点の集合である。カメラ姿勢は３次元空間で位置と方向合せて６自由度をもつとする。なお、本発明をカメラを搭載する移動ロボットに用いる場合には、カメラ姿勢とロボット姿勢は同一視する。また、カメラ運動はカメラ姿勢の時系列という意味で用いるが、カメラ姿勢とカメラ運動をとくに区別せずに用いることもある。
【００１１】
本実施形態のカメラ運動及び物体形状の復元システムの処理の流れを図１に示す。ここで説明するシステム概要について、基本的な流れは、山崎・友納らのシステムに沿っている（K. Yamazaki, M. Tomono, T. Tsubouchi, and S. Yuta: “3-D Object Modeling by a Camera Equipped on a Mobile Robot,” Proceedings of the IEEE International Conference on Robotics and Automation, 2004.  を参照されたい。）が、本実施形態では、本実施形態の新しい手法である基線長選択方法を用いて、初期推定処理（図１のＳ１５０）において退化を起こさずにカメラ姿勢及び３次元物体形状を復元することができる適切な画像枚数ｍを決定する。基線長選択方法については、次項（２．基線長選択方法）で説明する。また、逐次推定処理における物体形状復元処理において、復元誤差がなるべく小さくなる適切な画像枚数を求める。
カメラの内部パラメータは既知とする。なお、ここで用いる時刻ｔは仮想的な時刻であり、画像枚数に対応した離散量である。
【００１２】
（１）特徴点抽出・追跡処理（Ｓ１４０）
図１に示すように、本実施形態の復元システムでは、まず、撮影した画像列１１０を本実施形態の復元システムが構築されたコンピュータ等に入力し、特徴点の抽出と追跡（画像間での特徴点の対応づけ）を行なう（Ｓ１４０）。
形状復元は、画像間で対応づけられた特徴をもとに、ステレオ視の原理で行われる。本実施形態では、この特徴点の抽出と対応づけには、従来技術であるＫＬＴトラッカを用いるが、他の手法を用いてもよい。ＫＬＴトラッカは、画像エッジのコーナ点や交差点に相当する特徴を抽出し、現画像での特徴点の近傍領域とよくマッチする領域を次画像から所定の範囲内で探索することで、特徴点の追跡を行う（詳しくは非特許文献１を参照）。
ＫＬＴトラッカにより、特徴点の対応はかなり良くとれるが、近くに似た特徴があると対応誤りが生じる。また、透視投影による変形が強い部分やオクルージョンの付近では、対応する特徴点の位置誤差が大きくなることがある。これらの問題には、後述のように、従来技術のＲＡＮＳＡＣを用いて対処する。
ここで求めた特徴点とその対応づけは、例えば図４に示すように、特徴点を一意に識別する番号と、どの画像から得られたかを示す番号をインデックスとして、配列などの記憶領域に記憶する。記憶された特徴点は、後で説明する初期推定処理（Ｓ１５０），逐次推定処理（Ｓ１６０〜Ｓ１７０）の各処理で用いる。
【００１３】
（２）初期推定処理（Ｓ１５０）
次に、Ｓ１４０で求めた特徴点から、初期推定を行なう（Ｓ１５０）。
本実施形態の復元システムにより３次元に復元された物体形状の特徴点は、記憶領域１３０に融合されて３次元物体形状を構成する。しかしながら、３次元物体形状復元の開始時（ｔ＝１〜ｍ）においては、本実施形態の復元システムは、まだ３次元物体形状が何もない状態で、入力した画像列だけからカメラ姿勢と３次元物体形状を同時に推定しなければならない。このため、従来技術である因子分解法を用いて、Ｓ１４０で求めた特徴点からカメラの初期姿勢ｒ１，…，ｒｍと物体の初期形状（物体形状の３次元特徴点の集合）を同時に求める（詳しくは非特許文献３を参照）。因子分解法は弱透視投影への近似による誤差をもつので、非線形最小化を用いて正確な解を求める。なお、因子分解法の代わりに、同じく従来技術であるエピポーラ幾何に基づく手法を用いてもよい。
因子分解法は、特徴点の座標を並べた行列Ｗを、特異値分解を用いて、カメラ運動を表す行列Ｍと物体形状を表す行列Ｓの積Ｗ＝ＭＳに分解する。この分解は一意ではないが、カメラ姿勢の座標軸の直交性に関する計量制約を用いて、Ｍを唯一に求める。
【００１４】
因子分解法では、透視投影を平行投影あるいは弱透視投影に線形近似する。このため、非常に安定して解けるという利点があるが、得られた復元結果には線形近似の誤差が含まれる。そこで、非線形最小化によって線形近似誤差を除去し、透視投影のもとでのカメラ運動と物体形状を求める。これは、式（１）に基づいて行う。
【数１】
2006252275.tif 000003
【００１５】
ここで、（ｕｔ，ｉ，ｖｔ，ｉ）は、時刻ｔの画像におけるｉ番目の特徴点の座標、ＲｔおよびＴｔは、それぞれ、時刻ｔのカメラ座標系の回転行列と並進量、Ｐｉ＝（Ｘｉ，Ｙｉ，Ｚｉ）Ｔはｉ番目の特徴点の３次元位置である。Ｐｔ，ｉは時刻ｔのカメラ座標系から見たｉ番目の特徴点の３次元位置である。また、ｍは画像枚数、ｎは特徴点数である。この式は、３次元空間の特徴点Ｐｉをカメラ姿勢に基づいて画像上に逆投影した誤差を表している。この非線形最小化問題は、因子分解法で求めた解を初期値として、繰り返し法を用いて解く。
なお、この処理では対象となる物体のスケールは決められないので、何らかの形で実スケールを与える必要がある。たとえば、人間がスケールを明示的に教える、既知の物体をロボットが認識してスケールを自動設定する、距離センサなど他のセンサを利用する、などの方法が考えられる。
【００１６】
特徴点の誤対応に対処するために、従来技術であるＲＡＮＳＡＣを用いてロバストな推定を行う（詳しくは「M. Fischler and R. Bolles: “Random Sample Consensus: a Paradigm for Model Fitting with Application to Image Analysis and Automated Cartography”, Communications ACM, 24:381-395, 1981.」を参照）。まず、特徴点からｎ１個の点をランダムに選び、上述の因子分解と非線形最小化によってカメラ姿勢を求めた後、そのカメラ姿勢に基づいて残りのｎ−ｎ１個の特徴点を３次元復元する。特徴点が誤対応をしていると、その３次元復元は大きな誤差をもつ。そこで、復元した３次元点を画像に逆投影して、対応する画像特徴点との誤差が所定の閾値以上であるものは誤対応として削除する。これを繰り返して、正しい特徴点対応の個数が最大になるカメラ姿勢を解として採用する。
ここで求めたカメラの初期姿勢は記憶領域１２０に記憶され、物体の初期形状（３次元特徴点）は記憶領域１３０に記憶される。
【００１７】
（３）逐次推定（Ｓ１６０〜Ｓ１７０）
初期推定（Ｓ１５０）の後は、カメラ姿勢と３次元特徴点を交互に推定する逐次推定を行なう（Ｓ１６０〜Ｓ１７０）ことにより、カメラ運動および物体形状を復元する。
（ｉ）カメラ姿勢の推定（Ｓ１６０）
時刻ｔ−１までに求めた物体形状の３次元特徴点（記憶領域１３０に記憶されている）と、時刻ｔの画像の特徴点がマッチするように、時刻ｔのカメラ姿勢を計算する。まず、時刻ｔ−１とｔの画像間で特徴点を追跡する。ここで得られた特徴点には、時刻ｔ−１以前から存在する特徴点もあるが、オクルージョンなどで消失した特徴点に代わって新たに抽出された特徴点もある。既に記憶領域１３０に登録されているのは時刻ｔ−１以前の特徴点なので、カメラ姿勢の推定にはこれらの特徴点だけを用いる。時刻ｔ−１までに記憶領域１３０に登録された３次元特徴点をＰｉ＝（Ｘｉ，Ｙｉ，Ｚｉ）Ｔとすると、次式を最小化するカメラ姿勢Ｒｔ，Ｔｔを求める。
【数２】
2006252275.tif 000004
これは、物体形状の３次元点を時刻ｔの画像に逆投影した誤差を表す。これも非線形最小化問題となるので、ｔ−１のカメラ姿勢（記憶領域１２０に記憶されている）を初期値として、繰り返し法を用いて解く。ここでも、特徴点の誤対応に対処するためにＲＡＮＳＡＣを用いる。
ここで求めたカメラ姿勢は、記憶領域１２０に記憶する。
【００１８】
（ｉｉ）物体形状の復元（Ｓ１７０）
特徴点ごとに、時刻ｔ−１以前のカメラ姿勢と時刻ｔのカメラ姿勢とから三角測量の原理で特徴点の３次元位置を求める。
時刻ｔ1とｔ２のカメラ姿勢（記憶領域１２０に記憶されている）と画像から３次元点の位置を求める。時刻ｔ１のカメラから見たｔ２のカメラ姿勢をＲ，Ｔとすると、両時刻の特徴点ｑｔ１，ｉ，ｑｔ２，ｉの間には次の関係が成り立つ。ｓ１，ｓ２は奥行きを表すパラメータである。
【数３】
2006252275.tif 000005
特徴点抽出やカメラ姿勢推定の誤差のため、ほとんどの場合、この方程式は厳密には解けないので、以下の二乗誤差を最小にする解を求める。
【数４】
2006252275.tif 000006
３次元復元した特徴点は、記憶領域１３０に既に記憶されている３次元特徴点と融合する。このようにして、３次元物体形状を復元する。なお、３次元復元した特徴点を３次元物体形状に融合する方法については、後で詳しく説明する。
【００１９】
（２．基線長選択方法）
背景技術で述べたように、従来、カメラ運動及び物体形状の復元においては、カメラ運動の並進成分が対象物体までの距離に対して微小な場合に、退化が起きることにより復元結果が不安定になるという問題があった。
本実施形態では、入力された画像列だけから並進成分に関する退化を検出し、さらに、初期推定処理において十分な並進成分が確保できるだけの適切な画像枚数を求める方法を提案することにより、上記の問題を解決する。
以降、本実施形態の復元システムで提案する基線長選択方法について詳細に説明する。
本実施形態で提案する基線長選択方法は、初期推定処理（図１のＳ１５０）で用いる画像枚数（基線長）を決定する処理であり、具体的には、例えば、ここで提案する基線長選択方法の処理の各ステップを初期推定処理（Ｓ１５０）に組み込むことにより実現することができる。
【００２０】
上記問題に対処するため、本実施形態では、画像特徴点の系列で構成される基礎方程式行列の特異値を調べることにより、その特徴点系列から退化を起こさずにカメラ運動と物体形状が復元できるかを調べる。
退化のチェックは、画像列の最初の画像Ｉ１とｋ番目の画像Ｉｋの２枚で行う。いま、画像Ｉ１上の特徴点ｑ１，ｉに対応する画像Ｉｋ上の特徴点をｑｋ，ｉとし、両画像間の基礎行列をＦ１，ｋとすると、次の基礎方程式が成り立つ（非特許文献２参照）。
【数５】
2006252275.tif 000007
【００２１】
上式を展開し、同次座標系で表した各画像特徴点ｑ１，ｉ＝（ｕ１ｉ，ｖ１ｉ，１）Ｔ，ｑｋ，ｉ＝（ｕｋｉ，ｖｋｉ，１）Ｔ，（１≦ｉ≦ｎ）に関してまとめると、次式が得られる。
【数６】
2006252275.tif 000008
【数７】
2006252275.tif 000009
ここで、ｆは基礎行列Ｆ１，ｋの要素を一列に並べたベクトルである。本明細書では、この行列Ａを基礎方程式行列と呼ぶ。
【００２２】
非特許文献２の２７９〜２８０頁によると、微小並進により退化が起こると、行列Ａのランクは６になる。したがって、行列Ａのランクを調べれば、退化が起きているかどうかを判定できる。ところが、実際には、並進成分が完全に０でなくても、前述のように広い意味での退化は起きる。また、ノイズの影響により、行列Ａのランクが厳密に６になることはない。
そこで、本発明では、行列Ａを特異値分解し、特異値を大きい順に並べて、その７番目の特異値（第７特異値）と８番目の特異値（第８特異値）が０に近いかどうかで退化を判定する。たとえば、それぞれの特異値をｓ７，ｓ８とすると、その相乗平均であるＤ＝√ｓ７ｓ８を退化の尺度として用いる。これを退化基準とよぶことにする。退化基準Ｄの大小によって、退化の有無だけでなく、退化の度合もわかる。これにより、Ｄが適当な閾値を超えたかどうかで、退化が起こらずに高精度な復元ができるかどうかを判定することができる。すなわち、画像枚数ｋを増やしながら、退化基準値が閾値を超えるｋを求め、そのときのｋを十分な並進成分（基線長）が確保できる適切な画像枚数として採用する。
画像特徴点の誤追跡があると、基礎方程式行列に大きなノイズが入ることになるので、実際は退化が起きているにもかかわらず、退化基準値が大きくなることがありうる。そこで、ロバスト推定により画像特徴点の誤追跡分を除去した後で、退化基準値の計算を行う。
以上のように、退化基準値によって退化の度合まで考慮して適切な画像枚数を求める点、および、ノイズを除去した上で信頼性の高い退化基準値を計算する点が本発明の特徴である。
【００２３】
図２は、上述で説明した基線長選択方法を、本実施形態の復元システムにおいて処理する場合の処理の流れ図である。なお、上述したように、図１に示す初期推定処理（Ｓ１５０）に、ここで説明する基線長選択方法の処理の各ステップを組み込むことにより実現することができる。
まず、ステップＳ１１において、画像枚数ｋの初期値ｋ０を与える。次に、ステップＳ１２において、画像１から画像ｋまでに共通して現れる特徴点系列Ｆを抽出する。なお、特徴点は上述した特徴点抽出・追跡処理（図１のＳ１４０）により求められ、記憶されている。
次に、ステップＳ１３において、特徴点系列Ｆ全体に対して、退化基準値Ｄを計算する。そして、ステップＳ１４において、Ｆの退化基準値が所定の閾値を超えるかどうかを判定し、閾値を超える場合はステップＳ１５に進み、閾値を超えない場合はステップＳ１９でｋを増やしてステップＳ１２に戻る。特徴点系列Ｆ全体で退化が起きている場合は、Ｆのどの部分集合を選んでも退化が起きると予想される。その場合にステップＳ１５以降に進むのは無駄であり、処理の効率化のため、ステップＳ１３〜Ｓ１４でＦ全体の退化判定を行う。
【００２４】
なお、ステップ１５以降の処理を行なわず、ステップＳ１４でＦの退化基準値が閾値を超えた場合のｋを適切な画像枚数として採用することもできる。（この場合、ステップＳ１４でＹｅｓになれば処理を終了する。）
また、ステップ１３，ステップ１４を行なわずに（ロバスト推定を行なう前に特徴点系列Ｆ全体での退化判定を行なわずに）ステップ１２からステップＳ１５に進む処理とすることもできる。
【００２５】
ステップＳ１５では、ＲＡＮＳＡＣなどのロバスト推定を用いて、カメラ運動と物体形状を求める。このロバスト推定は、特徴点の誤追跡を取り除くことにより、精度の高い復元を実現するとともに、ステップＳ１６での退化基準値の信頼性を上げるために行う。そして、誤追跡された特徴点をＦから取り除き、特徴点系列の部分集合を求める。このとき、精度のよい復元を与える特徴点系列の部分集合が複数個得られることがあるので、部分集合の族｛ｇｉ｝を解候補として登録する。そして、解候補から適切な解となる部分集合を１つ選択するために、各部分集合ｇｉに対して、復元の良さを表す復元基準値を計算する。なお、求められた部分集合が１つである場合には、最適な画像枚数ｋにおける部分集合をそのまま解として採用すればよい。
次に、ステップＳ１６において、各ｇｉに対して退化基準値を計算する。そして、ステップＳ１７において、退化基準値が閾値を超えるｇｉがあるかどうかを判定し、閾値を超えるｇｉがあればステップＳ１８に進み、閾値を超えるｇｉがなければステップＳ１９でｋを増やしてステップＳ１２に戻る。ステップＳ１８では、ｋを十分な並進成分（基線長）が確保できる適切な画像枚数として採用し、また、特徴点系列として退化基準値と復元基準値から計算されるスコアが最良となるｇｉを選択する。
以下、図２の処理フローの各ステップについて詳細に説明する。
【００２６】
ステップＳ１１は、画像列から取り出す画像枚数ｋを規定し、画像列から最初の画像とｋ番目の画像を取り出す。ｋの初期値ｋ０は適当な値を与えてよい。ただし、エピポーラ幾何に基づく手法ではｋ０は２以上、因子分解法で復元する場合はｋ０は３以上にする必要がある。
ステップＳ１２では、画像１から画像ｋまでに共通して現れる特徴点集合を求める。各画像の特徴点は、従来の技術及び上述の特徴点抽出・追跡処理（Ｓ１４０）で説明した方法により、画像エッジのコーナ点やテクスチャの複雑な点を抽出し、画像間で追跡すればよい。得られた特徴点は、図４に示すように、特徴点を一意に識別する番号と、どの画像から得られたかを示す番号をインデックスとして、配列などの記憶領域に格納される。
【００２７】
ステップＳ１３では、特徴点系列Ｆに対して、図３に示す手順で退化基準値を計算する。図３では、まず、ステップＳ２１において、式（７）にしたがって、特徴点系列から基礎方程式行列Ａを生成する。この際、ノイズの影響を軽減し、また、特異値の範囲を標準化するために、エピポーラ幾何に基づく復元でよく行われる方法にしたがって、特徴点の座標値を正規化しておく。すなわち、画像特徴点ｑ１，ｉ，ｑｋ，ｉ全体の重心を計算し、その重心を原点として、ｑ１，ｉ，ｑｋ，ｉのｕ座標値およびｖ座標値の範囲が−√２〜√２の間に入るように、各ｑ１，ｉ，ｑｋ，ｉを正規化する（詳しくは、R. Hartley: “In defense of the eight-point algorithm,” IEEE Transaction on Pattern Analysis and Machine Intelligence, Vol. 19, No. 6, pp. 580--593, 1997. を参照）。
次に、ステップＳ２２において、行列Ａを特異値分解する。特異値は大きい順にソーティングしておく。そして、ステップＳ２３において、第７特異値と第８特異値から退化基準を計算する。退化基準としては、たとえば、前述のように相乗平均を用いてもよいし、相加平均や二乗平均など、他の基準を用いてもよい。
ステップＳ１４は退化基準値を閾値によって判定するステップであり、該閾値は経験的に与える。
【００２８】
ステップＳ１５では、特徴点の誤対応に対処するために、たとえば、ＲＡＮＳＡＣを用いてロバストな推定を行う。まず、特徴点系列Ｆからｎ１個の特徴点をランダムに選び、前述のエピポーラ幾何に基づく手法や因子分解法を用いて、このｎ１個の点を復元するカメラ姿勢を求めた後、そのカメラ姿勢に基づいて残りのｎ−ｎ１個の特徴点を３次元復元する。特徴点が誤対応をしていると、その３次元復元は大きな誤差をもつ。そこで、復元した３次元点をもとの画像上に逆投影した位置と、対応する画像特徴点との位置の誤差が所定の閾値以上であるものは誤追跡として削除する。特徴点系列Ｆから誤追跡分を除いた特徴点系列の部分集合をｇｉとする。そして、ｇｉに含まれる特徴点の個数を、このｇｉの復元の良さを表す復元基準値とする。これは、逆投影誤差の小さい特徴点を多くもつカメラ姿勢ほどよいということを表している。以上の処理を繰り返して、復元基準値が閾値を超えたｇｉを解候補とする。なお、ＲＡＮＳＡＣの詳細は上述で紹介したM. Fischler and R. Bollesの文献に述べられている。また、ＲＡＮＳＡＣ以外に、ＬＭｅｄｓなどの他のロバスト推定の手法を用いてもよい。
【００２９】
ステップＳ１６では、特徴点系列の部分集合ｇｉに対して、ステップＳ１３と同様に、図３に示す手順で退化基準値を計算する。
ステップＳ１７は、ステップＳ１４と同様に、退化基準値を閾値によって判定するステップであり、該閾値は経験的に与える。
ステップＳ１８では、そのときのｋを十分な並進成分が確保できる適切な画像枚数とし、また、候補ｇｉのうち、スコアが最良のものを、復元に用いる特徴点系列として選ぶ。ここでのスコアとして、たとえば、復元基準値、あるいは、退化基準値をそのまま用いてもよい。または、復元基準値と退化基準値の平均などによりスコアを定義してもよい。
ステップＳ１９は、現在の画像枚数ｋに増分ｄｋを加えて、画像列から最初の画像とｋ＋ｄｋ番目の画像を取り出す。ｄｋの値は標準的には１であるが、動画像のように間隔の小さい画像の場合は、ｄｋを１より大きくしてもよい。
【００３０】
以上の処理により、退化基準値が閾値を超える画像枚数ｋを自動的に求め、しかも、復元基準値が高くなる特徴点系列の部分集合ｇｉを求めることができる。そして、選ばれた画像枚数と特徴点系列の部分集合を用いて、上述の初期推定処理（図１のＳ１５０）で説明した方法により、カメラ運動と物体形状を復元して、カメラ初期姿勢は記憶領域１２０に記憶し、物体形状の３次元点（３次元物体の初期形状）は記憶領域１３０に記憶する。
なお、一般に、退化基準値は、カメラ運動の並進成分が長いほど、また、特徴点数が多いほど大きくなる。ところが、並進成分が大きくなると画像間で共通に抽出できる特徴点が減るため、ある時点から退化基準値は減少する。また、カメラ運動の仕方や対象物体の形状によっては、画像枚数をいくら増やしても、退化基準値が閾値を超えずに減少に向かうことがありうる。これに対処するため、あらかじめ画像枚数の上限値を定めておき、画像枚数がその上限値を超えても退化基準値が閾値を超えなければ、別の画像列に変えて再試行する処理を加えてもよい。あるいは、退化基準値が減少に向かった時点で、別の画像列に変えて再試行するようにしてもよい。
【００３１】
（微小並進下での３次元点の復元方法）
上述で説明した基線長選択方法では、特徴点の集合に対して基準が最もよく満たされる画像枚数を選択することにより、初期推定処理におけるカメラ姿勢と３次元特徴点の復元を改善することができる。
しかしながら、並進成分が０に近い場合のもう１つの問題として、３次元点の復元精度が極端に悪くなることが挙げられる。特徴点の３次元復元は三角測量の原理で行うので、その基線長が短いと復元精度が悪くなる。特徴点の３次元位置の精度が悪いと、次のカメラ姿勢推定に誤差が伝播し、どんどん誤差が拡大する。この問題は、初期推定と逐次推定の両方に現れる。これに対処するために、ここでは、逐次推定処理において、復元精度が許容範囲内に収まるよう基線長が十分長くなるまで３次元特徴点の復元を行わない方法を提案する。なお、初期推定処理で復元された３次元特徴点も、ここで説明する処理の対象となりうる。
具体的には、逐次推定処理における物体形状復元処理（図１のＳ１７０）にここで説明する処理を組み込むことにより実現することができる。
【００３２】
ここでは、復元精度の評価のために、特徴点の３次元復元の共分散行列 Ｖ［Ｐ］＝Ｅ［ΔＰΔＰＴ］を用いる。これは、次のように計算される。
【数８】
2006252275.tif 000010
ただし、ｓ１は前述の式（３）の奥行パラメータであり、Ｖ［ｓ１］＝Ｅ［（Δｓ１）２］、Ｖ［ｑ，ｓ１］＝Ｅ［ΔｑΔｓ１］である。なお、これらの導出については「K. Kanatani: “Statistical Optimization for Geometric Computation: Theory and Practice,” Elsevier, Amsterdam, 1996.」を参照されたい。
【００３３】
一般に、複数の画像間で同じ特徴点が追跡できるので、復元結果も複数得られる。それらを共分散行列を用いて融合する。時刻ｔ−１までに記憶領域１３０に３次元物体形状として登録されている特徴点の３次元位置をＰｔ−１、その共分散行列をＶ［Ｐｔ−１］とすると、時刻ｔで得た復元結果Ｐｔとその共分散行列Ｖ［Ｐｔ］を融合して、記憶領域１３０に記憶されている３次元位置を更新する。
【数９】
2006252275.tif 000011
３次元点の復元においては、どの画像対を選んで復元計算をするかにより、復元結果の精度が変わる。画像上の特徴点位置ｑの誤差分布は全画像で同じものを使うとすると、復元精度はカメラ姿勢に依存する。直観的には、基線長が長いほど精度がよくなる。そこで、式（８）を用いて、なるべく誤差が小さくなる画像対を選ぶ。以下に手順を示す。
【００３４】
（１）時刻ｔの画像特徴点ｑｔ，ｉに対応する特徴点を過去の画像から求め、その集合をＱｉとする。
（２）Ｑｉ内の各時刻ｔｋでの特徴点ｑｔｋ，ｉに対して、ｑｔ，ｉと組み合わせて上述で説明した逐次推定の方法により３次元復元を行い、その結果から式（８）を用いてＶ［Ｐｔ，ｉ］を計算する。
（３）共分散行列Ｖ［Ｐｔ，ｉ］の行列式の値が最小で、かつ、所定の閾値未満となるｑｔｋ，ｉがあれば、それとｑｔ，ｉを用いて３次元復元を行った結果を解として採用し、式（９）に基づいて記憶領域１３０に記憶されている３次元物体形状に融合する。
このようにして、本実施形態の逐次推定処理における物体形状復元処理（図１のＳ１７０）において、復元精度を向上させることができる。
【００３５】
（３．本実施形態の復元システムを用いた実験）
最後に、上述で説明した本実施形態のカメラ運動及び物体形状の復元システムを用いて実験を行なった結果を示す。
実験の条件として、人間がデジタルカメラを持ち、歩きながら連写モードで静止画を撮影した。もとの静止画は６４０×４８０であるが、これを３２０×２４０に縮小して使用した。撮影した画像からオフラインで復元実験を行った。
【００３６】
（１）最適な基線長（画像枚数）の選択
本実施形態の基線長選択方法により復元に最適な画像枚数（基線長）を自動的に選択する実験例を図５に示す。図５（ａ）は、用いた画像列のうちの画像例と、各々の画像に抽出された特徴点を示している。追跡した特徴点数は５０個である。この例では、カメラをゆっくり動かし、並進成分を小さくした。（ｂ）は、最初の画像３枚を用いて初期推定を行った復元例を読み出したものである。矢印５１０はカメラ視線の方向、５２０で示される点が復元結果である。実際は直角をなすべき部分がゆるやかになって、平面に近い形状になっているのがわかる。このときの退化基準値Ｄは０．０２であった。（ｃ）は、本実施形態の方法で適切な基線長を自動的に求めて得た復元結果を読み出したものである。矢印５３０はカメラ視線の方向、５４０で示される点が復元結果である。直角部分がうまく復元されていることがわかる。要した画像枚数は２４枚、退化基準値Ｄは０．２２であった。
上述した３次元復元の誤差分散の様子を図６に示す。対象物体は図５と同じである。図６では、視線方向の標準偏差を線分の長さで表している。復元点は各線分の中点である。（ａ）は基線長が画像１０枚の場合である。矢印６１０はカメラ視線の方向、６２０で示される線分が復元結果（標準偏差を示す線分）である。（ｂ）は基線長が画像２０枚の場合である。矢印６３０はカメラ視線の方向、６４０で示される線分が復元結果（標準偏差を示す線分）である。基線長が長い方が誤差が小さくなる様子がわかる。また、カメラから遠い点ほど誤差が大きいこともわかる。この標準偏差値は、実スケールが不定なのでカメラからの距離との比で表すと、（ａ）で０．０５５〜０．０７、（ｂ）で０．０１７〜０．０２であった。
【００３７】
（２）カメラ姿勢と物体形状の復元例
（ｉ）階段
図７に大学校舎の玄関の階段を画像９０枚から復元した例を示す。初期推定での基線長は画像３枚であった。（ａ）〜（ｃ）は入力された画像の例、（ｄ）は側面から見た復元結果である。７１０が復元されたカメラ姿勢、７２０が復元された物体の３次元点である。また、（ｅ）は正面から見た復元結果であり、７３０が復元されたカメラ姿勢、７４０が復元された物体の３次元点である。上下方向のカメラ運動や階段段差が復元できていることがわかる。これは、ロボットの不整地での移動に利用できることを示唆する。
（ｉｉ）ビル
図８に大学校舎を１２０枚の画像から復元した例を示す。初期推定での基線長は画像９枚であった。（ａ）〜（ｃ）は入力された画像の例、（ｄ）は側面から見た復元結果である。８１０が復元されたカメラ姿勢、８２０が復元された物体の３次元点である。また、（ｅ）は正面から見た復元結果であり、８３０が復元されたカメラ姿勢、８４０が復元された物体の３次元点である。このように、基線長を調節できる本方式では、遠方の物体も復元できる。撮影の途中で階段を降りた様子（８５０）も復元できている。
（ｉｉｉ）屋内
図９に研究室内で机を撮影した画像から復元した例を示す。初期推定での基線長は画像４枚であった。（ａ）は入力された画像の例（８枚）、（ｂ）は側面から見た復元結果である。９１０が復元されたカメラ姿勢、９２０が復元された物体の３次元点である。また、（ｃ）は正面から見た復元結果であり、９３０が復元されたカメラ姿勢、９４０が復元された物体の３次元点である。カメラの動きは不規則であるが、うまく復元できている。
【図面の簡単な説明】
【００３８】
【図１】本実施形態の復元システムの全体的な処理フローを示す図である。
【図２】本実施形態のカメラ運動及び物体形状復元処理の手順の一例を示す流れ図である。
【図３】退化基準の計算手順の一例を示す流れ図である。
【図４】画像特徴点の構成の一例を示す図である。
【図５】本実施形態の復元システムを用いた実験結果を示す図である。
【図６】本実施形態の復元システムを用いた実験結果を示す図である。
【図７】本実施形態の復元システムを用いた実験結果を示す図である。
【図８】本実施形態の復元システムを用いた実験結果を示す図である。
【図９】本実施形態の復元システムを用いた実験結果を示す図である。
【図１】
2006252275.tif 000012
【図２】
2006252275.tif 000013
【図３】
2006252275.tif 000014
【図４】
2006252275.tif 000015
【図５】
2006252275.tif 000016
【図６】
2006252275.tif 000017
【図７】
2006252275.tif 000018
【図８】
2006252275.tif 000019
【図９】
2006252275.tif 000020