(57)【要約】  映像または画像処理では２種の別々の仕事がある。一方で、画像解析および特色認識の困難な仕事があり、他方で入力画像が与えられるカメラの３Ｄ世界位置のコンピュータ計算というそれほど困難ではない仕事がある。生態映像では、これらの２種の仕事は一体に絡み合っているので、相互の区別は困難である。【選択図】  図１
2009514066.tif 000002
【特許請求の範囲】
【請求項１】
カメラが存在する世界のア・プリオリモデルの創造、カメラからの各素材の未処理ビデオフレームの取り出し、各ビデオフレーム毎の可能性のある該フレーム撮影位置および視角の小集合の仮定、各ビデオフレーム毎の各仮定位置と視角につき１画像のグラフィックスプロセッサーとア・プリオリモデルの頂点データを使用する画像レンダリング処理、該ビデオフレームとの最良合致画像の入手による最善位置および視角の取り出しの各段階が含まれるリアルタイム（エゴモーション）で較正されるカメラの位置および視角の追跡方法
【請求項２】
世界のア・プリオリモデルのレンダリングに利用される低コストグラフィックスプロセッサーが既に先行技術で実現されていると同時に真に迫るグラフィックスコンピュータゲームで利用されている請求項１に記載される方法
【請求項３】
最初のビデオフレームが既知の位置と角度を基にしている請求項２に記載される方法
【請求項４】
ビデオフレームとレンダリング画像が同じ解像度であると同時に、両方ともピクセルと０から１００％まで重複する長方形あるいは正方形領域に再分割される請求項３に記載される方法
【請求項５】
仮定される位置と視角の集合の計算が前後する２つのフレームを基にした最大確率のカメラの運動ベクトルと視角のコンピュータ計算により制約され、このコンピュータ計算に、相互に独立して処理される現在フレームにおける各領域の高速フーリエ変換（ＦＦＴ）のコンピュータ計算、その結果のＦＦＴマトリックスの位相要素の取り出しと純位相要素マトリックスの入手、該位相要素マトリックスのメモリへの格納、現在および前回フレームを基にした位相要素マトリックスの利用、現在カメラフレームの各領域と前回カメラフレームの該当領域間の位相差の取り出し、位相相関面となる位相差マトリックスのＦＦＴ逆変換のコンピュータ計算、各領域毎の２Ｄ光学流れベクトルを形成する各領域の位相相関面における最大値の２Ｄ位置の決定、全体領域の光学流れベクトルをもとにしたカメラの最大確率の３Ｄ運動ベクトルと視角の計算、の各副次段階が含まれる請求項４に記載される方法
【請求項６】
２Ｄ光学流れベクトルを基にした最大確率の３Ｄ運動ベクトルおよび視角に関する計算に、参照世界フレームの移動の進路または方向の決定とその後のこれによる次の最大確率位置が存在する進行方向の定義、進路進行方向に沿った次位置候補を決定するための前回速度計算値の利用、計算済み候補地点周囲の地点からの立体的選定を基にした多数の最大確率位置の取り出し、該立体的選定範囲内の地点での最良の次位置を選定するための下り勾配の利用の各副次段階が含まれる請求項５に記載される方法
【請求項７】
すべての各ビデオフレームに対する最良の合致レンダリング画像の選定方法に、レンダリング画像の各領域のＦＦＴのコンピュータ計算、各領域のＦＦＴマトリックスからの位相要素の取り出し、現在フレームおよびそのレンダリング画像をもとにしたそれぞれの位相要素マトリックスの利用、現在カメラフレームの各領域とレンダリング画像の当該領域間の位相相関マトリックスを形成する位相差の取り出し、各領域毎の位相相関面となるカメラフレーム領域とレンダリング画像領域との間の位相相関マトリックスのＦＦＴ逆変換のコンピュータ計算の各副次段階が含まれるもので、最良合致レンダリング画像が全体領域にわたり合計される光学流れベクトルの最小平方和（ドット積）を有するものである請求項５に記載される方法
【請求項８】
すべてのビデオフレームに対する最良合致レンダリング画像の選定方法に、先行技術で「直接法」と呼ばれる次の各副次段階、すなわち、すべてのレンダリング画像毎のレンダリング画像とビデオフレーム間のすべてのピクセル毎のグレーレベルの差分の入手、すべての領域に関する全差分の単純平方和の計算の段階が含まれるもので、該選定レンダリング画像がビデオフレームとの差分の最小平方和の場合のものでなくてはならない請求項５に記載される方法
【請求項９】
ア・プリオリモデルが「オートキャド」のような現在市販されている手段を利用して構築される請求項５に記載される方法
【請求項１０】
ア・プリオリモデルが先行技術の方法を利用してカメラの存在する世界から予め取り出されるビデオフレームの画像処理によって構築される請求項５に記載される方法
【請求項１１】
ア・プリオリモデルが先行技術方法を利用して運動の予測とリアルタイムで同時平行的にかつそれぞれ別々に構築される請求項５に記載される方法
【請求項１２】
ビデオカメラおよびその内容が一定のフレーム速度で更新されるそのフレームバッファー、次々続くビデオフレームを基にした光学流れのコンピュータ計算とこの光学流れ解析を基にした多数の試行カメラ位置および視角の仮定用のデジタル処理手段、世界のア・プリオリモデル、カメラがフレームバッファーを更新するのにかかるわずかな時間で世界モデルの複数レンダリングが可能なグラフィックスプロセッサーまたは複数のグラフィックスプロセッサー、世界モデルにおける試行位置と視角に対応するレンダリング面を格納する複数のグラフィックス面または画像バッファー、ならびにビデオフレームバッファーと各レンダリング画像の比較と同時にその後の最良合致レンダリング画像の選定用のデジタル処理手段が含まれることによって最高精度のカメラの瞬間的位置および視角の決定も行うリアルタイム（エゴモーション）でのカメラの位置および視角の追跡装置
【請求項１３】
世界のア・プリオリモデルのレンダリングに利用される低コストグラフィックスプロセッサーが既に先行技術で実現されていると同時にリアリスティックなグラフィックスコンピュータゲームで利用されている請求項１２に記載される装置
【請求項１４】
装置が初期化されてコンピュータ計算が既知の位置、視角、速度および角速度から開始される請求項１３に記載される装置
【請求項１５】
ビデオフレームとレンダリングされる画像が同じ解像度であると同時に両方ともピクセルと０から１００％だけ重複する長方形あるいは正方形領域に再分割される請求項１４に記載される装置
【請求項１６】
仮定される位置および視角の集合計算が互いに前後する２つのフレームを基にしたカメラの最大確率運動ベクトルおよび視角のコンピュータ計算によって制限されるように構成され、このコンピュータ計算に、相互に独立して処理される現在フレームの各領域の高速フーリエ変換（ＦＦＴ）のコンピュータ計算、結果のＦＦＴマトリックスからの位相要素の取り出しならびに純位相要素マトリックスの入手、この位相要素マトリックスのメモリへの格納、現在および前回フレームを基にした位相要素マトリックスの利用、位相相関マトリックスを形成する現在カメラフレームの各領域と前回カメラフレームの当該領域間の位相差の取り出し、位相相関面となる位相相関マトリックスのＦＦＴ逆変換のコンピュータ計算、各領域毎の光学流れベクトルを形成する各領域の位相相関面での最大値の２Ｄ位置の決定、すべての領域の光学流れベクトルを基にしたカメラの最大確率３Ｄ運動ベクトルおよび視角の計算が含まれる請求項１５に記載される装置
【請求項１７】
参照世界フレームの移動の進路または方向の決定、その後のこれによる最大確率の次位置にある進行方向の定義、該進路進行方向位置に沿った次候補位置を決定するための前回速度計算の利用、計算候補周辺地点の立体的選定もとにした最大確率の多数の位置の取り出し、該立体選定地点の範囲内の最良次位置を選定するための下り勾配の利用の一連のコンピュータ計算を利用する光学流れベクトルを基に最大確率の３Ｄ運動ベクトルと視角の計算を行うよう構成される請求項１６に記載される装置
【請求項１８】
レンダリング画像の各領域のＦＦＴの計算、各領域のＦＦＴマトリックスの位相要素の取り出し、現在フレームおよびレンダリング画像を基にした位相要素マトリックスの利用、位相相関マトリックスを形成する現在カメラフレームの各領域とレンダリング画像の対応領域の間の位相差の取り出し、各領域毎の位相相関面となるカメラフレーム領域とレンダリング画像領域間の位相相関マトリックスのＦＦＴの逆変換の計算の一連のコンピュータ計算を利用して全領域にわたる光学流れベクトルの最小平方和（ドット積）を有するすべてのビデオフレームの最良合致レンダリング画像を選定するよう構成される請求項１６に記載される装置
【請求項１９】
すべてのレンダリング画像毎のレンダリング画像とビデオフレーム間のすべてのピクセルに関するグレーレベルの差分の入手ならびにすべての領域に関するすべての差分の単純平方和の計算の先行技術で「直接法」と呼ばれるコンピュータ計算を介して、すべてのビデオフレームに対する最良合致レンダリング画像の選定を行うよう構成されて、該選定レンダリング画像がビデオフレームの差分の最小平方和のものでなくてはならない請求項１６に記載される装置
【請求項２０】
ア・プリオリモデルが現在市販されているオートキャドのような手段を利用して構築される請求項１６に記載される装置
【請求項２１】
ア・プリオリモデルが先行技術方法を利用するカメラが存在する世界から予め取り出されるビデオフレームの画像処理によって構築される請求項１６に記載される装置
【請求項２２】
ア・プリオリモデルが先行技術方法を利用する運動予測と同時平行的にかつこれとは独立してリアルタイムで構築される請求項１６に記載される装置
【請求項２３】
請求項６から請求項１１までのいずれか一項における方法を実施するコンピュータプログラム製品
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピュータ視野の広がりを前進させる最新技術のコンピュータグラフィックスを利用する。
【０００２】
グラフィックスエンジンは、特にリアルタイムで利用されるファーストパーソンシューターゲームが非常にリアルになってきた。本発明の基本的なアイデアは画像処理にグラフィックスエンジンを利用すること、すなわち、リアルタイムのグラフィックスエンジンによって生成される画像フレームをカメラからのものを合致させることにある。
【背景技術】
【０００３】
映像あるいは画像の処理では２種の別個の仕事がある。一方では画像解析および特色認識という困難な仕事があり、他方では入力画像が与えられるカメラの３Ｄ世界位置のコンピュータ計算というそれほど困難ではない仕事がある。
【０００４】
生態映像では、これらの２種の仕事は相互に絡み合っており相互に区別するのは困難である。我々は我々の周囲の特色を認識すると同時にこれから三角測量を行ってその世界座標の位置を知覚している。我々は、最初に三角測量する特色を特定しなければ三角測量は不可能に思われると同時に、どこかにその特色が配置されえない限り我々が住む３Ｄ世界の特定は本当に不可能である。
【０００５】
すべてではないにしても、その多くの先行技術における映像システムは同一システムの中における両方の仕事を実施する試みといえる。例えば、参照米国特許番号US5,801,970には両方の仕事が含まれ、参照米国特許番号US6,704,621には三角測量だけから構成されるようであるが実際には道路の認識を必要とする。
【特許文献１】米国特許番号US5,801,970
【特許文献２】米国特許番号US6,704,621
【発明の概要】
【０００６】
三角測量の仕事が解析と特色認識の仕事とは別にかつ独立したまま本当に実行可能であれば、システムは後者の仕事を実行しないのでコンピュータ計算リソースは半分で済むであろう。グラフィックス処理における現在の進歩を活用して、本発明はカメラ位置の三角測量を通常の場面解析および特色認識無しで可能にする。これには視野内の世界の精確なア・プリオリモデルが利用される。３Ｄモデルが最新のグラフィックス処理装置を利用してグラフィックス面にレンダリングされる。カメラから入ってくる各フレームはその後、グラフィックス面の多数のレンダリング候補の中から最良の合致候補を求めて検索される。比較するレンダリング画像の計算は、次々と続くフレームをもとにしたカメラ位置および視角の変化のコンピュータ計算ならびに、その後の世界のア・プリオリモデルをレンダリングするための次の可能性のある位置と視角が限定される計算の結果の利用によって小型化される。
【０００７】
先行技術に勝る本発明の主な利点は現実世界の世界モデルへの地図化である。これが最も相応しい用途はロボットのプログラミングである。ア・プリオリ地図によって誘導されると同時にその地図におけるその位置を知るロボットはこのような誘導が行われないものよりもはるかに優れている。これは航行、自動誘導、経路探し、障害回避、関心地点の標的化およびその他のロボットの仕事に優れている。
【本発明の詳細説明】
【０００８】
図１には本発明の好ましい実施例の図解が示される。世界１００の世界のア・プリオリモデルが現在市販されている最新グラフィックスプロセッサー１０１を利用してレンダリング画像１０２、１０３および１０４にレンダリングされる。該モデルは現実世界１１０に関する精確ではあるが必ずしも完璧ではないモデルである。本発明の目的はそれぞれ時刻tおよびt+1時点でのフレーム１０７および１０８を生成するカメラ３０９の位置および視角の追跡にある。フレーム１０７および１０８は装置への初期リアルタイム入力として利用される。光学流れベクトルはフレーム１０７および１０８から最新技術の方法を利用して計算される。先行技術により、これらの光学流れベクトルをもとに精確な進路とカメラ視角が騒音と異常値に耐える方法で派生させることができる。それから、次に可能性のある位置が現在速度（１０５）から決定される現在位置から一定距離地点において、現在の進路によって定義される進行方向上にある地点周囲に仮定される。可能性のある候補地点Ｎがグラフックスプロセッサーまたはプロセッサー１０１によってＮ候補の画像１０２、１０３および１０４にレンダリングされる。各レンダリング画像はその後、現在のカメラフレームおよび最良合致選定画像（１０６）と比較される。該選定画像から、カメラの最大限に精確な位置、瞬間速度、視角、およびの角速度もまた該諸候補地点から選定可能である。
【０００９】
動的でフレーム毎の三角測量（あるいは追跡処理）は本発明において図３に示される「フローチャート」の次の諸段階を踏んで実行される。以降の諸段階の説明では、カメラからのすべてのビデオフレーム毎に、比較するためにグラフィックスプロセッサーによってレンダリングされる可能性のあるフレームから仮定される集合がある。この発明では、この比較がコンピュータ計算上最も高価につく。ビデオフレームはレンダリング画像の鉛直方向と水平方向の解像度が両方とも等しい。各フレームおよび各レンダリング画像は図２に示されるように多数のピクセルによって相互に重複しても良い多数の長方形領域に分割される。
【００１０】
１．カメラからのフレーム、ならびにフレームが取り出される時の時刻「t」の瞬間時点の、カメラの既知の絶対世界位置P(t)、視角V(t)、速度ゼロu(t)=0、および角速度ゼロw(t)=0を利用した開始。このフレームにおけるすべての領域(Cs)の個々のの高速フーリエ変換（FFT）の計算および変換の位相要素PFC(a,t)（時刻「t」、領域「a」）における取り出し
【００１１】
２．次フレームの取り出し。すべてのPFC(a,t+1)、時刻「t+1」時点の領域「a」におけるFFTの位相要素の計算。
【００１２】
３．PFC(a,1)およびPFC(a,t+1)間の位相差の計算、その後の位相相関面を得るための位相差マトリックスに関するにFFT逆変換の実行。カメラが「t」から「t+1」までパニングも移動もしない場合には、各領域毎の位相相関面は領域「a」の中心で最大値を示そう。移動するかあるいはパニングする場合には、最大値は各領域の中心以外のどこかに生じよう。位相相関面内の中心から最大値地点までの分岐として定義される各領域OP(a,t+1)毎の光学流れベクトルの計算。（風景領域に移動物体がある場合、各移動物体により位相相関面内に追加頂点が生み出されようが、比較される後続のフレームからの２領域が建物や壁あるいは地面のような静的物体が大勢を占める限りには、これらのその他頂点はカメラ地点および/または視角の変化に対応する頂点よりも低いはずである。）
【００１３】
４．このすべてのOP(a,t+1)をもとにするとともに、絶対地点P(t)、視角V(t)、現在速度u(t)、および現在角速度w(t)を利用して、すべての可能性のある絶対カメラ位置（ベクトルPi(t+1)）および時刻t+1時点の視角（単位ベクトルVi(t+1)）の変動幅の計算。1986年にMIT出版から出版されたB.K.P.ホーンによる「ロボット視覚」と題する参考書籍の第１７章に詳述されるようにOP(a,t+1)から容易に決定される運動進行方向（瞬間的進路）内にあるようにPiが選択されても良い。
【００１４】
５．少数の（例えばN個）可能性のあるカメラ位置Pi(t+1)およびア・プリオリモデルを利用してレンダリングする視角Vi(t+1)の仮定。これによりN個の画像レンダリングMi(a,t+1)が生ずる。各Mi(a,t+1)のFFTの計算および変換PFMi(a,t+1)からの位相要素の取り出し。
【００１５】
６．時刻t+1時点の最良合致カメラフレームは、その各領域のPFC(a,t+1)とのPFMi(a,t+1)の位相差が、考慮されるすべての領域で最も中心に近い最大値を伴う２Ｄ図形であるFFTの逆変換となるMiである。これをもとに最良の可能性のある位置P(t+1)および視角V(t+1)もまた選定される。それから、瞬間速度がu(t+1)=P(t+1)-P(t)として瞬間角速度w(t)=V(t+1)-V(t)と一緒に決定される。
【００１６】
７．  前回時刻t時の計算およびフレームは破棄されると同時に、現在時刻をt+1にして、P(t)に対しP(t+1)、V(t)に対しV(t+1)、u(t)に対しu(t+1)、w(t)に対しw(t+1)、およびPFC(a,t)に対しPFC(a,t+1)が上書きコピーされる。段階２に戻る。
【００１７】
カメラの視野は静的エンティティが大勢を占める（移動エンティティによって取り込まれる画像領域がより少なく世界座標に関して静的である）限り、動的三角測量または追跡処理が可能である。カメラフレームとこれによる領域は静的エンティティが大勢を占める限り、位相相関面内の頂点はカメラの運動に一致する。この点は先行技術で十分知られており、英国放送会社（BBC）によって1987年に出版されたG.A.トーマスによる「DATVおよびその他のアプリケーション用のテレビ運動計測」と題する参考論文中に詳述されている通りである。
【代替実施例】
【００１８】
本発明のある代替実施例では、段階５および６のコンピュータ計算コストはKフレームと同時ににわたり償却されるとともに、生じる補正は将来のフレームまで波及することになる。例えば、参照フレームがすべての５個の各カメラフレーム（K=5）毎に選択される場合には、第１フレームが１つの参照フレームであると同時に、段階５および段階６は第１フレームサンプルから第５サンプル（t+1から,t+5まで）までの時間間隔内で実行可能である。その間に、すべてのその他の段階（段階１から段階４までと段階７）が、すべてのサンプルフレームについてPおよびVに関する非補正値が利用されてすべてのサンプルについて実行される。第５フレームについては、第１フレームにつき最良合致フレームが最終的に選定される時に、誤差補正が施される。同一の誤差補正がPおよびVの５個すべての値に適用されるとともに、t+5によってPおよびVの前回値のすべてが破棄されたので、P(t+5)およびV(t+5)だけが補正を必要とする。
【００１９】
本発明のもう１つの実施例では、段階５および段階６のコンピュータ計算コストが、仮定される各カメラ位置につき１台の複数の低コストのゲーム用グラフィックスプロセッサーの利用によってまかなわれる。
【００２０】
また、もう１つの実施例では、段階５および段階６においてカメラフレームとレンダリング画像との間の位相相関面のコンピュータ計算に代わって、輝度値の差の平方和が代わりに計算されても良い（先行技術で「直接法」といわれる）。最良合致画像は最小平方和の場合のレンダリング画像である。
【００２１】
上記で説明されたものは本発明の好ましい実施例である。しかしながら、本発明の実施は上記で説明された好ましい実施例のものとは別の特定の形態で可能である。例えば、正方形または長方形領域「a」の代わりに、円状領域が代わって採用されても良い。
【００２２】
本発明の通常のアプリケーションはカメラの位置および視角を追跡処理する。しかしながら、当技術の専門家であれば本発明による装置または操作方法は物体位置の測定、航行、または自動誘導が必要な任意の筋書きで応用可能であることを理解すると同時に認識しよう。好ましい実施例類は単に例示的なものであり制限的なものとは決して受け取ってはならない、本発明の範囲は上記の説明よりも付録の請求項によって与えられると同時に、請求項の精神内にあてはまるすべての変型例および等価なものがこの中に含まれるものと意図される。
【図面の簡単な説明】
【００２３】
【図１】本発明の、現実世界でのカメラの動きがいかに３D世界モデルにおいて追跡させるかを示した実施例の全体図である。
【図２】本発明の領域分割されたレンダリング面またはカメラフレームのいずれかの例示図である。
【図３】本発明の”本発明の詳細説明”に説明されるアルゴリズムに関する高度レベルのフローチャートである。
【図１】
2009514066.tif 000003
【図２】
2009514066.tif 000004
【図３】
2009514066.tif 000005