(57)【要約】本発明は、画像系列から取得される少なくとも１つのピクチャからローカルベクトルを帰納的に推定する方法に関する。前記推定の方法の計算の複雑性を、精度を劣化させることなく軽減するように、当該方法が、帰納法の少なくとも部分的な使用の下で、候補ベクトルの第１集合を生成するステップと、候補ベクトルのより小さい第２集合を形成するように、第１基準に従って、前記候補ベクトルの第１集合から候補ベクトルを選択するステップと、ピクセル群に対する前記候補ベクトルの第２集合の候補ベクトルを、第２基準に基づいて評価するステップと、前記第２基準に従って、前記候補ベクトルの第２集合から最良ベクトルを決定するステップと、決定された前記最良ベクトルを、これに対して前記候補ベクトルの第２集合の前記候補ベクトルが評価されている前記ピクセル群に関連するピクセル群に、割り当てるステップと、を有することが、提案される。本発明は、更に、画像系列から取得される少なくとも１つのピクチャからローカルベクトルを帰納的に推定するための装置と、画像系列から取得される少なくとも１つのピクチャからローカルベクトルを帰納的に推定するためのソフトウェアコード部を含むコンピュータプログラムとに関する。
2006513478.tif 000002
【特許請求の範囲】
【請求項１】
画像系列から取得される少なくとも１つのピクチャから、ローカルベクトルを帰納的に推定する方法であって、
―  帰納法の少なくとも部分的な使用の下で、候補ベクトルの第１集合を生成するステップと、
―  候補ベクトルのより小さい第２集合を形成するように、第１基準に従って、前記候補ベクトルの第１集合から候補ベクトルを選択するステップと、
―  ピクセル群に対する前記候補ベクトルの第２集合の前記候補ベクトルを、第２基準に基づいて評価するステップと、
―  前記第２基準に従って、前記候補ベクトルの第２集合から最良ベクトルを決定するステップと、
―  決定された前記最良ベクトルを、これに対して前記候補ベクトルの第２集合の前記候補ベクトルが評価されている前記ピクセル群に関連するピクセル群に、割り当てるステップと、
を有する方法。
【請求項２】
ランダムベクトルであるか若しくは更新ベクトルの限定され固定されている集合に属しているかのいずれかである更新ベクトル、及び／又ゼロベクトル、及び／又は既に推定されて決定されているローカルベクトルに基づいて、前記候補ベクトルの第１集合内の前記候補ベクトルが、空間的に及び／又は時間的に予測されることを特徴とする、請求項１に記載の方法。
【請求項３】
前記ローカルベクトルは、画像系列のピクチャ内のピクセルの群の動きを記述する動きベクトルであることを特徴とする、請求項１又は２に記載の方法。
【請求項４】
前記動きベクトルの少なくとも１つが、パラメータの二次元全体の動きモデルに従って予測されることを特徴とする、請求項３による方法。
【請求項５】
前記ローカルベクトルが、画像系列のピクチャ内のピクセル群の前記動きモデルを記述するパラメータの集合を表していることを特徴とする、請求項１又は２に記載の方法。
【請求項６】
前記ローカルベクトルが、ピクセル群の空間フィーチャを、テクスチャ、ダイナミックレンジ、色又は平均値において表していることを特徴とする、請求項１又は２に記載の方法。
【請求項７】
前記第２基準は、絶対差分総和（ＳＡＤ）基準又は平均二乗誤差基準のような整合エラー基準、であることを特徴とする、請求項１ないし６のいずれか一項に記載の方法。
【請求項８】
候補ベクトルのより小さい第２集合を形成するための前記候補ベクトルの第１集合からの候補ベクトルの選択が、前記候補ベクトルの第１集合内の前記候補ベクトルの対応するベクトル成分の順位付けに基づいていることを特徴とする、請求項１ないし７のいずれか一項に記載の方法。
【請求項９】
候補ベクトルのより小さい第２集合を形成するための前記候補ベクトルの第１集合からの候補ベクトルの選択が、前記候補ベクトルの第１集合内の前記候補ベクトルの順位付けに基づいていることを特徴とする、請求項１ないし７のいずれか一項に記載の方法。
【請求項１０】
前記候補ベクトルの第２集合が、前記第１基準による前記候補ベクトルの第１集合の少なくとも１つの極端候補ベクトル及び／又は１つの最小の極端候補ベクトルを含むことを特徴とする、請求項１ないし９のいずれか一項に記載の方法。
【請求項１１】
前記極端候補ベクトルは、前記候補ベクトルの第１集合の複数の候補ベクトルの平均ベクトルまでの最長距離を有する、若しくは前記候補ベクトルの第１集合内の空間的予測ベクトルまでの最大距離を有する、又は最長及び最短ベクトル、又は前記候補ベクトルの第１集合の候補ベクトルの残りまで最長距離を有する、２つのベクトルであることを特徴とする、請求項１０に記載の方法。
【請求項１２】
前記最小の極端候補ベクトルが、前記候補ベクトルの第１集合の複数の候補ベクトルの平均ベクトルまでの最小距離を有する、若しくは前記候補ベクトルの第１集合内の空間的予測ベクトルまでの最小距離を有するベクトル、又はベクトルメディアンであることを特徴とする、請求項１０に記載の方法。
【請求項１３】
画像系列から取得される少なくとも１つのピクチャから、ローカルベクトルを帰納的に推定する装置であって、
―  帰納法の少なくとも部分的な使用の下で、候補ベクトルの第１集合を生成する手段と、
―  候補ベクトルのより小さい第２集合を形成するように、第１基準に従って、前記候補ベクトルの第１集合から候補ベクトルを選択する手段と、
―  ピクセル群に対する前記候補ベクトルの第２集合の前記候補ベクトルを、第２基準に基づいて評価する手段と、
―  前記第２基準に従って、前記候補ベクトルの第２集合から最良ベクトルを決定する手段と、
―  決定された前記最良ベクトルを、これに対して前記候補ベクトルの第２集合の前記候補ベクトルが評価されている前記ピクセル群に関連するピクセル群に、割り当てる手段と、
を有する装置。
【請求項１４】
コンピュータプログラムがコンピュータ上で走らされた場合に、請求項１に記載のステップを実施するソフトウェアコード部を含む、デジタルコンピュータの内部メモリに直接的にロード可能な、該コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像系列から取得される少なくとも１つのピクチャからローカルベクトルを帰納的に推定する方法であって、帰納法の少なくとも部分的な使用の下で、候補ベクトルの第１集合を生成するステップと、候補ベクトルのより小さい第２集合を形成するように、第１基準に従って、前記候補ベクトルの第１集合から候補ベクトルを選択するステップと、ピクセル群に対する前記候補ベクトルの第２集合の候補ベクトルを、第２基準に基づいて評価するステップと、前記第２基準に従って、前記候補ベクトルの第２集合から最良ベクトルを決定するステップと、決定された前記最良ベクトルを、これに対して前記候補ベクトルの第２集合の前記候補ベクトルが評価されている前記ピクセル群に関連するピクセル群に、割り当てるステップと、を有する方法に関する。本発明は、更に、画像系列から取得される少なくとも１つのピクチャからローカルベクトルを帰納的に推定する装置と、画像系列から取得される少なくとも１つのピクチャからローカルベクトルを帰納的に推定するソフトウェアコード部を含むコンピュータプログラムとに関する。
【背景技術】
【０００２】
画像データからのローカルベクトルの推定は、符号化／圧縮、ノイズ低減、オブジェクト追跡、及びスキャンレート変換のような、画像処理アプリケーションの広範囲で必要とされている。ＭＰＥＧ２又はＨ．２６１のような、ビデオ符号化フレーム構造において、ローカルベクトルは、一方の画像から他方の画像への動き（又はオブジェクトの変位）を決定する動きベクトルによって表される。動きベクトルの推定は、例えば、動き補償された予測符号化に使用されることができる。画像内の１つのピクチャは、通常、その前身のコピーをずらしたものに非常に類似しているので、推定された動きベクトルのデータを、実際の画像と、ピクセル又はＤＣＴ領域のいずれかにおけるこの予測との間の差分に関する情報と共にエンコードすることで、符号化された信号の時間的冗長性を、大幅に減少することができる。
【０００３】
ローカルベクトルの推定に関する他の例は、画像を、類似する空間特徴を有する領域にセグメント化する方法（オブジェクトセグメント化）であって、前記ローカルベクトルが、前記空間特徴に対する量的な尺度を表す方法と、画像セグメント（オブジェクト）に対する動きモデルを推定する方法であって、前記ローカルベクトルの成分が、前記動きモデルのパラメータを含んでいる方法とを含む。
【０００４】
画像データからローカルベクトルを推定する最新の技術は、通常、画像が、固定又は可変の大きさのブロックに分解される、ある種のブロック整合アルゴリズム（ＢＭＡ）を利用している。よく知られているように、画像は、ブロックの代わりに主要オブジェクトに分解されることができ（オブジェクトセグメント化）、この結果、後続の記述は、ブロックの代わりにオブジェクトに対して、同様に等しく保持される。現画像の各ブロックに対して、類似性尺度が、前記現ブロックに最も類似する先行ブロックを識別するのに利用され、先行画像における類似するブロックが、検索される。前記先行画像の、最大の類似性が決定されているブロックに関連する前記ローカルベクトルが、前記現ブロックのピクセルに関連するローカルベクトルを表す。前記類似性尺度を計算する際に、比較されるべき２つのブロックのピクセルの全てが、評価される必要があるわけではないことに留意されたい。例えば、前記ブロックは、空間的にサブサンプリングされることができ、これにより、両ブロックの各ｋ番目のピクセルのみが、前記類似性尺度の評価に、考慮される。
【０００５】
前記現ブロックの、先行画像内の全ブロックとの類似性を調べようとする際に生じる、計算の労力を軽減するように、ローカルベクトルが、一般的に予測によって、即ち現ブロックの近隣領域内のブロックに関連する、限定された数の、いわゆる候補ベクトルに対する前記類似性尺度のみを評価することによって、推定される。
【０００６】
米国特許第５ ０７２ ２９３号明細書には、三次元（３Ｄ）の近隣からの予測が、動きベクトル推定用の候補ベクトルとして使用されるような、ＢＭＡが記載されている。候補動きベクトルの集合は、動きベクトルの空間的（２Ｄ）及び時間的（１Ｄ）予測の両方を有し、これらのうちの最良なものが、帰納的に、各ブロックに対して決定される。この技術は、前記現画像ｎにおけるブロックに対する前記候補動きベクトルの集合内の少なくとも１つの候補動きベクトルが、画像ｎ（空間的予測）における又は先行画像ｎ−ｌ（時間的予測）における、他のブロックの既に決定されている動きベクトルに依存することにおいて、帰納的である。この帰納的な推定技術は、オブジェクトがブロックよりも大きいので、前記動きベクトルが、近隣ブロックからの前記空間的予測の少なくとも１つにおいて発見されることができることを、暗に、仮定している。更に、オブジェクトの慣性が仮定されており、因果関係により空間的予測がもう利用可能でない場合に特に有用な、時間的予測を使用する推定技術も可能にしている。従って、両方の仮定に基づいて、予め発見された動きベクトルが、帰納的に最適化される。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
帰納的ＢＭＡにおいて、前記類似性尺度が各帰納ステップにおいて評価されなければならない、ブロックに対する候補ベクトルの集合の合成は、帰納的動き推定技術の正確さ及び集束速度だけでなく、計算の複雑性も決定する。正確な動きベクトル推定を保証するように、候補動きベクトルの大きい集合が選択されなくてはならず、これにより、計算の複雑性が増加される。
【０００８】
従って、本発明の目的は、低減された複雑性及び速い収束によるローカルベクトルの正確な推定のための帰納的方法を提供することにある。
【課題を解決するための手段】
【０００９】
本発明の目的を解決するためには、画像系列から取得される少なくとも１つのピクチャからローカルベクトルを帰納的に推定する方法が、帰納法の少なくとも部分的な使用の下で、候補ベクトルの第１集合を生成するステップと、候補ベクトルのより小さい第２集合を形成するように、第１基準に従って、前記候補ベクトルの第１集合から候補ベクトルを選択するステップと、ピクセル群に対する前記候補ベクトルの第２集合の候補ベクトルを、第２基準に基づいて評価するステップと、前記第２基準に従って、前記候補ベクトルの第２集合から最良ベクトルを決定するステップと、決定された前記最良ベクトルを、これに対して前記候補ベクトルの第２集合の前記候補ベクトルが評価されている前記ピクセル群に関連するピクセル群に、割り当てるステップと、を有することが提案される。
【００１０】
前記候補ベクトルの第１集合の大きさを、前記第１基準に従って減少することにより、前記第２基準に従う前記類似性尺度は、より少ない候補ベクトルに対して評価されるはずであるので、当分野の最新の推定器であって、前記類似性尺度が、前記候補ベクトルの第１集合の全ての候補ベクトルに対して評価されなければならない推定器と比較して、計算の複雑性が大幅に減少されることができる。前記第１基準は、前記第２基準と比較して低い計算の複雑性を有し、前記推定器の精度及び収束の両方を制御する。提案されている当該方法の大きな利点は、候補ベクトルのより大きい第１集合が使用されることができると同時に、事前選択の方法が、前記類似性尺度の実際の評価に関して、集合から最も有望なものを選択することにある。この結果は、減少された候補ベクトルの第１集合による、同一の当分野の最新のローカルベクトル推定器に対する必要性よりも、ほとんど計算を必要としないが、前記類似性尺度が評価されているベクトルのうちの最も有望な候補ベクトルを有する可能性は、著しく増加されている。
【００１１】
当該方法の更なる利点は、専用のハードウェアの実施を考慮する際に、明らかになる。前記のような実施は、平均で低い演算数からの利益をあまり得ることができない。これは、最悪の場合の状況に対して設計されなければならない。今、候補ベクトルの限定された第１集合によれば、実際に異なる候補ベクトルの数が前記ハードウェアの容量よりも少ないという可能性が高い。この発明において提案されている事前選択のモジュールが後続している、より大きい前記第１集合によれば、この可能性は、かなり減少されることができる。これにより、前記ハードウェアの容量をより最適に使用することができる。
【００１２】
オプションで、候補動きベクトルの前記第２集合は、動きベクトルの前記第１集合に含まれていない候補動きベクトルによって、拡張される。例えば、ヌルベクトル（即ち、無運動）が付加される、又は動きベクトルの前記第１集合のうちの選択された動きベクトルのメディアン（median）に基づく候補ベクトルが付加される。
【００１３】
前記候補ベクトルの第１集合の前記候補ベクトルは、好ましくは、ランダムベクトルであるか若しくは更新ベクトルの限定され固定されている集合に属しているかのいずれかである更新ベクトル、及び／又は及び／又はゼロベクトル、及び／又は既に推定されて決定されているローカルベクトルに基づいて、空間的に及び／又は時間的に予測される。画像系列のピクチャにおけるオブジェクトがブロックよりも大きく、かつ、慣性を有すると仮定すると、現ブロックのローカルベクトルは、現ブロックの周りの現ピクチャの他の近隣のブロックにおける既に決定されているローカルベクトル（空間的予測）に、又は先行画像における近隣ブロックの既に決定されているローカルベクトル（時間的予測）に、かなり類似しそうである。候補ベクトルとしてのゼロベクトルは、動きを有さないピクチャ部分に対して、特に有用であるのに対し、空間的に及び／又は時間的に予測されるローカルベクトルへの更新ベクトルの付加は、初期設定の段階において、前記予測に基づき得る全てのローカルベクトルが、ゼロであるという問題を解決する。
【００１４】
本発明によれば、前記ローカルベクトルとは、好ましくは、画像系列のピクチャ内のピクセル群の動きを記述する動きベクトルを表している。
【００１５】
前記動きベクトルの少なくとも１つは、パラメータの二次元の全体の動きモデルに従って予測されることもできる。例えば、２次元１次方程式として、動きベクトルを表現すると、パン、傾斜、移動（traveling）及びズームのようなカメラの動きを、正確にモデル化することができる。この種類の動きは、規則的な特徴を有し、オブジェクトの動きと比較して、滑らかな動きベクトルを生じる。ズームが、空間位置と共に線形的に変化する動きベクトルを生成するのに対し、パン、傾斜及び移動は、ピクチャ全体に対して一様な動きベクトルを生成する。前記全体の動きが生じる場合、動きベクトル自体の代わりに、パラメータの二次元の全体の動きモデルのパラメータを推定するのが、より効率的であり得る。
【００１６】
前記ローカルベクトルは、画像系列のピクチャ内のピクセル群の動きモデルを記述するパラメータの集合を表すこともできる。
【００１７】
他の代替的なものとして、前記ローカルベクトルは、ピクセル群の空間フィーチャ、特に、テクスチャ、ダイナミックレンジ、色又は平均値を表すことができる。
【００１８】
本発明によれば、前記第２基準は、絶対差分総和（ＳＡＤ）の基準又は平均二乗誤差（ＭＳＥ）の基準のような整合エラー基準として実施されることができ、前記予測された画像と現画像とのピクセル又はピクセル群の間の、ＳＡＤ又はＭＳＥが、計算される。対照的に、前記ローカルベクトルの成分が画像セグメントのテクスチャ、ダイナミックレンジ、色又は平均輝度値のような空間フィーチャを表す、画像セグメントのコンテキストにおいては、前記ＳＡＤ及びＭＳＥの基準は、ローカルベクトルの成分、及びローカル画像コンテンツから測定される対応する空間フィーチャに、直接的に適用される。
【００１９】
候補ベクトルのより小さい第２集合を形成するための、前記候補ベクトルの第１集合からの候補ベクトルの選択は、前記候補ベクトルの第１集合の前記候補ベクトルの対応するベクトル成分の順位付けに、適切に基づく。
【００２０】
候補ベクトルのより小さい第２集合を形成するための、前記候補ベクトルの第１集合からの候補ベクトルの選択は、前記候補ベクトルの第１集合の前記候補ベクトルの順位付けに基づくこともできる。
【００２１】
本発明の好適実施例において、前記候補ベクトルの第２集合は、前記第１基準に従って、前記候補ベクトルの第１集合のうちの、少なくとも１つの極端候補ベクトル及び／又は１つの最小の極端候補ベクトルを含む。
【００２２】
前記最小の極端候補ベクトルは、より極端なベクトルは、収束されていない状況において特に有用であるのに対して、しばしば、収束された状況において良好なものであるので、これらのみを、後続の、計算的により高価である前記第２基準による評価用に選択することは、意味をなす。静止ピクチャ部の内挿は、動きベクトルの多くのアプリケーションにおいて重要であるので、極端ベクトルとしてのゼロベクトル（無運動を表す）の付加も、意味をなす。
【００２３】
前記極端候補ベクトルは、前記候補ベクトルの第１集合のうちの複数の候補ベクトルの平均ベクトルまで最大距離を有する、前記候補ベクトルの第１集合における空間的予測ベクトルまで最大距離を有する、又は前記候補ベクトルの第１集合の残りまで最大距離を有する、２つのベクトルであることが好ましい。
【００２４】
前記最小の極端候補ベクトルは、好ましくは、前記候補ベクトルの第１集合のうちの複数の候補ベクトルの前記平均ベクトルまで最小距離を有する、若しくは前記候補ベクトルの第１集合における空間的予測ベクトルまで最小距離を有するベクトル、又はベクトルメディアンである。
【００２５】
本発明の他の好適実施例は、画像系列から取得される少なくとも１つのピクチャからローカルベクトルを帰納的に推定する装置であって、帰納法の少なくとも部分的な使用の下で、候補ベクトルの第１集合を生成する手段と、候補ベクトルのより小さい第２集合を形成するように、第１基準に従って、前記候補ベクトルの第１集合から候補ベクトルを選択する手段と、ピクセル群に対する前記候補ベクトルの第２集合の候補ベクトルを、第２基準に基づいて評価する手段と、前記第２基準に従って、前記候補ベクトルの第２集合から最良ベクトルを決定する手段と、決定された前記最良ベクトルを、これに対して前記候補ベクトルの第２集合の前記候補ベクトルが評価されている前記ピクセル群に関連するピクセル群に、割り当てる手段とから構成されている装置である。
【００２６】
本発明の最後の好適実施例は、コンピュータプログラムがコンピュータ上で走らされた場合に、デジタルコンピュータの内蔵メモリに直接的にロード可能である該コンピュータプログラムであって、帰納法の少なくとも部分的な使用の下で、候補ベクトルの第１集合を生成するステップと、候補ベクトルのより小さい第２集合を形成するように、第１基準に従って、前記候補ベクトルの第１集合から候補ベクトルを選択するステップと、ピクセル群に対する前記候補ベクトルの第２集合の候補ベクトルを、第２基準に基づいて評価するステップと、前記第２基準に従って、前記候補ベクトルの第２集合から最良ベクトルを決定するステップと、決定された前記最良ベクトルを、これに対して前記候補ベクトルの第２集合の前記候補ベクトルが評価されている前記ピクセル群に関連するピクセル群に、割り当てるステップと、を実行するソフトウェアコード部を含むコンピュータプログラムである。
【発明を実施するための最良の形態】
【００２７】
本発明のこれら及び他の見地は、以下に記載される実施例を参照して、明らかになり、説明されるであろう。
【００２８】
図１は、本発明の第１実施例による動きベクトルの推定のための帰納的ＢＭＡを示している。
2006513478.tif 000003
によって、画像系列の現画像
2006513478.tif 000004
と、画像系列の先行画像
2006513478.tif 000005
との間の動きベクトル場を表すとする。ここで、
【数１】
2006513478.tif 000006
は、ピクセルグリッドベクトルである。更に、
2006513478.tif 000007
によって、現画像
2006513478.tif 000008
の、その中心がブロックグリッドベクトル
【数２】
2006513478.tif 000009
によって識別されているピクセルのＸ×Ｙブロック
2006513478.tif 000010
に割り当てられた動きベクトルを表すとする。
【００２９】
図１に示されているように、予測メモリインスタンス１は、候補ベクトルの集合
【数３】
2006513478.tif 000011
を出力する。ここで、前記候補ベクトル
【数４】
2006513478.tif 000012
は、定数、即ち、事前規定された整数Ｎ及びＭによって、離散的な候補ベクトルの集合
【数５】
2006513478.tif 000013
に限定されている。
【００３０】
候補ベクトルの集合
2006513478.tif 000014
の合成と、この好適実施例の記述の結果、提示される更新の手順とに関して、様々な異なる選択が存在することに留意されたい。この特有の実施例は、ピクチャ内のブロックが左上から右下までスキャンされると仮定し、時間及び／又は空間整合性を仮定しており、従って、更に多くの一般的なローカルベクトルの推定の原理のための例であるとだけ、考えられるべきである。
【００３１】
候補ベクトルの提示された前記集合
2006513478.tif 000015
の４つの空間候補ベクトルのうちのどれか、即ち、添え字ｋのみに依存する、又は全ての添え字ｉ、ｊ、ｋから独立であるベクトルが、更新インスタンス２に供給され、更新ベクトル
2006513478.tif 000016
が付加される。更新ベクトルを、
2006513478.tif 000017
に含まれている前記空間候補ベクトルの１つに付加することで、当該帰納法の初期化段階において、全てのベクトルが、
2006513478.tif 000018
ベクトルに等しいという問題が解決される。更新ベクトルは、ノイズベクトルとして発生されることができるか、又は、より簡単には、整数の更新値によるピクセル解像度が望まれている場合の
【数６】
2006513478.tif 000019
、若しくは分数の更新値による４倍のピクセル解像度のための
【数７】
2006513478.tif 000020
のような、ルックアップテーブル内に記憶されている、限定され固定されている更新の集合から取得されることができるかのいずれかである。
【００３２】
このコンテキストにおいて、
【数８】
2006513478.tif 000021
及び
【数９】
2006513478.tif 000022
は、２次元正規直交基底ベクトルを表している。
【００３３】
図１に示されているように、ｍｏｄ−ｐカウンタ（modulo-p-counter）４とルックアップテーブル５とから成る更新発生器インスタンス３は、前記更新値の集合から、ｐで巡回する必要とされる更新ベクトル
2006513478.tif 000023
を出力する。前記ｍｏｄ−ｐカウンタは、現ブロックカウントＮｂｌによってトリガされる。更に、整数ｐは、ピクチャ内のブロックの数の因数として選択されることができないので、更新ベクトルと画像内の空間位置との結合は、防止される。
【００３４】
予測メモリインスタンス１からの出力としての時間候補ベクトル、及び前記空間候補ベクトル（これらのどちらもが、更新インスタンス２内で更新されている）は、事前選択インスタンス６に入力される。前記事前選択インスタンスは、
例えば、集合
2006513478.tif 000024
内の全ての候補ベクトルの平均ベクトルまでの、全ての候補ベクトルの距離を判定することにより、集合
2006513478.tif 000025
内に含まれている候補ベクトル
2006513478.tif 000026
の順位付けを実施する。代替的なものとして、前記候補ベクトルは、長さ（大きさ）で記憶される。前記事前選択インスタンス６は、次いで、前記順位付けに従って、例えば、前記平均ベクトルまでの最大距離を有する２つのベクトル、又は最大及び最小ベクトルのような、２つの極端候補ベクトル（extreme candidate vector）を決定する。事前選択インスタンス６は、前記平均ベクトルまでの最小距離を有するベクトルのような、候補ベクトル
2006513478.tif 000027
の最小の極端なもの（the least extreme of candidate vector）も決定する。代替的には、メディアンベクトルが、最小の極端ベクトルとして決定されることができる。事前選択インスタンス６によって決定された、最大の極端ベクトル及び最小の極端ベクトルは、集合
2006513478.tif 000028
を構成し、これは、最良ベクトル選択インスタンス７に転送される。従って、この模範的な構成において、候補ベクトルの集合
2006513478.tif 000029
は、
2006513478.tif 000030
内に含まれている３つの最大／最小の極端候補ベクトルの集合に減少される。
【００３５】
図１に示されている最良ベクトル選択インスタンス７は、現画像
2006513478.tif 000031
内のブロックグリッドベクトル
2006513478.tif 000032
に中心を合わせられた当該ブロック
2006513478.tif 000033
と、集合
2006513478.tif 000034
内の各候補ベクトルに割り当てられている先行画像
2006513478.tif 000035
における前記ブロックとの間の類似性を、類似性尺度（例えば、絶対差分総和、即ちＳＡＤ）：
【数１０】
2006513478.tif 000036
を計算することによって、判定する。ここで、
2006513478.tif 000037
は、前記更新ベクトルの長さであって、整合エラーは、幅Ｘ及び高さＹを有するブロックグリッドの、位置
【数１１】
2006513478.tif 000038
における、
【数１２】
2006513478.tif 000039
で規定されているブロック
2006513478.tif 000040
に渡って総和される。代替的には、平均二乗誤差（ＭＳＥ）のような、異なる類似性尺度が、第２基準として、同様に適用されることができる。ブロック
2006513478.tif 000041
内のピクセルグリッド上の全てのピクセル
【数１３】
2006513478.tif 000042
に対する前記類似性尺度の評価の代わりに、ｘ及びｙ方向の両方における空間サブサンプリングが、前記類似性尺度を評価する前に、勿論、精度が多少低下するが、計算の数を減少させるように実施されることができる。
【００３６】
適用された前記第２基準及びサンプリング技術に関わらず、最良ベクトル選択インスタンス７は、更に、最大の類似性尺度：
【数１４】
2006513478.tif 000043
に至る前記候補動きベクトルを選択し、（たとえ、空間サブサンプリングが、前記類似性尺度の評価における計算の労力を減少させるように実施されていても）この最良の候補動きベクトルを、前記ブロック
2006513478.tif 000044
内のピクセル上の、位置
【数１５】
2006513478.tif 000045
における全てのピクセルに割り当てる。
【００３７】
前記最良の動きベクトル
2006513478.tif 000046
は、次いで、ブロック
2006513478.tif 000047
に対する動き推定の結果として出力されるだけでなく、後続の帰納的ステップにおける使用のために、予測メモリインスタンス１内に記憶される。
【００３８】
図２は、本発明による第２の好適実施例であって、動きベクトルがローカルベクトルとして推定され、当該帰納的推定が、全体の動きモデル（global motion model）に従って予測される候補動きベクトルを取り入れることによって強調されている、実施例を示している。
【００３９】
基本的に、図２の構成は、図１の構成を発展させたものであり、図２の構成は、予測メモリインスタンス１と、更新インスタンス２と、ｍｏｄ−ｐカウンタ４及びルックアップテーブル５から成る更新発生器インスタンス３と、事前選択インスタンス６と、最良ベクトル選択インスタンス７とを有する。
【００４０】
図１に示されている本発明の第１の好適実施例にあるように、候補動きベクトルの第１集合
2006513478.tif 000048
は、予測メモリインスタンス１によって空間的に及び時間的に予測され、事前選択インスタンス６に入力される。どの空間的な候補も、更新発生器インスタンス３によって発生される巡回更新ベクトル
2006513478.tif 000049
によって、更新インスタンス２内で、予め更新される。事前選択インスタンス６によって決定された最大の／最小の極端候補ベクトル
2006513478.tif 000050
は、次いで、最良ベクトル選択インスタンス７における前記類似性尺度による評価に従い、ブロック
2006513478.tif 000051
に対する最良動きベクトル
2006513478.tif 000052
が決定され、次の帰納的ステップのために、予測メモリ１内に記憶される。
【００４１】
しかしながら、図２に示されている前記第２の好適実施例は、カメラのパンをｐ１（ｎ）、傾斜をｐ２（ｎ）、ズームをｐ３（ｎ）で表した、
【数１６】
2006513478.tif 000053
による、３つのパラメータｐ１（ｎ）、ｐ２（ｎ）及びｐ３（ｎ）による２次元の線形１次方程式によって表されることができる候補動きベクトルを、前記候補ベクトルの第１集合が付加的に含んでいる点で、図１に示されている第１の好適実施例とは異なる。従って、この全体の動きベクトルのモデルは、動きが、非常に滑らかな速度、即ち動きベクトルを生じる非常に規則的な特徴を持っていると仮定している。カメラによるズームは、空間位置と共に線形的に変化する動きベクトルを生成する。他方で、カメラによるパン、傾斜又は移動は、スクリーン全体に対して一様な動きベクトルを生成する。前記モデルを、付加的に、６つのパラメータのモデルに拡張すると、回転によるベクトル場の記述が可能になる。この種類の動きは、カメラの動きによるものではなさそうであるが、他の状況において起こり得る。
【００４２】
図２によれば、動きモデルのパラメータｐ１（ｎ）、ｐ２（ｎ）及びｐ３（ｎ）は、例えば、予測メモリ１からのサンプルベクトルに基づき、マイクロプロセッサ８によって決定される。推定される動きベクトル場から、全体の動きモデルの３つのパラメータを抽出するための多くのオブションがある。前記動きモデルが、帰納的ＢＭＡ内に組み込まれている好適実施例において、既に利用可能な動きベクトル、即ち、前記時間的予測メモリ内で利用可能なベクトルから、開始することは意味をなす。演算数を低く維持するように、このメモリにおいて利用可能であるベクトルの限定された集合のみを使用することは、更に魅力的である。
【００４３】
前記動きモデルの推定されたパラメータｐ１（ｎ）、ｐ２（ｎ）及びｐ３（ｎ）は、次いで、ローカル候補計算インスタンス９に入力され、動きベクトル
2006513478.tif 000054
が構成され、続いて、更新なしに、予測メモリインスタンス１からの空間的（これらの一部は、更新され得る）及び時間的予測と共に、事前選択インスタンス６に入力される。
【図面の簡単な説明】
【００４４】
【図１】動きベクトルがローカルベクトルとして推定されている、本発明による帰納的ＢＭＡの第１実施例を示している。
【図２】ローカルベクトルとしての動きベクトルの推定が、全体の動きモデルによって予測される候補動きベクトルを取り入れることによって強調されている、本発明による帰納的ＢＭＡの第２実施例を示している。
【図１】
2006513478.tif 000055
【図２】
2006513478.tif 000056
【国際調査報告】
2006513478.tif 000057
2006513478.tif 000058
2006513478.tif 000059