(57)【要約】【課題】  質量中心の繰り返し使用によるカメラパンベクトルのロバスト推定【解決手段】  カメラパンベクトルを推定するための技術を実施および使用する、コンピュータプログラム製品を含む方法ならびに装置が開示される。複数のパラメータに基づいて動きベクトルを表すためのカメラモデルが提供される。動きベクトルの分布が生成される。動きベクトルの分布においてクラスタが特定される。特定されたクラスタの質量中心が決定される。決定された質量中心に基づいてカメラパンベクトルが提供される。【選択図】  図８
2005182830.tif 000002
【特許請求の範囲】
【請求項１】
カメラパンベクトルを推定するための方法であって、
動きベクトルの分布を生成する動作と、
前記動きベクトルの分布においてクラスタを特定する動作と、
前記特定されたクラスタの質量中心を決定する動作と、
前記決定された質量中心に基づいて前記カメラパンベクトルを提供する動作と、を備える、方法。
【請求項２】
請求項１記載の方法であって、
前記カメラパンベクトルは、画像パッチの中の前記動きベクトルを表しているカメラモデルのパラメータを含む、方法。
【請求項３】
請求項２記載の方法であって、
前記決定された質量中心に基づいて前記カメラパンベクトルを提供する前記動作は、前記決定された質量中心を前記カメラモデルの１つまたはそれ以上の前記パラメータとして提供することを含む、方法。
【請求項４】
請求項１記載の方法であって、さらに、
前記提供されたカメラパンベクトルをプロセッサ読み出し可能メモリに格納する動作を備える、方法。
【請求項５】
請求項１記載の方法であって、
前記動きベクトルは値を含み、
前記動きベクトルの分布を生成する前記動作は、
複数のビンを有する二次元ヒストグラムを生成する動作と、
前記動きベクトルの値を前記二次元ヒストグラムの適切なビンに提供する動作と、を含む、方法。
【請求項６】
請求項１記載の方法であって、さらに、
前記動きベクトルを第１の解像度で提供する動作と、
前記動きベクトルの分布を生成するのに先だって、前記動きベクトルを、前記第１の解像度よりも低い解像度である第２の解像度に投影する動作と、を備える、方法。
【請求項７】
請求項１記載の方法であって、
前記カメラパンベクトルは、単一の画素を含む画像パッチに対応して生成される、方法。
【請求項８】
請求項１記載の方法であって、
前記カメラパンベクトルは、複数の画素を含む画像パッチに対応して生成される、方法。
【請求項９】
請求項５記載の方法であって、
前記動きベクトルの分布においてクラスタを特定する動作は、
前記二次元ヒストグラムの第１の近傍区域の中のビンを累算する動作と、
前記二次元ヒストグラムの第２の近傍区域の中のビンを累算する動作と、
前記近傍区域のうちの１つを、ビンの累算がより多いものとして選択する動作と、
前記選択された近傍区域を、前記動きベクトルの分布において特定されたクラスタとして提供する動作と、を含む、方法。
【請求項１０】
請求項９記載の方法であって、
各近傍区域は、所定の大きさの窓の中に含まれる、方法。
【請求項１１】
請求項９記載の方法であって、
前記動きベクトルの分布においてクラスタを特定する動作は、さらに、
近傍区域を１つ選択するのに先立って、前記二次元ヒストグラムのさらに他の近傍区域の中のビンを累算する動作を含む、方法。
【請求項１２】
請求項１記載の方法であって、
前記特定されたクラスタの前記質量中心は、所定の大きさの窓の中で決定される、方法。
【請求項１３】
請求項１０記載の方法であって、
前記特定されたクラスタの前記質量中心は、前記近傍区域を含む前記１つまたはそれ以上の窓よりも大きいサイズの窓の中で決定される、方法。
【請求項１４】
カメラパンベクトルを推定するための装置であって、
動きベクトルの分布を生成するように構成された動きベクトル生成部と、
前記動きベクトルの分布においてクラスタを特定するように構成されたクラスタ特定部と、
前記特定されたクラスタの質量中心を決定するように構成された決定モジュールと、
前記決定された質量中心に基づいて前記カメラパンベクトルを提供するように構成されたカメラパン計算部と、を備える、装置。
【請求項１５】
請求項１４記載の装置であって、
前記カメラパンベクトルは、画像パッチの中の前記動きベクトルを表しているカメラモデルのパラメータを含む、装置。
【請求項１６】
請求項１５記載の装置であって、
前記カメラパンベクトル計算部は、前記決定された質量中心を前記カメラモデルの１つまたはそれ以上の前記パラメータとして提供するように構成される、装置。
【請求項１７】
請求項１４記載の装置であって、
前記動きベクトルは値を含み、
前記動きベクトル生成部は、複数のビンを有する二次元ヒストグラムを生成し、前記動きベクトルの値を前記二次元ヒストグラムの適切なビンに提供するように構成される、装置。
【請求項１８】
請求項１７記載の装置であって、
前記クラスタ特定部は、前記二次元ヒストグラムの第１の近傍区域の中のビンを累算し、前記二次元ヒストグラムの第２の近傍区域の中のビンを累算し、前記近傍区域のうちの１つをビンの累算がより多いものとして選択し、前記選択された近傍区域を前記動きベクトルの分布において特定されたクラスタとして提供するように構成される、装置。
【請求項１９】
プロセッサ読み取り可能な媒体に格納されたコンピュータプログラム製品であって、カメラパンベクトルを推定するための方法をコンピュータに実行させるように機能できる命令を備え、前記方法は、
動きベクトルの分布を生成する動作と、
前記動きベクトルの分布においてクラスタを特定する動作と、
前記特定されたクラスタの質量中心を決定する動作と、
前記決定された質量中心に基づいて前記カメラパンベクトルを提供する動作と、を含む、コンピュータプログラム製品。
【請求項２０】
請求項１９記載のコンピュータプログラム製品であって、
前記動きベクトルは値を含み、
前記動きベクトルの分布を生成する前記動作は、
複数のビンを伴う二次元ヒストグラムを生成する動作と、
前記動きベクトルの値を前記二次元ヒストグラムの適切なビンに提供する動作と、を含む、コンピュータプログラム製品。
【請求項２１】
請求項２０記載のコンピュータプログラム製品であって、
前記動きベクトルの分布においてクラスタを特定する動作は、
前記二次元ヒストグラムの第１の近傍区域の中のビンを累算する動作と、
前記二次元ヒストグラムの第２の近傍区域の中のビンを累算する動作と、
前記近傍区域のうちの１つをビンの累算がより多いものとして選択する動作と、
前記選択された近傍区域を前記動きベクトルの分布において特定されたクラスタとして提供する動作と、を含む、コンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、映像および図形処理の改良に関する。
【背景技術】
【０００２】
表示装置のための標準的な映像コンテンツおよびフィルムコンテンツは、低いリフレッシュレート（例えば、インターレース形式の映像マテリアルの場合は毎秒５０フィールド、フィルムをもとにしたマテリアルの場合は毎秒２４フレーム）で記録および表示される。プログレッシブ形式のデジタル表示装置を含む、このような装置に関連する問題は、１つには、表示アーチファクトの存在である。例えば、表示のリフレッシュレートが低いと、「エリアフリッカー」と呼ばれる表示アーチファクトが生じる可能性がある。人間の視覚は、末端にいくほどフリッカーに対して敏感になるので、エリアフリッカーは、表示サイズが大きくなるにつれて顕著になる。エリアフリッカーを低減させるための単純な解決法は、フィールドまたはフレームの高速入力（例えば、インターレース形式の映像の場合は毎秒１００フィールド）を繰り返し、表示のリフレッシュレートを増大させることである。この方法は、静止場面に対してならば、エリアフリッカーの問題を解決することができる。しかしながら、動きのある場面に対しては、このような高速入力の繰り返しによって、「モーションジャダー」または「モーションスミア」として知られる新たなアーチファクトが生じ、特に、コントラストの高い領域では顕著である。これは、人間の目が、動く対象の軌跡を追う傾向を有するからである。このため、動きを補償するフレーム補間が望まれている。このようなフレーム補間では、局所的な動きの軌跡の中間点にある補間フレームまたは補間フィールドにおいて画素計算が行われるので、視標追跡によって期待される画像の動きと、表示される画像の動きとの間の不一致が解消される。あるフィールドまたはフレームから次のフィールドまたはフレームに至る局所的な画像の動きの軌跡は、動きベクトルによって記述される。
【０００３】
動きベクトルは、画素レベル、画像パッチレベル、または対象レベルなど、様々なレベルの空間解像度で計算することができる。「画像パッチ」とは、フレームに表示される画像の任意の一部分を指して言う。画像パッチは、１つまたは複数の画素で構成され、様々な形状および大きさを採ることができる。個々の画素ごとに独立に動きベクトルを計算すれば、理論上は理想的なデータセットを得ることができるが、これには大量の計算が必要とされるので、実際は実行不可能である。個々の画像パッチごとに動きベクトルを計算すれば、計算の量を減らすことができるが、１つの画像パッチ内における動きベクトルの不連続性によって、アーチファクトが生じる可能性がある。対象を基準にして動きベクトルを計算すれば、理論上は高い解像度および少ない所要計算量を実現することができるが、対象の区分けが困難な問題として残される。
【０００４】
画像のノイズおよびその他の問題は、動きベクトルの計算および処理に誤差を生む可能性がある。調査によると、動きベクトルを正確に推定する目的で、様々な技術が提案されてきたことが知られている。これらの技術の１つがカメラモデルである。この技術では、フレームシーケンスを映像信号のかたちで記録するカメラの運動が数学的モデルによって表される。カメラモデルは、カメラのパン、ズーム、および回転を含むカメラの様々な運動を数学的に表すことができる。例えば、カメラのパン運動において、カメラモデルは、水平方向および／または垂直方向に一定速度で運動するカメラの動きに関連付けられた動きベクトルを、数学的に表すことができる。カメラモデルが望ましいのは、１つの画像パッチまたは１つの画像フレーム全体に含まれるあらゆる動きベクトルに関してグローバルなモデルを提供できるからである。したがって、カメラモデルを適用すれば、画像フレームの中のどの位置のどの動きベクトルをも数学的に予測することができる。
【０００５】
動きベクトルの推定にカメラモデルを使用する従来の方法に伴う問題の１つは、１つのフレームシーケンスに２つまたはそれ以上の独立に運動する対象が含まれる場合に生じる。このような状況では、独立に運動する対象に関連付けられた画像データにカメラモデルを適合させようとする際に、それらの独立に運動する対象によって欠陥が引き起こされる。例えば、１つのフレームシーケンスに、車および背景画像という２つの運動する対象が含まれる場合を考える。フレームの１０％を占める車は、水平方向に西向きに運動する。フレームの９０％を占める背景画像は、車と反対の東方向に運動する。テストの画像として望ましいのは、背景画像の方である。何らかの改善措置を採らない限り、背景画像に関連付けられて予測されたカメラモデルの動きベクトルは、車の運動の影響によって誤りを含むこととなる。とりわけ、カメラモデルを計算するための従来の技術は、カメラの回転を、正しいカメラパンではなく誤って背景画像に適合させると考えられる。また、欠陥を伴うこのカメラモデルによって予測される動きベクトルは、画像のあらゆるポイントで誤りを含むと考えられる。
【０００６】
したがって、画像フレームのシーケンスにカメラモデルを適合させるための技術であって、テストされる特定の運動する対象または背景以外の独立に運動する対象に関連付けられたデータを排除することによって、より正確なカメラモデルを実現する技術が必要とされている。
【発明の開示】
【０００７】
本発明の態様は、他の独立に運動する対象を含み得る１つのフレームシーケンスにおいて、１つの独立に運動する対象または背景に関連付けられた動きベクトルを予測するための、ロバスト適合を提供することのできる、カメラモデルを規定および適用することを含む。
【０００８】
一般に、本発明の一態様は、カメラパンベクトルを推定するための技術を実施および使用する、コンピュータプログラム製品を含む方法ならびに装置を提供する。先ず、複数のパラメータに基づいて動きベクトルを表すためのカメラモデルが提供される。次に、動きベクトルの分布が生成される。生成された動きベクトルの分布において１つのクラスタが特定される。特定されたクラスタの質量中心が決定される。決定された質量中心に基づいてカメラパンベクトルが提供される。
【０００９】
本発明の実施形態は、下記の特徴のうち、１つまたはそれ以上の特徴を含むことができる。すなわち、動きベクトルは、値の二次元のセットを含むことができ、動きベクトルの分布の生成は、複数のビンを有する二次元ヒストグラムの生成を含むことができる。動きベクトルの値は、二次元ヒストグラムの有する適切なビン中に提供される。また、動きベクトルは、その分布の生成に先だって、より低い解像度に投影することができる。
【００１０】
動きベクトルの分布におけるクラスタの特定は、二次元ヒストグラムの第１の近傍区域の中のビンを累算すること、二次元ヒストグラムの第２の近傍区域の中のビンを累算すること、いずれかの近傍区域をビンの累算がより多いものとして選択すること、そして、選択された近傍区域を動きベクトルの分布において特定されたクラスタとして提供すること、を含むことができる。
【００１１】
本発明の１つまたはそれ以上の実施形態が、添付の図面および以下の説明で詳細に示される。本発明の他の特徴、目的、および利点は、以下の説明および添付の図面、ならびに特許請求の範囲から明らかになる。
【００１２】
図面において、類似の参照番号は、類似の構成要素を示すものとする。
【発明を実施するための最良の形態】
【００１３】
本発明の実施形態は、画像パッチに対してその動きベクトルの数学的モデルを提供するために使用されるカメラモデルを含む。カメラモデルは、１つのフレームシーケンスにおけるカメラの運動を表すものである。例えば、カメラモデルは、水平および／または垂直のカメラパン、ズームインまたはズームアウト操作、および回転操作を提供するために使用することができる。また、カメラモデルは、上記のカメラ運動の１つまたはそれ以上を組み合わせたものを表すこともできる。カメラモデルは、１つのフレームシーケンスに関してその動きベクトルをグローバルに記述するものである。
【００１４】
カメラモデルは、独立に計算される各画像パッチ位置におけるローカルベクトルとは対照的に、フレームコンテンツのグローバルな運動を記述するので、より正確な、すなわちより真実に近い動きベクトルを見つけるのに役立つ。一般に、フレームの全ての位置におけるカメラ運動に基づく動きベクトルは、単純なモデルの使用によって、極めて容易に予測することができる。例えば、カメラレンズが遠景をパンする場合は、どの動きベクトルも同一で、なおかつ、カメラの速度に等しいと考えられる。もう１つは、カメラレンズが、例えば壁に掛かった絵など、平坦な表面上にある対象にズームインする場合である。この場合は、どの運動ベクトルも放射方向で、なおかつ、画像の中心から周辺にかけてゼロ値から最大値へと増大する。
【００１５】
本発明の実施形態は、他に独立に運動する対象を含み得るフレームシーケンスにおいて、１つの独立に運動する対象に関連付けられた動きベクトルを予測するためのロバスト適合を提供することのできる、カメラモデルを規定および適用するための方法ならびに装置を提供する。本明細書において開示されるのは、画像フレームのシーケンスにカメラモデルを適合させるための技術であって、テストされる特定の運動する対象または背景以外の独立に運動する対象に関連付けられたデータを排除することによって、より正確なカメラモデルを実現する技術である。テストされる特定の運動する対象以外の独立に運動する対象を排除することによって、より正確なカメラモデルを計算し、ひいては、より正確な動きベクトルを予測することが可能になる。
【００１６】
本発明の実施形態は、カメラモデルのためのパラメータの決定と、決定されたカメラモデルパラメータを使用した動きベクトルの生成とを可能にする。先ず、メモリに格納されている既存の動きベクトルのセットが提供され、そこからカメラモデルパラメータが計算される。後述されるように、数学的モデルの適用によって、既存の動きベクトルに対して最良適合方法（線形最小二乗法など）が施され、その結果、カメラモデルパラメータが推定される。カメラモデルパラメータは、次いで、デジタル映像フレームシーケンスの中の後続フレームに対してその動きベクトルを予測するために使用される。具体的な一実施形態において、このカメラモデルを使用した後続の動きベクトルの推定は、２００４年４月２６日出願の同時係属の米国特許出願第１０／８３３，１９８号「動きベクトルの一時フィルタリング（Temporal Motion Vector Filtering）」に記載されるような帰納的階層的プロセスを取り入れている。本文献は、引用によって本明細書に援用されるものとする。
【００１７】
独立に運動する対象（それらの中のいくつかは、互いに反対方向に動いている）を含む１つのフレームシーケンスに対してそのカメラモデルパラメータを計算するにあたって、本発明の実施形態は、独立に運動する対象のうち主要な１つにカメラモデルを適合させ、その他の独立に運動する対象を排除する技術を提供する。主要な対象は、ほとんどの状況下では背景である。先ず、第１の、すなわち最初の解像度を有する入力された動きベクトルのセットが低い解像度に投影され、メモリ資源の節約が図られる。次いで、全ての動きベクトル値に関するヒストグラムが生成され、動きベクトルの分布が作成される。ヒストグラムのビンの中の動きベクトル値が累算され、主要な動きベクトルクラスタが特定される。次いで、二次元分布において他の動きベクトルクラスタを排除した状態で、このクラスタの質量中心が計算され、所望のロバスト適合が達成される。この質量中心は、カメラモデルの１つまたはそれ以上の変換（即ちパンパラメータ）を表すものである。カメラモデルパラメータは、次いで、カメラモデルを使用してその後に行われる動きベクトルの推定に使用される。このようにすれば、視標追跡によって期待される画像の動きと、デジタル映像に表示される画像の動きと、の間にほとんどまたは全く不一致がないように、効率良くかつ精度良く動きベクトルを決定することができる。
【００１８】
カメラモデルの数学的表現は、次の通りである。
【００１９】
【数１】
2005182830.tif 000003
【００２０】
上記の式において、カメラモデルは、カメラモデルパラメータＳy，Ｓx，ｒ1，ｒ2，ｔy，ｔxを画像の中の位置シーケンス（ｘ，ｙ）にあてはめることによって、複数の動きベクトルの推定値Ｍy，Ｍxを提供する。Ｓy，Ｓx，ｒ1，ｒ2，ｔy，ｔxは、カメラの運動を表すカメラモデルパラメータである。上記のモデルにおいて、ｔy，ｔxは、カメラをパンする際の水平および垂直の変換をそれぞれ表すパラメータである。カメラのパンに関連付けられた動きベクトルが、図２Ａに例示されている。上記の式において、ｒ1，ｒ2は、カメラの回転を表すパラメータである。図２Ｂは、カメラの回転に関連付けられた動きベクトルを例示している。Ｓy，Ｓxは、ズームアウトまたはズームインの操作に関連付けられたパラメータであって、図２Ｃに例示されている。
【００２１】
上述の実施形態において、パラメータＳy，Ｓx，ｒ1，ｒ2，ｔy，ｔxは、米国特許出願第１０／８３３，１９８号に記載されている帰納的階層的プロセスを使用して決定された動きベクトルのセットを使用して計算される。したがって、動きベクトルは、第１の画像フレームにソース相関窓を適用すると共に、後続の画像フレームにターゲット相関窓を適用し、次いで、ターゲット相関窓がソース相関窓に最も良く一致するように、すなわち、ターゲット相関窓のコンテンツがソース相関窓のコンテンツに可能な限り一致するようにターゲット相関窓を配置することによって決定される。また、帰納的階層的方法は、複数の解像度レベルの画像フレームを使用する。先ず、最も高い解像度レベルに対応する先の最適動きベクトルが最も低い解像度レベルに投影され、それがテストされ、１回またはそれ以上に渡って更新されることによって、最も低い解像度レベルに対応する最適動きベクトルが決定される。この最適動きベクトルは、次いで、より高い解像度レベルに伝搬され、更なる調整を経た後に、新たな最適動きベクトルとして決定される。このプロセスは、最も高い最初の解像度レベルに到達するまで繰り返され、その結果、最初の解像度レベルに対応する最適動きベクトルが特定される。
【００２２】
図１は、米国出願第１０／８３３，１９８号の帰納的階層的プロセス（１００）の一実施形態を示している。ただし、ここでは、複数の解像度レベルの画像フレームが既に生成されたものと仮定する。図１からわかるように、動きベクトルを決定するための帰納的階層的プロセス（１００）は、先の画像フレームからの動きベクトルを、最も低い解像度レベルに投影することから開始する（ステップ１０２）。この最も低い解像度レベルにおける最適動きベクトルを見つけるために、更新ベクトルのセットが生成され、テストされる（ステップ１０４）。一実施形態において、このテストは、動きベクトルの起点を中心とするソース相関窓と、対応する各更新ベクトルの終点を中心とするターゲット相関窓との間で、それぞれの対応位置にある画素を比較することによって実施される。この比較は、例えば、ソース窓の中の各画素の輝度値を、それぞれのターゲット窓の中の対応画素から差し引くことによって実施される。この場合は、絶対差の合計（ＳＡＤ）が最小となるソース相関窓とターゲット相関窓とのペアを探すことによって、最適な一致が定められ、このソース相関窓とターゲット相関窓とのペアに関連付けられたベクトルが、最適動きベクトルになる。
【００２３】
最小のＳＡＤが見つかると、最適ベクトルが選択される（ステップ１０６）。プロセス（１００）は、次いで、より高い解像度レベルが存在するか否かを調べる（ステップ１０８）。より高い解像度レベルが存在する場合は、プロセスは、最適ベクトルを次に高い解像度レベルに伝搬し（ステップ１１０）、ステップ１０４〜１０８を繰り返す。より高い解像度レベルが存在しない場合は、プロセスは、ステップ１１２に進む。ステップ１１２では、最適ベクトルが動きベクトルとして選択され、動きを補償するために使用される。こうして、現行のフレームに対するプロセスが完了する。
【００２４】
図１のステップ１１２において決定された最適ベクトルは、次いで、上記の式（１）によって表される数学的モデルにＭy，Ｍxとして代入することができる。当業者ならば明らかなように、Ｍy，Ｍxとしては、図１の任意の低い解像度（例えばステップ１０４の解像度）に対応して決定された最適ベクトルを使用しても良い。他の実施形態では、カメラモデルの式に、Ｍy，Ｍxとして他のベクトルを代入しても良い。なお、上述の実施形態では、線形最小二乗法の適合方法が使用されているが、他にも、任意の適切なデータ適合技術が使用可能である。こうして、Ｓy，Ｓx，ｒ1，ｒ2，ｔy，ｔxについて式を解くために、線形最小二乗の適合方法が実施される。すなわち、上記の数学的モデルによれば、既知のｘ，ｙ位置に対応する既知の値のセットＭy，Ｍxが提供されるので、行列反転動作の実施によって、未知のパラメータＳy，Ｓx，ｒ1，ｒ2，ｔy，ｔxを決定することができる。
【００２５】
カメラモデルパラメータの決定後、これらのカメラモデルパラメータは、画像パッチまたはフレームの中の位置ｙ，ｘに対応するカメラモデル動きベクトルＭy，Ｍxを生成するために適用され、その結果、上述された帰納的階層的プロセスの１回またはそれ以上の繰り返しに使用されるベクトル候補が提供される。例えば、カメラモデルによって予測されるこれらの動きベクトルは、ＳＡＤを計算するためのテスト候補として、更新ベクトルと共に使用することができる。次いで、図１のステップ１０６において、全てのテスト候補をもとにして、最適ベクトルが決定される。
【００２６】
図３は、カメラモデルパラメータを計算するため、そして、これらのカメラモデルパラメータを使用して動きベクトルを生成するための、本発明の一実施形態に従った装置３００のブロック図である。図４は、図３の装置の動作を説明した方法４００のフローチャートである。ステップ４０５において、例えば図１のステップ１０６において決定された最適ベクトルなどのテストベクトルＭy'，Ｍx'が、カメラモデルパラメータ計算部３１０によって、メモリ３０５から読み出される。このカメラモデルパラメータ計算部３１０は、主に、ソフトウェアのかたちで実装されることが好ましいが、当業者ならば理解できるように、ソフトウェアとハードウェアとの様々な組み合わせを使用することが可能である。メモリ３０５は、例えばＳＤＲＡＭのような、プロセッサによる読み取りが可能な任意の適切な記憶媒体である。
【００２７】
図４のステップ４１０において、カメラモデルパラメータ計算部３１０は、上述のように、読み出された動きベクトルと、それに対応する既知のｘ，ｙ位置とに基づいて、カメラモデルパラメータＳy，Ｓx，ｒ1，ｒ2，ｔy，ｔxを計算する。すなわち、カメラモデルパラメータＳy，Ｓx，ｒ1，ｒ2，ｔy，ｔxを決定する目的で、行列反転の動作が実施される。ステップ４１５において、カメラモデルパラメータ計算部３１０は、次いで、計算されたこれらのカメラモデルパラメータＳy，Ｓx，ｒ1，ｒ2，ｔy，ｔxを、１つまたはそれ以上のレジスタに格納するために、メモリ３１０に出力する。ステップ４２０において、カメラモデル動きベクトル生成部３１５は、カメラモデルパラメータＳy，Ｓx，ｒ1，ｒ2，ｔy，ｔxを、メモリ３１０のレジスタから読み出す。したがって、ステップ４２５において、カメラモデル動きベクトル生成部３１５に画像のｘ，ｙ位置が提供されると、カメラモデル動きベクトル生成部３１５は、ステップ４３０において、上記のカメラモデルの式を適用し、動きベクトルＭy，Ｍxを生成することができる。これらの動きベクトルＭy，Ｍxは、カメラモデル動きベクトル生成部３１５によって出力され、ステップ４３５において格納することができる。帰納的階層的プロセスの次の繰り返しの際は、帰納的に且つ階層的に予測されたベクトルに加えて、格納されたこれらの動きベクトルがテスト候補として使用可能である。
【００２８】
図５には、Ｘ方向およびＹ方向に沿った動きベクトルの二次元表現５００が例示されている。図５において、動きベクトル５０５ａ〜５０５ｅのグループは、カメラモデルが適合されることが望ましい、独立に運動する対象を表している。一方で、動きベクトル群５１０は、カメラモデルから排除されることが望ましい、独立に運動する別の画像すなわち対象に関連付けられた動きベクトルである。この例において、カメラモデルが採用するのはパンのケースであるので、上記の数学的モデルのうち、計算する必要があるのはｔy，ｔxの値のみである。ここで、動きベクトル５０５ａ〜５０５ｅの大部分は同じであるので、カメラパンモデルは、これらの動きベクトル５０５ａ〜５０５ｅのモデルの提供を目的として適合されることが望ましい。カメラモデルが有効であるためには、カメラパンモデルの変換パラメータｔy，ｔxが計算される際に、動きベクトル群５１０が例外値として排除されることが望ましい。以下で説明される技術は、カメラモデルパラメータの計算から動きベクトル群５１０を排除することによって、ロバストでかつ正確なカメラモデルの適合を達成する。
【００２９】
図６Ａは、代表的な動きベクトルのセットＭy，Ｍxに関するそのＭy値およびＭx値の二次元分布６００を示している。動きベクトルＭy，Ｍxの値は、全て、二次元表現の範囲内にある。すなわち、全てのＭx値は、−Ｍx ｍａｘから＋Ｍx ｍａｘまでの範囲に分布し、同様に、全てのＭy値は、−Ｍy ｍａｘから＋Ｍy ｍａｘからまでの範囲に分布する。一例では、Ｍx値は−３２から＋３２までの範囲内であり、Ｍy値は−２４から＋２４までの範囲内である。当業者ならば明らかなように、これらのＭy値およびＭx値の範囲は例示に過ぎないので、本発明の実施形態にしたがって、他にも様々な範囲が使用可能である。図６において、動きベクトルは、その大半がクラスタ６０５を構成している。これは、どの動きベクトルも、カメラのパンを表すほぼ同じ値を有することを意味する。したがって、クラスタ６０５の質量中心を決定すれば、カメラモデルのパラメータｔy，ｔxを得ることができる。クラスタ６０５の外側のベクトルは、ｔy，ｔxの計算の際に、例外値として排除されることが好ましい。
【００３０】
図６Ｂは、例えば図６Ａの動きベクトル値などのＭx値の分布を側面から示した図である。Ｍx値の分布は、第１のピーク６１５および第２のピーク６２０を呈している。これらのピーク６１５，６２０は、特定のＭx値を有するベクトルの数を示している。したがって、第１のピーク６１５は、Ｍx1の値を有するベクトルが沢山集中したために形成されたものである。小さめの第２のピーク６２０は、それとは別にＭx2の値を有するベクトルが集中したために形成されたものである。特定のＭx値を有するベクトルがより多数であるピーク６１５は、ここでは主要ピークと称され、カメラモデルのパラメータｔy，ｔxの真の値を突き止めるための近傍区域を表している。本発明の実施形態に従った方法および装置は、主要ピーク６１５を特定し、ピーク６２０のような小さめのピークを排除し、主要ピーク６１５の質量中心をカメラモデルパラメータｔy，ｔxとして決定することを可能にする。
【００３１】
図７は、離散値Ｍy，Ｍxを累算するためのビン７０５ａ〜７０５ｃを伴う二次元ヒストグラムの一例を示した平面図である。Ｍy，Ｍxは離散的であるので、ヒストグラムはグリッドとして表現され、グリッド内の各ブロックすなわちビンによって、特定のＭy値またはＭx値が表される。Ｍxの値が−３２から＋３２までの範囲内で、かつ、Ｍyの値が−２４から＋２４までの範囲内である上記の例では、動きベクトル値の二次元分布は、特定の動きベクトル値が配置されうる総分布数すなわち総ビン数が６４×４８であるグリッドサイズを有すると考えられる。ビンの集合は、６４×４８の二次元ヒストグラムを提供する。ビン７０５は、各ビンにおける動きベクトル値Ｍy，Ｍxの数を表すビンカウント数を有する。例えば、ビン７０５ｂは、カウント数が７の動きベクトルを有し、ビン７０５ｃは、カウント数が１００の動きベクトルを有する。各ビンカウント数は、そのビンに動きベクトル値が分配されるたびに増加される。この例において、ビン７０５ｃを含むビンの近傍区域は、ヒストグラムの主要ピークを表している。以下で説明される技術を使用して、カメラパンベクトルの推定値を正確に決定するためには、この主要ピークを特定することが望ましい。
【００３２】
図８および図９は、本発明の一実施形態にしたがって実施される、カメラパンベクトルを推定するための方法８００および装置９００をそれぞれに示している。当業者ならば理解できるように、装置９００は、ハードウェアおよびソフトウェアを様々に組み合わせて実装することができる。図８の方法は、図９を参照にしながら説明される。ステップ８０５において、カメラモデルが提供される。このカメラモデルは、上述のように、図３および図４を参照にして説明された方法にしたがって定められる。カメラモデルは、例えば上述された動きベクトルＭy，Ｍxの二次元セットのような複数のカメラモデル動きベクトルを、デジタル映像シーケンスの複数のフレーム中の一画像パッチに対応して生成するために使用される。カメラモデルは、上述のように、ｔy，ｔxなどの複数のパラメータを含み、これらのパラメータｔy，ｔxは、動きベクトルＭy，Ｍxを生成する目的で、ｙ座標およびｘ座標に適用される。カメラモデルの動きベクトルは、例えば１：１などの第１の解像度で提供される。
【００３３】
図８のステップ８１０において、カメラモデルの動きベクトルＭy，Ｍxは、より低い解像度に投影されることが好ましい。動きベクトルをより低い解像度に投影するこのステップは、メモリを節約すると共に所要の計算量を減らすことができる。解像度としては、様々なレベルが使用可能である。一例では、最初の、すなわち第１の解像度が１：１であるのに対し、より低い解像度は１：２、１：４、または１：８である。したがって、図９の二次元ヒストグラムの中のビンの数は、大幅に低減される。例えば、もとは−３２から＋３２までの範囲のＭx値と、もとは−２４から＋２４までの範囲のＭy値とが、１：２まで低減されると、対応するビンカウント数も、６４×４８から３２×２４に低減される。すなわち、動きベクトルの値が２分の１に縮小されると、ビンカウント数は４分の１に低減される。この例では、隣り合う４つのビンのビンカウント数が効果的に組み合わされて、単一のビンを形成している。当業者ならば理解できるように、低減された解像度としては、他の様々な解像度が使用可能である。
【００３４】
図８のステップ８１５において、図９に示された動きベクトル生成部９１０は、動きベクトルの分布を生成する。動きベクトルが二次元である場合は、図７を参照にして上述されたように、二次元の動きベクトルセットの特定の値が、複数のビンを伴う二次元ヒストグラムに分配される。
【００３５】
図８のステップ８２０において、図９に示されたクラスタ特定部９２０は、図７の二次元ヒストグラムの中から主要ピークを見つけ出す。すなわち、クラスタ特定部９２０は、動きベクトル値の分布において最も多くの動きベクトルが集中した箇所を、その分布のクラスタとして特定する。一実施形態において、この特定のステップは、図７に示されるような二次元ヒストグラムの複数の近傍区域の中のビンを累算することを含む。これらの近傍区域は、ｐ×ｑの窓７１０または３×３、４×４、１２×１２、もしくは１００×１００などの他の所定の大きさの窓として定められ、ヒストグラムの中を動かされ、窓に一定数のビンが含まれるように様々な位置に配置される。ある特定の位置にある窓に関し、その窓に含まれるビンカウント数が累算され、その窓すなわち近傍区域に関連付けられたビンカウント総数が提供される。次いで、ビンの累算数のより多いまたは最も多い近傍区域が、特定されたクラスタとして選択される。特定されたこのクラスタは、図６Ｂのピーク６１５のような、ヒストグラムの主要ピークを提供する。
【００３６】
図８のステップ８２５において、図９に示された決定モジュール９３０は、ステップ１０２０において特定されたクラスタの質量中心を決定する。この質量中心の計算は、所定の大きさの別の窓の中で実施されることが好ましい。一実施形態において、この窓の大きさは、ステップ８２０においてビンの累算に使用された近傍区域を含むｐ×ｑの窓よりも大きいｍ×ｎである。上述されたカメラモデルの数学的表現に従うと、ステップ８２５において決定された質量中心は、ステップ８３０において、後続の動きベクトルの計算に使用される１つまたはそれ以上のカメラモデルパラメータとして提供される。例えばカメラパンのケースでは、決定された質量中心は、変換パラメータｔx，ｔyとして提供される。ステップ８１０において、動きベクトルが最初の解像度からより低い解像度に投影される実施形態では、決定された質量中心は、最初の解像度に再び投影されることが好ましい。実施形態によっては、この投影のための計算が、より正確な投影を実現する目的で、浮動小数点を使用して行われる場合もある。カメラモデルパラメータは、次いで、ステップ８３５において格納され、後に、上記の式（１）を使用してカメラパンモデルの動きベクトルＭy，Ｍxを生成するために、図９のカメラパン計算部９４０によって読み出される。一実施形態において、これらのカメラパンモデルの動きベクトルＭy，Ｍxは、次いで、米国出願第１０／８３３，１９８号に記載されている帰納的階層的プロセスのためのテスト候補を決定するために使用される。
【００３７】
カメラモデルによって予測されたベクトルを、帰納的階層的プロセスにおける更なる候補ベクトルとして使用すれば、帰納的階層的検索の帰納部分が真の極小点ではなく偽の極小点に収束する可能性を、最小限に抑えることができる。このような候補としての予測ベクトルの使用は、このプロセスを真の極小点に導くことができる。実施形態によっては、本明細書において説明されるように、カメラモデルによって予測または生成された動きベクトルが、ＳＡＤを計算するためのテスト候補としても使用される。
【００３８】
図３および図９の装置を含む本発明の実施形態は、デジタル電子回路のかたちで、または、コンピュータのハードウェア、ファームウェア、ソフトウェア、もしくはそれらの組み合わせのかたちで実装することができる。本発明による装置の実施形態は、プログラマブルプロセッサによる実行のための、機械読み取り可能な記憶装置の中に具体的に組み込まれたコンピュータプログラム製品の形態で実装することができる。また、本発明による方法のステップは、プログラマブルプロセッサが命令プログラムを実行し、入力データに作用すると共に出力を生成することによって本発明の機能を実行することにより実施することができる。本発明の実施形態は、データおよび命令を送受信するためにデータ記憶システムに連結された少なくとも１つのプログラマブルプロセッサと、少なくとも１つの入力装置と、少なくとも１つの出力装置と、を含むプログラマブルシステム上で実行可能である１つまたはそれ以上のコンピュータプログラムの形態で実装することができる。各コンピュータプログラムは、プロシージャ型もしくはオブジェクト指向型の高水準のプログラミング言語、または、もし所望であればアセンブリもしくはマシン言語で記述することができる。いずれの場合も、その言語は、コンパイラ型言語またはインタプリタ型言語のいずれかであって良い。適切なプロセッサの例としては、例えば、汎用および特殊用途の両方のマイクロプロセッサが含まれる。一般に、プロセッサは、読み出し専用メモリおよびランダムアクセスメモリの一方または両方から命令およびデータを受信する。一般に、コンピュータは、データファイルを格納するための１つまたはそれ以上の大容量の記憶装置を含む。このような記憶装置の例としては、内部ハードディスクおよびリムーバブルディスクなどの磁気ディスク、光磁気ディスク、ならびに光ディスクなどが含まれる。コンピュータプログラム命令およびデータを具体的に組み込むのに適した記憶装置としては、あらゆる形態の不揮発性メモリが含まれ、例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュメモリ装置などの半導体メモリ装置、内部ハードディスクおよびリムーバブルディスクなどの磁気ディスク、光磁気ディスク、ならびにＣＤ−ＲＯＭディスクが含まれる。上記のいずれも、ＡＳＩＣ（特定用途向け集積回路）によって補足される、あるいは、ＡＳＩＣに組み入れることができる。
【００３９】
以上では、本発明の様々な実施形態が説明された。しかしながら、本発明の趣旨および範囲から逸脱することなく、様々な変更形態が実現可能である。したがって、他の実施形態も、添付の特許請求の範囲に含まれる。
【図面の簡単な説明】
【００４０】
【図１】動きベクトルを決定するための帰納的階層的プロセスのフローチャート。
【図２Ａ】カメラのパンに関連付けられた動きベクトルの一例を示した図。
【図２Ｂ】カメラの回転に関連付けられた動きベクトルの一例を示した図。
【図２Ｃ】カメラのズームイン操作に関連付けられた動きベクトルの一例を示した図。
【図３】カメラモデルパラメータを計算し、さらに、カメラモデルを使用して動きベクトルを生成するための装置のブロック図。
【図４】本発明の一実施形態に従ったカメラパンベクトルを推定するための方法のフローチャート。
【図５】独立に運動する複数の対象に関連付けられた動きベクトルの一例を示した図。
【図６Ａ】二次元に沿った動きベクトルの分布を示した図。
【図６Ｂ】動きベクトル値の分布を側面から示した図。
【図７】複数のビンを有する二次元ヒストグラムにおける動きベクトル値の分布を示した図。
【図８】デジタル映像のフレームシーケンスに関し、カメラモデルを使用して動きベクトルを推定するための方法のフローチャート。
【図９】本発明の一実施形態に従ったカメラパンベクトルを推定するための装置を示した図。
【図１】
2005182830.tif 000004
【図２Ａ】
2005182830.tif 000005
【図２Ｂ】
2005182830.tif 000006
【図２Ｃ】
2005182830.tif 000007
【図３】
2005182830.tif 000008
【図４】
2005182830.tif 000009
【図５】
2005182830.tif 000010
【図６Ａ】
2005182830.tif 000011
【図６Ｂ】
2005182830.tif 000012
【図７】
2005182830.tif 000013
【図８】
2005182830.tif 000014
【図９】
2005182830.tif 000015
【外国語明細書】
1. TITLE OF THE INVENTION
ROBUST CAMERA PAN VECTOR ESTIMATION USING ITERATIVE CENTER OF MASS
2. DETAILED DESCRIPTION OF THE INVENTION
BACKGROUND
[0001]    This invention relates to improving video and graphics processing.
[0002]    Standard video and film content for display devices is recorded and displayed at low  refresh rates (for example, 50 fields/sec for interlaced video material, and 24 frames/sec for film-originated material).  One associated problem with such devices, including progressive digital display devices, is the presence of display artifacts.  For example, one display artifact referred to as "area flicker" can occur due to the low display refresh rate. The area flicker becomes more visible as the size of the display increases, due to the high sensitivity to flicker in the human visual peripheral region.  A simple solution for reducing the area flicker is to increase the display refresh rate by repeating the input fields or frames at a higher rate (for example, 100 fields/sec for interlaced video).  This solves the area flicker problem for static scenes. However, the repetition introduces a new artifact in scenes with motion, known as "motion judder" or "motion smear," particularly in areas with high contrast, due to the human eye's tendency to track the trajectory of moving objects.  For this reason, motion compensated frame interpolation is preferred, in which the pixels are computed in an interpolated frame or field at an intermediate point on a local motion trajectory, so that there is no discrepancy between an expected image motion due to eye tracking and a displayed image motion.  The local image motion trajectory from one field or frame to the next is described by a motion vector. 
[0003]    Motion vectors can be computed at different levels of spatial resolution, such as at a pixel level, at an image patch level, or at an object level.  "Image patch" refers to any portion of an image displayed in a frame.  The image patch can be a single pixel, a plurality of pixels, and can have various shapes and sizes.  Computing a motion vector for every pixel independently would theoretically result in an ideal data set, but is unfeasible due to the large number of computations required.  Computing a motion vector for each image patch reduces the number of computations, but can result in artifacts due to motion vector discontinuities within an image patch.  Computing motion vectors on an object basis can theoretically result in high resolution and lower computational requirements, but object segmentation is a challenging problem.
[0004]    Image noise and other problems can lead to errors in the computation and processing of motion vectors.  Various techniques have been proposed in the search for accurate motion vector estimation.  One of these techniques is the camera model, in which a mathematical model represents the movement of a camera which recorded the sequence of frames in a video signal.  Camera models can provide mathematical representations of various camera movements including camera pans, zooms, and rotations.  For instance, in a camera pan movement, the camera model provides a mathematical representation of the motion vectors associated with the camera moving in a horizontal and/or vertical direction at a constant velocity.  The camera model is desirable because it can provide a global model of all of the motion vectors in an image patch or entire image frame.  Thus, applying the camera model, every motion vector can be mathematically predicted at every location in the image frame.
[0005]    One problem with conventional uses of camera models for motion vector estimation arises when there are two or more independently moving objects in a sequence of frames.  In this situation, the independently moving objects introduce flaws into the camera model when attempting to fit the camera model to image data associated with the independently moving objects.  For instance, in one sequence of frames, there are two moving objects:  a car and a background image.  The car, occupying 10 % of the frame, moves westward in the horizontal direction.  The background image, occupying 90 % of the frame, moves eastward, opposite the car.  The background image is the desired image for testing.  Unless remedial measures are taken, the predicted camera model motion vectors associated with the background image will be erroneous due to the effect of the car movement.  In particular, conventional techniques for computing the camera model would improperly fit a camera rotation to the background image rather than a proper camera pan.  Resulting motion vectors predicted by this flawed camera model would also be erroneous at every point in the image.
[0006]    Therefore, what is needed is a technique for fitting a camera model to a sequence of image frames wherein data associated with independently moving objects other than a particular moving object or background to be tested is excluded to achieve a more accurate camera model. 
SUMMARY 
[0007]    Aspects of the present invention involve defining and applying a camera model which provides a robust fit for predicting motion vectors associated with an independently moving object or background in a sequence of frames in which there may be other independently moving objects.
[0008]    In general, in one aspect, the invention provides methods and apparatus, including computer program products, implementing and using techniques for camera pan vector estimation.  A camera model is provided for representing motion vectors based on a plurality of parameters.  A distribution of the motion vectors is generated.  A cluster in the distribution of motion vectors is identified.  A center of mass of the identified cluster is determined.  The camera pan vector is provided based upon the determined center of mass.
[0009]    Implementations can include one or more of the following features.  The motion vectors can include a two-dimensional set of values, and generating the distribution of the motion vectors can include generating a two-dimensional histogram having bins.  The motion vector values are provided in appropriate bins of the two-dimensional histogram.  Also, before generating the distribution of the motion vectors, the motion vectors can be projected in a lower resolution.
[0010]    Identifying the cluster in the distribution of motion vectors can include accumulating bins within a first neighborhood in the two-dimensional histogram, accumulating bins within a second neighborhood in the two-dimensional histogram, selecting one of the neighborhoods as having a higher accumulation of bins, and providing the selected neighborhood as the identified cluster in the distribution of motion vectors.
[0011]    The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims. 
DETAILED DESCRIPTION
[0012]    Implementations of the present invention include a camera model used to provide a mathematical model of motion vectors for an image patch.  The camera model represents a camera movement in a sequence of frames.  For example, camera models can be used to provide for horizontal and/or vertical camera pans, zoom in or zoom out operations, and rotation operations.  The camera model can also represent combinations of one or more of the above camera movements.  The camera model provides a global description of motion vectors for a sequence of frames.  
[0013]    The camera model describes a global movement of the contents of the frame, as opposed to the local vectors at each image patch location that are computed independently and can therefore be used to aid in finding a more accurate, or true, motion vector.  Typically, a motion vector resulting from camera movements at every location in a frame can be predicted quite easily with a simple model.  For example, in the case of a camera lens panning across a distant landscape, all the motion vectors will be identical and equivalent to the velocity of the camera.  Another scenario is when a camera lens zooms into an object on a flat surface, such as a picture on a wall.  All the motion vectors then have a radial direction and increase from zero at the image center to a maximum value at the image periphery.
[0014]    Embodiments of the present invention provide methods and apparatus for defining and applying a camera model which provides a robust fit for predicting motion vectors associated with an independently moving object in a sequence of frames in which there may be other independently moving objects.  Disclosed herein are techniques for fitting a camera model to a sequence of image frames wherein data associated with independently moving objects other than a particular moving object or background to be tested is excluded to achieve a more accurate camera model.  By excluding independently moving objects other than the particular moving object to be tested, a more accurate camera model is calculated, providing for more accurate motion vector prediction.  
[0015]    Embodiments of the present invention provide for the determination of parameters for a camera model, and the generating of motion vectors using the determined camera model parameters.  A set of existing motion vectors stored in memory is provided, from which the camera model parameters are calculated.  Applying a mathematical model, described below, a best fit method (such as linear least squares) is performed on the existing motion vectors to estimate the camera model parameters.  The camera model parameters are then used to predict motion vectors for subsequent frames in a digital video sequence of frames.  In a particular embodiment, this subsequent prediction of motion vectors using the camera model incorporates a recursive and hierarchical process such as that described in co-pending U.S. patent application entitled, "Temporal Motion Vector Filtering," having Application No. 10/833,198 filed April 26, 2004 which is incorporated by reference in its entirety for all purposes.
[0016]    When calculating camera model parameters for a sequence of frames in which there are independently moving objects (some of which are moving in adverse directions to each other), embodiments of the present invention provide techniques for fitting the camera model to a dominant one of the independently moving objects and excluding the other independently moving objects.  In most situations, the dominant object is the background. A set of input motion vectors having a first, or original resolution, are projected to a lower resolution to conserve memory resources.  A histogram of all of the motion vector values is then generated to produce a distribution of the motion vectors.  Motion vector values in bins of the histogram are accumulated to identify a dominant cluster of the motion vectors.  Then a center of mass of this cluster is calculated while excluding other clusters of motion vectors in the two-dimensional distribution to achieve the desired robust fit.  This center of mass provides one or more translation (or pan parameters) of the camera model.  The camera model parameters are then used for later estimation of motion vectors using the camera model.  In this way, motion vectors can be determined efficiently and accurately, such that little or no discrepancy exists between an expected image motion due to eye tracking and a displayed image motion in a digital video.
[0017]    A mathematical representation of the camera model is as follows:
2005182830.tif 000016
[0018]    In the equation above, the camera model provides an estimate of a plurality of motion vectors, My and Mx, by applying camera model parameters Sy, Sx, r1, r2, ty, and tx to a sequence of (x, y) locations in an image.  Sy, Sx, r1, r2, ty, and tx are parameters of the camera model representing camera movements.  In the above model, ty, and tx represent a horizontal and vertical translation, respectively, during a during a camera pan.  An illustration of motion vectors associated with a camera pan is provided in Fig. 2A.  In the equation above, r1 and r2, are parameters representing camera rotation.  Fig. 2B shows an illustration of motion vectors associated with a camera rotation.  The Sy and Sx parameters are associated with a zoom out or zoom in operation which is illustrated in Fig. 2C.  
[0019]    In the described embodiment, the parameters Sx, Sy, r1, r2, ty, and tx are computed using a set of motion vectors determined using the recursive hierarchical process described in U.S. Patent Application No. 10/833,198 .   Accordingly, a motion vector is determined by applying a source correlation window to a first image frame and a target correlation window to a subsequent image frame, and placing the target correlation window such that a best match with the source correlation window is obtained, that is, the contents of the source correlation window and target correlation window are as similar as possible.  In addition, the recursive hierarchical method uses multiple resolution levels of the image frames.  A best motion vector is first determined for the lowest resolution level by projecting the previous best motion vector at the highest resolution level down to the lowest resolution level, and testing it and one or more updates.  This best motion vector is then propagated up to a higher resolution level, where some adjustments are made and a new best motion vector is determined.  This new best motion vector is propagated up to yet another higher resolution level, where more adjustments are made and another new best motion vector is determined.  This process is repeated until the highest, original, resolution level has been reached and a best motion vector has been identified for the original resolution level.
[0020]    FIG. 1 shows one implementation of the recursive hierarchical process (100) of U.S. Application No. 10/833,198 .  It is assumed that multiple resolution levels of the image frames have already been generated.  As can be seen in FIG. 1, the recursive hierarchical process (100) for determining a motion vector starts by projecting a motion vector from a previous image frame down to a lowest resolution level (step 102).  A set of update vectors is generated and tested to find a best motion vector at this lowest resolution level (step 104).  In one implementation this test is performed by comparing pixels in corresponding positions in a source correlation window centered on the origin of the motion vector and a target correlation window centered on the end point of each respective update vector.  The comparison can, for example, be performed by subtracting a luma value for each pixel in the source window from the corresponding pixel in the respective target windows.  In this case the best match would be defined by finding a minimum sum of absolute differences (SAD) for a source correlation window and a target correlation window pair, and the best motion vector would be the vector associated with this source correlation window and a target correlation window pair.  
[0021]    After the minimum SAD has been found, the best vector is selected (step 106).  The process (100) then examines whether there are any higher resolution levels (step 108).  If there are higher resolution levels, the process propagates the best vector up to the next higher resolution level (step 110) and repeats steps 104 through 108.  If there are no higher resolution levels, the process proceeds to step 112, where the best vector is selected as the motion vector and is used for motion compensation, which completes the process for the current frame.
[0022]    The best vector, as determined in step 112 of Fig. 1, can then be inserted into the mathematical model represented by equation (1) above as My and Mx.  Those skilled in the art should appreciate that the best vector determined for any of the lower resolutions in Fig. 1, such as step 104, may also be used.  In other embodiments, other vectors may be substituted for My and Mx in the camera model equation.  It should be noted that although a linear least squares fit procedure is used in the described embodiment, any suitable data fitting technique can be used.  Accordingly, a linear least squares fit procedure is then performed to solve for Sx, Sy, r1, r2, ty, and tx.  That is, referring to the mathematical model above, since a known set of My and Mx values are provided for known corresponding x and y locations, a matrix inversion operation can be performed to determine the unknown parameters Sx, Sy, r1, r2, ty, and tx.
[0023]    After the camera model parameters are determined, the camera model parameters are applied to generate camera model motion vectors My and Mx for positions y and x within an image patch or frame to provide vector candidates for one or more iterations of the recursive and hierarchical process described herein.  For instance, these camera model predicted motion vectors can be used along with the updated vectors as test candidates for a SAD computation.  Then, in step 106 of Fig. 1, the best vector is determined from all of the test candidates. 
[0024]    Fig. 3 shows a block diagram of an apparatus 300 for calculating camera model parameters and then using those camera model parameters to generate motion vectors in accordance with an embodiment of the invention.  Fig. 4 shows a flow chart of a method 400 describing the operation of the apparatus of Fig. 3.  In step 405, a test vector My' and Mx', such as the best vector determined in step 106 of Fig. 1, is retrieved from memory 305 by a camera model parameter calculator 310.  This camera model parameter calculator 310 is preferably implemented primarily in software, although various combinations of software and hardware can be used as will be understood by those skilled in the art.  Memory 305 is any suitable processor readable storage medium such as SDRAM.
[0025]    In step 410 of Fig. 4, the camera model parameter calculator 310 computes camera model parameters Sx, Sy, r1, r2, ty, and tx based on the retrieved motion vectors and known corresponding x,y locations, as described above.  That is, a matrix inversion operation is performed to determine the camera model parameters Sx, Sy, r1, r2, ty, and tx.  In step 415, camera model parameter calculator 310 then outputs these computed camera model parameters Sx, Sy, r1, r2, ty, and tx to memory 310 for storage in one or more registers.  In step 420, a camera model motion vector generator 315 retrieves the camera model parameters Sx, Sy, r1, r2, ty, and tx from the registers in memory 310.  Accordingly, when x,y locations for an image are provided to camera model motion vector generator 315 in step 425, the camera model motion vector generator 315 can generate motion vectors My and Mx in step 430, applying the camera model equation above.  These motion vectors My and Mx are output by camera model motion vector generator 315 and can be stored in step 435.  For the next iteration of the recursive hierarchical process, the stored motion vectors can be used as test candidates in addition to the recursive hierarchical predicted vectors.
[0026]    In Fig. 5, a two-dimensional representation 500 of motion vectors along X and Y directions is illustrated.  In Fig. 5, a group of motion vectors 505a-505e represent an independently moving object to which a camera model is desirably fitted.  On the other hand, motion vectors 510 are motion vectors associated with a further independently moving image or object that is desirably excluded from the camera model.  In this example, the camera model provides a pan scenario; thus, only the tx and ty values of the mathematical model above need be computed.  Here, because the majority of motion vectors 505a-505e are the same, the camera pan model is desirably fitted to provide a model of these motion vectors 505a-505e.  For the camera model to be effective, the motion vectors 510 are desirably excluded as outliers when calculating the tx and ty translation parameters for the camera pan model.  Techniques described below provide for the exclusion of motion vectors 510 from the camera model parameter calculations, so that a robust and accurate camera model fit is achieved.
[0027]    Fig. 6A shows a two-dimensional distribution 600 of My and Mx values for an exemplary set of motion vectors My and Mx.  All of the values of the motion vectors My and Mx are within the bounds of the two-dimensional representation.  That is, all of the Mx values range within - Mx max and + Mx max; similarly, all of the My values range within - My max and + My max.  In one example, the Mx values range between -32 and +32, and the My values range between -24 and +24.  Those skilled in the art should appreciate that these ranges of My and Mx values are only exemplary, and various other ranges may be used in accordance with embodiments of the present invention.  In Fig. 6, the majority of the motion vectors form a cluster 605, indicating that all of the motion vectors have substantially similar values representing a camera pan.  Thus, determining the center of mass of the cluster 605 provides the tx and ty parameters for the camera model.  The vectors outside of cluster 605 are preferably excluded as outliers during the computation of tx and ty.
[0028]    Fig. 6B shows a side view of a distribution of Mx values, such as the motion vector values of Fig. 6A.  The distribution of Mx values yields a first hill 615 and a second hill 620.  The hills 615 and 620 indicate the number of vectors having particular Mx values.  Thus, first hill 615 is formed because of a large concentration of vectors having the value Mx1.  The relatively smaller second hill 620 is formed by another concentration of vectors having the value Mx2.  The hill 615 having the larger count of vectors for a particular Mx value, referred to herein as the dominant hill, represents a neighborhood for locating the true tx and ty parameters for the camera model.  Methods and apparatus according to embodiments of the present invention provide for identifying the dominant hill 615, excluding smaller hills such as hill 620, then determining a center of mass of the dominant hill 615 as the camera model parameters tx and ty.
[0029]    Fig. 7 shows a top view of an example of a two-dimensional histogram with bins 705a-705c for accumulating discrete My and Mx values.  Because the My and Mx values are discrete, the histogram is represented as a grid, with each block or bin in the grid representing a particular My and Mx value.  In the example in which the Mx values range between -32 and +32, and the My values range between -24 and +24, a two-dimensional distribution of the motion vector values would have a grid size of 64 x 48 total distributions or bins in which the particular motion vector values can be located.  The aggregation of the bins provides a 64 x 48 two-dimensional histogram.  The bins 705 have bin counts indicating the number of motion vector My and Mx values in the respective bins.  For instance, bin 705b has a count of 7 motion vectors, and bin 705c has a count of 100 motion vectors.  Each bin count is incremented for every motion vector value deposited in that bin.  In this example, a neighborhood of bins including bin 705c represents the dominant hill of the histogram.  It is desirable to identify this dominant hill for determining an accurate camera pan vector estimate using techniques described below.
[0030]    Figs. 8 and 9 show a method 800 and apparatus 900, respectively, for estimating a camera pan vector, performed in accordance with one embodiment of the present invention.  The apparatus 900 can be implemented with various combinations of hardware and software, as will be understood by those skilled in the art.  The method of Fig. 8 is described with reference to Fig. 9.  In step 805, a camera model is provided.  This camera model is defined according to the method described with reference to Figs. 3 and 4, as explained above.  The camera model is used to generate a plurality of camera model motion vectors, for instance, a two-dimensional set of motion vectors My and Mx, as explained above, for an image patch in a plurality of frames of the digital video sequence.  The camera model includes a plurality of parameters, such as tx and ty, as described above, which are applied to y and x coordinates to generate the motion vectors, My and Mx.  The camera model motion vectors are provided in a first resolution, such as 1:1.  
[0031]    In step 810 of Fig. 8, the camera model motion vectors My and Mx are preferably projected in a lower resolution.  This step of projecting the motion vectors in the lower resolution conserves memory and reduces computational demands.  Various resolutions may be used.  In one example, where the original or first resolution is 1:1, this lower resolution is 1:2, 1:4, or 1:8.  Accordingly, the number of bins in the two-dimensional histogram of Fig. 9 is greatly reduced.  For instance, when the original Mx value range of -32 to +32 and value range of -24 to +24 is reduced to 1:2, the corresponding bin count is reduced from 64x48 to 32x24.  That is, scaling the motion vector values by a factor of 2 causes the bin count to be reduced by a factor of 4.  In this example, the bin counts for 4 neighboring bins are effectively combined into a single bin.  Various other reduced resolutions may be used, as will be understood by the skilled artisan. 
[0032]    In step 815 of Fig. 8, a motion vector generator 910, shown in Fig. 9, generates a distribution of the motion vectors.  When the motion vectors are two-dimensional, the particular values of the set of two-dimensional motion vectors are distributed in a two-dimensional histogram with bins, as explained above with reference to Fig. 7.  
[0033]    In step 820 of Fig. 8, a cluster identifier 920, shown in Fig. 9, finds the dominant hill in the two-dimensional histogram of Fig. 7.  That is, cluster identifier 920 identifies a cluster in the distribution of motion vector values as having the highest concentration of motion vectors in the distribution.  In one embodiment, this identification step includes accumulating bins within a plurality of neighborhoods in the two-dimensional histogram as shown in Fig. 7.  These neighborhoods are defined by a pxq window 710 or other window of predetermined size, e.g. 3 x 3, 4 x 4, 12 x 12, 100 x 100, moved over various positions in the histogram such that a certain number of bins are included within the window at each position.  All of the bin counts within the window at a certain position are added to provide a total bin count associated with that window or neighborhood.  Then, the neighborhood having the higher or highest accumulation of bins is selected as the identified cluster.  This identified cluster provides the dominant hill of the histogram, such as hill 615 in Fig. 6B.  
[0034]    In step 825 of Fig. 8, a determining module 930 shown in Fig. 9 determines a center of mass for the identified cluster from step 1020.  This center of mass calculation is preferably performed within another window of predetermined size.  In one embodiment, this window has a size mxn which is larger than the pxq window containing the neighborhoods used for the bin accumulations in step 820.  In step 830, the center of mass determined in step 825 is provided as one or more of the camera model parameters for subsequent motion vector calculation, referring to the mathematical representation of the camera model above.  For instance, in the camera pan example, the determined center of mass is provided as the translation parameters, tx and ty.  In embodiments in which the motion vectors were projected from an original resolution to a lower resolution in step 810, the determined center of mass is preferably projected back to the original resolution.  In some embodiments, the calculations for this projection are done using floating point to provide a more accurate projection.  The camera model parameters are then stored in step 835, and later retrieved by camera pan calculator 940 of Fig. 9 for the generation of camera pan model motion vectors My and Mx, using equation (1) above.  In one embodiment, these camera pan model motion vectors My and Mx are then used to determine test candidates for the recursive hierarchical process described in U.S. Application No. 10/833,198 .
[0035]    Using the camera model predicted vector as an additional candidate vector in the recursive hierarchical process minimizes the possibility that the recursive portion of the recursive hierarchical search converges into a false local minimum instead of the true minimum.  The camera predicted vector candidate can direct the process towards a true minimum.  In some embodiments, as described herein, motion vectors predicted or generated by the camera model are also used as test candidates for SAD computation.
[0036]    Embodiments of the invention, including the apparatus of Figs. 3 and 9, can be implemented in digital electronic circuitry, or in computer hardware, firmware, software, or in combinations of them. Apparatus embodiments of the invention can be implemented in a computer program product tangibly embodied in a machine-readable storage device for execution by a programmable processor; and method steps of the invention can be performed by a programmable processor executing a program of instructions to perform functions of the invention by operating on input data and generating output.  Embodiments of the invention can be implemented advantageously in one or more computer programs that are executable on a programmable system including at least one programmable processor coupled to receive data and instructions from, and to transmit data and instructions to, a data storage system, at least one input device, and at least one output device. Each computer program can be implemented in a high-level procedural or object-oriented programming language, or in assembly or machine language if desired; and in any case, the language can be a compiled or interpreted language. Suitable processors include, by way of example, both general and special purpose microprocessors. Generally, a processor will receive instructions and data from a read-only memory and/or a random access memory. Generally, a computer will include one or more mass storage devices for storing data files; such devices include magnetic disks, such as internal hard disks and removable disks; magneto-optical disks; and optical disks. Storage devices suitable for tangibly embodying computer program instructions and data include all forms of non-volatile memory, including by way of example semiconductor memory devices, such as EPROM, EEPROM, and flash memory devices; magnetic disks such as internal hard disks and removable disks; magneto-optical disks; and CD-ROM disks. Any of the foregoing can be supplemented by, or incorporated in, ASICs (application-specific integrated circuits).
[0037]    A number of implementations of the invention have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention.  Accordingly, other embodiments are within the scope of the following claims.
3. BRIEF DESCRIPTION OF THE DRAWINGS
[0038]    
FIG. 1 shows a flowchart of a recursive hierarchical process for determining a motion vector.
FIG. 2A shows an example of motion vectors associated with a camera pan.  
FIG. 2B shows an example of motion vectors associated with a camera rotation.
FIG. 2C shows an example of motion vectors associated with a camera zoom in operation.
FIG. 3 shows a block diagram of an apparatus for calculating camera model parameters and generating motion vectors using a camera model.
FIG. 4 shows a flowchart of a method for estimating a camera pan vector, in accordance with one embodiment of the present invention.
FIG. 5 shows an example of motion vectors associated with independently moving objects.
FIG. 6A shows a distribution of motion vectors along two dimensions.
Fig. 6B shows a side view of a distribution of motion vector values.
FIG. 7 shows a distribution of motion vector values in a two-dimensional histogram having bins.
FIG. 8 shows a flowchart of a method for motion vector estimation using a camera model for a digital video sequence of frames.
FIG. 9 shows an apparatus for estimating a camera pan vector, in accordance with one embodiment of the present invention.
Like reference symbols in the various drawings indicate like elements. 
1.   A method for estimating a camera pan vector comprising:
generating a distribution of motion vectors;
identifying a cluster in the distribution of motion vectors;
determining a center of mass of the identified cluster; and  
providing the camera pan vector based upon the determined center of mass.
2.  The method of claim 1, the camera pan vector including parameters of a camera model representing the motion vectors in an image patch.
3.  The method of claim 2, wherein providing the camera pan vector based upon the determined center of mass comprises:
providing the determined center of mass as one or more of the parameters of the camera model.
4.  The method of claim 1, further comprising:
storing the provided camera pan vector in a processor readable memory.
5.  The method of claim 1, the motion vectors including values, wherein generating the distribution of the motion vectors comprises:
generating a two-dimensional histogram having bins, and
providing the motion vector values in appropriate bins of the two-dimensional histogram.
6.  The method of claim 1 further comprising:
providing the motion vectors in a first resolution, and
before generating the distribution of the motion vectors,
projecting the motion vectors in a second resolution, the second resolution of lower resolution than the first resolution.
7.  The method of claim 1, wherein the camera pan vector is generated for an image patch, the image patch including a single pixel.
8.  The method of claim 1, wherein the camera pan vector is generated for an image patch, the image patch including a plurality of pixels.
9.  The method of claim 5, wherein identifying the cluster in the distribution of motion vectors comprises:
accumulating bins within a first neighborhood in the two-dimensional histogram,
accumulating bins within a second neighborhood in the two-dimensional histogram,
selecting one of the neighborhoods as having a higher accumulation of bins, and
providing the selected neighborhood as the identified cluster in the distribution of motion vectors.
10.  The method of claim 9, wherein each neighborhood is contained within a window of a predetermined size.
11.  The method of claim 9, wherein identifying the cluster in the distribution of motion vectors further comprises:
before selecting the one neighborhood,
accumulating bins within further neighborhoods in the two-dimensional histogram.
12.  The method of claim 1, wherein the center of mass of the identified cluster is determined within a window of predetermined size.
13.  The method of claim 10, wherein the center of mass of the identified cluster is determined within a window having a larger size than the window or windows containing the neighborhoods.
14.   An apparatus for estimating a camera pan vector comprising:
a motion vector generator configured to generate a distribution of motion vectors;
a cluster identifier configured to identify a cluster in the distribution of motion vectors;
a determining module configured to determine a center of mass of the identified cluster; and
a camera pan calculator configured to provide the camera pan vector based upon the determined center of mass.
15.  The apparatus of claim 14, the camera pan vector including parameters of a camera model representing the motion vectors in an image patch.
16.  The apparatus of claim 15, the camera pan calculator configured to:
provide the determined center of mass as one or more of the parameters of the camera model.
17.  The apparatus of claim 14, the motion vectors including values, the motion vector generator configured to:
generate a two-dimensional histogram having bins, and
provide the motion vector values in appropriate bins of the two-dimensional histogram.
18.  The apparatus of claim 17, the cluster identifier configured to:
accumulate bins within a first neighborhood in the two-dimensional histogram,
accumulate bins within a second neighborhood in the two-dimensional histogram,
select one of the neighborhoods as having a higher accumulation of bins, and
provide the selected neighborhood as the identified cluster in the distribution of motion vectors.
19.  A computer program product, stored on a processor readable medium, comprising instructions operable to cause a computer to perform a method for estimating a camera pan vector, the method comprising:
generating a distribution of motion vectors;
identifying a cluster in the distribution of motion vectors;
determining a center of mass of the identified cluster; and
providing the camera pan vector based upon the determined center of mass.
20.  The computer program product of claim 19, the motion vectors including values, wherein generating the distribution of the motion vectors comprises:
generating a two-dimensional histogram having bins, and
providing the motion vector values in appropriate bins of the two-dimensional histogram.
21.  The computer program product of claim 20, the step of identifying the cluster in the distribution of motion vectors including:
accumulating bins within a first neighborhood in the two-dimensional histogram,
accumulating bins within a second neighborhood in the two-dimensional histogram,
selecting one of the neighborhoods as having a higher accumulation of bins, and
providing the selected neighborhood as the identified cluster in the distribution of motion vectors.
1. ABSTRACT
Methods and apparatus, including computer program products, implementing and using techniques for camera pan vector estimation, are disclosed.  A camera model is provided for representing motion vectors based on a plurality of parameters.  A distribution of the motion vectors is generated.  A cluster in the distribution of motion vectors is identified.  A center of mass of the identified cluster is determined.  The camera pan vector is provided based upon the determined center of mass.  
2. REPRESENTATIVE DRAWING
Fig. 8
2005182830.tif 000017
2005182830.tif 000018
2005182830.tif 000019
2005182830.tif 000020
2005182830.tif 000021
2005182830.tif 000022
2005182830.tif 000023
2005182830.tif 000024
2005182830.tif 000025
2005182830.tif 000026
2005182830.tif 000027
2005182830.tif 000028