ビジュアル・オドメトリのための方法および装置
(例えば周囲の環境の中をナビゲートする)ビジュアル・オドメトリのための方法および装置が開示される。一実施形態では、周囲の環境の少なくとも一部を表すシーン・イメージのシーケンスが(例えばビデオ・カメラまたはステレオ・ヘッドから)受領される。シーン・イメージのシーケンスが(例えばビデオ処理技法に従って)処理され、周囲の環境に対するポーズの推定が導出される。この推定は、グローバル・ポジショニング・システム、あるいは慣性センサまたは機械センサなどの他のセンサからのデータでさらに補足することができる。
【発明の詳細な説明】
【背景技術】
【0001】
関連出願への相互参照
本願は、参照により本明細書にその全体が組み込まれる2004年6月22日出願の米国仮特許出願第60/581867号の特典を主張するものである。
【0002】
政府資金援助への参照
本発明は、DARPA(Defense Advanced Research Projects Agency) によって与えられた交付番号MDA972−01−9−0016の下で政府援助を伴ってなされたものである。政府は、本発明における一定の権利を有する。
【0003】
様々な応用例におけるコンピュータ・ビジョン・システムの有用性が認められている。例えば、(例えば車両用およびロボット用の)自律ナビゲーション・システムは、周囲の環境内での障害物検出およびナビゲーションのためにそのようなシステムを大いに利用する。そのようなシステムは、人間のオペレータを危険にさらすことなく、難しい地帯または危険な地帯のナビゲーションおよび/または監視を可能にする。
【0004】
しかし、自律的ナビゲーション用のほとんどの既存のシステムは、一般に環境特有のものであるという点で汎用性に欠けている。例えば、GPSベースのナビゲーション・システムは、屋外環境では良好に動作するが、屋内での動作が不十分である。ホイール・エンコーダからの情報を利用するナビゲーション・システムは、地上車両で実装したときは良好に動作するが、例えば航空機での使用には適していない。さらに、ビデオまたはイメージ・データを解析することによって動作するほとんどの既存のシステムは、過去の運動の知識を提供することができるが、現在の運動および/または位置の(例えばリアル・タイムの)知識を適時に提供することができない。
【特許文献1】米国仮特許出願第60/581867号
【非特許文献1】C.HarrisおよびM.Stephens、A Combined Corner and Edge Detector (Proc.Fourth Alvey Vision Conference、pp.147−151、1988年)
【非特許文献2】D.Nister、Preemptive RANSAC for Live Structure and Motion Estimation、IEEE International Conference on Computer Vision、pp.199−206、2003年
【特許文献2】米国特許出願第10/798726号
【非特許文献3】R.Haralick、C.Lee、K.Ottenberg、およびM.Nolle、Review and Analysis of Solutions of the Three Point Perspective Pose Estimation Problem、International Journal of Computer Vision、13(3):331−356、1994年
【発明の開示】
【発明が解決しようとする課題】
【0005】
したがって、環境に無関係であり、ほぼリアル・タイムで運動推定および/または位置推定を確実に提供することのできるビジュアル・オドメトリのための方法および装置が当技術分野で求められている。
【課題を解決するための手段】
【0006】
(例えば周囲の環境の中をナビゲートする)ビジュアル・オドメトリのための方法および装置が開示される。一実施形態では、周囲の環境の少なくとも一部を表すシーン・イメージのシーケンスが(例えばビデオ・カメラまたはステレオ・ヘッドから)受領される。シーン・イメージのシーケンスが(例えばビデオ処理技法に従って)処理され、周囲の環境に対するポーズの推定が導出される。この推定は、グローバル・ポジショニング・システム、あるいは慣性センサまたは機械センサなどの他のセンサからのデータでさらに補足することができる。
【0007】
上述の本発明の特徴を詳細に理解できるように、添付の図面にその一部が図示される実施形態を参照することにより、上記で簡潔に要約される本発明のより具体的な説明を得ることができる。しかし、添付の図面は本発明の典型的な実施形態を示すに過ぎず、したがって、本発明は同様に効果的な他の実施形態を認めることができるので、添付の図面を本発明の範囲の制限と見なすべきでないことに留意されたい。
【発明を実施するための最良の形態】
【0008】
本発明は、(例えば、自律的車両またはロボットなどの移動物体の自律的ナビゲーション用の)ビジュアル・オドメトリのための方法および装置を開示する。従来の自律的ナビゲーション・システムとは異なり、一実施形態では、本発明は、主にビデオ・データを利用して物体の位置推定および運動推定を導出する。したがって、本発明による自律的ナビゲーションは実質上、環境に無関係である。自律的ナビゲーション・システムで通常使用されるような環境特有のセンサは主に、ビデオ・ベースの推定を補足するためのデータを得るための任意選択手段として働く。
【0009】
図1は、本発明によるビジュアル・オドメトリのための方法100の一実施形態を示す流れ図である。方法100は、例えば、自律的(例えば無人の)車両またはロボットなどのナビゲーションを必要とする物体で実装することができる。方法100はステップ102で初期化され、ステップ104に進み、ステップ104では、方法100は、周囲の環境の少なくとも一部を表すシーン・イメージのシーケンスを受け取る。一実施形態では、ナビゲーションを必要とする物体に取り付けられた移動カメラまたはステレオ・ヘッドを介してこのシーン・イメージのシーケンスを受け取ることができる。
【0010】
ステップ106では、方法100は、シーン・イメージのシーケンスを処理し、それから位置推定を導出する。すなわち、方法100は、受け取ったシーン・イメージのシーケンスから直接、ナビゲーションを必要とする物体の現在位置を推定する。一実施形態では、シーン・イメージのシーケンスが、ビデオ処理のための任意の適切な周知の方法に従って処理される。
【0011】
位置推定をシーン・イメージのシーケンスから導出した後、任意選択で、方法100はステップ108に進み、追加のデータで位置推定を補足する。したがって、この実施形態では、ステップ106で導出されたビデオ・ベースの位置推定を、その後で他のソースからデータを取り入れることによって改善される予備推定と見なすことができる。一実施形態では、この追加のデータは、GPSシステム、慣性センサ、および機械センサ(例えばホイール・エンコーダ)のうちの少なくとも1つなどの、少なくとも1つの追加のセンサで与えられるデータを含む。
【0012】
(追加のデータを用いて、または追加のデータを用いずに)位置推定を導出した後、方法100はステップ110で終了する。
それによって方法100は、方法100が機能する環境とは無関係な、迅速で正確な運動推定および位置推定を可能にする。方法100は主に(ある場合には専ら)ビデオ・データを利用して運動推定および位置推定を導出するので、ほぼ任意の場所、すなわち屋外、屋内、地上、空中などで利用するように実装することができる。
【0013】
図2は、本発明によるビデオ・データから運動推定および/または位置推定を導出する方法200の一実施形態を示す流れ図である。上記で議論した方法100のステップ106に従って方法200を実装して、ナビゲーションを必要とする車両、ロボットなどの運動または位置のビデオ・ベースの推定を生成することができる。
【0014】
方法200はステップ202で初期化され、ステップ204に進み、ステップ204では、方法200は、シーン・イメージのシーケンスの現フレーム内のポイント・フィーチャの位置を突き止める。一実施形態では、突き止めたポイント・フィーチャは、小さなイメージひずみから中程度のイメージひずみの下で比較的安定すると予想されるフィーチャである。例えば、一実施形態では、ポイント・フィーチャは、C.HarrisおよびM.Stephens、A Combined Corner and Edge Detector (Proc.Fourth Alvey Vision Conference、pp.147−151、1988年)に記載されているハリス・コーナである。ポイント・フィーチャは、確実に追跡することのできるフレームの任意の識別可能な要素でよい。一実施形態では、最大数百個のポイント・フィーチャの位置がステップ202で突き止められる。例えば、図8は、シーン・イメージのシーケンスから取られた例示的フレーム800であり、その中で複数のポイント・フィーチャの位置が円で突き止められている。話を簡単にするために、これらの円で囲まれたポイント・フィーチャのうちの一部だけに802と符号を付ける。
【0015】
ステップ206では、方法200は、ステップ204で位置が突き止められたポイント・フィーチャを(例えば、フィーチャを、後続のフレーム内の対応するフィーチャと突き合わせることによって)複数の後続のフレームにわたって追跡する。一実施形態では、ポイント・フィーチャは、フィーチャが視野内にとどまる限り追跡される。一実施形態では、幾何学的制約なしに追跡が実施される。
【0016】
ステップ208では、方法200は、ステップ206で得られたフィーチャ追跡データに基づいて1組の軌跡を生成する。軌跡は、ナビゲーションを必要とする物体に対する、追跡したフィーチャの位置および/または向きの経時的な変化を表す。一実施形態では、突き合わせたフィーチャが基本的にフレーム間でリンクされる。再び図8を参照すると、図示されている複数の軌跡(その一部に804と符号を付けてある)は、関連するポイント・フィーチャの以前の相対運動を示す。
【0017】
軌跡の組を確立した後、方法200はステップ210に進み、ポイント・フィーチャ軌跡で伝えられた情報に基づいて、ナビゲーションを必要とする車両、ロボットなどについての複数の増分フレーム間ポーズ推定を生成する。一実施形態では、「ポーズ」が6つの自由度で推定され、3次元(例えばx、y、z座標)位置と角度方向として定義される。一実施形態では、幾何学的推定方法に従ってポーズ推定が生成される。ポーズ推定を生成する幾何学的推定方法は、シーン・イメージの元のシーケンスをキャプチャする手段に応じて変化する可能性がある(例えば、単眼ビデオ入力、ステレオ入力など)。
【0018】
ステップ212では、方法200は、ポーズ推定を評価し、最も可能性の高い推定を、現在のポーズを示すものとして選択する。一実施形態では、ポーズ推定の評価は、以下でより詳細に議論するように、周知のRANSAC(random sample consensus)技法(例えば、D.Nister、Preemptive RANSAC for Live Structure and Motion Estimation、IEEE International Conference on Computer Vision、pp.199−206、2003年で論じられている)に従って実施される。
方法200はステップ214で終了する。
【0019】
図3は、例えば方法200のステップ204による、ポイント・フィーチャ検出のための方法300の一実施形態を示す流れ図である。方法300はステップ302で初期化され、ステップ304に進み、ステップ304では、方法300は、解析中のシーン・イメージのシーケンスからイメージ・フレームを取り出す。一実施形態では、イメージ・フレームが、ピクセル当たり約8ビットで表される。
【0020】
ステップ306では、方法300は、フレームのコーナ応答の強度sを計算する。例えば、一実施形態では、ハリス・コーナ検出器は、イメージ勾配から計算される局所平均モーメント行列を計算する。次いで、モーメント行列の固有値が組み合わされ、コーナ応答または「強度」が計算される。その最大値がコーナ位置を示す。
【0021】
(例えば汎用コンピュータを使用する)非常に効率的な計算のために設計された一実施形態では、sが以下のように計算される。コーナ応答の出力ラインごとに、現出力ラインの上または下のいくつかのラインに関して一時フィルタ出力が必要である。すべてのフィルタ出力が一度だけ計算され、最適なキャッシュ性能のためにラップアラウンド・バッファに格納される。ラップアラウンド・バッファは、ローリング・ウィンドウでの一時フィルタ出力を表す。ローリング・ウィンドウは、何らかのフィルタ出力の再計算を回避するために必要な最低限の数のラインを含む。
【0022】
例えば、一実施形態では、イメージ・フレームの水平方向微分および垂直方向微分が、それぞれIxおよびIyと表される。一実施形態では、IxおよびIyがタイプ[−1 0 1]の水平フィルタおよび垂直フィルタによって計算され、入力を8ビットだけ下に、出力を16ビットだけ下に保つために、乗算を実行する前に1ビットだけ下にシフトされる。
【0023】
この場合、ラップアラウンド・バッファおよび得られるコーナ応答が、ラインごとに4つの「掃引」を使用して、ラインごとに更新される。第1掃引は、IxIx、IxIy、およびIyIyについてのラップアラウンド・バッファを更新する。一実施形態では、IxIx、IxIy、およびIyIyについてのラップアラウンド・バッファはライン5本分であり、典型的な掃引は、コーナ応答の現在の出力ラインより2つ先に位置する1つのラインを更新する。
【0024】
第2掃引は、32ビット・フィルタ出力の3つの単一ラインgxx、gxy、およびgyyを生成するために、2項フィルタ(例えば[1 4 6 4 1])でラップアラウンド・バッファ内のすべてのラインを垂直方向にコンボルブする。一実施形態では、このことは、コストのかかる乗算を回避するためにシフトおよび加算で実施される。
【0025】
第3掃引は、第2掃引で使用されたのと同じ2項フィルタで水平方向にコンボルブし、32ビット単一ラインGxx、Gxy、Gxyを生成する。Gxx、Gxy、Gxyは、gxx、gxy、およびgyyと同じ場所に格納されるが、2ピクセルだけシフトされる。
【0026】
最後に、第4掃引は、コーナ応答の
行列式d=GxxGyy−GxyGxy (式1)
トレースt=Gxx+Gyy (式2)
および強度s=d−kt2 (式3)
を浮動小数点で計算する(ただしk=0.06)。一実施形態では、第1掃引から第4掃引はすべて、128ピクセルのマルチメディア・エクステンション(MMX)チャンクで実装され、ストールを回避し、両方のパイプラインを最適に用いるために、手動でインターリーブされる。
【0027】
図3に戻ると、コーナ応答の強度を計算した後、方法300はステップ310に進み、計算したコーナ応答強度に従って、イメージ・フレーム内のポイント・フィーチャを定義する。上述のように、単一のイメージ・フレーム内に数百ものポイント・フィーチャを定義することができる。一実施形態では、ポイント・フィーチャの定義は、非最大抑制技法(non−maximum suppression technique)に従って達成される。具体的には、コーナ応答が定義された半径(例えば5ピクセルごとの近傍)内で他のすべてのピクセルよりも強いと計算される各ピクセルで、ポイント・フィーチャが宣言される。
方法300はステップ312で終了する。
【0028】
図4は、例えばステップ206による、ポイント・フィーチャ整合のための方法400の一実施形態を示す流れ図である。方法400はステップ402で初期化され、ステップ404に進み、ステップ404では、方法400は、第1フレーム内の所与のポイント・フィーチャを第2フレーム内の対応するポイント・フィーチャから固定の距離以内のあらゆるポイント・フィーチャと突き合わせることを試みる(例えば、互いの事前定義された不一致限界以内のすべてのポイント・フィーチャが突き合わされる)。一実施形態では、ポイント・フィーチャ合致に関する不一致限界は、所望の出力速度およびシーン・イメージの入力シーケンスの平滑度に応じて、イメージ・サイズの約3から30パーセントである。
【0029】
方法400の次の段階は、フレーム間フィーチャ対応を確立する。このフレーム間フィーチャ対応は、オプティカル・フロー技法およびエリア相関技法を含む様々な周知の方法に従って確立することができる。ステップ406〜408は、(汎用コンピュータ上の)計算速度に関して最適化された、フレーム間フィーチャ対応を確立する1つの例示的プロセスを示す。
【0030】
ステップ406では、方法400は、正規化相関を使用して第1フレームと第2フレームの間の潜在的ポイント・フィーチャ合致を評価する。一実施形態では、正規化相関は、検出されたポイント・フィーチャ上に中心が置かれた11ピクセル四方のウィンドウにわたって実施される。一実施形態では、速度に関してウィンドウ全体にわたって一様な重み付けが使用される。各ウィンドウがイメージ・フレームからコピーされ、n=121バイト・ベクトル(一実施形態では、便宜上128バイトに増加される)としてメモリ内に連続的にレイアウトされる。各ウィンドウについて、以下の値が事前計算される。
【0031】
A=ΣI (式4)
B=ΣI2 (式5)
【数1】
(式6)
次いで、各潜在的合致について、以下のスカラ積が2つのウィンドウ間で計算される。
D=ΣI1I2 (式7)
次いで正規化相関は、
(nD−A1A2)C1C2 (式8)
【0032】
各潜在的合致について正規化相関が計算された後、方法400はステップ408に進み、相互の整合性に従ってどの合致を受け入れるかを決定する。この理論によれば、第1イメージ・フレーム内のあらゆるポイント・フィーチャは、(例えば最大不一致によって決定される)第2イメージ・フレームからのポイント・フィーチャとの間のいくつかの正規化相関に関係する。したがって、最高の正規化相関を生成する第2イメージ・フレームからのポイント・フィーチャが、第1フレーム内のポイント・フィーチャに対する好ましい合致として選択される。逆に、第2イメージ・フレーム内の各ポイント・フィーチャも、第1イメージ・フレームで好ましい合致を生成する。したがって、相互に好ましいマッチとして互いを指定するポイント・フィーチャの対が有効な合致として受け入れられる。上述のように、経時的なポイント・フィーチャの運動を示す軌跡を生成するために、この突合せ技法を複数のイメージ・フレームにわたって実施することができる。
方法400はステップ410で終了する。
【0033】
図5は、本発明によるフレーム間増分ポーズ推定を生成する方法500の一実施形態を示す流れ図である。様々な周知のフレーム間ポーズ推定方法のいずれかを実装して推定を生成することができ、方法500は使用することのできる例示的一方法に過ぎないことを当業者は理解されよう。方法500は、カメラの運動に対応しない移動物体または他の潜在的イメージ源の対応を含む可能性のある環境でのリアル・タイム・フレーム間ポーズ推定に特に適している。
【0034】
方法500は、例えば上記で議論した方法200のステップ210に従って実装することができる。具体的には、方法500は、単眼ビデオ入力(例えば単一の移動ビデオ・カメラからのデータ)に基づいてフレーム間増分ポーズ推定を生成する際に有用である。
【0035】
方法500はステップ502で初期化され、ステップ504に進み、ステップ504では、方法500は、(例えばナビゲーションを必要とする移動物体に取り付けられた単一のビデオ・カメラからフィードとして受領された)シーン・イメージのシーケンスの複数のフレームを通じて追跡されたポイント・フィーチャに関する複数のポイント・フィーチャ軌跡を受け取る。ステップ506では、方法500は、受け取った軌跡データに基づいて、複数のフレームの中から識別されたポイント・フィーチャに対する、ナビゲーションを必要とする物体のポーズを推定する。
【0036】
一実施形態では、ステップ506によるポーズ推定が、5点アルゴリズム(例えば、参照によりその全体が本明細書に組み込まれる2004年3月11日出願の米国特許出願第10/798726号に記載されている)およびプリエンプティブRANSACと、その後に続く反復的改善とに従って実施される。したがって、方法500は、与えられたポイント・フィーチャに基づいて、1組の可能なポーズ解または仮定を生成する。こうした仮定は、利用可能なポイント・フィーチャ軌跡のサブセットを選択することによって生成される。一実施形態では、このサブセットは、少なくとも5つの無作為に選択されたポイント・フィーチャを含む。次いで、こうした仮定のそれぞれが、利用可能なすべてのポイント・フィーチャ軌跡に対して評価され、どの仮定が最大フィーチャ軌跡数と整合するかが判定される。一実施形態では、この最高に整合する仮定が、正確である可能性が最も高いと理解される。
【0037】
ステップ508では、方法500は、ステップ506で決定した推定ポーズを使用して、観測したポイント・フィーチャ軌跡を複数の3次元(3D)ポイントに三角形分割する。一実施形態では、ポイント・フィーチャ軌跡に沿って最初および最後に観測したポイント・フィーチャを使用して三角形分割が実施される。別の実施形態では、方向誤差による最適三角形分割に従って三角形分割が実施される。一実施形態では、ステップ508が実行されるのが初めてではない場合、現在のポイント・フィーチャ軌跡結果と直前のポイント・フィーチャ軌跡結果との間の目盛係数が(例えばプリエンプティブRANSAC手続きに従って)推定される。次いで、現在のポイント・フィーチャ軌跡結果が前の結果に取って代わる。
【0038】
ステップ510では、方法500は、(例えば、ステップ504でポイント・フィーチャ軌跡を最初に受け取った時点に続いて)関連するポイント・フィーチャがいくつかの後続のフレームについて追跡されるとき、例えばビデオ入力のストリームの形の追加のポイント・フィーチャ軌跡データを受け取る。ステップ512では、方法500は、追加のポイント・フィーチャ軌跡データに基づいて、(例えばステップ508で確立された)既知の3Dポイントに対する現在のポーズを計算する。一実施形態では、3点2次元−3次元アルゴリズムおよびプリエンプティブRANSACと、その後に続く反復的改善とに従ってポーズ推定が実施される。(例えば、R.Haralick、C.Lee、K.Ottenberg、およびM.Nolle、Review and Analysis of Solutions of the Three Point Perspective Pose Estimation Problem、International Journal of Computer Vision、13(3):331−356、1994年や様々なテキストブックに記載の)1つの周知の3点アルゴリズムは、3つの3次元ワールド・ポイントに対する2次元イメージ・ポイントの対応を使用してカメラ・ポーズを推定する。
【0039】
ステップ512での既知の3次元ポイントに対するポーズ推定に続いて、方法500はステップ514に進み、新しいポイント・フィーチャ軌跡データに関して追加の3Dポイントを再三角形分割する。一実施形態では、再三角形分割は、(例えば、このとき新しいフィーチャ・ポイント軌跡データを含む)軌跡に沿って最初および最後に観測したフィーチャ・ポイントを使用して再三角形分割が実施される。次いで、方法500はステップ516に進み、ステップ510から追跡を続行すべきかどうか(例えば追加のポイント・フィーチャ軌跡データを処理すべきかどうか)を判定する。一実施形態では、ステップ510からさらなる反復を続行するかどうかに関する判定は、計算コストおよび環境的複雑さの少なくとも一方など、いくつかの応用例特有の基準のうちの1つまたは複数に従って行うことができる。例えば、上記で議論した3点ポーズ推定技法は、関連する他の方法よりも一般に計算的に複雑ではなく、したがって5点推定の数に比べて、追加の3点推定を実施することは、一般に全計算負荷を低減する。しかし、3点ポーズ推定技法の精度は、特に複雑なシーン環境では誤差を受けやすい、三角形分割された3次元ポイントの精度に直接依存する。したがって、所与の応用例についてステップ510〜514の最適な反復回数を決定するのに、応用例ごとの方法に関してこれらの考慮すべき点の平衡を取ることが一般には望ましい。しかし、一実施形態では、ステップ510からの反復回数は3に事前設定される。
【0040】
ステップ510から追跡を続行すべきであると方法500がステップ516で判定した場合、方法500はステップ510に戻り、上述と同様に進む。あるいは、ステップ510から追跡を続行すべきでないと方法500がステップ516で判定した場合、方法500はステップ518に進む。
【0041】
ステップ518では、方法500は、ステップ504から追跡を続行すべきかどうか(例えば、追加のフィーチャ軌跡データを処理すべきかどうか)を判定する。一実施形態では、処理はステップ504からいくつかの反復だけ続行する。反復回数は、運動速度やポーズおよび/または三角形分割誤差の確率などの応用例特有の基準に基づく。一実施形態では、ステップ504から実施される反復回数は3に事前設定される。ステップ504から追跡を続行すべきであると方法500がステップ518で判定した場合、方法500はステップ504に戻り、上述と同様に進む。あるいは、ステップ504から追跡を続行すべきでないと方法500がステップ518で判定した場合、方法500はステップ520に進む。
【0042】
ステップ520では、方法500は、入力データのストリームにファイアウォールを挿入し、それによって、将来の3Dポイントの三角形分割が、最新のファイアウォールに先行する観測を使用して実施されないことになる。したがって、三角形分割では、ファイアウォールの直後のシーン・イメージのシーケンスのフレームが第1フレームと見なされる。言い換えれば、先行する反復に対して使用される3次元ポイントが廃棄され、完全に新しい1組の3次元ポイントが推定される。これは、方法500の実行全体を通して、(例えば3Dポイント位置決め、ポーズ推定などでの)誤差の伝播を低減する助けになる。次いで方法500はステップ504に戻り、上述と同様に進む。
【0043】
図6は、本発明によるフレーム間増分ポーズ推定を生成する方法600の第2実施形態を示す流れ図である。方法500と同様に、方法600は、上記で議論した方法200のステップ210に従って実装することができる。しかし、方法500とは対照的に、方法600は、ステレオ・ビデオ(例えば、較正された1対のビデオ・カメラからのデータ)に基づいてフレーム間増分ポーズ推定を生成する際に有用である。
【0044】
方法600はステップ602で初期化され、ステップ604に進み、ステップ604では、方法600は、(例えば、移動車両またはロボットに取り付けられた2つの移動ビデオ・カメラからの個々のフィードで実施される)ポイント・フィーチャ軌跡を受け取る。ポイント・フィーチャ軌跡は、(例えば左のビデオ・カメラと右のビデオ・カメラから見た)同一のポイント・フィーチャ軌跡の異なるパースペクティブを提示する2つの異なるビューから受領される。方法600はステップ606に進み、着信するイメージまたはシーン・イメージのシーケンスで提示される2つのビュー間でポイント・フィーチャを突き合わせる。
【0045】
ステップ608では、方法600は、ステレオ較正データの知識を使用して、ステップ606で確立された合致を3Dポイントに三角形分割する。次いで、ステップ610で追加のポイント・フィーチャ軌跡データを受け取る。
【0046】
ステップ612では、方法600は、受け取ったポイント・フィーチャ軌跡データに基づいて、シーン・イメージのシーケンスの複数のフレーム間の、(例えばステレオ・ヘッドが取り付けられた)ナビゲーションを必要とする物体の相対的ポーズを推定する。一実施形態では、ステップ612によるポーズ推定が、(例えば上記で議論したように、例えば左イメージからのフィーチャを用いる)3点アルゴリズムおよびプリエンプティブRANSACと、その後に続く左イメージと右イメージの両方におけるフィーチャに基づく反復的改善とに従って実施される。したがって、方法600は、与えられたフィーチャ・ポイントに基づいて、1組の可能なポーズ解または仮定を生成する。こうした仮定は、利用可能なフィーチャ軌跡のサブセットを選択することによって生成される。一実施形態では、このサブセットは、少なくとも3つの無作為に選択されたフィーチャ軌跡を含む。次いで、こうした仮定のそれぞれが、利用可能なすべてのフィーチャ軌跡に対して評価され、(例えばすべてのフィーチャとの最大の整合性に基づいて)どの仮定が正確である可能性が最も高いかが判定される。
【0047】
ステップ614では、方法600は、ステップ610から追跡を続行すべきかどうか(例えば、追加のポイント・フィーチャ軌跡データを処理すべきかどうか)を判定する。上記で議論したように、この判定は応用例特有の基準に基づいて行うことができ、または固定の回数だけ反復を実施することができる。ステップ610から追跡を続行すべきであると方法600がステップ614で判定した場合、方法600はステップ610に戻り、上述と同様に進む。あるいは、ステップ610から追跡を続行すべきでないと方法600がステップ614で判定した場合、方法600はステップ616に進む。
【0048】
ステップ616では、方法600は、左イメージおよび右イメージでの観測に従って、すべての新しいポイント・フィーチャ合致を三角形分割する。次いで、方法600はステップ618に進み、ステップ610から追跡を続行すべきかどうかを判定する。上記で議論したように、この判定は応用例特有の基準に基づいて行うことができ、または固定の回数だけ反復を実施することができる。ステップ610から追跡を続行すべきであると方法600がステップ618で判定した場合、方法600はステップ610に戻り、上述と同様に進む。あるいは、ステップ610から追跡を続行すべきでないと方法600がステップ618で判定した場合、方法600はステップ620に進む。
【0049】
ステップ620では、方法600は、すべての既存の3Dポイントを廃棄し、新しいポイント・フィーチャ軌跡データに基づいてすべての3Dポイントを再三角形分割し、したがって入力データのストリームにファイアウォールを挿入し、それによって、将来の3Dポイントの三角形分割が、最新のファイアウォールに先行する観測を使用して実施されないことになる。次いで、方法600はステップ610に戻り、前述と同様に進む。
【0050】
図7は、汎用コンピューティング装置700を使用して実施されるビジュアル・オドメトリ方法の高レベル・ブロック図である。一実施形態では、汎用コンピューティング装置700は、プロセッサ702、メモリ704、ビジュアル・オドメトリ・モジュール705、およびディスプレイ、キーボード、マウス、モデムなどの様々な入出力(I/O)装置706を備えることができる。一実施形態では、少なくとも1つのI/O装置は記憶装置(例えばディスク・ドライブ、光ディスク・ドライブ、フロッピィ・ディスク・ドライブ)である。通信チャネルを介してプロセッサに結合された物理的装置またはサブシステムとしてビジュアル・オドメトリ・モジュール705を実装できることを理解されたい。
【0051】
あるいは、ビジュアル・オドメトリ・モジュール705は、1つまたは複数のソフトウェア・アプリケーション(さらには、ソフトウェアと、例えば特定用途向け集積回路(ASIC)を用いたハードウェアとの組合せ)で表すことができる。その場合ソフトウェアは、記憶媒体(例えばI/O装置706)からロードされ、汎用コンピューティング装置700のメモリ704内でプロセッサ702によって操作される。したがって、一実施形態では、上記の図を参照しながら本明細書で説明した運動および位置を推定するビジュアル・オドメトリ・モジュール705を、コンピュータ可読媒体またはキャリア(例えばRAM、磁気または光ドライブまたはディスケットなど)上に格納することができる。
【0052】
別の実施形態では、ビジュアル・オドメトリを従来のナビゲーション装置(GPS、慣性測定ユニット、コンパスなど)と組み合わせる統合検出装置として本発明を実装することができる。そのような実施形態では、ビジュアル・オドメトリで生成された6自由度運動推定が、従来のセンサで生成された推定を補正するのに使用され、逆も同様である。したがって、この統合システムは、利用可能なすべてのセンサ入力を組み込む単一ナビゲーション解を生成することができる。このようなシステムの従来装置に勝る利点は、統合ナビゲーション・システムが、ビジュアル入力単独、またはより正確かつ安定した位置確認のために追加のセンサ入力で補足されたビジュアル入力を操作できることである。
【0053】
したがって、本発明は、自律的ナビゲーションの分野での著しい進歩を表す。移動物体(例えば自律的車両またはロボット)が周囲環境の性質の如何に関わらず周囲の環境の中をナビゲートすることを可能にする方法および装置が提供される。ほぼどんな環境または条件でも得ることのできるビデオ・データを主に処理することにより、位置および運動を正確に推定することができる。次いで、任意選択で、自律的ナビゲーション・システムで通常使用されているような追加の環境特有のセンサからのデータを使用して、ビデオ・データから導出された推定を補足することができる。
【0054】
上記は本発明の実施形態を対象とするものであるが、本発明の基本的範囲から逸脱することなく、本発明の別の実施形態を考案することができ、本発明の範囲は、添付の特許請求の範囲によって決定される。
【図面の簡単な説明】
【0055】
【図1】本発明によるビジュアル・オドメトリのための方法の一実施形態を示す流れ図である。
【図2】本発明によるビデオ・データから運動推定および/または位置推定を導出する方法の一実施形態を示す流れ図である。
【図3】ポイント・フィーチャ検出のための方法の一実施形態を示す流れ図である。
【図4】ポイント・フィーチャ整合のための方法の一実施形態を示す流れ図である。
【図5】本発明によるフレーム間増分ポーズ推定を生成する方法の一実施形態を示す流れ図である。
【図6】本発明によるフレーム間増分ポーズ推定を生成する方法の第2実施形態を示す流れ図である。
【図7】汎用コンピューティング装置を使用して実施されるビジュアル・オドメトリ方法の高レベル・ブロック図である。
【図8】シーン・イメージのシーケンスから取られた例示的フレームであり、その中で複数のポイント・フィーチャの位置が円で突き止められている図である。
【背景技術】
【0001】
関連出願への相互参照
本願は、参照により本明細書にその全体が組み込まれる2004年6月22日出願の米国仮特許出願第60/581867号の特典を主張するものである。
【0002】
政府資金援助への参照
本発明は、DARPA(Defense Advanced Research Projects Agency) によって与えられた交付番号MDA972−01−9−0016の下で政府援助を伴ってなされたものである。政府は、本発明における一定の権利を有する。
【0003】
様々な応用例におけるコンピュータ・ビジョン・システムの有用性が認められている。例えば、(例えば車両用およびロボット用の)自律ナビゲーション・システムは、周囲の環境内での障害物検出およびナビゲーションのためにそのようなシステムを大いに利用する。そのようなシステムは、人間のオペレータを危険にさらすことなく、難しい地帯または危険な地帯のナビゲーションおよび/または監視を可能にする。
【0004】
しかし、自律的ナビゲーション用のほとんどの既存のシステムは、一般に環境特有のものであるという点で汎用性に欠けている。例えば、GPSベースのナビゲーション・システムは、屋外環境では良好に動作するが、屋内での動作が不十分である。ホイール・エンコーダからの情報を利用するナビゲーション・システムは、地上車両で実装したときは良好に動作するが、例えば航空機での使用には適していない。さらに、ビデオまたはイメージ・データを解析することによって動作するほとんどの既存のシステムは、過去の運動の知識を提供することができるが、現在の運動および/または位置の(例えばリアル・タイムの)知識を適時に提供することができない。
【特許文献1】米国仮特許出願第60/581867号
【非特許文献1】C.HarrisおよびM.Stephens、A Combined Corner and Edge Detector (Proc.Fourth Alvey Vision Conference、pp.147−151、1988年)
【非特許文献2】D.Nister、Preemptive RANSAC for Live Structure and Motion Estimation、IEEE International Conference on Computer Vision、pp.199−206、2003年
【特許文献2】米国特許出願第10/798726号
【非特許文献3】R.Haralick、C.Lee、K.Ottenberg、およびM.Nolle、Review and Analysis of Solutions of the Three Point Perspective Pose Estimation Problem、International Journal of Computer Vision、13(3):331−356、1994年
【発明の開示】
【発明が解決しようとする課題】
【0005】
したがって、環境に無関係であり、ほぼリアル・タイムで運動推定および/または位置推定を確実に提供することのできるビジュアル・オドメトリのための方法および装置が当技術分野で求められている。
【課題を解決するための手段】
【0006】
(例えば周囲の環境の中をナビゲートする)ビジュアル・オドメトリのための方法および装置が開示される。一実施形態では、周囲の環境の少なくとも一部を表すシーン・イメージのシーケンスが(例えばビデオ・カメラまたはステレオ・ヘッドから)受領される。シーン・イメージのシーケンスが(例えばビデオ処理技法に従って)処理され、周囲の環境に対するポーズの推定が導出される。この推定は、グローバル・ポジショニング・システム、あるいは慣性センサまたは機械センサなどの他のセンサからのデータでさらに補足することができる。
【0007】
上述の本発明の特徴を詳細に理解できるように、添付の図面にその一部が図示される実施形態を参照することにより、上記で簡潔に要約される本発明のより具体的な説明を得ることができる。しかし、添付の図面は本発明の典型的な実施形態を示すに過ぎず、したがって、本発明は同様に効果的な他の実施形態を認めることができるので、添付の図面を本発明の範囲の制限と見なすべきでないことに留意されたい。
【発明を実施するための最良の形態】
【0008】
本発明は、(例えば、自律的車両またはロボットなどの移動物体の自律的ナビゲーション用の)ビジュアル・オドメトリのための方法および装置を開示する。従来の自律的ナビゲーション・システムとは異なり、一実施形態では、本発明は、主にビデオ・データを利用して物体の位置推定および運動推定を導出する。したがって、本発明による自律的ナビゲーションは実質上、環境に無関係である。自律的ナビゲーション・システムで通常使用されるような環境特有のセンサは主に、ビデオ・ベースの推定を補足するためのデータを得るための任意選択手段として働く。
【0009】
図1は、本発明によるビジュアル・オドメトリのための方法100の一実施形態を示す流れ図である。方法100は、例えば、自律的(例えば無人の)車両またはロボットなどのナビゲーションを必要とする物体で実装することができる。方法100はステップ102で初期化され、ステップ104に進み、ステップ104では、方法100は、周囲の環境の少なくとも一部を表すシーン・イメージのシーケンスを受け取る。一実施形態では、ナビゲーションを必要とする物体に取り付けられた移動カメラまたはステレオ・ヘッドを介してこのシーン・イメージのシーケンスを受け取ることができる。
【0010】
ステップ106では、方法100は、シーン・イメージのシーケンスを処理し、それから位置推定を導出する。すなわち、方法100は、受け取ったシーン・イメージのシーケンスから直接、ナビゲーションを必要とする物体の現在位置を推定する。一実施形態では、シーン・イメージのシーケンスが、ビデオ処理のための任意の適切な周知の方法に従って処理される。
【0011】
位置推定をシーン・イメージのシーケンスから導出した後、任意選択で、方法100はステップ108に進み、追加のデータで位置推定を補足する。したがって、この実施形態では、ステップ106で導出されたビデオ・ベースの位置推定を、その後で他のソースからデータを取り入れることによって改善される予備推定と見なすことができる。一実施形態では、この追加のデータは、GPSシステム、慣性センサ、および機械センサ(例えばホイール・エンコーダ)のうちの少なくとも1つなどの、少なくとも1つの追加のセンサで与えられるデータを含む。
【0012】
(追加のデータを用いて、または追加のデータを用いずに)位置推定を導出した後、方法100はステップ110で終了する。
それによって方法100は、方法100が機能する環境とは無関係な、迅速で正確な運動推定および位置推定を可能にする。方法100は主に(ある場合には専ら)ビデオ・データを利用して運動推定および位置推定を導出するので、ほぼ任意の場所、すなわち屋外、屋内、地上、空中などで利用するように実装することができる。
【0013】
図2は、本発明によるビデオ・データから運動推定および/または位置推定を導出する方法200の一実施形態を示す流れ図である。上記で議論した方法100のステップ106に従って方法200を実装して、ナビゲーションを必要とする車両、ロボットなどの運動または位置のビデオ・ベースの推定を生成することができる。
【0014】
方法200はステップ202で初期化され、ステップ204に進み、ステップ204では、方法200は、シーン・イメージのシーケンスの現フレーム内のポイント・フィーチャの位置を突き止める。一実施形態では、突き止めたポイント・フィーチャは、小さなイメージひずみから中程度のイメージひずみの下で比較的安定すると予想されるフィーチャである。例えば、一実施形態では、ポイント・フィーチャは、C.HarrisおよびM.Stephens、A Combined Corner and Edge Detector (Proc.Fourth Alvey Vision Conference、pp.147−151、1988年)に記載されているハリス・コーナである。ポイント・フィーチャは、確実に追跡することのできるフレームの任意の識別可能な要素でよい。一実施形態では、最大数百個のポイント・フィーチャの位置がステップ202で突き止められる。例えば、図8は、シーン・イメージのシーケンスから取られた例示的フレーム800であり、その中で複数のポイント・フィーチャの位置が円で突き止められている。話を簡単にするために、これらの円で囲まれたポイント・フィーチャのうちの一部だけに802と符号を付ける。
【0015】
ステップ206では、方法200は、ステップ204で位置が突き止められたポイント・フィーチャを(例えば、フィーチャを、後続のフレーム内の対応するフィーチャと突き合わせることによって)複数の後続のフレームにわたって追跡する。一実施形態では、ポイント・フィーチャは、フィーチャが視野内にとどまる限り追跡される。一実施形態では、幾何学的制約なしに追跡が実施される。
【0016】
ステップ208では、方法200は、ステップ206で得られたフィーチャ追跡データに基づいて1組の軌跡を生成する。軌跡は、ナビゲーションを必要とする物体に対する、追跡したフィーチャの位置および/または向きの経時的な変化を表す。一実施形態では、突き合わせたフィーチャが基本的にフレーム間でリンクされる。再び図8を参照すると、図示されている複数の軌跡(その一部に804と符号を付けてある)は、関連するポイント・フィーチャの以前の相対運動を示す。
【0017】
軌跡の組を確立した後、方法200はステップ210に進み、ポイント・フィーチャ軌跡で伝えられた情報に基づいて、ナビゲーションを必要とする車両、ロボットなどについての複数の増分フレーム間ポーズ推定を生成する。一実施形態では、「ポーズ」が6つの自由度で推定され、3次元(例えばx、y、z座標)位置と角度方向として定義される。一実施形態では、幾何学的推定方法に従ってポーズ推定が生成される。ポーズ推定を生成する幾何学的推定方法は、シーン・イメージの元のシーケンスをキャプチャする手段に応じて変化する可能性がある(例えば、単眼ビデオ入力、ステレオ入力など)。
【0018】
ステップ212では、方法200は、ポーズ推定を評価し、最も可能性の高い推定を、現在のポーズを示すものとして選択する。一実施形態では、ポーズ推定の評価は、以下でより詳細に議論するように、周知のRANSAC(random sample consensus)技法(例えば、D.Nister、Preemptive RANSAC for Live Structure and Motion Estimation、IEEE International Conference on Computer Vision、pp.199−206、2003年で論じられている)に従って実施される。
方法200はステップ214で終了する。
【0019】
図3は、例えば方法200のステップ204による、ポイント・フィーチャ検出のための方法300の一実施形態を示す流れ図である。方法300はステップ302で初期化され、ステップ304に進み、ステップ304では、方法300は、解析中のシーン・イメージのシーケンスからイメージ・フレームを取り出す。一実施形態では、イメージ・フレームが、ピクセル当たり約8ビットで表される。
【0020】
ステップ306では、方法300は、フレームのコーナ応答の強度sを計算する。例えば、一実施形態では、ハリス・コーナ検出器は、イメージ勾配から計算される局所平均モーメント行列を計算する。次いで、モーメント行列の固有値が組み合わされ、コーナ応答または「強度」が計算される。その最大値がコーナ位置を示す。
【0021】
(例えば汎用コンピュータを使用する)非常に効率的な計算のために設計された一実施形態では、sが以下のように計算される。コーナ応答の出力ラインごとに、現出力ラインの上または下のいくつかのラインに関して一時フィルタ出力が必要である。すべてのフィルタ出力が一度だけ計算され、最適なキャッシュ性能のためにラップアラウンド・バッファに格納される。ラップアラウンド・バッファは、ローリング・ウィンドウでの一時フィルタ出力を表す。ローリング・ウィンドウは、何らかのフィルタ出力の再計算を回避するために必要な最低限の数のラインを含む。
【0022】
例えば、一実施形態では、イメージ・フレームの水平方向微分および垂直方向微分が、それぞれIxおよびIyと表される。一実施形態では、IxおよびIyがタイプ[−1 0 1]の水平フィルタおよび垂直フィルタによって計算され、入力を8ビットだけ下に、出力を16ビットだけ下に保つために、乗算を実行する前に1ビットだけ下にシフトされる。
【0023】
この場合、ラップアラウンド・バッファおよび得られるコーナ応答が、ラインごとに4つの「掃引」を使用して、ラインごとに更新される。第1掃引は、IxIx、IxIy、およびIyIyについてのラップアラウンド・バッファを更新する。一実施形態では、IxIx、IxIy、およびIyIyについてのラップアラウンド・バッファはライン5本分であり、典型的な掃引は、コーナ応答の現在の出力ラインより2つ先に位置する1つのラインを更新する。
【0024】
第2掃引は、32ビット・フィルタ出力の3つの単一ラインgxx、gxy、およびgyyを生成するために、2項フィルタ(例えば[1 4 6 4 1])でラップアラウンド・バッファ内のすべてのラインを垂直方向にコンボルブする。一実施形態では、このことは、コストのかかる乗算を回避するためにシフトおよび加算で実施される。
【0025】
第3掃引は、第2掃引で使用されたのと同じ2項フィルタで水平方向にコンボルブし、32ビット単一ラインGxx、Gxy、Gxyを生成する。Gxx、Gxy、Gxyは、gxx、gxy、およびgyyと同じ場所に格納されるが、2ピクセルだけシフトされる。
【0026】
最後に、第4掃引は、コーナ応答の
行列式d=GxxGyy−GxyGxy (式1)
トレースt=Gxx+Gyy (式2)
および強度s=d−kt2 (式3)
を浮動小数点で計算する(ただしk=0.06)。一実施形態では、第1掃引から第4掃引はすべて、128ピクセルのマルチメディア・エクステンション(MMX)チャンクで実装され、ストールを回避し、両方のパイプラインを最適に用いるために、手動でインターリーブされる。
【0027】
図3に戻ると、コーナ応答の強度を計算した後、方法300はステップ310に進み、計算したコーナ応答強度に従って、イメージ・フレーム内のポイント・フィーチャを定義する。上述のように、単一のイメージ・フレーム内に数百ものポイント・フィーチャを定義することができる。一実施形態では、ポイント・フィーチャの定義は、非最大抑制技法(non−maximum suppression technique)に従って達成される。具体的には、コーナ応答が定義された半径(例えば5ピクセルごとの近傍)内で他のすべてのピクセルよりも強いと計算される各ピクセルで、ポイント・フィーチャが宣言される。
方法300はステップ312で終了する。
【0028】
図4は、例えばステップ206による、ポイント・フィーチャ整合のための方法400の一実施形態を示す流れ図である。方法400はステップ402で初期化され、ステップ404に進み、ステップ404では、方法400は、第1フレーム内の所与のポイント・フィーチャを第2フレーム内の対応するポイント・フィーチャから固定の距離以内のあらゆるポイント・フィーチャと突き合わせることを試みる(例えば、互いの事前定義された不一致限界以内のすべてのポイント・フィーチャが突き合わされる)。一実施形態では、ポイント・フィーチャ合致に関する不一致限界は、所望の出力速度およびシーン・イメージの入力シーケンスの平滑度に応じて、イメージ・サイズの約3から30パーセントである。
【0029】
方法400の次の段階は、フレーム間フィーチャ対応を確立する。このフレーム間フィーチャ対応は、オプティカル・フロー技法およびエリア相関技法を含む様々な周知の方法に従って確立することができる。ステップ406〜408は、(汎用コンピュータ上の)計算速度に関して最適化された、フレーム間フィーチャ対応を確立する1つの例示的プロセスを示す。
【0030】
ステップ406では、方法400は、正規化相関を使用して第1フレームと第2フレームの間の潜在的ポイント・フィーチャ合致を評価する。一実施形態では、正規化相関は、検出されたポイント・フィーチャ上に中心が置かれた11ピクセル四方のウィンドウにわたって実施される。一実施形態では、速度に関してウィンドウ全体にわたって一様な重み付けが使用される。各ウィンドウがイメージ・フレームからコピーされ、n=121バイト・ベクトル(一実施形態では、便宜上128バイトに増加される)としてメモリ内に連続的にレイアウトされる。各ウィンドウについて、以下の値が事前計算される。
【0031】
A=ΣI (式4)
B=ΣI2 (式5)
【数1】
(式6)
次いで、各潜在的合致について、以下のスカラ積が2つのウィンドウ間で計算される。
D=ΣI1I2 (式7)
次いで正規化相関は、
(nD−A1A2)C1C2 (式8)
【0032】
各潜在的合致について正規化相関が計算された後、方法400はステップ408に進み、相互の整合性に従ってどの合致を受け入れるかを決定する。この理論によれば、第1イメージ・フレーム内のあらゆるポイント・フィーチャは、(例えば最大不一致によって決定される)第2イメージ・フレームからのポイント・フィーチャとの間のいくつかの正規化相関に関係する。したがって、最高の正規化相関を生成する第2イメージ・フレームからのポイント・フィーチャが、第1フレーム内のポイント・フィーチャに対する好ましい合致として選択される。逆に、第2イメージ・フレーム内の各ポイント・フィーチャも、第1イメージ・フレームで好ましい合致を生成する。したがって、相互に好ましいマッチとして互いを指定するポイント・フィーチャの対が有効な合致として受け入れられる。上述のように、経時的なポイント・フィーチャの運動を示す軌跡を生成するために、この突合せ技法を複数のイメージ・フレームにわたって実施することができる。
方法400はステップ410で終了する。
【0033】
図5は、本発明によるフレーム間増分ポーズ推定を生成する方法500の一実施形態を示す流れ図である。様々な周知のフレーム間ポーズ推定方法のいずれかを実装して推定を生成することができ、方法500は使用することのできる例示的一方法に過ぎないことを当業者は理解されよう。方法500は、カメラの運動に対応しない移動物体または他の潜在的イメージ源の対応を含む可能性のある環境でのリアル・タイム・フレーム間ポーズ推定に特に適している。
【0034】
方法500は、例えば上記で議論した方法200のステップ210に従って実装することができる。具体的には、方法500は、単眼ビデオ入力(例えば単一の移動ビデオ・カメラからのデータ)に基づいてフレーム間増分ポーズ推定を生成する際に有用である。
【0035】
方法500はステップ502で初期化され、ステップ504に進み、ステップ504では、方法500は、(例えばナビゲーションを必要とする移動物体に取り付けられた単一のビデオ・カメラからフィードとして受領された)シーン・イメージのシーケンスの複数のフレームを通じて追跡されたポイント・フィーチャに関する複数のポイント・フィーチャ軌跡を受け取る。ステップ506では、方法500は、受け取った軌跡データに基づいて、複数のフレームの中から識別されたポイント・フィーチャに対する、ナビゲーションを必要とする物体のポーズを推定する。
【0036】
一実施形態では、ステップ506によるポーズ推定が、5点アルゴリズム(例えば、参照によりその全体が本明細書に組み込まれる2004年3月11日出願の米国特許出願第10/798726号に記載されている)およびプリエンプティブRANSACと、その後に続く反復的改善とに従って実施される。したがって、方法500は、与えられたポイント・フィーチャに基づいて、1組の可能なポーズ解または仮定を生成する。こうした仮定は、利用可能なポイント・フィーチャ軌跡のサブセットを選択することによって生成される。一実施形態では、このサブセットは、少なくとも5つの無作為に選択されたポイント・フィーチャを含む。次いで、こうした仮定のそれぞれが、利用可能なすべてのポイント・フィーチャ軌跡に対して評価され、どの仮定が最大フィーチャ軌跡数と整合するかが判定される。一実施形態では、この最高に整合する仮定が、正確である可能性が最も高いと理解される。
【0037】
ステップ508では、方法500は、ステップ506で決定した推定ポーズを使用して、観測したポイント・フィーチャ軌跡を複数の3次元(3D)ポイントに三角形分割する。一実施形態では、ポイント・フィーチャ軌跡に沿って最初および最後に観測したポイント・フィーチャを使用して三角形分割が実施される。別の実施形態では、方向誤差による最適三角形分割に従って三角形分割が実施される。一実施形態では、ステップ508が実行されるのが初めてではない場合、現在のポイント・フィーチャ軌跡結果と直前のポイント・フィーチャ軌跡結果との間の目盛係数が(例えばプリエンプティブRANSAC手続きに従って)推定される。次いで、現在のポイント・フィーチャ軌跡結果が前の結果に取って代わる。
【0038】
ステップ510では、方法500は、(例えば、ステップ504でポイント・フィーチャ軌跡を最初に受け取った時点に続いて)関連するポイント・フィーチャがいくつかの後続のフレームについて追跡されるとき、例えばビデオ入力のストリームの形の追加のポイント・フィーチャ軌跡データを受け取る。ステップ512では、方法500は、追加のポイント・フィーチャ軌跡データに基づいて、(例えばステップ508で確立された)既知の3Dポイントに対する現在のポーズを計算する。一実施形態では、3点2次元−3次元アルゴリズムおよびプリエンプティブRANSACと、その後に続く反復的改善とに従ってポーズ推定が実施される。(例えば、R.Haralick、C.Lee、K.Ottenberg、およびM.Nolle、Review and Analysis of Solutions of the Three Point Perspective Pose Estimation Problem、International Journal of Computer Vision、13(3):331−356、1994年や様々なテキストブックに記載の)1つの周知の3点アルゴリズムは、3つの3次元ワールド・ポイントに対する2次元イメージ・ポイントの対応を使用してカメラ・ポーズを推定する。
【0039】
ステップ512での既知の3次元ポイントに対するポーズ推定に続いて、方法500はステップ514に進み、新しいポイント・フィーチャ軌跡データに関して追加の3Dポイントを再三角形分割する。一実施形態では、再三角形分割は、(例えば、このとき新しいフィーチャ・ポイント軌跡データを含む)軌跡に沿って最初および最後に観測したフィーチャ・ポイントを使用して再三角形分割が実施される。次いで、方法500はステップ516に進み、ステップ510から追跡を続行すべきかどうか(例えば追加のポイント・フィーチャ軌跡データを処理すべきかどうか)を判定する。一実施形態では、ステップ510からさらなる反復を続行するかどうかに関する判定は、計算コストおよび環境的複雑さの少なくとも一方など、いくつかの応用例特有の基準のうちの1つまたは複数に従って行うことができる。例えば、上記で議論した3点ポーズ推定技法は、関連する他の方法よりも一般に計算的に複雑ではなく、したがって5点推定の数に比べて、追加の3点推定を実施することは、一般に全計算負荷を低減する。しかし、3点ポーズ推定技法の精度は、特に複雑なシーン環境では誤差を受けやすい、三角形分割された3次元ポイントの精度に直接依存する。したがって、所与の応用例についてステップ510〜514の最適な反復回数を決定するのに、応用例ごとの方法に関してこれらの考慮すべき点の平衡を取ることが一般には望ましい。しかし、一実施形態では、ステップ510からの反復回数は3に事前設定される。
【0040】
ステップ510から追跡を続行すべきであると方法500がステップ516で判定した場合、方法500はステップ510に戻り、上述と同様に進む。あるいは、ステップ510から追跡を続行すべきでないと方法500がステップ516で判定した場合、方法500はステップ518に進む。
【0041】
ステップ518では、方法500は、ステップ504から追跡を続行すべきかどうか(例えば、追加のフィーチャ軌跡データを処理すべきかどうか)を判定する。一実施形態では、処理はステップ504からいくつかの反復だけ続行する。反復回数は、運動速度やポーズおよび/または三角形分割誤差の確率などの応用例特有の基準に基づく。一実施形態では、ステップ504から実施される反復回数は3に事前設定される。ステップ504から追跡を続行すべきであると方法500がステップ518で判定した場合、方法500はステップ504に戻り、上述と同様に進む。あるいは、ステップ504から追跡を続行すべきでないと方法500がステップ518で判定した場合、方法500はステップ520に進む。
【0042】
ステップ520では、方法500は、入力データのストリームにファイアウォールを挿入し、それによって、将来の3Dポイントの三角形分割が、最新のファイアウォールに先行する観測を使用して実施されないことになる。したがって、三角形分割では、ファイアウォールの直後のシーン・イメージのシーケンスのフレームが第1フレームと見なされる。言い換えれば、先行する反復に対して使用される3次元ポイントが廃棄され、完全に新しい1組の3次元ポイントが推定される。これは、方法500の実行全体を通して、(例えば3Dポイント位置決め、ポーズ推定などでの)誤差の伝播を低減する助けになる。次いで方法500はステップ504に戻り、上述と同様に進む。
【0043】
図6は、本発明によるフレーム間増分ポーズ推定を生成する方法600の第2実施形態を示す流れ図である。方法500と同様に、方法600は、上記で議論した方法200のステップ210に従って実装することができる。しかし、方法500とは対照的に、方法600は、ステレオ・ビデオ(例えば、較正された1対のビデオ・カメラからのデータ)に基づいてフレーム間増分ポーズ推定を生成する際に有用である。
【0044】
方法600はステップ602で初期化され、ステップ604に進み、ステップ604では、方法600は、(例えば、移動車両またはロボットに取り付けられた2つの移動ビデオ・カメラからの個々のフィードで実施される)ポイント・フィーチャ軌跡を受け取る。ポイント・フィーチャ軌跡は、(例えば左のビデオ・カメラと右のビデオ・カメラから見た)同一のポイント・フィーチャ軌跡の異なるパースペクティブを提示する2つの異なるビューから受領される。方法600はステップ606に進み、着信するイメージまたはシーン・イメージのシーケンスで提示される2つのビュー間でポイント・フィーチャを突き合わせる。
【0045】
ステップ608では、方法600は、ステレオ較正データの知識を使用して、ステップ606で確立された合致を3Dポイントに三角形分割する。次いで、ステップ610で追加のポイント・フィーチャ軌跡データを受け取る。
【0046】
ステップ612では、方法600は、受け取ったポイント・フィーチャ軌跡データに基づいて、シーン・イメージのシーケンスの複数のフレーム間の、(例えばステレオ・ヘッドが取り付けられた)ナビゲーションを必要とする物体の相対的ポーズを推定する。一実施形態では、ステップ612によるポーズ推定が、(例えば上記で議論したように、例えば左イメージからのフィーチャを用いる)3点アルゴリズムおよびプリエンプティブRANSACと、その後に続く左イメージと右イメージの両方におけるフィーチャに基づく反復的改善とに従って実施される。したがって、方法600は、与えられたフィーチャ・ポイントに基づいて、1組の可能なポーズ解または仮定を生成する。こうした仮定は、利用可能なフィーチャ軌跡のサブセットを選択することによって生成される。一実施形態では、このサブセットは、少なくとも3つの無作為に選択されたフィーチャ軌跡を含む。次いで、こうした仮定のそれぞれが、利用可能なすべてのフィーチャ軌跡に対して評価され、(例えばすべてのフィーチャとの最大の整合性に基づいて)どの仮定が正確である可能性が最も高いかが判定される。
【0047】
ステップ614では、方法600は、ステップ610から追跡を続行すべきかどうか(例えば、追加のポイント・フィーチャ軌跡データを処理すべきかどうか)を判定する。上記で議論したように、この判定は応用例特有の基準に基づいて行うことができ、または固定の回数だけ反復を実施することができる。ステップ610から追跡を続行すべきであると方法600がステップ614で判定した場合、方法600はステップ610に戻り、上述と同様に進む。あるいは、ステップ610から追跡を続行すべきでないと方法600がステップ614で判定した場合、方法600はステップ616に進む。
【0048】
ステップ616では、方法600は、左イメージおよび右イメージでの観測に従って、すべての新しいポイント・フィーチャ合致を三角形分割する。次いで、方法600はステップ618に進み、ステップ610から追跡を続行すべきかどうかを判定する。上記で議論したように、この判定は応用例特有の基準に基づいて行うことができ、または固定の回数だけ反復を実施することができる。ステップ610から追跡を続行すべきであると方法600がステップ618で判定した場合、方法600はステップ610に戻り、上述と同様に進む。あるいは、ステップ610から追跡を続行すべきでないと方法600がステップ618で判定した場合、方法600はステップ620に進む。
【0049】
ステップ620では、方法600は、すべての既存の3Dポイントを廃棄し、新しいポイント・フィーチャ軌跡データに基づいてすべての3Dポイントを再三角形分割し、したがって入力データのストリームにファイアウォールを挿入し、それによって、将来の3Dポイントの三角形分割が、最新のファイアウォールに先行する観測を使用して実施されないことになる。次いで、方法600はステップ610に戻り、前述と同様に進む。
【0050】
図7は、汎用コンピューティング装置700を使用して実施されるビジュアル・オドメトリ方法の高レベル・ブロック図である。一実施形態では、汎用コンピューティング装置700は、プロセッサ702、メモリ704、ビジュアル・オドメトリ・モジュール705、およびディスプレイ、キーボード、マウス、モデムなどの様々な入出力(I/O)装置706を備えることができる。一実施形態では、少なくとも1つのI/O装置は記憶装置(例えばディスク・ドライブ、光ディスク・ドライブ、フロッピィ・ディスク・ドライブ)である。通信チャネルを介してプロセッサに結合された物理的装置またはサブシステムとしてビジュアル・オドメトリ・モジュール705を実装できることを理解されたい。
【0051】
あるいは、ビジュアル・オドメトリ・モジュール705は、1つまたは複数のソフトウェア・アプリケーション(さらには、ソフトウェアと、例えば特定用途向け集積回路(ASIC)を用いたハードウェアとの組合せ)で表すことができる。その場合ソフトウェアは、記憶媒体(例えばI/O装置706)からロードされ、汎用コンピューティング装置700のメモリ704内でプロセッサ702によって操作される。したがって、一実施形態では、上記の図を参照しながら本明細書で説明した運動および位置を推定するビジュアル・オドメトリ・モジュール705を、コンピュータ可読媒体またはキャリア(例えばRAM、磁気または光ドライブまたはディスケットなど)上に格納することができる。
【0052】
別の実施形態では、ビジュアル・オドメトリを従来のナビゲーション装置(GPS、慣性測定ユニット、コンパスなど)と組み合わせる統合検出装置として本発明を実装することができる。そのような実施形態では、ビジュアル・オドメトリで生成された6自由度運動推定が、従来のセンサで生成された推定を補正するのに使用され、逆も同様である。したがって、この統合システムは、利用可能なすべてのセンサ入力を組み込む単一ナビゲーション解を生成することができる。このようなシステムの従来装置に勝る利点は、統合ナビゲーション・システムが、ビジュアル入力単独、またはより正確かつ安定した位置確認のために追加のセンサ入力で補足されたビジュアル入力を操作できることである。
【0053】
したがって、本発明は、自律的ナビゲーションの分野での著しい進歩を表す。移動物体(例えば自律的車両またはロボット)が周囲環境の性質の如何に関わらず周囲の環境の中をナビゲートすることを可能にする方法および装置が提供される。ほぼどんな環境または条件でも得ることのできるビデオ・データを主に処理することにより、位置および運動を正確に推定することができる。次いで、任意選択で、自律的ナビゲーション・システムで通常使用されているような追加の環境特有のセンサからのデータを使用して、ビデオ・データから導出された推定を補足することができる。
【0054】
上記は本発明の実施形態を対象とするものであるが、本発明の基本的範囲から逸脱することなく、本発明の別の実施形態を考案することができ、本発明の範囲は、添付の特許請求の範囲によって決定される。
【図面の簡単な説明】
【0055】
【図1】本発明によるビジュアル・オドメトリのための方法の一実施形態を示す流れ図である。
【図2】本発明によるビデオ・データから運動推定および/または位置推定を導出する方法の一実施形態を示す流れ図である。
【図3】ポイント・フィーチャ検出のための方法の一実施形態を示す流れ図である。
【図4】ポイント・フィーチャ整合のための方法の一実施形態を示す流れ図である。
【図5】本発明によるフレーム間増分ポーズ推定を生成する方法の一実施形態を示す流れ図である。
【図6】本発明によるフレーム間増分ポーズ推定を生成する方法の第2実施形態を示す流れ図である。
【図7】汎用コンピューティング装置を使用して実施されるビジュアル・オドメトリ方法の高レベル・ブロック図である。
【図8】シーン・イメージのシーケンスから取られた例示的フレームであり、その中で複数のポイント・フィーチャの位置が円で突き止められている図である。
【特許請求の範囲】
【請求項1】
周囲の環境の中をナビゲートする方法であって、
前記周囲の環境の少なくとも一部を表すシーン・イメージのシーケンスを受け取ること、および
前記シーン・イメージのシーケンスを処理して、前記周囲の環境に対するポーズの推定を導出すること
を含む方法。
【請求項2】
少なくとも1つのセンサから補足位置関連データを受け取ること、および
前記補足位置関連データで前記推定を補足すること
をさらに含む請求項1に記載の方法。
【請求項3】
前記処理することが、
前記シーン・イメージのシーケンスの第1フレーム内の複数のポイント・フィーチャの位置を突き止めること、
前記シーン・イメージのシーケンスの複数の後続のフレームにわたって前記複数のポイント・フィーチャを追跡し、第1の複数の関連ポイント・フィーチャ軌跡を生成すること、および
前記第1の複数のポイント・フィーチャ軌跡に従って前記ポーズを推定すること
を含む請求項1に記載の方法。
【請求項4】
前記位置を突き止めることが、
前記シーン・イメージのシーケンスの前記第1フレーム内の各ピクセルについてコーナ応答を計算すること、および
定義された半径以内の他のすべてのピクセルよりも前記コーナ応答が強い各ピクセルでポイント・フィーチャを宣言すること
を含む請求項3に記載の方法。
【請求項5】
前記追跡することが、
前記シーン・イメージのシーケンスの前記第1フレーム内の前記複数のポイント・フィーチャのそれぞれを、前記シーン・イメージのシーケンスの少なくとも1つの後続フレーム内の第2の複数のポイント・フィーチャと比較して、複数の潜在的合致を生成すること、および
相互の整合性に従って前記潜在的合致のうちの1つを選択すること
を含む請求項3に記載の方法。
【請求項6】
前記推定することが、
前記第1の複数のポイント・フィーチャ軌跡の指定されたサブセットに基づいて複数のフレーム間増分ポーズ推定を生成すること、および
前記ポーズを示す可能性が最も高いものとして前記複数のフレーム間増分ポーズ推定のうちの1つを選択すること
を含む請求項3に記載の方法。
【請求項7】
前記生成することが、
前記第1の複数のポイント・フィーチャ軌跡の2つの同時ステレオ・ビューを受け取ること、
前記2つの同時ステレオ・ビューに従って複数の3次元ポイントを三角形分割すること、
前記複数の3次元ポイントに関連する後続ポイント・フィーチャ軌跡データを受け取ること、および
前記複数の3次元ポイントおよび前記第1の複数のポイント・フィーチャ軌跡に従って、少なくとも1つの増分ポーズ推定を生成すること
を含む請求項6に記載の方法。
【請求項8】
第2の複数のポイント・フィーチャ軌跡を複数の3次元ポイントに増分式に三角形分割すること、
前記第2の複数のポイント・フィーチャ軌跡に関連する後続のポイント・フィーチャ軌跡データを受け取ること、および
前記複数の3次元ポイントおよび前記第2の複数のポイント・フィーチャ軌跡に従って、少なくとも1つの増分ポーズ推定を生成すること
をさらに含む請求項3に記載の方法。
【請求項9】
複数の命令が格納されたコンピュータ可読媒体であって、前記複数の命令が、プロセッサで実行されたときに、周囲の環境の中をナビゲートする方法の工程を前記プロセッサに実行させる命令を含み、前記方法が、
前記周囲の環境の少なくとも一部を表すシーン・イメージのシーケンスを受け取ること、および
前記シーン・イメージのシーケンスを処理して、前記周囲の環境に対するポーズの推定を導出すること
を含むコンピュータ可読媒体。
【請求項10】
周囲の環境の中をナビゲートする装置であって、
前記周囲の環境の少なくとも一部を表すシーン・イメージのシーケンスを受け取る手段と、
前記シーン・イメージのシーケンスを処理して、前記周囲の環境に対するポーズの推定を導出する手段と
を備える装置。
【請求項1】
周囲の環境の中をナビゲートする方法であって、
前記周囲の環境の少なくとも一部を表すシーン・イメージのシーケンスを受け取ること、および
前記シーン・イメージのシーケンスを処理して、前記周囲の環境に対するポーズの推定を導出すること
を含む方法。
【請求項2】
少なくとも1つのセンサから補足位置関連データを受け取ること、および
前記補足位置関連データで前記推定を補足すること
をさらに含む請求項1に記載の方法。
【請求項3】
前記処理することが、
前記シーン・イメージのシーケンスの第1フレーム内の複数のポイント・フィーチャの位置を突き止めること、
前記シーン・イメージのシーケンスの複数の後続のフレームにわたって前記複数のポイント・フィーチャを追跡し、第1の複数の関連ポイント・フィーチャ軌跡を生成すること、および
前記第1の複数のポイント・フィーチャ軌跡に従って前記ポーズを推定すること
を含む請求項1に記載の方法。
【請求項4】
前記位置を突き止めることが、
前記シーン・イメージのシーケンスの前記第1フレーム内の各ピクセルについてコーナ応答を計算すること、および
定義された半径以内の他のすべてのピクセルよりも前記コーナ応答が強い各ピクセルでポイント・フィーチャを宣言すること
を含む請求項3に記載の方法。
【請求項5】
前記追跡することが、
前記シーン・イメージのシーケンスの前記第1フレーム内の前記複数のポイント・フィーチャのそれぞれを、前記シーン・イメージのシーケンスの少なくとも1つの後続フレーム内の第2の複数のポイント・フィーチャと比較して、複数の潜在的合致を生成すること、および
相互の整合性に従って前記潜在的合致のうちの1つを選択すること
を含む請求項3に記載の方法。
【請求項6】
前記推定することが、
前記第1の複数のポイント・フィーチャ軌跡の指定されたサブセットに基づいて複数のフレーム間増分ポーズ推定を生成すること、および
前記ポーズを示す可能性が最も高いものとして前記複数のフレーム間増分ポーズ推定のうちの1つを選択すること
を含む請求項3に記載の方法。
【請求項7】
前記生成することが、
前記第1の複数のポイント・フィーチャ軌跡の2つの同時ステレオ・ビューを受け取ること、
前記2つの同時ステレオ・ビューに従って複数の3次元ポイントを三角形分割すること、
前記複数の3次元ポイントに関連する後続ポイント・フィーチャ軌跡データを受け取ること、および
前記複数の3次元ポイントおよび前記第1の複数のポイント・フィーチャ軌跡に従って、少なくとも1つの増分ポーズ推定を生成すること
を含む請求項6に記載の方法。
【請求項8】
第2の複数のポイント・フィーチャ軌跡を複数の3次元ポイントに増分式に三角形分割すること、
前記第2の複数のポイント・フィーチャ軌跡に関連する後続のポイント・フィーチャ軌跡データを受け取ること、および
前記複数の3次元ポイントおよび前記第2の複数のポイント・フィーチャ軌跡に従って、少なくとも1つの増分ポーズ推定を生成すること
をさらに含む請求項3に記載の方法。
【請求項9】
複数の命令が格納されたコンピュータ可読媒体であって、前記複数の命令が、プロセッサで実行されたときに、周囲の環境の中をナビゲートする方法の工程を前記プロセッサに実行させる命令を含み、前記方法が、
前記周囲の環境の少なくとも一部を表すシーン・イメージのシーケンスを受け取ること、および
前記シーン・イメージのシーケンスを処理して、前記周囲の環境に対するポーズの推定を導出すること
を含むコンピュータ可読媒体。
【請求項10】
周囲の環境の中をナビゲートする装置であって、
前記周囲の環境の少なくとも一部を表すシーン・イメージのシーケンスを受け取る手段と、
前記シーン・イメージのシーケンスを処理して、前記周囲の環境に対するポーズの推定を導出する手段と
を備える装置。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【公表番号】特表2008−503757(P2008−503757A)
【公表日】平成20年2月7日(2008.2.7)
【国際特許分類】
【出願番号】特願2007−518274(P2007−518274)
【出願日】平成17年6月22日(2005.6.22)
【国際出願番号】PCT/US2005/022297
【国際公開番号】WO2006/002322
【国際公開日】平成18年1月5日(2006.1.5)
【出願人】(599134012)サーノフ コーポレーション (59)
【Fターム(参考)】
【公表日】平成20年2月7日(2008.2.7)
【国際特許分類】
【出願日】平成17年6月22日(2005.6.22)
【国際出願番号】PCT/US2005/022297
【国際公開番号】WO2006/002322
【国際公開日】平成18年1月5日(2006.1.5)
【出願人】(599134012)サーノフ コーポレーション (59)
【Fターム(参考)】
[ Back to top ]