(57)【要約】（例えばコンピュータ・ビジョン・システムで使用される）６つの自由度で特徴付けられるカメラ・ポーズを決定する方法および装置が開示される。一実施形態では、カメラでキャプチャされたイメージが受領され、潜在的ポーズに関する少なくとも２つの制約が、カメラに対するイメージの既知の関係に従って実施され、それによって潜在的ポーズが、残りの２つの自由度に制限される。次いで、少なくとも１つの潜在的ポーズが、その残りの２つの自由度に従って決定される。
2008506283.tif 000002
【特許請求の範囲】
【請求項１】
イメージ取込み装置の潜在的ポーズを決定する方法において、前記潜在的ポーズが６つの自由度を有する方法であって、
前記イメージ取込み装置で取り込んだイメージを受け取るステップであって、前記イメージが少なくとも第１の既知のワールド・ポイント、第２の既知のワールド・ポイント、および第３の既知のワールド・ポイントのイメージを含み、および
前記イメージ取込み装置に対する前記イメージの既知の関係に従って前記潜在的ポーズに対して制約を実施するステップと、
第１光線、第２光線、および第３光線によって与えられる制約を実施するステップであって、前記第１光線、前記第２光線、および前記第３光線がそれぞれ、前記イメージ取込み装置から、それぞれ前記第１の既知のワールド・ポイント、前記第２の既知のワールド・ポイント、および前記第３の既知のワールド・ポイントに投射し、および
前記制約に従って少なくとも１つの潜在的ポーズを決定するステップと
を含むこと
を含む方法。
【請求項２】
前記実施するステップが、
前記潜在的ポーズが残りの２つの自由度に制限されるように前記第１光線および前記第２光線で与えられる制約をまず実施するステップ、および
前記第３ポイント、前記第３光線、および前記残りの２つの自由度に従って前記潜在的ポーズをさらに制限するステップと
を含む請求項１に記載の方法。
【請求項３】
前記残りの２つの自由度が、
前記第３の既知のワールド・ポイントの変換を表す第１自由度と、
前記イメージ取込み装置を前記第３既知のワールド・ポイントに投射する第３光線の少なくとも１つの可能な位置を表す第２自由度と
を含む請求項２に記載の方法。
【請求項４】
前記第１自由度が、前記イメージ取込み装置に対する前記第３の既知のワールド・ポイントの位置を円で画定されるエリア内に制限し、前記第２自由度が、前記イメージ取込み装置に対する前記第３光線の位置を線織４次曲面で画定されるエリア内に制限し、前記円と前記線織４次曲面が複数の交点を有する請求項３に記載の方法。
【請求項５】
前記複数の交点のそれぞれが、前記第１ワールド・ポイント、前記第２ワールド・ポイント、および前記第３ワールド・ポイントに対する前記イメージ取込み装置の潜在的ポーズを特定する請求項４に記載の方法。
【請求項６】
前記イメージ取込み装置が非中心投射イメージ形成モデルに準拠する請求項１に記載の方法。
【請求項７】
前記イメージ取込み装置が、マルチカメラ・リグ、カタディオプトリック・カメラ、ジオプトリック・カメラ、またはマルチレンズ・カメラのうちの少なくとも１つを含む請求項６に記載の方法。
【請求項８】
前記イメージ取込み装置が、異なる位置に配置された複数のカメラを含み、前記複数のカメラの相対的向きが既知である請求項６に記載の方法。
【請求項９】
複数の命令が格納されたコンピュータ可読媒体であって、前記複数の命令が、プロセッサで実行されたときに、イメージ取込み装置の潜在的ポーズを決定する方法の工程をプロセッサに実行させる命令を含み、前記潜在的ポーズが６つの自由度を有し、前記方法が、
前記イメージ取込み装置で取り込んだイメージを受け取るステップであって、前記イメージが少なくとも第１の既知のワールド・ポイント、第２の既知のワールド・ポイント、および第３の既知のワールド・ポイントのイメージを含み、および
前記イメージ取込み装置に対する前記イメージの既知の関係に従って前記潜在的ポーズに対して制約を実施することであって、
第１光線、第２光線、および第３光線によって与えられる制約を実施するステップであって、前記第１光線、前記第２光線、および前記第３光線がそれぞれ、前記イメージ取込み装置から、それぞれ前記第１の既知のワールド・ポイント、前記第２の既知のワールド・ポイント、および前記第３の既知のワールド・ポイントに投射し、および
前記制約に従って少なくとも１つの潜在的ポーズを決定するステップと
を含む
コンピュータ可読媒体。
【請求項１０】
イメージ取込み装置の潜在的ポーズを決定する装置において、前記潜在的ポーズが６つの自由度を有し、
前記イメージ取込み装置で取り込んだイメージを受け取る手段であって、前記イメージが少なくとも第１の既知のワールド・ポイント、第２の既知のワールド・ポイント、および第３の既知のワールド・ポイントのイメージを含む手段と、
前記イメージ取込み装置に対する前記イメージの既知の関係に従って前記潜在的ポーズに対して制約を実施する手段であって、
第１光線、第２光線、および第３光線によって与えられる制約を実施する手段であって、前記第１光線、前記第２光線、および前記第３光線がそれぞれ、前記イメージ取込み装置から、それぞれ前記第１の既知のワールド・ポイント、前記第２の既知のワールド・ポイント、および前記第３の既知のワールド・ポイントに投射する手段と、
前記制約に従って少なくとも１つの潜在的ポーズを決定する手段と
を含む
装置。
【発明の詳細な説明】
【背景技術】
【０００１】
関連出願への相互参照
本願は、参照により本明細書にその全体が組み込まれる２００４年６月２２日出願の米国仮特許出願第６０／５８１，８６８号の特典を主張するものである。
【０００２】
政府資金援助への参照
本発明は、米国陸軍によって与えられた交付番号ＤＡＡＤ１９−０１−２−００１２の下で政府援助を伴ってなされたものである。政府は、本発明における一定の権利を有する。
【０００３】
様々な応用例におけるコンピュータ・ビジョン・システムの有用性が広く認められている。コンピュータ・ビジョン・システムでの基本的な課題は、ワールド内の既知の地点の１つまたは複数のイメージが与えられたとして、イメージ取込み装置（例えばビデオカメラ）のポーズを決定することである。
【０００４】
ポーズ推定の例示的応用例は車両位置確認である。車載カメラからの環境的特徴を追跡することにより、車両位置の変化を推定し、ナビゲーション、追跡、またはその他の目的でこの情報を使用することが可能である。しかし、周知のポーズ推定アルゴリズムに基づくカメラ・ベースの車両位置確認のための現在の技法は、車両上にある複数のカメラを最適に使用していない。ポーズ推定のための既存の方法は単一パースペクティブ・カメラ・モデルを想定しているからである。この制限の結果として、その場しのぎのポーズ推定方法が使用される。例えば、各車載カメラについて別個にポーズが推定され、その後で別々のポーズ推定が組み合わせされることがある。したがって、そのような方法は一般に、利用可能な情報を最良に使用していない。
【０００５】
別の例として、較正パースペクティブ・カメラのポーズを決定する周知の一方法は、カメラの可能なポーズを最大４対の解に制限するために（ただし、各対からの有効な解はせいぜい１つである）、ワールド内の３つの既知の地点のイメージを実装する。これらの解は通常、周知の「３点パースペクティブ・ポーズ問題」に従って生成される。この手法を多くの状況で首尾よく適用することができるが、現状では、その有用性は、特定のカメラ幾何形状および視点に限定される。したがって、この手法は、コンピュータ・ビジョン・システムでますます一般的なツールとなっている、より一般化された幾何形状（例えば、中央パースペクティブ・モデルに準拠せず、または単一視点に対応しない幾何形状）を有するカメラモデルにはあまり適用可能ではない。
【非特許文献１】Ｂｏｏｋ  ＩＩＩ  ｏｆ  Ｅｕｃｌｉｄ’ｓ  Ｅｌｅｍｅｎｔｓ
【非特許文献２】Ｄ．Ｎｉｓｔｅｒ、Ａｎ  Ｅｆｆｉｃｉｅｎｔ  Ｓｏｌｕｔｉｏｎ  ｔｏ  ｔｈｅ  Ｆｉｖｅ−Ｐｏｉｎｔ  Ｒｅｌａｔｉｖｅ  Ｐｏｓｅ  Ｐｒｏｂｌｅｍ、ＩＥＥＥ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ、Ｖｏｌｕｍｅ  ２、ｐｐ．１９５−２０２、２００３
【発明の開示】
【発明が解決しようとする課題】
【０００６】
したがって、実質的にモデルに無関係なカメラ・ポーズを決定する方法および装置が当技術分野で求められている。
【課題を解決するための手段】
【０００７】
（例えばコンピュータ・ビジョン・システムで使用される）６つの自由度で特徴付けられるカメラ・ポーズを決定する方法および装置が開示される。一実施形態では、カメラでキャプチャされたイメージが受領され、潜在的ポーズに関する少なくとも２つの制約が、カメラに対するイメージの既知の関係に従って実施され、それによって潜在的ポーズが、残りの２つの自由度に制限される。次いで、少なくとも１つの潜在的ポーズが、その残りの２つの自由度に従って決定される。
【０００８】
上述の本発明の特徴を詳細に理解できる方式の結果、添付の図面にその一部が図示される実施形態を参照することにより、上記で簡潔に要約される本発明のより具体的な説明を得ることができる。しかし、添付の図面は本発明の典型的な実施形態を示すに過ぎず、したがって、本発明は同様に効果的な他の実施形態を認めることができるので、添付の図面を本発明の範囲の制限と見なすべきでないことに留意されたい。
【発明を実施するための最良の形態】
【０００９】
本発明は、（例えばコンピュータ・ビジョン・システムのための）カメラ・ポーズを決定する方法および装置を開示する。カメラモデルまたはイメージ・キャプチャ幾何形状に関する仮定に依拠する、ポーズを決定する従来の方法とは異なり、本発明の方法および装置は、カメラモデルまたは幾何形状の如何に関わらず機能し、したがって実質上任意の種類のカメラのポーズを決定するように実装することができる。例えば、曲面ミラー（例えばカタディオプトリック系またはジオプトリック系）と共に動作するカメラ、マルチカメラ・リグ（例えばステレオ・カメラヘッド）、または互いにしっかりと取り付けられた複数の個々の検出素子を備える複合カメラはすべて、本発明の適用から利益を受けることのできる潜在的な構成である。さらに、ある時間から別の時間にカメラ位置を関係付けるポーズ変換が既知である限り、経時的に移動する１つまたは複数の従来型カメラを単一の一般化カメラとして扱うことができる。それぞれの場合に、本明細書で説明される方法および装置によって課される唯一の要件は、イメージ位置に対応する光線間の空間的関係が既知であることである。言い換えれば、本発明は、分類されない特殊ケースとして較正カメラ構成を含む較正一般化カメラに対処する。
【００１０】
図１は、本発明による、カメラ・ポーズを決定する方法１００の一実施形態を示す流れ図である。方法１００は、実質上任意のカメラまたはイメージ取込み装置のポーズを決定するように実装することができる。本発明の一実施形態では、決定されるポーズは、６つの自由度、すなわち回転についての３つの自由度と並進に関する３つの自由度を有すると理解される。
【００１１】
方法１００はステップ１０２で初期化され、ステップ１０４に進み、ステップ１０４では、方法１００は、少なくとも３つの既知のワールド・ポイントを含むイメージ（例えば、一続きのシーンイメージの個々のフレーム）を受け取る。一実施形態では、イメージが、何らかの任意ではあるが周知の方式でライト・フィールドまたはプレノプティック関数をサンプリングする一般化カメラから受領される。例えば、曲面ミラー（例えばカタディオプトリック系またはジオプトリック系）と共に動作するカメラ、マルチカメラ・リグ、または互いにしっかりと取り付けられた複数の個々の検出素子を備える複合カメラのうちの少なくとも１つからイメージを受け取ることができる。ワールド・ポイントは、受領されたイメージ内にキャプチャされ、現実世界での３次元位置が既知である現実世界の任意の地点を含む。
【００１２】
ステップ１０６では、方法１００は、既知のワールド・ポイントのうちの３つに投射される、イメージ取込み装置の座標系内の地点の光線を識別する。一実施形態では、これらの光線を直ちに導出することができるようにイメージ取込み装置が較正される。
【００１３】
図２は、３つの既知のワールド・ポイント２０４１〜２０４３（以後「ワールド・ポイント２０４」と総称する）のイメージ２０２１〜２０２３（以後「イメージ２０２」と総称する）を含む例示的イメージ２００を示す略図である。図示するように、既知のワールド・ポイント２０４の各イメージ２０２および対応するワールド・ポイント２０４自体は、共通光線２０６１〜２０６３（以後「光線２０６」と総称する）沿いにある。一般に、イメージ２００をキャプチャしたイメージ取込み装置のポーズは、すべての光線２０６がそれらの対応するワールド・ポイント２０４と出会うように３つの光線２０６の固定変換を求めることによって推定することができる。この固定変換を求める方法の一実施形態を以下でより詳細に説明する。
【００１４】
図１に戻ると、３つの光線（例えば光線２０６）を識別した後、方法１００はステップ１０８に進み、３つの光線のうちの２つ（例えば第１光線および第２光線）によって与えられる制約を実施する。単一光線の制約（すなわち、光線が既知のワールド・ポイントを通過すべきであることを規定する制約）の実施により、カメラのポーズの２つの自由度が除かれる。したがって、２つの光線の制約を実施することにより、イメージ取込み装置のポーズが、６つの自由度から２つの自由度に制限される。したがって、ワールドに対する３つの光線の組全体のポーズは、ずっと狭い１組の可能性に制限される。
【００１５】
次いで、方法１００はステップ１１０に進み、実施された制約がこれら残りの２つの自由度に対して有する効果を求める。これら残りの２つの自由度のうちの一方は、第３光線に対応する既知のワールド・ポイントの変換の点から考慮することができる。残りの２つの自由度の２番目は、第３光線の可能な位置の点から考慮することができる。
【００１６】
ステップ１１２では、方法１００は、残りの２つの自由度の知識を使用して、ワールド・ポイントの座標系と光線の座標系との間の可能な変換を求める。これらの変換は、イメージ取込み装置のポーズに関する可能な解を表す。次いで方法１００はステップ１１４で終了する。
【００１７】
図３は、例示的な１対の光線（例えば、第１光線３００１および第２光線３００２。以後「光線３００」と総称する）と、光線の制約の実施が残りの２つの自由度のうちの１番目（したがって、その１対の光線３００を含む１組の３つの光線の潜在的ポーズ）に対して有する効果を示す略図である。３つのワールド・ポイント、すなわち第１ワールド・ポイント３０２１、第２ワールド・ポイント３０２２、および第３ワールド・ポイント３０２３（以後「ワールド・ポイント３０２」と総称する）が既知である。第１および第２光線３００は、それぞれ第１および第２ワールド・ポイント３０２１、３０２２と出会う。
【００１８】
第１および第２ワールド・ポイント３０２１、３０２２は、第１ワールド・ポイントと第２ワールド・ポイントの両方を通過する、空間内の固有軸３０４を定義する。したがって、ワールド・ポイント３０２の構成は、第１および第２光線３００によって与えられる制約に違反することなく、軸３０４の周りに回転することができる（実際、これは、図１に関連して上記で議論した残りの２つの自由度の１番目を示す）。そのような回転は、第３ワールド・ポイント３０２３が、軸３０４に対してほぼ垂直な平面内の円３０６をトレースすることを可能にする。一実施形態では、円３０６の中心点Ｃは軸３０４沿いにある。したがって、ワールド座標系が第１および第２ワールド・ポイント３０２１、３０２２、および円３０６を含むと見なすことができる。したがって、（上記で議論した）第１の残りの自由度は、第３ワールド・ポイント３０２３がイメージ取込み装置に対する円をトレースすることを可能にする。
【００１９】
図４は、第１および第２光線の制約の実施が光線３００の対を含む１組の３つの光線の潜在的ポーズに対して有する効果をさらに示す略図である。具体的には、図４は、第１および第２光線３００によって与えられる制約の実施が図１に関連して上記で議論した残りの２つの自由度の２番目に対して有する効果を示す。
【００２０】
図４に示すように、与えられたイメージから投射される光線はすべてが平行ではないと仮定する。したがって、別個の方向を有する２つの光線を、その後でその制約が実施される第１および第２光線３００として選ぶことができる。第１および第２光線３００は、固有の共通垂直方向と、両方の光線３００と交わる共通垂直方向の固有垂直軸４００とを有する。
【００２１】
第１および第２光線３００によって課された制約を満たしながら、円筒（円筒の端部が円４０４１および４０４２で画定される。以後、円４０４１および４０４２を「円４００」と呼ぶ）の周りに垂直軸４００を回転させる剛体運動が存在する。垂直軸４００に加えて、円４００で画定された円筒は、それぞれの円４００の円周上にある第１および第２ワールド・ポイント３０２１、３０２２も含む。垂直軸４００の回転運動は、垂直軸４００に垂直なすべての平面に同様に影響を及ぼす。したがって、垂直軸に沿った正射影を考慮する場合（射影方向を矢印４０２で示す）、円筒の断面を図５に示すように表すことができる。
【００２２】
図５は、図４の垂直軸４００に沿った正射影を示す図である（例えば円筒５００の断面図）。図示するように、第１および第２光線３００の相対位置が、その間の弧５０４を画定する。弧５０４を張り、第１および第２光線３００で画定される角度（上述の垂直軸４００が通過する円筒５００上の地点５０２と接する角度）は、サイズθを有する。Ｂｏｏｋ  ＩＩＩ  ｏｆ  Ｅｕｃｌｉｄ’ｓ  Ｅｌｅｍｅｎｔｓで述べられているように、円内の同一の弧（例えば弧５０４）を張るすべての内接角は等しい。したがって、弧５０４を張り、円筒５００の円形断面で内接するすべての角はサイズθを有する。
【００２３】
図４に戻ると、第３光線（図示せず）に対する垂直軸４００の回転運動の効果を代数表現を使用して求めることができる。一実施形態では、既知のワールド・ポイント３０２を垂直軸４００の円運動でトレースされる有効な位置のうちの１つにそれぞれ写像する変換のファミリが求められる。したがって、変換は、既知のワールド・ポイント３０２を光線３００の座標系に写像する。以下でより詳細に議論するように、第３光線上に写像することのできるワールド・ポイントは、垂直軸４００が回転するときに第３光線によってトレースされる線織４次曲面上にある。
【００２４】
図６は、既知のワールド・ポイントをそれ自体の座標系から対応する光線の座標系に写像する方法６００の一実施形態を示す流れ図である。方法６００はステップ６０２で初期化され、ステップ６０４に進み、ステップ６０４では、方法６００は、第１および第２光線３００および既知のワールド・ポイント３０２を開始位置に変換する。これにより、後続の解析が単純になる。
【００２５】
図７Ａおよび７Ｂは、第１および第２光線３００ならびに既知のワールド・ポイント３０２の変換の正射図を示すグラフである。図７Ａおよび７Ｂでは、第１光線３００１がｙ軸と一致し、垂直軸４００がｚ軸と一致する。したがって、原点７００は、第１光線３００１が垂直軸４００と交わる位置である。
【００２６】
次いで、第１および第２ワールド・ポイント３０２１、３０２２が特定の位置に配置されるように既知のワールド・ポイント３０２が変換される。一実施形態では、第１ワールド・ポイント３０２１は原点源７００と一致する。第１ワールド・ポイント３０２１の周りの回転の結果、第２ワールド・ポイント３０２２が第２光線３００２のｘｚ平面とｚ平面の間の交線上にある。通常、第２ワールド・ポイント３０２２について、そのような可能な位置が２つある。一実施形態では、ｘ≧０となるように第２ワールド・ポイント３０２２についての位置が選ばれる。これにより、第１および第２ワールド・ポイント３０２１、３０２２によって画定される軸の周りの回転に対するワールド・ポイント３０２についての座標系が決定される。一実施形態では、この回転は任意に選ばれる。
【００２７】
図６に戻ると、第１および第２光線３００および既知のワールド・ポイント３０２が、その開始位置（例えば図７Ａおよび７Ｂに示すもの）に変換された後、方法６００はステップ６０６に進み、第１および第２ワールド・ポイント３０２をその対応する光線３００上に変換する。一実施形態では、この変換はｘｙ平面内で行われ、光線３００を固定したままでワールド・ポイント３０２に適用される。
【００２８】
図８は、例えば方法６００のステップ６０６に従って、対応する光線（例えば光線３００）上に変換された後の、ワールド・ポイント（例えばワールド・ポイント３０２）の構成の一実施形態を示す略図である。図示する構成は、第１および第２ワールド・ポイント３０２１、３０２２をそれぞれ第１および第２光線３００１および３００２上に配置するｘｙ平面内の並進および回転の結果として得られる１つの可能な構成である。このとき、上記で議論した図４の円４０４で画定される円筒の周りの垂直軸（例えば垂直軸４００）の回転運動は、確立された一致を維持する。この位置合せを達成するために、第２光線３００２の投射が、以下の直線方程式を有するように求められる。
【００２９】
ｙ＝ｓｘ  （式１）
ただしｓは投射の傾きである。
一実施形態では、変換は第１ワールド・ポイント３０２１をｙ軸上に維持しなければならない。したがって、第１ワールド・ポイント３０２１の位置はｙ＝ｍであると求められる。さらに、投射８００の直線方程式が以下のようになるように、第１および第２ワールド・ポイント３０２１、３０２２を通る軸の投射線８００が配置される。
【００３０】
ｙ＝ｋｘ＋ｍ  （式２）
ただしｋは投射８００の傾きである。
さらに、変換は、第２ワールド・ポイント３０２２を第２光線３００２上に維持する。したがって、第２光線３００２の投射と投射８００とは第２ワールド・ポイント３０２２の投射（ｂ，ｃ）で交わり、投射（ｂ，ｃ）は、以下のようなｘ座標ｂを有する。
【００３１】
ｍ＝（ｓ−ｋ）ｂ  （式３）
図８から明らかなように、有効な変換は、以下の式に従ってワールド・ポイント３０２のｘｙ座標（ｘ，ｙ）をｘｙ座標（ｘ’，ｙ’）に写像する。
【００３２】
【数１】
2008506283.tif 000003
ただしＤは、第１および第２ワールド・ポイント３０２１、３０２２間の投射距離である。
ｕ≡Ｄ／ｂ  （式５）
のようにスカラｕを定義し、ピタゴラスの定理により、（ｋ２＋１）ｂ２＝Ｄ２であることに注目することによって式４を書き直すことができる。
ｕ２＝１＋ｋ２  （式６）
したがって、式２、３、および５により、式４の変換を以下のように書き直すことができる。
【００３３】
【数２】
2008506283.tif 000004
したがって、有効な変換の１次元ファミリは、式６の制約下でｕおよびｋによってパラメータ表示される。
図６に戻ると、第１および第２ワールド・ポイント３０２１、３０２２が対応する光線３００上に適切に変換された後、方法６００はステップ６０８に進み、図４の円４０４で画定される円筒の周りの垂直軸（例えば垂直軸４００）の回転運動によって第３光線上に写像されたワールド・ポイントのファミリを求める。方法６００はステップ６１０で終了する。
一実施形態では、式７の変換を、ワールド・ポイントの均質座標Ｘ＝［ｘ  ｙ  ｚ  １］Ｔを新しい均質座標Ｘ’に写像する完全３次元変換として解釈することにより、第３光線上に写像されるワールド・ポイントのファミリを求めることができ、以下が得られる。
【００３４】
【数３】
2008506283.tif 000005
変換後の点Ｘ’は、ＬＴＸ’＝０、すなわち
ａ１＋ｋａ２＋ｕａ３＝０  （式９）
である場合にのみ、平面Ｌ＝［ｌ１  ｌ２  ｌ３  ｌ４］Ｔ上にある。
ただし、
ａ１≡ｘｌ１＋ｙｌ２＋ｓＤＩ２  （式１０）
ａ２≡ｘｌ２−ｙｌ１−ＤＩ２  （式１１）
ａ３≡ｚｌ３＋ｌ４  （式１２）
第３光線は、２つの平面ＬおよびＬ’で表すことができ、Ｌ’を用いて同様にａ１’、ａ２’、ａ３’を定義した場合、以下を得る。
ａ１＋ｋａ２＋ｕａ３＝０  （式９）
ａ１’＋ｋａ２’＋ｕａ３’＝０  （式１３）
ｋおよびｕをそれぞれ取り除くと、
ｕ（ａ２’ａ３−ａ２ａ３’）＝（ａ２ａ１’−ａ２’ａ１）  （式１４）
−ｋ（ａ２’ａ３−ａ２ａ３’）＝（ａ３ａ１’−ａ３’ａ１）  （式１５）
式１５および１６を式６に挿入すると、
（ａ２ａ１’−ａ２’ａ１）２＝（ａ２’ａ３−ａ２ａ３’）２＋（ａ３ａ１’−ａ３’ａ１）２  （式１６）
【００３５】
これは、次数により、４次曲面の定義であることが容易にわかる。４次曲面は直線の集合であるので、線織４次曲面である。
【００３６】
図９は、第２の残りの自由度に関連する回転運動によって第３光線でトレースすることのできる例示的線織４次曲面９００を示すグラフである。一実施形態では、ｘｙ平面に平行である線織４次曲面９００のすべての区間がリマソンであり、リマソンの頂点が、ねじれた立方体を形成し、その一部が線織４次曲面９００についての自己交差の曲線である。
【００３７】
ここで、円（例えば図３の円３０６）を含む平面についての式を挿入して、その平面内の４次曲線を得ることができる。円は、４次曲線と最大８個の交点を有し、これらの交点は、第３光線沿いにあるワールド・ポイントのファミリに対応する。
【００３８】
図１１Ａ〜１１Ｂは、例えば上記で議論した第１および第２光線の制約を実施することによって得られる、円１１０２（例えば図３に従って議論したときに導出されたもの）と線織４次曲面１１０４（例えば図９に従って議論したときに導出されたもの）との交差を示すグラフである。図示するように、複数の交差１１０６１〜１１０６８（以後「交差１１０６」と総称する）が、円１１０２と線織４次曲面１１０４との間に存在する。具体的には、図１１Ａは、頂面１１０８でのそのような４つの交差１１０６を示し、図１１Ｂは底面１１１０でのそのような４つの交差１１０６を示す。以下でさらに詳細に議論するように、円１１０２と線織４次曲面１１０４との間の合計最大８個の交差１１０６は、ワールド・ポイントの座標系と対応する光線の座標系との間の変換に関する最大８個の可能な解を表す。これらの各変換は、ワールド・ポイントに対するイメージ取込み装置に関するポーズを確立する。
【００３９】
図１０は、以下でさらに議論する、ワールド・ポイントの座標系と対応する光線の座標系との間で変換する方法１０００の一実施形態を示す流れ図である。方法１０００はステップ１００２で初期化され、ステップ１００４に進み、ステップ１００４では、方法１０００は３つの光線（例えば光線３００）をその正準位置に整列させる。
【００４０】
一実施形態では、光線が、光線上の点ｐ１、ｐ２、およびｐ３と、単位方向ベクトルｄ１、ｄ２、およびｄ３によって表される。ｄ１はｙ軸に平行にされる。第１および第２光線の共通垂直方向は、
ｄ４≡（ｄ１×ｄ２）／｜ｄ１×ｄ２｜  （式１７）
これはｚ軸に平行となるべき方向である。
次いで、ｘ軸に平行となる方向は、以下のように定義される。
ｄ５≡ｄ１×ｄ４  （式１８）
式１７および式１８の条件は、光線が以下の回転で回転する場合に満たされる。
Ｒ１≡［ｄ５  ｄ１  ｄ４］Ｔ  （式１９）
式１で定義される第２光線の傾きｓは、
ｓ≡（ｄ１Ｔｄ２）／（ｄ５Ｔｄ２）  （式２０）
さらに、第１光線が垂直軸と交わる点が原点に配置され、それによってその点が以下のように与えられる。
【００４１】
Ｐ４≡Ｐ１＋αｄ１  （式２１）
ただし、α≡（ｄ１−ｓｄ５）Ｔ（ｐ２−ｐ１）  （式２２）
したがって、光線をその開始位置に移動させる変換は、
【数４】
2008506283.tif 000006
ただし、この変換が光線に対して常に適用されたと仮定することができる。
ステップ１００６では、方法１０００は、ワールド・ポイント（例えばワールド・ポイント３０２）をその正準位置に整列させる。一実施形態では、ワールド・ポイントはｑ１、ｑ２、およびｑ３として与えられる。ワールド・ポイントをその開始位置に移動させるために、まず、第２光線がそのときにｚ座標ｅがｚ座標ｐ２であるｚ平面内に完全にあることを観察することができる。
さらに、以下を観察することができる。
【００４２】
【数５】
2008506283.tif 000007
やはり、
ｄ６≡［Ｄ  ０  ｅ］Ｔ／｜ｑ１−ｑ２｜  （式２５）
は、原点から、第２ワールド・ポイントを配置すべき位置に向かう方向の単位ベクトルである。変換前は、この方向は、
ｄ７≡（ｑ１−ｑ２）／｜ｑ１−ｑ２｜  （式２６）
ｄ８≡［０  １  ０］Ｔ  （式２７）
および
ｄ９≡（ｄ７×（ｑ３−ｑ１））／｜ｄ７×（ｑ３−ｑ１）｜  （式２８）
も定義される。ただしｄ８およびｄ９は、それぞれｄ６およびｄ７に対して垂直な単位ベクトルである。したがって、所望の回転は、
Ｒ２≡［ｄ６  ｄ８  （ｄ６×ｄ８）］［ｄ７  ｄ９  ｄ７×ｄ９］Ｔ  （式２９）
となり、点に適用される変換は、
【数６】
2008506283.tif 000008
ただし、一実施形態では、変換Ｈ２が既に点に適用されていると仮定する。
【００４３】
ステップ１００８では、方法１０００は、第３光線を表す２つの平面方程式の係数ＬおよびＬ’を計算する。一実施形態では、係数ＬおよびＬ’は、ｄ３に対して垂直な２つの別個の法線ベクトルｎおよびｎ’を見つけることによって計算される。一実施形態では、ｎは、２つのベクトル積ｄ３×［１  ０  ０］およびｄ３×［０  １  ０］Ｔの最大の大きさのベクトルとして選ばれる。次いで、ｎ’は、ｎ’≡ｄ３×ｎとなるように選ばれ、平面ベクトルは、
Ｌ≡［ｎＴ−ｎＴｐ３］Ｔ  （式３１）
および
Ｌ≡［ｎ’Ｔ−ｎ’Ｔｐ３］Ｔ  （式３２）
となる。
【００４４】
次いで、方法１０００はステップ１０１０に進み、その根が円と線織４次曲面の交差に対応する８次多項式の係数を計算する。一実施形態では、ｚの８次多項式は、式１６の４次表現からｘおよびｙを取り除くことによって導出される。ワールド・ポイントがステップ１００６に従って整列された後、円は、以下によって定義される平面内に位置する。
［ｘ  ｙ  ｚ］ｄ６＝ｑ３Ｔｄ６  （式３３）
これにより、
ｘ＝ｋ１  （式３４）
が得られる。ただし、
【数７】
2008506283.tif 000009
さらに、円は、平面と球
ｘ２＋ｙ２＋ｚ２＝｜ｑ３｜２  （式３６）
の間の交差である。
式３４を式３６に代入した場合、以下が得られる。
ｙ２＝ｋ２  （式３７）
ただし、ｋ２＝｜ｑ３｜２−ｚ２−ｋ１２  （式３８）
式３４を式１０および１１に次々に代入することにより、以下が得られる。
ａ１＝ｙｋ３＋ｋ４  （式３９）
ａ２＝ｙｋ５＋ｋ６  （式４０）
ａ３＝ｋ７  （式４１）
ａ１’＝ｙｋ８＋ｋ９  （式４２）
ａ２’＝ｙｋ１０＋ｋ１１  （式４３）
ａ３’＝ｋ１２  （式４４）
ただし、
ｋ３≡ｌ２  （式４５）
ｋ４≡ｌ１ｋ１＋ｓＤｌ２  （式４６）
ｋ５≡−ｌ１  （式４７）
ｋ６≡ｌ２ｋ１−Ｄｌ２  （式４８）
ｋ７≡ｚｌ３＋ｌ４  （式４９）
ｋ８≡ｌ’２  （式５０）
ｋ９≡ｌ’１ｋ１＋ｓＤｌ’２  （式５１）
ｋ１０≡−ｌ’１  （式５２）
ｋ１１≡ｌ’２ｋ１−Ｄｌ’２  （式５３）
ｋ１２≡ｚｌ’３＋ｌ’４  （式５４）
式３９から４４および式３８を適用すると、式１７の表現は以下のように拡張される。
ａ２ａ’１−ａ’２ａ１＝ｋ１３ｙ＋ｋ１４  （式５５）
ａ’２ａ３−ａ２ａ’３＝ｋ１５ｙ＋ｋ１６  （式５６）
ａ３ａ’１−ａ’３ａ’１＝ｋ１７ｙ＋ｋ１８  （式５７）
ただし、
ｋ１３≡ｋ５ｋ９＋ｋ６ｋ８−ｋ３ｋ１１−ｋ４ｋ１０  （式５８）
ｋ１４≡ｋ６ｋ９−ｋ４ｋ１１＋ｋ２（ｋ５ｋ８−ｋ３ｋ１０）  （式５９）
ｋ１５≡ｋ７ｋ１０−ｋ５ｋ１２  （式６０）
ｋ１６≡ｋ７ｋ１１−ｋ６ｋ１２  （式６１）
ｋ１７≡ｋ７ｋ８−ｋ３ｋ１２  （式６２）
ｋ１８≡ｋ７ｋ９−ｋ４ｋ１２  （式６３）
式５５〜５７の右辺を２乗し、式１６に代入し、再び式３８を適用すると、
ｋ１９＝ｋ２０ｙ  （式６４）
ただし
ｋ１９≡ｋ２（ｋ１３２−ｋ１５２−ｋ１７２）＋ｋ１４２−ｋ１６２−ｋ１８２  （式６５）
ｋ２０≡２（ｋ１５ｋ１６＋ｋ１７ｋ１８−ｋ１３ｋ１４  （式６６）
式６４を２乗し、再び式３８を適用すると、以下が得られる。
ｋ２１＝０  （式６７）
ただし、
ｋ２１≡ｋ１９２−ｋ２ｋ２０２  （式６８）
【００４５】
これは、その根が最大８個の解に対応するｚの８次多項式である。
ステップ１０１０で８次多項式が確立された後、方法１０００はステップ１０１２に進み、８次多項式の根を抽出する。一実施形態では、根は、随伴行列を固有値分解することによって抽出される。
一実施形態では、８次多項式がまず正規化され、その結果以下のように書くことができる。
ｚ８＋β７ｚ７＋β６ｚ６＋．．．＋β０  （式６９）
次いで、根が８×８随伴行列の固有値として見つけられる。
【００４６】
【数８】
2008506283.tif 000010
代替実施形態では、例えばＤ．ＮｉｓｔｅｒがＡｎ  Ｅｆｆｉｃｉｅｎｔ  Ｓｏｌｕｔｉｏｎ  ｔｏ  ｔｈｅ  Ｆｉｖｅ−Ｐｏｉｎｔ  Ｒｅｌａｔｉｖｅ  Ｐｏｓｅ  Ｐｒｏｂｌｅｍ、ＩＥＥＥ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ、Ｖｏｌｕｍｅ  ２、ｐｐ．１９５−２０２、２００３で論じているように、８次多項式の根をステュルム列として見つけることができる。
【００４７】
８次多項式の根が抽出された後、方法１０００はステップ１０１４に進み、８次多項式の各根で後退置換し、ワールド・ポイント座標系と光線座標系との間の変換のための解を得る。一実施形態では、これは、ｚ、ｘについての各解を式３４で計算し、ｙについての各解を式６４で計算することによって実施される。次いで、ＥＱＮ１４および１５をそれぞれ使用して、ｕおよびｋを計算することができる。次いで、式７で定義される変換が一意的に求められ、それにＨ３と符号を付ける。各解について、円上の正しい点の周りに第３ワールド・ポイントｑ３を回転させる変換Ｈ４も見つかる。
【００４８】
一実施形態では、ｄ１０が以下のように定義される。
ｄ１０＝（ｄ６×［ｘ  ｙ  ｚ］Ｔ）／｜ｄ６×［ｘ  ｙ  ｚ］Ｔ｜  （式７１）
次いで、所望の回転は、
Ｒ４≡［ｄ６  ｄ１０  （ｄ６×ｄ１０）］［ｄ６  ｄ８  （ｄ６×ｄ８）］Ｔ  （式７２）
また、ワールド・ポイントに適用される変換は、
【数９】
2008506283.tif 000011
次いで、ワールド・ポイントの座標系から光線の座標系への全変換は、
Ｈ＝Ｈ１−１Ｈ３Ｈ４Ｈ２  （式７４）
【００４９】
式７４で実施される変換が、８次多項式の各根について求められ、それによって最大８個の変換が得られる。これらの８個の変換は、ワールド・ポイントの座標系から光線の座標系への変換についての潜在的解を表す。したがって、潜在的解を、イメージ取込み装置のポーズを求める仮定−試験アーキテクチャ内で試験するための仮定として扱うことができる。
【００５０】
次いで方法１０００はステップ１０１６で終了する。
図１２は、汎用コンピューティング装置１２００を使用して実装されるカメラ・ポーズ推定方法の高レベルブロック図である。一実施形態では、汎用コンピューティング装置１２００はプロセッサ１２０２、メモリ１２０４、カメラ・ポーズ推定モジュール１２０５、およびディスプレイ、キーボード、マウス、モデムなどの様々な入出力（Ｉ／Ｏ）装置１２０６を備えることができる。一実施形態では、少なくとも１つのＩ／Ｏ装置は記憶装置（例えばディスク・ドライブ、光ディスク・ドライブ、フロッピィ・ディスク・ドライブ）である。通信チャネルを介してプロセッサに結合された物理的装置またはサブシステムとしてカメラ・ポーズ推定モジュール１２０５を実装できることを理解されたい。
【００５１】
あるいは、カメラ・ポーズ推定モジュール１２０５は、１つまたは複数のソフトウェア・アプリケーション（さらには、ソフトウェアと、例えば特定用途向け集積回路（ＡＳＩＣ）を用いたハードウェアとの組合せ）で表すことができる。その場合ソフトウェアは、記憶媒体（例えばＩ／Ｏ装置１２０６）からロードされ、汎用コンピューティング装置１２００のメモリ１２０４内でプロセッサ１２０２によって操作される。したがって、一実施形態では、上記の図を参照しながら本明細書で説明したカメラまたは他のイメージ取込み装置のポーズを求めるカメラ・ポーズ推定モジュール１２０５を、コンピュータ可読媒体またはキャリア（例えばＲＡＭ、磁気または光ドライブまたはディスケットなど）上に格納することができる。
【００５２】
したがって、本発明は、コンピュータ・ビジョン・システムの分野での著しい進歩を表す。イメージ取込み装置およびイメージ取込み装置でキャプチャされたイメージについて知られている限られた量の情報に基づいて、イメージ取込み装置のポーズを仮定することを可能にする方法および装置が提供される。この方法および装置は、イメージ取込み装置のモデルまたは幾何形状とは無関係に機能し、したがって実質上任意の種類のイメージ取込み装置のポーズを決定するように実装することができる。
【００５３】
上記は本発明の実施形態を対象とするものであるが、本発明の基本的範囲から逸脱することなく、本発明の別の実施形態を考案することができ、本発明の範囲は、添付の特許請求の範囲によって決定される。
【図面の簡単な説明】
【００５４】
【図１】本発明による、カメラ・ポーズを決定する方法の一実施形態を示す流れ図である。
【図２】３つの既知のワールド・ポイントのイメージを含む例示的イメージを示す略図である。
【図３】例示的な１対の光線（および光線の制約の実施が残りの２つの自由度の１番目に対して有する効果）を示す略図である。
【図４】第１および第２光線の制約の実施が光線の対を含む１組の３つの光線の潜在的ポーズに対して有する効果をさらに示す略図である。
【図５】図４の垂直軸に沿った正射影を示す図である。
【図６】既知のワールド・ポイントをそれ自体の座標系から対応する光線の座標系に写像する方法の一実施形態を示す流れ図である。
【図７】第１および第２光線ならびに既知のワールド・ポイントの変換の正射図を示すグラフである。
【図８】対応する光線上に変換された後のワールド・ポイントの構成の一実施形態を示す略図である。
【図９】第２の残りの自由度に関連する回転運動によって第３光線でトレースすることのできる例示的線織４次曲面を示すグラフである。
【図１０】上記でさらに詳細に議論した、ワールド・ポイントの座標系と対応する光線の座標系との間で変換する方法の一実施形態を示す流れ図である。
【図１１】例えば第１および第２光線の制約を実施することによって得られる、円と線織４次曲面との交差を示すグラフである。
【図１２】汎用コンピューティング装置を使用して実装されるカメラ・ポーズ推定方法の高レベルブロック図である。
【図１】
2008506283.tif 000012
【図２】
2008506283.tif 000013
【図３】
2008506283.tif 000014
【図４】
2008506283.tif 000015
【図５】
2008506283.tif 000016
【図６】
2008506283.tif 000017
【図７】
2008506283.tif 000018
【図８】
2008506283.tif 000019
【図９】
2008506283.tif 000020
【図１０】
2008506283.tif 000021
【図１１】
2008506283.tif 000022
【図１２】
2008506283.tif 000023
【国際調査報告】
2008506283.tif 000024