(57)【要約】      （修正有）【課題】フレームのデータを記憶構造内で新しい方法で編成することによってフレームの符号化／復号化を容易にする。【解決手段】フレームのスライスに対して割り当てられた記憶構造の一部において、使用される区画エントリが前記割り当てられた部分の第１のセクション内に記憶され、使用されない区画エントリが前記割り当てられた部分の第２のセクション内に記憶され、前記第１および第２のセクションはそれぞれ前記記憶構造内の記憶の連続した領域を含み、使用される区画エントリが使用されない区画エントリと一緒に分散化されないようになっている。実施形態においては、ビデオ・データの符号化または復号化において有用な追加のデータが決定されて使用される区画エントリの前記使用されないバイト内に記憶される。他の実施形態においては、マクロブロックの２つ以上の同一の区画が１つの区画内に一体化される。【選択図】図７
2006025414.tif 000002
【特許請求の範囲】
【請求項１】
ビデオ・フレーム・スライスのデータをそのスライスに対して割り当てられた記憶装置内に記憶するための方法であって、前記スライスは２つ以上のマクロブロックを含み、各マクロブロックは１つまたは複数の区画を含み、前記割り当てられた記憶装置内に前記マクロブロックに対して割り当てられた複数の区画エントリを有し、前記スライスの前記データは前記マクロブロックの区画に対する区画データを含み、前記方法が、
前記マクロブロックの使用される区画エントリを前記割り当てられた記憶装置の第１のセクション内に記憶するステップを含み、使用される区画エントリがマクロブロックの区画に対するデータを含み、さらに、
前記マクロブロックの使用されない区画エントリを前記割り当てられた記憶装置の第２のセクションに記憶するステップを含み、使用されない区画エントリがマクロブロックの区画に対するデータを含まない方法。
【請求項２】
前記第１および第２のセクションがそれぞれ前記割り当てられた記憶装置内の記憶の連続した領域を含み、それにより、使用される区画エントリが前記割り当てられた記憶装置内で使用されない区画エントリと一緒に分散化されないようにしている請求項１に記載の方法。
【請求項３】
前記割り当てられた記憶装置に関連付けられたインデックスのリストを生成するステップをさらに含み、前記インデックスのリスト内のインデックスは前記スライス内のマクロブロックおよび、前記割り当てられた記憶装置内の前記マクロブロックの第１の区画エントリだけに対するロケーション情報を識別する請求項１に記載の方法。
【請求項４】
前記スライスの前記データが各マクロブロックに対する元のヘッダ・データをさらに含み、
前記マクロブロックに対する前記元のヘッダ・データを使用してマクロブロックに対する統合化されたヘッダ・データを導くステップと、
前記マクロブロックに対して導かれた前記統合化されたヘッダ・データを、前記マクロブロックの使用される区画エントリ内に記憶するステップとをさらに含む請求項１に記載の方法。
【請求項５】
前記統合化されたヘッダ・データを導くステップが、
前記マクロブロックの区画構成にマッチする区画構成を識別するステップと、
前記マクロブロックに対して識別された前記区画構成に関連付けられた一意の識別子を決定するステップとを含み、前記一意の識別子が前記マクロブロックに対する前記統合化されたヘッダ・データを含む請求項４に記載の方法。
【請求項６】
前記識別および決定のステップが、前記マクロブロックの可能なパターン構成を含むパターン構成ルックアップ・テーブルを使用して実行され、可能な各パターン構成が一意の識別子に関連付けられている請求項５に記載の方法。
【請求項７】
前記スライスが一連のフレーム内のフレーム内に含まれ、前記スライスの前記データが第１の元のフレーム基準リストに対するデータをさらに含み、区画は関連付けられた運動ベクトルおよび、前記第１の元のフレーム基準リスト内のフレーム番号を示す元の基準フレーム・インデックスを有し、前記フレーム番号は前記運動ベクトルがベースとしている前記一連のフレーム内の特定のフレームを示し、
前記スライス内の１つまたは複数の区画に対して、前記第１の元のフレーム基準リストとカノニカルなフレーム基準リストとを使用して、関連付けられた元の基準フレーム・インデックスをカノニカルな基準フレーム・インデックスに対してマップするステップと、
前記カノニカルな基準フレーム・インデックスに対するデータを前記区画に対する前記使用される区画エントリ内に記憶するステップとをさらに含む請求項１に記載の方法。
【請求項８】
前記カノニカルな基準フレーム・インデックスが、前記カノニカルなフレーム基準リスト内のフレーム番号を示し、前記フレーム番号は前記区画に関連付けられている運動ベクトルがベースとしている一連のフレーム内の特定のフレームを示す請求項７に記載の方法。
【請求項９】
追加のビデオ・フレーム・スライスに対するデータを受信するステップをさらに含み、前記追加のスライスが前記一連のフレーム内のフレーム内に含まれ、前記追加のスライスの前記データが前記第１の元のフレーム基準リストとは異なっている第２の元のフレーム基準リストに対するデータを含み、前記追加のスライス内の区画が前記第２の元のフレーム基準リスト内のフレーム番号を示す関連付けられた運動ベクトルおよび元の基準フレーム・インデックスを有し、前記フレーム番号が前記運動ベクトルがベースとしている前記一連のフレーム内の特定のフレームを示し、
前記追加のスライス内の１つまたは複数の区画に対して、前記第２の元の基準フレーム・リストとカノニカルなフレーム基準リストとを使用して、関連付けられた元の基準フレーム・インデックスを前記カノニカルな基準フレーム・インデックスに対してマップするステップをさらに含む請求項７に記載の方法。
【請求項１０】
値が同じであるスライスのいずれかにおける任意の区画に対してマップされている任意のカノニカルな基準フレーム・インデックスが、前記一連のフレーム内の同じ特定のフレームを示す請求項９に記載の方法。
【請求項１１】
使用される区画エントリが運動ベクトルおよび基準フレーム・インデックス・データおよび使用されないバイトを含み、
前記スライスの符号化または復号化において有用である他のデータを決定するステップと、
前記決定されたデータを、使用される区画エントリの前記使用されないバイト内に記憶するステップとをさらに含む請求項１に記載の方法。
【請求項１２】
特定のマクロブロックの２つ以上の区画が同一であるかどうかを判定するステップと、
前記判定に基づいて前記２つ以上の区画を前記特定のマクロブロックの１つの区画内に一体化するステップとをさらに含む請求項１に記載の方法。
【請求項１３】
区画に対する区画データが運動ベクトルと基準フレーム・インデックス・データを含み、
２つ以上の区画が同一であるかどうかを判定するステップが、前記２つ以上の区画の前記運動ベクトルおよび基準フレーム・インデックス・データが同一であるかどうかを判定するステップを含む請求項１２に記載の方法。
【請求項１４】
命令が記憶されているコンピュータ可読媒体を含むコンピュータ・プログラム製品であって、実行時にビデオ・フレーム・スライスのデータを前記スライスに対して割り当てられた記憶装置内に記憶し、前記スライスが２つ以上のマクロブロックを含み、各マクロブロックが１つまたは複数の区画を含み、前記マクロブロックに対して割り当てられている複数の区画エントリを前記割り当てられた記憶装置内に有し、前記スライスの前記データが前記マクロブロックの区画に対する区画データを含み、前記コンピュータ・プログラム製品が、
前記マクロブロックの使用される区画エントリを前記割り当てられた記憶装置の第１のセクション内に記憶するステップであって、使用される区画エントリはマクロブロックの区画に対するデータを含むステップのための命令の組と、
前記マクロブロックの使用されない区画エントリを前記割り当てられた記憶装置の第２のセクション内に記憶するステップであって、使用されない区画エントリはマクロブロックの区画に対するデータを含んでいないステップのための命令の組とを含むコンピュータ・プログラム製品。
【請求項１５】
前記第１および第２のセクションがそれぞれ前記割り当てられた記憶装置内の記憶の連続した領域を含み、それにより、使用される区画エントリが前記割り当てられた記憶装置内で使用されない区画エントリと一緒に分散化されない請求項１４に記載のコンピュータ・プログラム製品。
【請求項１６】
前記スライスの前記データが各マクロブロックに対する元のヘッダ・データをさらに含み、前記コンピュータ・プログラム製品が、
前記マクロブロックに対する前記元のヘッダ・データを使用してマクロブロックに対する統合化されたヘッダ・データを導き出すステップのための命令の組と、
前記マクロブロックに対して導き出された前記統合化されたヘッダ・データを、使用される区画エントリ内に記憶するステップのための命令の組とをさらに含む請求項１４に記載のコンピュータ・プログラム製品。
【請求項１７】
前記スライスが一連のフレーム内のフレーム内に含まれ、前記スライスの前記データが第１の元のフレーム基準リストに対するデータをさらに含み、区画は関連付けられている運動ベクトルとフレーム番号を示す元の基準フレーム・インデックスを前記第１の元のフレーム基準リスト内に有し、前記フレーム番号が、前記運動ベクトルがベースとしている前記一連のフレーム内の特定のフレームを示し、前記コンピュータ・プログラム製品が、
前記スライス内の１つまたは複数の区画に対して、前記第１の元のフレーム基準リストおよびカノニカルなフレーム基準リストを使用して、関連付けられた元の基準フレーム・インデックスをカノニカルな基準フレーム・インデックスに対してマップするステップのための命令の組と、
前記カノニカルな基準フレーム・インデックスに対するデータを前記区画に対する前記使用される区画エントリ内に記憶するステップのための命令の組とをさらに含む請求項１４に記載のコンピュータ・プログラム製品。
【請求項１８】
追加のビデオ・フレーム・スライスに対するデータを受信するための命令の組をさらに含み、前記追加のスライスが前記一連のフレーム内のフレーム内に含まれ、前記追加のスライスの前記データが前記第１の元のフレーム基準リストとは異なっている第２の元のフレーム基準リストに対するデータを含み、前記追加のスライス内の区画が関連付けられた運動ベクトルと前記第２の元のフレーム基準リスト内のフレーム番号を示す元の基準フレーム・インデックスとを有し、前記フレーム番号が、前記運動ベクトルがベースとしている前記一連のフレーム内の特定のフレームを示し、
前記追加のスライス内の１つまたは複数の区画に対して、前記第２の元のフレーム基準リストおよびカノニカルなフレーム基準リストを使用して、関連付けられた元の基準フレーム・インデックスを前記カノニカルな基準フレーム・インデックスに対してマップするための命令の組をさらに含み、値が同じであるいずれかのスライス内の任意の区画に対してマップされた任意のカノニカルな基準フレーム・インデックスが前記一連のフレーム内の同じ特定のフレームを示す請求項１７に記載のコンピュータ・プログラム製品。
【請求項１９】
使用される区画エントリが運動ベクトルおよび基準フレーム・インデックス・データを含む使用されるバイトと、使用されないバイトとを含み、前記コンピュータ・プログラム製品が、
前記スライスの前記符号化または復号化において有用な他のデータを決定するステップのための命令の組と、
前記決定されたデータを、使用される区画エントリの前記使用されないバイト内に記憶するステップのための命令の組とをさらに含む請求項１４に記載のコンピュータ・プログラム製品。
【請求項２０】
特定のマクロブロックの２つ以上の区画が同一であるかどうかを判定するステップのための命令の組と、
前記判定に基づいて前記２つ以上の区画を前記特定のマクロブロックの１つの区画内に一体化するステップのための命令の組とをさらに含む請求項１４に記載のコンピュータ・プログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願）
本出願は、２００４年６月２７日出願の出願番号６０／５８３，４４７の「画像の符号化および復号化」（Ｅｎｃｏｄｉｎｇ  ａｎｄ  Ｄｅｃｏｄｉｎｇ  Ｉｍａｇｅｓ）という名称の米国仮特許出願に対する利益を主張する。
（技術分野）
本発明は、ビデオ・データ・ストリームの符号化および復号化における記憶装置の効率的使用法に関する。
【背景技術】
【０００２】
ビデオ・コーデック（ＣＯｍｐｒｅｓｓｏｒ‐ＤＥＣｏｍｐｒｅｓｓｏｒ）は、ビデオ・データ・ストリームを符号化／圧縮および復号化／解凍して伝送を高速化し、記憶装置の空間を小さくするようにストリームのサイズを減らすために設計された圧縮アルゴリズムである。損失はあるが、ビデオ・コーデックはビデオ・ストリームのバイナリ・データを圧縮しながらビデオの品質を維持しようとする。一般的なビデオ・コーデックの例としては、ＭＰＥＧ‐４、ＡＶＩ、ＷＭＶ、ＲＭ、ＲＶ、Ｈ．２６１、Ｈ．２６３およびＨ．２６４がある。
ビデオ・ストリームは一連のビデオ・フレームから構成され、各フレームは複数のマクロブロックから構成されている。ビデオ・コーデックは整数個のマクロブロックを含んでいる１つまたは複数のスライスまたはサブ部分にフレームを分割することによってその一連のフレームで各フレームを符号化する。１つのマクロブロックは、通常、画素の１６×１６アレイであり（他のサイズのマクロブロックも可能であるが）、符号化および復号化のために区画（ｐａｒｔｉｔｉｏｎ）に分割することができる。一例として、図１は、Ｈ．２６４圧縮規格における、マクロブロックを区画化することができる異なる方法を示す。
【０００３】
図１に示すように、１つのマクロブロックは以下のように２５９種類の可能な方法のうちの１つで区画化することができる。
１．  １つの区画
２．  ２つの垂直方向の区画
３．  ２つの水平方向の区画
４．  ４つのより小さな四角形の区画
最後のケースにおいては、結果としての四角形の各区画を、１つのマクロブロックに対する最大１６個の区画にまで同様な方法で（マクロブロックを区画化するための他の２５６種類の方法を勘定して）区画化することができる。
マクロブロックの内容は自己充足型とするか、または１つまたは２つの異なるフレームから予測されるようにすることができる。受信されたビット・ストリーム（符号化プロセスの間に生成された）において、次の予測情報を各区画に対して導き出すことができる。それらは、運動ベクトル（ｘおよびｙの成分から構成されている）およびその運動ベクトルがベースとしているフレーム（一連のフレーム内の）に対して関連付けられた指示子である。この指示子は、例えば、関連付けられた基準フレーム・リストと結合して使用される基準フレーム・インデックスであってよく、その運動ベクトルがどの特定のフレームをベースとしているかどうかを示す。
【０００４】
図２は、基準フレーム・インデックスおよび基準フレーム・リストの概念を示す。１つのフレームの各スライスに対して、運動ベクトルに対して特定のフレームを識別するために使用される１つまたは複数の基準フレーム・リストが記憶されている。図２の例においては、運動ベクトルに対して特定のフレームを識別するために第１および第２の基準フレーム・リストが使用されている。通常、スライスが受信される時、そのスライスのヘッダはフレーム基準リストを導き出すための情報を含んでいる。
１つの運動ベクトルに関連付けられた基準フレーム・インデックスは、１つの基準フレーム・リスト内の１つのエントリ（フレーム番号を含む）を規定し、それは一連のフレームでその運動ベクトルがベースとしているフレームを指す。図２の例においては、０から６までの番号が付けられている７個のアクティブ・フレーム（すなわち、記憶装置内に現在保持されているフレーム）がある。「３」と番号が付けられているフレームが現在処理されている。基準フレーム・インデックスが関連付けられた第１の運動ベクトルに対して０の値を指定する場合、これはその第１の基準フレーム・リストの第１のエントリ内のフレーム番号が、その運動ベクトルがベースとしているフレームであることを示す。従って、図２の例に示すように、「２」の番号が付けられたフレームは第１の運動ベクトルがベースとしているフレームである。さらに、もう１つの例として、基準フレーム・インデックスが関連付けられた第２の運動ベクトルに対する２の値を指定している場合、これは第２の基準フレーム・リスト（第２の運動ベクトルに対する）の第３のエントリ内のフレーム番号が、第２の運動ベクトルがベースとしているフレームであることを示す。従って、図２の例に示すように、「６」と番号付けられているフレームは第２の運動ベクトルがベースとしているフレームである。
【０００５】
図３は、１つのフレームの１つのスライスに対する区画データを含んでいる通常の記憶構造３０５の概念図を示す。図３の例においては、そのスライスは３つのマクロブロックから構成されており、この場合、第１のマクロブロック（マクロブロック０）は１つの区画から構成されており、第２のマクロブロック（マクロブロック１）は１６個の区画から構成されており、そして第３のマクロブロック（マクロブロック２）は２個の区画から構成されている。
通常、復号化時に記憶装置はそのスライスの各マクロブロックが最大個数の区画（例えば、Ｈ．２６４規格では１６個の区画）に分割されることを仮定する「最悪ケースのシナリオ」でスライスに対して割り当てられる。従って、Ｈ．２６４規格の場合、スライスの各マクロブロックに対して、１つのヘッダおよび１６個の区画エントリに対して十分な記憶空間が割り当てられている。１つのデータ構造の区画エントリはフレームの復号化時に区画データを記憶する。各区画エントリは１つの区画に対するデータ（例えば、運動ベクトルおよび基準フレーム・インデックス・データ）を含んでいる。
図３の図はそのスライスに対して割り当てられた記憶構造の割り当てられた部分３１０を示す。１つのスライスの各マクロブロックは、通常、１６個の区画には分割されないので、１つのマクロブロックにはそのマクロブロック内に含まれている区画より多い区画エントリに対する記憶が割り当てられることが多い。従って、１つのマクロブロックに対する記憶構造の割り当てられた部分は１つまたは複数の使用されない区画エントリ（そのマクロブロックの１つの区画に対するデータを含んでいないエントリ）以外に、通常、１つまたは複数の使用される区画エントリ（そのマクロブロックの実際の区画に対するデータを含んでいるエントリ）を含んでいる。使用される区画エントリは意味のある／有用なデータ（例えば、１つの区画に対する運動ベクトルおよび基準フレーム・インデックスなど）を含み、一方、使用されない区画エントリは意味のある／有用なデータを含まない。
図３に示すように、その区画の各マクロブロックに対して、その記憶構造はヘッダ・セクションと区画エントリ・セクションを含んでいる。通常、復号化時に、１つのヘッダに対して、そのマクロブロックが１６個の区画に分割されることを仮定する「最悪ケースのシナリオ」ベースで記憶が割り当てられる。従って、各マクロブロック・ヘッダに対して、１６個のヘッダ区画エントリのための十分な記憶空間が割り当てられている。マクロブロックに対する従来のヘッダはそのマクロブロックがどのように区画化されているかを記述しているデータを含んでいる。そのような記述データは、例えば、各区画の位置および寸法のデータを含む。図４は、マクロブロック２に対する記憶構造内に記憶されている従来のヘッダ４０５の概念図を示す。マクロブロック２は２個の区画に分割されている。従って、そのヘッダはそれぞれが特定の区画の記述データを含む２個の使用されるヘッダ区画エントリを含むことになる。残りの１４個のヘッダ区画エントリは空（使用されない）になる。さらに、各ヘッダはそのマクロブロック内の区画の数を示すデータを含んでいる。
【０００６】
図３に示すように、記憶構造３０５の第１の部分３１５はマクロブロック０に対するデータを含んでいる。マクロブロック０は１個の区画から構成されているので、その記憶構造はマクロブロック０の第１の区画だけに対する使用される区画エントリ（区画エントリ０）を含み、一方、マクロブロック０に対して割り当てられている残りの１５個の区画エントリ（区画エントリ１〜１５）は使用されないエントリである。記憶構造３０５の第２の部分３２０はマクロブロック１に対するデータを含んでいる。マクロブロック１は１６個の区画から構成されているので、その記憶構造はマクロブロック１の第１から第１６の区画に対して使用される区画エントリ（区画エントリ０〜１５）を含み、マクロブロック１に対して割り当てられるすべてのエントリが使用されるようになっている。記憶構造３０５の第３の部分３２５は、マクロブロック２に対するデータを含んでいる。マクロブロック２は２個の区画から構成されているので、その記憶構造はマクロブロック２の第１および第２の区画に対して使用される区画エントリを含み、一方、マクロブロック２に対して割り当てられている残りの１４個の区画エントリは使用されない。
従って、このスライスに対する区画データは、通常、使用されない区画エントリが使用される区画エントリと一緒に分散している偶然のパターンで記憶構造内に記憶されている。記憶構造内のデータ記憶のこの偶然のパターンによって、スライスの復号化が非効率となる。これはＣＰＵが復号化時に記憶装置から区画データをロードしている時に、ＣＰＵがその時点で必要とする正確なデータだけでなく、その記憶構造からメモリのチャンク（隣接している区画データなど）を取り出すという事実に起因している。その取り出されたデータのチャンクは使用される区画エントリおよび使用されない区画エントリを含んでいる可能性がある。そのデータの取り出されたチャンクはキャッシュ（例えば、ＣＰＵキャッシュ）内に記憶され、ＣＰＵは迅速に（通常、ＣＰＵが記憶構造にアクセスできるより大幅に短い時間で）アクセスすることができる。
そのスライスの処理の間に、ＣＰＵが後で特定の区画データを必要とする場合、ＣＰＵはその特定の区画データがそのキャッシュ内に存在するかどうかを判定する。何故なら、その特定の区画データが以前に取り出されたデータのチャンク内に含まれていた可能性があり、そのキャッシュに対するアクセス時間は記憶構造に対するアクセス時間より短いからである。特定の区画データがキャッシュ内に存在した場合、これは「キャッシュ・ヒット」と呼ばれ、その場合、その特定の区画データのキャッシュからの取り出しは速い。その特定の区画データがキャッシュ内に存在しなかった場合、これは「キャッシュ・ミス」と呼ばれ、その時はＣＰＵはより低速である記憶構造からその特定の区画データを取り出さなければならない。
使用されない区画エントリが使用される区画エントリと一緒に分散している偶然の方法で記憶構造内に記憶されている時、通常、そのスライスの処理時に「キャッシュ・ミス」のレートが高くなる。何故なら、その取り出された区画のチャンクは、使用される区画エントリと一緒に分散している使用されない区画エントリをも含み、その使用されない区画エントリは有用なデータを含んでいないからである。
【特許文献１】米国仮出願第６０／５８３，４４７号
【発明の開示】
【０００７】
従って、区画データのより効率的な処理を可能にする記憶構造内に区画データを編成する方法に対するニーズが存在する。
本発明のいくつかの実施形態は、記憶構造内のフレームのデータを新しい方法で編成することによって、フレームの符号化／復号化を容易にする。より詳細には、１つのフレームのスライスに対して割り当てられた記憶構造の一部分において、使用されるエントリ（有用なデータを含むエントリ）がその割り当てられた部分の第１のセクションに記憶され、そして使用されない区画エントリ（有用なデータを含んでいないエントリ）は、その割り当てられた部分の第２のセクションに記憶され、第１および第２のセクションはその記憶構造内の連続で隣接した記憶領域を含んでいる。いくつかの実施形態においては、使用される区画エントリはその記憶構造の割り当てられた部分のうちの第１のセクション内に「パック」され、一方、使用されない区画エントリはその割り当てられた部分の残りを占有する。
いくつかの実施形態においては、ビデオ・データの符号化または復号化において有用な追加のデータが判定／識別され、使用される区画エントリの使用されないバイト内に記憶される。いくつかの実施形態においては、１つのマクロブロックに対するヘッダ・データがそのマクロブロックの特定の区画エントリ（例えば、そのマクロブロックの第１の区画に対する第１の区画エントリ）に記憶される。これらの実施形態においては、そのヘッダ・データは区画エントリの区画データと統合化されている。いくつかの実施形態においては、カノニカルな基準フレーム・インデックス・データが計算され、使用される区画エントリの使用されないバイト内に記憶される。いくつかの実施形態は、１つのマクロブロックの区画が比較されてそのマクロブロックの任意の区画が同じであるかどうかが判定され、それにより同一の区画はそのマクロブロックの１つの区画内に一体化される。
【０００８】
（図面の簡単な説明）
図１は、１つのマクロブロックをＨ．２６４圧縮規格で区画化することができる異なる方法を示す。
図２は、基準フレーム・インデックスおよび基準フレーム・リストの概念を示す。
図３は、１つのフレームのスライスに対する区画データを含む従来の記憶構造の概念図を示す。
図４は、記憶構造内に記憶されている従来のヘッダの概念図を示す。
図５は、１つのフレームの復号化時に区画データを記憶するデータ構造の区画エントリの組成を示す。
図６は、１つのフレームのスライスに対する区画データを含む記憶構造の概念図を示し、その区画データは本発明による記憶構造内に編成されている。
図７は、図６に示されている記憶構造の割り当てられた部分に関連付けられているロケータ・リストの概念図を示す。
図８は、１つのビデオ・フレームのスライスに対するデータを記憶するための方法のフローチャートである。
図９は、エントリの６個の使用されていないバイト内に有用なデータを含む区画エントリの組成を示す。
図１０は、Ｈ．２６４規格に対するルックアップ・テーブルを示す。
図１１は、１つのフレームのスライスに対する区画データを含む記憶構造の概念図を示し、ここでヘッダ・データが区画エントリ内に統合化されている。
図１２は、統合化されたヘッダを使用したビデオ・フレームのスライスに対するデータを記憶するための方法のフローチャートである。
図１３は、カノニカルな基準フレーム・リストの一例を示す。
図１４は、カノニカルな基準フレーム・インデックスを使用して一連のフレーム内の１つのフレームのスライスの組に対するデータを記憶するための方法のフローチャートである。
図１５Ａは、一体化された区画の例を示す。
図１５Ｂは、一体化された区画の例を示す。
図１６は、マクロブロックの区画を一体化するための方法のフローチャートである。
図１７は、本発明のいくつかの実施形態が実施されているコンピュータ・システムを表している。
【発明を実施するための最良の形態】
【０００９】
２００４年６月２７日出願の「画像の符号化および復号化」（Ｅｎｃｏｄｉｎｇ  ａｎｄ  Ｄｅｃｏｄｉｎｇ  Ｉｍａｇｅｓ）という名称の米国仮出願第６０／５８３，４４７号の内容は、参照により本明細書に明示的に組み込むものとする。
本発明の以下の詳細な説明において、本発明の種々の詳細、例および実施形態が説明され記載される。しかし、本発明はその説明されている実施形態に限定されるものではないこと、本発明は説明されている特定の詳細および例のいくつかなしで実施できることは、当業者であれば明らかであろう。
区画エントリ：
いくつかの実施形態においては、１つの区画に対する区画エントリはその区画の復号化を早めるために所定の長さを有するように整合されている。整合の問題のために、データは、通常、複数の特定個数のバイトに分割される。これらの実施形態においては、各区画エントリは同じ所定の個数のバイトとなるように整合される。
【００１０】
図５は、１つのフレームの復号化時に区画データを記憶するデータ構造における区画エントリ５００の組成を示す。各区画エントリは１つの区画に対するデータ（すなわち、運動ベクトルおよび基準フレーム・インデックス・データ）を含んでいる。図５に示されている例においては、１つの区画エントリの長さは１６バイトである。図に示すように、第１の運動ベクトル５０５は４バイトのデータを含み、また、第２の運動ベクトル５１０に対するデータはその区画エントリ内に２バイトのデータ（１つの運動ベクトルの各ｘまたはｙ成分に対して２バイト）を含む。第１の基準フレーム・インデックス５１５に対するデータは１バイトを含み、そして第２の基準フレーム・インデックス５２０に対するデータもその区画エントリ内に１バイトのデータを含む。図５の例に示すように、区画エントリは１６バイトであり、区画エントリは１０個の使用されるバイトを含み、ここでそのエントリの６個のバイト５２５は、通常、空であって使用されない（すなわち、意味のある、または有用なデータを含まない）。
【００１１】
符号化／復号化時の記憶装置の効率的使用法：
いくつかの実施形態においては、フレームのスライスの符号化／復号化を容易にするために、使用される区画エントリが使用されない区画エントリと一緒に分散化されないように、そのスライスのデータが記憶構造内で編成される。より詳細には、そのスライスに対して割り当てられた記憶構造の一部において、使用される区画エントリがその割り当てられた部分の第１のセクションに記憶され、そして使用されない区画エントリがその割り当てられた部分の第２のセクションに記憶され、第１および第２のセクションはそれぞれその記憶構造内の記憶の連続で隣接した領域を含んでいる。いくつかの実施形態においては、使用される区画エントリは記憶構造の割り当てられた部分の第１の所定のセクション内に「パックされ」、一方、使用されない区画エントリはその割り当てられた部分の残りを占める。
記憶構造の割り当てられた部分には、その割り当てられた部分に含まれる区画エントリに対するインデックスのリストであるロケータ・リストが関連付けられている。より詳細には、ロケータ・リストは割り当てられた部分の区画エントリのロケーション情報（例えば、アドレス情報）を含んでいるインデックス（例えば、ポインタ）のリストを含む。ロケータ・リストは割り当てられた部分の特定のマクロブロックの特定の区画エントリを見つけるために、割り当てられた部分と結合して使用される。
いくつかの実施形態においては、各マクロブロックに対するヘッダ・データは、使用される区画エントリが記憶されている割り当てられた部分の第１のセクションに記憶される。いくつかの実施形態においては、マクロブロックに対するヘッダ・データは第１のセクションに記憶されるが、そのマクロブロックのどの区画エントリからも分かれて記憶される。他の実施形態においては、マクロブロックに対するヘッダ・データはそのマクロブロックの特定の区画エントリ（例えば、そのマクロブロックの第１区画に対する最初の区画エントリ）内に記憶される。これらの実施形態においては、そのヘッダ・データは区画エントリの区画データと統合化されている。
【００１２】
図６は、１つのフレームのスライスに対する区画データを含み、その区画データが本発明に従って記憶構造内で編成されている記憶構造６０５の概念図を示す。図６の例においては、そのスライスは図３の例の場合と同様に同じ３つのマクロブロックから構成されており、ここで第１のマクロブロック（マクロブロック０）は１個の区画から構成され、第２のマクロブロック（マクロブロック１）は１６個の区画から構成され、第３のマクロブロック（マクロブロック２）は２個の区画から構成されている。
そのスライスに対して割り当てられる記憶部分６１０のサイズはそのスライスの各マクロブロックに対して、１つのヘッダおよび１６個の区画エントリ（ここで各区画エントリは１６バイトのデータを含む）に対して十分な記憶空間が割り当てられているように「最悪ケースのシナリオ」に基づいて決定される。従って、マクロブロック０の場合、１つの使用されている区画エントリ（区画エントリ０）と１５個の使用されていない区画エントリ（区画エントリ１〜１５）があり、マクロブロック１に対しては、１６個の使用されている区画エントリがあり、マクロブロック２に対しては、２個の使用されている区画エントリと１４個の使用されていない区画エントリとがある。
図６に示すように、そのスライスのすべてのマクロブロックの使用されている区画エントリはその記憶構造の割り当てられている部分の第１のセクション６３０に対して記憶され（「パックされ」）、一方、使用されない区画エントリがその割り当てられた部分の第２のセクション６３５（その割り当てられた部分の残り）に対して記憶されている。マクロブロック０の場合、そのヘッダ・データおよび使用される区画エントリ０がマクロブロック０に対する第１の「使用される」セクション６３０の部分分割６１５内にある。マクロブロック０に対する使用されない区画エントリ１〜１５は、その割り当てられた部分の第２の「使用されない」セクション６３５内にある。マクロブロック１の場合、そのヘッダ・データおよび使用される区画エントリ０〜１５がマクロブロック１に対する第１の「使用される」セクション６３０の部分分割６２０内にある。マクロブロック２の場合、そのヘッダ・データおよび使用される区画エントリ０〜１がマクロブロック２に対する第１の「使用される」セクション６３０の部分分割６２５内にある。マクロブロック２に対する使用されない区画エントリ２〜１５は、その割り当てられた部分の第２の「使用されない」セクション６３５内にある。これは、記憶装置３０５の割り当てられた部分３１０全体を通じて使用される区画エントリと使用されない区画エントリとが分散している図３と対照的である。
そのような方法で区画データを編成することによって、キャッシュ・ミスの発生が少なくなるので、そのスライスの復号化をより効率的に行うことができる。ＣＰＵがその割り当てられた部分の第１のセクションから区画データのチャンクを取り出す時、区画データの各チャンクは使用される区画エントリの全体またはそのほとんどから構成されることになる。何故なら、使用される区画エントリが第１のセクション内にパックされており、そして使用されない区画エントリが第２の別のセクション内にパックされているからである。これにより、キャッシュ・ミスがより少なくなる。何故なら、使用されている区画エントリからの意味のある／有用なデータの大部分をそのキャッシュが含んでいることになるからである。
【００１３】
図７は、図６に示されている記憶構造６０５の割り当てられた部分６１０と関連付けられているロケータ・リスト７０５の画面図を示す。このロケータ・リストは割り当てられた部分で区画エントリを見つけるのに役立てるために使用されるロケーション情報（例えば、アドレス情報）を含んでいるインデックス（例えば、ポインタ）のリストである。ロケータ・リストは割り当てられた部分と結合して使用され、その割り当てられた部分の特定のマクロブロックの特定の区画エントリを見つけるのを助ける。
いくつかの実施形態においては、１つのマクロブロックに対する１つのインデックスだけがロケータ・リスト７０５内に記憶されている。いくつかの実施形態においては、１つのマクロブロックの第１の区画に対する第１の区画エントリだけに対するインデックスがロケータ・リスト７０５内に記憶されている。これらの実施形態においては、そのリスト内のインデックスはそのスライス内のマクロブロック番号および、記憶構造６０５の割り当てられた部分６１０内のマクロブロックに対する第１の区画エントリのロケーション情報を識別する。例えば、図７に示すように、マクロブロック０に対するインデックスは割り当てられた部分６１０内のマクロブロック０に対する第１の区画エントリのロケーション情報を含んでいる。
【００１４】
図８は、ビデオ・フレームのスライスに対するデータを記憶するための方法８００のフローチャートである。方法８００は、例えば、データ記憶構造を使用してビデオ・データ・ストリームを符号化または復号化するように構成されているアプリケーションによって実行することができる。
方法８００はビデオ・フレームのスライスに対するデータを受信する（８０５において）ことから開始し、そのスライスは２つ以上のマクロブロックを含み、各マクロブロックは１つまたは複数の区画を含む。そのスライスに対するデータはそのスライスのマクロブロックの区画に関連付けられた区画データ（例えば、運動ベクトルおよび基準フレーム・インデックス・データ）および、各マクロブロックに対するヘッダ・データを含む。オプションのステップとして、各マクロブロックに対して、その方法はマクロブロックの区画を比較し（８０７において）、同じ区画があればそれらをすべて一体化する（８０７において）（以下に説明されるように）。
次に、方法８００はスライスのデータを記憶するために記憶装置の一部を割り当て（８１０において）、その割り当てられた記憶の部分は区画エントリおよびマクロブロック・ヘッダに対して割り当てられた記憶部分を含んでいる。いくつかの実施形態においては、その割り当てられた記憶部分のサイズはそのスライスの各マクロブロックに対して割り当てられる区画エントリの所定の個数に従って決定される。いくつかの実施形態においては、割り当てられる記憶の部分のサイズは「最悪ケースのシナリオ」に基づいて決定され、そのスライスの各マクロブロックに対して、そのマクロブロック・ヘッダおよび１６個の区画エントリに対して十分な記憶空間が割り当てられている。
次に、その方法はそのスライスの区画に関連付けられた区画データをその割り当てられた区画エントリ（使用される区画エントリと呼ばれる）内に記憶する（８１２において）。オプションのステップとして、その方法は追加の有用な／意味のあるデータを、使用される区画エントリの使用されないバイト内に記憶する（８１３において）（以下に説明されるように）。いくつかの実施形態においては、その方法は統合化されたヘッダのデータまたはカノニカルな基準フレーム・インデックス・データを、使用される区画エントリ内に記憶する（８１３において）。いくつかの実施形態においては、その方法はその区画の符号化または復号化において有用である任意の他のデータを計算／識別して記憶する。
次に、方法８００は割り当てられた記憶部分の第１のセクション内に各マクロブロックに対するヘッダ・データを記憶する（８１５において）。また、方法８００は使用される区画エントリを、割り当てられた記憶部分の第１のセクションに記憶／配置し（８１７において）、使用される区画エントリはそのスライスのマクロブロックの区画に対するデータを含んでいる。また、方法８００は使用されない区画エントリ（１つの区画のデータを含んでいないエントリ）を、割り当てられた記憶部分の第２のセクションに記憶／配置する（８２０において）。いくつかの実施形態においては、第１および第２のセクションはそれぞれ割り当てられた記憶部分の連続した記憶の領域を含み、それにより、使用される区画エントリがその割り当てられた記憶部分で使用されない区画エントリと一緒に分散化されない。
次に、方法８００は割り当てられた記憶部分に関連付けられるロケータ・リストを生成し（８２５において）、そのロケータ・リストは割り当てられた部分の区画エントリに対するロケーション情報（例えば、アドレス情報）を含んでいるインデックス（例えば、ポインタ）のリストを含んでいる。ロケータ・リストは割り当てられた部分の特定のマクロブロックの特定の区画エントリを見つけるのを助けるために使用される。いくつかの実施形態においては、マクロブロックの第１の区画に対する第１のエントリだけに対するインデックスがロケータ・リスト内に記憶される。ここでこの方法は終了する。
【００１５】
区画エントリ内の使用されないバイトの使用法：
統合化されたヘッダ
図６に示すように、各マクロブロックに対して、１つのマクロブロック・ヘッダ・データがあり、それも、使用されている区画エントリが記憶される場所の割り当てられた部分の第１のセクション内に記憶される。いくつかの実施形態においては、マクロブロックに対するヘッダ・データは第１のセクションに記憶されるが、そのマクロブロックのどの区画エントリからも離れて記憶される。他の実施形態においては、マクロブロックに対するヘッダ・データはそのマクロブロックの特定の区画エントリ内に記憶される。これらの実施形態においては、ヘッダ・データは区画エントリの区画データと統合化されている。
図５の例に示すように、区画エントリの長さは１６バイトになる可能性がある。図５に示すように、区画データ（運動ベクトルおよび基準フレーム・インデックス・データ）は区画エントリの１０バイトの５０５〜５２０を含み、その区画エントリの残りの６バイト５２５は使用されないままになっている。図９は、本発明による区画エントリ９００の組成を示し、ここで区画エントリ９００はそのエントリの６個の使用されないバイト５２５内に有用なデータを含んでいる。
いくつかの実施形態においては、マクロブロックに対するヘッダ・データはそのマクロブロックの特定の区画エントリの使用されないバイト内に記憶される。いくつかの実施形態においては、そのマクロブロックのヘッダ・データはそのマクロブロックの第１の区画に対する第１の区画エントリ内にだけ統合化される。いくつかの実施形態においては、統合化されたヘッダ・データ９３０は区画エントリ９００の使用されないバイト５２５のうちの２バイトを含む。
統合化されたヘッダ・データ９３０は区画構成ルックアップ・テーブルと結合して使用され、そのマクロブロックの一意の区画構成を識別する。上記のように、Ｈ．２６４規格の下では、マクロブロックを２５９種類の可能な区画構成内に区画化することができる。これらの実施形態においては、その２５９種類の可能な区画構成のそれぞれと、各区画構成に関連付けられた一意の識別子（０〜２５８の範囲の）を含んでいるルックアップ・テーブルが生成される。Ｈ．２６４規格に対するルックアップ・テーブル１００５の一例が図１０に示されている。これらの実施形態においては、各マクロブロックに対して、統合化されたヘッダ・データはそのマクロブロックの区画構成を示すルックアップ・テーブル内の特定の区画構成を識別する（ここで、統合化されたヘッダ・データの値が特定の区画構成に関連付けられた一意の識別子に対してマッチされる）。
マクロブロックに対する従来のヘッダは、そのマクロブロックがどのように区画化されているかについての記述データを含み、例えば、そのマクロブロックに対してマクロブロック内の各区画の位置および寸法のデータを含んでいることを思い出されたい。この従来の記述データはマクロブロックの一意の区画構成から導くことができる。何故なら、区画構成がそのマクロブロックに対してマクロブロック内の各区画の位置および寸法を示すことになるからである。従って、そのマクロブロックの一意の区画構成が一度決定されると、ヘッダ内に通常含まれているその記述データも決定することができる。
統合化されたヘッダ・データを使用して記憶の消費が削減される。何故なら、統合化されたヘッダ・データは区画エントリの使用されていない部分に記憶され、従来のヘッダに対する別の記憶空間が不要となるからである。図１１は、１つのフレームの１つのスライスに対する区画データを含んでいる記憶構造の概念図を示し、ここでヘッダ・データは区画エントリ内に統合化されている。図３および図６に対して比較して、各マクロブロックに対する別々のヘッダ・セクションは不要となっていることに留意されたい。
【００１６】
図１２は、統合化されたヘッダを使用してビデオ・フレームのスライスに対するデータを記憶するための方法１２００のフローチャートである。方法１２００は、例えば、データ記憶構造を使用してビデオ・データ・ストリームを符号化または復号化するために構成されるアプリケーションによって実行することができる。
方法１２００は、ビデオ・フレームのスライスに対するデータを受信する（１２０５において）ことから開始され、そのスライスは２つ以上のマクロブロックを含み、各マクロブロックは１つまたは複数の区画を含む。スライスに対するデータはそのスライスのマクロブロックの区画に関連付けられた区画データ（例えば、運動ベクトルおよび基準フレーム・インデックス・データ）と、そのマクロブロックがどのように区画化されているかを記述しているデータ（例えば、そのマクロブロック内の各区画の位置および寸法のデータ）を含む各マクロブロックに対するヘッダ・データとを含む。
次に、方法１２００は１つのマクロブロックの可能な各区画構成を含んでいる区画構成ルックアップ・テーブルを生成または受信し（１２０６において）、可能な各区画構成は一意の識別子（例えば、数値的識別子）に関連付けられている。スライスの各マクロブロックに対して、次に、方法１２００はそのマクロブロックの区画構成にマッチする特定の区画構成をそのルックアップ・テーブル内で識別する（１２０７において）。次に、方法１２００は、ルックアップ・テーブルからその識別された区画構成に関連付けられた一意の識別子を決定する（１２０８において）。その関連付けられた一意の識別子は、ここではマクロブロックに対する統合化されたヘッダ・データと呼ばれる。その方法はそのマクロブロックがどのように区画化されているかを記述しているデータを含んでいるマクロブロックに対する受信されたヘッダ・データを使用して、そのマクロブロックの特定の区画構成を識別する（１２０７において）ことができる。従って、１つのマクロブロックに対する統合化されたヘッダ・データはそのマクロブロックに対する元の受信されたヘッダ・データから導かれる（ステップ１２０７および１２０８において）。
次に、方法１２００はそのスライスのデータを記憶するために記憶構造の一部を割り当てる（１２１０において）。いくつかの実施形態においては、割り当てられる記憶部分のサイズはそのスライスのマクロブロックのヘッダ・データに対する別の記憶セクションを考慮せずに決定される。これらの実施形態においては、所定の数の区画エントリがそのスライスの各マクロブロックに対して割り当てられ、一方、各マクロブロックのヘッダ・データに対しては別の記憶セクションは割り当てられない（図１１に図示）。
次に、その方法は割り当てられた区画エントリ（使用される区画エントリと呼ばれる）内に、そのスライスの区画に関連付けられた区画データを記憶する（１２１２において）。次に方法１２００は各マクロブロックに対する統合化されたヘッダ・データ（ステップ１２０８において決定された）を、そのマクロブロックの１つの区画に対して使用される区画エントリ内に記憶する（１２１５において）。その方法はそのマクロブロックの区画エントリの任意の使用されないバイト内に統合化されたヘッダ・データを記憶することによってそれを行うことができる。いくつかの実施形態においては、マクロブロックに対する統合化されたヘッダ・データはそのマクロブロックの第１の区画に対する第１の使用される区画エントリの中だけに記憶される。いくつかの実施形態においては、統合化されたヘッダ・データは使用される区画エントリのうちの２バイトの使用されないバイトを含む。
いくつかの実施形態においては、次に方法１２００は、使用される区画エントリを、割り当てられた記憶部分の第１のセクションに記憶／配置する（１２１７において）。いくつかの実施形態においては、方法１２００はまた、割り当てられた記憶部分の第２のセクション内に使用されない区画エントリ（区画のデータを含んでいないエントリ）を記憶／配置する（１２２０において）。いくつかの実施形態においては、次に方法１２００は割り当てられた記憶部分に関連付けられているロケータ・リストを生成し（１２２５において）、そのロケータ・リストは割り当てられた部分の区画エントリに対するロケーション情報を含んでいるインデックスのリストを含んでいる。ここでこの方法は終了する。
【００１７】
カノニカルな基準フレーム・インデックス
いくつかの実施形態においては、カノニカルな基準フレーム・インデックスが計算され、各区画エントリの使用されないバイト内に記憶される。これらの実施形態においては、１つの区画エントリ内の第１および第２の基準フレーム・インデックスがそれぞれカノニカルな基準フレーム・インデックスに対してマップされる。
図２に関連して上で説明されたように、運動ベクトルに関連付けられた基準フレーム・インデックスは、その運動ベクトルがベースとしているフレームを識別する基準フレーム・リスト内の１つのエントリ（フレーム番号を含む）を指定する。第１および第２の基準フレーム・リストは１つのフレームの各スライスごとに変化する可能性があるので、異なるマクロブロックの異なる区画エントリ内で値が同じである基準フレーム・インデックスが同じフレームを指すかどうかを確信を持って決定することができない。例えば、２つの異なるマクロブロック内の２つの区画エントリはその第１の運動ベクトルに関連付けられている「２」の基準フレーム・インデックスをそれぞれ有している可能性がある。しかし、これは両方の第１の運動ベクトルが同じフレームをベースにしていることを示さない。
これにより、復号化のプロセスのデブロッキング・フィルタ段において効率が悪くなる。デブロッキング・フィルタ段においては、２つの時間的に隣接したマクロブロックの２つの区画に対して、その区画の第１および第２の運動ベクトルの値が同じである（または所定の変動範囲内にある）かどうか、および、その第１および第２の運動ベクトルが同じフレームをベースとしているかどうかが判定される。そうであった場合、これはその区画の運動が同じであり（あるいはほぼ同じであり）、それにより次に異なるフィルタリング・プロセス（例えば、より弱いフィルタリング・プロセス）が適用されることを示す。
通常、２つの区画の第１および第２の運動ベクトルが同じフレームをベースとしているかどうかを判定するために非効率的なプロセスが使用されている。このプロセスは各区画に対して、その運動ベクトルに関連付けられている基準フレーム・インデックスの取り出しと、基準フレーム・リストの取り出しと、基準フレーム・インデックスによって指定された基準フレーム・リスト内のフレーム番号の決定とを必要とする。次にこのプロセスはそのフレームが同じであるかどうかを判定するためにフレームの番号の比較を必要とする。
いくつかの実施形態においては、カノニカルな基準フレーム・リストが１つのフレームのすべてのスライスまたは一連のフレームのすべてのフレームに対して生成され、記憶され、使用される。いくつかの実施形態においては、そのカノニカルな基準フレーム・リストは復号化プロセスの間には変更されない。図１３は、カノニカルな基準フレーム・リストの一例を示す。
いくつかの実施形態においては、１つの区画エントリ内の基準フレーム・インデックスがカノニカルな基準フレーム・インデックスに対してマップされている。これらの実施形態においては、基準フレーム・インデックスはその基準フレーム・インデックスによって指示されたフレーム番号を決定するために関連付けられた基準フレーム・リストと結合して使用される。次に、マッチしているフレーム番号が、そのマッチしているフレーム番号を含んでいるカノニカルな基準フレーム内のエントリ番号（カノニカルな基準フレーム・インデックス）を決定するためにカノニカルな基準フレーム・リスト内に置かれる。次に、その決定されたカノニカルな基準フレーム・インデックスがその区画エントリの使用されないバイト内に記憶される。図９に示されている例においては、カノニカルな基準フレーム・インデックス９３５に対するデータは使用されないバイト５２５のうちの２つのバイトを含む。
【００１８】
次は、図１３に示されているカノニカルな基準フレーム・リストと図２の第１および第２の基準フレーム・リストを使用したマッピング・プロセスの一例である。第１の基準フレーム・インデックス「２」と第２の基準フレーム・インデックス「０」とが１つの区画エントリ内に含まれていると仮定する。基準フレーム・インデックス「２」に関連付けられている第１の基準フレーム・リストはフレーム番号２、１、および０をエントリ番号０、１、および２においてそれぞれ含んでいる。従って、基準フレーム・インデックス「２」はフレーム番号０を示す。カノニカルな基準フレーム・リストにおいては、フレーム番号０がエントリ０内のフレーム番号にマッチする。従って、基準フレーム・インデックス２がカノニカルな基準フレーム・インデックス０に対してマップされる。同様に、第２の基準フレーム・インデックス「０」に関連付けられている第２の基準フレーム・リストは、フレーム番号４、５、および６をエントリ番号０、１、および２においてそれぞれ含んでいる。従って、第２の基準フレーム・インデックス「０」はフレーム番号４を示す。カノニカルな基準フレーム・リストにおいては、フレーム番号４はエントリ３内のフレーム番号にマッチする。従って、第２の基準フレーム・インデックス０はカノニカルな基準フレーム・インデックス３に対してマップされる。
いくつかの実施形態においては、１つのカノニカルな基準フレーム・リストが生成されて記憶される。他の実施形態においては、第１の運動ベクトルに対する特定のフレームを識別するために使用される第１のカノニカルな基準フレーム・リストと、第２の運動ベクトルに対する特定のフレームを識別するために使用される第２のカノニカルな基準フレーム・リストとが生成されて記憶される。
これらの実施形態においては、カノニカルな基準フレーム・リストを生成すること、およびカノニカルな基準フレーム・インデックスに対して基準フレーム・インデックスをマップすることの追加のオーバヘッドがある。しかし、これらの動作が一度実行されると、２つの区画の運動ベクトルが同じフレームをベースとしているかどうかを判定するためのプロセスは時間が節約される。これらの実施形態においては、この判定を実行するために、区画のカノニカルな基準フレーム・インデックスだけを取り出して比較すればよい。また、フレーム番号の実際の値は必要ではないので、カノニカルな基準フレーム・インデックスによって示されるフレーム番号が決定される必要はない。これは、カノニカルな基準フレーム・インデックスが同じカノニカルな基準フレーム・リストを示していて、カノニカルな基準フレーム・インデックスの値は同じであり、従って、同じフレーム番号を指定しているということによる。
【００１９】
図１４は、カノニカルな基準フレーム・インデックスを使用して一連のフレーム内の１つのフレームの一組のスライスに対するデータを記憶するための方法１４００のフローチャートである。方法１４００は、例えば、データ記憶構造を使用してビデオ・データ・ストリームを符号化または復号化するために構成されているアプリケーションによって実行することができる。
方法１４００はビデオ・フレームの１つまたは複数のスライスの組に対するデータを受信する（１４０５において）ことから始まり、各スライスは２つ以上のマクロブロックを含み、各マクロブロックは１つまたは複数の区画を含む。そのスライスの組に対するデータは、各スライスに対するヘッダ・データ（１つまたは複数の元の基準フレーム・リストに対するデータを含む）と、そのマクロブロックの区画に関連付けられている区画データ（運動ベクトルおよび元の基準フレーム・インデックス・データ）と、各マクロブロックに対するヘッダ・データとを含む。いくつかの実施形態においては、１つの区画に対する運動ベクトルおよび元の基準フレーム・インデックス・データは、第１および第２の運動ベクトルと、関連付けられている第１および第２の元の基準フレーム・インデックスに対するデータを含む。第１の元の基準フレーム・インデックスは関連付けられている第２の元の基準フレーム・リスト（その区画が含まれているスライスのヘッダ・データから導くことができる）内で１つのエントリ（フレーム番号を含む）を指定し、それはその一連のフレームでその第１の運動ベクトルのベースとなっている特定のフレームを示す。同様に、第２の元の基準フレーム・インデックスは関連付けられている第２の元の基準フレーム・リスト（その区画が含まれているスライスのヘッダ・データから導くことができる）内で１つのエントリを指定し、それはその第２の運動ベクトルがベースとしている一連のフレーム内の特定のフレームを示す。
【００２０】
次に、その方法はそのスライスの組のうちのすべてのスライスに対して使用されるカノニカルな基準フレーム・リストを生成または取り出す（１４０６において）。カノニカルな基準フレーム・リストはカノニカルな基準フレーム・インデックス（エントリ番号）のリストとフレーム番号のリストとを含み、各フレーム番号は特定のカノニカルな基準フレーム・インデックスに対応している。いくつかの実施形態においては、第１および第２の元の基準フレーム・インデックスをマップするために１つのカノニカルな基準フレーム・リストが生成される（以下に説明されるように）。他の実施形態においては、第１および第２のカノニカルな基準フレーム・リストが、第１および第２の元の基準フレーム・インデックスをそれぞれマップするために生成される。
受信したスライスの組の中の１つのマクロブロックの各区画に対して、方法１４００は元の基準フレーム・リストおよびカノニカルな基準フレーム・リストを使用して、第１および第２のカノニカルな基準フレーム・インデックスに対して、その区画に関連付けられている第１および第２の元の基準フレーム・インデックスをマップする（１４０７において）。その方法は、その区画に関連付けられている元の基準フレーム・リスト内の元の基準フレーム・インデックスによって示されているフレーム番号を決定し、カノニカルな基準フレーム・リスト内のフレーム番号をマッチし、そのマッチしているフレーム番号に対応しているカノニカルな基準フレーム・インデックスを決定することによって示されるフレーム番号を決定することにより、そのことを行うことができる。従って、第１および第２のカノニカルな基準フレーム・インデックスは、その区画に関連付けられている第１および第２の運動ベクトルがそれぞれベースとしているフレームを示す。
区画の元の基準フレーム・インデックスをカノニカルな基準フレーム・インデックスに対してマップするために同じカノニカルな基準フレーム・リストが使用されることに留意されたい。これは元の基準フレーム・インデックスが異なる元の基準フレーム・リストをベースとしている場合であっても（例えば、元の基準フレーム・インデックスに関連付けられている区画が、受信したスライスの組の中の異なるスライス内にある時であっても）成立する。結果として、関連付けられているカノニカルな基準フレーム・インデックスが同じである組の中のどのスライス内のどの区画も、その区画が異なるスライス内に含まれている場合であっても、一連のフレーム内の同じフレームを参照し、指示する。上記のように、カノニカルな基準フレーム・インデックスのこの特性は区画のそれ以降の処理において利点を提供することができる。
【００２１】
スライスの組のうちの各スライスに対して、方法１４００は次にそのスライスのデータを記憶するための記憶構造の特定の部分を割り当てる（１４１０において）。これらの実施形態においては、各スライスの各マクロブロックに対して所定の数の区画エントリが割り当てられる。次にその方法はそのスライスの区画に関連付けられている区画データをその割り当てられた区画エントリ（使用される区画エントリと呼ばれる）内に記憶する（１４１２において）。
受信したスライスの組の中の各区画に対して、方法１４００は次にその区画に関連付けられている第１および第２のカノニカルな基準フレーム・インデックスをその区画に対して使用される区画エントリ内に記憶する（１４１５において）。その方法は、第１および第２のカノニカルな基準フレーム・インデックスに対するデータをその区画に対する区画エントリの使用されないバイトのどれか内に記憶することによって行うことができる。いくつかの実施形態においては、第１および第２のカノニカルな基準フレーム・インデックスに対するデータは、使用される区画エントリの使用されないバイトのうちの２バイトを含む。
いくつかの実施形態においては、各スライス（複数の区画を含む）に対して、その方法１４００はまた使用される区画エントリ（そのスライス内の区画に対するデータを含む）をそのスライスに対して割り当てられた記憶部分の第１のセクション内に記憶／配置する（１４１７において）。いくつかの実施形態においては、各スライスに対して、方法１４００はまた、使用されない区画エントリ（１つの区画のデータを含んでいないエントリ）をそのスライスに対して割り当てられた記憶部分の第２のセクション内に記憶／配置する（１４２０において）。いくつかの実施形態においては、各スライスに対して、方法１４００はそのスライスに対して割り当てられている記憶部分に関連付けられているロケータ・リストを生成し（１４２５において）、ロケータ・リストは割り当てられた部分の区画エントリに対するロケーション情報を含んでいるインデックスのリストを含んでいる。ここでこの方法は終了する。
【００２２】
区画エントリ内の使用されないバイトの他の使用法
上記のように、１つの区画エントリは６個の使用されないバイトを含んでいる。いくつかの実施形態においては、統合化されたヘッダ・データ９３０が１つのマクロブロックの第１区画の使用されないバイト内に記憶される。いくつかの実施形態においては、カノニカルな基準フレーム・インデックス９３５が計算され、各区画エントリの使用されないバイト内に記憶される。
他の実施形態においては、区画エントリ内の使用されないバイトはその区画の符号化または復号化をより効率的にすることができる任意の目的のために使用される。いくつかの実施形態においては、区画エントリの使用されないバイトはその区画の符号化または復号化を容易にする、識別された、あるいは計算されたデータを記憶するために使用される。例えば、マクロブロックのいくつかの区画を計算し、そのマクロブロックの第１の区画の使用されないバイト内に記憶することができる。これにより、復号化時に区画の番号を後で計算する必要がなくなる。図９に示されている例においては、いくつかの区画９４０に対するデータは使用されないバイトのうちの１バイトを含む。
図９に示されている例においては、使用されるバイト５２５内のデータ（統合化されたヘッダ・データ９３０およびカノニカルな基準フレーム・インデックス９３５に対するデータなど）が区画エントリ９００内で特定の順序で示されている。しかし、この分野の技術に熟達した人であれば、他の順序のデータも可能であること理解することができるだろう。
【００２３】
区画の一体化：
いくつかの実施形態においては、同じマクロブロックのいくつかの、あるいはすべての区画が同じ運動ベクトルおよび同じ基準フレーム・インデックスを備えている時（同一区画と呼ばれる）、その同一区画は復号化の目的のために１つの区画にまとめられる（一体化される）。この状況においては、そのマクロブロックに対して複数の区画エントリではなく、１つの区画エントリだけを保存すれば済み、従って、記憶装置のオーバヘッドが減少する。
図１５Ａは同じマクロブロックの４つの区画すべてが同じ運動ベクトルおよび基準フレーム・インデックスを有している時の一例を示し、その４つの区画は復号化の目的のために１つの区画に一体化される。従って、このマクロブロックに対しては４つの区画エントリでなく、１つの区画エントリだけを保存するだけで済む。図１５Ｂは同じマクロブロックの５個の区画のうちの２つが同じ運動ベクトルおよび基準フレーム・インデックスを有している時の例を示し、その２つの同じ区画がマクロブロックの左上側に置かれている。図１５Ｂに示すように、その２つの同一区画は１つの区画に一体化され、５個の区画エントリではなく４個の区画エントリだけをそのマクロブロックに対して保存すればよいようになる。
【００２４】
いくつかの実施形態においては、その一体化の方法は本発明の区画エントリのパッキング法（図６に関連して上述した）と結合して使用される。これらの実施形態においては、マクロブロックの使用される区画エントリが記憶構造の割り当てられた部分の第１セクション内にパックされる前に、そのマクロブロックの区画がチエックされてそのマクロブロック内に同一区画があるかどうかが判定される。同一区画があった場合、そのマクロブロックの同一区画は１つの区画内にまとめられ、そしてその同一区画に対する１つの区画が、割り当てられた部分の第１セクションに対して記憶される。
同じマクロブロックの区画が同じ第１および第２の運動ベクトルと、同じ第１および第２の基準フレーム・インデックスとを有している時、その同一区画を１つの区画として扱うことがより効率的である。運動ベクトルと基準フレーム・インデックスとの比較を実行するための最初の時間的オーバヘッドはあるが、同一区画が１つの区画として一体化されると、すべての復号化段をより高速に実行することができ、いくつかのより小さい区画におけるいくつかの操作を行うのではなく、１つのより大きい一体化された区画について１つの操作を実行すればよいことになる。これは時間的により効率的である。何故なら、その一体化された区画について実行されるすべての復号化機能に対して、１回のローディング操作だけ、および復号化機能に対する１回の呼出しだけで済み、複数のローディング操作および復号化機能に対する複数の呼出しは不要であるからである。
同じマクロブロックの区画は同じ基準フレーム・リストを使用することに留意されたい。何故なら、同じ基準フレーム・リストが同じスライスのすべてのマクロブロックに対して使用されるからである。従って、基準フレーム・インデックスによって指定される実際のフレーム番号を求めて比較する必要はない。何故なら、その基準フレーム・インデックスが同じ基準フレーム・リストと結合して使用されるからである。
【００２５】
図１６は、ビデオ・スライスのマクロブロックの区画を一体化するための方法１６００のフローチャートである。いくつかの実施形態においては、方法１６００は図８に関連して説明されている方法８００のステップ８０７を含む。図８の方法８００においては、方法８００はビデオ・フレームの１つのスライスに対するデータを受信し（８０５において）、そのスライスは２つ以上のマクロブロックを含み、各マクロブロックは１つまたは複数の区画を含む。そのスライスに対するデータはそのスライスのマクロブロックの区画に関連付けられた区画データ（例えば、運動ベクトルおよび基準フレーム・インデックス・データ）と、各マクロブロックに対するヘッダ・データとを含む。
方法１６００は受信したスライス内の最初のマクロブロックを現在マクロブロックとして設定することから開始する。次に方法１６００は区画に関連付けられている区画データ（１６０５において）（運動ベクトルおよび基準フレーム・インデックス・データ）を比較することによって現在マクロブロックのすべての区画を比較する（１６１０において）。次にその方法は現在マクロブロックの区画のどれかが同一であるかどうか（すなわち、区画のどれかに関連付けられている運動ベクトルおよび基準フレーム・インデックスが同じであるかどうか）を判定する（１６１５において）。その場合、その方法は現在マクロブロックの同一区画を１つの区画に一体化し（１６２０において）、ステップ１６２５へ進む。そうでなかった場合、その方法は直接にステップ１６２５へ進む。
ステップ１６２５において、その方法は現在マクロブロックがそのスライス内の最後のマクロブロックであるかどうかを判定する。そうでなかった場合、その方法は次のマクロブロックを現在マクロブロックとして設定し（１６３０において）、そしてステップ１６１０へ継続する。そうであった場合、この方法は終了する。
【００２６】
図１７は、本発明のいくつかの実施形態が実施されているコンピュータ・システム１７００を示す。コンピュータ・システム１７００はバス１７０５と、プロセッサ１７１０と、システム・メモリ１７１５と、読出し専用メモリ１７２０と、永久記憶装置１７２５と、入力装置１７３０と、出力装置１７３５とを含む。
バス１７０５は、すべてのシステム、周辺装置、およびコンピュータ・システム１７００の多数の内部装置と通信できるように接続するチップセットのバスを集合的に表す。例えば、バス１７０５は、プロセッサ１７１０を読出し専用メモリ１７２０、システム・メモリ１７１５、および永久記憶装置１７２５と通信できるように接続している。
読出し専用メモリ（ＲＯＭ）１７２０は、プロセッサ１７１０およびコンピュータ・システムの他のモジュールによって必要とされる静的データおよび命令を記憶する。他方、永久記憶装置１７２５は読出し／書込みメモリ装置である。この装置はコンピュータ・システム１７００がオフになった時でも命令およびデータを記憶する不揮発性メモリである。本発明のいくつかの実施形態は大容量記憶装置（磁気ディスクまたは光ディスクなど、およびその対応しているディスク・ドライブ）を永久記憶装置１７２５として使用する。他の実施形態は取り外し可能記憶装置（フロッピー・ディスクまたはｚｉｐ（登録商標）ディスクなど、およびその対応しているディスク・ドライブ）を永久記憶装置として使用する。
永久記憶装置１７２５と同様に、システム・メモリ１７１５は読出し／書込みメモリ装置である。しかし、記憶装置１７２５と違って、システム・メモリはランダム・アクセス・メモリ（ＲＡＭ）などの揮発性読出し／書込みメモリである。システム・メモリはプロセッサが実行時に必要とする命令およびデータのいくつかを記憶する。
【００２７】
いくつかの実施形態においては、本発明の方法を実行するために必要な命令および／またはデータがシステム・メモリ１７１５、永久記憶装置１７２５、読出し専用メモリ１７２０、またはこの３つの任意の組合せ内に記憶される。例えば、各種の記憶装置は本発明の方法に従ってビデオ・データを符号化または復号化するための命令を含み、および／またはビデオ・データを含むことができる。これらの各種の記憶装置から、プロセッサ１７１０は本発明のプロセスを実行するために実行する命令および処理するデータを取り出す。
また、バス１７０５は入力装置１７３０および出力装置１７３５に対しても接続する。入力装置１７３０によって、ユーザは情報を通信し、コンピュータ・システム１７００に対するコマンドを選択することができる。入力装置１７３０は英数字キーボードとカーソル・コントローラとを含む。出力装置１７３５はコンピュータ・システム１７００によって発生された画像を表示する。出力装置はプリンタおよび、陰極線管（ＣＲＴ）または液晶表示装置（ＬＣＤ）などの表示装置を含む。
最後に、図１７に示すように、バス１７０５はコンピュータ・システム１７００を、例えば、ネットワーク・アダプタ（図示せず）を通じてネットワーク１７６５に対して結合する。この方法で、コンピュータ・システム１７００はコンピュータのネットワーク（ローカル・エリア・ネットワーク（「ＬＡＮ」）、広域ネットワーク（「ＷＡＮ」）、またはイントラネットなど）の一部であるか、あるいはネットワークのネットワーク（インターネットなど）であることができる。コンピュータ・システム１７００の構成要素のうちの任意のもの、またはすべてを本発明と結合して使用することができる。しかし、当業者なら、他のシステム構成も本発明と結合して使用できることを理解されたい。
本発明は多数の特定の詳細事項を参照して説明されてきたが、当業者なら、本発明は本発明の精神から逸脱することなしに他の特定の形式で実施できることを理解することができるだろう。例えば、本発明の多くの実施形態がマクロブロックを参照しながら上述された。当業者なら、これらの実施形態を任意の他の画素値のアレイと結合して使用することができることを理解することができるだろう。
【図面の簡単な説明】
【００２８】
【図１】１つのマクロブロックをＨ．２６４圧縮規格で区画化することができる異なる方法を示す。
【図２】基準フレーム・インデックスおよび基準フレーム・リストの概念を示す。
【図３】１つのフレームのスライスに対する区画データを含む従来の記憶構造の概念図を示す。
【図４】記憶構造内に記憶されている従来のヘッダの概念図を示す。
【図５】１つのフレームの復号化時に区画データを記憶するデータ構造の区画エントリの組成を示す。
【図６】１つのフレームのスライスに対する区画データを含む記憶構造の概念図を示し、その区画データは本発明による記憶構造内に編成されている。
【図７】図６に示されている記憶構造の割り当てられた部分に関連付けられているロケータ・リストの概念図を示す。
【図８】１つのビデオ・フレームのスライスに対するデータを記憶するための方法のフローチャートである。
【図９】エントリの６個の使用されていないバイト内に有用なデータを含む区画エントリの組成を示す。
【図１０】Ｈ．２６４規格に対するルックアップ・テーブルを示す。
【図１１】１つのフレームのスライスに対する区画データを含む記憶構造の概念図を示し、ここでヘッダ・データが区画エントリ内に統合化されている。
【図１２】統合化されたヘッダを使用したビデオ・フレームのスライスに対するデータを記憶するための方法のフローチャートである。
【図１３】カノニカルな基準フレーム・リストの一例を示す。
【図１４】カノニカルな基準フレーム・インデックスを使用して一連のフレーム内の１つのフレームのスライスの組に対するデータを記憶するための方法のフローチャートである。
【図１５Ａ】一体化された区画の例を示す。
【図１５Ｂ】一体化された区画の例を示す。
【図１６】マクロブロックの区画を一体化するための方法のフローチャートである。
【図１７】本発明のいくつかの実施形態が実施されているコンピュータ・システムを表している。
【符号の説明】
【００２９】
５０５  第１の運動ベクトル  ５１０  第２の運動ベクトル  
５１５  第１の基準フレーム・インデックス
５２０  第２の基準フレーム・インデックス
５２５  バイト    ６０５  記憶構造
６１０  記憶部分  ６３０  第１のセクション
６３５  第２のセクション  ７０５  ロケータ・リスト
８００  方法  ９００  区画エントリ
９３０  ヘッダ・データ  １００５  ルックアップ・テーブル
１２００  方法  １４００  方法
１７００  コンピュータ・システム  １７０５  バス
１７１０  プロセッサ  １７１５  システム・メモリ
１７２０  読出し専用メモリ  １７２５  永久記憶装置
１７３０  入力装置  １７３５  出力装置
【図１】
2006025414.tif 000003
【図２】
2006025414.tif 000004
【図３】
2006025414.tif 000005
【図４】
2006025414.tif 000006
【図５】
2006025414.tif 000007
【図６】
2006025414.tif 000008
【図７】
2006025414.tif 000009
【図８】
2006025414.tif 000010
【図９】
2006025414.tif 000011
【図１０】
2006025414.tif 000012
【図１１】
2006025414.tif 000013
【図１２】
2006025414.tif 000014
【図１３】
2006025414.tif 000015
【図１４】
2006025414.tif 000016
【図１５Ａ】
2006025414.tif 000017
【図１５Ｂ】
2006025414.tif 000018
【図１６】
2006025414.tif 000019
【図１７】
2006025414.tif 000020