(57)【特許請求の範囲】
【請求項１】
ビデオ符号化アプリケーションで動き推定を行う方法であって、該方法は、
ａ）  ソース・フレーム内の選択されたソース・ブロックのロケーションに対して、ターゲット・フレーム内の複数のターゲット・ブロックの中でマッチング・ブロックの探索（サーチ）を開始する開始ロケーションを見つけるステップと、
ｂ）  前記ソース・フレームからの前記ソース・ブロック内のピクセル・ロケーションにあるピクセル値と、前記ターゲット・フレーム内の前記複数のターゲット・ブロックの第１のターゲット・ブロック中の対応するピクセル・ロケーションにあるピクセル値との間の誤差信号データを計算するステップであって、前記第１のターゲット・ブロックは、前記開始ロケーションに置かれているステップと、
ｃ）  前記開始ロケーションに置かれている前記第１のターゲット・ブロックに対する動きベクトルデータと前記誤差信号データとから結合探索基準の測定量を計算するステップと、
ｄ）  前記ターゲット・フレーム内でスパイラル・パスに沿って探索中の前記複数のターゲット・ブロックの一つまたは複数の後続ターゲット・ブロックの各々に対し、
前記後続ターゲット・ブロックに関連付けられた前記動きベクトルデータを符号化するために必要とされるビット数の測定量を計算するステップと、
前記動きベクトルデータを符号化するために必要とされるビット数の前記測定量と最小結合探索基準測定量とを比較して、前記マッチング・ブロックの前記探索を終了するかどうかを決定するステップと、
前記動きベクトルデータを符号化するために必要とされるビット数の前記測定量が、前記最小結合探索基準測定量より大である場合は、前記最小結合探索基準測定量に関連付けられた前記ターゲット・ブロックの前記動きベクトルデータを、前記ソース・ブロックの符号化に使用される前記動きベクトルデータとして選択するステップと、
さもなければ、前記後続のブロックに対しステップｂおよびステップｃを繰り返し、前記最小結合探索基準測定量を維持するステップと
を含むことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記結合探索基準測定量は、前記結合探索基準測定量に関連付けられた前記ターゲット・ブロックに対する前記動きベクトルデータの符号化に必要なビット数の測定量を算入することを特徴とする方法。
【請求項３】
請求項２に記載の方法において、前記結合探索基準測定量は、
Ｋは符号化されるビデオ・シーケンスについて選択された定数、
Ｑｓは量子化ステップ、
Ｂｉｔｓ（動きベクトル）は前記動きベクトルデータの符号化に必要なビット数の前記測定量、および
ＳＡＤは、前記ソース・ブロック内の前記ピクセル値と、前記結合探索基準測定量に関連付けられた前記ターゲット・ブロック内の対応するピクセル値との差分の絶対値の総和として表された誤差信号データ、とした際に、
Ｋ＊Ｑｓ＊Ｂｉｔｓ（動きベクトル）＋ＳＡＤ
で表されることを特徴とする方法。
【請求項４】
請求項１に記載の方法において、前記開始ロケーションは、前記ソース・フレームに含まれる前記ソース・ブロックの近隣ブロックについて以前に計算された動きベクトルから計算されることを特徴とする方法。
【請求項５】
請求項１に記載の方法において、前記スパイラル探索パスは、前記ターゲット・フレーム内のブロック・ロケーションの順序付けられたシーケンスを含み、前記開始ロケーションの後の後続するブロック・ロケーションは、開始ロケーションからの距離が増加する位置に置かれていることを特徴とする方法。
【請求項６】
請求項１に記載の方法において、さらに、
前記ソース・フレーム内の前記ソース・ブロックに隣接するブロックの少なくとも１つの動きベクトルから前記開始ロケーションを予測するステップと、
前記予測開始ロケーションが最大動きベクトル・サイズによって制限されていないときは、第１のスパイラル探索パスを使用し、
前記予測開始ロケーションが最大動きベクトル・サイズによって制限されているときは、前記第１のスパイラル探索パスのシフトされた探索順序を使用するステップと
を含むことを特徴とする方法。
【請求項７】
請求項１に記載の方法において、さらに、
前記ソース・フレームからセグメント化された任意形状のオブジェクトにオーバーラップするソース・ブロックについて、前記ステップａ〜ｄを繰り返すステップを含むことを特徴とする方法。
【請求項８】
請求項１に記載の方法において、さらに、
前記ソース・フレーム内のソース・ブロックについて、前記ステップａ〜ｄを繰り返すステップを含むことを特徴とする方法。
【請求項９】
ビデオ・シーケンスにおける動き推定のためのブロック・マッチングの方法を実行する命令が格納されているコンピュータ読取可能媒体であって、前記方法は、
ソース・フレームのソース・ブロックについて、ターゲット・フレームの複数のターゲット・ブロックの中からマッチングするターゲット・ブロックを探索するステップであって、探索される各々のターゲット・ブロックについて、
前記探索されるターゲット・ブロックに対する動きベクトルデータを符号化するために必要とされるビット数の第１の測定量を計算するステップ、
前記動きベクトルデータと誤差信号データとの単位の差異を調整するように、量子化ステップのサイズに依存する量子化係数で前記ビット数の第１の測定量を重み付けするステップ、および
前記探索されるターゲット・ブロックの探索基準の第２の測定量を、前記重み付けされたビット数の第１の測定量に少なくとも部分的に基づいて計算するステップ
を含む探索ステップと、
前記探索されるターゲット・ブロックに対するそれぞれの第２の測定量に基づいて前記マッチングするターゲット・ブロックを選択するステップと
を含み、
前記複数のターゲット・ブロックが探索される際の順序をスパイラル探索パターンが制御し、
探索される各々のターゲット・ブロックの第２の測定量は、前記探索されるターゲット・ブロックと前記ソース・ブロックとの間の誤差信号データにも少なくとも部分的に基づき、探索される各々のターゲット・ブロックについて、前記探索ステップは、さらに、
前記探索されるターゲット・ブロックの前記重み付けされたビット数の第１の測定量が、以前に探索されたターゲット・ブロックの最良な第２の測定量を超えていれば、前記探索を終了させるステップを含むことを特徴とするコンピュータ読取可能媒体。
【請求項１０】
請求項９に記載のコンピュータ読取可能媒体において、探索される各々のターゲット・ブロックの前記第２の測定量は、前記探索されるターゲット・ブロックと前記ソース・ブロックとの間の誤差信号データにも、少なくとも部分的に基づいていることを特徴とするコンピュータ読取可能媒体。
【請求項１１】
請求項９に記載のコンピュータ読取可能媒体において、探索される各々のターゲット・ブロックについて、前記探索ステップは、さらに、
定数によりビット数の前記第１の測定量を重み付けするステップを含み、前記定数は、ビデオ・シーケンス全体にわたって符号化コストを低減するように最適化されていることを特徴とするコンピュータ読取可能媒体。
【請求項１２】
請求項９に記載のコンピュータ読取可能媒体において、前記方法は、さらに、
前記スパイラル探索パターンをシャッフルして、動きベクトル・サイズの制約に対して調整するステップを含むことを特徴とするコンピュータ読取可能媒体。
【請求項１３】
ビデオ・エンコーダであって、
ソース・フレーム内のソース・ブロックに対するターゲット・フレーム内の複数のターゲット・ブロックの中のマッチング・ブロックをスパイラル探索パスに沿って探索する手段であって、前記ターゲット・フレーム内の前記複数のターゲット・ブロックのうちの一つまたは複数のターゲット・ブロックに対する動きベクトルデータと誤差信号データとから結合探索基準測定量を計算する手段を含み、現在のターゲット・ブロックに対する前記動きベクトルデータを符号化するために必要とされるビット数の測定量が、前記ターゲット・フレーム内の以前のターゲット・ブロックの中の最良の結合探索基準測定量を超えた場合にスパイラル探索を停止し、探索の停止後に、前記最良の結合探索基準測定量に基づいて、前記ターゲット・フレーム内の前記複数のターゲット・ブロックの中から前記マッチング・ブロックを選択する、探索手段、および
前記ソース・ブロックを、選択されたマッチング・ブロックの動きベクトルデータに少なくとも部分的に基づいて、符号化する手段
を備えることを特徴とするビデオ・エンコーダ。
【発明の詳細な説明】
【０００１】
（技術分野）
本発明はビデオ符号化に関し、具体的には、ビデオ符号化アプリケーションで動き推定を行うための改良方法に関する。
【０００２】
（発明の背景）
アナログビデオ信号をベースとするフル・モーション・ビデオ・ディスプレイは、長期間にわたってテレビジョンの形で利用されてきた。近年、コンピュータの処理能力が進歩し、コンピュータが手ごろな値段で入手可能になったことに伴い、デジタル・ビデオ信号をベースとするフル・モーション・ビデオ・ディスプレイが幅広く利用されるになっている。デジタル・ビデオ・システムは、従来のアナログ・ビデオ・システムに比べると、フル・モーション・ビデオ・シーケンスの創作、変更、伝送、保管、およびプレイ（再生）の面で大幅に向上している。
【０００３】
デジタル・ビデオ・ディスプレイは、３０Ｈｚから７５Ｈｚまでの範囲の周波数で連続的にプレイまたはレンダリング（rendering）される画像フレーム（image frame）を非常に多数含んでいる。各画像フレームは、特定のシステムのディスプレイ解像度に基づくピクセル配列（array of pixels）から形成された静止画像（still image）になっている。いくつかの例を挙げると、ＶＨＳベースのシステムでは、ディスプレイ解像度が３２０ｘ４８０ピクセルに、ＮＴＳＣベースのシステムでは、ディスプレイ解像度が７２０ｘ４８６ピクセルに、開発段階にある高精細テレビジョン（high-definition televisionＨＤＴＶ）ベースのシステムでは、ディスプレイ解像度が１３６０ｘ１０２４ピクセルになっている。
【０００４】
ビデオ・シーケンスに含まれる生（raw未処理）デジタル情報量は非常に大量である。このような大量のビデオ情報を保管し、伝送することは、従来のパーソナル・コンピュータ機器では実現不可能である。たとえば、３２０ｘ４８０ピクセル解像度を有する相対的に低解像度のＶＨＳ画像フォーマットをデジタル化した場合を考えてみる。この解像度で、持続時間が２時間のモーション・ピクチャ（動画）の全長は、１００ギガ・バイトのデジタル・ビデオ情報に相当している。これに比べて、従来のコンパクト光ディスクは容量が０．６ギガ・バイトであり、磁気ハードディスクは容量が１−２ギガ・バイトであり、開発段階にあるコンパクト光ディスクは容量が最大８ギガ・バイトである。
【０００５】
このような大量のデジタル・ビデオ情報を保管または伝送するときの制約を解消するために、さまざまなビデオ圧縮標準またはプロセスが確立されており、その中には、ＭＰＥＧ−１、ＭＰＥＧ−２、およびＨ．２６Ｘが含まれている。これらのビデオ圧縮手法は、時間的またはインターフレーム（フレーム間）相関（temporal or interframe correlation）と呼ばれる、連続する画像フレーム間の類似性を利用してインターフレーム圧縮を得ており、そこではフレーム間の変化を符号化（エンコード）するために動きデータ（motion data）と誤差信号が使用されている。
【０００６】
さらに、従来のビデオ圧縮手法は、空間的またはイントラフレーム（フレーム内）相関（spatial or intraframe correlation）と呼ばれる、画像フレーム内の類似性を利用してイントラフレーム圧縮を得ており、そこでは画像フレーム内の画像サンプルが圧縮されている。イントラフレーム圧縮は、離散コサイン変換（discrete cosine transformＤＣＴ）符号化のように、静止画像を符号化する従来のプロセスに基づいている。このタイプの符号化は、「テクスチャ（texture）」または「変換(transform)符号化とも呼ばれている。ここで「テクスチャ」とは、広い意味では、色差（chrominanceクロミナンス）値と輝度（luminanceルミナンス）値の配列（アレイ）やアルファ（不透明）値の配列のように、画像サンプル値の２次元配列のことである。また、ここで言う「変換」という用語は、符号化プロセスの過程で画像サンプルがどのように空間的周波数成分に変換されるかを表している。ここで使用している「変換」という用語は、ある種のインターフレーム圧縮手法でシーン変化を推定するために使用される幾何的変換（geometric transform）とは区別しておく必要がある。
【０００７】
インターフレーム圧縮では、動き推定（motion estimation）と動き補償（motion compensation）を利用して、フレーム間のシーン変化を推定しているのが代表的である。動き推定とは、フレーム間の画像サンプル（たとえば、ピクセル）の動きを推定するプロセスである。動き推定を使用して、符号器（encoder−エンコーダ）は、あるフレーム内のピクセルのブロックを別のフレーム内の対応するピクセルと突き合わせることを試みる。最も類似するブロックが所与のサーチ・エリアで見つかると、対応するピクセルのピクセル・ロケーションの置換が近似化され、動きベクトル（motion vector）のような動きデータとして表される。動き補償とは、予測画像（predicted image）を決定し、その予測画像とオリジナル画像との誤差を計算するプロセスである。動き補償を使用して、符号器は動きデータを画像に適用し、予測画像を計算する。予測画像と入力画像との差分は、誤差信号と呼ばれている。誤差信号は、画像サンプル値間の差分を表す値の配列にすぎないため、この誤差信号は、画像サンプルをイントラフレーム符号化するときに使用されるのと同じテクスチャ符号化手法を使用して圧縮することができる。
【０００８】
具体的実装方法に違いがあるとしても、ＭＰＥＧ−１、ＭＰＥＧ−２、およびＨ．２６Ｘビデオ圧縮標準には類似する面がいくつかある。以下ではＭＰＥＧ−２ビデオ圧縮標準が説明されているが、その説明は全体的には他のビデオ標準にも当てはまるものである。
【０００９】
ＭＰＥＧ−２では、ビデオ画像内のピクセルの四角ブロックまたは配列に基づいてインターフレーム圧縮とイントラフレーム圧縮を得ている。ビデオ画像は、１６ｘ１６ピクセルの寸法をもつマクロブロック（macroblock）と呼ばれる、画像サンプル・ブロックに分割されている。ＭＰＥＧ−２では、マクロブロックは、４つの輝度ブロック（各ブロックは８ｘ８輝度（Ｙ）サンプルからなる）と２つの色差ブロック（ＣｂとＣｒごとに８ｘ８サンプル・ブロック）を含んでいる。
【００１０】
ＭＰＥＧ−２では、インターフレーム符号化はマクロブロックについて行われている。ＭＰＥＧ−２符号器は、動き推定と動き補償を行って動きベクトルとブロック誤差信号を計算している。画像フレームＮ内の各々のブロックＭＮごとに、つぎに続くビデオ・フレームＮ＋１に、または直前の画像フレームＮ−１の画像に渡って（つまり、双方向に）サーチが行われ、最も類似するそれぞれのブロックＭＮ＋１またはＭＮ−１を特定している。最も類似するブロックのブロックＭＮに対する位置が、動きベクトル（ＤＸ，ＤＹ）を使用して符号化される。そのあと、動きベクトルは予測サンプル値のブロックを計算するために使用される。これらの予測サンプル値はブロックＭＮと比較され、ブロック誤差信号が求められる。誤差信号は、離散コサイン変換（ＤＣＴ）符号化などの、テクスチャ符号化手法を使用して圧縮される。
【００１１】
オブジェクト・ベースのビデオ符号化手法は、従来のフレーム・ベース符号化標準の改良版として提案されたものである。オブジェクト・ベース符号化では、任意形状画像フィーチャは、「セグメンテーション(segmentation）」と呼ばれる手法を使用してビデオ・シーケンス内のフレームから分離されている。ビデオ・オブジェクト、つまり、「セグメント」は独立に符号化されている。オブジェクト・ベース符号化によると、連続フレーム内のビデオ・オブジェクト間のインターフレーム相関が大きくなるので、圧縮レートを向上することができる。また、オブジェクト・ベース符号化は、ビデオ・シーケンス内のオブジェクトにアクセスし、それをトラッキング（追跡）していく必要のある種々のアプリケーションで利用すると、便利である。
【００１２】
ＭＰＥＧ−４標準用に提案されているオブジェクト・ベースのビデオ符号化手法では、ビデオ・オブジェクトの形状、動きおよびテクスチャは独立に符号化されている。オブジェクトの形状は、ビデオ・フレーム内の任意形状オブジェクトの境界（boundary）を定義している１つのバイナリ（binary）またはアルファ（alpha）マスクで表されている。オブジェクトの動きは、長方形フレームから分離されたオブジェクトの任意形状画像に適用されることを除けば、ＭＰＥＧ−２の動きデータに類似している。動き推定と動き補償は、フレーム全体ではなく、「ビデオ・オブジェクト・プレーン」のブロックに対して行われる。ビデオ・オブジェクト・プレーン（video object plane）とは、シングル・フレーム内のオブジェクトの形状画像を表す名前である。
【００１３】
ビデオ・オブジェクトのテクスチャは、オブジェクトの形状の内側に位置するビデオ・オブジェクト・プレーン内の画像サンプル情報である。オブジェクトの画像サンプルと誤差信号のテクスチャ符号化は、フレーム・ベース符号化で行われるのと類似のテクスチャ符号化手法を使用して行われる。たとえば、セグメント化画像は、マクロブロックから形成された境界長方形（bounding rectangle）内にはめ込むことが可能である。境界長方形で形成された長方形画像は、透明マクロブロックは符号化の必要がないことを除けば、長方形フレームと同じように圧縮することができる。部分的に透明なブロックは、サンプル値を有するそのオブジェクトの形状境界（boundary）外側を「パディング（padding埋め込み）」と呼ばれる技法でそのブロックのその部分を満たしたあと符号化されている。
【００１４】
フレーム・ベース符号化とオブジェクト・ベース符号化のどちらの場合も、動き推定のプロセスは、符号化プロセスのスピードとビデオ品質の両面で符号化システムの重要な部分となっている。Ｈ２６３とＭＰＥＧ−４のどちらの符号化標準も、マクロブロックについて動き推定を行っている。動き推定プロセスの目標は、動き補償のあと誤差信号が最小となるようなマクロブロックを、参照ピクチャ（reference picture−参照画像）の中から見つけることである。誤差信号を最小化することによって、符号器は、マクロブロックの符号化に必要なビット数を最小限にすることを試みる。しかし、誤差信号を符号化することのほかに、符号器は、マクロブロック・ヘッダと動きベクトルも符号化しなければならない。誤差信号を最小化することは、その誤差信号の符号化に必要なビット数が最小限化するかも知れないが、マクロブロック全体の符号化が最大限に効率化されるとは限らない。
【００１５】
（発明の概要）
本発明は、動き推定を行うための改良方法を提供している。本発明の一側面は、ブロックに関する動きパラメータ（たとえば、動きベクトル）を選択するために動きと誤差の結合データ（combined motion and error data）の測定量を使用して、ことによって符号化効率を向上する、動き推定を行う方法である。この修正探索基準（modified search criteria）は、誤差信号と同様にブロックに関する動きパラメータに関連付けられたオーバー・ヘッドを考慮に入れている。
【００１６】
一実施形態による符号器（encoder）では、動き推定プロセスにおいてピクセルの合致する（マッチング）ブロックを見つける探索基準として、動きと誤差信号データ結合された測定量を使用している。ブロック・マッチング方式を使用して、符号器は、ソース・フレーム内のソース・ブロックに対応するマッチング・ブロックを、ターゲット・フレームの中から探し出している。この探索の目的は、ソース・ブロックに対する動きと誤差信号の結合符号化オーバー・ヘッドを最小限にするピクセル・ブロックをターゲット・フレームの中から見つけることである。この修正探索基準を使用することで、符号器はより良い符号化効率を実行することができる。
【００１７】
本発明の別の側面は、マッチング・プロセスで効率のよい探索パス(search path）を選択することによって符号化スピードを向上する、ピクセル・ブロックマッチングを行う方法が提供される。具体的には、この方法によれば、ブロック・マッチング・プロセスで使用される探索順序（search order）は、望みの開始ポイント（desired starting point）（たとえば、予測ポイント）に近いピクセルが、その望みの開始ポイントから遠く離れた個所にあるピクセルよりも先に探索されるような順序になっている。
【００１８】
ＭＰＥＧ−４符号化標準用に設計された実施形態では、上記アプローチが使用されて、望みの開始ポイントに近いブロックが最初に探索されるようにターゲット・フレーム内のブロックの探索順序をシフトしている。ＭＰＥＧ−４のような符号化標準では、動きベクトル・サイズを制限する制約があり、そのことが探索開始ポイントと言えない結果に至らしめるため、探索パスを最適化する必要性が生じている。その探索の開始ポイントが最適でないのは、動きベクトルがサイズで制限されていることから派生する理由に起因している。その探索順序をシフトさせることは、最適開始ポイントとは言えないという問題を解消する。
【００１９】
最後に、本発明の別の側面によれば、ピクセル・ブロックに対する動きパラメータを計算するために必要な探索量を低減する探索パスと探索基準を使用して、ブロックマッチングを行う方法が提供されている。この方法の一実施形態は、スパイラル探索パス（spiral search path）を使用し、その概要を上述した修正探索基準が使用されている。この修正探索基準の属性に基づいて、符号器は、探索エリア内のすべてのターゲット・ブロックを探索せずに、修正探索基準を最小限とするターゲット・ブロックを見つけたかどうかを判断することができる。したがって、このアプローチによると、ブロック・マッチング・プロセスでの探索が高速化されるので、符号器のパフォーマンスが向上することになる。
【００２０】
本発明のその他の特徴と利点は、本発明の実施形態を詳述している以下の説明と添付図面に示されているとおりである。
【００２１】
（詳細な説明）
（序論）
以下の最初のセクションでは、ビデオ符号器（エンコーダ）と復号器（デコーダ）の説明が記載されている。そのあとに続くセクションでは、本発明による符号器がどのように実現されているかが説明されている。この実施形態による符号器は、ピクセルのブロック（たとえば、ビデオ符号化標準ＭＰＥＧ−４とＨ２６３に定義されているマクロブロック）を符号化することを特に目的としている。予測フレームに対するマクロブロックの各々は、ヘッダパラメータ、動きベクトル、およびテクスチャ符号化誤差信号を含んでいる。この実施形態による符号器は、ブロック・マッチング・プロセスでマッチング（合致する）ブロックを探索するとき、動きと誤差の結合データの測定量を使用することによって符号化効率を向上している。このアプローチによると、特定の動きパラメータに関連付けられた符号化オーバー・ヘッドの全体像が考慮されるので、符号化効率が向上されている。また、この実施形態による符号器は、改良修正探索パターンを使用し、動きベクトルを見つけるために必要な探索量を低減するので、高速化されている。
【００２２】
本発明は、以下に説明されている符号器の具体的実施形態と共に、フレーム・ベースのビデオ符号化にも、ブロック・ベースのビデオ符号化にも適用される。オブジェクト・ベースの符号器と復号器は、フレーム・ベースの符号器と復号器がもつ特徴のすべてを備えているので、以下の説明は、フレーム・ベースの符号化方式でも、オブジェクト・ベースの符号化方式でも、本発明がどのように実現されるかを理解するのに十分な基礎を提供している。
【００２３】
（例示する符号器と復号器の説明）
図１は、オブジェクト・ベースのビデオ符号器の実施形態を示すブロック図である。符号器への入力３０は、各フレーム内のビデオ・オブジェクト、各ビデオ・オブジェクトの形状、および境界長方形（bounding rectangle）を表している画像（イメージ）を含んでいる。形状情報は、符号器がテクスチャ・データまたは動きデータを符号化する前に利用可能になっている。フレーム・ベースの符号化がオブジェクト・ベースの符号化と異なるのは、フレーム全体が形状情報なしで符号化され、入力３０が一連の画像フレームからなっている点である。
【００２４】
形状符号化モジュール３２は、その境界長方形を含むオブジェクトの定義を受け取り、境界長方形をマクロブロックの整数倍数に延長する。オブジェクトの形状情報は、マスクまたは「アルファ・プレーン(alpha plane）」を含んでいる。形状符号化モジュール３２はこのマスクを読み取り、たとえば、従来のチェーン符号化（chain coding）手法を使用してオブジェクトの輪郭（contour）を符号化することによってマスクを圧縮する。
【００２５】
動き推定モジュール３４は、その境界長方形を含むオブジェクトと以前に再構築された画像３６とを読み取り、あるフレームから別のフレームへのオブジェクトの動きを予測するために使用される動き推定データを計算する。動き推定モジュール３４は、現オブジェクト画像内の各々のマクロブロックごとに再構築画像内の最も類似するマクロブロックを探し出し、各々のマクロブロックごとに動きベクトルを計算する。動き推定モジュール３４からの動きデータの具体的フォーマットは、使用される動き推定手法に応じて変化させることが可能である。以下に説明している実施形態では、各々のマクロブロックごとに動きベクトルがあり、これは、現行ＭＰＥＧとＨ２６Ｘのフォーマットに準拠している。
【００２６】
動き補償モジュール３８は、動き推定モジュールによって計算された動きベクトルと以前に再構築された画像３６を読み取り、現フレームの予測画像を計算する。予測画像内の各ピクセルは、動きベクトルがそこに置かれている、マクロブロックの動きベクトルを使用して、以前に再構築された画像３６内の対応するピクセルを見つけることによって構築される。そのあと、符号器は、入力３０の中で指定されている、入力画像ブロック内の画像サンプル値と、動き補償モジュール３８で計算されたときの、予測画像ブロック内の対応するサンプル値との差分を求め、マクロブロックの誤差信号を決定する。
【００２７】
テクスチャ符号化モジュール４０は、インターフレーム（フレーム間）符号化オブジェクトについては、この誤差信号を圧縮し、イントラフレーム（フレーム内）符号化オブジェクトについては、入力データストリーム３０からのオブジェクトに対する画像サンプル値を圧縮する。テクスチャ符号化モジュール４０からのフィードバック路４２は、誤差信号を表している。符号器は、誤差信号ブロックと、動き補償モジュールからの予測画像マクロブロックとを併用して、以前に再構築イメージ（画像）３６を計算する。
【００２８】
テクスチャ符号化モジュール４０は、イントラフレームのブロックとオブジェクトに対する誤差信号データを、各種の静止画像圧縮手法のいずれかを使用して符号化する。圧縮手法の例としては、ＤＣＴやウェーブレット（wavelet）のほかに、従来の画像圧縮方法がある。
【００２９】
圧縮ビデオ・シーケンスのビット・ストリームは、形状符号化モジュール、動き推定モジュール、およびテクスチャ符号化モジュールからの形状、動きおよびテクスチャ符号化情報を含んでいる。マルチプレクサ４４はこのデータを結合し、正しいシンタックス（系統的配列）になるようにフォーマッティングし、それをバッファ４６に出力する。
【００３０】
符号器はハードウェアでも、ソフトウェアでも実現できるが、ソフトウェアで実現されることが最も多い。ソフトウェアで実現する場合には、符号器内のモジュールは、コンピュータのメモリに格納され、プロセッサで実行されるソフトウェア命令と、メモリに格納されたビデオ・データとを表している。ソフトウェアによる符号器（エンコーダ）は、従来の種々コンピュータ読取可能媒体に格納し、配布することができる。ハードウェアで実現する場合には、符号器内のモジュールはデジタル・ロジック、好ましくは、集積回路に実装されている。符号器がもつ機能のいくつかは、ホストコンピュータから処理負担を解放するように、コンピュータ周辺装置内に特定目的デジタル・ロジック・デバイスの形で、最適化することができる。
【００３１】
図２は、オブジェクト・ベースのビデオ符号化手法のための復号器（デコーダ）を示すブロック図である。デ・マルチプレクサ６０は、圧縮ビデオ・シーケンスを表しているビット・ストリーム６２を受け取り、形状、動きおよびオブジェクト・ベースに基づくオブジェクト上のテクスチャ符号化データに分離する。デ・マルチプレクサは、各マクロブックの動きベクトルをシングル可変長符号から再構築する動きベクトル復号器も含んでいる。
【００３２】
形状復号化モジュール６４は、処理される現オブジェクト用の形状または輪郭を復号化する。これを行うために、このモジュールは、図１の符号器で使用されている形状符号化方法の逆の方法を実装している形状復号器を採用している。その結果として生成された形状データは、オブジェクトの形状を表しているバイナリ・アルファ・プレーンまたはグレー・スケール・アルファ・プレーンのように、マスクになっている。
【００３３】
動き復号化モジュール６６は、ビット・ストリームに含まれる動き情報を復号する。復号された動き情報には、入力ビット・ストリーム内のエントロピー符号から再構築される各マクロブロック用の動きベクトルが含まれている。動き復号化モジュール６６は、この動き情報を動き補償モジュール６８に渡し、動き補償モジュール６８はその動きデータを使用して、以前に再構築されたオブジェクト・データ７０の中から予測画像サンプルを探し出す。
【００３４】
テクスチャ復号化モジュール７４は、インターフレーム符号化テクスチャ・データの誤差信号と、イントラフレーム・テクスチャ・データのカラー値の配列とを復号し、この情報をモジュール７２に渡し、再構築画像の計算と累算が行われる。インターフレーム符号化オブジェクトの場合は、このモジュール７２は誤差信号データを、動き補償モジュールからの予測画像出力に適用し、現フレームに対する再構築オブジェクトが計算される。イントラフレーム符号化オブジェクトの場合は、テクスチャ復号化モジュール７４は、オブジェクトの画像サンプル値を復号化し、再構築オブジェクトを再構築オブジェクト・モジュール７２の中に置いておく。以前に再構築されたオブジェクトは一時的にオブジェクト・メモリ７０に格納しておき、他のフレームのオブジェクトを構築するために使用される。
【００３５】
符号器と同じように、復号器はハードウェアでも、ソフトウェアでも、あるいはその組み合わせでも実現することができる。ソフトウェアで実現する場合には、復号器内のモジュールは、コンピュータのメモリに格納され、プロセッサで実行されるソフトウェア命令になっている。ソフトウェアの復号器（デコーダ）は、従来の種々コンピュータ読取可能媒体に格納し、配布することができる。ハードウェアで実現する場合には、復号器のモジュールはデジタル・ロジック、好ましくは、集積回路に実装されている。復号器がもつ機能のいくつかを、ホストコンピュータから処理負担を解放するように、コンピュータ周辺装置内に特定目的デジタル・ロジック・デバイスの形で、最適化することができる。
【００３６】
（動き推定とブロックマッチング・パターンの改善）
符号器の実施形態を詳細に説明する前に、動き推定プロセスの例を説明することから始めることにする。図３は、単純なビデオ・シーケンスにおけるソース・フレームとターゲット・フレーム３００、３０２の例である。各フレームは、フォアグラウンド（前景）オブジェクト（動いているヘッド３０４）とバックグランド（背景）オブジェクト３０６（たとえば、バックグランドの静止ハウスとツリー）を含んでいる。動き推定のプロセスは、ターゲット・フレームに対するソース・フレーム内のピクセルの動きを近似化する。これを行うために、符号器内の動き推定器（motion estimator）は、ソース・フレーム内のソース・ピクセル・ブロック３０８とターゲット・フレーム内の探索エリア３１０を選択する。ターゲット画像内の探索パスをたどっていきながら、動き推定器は、ソース・ブロック内のピクセル値を、探索エリア３１０内の領域の対応するロケーションに置かれているピクセル値とマッチング（突き合わせ）する。探索パス上の各ステップで、動き推定器は誤差信号を計算する。この誤差信号は、ソース・ブロック内のピクセル値と、探索エリア内の対応するロケーションに置かれたピクセル値との差分測定量を示している。この誤差信号は、絶対差分の和（sum of absolute differences ＳＡＤ）として計算されるのが代表的である。このプロセスはブロック・マッチング（block matching−ブロック突き合わせ）とも呼ばれているが、これはソース・ブロックに最も緊密に合致するピクセル・ブロックが探索で探し出されるからである。
【００３７】
マッチング・ブロックを特定したあと、動き推定器は、各ソース・ピクセルとターゲット・フレーム内の対応するピクセル・ロケーションとの間の動きを定義している動きパラメータを使用して、ソース・フレーム内のピクセルの動きを近似化する（見積もる）。動きパラメータは、各ピクセルについても、ピクセル・ブロックについても符号化することができる。ケースによっては、動きパラメータは、ソース・フレームからターゲット・フレームへのピクセルまたはピクセル・ブロックを記述している幾何変換（たとえば、アフィン変換（affine transform）または透視変換（perspective transform）の係数になっている場合がある。これらの係数は、あるピクセル・ブロックに対する参照ポイントの動きを記述している、一連の動きベクトルとして符号化することができる。そのあと、復号器は、参照ポイントから動き係数を導き出す。別のアプローチによる方法では、ソース・ブロックに含まれる全ピクセルの平行移動の動き（translation motion）を記述しているシングル（単一の）動きベクトルが、ソース・フレーム内のピクセル・ブロックごとに選択される。
【００３８】
符号器と復号器のどちらも、動きパラメータを同じ方法で使用してソース画像内の各ピクセルについて予測ピクセルを計算する。予測ピクセルはソースピクセルに完全に合致していないので、符号器のコンポーネントである動き補償器は、予測ピクセルと、それに対応するソースピクセルとの差分として誤差信号を計算する。ソース・フレームに含まれる各ピクセルの実際のピクセル値を符号化するのではなく、符号器は、動きパラメータ、ターゲット・フレーム内のピクセル、および動き補償コンポーネントで計算された誤差信号を符号化する。
【００３９】
符号器の実施形態によると、ターゲット・エリア内のマッチング・ピクセルブロックを選択するために修正選択基準を使用することによって、インター符号化（inter-coded）ビデオ画像の符号化効率と品質を向上している。この修正選択基準は、インターフレーム・ブロックに対する動きと誤差信号の結合された測定量である。符号器の実施形態によれば、ＭＰＥＧ−４およびＨ２６３符号化標準と同じブロック・サイズとブロック・フォーマットを使用しており、これらのブロックはマクロブロックと呼ばれている。
【００４０】
ハイ・レベルでは、動きと誤差信号の結合測定量は、次式で表すことができる。
ＣＯＭＢＩＮＥＤ＿ＭＥＡＳＵＲＥ＝Ａ＊Ｂｉｔｓ（動きベクトル）＋ＳＤ
【００４１】
上記において、Ａは、動きベクトル（Ｂｉｔｓ）の符号化に必要なビット数の測定量を調整するためのパラメータ、ＳＤは差分の和である。符号器の実施形態では、ＳＤは差分の絶対値の和である。パラメータAは２つの問題を取り扱っている。第一に、このパラメータは、符号化される画像に対して使用される量子化ステップ（quantization step）に依存する重み付けコンポーネントを含んでいる。動きベクトルと誤差信号は異なる単位で表されているので、この重み付けコンポーネントは、単位に差異があるとき、量子化ステップの関数としてその差異の調整を行っている。第二に、パラメータＡは、符号化されるビデオ・クリップ（video clip）のビット数を低減するように計算される定数を含んでいる。この定数は、インターフレーム・マクロブロックの符号化に必要なビット数を最小限にする定数の値を見つけることをビデオ・クリップに対して実験することによって選択されている。
【００４２】
その概要を上述した実施形態の詳細によると、動きと誤差信号の結合データの測定量は、修正された絶対差分の和として表すことができる。
修正ＳＡＤ＝Ｋ＊Ｑｓ＊Ｂｉｔｓ（動きベクトル）＋ＳＡＤ
【００４３】
上記において、Ｋは、ビデオ・クリップに対するインタフレーム・ビット数を低減するように最適化された定数、Ｑｓは、量子化ステップを調整するフレーム単位のパラメータ、Ｂｉｔｓは、符号化されるソース・イメージ内のピクセル・ブロックに対する動きベクトルの符号化に必要なビット数の測定量、ＳＡＤは、ソース・ブロックの画像サンプルと、ターゲット・ブロック内の対応するロケーションに置かれた画像サンプル値との差分の絶対値の和である。動きベクトルは、ターゲット・ブロックがソース・ブロックに対して置かれている相対的ロケーションを定義している。
【００４４】
実験で明らかになったことは、修正ＳＡＤの上式によると、ＳＡＤだけに基づくブロックマッチングに比べて、インターフレーム・マクロブロックの符号化オーバー・ヘッドが低減されることである。具体的には、修正ＳＡＤによると、動きビデオ・シーンが少ないときのパフォーマンスが向上する（つまり、ＳＡＤは相対的に小さくなる傾向がある）。
【００４５】
ブロックマッチングを行うための新基準は、ターゲット・エリア内にマッチング・ブロックを探し出すために使用されている。この探索はターゲット・フレームの探索エリア内の開始ロケーションから始まり、探索パスに沿って進められていく。探索パス上の各ステップで、動き推定モジュールは動きと誤差信号の結合データの測定量を査定する。単純化のために、この量は結合探索基準（Combined Search Criteria ＣＳＣ）と呼ぶことにする。探索の目的は、探索エリアに置かれているターゲット・ピクセルブロックに対するＣＳＣ値を最小限にすることである。
【００４６】
探索を始める前に、符号器は探索開始ロケーションを選択する。好ましくは、開始ロケーションは、動きベクトルは近隣ブロックについて計算されるということに基づいて選択される。近隣ブロックの動きは着目するブロックに類似する傾向があるので、近隣動きベクトルに基づく開始ポイントは、探索エリア内のマッチング・ブロック付近で次の探索を開始する可能性がある。図４は、近隣マクロブロック４０４−４１０で囲まれた現マクロブロック４００とその動きベクトル４１４−４２０を示す図である。動き推定モジュールは、現ブロックの予測子（predictor）を計算することによって開始ロケーションを計算する。予測子は、左ブロック４１０、上ブロック４１６そして上右ブロック４１８のＸとＹの動きベクトル・コンポーネントのメディアン（ｍｅｄｉａｎ）として計算される。これら候補ブロックのＸコンポーネントのメディアンはＸコンポーネントの予測子であり、これらブロックのＹコンポーネントのメディアンはＹコンポーネントの予測子である。
【００４７】
開始ロケーションを計算したあと、動き推定モジュールは探索パスに沿ってステップして行き、探索パス上のステップに位置しているターゲット・ブロックに対するＣＳＣを評価する。具体的には、符号器の実施形態では、スパイラル探索パス（spiral search path）が使用されており、そこでは、各探索ステップは開始ロケーションから離れるように移動していく。図５は、図３に示す探索エリア５００の拡張バージョンにおけるスパイラル探索パスの例を示す図である。最初のターゲット・ブロック５０２は開始ロケーションのほぼ中央に置かれており、これは予測子動きベクトル５０４によって定義されている。ドット（たとえば、５０６、５０８）は、スパイラル探索パス上のステップの例である。
【００４８】
図６は、符号器の実施形態におけるスパイラル探索パスのステップの例を示す詳細図である。各番号は、探索パスの１ステップに対応している。探索パスの開始ポイントは、多くの場合、動きベクトル予測子によって定義されたロケーションになっている。
【００４９】
好ましくは、探索パスのステップは、開始ロケーションからの距離が離れて行く順序になっている。以下で詳しく説明するように、このような順序にすると、ブロック・マッチング・プロセスが探索エリアで全数探索（exhaustive search）を行うことなくマッチング・ブロックを特定できるので、探索が最適化されることになる。符号器の実施形態は、ＭＰＥＧ−４符号化標準に準拠する設計になっている。ＭＰＥＧ−４では、動きベクトルのサイズに制約があるため、動きベクトル予測子は、スパイラル探索に都合のよい開始ポイントを表しているとは限らないことがある。
【００５０】
上記問題を分かりやすく説明するために、図６に示す例を検討することにする。なお、そこでは、破線の動きベクトル６００は探索を行うのに望ましい開始ロケーションを表し、実線の動きベクトル６０２はＭＰＥＧ−４標準で動きベクトルのサイズに制約があることに起因する動きベクトルを表している。動きベクトル予測子６００で示されたポイントから探索を開始するのではなく、探索は制約された動きベクトル６０２で示されたポイントから開始せざるを得ない。
【００５１】
この制約を解消する１つの方法は、ターゲット・エリアにおけるロケーションの探索順序を、望ましい開始ポイント（たとえば、動きベクトル予測子のポイント）からのロケーション別にソートする（並べ換える）ことである。しかし、この方法によると、動き推定のための処理オーバー・ヘッドが増加することになる。
【００５２】
もう１つの方法は、符号器の実施形態で使用されているもので、最も一致しているものに近い可能性のあるブロックが最初に探索されるように探索順序をシャッフル（shuffle）またはシフトすることである。具体的には、符号器は、予測子ポイントに近いターゲット・ブロックが最初に探索されるように探索順序をシャッフルする。
【００５３】
このアプローチによる方法を理解しやすくするために、図６に示す例を検討することにする。ブロック・マッチング・プロセスのオリジナル探索順序は、｛１、２、３、．．．、４８｝になっている。
【００５４】
シフトされた探索順序は、｛１５、１６、１７、１８、．．．、４８、１４、１３、１２、．．．、１｝である。
【００５５】
この実施形態では、シフトされた探索順序は２つのステップで計算される。すなわち、最初に、望ましいスパイラル探索センタ（つまり、望ましい開始ポイント）と予測ポイントとの距離が計算される。ここで、予測ポイントが望ましい開始ポイントとは異なるロケーションにあるのは、動きベクトル・サイズに制約があるためである。つぎに、この距離に対する、新しい事前計算開始ポイントがルックアップされる。このルック・アップ（look up）オペレーション（目的地の方角に向ける操作）の結果として、探索順序における新しい開始インデックス（たとえば、上記の例では１５）が得られる。
【００５６】
この探索順序の調整（修正）は、スパイラル探索の望ましい開始ポイントが予測ポイントとは異なっている場合に行われる特殊ケースである。望ましい開始ポイントは、動きベクトル・サイズが制約されることなく、上述したように、近隣動きベクトルのＸコンポーネントとＹコンポーネントのメディアンを見つけることによって計算される。予測ポイントは、符号化標準で動きベクトル・サイズが制限されていることを除けば、同じように計算される。その結果、動きベクトル・サイズの制約が予測ポイントを計算するために使用される動きベクトルのサイズに縮小を生じさせた場合、望ましい開始ポイントと予測ポイントは、異なったものになる。
【００５７】
この実施形態では、事前計算された開始ポイントがテーブル内に格納されている。すなわち、最初のステップで計算された距離が与えられ、シフトされた探索順序の最初のブロックに対する開始インデックスが、このテーブルから得られるようになっている。上に示した例では、開始インデックスは、１から４８の範囲から選択される数値になっており、この場合、各インデックスはスパイラル探索順序の探索ポイントに対応している。
【００５８】
この実施形態におけるテーブルの定義は、次式で表すことができる。
新開始インデックス＝Ｆ（ｄ）；
ここで、ｄはステップ１で計算された距離である。
【００５９】
距離ｄが与えられているとき、関数Ｆ（ｄ）からはインデックスｙが戻され、各インデックスｉがｉ＞ｙであるときは、インデックスｉに対する探索ロケーションのスパイラル探索センタＰ0と座標Ｐｉとの距離は、常に（ｄ１）より大か、等しく、各インデックスｉがｉ＜ｙであるときは、ＰｉとＰ0との距離は常に（ｄ１）より小か、等しくなるようになっている。
【００６０】
表現の仕方を変えると、テーブルは次のように定義されている。
Ｆ（ｄ）＝ｙ；ｉ＞ｙのとき、Ｄｉｓｔａｎｃｅ（Ｐ0，Ｐｉ）≧（ｄ１）；
および、      ｉ＜ｙのとき、Ｄｉｓｔａｎｃｅ（Ｐ0，Ｐｉ）＜（ｄ１）
【００６１】
この新探索順序は、元の順序による場合よりも早期に望ましい開始ポイントに最も近いポイントを探索することができる。この代替アプローチによると、望ましい開始ポイントが予測ポイントと異なるとき、その開始ポイントからの距離別に探索順序をソートするという、余分の処理オーバー・ヘッドが回避されることになる。
【００６２】
符号器の実施形態によれば、結合探索基準（たとえば、修正ＳＡＤ）をスパイラル探索と併用することによって、動き推定プロセスのスピードを向上させる。ＣＳＣの１つの属性は、探索パスの終わりに達しなくても、ブロック・マッチング・プロセスが探索を終了できることである。この属性は、探索プロセスが次のような特徴をもっている結果である。
１）ＣＳＣは動きベクトルのサイズを取り入れている。
２）スパイラル探索パスは各ステップに比例して動きベクトルのサイズを大きくして行く。
この特徴を分かりやすく説明するために、ＣＳＣの次式を検討することにする。
ＣＯＭＢＩＮＥＤ＿ＭＥＡＳＵＲＥ＝Ａ＊Ｂｉｔｓ（動きベクトル）＋ＳＤ
【００６３】
スパイラル・センタから離れて行くステップの数が増加すると、動きベクトルの符号化に必要なビット数も増加して行く。
各ステップでのＣＳＣの最小値は次の通りである。
ＣＳＣｍｉｎ＝Ａ＊Ｂｉｔｓ（動きベクトル）
【００６４】
この結果は、ＳＤの値がゼロになる場合を生じさせる。動きベクトルの符号化に必要なビット数はスパイラル探索パスのステップに比例して増加していくことから、ＣＳＣの最小値もステップごとに増加して行く。
【００６５】
ＣＳＣｍｉｎ（ｉ＋１）≧ＣＳＣ（ｉ）、ただし、ｉはスパイラル探索パスのステップである。
【００６６】
スパイラル探索には上述した属性をもっているため、ブロック・マッチング・プロセスは、現ＣＳＣｍｉｎがそのポイント（ＣＳＣｓｔｏｒｅｄ）までに見つかった最小ＣＳＣより大か、等しくなっているポイントで探索を終了することができる。具体的には、ポイントｓのＣＳＣｍｉｎが次のように存在していれば、
【００６７】
ＣＳＣｍｉｎ（ｓ）≧ＣＳＣｓｔｏｒｅｄ
探索パスにおけるｓより大きいすべてのｉについては、
すべてのｉが＞ｓのときＣＳＣ（ｉ）≧ＣＳＣｍｉｎ（ｓ）≧ＣＳＣｓｔｏｒｅｄとなる。
【００６８】
変数ＣＳＣｓｔｏｒｅｄは、スパイラル探索パスでそれまでに探索した探索ポイントのいずれに対しても、ＣＳＣの最小の値を有する。この特徴を利用するために、この実施形態の符号器では、それまでに見つかったＣＳＣの最小値の情報を得て、それを現ステップのＣＳＣｍｉｎと比較する。現探索ポイントのＣＳＣｍｉｎがＣＳＣｓｔｏｒｅｄより大か、等しければ、探索は中止され、ＣＳＣ値の最小値を生じさせた探索ポイントが使用される。
【００６９】
図７は、この実施形態による符号器のオペレーションを示すフロー図である。この図には、符号効率と符号化スピードを向上する、上述した特徴が具現化されている。図７に示すように、符号器は探索開始ポイントを計算することから開始する（ステップ７００）。このステップでは、符号器は、上述したように近隣ブロックの動きベクトルから動きベクトル予測子を計算する。予測動きベクトルが、ＭＰＥＧ−４符号化標準における動きベクトル・サイズの制約のために制限されていれば（判定ステップ７０２）、符号器は探索順序をシフトする。具体的には、符号器は、実際の予測ポイントの近くに置かれたターゲット・ブロックが、動きベクトル・サイズの制約を原因とする予測ポイントのロケーションの近くに置かれているブロックよりも先に評価されるように探索順序をシフトする（ステップ７０４）。
【００７０】
つぎに、符号器は、ステップ７０４で決定された探索順序にしたがってブロック・マッチング・プロセスを開始する。探索パス上の各ターゲット・ブロックについて、符号器は、ソース・ブロック内のサンプル値とターゲット・ブロックの差分の絶対値の和（ＳＡＤ）を計算する（ステップ７０６）。つぎに、符号器は、修正ＳＡＤと名付けた動きベクトルと誤差信号の結合データの測定量を計算する（ステップ７０８）。この実施形態では、この量は修正ＳＡＤと呼ばれ、最小修正ＳＡＤと現ブロックのＳＡＤを結合したものであり、この場合、ブロックの最小修正ＳＡＤは次のように計算される。
修正ＳＡＤｍｉｎ＝Ｋ＊Ｑｓ＊Ｂｉｔｓ（動きベクトル）その結果、
修正ＳＡＤ＝修正ＳＡＤｍｉｎ＋ＳＡＤ
この修正ＳＡＤの計算の詳細は図８に示されている。
【００７１】
ＳＡＤが小さくなっている（たとえば、動きシーンが少ない）アプリケーションでは、探索は、現ブロックの最小修正ＳＡＤが、格納された修正ＳＡＤ値よりも大か、等しいとき中止させることができる。探索を続けるかどうかを決定するために、符号器は、現ターゲット・ブロックの現最小修正ＳＡＤを、格納された修正ＳＡＤ値と比較する（ステップ７１０）。現修正ＳＡＤｍｉｎがそれまでに見つかった最小ＳＡＤよりも小であれば、符号器は、格納された修正ＳＡＤ値を更新し（ステップ７１２）、探索パスの次のポイントへ進む（ステップ７１４）。初期時には、格納された修正ＳＡＤ値は、最初に探索されるブロックの修正ＳＡＤにセットされる。探索パスの後続するターゲット・ブロックでは、格納された修正ＳＡＤ値は、現修正ＳＡＤが以前に格納された値よりも小であれば、現修正ＳＡＤにセットされる。図７に示すように、探索は、現ブロックの修正ＳＡＤがそれまでに見つかった修正ＳＡＤの最低値より大であれば中止される。
【００７２】
図８は、図７に示す方法を採用している動き推定器（motion estimator）８００の実施形態を示すブロック図である。動きベクトル予測器（motion vector predictor）８０２は予測動きベクトルを計算することを表している。これは近隣ブロックの動きベクトルを受け取り、現ブロックの予測動きベクトルを計算する。探索パス・コントロール（search path control）８０４はこの予測動きベクトルを使用して、ターゲット・フレームの探索エリアにある、マッチング・ブロックを探索する開始ポイントを決定する。探索パス・コントロールへの入力ＴＡＲＧＥＴとＳＯＵＲＣＥはターゲット画像とソース画像である。ソース画像内の各ソース・ブロックについて、探索パス・コントロールはターゲット画像内の探索開始ロケーション、およびターゲット画像内のターゲット・ブロックの探索順序とロケーションを計算する。探索順序は、予測動きベクトルで特定されたポイントからスパイラル・パスをたどって行く。予測動きベクトルのサイズが、動きベクトルのサイズに制約があるために制限されていれば、探索パス・コントロールは、シフトされた探索順序を上述したように選択する。
【００７３】
減算器（subtractor）８０６は、探索パスで指示された通りに、ソース・ブロック内のピクセル値と現ターゲット・ブロック内のピクセル値との差分を、計算される。ＳＡＤ累算器（accumulator）８０８は差分を加算し、現ブロックの和を累算する。
【００７４】
動き推定器は、探索パス上の現在位置の動きベクトルに基づく動きベクトル・ビット数に起因するオーバー・ヘッドを査定する。探索の各ステップは、それに関連付けらた動きベクトルを有している。この動きベクトルのサイズが分かっていれば、動き推定器は、現ステップの動きベクトルに起因するビット数を計算することができる。そのあと、動きベクトルのオーバー・ヘッド（たとえば、動きベクトルの符号化に必要なビット数）を定数Ｋと量子化ステップＱｓによって調整する。乗算器８１０は、現ステップの最小修正ＳＡＤをＢｉｔｓ（動きベクトル）＊Ｋ＊Ｑｓとして計算する。
【００７５】
現ブロックの最小修正ＳＡＤ値（修正ＳＡＤｍｉｎ）は、上述したように探索をそのまま続けるかどうかを判断するために使用できる。具体的には、比較器８１２は、現ブロックの修正ＳＡＤｍｉｎを格納された修正ＳＡＤ値と比較する。修正ＳＡＤｍｉｎが格納値より大か、等しければ、動き推定器は探索を中止し、ＳＡＤ値が最小であるターゲット・ブロックを使用して現マクロブロックの動きベクトルを計算することができる。
【００７６】
動き推定器は、各ターゲット・ブロックの修正ＳＡＤを、最小修正ＳＡＤ（Ｋ＊Ｑｓ＊Ｂｉｔｓ（動きベクトル））と現ブロックのＳＡＤの和として計算する。そのあと、動き推定器は、それまでに見つかった最小修正ＳＡＤ（修正ＳＡＤｓｔｏｒｅｄ）を、その最低値を生じたターゲット・ブロックの動きベクトルと一緒に記録しておく。図８に示す第２比較器８１６は、各ターゲット・ブロックが評価されたあと探索で見つかった最低修正ＳＡＤ値を更新するプロセスを表している。探索が終了すると、最低修正ＳＡＤ値をもつターゲット・ブロックに関連する動きベクトルは、マクロブロックに対して符号化される。
【００７７】
（コンピュータ・システムの概要説明）
図９と以下の説明は、本発明を実現するのに適しているコンピューティング環境の概要を要約して説明したものである。本発明または本発明のいくつかの側面はハードウェア・デバイスで実現することが可能であるが、上述してきた符号器（エンコーダ）と復号器（デコーダ）は、プログラム・モジュール構造の、コンピュータ実行可能命令で実現されている。プログラム・モジュールには、タスクを実行し、上述したデータタイプを実装しているルーチン、プログラム、オブジェクト、コンポーネント、およびデータ構造が含まれている。
【００７８】
図９は、デスクトップ・コンピュータの代表的な構成を示しているが、本発明はその他のコンピュータ・システム構成で実現することも可能であり、その中には、ハンドヘルド・デバイス、マルチ・プロセッサ・システム、マイクロ・プロセッサ・ベースまたはプログラマブル・コンシューマ・エレクトロニクス、ミニ・コンピュータ、メインフレーム・コンピュータなどが含まれている。また、本発明は、通信ネットワークを通してリンクされているリモート処理デバイスによってタスクが実行されるような、分散コンピューティング環境で使用することも可能である。分散コンピューティング環境では、プログラム・モジュールは、ローカルとリモートの両方のメモリ・ストレージ・デバイスに置いておくことができる。
【００７９】
図９は、本発明の動作環境として働くコンピュータ・システムの例を示す図である。コンピュータ・システムは、処理ユニット９２１、システム・メモリ９２２、およびシステム・メモリを含む種々のシステム・コンポーネントを処理ユニット９２１に相互接続するシステム・バス９２３を内蔵しているパーソナル・コンピュータ９２０を含んでいる。システム・バスは、ＰＣＩ、ＶＥＳＡ、マイクロチャネル（Microchannel MCA）、ＩＳＡ、ＥＩＳＡなどのバス・アーキテクチャを使用している、数種類のバス構造のいずれでも構成することが可能であり、その中には、そのいくつかを挙げると、メモリ・バスやメモリ・コントローラ、周辺バス、およびローカル・バスが含まれている。システム・メモリとしては、リード・オンリ・メモリ（read only memory ROM）９２４およびランダム・アクセス・メモリ（random access memory RAM）９２５が含まれている。スタートアップ時のように、パーソナル・コンピュータ９２０内のエレメント間で情報を転送するときそれを支援する基本ルーチンを含んでいる基本入出力システム（basic input/output system ＢＩＯＳ）９２６は、ＲＯＭ９２４に格納されている。パーソナル・コンピュータ９２０は、さらに、ハード・ディスク・ドライブ９２７、たとえば、取外し可能ディスク９２９との間で読み書きを行う磁気ディスク・ドライブ９２８および、たとえば、ＣＤ−ＲＯＭディスク９２８を読み取ったり、他の光ディスク媒体との間で読み書きを行ったりする光ディスク・ドライブ９２８を搭載している。ハード・ディスク・ドライブ９２７、磁気ディスク・ドライブ９２８、および光ディスク・ドライブ９３０は、それぞれハードディスク・ドライブ・インターフェース９３２、磁気ディスク・ドライブ・インタフェース９３３、および光ドライブ・インターフェース９３４を介してシステム・バス９２３に接続されている。これらのドライブとそれぞれに関連するコンピュータ読取可能媒体は、データ、データ構造、コンピュータ実行可能命令（ダイナミック・リンク・ライブラリや実行可能ファイルなどのプログラムコード）などを、パーソナル・コンピュータ９２０のために保管しておく不揮発性ストレージとなっている。上記のコンピュータ読取可能媒体の説明個所では、ハード・ディスク、取り外し可能磁気ディスクおよびＣＤだけが示されているが、その中には、磁気カセット、フラッシュ・メモリ・カード、デジタル・ビデオ・ディスク、ベルヌーイ（Bernoulli）カートリッジなどのように、コンピュータで読み取り可能である、他のタイプの媒体を含めることも可能である。
【００８０】
これらのドライブとＲＡＭ９２５にはいくつかのプログラム・モジュールを格納しておくことが可能であり、その中には、オペレーティング・システム９３５、１つまたは２つ以上のアプリケーション・プログラム９３６、その他のプログラム・モジュール９３７、プログラム・データ９３８が含まれている。ユーザは、キーボード９４０およびマウス９４２などのポインティング・デバイスを通して、コマンドと情報をパーソナル・コンピュータ９２０に入力することができる。他の入力デバイス（図示せず）としては、マイクロホン、ジョイスティック、ゲームパッド、サテライト・ディッシュ、スキャナなどがある。上記およびその他の入力デバイスは、システム・バスに結合されているシリアル・ポート・インタフェース９４６を通して処理ユニット９２１に接続されていることが多いが、パラレルポートやゲームポート、ユニバーサル・シリアルバス（universal serial busＵＳＢ）などの、他の・インターフェースを介して接続することもできる。モニタ９４７や他のタイプのディスプレイ・デバイスも、ディスプレイ・コントローラやビデオ・アダプタ９４８などの・インターフェースを介してシステム・バス９２３に接続されている。モニタのほかに、パーソナル・コンピュータは、スピーカやプリンタなどの、他の周辺出力デバイス（図示せず）を搭載しているのが代表的である。
【００８１】
パーソナル・コンピュータ９２０は、リモート・コンピュータ９４９などの、１つまたは２つ以上のリモート・コンピュータとの論理的コネクションを使用して、ネットワーキング環境で動作させることができる。リモート・コンピュータ９４９は、サーバ、ルータ、ピアデバイスまたは他の共通ネットワーク・ノードにすることが可能であり、図９にはメモリ・ストレージ・デバイス９５０だけが示されているが、パーソナル・コンピュータ９２０に関連して上述したエレメントの多くまたは全部を搭載しているのが代表的である。図９に示す論理的コネクションとしては、ローカル・エリア・ネットワーク（local area network ＬＡＮ）９５１と広域ネットワーク（wide area network ＷＡＮ）９５２がある。このようなネットワーキング環境は、オフィス、エンタープライズ・ワイド（企業内）コンピュータ・ネットワーク、イントラネット（intranet）およびインターネット（the Internet）では日常的になっている。
【００８２】
ＬＡＮネットワーキング環境で使用されるときは、パーソナル・コンピュータ９２０は、ネットワーク・インタフェースまたはアダプタ９５３を通してローカルネットワーク９５１に接続されている。ＷＡＮネットワーキング環境で使用されるときは、パーソナル・コンピュータ９２０は、インターネットなどの広域ネットワーク９５２を利用した通信を確立するためのモデム９５２や他の手段を搭載しているのが代表的である。モデム９５４は内蔵することも、外付けにすることも可能であるが、シリアル・ポート・インタフェース９４６を介してシステム・バス９２３に接続されている。ネットワーキング環境では、パーソナル・コンピュータ９２０に関連して説明したプログラム・モジュールまたはその一部は、リモートのメモリ・ストレージ・デバイスに格納しておくことができる。図示のネットワーク・コネクションは単なる例であり、コンピュータ間のコミュニケーションリンクを確立する他の手段を使用することも可能である。
【００８３】
（結論）
以上、特定の実施形態を例にして本発明を説明してきたが、本発明の範囲はこれらの特定実施形態に限定されるものではない。たとえば、上述した実施形態では、マクロブロックに対する動きベクトルと誤差信号の結合測定量は、動きベクトルの符号化に使用されるビット数に重みを付ける特定の式を使用して計算されている。しかし、動きベクトルと誤差信号のオーバー・ヘッドがどのように測定されるかは、実施形態によって異なるものである。
【００８４】
上述したスパイラル検索パスには、符号器を高速化するという利点があるが、このアプローチは、本発明のどの実施形態においても使用されるとは限らない。同様に、探索順序をシフトするアプローチは、動きベクトル・サイズに制約があるためにブロック・マッチング・プロセスの最適開始ロケーションが得られない場合にのみ使用することが可能である。しかし、探索パスを選択し、および／または探索順序をシフトさせると、動きベクトルと誤差信号の結合オーバー・ヘッドを低減化する可能性が大であるブロックが探索されるという利点がある。
【００８５】
本発明は多数の形態で実現することが可能であるので、当然に理解されるように、上述した実施形態は本発明の一例にすぎず、本発明を限定するものではない。むしろ、本発明の範囲は請求項に明確化されている通りである。したがって、これらの特許請求の範囲と精神に属するものはすべて本発明に係わるものである。
【図面の簡単な説明】
【図１】  ビデオ符号器（コーダ）を示すブロック図である。
【図２】  ビデオ復号器（デコーダ）を示すブロック図である。
【図３】  ビデオ符号化のために使用される動き推定プロセスの理解を容易にするために、ソース・フレームとターゲット・フレームの例を示す図である。
【図４】  マクロブロックの動きベクトルがどのように予測されるかを示すために、マクロブロックの例と、ビデオ・フレーム内でそれらのブロックと関連づけられている動きベクトルを示す図である。
【図５】  ブロックマッチングで使用されるスパイラル探索パターンの理解を容易にするために、図３に示すもののように、ターゲット・フレーム内の拡張探索エリアを示す図である。
【図６】  より最適な開始ロケーションからシフトされている開始ロケーションが発生源であるスパイラル探索パターンを示す図である。
【図７】  動きベクトルと誤差信号の結合データの測定量をブロック・マッチング・プロセスで探索基準として使用する、符号器の一実施形態のオペレーションを示すフロー図である。
【図８】  修正された差分計算の和をブロック・マッチング・プロセスで探索基準として使用する動き推定器を示す図である。
【図９】  本発明をソフトウェアで実現するときの動作環境の働きをするコンピュータ・システムを示すブロック図である。
【図１】
0004662636.tif 000002
【図２】
0004662636.tif 000003
【図３】
0004662636.tif 000004
【図４】
0004662636.tif 000005
【図５】
0004662636.tif 000006
【図６】
0004662636.tif 000007
【図７】
0004662636.tif 000008
【図８】
0004662636.tif 000009
【図９】
0004662636.tif 000010