(57)【要約】この明細書はビデオ系列を符号化するために必要な処理サイクル及びメモリ移転の数を低減させることが可能な符号化技術を述べている。このように、開示されたビデオ符号化技術はビデオ符号化速度を増大させ、電力消費を低減する。一般に、ビデオ符号化技術は動き推定ルーチンについて検索空間に対応する縦列におけるビデオ・ブロックを記憶する候補メモリを利用する。メモリ制御ユニットは、例えば、絶対差分和（ＳＡＤ）及び二乗差分和（ＳＳＤ）技術を用いて符号化されるビデオ・ブロックにおけるピクセルと同時比較して並行して多数のピクセルを再生するために候補メモリをアドレス指定する。差分プロセッサは並行計算を行う。さらに、符号化される次のビデオ・ブロックについて、候補メモリは全体の検索空間に再装荷するのではなく、ビデオ・ブロックの新しい縦列を装荷することによって増加的に更新することができる。
2005530420.tif 000002
【特許請求の範囲】
【請求項１】
検索空間内の一以上の候補ビデオ・ブロックのピクセルに関して符号化されるビデオ・ブロックの多数のピクセルについて並行して差分計算を行うこと、及び
少なくとも一部計算された差分計算に基づいて符号化されるビデオ・ブロックと候補ビデオ・ブロックとの間の類似のレベルを規定する差分値を生成することを含む方法。
【請求項２】
候補ビデオ・メモリ中の多数の出力バンクから各々の候補ビデオ・ブロックにおける多数のピクセルを再生することをさらに含む、請求項１記載の方法。
【請求項３】
候補ビデオ・ブロックの一つを確認するピクセル指数を受信すること、
ピクセル指数を候補メモリ中の物理アドレスに変換すること、及び
物理アドレスに基づいて多数の出力バンクから候補ビデオ・ブロックにおける多数のピクセルを再生することをさらに含む、請求項２記載の方法。
【請求項４】
ピクセル指数を候補メモリ中の論理アドレスに変換すること、及び論理アドレスを候補メモリ中の物理アドレスに変換することをさらに含む、請求項３記載の方法。
【請求項５】
符号化されるビデオ・ブロック及び各々の候補ビデオ・ブロックはＭＰＥＧ‐４規格に準拠するピクセルの１６×１６マクロブロック配列を規定する、請求項３記載の方法。
【請求項６】
符号化されるビデオ・ブロックの一行における全てより少ないピクセルと検索空間内の候補ビデオ・ブロックのピクセルとの間で並行して差分値を計算することをさらに含む、請求項１記載の方法。
【請求項７】
検索空間は縦列で配置される多数の候補ビデオ・ブロックの配列を規定する、請求項１記載の方法。
【請求項８】
検索空間中の候補ビデオ・ブロックを候補メモリに装荷すること、
符号化される第一のビデオ・ブロック及び候補メモリ中の候補ビデオ・ブロックにおける多数のピクセル間で並行して差分計算を行うこと、
検索空間における新しい縦列に対応する候補ビデオ・ブロックによって候補メモリの部分集合を再装荷すること、及び
符号化される第二のビデオ・ブロック及び候補メモリ中の候補ビデオ・ブロックにおける多数のピクセルの間で並行して差分値を計算することを含む、請求項７記載の方法。
【請求項９】
ＭＰＥＧ‐４規格の一つに従って符号化されるビデオ・ブロックを符号化することをさらに含む、請求項１記載の方法。
【請求項１０】
少なくとも一部計算された差分に基づいて符号化されるビデオ・ブロックの部分集合と候補ビデオ・ブロックの部分集合との間で類似のレベルを規定する差分値を生成することをらに含む、請求項１記載の方法。
【請求項１１】
検索空間内の一以上の候補ビデオ・ブロックのピクセルに関連して符号化されるビデオ・ブロックの多数のピクセルについて並行して差分計算を行う差分プロセッサ、及び
少なくとも一部計算された差分計算に基づいて符号化されたビデオ・ブロックと候補ビデオ・ブロックとの間の類似のレベルを規定する差分値を生成し、受入れ可能な差分値をもたらす特定の候補を確認し、且つ特定の候補に動きベクトルを用いて符号化されるビデオ・ブロックを符号化するビデオ符号化制御器を具備するデバイス。
【請求項１２】
候補ビデオ・ブロックを記憶する候補メモリ、候補メモリ中の多数の出力バンクから各々の候補ビデオ・ブロックにおける多数のピクセルを再生する差分プロセッサをさらに具備する、請求項１１記載のデバイス。
【請求項１３】
ビデオ符号化制御器は候補ビデオ・ブロックの一つを確認するピクセル指数を生成し、デバイスが、
ピクセル指数を候補メモリ中の物理アドレスに変換するメモリ制御ユニット、物理アドレスに基づいて多数の出力バンクから候補ビデオ・ブロックにおける多数のピクセルを再生する差分プロセッサをさらに具備する、請求項１２記載のデバイス。
【請求項１４】
メモリ制御ユニットはピクセル指数を候補メモリ中の論理アドレスに変換し、且つ論理アドレスを候補メモリ中の物理アドレスに変換する、請求項１３記載のデバイス。
【請求項１５】
符号化されるビデオ・ブロック及び候補ビデオ・ブロックの各々はＭＰＥＧ‐４規格に準拠するピクセルの１６×１６配列を規定する、請求項１３記載のデバイス。
【請求項１６】
差分プロセッサは符号化されるビデオ・ブロックの一行における全てより少ないピクセルと検索空間内の候補ビデオ・ブロックとの間で並行して差分値を計算する、請求項１１記載のデバイス。
【請求項１７】
検索空間は縦列で配置される多数の候補ビデオ・ブロックの配列を規定する、請求項１１記載のデバイス。
【請求項１８】
並行して差分計算の計算のために検索空間中の候補ビデオ・ブロックによっを候補メモリを装荷するメモリ制御ユニットをさらに含む、請求項１７記載のデバイス。
【請求項１９】
ビデオ符号化制御器はＭＰＥＧ‐４規格の一つに従って符号化されるビデオ・ブロックを符号化する、請求項１１記載のデバイス。
【請求項２０】
差分計算を計算することは絶対差分計算を計算することを含む、請求項１１記載のデバイス。
【請求項２１】
検索空間内の一以上の候補ビデオ・ブロックのピクセルに関連して符号化されるビデオ・ブロックの多数のピクセルについて並行して差分計算を行う手段、
少なくとも一部計算された差分計算に基づいて符号化されるビデオ・ブロックと候補ビデオ・ブロックとの間の類似のレベルを規定する差分値を生成する手段、
受入れ可能な差分値をもたらす特定の候補を確認する手段、及び
特定の候補に動きベクトルを用いて符号化されるビデオ・ブロックを符号化する手段
を具備するデバイス。
【請求項２２】
候補メモリ中の多数の出力バンクから各々の候補ビデオ・ブロックにおける多数のピクセルを再生する手段をさらに具備する、請求項２１記載のデバイス。
【請求項２３】
候補ビデオ・ブロックの一つを確認するピクセル指数を受信する手段、
ピクセル指数を候補メモリ中の物理アドレスに変換する手段、及び
物理アドレスに基づいて候補ビデオ・ブロックにおける多数のピクセルを多数の出力バンクから再生する手段をさらに具備する、請求項２２記載のデバイス。
【請求項２４】
ピクセル指数を候補メモリ中の論理アドレスに変換する手段、及び
論理アドレスを候補メモリ中の物理アドレスに変換する手段をさらに具備する、請求項２３記載のデバイス。
【請求項２５】
符号化されるビデオ・ブロック及び候補ビデオ・ブロックの各々はＭＰＥＧ‐４規格に準拠するピクセルの１６×１６配列を規定する、請求項２３記載のデバイス。
【請求項２６】
符号化されるビデオ・ブロックの一行における全てより少ないピクセルと検索空間内の候補ビデオ・ブロックとの間で並行して差分値を計算する手段をさらに具備する、請求項２１記載のデバイス。
【請求項２７】
検索空間は縦列で配置される多数の候補ビデオ・ブロックの配列を規定する、請求項２１記載のデバイス。
【請求項２８】
検索空間中の候補ビデオ・ブロックによって候補メモリを装荷する手段、
符号化される第一のビデオ・ブロック及び候補メモリ中の候補ビデオ・ブロックにおける多数のピクセル間で並行して差分計算を行う手段、
検索空間における新しい縦列に対応する候補ビデオ・ブロックによって候補メモリの部分集合を再装荷する手段、及び
符号化される第二のビデオ・ブロック及び候補メモリ中の候補ビデオ・ブロックにおける多数のピクセルの間で並行して差分値を計算する手段を具備する、請求項２７記載のデバイス。
【請求項２９】
ＭＰＥＧ‐４規格の一つに従って符号化されるビデオ・ブロックを符号化する手段をさらに具備する、請求項２１記載のデバイス。
【請求項３０】
少なくとも一部計算された差分計算に基づいて符号化されるビデオ・ブロックの部分集合と候補ビデオ・ブロックの部分集合との間の類似のレベルを規定する差分値を生成する手段をさらに含む、請求項２１記載のデバイス。
【請求項３１】
ビデオ・ブロックを含むビデオ・フレームを獲得するビデオ獲得デバイス、
検索空間内の一以上の候補ビデオのピクセルに関して符号化されるビデオ・ブロックについて並行に差分計算を行い、少なくとも一部計算された差分計算に基づいて符号化されたビデオ・ブロックと候補ビデオ・ブロックとの間で類似のレベルを規定する差分値を生成し、受入れ可能な差分値をもたらす特定の候補を確認し、且つ特定の候補に動きベクトルを用いて符号化されるビデオ・ブロックを符号化するビデオ符号器、及び
符号化されたビデオ・ブロックを別のデバイスに伝送する送信器を具備する無線通信デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
この出願は２００２年６月１８日に出願され、本発明の譲請人に譲渡され、全てにおいてその全体が引用文献としてここに組込まれた「ビデオ動き推定システムにおける電力消費を低減する方法（Method to Reduce Power Consumption in a Video Motion Estimation System）」と題する米国特許出願仮番号第６０／３９０，１０１号の特典を主張する。
【０００２】
この明細書はディジタル・ビデオ処理、特にビデオ系列の符号化に関する。
【背景技術】
【０００３】
ディジタル・テレビジョン、直接ディジタル放送システム、無線通信デバイス、携帯情報機器（ＰＤＡ）、ラップトップ・コンピュータ、デスクトップ・コンピュータ、ディジタル・カメラ、ディジタル記録デバイス、セルラーまたは衛星無線電話等を含む、広範囲のデバイスにディジタル・ビデオ機能が組込まれている。ディジタル・ビデオ・デバイスはフルモーション・ビデオ系列（ビデオ信号）を創成し、修正し、伝送し、記憶し、記録し、且つ再生（playing）する際、従来のアナログ・ビデオ・システムよりもかなりの改善を行うことができる。
【０００４】
種々なビデオ符号化規格がディジタル・ビデオ信号を符号化するために制定された。例えば、動画専門委員会（Moving Picture Experts Group：ＭＰＥＧ）はＭＰＥＧ‐１、ＭＰＥＧ‐２、及びＭＰＥＧ‐４を含むいくつかの規格を作成した。他の規格としては、ＩＴＵ  Ｈ．２６３、カリフォルニア州クパチノのアップル・コンピュータ社により開発されたクイックタイム（商標  ＱｕｉｃｋＴｉｍｅTM）、ワシントン州レドモンドのマイクロソフト社より開発されたウィンドウズ用ビデオ（商標  WindowsTM）、インテル社により開発されたインデオ（商標  ＩｎｄｅｏTM）、ワシントン州シアトルのリアルネットワーク社からのリアルビデオ（商標  ＲｅａｌＶｉｄｅｏTM）、及びスーパーマック社により開発されたシネパック（商標  ＣｉｎｅｐａｋTM）がある。
【０００５】
多くのビデオ符号化規格は圧縮方式でデータを符号化することによって伝送速度を増大させる。圧縮はビデオ・フレームの効果的な伝送のため伝送するのに必要な全体のデータ量を低減することができる。例えば、ＭＰＥＧ規格は圧縮なしで達成できるよりも更に狭い帯域幅でビデオ及び画像伝送を容易にするために設計された画像及びビデオ圧縮技術を利用する。
【０００６】
例えば、ＭＰＥＧ規格は、フレーム間（inter-frame）圧縮を行うために、時間的或いはフレーム間相関と呼ばれ、連続するビデオ・フレームの間の類似性を利用するビデオ符号化技術に対応する（support）。フレーム間圧縮技術はビデオ・フレームのピクセル（画素）基準の表現を動き表現に変換することによってフレームに亘るデータ冗長性を利用する。その上、さらにビデオ・フレームを圧縮するために、ビデオ符号化技術は空間的或いはフレーム内相関と呼ばれるフレーム内の類似を利用してもよい。フレーム内圧縮は一般に離散コサイン変換（ＤＣＴ）符号化のような静止画像を圧縮するテクスチャ符号化に基づいている。
【０００７】
圧縮を行うために、ディジタル・ビデオ・デバイスは一般にディジタル・ビデオ系列を圧縮するための符号器、及びディジタル・ビデオ系列を伸張するための復号器を含む。多くの場合、符号器及び復号器はビデオ画像の系列を規定するフレーム中のピクセルのブロックに作用する一体化された符号器／復号器（コーデック）を形成する。ＭＰＥＧ‐４規格では、例えば、符号器は伝送すべきビデオ・フレームを１６×１６ピクセル配列（pixel arrays）を含むマクロブロックに分割する。
【０００８】
ビデオ・フレーム中の各マクロブロックについて、符号器は最も類似するマクロブロックを鑑定するため直ぐ前のビデオ・フレーム（或いは、次のフレーム）を探し、前のいずれのマクロブロックが符号化に使用されたかを指示する動きベクトルとともに、伝送のためマクロブロック間の差分を符号化する。復号器は動きベクトルと符号化された差分を受信し、そしてビデオ系列を生成するために動き補償を行う。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
特に、動き推定技術が使用されるとき、ビデオ符号化処理は計算的に強烈である。例えば、符号化されるビデオ・ブロックを前に伝送されたフレームと比較する処理は多数の計算を必要とする。改良符号化技術は特に計算資源が非常に制限され、且つ電力消費が関心事である無線デバイスまたは携帯ビデオ・デバイスでの使用においては非常に望ましい。同時に、圧縮法の改良はビデオ系列の効果的な伝送に必要とされる帯域幅を低減するために望ましい。特に無線及び他の限られた帯域幅設定において、一以上のこれらの要素を改善することはビデオ系列の実時間符号化を促進し、もしくは改良する。
【課題を解決するための手段】
【００１０】
この明細書はビデオ系列を符号化するために必要な処理サイクル及びメモリ移転の数を低減することが可能なビデオ符号化技術を述べる。このように、開示されたビデオ符号化技術はビデオ符号化速度を増加させ、そして電力消費を減少させる。その上、それらの技術は符号化されるマクロブロックに関連する差分値を規定し、そして符号化されるマクロブロックを形成する様々なマイクロブロックと関連する差分値を規定するために同じ計算の組を使用する。
【００１１】
ここに述べられるビデオ符号化技術は動き推定ルーチンのための検索空間を縦列的に記憶する候補メモリを使用する。メモリ制御ユニットは、例えば、絶対差分和（Sum of Absolute Difference：ＳＡＤ）または二乗差分和（Sum of Squared Difference：ＳＳＤ）技術を用いて、符号化されるビデオ・ブロックのピクセルとの同時比較に並行して多数のピクセルを再生するために候補メモリを指定（address）することができる。差分プロセッサは並行して計算を行う。並行計算の各組はマクロブロックを形成する一つのマイクロブロックの列に対応する。その上、符号化されるビデオ・ブロックについて、候補メモリは全体の検索空間を再装荷するのではなく、ビデオ・ブロックの新しい縦列を装荷することによって増加的に更新することができる。
【００１２】
ここに述べられたこれら及び他の技術はハードウェア、ソフトウェア、ファームウェア、またはそのある組合せにおいてディジタル・ビデオ・デバイスで実施される。ソフトウェアにおいて実施されるとすれば、その技術はプログラム・コードを含むコンピュータ可読媒体に適用され、それが実行されたとき、ここに述べられる一以上の符号化技術を実行する。別の様々な実施例の詳細は下記の付属の図及び記述において示される。他の特徴、目的及び利点は記述及び図から、及び請求項から明白になるであろう。
【発明を実施するための最良の形態】
【００１３】
一般に、この明細書はディジタル・ビデオ・データの符号化を改良するために使用できるビデオ符号化技術に関する。ビデオ符号化技術はビデオ系列を符号化するために必要な処理サイクル（cycles）及びメモリ移転の数を低減し、それによってビデオ符号化速度を増加し、且つ電力消費を低減させる。例えば、ビデオ符号化技術は計算の効率、特にビデオ符号化処理の最も計算的に強烈な形態である、動き推定処理に関する計算の効率を増加させる。さらに、ビデオ符号化技術はＭＰＥＧ‐４規格のような復号規格と互換性がある。
【００１４】
ビデオ符号化技術はディジタル放送システム、携帯情報機器（ＰＤＡ）、ラップトップ・コンピュータ、デスクトップ・コンピュータ、ディジタル・カメラ、ディジタル記録デバイス、携帯電話等といった様々なディジタル・ビデオ・デバイスにおいて実施される。ビデオ符号化技術はＭＰＥＧ‐４のような規格に従ってビデオ符号化の効率を改善し、そして計算資源が非常に制限され、且つ電力消費が関心事である、携帯電話のような無線通信デバイス中でビデオ符号化の実施をよりよく促進する。
【００１５】
ビデオ符号化技術は検索空間にビデオ・ブロックを縦列的に記憶する候補メモリを使用する。メモリ制御ユニットは、例えば、絶対差分和（Sum of Absolute Difference：ＳＡＤ）または二乗差分和（Sum of Squared Difference：ＳＳＤ）技術を用いて、符号化されるビデオ・ブロックのピクセルとの同時比較に並行して多数のピクセルを再生するために候補メモリをアドレス指定することができる。差分プロセッサは並行して計算を行う。何回かの並行計算の後で、差分プロセッサは符号化されるビデオブロックと比較される検索空間の候補ビデオブロックに関連する差分値 （しばしば差分測定基準と云われる）の形で検索結果を生成することができる。さらに、符号化される次のビデオ・ブロックについて、候補メモリは全体の検索空間を再装荷するのでなく、増加的にビデオ・ブロックの新しい縦列を装荷することによって更新することができる。そのような縦列の更新は電力消費及びシステム・バス使用を低減することができ、新しい検索空間を装荷するために要する時間を低減する。
【００１６】
図１は発信デバイス１２が通信回線を介してビデオ・データの符号化系列を受信デバイス１４に伝送するシステム例１０を例示するブロック図である。発信デバイス１２及び受信デバイス１４は双方ともディジタル・ビデオ・デバイスである。特に、発信デバイス１２は、例えば、動画専門委員会（Moving Picture Experts Group）によって開発されたＭＰＥＧ‐４といった様々なビデオ圧縮規格のある一つを使用してビデオ・データを符号化して伝送する。他の規格は動画専門委員会によって開発されたＭＰＥＧ‐１、ＭＰＥＧ‐２または他のＭＰＥＧ規格、ＩＴＵ  Ｈ．２６３及び類似の規格、動画ＪＰＥＧ２０００、カリフォルニア州クパチノのアップル・コンピュータ社により開発されたクイックタイム（商標  ＱｕｉｃｋＴｉｍｅTM）技術、ワシントン州レドモンドのマイクロソフト社より開発されたウィンドウズ用ビデオ（商標  WindowsTM）、インテル社により開発されたインデオ（商標  ＩｎｄｅｏTM）、及びスーパーマック社により開発されたシネパック（商標  ＣｉｎｅｐａｋTM）を含む。
【００１７】
通信回線１５は無線回線、物理伝送回線、ローカル・エリア・ネットワークといったパケット準拠ネットワーク、広域ネットワーク、またはインターネットのようなグローバル・ネットワーク、公衆電話網（ＰＳＴＮ）、等々を含む。このように、通信回線１５は、発信デバイス１２から受信デバイス１４へビデオ・データを伝送するためのある適当な通信媒体、または恐らくは異なるネットワーク及び回線の集合を表す。
【００１８】
発信デバイス１２はビデオ・データを符号化して伝送することが可能なあるディジタル・ビデオ・デバイスである。例えば、発信デバイス１２はディジタル・ビデオ系列を記憶するビデオ・メモリ１６、ビデオ系列を符号化するビデオ符号器１８、及び通信回線１５上で符号化系列を受信デバイス１４へ伝送する送信器２０を含む。例えば、ビデオ符号器１８はビデオ符号化技術を制御する一以上のプログラム可能ソフトウェア・モジュールを実行するディジタル信号プロセッサ（ＤＳＰ）を含む。関連するメモリ及び論理回路はビデオ符号化技術を制御する際にＤＳＰを支援するために提供される。記述されであろうが、ビデオ符号器１８は処理サイクル、メモリ移転、及び電力消費を低減するように構成される。さらに、ビデオ符号器１８はマクロブロックを形成するマイクロブロックの様々な差分値と同様にマクロブロックについて差分値を生成するため一組の計算を行うように構成することができる。
【００１９】
さらに、ビデオ系列を獲得し、且つ獲得した系列をメモリ１６に記憶するために、発信デバイスはビデオ・カメラのようなビデオ獲得デバイス２３を含む。特に、ビデオ獲得デバイス２３はビデオ画像またはディジタル・ビデオ系列を獲得することが可能な電荷結合素子（ＣＣＤ）、電荷注入デバイス、フォトダイオード・アレイ、相補型金属酸化膜半導体（ＣＭＯＳ）デバイス、または他の或る感光デバイスを含む。
【００２０】
さらなる例として、ビデオ獲得デバイス２３は、例えば、テレビジョン、ビデオカセット・レコーダ、ビデオ・カメラ等々からアナログ・ビデオ・データをディジタル・ビデオ・データに変換するビデオ変換器である。いくつかの実施例では、発信デバイス１２は実時間ビデオ系列を通信回線１５上で伝送するように構成される。そのような場合には、受信デバイス１４は実時間ビデオ系列を受信してユーザーにビデオ系列を表示する。代って、発信デバイス１２は受信デバイス１４にビデオ・データ・ファイルとして、即ち、実時間ではなく送信されるビデオ系列を獲得して符号化する。このように、発信デバイス１２は、例えば、移動無線ネットワークにおいて、ビデオ・クリップ再生、ビデオ・メイル、またはテレビ会議といったアプリケーションに対応する。
【００２１】
受信デバイス１４はビデオ・データを受信して復号することが可能な或るディジタル・ビデオ・デバイスの形を取る。例えば、受信デバイス１４は、例えば、中間回線、ルーター、他のネットワーク設備等々を経由して符号化されたディジタル・ビデオ系列を受信する受信器２２を含む。受信デバイス１４はまた系列を復号するビデオ復号器２２、及び系列をユーザーに表示する表示デバイス２６を含む。いくつかの実施例では、受信デバイス１４は一体化された表示デバイス２６を含まない。むしろ、受信デバイス１４は個別の表示デバイス、例えば、テレビジョンまたはモニターを駆動するために受信ビデオ・データを復号する。
【００２２】
発信デバイス１２及び受信デバイス１４のデバイス例はコンピュータ・ネットワーク、ワークステーションまたは他のデスクトップ型計算デバイス、及びラップトップ・コンピュータまたは携帯情報機器（ＰＤＡ）といったモバイル計算デバイス上に設置されたサーバーを含む。他の例は、ディジタル・テレビジョン、ディジタル・カメラ、ディジタル・ビデオ・カメラまたは他のディジタル記録デバイス、ビデオ機能を持つ携帯電話のようなディジタル・ビデオ電話、他の無線ビデオ・デバイス、等々といったディジタルテレビ放送衛星及び受信デバイスを含む。
【００２３】
いくつかの場合には、発信デバイス１２及び受信デバイス１４は各々ディジタル・ビデオ・データを符号化及び復号する符号器／復号器（コーデック（CODEC））を含む。その場合には、発信デバイス１２及び受信デバイス１４双方はメモリや表示装置（displays）と同様に送信器及び受信器を含む。下で概説される多数の符号化技術は符号器を含むディジタル・ビデオ・デバイスの文面で記述される。しかしながら、符号器はコーデックの一部を形成することは了解されている。その場合には、コーデックはＤＳＰ、マイクロプロセッサ、特定用途向け集積回路（ＡＳＩＣ）、個別ハードウェア部品、またはその様々な組合せによって実施される。
【００２４】
発信デバイス１２中のビデオ符号器１８はビデオ・データを符号化するためにビデオ・フレームの系列中のピクセルのブロックに作用する。例えば、ビデオ符号器１８は伝送されるビデオ・フレームがピクセルのブロック（ビデオ・ブロックと云われる）に分割される動き推定符号化技術を実行する。説明のために、ビデオ・ブロックはマイクロブロック及びマクロブロックを含む。例として、マイクロブロックは８×８配列のピクセルである。マクロブロックは１６×１６配列のピクセルである。従って、マクロブロックは４マイクロブロックを含む。そのようなフォーマットはＭＰＥＧ‐４準拠の符号化技術においてしばしば使用される。しかしながら、他のマイクロブロック及びマクロブロックの大きさも使用することができる。一般に、この明細書では、用語「マクロブロック」及び「マイクロブロック」は複数のピクセルを含むビデオ・ブロックを意味する。マクロブロックはさらに複数のマイクロブロックとして規定される。マクロブロックを規定するマイクロブロックの数、マイクロブロックを規定するピクセルの数、同様にマクロブロックを規定するピクセルの数は多種多様な実施特定のフォーマットに従う。
【００２５】
時々、改良された分解法はマクロブロックよりむしろマイクロブロックの動き推定を計算することによって達成できる。さらに、下でさらに詳細に説明されるように、マクロブロックの差分値の計算と並行してさらに小さなマイクロブロックに関する、差分測定基準とも云われる、差分値の計算を許容するようにマクロブロックのピクセルは記憶、または指定される。すなわち、マクロブロックの差分測定基準の計算はマクロブロックを形成する四つのマイクロブロックに関する差分測定基準の四つの計算と見なされる。従って、マクロブロックを形成するマイクロブロックと同様に、マクロブロックに関する差分測定基準はまた同じ計算から生成することができる。特に、そのような技術は余計なＳＡＤまたはＳＳＤ計算をすることなく促進される。むしろ、同じ計算がマイクロブロック差分値の計算及びマクロブロック差分値の計算であるとして符号器によって解釈できるようにアドレス指定及び計算手法を設計することができる。
【００２６】
マイクロブロックまたはマクロブロック中の各ピクセルはｎビット値、例えば、８ビットで表され、それは色及び強度、例えば、色度及び輝度といった視覚特性を規定する。しかしながら、人間の視覚は色より輝度の変化に対して敏感であるから、動き推定は輝度成分のみに通常は行われる。従って、動き推定のために、全体のｎビット値は所定のピクセルの輝度を定量化している。しかしながら、この明細書の原理はそのピクセルのフォーマットに限定されず、もっと簡単な数ビットのピクセル・フォーマット、またはさらに複雑な大きなビットのピクセル・フォーマットで使用するために拡張される。
【００２７】
ビデオ・フレーム中の各ビデオ・ブロックについて、発信デバイス１２のビデオ符号器１８は既に伝送された前のビデオフレーム（または、次のビデオ・フレーム）についてメモリ１６に記憶されたビデオ・ブロックを検索し、符号化に使用された前のフレーム（または、次のフレーム）からビデオ・ブロックを識別する動きベクトルと共に、ビデオ・ブロック間の差分を符号化する。このように、各フレームを独立した画像（picture）として符号化する代りに、ビデオ符号器１８は隣接フレーム間の差分を符号化する。動き推定は符号化される現在のフレーム中のマイクロブロックまたはマクロブロックに最もよく適合する前または次のフレーム中のマイクロブロックまたはマクロブロックの識別を包含する。
【００２８】
動きベクトルについて他のフォーマットも使用できるが、動きベクトルはビデオ・ブロックの左上角に関連するピクセル場所を規定する。いずれにせよ、動きベクトルを使用してビデオ・ブロックを符号化することによって、ビデオ・データ・ストリームの伝送に必要な帯域幅は著しく低減することができる。いくつかの場合には、発信デバイス１２は計算の数を低減し、且つ電力を保存するために符号化処理の間様々な比較または計算の終了をもたらすことができるプログラム可能な閾値を与える。
【００２９】
受信デバイス１４の受信器２２は動きベクトル及び符号化差分の形で符号化ビデオ・データを受信する。復号器２４は表示デバイス２６によってユーザーに表示のためのビデオ系列を生成するために動き補償技術を実行する。受信デバイス１４の復号器２４もまた符号器／復号器（コーデック）として実装される。その場合には、発信デバイス１２及び受信デバイス１４双方はディジタル・ビデオ系列を符号化し、受信し、且つ復号することが可能である。
【００３０】
図２はここに述べられた技術に従ってディジタル・ビデオ系列を符号化するビデオ符号器１８を例示するブロック図である。図２は典型的な実施を表し、明細書を限定するものと考えられるべきでない。図２に示されるように、ビデオ符号器１８はディジタル信号プロセッサ（ＤＳＰ）２８及び動き推定器２９を含む。ＤＳＰ２８は動き推定器２９の動作を制御し、ビデオ符号化制御器として働く。代りに、ビデオ符号化制御器はプロセッサ、ハードウェア要素、ファームウェア、特定用途向け集積回路（ＡＳＩＣ）フィールド・プログラマブル・ゲートアレイ（ＦＰＧＡ）等によって実現することができる。
【００３１】
図２の例では、ＤＳＰ２８はビデオ符号化技術を制御するため一以上のプログラム可能なソフトウェア・モジュールを実行する。動き推定器２９はＤＳＰインタフェース３０を含む。ＤＳＰ２８、ＤＳＰインタフェース３０及びビデオ・メモリ３２はバス３３を介して通信する。ビデオ・メモリ３２はビデオ符号器１８への外部部品と見なされるか、またはビデオ符号器１８の一部として一体化される。ＤＳＰインタフェース３０は動き推定ルーチンに関連する計算を行う差分プロセッサ３４と相互に作用する。例えば、差分プロセッサ３４は所定のビデオ・フレームについて符号化されるブロックまたはマクロブロックの動きベクトルを計算するためにＳＡＤまたはＳＳＤ計算を実行する。符号化アルゴリズムの制御をＤＳＰ２８に知らせ、且つ動き推定器２９のハードウェア内で計算のために計算的に強烈な動き推定を分離することによって、実時間符号化に対応する能力を向上させることができる。
【００３２】
さらに図２に示されるように、差分プロセッサ・メモリ３５は符号化メモリ３６及び候補メモリ３８を含む。符号化メモリ３６は動き推定ルーチンを用いて符号化される現在のマクロブロックを記憶する。現在のマクロブロックは符号化されるビデオ・フレームの配列（array）の一つに対応する。候補メモリ３８は検索空間を形成する別のフレームからのマクロブロックの配列を記憶する。差分プロセッサ３４は動きベクトルとして使用のための最良の適合を確認するために候補メモリ３８中のマクロブロックを符号化メモリ３６中のマクロブロックと比較する。例として、４８×４８の検索空間が使用される。その場合には、検索空間は９マクロブロック、各々が１６×１６配列のピクセルを含む３マクロブロックの３縦列を含むであろう。他のマクロブロックもまた検索空間を規定する二以上の９マクロブロックからのピクセルを含む４８×４８ピクセル配列検索空間内で規定することができる。
【００３３】
メモリ制御ユニット３９は動き推定ルーチンのための検索処理を働かすために候補メモリ３８及び符号化メモリ３６のアドレス指定を制御する。特に、メモリ制御ユニット３９は検索空間を形成するためにバス３３を経由してビデオ・メモリ３２から候補メモリ３８へのピクセル・データの装荷を制御する。この目的のために、メモリ制御ユニット３９はメモリ・アドレス変換を行うために装備される。ＤＳＰ２８による介入なしで全体の４８×４８ピクセル検索空間を候補メモリ３８へ直接装荷することはＤＳＰ２８とＤＳＰインタフェース・ユニット３０との間でバス活動を低減させ、そしてビデオ・データを移動するのに必要とされるＤＳＰ２８において必要な指令数を低減することができる。差分プロセッサ３４は各マクロブロックに関するＳＡＤまたはＳＳＤの結果を判定し、最良の適合結果をＤＳＰインタフェース３０に返す。ＤＳＰインタフェース３０は、交互に、符号化されたマクロブロック及び動きベクトルをバス３３経由でビデオ・メモリ３２に記憶のためにＤＳＰ２８に提供する。
【００３４】
動作では、ＤＳＰ２８は制御チャネル４０経由で検索処理を動かすためにＤＳＰインタフェース・ユニット３０を制御する。一般に、制御チャネル４０はメモリ装荷命令について使用され、それは候補メモリ３８に装荷される検索空間に関するピクセル指数を含む。他のフォーマットも使用されるであろうが、各ピクセル指数は左上角または候補マクロブロックのアドレスを指示する。さらに、ＤＳＰ２８はデータ・チャネル４１経由で差分プロセッサ３４によって生成された検索結果を受信する。データ・チャネル４１はまたハードウェア構成及びモード切替のために使用される。ＤＳＰ２８とビデオ・メモリ３２との間のメモリ移転はバス３３上の直接メモリ交換（Direct Memory Exchange：ＤＭＥ）ポート及びバス３３経由で達成される。この場合には、ＤＳＰインタフェース・ユニット３０、差分プロセッサ３４、符号化メモリ３６、候補メモリ３８及びメモリ制御ユニット３９はＤＳＰ２８によって制御された全体の動き推定器（ＭＥ）中にある。一般に、ＤＭＥは符号化メモリ３６及び候補メモリ３８へ装荷するためにビデオ・メモリ３２からデータを取って来るために使用される。
【００３５】
図２の例では、ＤＳＰインタフェース・ユニット３０はバス３３及びメモリ制御ユニット３９経由でビデオ・メモリ３２から符号化メモリ３６及び候補メモリ３８へのメモリ移転のためのスレーブとして役立つ。初めに、ＤＳＰインタフェース・ユニット３０は候補メモリ３８中に全体の検索空間を装荷する。それ以降、ＤＳＰインタフェース・ユニット３０は、例えば、符号化される所定のフレーム内の次のブロックとして新しい縦列を検索空間に加えるために候補メモリ３８を増加的に更新する。ＤＳＰインタフェース・ユニット３０はビデオ・データ及びメモリ制御ユニットの配置の移転のためのデータ及び配置チャネルを有する。さらに、ＤＳＰインタフェース・ユニット３０は差分プロセッサ３４によって行われる検索処理を制御するための配置チャネル及び検索結果を受信するための結果チャネルを有する。
【００３６】
図２の例では、ビデオ符号器１８は受信デバイスへ伝送のためホスト発信デバイス１２に圧縮ディジタル・ビデオ系列を提供する。ビデオ符号器１８はビデオ系列を符号化し、伝送の前にビデオ・メモリ３２内で符号化ディジタル・ビデオ系列を緩衝記憶（バッファ）する。ビデオ・メモリ３２は、差分プロセッサ・メモリ３５と同様に、同期的ダイナミック・ランダム・アクセス・メモリ（ＳＤＲＡＭ）、フラッシュ（ＦＬＡＳＨ）メモリ、 電気的消去可能プログラム可能読取専用メモリ（ＥＥＰＲＯＭ）等々の形をとる。符号化メモリ３６及び候補メモリ３８は一般的にビデオ符号器１８の局部メモリであり、「仮想」メモリに分離された一般のメモリ・デバイスを含む。
【００３７】
図２に例示された要素に加えて、いくつかの実施例では、ビデオ符号器１８は、離散コサイン変換（ＤＣＴ）符号化といった、静止画像を圧縮するために普通に使用されるフレーム内またはフレーム間圧縮を行うテクスチャ符号器のような他の要素を含む。例えば、テクスチャ符号化は動き推定に加えて、或いは恐らくは動き推定の代わりに、処理能力が効果的な動き推定にはあまりにも限定されていると思われるシナリオにおいて行われる。ＤＳＰ２８はその時々に処理能力に基づいて動き推定器（２９）及びテクスチャ符号器（示されてない）を選択的に作動させることによって符号化ルーチンを指令する。
【００３８】
図３はビデオ・フレームをビデオ・メモリ３２内に記憶できるマクロブロック４２の形でビデオ・ブロック例を例示する。ＭＰＥＧ規格及び他のビデオ符号化手法は動き推定ビデオ符号化の間にマクロブロックの形式においてビデオ・ブロックを使用する。上で述べられたように、ＭＰＥＧ‐４準拠のシステムにおいて、用語「マクロブロック」はビデオ・フレームの部分集合を形成するピクセル値の１６×１６の集まりを意味する。さらに大きい、或いはさらに小さいビットもまた所望の画像品質を得るように各ピクセルを規定するために使用されるであろうが、各ピクセル値は１バイトのデータで表される。マクロブロックはいくつかのさらに小さな８×８ピクセル・マイクロブロック４４Ａ〜４４Ｄを含む。一般に、しかしながら、ここに述べられた符号化技術は１６バイト×１６バイト・マクロブロック、８バイト×８バイト・マイクロブロック、または別の大きさのビデオ・ブロックといった、或る規定された大きさのブロックを使用して動作する。
【００３９】
図４は候補メモリ３８中に記憶できる検索空間４６の部分例を例示する。検索空間４６は前に伝送されたビデオ・フレーム（或いは、一連のフレームの次のビデオ・フレーム）に対応するピクセルの集まりである。検索空間はそのままの前または次のビデオ・フレーム、または必要であればビデオ・フレームの部分集合を含む。検索空間は、例示のように、矩形であってもよく、もしくは様々な形状及び大きさのどれでもよい。
【００４０】
ビデオ符号化の間、符号化された現在のマクロブロックは、現在のマクロブロックと検索空間中の類似マクロブロックとの間の差分が同様のビデオ・ブロックを確認する動きベクトルと共に伝送できるように十分な適合を確認するために検索空間のビデオ・ブロックと比較される。上で述べられたように、検索空間４６中で規定されたマクロブロック４８は候補メモリ３８に記憶でき、一方、符号化された現在のマクロブロックは符号化メモリ３６に記憶することができる。
【００４１】
動き推定ビデオ符号化の間、差分プロセッサ３４はＳＡＤ及びＳＳＤ技術といった比較技術を使用して符号化される現在のマクロブロックを前または次のフレームのマクロブロックと比較することができる。図４に示されたように、検索空間４６中のマクロブロックはそれぞれのマクロブロックに関する左手上のピクセル・アドレス４８によって確認することができる。他の比較技術もまた使用される。気付かれるごとく、この明細書の原理に従って、ＳＡＤ及びＳＳＤ計算は多数のピクセルについて並行して行うことができる。さらに、ピクセルに関する比較の指定及び計算順序は、マクロブロックを形成するマイクロブロックに関する差分値と同様に、符号化される各マクロブロックに関する差分値の生成をもたらすように行うことができる。
【００４２】
この明細書では、用語「タスク」は現在のビデオ・ブロックを検索空間内の別のビデオ・ブロックと比較するために使用される計算の一般の集合を意味する。即ち、タスクは現在のビデオ・ブロックと検索空間中の別のビデオ・ブロックとの間の単一の比較を意味する。例えば、タスクは現在のビデオ・ブロックのいくつかのピクセルを検索空間中の候補ビデオ・ブロックのそれらと比較するためにいくつかの計算を行うことを含む。ここに述べられたように、これらのタスク計算の様々な部分は符号化処理を加速するために並行して実行される。６４個の計算は（マイクロブロックが８×８ピクセル配列として規定されることを仮定する）マイクロブロック・タスクと見なされ、２５６個の計算は（マイクロブロックが１６×１６ピクセル配列として規定されることを仮定する）マイクロブロック・タスクと見なされる。各タスクの間、計算はタスクに関する進行中の差分値（時折、差分測定基準と云われる）を規定するために累積される。
【００４３】
この明細書では、用語「反復（iteration）」はビデオ符号化の間に行われるタスクの一般の集合を意味する。現在の符号化されるビデオブロックと関連する一連の完全なタスクは反復である。即ち、反復は現在のビデオ・ブロックが検索空間中の一組の前のビデオ・ブロック（または、次のビデオ・ブロック）と比較される一組の比較である。各個々の比較はいくつかの計算を包含するタスクである。このように、検索空間は反復の間に現在のビデオ・ブロックと比較される一組のビデオ・ブロックを規定する。反復の各比較はタスクと云われ、各タスク、即ち、各比較はいくつかの計算を包含する。
【００４４】
いくつかの場合には、反復は検索空間に関する第一の検索を規定すること、検索空間における第一の適合を確認すること、第一の適合に基づいて検索空間の部分集合に関する第二の検索を規定すること、及び部分集合における第二の適合を確認することを含む。例えば、反復の後検索は最良の適合をさらに十分に正確に指摘するために検索空間内における僅かな偏移を包含する。最低の差分値をもたらすマクロブロックを確認するピクセル場所がダイヤモンド形検索パラメータの中心に集まるまで検索が続くダイヤモンド検索技術といった他の検索技術もまた使用することができる。さらに、最低の差分値をもたらすマクロブロックを確認するピクセル場所が半径（Ｒ）によって規定される検索パラメータの中心に集まる円検索技術のような他の技術が使用される。半径（Ｒ）の円はダイヤモンド検索パラメータより大きく、さらに包括的な検索パラメータを規定することができる。
【００４５】
ダイヤモンド検索技術または円検索技術が反復の間に使用されれば、初期化技術もまたダイヤモンド形検索パラメータまたは円で規定される検索パラメータの中心において最低の差分値をもたらすマクロブロックを確認する処理を加速するために使われる。例えば、空間冗長性の現象を利用する初期化技術が使用される。所定のビデオ・ブロックのビデオの動きが所定のビデオ・ブロックに対して近い空間近傍における別のビデオ・ブロックのビデオの動きに類似しているであろうことを空間冗長性は一般に予測する。初期化技術は効果的なビデオ符号化のために使用できるビデオ・ブロックを含む非常に高い確率を有する検索空間内の場所における推定を初期化するためにこの現象を直ちに利用することができる。
【００４６】
特に、初期化技術は動き推定ルーチンが初期化できる検索空間内の場所、即ち、動き推定ルーチンが始まる検索空間内のピクセル場所を確認するために符号化されるビデオ・ブロックに近い空間近傍におけるビデオ・ブロックについて計算された動きベクトルを利用する。例えば、平均ピクセル場所、中央のピクセル場所または重み付け関数を使用して計算されるピクセル場所は符号化されるビデオ・ブロックに近い空間近傍におけるビデオ・ブロックについて前に決定された動きベクトルに基づいて計算される。他の線形または非線型関数もまた使用できるであろう。いずれにせよ、動き推定をこのように初期化することによって、ビデオ符号化は符号化されるビデオ・ブロックに受入れ可能な適合である検索空間内のビデオ・ブロックを位置決めするに要する反復におけるタスクの数を低減することによってダイヤモンド検索または円検索シナリオにおいて加速される。
【００４７】
差分値を生成するために使用される計算はＳＡＤ技術、ＳＳＤ技術、または必要であれば、他の比較技術を包含する。ＳＡＤ技術は、現在のマクロブロックが比較されつつある前のマクロブロックのピクセル値によって、符号化される現在のマクロブロックのピクセル値間の絶対差分計算を行うというタスクを包含する。これらの絶対差分計算の結果は、現在のマクロブロックと現在のビデオ・ブロックが比較されつつある前のマクロブロックとの間の差分を表している差分値を規定するために、合計、即ち、累積される。８×８ピクセル画像ブロックについて、６４個の差分が計算され、且つ合計され、そして１６×１６ピクセルのマクロブロックについては２５６個の差分が計算され、且つ合計される。現在のビデオ・ブロックをアドレス指定し、特定の順番に計算を行うことによって、２５６個の差分は計算されるが、また差分値が各マイクロブロックについて生成できるように四つの個別の組において合計される。そして、四組の全ての計算の全合計はマクロブロックについて差分値を規定することができる。
【００４８】
現在のマクロブロックと比較されつつあるマクロブロックがより良い適合であり、このようにより高い差分値、即ち歪みの増加をもたらす候補マクロブロックよりも動き推定における使用により良い候補であることをより低い差分値は一般に示している。いくつかの場合では、累積差分値が規定された閾値を越えるとき、計算は終結する。そのような場合には、現在のビデオ・ブロックと比較されつつあるマクロブロックは動き推定符号化における効果的な使用に受入れできないであろうから、追加の計算は不必要である。
【００４９】
ＳＳＤ技術はまた現在のマクロブロックが比較されつつある前のマクロブロックによって符号化される現在のマクロブロックのピクセル値間の差分計算を行うというタスクを包含する。しかしながら、ＳＳＤ技術では、絶対差分計算の結果は二乗され、そして二乗された値は、現在のマクロブロックと現在のマクロブロックが比較されつつある前のマクロブロックとの間の差分を表している差分値を規定するために、合計、即ち累積される。代りに、平均二乗誤差（Mean Square Error：ＭＳＥ）、正規化相互相関関数（Normalized Cross Correlation Function：ＮＣＦＦ）、または別の適当な比較アルゴリズムといった他の比較技術が実行される。
【００５０】
いくつかの場合には、例えば、所定のタスクが前のタスクよりよい適合をもたらさないことを判定するとき、または所定のタスクが受入れ可能な適合をもたらすことを確認するとき、様々なタスクまたは反復は早く終結する。例えば、所定のタスクについて余分な計算が不必要であるときを確認する技術は使用することができる。特に、第二のタスクの計算の一部が前に計算された第一のタスクの差分値より大きい差分値を合計してもたらすとき、第二のタスクの終了が第一のタスクより低い差分値をもたらさないから第二のタスクについて余分な計算が不必要であることは一般に知られている。その場合には、第二のタスクは符号化性能を犠牲にせずに終結することができ、第三のタスクの実行はより迅速に始まることができる。
【００５１】
終結技術はまた反復レベル、またはタスクレベルと反復レベルの双方で行われる。一例では、反復閾値は受入れ可能、即ち、効果的なビデオ符号化に十分な値を規定する。その場合には、反復閾値によって受入れ可能と思われるように符号化される現在のビデオ・ブロックに適合する検索空間において候補ビデオ・ブロックを確認するタスクが行われれば、その反復は終結することができ、符号化される次のビデオ・ブロックは検索空間と比較することができる。その場合には、いくつかの不必要なタスクの実行は回避することができる。
【００５２】
多くの技術は符号化されるビデオ・ブロックを前のビデオ・フレームの前のビデオ・ブロックと比較する文面でここに述べられている。しかしながら、符号化されるビデオ・ブロックを次のビデオ・フレームの候補ビデオ・ブロックと比較するとき同じ技術が使用されることは了解済みである。いくつかの場合には、双方向の動き推定が使用され、そこでは符号化されるビデオ・ブロックが一以上の前のビデオ・フレームの様々な候補ビデオ・ブロック及び次のビデオ・フレームの様々なビデオ・ブロックと比較される。要約すれば、符号化されるビデオ・ブロックが前のビデオ・フレームの候補ビデオ・ブロックまたは次のビデオ・フレームの候補ビデオ・ブロックといった異なるビデオ・ブロックと比較されているときはいつでもここに述べられた多くの技術が使用される。即ち、検索空間は様々な異なる実施において様々な異なる候補によって装荷される。
【００５３】
図５は候補マクロブロックの配列として配置された典型的な検索空間５２中で符号化される現在のマクロブロック５０の概念図である。特に、図５に示されたように、検索空間５２は符号化されるマクロブロック５０との比較のために候補マクロブロックの３行５４Ａ〜５４Ｃ及び３縦列５６Ａ〜５６Ｃを含む。従って、図５の例では、検索空間５２は４８×４８ピクセル領域を形成する９個の１６×１６ピクセル・マクロブロックの配列を含む。符号化される現在のマクロブロック５０は差分プロセッサ３４を使用して検索空間５２においてマクロブロックと比較される。
【００５４】
ビデオ・メモリ３２と候補メモリ３８との間のメモリ移転及び関連する処理のオーバヘッドを低減させるため、一旦、検索空間５２が初めに装荷されると、検索空間に対して次の更新が必要に応じて縦列ごとに行われ得る。例えば、所定のフレームの次のマクロブロックを符号化するために、メモリ制御ユニット３９は、全体の検索空間５２を再装荷するのではなく、検索空間５２の左手縦列５６Ａにおける候補マクロブロックを単に置換える。
【００５５】
縦列ごとの更新を達成し、且つ同時に多数のピクセルについて行われる並行動き推定計算を可能にするために、メモリ制御ユニット３９はビデオ・メモリ３２、符号化メモリ３６及び候補メモリ３８に維持されるメモリ・アドレスの間の変換についてアドレス写像を実行するように構成される。符号化メモリ３６及び候補メモリ３８に関するデータ更新はビデオ・メモリを直接指定するバス３３を介してビデオ・メモリ３２の間で行われる。バス３３上でこの移転を初期化し、且つ制御するために、ＤＳＰ２８はＤＭＥポート経由でバス・マスターとして働く。
【００５６】
図６Ａはマクロブロック・ピクセル指数を例示する図である。図６Ａに示されたように、マクロブロック・ピクセル指数は四個のマイクロブロック（Ａ、Ｂ、Ｃ、Ｄ）に分割される。マクロブロック・ピクセル指数は１６×１６であり、一方、各々のマイクロブロックＡ、Ｂ、Ｃ、Ｄは８×８である。全体のマクロブロック・ピクセル指数は左手上のピクセルＹ０から右手下のピクセルＹ２５５（示されない）まである。ピクセル指数はＤＳＰ２８によって検索空間内でマクロブロックを追跡するために維持される。メモリ制御ユニット３９は、適用可能なように、ＤＳＰ２８によって提供されるピクセル指数をビデオ・メモリ３２、符号化メモリ３６または候補メモリ３８中の物理メモリのアドレスに変換するために働く。例えば、メモリ制御ユニット３９は変換されたアドレスを検索空間更新のための候補メモリ３８またはＳＡＤエンジンによるＳＡＤ計算のための符号化メモリ３６に提供する。
【００５７】
図６Ｂはビデオ・メモリ３２内のビデオ・データの配置を例示する図である。特に、図６ＢはＤＳＰ２８によって維持されるマクロブロック・ピクセル指数とビデオ・メモリ３２内のマクロブロック・ピクセル・データの物理配置との間の差分を例示する。図６Ｂに示されたように、ビデオ・メモリ３２は各マクロブロックについて６４行を生成し、４ピクセルの行に配置された６４アドレスにマクロブロック・ピクセル・データを記憶する。ピクセルにつき８ビットで、各行は３２ビットのデータを含む。このように、ＤＳＰ２８からピクセル指数に対応してビデオ・メモリ３２をアクセス指定するために、メモリ制御ユニット３９はピクセル指数をビデオ・メモリにおける物理アドレスに変換する必要がある。
【００５８】
図６Ｃは符号化メモリ３６中のビデオ・データの配置を例示する図である。図６Ｃに示されたように、符号化メモリ３６に記憶されるマクロブロック・ピクセル・データは行当たり８ピクセル（即ち、行当たり６４ビット）の３２行に配置される。この明細書に従って、符号化メモリ３６におけるメモリ配置は多数のピクセルについて同時に差分プロセッサ３４による並行絶対差分（ＡＤ）計算を促進する。特に、図６Ｃの例は一度に８ピクセルについて並行ＡＤ計算を可能にする符号化メモリ３６の物理配置である。さらに、マイクロブロックが８ピクセル幅を持つように規定されるとき、マイクロブロックが一般的に８ピクセル幅を持っているので図６Ｃの物理配置はマクロブロックと同様に異なる差分値がマイクロブロックについて生成されることを可能にする。符号化メモリ３６の幅は６４ビットでもよい。共に、図６Ａ〜６Ｃはいかにマクロブロック・ピクセル指数がビデオ・メモリ３２に写像されるか、そしていかにビデオ・メモリが差分プロセッサ・メモリ３５において物理符号化メモリ３６に写像されるかを例示する。
【００５９】
図７ＡはＤＳＰ２８によって維持される検索空間ピクセル指数を例示する図である。検索空間内のピクセル指数はＤＳＰ２８によって検索タスク、例えば、差分プロセッサ３４によって生成された結果（差分値）を創成するために使用される一組の計算を指定するために使用される。図７Ａの検索空間ピクセル指数は３マクロブロック×３マクロブロックに対応し、従って、２３０４ピクセル（３＊３＊１６＊１６）を含む。さらに図７Ａに示されたように、検索空間ピクセル指数は４８列を含み、それぞれは４８ピクセルを含む。
【００６０】
図７Ｂはビデオ・メモリ３２中の検索空間の配置を例示する図である。図７Ｂに示されたように、検索空間ピクセルの物理配置は、図６Ｂのマクロブロック・メモリ配置と同様に、行当たり４ピクセルを含む。さらに、そのピクセルは５７６行に配置される。ピクセル当たり８ビットで、４ピクセルの各行は３２ビットを含む。
【００６１】
図７Ｃは候補メモリ３８中の検索空間の配置を例示する図である。気付かれるごとく、符号化メモリ３６と同じように、候補メモリ３８は８ピクセルの行で配置される。全体の検索空間を記憶するために、候補メモリ３８は２８８行を含む。即ち、候補メモリ３８は８ビット・メモリ×２８８の８バンクとして配置される。各列は６４ビット幅である。符号化メモリ３６はマクロブロックのみを記憶し、候補メモリ３８は３マクロブロック幅ある検索空間を記憶し、全部で９マイクロブロックを含むが、メモリ３６、３８は８ピクセル幅の出力を有する。このように、符号化メモリ３６及び候補メモリ３８は符号化される各マクロブロックの即座の比較のため、即ち、一度に８ピクセルについて絶対差分値の並行計算を促進にするために配置される。さらに、符号化メモリ３６及び候補メモリ３８はマクロブロック差分値の計算の間マイクロブロック差分値の計算のために配置される。
【００６２】
また、多数のピクセルについて並行ＡＤ計算を可能にすることに加えて、候補メモリ３８は検索空間内の或るピクセルで開始するマクロブロックのアドレス指定を可能にするように配置される。さらに、述べられるように、候補メモリ３８の構造は縦列更新の増加、即ち、符号化される新しい各マクロブロックについて全体の検索空間を再装荷するのではなく、一度にマクロブロックの１縦列を装荷することを可能にする。そのような装荷技術は冗長なメモリ装荷を回避し、バス３３の使用を低減することによって電力を低減することができる。また一方、メモリ制御ユニット３９は検索空間ピクセル指数をビデオ・メモリ３２中の物理メモリ・アドレスに変換するために装備され、そしてビデオ・メモリから候補メモリ３８における対応する物理メモリ・アドレスにメモリ・アドレスを変換する。
【００６３】
図８Ａはマクロブロック縦列ピクセル指数を例示する図である。符号化される二つの隣接マクロブロックについて、適用可能な検索空間の間の差分はただ一つのマクロブロック縦列である。その結果、ただ一つのマクロブロック縦列は更新される必要がある。候補メモリ３８はこの形態を利用し、それによってビデオ・メモリ３２と候補メモリとの間の移転に必要とされるデータ帯域幅を下げるように配置される。図８Ａに示されたように、ＤＳＰ２８０によって維持されるマクロブロック縦列ピクセル指数は１６ピクセルの列に配置され、検索空間における単一縦列の長さ、即ち、４８行ある。このように、図８Ａに示されたマクロブロック・ピクセル指数は３マクロブロックの縦列に対応し、このように図７Ａの検索空間ピクセル指数の３分の１に対応する。
【００６４】
マクロブロック縦列ピクセル指数についてビデオ・メモリ３２における物理メモリ配置は全体の検索空間ピクセル指数のメモリ配置とは異なる。図８Ｂはビデオ・メモリ３２中でマクロブロック縦列配置を例示する図である。マクロブロック縦列について、ビデオ・メモリ３２は各々４ピクセルの１９２行を提供する。従って、ビデオ・メモリ３２は３２ビット幅を持つマクロブロック縦列を配置する。一旦、検索空間が最初のマクロブロックに関する候補メモリ３８に装荷されると、符号化される次の隣接マクロブロックに関する検索は新しい縦列を単に装荷することによって達成することができる。
【００６５】
縦列更新の間、メモリ制御ユニット３９は前の左手マクロブロック縦列を新しいマクロブロック縦列と置換する。そして、新しく装荷されたマクロブロック縦列は現在の右手マクロブロック縦列として指定される。さらに、前の中間マクロブロック縦列は新しい左手マクロブロック縦列として指定され、一方、前の右手マクロブロック縦列は新しい中間マクロブロック縦列として指定される。
【００６６】
したがって、検索空間は前の左手マクロブロック縦列を除去するために右に偏移すると見なされ、それによって新しい右手マクロブロック縦列の余地を作ることができる。この縦列更新動作の後で、候補メモリ３８中の検索空間は符号化メモリ３６中の次のマクロブロックを考えるのに適切である。
【００６７】
ＤＳＰ２８によって提供されるピクセル指数をメモリ制御ユニット３９内のビデオ・メモリ３２及び候補メモリにおける物理アドレスへ変換することによって、ＤＳＰは縦列偏移動作を追跡する必要性はない。結果として、ＤＳＰ２８は単に新しい右手マクロブロック縦列にピクセル指数を提供する必要がある。
【００６８】
図９は候補メモリ３８中のメモリ・バンクに関する基本アドレスへのピクセル指数の変換において使用するメモリ制御ユニット３９の一部を形成する典型的な回路構成を例示するブロック図である。図９に示されたように、メモリ制御ユニット３９はこのメモリ・アドレス変換を達成するために適切な論理回路構成を含む。メモリ制御ユニット３９は符号化メモリ３６の更新、候補メモリ３８の更新または完全装荷または差分プロセッサ３４が符号化メモリ及び候補メモリの内容について並行ＡＤ計算を実行する検索タスクといった現在の反復を追跡する。述べられるように、メモリ制御ユニット３９はまた検索の間にブロック境界を追跡し、候補メモリ３８においてマクロブロック縦列偏移を管理し、そしてピクセル対アドレス変換を実行する。
【００６９】
一般に、検索について、メモリ制御ユニット３９は対応する開始バンク、即ち、次の式：
開始ピクセルのバンク＝ｍｏｄ８（ピクセル指数）    （１）
に従って候補メモリにおける８ピクセルの行内の位置を決定する。さらに、メモリ制御ユニット３９は次の式：
開始ピクセルの行＝ｉｎｔ（ピクセル指数／８）      （２）
に従って開始ピクセルの行を決定する。このように、ｍｏｄ関数（１）に従って、開始バンクは８で除算されたピクセル指数の剰余である。整数分割関数（２）に従って、開始列はピクセル指数によって除算可能な最大整数である。
【００７０】
上の式（１）及び（２）が与えられると、それぞれのバンクｘの開始または「基本（base）」アドレスは次のように表される：
バンクｘの基本アドレス＝開始ピクセルの行  （ｘ≧開始ピクセルのバンク）
＝開始ピクセルの行＋１  （ｘ＜開始ピクセルのバンク）（３）
図９に示されたように、メモリ制御ユニット３９内の比較器５８はピクセル指数によって示された行をバンク指数と比較し、ピクセル指数がバンク指数より小さければ１の出力を、ピクセル指数がバンク指数より大きいか、等しければ０の出力を生成する。そして、バンクｘの基本アドレスを生成するために、メモリ制御ユニット３９内の加算器６０は１または０いずれかの比較器５８の出力をピクセル指数［ｉｎｔ（ピクセル／８）］に加算する。
【００７１】
図１０は図３に示されたマクロブロック（Ａ、Ｂ、Ｃ、Ｄ）を形成する一連のマイクロブロックを通して検索の進行を追跡するビデオ・ブロック・カウンタ６２を例示するブロック図である。一旦、それぞれのバンクの基本アドレスが決定されると、メモリ制御ユニット３９はブロック境界に基づいてアドレス生成カウンタの更新及び再装荷の増加を追跡する。図１０の例では、ブロック・カウンタ回路６２は３２の計数を行うため最初に３１の値が取込まれる５ビット・カウンタ６４を含む。初期化（task_start ）に関して、カウンタ６４はクロック・サイクル当たり１計数を数える。しかしながら、カウントダウンしたカウンタもまた使用できる。
【００７２】
計数が０ｂ１１０００に到達すると、判定論理は差分プロセッサ３４によって行なわれた検索がマイクロブロックＡについてＡＤ計算を終了したことを示す。同様に、計数０ｂ１００００、１ｂ０１０００及び０ｂ０００００はマイクロブロックＢ、Ｃ、及びＤが行われたことを示す。計数０ｂ０００００に到達すると、検索は所定のマクロブロックについて終了（task_done）する。このように、ブロック・カウンタ回路６２は差分プロセッサ３４によって取扱われつつある現在のマクロブロックに関する差分値の計算の進行を追跡する。さらに、ブロック・カウンタ回路６２はいつ各マイクロブロックに関連する差分値が計算されたかを判定することができる。
【００７３】
各マイクロブロックの境界を横切ると、判定論理６６は個々のマイクロブロックの結果をラッチするように差分プロセッサ３４に命令するブロック終了（block_done）信号を生成する。従って、ビデオ符号器１８はマクロブロックに関する差分値結果と同様に個々の各マイクロブロックに関する差分値結果を生成する。さらに、これらの異なる結果は同じそれぞれの計算を用いて生成される。即ち、四つの個別の計算はマイクロブロックに関する各差分値を生成し、全ての計算の和はマクロブロックに関する差分値を生成する。
【００７４】
上で述べられたように、或るシナリオにおける計算を回避するために、終了技術が様々なタスクまたは反復を終結させるために加えられる。一つの実施においては、タスクを終結させるかどうかの判定は各組の並行ＡＤ計算を行った後で行うことができる。即ち、マイクロブロック行の各ラッチはタスク閾値を超えたかどうかを判定する適切な時間を提供する。そうであれば、検索は最低の差分値をもたらさないであろうことが知られているので、特定のタスクに関する余分な計算は終了することができる。特に、タスク閾値を超えれば、候補マクロブロックの一部の差分値は既に検索空間の初期の候補マクロブロックについて計算された差分値を超えているかもしれない。
【００７５】
図１１は候補メモリ３８中のメモリ・バンクの物理アドレス写像回路６８を例示するブロック図である。候補メモリ３８中の物理アドレスの生成は図９に示されたアドレス変換に対するピクセル指数によって生成された基本アドレスを累算器（accumulator）に装荷することを含む。各クロック・サイクルによって、アドレスは６列（４８ピクセル÷８バンク）に変換するマクロブロック中のピクセルの次の線まで４８ピクセルずつ増加する。ブロックＢの完成の際、累算器はブロックＣ及びブロックＤの計算について基本アドレス＋１を再装荷する。
【００７６】
図１１に示されたように、写像回路６８はブロックＢについて計算が行われる（block_b_done）とき基本アドレス（mb_base_addr）に１を加算する加算器を含み、それによって候補メモリ３８内で縦列基本アドレス（col_base_addr）を生成する。ブロックＢが行われるか、または検索タスクが開始（task_start）されれば、ＯＲゲート７２は高論理出力をマルチプレクサ７４に渡す。
【００７７】
ＯＲゲート７２からの高論理出力に対して、マルチプレクサ７４は縦列基本アドレスを累算器７６に出力する。ＯＲゲート７２からの低論理出力に対して、マルチプレクサ７４は加算器７８の出力を累算器７６に渡す。加算器７８は累算器７６からの現在の候補メモリ・アドレス（logical_cram_addr）に６の値を加える。ブロックＢの開始または終了のどちらもなければ、マルチプレクサ７４及び累算器７６は候補メモリ・アドレスを６行、即ち、８分の４８ピクセルだけ進める。このように、メモリ制御ユニット３９は、ブロックＢの終了または新しい検索タスクの開始のいずれかに従って、差分プロセッサ３４に一度で１マイクロブロック行を提示のための候補メモリ３８中の８バンクの各行を巡回する。従って、計算はマイクロブロックに関する各差分値が生成されるまで一行づつ行われ、そしてマクロブロックに関する各差分値が生成されるまでマイクロブロックごとに行われる。そして、その処理は検索空間の次のマクロブロックについて別の行ごと、マイクロブロックごと、等々に続く。
【００７８】
図１２は候補メモリにおけるマクロブロック縦列更新のための物理アドレス写像回路８０を例示するブロック図である。マクロブロック縦列更新が発生したとき、図１１に示されたアドレス写像回路６８はマクロブロック縦列偏移を扱わない。むしろ、写像回路６８は完全に再装荷された検索空間におけるマクロブロック縦列に適用可能である。縦列更新機能が適用されるとき、図１２のアドレス写像回路８０は別レベルのアドレス写像を行う。
【００７９】
物理候補メモリ３８において、マクロブロック縦列における各行は２行のデータに写像される。例えば、リセットの際、アドレス０及びアドレス１（addr 0/1）は左マクロブロック縦列の第一の行を表す。特に、アドレス０は左マクロブロック縦列に関するピクセル指数行において第一の８ピクセルに対応する候補メモリ３８における８バンク行を表す。アドレス１は左マクロブロック縦列に関するピクセル指数行において第二の８ピクセルに対応する候補メモリ３８における８バンク行を表す。
【００８０】
そして、アドレス２及びアドレス３（addr 2/3）は中間の第一の行を表し、アドレス４及びアドレス５（addr 4/5）は右マクロブロック縦列の第一の行を表す。このように、図７Ｃに示されたように、候補メモリ３８の８バンク行は左、中間及び右のマクロブロックにわたる全体の行（例えば、第一行についてＹ０‐Ｙ４７）ごとにピクセル・データを順次に記憶する。
【００８１】
一マクロブロック縦列更新の後、（前の左マクロブロック縦列を表した）addr 0/1 は右マクロブロック縦列を表すために使用され、addr 2/3（前の中間マクロブロック縦列）は左マクロブロック縦列を表すために使用され、そしてaddr 4/5（前の右マクロブロック縦列）は中間のマクロブロック縦列を表す。
【００８２】
このように、左及び右マクロブロック縦列は前の中央及び右マクロブロック縦列と同じデータをそれぞれ記憶し、新しいデータによって再装荷する必要はない。しかしながら、アドレス（addr 2/3 及び addr 4/5）は左及び中間マクロブロック縦列に今や写像される。しかしながら、前の左マクロブロック縦列アドレス（addr 0/1）は右マクロブロック縦列に再写像され、ビデオ・メモリ３２からの新しいデータによって再装荷される。
【００８３】
縦列更新モードについてアドレス写像を実行するために、図１２の写像回路は二つの条件：候補メモリ縦列基本アドレスに関するｍｏｄ３出力（col_base_addr mod 3）及びマクロブロック縦列状態（即ち、完全更新或いは縦列更新のいずれが要求されているかどうか）を判定する。
【００８４】
図１２に示されたように、写像回路８０は２で除算された現在の基本縦列アドレス（cram_addr[8：1]）のｍｏｄ３出力を生成し、且つｍｏｄ３出力を一時記憶デバイス８４（時折、フリップ・フロップと云われる）に与えるｍｏｄ３演算器８２を含む。ｍｏｄ３出力は縦列基本アドレスについて常に０、１、または２であろう。例えば、第一縦列の縦列基本アドレス（Ｙ０）は０をもたらし、第二の縦列の縦列基本アドレス（Ｙ１６）は１をもたらし、そして第三縦列の縦列基本アドレス（Ｙ３２）は２をもたらすであろう。
【００８５】
新しい検索タスクが開始（task_start）されるか、もしくはブロックＢに関する計算が行われる（block_b_done）とき、ＯＲゲート８６はマルチプレクサ８８に与えるｍｏｄ３演算器８２からのｍｏｄ３出力を出力するようフリップ・フロップ８４を可動にする。ｍｏｄ３出力は縦列基本アドレスが現在駐在している縦列、即ち、第一縦列（０）、第二縦列（１）または第三縦列（２）を指示する。
【００８６】
それに対して、マルチプレクサ８８はマルチプレクサ９０、９２、９４の出力の一つを加算器９６に渡す。マルチプレクサ９０、９２、９４の出力は２ビットカウンタ９８の出力によって決定される。カウンタ９８は候補メモリ３８における全体の検索空間が再装荷されるであろうことを示すfull_update 信号の受信に応答して０の値によってリセットされる。可動入力における col_update 信号に応答して、カウンタ９８は１増分を計数する（または、他の実施については下方に計数する）。
【００８７】
col_update 信号は候補メモリ３８中の検索空間が一つの新しい縦列を装荷することによって増加的に更新されるであろうことを示す。カウンタ９８は各縦列更新について増加、または２縦列更新について増加し、第三縦列更新の後に０の値に戻る。例えば、カウンタ９８は０から１へ、２へと増加し、０へ、１へ、２へ、０へ、１へ、２へ戻る等々となる。カウンタ９８はまた計数が０ｘ１１に等しくなるとリセットされ、このリセットは可動状態に関係なく起こる。
【００８８】
いずれにせよ、カウンタ９８の出力はいかに多くの縦列偏移が増加縦列更新ルーチンの過程で実行されたか追跡する。カウンタ９８の計数出力はアドレス写像決定を促進するため論理入力をマルチプレクサ９０、９２、９４へ提供する。マルチプレクサ９０、９２、９４はそれぞれ検索空間の左、中央及び右縦列に対応する。計数出力が０であれば、マルチプレクサ９０、９２、９４は値０、０、及び０を出力する。計数出力が１であれば、マルチプレクサ９０、９２、９４は＋２、＋２及び−４を出力する。計数出力が２であれば、マルチプレクサ９０、９２、９４はそれぞれ０、−４、及び＋２を出力する。さらに、計数出力はＯＲゲートに信号を提供する０ｂ１１比較器９５に提供される。このように、カウンタ９８のリセットは full_update 信号あるいは比較器９５からの信号のいずれかに応答して起こり、その双方ともＯＲゲート９７への入力である。
【００８９】
マルチプレクサ９０、９２、９４のこの動作は前の中間縦列の左縦列への偏移及び前の右縦列の中間縦列への偏移、即ち、各場合における左への二行（＋２）の偏移を反映する。マクロブロック縦列における各行が候補メモリ３８における二行によって示されることを思出してみよ ( 図７Ｃ参照)。この動作はまた前の左縦列の右縦列への偏移、即ち、左への四行（−４）の偏移を反映する。三つの縦列の後、アドレスは物理メモリにもう一度適合し、従ってマルチプレクサ９０、９２及び９４の出力値はそれぞれ０、０、及び０に戻る。
【００９０】
マルチプレクサ９０、９２及び９４の出力は系列における次の偏移を反映する。第二の偏移の後では、元の中間縦列は左縦列に既に偏移してしまって、現在は右縦列に偏移し、元の右縦列は左縦列に現在は偏移し、そして元の左縦列は中間縦列に現在は偏移している。この場合、現在の左縦列は右縦列においてその元の位置から＋４行離れており、現在の中間縦列は左縦列においてその元の位置から−２行離れており、そして現在の右の縦列は中間縦列においてその元の位置から−２行離れている。
【００９１】
フリップ‐フロップ８４の出力がゼロであれば、第一の縦列マルチプレクサ９０はマルチプレクサ８８を通過する。フリップ‐フロップ８４の出力が１または２であれば、第二または第三の縦列マルチプレクサ９２、９４はそれぞれマルチプレクサ８８を通過する。各場合おいて、マルチプレクサ８８の出力は加算器９６に与えられ、それはその出力を論理候補メモリ・アドレス（logical_cram_addr）に加算する。
【００９２】
このように、加算器９６は適切なマクロブロックに関する物理候補メモリ・アドレスを得るめに縦列更新偏移状態に相応な量だけ論理候補メモリ・アドレスを偏移させる。論理アドレスは偏移動作の結果として右縦列に対応するが、物理アドレスが中間縦列に実際に対応すれば、写像回路８０は必要なアドレス変換を行う。そして、メモリ制御ユニット３９は、例えば、８出力バンクに亘る並行ＡＤ計算のために、差分プロセッサ３４に候補メモリ３８において適切にアドレス指定されたデータを符号化メモリ３６における対応するデータと比較させることになる。
【００９３】
図１３はさらに詳細に差分プロセッサ３４を例示するブロック図である。特に、図１３は８つの同時バンク出力を生成するため符号化メモリ３６及び候補メモリ３８の配置によって提供される並行計算機能を図示する。図１３に示されたように、差分プロセッサは多数の絶対差分（ＡＤ）計算チャネル１００Ａ〜１００Ｈ（全体では１００）を含む。各ＡＤ計算チャネル１００は符号化されるマクロブロックについて符号化メモリ３６からそれぞれのバンク出力（ａ０〜ａ７）を受信する。
【００９４】
比較、及び絶対差分の計算について、各ＡＤ計算チャネルはまた候補メモリ３８から対応するバンク出力（ｂ０〜ｂ７）を受信する。ＡＤ結果は縦続された一組の８ビット加算器１０２Ａ〜１０２Ｄ、対の９ビット加算器１０４Ａ、１０４Ｂ及び１０ビット加算器１０６によって合計される。より大きなビット値がピクセルを表すために使用されれば、より大きな加算器が実装される。いずれにせよ、加算器１０６の出力は加算器１０８に与えられる。加算器１０８は絶対差分（ＳＡＤ）結果の合計を生成するためにフリップ‐フロップ１１０経由でそれ自身の出力を加算器１０６の出力と合計する。８つの入力（ａ０〜ａ７）の各組はマイクロブロックの８ピクセル行に対応する。例えば、入力はマイクロブロックＡの各行（図６ａ）、それからマイクロブロックＢの各行、それからマイクロブロックＣ、それからマイクロブロックＤについて差分プロセッサに提供される。累積は各マイクロブロックに関する差分測定基準を計算した後でラッチすることができ、そしてマクロブロックに関する差分測定基準に対応する全体の累積について再びラッチすることができる。
【００９５】
さらに、それぞれの各ラッチ後、タスクを終結させるかどうかの判定を行うことができる。即ち、マイクロブロック行の各ラッチはタスク閾値が超えられたかどうかを判定する適切な時間を提供する。そうであれば、検索が最低の差分値をもたらさないであろうことが知られているので、その特定タスクについて余分な計算は終結することができる。
【００９６】
図１４はここに示されたビデオ符号化技術を例示するフローチャートである。図１４に示されたように、検索の開始、即ち、タスクの開始（１１２）の際、ＤＳＰ２８は符号化されるマクロブロックのピクセル指数を生成する（１１４）。メモリ制御ユニット３９はマクロブロック・ピクセル指数をビデオ・メモリ・アドレスに変換し（１１６）、マクロブロックはバス３３及びメモリ制御ユニットを経由してビデオ・メモリ３２から符号化メモリへ装荷される（１１８）。ＤＳＰ２８はまた検索空間についてピクセル指数を生成する（１２０）。検索空間ピクセル指数をビデオ・メモリ・アドレス及び候補メモリ・アドレスに変換すると（１２２）、メモリ制御ユニット３９は候補メモリ３８に検索空間マクロブロックを装荷する（１２４）。
【００９７】
差分プロセッサ３４は候補メモリ３８の多数のバンク出力間でＡＤ計算を行い（１２６）、符号化されるマクロブロックを検索空間内のマクロブロックと比較する。並行ＡＤ計算に基づいて、差分プロセッサ３４は全体の検索空間に亘って最良のＳＡＤ結果を生成する（１２８）（または、完全な検索空間を考慮しないで受入れ結果を生成する）。いずれにせよ、その結果は符号化されるマクロブロックに関するピクセル指数と関連する。以上のように、差分プロセッサ３４は余分なＳＡＤ計算を要しないでマクロブロックを形成する各ブロックについてＳＡＤ結果を生成する。マクロブロックについてＳＡＤ結果を生成した後、ＤＳＰ２８は受入れ可能な適合が確認されたかどうかを判定することができ、そうであれば、ＭＰＥＧ‐４圧縮規格に従って符号化されるマクロブロックを確認するため動きベクトルを記憶することができる。
【００９８】
図１５は増加的に検索空間を装荷するため縦列更新を使用するビデオ符号化技術を例示するフローチャートである。別の検索タスクを働かすためＤＳＰ２８による次のピクセル指数の生成（１３０、１３２）の際、メモリ制御ユニット３９はマクロブロック・ピクセル指数をビデオ・メモリ・アドレス及びメモリ・アドレスに変換する（１３４）。そして、関連のマクロブロックはビデオ・メモリ３２から符号化メモリ３６に装荷される（１３６）。この場合には、しかしながら、検索空間は全体の検索空間を再装荷するのではなく新しい縦列を加えることによって増加的に更新される。
【００９９】
従って、ＤＳＰ２８は検索空間縦列更新についてピクセル指数を生成し（１３８）、それは関連のビデオ・メモリ・アドレス及び候補メモリ・アドレスを生成するためにメモリ制御ユニット３９によって変換される（１４０）。ビデオ・メモリ３２から候補メモリ３８へ新しいマクロブロック縦列を装荷すると（１４２）、差分プロセッサ３４は候補メモリ３８及び符号化メモリ３６の８つの出力バンクに亘って並行ＡＤ計算を行い（１４４）、そしていくつかの並行ＡＤ計算の後、最良のＳＡＤ結果（または、受入れ可能なＳＡＤ結果）を生成する（１４６）。
【０１００】
図１６は候補メモリ中のメモリ・バンクに関する基本アドレス写像を例示するフローチャートである。図１６に示された処理は図９の回路の動作に対応するが、他の回路の変形も使用することができる。ピクセル指数から基本アドレスを得るために、メモリ制御ユニット３９はピクセル指数に対するｍｏｄ８演算の結果を計算する（１５０）。その結果が現在のバンク指数より大きいか等しければ（１５２）、基本アドレスは８で除算したピクセル指数の整数商に（１５４）。結果が現在のバンク指数より小さければ（１５２）、基本アドレスは８で除算したピクセル指数の整数商に１を足したものに等しい（１５６）。
【０１０１】
図１７は候補メモリ中のメモリ・バンクについて物理アドレス写像を例示するフローチャートである。図１７に示された処理は図１１における回路６８の動作に対応し、他の回路の変形も使用することができる。マクロブロック中のブロックＢに関するＡＤ計算が完了していれば（１６０）、候補メモリ３８における縦列基本アドレスはマクロブロック基本アドレスに１を足したものに等しい（１６２）。ブロックＢが終わっていなければ（１６０）、候補メモリ３８における縦列基本アドレスはマクロブロック基本アドレスに等しい（１６４）。そして、ブロックＢが終わるか、または新しい検索タスクが開始されれば（１６６）、候補メモリ３８における論理メモリ・アドレスは縦列基本アドレスに等しい（１６８）。ブロックＢが終わらず、あるいは新しい検索タスクが開始されなければ（１６６）、論理候補メモリ・アドレスは６行だけ偏移する（１７０）。
【０１０２】
図１８は候補メモリにおけるマクロブロック縦列更新について物理アドレス写像を例示するフローチャートである。図１８に示された処理は図１２における回路８０の動作に対応し、他の回路の変形も使用することができる。図１８に示されたように、縦列基本アドレスによって指示された縦列を決定するために、メモリ制御ユニット３９は縦列基本アドレスにｍｏｄ３演算を適用する（１７４）。縦列更新機能が可動でなければ（１７６）、論理候補メモリ・アドレスは偏移しない（１７８）。これはカウンタ９８からの０のカウンタ出力に対応して、図１２のマルチプレクサ９０、９２、９４の（０、０、０）の出力に対応し、従ってマルチプレクサ８８による０の通過に対応する。
【０１０３】
縦列更新機能がが可動であれば（１７６）、メモリ制御ユニット３９はカウンタ９８の出力の参照によって発生した縦列更新の数を決定する（１８０）。確認された縦列及び縦列更新偏移の数に基づいて、メモリ制御ユニット３９は正しい物理候補メモリ・アドレスを生成するために論理候補メモリ・アドレスが偏移されるべき量を決定する（１８２）。そして、メモリ制御ユニット３９はアドレス偏移を加えることによって論理候補メモリ・アドレスを物理候補メモリ・アドレスに変換する（１８４）。
【０１０４】
図１９は同じ計算を使用してマクロブロックを形成するマクロブロック及びいくつかのマイクロブロックについて差分値の生成を例示するフローチャートである。以上のように、動き推定器２９がマクロブロック検索反復を始めるとき（１９１）、差分プロセッサ３４はマイクロブロック行基準によってマイクロブロック列に関する並行絶対差分（ＡＤ）計算を行う。例えば、値Ｘは初期化することができ（１９２）、差分プロセッサ３４は符号化されつつあるマクロブロック中の第一マイクロブロックのＸ番目の行に関する並行ＡＤ計算を行うことができる（１９３）。マイクロブロックにより多くの行がある限り（１９４のｙｅｓ分岐）、値Ｘは増分され（１９５）、並行ＡＤ計算はマイクロブロックの次の行について行われる。
【０１０５】
ビデオ・ブロック計数回路６２はマイクロブロックにさらに多くの行があるかどうかを判定することができる（１９４）。一例として、ビデオ・ブロック計数回路６２は差分プロセッサ３４の一部として統合することができ、もしくはＤＳＰインタフェース・ユニット３０の一部を形成する。ＡＤ計算が第一のマイクロブロックの全ての行について行われたことが判定されると、差分プロセッサ３４は第一のマイクロブロックに関する差分値を出力する（１９６）。マイクロブロックがなくなるまで、この処理はマクロブロックの全てのマイクロブロックについて続けることができる（１９７）。タスク終結技術はまた処理のこの段階において、例えば、全体の累積差分値が現在の反復について既に計算された最低の差分値に対応する閾値のようなタスク閾値を超えるときタスクを終結させるために、使用される。
【０１０６】
差分プロセッサ３４はマクロブロックについて進行中の差分値を累積することができ、各マイクロブロックについて計算が行われるので、各マイクロブロックに関する差分値を出力する。第一のマイクロブロックに関する差分値はその点までの差分値の累積である。第二のマイクロブロックに関する差分値はその点までの全部の累積から第一のマイクロブロックに関する差分値を減じたものに対応する。第三のマイクロブロックに関する差分値はその点までの全部の累積から第一と第二のマイクロブロックに関する差分値を減じたものに対応する、等々。
【０１０７】
ビデオ・ブロック計数回路６２はまたいつ最後のマイクロブロックに関する計算が累積されたかを決定する（１９７のｙｅｓ分岐）。その点において、差分プロセッサ３４はマクロブロックに関する差分値を出力し（１９８）、それはその点までのＡＤ計算の全部の累積である。ＤＳＰ２８、または恐らくＤＳＰインタフェース・ユニット３０はマイクロブロックにさらに多くの列があるとき符号化される現在のマクロブロックについて行われる別のタスクがあるかどうかを判定することができる（１９４）。再び、タスクは符号化される現在のビデオ・ブロックを検索空間におけるビデオ・ブロックと比較するために使用される一組の計算を参照し、反復は検索空間の様々な異なるビデオ・ブロックと符号化される現在のビデオ・ブロックの比較に対応する一組のタスクを参照する。
【０１０８】
反復は検索空間のビデオ・ブロックの規定された組を符号化されるビデオ・ブロックと比較することと同じくらい簡単であるか、または検索空間内の位置を決める初期化技術、入れ子検索、及び／またはできる限り迅速に最良の適合を設置する規定及び再規定された検索パラメータを含めるためさらに複雑になる。いずれにせよ、動き推定器２９が反復について全てのタスクを実行した後（１９９のｎｏ分岐）、ビデオ符号器１８は現在のマクロブロックを符号化する（２００）。検索空間の様々な候補マクロブロックに関する差分値が生成され、且つ候補を形成するマイクロブロックに関する差分値もまた生成されるとき、ビデオ符号器は符号化プロセスに様々な選択肢を持つと有利である。
【０１０９】
最良の候補マイクロブロックに対応する四つの別個の動きベクトルの使用は改良された圧縮についてマクロブロックを符号化するために使用される。最良の候補マクロブロックに対応する単一の動きベクトルの使用は、しかしながら、マクロブロック動きベクトルだけを認識する復号器との適合性を維持するといった他の理由に対して好ましい。符号化される現在のマクロブロックと動きベクトルによって規定されたビデオ・ブロックとの間の差分を規定する行列（matrix）に対して離散コサイン変換（ＤＣＴ）符号化を行うといった、テクスチャー符号化もまた追加される。
【０１１０】
現在のマクロブロックが符号化された後、ビデオ符号器１８は現在のビデオ・フレームについて符号化される別のマクロブロックがあるか否か、即ち、実行されるべき別の反復があるか否かを判定する（２０１）。なければ、所定のビデオ・フレームについて符号化処理は完了し（２０１のｎｏ分岐）、そのフレームに関する符号化ビデオ・ブロックは通信媒体１５上で送信器２０によって伝送することができる。しかしながら、現在のビデオ・フレームについて符号化される別のマクロブロックがあれば、検索空間は再装荷することができ（２０２）、次の反復を始めることができる（１９１）。さらに、検索空間を再装荷する処理（２０２）は上で述べた縦列更新技術を利用し、その中でメモリ制御ユニットは候補メモリ３８の縦列の一部を再装荷し、この中で述べたようなアドレス指定手法によって候補メモリの追跡を行う。この中で述べたこれら及び他の技術は、様々な従来の符号化処理を改善するスタンドアロン技術が使用されるであろうとき、または組合せで使用されるとき、ＭＰＥＧ‐４のような規格に従ってビデオ符号化の効率を改善し、計算資源が非常に制限され、電力消費が問題となる携帯電話のような無線通信デバイス内のビデオ符号化をさらによく促進する。
【０１１１】
いくつかの異なる実施例が述べられてきた。その技術は、メモリ移転、計算サイクル、及び電力消費を低減させることによりビデオ符号化を改善することが可能で、それによって符号化処理を加速し、そして恐らくは電池動作ビデオ・デバイスの寿命を拡張することができる。さらに、その技術は余計なＡＤ計算を必要とせずにマクロブロック及びマイクロブロックについて差分値を生成することによって符号化処理における選択肢を提供する。これら及び恐らく他の方法において、その技術はＭＰＥＧ‐４のような規格またはその他のビデオ符号化規格に従ってビデオ符号化を改善することができる。
【０１１２】
その技術はハードウェア、ソフトウェア、ファームウェア、それらのある組合せにおいて実施される。ソフトウェアにおいて実施されれば、それらの技術は、ＭＰＥＧ‐４規格に準拠するデバイスにおいて実行されるとき上で述べられた一以上の方法を実行するプログラム・コードを含むコンピュータ可読媒体に適用される。その場合には、コンピュータ可読媒体は同期式ダイナミック・ランダム・アクセス・メモリ（ＳＤＲＡＭ）、読出し専用メモリ（ＲＯＭ）、不非揮発性ランダム・アクセス・メモリ（ＮＶＲＡＭ）、電気的消去可能読出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュ（ＦＬＡＳＨ）メモリ等といったランダム・アクセス・メモリ（ＲＡＭ）を含む。
【０１１３】
プログラム・コードはコンピュータ可読命令の形式のメモリに記憶される。その場合、ＤＳＰのようなプロセッサはここに述べられた技術の一以上を実行するためにメモリに記憶された命令を実行する。いくつかの場合には、その技術は符号化処理を加速するために動き推定器のような様々なハードウェア構成要素に頼るＤＳＰによって行われる。他の場合には、ビデオ符号器はマイクロプロセッサ、一以上の特定用途向け集積回路（ＡＳＩＣ）、一以上のフィールド・プログラマブル・ゲートアレイ（ＦＰＧＡ）、またはいくつかの他のハードウェア‐ソフトウェアの組合せとして実施される。これら及び他の実施例は次の請求項の範囲内にある。
【図面の簡単な説明】
【０１１４】
【図１】発信（source）ディジタル・ビデオ・デバイスがビデオ・データの符号化系列を受信ディジタル・ビデオ・デバイスに伝送するシステム例を例示するブロック図である。
【図２】ディジタル・ビデオ系列を符号化するビデオ符号器を例示するブロック図である。
【図３】ビデオデータのマクロブロック例の概念図である。
【図４】検索空間例の概念図である。
【図５】一連のマクロブロックとして配置された検索空間上に概念的に位置する符号化されるマクロブロックの概念図である。
【図６Ａ】マクロブロック・ピクセル指数を例示する図である。
【図６Ｂ】ビデオ・メモリ内のビデオ・データの配置を例示する図である。
【図６Ｃ】符号化メモリ内のビデオ・データの配置を例示する図である。
【図７Ａ】検索空間ピクセル指数を例示する図である。
【図７Ｂ】ビデオ・メモリ内の検索空間の配置を例示する図である。
【図７Ｃ】候補メモリ内の検索空間の配置を例示する図である。
【図８Ａ】マクロブロック縦列ピクセル指数を例示する図である。
【図８Ｂ】ビデオ・メモリ内のマクロブロック縦列を例示する図である。
【図９】候補メモリ中のメモリ・バンクの基本アドレス変換へのピクセル指数の変換を例示するブロック図である。
【図１０】マクロブロックを形成する一連のブロックを通して検索の進行を追跡するブロック・カウンタを例示するブロック図である。
【図１１】候補メモリ中のメモリ・バンクに関する物理的アドレス写像を例示するブロック図である。
【図１２】候補メモリ中のマクロブロック縦列更新に関する物理的アドレス写像を例示するブロック図である。
【図１３】差分プロセッサを例示するブロック図である。
【図１４】ビデオ符号化技術を例示するフローチャートである。
【図１５】検索空間を増加的に装荷するため縦列更新を使用するビデオ符号化技術を例示するフローチャートである。
【図１６】候補メモリ中のメモリ・バンクに関する基本アドレス写像を例示するフローチャートである。
【図１７】候補メモリ中のメモリ・バンクに関する物理アドレス写像を例示するフローチャートである。
【図１８】候補メモリ中のマクロブロック縦列に関する物理アドレス写像を例示するフローチャートである。
【図１９】同じ計算を使ってマクロブロック、及びマクロブロックを形成するいくつかのマイクロブロックに関する差分値の生成を例示するフローチャートである。
【図１】
2005530420.tif 000003
【図２】
2005530420.tif 000004
【図３】
2005530420.tif 000005
【図４】
2005530420.tif 000006
【図５】
2005530420.tif 000007
【図６Ａ】
2005530420.tif 000008
【図６Ｂ】
2005530420.tif 000009
【図６Ｃ】
2005530420.tif 000010
【図７Ａ】
2005530420.tif 000011
【図７Ｂ】
2005530420.tif 000012
【図７Ｃ】
2005530420.tif 000013
【図８Ａ】
2005530420.tif 000014
【図８Ｂ】
2005530420.tif 000015
【図９】
2005530420.tif 000016
【図１０】
2005530420.tif 000017
【図１１】
2005530420.tif 000018
【図１２】
2005530420.tif 000019
【図１３】
2005530420.tif 000020
【図１４】
2005530420.tif 000021
【図１５】
2005530420.tif 000022
【図１６】
2005530420.tif 000023
【図１７】
2005530420.tif 000024
【図１８】
2005530420.tif 000025
【図１９】
2005530420.tif 000026
【国際調査報告】
2005530420.tif 000027
2005530420.tif 000028
2005530420.tif 000029
2005530420.tif 000030