ビデオシーケンス内の第2の画像を参照して第1の画像内の第1のピクセルセットを符号化するための方法であって、a第2の画像内の第1の検索ウィンドウ内で、前記第1の画像内の前記第1のピクセルセットに最もよく一致する前記第2の画像内の第1の特定の部分を識別するための検索を行うステップと、前記第2の画像内の前記第1の検索ウィンドウ内で、前記第1の特定の部分に対応する第1のロケーションを識別するステップと、b前記第1のロケーションの近くに画定された前記第2の画像内の第2の検索ウィンドウ内で、前記第1の画像内の前記第1のピクセルセットに最もよく一致する前記第2の画像内の第2の特定の部分を識別するための検索を行うステップとを含む方法。前記第2の画像内の前記第2の検索ウィンドウが前記第2の画像内の前記第1の検索ウィンドウよりも小さい請求項1に記載の方法。前記第1の特定の部分を識別するための検索を行う前記ステップが、複数の開始ロケーションから検索するステップを含む請求項1に記載の方法。前記第1の検索ウィンドウ内で検索を行う前記ステップが粗検索を含み、前記第2の検索ウィンドウ内で検索を行う前記ステップが微細検索を含む請求項1に記載の方法。前記第2の検索ウィンドウ内で検索を行う前記ステップが、a前記第2の検索ウィンドウ内の複数の検索ポイントを識別するステップと、b各々の特定の検索ポイントについて、繰り返し、i.複数の第2のピクセルグループを識別するステップと、ii.各々の識別された第2のピクセルグループについての動きベクトルメトリックを計算するステップと、iii.各々の第1のピクセルグループについて最良の第2のピクセルグループを指定するステップと、iv.判定基準が満たされたら残りの前記検索ポイントを見送るステップとをさらに含む請求項1に記載の方法。a特定のピクセルグループに関連する前記指定された第2のピクセルグループが閾値を超える計算された動きベクトルメトリックを有するか否かを判定するステップと、b前記特定の第1のピクセルグループに関連する前記指定された第2のピクセルグループが前記閾値を超えると判定した後で、前記特定の第1のピクセルグループを以降の検索から除外するステップとをさらに含む請求項5に記載の方法。前記第2の検索ウィンドウ内で検索を行う前記ステップの間に前記閾値が動的に定義される請求項6に記載の方法。前記第2の検索ウィンドウ内で検索を行う前記ステップが第1のピクセルレベルで検索を行うステップを含む請求項5に記載の方法。前記第2の検索ウィンドウ内で検索を行う前記ステップが第2のピクセルレベルで検索を行うステップを更に含み、前記第1のピクセルレベルが整数ピクセルレベルであり、前記第2のピクセルレベルがハーフピクセルレベルである請求項8に記載の方法。ビデオシーケンス内の画像のブロック間符号化方法であって、ビデオシーケンス内の各画像が複数の整数ピクセルロケーションを有し、各整数ピクセルロケーションが少なくとも1つの画像値を有し、a第2の画像を参照して符号化するための第1の画像を選択するステップと、b前記第1の画像内のピクセルセットに一致する前記第2の画像内の非整数ピクセルロケーションの第1のセットを識別するステップであって、この識別が、前記第2の画像内の複数の整数ピクセルロケーションの画像値から前記第2の画像内の非整数ピクセルロケーションに関連する画像値を補間するステップを含むステップと、c前記第2の画像を参照して第3の画像を符号化する際に使用するために非整数ピクセルロケーションの補間された画像値を記憶するステップとを含む方法。前記第2の画像内の非整数ピクセルロケーションのセットを識別した後で、前記第2の画像内の他の非整数ピクセルロケーションのグループの画像値を補間するステップをさらに含む請求項10に記載の方法。非整数ピクセルロケーションのグループが非整数ピクセルロケーションの前記第1のセットの近くにある請求項11に記載の方法。ビデオシーケンス内の画像のブロック間復号化方法であって、前記ビデオシーケンス内の各画像が複数の整数ピクセルロケーションを有し、各整数ピクセルロケーションが少なくとも1つの画像値を有し、a第2の画像を参照して復号化するための第1の画像を選択するステップと、b前記第1の画像内のピクセルセットに対応する前記第2の画像内の非整数ピクセルロケーションのセットを識別するステップと、c前記第2の画像内の複数の整数ピクセルロケーションの画像値から前記第2の画像内の非整数ピクセルロケーションに関連する画像値を補間するステップと、d前記第2の画像を参照して第3の画像を復号化する際に使用するために前記非整数ピクセルロケーションの補間された画像値を記憶するステップとを含む方法。前記非整数ピクセルロケーションに関連する画像値を補間した後で、前記第2の画像内の他の非整数ピクセルロケーションのグループの画像値を補間するステップをさらに含む請求項13に記載の方法。非整数ピクセルロケーションのグループが前記第1の非整数ピクセルロケーションの近くにある請求項14に記載の方法。ビデオ画像のシーケンス内の第2の画像を参照して第1の画像内の第1の部分をブロック間処理する方法であって、a前記第2の画像をタイルのセットに分割するステップと、b前記タイルを第1の非キャッシュメモリ記憶域に記憶するステップと、cタイルのサブセットが必要な時はいつでも、前記第1の非キャッシュメモリ記憶域から前記タイルのサブセットを取り出すステップと、d前記第1の部分と前記取り出されたタイルのサブセットの一部である前記第2の画像の部分との間で、前記取り出されたタイルのサブセットを第2のキャッシュメモリ記憶域に記憶するステップであって、前記取り出されたタイルのサブセットがタイルのセット全体よりも小さいステップとを含む方法。前記第1の部分に一致する前記第2の画像内の一部を識別するために検索する前記タイルのサブセットに対応する前記第2の画像内のロケーションを識別する時に、タイルのサブセットを取り出して前記第2のキャッシュメモリ記憶域に記憶する必要があると判断する請求項16に記載の方法。前記キャッシュメモリ記憶域がコンピュータのランダムアクセスメモリである請求項16に記載の方法。前記キャッシュメモリ記憶域がコンピュータの不揮発性記憶装置である請求項16に記載の方法。ブロック間処理方法がブロック間符号化方法である請求項16に記載の方法。ブロック間処理方法がブロック間復号化方法である請求項16に記載の方法。前記タイルのセットが少なくとも2つの水平方向に隣接したタイルと少なくとも2つの垂直方向に隣接したタイルとを含む請求項16に記載の方法。前記タイルが前記キャッシュメモリ記憶域に順次記憶される請求項16に記載の方法。第1のビデオ画像内の第1のピクセルセットを符号化するブロック間符号化方法であって、a前記第1のピクセルセットに一致する可能性がある第2の画像の複数の部分を検査するパターンを各々が定義する検索パターンセットから第1の検索パターンを選択するステップと、b判定基準セットに基づいて前記検索パターンセット内の前記第1の検索パターンを適応的に選択するステップとを含む方法。前記判定基準セットが媒体内の画像のシーケンスの解像度符号化を含む請求項24に記載の方法。前記判定基準セットが隣接する複数の動きベクトルに関する複数の動きベクトルを含む請求項24に記載の方法。前記判定基準セットがビデオ画像セット内の動きフィールドを含む請求項24に記載の方法。画像シーケンス内の第2の画像を参照して第1の画像内の第1のピクセルセットを符号化するための方法であって、a第2の画像内の複数の第2のピクセルセットを識別するステップと、b前記第2のピクセルセットの各々について第1の測定基準評価を計算するステップと、c前記第1の測定基準評価に基づいて第2のピクセルセットのサブセットを識別するステップと、d識別された第2のピクセルセットのサブセットから、i.前記識別された第2のピクセルセットの各々について第2の測定基準評価を計算するステップと、ii.最良の第2の測定基準評価を有する前記識別された第2のピクセルセットを選択するステップであって、選択済みの識別された第2のピクセルセットが前記第1のピクセルセットと最もよく一致するステップとを含む方法。各々の第2のピクセルセットが複数の第2のピクセルグルーピングを含み、各々の第2のピクセルグルーピングが複数の第2のピクセルグループを含む請求項28に記載の方法。第1の測定基準評価を計算するステップが、a各々の第2のピクセルグルーピングについて第1の測定基準評価を計算するステップと、b各々の第2のピクセルグループについて第1の測定基準評価を計算するステップとを含む請求項29に記載の方法。第2のピクセルセットのサブセットを識別するステップが、第2のピクセルグルーピングのサブセットと第2のピクセルグループのサブセットを識別するステップを含む請求項30に記載の方法。前記第2の測定基準評価を計算するステップが、各々の第2のピクセルグルーピングと各々の第2のピクセルグループについて第2の測定基準評価を計算するステップを含む請求項31に記載の方法。前記第1の測定基準評価が絶対差の総和SAD測定基準評価である請求項32に記載の方法。第2のピクセルセットのサブセットを識別するステップが最小の第1の測定基準評価を有する上位N個の第2のピクセルセットを選択するステップを含む請求項28に記載の方法。第2のレート測定基準評価が、送信するデータの量と送信データに関連する歪の量を定量化するレートディストーションコストである請求項34に記載の方法。a最小の第2の測定基準評価を有する上位N個の第2のピクセルセットについて第3の測定基準評価を計算するステップと、b最良の第3の測定基準評価を有する識別された第2のピクセルセットを選択するステップであって、選択済みの識別された第2のピクセルセットが第1のピクセルセットに最もよく一致するステップとをさらに含む請求項28に記載の方法。以下の本発明の詳細な説明で、本発明のさまざまな詳細、例、および実施形態を提示し、説明する。しかし、本発明は提示された実施形態に限定されず、また本発明は説明した特定の詳細および例示なしで実施することができることは当業者には明らかであろう。I.概要本発明のいくつかの実施形態では、新規なブロック間符号化および復号化プロセスが提供される。これらの新規なプロセスは、1多段動き推定プロセスと、2基準フレームの非整数ピクセルロケーション値をキャッシュする補間キャッシングプロセスと、3基準フレームのタイルのサブセットをキャッシュするタイルキャッシングプロセスと、4基準フレーム内の検索に用いる検索パターンを適応的に選択する動き推定プロセスとを含む。A.多段動き推定いくつかの実施形態の多段動き推定プロセスは、ビデオシーケンス内の第2の画像を参照して第1の画像内の第1のピクセルセットを符号化する。動き推定プロセスは、第2の画像内の第1の検索ウィンドウ内で、第1の画像内の第1のピクセルセットに最もよく一致する第2の画像内の第1の特定の部分を検索して識別する。第2の画像内の第1の検索ウィンドウ内で、動き推定プロセスは、第1の特定の部分に対応する第1のロケーションを識別する。次に、動き推定プロセスは、第1のロケーションの近くに画定された第2の画像内の第2の検索ウィンドウ内で、第1の画像内の第1のピクセルセットに最もよく一致する第2の画像内の第2の特定の部分を検索して識別する。いくつかの実施形態では、第1の検索は粗動き推定プロセスで、第2の検索は微細動き推定プロセスである。さらに、いくつかの実施形態では、微細動き推定プロセスは可変ブロックサイズを検索する。B.補間キャッシュ本発明のいくつかの実施形態のエンコーダはビデオシーケンス内の画像をブロック間符号化する。ビデオシーケンス内の各画像はいくつかの整数ピクセルロケーションを有し、各整数ピクセルロケーションは少なくとも1つの画像値例えば、輝度値を有する。エンコーダは、第2の画像を参照して符号化する第1の画像を選択する。次いでエンコーダは、第1の画像内のピクセルセットに一致する第2の画像内の非整数ピクセルロケーションのセットを識別する。この識別は、第2の画像内のいくつかの整数ピクセルロケーションの画像値から第2の画像内の非整数ピクセルロケーションに関連する画像値を補間する処理を必然的に伴う。エンコーダは、第2の画像を参照して第3の画像を符号化する際に使用するために非整数ピクセルロケーションの補間された画像値を補間キャッシュ内に記憶する。本発明のいくつかの実施形態のデコーダも同様の補間キャッシュを使用する。特に、デコーダは、第2の画像を参照して復号化する第1の画像を選択する。次いでデコーダは、第1の画像内のピクセルセットに対応する第2の画像内の非整数ピクセルロケーションのセットを識別する。デコーダは、次に、第2の画像内のいくつかの整数ピクセルロケーションの画像値から第2の画像内の非整数ピクセルロケーションに関連する画像値を補間する。デコーダは、第2の画像を参照して第3の画像を復号化する際に使用するために非整数ピクセルロケーションの補間された画像値を記憶する。C.タイルキャッシングプロセスいくつかの実施形態は、ビデオ画像のシーケンス内の第2の画像を参照して第1の画像内の第1の部分を処理するブロック間プロセスにタイルキャッシングプロセスを使用する。キャッシングプロセスは、第2の画像をタイルのセットに分割し、タイルを第1の非キャッシュメモリ記憶域に記憶する。第1の画像内の第1の部分を第2の画像内の部分に一致させるためにタイルのサブセットが必要な時はいつでも、キャッシングプロセスは、第1の非キャッシュメモリ記憶域からタイルのサブセットを取り出して、この取り出されたタイルのサブセットを第2のキャッシュメモリ記憶域に記憶して、第1の部分と取り出されたタイルのサブセットの一部である第2の画像の複数の部分とを高速で比較する。取り出されたタイルのサブセットはタイルのセット全体よりも小さい。いくつかの実施形態で、キャッシングプロセスは、第1の部分に一致する第2の画像内の部分を識別するために検索すべき、タイルのサブセットに対応する第2の画像内のロケーションを識別した時に、タイルのサブセットを取り出して第2のキャッシュメモリ記憶域に記憶する必要があると判断する。いくつかの実施形態では、キャッシュメモリ記憶域はコンピュータのランダムアクセスメモリであるが、非キャッシュメモリ記憶域はコンピュータの不揮発性記憶装置である。また、ブロック間プロセスは、いくつかの実施形態ではブロック間符号化プロセスであるが、別の実施形態では、ブロック間復号化プロセスである。さらに、いくつかの実施形態では、タイルのセットは少なくとも2つの水平方向に隣接したタイルと少なくとも2つの垂直方向に隣接したタイルとを含む。D.適応検索パターン本発明のいくつかの実施形態の動き推定プロセスは、第1のピクセルセットに一致する可能性がある第2の画像の一部を検査するパターンを各々定義する検索パターンのセットから第1の検索パターンを選択して第1のビデオ画像内の第1のピクセルセットを符号化する。動き推定プロセスは、判定基準のセットに基づいて検索パターンのセット内の第1の検索パターンを適応的に選択する。いくつかの実施形態の判定基準のセットはビデオ画像の媒体のタイプを含む。上記の新規なブロック間符号化および復号化プロセスについて説明する前に、本発明のブロック間符号化プロセスを含む符号化プロセスの全体のフローについて以下に説明する。II.全体フロー図1は符号化プロセスを簡単化するために種々の新規な刈り込み技法を使用するエンコーダの処理の流れを概念図で示すプロセス100を示す。いくつかの実施形態では、本章の刈り込み技法のすべてを使用するわけではない。また、いくつかの実施形態は、II章で後述するこれらの刈り込み技法を多段動き推定演算と併用する。図1に示すように、プロセス100はインタブロックとしてのマクロブロックの符号化を見送るか否かを決定するステップ105から開始する。いくつかの実施形態では、ある状況の下でプロセスはブロック間符号化を見送る。これらの状況は、各フレームをイントラブロックとして符号化する処理を必要とするデバッグモードにエンコーダを設定する処理、いくつかのマクロブロックをイントラブロックとして符号化する処理を必要とするイントラブロックリフレッシュの指定、ブロック内符号化が最終的に選択されるという認識、ブロック内符号化されているマクロブロックの数が少なすぎるという認識、またはマクロブロックをイントラブロックとして符号化することが必要な何か別の指定を含む。プロセス100が、マクロブロックをインタブロックとして符号化する必要がないと判断すると、プロセスは110に進む。110で、プロセスはマクロブロックをイントラブロックとして符号化する。ブロック内符号化を実行する種々の新規な方法は、弁理士整理番号APLE.P0078IntrablockEncodingApplicationを有するビデオデータを符号化するための符号化タイプおよび予測モードの選択SelectingEncodingTypesandPredictiveModesforEncodingVideoDataという名称の米国特許出願に記載されている。この米国特許出願は参照により本明細書に組み込むものとする。プロセスがマクロブロックをイントラブロックとして110で符号化すると、プロセスは150に進み、符号化方法を指定する。この場合、プロセスは110でそのイントラコーディングの結果を指定する。これはフローのこのパス内でプロセス100が探索した唯一の符号化方法であるからである。150の後で、プロセス100は終了する。別の方法としては、プロセス100がブロック間符号化を見送るべきすなわち、切り詰めるでないと105で決定した場合、プロセスはマクロブロックのスキップモード符号化を115で実行し、必要に応じて、マクロブロックの直接モード符号化を実行する。スキップモード符号化で、マクロブロックはスキップされたマクロブロックとして符号化される。デコーダ側では、このマクロブロックは周囲のマクロブロックおよび/または周囲のマクロブロック内のパーティションの動きベクトルを参照して復号化される。スキップモード符号化は、さらに、弁理士整理番号APLE.P0073PruningApplicationを有するビデオ符号化時の刈り込みPruningDuringVideoEncodingという名称の共願の米国特許出願に記載されている。この米国特許出願は参照により本明細書に組み込むものとする。直接モード符号化は、直接モード符号化では、マクロブロックのテクスチャデータの一部が量子化され、符号化ビットストリーム内で送信されるという点を除き、スキップモード符号化と同様である。いくつかの実施形態では、直接モード符号化はマクロブロックのBモード符号化として実行される。また、いくつかの実施形態は、Pモード符号化の際に直接モード符号化を実行する。115の後で、プロセス100は、スキップモード符号化が115で最良の符号化方法であったか否かを120で判定する。これは明らかに、115で直接モード符号化が実行されなかった時には最良の符号化方法である。他方、115で直接モード符号化が実行され、この符号化が結果的にスキップモード符号化より優れた方法の時には、プロセスは135に進んでインターコーディングを実行する。これについては後述する。ただし、プロセスが、スキップモード符号化が115で最良の結果であったと120で判定した時には、プロセスはスキップモード符号化が符号化を終了するのに十分優れていたか否かを125で判定する。そのような判定の1つの方法が上記組み込まれたPruningApplicationに記載されている。スキップモード符号化が十分に優れているとプロセスが125で判定した場合、プロセス100は130に進み、スキップモード符号化方法を廃棄するか否かを決定する。いくつかの実施形態は、レートディストーションコストRDコストと呼ばれる符号化コストに基づいて方法を判定する。II章で詳述するように、符号化方法のRDコストは、多くの場合、符号化されたマクロブロックの歪を表し、その符号化方法で生成される実際のビット数をカウントする。スキップモード方法はRDコストが大きいことがあるがそれでも魅力的な方法である。これは、そのような方法がきわめて小さいレートコストを有し、そのような小さいレートコストは全RDコストを大幅にゆがめて、劣った方法を最良の方法と思わせるためである。したがって、125でスキップモード符号化方法を選択した後でも、プロセス100はスキップモード方法を除去するか否かを125で判定する。いくつかの実施形態では、この判定の基準は、現在のマクロブロックのスキップモード符号化の歪が現在のマクロブロックの隣接マクロブロックの最大歪の2倍より大きいか否かである。プロセスが、スキップモード方法を除去しないと130で決定した場合、プロセスは符号化方法を指定する。この場合、プロセスはスキップモード符号化方法の結果を指定する。150の後で、プロセス100は終了する。他方、プロセス100が、スキップモード符号化方法を除去すると130で決定した場合、135に進む。スキップモード方法が符号化を終了させるのに十分優れてはいないと125で判定した場合も、プロセスは135に進む。135で、プロセスは種々のブロック間符号化を検査する。いくつかの実施形態では、プロセス100は種々のマクロブロックとサブマクロブロック符号化例えば、16×16、8×16、16×8、8×8、8×4、4×8、および4×4BモードおよびPモード符号化を探索することがある。これについてはII章で詳述する。ただし、上記組み込まれたPruningApplicationに記載されているように、いくつかの実施形態は、マクロブロックまたはサブマクロブロック符号化モードのいくつかの探索および/または分析を切り詰めすなわち、見送り、ブロック間符号化プロセスを高速化する。135でブロック間符号化を実行した後、プロセスはマクロブロックのブロック間符号化がマクロブロックのブロック内符号化を見送るほど優れているか否かを140で判定する。別の実施形態ではこの判定方法が異なる。これらの手法のいくつかについてII章で詳述する。プロセス100が、ブロック内符号化を実行すると140で決定すると、145に進み、この符号化を実行する。上記のように、このプロセスのブロック内符号化のいくつかの新規な特徴は上記組み込まれたIntrablockEncodingApplicationに記載されている。145の後で、プロセスは150に進む。プロセスはブロック内符号化を見送ると140で決定した場合も、150に進む。上記のように、プロセスはマクロブロックの符号化方法を150で指定する。プロセス100が150の前にその動作中に複数の符号化方法を識別すると、プロセスはこれらの方法の1つを150で選択する。いくつかの実施形態では、プロセス100は最良のRDコストを有する方法を選択する。RDコストのいくつかの例を以下に示す。150の後で、プロセスは終了する。III.ブロック間符号化A.多段動き推定上記のように、いくつかの実施形態は、多段動き推定演算を図1に示すプロセス100と併用する。いくつかの実施形態では、多段動き推定演算はマクロブロックをブロック間符号化する時に実行される。以下に述べるように、いくつかの多段動き推定演算は粗動き推定と微細動き推定とを含む。いくつかの実施形態では、プロセス100は初期の粗動き推定演算の後に実行される。しかし、初期の粗動き推定演算は、また、プロセス100中に例えば、ステップ105とステップ115との間のステップ140で実行できることは当業者には明らかであろう。1.全体フロー図2は、1つまたは2つの基準フレームとカレントフレームとの間のマクロブロックの動きを指定する動きベクトルを識別する多段動き推定演算を実行するプロセスを示す図である。本発明の多段動き推定演算の説明を分かりにくくしないために、単一の基準フレーム内のカレントフレームマクロブロックの位置を発見する処理に関してプロセス200を以下に説明する。しかし、このプロセスはしばしば2つの基準フレームを探索してマクロブロックの最良の動き推定符号化を識別することは当業者には明らかであろう。このプロセスの第1段階は、基準フレーム内のカレントフレームマクロブロックの位置の粗近似を識別する粗検索例えば、粗動き推定である。第2段階は、基準フレーム内のカレントフレームマクロブロックの位置のより高精度の近似を識別するより微細検索例えば、微細動き推定である。プロセスは最初、カレントフレームマクロブロックに最もよく一致するマクロブロックの基準フレームの第1の検索を210で実行する。第1の検索は基準フレーム内の第1の検索ウィンドウ内で実行される。別の実施形態は第1の検索ウィンドウの位置を異なって識別する。例えば、図3に示すように、いくつかの実施形態は、第1の検索ウィンドウ300をカレントフレーム内のマクロブロック330のロケーション320に対応する基準フレームのロケーション310の近くに配置する。別の実施形態は、第1の検索ウィンドウを基準フレーム内のカレントフレームマクロブロックの指定のロケーションに配置する。図4は、カレントフレームマクロブロックに関連する予測動きベクトルに基づいて第1の検索ウィンドウのロケーションを識別する1つの方法を示す図である。図4はカレントフレーム400内のカレントフレームマクロブロック410を示す。この図はまた、カレントフレームマクロブロック410に関連する予測動きベクトル420を示す。この予測動きベクトル420は、カレントフレーム内のカレントフレームマクロブロック410に隣接するマクロブロックの動きベクトルに基づいて計算できる。図4に示すように、予測動きベクトル420は基準フレーム430内のロケーション440に対応するカレントフレーム400内のロケーションポイント460をポイントする。したがって、図4にさらに示すように、いくつかの実施形態は、基準フレーム430内の第1の検索ウィンドウ450をロケーションポイント440の近くに配置する。プロセス200は、カレントフレームマクロブロックが基準フレーム内に出現してから動いた量を指定する動きベクトルを識別しようとして第1の検索ウィンドウ内で粗検索を210で実行する。プロセスは、カレントフレームマクロブロックに最もよく一致する第1の検索ウィンドウ内で基準フレームマクロブロックを検索することでこの動きベクトルを識別できる。プロセスは、検索ウィンドウ内のすべての基準フレームマクロブロックを参照するわけではなく、ある種の所定のパラメータの範囲にあるマクロブロックを決定するのに十分なだけ参照する。プロセスが十分な基準フレームマクロブロックを識別すると、この粗検索で遭遇する最良の基準フレームマクロブロックを210で識別する。次いで、プロセスは識別された最良の基準フレームマクロブロックを210で用いて基準フレーム内のカレントフレームマクロブロックのロケーションの粗近似を示す動きベクトルを指定する。210の後で、プロセスは第1の検索ウィンドウ内で粗検索を十分に繰り返したか否かを220で判定する。いくつかの実施形態は、このウィンドウ内で1回の検索しか実行しない。そのような実施形態では、プロセス200は220で判定する必要がなく、その代わりに、210から直接230に進む。あるいは、他の実施形態は、このウィンドウ内で、複数の異なるポイントで開始する複数の検索を実行する。プロセス200が、第1の検索ウィンドウ内で、別の粗検索を実行すると220で決定した場合、プロセスは210に戻って、マクロブロックに関して210で実行された他の以前の粗検索とは異なるロケーションで開始する別の検索このウィンドウ内のを実行する。図5は、第1の検索ウィンドウ内の複数の開始ポイントの一例を示す図である。特に、この図は第1の検索ウィンドウ500内の4つの開始ポイント510~540を示す。各開始ポイント510~540は異なる基準フレームマクロブロックを識別する検索を実行する。いくつかの実施形態では、異なる開始ポイントが同じ基準フレームマクロブロックを識別してもよい。プロセスが第1の検索ウィンドウ内で粗検索を十分に繰り返したと220で判定した場合、210までの1つまたは複数の繰り返しで識別した最良の可能な粗い段階の方法を230で識別する。図6に示すように、この方法は、基準フレーム内のロケーション630に対応するカレントフレーム内のマクロブロック410のロケーション610を識別する動きベクトル620を識別する。次に、プロセスはカレントフレームマクロブロックに一致する基準フレームマクロブロックの第2の微細動き推定検索を240で実行する。第2の検索は基準フレームの第2の検索ウィンドウ内で実行される。いくつかの実施形態では、この第2の検索ウィンドウは210の粗い第1段階の検索で使用した第1の検索ウィンドウよりも小さい。また、いくつかの実施形態では、第2の検索ウィンドウは、第1段階の検索によってすなわち、230で選択された動きベクトルによって生成された動きベクトルによって識別された基準フレーム内の位置の近くに画定される。図6はそのような第2段階の検索ウィンドウの一例を示す図である。特に、この図は、第1の検索で指定されたロケーションポイント630の近くの第2の検索ウィンドウ640を示している。いくつかの実施形態では、第2の検索段階で240で使用した検索プロセスは第1の検索段階で使用した検索プロセスよりもはるかに徹底している。例えば、いくつかの実施形態は、第2段階ではレートディストーション最適化を利用する詳細なサブマクロブロック検索を使用するが、第1の検索段階ではより簡単な3ステップの検索を使用する。240の第2の検索段階の最後に、プロセス200は、カレントフレームマクロブロックが基準フレーム内に出現してから動いた量を指定する動きベクトルを提供する。240の後で、プロセスは終了する。2.微細動き推定図7は、カレントフレームマクロブロックのピクセルのパーティションセットに最もよく一致する基準フレーム内のピクセルのパーティションセットを識別するために実行される微細動き推定プロセス700を示す図である。いくつかの実施形態では、プロセス700はプロセス200の第2の検索240中に実施される。この図に示すように、プロセス700は検索ウィンドウ内でロケーションポイントを705で選択する。いくつかの実施形態では、検索ウィンドウは最初はプロセス200の230で識別された微細基準フレームマクロブロックの近くに画定される。図8は、いくつかのロケーションポイントを有する検索ウィンドウ800を示す概念図である。この図に示すように、検索ウィンドウ800は、9つのロケーションポイント805~845を含む。いくつかの実施形態では、これらのロケーションポイント805~845はランダムに生成できる。別の実施形態では、これらのロケーションポイント805~845は判定基準のセットによって事前に規定されている。これらのロケーションポイント805~845の各々は整数ピクセルレベルの基準フレームマクロブロックに対応する。さらに、図8は、ハーフおよびクォータピクセルレベルのロケーションポイントなどの非整数ピクセルレベルすなわち、サブピクセルレベルのロケーションポイントを示す。これらのサブピクセルレベルのロケーションポイントの使用法について図9を参照しながら詳述する。次に、カレントフレームマクロブロック内のピクセルの各々の可能なパーティションについて、プロセス700は選択されたロケーションポイントの特定のピクセルのパーティションがカレントフレームマクロブロックのピクセルのパーティションにどの程度一致するか710で検査する。図10は、いくつかの可能なパーティションすなわち、ブロックサイズを示す概念図である。特に、この図は、各ブロックサイズが特定のピクセルブロックを表す9つの可能なブロックサイズを示す。例えば、ブロックサイズ1は16×16のピクセルアレイを含むピクセルブロックを表す。ブロックサイズ2は16×8のピクセルアレイを含むピクセルブロックを表す。この図は9つのブロックサイズしか示していないが、プロセス700は他のピクセル構成のブロックサイズを検索することができる。いくつかの実施形態は、これらのブロックサイズをすべて検索するが、別の実施形態は、これらのブロックサイズの一部しか検索しない。検査が710で実行されると、プロセス700は各ブロックサイズの基準フレームマクロブロックの最良のロケーションを715で更新する。プロセス700は、別のロケーションポイントがあるか否かを720で判定する。ある場合、プロセス700は705に進んで別のロケーションポイントを選択し、ステップ710~720をもう1回繰り返す。プロセス700がもうロケーションポイントはないと720で判定すると、プロセス700はあるブロックサイズの検索結果が良好であるか否かを725で判定する。いくつかの実施形態では、更新されたロケーションを有するブロックサイズが一定の判定基準例えば、一定のしきい値より下のSADを満たしていれば、検索結果は良好である。いくつかの実施形態では、特定のブロックサイズに関連するコストと最小のコストを有するブロックサイズに関連するコストとの差がしきい値を超えている場合、検索結果は良好ではない。いくつかの実施形態では、しきい値は検索中に動的に定義される。プロセス700があるブロックサイズの検索結果が良好ではないと725で判定すると、プロセス700は以降のどの検索でもこれらのブロックサイズを730で除外する。これらのブロックサイズを730で除外した後、またはすべての検索結果が良好であると725で判定した後で、プロセス700は別の検索を735で実行する。この検索中、各ブロックサイズについて、プロセス700はカレントフレームマクロブロックのパーティションに最もよく一致する基準フレーム内のピクセルのパーティションを検索する。この検索は、サブピクセルレベルでのピクセルのパーティションの検索を含む。このサブピクセルレベル検索について以下に詳述する。735の検索の後で、プロセス700は終了する。3.サブピクセルレベルでの検索図9は、多重ピクセルレベルの基準フレームマクロブロックのピクセルのパーティションを検索するプロセス900を示す概念図である。いくつかの実施形態では、プロセス900はプロセス700の検索735中に実行される。この図に示すように、プロセス900は、カレントフレームマクロブロックのピクセルのパーティションを905で選択するすなわち、ブロックサイズを選択する。プロセス900は905までを数回繰り返す。905までの繰り返しで、いくつかの実施形態のプロセスは、図10に示す数字指定に基づいて730で順次廃棄されなかったパーティションすなわち、ブロックを繰り返し選択する。例えば、730でどのパーティションも廃棄されなかった場合、プロセス900はブロック1~9を順次選択する。905の後、プロセス900は検索の初期ピクセル解像度例えば、ピクセルレベルを910で定義するすなわち、検索の粒度を定義する。例えば、プロセス900は最初、ピクセル解像度を整数ピクセルで1ロケーションおきすなわち、整数のピクセルレベル解像度の半分の解像度と定義できる。次に、プロセス900は、検索ロケーションを、カレントフレームマクロブロックの選択されたパーティションのこれまでに識別されたうち最良のロケーションと915で定義する。この最良と識別されたロケーションは、図7のプロセス700のピクセルレベル検索中に識別でき、または、以下に詳述するように、図9のプロセス900のピクセル解像度検索のいずれかの実行中に識別できる。730で廃棄されなかった特定のカレントフレームパーティションの各々について、プロセス900は、920で1定義されたピクセルレベル解像度すなわち、検索の粒度で915で識別された検索ロケーション近くの基準フレームパーティションを検査し、2カレントフレームパーティションに最もよく一致する特定の検査済の基準フレームパーティションを識別する。次いで、730で廃棄されなかった特定のカレントフレームパーティションの各々について、プロセス900は、925で特定のカレントフレームパーティションの920で識別された特定のカレントフレームパーティションが特定のカレントフレームパーティションの以前に識別された最高の一致よりもよい一致であるか否かを判定する。そうである場合、プロセスは920で識別された特定の基準フレームパーティションのロケーションを特定のカレントフレームパーティションの最良のロケーションとして925で定義する。次に、プロセス900は、選択されたパーティションの最大ピクセルレベル解像度で基準フレームを検査したか否かを930で判定する。そうでない場合、プロセス900はピクセルレベル解像度を次のピクセルレベル解像度例えば、半分、4分の1に935で増やし、915に戻る。これについては前述の通りである。したがって、ステップ915~935の以降の繰り返しで、プロセス900はサブピクセルレベル例えば、半分、4分の1でカレントフレームマクロブロックのパーティションを検査する。プロセス900が、選択されたパーティションの最大ピクセルレベル解像度で基準フレームを検査したと930で判定した場合、プロセス900は、730で廃棄されなかったすべてのカレントフレームパーティションを検査したか否かを940で判定する。そうでない場合、プロセス900は905に戻って次のカレントフレームパーティションを選択し、このパーティションについてステップ910~935を繰り返す。プロセス900は、730で廃棄されなかったすべてのピクセルのパーティションを検査したと940で判定すると、終了する。図11は、異なるピクセルレベルのいくつかの検索ロケーションを示す概念図である。特に、この図は、4つの整数ピクセルレベルロケーション825~830と840~845とによって区切られた検索領域860を示す。いくつかの実施形態では、この区切られた検索領域860は、図8に示すように、検索ウィンドウ800内にある。区切られた検索領域860内には5つのハーフピクセルレベルロケーションがある。さらに、この区切られた検索領域860内には、16のクォータピクセルレベルロケーションがある。別の実施形態では、これより多い、または少ない整数および非整数のロケーションを含む別の区切られた検索領域を指定できる。いくつかの実施形態は、プロセス900が検索ロケーションをロケーション850と915で定義している時には、920での検索時にこの区切られた検索領域860の内部および周囲を検索できる。いくつかの実施形態では、上記のステップのいくつかの繰り返しが実行される。上記のように、いくつかの実施形態は、ピクセルレベルごとに別途検索を行う。ただし、いくつかの実施形態では、異なるピクセルレベルでいくつかのブロックサイズを検索ロケーションごとに同時に検索できるすなわち、すべてのブロックサイズについて整数、ハーフおよびクォータピクセルレベルで同時に各ロケーションについて検索できることは当業者には明らかであろう。サブピクセルレベルはハーフおよびクォータピクセルレベルとして説明しているが、サブピクセルレベルは任意の非整数ピクセルレベルでよいことは当業者には明らかであろう。さらに、プロセス700は、あるブロックサイズの検索結果が良好か否かを725で判定すると記述している。いくつかの実施形態では、この判定725は、プロセス900中に行ってもよい。さらに、この判定725はプロセス700および900の異なるステップ中に実行してもよいことは当業者には明らかであろう。例えば、各ブロックサイズの最良のロケーションを見つけた後でそのような判定プロセス725を実行してもよい。さらに、いくつかの実施形態は、プロセス700中に735で検索を実行しない。また、上記プロセス700および900は基準フレームマクロブロックの検索を実行すると記述してあるが、プロセス700および900を用いて他のタイプのピクセルアレイ例えば、16×8のサブマクロブロックを検索できることは当業者には明らかであろう。B.キャッシュ補間値図12は、基準フレーム内のいくつかのピクセルおよびサブピクセルロケーションを示す概念図である。これらのサブピクセルロケーションはハーフおよびクォータピクセルロケーションを含む。この図に詳細に示すように、カレントフレームマクロブロック1200はクォータサブピクセルロケーション1205と位置合わせされているすなわち、カレントフレームマクロブロック内のピクセルロケーションは基準フレーム内のクォータサブピクセルロケーションと揃っている。上記のように、エンコーダは、いくつかの実施形態の動き推定演算中に、基準フレーム内のサブピクセルロケーションと位置合わせされたすなわち、ピクセルロケーションと位置合わせされていないマクロブロックまたはマクロブロックパーティションを検査する。いくつかの実施形態のデコーダは、また、場合によっては、基準フレームからサブピクセルロケーションと位置合わせされたすなわち、ピクセルロケーションと位置合わせされていないマクロブロックまたはマクロブロックパーティションを取り出す必要がある。サブピクセルロケーションと位置合わせされたマクロブロックまたはマクロブロックパーティションの検査および取り出しを行うには、エンコーダまたはデコーダが、復号化演算時のカレントフレーム内のピクセルロケーションに対応し、符号化演算時にカレントフレーム内のピクセルロケーションと比較する必要があるサブピクセルロケーションの基準フレームの画像値例えば、輝度値を生成することが必要である。いくつかの実施形態では、サブピクセルロケーションに対応する画像値の生成は、隣接するピクセルロケーションの画像値から画像値を補間するすなわち、ピクセルロケーションの画像値からサブピクセルロケーションの画像値を抽出する処理を必然的に伴う。多くの場合、サブピクセルロケーションの画像値の補間は2つの最も近い隣接したピクセルロケーションの画像値を単に計算する以上の処理を必然的に伴う困難な演算例えば、計算が高価な演算である。したがって、いくつかの実施形態は、サブピクセルロケーションの補間された画像値をキャッシュに記憶する。この画像値は、別のカレントフレームパーティションの以降の検索がサブピクセルロケーションの上記の補間された画像値を検査しようとする時には容易に取り出すことができる。いくつかの実施形態はすべての補間された値をキャッシュに記憶するが、別の実施形態は補間された値の一部しかキャッシュに記憶しない。符号化および/または復号化演算中、カレントフレームマクロブロックのセットの多くの動きベクトルが同じ基準フレームをポイントする。例えば、図13に示すように、フレーム1310はフレーム1305および1325を参照して定義された動きベクトルを有する。さらに、両方のフレーム1315および1320はフレーム1305を参照して定義された動きベクトルを有する。したがって、ある実施形態の場合には、他の複数のフレームを符号化、または復号化するために基準フレームを使用できる。この結果、基準フレームについて補間されたすべての、またはいくつかのサブピクセル値をキャッシュに入れることが必要である。これは、サブピクセル値が他のフレームの符号化に使用できるためである。C.キャッシュタイリング図14は、基準フレームをキャッシュに記憶するための方法を示す概念図である。いくつかの実施形態では、この方法は上記の補間演算と併用される。この図に示すように、基準フレーム1305はいくつかのタイル1430に分割される。いくつかの実施形態では、フレーム1305は複数のタイルの列と複数のタイルの行とを含むように分割される。図14はさらに基準フレーム内のピクセルロケーションと位置合わせされたまたはされていないピクセルブロック1450を示す。ピクセルブロック1450は符号化演算時にすなわち、動き推定時に検査されるかまたは復号化演算時に取り出される基準フレームの一部を表す。図14に示すように、タイル1430a~1430dの一部はピクセルブロック1450を検査または取り出すために必要である。したがって、符号化または復号化演算時にピクセルブロックピクセルブロック1450などの検査を容易にするために、いくつかの実施形態では、基準フレーム1305をそのタイルに関してキャッシュに入れる。言い換えれば、基準フレーム1305全体にわたるピクセルの行例えば、ピクセルブロック1450を含むピクセル行1401~1425をキャッシュに入れる代わりに、いくつかの実施形態では、基準フレーム内のタイルをキャッシュに入れるだけである。特定のピクセルブロックの分析のためにタイルのセットが必要な時には、これらの実施形態のエンコーダまたはデコーダは特定のピクセルブロックが重なっているすべてのタイルがキャッシュに入っているか否かを判定する。そうである場合、エンコーダまたはデコーダはキャッシュに入っているタイルを用いて特定のピクセルブロックを処理する。そうでない場合、エンコーダまたはデコーダは、1非キャッシュ記憶域から所望のタイルすなわち特定のピクセルブロックと重なるが現在キャッシュに入っていないタイルを取り出し、2これらのタイルをキャッシュに記憶し、次に、3これらのタイルを用いて特定のピクセルブロックを処理する。例えば、ピクセルブロック1450を処理しようとする場合、エンコーダまたはデコーダはこのブロックがタイル1430a~1430dに重なっていると判定する。したがって、エンコーダまたはデコーダはこれらのタイル1430a~1430dをキャッシュに入れまだ入っていない場合、次に、これらのタイルを用いてブロック1450を処理する。いくつかの実施形態では、キャッシュ記憶域は符号化または復号化演算を実行するためのコンピュータシステムのプロセッサのキャッシュである。別の実施形態では、キャッシュ記憶域は符号化または復号化演算を実行するためのコンピュータシステムの揮発性メモリ例えば、ランダムアクセスメモリの専用の領域である。また、図14はキャッシュ処理のための正方形のタイルを示しているが、いくつかの実施形態では、そのタイルに長方形などの他の形状を用いてもよい。D.動き推定のための適応検索パターンいくつかの実施形態は、上記の多段動き推定演算中に異なる検索判定基準を用いて検索を実行する。いくつかの実施形態は、検索を実行する際に固定検索パターンを使用する。別の実施形態では、異なる検索パターンを使用してもよい。例えば、いくつかの実施形態は、ある種の判定基準に基づいて検索パターンを適応的に選択する。1つの例は、低密度および高密度検索パターンの間の選択である。図15は、検索ウィンドウ1500内の低密度検索パターンを示す。この図は、パターンが検索のために指定するロケーションを表す黒い円で検索パターンを示している。図15に示すように、検索パターンは、検査できる49個の潜在的なマクロブロックロケーション黒と白の円で識別されるから検索のために16個のロケーションだけを指定する。図16は、検索ウィンドウ1500内の高密度検索パターンを示す。この図の検索パターンは、検査できる49個の潜在的なマクロブロックロケーション黒と白の円で識別されるから検索のために25個のロケーションを指定する。いくつかの実施形態は、所望の符号化結果に基づいて図15および図16に示す検索パターンから適応的に選択を行う。例えば、いくつかの実施形態は、高解像度符号化例えば、HDテレビジョン符号化には図16に示す高密度パターンを使用し、別の実施形態は、ネットを通じて搬送されるストリーミングリアルタイムビデオのために図15に示す低密度パターンを使用する。あるいは、いくつかの実施形態は、垂直検索の動きを強調する検索パターンを使用し、別の実施形態は、水平検索の動きを強調する検索パターンを使用する。図17は、予測されたマクロブロックロケーション付近に中心がある検索ウィンドウ内の検索パターンの一例を示す。この検索パターンは垂直方向に偏っている。探索できるロケーションの数が限られているので、図17に示すパターンは、エンコーダの限られた検索予算を使って検索ウィンドウ1500の中心にある予測されたマクロブロックロケーションの近くの垂直列にあるロケーションを検査する。図18は、予測されたマクロブロックロケーション付近に中心がある検索ウィンドウ内の検索パターンの一例を示す。この検索パターンは水平方向に偏っている。探索できるロケーションの数が限られているので、図18に示すパターンは、エンコーダの限られた検索予算を使って検索ウィンドウ1500の中心にある予測されたマクロブロックロケーションの近くの水平行にあるロケーションを検査する。いくつかの実施形態は、隣接マクロブロックのベクトルに基づいて、図17および図18に示す2つのパターンのうちから適応的に選択を行う。それらの大半またはすべてが特定の方向例えば、垂直または水平方向を指す場合、これらの実施形態は図17または図18に示すパターンを選択する。いくつかの実施形態は一方の方向例えば、y軸の動きベクトルの絶対値が他方の方向例えば、x軸の動きベクトルの絶対値より大きいか否かを判定することで、隣接するマクロブロックの動きベクトルが特定の方向を指すか否かを判定する。いくつかの実施形態は、隣接するマクロブロックの動きベクトルの方向だけでなく、これらのベクタの大きさも考慮する。いくつかの実施形態は、検索パターンを適応的に選択する際に、画像のセットの動きフィールド例えば、画像のセットが特定の方向の動きを示すか否かも考慮する。E.RDコスト計算上記のように、本発明のいくつかの実施形態は、動き推定演算中にレートディストーションRDコストなどの特定のマクロブロックのコストを計算する。動き推定中にすべての可能なモードについてレートディストーションコストを生成することは計算処理の負荷が高い。このコストが、多くの場合、生成される実際のビットの歪と数の測定を必然的に伴うとするとこれは正しい。したがって、いくつかの実施形態では、すべての可能なモードについてRDコストを計算することはない。その代わりに、これらの実施形態は、動き推定方法をランク付けし、上位N個の動き推定方法を選択し、次いで選択した方法のRDコストを計算することで可能なモードの数を減らす。図19は、本発明のいくつかの実施形態のプロセス1900を示す。このプロセスはRDコストを計算する必要がある動き推定方法を識別するために、動き推定方法のサブセットを選択的に検査する。いくつかの実施形態では、このプロセスが開始する前にいくつかの符号化方法が計算されている。別の実施形態は、このプロセスを符号化方法と併用する。最初、プロセス1900は、最小から最大推定誤差に基づいて符号化方法を1910でランク付けする。いくつかの実施形態では、各符号化方法は動きベクトルだけでなく推定誤差も生成する。別の実施形態は別のメトリック計算を用いて誤差を量子化する。例えば、いくつかの実施形態は、平均絶対差MAD測定基準評価metricscoreを使用するが、絶対差の総和SAD測定基準評価を使用する実施形態もある。後者の方法は上記組み込まれたPruningApplicationに記載されている。さらに別の実施形態では、複数の測定基準評価の組み合わせを使用する。次に、プロセスはランク付けされたリストの上位N個の符号化方法を1920で選択する。いくつかの実施形態では、Nの値は事前定義された数で、別の実施形態では、動的に生成される数である。次いで、プロセスは選択した上位N個の結果のRDコストを1930で計算し、最も低いRDコストを備えた符号化方法を1940で選択し、終了する。いくつかの実施形態は、符号化方法のRDコストを下式で表す。RdCost=歪コストλ×NBただし、λは重み付け係数、NBは符号化のために生成されたビット数である。RdCostは送信するデータの量とそのデータに関連する歪の量を定量化する。単一のRDコストを計算する代わりに、いくつかの実施形態では、RDコストを因子に分解するだけでなく符号化方法が生成された所与のモードを復号化する複雑さも因子に分解するコストを2330で計算する。このコストは下式で表される。複合RD=RdCostαcfただし、RdCostは上記の指定された等式で計算され、αは復号化の複雑さに関連する重要な因子で、cfはデータ上で実行される復号化の量を定量化する複雑さの因子である。1930の後で、プロセスは1930で計算された最小コストに至った動き推定方法を1940で選択し、終了する。最初に初期測定基準評価で動き推定演算をランク付けし、最小初期測定基準評価でこれらの符号化方法のコストメトリックに対して定量化のみを実行することで、プロセス1900は可能な限り高速に受け入れられる結果を確実に見つけるようにする。IV.コンピュータシステム図20は、本発明のいくつかの実施形態が実施されるコンピュータシステムを示す概念図である。コンピュータシステム2000は、バス2005と、プロセッサ2010と、システムメモリ2015と、読み出し専用メモリ2020と、永久記憶装置2025と、入力装置2030と、出力装置2035とを含む。バス2005は、コンピュータシステム2000の内部装置間の通信をサポートするすべてのシステム、周辺装置、およびチップセットバスを集合的に表す。例えば、バス2005は、プロセッサ2010を通信可能に読み出し専用メモリ2020と、システムメモリ2015と、永久記憶装置2025とに接続する。これらの種々のメモリユニットから、プロセッサ2010は本発明のプロセスを実行するために、実行する命令と、処理するデータとを取り出す。読み出し専用メモリROM2020は、プロセッサ2010とコンピュータシステムの他のモジュールが必要とする静的データと命令とを記憶する。他方、永久記憶装置2025は、読み出し/書き込みメモリ素子である。この素子はコンピュータシステム2000がオフになっても命令およびデータを記憶する不揮発性記憶装置である。本発明のいくつかの実施形態は、永久記憶装置2025として、大容量記憶装置磁気または光ディスクとそれに対応するディスクドライブなどを使用する。別の実施形態は、永久記憶装置として、着脱式記憶装置フロッピーディスクまたはzip登録商標ディスクとそれに対応するディスクドライブなどを使用する。永久記憶装置2025のように、システムメモリ2015は読み出し/書き込みメモリ素子である。ただし、記憶装置2025とは違って、システムメモリはランダムアクセスメモリのような揮発性読み出し/書き込みメモリである。システムメモリはプロセッサが実行時に必要とする命令とデータの一部を記憶する。いくつかの実施形態では、本発明のプロセスは、システムメモリ2015、永久記憶装置2025、および/または読み出し専用メモリ2020に記憶される。バス2005はまた入力および出力装置2030および2035に接続する。ユーザは入力装置を用いてコンピュータシステムに情報を伝え、コマンドを選択する。入力装置2030は英数字キーボードおよびカーソル制御装置を含む。出力装置2035はコンピュータシステムによって生成される画像を表示する。出力装置はプリンタと陰極線管CRTまたは液晶ディスプレイLCDなどの表示装置を含む。最後に、図20に示すように、バス2005はまたネットワークアダプタ図示せずを介してコンピュータ2000をネットワーク2065に結合する。こうして、コンピュータはコンピュータのネットワークローカルエリアネットワークLAN、ワイドエリアネットワークWAN、もしくはイントラネットなどまたはネットワークのネットワークインターネットなどの一部になる。コンピュータシステム2000のいずれかまたはすべての構成要素を本発明と併用することができる。ただし、任意のその他のシステム構成も本発明と併用できることは当業者には明らかであろう。多数の特定の詳細を参照しながら本発明を説明してきたが、通常の当業者であれば、本発明の精神から逸脱することなしに、本発明を他の特定の形態で実施することができることを理解することができるだろう。例えば、本発明の多くの実施形態をマクロブロックを参照しながら説明してきたが、通常の当業者であれば、これらの実施形態は、ピクセル値の任意の他のアレイと一緒に使用することができることを理解することができるだろう。