(57)【特許請求の範囲】
【請求項１】
１つまたは複数の目標ブロックを含む目標フレームと探索フレームとの間で動き予測を実行する方法であって、
目標フレーム内の１つまたは複数の目標ブロック上で周波数領域変換を実行し、
探索フレームから候補ブロックを選択し、ここで、選択された候補ブロックが前記目標ブロックの行境界または列境界に位置しないものであり、
探索フレームから選択された候補ブロック上で周波数領域変換を実行し、
前記選択された候補ブロックに応じて、目標フレーム内で１つまたは複数の目標ブロックを決定し、ここで、該決定が、選択された候補ブロックを含む対応する探索ウィンドウを有する１つまたは複数の目標ブロックを目標フレーム内で決定することと、目標フレーム内で第１の数の隣接目標ブロックを決定することとを含むものであり、さらにここで、決定された該第１の数の隣接目標ブロックの各々が、選択された候補ブロックを含む対応する探索ウィンドウを有するものであり、
前記１つまたは複数の決定された目標ブロックごとに、前記選択された候補ブロックの変換値と前記１つまたは複数の決定された目標ブロックの各々の変換値との間の距離を計算し、
前記計算された距離が、前記１つまたは複数の決定された目標ブロックの各々についてすでに計算され記憶されている計量値よりも良好な計量値であるかどうかを決定し、
前記目標ブロックの各々のために計算された距離が、その目標ブロックのために計算されたそれまでの距離の最良値よりも良好な計量値であるとき、その目標ブロックのために前記選択された候補ブロックの位置を記憶し、
探索フレームから候補ブロックを選択する前記の選択と、探索フレームから選択された候補ブロック上で周波数領域変換を実行する前記の実行と、目標フレーム内で１つまたは複数の目標ブロックを決定する前記の決定と、距離を計算する前記の計算と、前記計算された距離がより良好な計量値であるかどうかを決定する前記の決定と、前記選択された候補ブロックの位置を記憶する前記の記憶とが、前記探索フレーム内の複数の候補ブロックについて実行され、この実行によって前記目標フレーム内の複数の目標ブロックのために動きベクトルが生成されるようにした、動き予測実行方法。
【請求項２】
前記選択された候補ブロックが前記目標ブロックの行境界および列境界の双方に位置しており、目標フレーム内で１つまたは複数の目標ブロックを決定する前記の決定が、目標フレーム内で第２の数の隣接目標ブロックを決定することを含み、前記決定された第２の数の隣接目標ブロックの各々が、選択された候補ブロックを含む対応する探索ウィンドウを有し、前記第２の数は前記第１の数よりも大きい、請求項１に記載の動き予測実行方法。
【請求項３】
前記選択された候補ブロックが少なくとも１つの前記目標ブロックの行境界または列境界の１つに位置し、目標フレーム内で１つまたは複数の目標ブロックを決定する前記の決定が、目標フレーム内で第３の数の隣接目標ブロックを決定することを含み、前記決定された第３の数の隣接目標ブロックの各々が、選択された候補ブロックを含む対応する探索ウィンドウを有し、前記探索ウィンドウが正方形であり、前記第３の数は前記第１の数よりも大きく前記第２の数よりも小さい、請求項２に記載の動き予測実行方法。
【請求項４】
選択された候補ブロックの変換値と前記１つまたは複数の決定された目標ブロックの各々の変換値との間で距離を計算する前記の計算が、選択された候補ブロックの変換値を前記１つまたは複数の決定された目標ブロックの各々の変換値から減算して、前記１つまたは複数の決定された目標ブロックの各々のためにマトリクスを生成することと、前記１つまたは複数の決定された目標ブロックの各々のためにゼロへ量子化される前記マトリクス内の値の数を決定することとを含む、請求項１に記載の動き予測実行方法。
【請求項５】
選択された候補ブロックの変換値と前記１つまたは複数の決定された目標ブロックの変換値との間の距離を計算する前記の計算が、選択された候補ブロックの変換値を前記１つまたは複数の決定された目標ブロックの各々の変換値から減算して、前記１つまたは複数の決定された目標ブロックの各々のためにマトリクスを生成することと、
前記１つまたは複数の決定された目標ブロックの各々のために前記マトリクスを量子化することと、前記１つまたは複数の決定された目標ブロックの各々のための前記量子化されたマトリクスの各々を複数のビットへ符号化することと、前記符号化されたマトリクスのどれが最少数のビットを有するかを決定することとを含む、請求項１に記載の動き予測実行方法。
【請求項６】
前記計算された距離が前記目標ブロックのために計算されたそれまでの距離の最良値よりも良好な計量値であるとき、前記目標ブロックのために前記計算された距離を記憶する、請求項１に記載の動き予測実行方法。
【請求項７】
周波数領域変換を実行する前記の実行が離散コサイン変換（ＤＣＴ）を実行することを含む、請求項１に記載の動き予測実行方法。
【請求項８】
探索フレームから候補ブロックを選択する前記の選択、探索フレームから選択された候補ブロック上に周波数領域変換を実行する前記の実行、目標フレーム内で１つまたは複数の目標ブロックを決定する前記の決定、距離を計算する前記の計算、前記計算された距離がより良好な計量値であるかどうかを決定する前記の決定、および前記選択された候補ブロックの位置を記憶する前記の記憶が、前記探索フレーム内のすべての候補ブロックについて実行され、この実行によって前記目標フレーム内の前記目標ブロックの各々のために動きベクトルが生成される、請求項１に記載の動き予測実行方法。
【請求項９】
前記目標フレームおよび前記探索フレームがＭＰＥＧストリーム中に含まれる、請求項１に記載の動き予測実行方法。
【請求項１０】
探索フレームから選択された候補ブロック上で周波数領域変換を実行する前記の実行の後で、選択された候補ブロックの前記変換値の少なくとも一部を記憶し、探索フレームから候補ブロックを選択する前記の選択が、前に選択された候補ブロックの前記変換値の前記少なくとも一部を再使用する候補ブロックを選択することを含む、請求項１に記載の動き予測実行方法。
【請求項１１】
探索フレームから選択された候補ブロック上で周波数領域変換を実行する前記の実行が、選択された候補ブロックを複数のサブブロックに区分することと、前記複数のサブブロックの各々の上で周波数領域変換を実行することとを含み、選択された候補ブロックの前記変換値の少なくとも一部を記憶する前記の記憶が、前記サブブロックの１つまたは複数の変換値を記憶することを含み、探索フレームから候補ブロックを選択する前記の選択が、前記サブブロックの前記１つまたは複数の前記記憶された変換値を再使用する候補ブロックを選択することを含む、請求項１０に記載の動き予測実行方法。
【請求項１２】
前記探索フレームが複数の水平方向バンドを含み、前記水平方向バンドの各々の垂直方向長さは前記候補ブロックの垂直方向長さと等しく、前記水平方向バンドの各々は第１の部分と第２の部分とを含み、前記探索フレームは複数の垂直方向ストリップを含み、前記垂直方向ストリップの各々の水平方向幅は前記候補ブロックの水平方向幅と等しく、探索フレームから候補ブロックを選択する前記の選択が、各垂直方向ストリップについて、前の水平方向バンドの前記第２の部分を再使用する水平方向バンドを垂直ストリップ内で選択することを含む、請求項１１に記載の動き予測実行方法。
【請求項１３】
前記探索フレームが複数の水平方向バンドを含み、前記水平方向バンドの各々の垂直方向長さは前記候補ブロックの長さと等しく、前記水平方向バンドの各々は１つまたは複数の上部サブブロックより成る上部部分と、１つまたは複数の下部サブブロックより成る下部部分とを含み、前記探索フレームは複数の垂直方向ストリップを含み、前記垂直方向ストリップの各々の水平方向幅は前記候補ブロックの水平方向幅と等しく、各垂直方向ストリップについて、探索フレームから候補ブロックを選択する前記の選択が、前の水平方向バンドの下部サブブロックを含む下部部分を再使用する水平方向バンドを垂直方向ストリップ内で選択することを含み、この選択は垂直方向ストリップ内の複数の水平方向バンドのために複数回実行され、前の水平方向バンドの下部部分を再使用する水平方向バンドを垂直方向ストリップ内で選択する前記の選択は、前記探索フレーム内のすべての候補ブロックを選択するために前記垂直方向ストリップの各々について複数回実行される、請求項１２に記載の動き予測実行方法。
【請求項１４】
垂直方向ストリップから選択された候補ブロックの前記変換値の少なくとも一部を記憶し、探索フレームから候補ブロックを選択する前記の選択が、前の垂直方向ストリップから選択された前記候補ブロックの前記変換値の少なくとも一部を再使用させる新しい垂直方向ストリップを選択することを含む、請求項１２に記載の動き予測実行方法。
【請求項１５】
前記候補ブロックが複数の列と複数のサブブロックを含み、探索フレームから選択された候補ブロック上で周波数領域変換を実行する前記の実行が、前記選択された候補ブロックの前記複数の列の各々の上で周波数領域変換を実行することを含み、選択された候補ブロックの前記変換値の少なくとも一部を記憶する前記の記憶が、１つまたは複数の前記列の変換値を記憶することを含み、探索フレームから候補ブロックを選択する前記の選択が、前記１つまたは複数の前記列の前記記憶された変換値を再使用する候補ブロックを選択することを含む、請求項１０に記載の動き予測実行方法。
【請求項１６】
前記探索フレームが複数の水平方向バンドを含み、さらに、前記探索フレームが複数の垂直方向ストリップを含み、前記垂直方向ストリップの各々は複数の列を含み、探索フレームから候補ブロックを選択する前記の選択が、前に選択された垂直方向ストリップの計算された列を再使用する垂直方向ストリップを選択することと、各垂直方向ストリップについて、垂直ストリップ内の水平方向バンドを選択することとを含む、請求項１５に記載の動き予測実行方法。
【請求項１７】
垂直方向ストリップ内で水平方向バンドを選択する前記の選択が、各垂直方向ストリップについて、前の水平方向バンドの計算された部分を再使用する水平方向バンドを垂直方向ストリップ内で選択することを含む、請求項１６に記載の動き予測実行方法。
【請求項１８】
１つまたは複数の目標ブロックを含む目標フレームと探索フレームとの間で動き予測を実行するＭＰＥＧエンコーダであって、
目標フレーム内の１つまたは複数の目標ブロック上で周波数領域変換を実行するＤＣＴ変換ブロックと、
探索フレームから候補ブロックを選択し、選択された候補ブロック上で前記ＤＣＴブロックが周波数領域変換を実行するようにする手段と、
前記選択された候補ブロックに応じて、目標フレーム内で１つまたは複数の目標ブロックを決定する手段であって、選択された候補ブロックを含む対応する探索ウィンドウを有する１つまたは複数の目標ブロックを目標フレーム内で決定する手段と、
前記１つまたは複数の決定された目標ブロックの各々のために、選択された候補ブロックの変換値と前記１つまたは複数の決定された目標ブロックの各々の変換値との間の距離を計算する手段と、
前記計算された距離が、前記１つまたは複数の決定された目標ブロックの各々のためにそれまで計算されて記憶されている距離よりも良好な計量値であるかどうかを決定する手段と、
前記目標ブロックのために計算された前記距離が、その目標ブロックのためにそれまで計算された最良の距離よりも良好な計量値であるとき、その目標ブロックのために前記選択された候補ブロックの位置を記憶するメモリとを備え、
探索フレームから候補ブロックを選択する前記手段と、探索フレームから選択された候補ブロック上で周波数領域変換を実行する前記ＤＣＴブロックと、目標フレーム内で１つまたは複数の目標ブロックを決定する前記手段と、距離を計算する前記手段と、前記計算された距離がより良好な計量値であるかどうかを決定する前記手段と、前記選択された候補ブロックの位置を記憶する前記メモリとが、前記探索フレーム内の複数の候補ブロックのために動作し、よって前記目標フレーム内の複数の前記目標ブロックのために動きベクトルを生成する、ＭＰＥＧエンコーダ。
【請求項１９】
選択された候補ブロックの変換値と前記１つまたは複数の決定された目標ブロックの各々の変換値との間の距離を計算する前記手段が、選択された候補ブロックの変換値を前記１つまたは複数の決定された目標ブロックの各々の変換値から減算して、前記１つまたは複数の決定された目標ブロックの各々のためにマトリクスを生成する減算器と、前記１つまたは複数の決定された目標ブロックの各々のためにゼロへ量子化される前記マトリクス内の値の数を決定する手段とを具備する、請求項１８に記載のＭＰＥＧエンコーダ。
【請求項２０】
選択された候補ブロックの変換値と前記１つまたは複数の決定された目標ブロックの各々の変換値との間の距離を計算する前記手段が、選択された候補ブロックの変換値を前記１つまたは複数の決定された目標ブロックの各々の変換値から減算し、前記１つまたは複数の決定された目標ブロックの各々のためにマトリクスを生成する減算器と、前記１つまたは複数の決定された目標ブロックの各々のための前記マトリクスを量子化する量子化器と、前記１つまたは複数の決定された目標ブロックの各々のための前記量子化されたマトリクスの各々を複数のビットへ符号化する符号化器と、前記符号化されたマトリクスのどれが最少数のビットを有するかを決定する手段とを具備する、請求項１８に記載のＭＰＥＧエンコーダ。
【請求項２１】
前記計算された距離が、前記目標ブロックのためにそれまで計算された最良の距離よりも良好な計量値であるとき、前記目標ブロックのために前記計算された距離を記憶するメモリを備える、請求項１８に記載のＭＰＥＧエンコーダ。
【請求項２２】
選択された候補ブロックの前記変換値の少なくとも一部を記憶するメモリを備え、探索フレームから候補ブロックを選択する前記手段が、前に選択された候補ブロックの前記変換値の前記少なくとも一部を再使用する候補ブロックを選択する、請求項１８に記載のＭＰＥＧエンコーダ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般的にはディジタル・ビデオ圧縮に関し、具体的には、離散コサイン変換(discrete cosine transform: ＤＣＴ) 領域でビデオ・フレーム間の動き予測ベクトル(motion estimation vectors) を計算するとき、探索フレーム(search frame)内の候補ブロック(candidate block) の観点からＤＣＴ領域でブロック比較を実行し、演算量が軽減され、パフォーマンスが改善されるようにうまく候補ブロックを選択するシステムに関する。
【０００２】
【従来の技術】
引用することによる本明細書への組み込み
次の参考文献が引用することにより本明細書にの一部をなすものとする。
ＩＳＯ／ＩＥＣ  １３８１８と呼ばれるＩＳＯ／ＩＥＣ  ＭＰＥＧ仕様の全体が、引用することにより組み込まれる。
【０００３】
関連技術の説明
フル動画用ディジタル・ビデオは、大量の記憶域とデータ伝送帯域幅を必要とする。したがって、ビデオ・システムは各種のビデオ圧縮アルゴリズムを使用して、記憶域と伝送帯域幅の所要量を減少させる。一般的に、静止グラフィック画像と動画用ビデオでは、異なったビデオ圧縮方法が使用される。フレーム内圧縮方法は、フレーム内の空間冗長度を使用して静止画像または単一フレーム内のデータを圧縮するために使用される。フレーム間圧縮方法は、フレーム間の時間的冗長度を利用して複数のフレーム（すなわち、動画ビデオ）を圧縮するために使用される。フレーム間圧縮方法は、単独で、またはフレーム内圧縮方法と組み合わせて、動画ビデオのみに使用される。
【０００４】
フレーム内圧縮または静止画像圧縮の技術は、一般的に離散コサイン変換（ＤＣＴ）のような周波数領域技術を使用する。フレーム内圧縮は、典型的にピクチャ・フレームの周波数特性を使用して、フレームを効率的に符号化し空間冗長度を除去する。静止グラフィック画像用のビデオ・データ圧縮の例は、ＪＰＥＧ(Joint Photographic Experts Group)圧縮とＲＬＥ(run-length encoding) である。ＪＰＥＧ圧縮は、離散コサイン変換（ＤＣＴ）を使用する関連したいくつかの標準規格のグループで、可逆（画像品質の低下がない）または非可逆（重大な低下を認識しない）圧縮のいずれかを提供する。元来、ＪＰＥＧ圧縮はビデオではなく静止画像を圧縮するためにデザインされたものであるが、ある種の動画ビデオ・アプリケーションでＪＰＥＧが使用される。ＲＬＥ圧縮方法は、ビット・マップの単一行にある重複画素をテストし、画素データそのものではなく連続した重複画素の数を記憶する方法である。
【０００５】
静止画像の圧縮アルゴルズムとは異なり、大部分のビデオ圧縮アルゴリズムは動画ビデオを圧縮するようにデザインされている。前述したように、動画ビデオ用のビデオ圧縮アルゴリズムはフレーム間圧縮と呼ばれる概念を使用して、フレーム間の時間的冗長度を除去する。フレーム間圧縮はデータ・ファイル中の連続したフレーム間の差分のみを記憶する。フレーム間圧縮は、キー・フレームまたは参照フレームの全体の画像を、一般的に中程度の圧縮形式で記憶する。連続したフレームはキー・フレームと比較され、キー・フレームと連続フレームとの差分のみが記憶される。定期的に、たとえば新しいシーンが表示されるとき、新しいキー・フレームが記憶され、この新しい参照ポイントから、後続する比較が開始される。注意すべきは、フレーム間圧縮率を一定に保つと、ビデオ品質が変わることである。他方、フレーム間圧縮率は内容に依存する。すなわち、圧縮されているビデオ・クリップの中に、１つの画像から他の画像へ突然に変わるようなシーン・チェンジが何回も出てくる場合、圧縮の効率は悪くなる。フレーム間圧縮技術を使用するビデオ圧縮の例は、ＭＰＥＧ、ＤＶＩ、およびＩｎｄｅｏである。
【０００６】
ＭＰＥＧの背景
ＭＰＥＧ(Moving Pictures Experts Group) 圧縮と呼ばれる圧縮標準は、前述したフレーム間およびフレーム内圧縮技術を使用する動画ビデオ画像の圧縮・伸張の方法である。ＭＰＥＧ圧縮は動き補償と離散コサイン変換（ＤＣＴ）処理を使用し、２００：１を超える圧縮率を達成することができる。
【０００７】
２つの重要なＭＰＥＧ標準は、ＭＰＥＧ−１とＭＰＥＧ−２である。ＭＰＥＧ−１標準はブロック・ベースの動き補償予測(motion compensation prediction:ＭＣＰ) を使用するフィールド間データ削減に関するものである。ＭＣＰは時間的な差動パルス符号変調(differential pulse code modulation:ＤＰＣＭ) を使用する。ＭＰＥＧ−２標準はＭＰＥＧ−１標準と類似しているが、広いアプリケーションをカバーするように拡張され、高精細テレビ（ＨＤＴＶ）のようなインタレース・ディジタル・ビデオも対象となっている。
【０００８】
ＭＰＥＧのようなフレーム間圧縮方法は、大部分のビデオ・シーケンスで背景が比較的一定に保たれるのに対して、前景ではアクションが起こるという事実に基礎をもっている。背景が動く場合でも、連続したフレームの大部分はビデオ・シーケンス内で冗長性をもっている。ＭＰＥＧ圧縮はこの内在的な冗長性を使用して、シーケンス中のフレームを符号化すなわち圧縮する。
【０００９】
ＭＰＥＧストリームは、イントラ（Ｉ）フレーム (Intra frame)、予測（Ｐ）フレーム (Predicted frame)、および双方向内挿（Ｂ）フレーム(Bi-directional Interporated frame) と呼ばれる３種のピクチャを含む。Ｉフレームすなわちイントラフレームは、ビデオの全フレーム用のビデオ・データを含み、典型的には１０から１５フレームごとに配置される。Ｉフレームはファイルへランダムにアクセスするエントリ・ポイントを提供し、一般的に中程度に圧縮される。予測すなわちＰフレームは、過去のフレーム（すなわち、先行するＩまたはＰフレーム）を参照して符号化される。したがって、Ｐフレームは先行するＩまたはＰフレームに対する変更のみを含む。一般的に、Ｐフレームはかなり大きく圧縮され、将来の予測フレームの参照として使用される。したがって、ＩおよびＰフレームは後続フレームの参照として使用される。双方向内挿すなわちＢフレームは最大限に圧縮されており、その符号化には過去および将来の参照を必要とする。Ｂフレームは、決して他のフレームの参照としては使用されない。
【００１０】
一般的に、参照用フレームに続くフレーム（すなわち、参照用のＩまたはＰフレームに続くＰおよびＢフレーム）では、その小部分のみが参照用フレームの対応部分と異なっている。したがって、それらのフレームでは、差分のみが捕捉、圧縮、記憶される。それらフレームの差分は、典型的には、後述するような動きベクトル予測ロジックを使用して生成される。
【００１１】
ＭＰＥＧエンコーダがビデオ・ファイルまたはビットストリームを受け取ると、それは一般的にまずＩフレームを作成する。ＭＰＥＧエンコーダはフレーム内可逆圧縮技術を使用してフレームを圧縮することができる。Ｉフレームが圧縮された後、ＭＰＥＧエンコーダは各フレームをマクロブロックと呼ばれる１６ｘ１６画素より成る正方形格子に分割する。それぞれのフレームは動き予測／補償を実行するためにマクロブロックへ分割される。エンコーダは、目標ピクチャ(target picture)または目標フレーム(target frame)（符号化処理を受けているフレーム）のために、目標ピクチャのマクロブロックと、隣接ピクチャ（探索フレーム(search frame)とも呼ばれる）のブロックとの間の最良マッチを探索する。エンコーダは、Ｐの目標フレームについては、先行するＩまたはＰフレームの中を探索する。Ｂの目標フレームについては、エンコーダは先行または後続するＩまたはＰフレームの中を探索する。最良マッチが発見されると、エンコーダはベクトル運動コードすなわち動きベクトルを生成する。ベクトル運動コードすなわち動きベクトルは、最良マッチの探索フレーム・ブロックに対するポインタと、最良マッチ・ブロックとそれぞれの目標ブロック(target block)との間の差分情報を含んでいる。参照フレームすなわち探索フレーム中のブロックに対して、目標ピクチャ内のブロックが変化していない場合、そのブロックは無視される。したがって、それらのフレームのために実際に記憶されるデータ量は著しく削減される。
【００１２】
動きベクトルを生成した後、さらにエンコーダは空間冗長性を使用して変化を符号化する。対応するマクロブロックの位置に変化を発見すると、ＭＰＥＧアルゴルズムは、マクロブロック間の差分を計算し符号化する。差分の符号化は離散コサイン変換（ＤＣＴ）と呼ばれる数学処理により行われる。この処理はマクロブロックを４つのサブブロックへ分割し、色と明るさの変化を見つける。人間の認識能力は色の変化よりも明るさの変化に対して鋭敏である。したがって、ＭＰＥＧアルゴリズムは、明るさの空間よりも色の空間を減らすように努めている。
【００１３】
したがって、ＭＰＥＧ圧縮はビデオ・シーケンスの２種類の冗長性に基礎を置いている。すなわち、個々のフレーム内の冗長性である空間冗長性と、連続したフレーム間の冗長性である時間冗長性である。空間圧縮はピクチャ・フレームの周波数特性を考慮することによって達成される。各フレームは、重複しないブロックおよびサブブロックへ分割され、各ブロックは離散コサイン変換（ＤＣＴ）を介して変換される。変換されるブロックが「ＤＣＴ領域」へ変換された後、変換されたブロック内の各エントリが、量子化テーブルに関連づけて量子化される。周波数に対する人間の視覚システム（ＨＶＳ）の感性を考慮すると、各エントリの量子化ステップを変えることができる。ＨＶＳは高域周波数よりも低域周波数に鋭敏であるから、高域周波数エントリの大部分はゼロへ量子化される。エントリを量子化するこのステップで情報が失われ、再構成された画像に誤差が導入される。ゼロ・ラン・レングス符号化は、量子化された値を伝送するために使用される。さらに圧縮を達成するために、ブロックはまず低域周波数エントリからジグザグ順序で走査される。非ゼロに量子化された値は、ゼロ・ラン・レングスと共に、エントロピ符号化される。
【００１４】
前述したように、時間的圧縮は、大部分の対象は連続したピクチャ・フレーム間で同一であり、連続したフレームで対象またはブロックに差があるとすれば、それは動き（対象の動き、またはカメラの動き）の結果としてフレーム内で位置の差が生じたからであるという事実を使用する。この相対符号化へのキーは動き予測である。一般的に、動き予測は大部分のビデオ圧縮アルゴリズムの中で本質的な処理要件となる。概略的には、動き予測はビデオ・シーケンスのフレームの間で時間冗長性を識別する作業である。
【００１５】
動き予測
前述したように、動き予測では、符号化されている目標フレームがまず重複しない目標ブロックへ区分される。各目標ブロックは参照フレームまたは探索フレーム内にあるすべての重複する候補ブロックと比較される。これらの候補ブロックは目標ブロックの周囲の区域にある。目標ブロックとの最良マッチを示す候補ブロックは、目標ブロックを表すために選択される。言い換えれば、目標ブロックは「最良マッチ」候補ブロックへのポインタまたは動きベクトルで符号化される。したがって、目標ブロックは、すでに再構成されている候補ブロックに対するポインタという最低コストで符号化または表される。ポインタのほかに、候補ブロックと目標ブロックとの差分（画素ごとに減算する）が計算され、この差分は候補ブロックと目標ブロックの差分すなわち誤差を表す。次に、この差分ブロックすなわち誤差ブロックにＤＣＴ変換が適用され、差分ブロックの量子化されたＤＣＴ像が圧縮ストリーム中に付加される。
【００１６】
時間的動き予測に基づく圧縮の主な問題は、探索フレームまたは参照フレームの中で、目標フレーム中のブロックに最も適したブロックを見つけることである。動きベクトルを予測するためには、ブロック・マッチングを含む各種の方法がある。ブロック・マッチングはＭＰＥＧ標準で使用され、最もポピュラーな動き予測方法である。ブロック・マッチングは、動きベクトルを計算するために、目標ビデオ・フレームの各ブロックを、隣接するビデオ・フレームの参照ウィンドウまたは探索ウィンドウにある複数の候補ブロックと比較する。符号化される目標ビデオ・フレームは、目標ブロックと呼ばれる同一サイズの複数のブロックに分割される。同様に、隣接するフレームすなわち参照フレームは、各目標ブロックのための探索ウィンドウまたは探索域へ区分される。これらの探索ウィンドウまたは探索域は目標フレーム中のそれぞれの目標ブロックの位置に対応している。探索ウィンドウは対応する目標ブロックよりも大きく、ブロック・マッチングによって、目標ブロックを探索ウィンドウ中の異なった候補ブロックと比較することができる。したがって、ブロック・マッチングは、各目標ブロックのために、隣接フレームに設けられた探索ウィンドウにある候補ブロックの中から近接したブロックを探索する。
【００１７】
ブロック・マッチングの探索は、目標ブロックと、隣接フレームの探索ウィンドウにある各候補ブロックとの近接度を測定し、最も近接したマッチを選択する。目標ブロックと候補ブロックとの近接度を測定するには、一般的に２つのブロック間の「絶対誤差の合計」（Sum of Absolute Errors: ＳＡＥ）を計算する。ＳＡＥは、２つのブロックのすべての対応画素の間で絶対差を計算し、それを合計したものである。２つのブロックのＳＡＥが小さければ小さいほど、２つのブロックの近接度は大きく、良好なマッチが存在する。他方、目標ブロックと候補ブロックとの間の近接度の測定には、対応する画素値の間の誤差の２乗を計算し、それを合計してもよい。概して、動き予測の実行（すなわち、ビデオ・フレームのブロック間で動きを表す動きベクトルを生成する処理）には、大量の処理作業量を必要とする。
【００１８】
現時点の先行技術では、最良の候補ブロックまたは参照ブロックを見つけるために、画素に基づいた（すなわち、空間領域に基づいた）方法を使用する。前述したように、画素に基づく方法は、対応する画素値の間の誤差を２乗して、その合計を最小にすること、または対応する画素値の間の絶対差の合計を最小にすることを含む。この最後の方法は、乗算を含まないので計算的に効率がよい。これら２つの計算法の目的は、候補ブロックまたは予測ブロックと目標ブロックとの間の誤差の２乗の平均（mean square errors: ＭＳＥ）と信号対雑音比（signal to noise ration: ＳＮＲ）を最小にすることであり、これらの計算法によって高い圧縮を達成する予測ブロックを見つけることができるだろうとの期待から行われる。
【００１９】
前記の画素に基づくアプローチには、同じ原因から生じる２つの問題点がある。最初の問題点は、空間領域で「近接している」ブロックが周波数領域でも近接しているとはかぎらず、誤差または「距離」が周波数領域で符号化されることである。２番目の問題点は、ＭＳＥまたは（Ｐ）ＳＮＲに関連づけて行われる最適化は、必ずしも主観的ピクチャ品質（人間の観察者によって認識されるピクチャ品質）に寄与しないことが分かってきたからである。その原因は、導入される誤差に関しては最適化が行われない事実に帰することができる。言い換えれば、目標ブロックと最良マッチ候補ブロックとの差分はＤＣＴ値として転送され、したがって最良マッチ候補ブロックの探索はＤＣＴ領域で実行されるのが最適なのである。現在の方法では、最適化は画素値に関してなされ、その方法はＨＶＳが高域周波数の誤差よりも低域周波数の誤差に鋭敏であることを考慮していない。したがって、再構成された画像に対する誤差の影響に関して、誤差を重みづけてはいない。量子化によってこれらの重みづけを考慮すると仮定しても、最良マッチは画素すなわち空間領域で決定すべきではなく、周波数すなわちＤＣＴ値に関して決定すべきである。なぜなら、そこに誤差が導入されるからである。
【００２０】
改善された動き予測を提供する１つの既知の方法は、動き予測を周波数領域すなわちＤＣＴ領域で実行することである。この方法は、ＤＣＴを使用して、まず目標ブロックおよび参照ブロック（すなわち、候補ブロック）の各々を周波数領域へ変換する。次に、ＤＣＴ領域ブロックに対してある計量値を最小化することによって（たとえば、変換されたブロックの差分または誤差を最小化することによって）動き予測が実行される。周波数領域すなわちＤＣＴ領域で動き予測を実行すると、マッチングおよびピクチャ品質が改善され、圧縮も改善される。その理由は、主としてＤＣＴ領域の誤差または差分を最小にすることができるという事実による。圧縮されたストリーム中に実際に入れられるのは、そのような誤差または差分である。
【００２１】
【発明が解決しようとする課題】
ＤＣＴ領域または周波数領域で動き予測を実行する場合の１つの問題点は、ＤＣＴを使用して、目標ブロックおよび参照ブロック（または、候補ブロック）の各々を周波数領域へ変換しなければならないことである。これは、画素に基づくブロック・マッチングと比較して、演算のオーバーヘッドを非常に大きくする。その結果、ビデオ・ストリーム（たとえば、ＭＰＥＧストリーム）を圧縮または符号化するのに必要な処理パワーと時間が増大する。
したがって、より優れたピクチャ品質と圧縮を達成し、またＭＰＥＧ標準に合致した、動き予測を効率的に実行する新しいシステムと方法が望まれる。周波数領域またはＤＣＴ領域に基づいた基準を使用して、ＭＰＥＧ転換動き予測に最適のマッチ・ブロックを決定する新しいシステムと方法が望まれる。さらに、ＤＣＴ領域で動き予測を実行し、処理のオーバーヘッドと動き予測に必要な符号化時間を最小にする新しいシステムと方法が望まれる。
【００２２】
【課題を解決するための手段】
発明の要約
本発明は、ビデオ・シーケンスのフレーム間で動きベクトルを予測するシステムおよび方法に関する。本発明はビデオ・エンコーダを含むコンピュータ・システムで実施するのが望ましく、このビデオ・エンコーダは、圧縮されていないビデオ・ファイルまたはビデオ・ビットストリームを受け取り、圧縮すなわち符号化されたビデオ・ストリームを生成する。実施例では、ビデオ・エンコーダはＭＰＥＧ符号化技術を使用する。このようなＭＰＥＧエンコーダは、本発明に従って周波数領域またはＤＣＴ領域で動き予測を実行する動き予測／補償ロジックを含む。このＭＰＥＧエンコーダは本発明に従ってＤＣＴ領域で動き予測を実行するが、その効率性は改善され演算所要量も削減されている。
【００２３】
動き予測システムは、前に符号化されたブロック（参照ブロックまたは探索ブロックと呼ばれる）へのポインタまたは動きベクトルを使用して目標ブロックを符号化する。このシステムは、まず目標フレームを目標ブロックと呼ばれる複数のマクロブロックへ区分する。次に、このシステムは、周波数領域変換（ＤＣＴ変換が望ましい）を目標フレーム内の目標ブロック上で実行する。次に、動き予測システムは、探索フレームから候補ブロックを選択し、選択された候補ブロックの上で周波数領域変換を実行する。動き予測システムは、前に選択された候補ブロックの変換値の少なくとも一部分を再使用することができる新規な方法を使用して、候補ブロックを選択する。
【００２４】
候補ブロックが選択された後で、動き予測システムは目標フレーム内で１つまたは複数の「関連した」目標ブロックを決定する。これらの「関連した」目標ブロックは、選択された候補ブロックが含まれている対応する探索ウィンドウを有する。したがって、本発明の動き予測システムは、「逆」の観点からブロック比較を実行する。言い換えれば、通常の先行技術に基づくブロック・マッチングを実行する方法は、画素またはＤＣＴ領域のいずれに基づくものであっても、まず目標フレーム内で目標ブロックを選択し、この目標ブロックを、探索フレームまたは参照フレーム内の探索ウィンドウから取られた複数の候補ブロックと比較する。本発明の実施例によれば、参照フレームまたは探索フレーム内で候補ブロックが選択され、次に目標フレーム内で「関連した」目標ブロックが決定される。目標フレーム内の「関連した」目標ブロックとは、選択された候補ブロックが、問題としている目標ブロックの探索ウィンドウの中に含まれるようなブロックである。
【００２５】
関連した目標ブロックが選択された後で、システムは、選択された候補ブロックの変換値と、決定された目標ブロックの変換値との距離を計算する。次に、システムは、計算された距離が、決定された目標ブロックについて前に計算され現在記憶されている距離よりも良好な計量値であるかどうかを決定する。目標ブロックについて良好な計量値であれば、システムは、選択された候補ブロックの位置を目標ブロックのために記憶する。さらに、システムは計算された距離を記憶するかキャッシュに入れて、後で使用することができる。
【００２６】
前記のステップは、探索フレーム内で使用可能な候補ブロックの各々について実行される。この方法は目標ブロックの各々のために「最良マッチ」候補ブロックを生成または決定する。次に、システムは「最良マッチ」候補ブロックに基づいて、目標フレーム内の各目標ブロックについて動きベクトルを計算する。
【００２７】
探索フレームから選択された候補ブロック上でＤＣＴ変換を実行する方法は、選択された候補ブロックを複数のサブブロックへ区分すること、およびサブブロックの各々の上でＤＣＴ変換を実行することを含む。変換値が計算された後で、システムは、後の計算で再使用するためにサブブロックの変換値を記憶する。本発明のシステムは、先行する候補ブロックのサブブロックから変換されて記憶された値を再使用する新規な方法を実行して、探索フレームから候補ブロックを選択する。
【００２８】
実施例において、候補ブロックおよび目標ブロックは１６ｘ１６マクロブロックで、このマクロブロックは８ｘ８サブブロックから構成される。探索フレームは複数の水平方向バンドに区分され、各水平方向バンドの垂直方向の長さは候補ブロックの垂直方向の長さに等しい。水平方向バンドの各々は、２つの上部サブブロックを含む上部部分と、２つの下部サブブロックを含む下部部分に分かれている。さらに、探索フレームは複数の垂直ストリップに区分され、各垂直ストリップの水平方向の幅は、候補ブロックの水平方向の幅に等しい。探索フレームから候補ブロックを選択する望ましい方法は、先行する水平方向バンドから得られた先行する候補ブロックの２つの下部サブブロックの変換値を再使用できるように、各垂直方向ストリップ内で水平方向バンドを選択することである。この選択方法は、探索フレーム内の候補ブロックのすべてを選択するために実行される。さらに、望ましい方法は、先行する垂直方向ストリップの２つの右側サブブロックの変換値を再使用する新しい垂直方向ストリップを選択することである。これは演算所要量を削減し、動き予測システムのパフォーマンスを高める。
本発明は効率を高め演算所要量を削減する方法で周波数領域またはＤＣＴ領域で動き予測を実行する。すなわち、本発明はパフォーマンスを改善した方法でＤＣＴ領域でのビデオ符号化を実現する。
【００２９】
【発明の実施の形態】
本発明の良好な理解は、次の図面を参照して以下に記述する実施例の詳細な説明を検討することによって得ることができる。
【００３０】
ビデオ圧縮システム
ここで図１を参照すると、そこにはビデオ圧縮を実行するシステムが示される。このシステムは本発明に従う動き予測システムを含んでいる。本発明に従うシステムは、ビデオを符号化すなわち圧縮している間に、ビデオ・シーケンスの複数のフレーム間で動き予測を実行する。言い換えれば、本発明のシステムは、ビデオ圧縮に使用される動き予測ベクトルを生成する。しかし、本発明のシステムは、必要に応じて、動き予測を実行するために、もしくは各種のアプリケーションで使用される動きベクトルを生成するために、使用することができる。
【００３１】
図示されるように、１つの実施例では、ビデオ圧縮システムは汎用コンピュータ・システム６０を含んでいる。汎用コンピュータ・システム６０はメディア記憶装置６２へ接続される。メディア記憶装置６２は汎用コンピュータ・システム６０によって圧縮されるディジタル・ビデオ・ファイルを記憶している。実施例では、汎用コンピュータ・システム６０は通常の圧縮されていないディジタル・ビデオ・ファイルまたはビットストリームを受け取り、圧縮されたビデオ・ファイルを生成する。本明細書において、「圧縮されていないディジタル・ビデオ・ファイル」とは、圧縮されていない生のビデオ・ストリームを意味するものとし、「圧縮されたビデオ・ファイル」とは、動き予測の技法を使用する任意のビデオ圧縮アルゴリズム（ＭＰＥＧ標準を含む）に従って圧縮されたビデオ・ファイルを意味するものとする。
【００３２】
図示されるように、汎用コンピュータ・システム６０は、ビデオの符号化または圧縮動作を実行するビデオ・エンコーダ７６を含む。ビデオ・エンコーダ７６はＭＰＥＧエンコーダであることが望ましい。汎用コンピュータ・システム６０は、オプションとしてＭＰＥＧデコーダ７４を含んでいてもよい。ビデオ・エンコーダ７６およびＭＰＥＧデコーダ７４は、コンピュータ・システム内のバスに接続されたアダプタ・カードであるが、説明を分かりやすくするため汎用コンピュータ・システム６０の外部に示されている。さらに、汎用コンピュータ・システム６０はフロッピ・ディスク７２で表されるソフトウェアを含む。このソフトウェアは、必要に応じてビデオ圧縮動作の一部を実行し、もしくは他の動作を実行することができる。
【００３３】
汎用コンピュータ・システム６０は各種の標準コンポーネントを含んでいる。このような標準コンポーネントとしては、１つまたは複数のプロセッサ、１つまたは複数のバス、ハード・トライブ、およびメモリなどがある。ここで図２を参照すると、そこには図１のコンピュータ・システムに含まれるコンポーネントのブロック図が示される。注意すべきは、図２は例であり、必要に応じて他のコンピュータ・アーキテクチャを使用できることである。図示されるように、コンピュータ・システムは少なくとも１つのプロセッサ８０を含む。プロセッサ８０はチップセット・ロジック８２を介してシステム・メモリ８４へ接続される。チップセット・ロジック８２は、ＰＣＩ(Peripheral Componet Interconnect)バス８６へインタフェースされるＰＣＩブリッジ、または他の拡張バスへインタフェースされる他のバス・ブリッジを含む。図２では、ＭＰＥＧデコーダ７４およびビデオ・エンコーダ７６はＰＣＩバス８６へ接続されている。各種の他のコンポーネント（たとえば、ビデオ８８およびハード・ドライブ９０）がコンピュータ・システムに含まれてよい。
【００３４】
前述したように、図１の汎用コンピュータ・システム６０は１つまたは複数のディジタル記憶装置またはメディア記憶装置を含むか、それらに接続される。たとえば、図１の実施例では、汎用コンピュータ・システム６０はケーブル６４を介してメディア記憶装置６２へ接続される。メディア記憶装置６２は、ＲＡＩＤ(Redundent Array of Inexpensive Disks)ディスク・アレイ、１つまたは複数のＣＤ−ＲＯＭドライブまたはディジタル・ビデオ・ディスク（ＤＶＤ）記憶装置のようなメディアを含み、圧縮されるディジタル・ビデオを記憶するか、符号化されたビデオ・データを記憶する。さらに、コンピュータ・システムは、１つまたは複数の内部ＲＡＩＤアレイ、ＣＤ−ＲＯＭドライブを備えるか、１つまたは複数の別個のディジタル・ビデオ・ディスク（ＤＶＤ）記憶装置へ接続されてよい。さらに、汎用コンピュータ・システム６０は、必要に応じて他の種類のディジタルまたはアナログ記憶装置またはメディアへ接続されてよい。
【００３５】
代替方法として、ディジタル・ビデオ・ファイルは、外部源（たとえば、カメラまたは他のリアル・タイム装置）、遠隔記憶装置、または遠隔コンピュータ・システムから受け取ることができる。この実施例では、コンピュータ・システムは、ディジタル・ビデオ・ファイルを受け取るために、ＡＴＭ（非同期転送モード）アダプタまたはＩＳＤＮ（統合ディジタル・サービス通信網）端末アダプタ、または他のディジタル・データ受信器を備えることができる。さらに、ディジタル・ビデオ・ファイルは、アナログ形式で記憶または受け取られてディジタル・データへ変換されてよいが、そのようなことは汎用コンピュータ・システム６０の外部または内部で行われてよい。
【００３６】
前述したように、汎用コンピュータ・システム６０内のビデオ・エンコーダ７６は、ビデオの符号化または圧縮機能を実行する。ビデオの符号化または圧縮を実行する場合、ビデオ・エンコーダ７６はディジタル・ビデオ・ファイルの複数のフレーム間で動き予測ベクトルを生成する。後述するように、汎用コンピュータ・システム６０内のビデオ・エンコーダ７６は、本発明に従い効率が改善され演算所要量が削減されるような方法で、周波数領域またはＤＣＴ領域で動き予測を実行する。
【００３７】
注意すべきは、ビデオ・データを符号化し圧縮するシステムは、必要であれば２つ以上の相互接続されたコンピュータを使用できることである。ビデオ・データを符号化または圧縮するシステムは、セット・トップ・ボックスのような他のハードウェアを含むことができる。このようなハードウェアは単独または汎用プログラム可能コンピュータと組み合わせて使用される。注意すべきは、本発明に従ってビデオ・データを符号化または圧縮するためには、必要に応じて任意の種類のシステムを使用できることである。
【００３８】
図３  −  先行技術のＭＰＥＧエンコーダのブロック図
ここで図３を参照すると、そこには先行技術に従って動き予測を実行するＭＰＥＧエンコーダ７７を示すブロック図が示される。図示されるように、ＭＰＥＧエンコーダ７７は圧縮されていないディジタル・ビデオ・ストリームを受け取り符号化されたストリームを出力する。圧縮されていないディジタル・ビデオ・ストリームはビデオ・データのビットストリームである。このビットストリームは、ビデオ・シーケンス（たとえば、テレビの番組または映画）を画面（たとえば、テレビまたはコンピュータ・システム）に表示するために使用される。実施例では、ＭＰＥＧエンコーダ７７はＭＰＥＧ−２圧縮アルゴリズムを使用して、圧縮されていないディジタル・ビデオ・ストリームを圧縮する。
【００３９】
図３に示されるように、ブロック・コンバータ１０２は、輝度および色の入力ビデオ信号をブロック形式へ変換する。ここで、各ブロックは６４画素値より成る８ｘ８マトリクスである。ブロック形式は、符号化システムの特定の型に従って特定のスペーシング形式（たとえば、標準の４：４：４、４：２：２、４：２：０など）にまとめられた複数のマクロブロックとして実施される。後で詳しく説明するように、ブロック・コンバータ１０２は、順次の画素値を減算器１０４および動き予測／補償ロジック１２２へ与える。さらに、ブロック・コンバータ１０２は、出力をイントラＳＷ決定ブロック１３０へ与える。
【００４０】
減算器１０４はマルチプレクサ１２６から入力を受け取り、ブロック・コンバータ１０２の出力からマルチプレクサ１２６の出力を減算するように動作する。マルチプレクサ１２６は動き予測／補償ロジック１２２から入力を受け取り、さらにゼロ・ブロック１２８から０入力を受け取る。マルチプレクサ１２６はイントラＳＷ決定ブロック１３０から選択入力を受け取る。イントラＳＷ決定ブロック１３０は、インターフィールド・データ・モードまたはイントラフィールド・データ・モードのいずれが使用されるかを決定する。インターフィールド・データ・モードでは、マルチプレクサ１２６は動き予測／補償ロジック１２２から出力を与え、減算器１０４は動き予測／補償ロジック１２２によって与えられたマクロブロックの各ブロックを、ブロック・コンバータ１０２から与えられた対応するブロックから減算する。イントラフィールド・データ・モードでは、マルチプレクサ１２６はゼロ・ブロック１２８からの出力を与えるので、ブロック・コンバータ１０２からのブロックは、変更されないで減算器１０４を通過する。
【００４１】
減算器１０４は、差分的に符号化された動き予測マクロブロックの出力ブロック（インターモード）または変更されない出力ブロック（イントラモード）をＤＣＴコンバータ１０６へ与える。ＤＣＴコンバータ１０６はブロックの各々をＤＣＴ形式へ変換し、ＤＣＴ係数を含む対応する８ｘ８ブロックを生成する。ＤＣＴ形式は、ビデオ・データの圧縮を可能とするために周波数領域におけるデータを表している。各々のＤＣＴブロックについて、最初または最上部左の係数は、典型的にブロックのＤＣ成分を含み、残りの値は垂直方向および水平方向の周波数を増分するためのＡＣ成分である。
【００４２】
ＤＣＴコンバータ１０６からのＤＣＴ係数は、画素をジグ・ザグ形式に配列し直すＺＺブロック１０７へ与えられる。ＺＺブロック１０７の出力は、係数値の集合を量子化される値へマップする量子化器１０８へ与えられる。典型的には、低域周波数係数に対しては、高域周波数係数に対するよりも小さな集合が使用される（すなわち、精密量子化）。なぜなら、人間の目は低域空間周波数の画像成分に対してよりも、高域空間周波数の画像成分に対して鈍感だからである。
【００４３】
量子化器１０８からのデータ値は、データを符号化して記憶または伝送するために可変長エンコーダ（ＶＬＥ）１１０へ与えられる。可変長エンコーダ（ＶＬＥ）１１０は、データ・ブロックを走査し、それをエントロピ符号化の原理に従って可変長コード（ＶＬＣ）へ変換する。エントロピ符号化は、符号化利得（したがって、データ圧縮）を達成するため、短いコードを確率の高い値へ割り当てる。そのようなＶＬＣ符号化方式の１つはハフマン符号化であるが、他の符号化方式も使用することができる。ＶＬＣは可変長エンコーダ（ＶＬＥ）１１０から先入れ先出し（ＦＩＦＯ）バッファ１１２へ与えられる。
【００４４】
インターフィールド・データ・モードでは、量子化器１０８からのデータ値は、量子化器１０８によって実行された動作を逆転して符号化された画像の各ブロックを表す近似ＤＣＴ係数を生成するために逆量子化器１１４へ与えられる。通常、量子化は非可逆処理であるから、逆量子化器１１４の出力は雑音と誤差を生じる。
【００４５】
逆量子化器１１４の出力データは、ＺＺブロック１０７の動作を逆転する逆ＺＺブロック１１５へ与えられる。逆ＺＺブロック１１５の出力は、ＤＣＴコンバータ１０６によって実行された動作を逆転させるため逆ＤＣＴ（ＩＤＣＴ）コンバータ１１６へ与えられる。逆ＤＣＴ（ＩＤＣＴ）コンバータ１１６の出力で得られるフレーム差分ブロックは、二入力加算器１１８の１つの入力へ与えられる。さらに、二入力加算器１１８は、動き予測／補償ロジック１２２から出力データ・ブロックを受け取る。二入力加算器１１８からの出力画素値はフレーム記憶メモリ１２０へ与えられる。そこに記憶されたデータは、ビデオ・バッファ（図示されていない）に与えるか、モニタのような表示装置（図示されていない）で表示することができる。
【００４６】
フレーム記憶メモリ１２０内の値は、動き予測／補償ロジック１２２の入力へ与えられる。一般的に、動き予測／補償ロジック１２２は、動きベクトルの形式で動きを表すために、ブロック・コンバータ１０２から到着するブロックを、再構成されてフレーム記憶メモリ１２０内に記憶されている前のブロックと比較する。図３の動き予測／補償ロジック１２２は、先行技術の技法を用いて空間領域における動き予測を実行する。
【００４７】
動き予測／補償ロジック１２２は対象すなわちブロックを新しいフレーム内の予測位置へシフトし、予測ブロックを生成する。次に、インターフィールド・データ・モードでは、この予測ブロックは、ブロック差分または予測誤差を得るために入力ブロックから減算される。この処理は、フレーム間冗長性と予測誤差とを分離する。次に、インターフィールド・データ・モードでは、ブロック差分は空間冗長性を除去するためにＤＣＴコンバータ１０６、ＺＺブロック１０７、および量子化器１０８によって処理される。したがって、この先行技術による方法では、動き予測は空間領域（すなわち、画素領域）で実行され、その後でフレーム差分がＤＣＴ変換され量子化される。
【００４８】
図４  −  先行技術による空間領域ブロック・マッチング動き予測
前述したように、大部分のビデオ圧縮アルゴリズムは、画素に基づいたブロック・マッチング動き予測を空間領域で実行して、ビデオ・シーケンスのフレーム間に存在する時間冗長性を識別する。動き予測の計算では、目標フレームと隣接フレーム（または、探索フレーム）との間のブロックの動き（すなわち、変化）を予測するために、目標フレーム中の１つまたは複数のブロックと、隣接フレームまたは探索フレーム中の対応する１つまたは複数のブロックとの間で動き予測ベクトルを計算する。
【００４９】
一般的に、ブロック・マッチングは最もポピュラーな動き予測方法であり、ＭＰＥＧ標準で使用される。図４はブロック・マッチング動き予測方法の動作を示す。具体的に説明すると、図４は目標ビデオ・フレーム２０２と探索ビデオ・フレーム２１２とを示している。目標ビデオ・フレーム２０２は等しいサイズの複数の目標ブロック（たとえば、目標ブロック２０４）に区分される。探索ビデオ・フレーム２１２は各目標ブロックのための探索ウィンドウまたは探索域へ区分される。探索ウィンドウ２１４は目標ブロック２０４に対応している。各々の探索ウィンドウ２１４の中心の点または位置は、目標ビデオ・フレーム２０２における目標ブロック２０４の中心の点または位置に対応していることが望ましい。図示されるように、探索ウィンドウ２１４は目標ブロック２０４よりも大きく、目標ブロック２０４が中心に位置することが望ましい。
【００５０】
探索ウィンドウ２１４は目標ブロック２０４よりも大きいので、目標ブロック２０４を探索ウィンドウ２１４内の複数の候補ブロック２１６と比較することができる。探索ウィンドウ２１４は、目標ブロック２０４と同じサイズをもつ複数の候補ブロック２１６へ区分される。ブロック・マッチングは、目標ビデオ・フレーム２０２内の目標ブロック２０４の画素を、探索ビデオ・フレーム２１２の探索ウィンドウ２１４にある複数の候補ブロック２１６の画素と比較し、それぞれのフレームの２つのブロック間で最も近接したマッチを決定し動きベクトルを計算する。したがって、ブロック・マッチングは、隣接フレーム（すなわち、探索ビデオ・フレーム２１２）の探索ウィンドウ２１４（または、探索域）の中にある複数の候補ブロック２１６から目標ブロック２０４と近接したブロックを探索する。
【００５１】
ブロック・マッチング法では、目標ブロック２０４と、探索ビデオ・フレーム２１２の探索ウィンドウ２１４にある各候補ブロック２１６との近接性が測定され、最も近接したマッチを選択することにより探索が実行される。目標ブロック２０４と候補ブロック２１６との近接性の計測は、一般的に２つのブロックの間の絶対誤差の合計（ＳＡＥ）を計算することである。ＳＡＥは、２つのブロックにおけるすべての対応する画素の間の絶対差分の合計である。２つのブロックのＳＡＥが小さければ小さいほど、それらブロック間に、より近接した（または、より良好な）マッチが存在する。近接性を計測する他の方法はブロック間の誤差の２乗の合計を計算することである。
【００５２】
図４に示されるように、目標ブロック２０４は、探索ビデオ・フレーム２１２の探索ウィンドウ２１４にある異なった候補ブロック２１６と比較される。図４は、目標ブロック２０４と、探索ウィンドウ２１４にある２つの候補ブロック２１６を示す。目標ブロック２０４は、水平方向および垂直方向へ一時に１画素だけ変位されることによって、探索ウィンドウ２１４上を移動される。移動された位置で、目標ブロック２０４と候補ブロック２１６との間の「距離」が計算される。ここで、「距離」とはＳＡＥまたは誤差の２乗の合計である。すべての値の中で最小の距離となった候補ブロック２１６が、目標ブロック２０４とマッチするものとして選択される。
【００５３】
したがって、目標ビデオ・フレーム２０２内の各目標ブロック２０４について、動き予測の作業は探索ウィンドウ２１４内の各候補ブロック２１６のためにＳＡＥまたは誤差の２乗の合計を計算するという膨大な演算を実行して、各候補ブロック２１６のために距離の値を決定する。これらの距離値が計算された後に、最小距離をもつ候補ブロック２１６が選択される。
【００５４】
図５  −  本発明に従うＭＰＥＧエンコーダのブロック図
ここで図５を参照すると、そこには本発明に従って動き予測を実行するビデオ・エンコーダ７６のブロック図が示される。１つの実施例において、ビデオ・エンコーダ７６は図３に示されるアーキテクチャを含み、動き予測／補償ロジック１２２はＤＣＴ変換・量子化ブロックを含んで、本発明に従ってＤＣＴ領域で動き予測を実行する。図５の実施例では、ビデオ・エンコーダ７６は、本発明に従って周波数領域またはＤＣＴ領域で動き予測を実行するために異なったアーキテクチャを含む。図５の要素で図３の要素と同じものは、参照番号にＡまたはＢを付けてある。
【００５５】
図示されるように、ビデオ・エンコーダ７６は圧縮されていないディジタル・ビデオ・ストリームを受け取り、符号化されたストリームを出力する。圧縮されていないディジタル・ビデオ・ストリームは、ビデオ・シーケンス（たとえば、テレビの番組または映画）を画面（たとえば、テレビまたはコンピュータ・システム）で表示するために使用されるビデオ・データのビットスリームである。実施例において、ビデオ・エンコーダ７６は、ＭＰＥＧ−２圧縮アルゴリズムを使用して、圧縮されていないディジタル・ビデオ・ストリームを圧縮する。必要に応じて他のタイプの圧縮を行うことができる。
【００５６】
図５に示されるように、ブロック・コンバータ１０２Ａは、輝度および色の入力ビデオ信号をブロック形式に変換する。各ブロックは６４画素値を含む８ｘ８マトリクスで構成される。ブロック形式は、符号化システムの特定のタイプに従って特定のスペーシング・フォーマット（たとえば、標準の４：４：４、４：２：２、４：２：０など）にまとめられた複数のマクロブロックになっている。
【００５７】
ブロック・コンバータ１０２Ａは、順次の画素値をＤＣＴコンバータ１０６Ａへ与える。ＤＣＴコンバータ１０６Ａは、ブロックの各々をＤＣＴ形式に変換し、ＤＣＴ係数を含む対応する８ｘ８ブロックを生成する。ＤＣＴ形式はビデオ・データの圧縮を可能とするために周波数領域におけるデータを表している。各ＤＣＴブロックでは、最初または最上部左の係数は、典型的にはブロックのＤＣ成分を含み、残りの値は垂直方向および水平方向周波数を増分するＡＣ成分である。
【００５８】
ＤＣＴコンバータ１０６ＡからのＤＣＴ係数は、減算器１０４Ａおよび本発明に従う動き予測／補償ロジック２５０へ与えられる。動き予測／補償ロジック２５０については後で詳細に説明する。さらに、ＤＣＴコンバータ１０６Ａは、出力をイントラＳＷ決定ブロック１３０Ａへ与える。図５の動き予測／補償ロジック２５０は、図３の動き予測／補償ロジック１２２とは異なり、本発明に従って演算所要量を削減した方法でＤＣＴ変換値に動き予測を実行する。
【００５９】
減算器１０４Ａはマルチプレクサ１２６Ａから入力を受け取り、マルチプレクサ１２６Ａの出力をＤＣＴコンバータ１０６Ａの出力から減算するように動作する。マルチプレクサ１２６Ａは動き予測／補償ロジック２５０から入力を受け取り、さらにゼロ・ブロック１２８Ａから０の入力を受け取る。マルチプレクサ１２６ＡはイントラＳＷ決定ブロック１３０Ａから選択入力を受け取る。イントラＳＷ決定ブロック１３０Ａは、インターフィールド・データ・モードまたはイントラフィールド・データ・モードのいずれが使用されているのかを決定する。インターフィールド・データ・モードでは、マルチプレクサ１２６Ａは動き予測／補償ロジック２５０からの出力を与え、減算器１０４Ａは、動き予測／補償ロジック２５０から与えられたマクロブロックの各ブロックを、ＤＣＴコンバータ１０６Ａから与えられた対応するブロックから減算する。イントラフィールド・データ・モードでは、マルチプレクサ１２６Ａはゼロ・ブロック１２８Ａからの出力を与え、したがってＤＣＴコンバータ１０６Ａからのブロックは、変更されないで減算器１０４Ａを通過する。
【００６０】
減算器１０４Ａは予測の後にＤＣＴ変換ブロックの誤差項を出力する。減算器１０４Ａからのデータ値は、係数値の集合を量子化された値へマップする量子化器１０８Ａへ与えられる。典型的には、低域周波数係数に対しては、高域周波数係数に対するよりも小さい集合が使用される（すなわち、精細量子化）。なぜなら、人間の目は、低域空間周波数の画像成分よりも高域空間周波数の画像成分に鈍感だからである。
【００６１】
量子化器１０８Ａの出力は、画素をジグ・ザグまたは斜行形式に配列し直すＺＺブロック１０７Ａへ与えられる。ＺＺブロック１０７Ａの出力は、記憶または伝送用にデータを符号化するため、可変長エンコーダ（ＶＬＥ）１１０Ａへ与えられる。可変長エンコーダ（ＶＬＥ）１１０Ａはデータ・ブロックを走査し、それをエントロピ符号化の原理に従って可変長コード（ＶＬＣ）へ変換する。符号化利得（したがって、データ圧縮）を達成するため、短いコードが確率の高い値へ割り振られる。そのようなＶＬＣ符号化方式の１つはハフマン符号化であるが、他の符号化方式も使用することができる。ＶＬＣは可変長エンコーダ（ＶＬＥ）１１０Ａから先入れ先出し（ＦＩＦＯ）バッファ１１２Ａへ与えられる。
【００６２】
ＩおよびＰフレームについては、量子化器１０８Ａからのデータ値は、量子化器１０８Ａによって実行された動作を逆転して符号化された画像の各ブロックを表す近似ＤＣＴ係数を生成するため、逆量子化器１１４Ａへ与えられる。通常、量子化は非可逆処理であるから、逆量子化器１１４Ａの出力は雑音と誤差を導入する。
【００６３】
逆量子化器１１４Ａの出力データは、ＤＣＴコンバータ１０６Ａによって実行された動作を逆転するため、逆ＤＣＴ（ＩＤＣＴ）コンバータ１１６Ａへ与えられる。逆ＤＣＴ（ＩＤＣＴ）コンバータ１１６Ａの出力で得られるフレーム差分ブロックは、二入力加算器１１８Ａの１つの入力へ与えられる。さらに、二入力加算器１１８Ａは、マルチプレクサ１２６Ａから出力データ・ブロックを受け取る。この出力データ・ブロックは動き予測／補償ロジック２５０から与えられたものである。二入力加算器１１８Ａからの出力画素値はフレーム記憶メモリ１２０Ａへ与えられる。
【００６４】
フレーム記憶メモリ１２０Ａ内の値は、値にＤＣＴ変換を実行するＤＣＴコンバータ１０６Ｂの入力へ与えられる。ＤＣＴコンバータ１０６Ｂはその出力を動き予測／補償ロジック２５０へ与える。注意すべきは、ＤＣＴコンバータ１０６ＢはＤＣＴコンバータ１０６Ａと同一であることである。さらに注意すべきは、ＤＣＴコンバータ１０６Ｂは図５に追加された要素であって、先行技術を示す図３には含まれていないことである。
【００６５】
概略的には、動き予測／補償ロジック２５０は、動きベクトルの形式で動きを表すため、ＤＣＴコンバータ１０６Ａから到着するフレーム（すなわち、目標フレーム）のＤＣＴ変換値を、再構成された前のフレームのＤＣＴ変換値（ＤＣＴコンバータ１０６Ｂからの出力）と比較する。動き予測／補償ロジック２５０は、本発明に従って周波数領域またはＤＣＴ領域で動き予測を実行する。
【００６６】
動き予測／補償ロジック２５０は、対象すなわちブロックを新しいフレーム中の予測位置へシフトし、予測ブロックを生成する。インターフィールド・データ・モードでは、この予測ブロックは入力ブロックから減算され、ブロック差分すなわち予測誤差が得られる。この処理は、フレーム間冗長性および予測誤差を分離する。インターフィールド・データ・モードでは、このフレーム差分すなわち予測誤差は、空間冗長性を除去するためにすでにＤＣＴ変換されている。
【００６７】
したがって、本発明に従うエンコーダでは、動き予測はＤＣＴ変換値の上で実行される。動き予測／補償ロジック２５０は、後に説明するように、本発明に従ってパフォーマンスを改善し演算所要量を削減した方法で周波数領域すなわちＤＣＴ領域で動き予測を実行する。
【００６８】
さらに、後で説明するように、動き予測／補償ロジック２５０は、探索フレームから候補ブロックを選択する手段と、目標フレーム中で１つまたは複数の関連目標ブロックを決定する手段と、選択された候補ブロックの変換値と１つまたは複数の決定された目標ブロックの各々の変換値との間の距離を計算する手段と、計算された距離が１つまたは複数の決定された目標ブロックの各々のために計算されて現在記憶されている距離よりも良好な計量値であるかどうかを決定する手段と、各目標ブロック用に計算された距離がそれまで各目標ブロック用に計算された最良の距離よりも良好な計量値である場合に目標ブロックのために選択された候補ブロックの位置を記憶するメモリとを含んでいる。注意すべきは、これら手段の各々を別個のロジックとして実施してもよく、必要に応じて、これらの手段の１つまたは複数をプログラム可能ＤＳＰまたはＣＰＵとして実施してもよいことである。これら手段の動作は、フローチャートを使用して後で説明する。
【００６９】
図６  −  実施例に従って実行されるＤＣＴ領域中の動き予測のフローチャート
ここで図６を参照すると、そこには本発明の動き予測システムの動作を示すフローチャートが示される。図６の方法は、専用ロジックによって実施されるか、１つまたは複数のプログラム可能ＤＳＰによって実施される。ここで、動き予測システムは、１つまたは複数の目標ブロックに区分された目標フレームを符号化するものと仮定する。動き予測システムは、探索フレーム（すなわち参照フレーム）中の対応するブロックに従って１つまたは複数の目標フレーム・ブロックの各々を符号化する。１つの例として、動き予測システムは、先行するＩまたはＰフレームに対して、Ｐフレーム用の動きベクトルを符号化する。他の例として、動き予測システムは、先行または後続するＩまたはＰフレームに対して、Ｂフレームを符号化する。図７は図６と同様なフローチャートであるが、目標フレームがＢフレームであり、探索フレームがＩフレームである場合を示す。
図示されるように、ステップ３０２では、動き予測システムは目標フレーム内の目標ブロックのすべてに周波数領域変換を実行する。目標フレーム内の目標ブロックは図８に示されている。さらに、ステップ３０２では、動き予測システムは変換された目標ブロックをメモリに記憶する。実施例では、システムは目標ブロックにＤＣＴ変換を実行して、結果の値を生成する。ＤＣＴ変換は周知の技術であるから、その動作の詳細は省略する。
【００７０】
ステップ３０４では、システムは参照フレーム（すなわち探索フレーム）から候補ブロックを選択する。候補ブロックはＩまたはＰフレームのブロックである。これらのブロックは後続のＰフレーム・ブロック、または先行または後続のＢフレーム・ブロックのための参照または予測に使用されている。後で説明するように、本発明は、動き予測／補償ロジック２５０の演算所要量を削減する改善された候補ブロック選択方法を含む。この候補ブロック選択方法は、前に選択された候補ブロックのＤＣＴ変換値を最適に再使用することができる。候補ブロックを選択する方法は、図９から図１６までを使用して詳細に説明される。
【００７１】
ステップ３０６では、動き予測システムは、ステップ３０４で選択された候補ブロックにＤＣＴ変換を実行する。変換された値の少なくとも一部分は保存され、これらの値を後続の候補ブロックのために再使用できるようにされる。これについては後で説明する。
【００７２】
ステップ３０８では、動き予測システムは、参照フレーム（すなわち探索フレーム）から選択された候補ブロックのために、目標フレーム内のすべての「関連」目標ブロックを見つける。したがって、本発明の動き予測システムは、図８に示されるように「逆」の観点からブロックの比較を実行する。言い換えれば、ブロック・マッチングを実行する先行技術の方法は、画素に基づくものであれＤＣＴ領域にもとづくものであれ、まず目標フレーム内で目標ブロックを選択し、この目標ブロックを、探索フレーム（すなわち参照フレーム）内の探索ウィンドウにある複数の候補ブロックと比較する。この処理は、目標フレーム内の目標ブロックの各々についてなされる。
【００７３】
ブロック比較がＤＣＴ領域で実行される実施例では、この先行技術の方法は、候補ブロックの各々についての大量の冗長なＤＣＴ計算を生じる。本発明の方法では、参照フレームまたは探索フレーム内の候補ブロックを選択し、次に目標フレーム内の「関連」目標ブロックを決定する。目標フレーム内の「関連」目標ブロックとは、選択された候補ブロックが目標ブロックの探索ウィンドウに含まれるようなブロックである。したがって、ステップ３０８で目標フレーム内の「関連」目標ブロックを見つけることは、選択された候補ブロックを含むような対応する探索ウィンドウをもっている目標ブロックを決定することである。これは、先行技術で通常実行される手順とは逆である。先行技術の手順では、目標ブロックが選択され、探索フレームの探索ウィンドウにあるすべての候補ブロックが決定され、選択された１つの目標ブロックと比較される。
【００７４】
マクロブロックが１６ｘ１６画素のサイズであり、探索ウィンドウがマクロブロックに関して＋／−１６画素である実施例では、目標フレーム内の関連目標ブロックの数は、選択された候補ブロックの位置に依存して４、６、または９である。関連目標ブロックの数は、マクロブロックのサイズと探索域の関数であることに注意されたい。関連する目標ブロックを決定する方法については、図１７および図１８を参照して後で詳細に説明する。
【００７５】
ステップ３１０では、動き予測システムは、選択された候補ブロックと、ステップ３０８で見つけられた関連目標ブロックの１つとの間の「距離」を計算する。注意すべきは、ステップ３１０は、関連目標ブロックの各々について複数回実行されることである。ステップ３１０では、多くの方法を使用して距離を計算することができる。実施例では、動き予測システムは、選択された候補ブロックと目標ブロックにおけるＤＣＴ値の絶対差分を計算する。この実施例では、システムは、選択された候補ブロックの変換値を、決定された目標ブロックの変換値から減算する。この減算によって、１つまたは複数の決定された目標ブロックの各々のためにマトリクスが生成される。次に、システムは部分量子化を実行し、決定された目標ブロックのためのマトリクス内でゼロの数を決定する。
【００７６】
他の実施例では、動き予測システムは、選択された候補ブロックと目標ブロックにおけるＤＣＴ値の絶対差分を計算し、その結果を量子化し、その量子化された差分マトリクスをあるビット数に符号化する。次に、システムは、各候補ブロックのためにこの符号化された差分を伝送するのに必要なビットの数を決定し、次に、最少数のビットを必要とする候補ブロックを選択する。注意すべきは、最少数の符号化ビットを必要とする候補ブロックを選択する後者の方法は、演算所要量を増加させるが、候補ブロックを最適に選択できることである。
【００７７】
ステップ３１２では、動き予測システムは、目標ブロックのために計算された距離が、その目標ブロックのために記憶されている現在の最良の計量値よりも良好な計量値であるかどうかを決定する。ステップ３１０で計算された距離がその目標ブロックに対する現在の最良計量値よりも良好な計量値であることが、ステップ３１２で決定されると、その新しい候補ブロックの位置がステップ３１４で記憶される。ステップ３１４が終了すると、動作はステップ３１６へ進む。
【００７８】
したがって、目標ブロックについて、このフローチャートの前の繰り返しで選択された候補ブロックがある距離をもち、その候補ブロックが目標ブロックの探索ウィンドウの中にあり、現在の選択された候補ブロックと目標ブロックとの間の距離が、その目標ブロックのために現在記憶されている最良計量値よりも良好な計量値であれば、ステップ３１４で、最良計量値をもつこの新しい（すなわち現在選択されている）候補ブロックの位置が、その目標ブロックのために記憶される。実施例では、実際の差分値（距離の値）が一時バッファまたはキャッシュにも記憶されるので、後でこの差分値を再計算する必要はない。ステップ３１４が終了すると、動作はステップ３１６へ進む。
【００７９】
ステップ３１２で、ステップ３１０で計算された距離が、目標ブロックのために記憶されている現在の最良計量値よりも良好な計量値でないことがステップ３１２で決定されると、動作はステップ３１６へ進む。ステップ３１６では、システムは、これまでのステップが、選択された候補ブロックに対するすべての関連目標ブロックについて実行されたかどうかを決定する。実行されていなければ、システムはステップ３１０へ戻り、ステップ３１０からステップ３１６を繰り返す。これまでのステップが、選択された候補ブロックに対するすべての関連目標ブロックについて実行されたのであれば、システムはステップ３１８へ進む。
【００８０】
ステップ３１８では、システムは、これまでのステップが参照フレームまたは探索フレーム内のすべての候補ブロックについて実行されたかどうかを決定する。もし実行されたのであれば、動作は終了する。この場合、各目標ブロックのために「最良マッチ」候補ブロックが選択されている。ステップ３１８で、探索フレーム内の候補ブロックのすべてについて実行されたことが決定されなければ、動作はステップ３０４へ戻り、これまでのステップが繰り返される。
【００８１】
したがって、ある目標ブロックについて、探索フレームの探索ウィンドウ内にある関連候補ブロックのすべてが選択され、ステップ３０４からステップ３１８までの動作が実行されてしまうまでは、その目標ブロックと探索ウィンドウにあるすべての候補ブロックとの比較は実行されない。目標ブロックの近隣（すなわち探索ウィンドウ）にある候補ブロックのすべてが調べられた後では、目標ブロックに対して最良の計量値（すなわち最小距離）をもつ候補ブロックが決定されている。したがって、目標フレーム内の目標ブロックと探索フレーム内の候補ブロックとの間の最良マッチを与えるポインタまたは動きベクトルを生成することができる。
【００８２】
図９および図１０  −  フレームをバンドおよびストリップへ区分する
以下の説明では、例として６４ｘ６４画素のフレーム・サイズを使用する。注意すべきは、必要に応じて各種のフレーム・サイズに本発明を使用できることである。本発明の実施例では、動き予測／補償ロジック２５０は、ステップ３０４で、先行する候補ブロックの前に計算された変換値を再使用する候補ブロックを選択する。このような選択は、本発明に従ってＤＣＴ領域内でブロック・マッチング動き予測を実行するために必要なＤＣＴ変換の回数を削減する。
【００８３】
実施例において、目標ブロックは１６ｘ１６マクロブロックであり、候補ブロックも１６ｘ１６マクロブロックである。図８（ａ）は４つの８ｘ８サブブロックへ区分されたマクロブロックを示す。したがって、１６ｘ１６マクロブロックの各々は、４つの８ｘ８サブブロックとして区分することができ、２つの上部サブブロックと２つの下部サブブロックとを有する。動き予測は１つの１６ｘ１６目標マクロブロックと複数の１６ｘ１６候補ブロックとの間で実行される。ＤＣＴ変換は、マクロブロックを形成している４つの８ｘ８サブブロックの各々にＤＣＴ変換を個別的に実行することによって、１６ｘ１６マクロブロック上で実行される。
【００８４】
ここで図９（ａ）を参照すると、探索フレームは複数の水平方向バンドとして考えることができる。ここで、各水平方向バンドは、画素を含む複数の連続した行またはＤＣＴ変換値を含む複数の連続した行から構成される。実施例では、各バンドの垂直方向の長さ（すなわち行の数）は、目標ブロックおよび候補ブロックの行の長さまたは数に等しい。したがって、各水平方向バンドの垂直方向の長さは１６画素または１６行である。
【００８５】
図９（ａ）は、探索フレーム内にあるバンドのいくつかを示す。図９（ａ）の探索フレームの左にある数字は、探索フレーム内のバンドを表している。バンド１は探索フレームの最上部で始まり、その垂直方向の長さは１６行または１６画素である。したがって、バンド１は探索フレームの最上部マクロブロックを含む。図９（ａ）には示されていないが、バンド２はバンド１から１つの画素行だけ下から始まり、画素行２〜１７を含む。バンド３は２つの画素行だけ下から始まり、画素行３〜１８を含む。以下同様である。
【００８６】
図９（ａ）に示されるダッシ線は、各マクロブロックの中間地点を表す。言い換えれば、ダッシ線はサブブロック境界を表し、その境界はマクロブロックの最上部から８画素行だけ下にある。したがって、最初のダッシ線は画素行９で始まるように示され、二番目のダッシ線は画素行２５で始まるように示される。バンド９は画素行９（これは最初のマクロブロックの中間地点である）で始まり、その垂直方向の長さは１６である。バンド９は画素行９〜２４を含む。図示されるように、バンド１７は最上部から二番目のマクロブロックの開始点で始まり、画素行１７〜３２を含む。探索フレームの垂直方向の長さが６４画素（すなわち、４つのマクロブロック）である図９（ａ）の実施例では、全部で４９のバンドが探索フレーム内に存在する。
【００８７】
ここで図９（ｂ）を参照すると、探索フレームは複数の垂直方向ストリップから構成されるものと考えることができる。ここで、各垂直方向ストリップは画素を含む複数の連続した列、または、ＤＣＴ変換値を含む複数の連続した列から構成される。実施例では、各ストリップの水平方向の幅（すなわち列の数）は、目標ブロックの幅または列の数と等しく、また、それは候補ブロックの幅に等しい。したがって、目標マクロブロックおよび候補ブロックが１６ｘ１６ブロックである場合、各ストリップの幅は１６画素または１６列である。
【００８８】
図９（ｂ）は探索フレーム内のストリップのいくつかを示す。図９（ｂ）の探索フレームの最上部にある番号は、探索フレーム内のストリップを表す。したがって、ストリップ１は探索フレームの最上部左で始まり、その水平方向の幅は１６列または１６画素である。ストリップ１は探索フレームの最左端のマクロブロックを含む。図９（ｂ）には示されないが、ストリップ２はストリップ１から１つの画素列だけ横へずれて始まり、画素列２〜１７を含む。ストリップ３は２つの画素列だけ横へずれて始まり、画素列３〜１８を含む。以下同様である。
【００８９】
図９（ｂ）に示されるダッシ線は、各マクロブロックの中間地点を表す。言い換えれば、ダッシ線はサブブロックの境界を表し、その境界は各マクロブロックの左から横方向へ８画素列のところにある。したがって、最初のダッシ線は画素列９で始まるように示され、二番目のダッシ線は画素列２５で始まるように示される。以下同様である。ストリップ９はサブブロック境界上の画素列９（これは最初のマクロブロックの中間地点である）で始まり、その水平方向の幅は１６である。したがって、ストリップ９は画素列９〜２４を含む。図示されるように、ストリップ１７は左から二番目のマクロブロックの開始点で始まり、画素列１７〜３２を含む。探索フレームの水平方向の幅が６４画素（すなわち、４つのマクロブロック）である図９（ｂ）の実施例では、全部で４９のストリップが探索フレーム内に存在する。
【００９０】
図１０は、探索フレームの最初（すなわち最左端）のストリップ内で選択された候補ブロックを示す。図１０（ａ）から図１０（ｊ）において、探索フレームの左にある番号は、図９（ａ）を参照して説明したバンドに対応している。図１０（ａ）から図１０（ｊ）までに示された陰影部分は、選択された候補ブロックに対応している。選択された候補ブロックは、探索フレーム内のバンドと最初（すなわち最左端）のストリップの交差部分に存在する。注意すべきは、図１０は候補ブロックが選択される方式または順序を示すものではなく、単に探索フレームのストリップ内にある候補ブロックを示しているにすぎないことである。図９を参照して説明したように、探索フレームの各ストリップは４９の異なった候補ブロックを含む。
【００９１】
図１０（ａ）で示されるように、ストリップ内の最初の候補ブロックは、最上部のバンドとストリップとの交差部分にある。図１０（ｂ）、図１０（ｃ）、および図１０（ｄ）は二番目、三番目、および四番目のバンドと最左端のストリップとの交差部分を示す。図１０には示されていないが、バンド５、６、７、および８もストリップと交差して候補ブロックを形成する。図１０（ｅ）はバンド９が最左端のストリップと交差して候補ブロックを形成することを示す。この候補ブロックは図１０（ａ）に示される最初の候補ブロックから８画素行だけ下方で始まり、サブブロック境界に位置している。図１０には示されていないが、バンド１０からバンド１６もストリップと交差し候補ブロックを形成する。図１０（ｆ）はバンド１７と最左端のストリップとの交差を示す。図示されるように、結果として形成される候補ブロックはマクロブロック境界に位置している。図１０（ｇ）および図１０（ｈ）は、それぞれバンド２５と最左端のストリップとの交差、バンド３３と最左端のストリップとの交差を示している。同様に、図１０（ｉ）と図１０（ｊ）は、バンド４１および４９がストリップと交差して候補ブロックを形成することを示す。図１０（ｇ）および図１０（ｉ）に示される候補ブロックはサブブロック境界に位置しており、図１０（ｈ）および図１０（ｊ）に示される候補ブロックはマクロブロック境界に位置している。前述したように、フレーム・サイズが６４ｘ６４である場合、各ストリップには全部で４９の候補ブロックがあり、これらの一部のみが図１０に示されている。
【００９２】
本発明の実施例において、サブブロックの前に計算されたＤＣＴ変換値を最大限に再使用するように、ストリップ内で候補ブロックが選択される。したがって、後で説明するように、候補ブロックの選択は図１０に示された順序では進行せず、前に計算されたＤＣＴ変換値を最大限に再使用するような順序で進行する。
【００９３】
図１１〜図１５：  候補ブロックを選択する（ステップ３０４）
本発明の実施例は、サブブロック境界に位置している（すなわち、８画素行だけ離れている）複数のバンドから構成される「バンド集合」の概念を使用する。したがって、図１０（ａ）、図１０（ｅ）、図１０（ｆ）、１０（ｇ）、図１０（ｈ）、図１０（ｉ）、および１０（ｊ）に示されるバンド１、９、１７、２５、３３、４１、および４９はバンドの１つの集合を形成する。バンド２、１０、１８、２６、３４、および４２はバンドの二番目の集合を形成する。以下同様である。
【００９４】
候補ブロックを選択するステップ３０４の動作は、次の疑似コードで記述することができる。
【００９５】
【表１】
0004082525.tif 000002
【００９６】
前述したように、マクロブロック上でＤＣＴ変換を実行するには、マクロブロックを複数のサブブロックに区分し、これらサブブロックの各々に変換を実行する。したがって、マクロブロックが１６ｘ１６マクロブロックである実施例では、マクロブロックは４つの８ｘ８ブロックに区分され、マクロブロック内の４つのサブブロックの各々へＤＣＴ変換を適用する。
【００９７】
実施例では、バンド集合とは、サブブロック境界で始まる複数のバンドとして定義される。言い換えれば、バンド集合とは、サブブロックの長さだけ離れた複数のバンドとして定義される。それによって、候補ブロックのためのＤＣＴ変換を計算するとき、前に計算された候補ブロックの２つの下部サブブロックの計算済みＤＣＴ変換値を再使用することができる。
【００９８】
図１１は、探索フレームの最左端の（すなわち最初の）ストリップにある最初のバンド集合について候補ブロックが選択される様子を示す。図１１（ａ）では、最初の候補ブロックが選択され、前述したようにしてＤＣＴ変換が実行される。図６のフローチャートで実行される動作の次の繰り返しでは、選択される次の候補ブロックは、図１１（ｂ）で示されるように、バンド集合内の次のバンドと最初のストリップとの交差部分にある。図示されるように、図１１（ｂ）の候補ブロックで実行されるＤＣＴ変換の計算は、図１１（ａ）で計算された最初の候補ブロックの２つの下部サブブロックのＤＣＴ変換値を再使用することができる。言い換えれば、図１１（ａ）で示される最初の候補ブロックの下部サブブロックの８行（すなわち、行９〜１６）は、図１１（ｂ）に示される二番目の候補ブロックの上部行と同じである。したがって、これらの行に対するＤＣＴ変換値は再使用することができ、図１１（ｂ）の候補ブロックのＤＣＴ変換を計算するとき再計算する必要はない。同様に、図１１（ｃ）、図１１（ｄ）、図１１（ｅ）、図１１（ｆ）、および図１１（ｇ）ではサブブロックが重複しているため、これらの候補ブロックのＤＣＴ変換の計算は、前に計算された候補ブロックの２つの下部サブブロックの計算済みＤＣＴ変換値を使用する。
【００９９】
バンド集合とストリップとの交差部分にある候補ブロックが計算された後、図１２に示されるように、ストリップが１つだけ増分され、バンド集合と新しいストリップから新しい候補ブロックが形成される。したがって、図１２（ａ）から図１２（ｇ）までに示されるように、図１１（ａ）から図１１（ｇ）までに示されるバンド集合と同じバンド集合が使用され、このバンド集合と新しいストリップの交差部分に候補ブロックを形成するマクロブロックが選択される。図１２（ａ）から図１２（ｇ）で示されるように、これらの候補ブロックでは、最初の候補ブロックを除いて、２つの上部サブブロックは、前に計算された候補ブロックの２つの下部サブブロックと重複している。したがって、先行する候補ブロックの２つの下部サブブロックのＤＣＴ変換は、新しい候補ブロックのＤＣＴ変換の計算に再使用される。
【０１００】
さらに、ＤＣＴ変換は分離可能であるから、１つのストリップだけ進めることも計算量を削減する。一般的に、ＤＣＴ変換の実行は、まず列を変換し、次に行を変換する。したがって、ストリップが１つだけ増分されたとき、前の列の保存されている変換値が再使用される。それによって、２つの右側サブブロックの各々のために７つの列を再使用することができる。したがって、前に計算された２−Ｄサブブロックと前に計算された１−Ｄ列を再使用することによって計算量が削減される。
【０１０１】
このように、探索フレーム内のバンド集合とすべてのストリップの交差部分に候補ブロックが形成される。ここで図１３を参照すると、バンド集合とストリップ９との交差部分に候補ブロックが形成されるとき、その候補ブロックの左側境界は、図１１で計算された候補ブロックのサブブロック境界と一致する。本発明の実施例では、図１１（ａ）から図１１（ｇ）までの各候補ブロックにある右側サブブロックのＤＣＴ変換値は保存されており、これらのＤＣＴ変換値は図１３（ａ）から図１３（ｇ）までに示された候補ブロックのＤＣＴ変換の計算で使用される。
【０１０２】
バンド集合とストリップのすべてとの交差部分が使用されて候補ブロックが形成された後、選択は新しいバンド集合へ進む。前述したように、最初のバンド集合は１、９、１７、２５、３３、４１、および４９のバンドを含む。選択される次のバンド集合は２、１０、１８、２６、３４、および４２のバンドを含む。この新しいバンド集合と最初のストリップとの交差部分に形成される候補ブロックは図１４に示される。図１１を参照して説明したように、最初の候補ブロックのＤＣＴ変換の計算が図１４（ａ）で実行された後、残りの候補ブロックのＤＣＴ変換の計算は、図１４（ｂ）から図１４（ｆ）までに示されるように、前の候補ブロックの２つの下部サブブロックのＤＣＴ変換値を再使用するので、ＤＣＴ計算は単純化される。注意すべきは、図示されるように、新しいバンド集合とストリップとの交差部分にある候補ブロックは１つだけ少ないことである。
【０１０３】
最初のストリップとの交差部分にある候補ブロックが選択され、ＤＣＴ変換値が計算された後、図１５（ａ）から図１５（ｆ）までに示されるように、バンド集合と新しいストリップとの交差部分に新しい候補ブロックが形成される。このプロセスは各ストリップと各バンド集合について繰り返される。
【０１０４】
したがって、図６のステップ３０４で行われる候補ブロックの選択は、前記の疑似コードに従って進行する。この選択方式によって、前に計算されたＤＣＴ変換値を再使用して、新しく選択された候補ブロックのＤＣＴ変換を計算することができる。それによって、ＤＣＴ変換の計算は単純化され、ＤＣＴ領域で動作する動き予測システムのパフォーマンスは改善される。
【０１０５】
代替の実施例
本発明の１つの実施例において、候補ブロックの選択方法は、バンド集合と類似したストリップ集合の概念を使用する。１つのストリップ集合は、マクロブロックのサブブロック境界に対応して８列の距離だけ離された複数のストリップから構成される。この実施例では、最初の候補ブロックが図１１で計算された後、図１３に示されるように、選択プロセスはマクロブロックのサブブロック境界に位置するストリップ集合の中の次のストリップに進む。したがって、この実施例では、マクロブロックのＤＣＴ変換計算が図１１で実行された後、選択プロセスは図１３（ａ）から図１３（ｇ）までの候補ブロックを次に選択する。これらの候補ブロックの２つの左側サブブロックは、図１１に示される候補ブロックの２つの右側サブブロックと重複している。この実施例では、図１１の候補ブロックの右側サブブロックのＤＣＴ変換値が保存され、図１３（ａ）からず１３（ｇ）までに示される候補ブロックのＤＣＴ計算を実行するときに再使用される。したがって、この実施例では、選択プロセスはバンド集合およびストリップ集合ごとに進行する。
【０１０６】
図１６  −  候補ブロックを選択するフローチャート
ここで図１６を参照すると、そこには本発明に従って図６のステップ３０４で実行される選択方法を示すフローチャートが示される。実施例では、カレント・バンド・カウンタというカウンタが使用されて、候補ブロックを選択するために現在どのバンド集合が使用されているかを示す。後で説明するように、最初のバンド集合とすべてのストリップ集合の交差部分にある候補ブロックが選択されてしまったとき、このカウンタが増分されて新しいバンド集合を指し示す。
【０１０７】
図示されるように、ステップ４０２でストリップが選択される。このフローチャートの開始点で、選択されるストリップはデフォルト値へ設定される。このデフォルト値は、図１１で示されるように探索フレーム内の最初の（すなわち、最左端の）ストリップである。ステップ４０４で、バンドが選択される。前述したように、このフローチャートの開始点で、選択されるバンドはデフォルト値へ設定される。このデフォルト値は最初のバンド集合の最初のバンド（すなわち、図１１（ａ）で示されるバンド１）である。ステップ４０６で、選択プロセスは、選択されたストリップと選択されたバンドの交差部分にある候補ブロックを選択する。
【０１０８】
ステップ４０６で、選択されたストリップと選択されたバンドとの交差部分で候補ブロックが選択された後、選択プロセスは、新しいストリップと新しいバンドとを指定する変数を増分するように進行する。増分ステップが実行されるのは、新しい候補ブロックを選択するために図６のステップ３０４が次に実行されるとき、選択されたストリップと選択されたバンドとの交差部分に基づいて新しい候補ブロックが選択されるようにするためである。
【０１０９】
ステップ４０８で、選択プロセスは、選択された候補ブロック（すなわち、ステップ４０４で選択されたバンド）がストリップの終わりに位置するかどうかを判定する。ストリップの終わりに位置していなければ、このストリップの中でさらに候補ブロックを選択する必要がある。その場合、ステップ４４２で、選択プロセスはストリップ内の次のバンドへ進む。すなわち、バンド長の半分または１つのサブブロックの長さだけ進む。言い換えれば、ステップ４４２で、選択プロセスはバンド集合内の次のバンドへ進む。したがって、たとえば、図１１に示されるように、図１１（ａ）の候補ブロックが選択されたとすると、ストリップの終わりではないから、ステップ４４２で、選択プロセスは「次の」バンドを図１１（ｂ）に示されるバンドになるように設定する。したがって、ステップ４４２は、バンドを設定してバンド集合内の次に連続したバンドになるようにする。ステップ４４２が終わると動作は完了する。したがって、図６のフローチャートで次の繰り返しが実行されて、新しい候補ブロックがステップ３０４で選択されるとき、選択される候補ブロックは図１１から図１５までを参照して説明したようにして決定される。
【０１１０】
ステップ４０８で、候補ブロックがストリップの終わりに位置しているとき、ステップ４１２で、選択プロセスは、候補ブロックが最後のストリップの終わりに位置しているかどうかを決定する。最後のストリップの終わりに位置していなければ、ステップ４３２で、選択プロセスは次のストリップへ進む。ステップ４３４で、バンドはトップ値にカレント・バンド・カウンタの値を加えたものに設定される。前述したように、カレント・バンド・カウンタは、どのバンド集合が候補選択プロセスで使用されているかを識別するために使用される。最初、カレント・バンド・カウンタはゼロのデフォルト値に設定されている。したがって、最初のストリップ内で候補ブロックが選択された後（たとえば、図１１（ａ）から図１１（ｇ）までの候補ブロック）、新しいストリップが選択されると（たとえば、図１２（ａ）から図１２（ｇ）までを参照）、バンドはトップ値にカレント・バンド・カウンタを加えたものに設定される。カレント・バンド・カウンタは最初ゼロへ設定されているから、選択されるバンドは図１２（ａ）に示されるものになる。しかし、バンド集合についてすべてのストリップが使用された後では、後で説明するようにカレント・バンド・カウンタは増分され、バンドはトップ値にカレント・バンド・カウンタ（たとえば、１を含む）を加えたものに設定されるので、図１４（ａ）に示される候補ブロックが選択される。
【０１１１】
ステップ４１２で、候補ブロックが最後のストリップの終わりに位置しているとき、ステップ４１４で、選択プロセスは、カレント・バンド・カウンタの値が７であるかどうかを決定する。ブロックが１６ｘ１６マクロブロックであり、サブブロックが８ｘ８ブロックである実施例では、７に設定されたカレント・バンド・カウンタは、候補ブロックを決定するためにすべてのバンド集合が使用されたことを示す。候補ブロックを決定するためにすべてのバンド集合が使用されたのであれば、現在の候補ブロックが最後のストリップの終わりに位置しているから、探索フレーム内のすべての候補ブロックが選択され使用されている。この場合、図示されるように動作はステップ４１６で終了する。ステップ４１４で、カレント・バンド・カウンタが７に設定されていなければ、動作はステップ４２２へ進む。
【０１１２】
候補ブロックが最後のストリップの終わりに位置していることがステップ４１２で決定されたので、ステップ４２２では、最初のストリップへ戻る処理がなされる。ステップ４２４で、カレント・バンド・カウンタは１だけ増分され、したがって新しいバンド集合が選択される。ステップ４２６で、バンドはトップ値にカレント・バンド・カウンタを加えた値に設定される。このようにして、ストリップのすべてが所与のバンド集合について使用された後（その例の一部が図１１から図１３までに示される）、カレント・バンド・カウンタは、図１４（ａ）から図１４（ｆ）までに示されるような新しいバンド集合を選択するように増分される。
【０１１３】
したがって、本発明に従う動き予測システムは、ＤＣＴ領域で動き予測を実行し、候補ブロックの各々について必要とされるＤＣＴ変換の計算量を削減する新規な候補ブロック選択方法を含んでいる。この候補ブロック選択方法によって、先行する候補ブロックのために計算されたＤＣＴ変換値の再使用が可能となる。したがって、システムのパフォーマンスと効率が改善される。
【０１１４】
図１７  −  関連ブロックを見つける
ここで図１７を参照すると、そこには目標フレーム（たとえば、Ｂフレーム）内で関連ブロックを見つける動き予測システムの動作を示すフローチャートが示される。このフローチャートは図６のステップ３０８で実行される動作を示す。前述したように、図６のステップ３０８は、選択された候補ブロックを含む探索ウィンドウを有する目標ブロックを決定する。所与の目標ブロックについて、その目標ブロックのための探索ウィンドウは、目標ブロックの幅もしくは長さをいずれの方向にもプラスまたはマイナスしたサイズをもつウィンドウであることが望ましい。目標ブロックが１６ｘ１６マクロブロックである実施例では、探索ウィンドウは目標ブロックを取り囲んでいるウィンドウであって、目標ブロックの左方および右方に１６画素、その上方向および下方向に１６画素の境界をもっている。注意すべきは、関連ブロックを見つける方法は、必要に応じて多くのやり方で実施できることである。さらに、必要に応じて、探索ウィンドウの各種のサイズが使用されてよい。
【０１１５】
図示されるように、ステップ５０２では、決定プロセスは、選択された候補ブロックが目標フレーム中にある目標ブロックの行境界の上または列境界の上に位置しているかどうかを決定する。位置していなければ、決定プロセスは周囲の４つのブロックを関連ブロックとして決定する。これは図１８（ａ）で示され、候補ブロックは目標ブロックの行境界の上にも列境界の上にも位置していない。したがって、周囲の４つのブロックが関連ブロックとして選択される。
【０１１６】
図１８（ａ）で示されるように、陰影を付けられた関連目標ブロックの各々は、図示されるような候補ブロックを含む対応する探索ウィンドウを有する。目標フレーム中の他の目標ブロックは、候補ブロックの一部分のみを含むかまったく含んでいない探索ウィンドウを有する。したがって、そのような目標ブロックはその探索ウィンドウの中に候補ブロックを有しない。
【０１１７】
ステップ５０２で、候補ブロックが１つまたは複数の行または列の境界上に位置していると決定されると、ステップ５０６で、候補ブロックが行境界の上にのみ位置しているか、列境界の上にのみ位置しているかが決定される。ステップ５０６で、決定プロセスが、候補ブロックが列境界のみに位置しているか行境界のみに位置していることを決定すると、ステップ５０８で、周囲の６つのブロックが関連ブロックとして決定される。図１８（ｂ）は行境界の上のみに位置している候補ブロックを示し、図１８（ｃ）は列境界のみの上に位置している候補ブロックを示す。図１８（ｂ）および図１８（ｃ）で示されるように、関連目標ブロックは陰影を付けられている。図１８（ｂ）および図１８（ｃ）で示されるように、関連目標ブロックの各々はその探索ウィンドウの中に候補ブロックを含んでいる。図１８（ｂ）および図１８（ｃ）で陰影を付けられていない残りの目標ブロックは、それらの探索ウィンドウの中に候補ブロックを含んでいない。
【０１１８】
ステップ５０６で、候補ブロックが列境界の上のみ、または行境界の上のみに位置していなければ、候補ブロックは、図１８（ｄ）で示されるように、同時に行境界と列境界の上に位置していなければならない。この場合、候補ブロックを取り囲む９つの目標ブロックが関連目標ブロックとして決定される。関連目標ブロックは図１８（ｄ）に示される。注意すべきは、図１８（ｄ）で候補ブロックの真下にある目標ブロックも関連目標ブロックであることである。
【０１１９】
ＤＣＴ領域における動き予測
前述したように、最適マッチ・ブロックを見つける方法は、典型的には空間領域で動作する。このアプローチの問題点は、空間領域で「近接」しているブロックが周波数領域で「近接」しているとはかぎらず、符号化されるのは周波数領域の「距離」であることである。一般的に、量子化テーブルは導入される誤差を制御するので、量子化誤差を認識可能なしきい値の下に保つことが目的になる。したがって、動き予測が空間領域または画素領域で行われるとき、導入される誤差に関して最適化は行われない。最適化は画素値に関して行われるが、誤差は量子化ＤＣＴ領域値の中に導入される。したがって、ＨＶＳは高域周波数における誤差よりも低域周波数における誤差に敏感であるが、再構成された画像に誤差が及ぼす影響に関して、誤差の重みづけはなされない。
【０１２０】
したがって、本発明はＤＣＴ変換値を使用して動き予測を実行することにより、より良好な画像品質と圧縮を達成する。ＤＣＴ領域で動作することにより、本発明の方法はＭＰＥＧ転換動き予測のための最良マッチ・ブロックを決定し、またＭＰＥＧ標準とも合致している。動き予測の理想的な目的は、変換され量子化された差分を伝送するのに必要なビット数を最少にするブロックを見つけることである。最大ビット・レートが与えられると、動き予測はより良好になり、必要なビットは少なくなり、精細度の高い量子化を使用でき、したがって画像品質は良好になる。符号化された誤差が、許容される最大ビット・レートよりも高いレートを必要とすれば、粗い量子化を使用しなければならず、画像の歪みが増加する。本発明の動き予測システムはＤＣＴ領域で動作し、したがって変換され量子化される誤差を伝送するのに必要なビット数を最少化するブロックをより正確に決定する。したがって、真の「最良マッチ」ブロックを見つけだすシステムといえる。
【０１２１】
したがって、本発明の動き予測システムおよび方法を使用するエンコーダは、所与のビット・レートで最大の画像品質を達成する。あるシーン特性に合致するようにデザインされた量子化テーブルのファミリーを使用することが想定されている。シーンが分かれば、テーブルが選択される。このテーブルに関して、本発明の方法は、最大圧縮を達成する参照ブロックを選択する。これは、参照ブロックと目標ブロックとの誤差が変換され、量子化され、最短のストリングへ符号化されるような参照ブロックを選択することによって達成される。本発明は、最適候補ブロックを選択するとき、各誤差の符号化を必要としない、これまでの方式と異なった計量法を使用する。この計量法は、ゼロに量子化される係数の数をカウントする。これは最短ストリングを選択する計量法への近接した予測である。したがって、本発明は、画素領域で動き予測を実行し、動き予測が完了した後に誤差を変換する現在の方法ではなく、ＨＶＳに対して量子化テーブルを最適化し参照ブロックと目標ブロックのＤＣＴ画像に対して動き予測を実行することによって、認識される画像品質を最良にする。
【０１２２】
実施例において、量子化テーブルはＨＶＳの周波数認識能力を考慮して構成される。すなわち、量子化に起因する損失はすべての周波数について認識しきい値(perception thresholds) またはその倍数よりも低くなるようにされる。この方法により、各周波数に対する情報損失は、ＪＮＤ(just noticeable differences) 単位で記述することができる。したがって、画像品質のみを考慮して最大マッチを決定する場合、選択されるブロックは、ブロックあたりの最大単位数を最小にする参照ブロックにするか、ブロックあたりの平均単位数を最小にする参照ブロックにすることができる。量子化された誤差の値を知ることによって、各ブロックに必要な符号化ビットの数は、それを検討しているときに決めることができる。このようなことは、参照ブロックを選択するときに考慮に入れることができる。
ＤＣＴ領域でこのような動き予測を行う場合、画素領域での動き予測よりも多くのブロックが変換される。したがって、次に、必要となる作業を分析し、利用可能性を検討することにする。この分析の一部として、計算の労度と記憶域の間のトレードオフを分析し、これら２つの資源をバランスさせる最適作業点を結論づけることとする。
【０１２３】
通常のＭＰＥＧの場合と同じように、レート制御のストラテジを考察して、最大レートの範囲に収めることとする。本発明のシステムでは、最適ブロックを選択しながらこれらのストラテジを検討することができる。その結果は画像品質を高める。
【０１２４】
ＤＣＴ領域における動き予測の分析
ＭＰＥＧ２  ＭＰ＠ＭＬの制約は、輝度マトリクスの列の数を最大７２０に制限し、行の数を最大５７６に制限し、輝度サンプルの数を最大３４５、６００に制限している（３０フレーム／秒を想定する）。これらの制約では、重複しない（８ｘ８）輝度ブロックの最大数は５４００である。２つの色サンプルの各々は、水平方向および垂直方向で２：１でサブサンプルされる。したがって、色マトリクスは輝度マトリクスのサイズの四分の一であり、したがって最大で２７００（８ｘ８）の重複しない色ブロックが存在する。通常のＭＰＥＧ２符号化では、これらブロックの各々が変換され、フレームあたり８１００・１６＝１２９６００までの１Ｄ  ＤＣＴ変換にすることができる。通常のエンコーダは２７ＭＨｚで動作する１つのＤＣＴ装置を有する。本発明の方法に関連するコストを具体的に計るために、ＤＣＴ装置の数は実施に必要なだけ使用する。１つのＤＣＴ装置は、フレームあたり１２９６００の変換まで計算できると仮定する。ある実施に必要なＤＣＴ装置の数は、フレームあたりに必要な変換の数を１２９６００で除算することによって算定される。
【０１２５】
大まかな仮定とて、輝度の動きは色の動きと同じであるとすると、ＭＰＥＧシンタクスではマクロブロックあたり１つだけの動きベクトル（各方向で）が許される。したがって、輝度の動きだけが予測される。アプリケーションによっては、実際の動きを知っていることが有利であるかもしれないが、ここでは該当しない。唯一の関心事は目標ブロックからの差分が最小の符号化を生じるような参照ブロックを見つけることである。
【０１２６】
この分析のために、ＩフレームとＰフレームが連続して生じるたびに、それらの間には２つのＢフレームが存在するものと仮定する。Ｂフレームの符号化には、次の参照フレーム（ＩまたはＰフレーム）が使用されるから、次のＩフレームは先行するＢフレームの前に符号化される。この「次の」フレームがＰフレームであれば、それは予測を必要とし、したがって余分の変換を必要とする。これらの余分の変換は、Ｂフレームを符号化するときにも必要である。３つのフレームのすべてが同時に符号化されるのであれば、余分の変換は３つのフレーム上でなし崩しに実行することができる。Ｂフレームの符号化を完了するためには、逆方向予測を行う必要がある。すなわち、Ｐフレームの重複した（８ｘ８）ブロックを変換する必要がある。
【０１２７】
比較の基礎は、シーケンスＩＢＢまたはＰＢＢを符号化するのに必要な１Ｄ
ＤＣＴ変換の数である。通常の先行技術による方法では、これら３つのフレームはＩ／Ｐフレームの重複しない（８ｘ８）ブロックの２Ｄ変換と、Ｉ／Ｐフレームの再構成と、２つのＢフレーム中の重複しない（８ｘ８）ブロックの各々の２つの２Ｄ変換を必要とする。各フレームは、最高１２９６００  １Ｄ変換を必要とし、コストは６・１２９６００である。本発明の方法は、３つのすべてのフレーム中の（８ｘ８）ブロックの各々の変換、Ｉ／Ｐフレームの再構成、および過去および将来の参照ブロックのための余分の変換を必要とする。この余分の計算をＸで表せば、必要なＤＣＴ装置の数は次のようになる。
【０１２８】
【数１】
（２Ｘ＋４・１２９６００）／（６・１２９６００）
【０１２９】
注意すべきは、将来の参照フレームがＰフレームであれば、それは実際には２つのＢフレームと共に符号化されるが、（８ｘ８）ブロックの変換動作は、次のＰＢＢのセットでカウントされる。
【０１３０】
通常のＭＰＥＧでは、Ｐフレームが符号化される間、２つのＢフレームを記憶しておく必要がある。本発明でも、それが必要である。しかし、通常のＭＰＥＧが一時に１つのフレームを符号化するのに対して、本発明は一時に３つのフレームを符号化する。それによって、おそらく２つの追加の符号化バッファを必要とする。
【０１３１】
注意すべきは、３つ以上のＢフレームがＩ／Ｐフレーム間に存在する場合には、参照の変換はもっと多くのフレーム上でなし崩しに行われ、したがって必要なＤＣＴ装置の数が少なくなることである。しかし、必要な記憶域は多くなる。
【０１３２】
最適ブロックを見つけるのに必要な作業を見積もる場合、目標ブロックのプラス・マイナス１６画素の近隣で全面的探索が実行されるものと仮定する。もしＭＰＥＧが絶対差分に注目し、本発明が０へ量子化される係数の数を探すのであれば、作業の負荷は同じである。
【０１３３】
ＤＣＴ領域における動き予測の演算所要量
このサブセクションでは、余分のＤＣＴ計算を実行するのに必要な作業と、本発明に従ってＤＣＴ領域で動き予測を実行するときに必要な余分の記憶域について分析する。従来または先行技術のＭＰＥＧ方式では、目標ブロックはラスタ・スキャンの順序で考察され、各ブロックは、最適マッチを見つけるためにすべての参照ブロックまたは候補ブロックと比較される。しかし、前述したように、本発明の方法は反対のアプローチを採用する。すなわち、本発明では、参照ブロックまたは候補ブロックは、ラスタ・スキャンの順序ではなく一時に１つだけ考慮される。参照ブロックが目標ブロックの近隣に存在している場合、その目標ブロックは参照ブロックまたは候補ブロックと比較される。各目標ブロックは、それまで見つけられた最良の参照ブロックへのポインタと、その参照ブロックの適合値を保存する。
【０１３４】
この分析では、ｒおよびｃは、それぞれフレーム中の行と列の数を表す。さらに、バンドは１６の連続した行として定義される。バンドは、最上部から最下部にかけて１から（ｒ−１５）の番号を振られている。
【０１３５】
図１９は、ＤＣＴ計算の数と、対応するメモリ記憶所要量を描いたグラフである。図示されるように、曲線上の最初の点では、最小限の記憶域でよいが最多のＤＣＴ計算が必要である。まず、最初のバンド中の重複する（１６ｘ１６）ブロックの４つの（８ｘ８）変換が計算され、次に二番目のバンドの重複する（１６ｘ１６）ブロックの４つの（８ｘ８）変換が計算され、以下同様にして最下部のバンドまで計算される。現在の４つの（８ｘ８）変換済みブロックのほかに必要な余分の記憶域は、３０の変換された（８ｘ１）列である。これは２次元に変換される前の、現在の（１６ｘ１６）ブロックの１５の右側列の上部半分と下部半分である。必要な余分の記憶域は３０・８＝２４０  ＤＣＴ係数である。
【０１３６】
各バンドに必要な作業は、バンド内の８ｘ１列について２ｃの変換であり、（ｃ−１５）の重複する（１６ｘ１６）ブロックの各々について３２行の変換である。（ｒ−１５）のバンドが存在するので、全体の作業は、
【０１３７】
【数２】
（ｒ−１５）（２ｃ＋３２（ｃ−１５））
＝  ３４ｒｃ−４８０ｒ−５１０ｃ＋７２００        （１）
【０１３８】
等式（１）の最大値は、ｒとｃが１６の倍数として１１、１６０、０００である（ｒ＝４８０およびｃ＝７２０とする）。したがって、必要なＤＣＴ装置の数は、
【０１３９】
【数３】
(2・11,160,000＋ 4・129600）／(6・129600）＝29.37
【０１４０】
これは計算という観点からは非常に効率が悪い。なぜなら、８行離れているバンドが４つの（８ｘ８）ブロックの２つを共有し、８列離れている同じバンド中の（１６ｘ１６）ブロックも４つの（８ｘ８）ブロックの２つを共有するからである。
【０１４１】
記憶域を増加させることによって計算を減少させる第一のステップとして、本発明の方法は、図１３を参照して前に説明したように、新しい候補ブロックのＤＣＴ変換を計算するとき、前に計算された候補ブロックの右側サブブロックを再使用する。２つの右側（８ｘ８）変換済みブロックは、バンド中で８つの連続した重複する（１６ｘ１６）ブロックに記憶される。バンド中でｊ番目の（１６ｘ１６）ブロックの２つの右側（８ｘ８）ブロックは、（ｊ＋８）番目の（１６ｘ１６）ブロックの２つの左側ブロックであるから、これらの（８ｘ８）は再計算される必要はない。
【０１４２】
各バンドの中で、作業は次のようになる。
・最初の（１６＋７）列：  これらの列は最初の８つの重複する（１６ｘ１６）ブロックを含む。これらブロックの各々は、変換される必要のある４つの（８ｘ８）ブロックを有する。関連する作業は２・２３の列変換と８・４・８の行変換である。
【０１４３】
・残りの（ｒ−２３）列：  これらの列は残りの（ｃ−８−１５）の重複する（１６ｘ１６）ブロックを含む。これらブロックの各々については、２つの左側（８ｘ８）ブロックはすでに変換されている。残り（ｃ−２３）の重複するマクロブロックの各々に必要な作業は、２列の変換と１６行のｓ変換である。
【０１４４】
（ｒ−１５）のバンドがあって、全体の作業負荷は、
【０１４５】
【数４】
(r-15)(2・23+256+2(c-23)+16(c-23))=18rc-112r-270c+1680      （２）
【０１４６】
記憶域所要量は２・７変換列と２・８変換（８ｘ８）ブロックであり、全部で１４ｘ８＋１６・６４＝１１３６の記憶されるＤＣＴ係数となる。
【０１４７】
等式（２）の最大値５，９７４，３２０は、ｒ＝４８０およびｃ＝７２０のときに得られる。必要なＤＣＴ装置の数は、
【０１４８】
【数５】
(2・5,974,320 ＋ 4・129600）／(6・129600）＝16.30
【０１４９】
さらに記憶域を付け加えて計算を減らすために、本発明の方法は新しい候補ブロックのＤＣＴ変換を計算するときに前の計算済み候補ブロックの２つの下部サブブロックを再使用する。これについては、図１１から図１５までを参照して説明した。ｊ番目のバンドの下部の（８ｘ８）ブロックは（ｊ＋８）番目のバンドの上部ブロックである。順序外のバンドを処理する場合、本発明の方法はまず８を法として１と合同である番号のバンドへ行き、次に８を法として２と合同である番号のバンドへ行く。以下同様である。各バンド集合について、下部の（８ｘ８）ブロックの変換が記憶される。この方式では、（ｃ−２３）の左側の（１６ｘ１６）ブロックが、それらの下部右側の（８ｘ８）を計算されて記憶される。さらに、各集合の最初のバンドを変換するとき、上部右側の（８ｘ８）と２つの下部（８ｘ８）を記憶するのに十分の記憶域が存在する。したがって、これらのバンド内の右側（ｃ−２３）（１６ｘ１６）ブロックについて、２つの（８ｘ８）のみを計算する必要がある。したがって、実際の作業は次のようになる。
【０１５０】
・各集合中の最初のバンド：
−  最初の２３列：  ２・２３列の変換に８・４・８行変換を加えたもの。
−  残りの（ｃ−２３）列：  ２・（ｃ−２３）列変換に２・８（ｃ−２３）行変換を加えたもの。
【０１５１】
・残りの（ｒ−２３）バンド：
−  最初の２３列：  ２３列変換に８・２・８行変換を加えたもの。
−  残りの（ｃ−２３）列：  （ｃ−２３）列変換に（ｃ−２３）・８行変換を加えたもの。
【０１５２】
合計は次のようになる。
【０１５３】
【数６】
8(46+256+(c-23)(2+16))+(r-23)(23+128+(6-23)9)
= 9rc-56r-63c+392                     （３）
【０１５４】
等式（３）の最大値は３，０３８，５５２である（ｒ＝４８０およびｃ＝７２０のとき）。必要なＤＣＴ装置の数は、
【０１５５】
【数７】
(2・3,038,552 ＋ 4・19600)／(6・129600）＝8.48
【０１５６】
回路周波数が５４ＭＨｚに増加された場合、５つのＤＣＴ装置で十分である。
【０１５７】
前述したように、本発明の方法は１６の連続した列をストリップとして定義する。ストリップは左から右へ１から（ｃ−１５）までの番号を割り振られる。バンド集合を符号化するとき、処理は最上部から最下部へ進む。すなわち、符号化は集合の最上部バンドで始まり、最下部バンドで終わる。さらに、符号化の順序は斜め方向に進行することができる。すなわち、最初に集合と最初のストリップの交差部分が符号化され、次に二番目のストリップとの交差部分が符号化される。以下同様である。２つの方式で必要とされる変換の数は同じであるが、行の数は列の数よりも少ないので、バンド集合を上部から下部へ符号化する方が記憶域を節約する。
【０１５８】
必要な作業は次のとおりである。
最初の８ストリップと各集合内の最初のバンド：  これは最初の８つの重複する（１６ｘ１６）ブロックをカバーする。必要な作業は２・２３の列変換と８・４・８の行変換である。
【０１５９】
各集合の最初のバンドにおける残りの（ｃ−１５−８）ストリップ：各々の新しい（１６ｘ１６）ブロックの中で、２つの左側の（８ｘ８）が、右側の（８ｘ８）内の７つの左側列と同じように計算され記憶された。したがって、作業は２列変換と２ｘ８行変換である。
【０１６０】
残りのバンド内の最初の８ストリップ：  ２つの上部（８ｘ８）が計算され記憶された。下部の（８ｘ８）のみを変換すればよい。必要な作業は２３列変換と８・２・８行変換である。
【０１６１】
残りのバンド内の残りの（ｃ−１５−８）：  上部の２つおよび下部の左側（８ｘ８）が、下部の右側（８ｘ８）の７つの左側列と同じように計算され記憶された。したがって、作業は１つの列変換と８つの行変換である。
全体の作業は、
【０１６２】
【数８】
8(46+256+18c-46-16＼cdot23)+(r-15-8)(23+128+9c-9・23)
9rc-56r-63c+392
【０１６３】
これは等式（３）と等しい。
前述した方式と同じように、データは一時に１つの集合についてだけ記憶すればよい。集合の最初のバンドについては、８つの連続したブロックの２つの右側（８ｘ８）と、これら（８ｘ８）における右側の１４変換済み列を記憶する必要がある。残りのバンドについては、７列と８ブロックが必要である。（ｒ−１５）＝（ｒ−１６＋１）のバンドが存在し、ｒは１６で除算可能である。したがって、バンドの数は最初の集合で（ｒ−１６）／８＋１であり、残りの集合で（ｒ−１６）／８である。最初の集合はより多くのバンドを含み、したがってその記憶域所要量は次のようにして計算される。
【０１６４】
【数９】
0004082525.tif 000003
【０１６５】
最後の方式は最も有効であると考えられ、最適実施例である。最適ブロックが探索された近隣は、ＤＣＴ計算にも余分の記憶域所要量にも影響がないことに注意されたい。近隣の選択の影響は、通常の方式と同じく、最適マッチを見つけるのに必要な作業の中だけにある。
本発明の動き予測システムは、画素領域方式と比較すると、次の追加の資源が必要である。第一に、画素領域方式は１つの符号化バッファを必要とするのに対して、本発明は３つの符号化バッファを必要とする。さらに、画素領域方式は１つのＤＣＴ装置を必要とするのに対して、本発明は５つのＤＣＴ装置を必要とする。さらに、本発明は３４，０８０のＤＣＴ係数（４８０ｘ７２０のフレーム・サイズを仮定する）のために追加のメモリを必要とする。参照ブロックを評価するとき、画素領域方式では目標ブロックのプラス・マイナス１６画素近隣が包括的に探索されるが、その探索は、同じ近隣でゼロへ量子化される係数を本発明がカウントすることと等価である。
【０１６６】
結論
したがって、本発明のシステムと方法は、圧縮されていないディジタル・ビデオ・ストリームから動き予測ベクトルを生成する。本発明は周波数領域またはＤＣＴ領域で動き予測を実行することによって、パフォーマンスを改善し演算所要量を削減する。
【０１６７】
実施例を参照して本発明のシステムと方法を説明したが、本発明はここに開示された特定の形式に制限されるものではなく、特許請求の範囲に記載される発明の範囲内に合理的に含まれるような代替、変更、および等価の発明をもカバーするものである。
【図面の簡単な説明】
【図１】本発明に従いＤＣＴ領域で動き予測を実行するビデオ・エンコーダを備えることによってビデオ圧縮を実行するコンピュータ・システムを示す図である。
【図２】図１のコンピュータ・システムを示すブロック図である。
【図３】先行技術に従うＭＰＥＧエンコーダを示すブロック図である。
【図４】先行技術に従って、目標フレーム内の目標ブロックが探索フレームの探索ウィンドウの中で複数の候補ブロックを横切って掃引される、目標フレームと探索フレームとの間のブロック・マッチング動き予測の動作を示す図である。
【図５】本発明に従うＭＰＥＧエンコーダの１つの実施例を示すブロック図である。
【図６】本発明の動作を示すフローチャートである。
【図７】本発明の動作を示すフローチャートである。
【図８】探索フレーム内の候補ブロックと目標フレーム内の目標ブロックとを示す図である。図８（ａ）は、４つのサブブロックに区分されたマクロブロックを示す図である。
【図９】図９（ａ）および図９（ｂ）は、それぞれ参照フレーム内のバンドとストリップを示す図である。
【図１０】図１０（ａ）から図１０（ｊ）までは、参照フレームのストリップの中にある候補ブロックを示す図である。
【図１１】本発明に従って行われる候補ブロックの選択を示す図である。
【図１２】本発明に従って行われる候補ブロックの選択を示す図である。
【図１３】本発明に従って行われる候補ブロックの選択を示す図である。
【図１４】本発明に従って行われる候補ブロックの選択を示す図である。
【図１５】本発明に従って行われる候補ブロックの選択を示す図である。
【図１６】候補ブロックの選択を示すフローチャートである。
【図１７】目標フレーム内の関連ブロックの決定を示すフローチャートである。
【図１８】候補ブロックと、それに関連した「関連」目標ブロックの例を示す図である。
【図１９】メモリ記憶域所要量に対して描かれたＤＣＴ計算の数を示す図である。
【図１】
0004082525.tif 000004
【図２】
0004082525.tif 000005
【図３】
0004082525.tif 000006
【図４】
0004082525.tif 000007
【図５】
0004082525.tif 000008
【図６】
0004082525.tif 000009
【図７】
0004082525.tif 000010
【図８】
0004082525.tif 000011
【図９】
0004082525.tif 000012
【図１０】
0004082525.tif 000013
【図１１】
0004082525.tif 000014
【図１２】
0004082525.tif 000015
【図１３】
0004082525.tif 000016
【図１４】
0004082525.tif 000017
【図１５】
0004082525.tif 000018
【図１６】
0004082525.tif 000019
【図１７】
0004082525.tif 000020
【図１８】
0004082525.tif 000021
【図１９】
0004082525.tif 000022