(57)【要約】【課題】リアルタイム・ビジュアル・オドメトリの方法およびシステムを提供する。【解決手段】リアルタイム・ビジュアル・オドメトリの方法は、第１の時間に、或る位置の第１の３次元画像を取得するステップと、第１の時間より後の第２の時間に、前記の位置の第２の３次元画像を取得するステップと、第１および第２の３次元画像のそれぞれから、１または複数の特徴およびその記述子を抽出するステップとを含む。次に、第１の３次元画像からの１または複数の特徴が、第２の３次元画像からの１または複数の特徴と対応付けられる。この方法は更に、ランダム・サンプル・コンセンサス（ＲＡＮＳＡＣ）プロセスおよび独特の反復する改善技術を使用して、第１の時間から第２の時間までにおける第１の３次元画像と第２の３次元画像との間の回転および平行移動の変化を決定するステップを含む。【選択図】図１
2009266224.tif 000002
【特許請求の範囲】
【請求項１】
リアルタイム・ビジュアル・オドメトリの方法であって、
第１の時間に、或る位置の第１の３次元画像を取得するステップと、
前記第１の時間よりも後の第２の時間に、前記位置の第２の３次元画像を取得するステップと、
前記第１の３次元画像および前記第２の３次元画像のそれぞれから、１または複数の特徴とその記述子とを抽出するステップと、
前記第１の３次元画像からの１または複数の特徴と、前記第２の３次元画像からの１または複数の特徴とを対応付けるステップと、
ランダム・サンプル・コンセンサス（ＲＡＮＳＡＣ）プロセスおよび反復改善技術を使用して、前記第１の時間から前記第２の時間への、前記第１の３次元画像と前記第２の３次元画像との間の回転の変化および平行移動の変化を求めるステップと
を備え、
前記反復改善技術が、
第１組のインライアと、前記ＲＡＮＳＡＣプロセスから出力された前記第１組のインライアについての回転および平行移動の変化を受け取るステップと、
前記第１組のインライアについての前記回転および平行移動の変化のスコアを決定するステップと、
第１のジョイント・トライアルにおいて、最小２乗法を使用して前記第１組のインライアに対して演算を実施して、第１の反復の間に第２組のインライアを生成するステップと、
前記第１のジョイント・トライアルからの前記第２組のインライアの回転および平行移動の変化を計算するステップと、
前記第１のジョイント・トライアルからの前記第２組のインライアの前記回転および平行移動の変化のスコアを決定するステップと、
前記第１組のインライアの前記回転および平行移動の変化の前記スコアと、前記第２組のインライアの前記回転および平行移動の変化の前記スコアとを比較して、前記第１の反復の間に適当な出力を決定するステップと
を備える、
方法。
【請求項２】
請求項１に記載の方法であって、
前記第１組のインライアの前記回転および平行移動の変化の前記スコアと、前記第２組のインライアの前記回転および平行移動の変化の前記スコアとを比較する前記ステップが、
前記第１組のインライアの前記回転および平行移動の変化の前記スコアが、前記第２組のインライアの前記回転および平行移動の変化の前記スコアよりも大きいときに、前記第１組のインライアの前記回転および平行移動の変化を出力するステップと、
前記第１組のインライアの前記回転および平行移動の変化の前記スコアが、前記第２組のインライアの前記回転および平行移動の変化の前記スコアと等しいときに、前記第２組のインライアの前記回転および平行移動の変化を出力するステップと
を更に含む、
方法。
【請求項３】
請求項２に記載の方法であって、
前記第１組のインライアの前記回転および平行移動の変化の前記スコアが、前記第２組のインライアの前記回転および平行移動の変化の前記スコアよりも大きくもなく、等しくもない場合に、
第２のジョイント・トライアルにおいて、最小２乗法を使用して前記第２組のインライアに対して演算を実行して、第２の反復の間に第３組のインライアを生成するステップと、
前記第２のジョイント・トライアルからの前記第３組のインライアの回転および平行移動の変化を計算するステップと、
前記第２のジョイント・トライアルからの前記第３組のインライアの前記回転および平行移動の変化のスコアを決定するステップと、
前記第２組のインライアの前記回転および平行移動の変化の前記スコアと、前記第３組のインライアの前記回転および平行移動の変化の前記スコアとを比較して、前記第２の反復の間に適当な出力を決定するステップと
を更に含み、
前記第２組のインライアの前記回転および平行移動の変化の前記スコアを比較する前記ステップが、
前記第２組のインライアの前記回転および平行移動の変化の前記スコアが、前記第３組のインライアの前記回転および平行移動の変化の前記スコアよりも大きいときに、前記第２組のインライアの前記回転および平行移動の変化を出力するステップと、
前記第２組のインライアの前記回転および平行移動の変化の前記スコアが、前記第３組のインライアの前記回転および平行移動の変化の前記スコアと等しいときに、前記第３組のインライアの前記回転および平行移動の変化を出力するステップと
を更に含み、
前記第２組のインライアの前記回転および平行移動の変化の前記スコアが、前記第３組のインライアの前記回転および平行移動の変化の前記スコアよりも大きくもなく、等しくもない場合に、
第３のジョイント・トライアルにおいて、最小２乗法を使用して前記第３組のインライアに対して演算を実行して、第３の反復の間に第４組のインライアを生成するステップと、
前記第３のジョイント・トライアルからの前記第４組のインライアの回転および平行移動の変化を計算するステップと、
前記第４組のインライアの前記回転および平行移動の変化を出力するステップと
を更に含む、
方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リアルタイム・ビジュアル・オドメトリ（real-time visual odometry）の分野に関する。
【背景技術】
【０００２】
本出願は、２００７年２月１２日出願の「ＳＹＳＴＥＭ  ＡＮＤ  ＭＥＴＨＯＤ  ＦＯＲ  ＭＯＴＩＯＮ  ＥＳＴＩＭＡＴＩＯＮ  ＵＳＩＮＧ  ＶＩＳＩＯＮ  ＳＥＮＳＯＲＳ」という名称の米国特許出願第１１／６７３，８９３号に関連し、これを参照により本明細書に組み込む。
【０００３】
本出願はまた、２００７年２月１２日出願の「ＳＥＮＳＯＲ  ＦＵＳＩＯＮ  ＦＯＲ  ＮＡＶＩＧＡＴＩＯＮ」という名称の米国特許出願第１１／６７３，９０６号に関連し、これを参照により本明細書に組み込む。
【０００４】
多くの状況で、或る主体の位置を知る必要が生じる。例えば、航空機、宇宙機、陸上ビークルなどの操縦者は、航空／宇宙機または陸上ビークル（vehicle）を適切に操縦して危険な状態を回避するために、その位置を知る必要がある。更に、無人航空ビークル（unmanned aerial vehicle：ＵＡＶ）やモバイル・ロボットなどの無人ビークルも、或る領域を適切に航行するために正確な位置および速度の情報を必要とする。
【０００５】
地球上および地球の周辺において、正確な航行に関する問題は、通常、全地球測位システム（ＧＰＳ）センサの助けを借りて解決することができる。しかしながら、ＧＰＳ信号が常に使用可能というわけではない。例えば、ビークルが都会の高い建築物の間や大きな峡谷の中を移動しているときには、ＧＰＳ信号が使用できないことがある。ＧＰＳ信号が使用できないとき、精密な航行は、より困難になる。ＧＰＳ信号がない場合、知られている現行の大部分の航法は、ドリフトの影響を受けやすい。
【０００６】
ＧＰＳ信号がない場合のナビゲーション（航法）に関係した技術は、軍事部門と商業部門との両方から多くの注目を集めている。典型的な解決法は、相対的航法を提供するのみである。これは、プラットフォームがナビゲーションできる唯一の方法は、推測航法（dead reckoning）によるものであることを意味する。推測航法は、或る主体の現在の位置を、以前に求めた位置に基づいて推定し、その位置を、既知の速度と経過時間と進路とに基づいて進める方法である。
【０００７】
推測航法に依存した最新の慣性航法システムは、さまざまな有人または自律型のビークルにおいて幅広く使用されている。このような慣性航法システムは、ＧＰＳなどのような外部の参照を必要とせずに、コンピュータおよび運動センサを使用して、ビークルの位置、方向および速度を連続的に追跡する。このような慣性航法システムの主要な構成要素は、慣性測定ユニット（inertial measurement unit：ＩＭＵ）である。ＩＭＵは、加速度計とジャイロスコープとの組合せを使用してＩＭＵ自体の運動のレートおよび方向を感知することにより機能し、これにより、誘導コンピュータ（guidance computer）が、推測航法を使用してビークル位置を追跡することを可能にする。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】米国特許出願第１１／６７３，８９３号
【特許文献２】米国特許出願第１１／６７３，９０６号
【非特許文献】
【０００９】
【非特許文献１】Ｍ．Ａ．Ｆｉｓｃｈｌｅｒ、Ｒ．Ｃ．Ｂｏｌｌｅｓ、「Ｒａｎｄｏｍ  Ｓａｍｐｌｅ  Ｃｏｎｓｅｎｓｕｓ：Ａ  Ｐａｒａｄｉｇｍ  ｆｏｒ  Ｍｏｄｅｌ  Ｆｉｔｔｉｎｇ  ｗｉｔｈ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  Ｉｍａｇｅ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ａｕｔｏｍａｔｅｄ  Ｃａｒｔｏｇｒａｐｈｙ」、Ｃｏｍｍ．ｏｆ  ｔｈｅ  ＡＣＭ、２４巻：３８１〜３９５ページ（１９８１年６月）
【発明の概要】
【発明が解決しようとする課題】
【００１０】
推測航法の深刻な問題は集積ドリフト（integration drift）である。推測航法は、ナビゲーションのために集積法を使用するため、速度／レートの推定値の誤差が集積され、これが、航法の位置／姿勢の解のランダムで際限のないドリフトにつながる。従って、速度／レートの推定値の誤差を最小化することにより集積ドリフトの影響を制限するために使用できる技法が、求められている。
【課題を解決するための手段】
【００１１】
本発明は、リアルタイム・ビジュアル・オドメトリの方法およびシステムに関する。この方法は、第１の時間（時刻）に、或る位置の第１の３次元画像を取得するステップと、第１の時間よりも後の第２の時間（時刻）に、前記の位置の第２の３次元画像を取得するステップと、第１および第２の３次元画像のそれぞれから、１または複数の特徴およびその記述子を抽出するステップとを含む。次に、第１の３次元画像からの１または複数の特徴と、第２の３次元画像からの１または複数の特徴との対応付けが行われる。この方法は更に、ランダム・サンプル・コンセンサス（ＲＡＮＳＡＣ）・プロセスと、独特の反復する改善の技術（iterative refinement technique、反復改善技術）とを使用して、第１の時間から第２の時間までの、第１の３次元画像と第２の３次元画像との間の回転および平行移動（translation）の変化を求めるステップを含む。
【００１２】
前記の反復改善技術は、第１組のインライア（inlier）と、ＲＡＮＳＡＣプロセスから出力された第１組のインライアの回転および平行移動における変化とを受け取るステップと、第１組のインライアの回転および平行移動の変化のスコアを決定するステップとを含む。この反復改善技術は更に、第１のジョイント・トライアル（joint trial）において最小２乗法を使用して第１組のインライアに対して演算を実施して、第２組のインライアを生成するステップと、第１のジョイント・トライアルからの第２組のインライアの回転および平行移動の変化を計算するステップと、第１のジョイント・トライアルからの第２組のインライアの回転および平行移動の変化のスコアを決定するステップとを含む。次いで、１または複数の反復の間に適当な出力を決定するために、第１組のインライアと第２組とが比較される。
【００１３】
当業者には、図面を参照して以下の説明から本発明の特徴が明白になるであろう。図面は、本発明の典型的な実施形態のみを示すものであり、範囲を限定すると見なされないとの理解のもとで、添付図面を使用して、本発明を、追加の特定的構成および詳細とともに説明する。
【図面の簡単な説明】
【００１４】
【図１】図１は、本発明の方法を使用して３次元画像からビークルの運動を推定する一実施態様の概略図である。
【図２】図２は、本発明の方法で使用される改善アルゴリズムの流れ図である。
【図３】図３は、本発明のシステムの一実施形態のデータの流れを示すブロック図である。
【発明を実施するための形態】
【００１５】
以下の詳細な説明では、当業者が本発明を実施できるよう、実施形態が十分に詳細に説明される。本発明の範囲から逸脱することなく他の実施形態を使用することもできることを理解されたい。従って、以下の詳細な説明を限定的に解釈してはならない。
【００１６】
本発明は、フレーム・ツー・フレーム（frame-to-frame）・ナビゲーション技術において使用することができるリアルタイム・ビジュアル・オドメトリの方法およびシステムを対象とする。この方法は、慣性測定ユニット（ＩＭＵ）を使用するような、無人または有人の陸上用ビークルのナビゲーションのために使用される、あるいはパーソナル・ナビゲーションに使用される、ＧＰＳの使用を制限された又は受け付けない航法システムにおいて使用することができる。本発明の方法を使用すると、ＧＰＳ信号が使用できないときに、このような慣性航法システムにおけるドリフトを補償することができる。あるいは、本発明の方法を、ＩＭＵやＧＰＳの信号を使用しない航法に対して使用することもできる。本発明の方法およびシステムはまた、電気光学（ＥＯ）支援ソースを使用して、Δ位置／Δ姿勢（位置変化／姿勢変化）の推定値の誤差を最小化する。
【００１７】
一般に、本発明の方法およびシステムは、相対的な位置および姿勢の変化を含むビークルの運動を、３次元画像（３Ｄ）からリアルタイムでロバストに推定することができる。３Ｄ画像は、３次元の深さまたは強度の情報を提供することにより或る位置にある既知の特徴（feature）までの距離を計算することができるセンサ・デバイスまたはセンサ・デバイスの組合せを使用して、生成することができる。適当なセンサ・デバイスの非限定的な例は、立体カメラ、光検出およびレンジング（ライダ（lidar））デバイス、レーダ・デバイス、ソナー・デバイスなどを含む。これらのデバイスは３Ｄ画像を生成する手段の例である。
【００１８】
図１は、本発明の方法を用いてビークルの移動（運動）を推定する一実施態様を示す。立体カメラなどの画像センサ・デバイス１１４により、第１の画像対１１０および第２の画像対１１２が生成される。第１の画像対１１０は、第１の時刻（ｔ１）に取得された左フレーム１１０−Ｌおよび右フレーム１１０−Ｒを含み、第２の画像対１１２は、第２の時刻（ｔ２）に取得された左フレーム１１２−Ｌおよび右フレーム１１２−Ｒを含む。
【００１９】
第１の画像対１１０および第２の画像対１１２は、エゴモーション・エスティメータ（ego-motion estimator、エゴモーション評価手段）１２０で処理され、時刻ｔ１から時刻ｔ２への、第１および第２の画像対の回転（rotation）の変化（ｄＲ）および平行移動（translation）の変化（ｄＴ）が求められる。エゴモーション・エスティメータ１２０は、後述されるさまざまなタスクを実行するソフトウェアを実行する１または複数のプロセッサを有することができる。
【００２０】
一般に、エゴモーション・エスティメータ１２０は、それぞれの画像対の左フレームおよび右フレームから特徴およびその記述子（descriptor）を抽出する。特徴は、画像対の左フレームと右フレームの間で対応付けられる。誤った対応を退けるために、対応結果（match）は、エピポーラ制約（epipolar constraint）を使用してフィルタリングされる。例えば、図１のそれぞれの画像フレームにおいて識別され対応付けされることができる独特な特徴は、左フレーム１１０−Ｌ、左フレーム１１２−Ｌ、右フレーム１１２−Ｒおよび右フレーム１１０−Ｒにおいてそれぞれａ、ｂ、ｃおよびｄと標識付けされた街灯柱の先端である。立体カメラが使用される場合、左右の画像を使用することにより３Ｄポイント・クラウド（point cloud）が構築される。左右の画像は、画像フレームの左から右へ対応付けられた任意の特徴の３次元の位置情報を提供するものである。ライダが使用される場合、対応付けは時刻ｔ１と時刻ｔ２との間でのみ行われる。なぜなら、画像はすでに３Ｄ情報を含んでいるからである。エゴモーション・エスティメータ１２０は、次いで、ＲＡＮＳＡＣ（ＲＡＮｄｏｍ  ＳＡｍｐｌｅ  Ｃｏｎｓｅｎｓｕｓ（ランダム・サンプル・コンセンサス））・プログラムおよび独特の反復する改善アルゴリズム（iterative refinement algorithm）を使用して、ｄＲおよびｄＴを見つける。この改善アルゴリズムについては後に詳細に論じられる。
【００２１】
エゴモーションおよびＲＡＮＳＡＣ
エゴモーション（ego-motion）と呼ばれる画像シーケンスからのカメラの運動（動き）の計算は、ＵＡＶ、ロボットなどのモバイル型無人プラットフォームの位置推定能力を向上させる技法である。なぜなら、こうしたプラットフォームではオドメトリ誤差が急速に増大するならである。エゴモーションによる推定（評価）を使用する際には、以下のものが適用される。すなわち、２つの時刻におけるＮ個の点の３Ｄ座標が与えられた場合に、下記の式が最小となるような、回転変換（ｄＲ）および平行移動（ｄＴ）を見つける。
【００２２】
Ｊ＝Σ（Ｐｉ−ｄＲＱｉ−ｄＴ）Ｔ（Ｐｉ−ｄＲＱｉ−ｄＴ）
【００２３】
上記の式において、Ｊは費用関数（cost function）である。パラメータＰおよびＱは２つの異なる時刻における３Ｄ点を表す。アブソリュート・オリエンテーション（absolute orientation、絶対方向）を得るために、４元数（quaternion）および直交（orthonormal）マトリックスに関する解析解が存在する。しかしながら、問題は、最小２乗アルゴリズムが、アウトライア（outlier）に敏感であるということである。従って、特徴の不適当な対応（適切な対応関係ではない対応）を取り除くために、ＲＡＮＳＡＣプログラムが使用される。
【００２４】
ＲＡＮＳＡＣプログラムは、反復技術を使用して、観察されたデータの組から数学モデルのパラメータを推定する。ＲＡＮＳＡＣプログラムの基本的な仮定は、「観察されたデータには、或る組のモデル・パラメータにより説明することができるデータ点である『インライア（inlier）』と、モデルに当てはまらないデータ点である『アウトライア（outlier）』とが含まれる」というものである。アウトライアは、雑音や誤測定から生じ得る。ＲＡＮＳＡＣプログラムはまた、「或るインライアの組が与えられた場合に、データを最適に説明する又はデータに最適に適合するモデルのパラメータを推定することができる手順が存在する」ということを仮定する。
【００２５】
ＲＡＮＳＡＣプログラムに関する更なる詳細は、Ｍ．Ａ．Ｆｉｓｃｈｌｅｒ、Ｒ．Ｃ．Ｂｏｌｌｅｓによる論文「Ｒａｎｄｏｍ  Ｓａｍｐｌｅ  Ｃｏｎｓｅｎｓｕｓ：Ａ  Ｐａｒａｄｉｇｍ  ｆｏｒ  Ｍｏｄｅｌ  Ｆｉｔｔｉｎｇ  ｗｉｔｈ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  Ｉｍａｇｅ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ａｕｔｏｍａｔｅｄ  Ｃａｒｔｏｇｒａｐｈｙ」、Ｃｏｍｍ．ｏｆ  ｔｈｅ  ＡＣＭ、２４巻：３８１〜３９５ページ（１９８１年６月）に記載されており、これを参照により本明細書に組み込む。
【００２６】
改善アルゴリズム
ＲＡＮＳＡＣプログラムは幾つかのアウトライア点を排除するが、典型的には、幾つかのアウトライア点をインライア点として維持する。改善アルゴリズムは、インライアを保持し、アウトライアを排除することにより、より正確なｄＲおよびｄＴを得るために、ＲＡＮＳＡＣから出力されたデータ点の最良の候補に関して最小２乗フィット（fit、適合）を計算する。
【００２７】
図２は、本発明に基づく方法２００の流れ図であり、ＲＡＮＳＡＣモジュール２０４とともにデータ改善モジュール２０２が使用される。データ改善モジュール２０２は、ＲＡＮＳＡＣプログラムの改善アルゴリズムを実現し、ＲＡＮＳＡＣプログラムにおいて使用された最小２乗法が矛盾のない結果を生成したかをチェックする。
【００２８】
方法２００では、第１の時刻（ｔ１）における３Ｄデータ点の第１組Ｐおよび第２の時刻（ｔ２）おける３Ｄデータ点の第２組Ｑが、ＲＡＮＳＡＣモジュール２０４へ入力される。例えば、３Ｄデータ点の第１組Ｐは２０個のデータ点（Ｐ１〜Ｐ２０）を含むことができ、３Ｄデータ点の第２組Ｑは２０個のデータ点（Ｑ１〜Ｑ２０）を含む。これらの３Ｄデータ点の組は、前述の画像特徴抽出および対応付けの技術により生成することができる。ＲＡＮＳＡＣモジュール２０４は、３つのデータ点からなるランダムな組に対して最小２乗法を実行し（triplet trial、トリプレット・トライアル）、アウトライア・データ点を排除し、最良のトリプレット（triplet、三つ組）を得る。
【００２９】
この最良のトリプレットはＲＡＮＳＡＣモジュール２０４から出力され、インライアの最初（第１）の組（Ｐｉ、Ｑｉ）ならびに、回転の変化（ｄＲｉ）および平行移動の変化（ｄＴｉ）を定義する。これらは、収集ノード２１０においてデータ改善モジュール２０２へ入力される。データ改善モジュール２０２のソフトウェアは、全ての条件が満たされるまで反復して実行するように構成される。ｄＲｉおよびｄＴｉのスコア（score）は、第１の反復の間に３Ｄ点の対の数を計数することにより決定される。
【００３０】
第１組のインライア（Ｐｉ、Ｑｉ）はジョイント・トライアル（joint trial）・モジュール２１２へ送られ、ジョイント・トライアル・モジュール２１２は、最小２乗法を使用して第１組のインライアに対して演算を実施して、第１のジョイント・トライアルにおいて第２組のインライア（Ｐｏ、Ｑｏ）を生成する。第１の反復の間に、第１のジョイント・トライアルから、第１組のインライア（Ｐｉ、Ｑｉ）についての回転の変化（ｄＲｏ）および平行移動の変化（ｄＴｏ）が計算される。このジョイント・トライアルのｄＲｏおよびｄＴｏのスコアが、３Ｄ点の対の数を計数することにより、決定される。第１の反復の間に、比較器２１４で、第１のジョイント・トライアルのｄＲｏおよびｄＴｏのスコアが、第１組のインライアのｄＲｉおよびｄＴｉのスコアと比較され、適当な出力が求められる。ｄＲｉおよびｄＴｉのスコアが、第２組のインライアのｄＲｏおよびｄＴｏのスコアよりも大きい場合、ｄＲｉおよびｄＴｉが出力される。例えば、第２組のインライアの数が少な過ぎ（ｎ（Ｐｉ）＞ｎ（Ｐｏ））、判断ボックス２２０で「Ｙｅｓ」の場合、第１のジョイント・トライアルの結果が拒絶され、そして、第１組のインライアのｄＲｉおよびｄＴｉが、航法などで将来に使用されるように、保持されてデータ改善モジュール２０２から出力される。ｄＲｉおよびｄＴｉのスコアがｄＲｏおよびｄＴｏのスコアと等しいときには、ｄＲｏおよびｄＴｏが出力される。例えば、第１組と第２組のインライアが同じである場合（Ｐｉ＝Ｐｏ、判断ボックス２２２での「Ｙｅｓ」）、ジョイント・トライアルの結果ｄＲｏおよびｄＴｏが受け入れられ、航法などで将来に使用するためにデータ改善モジュール２０２から出力される。
【００３１】
第１組と第２組のインライアが異なる場合（判断ボックス２２２での「Ｎｏ」）、ＮＯＴコマンド２３０からの信号に応答して、第２組のインライア（Ｐｏ、Ｑｏ）が、保持ノード２２６から収集ノード２１０へ送られる。第２組のインライアを使用して、上記のステップが繰り返される。第２組のインライアは、ジョイント・トライアル・モジュール２１２へ入力され、第３組のインライア（Ｐｏ、Ｑｏ）を生成するために最小２乗法を使用する第２のジョイント・トライアル（第２の反復）が行われる。第２のジョイント・トライアルからの第３組のインライアについての回転の変化（ｄＲｏ）および平行移動の変化（ｄＴｏ）が計算される。次いで、第２のジョイント・トライアルのｄＲｏおよびｄＴｏのスコアが決定される。
【００３２】
第２の反復の間に、比較器２１４で、第２のジョイント・トライアルのｄＲｏおよびｄＴｏのスコアが、第１のジョイント・トライアルのｄＲｏおよびｄＴｏのスコアと比較される。インライアの数が少な過ぎる場合、第２のジョイント・トライアルの結果が拒絶され、第１のジョイント・トライアルのｄＲｏおよびｄＴｏが保持され、データ改善モジュール２０２から出力される。第２組と第３組のインライアが同じである場合、第２のジョイント・トライアルの結果ｄＲｏおよびｄＴｏが受け入れられ、データ改善モジュール２０２から出力される。
【００３３】
第２組と第３組のインライアが異なる場合、第３組のインライア（Ｐｏ、Ｑｏ）が、保持ノード２２６から収集ノード２１０へ送られ、ジョイント・トライアル・モジュール２１２へ入力され、そこで、最小２乗法を使用して、第３組のインライア（Ｐｏ、Ｑｏ）に対して最後のジョイント・トライアル（第３の反復）が実行され、第４組のインライア（Ｐｏ、Ｑｏ）が生成される。最後のジョイント・トライアルからの第４組のインライアに関して回転の変化（ｄＲｏ）および平行移動の変化（ｄＴｏ）が計算される。改善モジュール２０２のアルゴリズムは３回の反復を経たので（反復＜３、判断ボックス２３０での「Ｎｏ」）、第４組のインライアに対する最後のジョイント・トライアルの結果（ｄＲｏおよびｄＴｏ）が受け入れられ、将来の使用のためにデータ改善モジュール２０２から出力される。
【００３４】
システムのデータの流れ
図３は、本発明に基づくリアルタイム・ビジュアル・オドメトリのシステム３００の一実施態様のデータの流れを示すブロック図である。立体カメラなどの画像センサ・デバイス３０８は、左画像３１０および右画像３１２をそれぞれが含む連続した２次元画像を取得するように構成される。左画像３１０および右画像３１２は、イメージ・レクティフィケーション（rectification、調整）・モジュール３２０により受け取られ、このモジュールは、左画像３１０と右画像３１２とを共通の画像面に投影して、左画像３１０と右画像３１２との合成画像である１つの３Ｄ画像を生成する変換処理を実行するように、構成されている。イメージの調整、２つのカメラの方向の小さな変化を補正することができ、また、画像を互いに対して既知の方向に置くことができる。
【００３５】
イメージ・レクティフィケーション・モジュール３２０からの画像データは第１のプロセッサ３３０に入力され、この第１のプロセッサ３３０は、ハリス特徴エクストラクタ（Harris feature extractor、ハリス特徴抽出手段）を使用するなどにより左画像３１０から１または複数の特徴および記述子を抽出するように構成されている。イメージ・レクティフィケーション・モジュール３２０からの画像データは、第１のプロセッサと並行して動作する第２のプロセッサ３３２へも入力される。第２のプロセッサは、ハリス特徴エクストラクタを使用するなどにより、右画像３１２から１または複数の特徴および記述子を抽出するように構成されている。第１および第２のプロセッサは、デュアル・コア・システムなどのような、抽出処理を高速化するマルチプロセッサ・システムの一部とすることができる。
【００３６】
次いで、特徴抽出の結果は第１の特徴対応付けプログラム・モジュール３４０に入力され、このモジュールは、左画像３１０からの１または複数の特徴と、右画像３１２からの１または複数の特徴とを対応付けるように構成されている。この特徴対応付けは、エピポーラ制約を使用して、対応付けられる特徴が画像中の固定数の列（row）内にあることを要求することにより、改善することができる。
【００３７】
特徴は、次いで、時間にわたり対応付けされ、チェック・ループは第２の特徴対応付けプログラム・モジュール３５０を使用するものであり、このモジュールは、時刻ｔｌにおける左画像３１０および右画像３１２からの１または複数の特徴を、それぞれ、時刻ｔ２における後続の左画像および右画像からの１または複数の特徴と対応付けるように構成されている。その結果として、時刻ｔｌにおける３Ｄ点の組が、時刻ｔ２における３Ｄ点の組と対応付けられる。
【００３８】
この３Ｄデータは、次いで、ロバスト・ポーズ・エスティメータ（robust pose estimator）３６０へ入力され、このロバスト・ポーズ・エスティメータは、連続した３Ｄ画像間の回転の変化（ｄＲ）および平行移動の変化（ｄＴ）を決定するように構成されている。次いで、ｄＲおよびｄＴが、例えば航法システムなどで後に使用するために、３７０および３７２で出力される。ロバスト・ポーズ・エスティメータ３６０は、ＲＡＮＳＡＣプログラムと、より正確なｄＲおよびｄＴを提供する本発明の改善アルゴリズムを実現するソフトウェア・コードとを含む。このソフトウェア・コードの実行時間は、画像入力特徴の数と、実行されるＲＡＮＳＡＣトライアルの回数とにより決まる。
【００３９】
本発明の方法の実施で使用される命令、すなわち、さまざまな処理タスクや、計算や、信号および他のデータの生成を行うための命令は、ソフトウェアや、ファームウェアや、他のコンピュータ可読命令を含むコンピュータ・プログラム製品で実現することができる。これらの命令は、典型的には、コンピュータ可読命令やデータ構造を記憶するために使用される適当なコンピュータ可読媒体に記憶される。このようなコンピュータ可読媒体は、汎用や専用のコンピュータやプロセッサ、また、プログラム可能な論理デバイスがアクセスすることができる任意の使用可能媒体とすることができる。例えば、本発明の方法およびシステムは、ラップトップ・コンピュータで実行されるソフトウェアとして実現することができる。
【００４０】
適当なコンピュータ可読媒体は、例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリ・デバイスなどの半導体記憶デバイスや、内蔵ハード・ディスク、リムーバブル・ディスクなどの磁気ディスクや、光磁気ディスクや、ＣＤ、ＤＶＤ、その他の光記憶ディスクや、不揮発性ＲＯＭ、ＲＡＭ、その他の同様の媒体や、コンピュータ実行可能命令またはデータ構造の形態の所望されるプログラム・コード手段を担持または記憶するために使用できる他の任意の媒体を含む不揮発性記憶デバイスを含む。上記のもは何れも、特別に設計された特定用途向け集積回路（ＡＳＩＣ）やフィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）により補うことができ、また、これらに組み込むことができる。ネットワークまたは他の通信接続（有線、無線、または有線と無線の組合せ）を介してコンピュータへ情報が転送または提供されると、そのコンピュータは、適切に、その接続をコンピュータ可読媒体として見る。従って、そのような接続をコンピュータ可読媒体と呼ぶのは適切である。上記のものの組み合わせもコンピュータ可読媒体の範囲に含まれる。
【００４１】
本発明の方法は、データ・プロセッサにより実行されるプログラム・モジュールやアプリケーションなどのようなコンピュータ可読命令として実現することができる。一般に、プログラム・モジュールやアプリケーションは、特定のタスクを実行したり特定の抽象データ型を実現するルーチン、プログラム、オブジェクト、データ・コンポーネント、データ構造、アルゴリズムなどを含む。これらは、本明細書に記載した方法の諸ステップを実行するためのプログラム・コードの例を表す。このような実行可能命令または関連データ構造の特定のシーケンスは、そのようなステップにおいて記述された機能を実現するための対応する動作の例を表す。
【００４２】
本発明は、その本質的特性から逸脱することなく、他の特定の形態で具体化することができる。上記の実施形態は、全ての点で、単なる例であり、限定するものではないとみなされる。本発明の範囲は、上記の説明ではなく特許請求の範囲により示される。特許請求の範囲の等価の意味および範囲に含まれる変更の全ては、特許請求の範囲に含まれる。
【図２】
2009266224.tif 000003
【図３】
2009266224.tif 000004
【図１】
2009266224.tif 000005
【外国語明細書】
2009266224000001.pdf