(57)【要約】【課題】  ２枚の画像を撮影したカメラ間の相対姿勢を該画像から安定して推定すること。【解決手段】  特徴点追跡手段１０１は画像１と画像２の間で特徴点の対応をとる。カメラ姿勢スコア分布記憶手段１０３は、離散化したカメラ姿勢の尤もらしさを表すスコアを記憶する。カメラ姿勢スコア分布生成手段１０２は、離散化したカメラの回転角の各々に対して、特徴点追跡手段１０１で得た特徴点対応集合から２組の特徴点対応を取り出して特徴点対応ペアを作り、該特徴点対応ペアの各々に対して、エピポーラ幾何に基づいてカメラの並進量を計算し、該回転角と該並進量の組からなるカメラ姿勢のスコアをカメラ姿勢スコア分布記憶手段１０３を用いて集計して、カメラ姿勢のスコア分布を求める。カメラ姿勢仮説選択手段１０４は、該スコア分布に基づいて、スコアが所定の閾値を超えるか極大値をとるカメラ姿勢を仮説として選択する。【選択図】図１
2008224641.tif 000002
【特許請求の範囲】
【請求項１】
２枚の画像を撮影したカメラ間の相対姿勢を推定するシステムにおいて、画像１と画像２の間で特徴点の対応をとる特徴点追跡手段と、離散化したカメラ姿勢に対して、該カメラ姿勢の尤もらしさを表すスコアを記憶するカメラ姿勢スコア分布記憶手段と、離散化したカメラの回転角の各々に対して、前記特徴点追跡手段で得た特徴点対応集合から２組の特徴点対応を取り出して特徴点対応ペアを作り、該特徴点対応ペアの各々に対して、エピポーラ幾何に基づいてカメラの並進量を計算し、該回転角と該並進量の組からなるカメラ姿勢のスコアを前記カメラ姿勢スコア分布記憶手段を用いて集計して、カメラ姿勢のスコア分布を求めるカメラ姿勢スコア分布生成手段とを備えることを特徴とするカメラ姿勢推定システム。
【請求項２】
前記カメラ姿勢スコア分布記憶手段に記憶されたカメラ姿勢スコア分布に基づいて、スコアが所定の閾値を超えるか極大値をとるカメラ姿勢を仮説として選択するカメラ姿勢仮説選択手段を備えることを特徴とする請求項１記載のカメラ姿勢推定システム。
【請求項３】
前記カメラ姿勢仮説選択手段が生成した各カメラ姿勢仮説に対して、前記特徴点追跡手段で得た各特徴点対応について、エピポーラ幾何に基づいて該カメラ姿勢仮説と整合がとれているかどうかを判定する特徴点誤対応検出手段を備えることを特徴とする請求項２記載のカメラ姿勢推定システム。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、２枚の画像を撮影したカメラ間の相対姿勢を該画像から推定するシステムに関する。
【背景技術】
【０００２】  本発明で対象とするカメラ姿勢推定は、２枚の画像を入力して、両画像を撮影したカメラ間の相対姿勢を出力するものである。これら２枚の画像を画像１および画像２と表す。カメラ姿勢は、後述するように、両画像から抽出された特徴点をもとに推定する。画像１と画像２は、１台のカメラを移動して撮影してもよいし、別々に配置した２台のカメラで撮影してもよい。ここでいうカメラ姿勢とは、前者の場合はカメラの移動量であり、後者の場合は画像１を撮影したカメラから見た画像２を撮影したカメラの相対姿勢である。
カメラ姿勢は、３次元空間での回転角と並進量の組で表される。回転角は３次元の回転が表せれば、オイラー角やロール・ピッチ・ヨーなど、どのような表現方法でもよい。並進量は３次元の平行移動ベクトルである。ただし、画像のみから並進量を推定する場合は、一般に実寸法を知ることができないため、通常、その長さを１に正規化する。このため、並進量の実質的な自由度は２となる。なお、カメラの内部パラメータは既知とする。【０００３】  このような条件においてカメラで撮影した２枚の画像からカメラ姿勢を推定する手法として、エピポーラ幾何に基づく方法がある。これは、まず、画像から顕著な特徴点を抽出して、画像間で特徴点の対応をとり、次に、特徴点の画像上の位置とカメラ姿勢に関する幾何学的関係であるエピポーラ幾何を用いてカメラ姿勢を推定するものである。【０００４】  特徴点の抽出と対応づけは、たとえば、非特許文献１で提案されている方法を用いる。まず、画像１から画像エッジのコーナ点や交点に相当する点を特徴点として抽出する。次に、その特徴点を中心とする一定範囲の領域を画像１から取り出して、その領域と最もよく一致する領域を画像２から探索し、得られた画像２上の領域の中心点を前記特徴点と対応づける。これを画像１で抽出された各特徴点に対して繰り返す。【０００５】  エピポーラ幾何に基づくカメラ推定手法の代表例として８点法がある。８点法では、画像１および画像２上の特徴点の位置とカメラ姿勢との間に成り立つ関係式を８個以上の特徴点について並べた連立方程式を解いてカメラ姿勢を求める（非特許文献２、２６２〜２６５頁）。【０００６】
【非特許文献１】  Ｊ．Ｓｈｉ  ａｎｄ  Ｃ．Ｔｏｍａｓｉ：  “Ｇｏｏｄ  Ｆｅａｔｕｒｅｓ  ｔｏ  Ｔｒａｃｋ，”Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ，ｐｐ．５９３−６００，１９９４．
【非特許文献２】  Ｒ．Ｈａｒｔｌｅｙ  ａｎｄ  Ａ．Ｚｉｓｓｅｒｍａｎ：“Ｍｕｌｔｉｐｌｅ  Ｖｉｅｗ  Ｇｅｏｍｅｔｒｙ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，”Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，２０００．
【発明の開示】
【発明が解決しようとする課題】
【０００７】  背景技術で述べた方法は、特徴点の誤対応（以後、アウトライアと呼ぶ）があると、カメラ姿勢の推定に誤りが生じる。この問題に対処するために、ランダムサンプリングに基づくロバスト推定の手法がよく用いられる。
たとえば、ランダムサンプリングに基づくロバスト推定手法の代表例であるＲＡＮＳＡＣを用いた方法では、非特許文献１、２７５頁にあるように、特徴点対応の全体集合の中から所定の個数の特徴点対応を乱数を用いてランダムに取り出し、その特徴点対応群を用いて、前記手法によりカメラ姿勢の仮説を求める。そして、特徴点対応の全体集合のなかで、その仮説に矛盾しないものの個数をカウントする。このカウント数を仮説のスコアとする。これを所定の回数だけ繰り返し、そこで生成された仮説のうちスコアが最大のものを解として採用する。【０００８】  このようなランダムサンプリングに基づく手法の問題の１つは、乱数を用いるため、良い解が確率的にしか得られず、再現性が悪いことである。すなわち、全く同じ条件であっても、ある確率で失敗する。また、良い解が得られる場合でも、試行のたびに値が異なる。
もう１つの問題は、ランダムサンプリングに基づく手法は、解探索の網羅性が不十分であるという点である。ランダムサンプリング手法では、特徴点対応の集合の中で解を探索するため、カメラ姿勢空間をすべて調べたかどうかの判定が難しい。すなわち、良い解を見逃していないかどうかを直接に判定できない。一般に、アウトライア比率が大きかったり、特徴点の抽出位置の誤差が大きい場合、失敗する確率は増える。この場合、ランダムサンプリングの回数を増やすしか対処法がないが、特徴点対応の集合で探索するとカメラ姿勢空間の同じ領域を何度も調べる可能性があり、網羅性が悪いうえに効率も悪い。
本発明は、これらの問題に対処してカメラ姿勢推定の再現性と網羅性を高め、安定した推定結果を得ることを目的とする。
【課題を解決するための手段】
【０００９】  上述の目的を達成するために、本発明は、２枚の画像を撮影したカメラ間の相対姿勢を推定するシステムにおいて、画像１と画像２の間で特徴点の対応をとる特徴点追跡手段と、離散化したカメラ姿勢に対して、該カメラ姿勢の尤もらしさを表すスコアを記憶するカメラ姿勢スコア分布記憶手段と、離散化したカメラの回転角の各々に対して、前記特徴点追跡手段で得た特徴点対応集合から２組の特徴点対応を取り出して特徴点対応ペアを作り、該特徴点対応ペアの各々に対して、エピポーラ幾何に基づいてカメラの並進量を計算し、該回転角と該並進量の組からなるカメラ姿勢のスコアを前記カメラ姿勢スコア分布記憶手段を用いて集計して、カメラ姿勢のスコア分布を求めるカメラ姿勢スコア分布生成手段とを備えることを特徴とするカメラ姿勢推定システムである。【００１０】  また、該カメラ姿勢推定システムは、前記カメラ姿勢スコア分布記憶手段に記憶されたカメラ姿勢スコア分布に基づいて、スコアが所定の閾値を超えるか極大値をとるカメラ姿勢を仮説として選択するカメラ姿勢仮説選択手段を備えてもよい。【００１１】  また、該カメラ姿勢推定システムは、前記カメラ姿勢仮説選択手段を備えるともに、前記カメラ姿勢仮説選択手段が生成した各カメラ姿勢仮説に対して、前記特徴点追跡手段で得た各特徴点対応について、エピポーラ幾何に基づいて該カメラ姿勢仮説と整合がとれているかどうかを判定する特徴点誤対応検出手段を備えてもよい。
【発明の効果】
【００１２】  本発明によれば、乱数を用いずにカメラ姿勢の有力仮説を求めるため、同じ条件ではつねに同じ結果が得られるという再現性を保証できる効果がある。
また、本発明はカメラ姿勢空間で解探索を行うため、網羅性が高く、カメラ姿勢の有力仮説を取りこぼすことが少ないという効果がある。
【発明を実施するための最良の形態】
【００１３】  以下に、図面を用いて、本発明を実施するための形態を説明する。
＜概要＞
本発明では、上述の課題に対処するため、カメラ姿勢空間を探索して、有力なカメラ姿勢仮説を網羅的に求める。上述のように、並進量の自由度は２であるため、カメラ姿勢空間は実質的には５次元であるが、これを全探索するには膨大な計算を要し、効率が悪い。この効率化のために、本発明のカメラ推定システムでは次のように対処する。
まず、エピポーラ幾何を利用して探索空間を実質的に３次元に減らす。エピポーラ幾何のもとでは、後述するように、カメラの回転角を与えると並進量は２組の特徴点対応から計算できる。これにより、並進量は回転角に依存して求まるので、探索は３次元の回転角空間だけで行えばよい。なお、以後、２組の特徴点対応を特徴点対応ペアと呼ぶ。【００１４】  次に、探索を回転角空間に限定することで、探索範囲を狭めることができる。一般に、画像間で特徴点を追跡するには、画像撮影の際にカメラ回転角を小さくしなければならない。これは、カメラ回転角を大きくすると、画像１で抽出した特徴点の多くは画像２の外にはみ出てしまうからである。また、画像２に特徴点が写ったとしても、カメラ回転角が大きいと画像１に対する画像２の形状歪みや位置ずれが大きくなることが多く、特徴点の対応づけが困難になるからである。このため、回転角空間での探索は比較的小さい範囲に限定できる。多くの場合、３個の各回転角について、たとえば、±１０°程度の範囲ですむ。【００１５】  探索を網羅的に行うために、カメラ姿勢空間にカメラ姿勢の尤もらしさを示すスコア分布を作る。まず、回転角と並進量を離散化してスコア表を作る。次に、ある回転角について、特徴点対応の全体集合から取り出した各特徴点対応ペアに対してエピポーラ幾何により並進量を計算する。そして、その並進量のスコアをエピポーラ幾何に対する誤差で評価して、該スコア表に集計する。これにより、該回転角に対する並進量のスコア分布ができる。これを各回転角で繰り返して、カメラ姿勢空間のスコア分布を作る。このスコア分布の中で、スコアが高い回転角と並進量の組を有力なカメラ姿勢仮説として選択する。【００１６】＜システム構成＞
図１にしたがい、本発明におけるカメラ姿勢推定処理の一実施形態を説明する。
特徴点追跡手段１０１は、画像１および画像２の間で特徴点の対応づけを行う。カメラ姿勢スコア分布生成手段１０２は、カメラ回転角を所定の範囲で離散化し、その各離散値に対して、特徴点追跡手段１０１で得られた特徴点対応集合を用いて並進量を求め、該並進量のスコアを集計してカメラ姿勢のスコア分布を生成する。カメラ姿勢スコア分布記憶手段１０３は、カメラ姿勢スコア分布生成手段１０２が生成したカメラ姿勢スコア分布を記憶する。カメラ姿勢仮説選択手段１０４は、該カメラ姿勢スコア分布に基づいて、スコアの高いカメラ姿勢を仮説として選択して出力する。特徴点誤対応検出手段１０５は、特徴点対応がカメラ姿勢仮説に整合するかどうかを調べ、整合しない特徴点対応をアウトライアと判定する。【００１７】＜特徴点追跡手段＞
次に、特徴点追跡手段１０１の処理を詳しく述べる。
特徴点追跡手段１０１は、画像１の特徴点ｑ１ｉに対応する特徴点ｑ２ｊを画像２から見つける。デジタル画像では、画素の位置は一般に整数値をとるが、ｑ１ｉおよびｑ２ｊの位置は実数値でもよい。一般に、実数値の方がカメラの推定姿勢の精度はよくなる。
画像間で特徴点の対応づけを行うには、背景技術で述べた方法と同様にして、ｑ１ｉの近傍領域と一致度の高い領域を画像２から探索し、その中心をｑ２ｊとすればよい。領域の一致度は、従来からよく用いられている画素値の差の二乗和や画素値の正規化相関などの関数を用いて評価する。本発明では、評価関数の具体形は問わないが、一致度が大きいほど評価値が高くなる関数を用いる。たとえば、正規化相関はこの性質を満たす。【００１８】  従来の特徴対応づけ方法の多くは１対１の特徴点対応を与えるが、本発明の特徴点追跡手段１０１では１対多の対応も許す。すなわち、ｑ１ｉに対して、複数のｑ２ｊが対応してもよい。このためには、ｑ１ｉの近傍領域と一致度の高い領域を画像２から探索する際に、最も一致度の高い領域だけでなく、ある条件Ｃを満たす領域を採用すればよい。
条件Ｃとしては、たとえば、「一致度が最大値をとる領域」を用いると、特徴点対応は１対１になる。あるいは、「一致度が極大値をとる領域」を用いると、特徴点対応は１対多になる。あるいは、また、「一致度が所定の閾値より大きい領域」を用いても、特徴点対応は１対多になる。ただし、この場合は、特徴点対応の個数が増えすぎる可能性がある。その場合は、「一致度が極大値をとり、かつ、所定の閾値より大きい領域」を用いれば、特徴点対応が増えすぎるのを防ぐことができる。【００１９】  以上をふまえて、特徴点の対応関係を表す関数ｇ（ｑ１ｉ，ｑ２ｊ）を数１のように定義する。υは、前記評価関数によるｑ１ｉとｑ２ｊの一致度である。このｇ（ｑ１ｉ，ｑ２ｊ）は、カメラ姿勢スコア分布生成手段１０２で用いられる。
【数１】
2008224641.tif 000003
【００２０】＜カメラ姿勢スコア分布生成手段＞
次に、カメラ姿勢スコア分布生成手段１０２を詳しく説明する。
上述のように、カメラの回転角を離散化し、各離散値に対して並進量を求め、スコア分布を作る。画像１から抽出された特徴点集合をＱ１とし、カメラ姿勢を（ψ，τ）とする。ψは３次元の回転角、τは並進量である。カメラ姿勢（ψ，τ）におけるスコアＧ（ψ，τ）を次のように定義する。ただし、Ｑ２（ｑ１ｉ）はｑ１ｉに対応する画像２の特徴点の集合であり、数１でｑ１ｉに対して０でない値をとるｑ２ｊの集合として求められる。
【数２】
2008224641.tif 000004
Ｆ（ψ，τ，ｑ１ｉ，ｑ２ｊ，ｑ１ｋ，ｑ２ｌ）は、特徴点対応ペア（ｑ１ｉ，ｑ２ｊ），（ｑ１ｋ，ｑ２ｌ）に対するスコア関数であり、次のように定義される。
【数３】
2008224641.tif 000005
Ｄ（ψ，τ，ｑ１ｉ，ｑ２ｊ）は、カメラ姿勢（ψ，τ）のもとで、ｑ１ｉとｑ２ｊがエピポーラ幾何を満たせば大きな値をとり、満たさなければ小さな値をとる関数である。その具体例は後で述べる。【００２１】  数３によれば、Ｆは、特徴点対応の一致度が高く、かつ、特徴点対応ペアがエピポーラ幾何を満たす場合に大きな値をとる。また、数２によれば、ＧはＦの集計になっているので、特徴点対応の一致度が高く、かつ、エピポーラ幾何を満たす特徴点対応ペアが多いカメラ姿勢（ψ，τ）ほどＧが大きくなる。そこで、各（ψ，τ）についてＧを計算してカメラ姿勢空間にスコア分布を生成し、その中でスコアの高いカメラ姿勢を解候補とみなせば、有力なカメラ姿勢仮説を網羅的に得ることができる。【００２２】  次に、スコア分布Ｇの具体的な計算方法を説明する。まず、カメラ姿勢を離散化する。画像１と画像２の間のカメラ回転角ψが存在しうる範囲を決め、その範囲で離散化する。離散化した角度をψｍと表す。カメラ並進量τは長さ１に正規化されるので、その範囲で離散化する。離散化した並進量をτｎと表す。
このようにして得た離散化されたカメラ姿勢（ψｍ，τｎ）のそれぞれに対して、次の手順でＧ（ψｍ，τｎ）を求める。まず、回転ψｍを与える。そして、ψｍのもとで、特徴点対応ペア（ｑ１ｉ，ｑ２ｊ）と（ｑ１ｋ，ｑ２ｌ）に対して、並進量τを求める。これは、次のように、エピポーラ幾何に基づいて解くことができる。
図２は、エピポーラ幾何を示す説明図である。図２において、ｑ１ｉとｑ２ｊは対応づけがとれているとする。Ｃ１は画像１を撮影したカメラの中心、Ｃ２は画像２を撮影したカメラの中心である。ｑ１ｉおよびｑ２ｊは、それぞれ、３次元点Ｐが画像１および画像２に写った点なので、カメラ中心Ｃ１とｑ１ｉ結ぶ線分、カメラ中心Ｃ２とｑ２ｊを結ぶ線分、および、Ｃ１とＣ２を結ぶ線分は１つの平面上にある。この平面をエピ極面と呼ぶ。Ｃ１とＣ２を結ぶ線分は、カメラの並進量τに相当する。以上のことから、次のエピポーラ幾何の関係式が成り立つ。
【数４】
2008224641.tif 000006
ただし、Ｒｍは回転角ψｍに対する回転行列である。また、Ｔはベクトルの転値を表す。ｑ１ｉ×Ｒｍｑ２ｊはエピ極面の法線ベクトルである。数４は、τがエピ極面の法線ベクトルに垂直であることを意味している。【００２３】  回転角は与えられているので、数４はτに関する線形方程式になる。特徴点対応が２組あれば、それらによって決まる２枚のエピ極面の法線ベクトルそれぞれに垂直なベクトルとして、τを求めることができる。特徴点対応（ｑ１ｋ，ｑ２ｌ）および（ｑ１ｋ，ｑ２ｌ）によるエピ極面の法線ベクトルをそれぞれｎｉｊ、ｎｋｌとすると、τは次のように計算される。ただし、上述のように、画像だけから実寸法を知ることはできないので、τの大きさは１に正規化する。
【数５】
2008224641.tif 000007
【００２４】  このようにして得られたτを離散化してτｎとする。そして、Ｄ（ψｍ，τ，ｑ１ｉ，ｑ２ｊ）を、たとえば、次のように定義する。
【数６】
2008224641.tif 000008
これは、エピポーラ幾何を満たすτｎだけが有効なスコアをもち、それ以外はスコアが０であることを意味する。なお、これ以外にも、Ｄとして、ガウス関数のように、τｎで最大値をとり、τｎから離れるにつれて急激に減少する関数を採用してもよい。【００２５】  以上により、回転角ψｍと特徴点対応ペア（ｑ１ｋ，ｑ２ｌ）、（ｑ１ｋ，ｑ２ｌ）に対して数３のＦがτの関数として計算できる。数２にしたがって、各特徴点対応ペアについてＦを集計することで、ψｍに対するＧを計算できる。さらに、すべてのψｍに対して同様の計算を行えば、Ｇを求めることができる。この計算を行うために、次に述べるように、カメラ姿勢スコア分布記憶手段１０３に記憶した表を用いる。【００２６】＜カメラ姿勢スコア分布記憶手段＞
次に、カメラ姿勢スコア分布記憶手段１０３の構成を説明する。カメラ姿勢スコア分布記憶手段１０３は、並進量スコア表と回転角スコア表を記憶する。
まず、並進量スコア表について説明する。カメラの並進量は３次元ベクトルであるが、長さを１に正規化するため、実際の自由度は２となり、２個の変数α，βで表される。そこで、並進量スコア表を２次元の表で構成する。図３に並進量スコア表の構成の一例を示す。並進量スコア表の各セルは、離散化したα，βに対応する。
α，βとしては、たとえば、極座標の２つ角度を用いればよい。並進量τ＝（ｔｘ，ｔｙ，ｔｚ）からα，βへの変換は次のように計算される。
【数７】
2008224641.tif 000009
一般には、αの範囲は−１８０°から１８０°、βの範囲は−９０°から９０°である。所定の間隔でα，βを離散化し、並進量スコア表の各セルにα，βの離散値を対応させる。【００２７】  数２のＧは、カメラ姿勢スコア分布生成手段１０２により、並進量スコア表を用いて次のように計算する。まず、回転角ψｍにおいて、各特徴点対応ペアについて数５を用いてτを求める。その離散値τｎについて数３および数６にしたがってＦの値を計算し、その値を並進量スコア表のτｎに対応するセルに加算する。本来は、この処理をτの全離散値に対して行うことでＦが決まる。ところが、数６によりＤはτｎ以外では０となるので、加算してもＦは変わらない。このため、実際の処理はτｎ１個についてだけ行えばよい。全特徴点対応ペアについてこの処理を行って、ψｍを与えたときのＧを得る。そして、各ψｍに対して上述の処理を繰り返してＧを得る。
ここで重要なのは、τの全離散値ではなく、τｎについてだけＦを計算する点である。τの全離散値でＦを逐一計算すると、回転角と並進量を合わせた５次元空間の全域をたどることになる。一方、τｎについてだけＦを計算すると、３次元の回転角空間だけをたどることになり、計算量は大幅に減る。なお、上述のように、Ｄとして数６の関数ではなく、τｎを中心に急激に減衰する関数を用いる場合は、τｎから遠い点でＤを０と近似して、τｎ近傍の数個のτについてだけＦを計算すれば、やはり計算量は少なくて済む。【００２８】  スコア分布Ｇを完全に得るには、各ψｍに対して別々の並進量スコア表を用意する必要がある。しかし、このようにすると、大量の記憶領域を消費する。これに対処するために、次のようにＧを簡略化してもよい。すなわち、並進量スコア表は１個だけ用意し、１つのψｍについてＧの計算を行ったあと、最大のスコアを与えるτとそのスコアだけを後述の回転角スコア表に記憶する。そして、並進量スコア表のセル値をすべて０にリセットし、他のψｍに対して、同じ処理を繰り返す。【００２９】  次に、回転角スコア表について説明する。図４に回転角スコア表の構成の一例を示す。回転角ψは３次元であるので、回転角スコア表は３次元の表として作る。計算機でのデータ構造としては、たとえば、３次元配列を用いればよい。回転角スコア表の３つの軸は、それぞれ、回転角の３つの角度に対応する。たとえば、回転角としてロール・ピッチ・ヨーを採用する場合は、各軸はロール角、ピッチ角、ヨー角を表す。ψは離散化されているので、回転角スコア表の各セルは各ψｍに対応する。
各ψｍに並進量スコア表を用意する場合は、回転角スコア表の各セルに並進量スコア表へのポインタを格納する。一方、上述のように並進量スコア表を１個だけ用意する場合は、回転角スコア表の各セルには最大のスコアを与えるτとそのスコアを格納する。【００３０】＜処理の流れ＞
次に、図５にしたがって、本発明のカメラ姿勢推定の処理手順を説明する。このフローチャートは、特徴点追跡手段１０１で特徴点対応集合が得られたとして、カメラ姿勢スコア分布生成手段１０２の処理手順の一例を示したものである。
まず、ステップＳ１１において、回転角の離散値を１つ決める。これは、回転角の探索範囲の中から離散値を１つずつ順に取り出せばよい。上述のように、並進量スコア表を１個しか用いない場合は、ここで並進量スコア表の各セルの値を０に初期化する。次に、ステップＳ１２において、特徴点対応集合の中から、異なる２組の特徴点対応を取り出し、特徴点対応ペアを作る。次に、ステップＳ１３において、その特徴点対応ペアに対して、数５を適用してカメラの並進量を計算する。次に、ステップＳ１４において、ステップＳ１３で求めた並進量のスコアを数６より計算して、並進量スコア表に加算する。次に、ステップＳ１５において、すべての特徴点対応ペアを処理したかを調べる。すべて処理されていなければ、ステップＳ１２に戻る。特徴点対応ペアがすべて処理されていれば、ステップＳ１６に移る。ステップＳ１６では、並進量スコア表の中から最大スコアを与える並進量を見つけ、そのスコアと並進量を回転角スコア表に記憶する。次に、ステップＳ１７において、探索範囲内のすべての離散回転角について処理を行ったか調べる。すべての回転角について処理されていれば終了する。そうでなければ、ステップＳ１１に戻る。
なお、各ψｍに対して並進量スコア表を用意する場合は、ステップＳ１６は行わなくてもよい。【００３１】＜カメラ姿勢仮説の選択＞
次に、カメラ姿勢仮説選択手段１０４において、スコア分布Ｇ（ψ，τ）から有力なカメラ姿勢仮説を選択する方法を説明する。
まず、各ψｍ対して並進量スコア表を用意する場合は、全並進量スコア表から所定の条件を満たすカメラ姿勢を選べばよい。ここで、所定の条件とは、たとえば、スコアが閾値を超えた、スコアが極大である、などである。
次に、並進量スコア表を１個だけ用いる場合は、回転角スコア表の各セルに記憶した並進量とスコアを取り出して、上述の所定条件を満たすものを選べばよい。【００３２】  なお、本発明のカメラ姿勢推定システムは、有力な仮説を求めるだけで、解を唯一に決めるわけではない。他の情報を用いて、仮説をさらに選別することは可能であるが、本発明の範囲ではない。
また、本発明のカメラ姿勢推定システムで得られるカメラ姿勢は離散化されているため、その精度は必ずしも十分ではない。適当な初期値から出発して精密な解を求める手法は従来から開発されており、それを併用すれば精密な解を得ることができる。本発明のカメラ姿勢推定システムは、そのための初期値を求めるものと解釈することもできる。【００３３】＜アウトライアの判定＞
次に、特徴点誤対応検出手段１０５によるアウトライアの判定方法について説明する。
まず、スコア分布はアウトライアに大きな影響をうけないことを説明する。正しい回転角と正しい特徴点対応を与えた場合、数５で求めた並進量は、誤差により多少ずれるが、真値に近くなる。そのため、数２において多数の正しい特徴点対応でＦを集計すると、並進量スコア表は真値の付近で極大値をもつ。一方、アウトライアは多くの場合ランダムに発生するため、アウトライアから数５で計算した並進量もほぼランダムに分布する。したがって、その並進量は、並進量スコア表のランダムなセルに加算される。このため、アウトライア比率が極端に高くない限り、アウトライアから得られた並進量が特定のセルに集中して加算されることはなく、スコア分布に大きな影響は与えない。【００３４】  次に、カメラ姿勢（ψ，τ）が得られた場合に、それに対するアウトライアを判定する方法を説明する。カメラ姿勢（ψ，τ）に対するアウトライアは、ほとんどの場合、エピポーラ幾何を満たさない。そのため、その（ψ，τ）と特徴点対応に対して数４の左辺を計算しても、その値は０にならない。そこで、数４の左辺の値が所定の閾値より大きい特徴点対応をアウトライアと判定すればよい。
【産業上の利用可能性】
【００３５】  本発明は、例えば、単眼カメラによる自律移動体の３次元姿勢推定に用いることができる。また、カメラ姿勢の推定により物体形状の３次元復元が可能になるので、移動ロボットによる３次元地図構築や３次元物体モデル生成などにも適用することができる。
【図面の簡単な説明】
【００３６】
【図１】本発明におけるカメラ姿勢推定システムの一実施形態を示すブロック図である。
【図２】画像特徴点とカメラ姿勢の関係を説明する図である。
【図３】並進量スコア表の構成の一例を説明する図である。
【図４】回転角スコア表の構成の一例を説明する図である。
【図５】カメラ姿勢仮説の生成手順の一例を示すフローチャートである。
【図１】
2008224641.tif 000010
【図２】
2008224641.tif 000011
【図３】
2008224641.tif 000012
【図４】
2008224641.tif 000013
【図５】
2008224641.tif 000014