環境における3次元3Dオブジェクトの3D姿勢を求めるための方法であって、カメラによって前記環境から捕捉した画像から特徴を抽出することと、前記特徴を前記環境の3Dモデルにマッチングすることであって、対応を求める、マッチングすることと、前記対応を用いて、前記画像のカメラ基準系および前記環境のワールド基準系を対応する中間カメラ基準系および対応する中間ワールド基準系に変換することと、前記中間カメラ基準系および前記中間ワールド基準系に幾何学的制約を適用することであって、制約付き中間ワールド基準系および制約付きワールド基準系を取得する、適用することと、前記制約付き中間ワールド基準系および前記制約付きワールド基準系のパラメーターから前記3D姿勢を求めることを含み、これらのステップは、プロセッサにおいて実行される、方法。前記環境は、屋外都市場面であり、前記3D姿勢は、ジオロケーションのために用いられる、請求項1に記載の方法。前記姿勢は、自動ナビゲーションのために用いられる、請求項1に記載の方法。前記環境は、屋内工場設定であり、前記3D姿勢は、ロボットアームを用いて小さな工業用部品を掴み取るのに用いられる、請求項1に記載の方法。前記幾何学的制約は、共線性制約および共平面性制約である、請求項1に記載の方法。前記特徴は、2つの点および1つの線を含む、請求項1に記載の方法。前記特徴は、1つの点および2つの線を含む、請求項1に記載の方法。前記パラメーターは、前記姿勢の3つの回転パラメーターおよび3つの並進パラメーターを含む、請求項1に記載の方法。前記姿勢は、4次多項式を用いて求められる、請求項1に記載の方法。前記姿勢は、8次多項式を用いて求められる、請求項1に記載の方法。前記中間カメラ基準系において、前記カメラの中心は、座標C0、0、-1にあり、第1の線の投影光線は、Z軸上の線に対応し、第2の線の投影光線は、XZ平面上の線に対応する、請求項1に記載の方法。前記姿勢は、ランダムサンプルコンセンサスの枠組みを用いて推定される、請求項1に記載の方法。したがって、そのようなジオロケーション用途のためのカメラに基づく解法を提供することが望ましい。本発明の実施の形態は、最小数の画像特徴を用いてコンピュータービジョンにおける幾何学的問題を解くための方法を提供する。本方法は、幾何学的共線性制約および幾何学的共平面性制約を用いて、4つの最小幾何学問題の解をもたらす。中間基準系を用いて姿勢推定に関与する方程式を単純化する。本明細書において定義されるとき、基準系は、3D座標系である。制約の従来の適用では、64次多項式の解がもたらされる。本発明者らの中間基準系を用いると、問題は、4次多項式および8次多項式まで低減される。最小姿勢推定のために、点および線を用いて、最後の2つの欠けている項を与える。姿勢推定は、ワールド内の既知の特徴点および線並びに画像に対するそれらの投影を所与として、カメラの姿勢を回復する問題を指す。点特徴および線特徴を用いる4つの最小構成、すなわち、3点、2点1線、1点2線、および3線が存在する。点または線のいずれかのみに依拠する第1の構成および最後の構成のための解法が既知である。しかしながら、実際にはより一般的である混合構成は、これまで解決されていない。本発明者らは、同じ手法を用いて4つ全ての構成を解くことができる汎用技法を開発することが実際に可能であること、およびその解法が4次多項式または8次多項式のいずれかの根を求めることを伴うことを示している。解決の鍵は、適切な中間基準系の選択、および姿勢推定問題を解く際の共線性制約および共平面性制約の使用である。画像シーケンス、および無線受信が乏しいGPS不良都市環境の粗い3Dモデルを用いたジオローカライゼーションのための強力な適用も提供する。多くの現実世界の用途において、3点または3線の対応を求めることは、必ずしも可能でない。本発明は、これらの特徴を混合させるという選択を与え、それによって、以前には可能でなかった事例における解決を可能にすることによって、この状況を改善する。共線性制約および共平面性制約を用いた本発明者らの問題定式化、並びに中間基準系を選択する技法は、都市環境におけるジオロケーションおよびオブジェクト検出等の多くの用途で非常に有用である。図6は、本発明の実施の形態による、環境602におけるオブジェクトの3D姿勢641を求めるための方法を示している。姿勢は、並進Tにおいて3自由度、および回転Rにおいて3自由度を有する。カメラ603によって環境から捕捉された画像601内の点および線から、特徴が抽出される610。これらの特徴は、環境の3Dモデル609にマッチングされ、対応611が求められる。対応を用いて、画像のカメラ基準系および環境のワールド基準系を、対応する中間カメラ基準系および中間ワールド基準系621に変換する。本明細書において定義されるとき、基準系は、3D座標系である。幾何学的制約が中間基準系に適用される630。次に、制約付き基準系のパラメーターを用いて、3D姿勢が求められる640。図7は、環境、たとえば、屋外都市場面の3Dモデルを構築するために実行することができるステップを示している。たとえば、Google3DWarehouseからテクスチャのない粗い3Dモデルが捕捉される。代替的に、粗いモデルは、車両ナビゲーティング上に搭載されるカメラによって環境を通じて捕捉された画像から構築される。テクスチャを、たとえば、GoogleおよびSketchUpを用いて付加することができる702。テクスチャ化されたモデルに人を投入することができ703、投影マッピングを用いて道路標識を付加して、詳細な3Dモデルを生成することもできる704。構築中、都市環境のいくつかの点および線700を画像から抽出することができる。次に、本明細書において説明される方法を用いて、これらの点および線を用いて様々なオブジェクトの姿勢を求める。そして、この詳細な3Dモデルを、歩行者、車両、交通信号、および道路標識の自動検出を実行するジオロケーション、強化車両ナビゲーションサービスに用いることができる。代替的に、本方法は、自動化された製造中に、工業用部品を掴むための姿勢推定、および屋内場面でのロボットナビゲーションのために最小数の点特徴および線特徴が用いられるロボット設定において、用いることができる。たとえば、環境は、屋内工場設定であり、3D姿勢は、ロボットアームを用いて小さな工業用部品を掴み取るために用いられる。上記の方法ステップの全てを、当該技術分野において既知のメモリおよび入力/出力インターフェースに接続されたプロセッサ600において実行することができる。これより、本方法をより詳細に説明する。共線性および共平面性図1および図2に示すように、本発明者らの方法は、2つの幾何学的制約、すなわち、共線性および共平面性のみを用いて、4つ全ての最小構成を解決する。共線性制約は、2D-3D対応611から生じる。一般的なイメージングセットアップにおいて、画像内の全てのピクセルが3D投影光線に対応し、対応する3D点がこの光線上にある。ここで、x、y、およびzは、3D座標である。本明細書において説明される最小解は、2D画像特徴に連結される投影光線CD1を用い、環境内の関連付けられた3D点P1は、基準系内に表されるとき、共線である。図2において、2D線の端点に連結された2つの投影光線CD1およびCD2、並びに2つの点L1およびL2によって表される関連付けられる3D線は、全て共平面である。図1において、投影光線CD1および点P1は、同じ中間基準系内に表されるとき、光線上にある。本発明者らの目標は、姿勢R、Tのもとで、点P1が光線CD1上にある該姿勢R、Tを見つけることであり、ここで、Rは回転であり、Tは並進である。これらの点を以下の行列にスタックする。この行列を共線性行列と呼ぶ。第1の共線性制約は、上記の行列のサイズ3×3を有する任意の部分行列の行列式が消滅するように強制する。換言すれば、一度に1つの行を除去することによって、4つの制約を取得する。上記の行列から4つの式を取得するが、2つのみが独立しており、このため有用である。第2の共平面性幾何学的制約は、2D-3D線対応から生じる。図2に示すように、点C、D1、D2、P1、およびP2は、同じ基準系内に表されるとき、単一平面上にある。換言すれば、正しい姿勢[R、T]の場合、単一の2D-3D線対応から2つの制約を取得する。すなわち、4つ組C、D1、D2、[R、T]L1およびC、D1、D2、[R、T]L2が、それぞれ共平面である。4つ組C、D1、D2、[R、T]L1の共平面性制約は、以下の行列の行列式が消滅するように強制する。同様に、他方の4つ組C、D1、D2、[R、T]L2も共平面性制約を与える。したがって、全ての2D-3D線対応は、線上の2つの点から2つの式をもたらす。本発明者らの目標は、3D特徴点および線の双方が共線性制約および共平面性制約を満たす6つのパラメーター3つがR用で3つがT用を求めることである。このため、4つの可能な最小構成を有する3点、2点1線、1点2線、および3線。基準系図3に示すように、点および線が存在するカメラ基準系およびワールド基準系は、それぞれC0およびW0によって表される。本発明者らの目標は、ワールド基準系W0とカメラ基準系C0との間の変換を求めることである。最初にC0およびW0をそれぞれ中間カメラ基準系C1および中間ワールド基準系W1に変換する。次に、これらの中間ワールド基準系W1と中間カメラ基準系C1との間の姿勢を求める。これは、カメラ基準系とワールド基準系との間の姿勢を求めるのに用いることができる。これらの中間基準系を用いる解法によって、結果としての多項式の次数が大幅に低減される。すなわち、従来の6426次多項式から、本発明の4次多項式および8次多項式に低減される。変換Rw2c、Tw2cを求める。これは、ワールド基準系およびカメラ基準系内の3Dの点および線を表す。共線性制約および共平面性制約を直接適用した結果、12個の変数9個のRij、3個のTiを伴う6つの一次方程式となる。これらの変数を解くために、さらなる式を必要とする。これらの式は、6つの二次直交性制約とすることができる。そのような系の解は、最終的に、結果として64個の解を有する6426次多項式となる。そのような解を求めることは、いくつかのコンピュータービジョンアプリケーションにとって実現可能でない場合がある。本発明者らの主な目標は、この困難を克服する方法を提供することである。これをなすために、まずカメラ基準系C0およびワールド基準系W0の双方を、それぞれ中間カメラ基準系C1および中間ワールド基準系W1に変換する。この変換後、本発明者らの目標は、中間基準系間の姿勢R、Tを見つけることである。中間カメラ基準系C1および中間ワールド基準系W1を、結果としての多項式が、最も低い可能な次数となるように選択する。2つの最小構成のための姿勢推定手順を説明する。他の2つの構成は、類似した形で取り扱うことができる。最小解2点1線2つの2D-3D点および1つの2D-3D線の対応からの姿勢推定手順を提供する。点の2D座標から、較正を用いて対応する投影光線を求めることができる。2D線の構成において、画像内の線の端点の対応する投影光線を求めることができる。以下で、画像上の点特徴および線特徴の関連付けられる3D投影光線のみを考察する。図4A~図4Dは、カメラ基準系C0およびワールド基準系W0、並びに2点1線構成からの姿勢推定における中間カメラ基準系C1および中間ワールド基準系W1を示している。変換前および変換後のカメラ基準系がそれぞれ図4Aおよび図4Cに示されている。同様に、変換前および変換後のワールド基準系がそれぞれ図4Bおよび図4Dに示されている。中間カメラ基準系C1図4Aおよび図4Bにおいて、それぞれ、カメラ基準系C0およびワールド基準系W0におけるカメラ投影光線2Dの点および線に関連付けられるおよび3D特徴点および線を示している。カメラの中心は、C0であり、2つの2D点に対応する投影光線は、それらの方向ベクトルd1→およびd2→によって与えられ、2D線に対応する投影光線は、方向ベクトルd3→およびd4→によって与えられるここで、→の表記は、かっこの前の記号の上に→が付され、ベクトルを表すことを意味している。中間カメラ基準系C1において、常に、2つの点中心および光線上の点を用いてカメラの投影光線を表す。2つの2D点に対応する投影光線は、CD1およびCD2であり、線は、CD3およびCD4である。3つ組C、D3、D4によって形成される平面は、解釈平面と呼ばれる。以下の条件を満たす中間カメラ基準系C1を選択する。a.カメラ中心が座標C0、0、-1にある、b.線L3L4に対応する投影光線のうちの一方CD3が、D3=0、0、0となるようにZ軸上にある、およびc.線L3L4に対応する他方の投影光線CD4が、D4がX軸上にあるようにXZ平面上にある。構築的な偏角を用いて、2点1線に対応する投影光線の任意のセットの変換が可能である。P0およびPがそれぞれ基準系C0およびC内の任意の点の座標を表すとする。この表記に従って、点D3およびD4は、代数的微分を用いてC0およびC1で表される。C0とC1との間の姿勢Rc1、Tc1は、3つ組C0、D3、D4をC、D3、D4に変換するものによって与えられる。中間ワールド基準系W1中間ワールド基準系は、以下のように記述することができる。任意の2つの3D点PおよびQ間のユークリッド距離をdP、Qによって表されるものとする。W1における3D線上の2つの3D点および1つの3D点は、下式となる。ここで、X3およびY3は、三角法を用いて求めることができる。ワールド基準系W0と中間ワールド基準系W1との間の姿勢Rw1、Tw1は、3つ組P01、P02、L03をP1、P2、P3に変換するものによって与えられる。簡潔にするために、姿勢推定手順において、以下の表記を用いる。中間カメラ基準系C1と中間ワールド基準系W1との間の姿勢推定第1のステップは、全ての利用可能な共線性制約および共平面性制約を行列内にスタックすることである。この場合、3D点P1およびP2にそれぞれ対応する3つ組C、D1、P1およびC、D2、P2のための2つの共線性行列を有する。式1に示すように、これらの2つの共線性行列は、4つの方程式を与える。加えて、3D線L3L4に対応する4つ組C、D3、D4、L3およびC、D3、D4、L4からの2つの共平面性方程式を有する。部分行列の行列式からの制約をスタックした後、線形系AX=Bを得る。ここで、A、X、およびBは、下式である。行列Aは、既知の変数を有し、階数6である。線形系内に8つの変数が存在するので、2つのベクトルが広がる部分空間内に解を得ることができる。a.X=ul1vl2wここで、u、v、およびwは、サイズ8×1の既知のベクトルである。次に、回転行列からの直交性制約を用いて、未知の変数l1およびl2を推定する。回転変数を伴う2つの直交性制約を書くことができる。これらの回転変数をl1およびl2の関数として代入し、上記の連立二次方程式を解いた後、l1、l2について4つの解を得て、このためR11、R21、R31、R22、R23について4つの解を得る。回転行列内の5つの要素は、直交性制約を用いて、他の要素を一意に確定する。このため、2点1線構成によって、姿勢R、Tの合計4つの解がもたらされる。1点2線このセクションでは、1つの2D-3D点、および2つの2D-3D線対応からの姿勢推定手順を説明する。中間カメラ基準系W1図5Aおよび図5Bは、それぞれ、カメラ基準系C0およびワールド基準系W0におけるカメラ投影光線2Dの点および線に関連付けられるおよび3D特徴点および線を示している。カメラ基準系C0において、カメラの中心は、C0にあり、2D点に対応する投影光線は、それらの方向ベクトルd1→によって与えられ、2つの2D線に対応する投影光線は、方向ベクトルの対d2→、d3→およびd4→、d5→によって与えられる。中間カメラ基準系C1において、2D点に対応する光線は、CD1であり、2つの線に連結される光線は、それぞれ対CD2、CD3、およびCD3、CD4である。以下の条件を満たすことによって、C1を選択する。a.カメラ中心が、座標C0、0、-1にある、b.2つの解釈平面の交差線からの投影光線CD3が、D3=0、0、0となるようにZ軸上にある、およびc.光線CD2が、XZ平面上にあり、ただしD2が、X軸上にある。上記の構成と同様に、そのような変換が構築によって可能であることを証明する。解釈平面C0、d2→、d3→の単位法線ベクトルは、n1→=d2→×d→およびd2→=d4→×d→によって与えられる。2つの平面の交差線の方向ベクトルは、d12→=d1→×d2→として求めることができる。C0における方向ベクトルd2→、d12→およびd4→は、それぞれ投影光線CD2、CD3、およびCD4に対応する。代数的変換を用いて、中間基準系への変換前および変換後の点D2およびD3は下式となる。カメラ基準系C0と中間カメラ基準系C1との間の変換は、3つ組C0、D02、D03をC、D2、D3に投影するものによって与えられる。中間ワールド基準系W1中間ワールド基準系W1は、単一の3D点P1が原点0、0、0にあるように選択される。ワールド基準系W0と中間ワールド基準系W1との間の変換は、P01をP1に並進させる。簡潔にするために、C0およびW0におけるいくつかの点について、以下の表記を用いる。中間カメラ基準系C1と中間ワールド基準系W1との間の姿勢推定1点2線対応を用いた姿勢推定を説明した。3つ組C、D1、P1からの2つの共線性方程式と、4つ組C、D2、D3、L2およびC、D2、D3、L3からの4つの共平面性方程式とをスタックする。以下の線形系、すなわち、AX=Bを構築する。ここで、A、X、およびBは、下式となる。線形系AX=Bにおいて、第1の行および第2の行は、3つ組C、D1、P1について、式1の共線性制約を用いて得られる。第3行、第4行、第5行、および第6行は、それぞれ4つ組C、D2、D3、L2、C、D2、D3、L3、C、D3、D4、L4、およびC、D3、D4、L5について、式2の共平面性制約を用いて得られる。行列Mは、既知の変数を有し、階数6である。線形系内に9つの変数が存在するので、2つのベクトルが広がる部分空間内に以下に示すように解を得ることができる。すなわち、X=ul1vl2wl3yであり、ここで、u、v、w、およびyは、サイズ9×1の既知のベクトルであり、l1、l2、およびl3は、未知の変数である。3つの直交性制約は、回転変数R11、R12、R13、R21、R22、およびR23を含んでいるX内の個々の要素は、l1、l2、およびl3の関数として表される。上記の方程式の効率的で安定した解を得るために、グレブナー基底法を用いて構築された自動ソルバを用いて、l1、l2、l3の8つの異なる解を得る。結果として、これによって姿勢R、Tの8つの解が生成された。退化構成および他のシナリオ3D特徴間で、3D点が3D線上にある場合、構成は、退化している。座標変換の同じ着想および共線性制約および共平面性制約の使用を用いて、3点および3線を解くことが可能である。