JP4528441B2 - ブロック整合法及び統合投射法を用いた階層的動き評価処理及び装置 - Google Patents

Description

【０００１】
発明の背景
本発明は、ビデオ画像処理における動き評価を行う装置及び方法に関し、特に、粗検索ブロック整合動き予測法（sparse search block-matching motion estimation technique）及び統合射影情報（integral projection）に基づく階層的動き評価法を用いてビデオ画像のフレーム間の動きベクトルを判定する改善された装置及び方法に関する。
【０００２】
デジタル技術の進歩により、多くのデジタル映像のアプリケーションが開発されている。デジタル映像技術は、現在、デジタル高解像度テレビジョン、ビデオ会議、コンピュータによる画像処理、高画質ビデオテープレコーダ等に利用されている。圧縮されていないデジタル映像信号のデータ量は膨大であり、このようなデータの伝送及び記録のためには、広い帯域幅及び大きな記録容量が必要となる。そこで、多くのデジタル映像処理装置は、各アプリケーションに最適化されたデータ圧縮技術を採用し、これによりデジタル映像データのデータ量を削減している。デジタル圧縮装置は、一般に「符号化器（エンコーダ）」と呼ばれ、伸長処理を行う装置は、「復号器（デコーダ）」と呼ばれる。圧縮及び伸長の両方を行う装置は「符号化／復号器（コーデック）」と呼ばれる。
【０００３】
動画像ビデオデータの圧縮法を標準化するために、ＭＰＥＧ（Motion Picture Experts Group）は、複数種類のデジタル映像処理標準技術を提唱している。ＭＰＥＧ−１は、デジタル音声及びデジタル映像のコーディングを行うものであり、中間のデータレートを必要とする映像装置に広く使用されている。ＭＰＥＧ−２は、例えば直接放送衛星システム（direct broadcast satellite system）等における、より高いデータレートを用いる装置に使用されている。
【０００４】
動画像映像シーケンスは、連続する複数の静止画像、すなわち「フレーム」から構成され、これらフレームを連続的に表示することにより、連続的な動きが表現される。各フレームは、画像の要素、すなわち「画素」の２次元的な配列として記述することができる。各画素は、画像における特定の点の輝度及び色を記述する。画素情報は、デジタル形式で表現又は符号化でき、デジタル的に伝送することもできる。
【０００５】
映像データの一圧縮法として、映像シーケンスにおいて隣接するフレーム間の冗長性を利用する手法がある。隣接するフレームは類似する情報を含んでいる傾向があり、新規なフレームを作成するより、フレーム間の差分を記述する方がデータ量が少なくてすむ場合が多い。例えば、フレーム間に全く動きがない場合、フレーム全体を再度コーディングするより、フレーム間の差分（ゼロ）をコーディングする方がデータ量を節減できる。
【０００６】
動き評価とは、隣接するフレーム間の変位を評価する処理である。この変位は、動きベクトルによって表され、動きベクトルは、現在のフレームにおける特定の領域と、先行する又は後続する参照フレームにおける対応する変位した領域との間の最大整合性（best match）を示すものである。現在のフレームにおける特定の領域と、参照フレームにおける対応する変位された領域の差分を「剰余情報（residue）」と呼ぶ。
【０００７】
動きベクトルを評価するための動き評価には、大きく分けて、画素再帰アルゴリズム（pixel-recursive algorithm）及びブロック整合アルゴリズム（block-matching algorithm）の２つの手法がある。画素再帰アルゴリズムでは、隣接するフレームにおける対応する画素に対する各画素の変位を繰り返し予測する。一方、ブロック整合アルゴリズムでは、フレーム間の変位をブロック毎に評価し、差分を最小化するベクトルを選択する。
【０００８】
従来のブロック整合処理では、符号化すべき現在の画像を同じサイズの画素情報を有する複数のブロックに分割する。ＭＰＥＧ映像圧縮標準技術では、画素はマクロブロックとしてグループ化される。マクロブロックは、それぞれが２つの色差成分用の８×８サンプルブロックに対応する１６×１６輝度サンプル配列から構成される。さらに、１６×１６輝度サンプル配列は、通常圧縮モデルの入力ブロックとして使用される４つの８×８ブロックから構成される。
【０００９】
Ｆｉｇ．１は、従来の１回のブロック整合処理を説明する図である。現在のフレーム１２０は、複数のブロックに分割されている。各ブロックは、いかなるサイズであってもよいが、例えばＭＰＥＧ装置においては、現在のフレーム１２０は、通常１６×１６サイズのマクロブロックに分割される。現在のフレーム１２０をコード化するために、現在のフレーム１２０内の各ブロックと、先行するフレーム１１０又は後続するフレーム１３０におけるブロックとの差分をコード化する。各ブロック整合処理において、現在のブロック１００は、先行するフレーム１１０における検索範囲１１５又は後続するフレーム１３０における検索範囲１３５内の同サイズの候補ブロック（"candidate" blocks）と比較される。先行又は後続するフレーム内の候補ブロックのうち、現在のブロック１００と差分が最も小さいブロックが、Ｆｉｇ．１に示すように、参照ブロック１５０として選択される。続いて、参照ブロック１５０と現在のブロック１００間の動きベクトル及び剰余情報が算出され、コード化される。現在のフレーム１２０は、伸長処理において、参照フレーム１１０の各ブロックのコードと、現在のフレーム１２０に関する動きベクトル及び剰余情報のコードとを用いて復元される。
【００１０】
ブロック間の差分は、周知のいかなる基準に基づいて算出してもよいが、多くの場合、誤差を最小化する手法又は相関性を最大化する手法が用いられる。さらに、相関法は、計算量が多いため、誤差算出法が最も多く用いられている。誤差算出測定の手法には、自乗誤差平均法（mean square error：以下、ＭＳＥという。）、絶対歪み平均法（mean absolute distortion：以下、ＭＡＤという。）、絶対歪み総和法（sum of absolute distortion：以下、ＳＡＤという。）等がある。これらの判定基準は、インターナショナルトムソンパブリッシング社（International Thomson Publishing）より１９９７年に発行された、ジョーン・エル・ミッチェル他（Joan L. Mitchell et al.）著、「ＭＰＥＧ映像圧縮標準技術（MPEG Video Compression Standard）」の第２８４〜２８６頁に記載されている。整合性の判定基準としては、ＳＡＤが最も多く使用されている。
【００１１】
ＳＡＤは、以下のように定義される。
【００１２】
【数１】

【００１３】
ここで、ブロックサイズはＭ×Ｎであり、ｒ（ｘ，ｙ）は現在のブロックを表し、ｓ（ｘ＋ｉ，ｙ＋ｉ）は参照フレームにおける検索範囲１１５内の候補ブロックを表す。動きベクトルは値（ｉ，ｊ）は、ＳＡＤ（ｉ，ｊ）を最小とする値である。
【００１４】
現在のブロックと検索範囲内の全ての候補ブロックとを比較するブロック整合アルゴリズムは、「完全検索（full search）」と呼ばれる。一般的に、検索範囲を広くすれば、より正確な変位ベクトルを生成することができる。しかしながら、完全検索の計算の複雑性は、検索範囲のサイズに比例して高くなり、いくつかの適用例では処理時間が長すぎて使用できない。例えば、±Ｎの検索範囲において、１画素の精度で１６×１６画素サイズのマクロブロックに関する完全検索ブロック整合アルゴリズムを適用した場合、（２×Ｎ＋１）^２回のブロック比較処理が必要となる。Ｎを１６とした場合、１０８９回の１６×１６ブロックの比較処理が必要となる。各ブロックの比較は、１６×１６、すなわち２５６回の計算を必要とするため、この手法では計算量が膨大で、処理時間が遅くなる。また、ここで、単に検索範囲を狭くする手法では、最適な整合ブロックを見落としてしまう危険性が高くなってしまう。
【００１５】
このため、広い検索範囲で整合ブロックを正しく検出するための高速なアルゴリズムの開発が進められてきた。このような手法のいくつかは、上述のジョーン・エル・ミッチェル他の著書の第３０１〜３１１頁に記載されている。最も高速な検索法は、検索範囲全体に亘って粗サンプリング（sparse sampling）を行い、この粗サンプルのみに対して変位を算出することにより処理速度を高めている。例えば、２次元対数検索（2-D logarithmic search）は、最小歪み方向へ移動する連続するブロックのＭＳＥを算出することにより計算量を低減する。共役方向検索（conjugate direction search）では、アルゴリズムは、最小歪みを検出するまで水平方向への検索を行う。さらに、アルゴリズムは、最小歪みを検出した点から、垂直方向への検索を開始し、最小歪みを検出する。これら２つの手法は、いずれも完全検索に比べて高速な処理を実現するが、最適な整合ブロックの判定に失敗する可能性も高い。
【００１６】
完全検索の計算量を低減する他の手法としては、空間領域画素情報を直接用いる代わりに、統合射影情報（integral projection）を用いてブロック間の変位を算出する手法がある。画素情報の統合射影情報とは、水平方向又は垂直方向に沿った画像画素値の総和の１次元の配列である。ブロック整合アルゴリズムにおいて、画素情報の２次元配列を用いる代わりに、１次元水平射影配列及び１次元垂直射影配列の２つの１次元射影配列を用いることにより、各ブロック整合処理における計算の回数を著しく低減することができる。この手法は、１９８７年に発表された、アイ・エイチ・リー（I.H.Lee）及びアール・エイチ・パーク（R.H.Park）による論文「統合射影情報を用いた高速ブロック整合アルゴリズム（"A Fast Block Matching Algorithm Using Integral Projections," Proc. Tencon '87 Conf）」の第５９０〜５９４頁に記載されている。
【００１７】
高速の動き評価法は、あるデジタル映像フォーマットを他のデジタル映像フォーマットに変換する際に特に有用である。デジタル映像は、符号化され、圧縮された形式で保存される。従来の装置を用いて、あるフォーマットを他のフォーマットに変換する場合、デジタル映像は、元のフォーマットに伸長及び復号され、続いて目的のフォーマットに符号化及び圧縮されて保存又は伝送される。このような、デジタル映像を一度完全に復号する必要のある変換法は、非常に時間のかかるものである。
【００１８】
このような完全検索の問題点を克服するために階層的検索法を採用した手法が知られている。この手法では、第１の処理段階において、例えば、適度な広さの領域に対して粗検索を行う。続いて、行われる従来型の階層的検索処理においては、検索範囲が縮小される。３段階の階層的検索の例は、１９９４年８月に発行された「映像技術のための回路及びシステムに関するＩＥＥＥトランザクション（IEEE Trans. On Circuits and Systems for Video Technology, Vol.4, August 1994, pp.407-416）」第４巻第４０７〜第４１６頁、エイチ・エム・ジョン（H.M.Jong）他著、「３段階階層的検索ブロック整合アルゴリズムのためのパラレルアーキテクチャ（Parallel Architectures for 3-Step Hierarchical Search Block-Matching Algorithm）」に開示されている。ここに開示されている階層的検索法における粗検索処理段階では全ての画素情報を利用しておらず、したがって誤った開始点からより精密な検索を開始してしまうことがあるため、この手法は、いくつかの適用例においては不適切な処理を行ってしまう。
【００１９】
本発明は、動きベクトルの精度を維持しながら、ブロック比較処理の回数を最小化して高速階層的検索を実行する、改善された動き評価装置及び動き評価方法を提供することを目的とする。また、本発明は、本発明に基づく階層的検索処理及び統合射影情報を用いて、さらに計算の回数を低減できる動き評価装置及び動き評価方法を提供することを目的とする。さらに、本発明は、統合射影情報を用いて、画素データを完全に復号する必要なく、デジタル映像データをあるフォーマットから他のフォーマットに変換することにより、データフォーマットの変換処理時間を大幅に短縮できる階層的動き評価装置及び動き評価方法を提供することを目的とする。
【００２０】
発明の開示
本発明に係るベクトル判定方法は、ビデオ画像データにおける第１及び第２のフレーム間の動きベクトルを生成する動きベクトル判定方法において、（ａ）第１のフレームにおいて、画素情報の２次元配列として構成される現在のマクロブロックを決定するステップと、（ｂ）第１のフレームにおいて、現在のマクロブロックと複数のマクロブロックとから構成される現在のスーパーマクロブロックを決定するステップと、（ｃ）現在のスーパーマクロブロックと第１の検索範囲とに基づいて、第２のフレームにおける第１の検索領域を選択するステップと、（ｄ）変位判定基準と現在のスーパーマクロブロックとに基づいて、第１の検索範囲における最良候補スーパーマクロブロックを判定するステップと、（ｅ）最良候補スーパーマクロブロックを複数の候補マクロブロックに分割するステップと、（ｆ）複数の候補マクロブロックと第２の検索範囲とに基づいて、第２のフレームにおける複数の第２の検索範囲を選択するステップと、（ｇ）変位判定基準と現在のマクロブロックとに基づいて、第２の検索範囲における最良候補マクロブロックを判定するステップと、（ｈ）現在のマクロブロックと第１の最良候補マクロブロックとの間の距離を表す第１の動きベクトルを判定するステップとを有する。
【００２１】
また、本発明に係る動きベクトル判定装置は、ビデオ画像データにおける第１及び第２のフレーム間の動きベクトルを生成する動きベクトル判定装置において、プログラム命令が格納されたメモリと、プログラム命令を実行することにより、（ａ）第１のフレームにおいて、画素情報の２次元配列として構成される現在のマクロブロックを決定するステップと、（ｂ）第１のフレームにおいて、現在のマクロブロックと複数のマクロブロックとから構成される現在のスーパーマクロブロックを決定するステップと、（ｃ）現在のスーパーマクロブロックと第１の検索範囲とに基づいて、第２のフレームにおける第１の検索領域を選択するステップと、（ｄ）変位判定基準と現在のスーパーマクロブロックとに基づいて、第１の検索範囲における最良候補スーパーマクロブロックを判定するステップと、（ｅ）最良候補スーパーマクロブロックを複数の候補マクロブロックに分割するステップと、（ｆ）複数の候補マクロブロックと第２の検索範囲とに基づいて、第２のフレームにおける複数の第２の検索範囲を選択するステップと、（ｇ）変位判定基準と現在のマクロブロックとに基づいて、第２の検索範囲における最良候補マクロブロックを判定するステップと、（ｈ）現在のマクロブロックと第１の最良候補マクロブロックとの間の距離を表す第１の動きベクトルを判定するステップとを実行するプロセッサとを備える。
【００２２】
また、本発明に係るコンピュータプログラム製品は、ビデオ画像データにおける第１及び第２のフレーム間の動きベクトルを生成するコンピュータにより読取可能なコードが実現されたコンピュータにより使用可能な媒体を備えるコンピュータプログラム製品において、コンピュータにより使用可能な媒体は、（ａ）第１のフレームにおいて、画素情報の２次元配列として構成される現在のマクロブロックを決定するコンポーネントと、（ｂ）第１のフレームにおいて、現在のマクロブロックと複数のマクロブロックとから構成される現在のスーパーマクロブロックを決定するコンポーネントと、（ｃ）現在のスーパーマクロブロックと第１の検索範囲とに基づいて、第２のフレームにおける第１の検索領域を選択するコンポーネントと、（ｄ）変位判定基準と現在のスーパーマクロブロックとに基づいて、第１の検索範囲における最良候補スーパーマクロブロックを判定するコンポーネントと、（ｅ）最良候補スーパーマクロブロックを複数の候補マクロブロックに分割するコンポーネントと、（ｆ）複数の候補マクロブロックと第２の検索範囲とに基づいて、第２のフレームにおける複数の第２の検索範囲を選択するコンポーネントと、（ｇ）変位判定基準と現在のマクロブロックとに基づいて、第２の検索範囲における最良候補マクロブロックを判定するコンポーネントと、（ｈ）現在のマクロブロックと第１の最良候補マクロブロックとの間の距離を表す第１の動きベクトルを判定するコンポーネントとを備える。
【００２３】
さらに、本発明に係る動きベクトル判定システムは、ビデオ画像データにおける第１及び第２のフレーム間の動きベクトルを生成する動きベクトル判定システムにおいて、（ａ）第１のフレームにおいて、画素情報の２次元配列として構成される現在のマクロブロックを決定する現在マクロブロック決定手段と、（ｂ）第１のフレームにおいて、現在のマクロブロックと複数のマクロブロックとから構成される現在のスーパーマクロブロックを決定する現在スーパーマクロブロック決定手段と、（ｃ）現在のスーパーマクロブロックと第１の検索範囲とに基づいて、第２のフレームにおける第１の検索領域を選択する第１検索領域選択手段と、（ｄ）変位判定基準と現在のスーパーマクロブロックとに基づいて、第１の検索範囲における最良候補スーパーマクロブロックを判定する最良候補スーパーマクロブロック判定手段と、（ｅ）最良候補スーパーマクロブロックを複数の候補マクロブロックに分割する分割手段と、（ｆ）複数の候補マクロブロックと第２の検索範囲とに基づいて、第２のフレームにおける複数の第２の検索範囲を選択する第２検索範囲選択手段と、（ｇ）変位判定基準と現在のマクロブロックとに基づいて、第２の検索範囲における最良候補マクロブロックを判定するステップ最良候補マクロブロック判定手段と、（ｈ）現在のマクロブロックと第１の最良候補マクロブロックとの間の距離を表す第１の動きベクトルを判定する第１動きベクトル判定手段とを備える。
【００２４】
発明の好適な実施の形態の説明
以下、添付の図面に示された具体例を参照して、本発明の好適な実施の形態について詳細に説明する。
【００２５】
Ａ．階層的検索処理（Hierarchical Search Process）
動き評価法は、各フレーム全体を符号化する代わりに、隣接するフレームからの差分に関する情報を符号化することにより、デジタル映像シーケンスを表現するために必要なデータ量を圧縮する技術である。映像シーケンスを再生する際には、復号器は、参照フレームとともに動きベクトルを用いて現在のフレームを再構築する。
【００２６】
本発明に基づく手法では、複数段の処理（multi-stage operation）により、現在のフレームの各ブロックについて、参照フレームに対する動きベクトルが評価される。第１の処理段階では、本発明に基づく方法を実現するアプリケーションは、参照フレームにおける第１検索範囲を粗検索し、現在のスーパーマクロブロック（supermacroblock）に最も近似する候補スーパーマクロブロックを検出する。第２の処理段階では、このスーパーマクロブロックを複数のマクロブロックコンポーネントに分割する。これら複数のマクロブロックコンポーネントは、検索範囲を構成し、この検索範囲において候補マクロブロックが検索される。現在のマクロブロックに近似に近似するマクロブロックをさらに高精度に検出するためのさらなる処理段階を設けてもよい。
【００２７】
Ｆｉｇ．２は、現在のフレーム２２０と参照フレーム２１０を示す図である。参照フレームは、先行するフレームであっても、後続するフレームであってもよい。現在のフレーム２２０は、それぞれＭ×Ｎ画素から構成される複数のブロック２２５に分割される。Ｍ及びＮは、２以上のいかなる整数であってもよいが、この具体例においては、ＭＰＥＧ−１／２映像圧縮標準技術における標準的なマクロブロックのサイズと同様に、Ｍ＝Ｎ＝１６とする。現在のフレーム２２０を表すために、現在のフレーム２２０内の各ブロック２２５は、現在のフレーム２２０のマクロブロック及び参照フレーム２１０のマクロブロック間の剰余情報により表される。
【００２８】
Ｆｉｇ．３Ａ及びＦｉｇ．３Ｂは、本発明に基づく階層的検索法により、現在のフレームにおける１つのマクロブロックのための動きベクトルを導き出す手順を示すフローチャートである。まず、まず、ステップ３０２において、Ｆｉｇ．２に示す現在のフレーム２２０における現在のマクロブロック２３０が選択される。現在のマクロブロック２３０は、Ｍ×Ｎ画素のサイズを有している。Ｍ及びＮは、２以上のいかなる整数であってもよいが、この具体例においては、Ｍ＝Ｎ＝１６とする。
【００２９】
続いて、Ｆｉｇ．３Ａに示すステップ３０４において、現在のマクロブロック２３０を用いて、現在のスーパーマクロブロック２３５が決定される。現在のスーパーマクロブロックは、現在のマクロブロック２３０と、この現在のマクロブロック２３０と同じサイズ及び形状を有する隣接するいくつかのマクロブロックとから構成される。Ｆｉｇ．２に示す例では、現在のスーパーマクロブロック２３５は、現在のフレーム２２０内において、現在のマクロブロック２３０を左上コーナ部とする４つのマクロブロックから構成されている。
【００３０】
Ｆｉｇ．３Ａに示すステップ３０６において、参照フレーム２１０における検索領域２１５が選択される。Ｆｉｇ．２に示す検索領域２１５は、検索範囲（±ｐ_１，±ｑ_１）により定義され、現在のフレーム２２０における現在のスーパーマクロブロック２３５の位置に基づいて決定される。検索範囲ｐ_１，ｑ_１所定の値であってもよく、動的に決定されるものであってもよい。また、検索範囲値ｐ_１，ｑ_１は、１以上の正の整数でフレームサイズより小さいいかなる値であってもよい。通常、検索範囲が広いほどより正確な動きベクトルを生成することができるが、検索範囲の広さに比例して検索処理の複雑性が高くなるため、全フレームサイズより狭い検索範囲値ｐ_１，ｑ_１を指定することが望ましい。以下では、例示的に、検索範囲（±ｐ_１，±ｑ_１）を（±３２，±２４）とする。Ｆｉｇ．２において、（ｍ，ｎ）として示される点は、現在のフレーム２２０における現在のマクロブロック２３５の左上のコーナの画素に対応する点である。検索範囲を（±３２，±２４）とした場合、検索範囲２１５は、Ｆｉｇ．２に示すように、（ｍ−３２，ｎ−２４）（ｍ＋３２，ｎ−２４）（ｍ＋３２，ｎ＋２４）（ｍ−３２，ｎ＋２４）により定義される領域である。検索範囲２１５は、参照フレーム２１０内の可能な全てのスーパーマクロブロックの左上コーナを限定するものである。
【００３１】
本発明に基づく階層的動き予測処理の第１の処理段階では、検索範囲２１５内の候補スーパーマクロブロックと現在のスーパーマクロブロック２３５とを比較し、検索範囲２１５内における「最良」候補スーパーマクロブロックを検出する。「最良」候補スーパーマクロブロックとは、周知の任意の誤差算出法又は相関判定法を用いて、現在のスーパーマクロブロック２３５と比較して、最も誤差が少ない、又は相関性が高いと判定されるスーパーマクロブロックである。
【００３２】
ステップ３０８において、第１の検索処理段階が選択される。候補スーパーマクロブロックは、現在知られているいかなるブロック整合検索法により選択してもよく、例えば完全検索を行ってもよく、あるいは、検索範囲内において所定の画素検索間隔を適用してスーパーマクロブロックを比較することにより選択してもよい。ここで、候補スーパーマクロブロックの選択には、１９９８年５月２０日に出願された、チャン（Chang）他による米国特許出願第０９／０８１，２７９号「粗検索ブロック整合法及び統合射影情報を用いた動き評価処理及び装置(Motion Estimation Process and System Using Sparse Block-Maching and Integral Projection)」に開示されている手法を用いてもよく、この出願は参照により本願に組み込まれるものとする。
【００３３】
従来の完全検索法及びチャン他に記載されている検索法を含む多くの検索法において、画素シフト間隔としては様々な値を用いることがある。例えば、画素シフト間隔Ｋ_１を１画素分とした場合、各１画素毎にブロック比較を行う精密な検索を行うことができる。しかしながら、画素シフト間隔を１画素分として、完全検索を行った場合、計算処理は複雑なものとなり、したがって、この処理段階では画素シフト間隔を大きくすることが望ましい。画素シフト間隔Ｋ_１を４画素分とした場合、４画素毎に検索処理を行うため、粗検索が実現される。画素シフト間隔は、水平方向及び垂直方向において異なるものであってもよい。説明のため、ここでは、両方向に対し、同じ４画素分の画素シフト間隔を用いるものとする。
【００３４】
続いて、ステップ３１２において、選択された検索処理及び所定の整合性判定基準を用いて、現在のスーパーマクロブロック２３５と、検索範囲２１５内のスーパーマクロブロックとを比較し、第１の検索範囲における最良候補スーパーマクロブロックを検出する。絶対歪み総和ＳＡＤを整合性判定基準（matching criteria）として用いると、検索処理全体を以下のように表すことができる。
【００３５】
【数２】

【００３６】
ここで、−ｐ_１≦ｉ≦＋ｐ_１、−ｑ_１≦ｊ≦＋ｑ_１、ｒは現在の３２×３２画素のスーパーマクロブロックを表し、ｓは候補スーパーマクロブロックを表す。ＳＡＤ（ｉ，ｊ）の値を最小化する（ｉ，ｊ）の組により現在のスーパーマクロブロック２３５の動きベクトルが定義される。例えば、動きベクトル（１，１）は、参照フレーム内において、現在のスーパーマクロブロック２３５に対応する位置から１画素分水平方向に右に移動し、１画素分垂直方向に下に移動したスーパーマクロブロックが現在のスーパーマクロブロック２３５に近似することを示す。
【００３７】
上述の各スーパーマクロブロックに関する演算では、３２×３２回の計算が必要である。ここで、３２×３２＝１０２４個の画素のうち選択された下位集合のみに対してＳＡＤを算出することにより、計算回数を低減することができる。また、画素領域情報ではなく統合射影情報を用いてブロック比較を行うことにより計算の回数をさらに低減することができる。画素情報の統合射影情報は、水平方向又は垂直方向に沿った複数の画素値の総和を表す情報である。Ｆｉｇ．４Ａは、垂直統合射影情報を説明する図であり、Ｆｉｇ．４Ｂは、水平統合射影情報を説明する図である。
【００３８】
統合射影情報は、画素情報から１次元の統合射影配列を算出することにより、あるいは、例えばデジタルビデオ復号器からの離散コサイン変換（discrete cosine transform：以下、ＤＣＴという。）係数データに基づく統合射影情報を算出することにより得られる。特に、本発明は、必要な計算処理を低減し、したがって、１つのデジタル映像フォーマットから他のデジタルフォーマットへの変換、例えばデジタルビデオフォーマット（digital video：ＤＶ）からＭＰＥＧフォーマットへの変換に要する計算処理時間を短縮する点で有効である。
【００３９】
ＤＣＴは、数学的には以下のように表される。
【００４０】
【数３】

【００４１】
ここで、ｈ＝０，１，・・・，７、ｖ＝０，１，・・・，７であり、ｃ（ｈ）及びｃ（ｖ）は以下の値をとる。
【００４２】
【数４】

【００４３】
Ｐ（ｘ，ｙ）は、８×８ブロックの画素データであり、Ｑ（ｈ，ｖ）は、８×８ブロックのＤＣＴ係数である。数学的には、８×８ブロックのＤＣＴ係数を１次元の水平逆ＤＣＴへ入力した場合、演算結果は８×８配列となり、この配列の第１列は、定数が乗算された各行の画素情報の総和を含む。したがって、この第１列は、８×８ブロックの画素情報の１次元垂直射影情報に等しい。同様に、同じ８×８ブロックのＤＣＴ係数を１次元垂直逆ＤＣＴへ入力した場合、演算結果の第１行は、元となる８×８ブロックの画素情報の１次元水平射影情報に等しくなる。垂直統合射影情報及び水平統合射影情報は、動きベクトルの評価に使用することができる。
【００４４】
この具体例においては、各スーパーマクロブロックは、４つの隣接するマクロブロックからなり、各マクロブロックは、４つの隣接する８×８ブロックからなる。したがって、各スーパーマクロブロックは、１６個の８×８ブロックから構成される。各スーパーマクロブロックの比較に必要な計算の回数は、垂直統合射影情報又は水平統合射影情報を用いることにより低減できる。各８×８ブロックに対する垂直（又は水平）統合射影情報は、例えば、８×８ブロックにおける第１〜４行（又は列）の３２画素の画素値と第５〜８行（又は列）の３２画素の画素値との和として算出される。ＤＣＴ領域の情報を利用できる場合、２つの統合射影情報は、各２次元８×８ＤＣＴブロックにおける第１行（又は列）の最も小さい２つの係数に対する１次元２点逆ＤＣＴ（one-dimensional 2-point IDCT）を実行することにより得られる。これにより、各スーパーマクロブロックは、２×１６＝３２個の垂直（又は水平）統合投影情報により表現される。したがって、各スーパーマクロブロックの比較に必要な計算の回数は、３２回の計算と統合射影情報の算出に必要な計算とに減少させることができる。
【００４５】
統合射影情報は、例えば、８×８ブロックにおいて２つずつの行（又は列）の総和を求めて、４つの統合射影情報を得るか、又は各行（又は列）について個別に総和を求めて８つの統合射影情報を得ることによっても算出できることは、当業者にとって明らかである。同様に、統合射影配列は、ＤＣＴブロックの係数に対する１次元４点逆ＤＣＴを実行して得られるＤＣＴ領域情報からも得ることができる。これらの手法は、上述した２点統合射影配列の算出より多くの計算を必要とするが、画素情報を用いた同様の手法に比べると計算回数は少ない。
【００４６】
Ｆｉｇ．５は、第１の検索処理により得られる最良スーパーマクロブロック５１０を示す図である。最良スーパーマクロブロック５１０の左上コーナの座標は（ｕ，ｖ）であり、これは第１の検索処理における現在のスーパーマクロブロックへの動きベクトルである。Ｆｉｇ．５に示すように、スーパーマクロブロック５１０は、ステップ３１４において、複数の候補マクロブロック１，２，３，４に分割され、本発明に基づく階層的検索処理の第２の処理段階が開始される。ステップ３１６においては、第２の処理段階のための検索範囲（±ｐ_２，±ｑ_２）が決定される。各候補マクロブロック１，２，３，４について、候補マクロブロックと検索範囲（±ｐ_２，±ｑ_２）とに基づいて、検索範囲が決定される。例えば、Ｆｉｇ．６に示す検索範囲６１０は、候補マクロブロック１と検索範囲（±ｐ_２，±ｑ_２）により定義されている。検索範囲（±ｐ_２，±ｑ_２）は、所定のものであってもよく、動的に決定されるものであってもよい。検索範囲値ｐ_２，ｑ_２は、全てのフレームについて同一の値であってもよく、現在のフレームと参照フレームとの時間差によって異なるものとしてもよい。さらに、検索範囲検索ｐ_２，ｑ_２は、１以上でフレームサイズ以下のいかなる整数であってもよい。検索範囲値ｐ_２をｐ_１より小さくし、検索範囲値ｑ_２をｑ_１より小さくすることにより、第２の検索領域６１０は、Ｆｉｇ．２に示す第１の検索範囲２１５より小さくなる。通常、検索範囲を小さくすると、第１の処理段階により検出された動きベクトルの精度をさらに高めることができる。
【００４７】
ステップ３１８においては、第２の検索処理が選択され、ステップ３２０においては、画素シフト間隔Ｋ_２が選択される。最良候補マクロブロックは、現在知られているいかなるブロック整合検索法により選択してもよく、例えば完全検索を行ってもよく、あるいは、検索範囲内において所定の画素検索間隔を適用してマクロブロックを比較することにより選択してもよい。本発明の１具体例においては、候補マクロブロックは、上述したチャン他による米国特許出願第０９／０８１，２７９号に開示されている手法を用いる。Ｋ_２は、１以上で検索範囲以下のいかなる整数であってもよい。Ｋ_２＝１とした場合、１画素分ずつ比較処理を行う完全検索と同様の処理を実行することとなる。
【００４８】
ステップ３２２において、各候補マクロブロック１，２，３，４について、所定の検索領域に対する選択された検索処理が実行される。絶対歪み総和ＳＡＤを整合性判定基準として用いると、各マクロブロックの比較処理は、以下のように定義することができる。
【００４９】
【数５】

【００５０】
ここで、−ｐ_２≦ｉ≦＋ｐ_２、−ｑ_２≦ｊ≦＋ｑ_２、ｒは現在の１６×１６画素のマクロブロック２３０を表し、ｓは検索範囲６１０における１６×１６画素の候補マクロブロックを表す。
【００５１】
この具体例において、各マクロブロックは４つの隣接する８×８ブロックから構成される。各マクロブロックの比較に必要な計算回数は、垂直統合射影情報又は水平統合射影情報を用いることにより低減できる。各８×８ブロックに対する垂直（又は水平）統合射影情報は、例えば、８×８ブロックにおける第１〜４行（又は列）の３２画素の画素値と第５〜８行（又は列）の３２画素の画素値との和として算出される。ＤＣＴ領域の情報を利用できる場合、２つの統合射影情報は、各２次元８×８ＤＣＴブロックにおける第１行（又は列）の最も小さい２つの係数に対する１次元２点逆ＤＣＴを実行することにより得られる。これにより、各スーパーマクロブロックは、２×４＝８個の垂直（又は水平）統合投影情報により表現される。したがって、各スーパーマクロブロックの比較に必要な計算の回数は、８回の計算と統合射影情報の算出に必要な計算とに減少させることができる。
【００５２】
統合射影情報は、例えば、８×８ブロックにおいて２つずつの行（又は列）の総和を求めて、４つの統合射影情報を得るか、又は各行（又は列）について個別に総和を求めて８つの統合射影情報を得ることによっても算出できる。同様に、統合射影配列は、ＤＣＴブロックの係数に対する１次元４点逆ＤＣＴを実行して得られるＤＣＴ領域情報からも得ることができる。これらの手法は、上述した２点統合射影配列の算出より多くの計算を必要とするが、画素情報を用いた同様の手法に比べると計算回数は少ない。
【００５３】
現在のマクロブロックの動きベクトルの精度は、ステップ３２４において第３の検索処理段階を実行することによりさらに高められる。第３の検索範囲は、第２の階層的検索処理及び検索範囲（±ｐ_３，±ｑ_３）に基づいて決定される。検索範囲（±ｐ_３，±ｑ_３）は、所定のものであってもよく、動的に決定されるものであってもよい。検索範囲値ｐ_３，ｑ_３は、全てのフレームについて同一の値であってもよく、現在のフレームと参照フレームとの時間差によって異なるものとしてもよい。さらに、検索範囲検索ｐ_３，ｑ_３は、１以上でフレームサイズ以下のいかなる値であってもよい。検索範囲値ｐ_３をｐ_２より小さくし、検索範囲値ｑ_３をｑ_２より小さくすることにより、第３の検索範囲は、Ｆｉｇ．５に示す第２の検索範囲５１０より小さくなる。なお、この処理段階においては、検索範囲（±１，±１）が推奨される。
【００５４】
続いて、第３の検索処理及び画素シフト間隔Ｋ_３が選択される。画素シフト間隔Ｋ_３は、１以上で検索範囲以下のいかなる値であってもよい。なお、階層的検索処理における第３の処理段階では、画素シフト間隔Ｋ_３を１とすることが望ましい。Ｋ_３＝１とすることにより、それぞれ１画素ずつ移動した位置から開始される比較処理を行う完全検索と同じ処理が実行される。
【００５５】
現在のマクロブロックの動きベクトルの精度は、ステップ３２６において第４の検索処理段階を実行することによりさらに高められる。第４の検索範囲は、第３の階層的検索処理及び検索範囲（±ｐ_４，±ｑ_４）に基づいて決定される。検索範囲（±ｐ_４，±ｑ_４）は、所定のものであってもよく、動的に決定されるものであってもよい。検索範囲値ｐ_４，ｑ_４は、全てのフレームについて同一の値であってもよく、現在のフレームと参照フレームとの時間差によって異なるものとしてもよい。さらに、検索範囲検索ｐ_４，ｑ_４は、０より大きくフレームサイズ以下のいかなる値であってもよい。検索範囲値ｐ_４をｐ_３より小さくし、検索範囲値ｑ_４をｑ_３より小さくすることにより、第３の検索範囲は、第３の検索範囲より小さくなる。なお、この処理段階においては、検索範囲（±０．５，±０．５）が推奨される。
【００５６】
続いて、第４の検索処理及び画素シフト間隔Ｋ_４が選択される。画素シフト間隔Ｋ_３は、０より大きく、検索範囲以下のいかなる値であってもよい。なお、階層的検索処理における第４の処理段階では、画素シフト間隔Ｋ_４を０．５とすることが望ましい。当業者にとって明らかであるが、Ｋ_４＝０．５とすることにより、半画素検索（half-pixel search）に等しい処理が実行される。
【００５７】
第４の階層的検索処理段階が完了すると、この第４の階層的検索処理段階においてＳＡＤ（ｉ，ｊ）の値を最小とする（ｉ，ｊ）の組により現在のマクロブロック２３０の動きベクトルが定義される。例えば、動きベクトル（１，１）は、参照フレーム内において、現在のマクロブロックに対応する位置から１画素分水平方向に右に移動し、１画素分垂直方向に下に移動したマクロブロックが現在のマクロブロックに近似することを示す。ステップ３２８において、この動きベクトルは記録され、また一連の画素差分は現在のマクロブロックと候補マクロブロック間の剰余情報として記録される。
【００５８】
ステップ３２４における第３の検索処理及びステップ３２６における第４の検索処理は、処理量の低減が望まれるいくつかの実現例においては、省略してもよい。
【００５９】
Ｂ．システム
Ｆｉｇ．７は、本発明に基づくシステム７０５の構成を示す図である。Ｆｉｇ．７に示すように、プロセッサ７１０は、任意の適切なデータ接続線を介して、少なくとも１つの入出力装置７２０に接続されている。入出力装置７２０は、プロセッサ７１０にデータを供給し、また、プロセッサ７１０からデータを受信する能力を有するいかなる装置であってもよい。入出力装置７２０は、例えばＩＥＥＥ１３９４インターフェイスを介して接続されるデジタルカムコーダであってもよい。プロセッサ７１０は、例えばペンティアムプロセッサ（Pentium processor：商標）等、市販されているいかなるデジタルプロセッサであってもよい。また、プロセッサ７１０は、単一のプロセッサであっても複数のプロセッサであってもよい。なお、プロセッサ７１０の処理速度が速いほど、本発明における処理時間が短くなる。
【００６０】
さらに、本発明に基づくシステム７０５は、プロセッサ７１０により処理され、及び入出力装置７２０に供給され又は入出力装置７２０から供給されるデータを格納するメモリ７３０を備える。さらに、システム７０５は、例えば陰極線管等、情報を表示するための表示装置７４０を備えていてもよい。プロセッサ７１０、入出力装置７２０、メモリ７３０、表示装置７４０は、標準システムバス７６０を介して相互に接続されている。Ｆｉｇ．７は、各ハードウェアコンポーネントが従来の市販されているコンピュータシステムコンポーネントにより実現された例示的なネットワークを示している。
【００６１】
Ｆｉｇ．８は本発明に基づくプロセッサ７１０の内部構成を示す図である。プロセッサ７１０は、例えば１又は複数のメモリ管理部（memory management unit：以下、ＭＭＵという。）８１０と、１又は複数のプロセッサ要素アレイ（processor element arrays）８２０と、１又は複数のアキュムレータ（accumulator unit）８３０とを備える。プロセッサ要素アレイ８２０は、プロセッサ要素（図示せず）のアレイを備える。プロセッサ要素は、例えばブロック間のＳＡＤを算出するための減算及び加算器等から構成される。ＭＭＵ８１０は、プロセッサ要素アレイ８２０におけるデータバッファとして使用される。アキュムレータ８３０は、例えば、プロセッサ要素８２５からの出力データを累算するために用いられる。
【００６２】
本発明の一具体例において、プロセッサ７１０はメモリ７３０に格納されている１又は複数の命令シーケンスを実行する。この命令は、例えば入出力装置７２０を介してコンピュータにより読取可能な媒体からメモリ７３０に読み込まれたものである。メモリ７３０に格納されている命令シーケンスを実行することにより、プロセッサ７１０は、上述した処理を実行する。変形例においては、ソフトウェアプログラムにより実現された命令に代えて、あるいはソフトウェアプログラムにより実現された命令に加えて、ハードウェアにより構成された回路を用いて本発明を実現することもできる。すなわち、本発明の実現形態は、ハードウェア回路及びソフトウェアの特定の組み合わせによって限定されるものではない。
【００６３】
ここで、「コンピュータにより読取可能な媒体」とは、プロセッサ７１０に実行可能な命令を供給するためのあらゆる媒体を意味するものとする。この媒体は、いかなる形式のものであってもよく、例えば不揮発性媒体、揮発性媒体、伝送媒体等が含まれるが、これらに限定されるものではない。不揮発性媒体には、例えば光ディスク又は磁気ディスク等が含まれる。揮発性媒体には、例えばメモリ７３０のようなダイナミックメモリが含まれる。伝送媒体には、システムバス７６０を構成するデータ線を含む、同軸ケーブル、銅線、光ファイバケーブル等が含まれる。さらに、伝送媒体は、例えば無線電波及び赤外線データ通信により生成される音波及び光波であってもよい。
【００６４】
さらに、通常使用されるコンピュータにより読取可能な媒体は、例えば、フロッピーディスク、フレキシブルディスク、ハードディスク、磁気テープ又はその他のあらゆる磁気記録媒体、ＣＤ−ＲＯＭ又はその他のあらゆる光記録媒体、パンチカード、紙テープ、所定パターンの穿孔が設けられたあらゆる物理的記録媒体、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭ、フラッシュＥＰＲＯＭ、その他のあらゆるメモリチップ又はカートリッジ、後述する搬送波、及びコンピュータが読取可能なその他のあらゆる媒体を含む。情報を伝送するための搬送波の例としては、システムバス７６０を介してシステム７０５への、及びシステム７０５からのデジタルデータ及び可能であればプログラムコードを搬送するネットワーク信号が含まれる。本発明に基づき、システム７０５に供給されたプログラムは、供給されると同時にプロセッサ７１０により実行してもよく、及び／又はメモリ７３０に記憶してもよく、又は後に実行するために不揮発性記録媒体に記録してもよい。
【００６５】
本発明の思想及び範囲から逸脱することなく、本発明に基づく上述の手法及びシステムを様々に修正及び変形できることは当業者にとって明らかである。本発明の範囲は、添付の請求の範囲により定義される。
【図面の簡単な説明】
【図１】 Ｆｉｇ．１は、従来のブロック整合法を説明する図である。
【図２】 Ｆｉｇ．２は、本発明に基づく、ブロック整合検索における検索領域の選択処理を説明する図である。
【図３】 Ｆｉｇ．３Ａは、本発明に基づく階層的検索処理の手順を示すフローチャートである。
【図４】 Ｆｉｇ．３Ｂは、Ｆｉｇ．３Ａの続きである。
【図５】 Ｆｉｇ．４Ａは、８×８配列からなる画素情報の垂直統合射影情報の算出を説明する図である。
【図６】 Ｆｉｇ．４Ｂは、８×８配列からなる画素情報の水平統合射影情報の算出を説明する図である。
【図７】 Ｆｉｇ．５は、本発明に基づくブロック整合処理の１処理段階を説明する図である。
【図８】 Ｆｉｇ．６は、本発明に基づくブロック整合処理の１処理段階を説明する図である。
【図９】 Ｆｉｇ．７は、本発明に基づくシステムの構成を示す図である。
【図１０】 Ｆｉｇ．８は、本発明に基づくプロセッサの構成を示す図である。

Claims (32)

1. ビデオ画像データにおける第１及び第２のフレーム間の動きベクトルを生成する動きベクトル判定方法において、
   （ａ）上記第１のフレームにおいて、画素情報の２次元配列として構成される現在のマクロブロックを決定するステップ（３０２）と、
   （ｂ）上記第１のフレームにおいて、上記現在のマクロブロックを含む複数のマクロブロックを有する現在のスーパーマクロブロックを決定するステップ（３０４）と、
   （ｃ）上記現在のスーパーマクロブロックと第１の検索範囲とに基づいて、上記第２のフレームにおける第１の検索領域を選択するステップ（３０６）と、
   （ｄ）現在のスーパーマクロブロックを第１の検索領域に位置する複数の候補スーパーマクロブロックと比較することによって、第１のブロック整合法（３０８，３１０）に基づいて、上記第２のフレームの最良候補スーパーマクロブロックを判定するステップ（３１２）と、
   （ｅ）上記最良候補スーパーマクロブロックを複数の候補マクロブロックに分割するステップ（３１４）と、
   （ｆ）上記第２のフレームにおける複数の第２の検索領域を選択するステップであって、上記複数の第２の探索領域のそれぞれは、複数の候補マクロブロックのうちの一つと第２の検索範囲とに基づくものであり（３１６）、
   （ｇ）現在のマクロブロックを、それぞれが複数の第２の検索領域のうちの一つに位置する選択された複数のマクロブロックと比較することによって、第２のブロック整合法（３１８，３２０）に基づいて、第１の最良候補マクロブロックを判定するステップ（３２２）と、
   （ｈ）上記現在のマクロブロックと上記第１の最良候補マクロブロックとの間の変位ベクトルを表す第１の動きベクトルを判定するステップ（３２８）と、
   を有する動きベクトル判定方法。
2. （ｉ）上記第２のフレームにおいて、上記第１の最良候補マクロブロックと第３の検索範囲とに基づいて、第３の検索範囲を選択するステップ（３２４）と、 （ｊ）現在のマクロブロックを第３の検索領域に位置する選択された複数のマクロブロックと比較することによって、第３のブロック整合法に基づいて、第２の最良候補マクロブロックを判定するステップ（３２４）と、
   （ｋ）上記現在のマクロブロックと上記第２の最良候補マクロブロックとの間の変位ベクトルを表す第２の動きベクトルを判定するステップ（３２８）とを有する請求項１に記載の動きベクトル判定方法。
3. （ｌ）上記第２のフレームにおいて、上記第２の最良候補マクロブロックと第４の検索範囲とに基づいて、第４の検索範囲を選択するステップ（３２６）と、 （ｍ）現在のスーパーマクロブロックを第４の検索領域に位置する選択された複数のマクロブロックと比較することによって、第４のブロック整合法に基づいて、第３の最良候補マクロブロックを判定するステップ（３２６）と、
   （ｎ）上記現在のマクロブロックと上記第３の最良候補マクロブロックとの間の変位ベクトルを表す第３の動きベクトルを判定するステップ（３２８）とを有する請求項２に記載の動きベクトル判定方法。
4. 上記最良候補スーパーマクロブックを判定するステップは、
   （ａ）上記現在のスーパーマクロブロックと上記第１のブロック整合法とに基づいて、各画素情報のストリップにおいて少なくとも１つの候補スーパーマクロブロックを選択することにより、候補スーパーマクロブロックの第１の組を決定するステップと、
   （ｂ）上記現在のスーパーマクロブロックと第１のブロック整合とに基づいて、少なくとも１つの第２の検索領域のそれぞれにおける少なくとも１つの候補スーパーマクロブロックを選択することによって候補スーパーマクロブロックの第２の組を決定するステップであって、上記少なくとも１つの第２の検索領域は候補スーパーマクロブロックの第１の組に基づくものであり、
   （ｃ）上記第１のブロック整合法に基づいて、上記候補スーパーマクロブロックの第２の組から最良候補スーパーマクロブロックを判定するステップとを有することを特徴とする請求項１に記載の動きベクトル判定方法。
5. 上記第１の最良候補マクロブロックを判定するステップは、
   （ａ）上記現在のマクロブロックと上記第２のブロック整合法とに基づいて、各画素情報のストリップにおいて少なくとも１つの候補マクロブロックを選択することにより、候補マクロブロックの第１の組を決定するステップと、
   （ｂ）上記現在のマクロブロックと第２のブロック整合法とに基づいて、少なくとも１つの第２の検索範囲において少なくとも１つの候補マクロブロックを選択することにより候補マクロブロックの第２の組を決定するステップであって、上記第２の検索領域のそれぞれは上記候補マクロブロックの第１の組に基づくものであり、
   （ｃ）第２のブロック整合法に基づいて、上記候補マクロブロックの第２の組から最良候補マクロブロックを判定するステップとを有することを特徴とする請求項１に記載の動きベクトル判定方法。
6. 上記第１のブロック整合法は、現在のスーパーマクロブロックを表す第１の統合射影配列及び上記第１の検索領域に位置する複数の候補スーパーマクロブロックを表す第２の統合射影配列を決定することを含むものであるか、又は、上記第２のブロック整合法は、現在のマクロブロックを表す第３の統合射影配列及び複数の第２の検索領域に位置する選択された複数のマクロブロックを表す複数の第４の統合射影配列を決定することを含むものである、請求項１に記載の動きベクトル判定方法。
7. （ｋ）上記第１の最良候補マクロブロックと第３の検索範囲とに基づいて、第３の検索範囲を選択するステップと、
   （ｌ）現在のマクロブロックを上記第３の検索領域に位置する選択された複数のマクロブロックと比較することによる第３のブロック整合法に基づいて、第２の最良候補マクロブロックを判定するステップと、
   （ｍ）上記現在のマクロブロックと上記第２の最良候補マクロブロックとの間の変位ベクトルを表す第２の動きベクトルを判定するステップ（３２８）とを有する請求項６に記載の動きベクトル判定方法。
8. （ｎ）上記第２のフレームにおいて、上記第２の最良候補マクロブロックと第４の検索範囲とに基づいて、第４の検索範囲を選択するステップと、
   （ｏ）現在のスーパーマクロブロックを第４の検索領域に位置する複数の選択マクロブロックと比較することによって、第４のブロック整合法に基づいて、第３の最良候補マクロブロックを判定するステップと、
   （ｐ）上記現在のマクロブロックと上記第３の最良候補マクロブロックとの間の変位ベクトルを表す第３の動きベクトルを判定するステップとを有する請求項７に記載の動きベクトル判定方法。
9. 上記最良候補スーパーマクロブックを判定するステップは、
   （ａ）上記現在のスーパーマクロブロックを表す統合射影配列と第１のブロック整合法とに基づいて、各画素情報のストリップにおいて少なくとも１つの候補スーパーマクロブロックを選択することにより、候補スーパーマクロブロックの第１の組を決定するステップと、
   （ｂ）上記現在のスーパーマクロブロックを表す統合射影配列と上記第１ブロック整合法とに基づいて、少なくとも１つの第２の検索領域において少なくとも１つの候補マクロブロックを選択することにより候補スーパーマクロブロックの第２の組を決定するステップであって、上記少なくとも１つの第２の検索領域は上記候補スーパーマクロブロックの第１の組に基づくものであり、
   （ｃ）上記第１のブロック整合法に基づいて、上記候補スーパーマクロブロックの第２の組から上記最良候補スーパーマクロブロックを判定するステップとを有することを特徴とする請求項６に記載の動きベクトル判定方法。
10. 上記第１の最良候補マクロブロックを判定するステップは、
    （ａ）上記現在のマクロブロックを表す統合射影情報と第２のブロック整合法とに基づいて、各画素情報のストリップにおいて少なくとも１つの候補マクロブロックを選択することにより、候補マクロブロックの第１の組を決定するステップと、
    （ｂ）上記現在のマクロブロックを表す統合射影情報と上記第２ブロック整合法とに基づいて、少なくとも１つの第２の検索領域において少なくとも１つの候補マクロブロックを選択することにより候補スーパーマクロブロックの第２の組を決定するステップであって、上記少なくとも１つの第２の検索領域は上記候補マクロブロックの第１の組に基づくものであり、
    （ｃ）上記第２のブロック整合法に基づいて、上記候補マクロブロックの第２の組から第１の最良候補マクロブロックを判定するステップとを有することを特徴とする請求項６に記載の動きベクトル判定方法。
11. ビデオ画像データにおける第１及び第２のフレーム間の動きベクトルを生成する動きベクトル判定装置において、
    プログラム命令が格納されたメモリ（７３０）と、
    上記プログラム命令を実行することにより、
    （ａ）上記第１のフレームにおいて、画素情報の２次元配列として構成される現在のマクロブロックを決定するステップと、
    （ｂ）上記第１のフレームにおいて、上記現在のマクロブロックを含む複数のマクロブロックから構成される現在のスーパーマクロブロックを決定するステップと、
    （ｃ）上記現在のスーパーマクロブロックと第１の検索範囲とに基づいて、上記第２のフレームにおける第１の検索領域を選択するステップと、
    （ｄ）現在のスーパーマクロブロックを上記第１の検索領域に位置する複数の候補スーパーマクロブロックと比較することによって、第１のブロック整合法に基づいて、上記第２のフレームの最良候補スーパーマクロブロックを判定するステップと、
    （ｅ）上記最良候補スーパーマクロブロックを複数の候補マクロブロックに分割するステップと、
    （ｆ）上記第２のフレームにおける複数の第２の検索領域を選択するステップであって、上記複数の第２の探索領域は、上記複数の候補マクロブロックのうちの一つと第２の検索範囲とに基づくものであり、
    （ｇ）現在のマクロブロックを、それぞれが複数の第２の検索領域のうちの一つに位置する選択された複数のマクロブロックと比較することによって、第２のブロック整合法に基づいて、第１の最良候補マクロブロックを判定するステップと、
    （ｈ）上記現在のマクロブロックと上記第１の最良候補マクロブロックとの間を変位ベクトルを表す第１の動きベクトルを判定するステップと
    を実行するプロセッサ（７１０）とを備える動きベクトル判定装置。
12. 上記プロセッサは、上記プログラム命令を実行することにより、
    （ｉ）上記第２のフレームにおいて、上記第１の最良候補マクロブロックと第３の検索範囲とに基づいて、第３の検索範囲を選択するステップと、
    （ｊ）現在のマクロブロックを上記第３の検索領域に位置する選択された複数のマクロブロックと比較することによって、第３のブロック整合法に基づいて、第２の最良候補マクロブロックを判定するステップと、
    （ｋ）上記現在のマクロブロックと上記第２の最良候補マクロブロックとの間の変位ベクトルを表す第２の動きベクトルを判定するステップと
    を実行することを特徴とする請求項１１に記載の動きベクトル判定装置。
13. 上記プロセッサは、上記プログラム命令を実行することにより、
    （ｌ）上記第２のフレームにおいて、上記第２の最良候補マクロブロックと第４の検索範囲とに基づいて、第４の検索領域を選択するステップと、
    （ｍ）現在のスーパーマクロブロックを上記第４の検索領域における選択された複数のマクロブロックと比較することによって、第４のブロック整合法に基づいて、第３の最良候補マクロブロックを判定するステップと、
    （ｎ）上記現在のスーパーマクロブロックと上記第３の最良候補マクロブロックとの間の変位ベクトルを表す第３の動きベクトルを判定するステップと
    を実行することを特徴とする請求項１２に記載の動きベクトル判定装置。
14. 上記最良候補スーパーマクロブックを判定するステップは、
    （ａ）上記現在のスーパーマクロブロックと第１のブロック整合法とに基づいて、各画素情報のストリップにおいて少なくとも１つの候補スーパーマクロブロックを選択することにより、候補スーパーマクロブロックの第１の組を決定するステップと、
    （ｂ）上記現在のスーパーマクロブロックと上記第１のブロック整合法とに基づいて、少なくとも１つの第２の検索領域において少なくとも１つの候補スーパーマクロブロックを選択することにより候補スーパーマクロブロックの第２の組を決定するステップであって、上記少なくとも１つの第２の検索領域は上記第１の候補スーパーマクロブロックにもとづくものであり、
    （ｃ）上記第１のブロック整合法に基づいて、上記候補スーパーマクロブロックの第２の組から上記最良候補スーパーマクロブロックを判定するステップとを有することを特徴とする請求項１１に記載の動きベクトル判定装置。
15. 上記第１の最良候補マクロブロックを判定するステップは、
    （ａ）上記現在のマクロブロックと第２のブロック整合法とに基づいて、各画素情報のストリップにおいて少なくとも１つの候補マクロブロックを選択することにより、候補マクロブロックの第１の組を決定するステップと、
    （ｂ）上記現在のマクロブロックと第２のブロック整合法とに基づいて、少なくとも１つの第２の検索領域において少なくとも１つの候補マクロブロックを選択することにより候補マクロブロックの第２の組を決定するステップであって、上記少なくとも１つの第２の検索領域のそれぞれは上記候補マクロブロックの第１の組に基づくものであり、
    （ｃ）上記第２のブロック整合法に基づいて、上記候補マクロブロックの第２の組から第１の最良候補マクロブロックを判定するステップとを有することを特徴とする請求項１１に記載の動きベクトル判定装置。
16. 上記第１の第１のブロック整合法は、現在のスーパーマクロブロックを表す第１の統合射影配列および第１の検索領域に位置する複数の候補スーパーマクロブロックを表す第２の統合射影配列を決定することを含むか、又は、上記第２のブロック整合法は、現在のマクロブロックを表す第３の統合射影配列および第複数の第２の検索領域に位置する選択された複数のマクロブロックを表す複数の第４の統合射影配列を決定することを含むものである、請求項１１に記載の動きベクトル判定装置。
17. 上記プロセッサは、上記プログラム命令を実行することにより、
    （ｋ）上記第２のフレームにおいて、上記第１の最良候補マクロブロックと第３の検索範囲とに基づいて、第３の検索領域を選択するステップと、
    （ｌ）現在のマクロブロックを上記第３の検索領域に位置する選択された複数のマクロブロックと比較することによって、第３のブロック整合法に基づいて、第２の最良候補マクロブロックを判定するステップと、
    （ｍ）上記現在のマクロブロックと上記第２の最良候補マクロブロックとの間の変位ベクトルを表す第２の動きベクトルを判定するステップと
    を実行することを特徴とする請求項１６に記載の動きベクトル判定装置。
18. 上記プロセッサは、上記プログラム命令を実行することにより、
    （ｎ）上記第２のフレームにおいて、上記第２の最良候補マクロブロックと第４の検索範囲とに基づいて、第４の検索領域を選択するステップと、
    （ｏ）現在のスーパーマクロブロックを上記第４の検索領域に位置する選択された複数のマクロブロックと比較することによって、第４のブロック整合法に基づいて、第３の最良候補マクロブロックを判定するステップと、
    （ｐ）上記現在のマクロブロックと上記第３の最良候補マクロブロックとの間の変位ベクトルを表す第３の動きベクトルを判定するステップと
    を実行することを特徴とする請求項１７に記載の動きベクトル判定装置。
19. 上記最良候補スーパーマクロブックを判定するステップは、
    （ａ）上記現在のスーパーマクロブロックを表す統合射影配列と第１のブロック整合法とに基づいて、各画素情報のストリップにおいて少なくとも１つの候補スーパーマクロブロックを選択することにより、候補スーパーマクロブロックの第１の組を決定するステップと、
    （ｂ）上記現在のスーパーマクロブロックを表す統合射影配列と第１のブロック整合法とに基づいて、少なくとも１つの第２の検索領域のそれぞれにおいて少なくとも１つの候補スーパーマクロブロックを選択することにより候補スーパーマクロブロックの第２の組を決定するステップであって、上記少なくとも１つの第２の検索領域は候補スーパーマクロブロックの第１の組に基づくものであり、
    （ｃ）第１のブロック整合法に基づいて、上記第２の候補スーパーマクロブロックの組から最良候補スーパーマクロブロックを判定するステップとを有することを特徴とする請求項１６に記載の動きベクトル判定装置。
20. 上記第１の最良候補マクロブロックを判定するステップは、
    （ａ）上記現在のマクロブロックを表す統合射影情報と第２のブロック整合法とに基づいて、各画素情報のストリップにおいて少なくとも１つの候補マクロブロックを選択することにより、候補マクロブロックの第１の組を決定するステップと、
    （ｂ）上記現在のマクロブロックを表す統合射影情報と第２のブロック整合法とに基づいて、少なくとも１つの第２の検索領域において少なくとも１つの候補マクロブロックを選択することにより候補マクロブロック第２の組を決定するステップであって、上記少なくとも１つの第２の検索領域は上記候補マクロブロックの第１の組に基づくものであり、 （ｃ）第２のブロック整合法に基づいて、上記候補マクロブロックの第２の組から第１の最良候補マクロブロックを判定するステップとを有することを特徴とする請求項１６に記載の動きベクトル判定装置。
21. ビデオ画像データにおける第１及び第２のフレーム間の動きベクトルを生成するコンピュータにより読取可能なコードが記録されたな記録媒体において、
    上記コンピュータにより読取可能なコードは、
    （ａ）上記第１のフレームにおいて、画素情報の２次元配列として構成される現在のマクロブロックを決定する手順と、
    （ｂ）上記第１のフレームにおいて、上記現在のマクロブロックを含むと複数のマクロブロックから構成される現在のスーパーマクロブロックを決定する手順と、
    （ｃ）上記現在のスーパーマクロブロックと第１の検索範囲とに基づいて、上記第２のフレームにおける第１の検索領域を選択する手順と、
    （ｄ）現在のスーパーマクロブロックを上記第１の検索領域に位置する複数の候補スーパーマクロブロックと比較することによって、第１のブロック整合法に基づいて、第２のフレームにおける最良候補スーパーマクロブロックを判定する手順と、
    （ｅ）上記最良候補スーパーマクロブロックを複数の候補マクロブロックに分割する手順と、
    （ｆ）上記第２のフレームにおける複数の第２の検索領域を選択する手順であって、上記複数の第２の探索領域のそれぞれは、上記複数の候補マクロブロックのうちの一つと第２の検索範囲とに基づくものであり、
    （ｇ）現在のマクロブロックを、それぞれが複数の第２検索領域のうちの一つに位置する選択された複数のマクロブロックと比較することによって、第２のブロック整合法に基づいて、第１の最良候補マクロブロックを判定する手順と、
    （ｈ）上記現在のマクロブロックと上記第１の最良候補マクロブロックとの間の変位ベクトルを表す第１の動きベクトルを判定する手順と
    をコンピュータにより実行させるものである、コンピュータ読み取り可能な記録媒体。
22. 上記コードには、
    （ｉ）上記第２のフレームにおいて、上記第１の最良候補マクロブロックと第３の検索範囲とに基づいて、第３の検索領域を選択する手順と、
    （ｊ）現在のマクロブロックを上記第３の検索領に位置する選択された複数のマクロブロックと比較することによって、第３のブロック整合法に基づいて、第２の最良候補マクロブロックを判定する手順と、
    （ｋ）上記現在のマクロブロックと上記第２の最良候補マクロブロックとの間の変位ベクトルを表す第２の動きベクトルを判定する手順とが含まれる、請求項２１に記載のコンピュータ読み取り可能な記録媒体。
23. 上記コードには、
    （ｌ）上記第２のフレームにおいて、上記第２の最良候補マクロブロックと第４の検索範囲とに基づいて、第４の検索領域を選択する手順と、
    （ｍ）現在のスーパーマクロブロックを第４の検索領域に位置する選択された複数のマクロブロックと比較することによって、第４のブロック整合法に基づいて、第３の最良候補マクロブロックを判定する手順と、
    （ｎ）上記現在のマクロブロックと上記第３の最良候補マクロブロックとの間の変位ベクトルを表す第３の動きベクトルを判定する手順が含まれる、請求項２２に記載のコンピュータ読み取り可能な記録媒体。
24. 上記最良候補スーパーマクロブックを判定する手順は、
    （ａ）上記現在のスーパーマクロブロックと第１ブロック整合法とに基づいて、各画素情報のストリップにおいて少なくとも１つの候補スーパーマクロブロックを選択することにより、候補スーパーマクロブロックの第１の組を決定するステップと、
    （ｂ）上記現在のスーパーマクロブロックと第１のブロック整合法とに基づいて、少なくとも１つの第２の検索領域において少なくとも１つの候補スーパーマクロブロックを選択することにより候補スーパーマクロブロックの第２の組を決定する手順であって、上記少なくとも１つの第２の検索領域のそれぞれは候補スーパーマクロブロックの第１の組に基づくものであり、
    （ｃ）第１のブロック整合法に基づいて、上記候補スーパーマクロブロックの第２の組から最良候補スーパーマクロブロックを判定するステップとを備えることを特徴とする請求項２１に記載のコンピュータ読み取り可能な記録媒体。
25. 上記第１の最良候補マクロブロックを判定する手順は、
    （ａ）上記現在のマクロブロックと第２のブロック整合法とに基づいて、各画素情報のストリップにおいて少なくとも１つの候補マクロブロックを選択することにより、候補マクロブロックの第１の組を決定するステップと、
    （ｂ）上記現在のマクロブロックと第２のブロック整合法とに基づいて、少なくとも１つの第２の検索領域のそれぞれにおいて少なくとも１つの候補マクロブロックを選択することにより候補マクロブロックの第２の組を決定するステップであって、上記少なくとも１つの第２の検索領域は上記候補マクロブロックの第１の組に基づくもであり、
    （ｃ）第２のブロック整合法に基づいて、上記第２の候補マクロブロックの第２の組から最良候補マクロブロックを判定するステップとを有することを特徴とする請求項２１に記載のコンピュータ読み取り可能な記録媒体。
26. 上記第１の第１のブロック整合法は、現在のスーパーマクロブロックを表す第１の統合射影配列および第１の検索領域に位置する複数の候補スーパーマクロブロックを表す第２の統合射影配列を決定することを含むか、又は、上記第２のブロック整合法は、現在のマクロブロックを表す第３の統合射影配列および第複数の第２の検索領域に位置する選択された複数のマクロブロックを表す複数の第４の統合射影配列を決定することを含むものである、請求項２１に記載のコンピュータ読み取り可能な記録媒体。
27. 上記コードには、
    （ｋ）上記第２のフレームにおいて、上記第１の最良候補マクロブロックと第３の検索範囲とに基づいて、第３の検索領域を選択する手順と、
    （ｌ）現在のマクロブロックを上記第３の検索領域に位置する選択された複数のマクロブロッと比較することによって、第３のブロック整合法に基づいて、第２の最良候補マクロブロックを判定する手順と、
    （ｍ）上記現在のマクロブロックと上記第２の最良候補マクロブロックとの間の変位ベクトルを表す第２の動きベクトルを判定する手順とが含まれる請求項２６に記載のコンピュータ読み取り可能な記録媒体。
28. 上記コードには、
    （ｎ）上記第２のフレームにおいて、上記第２の最良候補マクロブロックと第４の検索範囲とに基づいて、第４の検索領域を選択する手順と、
    （ｏ）現在のスーパーマクロブロックを上記第４の検索領域に位置する選択された複数のマクロブロックと比較することによって、第４のブロック整合法に基づいて、第３の最良候補マクロブロックを判定する手順と、
    （ｐ）上記現在のマクロブロックと上記第３の最良候補マクロブロックとの間の変位ベクトルを表す第３の動きベクトルを判定する手順とが含まれる、請求項２７に記載のコンピュータ読み取り可能な記録媒体。
29. 上記最良候補スーパーマクロブックを判定する手順には、
    （ａ）上記現在のスーパーマクロブロックを表す統合射影配列と第１のブロック整合法とに基づいて、各画素情報のストリップにおいて少なくとも１つの候補スーパーマクロブロックを選択することにより、候補スーパーマクロブロックの第１の組を決定するステップと、
    （ｂ）上記現在のスーパーマクロブロックを表す統合射影配列と第１のブロック整合法とに基づいて、少なくとも１つの第２の検索領域のそれぞれにおいて少なくとも１つの候補スーパーマクロブロックを選択することにより候補スーパーマクロブロックの第２の組を決定するステップであって、上記少なくとも１つの第２の検索領域は候補スーパーマクロブロックの第１の組に基づくものであり、
    （ｃ）第１のブロック整合法に基づいて、上記候補スーパーマクロブロックの第２の組から最良候補スーパーマクロブロックを判定する手順とが含まれる、請求項２６に記載のコンピュータ読み取り可能な記録媒体。
30. 上記第１の最良候補マクロブロックを判定する手順には、
    （ａ）上記現在のマクロブロックを表す統合射影情報と第２のブロック整合法とに基づいて、各画素情報のストリップにおいて少なくとも１つの候補マクロブロックを選択することにより、候補マクロブロックの第１の組を決定するステップと、
    （ｂ）上記現在のマクロブロックを表す統合射影情報と第２のブロック整合法とに基づいて、少なくとも１つの第２の検索領域のそれぞれにおいて少なくとも１つの候補マクロブロックを選択することにより候補マクロブロックの第２の組を決定するステップであって、上記少なくとも１つの第２の検索領域は上記候補マクロブロックの第１の組に基づくものであり、
    （ｃ）第２のブロック整合法に基づいて、上記候補マクロブロックの第２の組から第１の最良候補マクロブロックを判定するステップが含まれる、請求項２６に記載のコンピュータ読み取り可能な記録媒体。
31. ビデオ画像データにおける第１及び第２のフレーム間の動きベクトルを生成する動きベクトル判定システムにおいて、
    （ａ）上記第１のフレームにおいて、画素情報の２次元配列として構成される現在のマクロブロックを決定する現在マクロブロック決定手段と、
    （ｂ）上記第１のフレームにおいて、上記現在のマクロブロックを含む複数のマクロブロックから構成される現在のスーパーマクロブロックを決定する現在スーパーマクロブロック決定手段と、
    （ｃ）上記現在のスーパーマクロブロックと第１の検索範囲とに基づいて、上記第２のフレームにおける第１の検索領域を選択する第１検索領域選択手段と、
    （ｄ）現在のスーパーマクロブロックを上記第１の検索領域に位置する複数の候補スーパーマクロブロックと比較することによって、第１のブロック整合法に基づいて、第２のフレームにおける最良候補スーパーマクロブロックを判定する最良候補スーパーマクロブロック判定手段と、
    （ｅ）上記最良候補スーパーマクロブロックを複数の候補マクロブロックに分割する分割手段と、
    （ｆ）上記第２のフレームにおける複数の第２の検索領域を選択する第２検索領域選択手段であって、上記複数の第２の検索領域は上記複数の候補マクロブロックのうちの一つと第２の検索範囲とに基づくものであり、
    （ｇ）現在のマクロブロックを、それぞれが複数の第２の検索領域のうちの一つに位置する選択された複数のマクロブロックと比較することによって、第２のブロック整合法に基づいて、第１の最良候補マクロブロックを判定するステップ最良候補マクロブロック判定手段と、
    （ｈ）上記現在のマクロブロックと上記第１の最良候補マクロブロックとの間の変位ベクトルを表す第１の動きベクトルを判定する第１動きベクトル判定手段とを備える動きベクトル判定システム。
32. 上記第１の第１のブロック整合法は、現在のスーパーマクロブロックを表す第１の統合射影配列および第１の検索領域に位置する複数の候補スーパーマクロブロックを表す第２の統合射影配列を決定することを含むか、又は、上記第２のブロック整合法は、現在のマクロブロックを表す第３の統合射影配列および第複数の第２の検索領域に位置する選択された複数のマクロブロックを表す複数の第４の統合射影配列を決定することを含むものである、請求項３１に記載の動きベクトル判定システム。

Images