(57)【要約】  同じ場面を撮影する２台のカメラ（Ｔ１，Ｔ２）を備えたステレオビジョン用システム（１００）において、エピポーラ幾何が知られている場合に散乱視差場を求める方法が実行される。この方法は、２台のカメラにより２つの異なる位置から当該場面の第１の画像及び第２の画像（ＩＭ１，ＩＭ２）を取り込むステップ；第１の画像中の少なくとも１つのピクセルを選択するステップであって、前記ピクセルは当該場面の１つのポイントに関連付けられており、第２の画像はこれも当該場面の前記ポイントに関連付けられた１つのポイントを含んでいる前記ステップ；及び前記ピクセルから第２の画像内の前記ポイントまでの変位を計算して費用関数を最小化するステップを含む。この費用関数は、第１の画像と第２の画像との間の差に依存した項と、エピポーラ直線から第２の画像内の前記ポイントまでの距離に依存した項とを含む。カメラを校正する際の誤差又は不確かさを考慮するために、前記ポイントの存在が許容されているエピポーラ直線のサブセットの周りの許容領域に属しているか否かをチェックする。【選択図】図２
2009517683.tif 000002
【特許請求の範囲】
【請求項１】
ステレオビジョンにおいて散乱視差場を求める方法であって、
・２つの異なる位置から同じ場面の第１の画像及び第２の画像を取り込むステップであって、前記第１の画像のピクセルからなる少なくとも１セットが前記第２の画像上のポイントの対応するセットに関連付けられる前記ステップ；
・前記第１の画像中の少なくとも１つのピクセルを選択するステップ；及び
・前記ピクセルに関連付けられた前記第２の画像のポイントを決定するステップであって、前記ピクセルと前記ポイントとの間の視差ベクトルを変数として有する費用関数を最小化することを含み、前記費用関数が、前記ピクセルが中心位置にある窓内及び決定すべきポイントが中心位置にある対応する窓内での第１の画像と第２の画像との差に依存している前記ステップ；
を含み、前記費用関数が、前記ピクセルに関連付けられた前記第２の画像中のエピポーラ直線から、決定されるべき前記ポイントまでの距離に単調増加にて依存する項を含むことを特徴とする方法。
【請求項２】
前記第１の画像及び第２の画像が第１のカメラ及び第２のカメラからそれぞれ取り込まれ、前記項が前記第１のカメラ及び第２のカメラの校正パラメータに依存している請求項１に記載の方法。
【請求項３】
前記項がカメラ校正データの不確かさに依存して重み付けされる請求項２に記載の方法。
【請求項４】
前記項が前記ポイントと前記エピポーラ直線との距離の２乗に比例している請求項１に記載の方法。
【請求項５】
前記ピクセルに関連付けられた前記第２の画像のポイントを決定するステップが、前記第２の画像内で前記エピポーラ直線の周りの前記ポイントの許容領域を画定することを含む請求項１〜４のいずれか一項に記載の方法。
【請求項６】
前記許容領域が、前記エピポーラ直線に垂直な直線により画定された半平面内に含まれる請求項５に記載の方法。
【請求項７】
前記費用関数が、前記第２の画像内の前記ピクセルが中心位置にある前記窓のピクセルにおける輝度勾配と、前記ピクセル上に中心位置がある前記窓のピクセルと同じ窓内の前記第２の画像のピクセルとの間の輝度差とから構成されるパラメータを含む、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
前記ピクセルに関連付けられた前記第２の画像のポイントを決定するステップが、前記ピクセルが中心位置にある前記窓内に含まれるすべてのピクセルに相対重みを加えることを含む、請求項１〜７のいずれか一項に記載の方法。
【請求項９】
前記ピクセルが中心位置にある前記窓の中央領域内のピクセルに加えられる重みが、前記窓の外部領域内のピクセルに加えられる重みよりも大きい請求項８に記載の方法。
【請求項１０】
前記ポイントを決定するステップが費用関数を最小化する前記ステップを含む請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
同じ場面を撮影できる第１の撮影カメラ及び第２の撮影カメラと、前記第１の撮影カメラ及び第２の撮影カメラから前記場面の夫々の同時画像を受信できる処理装置とを備え、前記処理装置が請求項１〜１０のいずれか一項に記載の方法によって前記夫々の画像を処理するよう構成されているステレオビジョン用システム。
【発明の詳細な説明】
【技術分野】
【０００１】
一般に、本発明はステレオビジョンのために画像を自動的に分析する方法を取り扱い、特に、エピポーラ幾何が知られている場合に散乱視差場を求める方法を取り扱う。
【背景技術】
【０００２】
画像を自動的に分析する際に解決すべき頻出課題は、１台以上のカメラにより異なる視点から得られた同じ場面を示す２つのフレーム間に存在する視差(disparity)を求めることである。視差は、同じ場面要素の２つのフレームの位置に関係する。すべての画像ピクセルに対して視差を計算するアルゴリズムや、ピクセルのサブセット（すなわちポイント群）に限定されたアルゴリズムが存在する。前者の場合は密な視差場(dense disparity field)を扱い、後者の場合は散乱視差場（scattered disparity field）を扱う。本発明は二番目のカテゴリーに属する。
【０００３】
２つのフレーム間に存在する散乱視差場を求める一般的な技術では、関係のある関連ポイント（すなわち特徴的な画像領域を記述するポイント）を特定して関連付ける。この目的のためにいくつかのアルゴリズムがあり、これらのアルゴリズムは角、エッジ、輪郭、又は（フレーム間でもっともらしく関連付け得る、すなわち曖昧さを低減する）他の任意の特徴を特定することに基づいている。これらのアルゴリズムは、異なる時間に１台のカメラにより撮られた一般フレーム間のポイントをトラッキングするために作られた。
【０００４】
「コンピュータビジョン」の分野では、異なるフレーム間の対応を探す課題を取り扱っている文献が数多く存在する。特に、ステレオビジョンにおいて、主な目標の一つは、ｎ個の異なるビュー（ｎ≧２）から開始して表示された対象物の距離を求めることである。ｎ＝２の場合、対応を決定するために、ビジョンシステムを記述するパラメータ（すなわちカメラの特徴及び位置）を考慮に入れて、同じ場面に関係した２つの画像間に存在する関係を記述するいわゆる基本マトリックスが用いられる。この関係とは、第１の画像（フレーム）上に１つのポイントをとると、第２の画像（フレーム）上の対応ポイントがエピポーラ線と称される直線上に存在することを意味する。
【０００５】
画像中に存在している特徴を特定しトラッキングすることに基づいて、散乱視差場を計算するために用いることのできる最もよく知られたアルゴリズムの一つが、Ｃａｒｌｏ  Ｔｏｍａｓｉ及びＴａｋｅｏ  Ｋａｎａｄｅによる論文「Ｓｈａｐｅ  ａｎｄ  Ｍｏｔｉｏｎ  ｆｒｏｍ  Ｉｍａｇｅ  Ｓｔｒｅａｍ  −  Ｐａｒｔ  ３  −  Ｄｅｔｅｃｔｉｏｎ  ａｎｄ  Ｔｒａｃｋｉｎｇ  ｏｆ  Ｐｏｉｎｔ  Ｆｅａｔｕｒｅｓ」，Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＣＭＵ−ＣＳ−９１−１３２，１９９１年４月に記載されており、当該技術においてＫＬＴ（Ｋａｎａｄｅ−Ｌｕｃａｓ−Ｔｏｍａｓｉ）技術として知られている。この論文に記載されているように、フレーム間での正確なポイントトラッキングのために解決すべき２つの重要な課題、すなわち、トラッキングされる特徴をいかにして選択するか（「特徴選択」）と、それらをフレーム毎にいかにしてトラッキングするか（「トラッキング」）という課題がある。特に、この論文には、２つのフレーム間のポイント特徴の２次元変位ベクトル（視差ベクトル）が知られていない２×２線形系（これは最小化すべき費用関数に変換し得る）によってトラッキングを実行するためのアルゴリズムが記載されている。ＫＬＴ技術は、一連の画像に関係する場合や、同じ場面の同時画像の場合にも効率的に使用できる。
【０００６】
Ｊ．Ｓｈｉ及びＣ．Ｔｏｍａｓｉの論文「Ｇｏｏｄ  Ｆｅａｔｕｒｅｓ  ｔｏ  Ｔｒａｃｋ」，ＩＥＥＥ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ（ＣＶＰＲ９４），Ｓｅａｔｔｌｅ，１９９４年６月は、ＫＬＴ技術に基づいており、トラッキングを実行し得る特徴についての選択基準を提案している。
【０００７】
Ｊ．Ｍｅｎｄｅｌｓｏｈｎ，Ｅ．Ｓｉｍｏｎｃｅｌｌｉ及びＲ．Ｂａｊｃｓｙの論文「Ｄｉｓｃｒｅｔｅ−Ｔｉｍｅ  Ｒｉｇｉｄｉｔｙ−Ｃｏｎｓｔｒａｉｎｅｄ  Ｏｐｔｉｃａｌ  Ｆｌｏｗ」，７ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｎａｌｙｓｉｓ  ｏｆ  Ｉｍａｇｅｓ  ａｎｄ  Ｐａｔｔｅｒｎｓ，１９９７年９月１０〜１２日は、密な場の計算を扱っており、（密な場を構成している）視差ベクトルがエピポーラ直線上に存在する位置を示していることを課している。この拘束により、エピポーラ直線が正確に知られている場合に得ることができる結果を改善することができる。
【０００８】
Ｈ．Ｎａｊａｆｉ及びＧ．Ｋｌｉｎｋｅｒの論文，「Ｍｏｄｅｌ-ｂａｓｅｄ  Ｔｒａｃｋｉｎｇ  ｗｉｔｈ  Ｓｔｅｒｅｏｖｉｓｉｏｎ  ｆｏｒ  ＡＲ」，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｓｅｃｏｎｄ  ＩＥＥＥ  ａｎｄ  ＡＣＭ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｍｉｘｅｄ  ａｎｄ  Ａｕｇｍｅｎｔｅｄ  Ｒｅａｌｉｔｙ  （ＩＳＭＡＲ），２００３は、第２のフレーム中の対応するポイントがエピポーラ直線上に存在しないような特徴を除去するために、ＫＬＴ技術の下流の基本マトリックスを使用することを提案している。したがって、２台のカメラからなる構成と矛盾する視差ベクトルが除去される。
【非特許文献１】Ｃａｒｌｏ  Ｔｏｍａｓｉ及びＴａｋｅｏ  Ｋａｎａｄｅによる論文「Ｓｈａｐｅ  ａｎｄ  Ｍｏｔｉｏｎ  ｆｒｏｍ  Ｉｍａｇｅ  Ｓｔｒｅａｍ  −  Ｐａｒｔ  ３  −  Ｄｅｔｅｃｔｉｏｎ  ａｎｄ  Ｔｒａｃｋｉｎｇ  ｏｆ  Ｐｏｉｎｔ  Ｆｅａｔｕｒｅｓ」，Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＣＭＵ−ＣＳ−９１−１３２，１９９１年４月
【非特許文献２】Ｊ．Ｓｈｉ及びＣ．Ｔｏｍａｓｉの論文「Ｇｏｏｄ  Ｆｅａｔｕｒｅｓ  ｔｏ  Ｔｒａｃｋ」，ＩＥＥＥ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ（ＣＶＰＲ９４），Ｓｅａｔｔｌｅ，１９９４年６月
【非特許文献３】Ｊ．Ｍｅｎｄｅｌｓｏｈｎ，Ｅ．Ｓｉｍｏｎｃｅｌｌｉ及びＲ．Ｂａｊｃｓｙの論文「Ｄｉｓｃｒｅｔｅ−Ｔｉｍｅ  Ｒｉｇｉｄｉｔｙ−Ｃｏｎｓｔｒａｉｎｅｄ  Ｏｐｔｉｃａｌ  Ｆｌｏｗ」，７ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｎａｌｙｓｉｓ  ｏｆ  Ｉｍａｇｅｓ  ａｎｄ  Ｐａｔｔｅｒｎｓ，１９９７年９月１０〜１２日
【発明の開示】
【発明が解決しようとする課題】
【０００９】
発明の簡単な説明
出願人は、特に２台以上のカメラの場合にしばしば利用可能な基本マトリックスの知識をＫＬＴ技術が利用していないことに気付いた。
【００１０】
また、出願人は、基本マトリックスを利用する視差計算技術では、ポイントがエピポーラ線上に存在するという拘束を有すること、及びこの拘束によってカメラの正確な校正のみを仮定する正確な結果が得られることに気付いた。しかしながら、一般にこの校正は推定によって得られるので、誤差又は不正確さを含む。
【００１１】
出願人は、校正プロセスにより計算し得る基本マトリックスに属する情報を考慮に入れるためにＫＬＴ方法を適切に修正することによって、抽出された視差場の質を改善できることを見いだした。特に、出願人は、絶対的な拘束を設定することなく基本マトリックスを考慮に入れるべくポイントトラッキングを修正することによって、本システムを校正する際の誤差を補正すべく随意に本プロセスに作用できることを見いだした。
【課題を解決するための手段】
【００１２】
特に、出願人は、エピポーラ線とサーチされたポイントとの距離の二乗に比例した項をＫＬＴ技術の費用関数に導入することで、配置がエピポーラ直線から外れることを可能にすることによって、おおよその校正が行われた場合にも正確な結果を得られることを見いだした。そのようにして得られた結果は、元のＫＬＴ技術を適用して得ることのできる結果よりも優れ、特定されたポイントがエピポーラ直線上にのみ存在するという拘束を課することにより得ることのできる結果よりも優れ得る。
【００１３】
好ましくは、第１の画像のピクセルに関連付けられた第２の画像のポイントを決定するために、費用関数最小化ステップが、前のサイクルで得られた費用関数の更新を毎回用いて多数回繰り返される。
【００１４】
また、出願人は、エピポーラ直線に関して有効領域を更に制限できることを見いだした。この制限は半直線（エピポーラ直線のサブセット）により表され、これにより、この半直線の近くの位置を示さないすべての視差ベクトルが除去される。
【００１５】
本発明を適用する好ましい分野は、コンピュータビジョンであり、特に多くの視点から撮影される場合である。
以下、限定するものではないが、本発明の適用例を示す添付図面に関して本発明を説明する。
【発明を実施するための最良の形態】
【００１６】
発明の詳細な説明
図１は、複数のカメラでビデオ撮影するシステム全体を１００で示す。特に、このシステム１００は、同じ場面を異なる位置から撮ることができると共に、このようにして撮られた画像間の散乱視差場を決定できる。
【００１７】
システム１００は第１のカメラＴ１と第２のカメラＴ２とを含み、両カメラとも同じ場面について夫々のデジタル画像（又はフレーム）ＩＭ１、ＩＭ２を生成できる。これら２台のカメラＴ１、Ｔ２は互いに平行となるか又は互いに傾斜するように当該場面に向けることができる。
【００１８】
システム１００は、両カメラＴ１、Ｔ２に接続された処理装置ＰＵを更に備え、この処理装置ＰＵは、後で説明する方法により散乱視差場を得るべく、これら２台のカメラＴ１、Ｔ２から受け取ったデジタル画像ＩＭ１及びＩＭ２を処理できる。また、システム１００は処理装置内又は別の装置内に存在しているカメラ校正モジュールＣＭ、好ましくはソフトウエアモジュールを備え、このモジュールは、本発明の方法による処理のために用いられる校正データを処理装置に提供できる。
【００１９】
同じ場面についての２つの同時画像間に存在する関係は、１つのカメラにより撮られた一連の連続した画像において存在する関係に類似している。したがって、画像特徴の変位を求める課題は、上記論文においてＳｈｉ及びＴｏｍａｓｉにより示唆されている特徴の選択と共にＫＬＴトラッキング技術を参照することで解決できる。
【００２０】
一連の画像は関数Ｆ（ｘ，ｙ，ｔ）により表すことができる。ここで、Ｆは強度（白黒の場合にはスカラー強度）を示し、ｘ及びｙは空間座標（フレーム内の位置）であり、ｔは時間である。ＫＬＴ技術の基礎ともなっている一般的な近似では、時間ｔと時間ｔ＋τとの間での画像変化を空間歪みとして次のように表す。
【数１】
2009517683.tif 000003
ここでｕ（ｘ，ｙ）及びｖ（ｘ，ｙ）は２つの空間方向における変位量である。式（１）は文献において「輝度変化拘束方程式」（ＢＣＣＥ）として知られている。
【００２１】
このことは、時間ｔでのすべての画像ポイントを適当な量だけ移動させること（変位という）によって時間ｔ＋τでの画像を得ることができることを意味する。画像中のすべてのピクセルの変位を知ることによって、画像自体の視差場を構築できる、すなわち関連フレームに適用されると他の時間でのフレームを構成可能な１セットのベクトルを構築できる。
【００２２】
実際には、ＢＣＣＥは正確には成り立たない。画像の一つ中の部分的に隠された対象物を考えれば十分である。すなわち、このような対象物は１つのフレームから次のフレームに「移動」せず、単に現れ又は消えている。同じ問題は画像のエッジでも見られ、画像エッジでは対象物が場面に入ってきたり、場面から外れたりする。いずれにしても、ＫＬＴ技術ではすべてのピクセルではなくいくつかの特徴を考慮し、これらの特徴について、変位計算の下流のＢＣＣＥ正確さの推定を行うことができる。
【００２３】
本発明の技術では、当該場面に属する異なる特徴について独立に２（又はそれより多い）フレーム間に存在する視差場を計算し、したがって散乱場を生成する。
【００２４】
要するに、図１に示されるように、本発明の方法は後に詳細に説明する以下のステップを含む。
-  カメラの固有のパラメータ（焦点距離や投影中心など）及び付随的なパラメータ（回転-並進マトリックス）を計算することによりカメラＴ１、Ｔ２を構成するステップ（ブロック１１０）；
-  画像ＩＭ１の特徴を抽出するステップ（ブロック１２０）；
-  校正パラメータを考慮して第２の画像ＩＭ２上の特徴をトラッキングするステップ（ブロック１３０）；及び
-  後に述べる第２の画像ＩＭ２中の許容領域内に存在するポイントを計算から除去するステップ（ブロック１４０）。
【００２５】
除去するステップは本発明の方法において好ましいものであるが、必須ではない。本方法の出力は、第１の画像ＩＭ１の特徴と第２の画像ＩＭ２の対応するポイントの特徴との一致である。
【００２６】
上述したように、散乱視差場を計算する課題は、２つの部分に分割できる。２つの部分とは、トラッキングされる対象物、すなわち画像特徴をいかにして選択するか、及び選択した対象物をいかにしてトラッキングするかである。本発明はトラッキング操作に関するものである。
【００２７】
２つの時刻ｔ及びｔ＋τでの上記関数Ｆは、２つの関数Ｉ及びＪとして次のように表すことができる。
【数２】
2009517683.tif 000004
及び
【数３】
2009517683.tif 000005
ここで、ｄは座標ｘ＝（ｘ，ｙ）を有するピクセルに関連付けられた変位ベクトルであり、２つの成分ｕ及びｖを含む。この変位を挿入することにより、式（１）により表されたＢＣＣＥを次のように書き換えることができる。
【数４】
2009517683.tif 000006
【００２８】
この方法は選択されたすべてのポイントに独立に適用されるので、動きを計算しなければならない対象物（すなわちピクセルｘ）が中心に位置しているピクセルの窓Ｗを考慮することができる。式（４）は窓Ｗ内において残差を除いて有効である。残差は次のように表すことができる。
【数５】
2009517683.tif 000007
【００２９】
最適な変位ベクトルｄは式（５）の残差を最小にすることにより得られる。式（５）は線形ではないので、それを解くには、線形に変換するのが好ましい。これは変位ベクトルｄが小さい場合に１次で切り捨てたテーラー近似を用いることによって次のように可能である。
【数６】
2009517683.tif 000008
ここで、ｇはｘ＝（ｘ，ｙ）にて求められた関数Ｊの勾配である。
【数７】
2009517683.tif 000009
【００３０】
窓Ｗ内に含まれるすべてのピクセルに対して式（６）を分離することにより、次の連立方程式が得られる。
【数８】
2009517683.tif 000010
ここで、Ｊｘ（ｐｎ）及びＪｙ（ｐｎ）は一般ピクセルｐｎにおける勾配ベクトルの２つの要素であり、Ｎは窓Ｗ内に含まれるピクセルの数である。
【００３１】
連立方程式（８）はマトリックス形式にて次のように表すことができる。
【数９】
2009517683.tif 000011
【００３２】
式（９）はコンパクトな形式Ａｄ＝ｂに書き直すことができる。マトリックスＡは、適用される窓内に含まれるピクセルにおける第２のフレームの輝度勾配から成る。ベクトルｂは、同じ窓内の２つのフレームのピクセル間での輝度差から成る。ベクトルｄは計算すべき変位である。変位は１ピクセル（よって離散座標を有する）に必ずしも向かっている必要はないが、より一般的には第２の画像の１ポイント（これも隣接した２つのピクセル間の中間に存在し得る）に向かっていることが分かる。
【００３３】
次のようにして各式に重みを掛けることにより、窓に属するすべてのピクセルに相対的重要度を割り当てるのが有利である。
【数１０】
2009517683.tif 000012
ここで、
【数１１】
2009517683.tif 000013
よって、一般ピクセルｐｎに割り当てられる重みはＷｎに等しい。窓の中心に存在しているピクセルに対してより大きな重要度を与えるように重みが用いられる。
【００３４】
この連立方程式はＮ個の式（Ｎ＞２）と２つの未知数から構成されており、最小２乗近似を表す正規方程式により次のように解くことができるので、この連立方程式は優決定の連立方程式である。
【数１２】
2009517683.tif 000014
ここで、
【数１３】
2009517683.tif 000015
【００３５】
ＫＬＴ技術はトラッキングすべきポイントを選択する基準を更に含む。この選択は、例えばＳｈｉ-Ｔｏｍａｓｉの教示に基づいた公知の技術により行うことができる。いずれにしても、この選択基準は、マトリックスＧの逆行列が得られること（invertibility）を保証しなければならない。
【００３６】
上記で述べた事項はすべて、図１のフレームＩＭ１及びＩＭ２と同様に同時に撮られ同じ場面を示す一対のフレームについても有効である。この場合、実際には、２つの関数Ｉ及びＪが第１の画像ＩＭ１及び第２の画像ＩＭ２にそれぞれ関連付けられる。２つのフレームＩＭ１、ＩＭ２が式（１）を満たすことができるために必要な条件は、２台のカメラＴ１、Ｔ２が互いに十分接近して配置されること、及び２台のカメラＴ１、Ｔ２が同じ場面部分を撮影することである。
【００３７】
同じ場面の２つの撮影の間の関係は、エピポーラ幾何により表される。両方の撮影において見ることのできる場面中のすべての要素は、２つのフレームＩＭ１、ＩＭ２内にて単純な式に従った位置に投影される。この式の係数は、３ｘ３要素から成る基本マトリックスＦ中に含まれている。２つのフレーム内での投影位置は、次のように同種の座標で特定される。
【数１４】
2009517683.tif 000016
及び
【数１５】
2009517683.tif 000017
ここで、ｘ１、ｙ１、ｘ２、ｙ２は、撮影された要素を示す２つのフレーム内での２つのピクセルの座標である。これらの座標は次式を満たす必要がある。
【数１６】
2009517683.tif 000018
したがって、これら２つのフレームのうち第１のフレーム内のポイントｍ１を考えると、第２のフレーム内のポイントｍ２は、積Ｆｍ１により係数が決定される直線上に存在しなければならない。対称的に、第２のフレーム内のポイントｍ２を考えると、ポイントｍ１は、積ｍ２ＴＦ中に含まれる係数を有する直線上に存在する。これらの直線はエピポーラと称される。これらの関係はエピポーラ幾何を構成し、これは基本マトリックスＦにより完全に表される。
【００３８】
本明細書においては、基本マトリックスを決定する固有のカメラ校正パラメータ及び付随的なカメラ校正パラメータが両方とも既知であると仮定する。しかしながら、出願人は、校正は推定誤差から影響を受け得るので、このようにして提供される情報を絶対的な拘束として用いるのは不正確となり得ることが分かった。
【００３９】
校正パラメータの知識から得られる情報を関連付けるためには、式（９）から得られる特定の関数の最小化としてＫＬＴ技術を解釈するのが便利である。この式は優決定の方程式であり、最小二乗近似により解くことができる。すなわち、その解法は、Ａｄ−ｂにより与えられるいわゆる残ノルム（residue norm）の最小を見つけることに対応する。したがって、上記で述べた問題を次のように、
【数１７】
2009517683.tif 000019
すなわち最小化すべき費用関数として言い換えることができる。式（１０）に導入された重みを考慮すると、式（１３）は次のようになる。
【数１８】
2009517683.tif 000020
【００４０】
実際には、このようにして得られたベクトルは常に正確であるわけではなく、すなわち一方のフレームからもう一方のフレームへの対象物の変位に必ずしも対応しているとは限らない。例えば、このことは、ＫＬＴアルゴリズムを基にした線形近似が有効でない場合に起こり得る。
【００４１】
２台のカメラの場合、校正に関する情報を考慮することができ、したがって結果を改善することができる。エピポーラ幾何は、変位ベクトルｄを計算するために特徴をサーチする必要のある第２のフレーム内で当該領域についての指示を与える。
【００４２】
本発明は、式（１４）中に既に含まれているものに加えるべき拘束に構成データを変換することにより、校正データを利用する。この拘束はエピポーラ情報にリンクされた費用項に変換される。この幾何が正確に知られているならば、サーチされるポイントはエピポーラ直線上に存在すべきである。推定により構成が得られること、したがって誤差又は不正確さを有することを考慮すると、校正情報に関係したバレンス（valence）を割り当てるのが更に好ましい。したがって、考慮しなければならないのは、本解法がエピポーラ直線から外れることであり、これは本発明において、エピポーラ線とサーチされるポイントとの距離の２乗に比例した項を費用関数（１４）に導入することによって得られる。
【００４３】
したがって、式（１４）は次の形式を仮定する。
【数１９】
2009517683.tif 000021
ここで、ρは、ポイントｚ＋ｄ（すなわちポイントｚ＝［ｘ  ｙ］Ｔからｄ＝［ｕ  ｖ］Ｔなる量だけ平行移動したポイント）とＬ（すなわちポイントｚに関連付けられたエピポーラ直線）とのユークリッド距離を表す関数である。係数λはあらかじめ設定しおく必要があり、これも基本マトリックスに割り当てられた信頼度に依存して発見的手法により決定できる。λの値が大きくなればなるほど、基本マトリックスの正確さが増すことを基にする。現実の解法がエピポーラ直線上に存在するよう拘束するまで、λを増すことができる。
【００４４】
エピポーラ直線は基本マトリックスＦにより得られる。第２のフレーム内で、ポイントｚ＋ｄから当該直線の距離は次式により表すことができる。
【数２０】
2009517683.tif 000022
ここで、係数ａ、ｂ及びｃは次に示す積により与えられる。
【数２１】
2009517683.tif 000023
その結果、当該直線上の任意のポイントｍ＝［ｘｍ  ｙｍ  １］Ｔは次式を満たす。
【数２２】
2009517683.tif 000024
【００４５】
式（１５）の解は次の正規方程式から得ることができる。
【数２３】
2009517683.tif 000025
ここで、ベクトルｐ及びｒは次式により定義される。
【数２４】
2009517683.tif 000026
及び
【数２５】
2009517683.tif 000027
【００４６】
ステップごとにテーラー級数の更新を行なう反復計算によってより正確な結果を得るために式（１１）及び（１４）を拡張できる。この場合、視差ベクトルは多くの項から構成される。ステップごとに１項が加えられ、最後の解は次式で表すことができる。
【数２６】
2009517683.tif 000028
ここで、すべての項は下記のベクトルである。
【数２７】
2009517683.tif 000029
【００４７】
ステップ数Ｍでの式（９）は下記のようになる。
【数２８】
2009517683.tif 000030
又は、簡単に下記のように示すことができる。
【数２９】
2009517683.tif 000031
【００４８】
したがって、式（１１）は反復数Ｍにて下記のようになる。
【数３０】
2009517683.tif 000032
【００４９】
この反復はＭ＝１にてｄ０＝０で初期化される。反復の総数はあらかじめ設定することもできるし、又は最後に加えられた項のノルムに依存して決定することもできる。
【００５０】
式（２０）に記載されたベクトルｒを修正することにより、式（１５）の解を与える正規方程式（１８）を上記の反復計算プロセスに適合させることができる。このベクトルは反復数Ｍにて下記の形式をとることが仮定される。
【数３１】
2009517683.tif 000033
【００５１】
ここまで説明したプロセスは、計算する必要がある変位ベクトルの方向についての情報を付加する、すなわち式（１５）がエピポーラ幾何に一致する変位ベクトルを生成する。しかしながら、このことはベクトル自体を正確に特徴付けるには十分ではあり得ない。というのは、エピポーラ直線に対する拘束が或る程度自由なままだからである。この或る程度の自由さは、式（１５）の第２項はエピポーラ直線に向かう解をとるが、第２のフレーム内の真の特徴位置に必ずしも向かってはいないからである。エピポーラ直線の許容領域を導入することで、それを半直線に変換することによって、この問題を小さくすることができる。
【００５２】
このチェックは、図２に関して、撮られた場面内で有限距離にて見いだし得るポイントＰを、第１のフレームＩＭ１内の特徴Ａに関連付けることができることに基づいている。したがって、ポイントＰの投射である第２のフレームＩＭ２に関連付けられたエピポーラ直線Ｌ上にポイントＢを配置できる。ポイントＡ上に投射される場面の任意の対象物は半直線ＡＰ上に存在するので、第２のフレーム内の当該対象物の投射は、半直線ＡＰの投射である半直線Ｓ上に存在する必要がある。したがって、この半直線はエピポーラ直線のサブセットである。
【００５３】
不確かな校正の信頼性に起因してエピポーラ直線から外れる可能性を考慮すると、図３から分かるように、ポイントＢを頂点として有しかつ半直線Ｓを含んだ許容領域Ｚまで許容可能なサブセットを拡張できる。
【００５４】
このような考えに基づくと、場面幾何を満たしていない変位ベクトルを効率的に除去できるチェックを実施できる。ポイントＢが第２のフレームＩＭ２内にある場合に有効なこのチェックにより、ポイントｚ＋ｄが許容領域Ｚ内に存在しないすべての候補｛ｚ、ｄ｝（特徴及び変位ベクトル）をこのように除去できる。領域Ｚは異なる形状を有し得る。Ｚは、ポイントＢの近くを通過する曲線により画定され半直線Ｓを含んだ平面のサブセットである必要がある。
【００５５】
半直線Ｓは下記のように表すことができる。
【数３２】
2009517683.tif 000034
ここで、Ｋは負でない係数であり、
【数３３】
2009517683.tif 000035
はエピポーラ直線に平行な方向ベクトルである。
【００５６】
半直線Ｓを定めるのに用いられる要素は、カメラ校正パラメータの知識から得ることができる。中でも、２台のカメラの固有のパラメータはマトリックスＫ１及びＫ２に含まれ、第２の機械に関連付けられた回転マトリックス及び平行移動ベクトル（付随的なパラメータ）はＲ及びｔで示される。詳しくは、Ｒｉｃｈａｒｄ  Ｈａｒｔｌｅｙ及びＡｎｄｒｅｗ  Ｚｉｓｓｅｒｍａｎのテキスト，「Ｍｕｌｔｉｐｌｅ  Ｖｉｓｉｏｎ  Ｇｅｏｍｅｔｒｙ」，Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，２０００，１５３〜１５６及び２４４頁を参照のこと。マトリックスＲ及びベクトルｔは第２のカメラに属する座標系を第１のカメラに属する座標系に変換する。第１のフレーム内の特徴Ａは同種の座標にて下記のように表すことができる。
【数３４】
2009517683.tif 000036
【００５７】
ポイントＢ（無限遠に存在するポイントＰの投影）はＡ及び校正パラメータにより下記のように表すことができる。
【数３５】
2009517683.tif 000037
ここでＲ３は回転マトリックスＲの第３行を示す。ベクトルｗはポイントＡから次式により得られる。
【数３６】
2009517683.tif 000038
方向ベクトル
【数３７】
2009517683.tif 000039
は次式により表すことができる。
【数３８】
2009517683.tif 000040
ここで、ｔ３は平行移動ベクトルｔの第３要素である。
【００５８】
例として、図３に関して、許容領域を次のようにして定めることができる。正確さを検証する必要があるポイントの位置は、和ｚ＋ｄにより与えられる。Ｂから開始しｚ＋ｄと交差する半直線が、特定の閾値より小さい半直線Ｓとの角度を形成する場合には、当該ポイントは許容領域に属する。この場合、それが属するか否かのチェックは、ベクトル項にて下記の関係を検証するものとして表すことができる。
【数３９】
2009517683.tif 000041
ここで、規格化されたベクトル間の内積は設定される閾値θ∈［０，１］を超える。最小の閾値は０であり、この場合には許容領域は、ポイントＢ内でエピポーラ直線に垂直な直線により画定されかつ半直線Ｓを含んだ半平面である。閾値が１の値に向かって更に増加すれば、許容領域は更に限定される。図３は０〜１の中間の閾値に対応する許容領域を示しており、上記の基準に基づき許容できないポイントｚ＋ｄ’の例が示されている。
【００５９】
上記処理の結果、処理装置ＰＵの出力として、第１のフレームＩＭ１から抽出された特徴と第２のフレームＩＭ２中に見いだされた対応するポイントとの間の関連性が得られ、よって当該ポイント自体にリンクされた変位ベクトルｄが得られる。
【００６０】
いくつかの例を図４〜９に示す。図４及び５は、本発明を構成するアルゴリズムを適用し、異なる角度から撮った同じ場面の一対のフレームを含む。
【００６１】
図６は元々の方法で実行されたＫＬＴトラッキング技術の結果を示し、図７は本発明の技術により得られた結果を示す。両図とも、トラッキングのために選択された特徴の変位ベクトルを線分として示す。図から分かるように、図７では線分が更に十分に密着して相互に方向付けられており、このことは誤差がより少ないことを示す。
【００６２】
図８及び９はいくつかの重要な詳細を示しており、本発明により与えられる利点がより明らかになっている。これらの画像の各々において、左上の長方形（８ａ、９ａ）は第１のフレームにより抽出された特徴を中心にしており、右上の長方形（８ｂ、９ｂ）は元のＫＬＴ技術により得られた第２のフレーム中の当該ポイントを中心にしており、右下の長方形（８ｃ、９ｃ）は本発明により得られた第２のフレーム中の当該ポイントを中心にしている。右の両長方形では、関連特徴に関連付けられたエピポーラ直線が示されおり、かなりの改善が得られたことが分かる。
【図面の簡単な説明】
【００６３】
【図１】２台のカメラと、本発明のプロセスを構成するブロックとを含んだビデオ撮影用システムを概略的に示す。
【図２】２台のカメラにより撮られた画像を概略的に示し、それらの一方の上に、もう一方の画像のピクセルに関連付けられたエピポーラ線を示している。
【図３】上記エピポーラ線と視差ベクトルの許容領域とを示す上記画像を表す。
【図４】本発明の技術と元の方法で実行されるＫＬＴ技術との比較テストのために異なる角度から撮られた同じ場面の一対のフレームを示す。
【図５】本発明の技術と元の方法で実行されるＫＬＴ技術との比較テストのために異なる角度から撮られた同じ場面の一対のフレームを示す。
【図６】元の方法で実行されるＫＬＴトラッキング技術の結果を示す。
【図７】本発明の技術により得られた結果を示す。
【図８】図６及び７に示された結果の比較を詳細に示す。
【図９】図６及び７に示された結果の比較を詳細に示す。
【符号の説明】
【００６４】
１００  ビデオ撮影システム
Ｔ１    第１のカメラ
Ｔ２    第２のカメラ
ＩＭ１  デジタル画像
ＩＭ２  デジタル画像
ＣＭ  カメラ校正モジュール
ＰＵ  処理装置
【図１】
2009517683.tif 000042
【図２】
2009517683.tif 000043
【図３】
2009517683.tif 000044
【図４】
2009517683.tif 000045
【図５】
2009517683.tif 000046
【図６】
2009517683.tif 000047
【図７】
2009517683.tif 000048
【図８】
2009517683.tif 000049
【図９】
2009517683.tif 000050
【国際調査報告】
2009517683.tif 000051
2009517683.tif 000052