(57)【特許請求の範囲】
【請求項１】
参照ブロックとして知られている少なくとも１つの他の既に符号化済みのブロックに応じて、現在のブロックのデータを予測し、予測されたブロックを供給するステップと、
前記現在のブロックと前記予測されたブロックとの比較によって残差に関する情報を決定するステップと、
前記残差に関する情報を符号化するステップと、
前記残差に関する情報を含む、各ブロックと関連付けられたデータの組を含むデータ信号を、該信号の中に符号化される前記ブロックと関連付けられたデータの書き込み走査の所定の書き込み走査順序に従って、送信および／または格納するステップと、
を含む、画像がブロックに細分化されている画像データの符号化方法であって、
前記予測ステップは、前記書き込み走査順序に沿って未だ考慮されていないブロックを含む、前記現在のブロックの近傍である符号化済みのブロックの組を考慮し、
現在のブロックと、該現在のブロックと関連付けられた前記予測されたブロックを予め決定したときに基礎とした少なくとも１つの参照ブロックと、を関連付ける依存ツリーを構築するステップと、
前記依存ツリーを表す情報を、各ブロックと関連付けられた前記データの組の中に挿入するステップと、
を含むことを特徴とする、符号化方法。
【請求項２】
前記予測ステップが、別個の予測走査順序に従って、ソースブロックのうちの少なくとも１つに対して、少なくとも２つの予測パスを有し、
所定の効率の基準に従って前記予測走査順序のうちの１つを選択するステップを含むことを特徴とする、請求項１に記載の符号化方法。
【請求項３】
参照ブロックとして知られている少なくとも１つの他の既に符号化済みのブロックに応じて、現在のブロックのデータを予測し、予測されたブロックを供給する手段と、
前記現在のブロックと前記予測されたブロックとの比較によって残差に関する情報を決定する手段と、
前記残差に関する情報を符号化する手段と、
前記残差に関する情報を含む、各ブロックと関連付けられたデータの組を含むデータ信号を、該信号の中に符号化される前記ブロックと関連付けられたデータの所定の書き込み走査順序に従って、送信および／または格納する手段と、
を備える、画像がソースブロックに細分化されている画像データの符号化装置であって、
前記予測手段は、前記書き込み走査順序に沿って未だ考慮されていないブロックを含む、前記現在のブロックの近傍である符号化済みのブロックの組を考慮し、
現在のブロックと、該現在のブロックと関連付けられた前記予測されたブロックを予め決定したときに基礎とした少なくとも１つの参照ブロックと、を関連付ける依存ツリーを構築する手段と、
前記依存ツリーを表す情報を、各ブロックと関連付けられた前記データの組の中に挿入する手段と、
を備えていることを特徴とする、符号化装置。
【請求項４】
通信ネットワークからダウンロード可能であり、および／または、コンピュータ読み取り可能な担体に記憶され、および／または、マイクロプロセッサによって実行可能であるコンピュータ・プログラムであって、
コンピュータ上で実行されるときに請求項１または２のいずれか一項に記載の符号化方法の前記ステップを実行するプログラムコード命令を備えていることを特徴とするコンピュータ・プログラム。
【請求項５】
画像がブロックに細分化され、書き込み走査順序に従って各組が前記ブロックのうちの１つと関連付けられた一連のデータの組を有する画像データ信号の復号化方法であって、前記データの組は前記書き込み走査順序に従って読み出され、
前記復号化方法は、現在のブロックに対して、
現在のブロックと、該現在のブロックと関連付けられた関連付け済みの予測されたブロックが予め決定されたときに基礎とした少なくとも１つの参照ブロックと、を関連付ける依存ツリーを表す情報を前記データの組から抽出するステップと、
前記依存ツリーの中で特定された１つ以上の前記参照ブロックが既に復号化されているときに前記ブロックを復号化するステップと、
を含み、前記復号化するステップが、
前記１つ以上の参照ブロックから予測されたブロックを予測するサブステップと、
前記予測されたブロックから、そして、前記データの組の中に表現された残差に関する情報に応じて、復号化済みのブロックを再構成するサブステップと、
を含むことを特徴とする復号化方法。
【請求項６】
現在のブロックに対して、
前記依存ツリーの中で特定された前記１つ以上の参照ブロックが既に復号化されている場合、前記現在のブロックを直ちに復号化するステップと、
そうではない場合、前記現在のブロックの前記データの組を待機中スタックに挿入するステップと、
前記書き込み走査順序に従って後のブロックを処理するステップと、
を含むことを特徴とする、請求項５に記載の復号化方法。
【請求項７】
待機中ブロックを復号化するために必要である参照ブロックを格納するステップを含み、前記待機中ブロックは、必要なすべての参照ブロックが利用可能になると直ちに復号化されることを特徴とする、請求項６に記載の復号化方法。
【請求項８】
復号化は、前記書き込み走査順序に従って連続パスにおいて行われ、前記参照ブロックのすべてが利用できる場合、現在のブロックは前記パスのうちの１回の間に復号化されることを特徴とする、請求項６に記載の復号化方法。
【請求項９】
少なくとも１つの現在のブロックに対して、前記予測サブステップは、各参照ブロックに重み付け値が割り当てられている少なくとも２つの参照ブロックを考慮することを特徴とする、請求項５に記載の復号化方法。
【請求項１０】
少なくとも１つの現在のブロックに対して、前記予測サブステップは、少なくとも２つのソースブロックで重なり合う少なくとも１つの参照ブロックを考慮することを特徴とする、請求項５に記載の復号化方法。
【請求項１１】
通信ネットワークからダウンロード可能であり、および／または、コンピュータ読み取り可能な媒体に記憶され、および／または、マイクロプロセッサによって実行可能であるコンピュータ・プログラムであって、コンピュータ上で実行されるときに、請求項５乃至１０のうちのいずれか一項に記載の復号化方法の前記ステップを実行するプログラムコード命令を備えていることを特徴とするコンピュータ・プログラム。
【請求項１２】
画像がブロックに細分化され、書き込み走査順序に従って各組が前記ブロックのうちの１つと関連付けられた一連のデータの組を有する画像データ信号の復号化装置であって、前記データの組は前記書き込み走査順序に従って読み出され、
前記ブロックのうちの少なくとも１つに対し、前記書き込み走査順序とは別個の復号化順序で復号化を行う復号化手段を実装していることを特徴とし、
前記復号化装置は、現在のブロックの復号化のため、
現在のブロックと、該現在のブロックと関連付けられた関連付け済みの予測されたブロックが予め決定されたときに基礎とした少なくとも１つの参照ブロックと、を関連付ける依存ツリーを表す情報を、前記データの組から抽出する手段と、
前記依存ツリーの中で特定された１つ以上の前記参照ブロックが既に復号化されているときに前記データの組の中に存在する残差に関する情報に応じて前記ブロックを復号化する手段と、
をさらに備えていることを特徴とする、復号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
１．発明の分野
本発明の分野は、一連の連続画像（successive images）により構成されている映像（video）ストリームを符号化および復号化することである。より具体的には、本発明は、ブロック変換を使用して画像圧縮または映像シーケンスの圧縮に適用されることができる。
【０００２】
したがって、本発明は、画像のブロックを符号化および復号化するため実施される予測技術に関する。
【０００３】
本発明は、特に、将来の映像圧縮規格において実施される映像符号化に適用されることができる。
【背景技術】
【０００４】
２．従来技術
多数の映像データ圧縮技術が既に知られている。これらの技術は、種々の映像符号化技術、たとえば、ＭＰＥＧ（ＭＰＥＧ−１、ＭＰＥＧ−２、ＭＰＥＧ−４パート２など）の機関、または、ＩＴＵ−Ｔ（Ｈ．２６１、・・・、Ｈ．２６４／ＡＶＣ）の機関に由来する映像圧縮規格を実施する技術を含み、映像シーケンスのブロック単位表現を使用する。よって、Ｈ．２６４技術によれば、各画像はスライスに細分化され、スライスは次にマクロブロックに細分化されることができる。各マクロブロックは、次に、いくつかのブロックに細分化される。１つのブロックは、画素の組によって構成される。
【０００５】
９個のマクロブロック１１１〜１１９によって形成されるスライスの実施例は、図１に概略的に示される。系統的に定義されるか、または、この目的で計画された、ストリーム中に存在する記述的要素によって指定されたパス１２に沿って、符号化演算および復号化演算の間、スライスは、マクロブロック単位で走査される。
【０００６】
この方法は、マクロブロックの構成ブロックに対してもほぼ同じである。マクロブロックは、特に、４×４または１６×１６個のブロックにより形成されることがある。従来技術によれば、これらのマクロブロックおよびブロックは、イントラ画像予測またはインター画像（inter-image）予測によって符号化される。
【０００７】
以下、ブロックのグループを考慮し、用語「グループ」は、特に、マクロブロックの組によって構成された画像もしくはスライス、または、マクロブロックに、すなわち、ブロックの組に対応することがある。用語「ブロック」は、したがって、Ｈ．２６４規格の用語に準拠して、マクロブロックまたはブロックにそれぞれ適用されることができる。
【０００８】
Ｈ．２６４技術によれば、ブロックは、
時間予測、すなわち、１つ以上の他の画像に属している参照ブロックへの参照、および／または、
現在の画像の隣接ブロックに応じての「空間」予測として知られている予測、
によって復号化されることができる。
【０００９】
後者の場合、予測は、既に符号化済みのブロックだけに由来して実行されることができる。
【００１０】
よって、図２の実施例では、図１の走査１２を考慮する場合、ブロック１１５は、前のブロック１１１〜１１４だけに応じて予測されることができる。符号化されていない後のブロック１１６〜１１９は、考慮されることができない。
【００１１】
図３Ａおよび３Ｂに示されるように、ブロックのグループでは、一般に、因果的領域（causal zone）３１および非因果的領域（anti-causal zone）３２としてそれぞれ称される２つのゾーン３１およびゾーン３２を区別することができる。ブロックのグループの因果的領域は、画像内のブロックの走査方向に関して現在のブロックより前に位置しているブロックからなる画像の領域である。
【００１２】
Ｈ．２６４エンコーダでは、画像内のブロックの走査の方向は、ブロックの符号化および復号化の走査の方向にも一致し、その上、ストリーム内のブロックの符号化済みデータの書き込みおよび読み取りの走査の方向にも一致する。以下、用語「因果的領域」は、ストリーム内のブロックの書き込みおよび読み取りの走査の方向に関して現在のブロックより前に位置しているブロックに対応する領域を意味する。非因果的領域は、ストリーム内のブロックの書き込みまたは読み取りの走査の方向に関して現在のブロックより後に位置しているブロックからなる画像の領域である。
【００１３】
従来技術による符号化技術と、特に、Ｈ．２６４エンコーダとは、非因果的領域のブロックが未だ符号化または復号化されず、その結果、予測のため利用できないので、現在のブロックの予測のため因果的領域のブロックだけを使用する。
【００１４】
図１に示される一般にラスタ走査として知られている走査、またはスパイラル状の走査によって中心からエッジへ向かって進むブロックのグループの走査を提案するスパイラル走査等、いくつかのタイプの走査が定義されている。
【００１５】
Ｈ．２６４／ＡＶＣ規格は各スライスに対し様々なパターンを定義している。しかし、これまでの技術の場合と全く同様に、走査スライスは予め定められ、予測のため使用できるブロック（因果的領域）と、使用できないブロック（非因果的領域）との区別につながる。
【００１６】
ブロックと関連付けられた予測は様々なタイプがある。
【００１７】
よって、Ｈ．２６４／ＡＶＣ符号化規格では、サイズが４×４であるブロックの場合、テクスチャ予測は、５つの考えられる予測の方向に沿って提案されている。各ブロック画素に対し、予測は、参照ブロックの最後の行または列を、最後の行および／または列の画素の組み合わせに拡張することによって取得される。
【００１８】
本発明は、符号化技術において、動き予測をさらに提案する。インター（inter）予測または時間予測において使用される参照ブロックは、動きベクトルを用いて特定され、因果的かつ時間的な近傍のブロックのベクトルによる予測を使用して、ストリーム内で符号化される。たとえば、符号化されるブロックのベクトルは、符号化されるブロックの上、左上、および、左のベクトルから中央値ベクトルを計算することにより予測されることができる。
【００１９】
符号化されるブロックの予測の基礎として既に再構成済みの画像のブロックを使用するシフトされたイントラ予測として知られている予測がさらに存在する。符号化されるブロックに最も近接する参照ブロックが、既に再構成済みの、符号化される画像の一部において探索される。目標参照ブロックの画素の値と符号化されるブロックの画素の値との差は最小化され、目標参照ブロックは、参照ブロックを取り出すために、符号化されるブロックに対して相対的なシフトを示すイントラ画像動きベクトルの符号化を用いてデコーダによって特定される。
【００２０】
３．従来技術の欠点
ストリーム内のブロックまたは生成された信号の書き込みおよび読み取り走査の使用に依存するこれらの様々な予測技術の１つの欠点は、可能な予測参照が因果的領域に限定されることである。実際に、ある種の状況では、たとえば、非因果的領域に存在するブロックである予測基準を使用することは、ブロック間の類似性のため、より効率的である。
【００２１】
しかし、このことは先行技術においては、非因果的領域のブロックが処理されていないため不可能であり、ゆえにこの予測のためには利用できない。
【００２２】
当業者にとって、この状況は、用語「非因果的領域」からわかるように、是正されるべき欠点としてではなく、不可避であることに注意を要する。
【発明の概要】
【００２３】
４．発明の概要
本発明は、画像がブロックに細分化されている画像データを符号化する方法の形式で、上記欠点をもたない新規な解決策を提案し、上記方法は、
参照ブロックとして知られている少なくとも１つの他の既に符号化済みのブロックに応じて、現在のブロックのデータを予測し、予測されたブロックを供給するステップと、
上記現在のブロックと上記予測されたブロックとの比較によって残差に関する情報を決定するステップと、
上記残差に関する情報を符号化するステップと、
各ブロックと関連付けられたデータの組からなるデータ信号であって、この信号の中に符号化されたブロックと関連付けられたデータの書き込みを走査するため所定の書き込み走査順序に従って上記残差に関する情報を含むデータ信号を送信および／または格納するステップと、
を備える。
【００２４】
本発明によれば、上記予測ステップは、上記書き込み走査順序に沿って未だ考慮されていないブロックを含む、上記現在のブロックの近傍である符号化済みのブロックの組を考慮し、符号化する方法は、
現在のブロックと、上記現在のブロックと関連付けられた予測されたブロックを予め決定したときに基礎とした少なくとも１つの参照ブロックを関連付ける依存ツリーを構築するステップと、
上記依存ツリーを表す情報を各ブロックと関連付けられた上記データの組の中に挿入するステップと、
を備える。
【００２５】
よって、画像の復号化は、上記ツリーに応じた、必ずしも書き込み走査順序に従わない復号化順序で行うことが可能である。
【００２６】
よって、本発明は、ユーザが符号化と復号化とに対してストリーム内のブロックの書き込み／読み取りの走査方向と同じ画像内のブロックの走査方向を使用する従来の技術とは異なる方法に依存する。これに反して、本発明は、符号化走査と書き込み走査とを区別し、より効率的な符号化走査の選択を可能とするが、書き込み走査は変化がない。本発明は、したがって、必要に応じて、非因果的領域に属しているために通常は無視される参照ブロックを考慮することを可能にする。
【００２７】
以下で説明されるように、別個の走査もまた復号化のため使用される。読み取り走査は書き込み走査に対応する。これに反して、符号化走査は、復号化走査と異なってもよい（いくつかの復号化走査が考えられる）。復号化走査は、符号化中に構築された依存ツリーを用いて復号化中に決定される。
【００２８】
本発明の一実施形態によれば、上記予測ステップは、別個の予測走査順序に準拠した少なくとも２つの予測パスを備え、符号化方法は、所定の効率の基準に従って上記予測走査順序のうちの１つを選択するステップを備える。
【００２９】
換言すると、いくつかの符号化走査がテストされ、最も効率のよい符号化テストが選択される。対照的に、書き込み走査順序は変化せず、したがって、選択された符号化の走査または順序とは無関係である。
【００３０】
上記効率の基準は、上記ブロックの符号化のため必要とされるビットレートと歪みを表す情報とを特に考慮することができる。
【００３１】
本発明は、前述の符号化方法を実施する画像データ符号化装置にさらに関係する。このような装置は、特に、
参照ブロックとして知られている少なくとも１つの他の既に符号化済みのブロックに応じて、現在のブロックのデータを予測し、予測されたブロックを供給する手段と、
上記現在のブロックと上記予測されたブロックとの比較によって残差に関する情報を決定する手段と、
上記残差に関する情報を符号化する手段と、
各ブロックと関連付けられたデータの組からなるデータ信号であって、この信号の中に符号化されたブロックと関連付けられたデータのための所定の書き込み走査順序に従って上記残差に関する情報を含むデータ信号を送信および／または格納する手段と、
を備える。
【００３２】
本発明によれば、上記予測手段は、上記書き込み走査順序に沿って未だ考慮されていないブロックを含む、上記現在のブロックの近傍である符号化済みのブロックの組を考慮し、上記装置は、
現在のブロックと、上記現在のブロックと関連付けられた予測されたブロックを予め決定したときに基礎とした少なくとも１つの参照ブロックを関連付ける依存ツリーを構築する手段と、
上記依存ツリーを表す情報を各ブロックと関連付けられた上記データの組の中に挿入する手段と、
を備える。
【００３３】
本発明は、通信ネットワークからダウンロード可能であり、および／または、コンピュータ読み取り可能な担体に記憶され、および／または、マイクロプロセッサによって実行可能であるコンピュータ・プログラム製品であって、コンピュータ上で実行されるときに、前述の符号化方法のステップを実行するプログラムコード命令を備えることを特徴とするコンピュータ・プログラム製品にさらに関係する。
【００３４】
本発明は、画像がブロックに細分化され、少なくとも１回の予測パスが実施される上記符号化方法に従って符号化された画像データ信号であって、現在のブロックに関して、
上記現在のブロックと、上記現在のブロックと関連付けられた予測されたブロックが予め決定されたときに基礎とした少なくとも１つの参照ブロックとを関連付ける依存ツリーを表す複数のデータと、
上記現在のブロックと対応する予測されたブロックとの間の差に対応する残差に関する情報と、
を含むデータの組を備える画像データ信号にさらに関係する。
【００３５】
よって、本発明による信号は、デコーダが（場合によっては、読み取り走査および／または符号化走査と異なることがある）このデコーダの復号化走査を決定することを可能にする依存ツリーの形をした情報を格納する。
【００３６】
本発明の１つの特定の実施形態によれば、依存ツリーを表す上記複数のデータは、上記現在のブロックのため考慮される参照ブロックの数を指定する情報と、参照ブロック毎に、上記参照ブロックと上記現在のブロックとを連結するベクトルを定義する複数のデータとを含む。
【００３７】
本発明は、前述されるように少なくとも１つの画像データ信号を備えるデータ担体にさらに関係する。
【００３８】
本発明は、前述の符号化方法によって符号化された信号を復号化する方法にさらに関係する。
【００３９】
本発明によれば、上記ブロックのうちの少なくとも１つに対して、復号化が上記書き込み走査順序とは別個の復号化順序に従って行われ、この方法は、現在のブロックに対して、
上記データの組から、現在のブロックと、上記現在のブロックと関連付けられた関連付け済みの予測されたブロックが予め決定されたときに基礎とした少なくとも１つの参照ブロックを関連付ける依存ツリーを表す情報を抽出するステップと、
上記依存ツリーの中で特定された１つ以上の参照ブロックが既に復号化されているときに上記ブロックを復号化するステップと、を備え
このステップは、
上記１つ以上の参照ブロックから予測されたブロックを予測するサブステップと、
上記予測されたブロックから、上記データの組の中に表された残差に関する情報に応じて、復号化済みのブロックを再構成するサブステップと、
を備える。
【００４０】
よって、本発明によれば、復号化は、ブロック読み取り順序ではなく、依存ツリーを考慮する別個の復号化走査に従って行われる。実際に、この依存ツリーの解析は、現在のブロックが所定の時点で（走査順序で既に読み出され、かつ、すでに復号化されたブロックに応じて）復号化できるかどうか、または、未だ復号化されていない１つ（または２つ以上）の参照ブロックの復号化を待つことが必要であるかどうかを決定するために使用される。
【００４１】
１つの特定の実施形態によれば、復号化方法は、現在のブロックに対して、
上記依存ツリーの中で特定された１つ以上の参照ブロックが既に復号化されている場合、上記現在のブロックを直ちに復号化するステップと、
そうではない場合、上記現在のブロックの中のデータの組を待機中スタックに挿入するステップと、
上記書き込み走査順序に従って後のブロックを処理するステップと、
を備える。
【００４２】
第１の特定の方法によれば、復号化方法は、待機中ブロックを復号化するために必要である参照ブロックを格納するステップを含むことができ、上記待機中ブロックは必要なすべての参照ブロックが利用可能になると直ちに復号化される。
【００４３】
別の特定の方法によれば、復号化は、上記書き込み走査順序に従って連続パスにおいて行うことができ、上記参照ブロックのすべてが利用できる場合、現在のブロックは上記パスのうちの１回の間に復号化される。
【００４４】
以上のように、復号化走査順序はアプリケーションに依存して変化することができる。特にできる限りブロックを復号化しようすること（第１の方法）、または、連続パスを行い、各パスにおいて可能であるブロックだけを復号化すること（第２の方法）が可能である。
【００４５】
符号化または復号化において、予測のため多くの適合およびオプションを考えることができる。よって、少なくとも１つの現在のブロックに対して、上記予測サブステップは、各参照ブロックに重み付け値が割り当てられている少なくとも２つの参照ブロックを考慮するということを計画することができる。
【００４６】
少なくとも１つの現在のブロックに対して、上記予測サブステップは、少なくとも２つのソースブロックで重なり合う少なくとも１つの参照ブロックを考慮するようにすることがさらに可能である。
【００４７】
本発明は、また、通信ネットワークからダウンロード可能であり、および／または、コンピュータ読み取り可能な媒体に記憶され、および／または、マイクロプロセッサによって実行可能であるコンピュータ・プログラム製品であって、コンピュータ上で実行されるときに、前述の復号化方法のステップを実行するプログラムコード命令を備えることを特徴とするコンピュータ・プログラム製品にさらに関係する。
【００４８】
本発明は、最後に、前述の符号化方法によって符号化された信号を復号化し、上記ブロックのうちの少なくとも１つに対して、上記書き込み走査順序とは別個の復号化順序に従って復号化を行う装置に関係する。この復号化装置は、現在のブロックの復号化のため、
上記データの組から、現在のブロックと、上記現在のブロックと関連付けられた関連付け済みの予測されたブロックが予め決定されたときに基礎とした少なくとも１つの参照ブロックを関連付ける依存ツリーを表す情報を抽出する手段と、
上記依存ツリーの中で特定された１つ以上の参照ブロックが既に復号化されているときに、上記データの組の中に存在する残差に関する情報に応じて上記ブロックを復号化する手段と、
を備える。
【００４９】
５．図のリスト
本発明の他の特徴および利点は、例示的かつ非限定的な実施例の目的のためだけに与えられた以下の実施形態の説明と、添付図面とからよりはっきりと明らかになる。
【図面の簡単な説明】
【００５０】
【図１】本書の冒頭で既に解説されたブロックのグループの実施例を対応する進行の順序で示す図である。
【図２】図１のブロックのグループの場合に空間的重み付けのため使用できるブロックを表す図である。
【図３Ａ】図２の実施例に対する因果的領域を示す図である。
【図３Ｂ】図２の実施例に対する非因果的領域を示す図である。
【図４】図２との比較によって本発明の原理を示す図である。
【図５】４×４形ブロックの場合に本発明によるイントラ空間予測のため使用される画素を表す図である。
【図６】インターモードにおける符号化済みブロックの場合に本発明による信号の構造の実施例を示す図である。
【図７】いくつかの、かつ、実際にはすべての優先ブロックを考慮する予測の実施例を表す図である。
【図８】本発明がイントラ符号化済みの画像に対してイントラシフトされたモードにあるとき、シンタックスを符号化する実施例を示す図である。
【図９】インターブロック型の符号化の場合にシンタックスの実施例を示す図である。
【図１０】ブロックのグループの復号化のための依存ツリーの実施例を示す図である。
【図１１】本発明による符号化の実施例を示すブロック図である。
【図１２】本発明による復号化の第１の実施形態のブロック図である。
【図１３】本発明による復号化の第２の実施形態のブロック図である。
【図１４】図１３の方法によるブロックの復号化の、より詳細な図である。
【発明を実施するための形態】
【００５１】
６．１  発明の原理についての注意喚起
本発明は、したがって、所定のブロックに対する空間予測の可能性を広げる技術を提案する。これらの予測は、ブロックのテクスチャ情報に適用可能であり、同様に、動き情報に適用可能である。
【００５２】
本発明による画像の圧縮プロセスのステップは２つの特定の段階を備える。一方は、符号化される画像のブロックに様々な処理および変換の演算（推定／動き補償、ＤＣＴ変換、量子化など）を実行することにある符号化段階であり、もう一方の段階は、画像のブロックと関連付けられたシンタックスを生成し、圧縮画像を表すストリームの中に書き込む書き込み段階である。本発明によれば、ブロックが符号化される順序は（少なくともある特定のブロックに対して）ブロックが画像内で走査される順序とは別個である。対照的に、符号化されるブロックがストリーム内で符号化される順序は変更されない。
【００５３】
画像を伸張するプロセスの対応する段階は、それぞれ、復号化の段階（動き補償、逆ＤＣＴ変換、逆量子化、再構成など）、および、構文解析としても知られているシンタックスを読み出す段階である。
【００５４】
本発明によれば、書き込みおよび読み取り走査順序（簡単にするため、「順序」と称されることもある）は、符号化または復号化順序と異なってもよい。
【００５５】
本発明によれば、符号化されるブロック、または、現在のブロックは、このようにして、予測参照として現在のブロックの因果的領域および非因果的領域に位置するブロックを使用することができる。予測参照としていくつかの（時間的および／または空間的に）隣接するブロックを使用し、重み付け和を適用することがさらに可能である。
【００５６】
このため、本発明は、少なくともある特定のブロックに対して、ストリーム（または信号）内のブロックの読み取りの順序に関して、または、ブロックが画像スライス内で走査される順序に関して、ブロックの復号化の順序を変更することが可能である。
【００５７】
本発明は、Ｈ．２６４／ＡＶＣ規格において理解されるようにブロックとマクロブロックとの両方に適用できることが思い出される。本明細書中で用語「ブロック」は、このようにして、特に断らない限り、本規格において理解されるように「マクロブロック」または「ブロック」を参照するものとして解釈できる。よって、以下に与えられた実施例はマクロブロックに属する。
【００５８】
一実施形態では、マクロブロックは、このように、マクロブロックによって使用される予測データに基づいて再帰的に定義された特定の復号化順序に従って復号化される。この復号化を可能にするため、マクロブロックの相互依存ツリーが定義される。復号化は、ツリー構造の葉に位置しているマクロブロックから始まり、根に遡る。本実施形態では、復号化順序は、ブロックが画像内で走査される典型的な順序を維持する読み取り順序に対して比較的変更される。
【００５９】
この技術は、いくつかの利点、特に、
ストリームの圧縮の改善と、
複雑さの増大がデコーダに制限されることと、
エンコーダにおいて制御することができる複雑さの増大と、
の利点を提供する。
【００６０】
この技術は、最大効率のため画像にいくつかのパス（pass）を作ることが好ましいので、エンコーダの複雑さのわずかな増大を導入する。しかし、この複雑さの増大は、適切な発見的解法を用いて制御することができる。
【００６１】
ツリーの定義および構築は付加的な処理演算の性能も仮定している。しかし、ツリーの中の依存の数は、複雑さを制御するために限定されることができる。
【００６２】
読み取り走査演算および復号化走査演算は、すべての映像圧縮規格において同一である。このことは、ブロックと関連付けられたシンタックスを読み取り、その後にこのブロックを直ちに復号化することを可能にする利点がある。しかし、読み取りおよび復号化は連続的に行うことが可能であり、すなわち、復号化は、すべてのブロックが読み出されると開始することができる。本発明によれば、符号化済みのブロックが読み出される順序は変更されず、ブロックが画像に書き込まれる順序と同一である。しかし、復号化順序は変更され、各ブロックのための予測モードに連結される。
【００６３】
詳細に後述される実施形態では、ブロックまたはマクロブロックを符号化または復号化するため、符号化／復号化コンテキストがセットアップされる。このコンテキストは、現在のブロックの符号化／復号化のための予測を構築するために使用することができるブロックを指し示す。これらのブロックは、以下では参照候補ブロックと呼ばれる。参照候補ブロックは、先に符号化／復号化され、再構築されたブロックである。
【００６４】
しかし、参照ブロックは、符号化される／復号化されるブロックの因果的領域または非因果的領域に位置することがあり、これらの領域は、ブロックが画像内で走査される方向、または、ブロックがストリーム内で読み出され、もしくは、書き込まれる方向に従って定義されている。
【００６５】
アルゴリズムを適用することができる予測のタイプの網羅的でないリストが次のセクションで提案される。当然ながら、他の予測のタイプが使用されることができる。
【００６６】
符号化および復号化アルゴリズムは、ブロックの符号化／復号化のコンテキストが確立されると、使用されるすべての予測のタイプに対し同じである。
【００６７】
後述される実施形態は、Ｈ．２６４／ＡＶＣエンコーダ、または、将来のＨ２６５エンコーダで使用される符号化コンテキストに対応する符号化コンテキストの中にある。
【００６８】
６．２  予測のタイプの実施例
現在のブロックは、予測をセットアップするために１つ以上の参照ブロックを使用する。現在のブロックと予測、すなわち、予測されたブロックとの間の差、または、残差は、次に、符号化され、送信される（および／または、アプリケーションに依存して格納される）。復号化の時点で、受信された差はブロックを再構成するために予測に加算される。
【００６９】
６．２．１  テクスチャの予測
本出願において、本発明は、Ｈ．２６４／ＡＶＣエンコーダで使用される予測を拡張することを提案する。実際に、ブロックの非因果的領域の使用は、符号化されるブロックの予測を構築するために、右ブロック、右下ブロック、下ブロック、左下ブロックの追加を可能にする。
【００７０】
図４は、本発明の方法に従ってブロック４１５の空間予測のため使用することができるすべての参照候補ブロック４１１〜４１４および４１６〜４１９を示す。
【００７１】
圧縮の効率を改善するため、閉ループ内の、すなわち、符号化済み／復号化済みのブロックに基づいて、各現在のブロック４１５を符号化するために、かつ、エンコーダとデコーダとの間のドリフトの現象を回避するために、既に符号化済みのブロック（図４の実施例における斜線領域４３）のみを使用する予測のみを可能にすることが必要である。中央ブロック４１５の可能性のある予測は、符号化されるブロックの因果的領域（４１１、４１２、４１３）と非因果的領域（４１６、４１９）に位置する参照候補ブロックを使用する予測である。
【００７２】
当然ながら、ブロック４１５は、Ｈ．２６４／ＡＶＣエンコーダにおいて既に候補となる時間予測を有する。
【００７３】
図５は、イントラ空間予測のため使用される画素を示す。因果的領域に対応し、Ｈ．２６４／ＡＶＣ規格に規定されている既知の予測のタイプ（画素Ａ〜Ｍ）を除いて、本発明の方法は、非因果的領域に位置している新しい画素（画素Ｎ〜Ｚ）を使用して予測のタイプを提案することを可能にする。これらの予測のタイプは、Ｈ．２６４／ＡＶＣエンコーダに存在する予測の方向を反転することによって得られる。
【００７４】
ブロックの各画素に対し、予測は、参照ブロックの最初の行または最初の列を拡張すること（Ｈ．２６４／ＡＶＣ規格の用語によれば、モード０またはモード１）により、または、最初の行および／または最初の列の画素の組み合わせ（モード２〜モード８）により得られる。
【００７５】
導入された新しいモードのシグナリングは、たとえば、以下のいずれかによって行うことができる。
各ブロックのための付加フラグを導入する。予測のタイプは、各ブロックに対しＨ．２６４／ＡＶＣエンコーダのシンタックスの中に既に存在する。フラグの値と関連付けられた予測のタイプの値は、予測のタイプの方向を指し示すことになる。値０はＨ．２６４／ＡＶＣエンコーダの方向を指し示し、一方、値１は新しい方向を指し示すことになる。
新しい予測のタイプを導入する。予測のタイプは、各ブロックに対しＨ．２６４／ＡＶＣエンコーダのシンタックスの中に既に存在する。予測のタイプを表すシンタックス要素は、そのとき、０から１７まで変化する値をとることになり、０〜８は、Ｈ．２６４／ＡＶＣエンコーダによって使用される予測のタイプであり、９〜１７は新しい予測のタイプである。
【００７６】
同様に下ブロックの最初の行からの画素と上ブロックの最後の行からの画素とを使用する予測のタイプを追加することが可能であり、または、同様に右ブロックの最初の列からの画素と左ブロックの最後の列からの画素とを使用することによって予測のタイプを追加することが可能である。このタイプの予測は、付加フラグを符号化することにより、または、補助的な予測のタイプの値を定義することにより追加される。
【００７７】
前述された方法は、大きさ４×４のブロックに適用することができる。同様の拡張は、他のタイプのブロック、たとえば、大きさ１６×１６のブロックにも行うことができる。
【００７８】
予測のタイプについてのシンタックス要素の符号化は、たとえば、シンタックス要素の符号化を最適化するために、符号化されるブロックに隣接するブロックのコンテキストを考慮することができる。符号化されるブロックに隣接するブロックが未だ符号化されていない場合、それらは、符号化されるブロックを予測するため用いることができず、ある特定の予測の方向はそのとき不可能になる。
【００７９】
６．２．２  動き予測
本発明の方法は、Ｈ．２６４／ＡＶＣ技術に比較して動きの予測を広げるためにも使用することができる。ブロックの非因果的領域の使用は、符号化されるブロックの動きベクトルの予測を構築するために、右ブロック、右下ブロック、下ブロック、左下ブロックの追加を可能にする。
【００８０】
付加的な情報は、動きベクトルを予測するため使用されたブロックを指し示すために、ストリーム内で符号化されるべきである。この情報は、インデックスの符号化を用いて挿入することができる。インデックスは、所定の予測ベクトルの組から符号化されるブロックの動きを予測するため使用される予測ベクトルを表す。
【００８１】
この組は各ブロックに適応する。この組は、Ｎ個の予測ベクトルを含む。この組は、符号化されるブロックの因果的近傍および非因果的近傍のベクトルと、中央値ベクトルと、別の画像の中に共通に存在するブロックのベクトルとを含むことができる。図６はこのモードと関連付けられたシンタックスを示す。
【００８２】
インターモードで符号化されたブロックに対し、ブロックのデータ項目は、
使用された予測ベクトルを指定するインデックスｉｄｘと、
動きベクトルの残差ｄｖｉおよびｄｖｊと、
ブロックテクスチャの残差ｒｅｓと、
を含む。
【００８３】
６．２．３  シフトされたイントラ予測
本発明は、非因果的領域で再構築されたブロックの使用を許可する際に、Ｈ．２６４／ＡＶＣ規格のシフトされたイントラ予測モードを拡張するためにも使用できる。動きベクトルを用いて行われるシグナリングは変化しない。
【００８４】
さらに、ベクトルを用いるこのブロックの予測は、同じ方向から、または、別の方向から来る２つ以上のブロックに基づいて計算することができる。よって、多次元予測を定義することができる。
【００８５】
現在のブロックＢと関連付けられた予測（予測されたブロック）Ｐｒｅｄは、次に、使用された異なる方向のブロックの重み付け和を使用して計算され、ブロックＢの画素（ｉ，ｊ）に対して、予測は、その結果、
【数１】
0005396600.tif 000002
であり、ここで、ＮはＢの予測のため使用された参照ブロックの数であり、（ｖｉｎ，ｖｊｎ）は、画像Ｉｔｎ内の参照ブロックを取り出すために画像Ｉｔｎ内のブロックＢに適用されるべきシフトを指定するベクトルであり、ｗｎは参照ブロックの寄与に重み付けする重みである。
【００８６】
第１の方法では、すべての参照ブロックは、全体的な予測の計算に同等に寄与することができる。重みはそのとき１／Ｎである。
【００８７】
別の方法によれば、ブロックは、参照ブロックと符号化されるブロックとの間の距離に反比例する重みを用いて全体的な予測の計算に寄与することができる。
【００８８】
画像Ｉｔｎは符号化される画像でもよく、または、別の画像でもよい。
【００８９】
時間予測の場合と全く同様に、ベクトル（ｖｉｎ，ｖｊｎ）によって指し示された参照ブロックは、画像をブロックに細分化するグリッドと揃えられていない画素のブロックでもよい。使用される参照ブロックは、そのとき、符号化されるブロックと同じサイズを有する画素の領域であり、この画素の領域の原点はベクトルが加算される符号化されるブロックの始点によって与えられる。
【００９０】
よって、参照ブロック７１は、図７に示されるように、グリッドのいくつかのブロックに重なることがある。この図７は、前述されているように、２つの参照ブロック７１および７２がブロック７３の予測に考慮される方式をさらに示す。
【００９１】
同様に、ベクトルがサブ画素ベクトルである場合、ベクトルによって指し示された領域は、参照ブロックのサブ画素位置を再構成するためにオーバーサンプルされるべきである。
【００９２】
このステップは、この予測が符号化される現在の画像内で行われる点を除いて、Ｈ．２６４／ＡＶＣエンコーダのサブ画素精度で動きベクトルを使用する時間予測に類似している。
【００９３】
この拡張され、シフトされたイントラ予測のモードでは、符号化される複数の情報は以下の通りである。
予測のため使用される参照ブロックの数。
各参照ブロック、予測の方向に対して、動きベクトル。
各参照ブロックに対して、予測のため使用される画像（符号化される画像自体、または、時間予測の場合における別の画像）。
【００９４】
この場合、イントラ画像とインター画像とを区別することが可能である。イントラ画像は、これらのイントラ画像自体だけを参照して符号化され、一方、インター画像はある画像または他の画像を参照して、または、インター画像自体を参照して符号化される。
【００９５】
シフトされたイントラ画像内で符号化されたイントラ画像のブロックを符号化するシンタックスは図８に示されている。
【００９６】
符号化されるデータは以下の通りである。
使用される参照ブロックの数Ｎ。
各参照ブロック８１１〜８１Ｎに対する動きベクトル残差ｄｖｉ、ｄｖｊ。動きベクトルは、符号化されるブロックの因果的領域に位置している既に符号化済みのブロックのベクトルに対して相対的に予測によって符号化することができる。この場合、残差だけがヘッダ内に符号化される。
変換され量子化されたブロックの残差の係数ｒｅｓ。
【００９７】
インター画像はブロックを含むことがある。
インター：シーケンスの１つ以上の符号化済み／復号化済みの画像に対して相対的に予測によって符号化される。
イントラ：符号化される画像のブロックに対して相対的に予測によって符号化される。
【００９８】
シフトされたイントラモードにおけるイントラブロックのシンタックスは、イントラ画像のブロックに対して本発明によって提案されるシンタックスと同じである。
【００９９】
インターブロックのシンタックスは、たとえば、図９に示された形式で、画像のうちのいくつかまたは他の画像のブロックに加えて、符号化される画像のブロックに関連してインターブロックを予測する可能性を追加するために修正される。
【０１００】
各ブロックに対し、ブロックのヘッダは、
使用される参照ブロックの数Ｎと、
各参照ブロック９１１〜９１Ｎに対し、動きベクトル残差ｄｖｉ、ｄｖｊと、
各参照ブロック９１１〜９１Ｎに対し、このブロックが属する画像のインデックスｒｅｆと、
を指し示す。
【０１０１】
ベクトルは、符号化されるブロックの因果的領域に位置している既に符号化済みのブロックのベクトルに対して相対的に予測によって符号化される。残差だけがヘッダ内に符号化される。
【０１０２】
ここで説明されている特定の実施形態では、ブロックのヘッダの残り部分は、Ｈ．２６４／ＡＶＣエンコーダのシンタックスに対して相対的に変化しない。同様に、ブロックのデータの残り部分は変化しない。ブロックのデータの残り部分は、ブロックの残差の変換、量子化された係数に対応する。
【０１０３】
イントラ画像に関するインター画像に対し、予測のため使用される参照ブロックの数Ｎは１、２または３に制限することができる。この制限は、符号化の際にすべてのブロックに共通した最大の可能な数Ｎｍａｘとして、画像のデータのヘッダ内に示唆することができる。
【０１０４】
Ｎが制限されているヘッダ内の情報の符号化を最適化するために、ブロックの符号化のタイプは、タイプに加えて、すなわち、イントラであるか、または、インターであるかに加えて、予測のため使用することができる参照ブロックの数を指し示すことにより修正することができる。
【０１０５】
たとえば、符号化モードは、ＩＮＴＲＡ−１ＲＥＦ、ＩＮＴＲＡ−２ＲＥＦ、ＩＮＴＥＲ−１ＲＥＦ、ＩＮＴＥＲ−２ＲＥＦであることができ、これらのモードはブロックのタイプ、すなわち、イントラまたはインターのどちらであるかと、使用される参照ブロックの数とを指し示す。これらのモードは、Ｈ．２６４／ＡＶＣエンコーダのＩＮＴＲＡモード／ＩＮＴＥＲモードに追加される。これらのモードは、従来のモードと同様に、サブブロックに区分する異なる事例の場合に同様に表現される。
【０１０６】
本変形例では、イントラブロックおよびインターブロックのシンタックスは，もはやフィールドＮを含まない。この値は符号化モジュールから推論される。
【０１０７】
６．３  ブロックの依存ツリー
依存ツリーは、現在のブロックの予測のため特定された参照ブロックから始めて現在のブロックのためセットアップすることができる。ブロックの復号化は、ブロックが未だ再構成されていないブロックを使用する場合、まず始めにブロックの１つずつの依存ツリーをセットアップする際にこれらのブロックを再構成することが必要であるので再帰的でもよい。
【０１０８】
図１０は、ブロック間の依存関係の実施例を示す。ブロック２の依存ツリーは、
２が１および６に依存すること、
６が５に依存すること、
５が１に依存すること、
１が０に依存すること、
によって与えられる。
【０１０９】
ブロック０は画像のブロックに依存しない。ブロック０は、ヌル予測に対して、または、時間予測のみに対して相対的に符号化される。
【０１１０】
その後、依存ツリーはトレースバックされ、ブロック０が再構成され、次に、ブロック１、次に、ブロック５および６、そして最後にブロック２が再構成される。
【０１１１】
本実施例は、現在のブロックの非因果的領域に位置している参照ブロックに基づく予測の追加によってより複雑になるブロック間の依存関係のメカニズムを示す。
【０１１２】
前述されているように、ブロックの読み取りの順序による復号化はもはや可能でないことが認められる。
【０１１３】
６．４  符号化の実施の実施例
マクロブロック（またはブロック）の符号化は、各マクロブロックのためいくつかの可能な符号化モードを競合させることによって行うことができる。現在のマクロブロック毎に、予測候補のリストが現在のマクロブロックに対し（空間的および時間的な）既に符号化されている隣接マクロブロックに応じて確立される。所定の性能の基準に依存する予測、たとえば、マクロブロックまたはブロックのフローレート（flowrate）と歪みとの間の最良の妥協点が選択される。
【０１１４】
この基準のための閾値を設定し、この閾値を満たす見つけられた第１の予測を選択することがさらに可能である。
【０１１５】
既に説明したように、従来の走査方向（たとえば、図２において、上から下へ画像を走査する方向）は、さらに既に定義された予測のすべての方向の利点をもたらさない。ここで提案されている符号化は、別個の走査方向が定められたいくつかの符号化パスを実施する。ブロック走査方向は、したがって、符号化パス毎に異なる。
【０１１６】
マクロブロックまたはブロックはグループ単位で空間的に符号化される。画像内の符号化されるＭ個の隣接ブロックを検討し、マクロブロックまたはブロックのグループを形成する。これらのグループはランダムに作ることが可能であり、または、解析の段階からもたらされることがある。
【０１１７】
各グループは、所定の回数に亘って、または、このグループのため定義されたビットレートもしくは歪みに達するまで、各符号化パスで別々に符号化される。
【０１１８】
グループの第１のブロックは、最初に、従来通りにすべて符号化される。考慮中のブロックのグループが第１のグループである場合、このブロックは、このブロックの空間的近傍に対して相対的に予測することなく符号化される。そうでない場合、ブロックは、別のグループの中のこのブロックの既に符号化済みの近傍に対して相対的に予測を使用することによって符号化されてよい。インター画像の場合、従来通りの時間予測も同様に可能である。
【０１１９】
次に、グループの他のマクロブロックが符号化される。グループの中のすべてのブロックが符号化されるとき、グループを符号化するビットレート／歪みコストがグループの中のブロックのすべてのビットレート／歪みコストを合算することによって計算される。
【０１２０】
いくつかの符号化パスはグループを符号化するため行われる。各パスは、新しい符号化順序に従ってグループの中のブロックを符号化する。
【０１２１】
符号化パスの最低ビットレート／歪みコストは維持され、ブロックはこの符号化パスの間に定められた予測を用いて符号化される。
【０１２２】
符号化アルゴリズムは、したがって、ブロックのすべてのグループが符号化されるまで次のグループを渡す。
【０１２３】
その後、符号化済みのブロックは、ブロック書き込み順序に従って送信および／または格納される。
【０１２４】
図１１は、グループの符号化の実施例の略図を与える。走査方向または順序が選択される（１１１）。最初の走査に対し、この走査は、送信されるべき信号を構築するため使用され、そして、復号化時にブロックの情報の読み取りのため使用される通常の符号化走査順序でもよい。
【０１２５】
符号化されるグループのブロックは、選択された走査順序に従って先頭から始めて符号化される（１１２）。グループのすべてのブロックの符号化が終わらない限り（テスト１１３）、新しいブロックが選択された走査順序に従って、そして、予測のため、既に符号化済みのブロックを考慮に入れて符号化される（１１２）。
【０１２６】
グループのすべてが符号化されると、符号化データは格納され、ビットレート／歪みの妥協点が決定される（１１４）。
【０１２７】
予想されるパスの回数に達しない場合（１１５）、および／または、ビットレート／歪み閾値に達しない場合、演算は、ステップ１１１へ戻り、新しい走査順序を選択する。新しい走査順序は、たとえば、スパイラル走査でもよく、または、グループ内に始点をもつどのような走査でもよい。
【０１２８】
ステップ１１２〜１１５は、この新しい走査順序に対して繰り返される。ステップ１１４において、最も効率的なパスに対応するデータだけを維持することが選択されることがある。
【０１２９】
予想されるパスの回数に達したとき（テスト１１５）、および／または、あるビットレート／歪みに到達した場合、各ブロックの複数の情報が最も効率的なパスに対応する順序で送信および／または格納のため保存される（１１６）。処理済みのブロックのグループが最後である場合（テスト１１７）、ブロックの符号化は終了し（１１８）、この方法は、画像内のブロックの走査の順序で、または、ブロックの書き込みの順序で（そして、ブロックのため選択されたパスの符号化走査順序ではなく）送信および／または格納されるべきストリームまたは信号を構築する。
【０１３０】
処理済みのブロックのグループが最後ではない場合（テスト１１７）、この方法はステップ１１１へ戻り、パスのカウントをリセットする。
【０１３１】
６．５  復号化
６．５．１  ストリームの復号化の第１の実施形態
復号化は、ブロックと関連付けられた情報の読み取りと、ブロックの再構築との２つの主要な段階を備える。
【０１３２】
図１２のダイアグラムに示された第１の実施形態では、符号化済みの画像のすべてのマクロブロックは、ストリーム内のブロックの書き込みの順序（すなわち、ブロックが、受信されたストリームまたは信号内に書き込まれ、ブロックの情報項目が保存される順序）で、順次に読み出される。
【０１３３】
ブロックの再構成は、再構成前のすべてのマクロブロックが積み重ねられるスタックを使用する。
【０１３４】
図１２によって示されるように、スタックは、最初に、読み出された最初のマクロブロックを用いてすべて初期化される（１２１）。
【０１３５】
スタックの最初のマクロブロックと関連付けられた情報の読み取り１２２は、このマクロブロックの再構成が画像内に位置している参照マクロブロックの再構成を第一に必要とするかどうかを決定するために使用される（１２３）。参照マクロブロックは、現在のマクロブロックの予測によって使用されるマクロブロックである。
【０１３６】
現在のマクロブロックが予測を使用しない場合、または、予測が既に再構成済みのマクロブロックだけを使用する場合、現在のマクロブロックは再構成することができる（１２４）。
【０１３７】
現在のマクロブロックが未だ再構成されていないマクロブロックを使用する予測を必要とする場合、これらの参照マクロブロックはスタック内に積み重ねられる（１２５）。このアルゴリズムは、その後、ステップ１２２へ戻る。
【０１３８】
マクロブロックが復号化されるとき（１２４）、このアルゴリズムは、スタックが空であることを検証する（１２６）。
【０１３９】
このスタックが空である場合、このアルゴリズムは、画像のすべてのマクロブロックが再構築されたことをチェックする（１２７）。応答が肯定である場合、画像のマクロブロックの復号化は終了する（１２８）。そうではない場合、画像走査方向に復号化されていない次のマクロブロックは積み重ねられ（１２９）、このアルゴリズムはステップ１２２へ戻る。
【０１４０】
スタックが空ではない場合（テスト１２６）、このアルゴリズムはステップ１２２へ戻る。
【０１４１】
この復号化アルゴリズムは、画像のすべてのマクロブロックの依存関係を考慮してすべてのマクロブロックを復号化するため使用される。
【０１４２】
６．５．２  ストリームの復号化の第２の実施形態
図１３に示された第２の実施形態によれば、復号化方法は、最大インデックスを有するブロックのインデックスに応じたブロックの優先順位を用いて、ブロック待ち時間の取捨選択リストを実施する。
【０１４３】
この方法は、したがって、このリストを空リストとして初期化する初期化ステップ１３１で始まる。
【０１４４】
ブロックは、その後に、（たとえば、ラスタ走査、スパイラル走査、レイン（rain）走査順序などの通常の指示に従って）画像内のブロックの走査の順序で走査され、
現在のブロックと関連付けられた依存ツリーに応じて現在のブロックの依存関係を特定され（１３２）、
現在のブロックに対し、関連付けられた符号化のモードおよび予測に従って、直ちに復号化可能であるか、または、復号化可能ではない状態を決定し（１３３）、
ブロックが復号化可能である場合、
復号化し（１３４）、そして、
待機スタック内の復号化可能なブロックをスタックから取り出し（１３５）、
ブロックが復号化可能ではない場合、
１３６：ブロックを待機リストに追加し、
次のブロックへ渡し（１３７）、
最後のブロックが処理されている場合（１３８）、処理を終了し（１３９）、そうでない場合、ステップ１３２へ戻る。
【０１４５】
復号化可能なブロックのスタックからの取り出し（１３５）は、図１４によって詳細に示される。このプロセスは次の通りである。
待機リストのすべてのブロックを走査し（１４０）、
リストの中の現在のブロックが復号化できる場合（すなわち、現在のブロックが依存するすべてのブロックが既に復号化済みである場合）（１４１）、
現在のブロックは待機リストまたはスタックから取り除かれ（１４２）、
現在のブロックは復号化され（１４３）、
すべてのブロックが考慮された場合（走査の終わり）（１４４）、
待機リストの処理を終了し（１４５）、
そうでなければ、演算は次のブロックへ進み（１４６）、処理はステップ１４１で再開される。
【０１４６】
このスタックからの取り出しプロセスは、その上、待機リストが空でなく、そして、スタックからの取り出し演算が待機リストから少なくとも１つの要素を回収している限り、反復的に繰り返される。
【図１】
0005396600.tif 000003
【図２】
0005396600.tif 000004
【図３Ａ】
0005396600.tif 000005
【図３Ｂ】
0005396600.tif 000006
【図４】
0005396600.tif 000007
【図５】
0005396600.tif 000008
【図６】
0005396600.tif 000009
【図７】
0005396600.tif 000010
【図８】
0005396600.tif 000011
【図９】
0005396600.tif 000012
【図１０】
0005396600.tif 000013
【図１１】
0005396600.tif 000014
【図１２】
0005396600.tif 000015
【図１３】
0005396600.tif 000016
【図１４】
0005396600.tif 000017