(57)【要約】  実施態様は、候補マクロブロック・パーティションの各々のビットレート信号を決定することを含んでいている、ビデオ符号器における動きの推定および補償において、複数の候補マクロブロック・パーティションから１つの予測マクロブロック・パーティションを選択し、候補マクロブロック・パーティションの各々についてひずみ信号を生成し、複数のコストを生成するために、それぞれのビットレートおよびひずみ信号に基づいて候補マクロブロック・パーティションの各々ついてコストを計算し、そして、前記コストから動きベクトルを決定する、方法に関する。前記動きベクトルは、前記予測マクロブロック・パーティションを指定する。
2009526499.tif 000002
【特許請求の範囲】
【請求項１】
ビデオエンコーダにおける動きの推定と補償において予測マクロブロック・パーティションを選択する方法であって、
ビットレート信号を決定すること、
ひずみ信号を生成すること、
前記ビットレート信号および前記ひずみ信号に基づいてコストを計算すること、
および、
前記コストから動きベクトルを決定すること、そこでは前記動きベクトルは前記予測マクロブロック・パーティションを指定する、
を含む、方法。
【請求項２】
前記ビットレート信号を決定することが、
サーチエリアのセクションから現在フレームのマクロブロックを引くことにより、残余誤差信号を生成すること、
前記残余誤差信号を整数個のブロックに分割すること、
前記整数個のブロックの変換を作成するために、前記整数個のブロックを、空間領域から周波数領域に変換すること、
前記整数個のブロックの前記変換のシフトと加算の組合せによって、量子化近似ブロックを生成すること、
前記量子化近似ブロックは、いくらかのゼロでない係数およびいくらかのゼロ値の係数を有すること、
そこでは、前記シフトと加算の組合せは、量子化パラメータに基づいており、
前記量子化近似ブロックの絶対値レベルの和を計算すること、および、
前記ゼロでない係数の数の３倍に前記ゼロ値の係数の数を足し、さらに前記絶対値レベルの和を足して、合計することによって、前記量子化ブロックのビットレート信号を計算すること、
を含む、請求項１に記載の方法。
【請求項３】
前記整数個のブロックの前記ブロックは、４ピクセル×４ピクセルの次元を持っている、請求項２に記載の方法。
【請求項４】
前記ひずみ信号を生成することは、
サーチエリアのセクションから現在フレームのマクロブロックを引くことにより、残余誤差信号を計算すること、
前記残余誤差信号を整数個のブロックに分割すること、
前記整数個のブロックを空間領域から周波数領域に変換し、前記整数個のブロックの変換を作成すること、
前記整数個のブロックの前記変換のシフトと加算の第１の組合せによって、量子化近似ブロックを生成すること、そこでは、シフトと加算の前記第１の組合せは、第１の量子化パラメータに基づくものであり、
前記整数個のブロックの前記変換のシフトと加算の第２の組合せによって、逆量子化近似ブロックを生成すること、そこでは、シフトと加算の前記第２の組合せは、第２の量子化パラメータに基づくものであり、
前記量子化近似ブロックと前記逆量子化近似ブロックの間の２乗誤差を決定すること、そこでは、前記ひずみ信号は、前記２乗誤差に等しい、
を含む、請求項１に記載の方法。
【請求項５】
前記整数個のブロックの前記ブロックは、４ピクセル×４ピクセルの次元を持っている、請求項４に記載の方法。
【請求項６】
メモリ内のルックアップテーブルに前記２乗誤差の可能な値を格納すること、
をさらに含む、請求項４に記載の方法。
【請求項７】
前記コストを計算することは、
ラグランジュの乗数で乗算された前記ビットレート信号と前記ひずみ信号の合計により、ラグランジュのコストを計算すること、および、
前記整数個のブロックの各々に対して前記ラグランジュのコストの合計を行なうこと、そこでは、前記コストは前記合計と等しい、
を含む請求項１に記載の方法。
【請求項８】
前記整数個のブロックの前記ブロックは、４ピクセル×４ピクセルの次元を持っている、請求項７に記載の方法。
【請求項９】
前記動きベクトルを決定することは、
最低の値を求めて前記コストを走査すること、そこでは前記動きベクトルは前記最低の値に対応するベクトルとして定義される、を含む、請求項１に記載の方法。
【請求項１０】
前記ビデオエンコーダは、Ｈ．２６４／ＡＶＣ符号器である、請求項１に記載の方法。
【請求項１１】
ビデオエンコーダにおける動きの推定と補償において、複数個の候補マクロブロック・パーティションから予測マクロブロック・パーティションを選択する方法であって、
前記候補マクロブロック・パーティションの各々について  ビットレート信号を決定すること、
前記候補マクロブロック・パーティションの各々について、ひずみ信号を生成すること、
複数個のコストを生成するために、それぞれのビットレート信号、および、それぞれのひずみ信号の  に基づいて  前記候補マクロブロック・パーティションの各々についてコストを計算すること、および、
前記コストからの動きベクトルを決定すること、そこでは前記動きベクトルは前記予測マクロブロック・パーティションを指定する、
を含む方法。
【請求項１２】
前記ビットレート信号を決定することは、
候補マクロブロック・パーティションごとに、それぞれの候補マクロブロック・パーティションから現在フレームのマクロブロックを引くことにより、残余誤差信号を生成すること、
候補マクロブロック・パーティションごとに、それぞれの残余誤差信号を整数個のブロックに分割すること、
候補マクロブロック・パーティションごとに、整数個のブロックそれぞれを、空間領域から周波数領域に変換して、複数個の変換を作成すること、
１つの変換ごとに、それぞれの変換のシフトと加算の組合せによって、量子化近似ブロックを生成すること、
前記量子化近似ブロックは、いくらかのゼロでない係数およびいくらかのゼロ値の係数を有し、
そこでは、前記シフトと加算の組合せは、量子化パラメータに基づいており、そして、
変換ごとに、前記量子化近似ブロックの絶対値レベルの合計を計算すること、
および、
変換ごとに、ゼロでない係数のそれぞれの数の３倍に、ゼロ値係数のそれぞれの数を足し、さらに、絶対値レベルのそれぞれの和を足して、合計することによって、前記ビットレート信号を計算すること、
を含む、請求項１１に記載の方法。
【請求項１３】
前記整数個のブロックの前記ブロックは、４ピクセル×４ピクセルの次元を持っている、請求項１２に記載の方法。
【請求項１４】
前記ひずみ信号を生成することは、  
候補マクロブロック・パーティションごとに、それぞれの候補マクロブロック・パーティションから現在フレームのマクロブロックを引くことにより、残余誤差信号を生成すること、
候補マクロブロック・パーティションごとに、それぞれの残余誤差信号を整数個のブロックに分割すること、
候補マクロブロック・パーティションごとに、整数個のブロックのそれぞれを空間領域から周波数領域に変換して、複数個の変換を作成すること、
１つの変換ごとに、それぞれの変換のシフトと加算の第１の組合せによって量子化近似ブロックを生成すること、そこでは、シフトと加算の前記第１の組合せは第１の量子化パラメータに基づいている、そして、
１つの変換ごとに、それぞれの変換のシフトと加算の第２の組合せによって逆量子化近似ブロックを生成して、そこでは、シフトと加算の前記第２の組合せは、第２の量子化パラメータに基づいている、および、
変換ごとに、それぞれの量子化近似ブロックとそれぞれの逆量子化近似ブロックの間の２乗誤差を決定すること、そこでは、前記ひずみ信号は前記２乗誤差に等しい、
を含む請求項１１に記載の方法。
【請求項１５】
前記整数個のブロックの前記ブロックは、４ピクセル×４ピクセルの次元を持っている、請求項１４に記載の方法。
【請求項１６】
メモリ内のルックアップテーブルに前記２乗誤差の可能な値を格納すること、をさらに含む請求項１４に記載の方法。
【請求項１７】
前記候補マクロブロック・パーティションの各々は、整数個のブロックを有し、そこでは、前記ブロックの各々は、それぞれのビットレート信号およびそれぞれのひずみ信号を持ち、また、前記コストを計算することは、
ブロックごとに、ラグランジュの乗数で乗算されたそれぞれのビットレート信号とそれぞれのひずみ信号との合計により、ラグランジュのコストを計算すること、および、
候補マクロブロック・パーティションごとに、それぞれのブロックのそれぞれのラグランジュのコストを合計することにより前記コストを生成すること、
を含む、請求項１１に記載の方法。
【請求項１８】
前記ブロックは、４ピクセル×４ピクセルの次元を持っている、請求項１７に記載の方法。
【請求項１９】
前記動きベクトルを決定することは、
最低の値を求めて前記コストを走査すること、そこでは、前記動きベクトルは、前記最低の値の候補マクロブロック・パーティションのそれぞれに対応するベクトルにしたがって定義される、を含む請求項１１に記載の方法。
【請求項２０】
前記ビデオエンコーダは、Ｈ．２６４／ＡＶＣ符号器である、請求項１１に記載の方法。
【請求項２１】
現在フレームのマクロブロックおよびＭ×Ｎサーチエリアを受信し、かつ残余誤差信号を生成するための動き補償ブロックと、
前記動き補償ブロックに結合され、前記残余誤差信号を受信し、そして、前記残余誤差信号を周波数領域の残余誤差信号に変換するための順方向変換ブロックと、
前記順方向変換ブロック結合され、前記周波数領域の残余誤差信号を受信し、かつ、第１の量子化パラメータに基づいて近似された量子化信号を生成し、そして、第２の量子化パラメータに基づいて近似された逆量子化信号を生成するための量子化近似ブロックと、
前記量子化近似ブロックに結合され、前記近似された量子化信号を受信し、かつ前記予測マクロブロック・パーティションを選択するのに使用されるレート信号を生成するためのエントロピー符号化近似ブロックと、
前記量子化近似ブロックに結合され、前記近似された量子化信号および前記近似された逆量子化信号を受信し、前記予測マクロブロック・パーティションを選択するのに使用されるひずみ信号を生成するための、２乗差分ブロックの総体と、
を備える、ビデオエンコーダにおける動きの推定と補償において予測マクロブロック・パーティションを選択するための装置。
【請求項２２】
前記エントロピー符号化近似ブロックおよび前記２乗差分ブロックの総体に結合され、前記レート信号と前記ひずみ信号を受信し、そして動きベクトルを生成するコスト決定ブロック、
をさらに備える、請求項２１に記載の装置。
【請求項２３】
前記Ｍ×Ｎサーチエリアは、複数個の候補マクロブロック・パーティションを含み、また、前記動き補償ブロックは、それぞれの候補マクロブロック・パーティションから前記マクロブロックを引くことにより１つの候補マクロブロック・パーティションごとに前記残余誤差信号を生成する、請求項２１に記載の装置。
【請求項２４】
前記Ｍ×Ｎサーチエリアは複数個の候補マクロブロック・パーティションを含み、そこでは、前記周波数領域の残余誤差信号は、複数個の周波数領域残余誤差サブ信号を含み、
前記周波数領域の残余誤差サブ信号の各々は、前記候補マクロブロック・パーティションのうちの１つに対応し、
前記量子化近似ブロックは、前記第１の量子化パラメータに基づいて、それぞれの周波数領域の残余誤差サブ信号のシフトと加算の組合せによって、各周波数領域残余誤差サブ信号について近似された量子化サブ信号を生成し、
複数個の近似された量子化サブ信号を生成すること、
前記に近似された量子化信号は、近似された量子化サブ信号の前記複数を含む、
請求項２１に記載の装置。
【請求項２５】
前記Ｍ×Ｎサーチエリアは複数個の候補マクロブロック・パーティションを含み、
前記周波数領域の残余誤差信号は複数個の周波数領域の残余誤差サブ信号を含み、
前記周波数領域の残余誤差サブ信号のそれぞれは前記候補マクロブロック・パーティションのうちの１つに対応し、
前記量子化近似ブロックは、前記第２の量子化パラメータに基づいた、それぞれの周波数領域の残余誤差サブ信号のシフトと加算の組合せによって、各周波数領域の残余誤差サブ信号について近似された逆量子化サブ信号を生成し、
そして、複数個の近似された逆量子化サブ信号の生成し、
前記近似された逆量子化信号は前記複数個の近似された逆量子化サブ信号を含む、
請求項２１に記載の装置。
【請求項２６】
前記Ｍ×Ｎサーチエリアは複数個の候補マクロブロック・パーティションを含み、
前記近似された量子化信号は複数個の近似された量子化サブ信号を含み、
前記近似された量子化サブ信号の各々は、前記候補マクロブロック・パーティションのうちの１つに対応し、いくらかのゼロでない係数といくらかのゼロ値の係数を有し、
前記エントロピー符号化近似ブロックは、近似された量子化サブ信号のそれぞれの絶対値レベルの和を計算し、そして  絶対値レベルのそれぞれの和に、ゼロでない係数のそれぞれの数の３倍を足し、さらにゼロ値の係数のそれぞれの数を足して、合計することによって、近似された量子化サブ信号の各々についてレート・サブ信号を生成し、
そして、複数の近似された量子化サブ信号を生成し、
前記近似された量子化信号が、前記複数の近似された量子化サブ信号を含む、
請求項２１に記載の装置。
【請求項２７】
前記Ｍ×Ｎサーチエリアは複数の候補マクロブロック・パーティションを含み、
前記近似された量子化信号は複数の近似された量子化サブ信号を含み、
前記近似された量子化サブ信号の各々は、前記候補マクロブロック・パーティションのうちの１つに対応し、
前記近似された逆量子化信号は複数の近似された逆量子化サブ信号を含み、
前記近似された逆量子化サブ信号の各々は、前記候補マクロブロック・パーティションのうちの１つに対応し、
前記２乗差分ブロックの総体は、複数の近似されたひずみサブ信号を生成するために、前記近似された量子化サブ信号と前記近似された逆量子化サブ信号との間の２乗誤差を決定することによって、候補マクロブロック・パーティション各々についてひずみサブ信号を生成し、
前記ひずみ信号は、前記複数のひずみサブ信号を含む、
請求項２１に記載の装置。
【請求項２８】
ルックアップテーブルに前記２乗誤差の可能な値を格納するために、前記２乗差分ブロックの総体に結合されたメモリ、をさらに含む、請求項２７に記載の装置。
【請求項２９】
前記Ｍ×Ｎサーチエリアは複数の候補マクロブロック・パーティションを含み、
前記レート信号は複数のレート・サブ信号を含み、
前記レート・サブ信号の各々は前記候補マクロブロック・パーティションのうちの１つに対応し、
前記ひずみ信号は複数のひずみサブ信号を含み、
前記ひずみサブ信号の各々は前記候補マクロブロック・パーティションのうちの１つに対応し、
前記コスト決定ブロックは、ラグランジュの乗数で乗算されたレート信号と、ひずみ信号のそれぞれを合計することによって、候補マクロブロック・パーティションの各々のラグランジュのコストを計算して、前記動きベクトルを生成し、
さらに、複数のラグランジュのコストを生成し、
そして、
最低の値を求めて前記ラグランジュのコストを走査し、
前記動きベクトルは、前記の最低の値の候補マクロブロック・パーティションのそれぞれに対応するベクトルとして定義される、
請求項２２に記載の装置。
【請求項３０】
前記ビデオエンコーダが、Ｈ．２６４／ＡＶＣ符号器である、請求項２１に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、ビデオ符号器、および、そこに使用されるコスト関数に関する。
【背景技術】
【０００２】
画像圧縮は、ディジタル映像データの圧縮を含んでいる。画像圧縮は、ビデオファイル・フォーマットおよびストリームビデオ・フォーマットにおいてビデオデータの効率的な符号化に使用される。圧縮は、データをより効率的に保存するか送信することができるように通常行なわれている、より少数のビットのフォーマットへのデータのリバー変換である。そのプロセスの逆、デコンプレッションがオリジナル・データの正確なレプリカを生成する場合には、その圧縮は可逆である。イメージデータに通常適用されるロッシ圧縮（lossy compression）は、オリジナル画像の正確なレプリカの再生を可能にしない。しかし、それはより効率的である。可逆の画像圧縮は可能であるが、実際上、それは事実上使用されない。標準のビデオデータ・レート・リダクションは、データを切り捨てることを含んでいる。
【０００３】
ビデオは、基本的に色ピクセルの３次元配列である。２次元は、動画の空間の（水平および垂直）方向を提供する。また、１次元は時間領域を表わす。
【０００４】
フレームは、単一の時点に対応する（ほぼ）１セットのピクセルすべてである。基本的に、フレームは静止画と同じである。しかしながら、インターレース・ビデオにおいて、偶数番号の水平ラインのセットおよび奇数番号のセットは、フィールドで一まとめにされる。用語「絵（picture）」は、フレームまたはフィールドを指すことができる。
【０００５】
ビデオデータは、空間・時間の冗長度を含んでいる。類似性は、フレーム間の(時間的な)、および/またはフレーム内の(空間的な)、違いを単に記録することにより、符号化することができる。空間的なの符号化は、明るさにおいて変更できるのと同じように容易に、人間の目が色の小さな差を識別することができないという事実の利用により行なわれる。それゆえ、色の非常に類似したエリアは、「平均する」ことができる。
【０００６】
時間的な圧縮では、ピクセルの大数が多くの場合一連のフレーム上で同じになるので、１つのフレームから次のものまでの変化のみがコード化される。
【０００７】
画像圧縮は、典型的には、ロッシ圧縮を使用して、この冗長度を縮小する。通常、これは、（ａ）フレームから空間的な冗長度を縮小する画像データ圧縮技術（これはフレーム内（intraframe）圧縮または空間的な圧縮として知られている）、および、（ｂ）動き補償および時間的な冗長度を縮小する他の技術（フレーム間（interframe）圧縮または時間的な圧縮として知られている）によって達成される。
【０００８】
Ｈ．２６４／ＡＶＣは、ＩＳＯ（国際標準化機構）およびＩＴＵ（国際電気通信連合）の共同事業に由来する画像圧縮標準である。図１は、Ｈ．２６４／ＡＶＣ符号器ついてのブロック図を示す。入力映像フレーム１０２は、マクロブロック１０４に分割され、システム１００に供給される。各マクロブロック１０４について、予測値１３２が生成され、残差（residual）１０７を生成するためにオリジナルのマクロブロック１０４から引かれる。この残差１０７は、それから変換１０８され、量子化１１０される。
【０００９】
量子化されたマクロブロックは、それから圧縮したビットストリーム列１１３を生成するためにエントロピー符号化１１２される。量子化されたマクロブロックは、また逆量子化１１４され、逆変換１１６され、さらに加算器１１８によって予測値に加えられる。復元されたマクロブロックは、デブロッキングフィルタ１２０によりマクロブロックの端についてフィルターされ、次に、メモリ１２２に格納される。
【００１０】
量子化は、原理において、信号のダイナミック・レンジを縮小することを含んでいる。これは、エントロピー符号化によって生成されたビット数（レート）を詰め込む。これは、さらに残差の損失を招き、それはオリジナルと改造されたマクロブロックとを異ならせる。この損失は通常、量子化誤差（ひずみ）と呼ばれる。量子化の強さは、量子化係数パラメータによって決定される。量子化パラメータが大きいほど、ひずみは、より大きく、およびレートはより低い。
【００１１】
上に議論されるように、予測値（predictor）は、イントラ（intra）１２８、及びインター（inter）１３０の２つのタイプになりえる。空間的な推定１２４は、多数の選択の中からのイントラ予測値（intra predictor）１２８を生成するために、１つのフレーム内において近隣のマクロブロックを見る。動きの推定１２６は、多数の選択の中からのインター予測値（inter predictor）１３０を生成するために、前の／将来のフレームを見る。インター予測値は、時間的な冗長度を減少させることを目標とする。典型的には、時間的な冗長度を減少させることは、低減率に最も大きな影響を及ぼす。
【００１２】
動きの推定は、それが選ばなければならない可能性のある予測値の巨大な数のために、符号器において最も計算上費用のかかるブロックのうちの１つかもしれない。実際に、動きの推定は、前のフレームのサブセットを含むサーチエリアのインター予測値を探索することを含んでいる。サーチエリアからの可能性のある予測値または候補は、コスト関数または距離（metric）に基づいて調べられる。一旦、距離がサーチエリアのすべての候補のために計算されれば、距離を最小化する候補がインター予測値として選ばれる。従って、動きの推定に影響する主な要因は、サーチエリア・サイズ、サーチ技法およびコスト関数、である、
特にコスト関数に注目すると、コスト関数は、本質的に現在フレームのオリジナルのブロックとサーチエリアの候補ブロックの間の冗長度を数量化する。冗長度は、理想としては、正確なレートおよび、ひずみの点から数量化されるべきである。
【００１３】
現在の動き推定量において使用されるコスト関数は、差分絶対値和（Sum-of-Absolute-Difference）（ＳＡＤ）である。図２は、ＳＡＤがどのように計算されるか示す。Frame(t) ２０６は、符号化ＭＢ（MACROBLOCK）  ＲＡＭ２１２に格納されるマクロブロック２０８を含んでいる現在フレームである。Frame(t-1) ２０２は、サーチＲＡＭ２１０に格納されるサーチエリア２０４を含んでいる前のフレームである。１つを超える前のフレームを使用することができることが認識される。
【００１４】
図２における例において、サーチエリア２０４のサイズは、Ｍ×Ｎである。検討するブロックのサイズをＡ×Ｂとする。ここでＡとＢは表１に定義される。現在フレーム２０６から与えられたブロック２０８をｃ２１５と表示する。サーチエリア２０４からの各候補をｐ（ｘ，ｙ）２１４と表示する。ここで、ｘ∈［０，Ｎ］およびｙ∈［０，Ｍ］である。（ｘ，ｙ）は、サーチエリア２１４の位置を表わす。
【表１】
2009526499.tif 000003
【００１５】
下記のステップが動きベクトル（Ｘ、Ｙ）を得るために計算される。
【００１６】
ｃは、残余誤差信号２１８、ｅ（ｘ，ｙ）を得るために、ｐ（ｘ，ｙ）２１４について、ｐ（ｘ，ｙ）２１４によって、動き補償２１６される。
【数１】
2009526499.tif 000004
【００１７】
その後、ＳＡＤ２２２が、ｅ（ｘ，ｙ）から計算される２２０。
【数２】
2009526499.tif 000005
【００１８】
その後、動きベクトル（Ｘ、Ｙ）が、ＳＡＤ（ｘ，ｙ）から計算される。
【数３】
2009526499.tif 000006
【００１９】
理想的には、予測値マクロブロック・パーティションは、最も厳密にマクロブロックに似ているマクロブロック・パーティションであるべきである。ＳＡＤの短所のうちの１つは、それが明確にかつ正確にレート（Rate）と、ひずみ（Distortion）を説明しないということである。よって、冗長度は正確に定量化されない。それゆえ、選ばれた予測マクロブロック・パーティションが最も有効な選択ではないことはありえる。したがって、ＳＡＤを利用するいくつかのケースにおいて、アプローチは、実際に最適な性能より低い結果となるかも知れない。
【発明の開示】
【発明の概要】
【００２０】
１つの実施態様は、ビットレート信号を決定することを含んでいるビデオ符号器における動きの推定および補償において、予測マクロブロック・パーティションを選択し、ひずみ信号を生成し、ビットレートおよび、ひずみ信号に基づいてコストを計算し、そして、前記コストから動きベクトルを決定する方法に関する。前記動きベクトルは予測マクロブロック・パーティションを指定する。この方法は、携帯電話、ディジタル・オーガナイザ、またはラップトップ・コンピュータのような、モバイル装置において実現され得る。
【詳細な説明】
【００２１】
いくつかの実施態様が、ここで詳細に言及されるであろう。それらの例は添付図面の中で示される。実施態様が説明を制限するようには意図されないことが理解されるであろう。それどころか、その説明は、代案、修正および等価物をカバーするように意図される。それは、請求項によって定義されるような説明の精神および範囲内に含まれ得る。さらに、詳細な説明では、多数の特定の詳細は十分な理解を提供するために述べられる。しかしながら、現在の説明がこれらの特定の詳細なしで実行され得ることは当業者にとって明白かもしれない。他の実例では、周知の方法、手続き、コンポーネントおよび回路は、現在の説明の態様をむだに不明瞭にしないように詳細に記述されていない。
【００２２】
以下の詳細な説明のいくつかの部分は、手続き、ロジック・ブロック、処理、およびコンピューターまたはデジタルシステムのメモリ内のデータ・ビットに対するオペレーションの他の記号表現の点から示される。これらの説明と表現は、有効に他の当業者にそれらの仕事の実体を伝えるために、データ処理技術の当業者よって使用される手段である。手続き、ロジック・ブロック、プロセスなどは、ここに、そして一般に、希望の結果に導くステップまたは命令のシーケンスと理解される。
【００２３】
ここにおける議論から明白なものとして特に別記しない限り、実施態様の議論の全体にわたって、「決定すること」、「出力すること」、「送信すること」、「記録すること」、「置くこと」、「格納すること」、「表示すること」、「受け取ること」、「認識すること」、「利用すること」、「生成すること」、「提供すること」、「アクセスすること」、「チェックすること」、「通知すること」、または「伝えること」などの用語を、利用する議論は、データを操作し変換するコンピュータ・システムまたは同様の電子コンピューティング装置のアクションおよびプロセスに関係することが理解される。データは、コンピュータ・システムのレジスタおよびメモリ内の物理的な（電子）量として表わされ、コンピュータ・システム・メモリまたはレジスタ、他のそのような情報記憶装置、伝送装置あるいは表示装置内において物理量として同様に表わされる、他のデータに変換される。
【００２４】
一般に、以下の説明の実施態様は、候補マクロブロック・パーティションに、マクロブロック・パーティションが受け、予測マクロブロック・パーティションとして実際に選択されるプロセスを近似する一連のプロセスを受けさせる（一般に図１を参照）。そうすることは、各候補マクロブロック・パーティションのレートおよび、ひずみの正確な近似を可能にする。それから、実施態様は、符号化プロセスの間に生じるレートおよび、ひずみに関連したコストを最も良く最小化する候補マクロブロック・パーティションを選択するために、ＳＡＤではなく、ラグランジュ関数に基づいたコスト関数を使用する。
【００２５】
予測マクロブロック・パーティション選択の最適解は、ＳＡＤがどこに立っているか、および可能なゲインの範囲を理解することを確立する必要がある。最適解は、レート（Ｒ）制約の下の最小のひずみ（Ｄ）を保証するであろう。そのような解は、Ｄ＋λＲのようにレートとひずみを組み合わせる、ラグランジュ関数に基づいた最適化を使用して見つかる。λは、レートとひずみの間のトレードオフを表わすラグランジュの乗数である。図３は、ＲＤ最適化されたコスト関数についての最適解のブロック図３００を示す。レートとひずみを正確に計算するために、図３に示され、下記に説明されるように、符号化プロセス全体は、候補ブロック３０４の各々について実行されるべきである。
【００２６】
現在フレーム３０８は、候補マクロブロック・パーティション３０４について、それによって、式（１）に示されるごとく残余誤差信号ｅ（ｘ，ｙ）を得るために、動き補償される３１０。
【００２７】
ｅ（ｘ，ｙ）は、整数個の４ｘ４ブロックｅ（ｘ，ｙ，z）３１２に分割される。ここで、
【数４】
2009526499.tif 000007
【００２８】
ｅ（ｘ，ｙ）の  サイズは、Ａ×Ｂである。ＡとＢがとることができる値は、表１に示される。ｅ（ｘ，ｙ，ｚ）をＥによって表すものとする。
【表２】
2009526499.tif 000008
【００２９】
Ｅ３１２は、空間領域からの周波数領域へ変換される３１４。変換されたブロックをｔ（ｘ，ｙ，ｚ）またはＴ３１６と表示するものとする。変換は分離可能であるので、それは、Ｅ３１２に対して、水平（４）および垂直（５）の２段階、で適用される。Ｅ’は、中間出力を表わす。Ｄは、式（６）で示される変換マトリックスを表わす。
【数５】
2009526499.tif 000009
【００３０】
Ｔ３１６は、事前に定義された量子化パラメータＱで量子化される３１８。量子化ブロックは、ｌ（ｘ，ｙ，ｚ）あるいはＬ３２０によって表すものとする。
【数６】
2009526499.tif 000010
【００３１】
Ｍの要素に対する値は、当技術分野において既知の表から導出される。表のサンプルは、表２に示される。
【表３】
2009526499.tif 000011
【００３２】
次に、Ｌ３２０は、コンテキスト適応型可変長符号化（context-adaptive variable length coding）（ＣＡＶＬＣ）方式を使用してエントロピー符号化される３２８。
【００３３】
これは、ｌ（ｘ，ｙ，ｚ）を表わすために得られたビットの数を生成する。それは、Ｒａｔｅ（ｘ，ｙ，ｚ，Ｑ）またはＲａｔｅ（Ｑ）３３２のように表示される。
【数７】
2009526499.tif 000012
【００３４】
ＣＡＶＬＣが当技術分野において知られ、別のエントロピー符号化アルゴリズムがその場所において使用されてもよいことは、当業者によって認識されるべきである。
【００３５】
Ｌ３２０は量子化パラメータＱで、逆量子化される３２２。逆量子化ブロックは、
【数８】
2009526499.tif 000013
【００３６】
で表示するものとする。
【数９】
2009526499.tif 000014
【数１０】
2009526499.tif 000015
【００３７】
の要素に対する値は、当技術分野において既知の表から導出される。この表のサンプルは、表３に示される。
【表４】
2009526499.tif 000016
【数１１】
2009526499.tif 000017
【００３８】
は周波数領域から空間領域へ変換される３２６。変換されたブロックを
【数１２】
2009526499.tif 000018
【００３９】
で表示するものとする。この変換は分離可能であるので、それは、
【数１３】
2009526499.tif 000019
【００４０】
に対して、水平（１４）および垂直（１５）の２段階で適用される。Ｌ’は中間の出力を表わす。
【数１４】
2009526499.tif 000020
【００４１】
は、式（１６）において示される変換マトリックスを表わす。
【数１５】
2009526499.tif 000021
【数１６】
2009526499.tif 000022
【００４２】
の間の２乗誤差は、ひずみ、Distortion(x,y,z,Q)  あるいはDistortion(Q)を表わす。
【数１７】
2009526499.tif 000023
【００４３】
ラグランジュのコストCost4x4(x,y,z,Q,λ) は、定義済みのλについて計算される。
【数１８】
2009526499.tif 000024
【００４４】
ｐ（ｘ，ｙ）についての全コストは、次式で与えられる。
【数１９】
2009526499.tif 000025
【００４５】
その後、動きベクトル（Ｘ，Ｙ）は、以下のように計算される。
【数２０】
2009526499.tif 000026
【００４６】
ここで説明した最適解は、たとえそれが最良の可能な解を提供するとしても、実際に応用するには複雑すぎるかもしない。現在の説明の実施態様は、最適解の計算上の近似を表わす、新しいコスト関数を導入する。この計算上の近似は、同じものの複雑さを著しく縮小するけれども最適解の結果に軽微な影響を及ぼすかもしれない。
【００４７】
図４は、１つの実施態様のブロック図４００を示す。単に最適解で、現在フレーム４０８は、残余誤差信号、ｅ（ｘ、ｙ）を得るために、候補マクロブロック・パーティション４０６について、それによって動き補償される４１０。その後、ｅ（ｘ、ｙ）は、表１に示されるように、整数個の４×４のブロック、ｅ（ｘ、ｙ、ｚ）つまりＥ４１２に分割される。それから、Ｅ４１２は、ｔ（ｘ、ｙ、ｚ）あるいはＴ４１６を得るために、式（４）、（５）および（６）において示されるように空間領域からの周波数領域へ変換される４１４。
【００４８】
最適解により、Ｔは、次に量子化されるだろう。しかしながら、それが乗算および他の複雑な２進数の関数を含んでいるので、量子化プロセスは計算上複雑である。したがって、１つの実施態様では、式（７）からのＴおよびＭの乗算は、一連のシフトと加算によって次のように近似される。
【数２１】
2009526499.tif 000027
【００４９】
したがって、式（７）は、量子化近似４１８にしたがい書き直すことができる。
【数２２】
2009526499.tif 000028
【００５０】
ここで、ｊ∈［０，３］であり、また、ｘが負の場合、Ｓｉｇｎ（ｘ）は１であり、そして正の場合０である。
【００５１】
ＳとＲは、式（９）と（１０）から決定することができる。
【００５２】
増倍係数Ｍは、
【数２３】
2009526499.tif 000029
【００５３】
で近似される。
【数２４】
2009526499.tif 000030
【００５４】
の値は、対応する第１の量子化近似パラメータおよび近似の増倍係数
【数２５】
2009526499.tif 000031
【００５５】
の対応する要素について、表４および表５で見つかる。
【数２６】
2009526499.tif 000032
【表５】
2009526499.tif 000033
【表６】
2009526499.tif 000034
【００５６】
その後、最適解によって、量子化近似ブロック４２０は、レート信号４２８を生成するためにエントロピー符号化されるであろう。しかしながら、ＣＡＶＬＣのようなエントロピー符号化するアルゴリズムは、高度な計算上のオペレーションを必要とする。４ｘ４の量子化したブロックのエントロピー符号化は、トークン（ゼロでない係数の数、および引き続く１の数を示す）、サインすなわち引き続く１、ゼロでない係数のレベル、および、ゼロでない係数の間のゼロのラン、をコード化することを含んでいる。１つの実施態様では、エントロピー符号化は、レートを評価するための高速ビット推定方法（Fast Bits Estimation Method）（ＦＢＥＭ）の使用により、省かれる。ＦＢＥＭによれば、異なる要素によって得られるビット数は、ゼロでない係数の数（Ｎｃ）、ゼロの数（Ｎｚ）および絶対値レベルの和（ＳＡＬ）から導き出すことができる。
【数２７】
2009526499.tif 000035
【００５７】
したがって、レート４２８は、エントロピー符号化近似４２４によって各候補マクロブロック・パーティション４０６ごとに決定することができる。
【００５８】
最適解によれば、Ｌは、さらに逆量子化３２２され、および逆変換３２６される、必要があるだろう。量子化に類似しているので、逆量子化もまた、計算上複雑である。１つの実施態様では、これらのプロセスは、逆量子化近似によって単純化される。
【００５９】
逆量子化近似は、量子化近似と同じステップであるが第２の量子化パラメータを用いて行なうことにより達成される。
【数２８】
2009526499.tif 000036
【００６０】
１つの実施態様では、第２の量子化パラメータは、Ｓ＝１５（それは、ゼロのひずみ値の計算することの等価物を近似する）のごとくのものが選ばれる。
【００６１】
上記のステップを行うことによって、逆量子化３２２は著しく単純化され、そして、逆変換３２６はもはや必要ではない。実施態様が、第２の量子化パラメータを用いた量子化近似によって逆量子化近似を達成するので、ＬとＬ’の両方は、同じ回路類、モジュールなどから生成することができることが、認識される。
【００６２】
１つの実施態様において、一度、逆量子化近似ブロックＬ’４２２が生成されると、ひずみ４３０、Distortion(x,y,z,Q) または Distortion(Q)は、Ｌ’とＬの間の２乗誤差によって表わすことができる。（Ｌ’−Ｌ）は、量子化誤差を表わし、小さなダイナミック・レンジを持っている。従って、実施態様は、２乗する演算を回避するためにルックアップテーブルに２乗された値を格納することができる。
【数２９】
2009526499.tif 000037
【００６３】
１つの実施態様では、整数個の４×４のブロックの各々に対するラグランジュのコストCost4x4(x,y,z,Q,λ)  が、定義済みのλについて計算される。
【数３０】
2009526499.tif 000038
【００６４】
１つの実施態様では、ｐ（ｘ，ｙ）に対する全コストは次式で与えられる。
【数３１】
2009526499.tif 000039
【００６５】
その後、最後に、動きベクトル（Ｘ，Ｙ）は以下のように選択される。
【数３２】
2009526499.tif 000040
【００６６】
したがって、上記の実施態様は、各候補マクロブロック・パーティションのレートおよびひずみを正確に近似することができる。実施態様は、その選択処理が明確にRateとDistortionを説明するので、ＳＡＤコスト関数より確実性のある最良の可能な予測マクロブロック・パーティションを選択し得る。したがって、図５および図６に示すように、実施態様は、与えられたビットレートについて、ＳＡＤより高い信号対雑音比を達成することができる。
【００６７】
開示された実施態様の前の説明は、任意の当業者が現在の説明を作るか使用することを可能にするために提供される。これらの実施態様の様々な修正は、当業者に即座に明白かもしれない。また、ここに定義された総括的な法則は、説明の精神か範囲から外れずに、他の実施態様に適用され得る。したがって、現在の説明は、ここに示された実施態様に限定するようには意図されず、ここに開示された法則および新規な特徴と一致する最も広い範囲を与えられるべきである。
【図面の簡単な説明】
【００６８】
【図１】Ｈ．２６４／ＡＶＣビデオ符号器のブロック図を示す。
【図２】標準ビデオ符号器において使用されるような差分絶対値和コスト関数のブロック図を示す。
【図３】ビデオ符号器ついての理論上最適な解決法のレートひずみ最適化されたコスト関数（Rate-Distortion-optimized cost function）のブロック図を示す。
【図４】ビデオ符号器ついてのレートひずみ最適化されたコスト関数のブロック図を示す。
【図５】コスト関数を使用するビデオ符号器と比較した、差分絶対値和コスト関数を使用するビデオ符号器の性能の第１のグラフ例を示す。
【図６】コスト関数を使用するビデオ符号器と比較した、差分絶対値和コスト関数を使用するビデオ符号器の性能の第２のグラフ例を示す。
【図１】
2009526499.tif 000041
【図２】
2009526499.tif 000042
【図３】
2009526499.tif 000043
【図４】
2009526499.tif 000044
【図５】
2009526499.tif 000045
【図６】
2009526499.tif 000046
【国際調査報告】
2009526499.tif 000047
2009526499.tif 000048
2009526499.tif 000049
2009526499.tif 000050