(57)【要約】ビデオシーケンスをスケーラビリティの制約下で圧縮するために、ウェーブレット分解のスケールに亘る有意情報の欠如の予測に基づく公知の２Ｄ又は３ＤのＳＰＩＨＴは、異なる解像度における同一画像に対応する画素の集合を有意水準と称される値と比較する。何れの場合も、変換係数は、有意な集合のリスト（ＬＩＳ）、有意でない画素のリスト（ＬＩＰ）及び有意な画素のリスト（ＬＳＰ）の３つの順序リストで表わされる画素に関連する大きさのテストで順序付けられる。元のビデオシーケンスでは、画素の値はそれを囲む画素の値に依存する。ｄの先行ビットによって与えられるシンボルの確率の推定は、条件付け事象の数が増加するにつれ困難となる。本発明はビットストリームに寄与する情報ソースの作用の変化を反映する効率的なビデオ符号化方法を提供することを目的とし、即ち、有意性の各水準におけるリスト中の０及び１の発生の確率の推定のために、４つの文脈ツリーによって表わされる４つのモデルが考えられ、これらのモデルはＬＩＳ、ＬＩＰ、ＬＳＰに対応し、輝度の係数のモデルとクロミナンスのモデルは識別される。
2004505520.tif 000002
【特許請求の範囲】
【請求項１】
連続する所定の数の解像度レベルを生じさせる３次元（３Ｄ）ウェーブレット変換によりフレーム群（ｇｒｏｕｐｓ ｏｆ ｆｒａｍｅｓ）へ分割されたビデオシーケンスを圧縮するための符号化方法であって、
上記方法は、上記ビデオシーケンスの元の画素集合から２値形式で符号化されたウェーブレット変換係数を生じさせる「集合分割階層ツリー（ｓｅｔ ｐａｒｔｉｔｉｏｎｉｎｇ ｉｎ ｈｉｅｒａｒｃｈｉｃａｌ ｔｒｅｅｓ：ＳＰＩＨＴ）」と称される階層サブバンド符号化処理に基づくものであり、
上記ウェーブレット変換係数は、有意でない集合のリスト（ＬＩＳ）、有意でない画素のリスト（ＬＩＰ）及び有意な画素のリスト（ＬＳＰ）と称される３つの順序付けリストによって表わされる画素を用いた大きさについてのテストによって、ツリーの形に編成され、各有意水準に対応する分割部分集合へ順序付けされ、
上記テストは、夫々の有意な係数が上記２値表現で符号化されるまで続けられる分割処理によって上記元の画素集合を上記分割部分集合へ分割するために行われ、
送信される出力ビットストリームにはサインビットも付され、
各有意水準において上記リスト中のシンボル０及び１の発生の確率を推定するために、４つの文脈ツリーによって表わされるＬＩＳ、ＬＩＰ、ＬＳＰ、及びサインに対応する４つのモデルが考えられ、更に、Ｕ係数とＶ係数と区別することなく輝度係数のモデルとクロミナンス係数のモデルとが更に識別される、符号化方法。
【請求項２】
各ビットを符号化するために、現在ビットに先行するｄのビットで形成され上記現在ビットについて考えられるモデルに従えば異なった文脈が用いられ、上記文脈は、Ｕ平面とＶ平面とを区別すると共に輝度係数とクロミナンス係数について識別され、また、空間的・時間的分解のときは各フレームについて識別され、これらの文脈は、色平面Ｙ、Ｕ又はＶ上で、及び、時間的なサブバンド中のフレーム上で、ＬＩＳ、ＬＩＰ、ＬＳＰから生ずるシンボル又はサインビットマップから生ずるシンボルの種類に従った構造へとまとめられる、
請求項１記載の符号化方法。
【請求項３】
上記文脈の表現は、夫々の場合に調べられたｄの最後のビットのシーケンスで埋められた３次元構造ＣＯＮＴＥＸＴであり、
ＣＯＮＴＥＸＴ［ＴＹＰＥ］［クロマ］［フレーム番号］
と表わされ、
種類を表わすＴＹＰＥは、ＬＩＰ＿ＴＹＰＥ、ＴＩＰ＿ＴＹＰＥ、ＴＳＰ＿ＴＹＰＥ又はＳＩＧＮ＿ＴＹＰＥであり、
クロマは、Ｙ、Ｕ又はＶである、請求項２記載の符号化方法。
【発明の詳細な説明】
【０００１】
本発明は、連続する所定の数の解像度レベルを生じさせる３次元（３Ｄ）ウェーブレット変換によりフレーム群（ｇｒｏｕｐｓ ｏｆ ｆｒａｍｅｓ）へ分割されたビデオシーケンスを圧縮するための符号化方法に関連し、この方法は、ビデオシーケンスの元の画素集合から２値形式で符号化されたウェーブレット変換係数を生じさせる「集合分割階層ツリー（ｓｅｔ ｐａｒｔｉｔｉｏｎｉｎｇ ｉｎ ｈｉｅｒａｒｃｈｉｃａｌ ｔｒｅｅｓ：ＳＰＩＨＴ）」と称される階層サブバンド符号化処理に基づく方法であり、ウェーブレット変換係数は、有意でない集合のリスト（ＬＩＳ）、有意でない画素のリスト（ＬＩＰ）及び有意な画素のリスト（ＬＳＰ）と称される３つの順序付けリストによって表わされる画素を用いた大きさについてのテストによって、ツリーの形に編成され、各有意水準に対応する分割部分集合へ順序付けされ、テストは、夫々の有意な係数が２値表現で符号化されるまで続けられる分割処理によって元の画素集合を分割部分集合へ分割するために行われ、送信される出力ビットストリームにはサインビットも付される。
【０００２】
従来のビデオ圧縮スキームは、４つの主なモジュール、即ち、動きの推定及び補償、係数の変換（例えば離散コサイン変換又はウェーブレット分解）、係数の定量化及び符号化、並びに、エントロピー符号化を含むと考えることができる。更に、ビデオ符号化器がスケーラブルでなくてはならない場合は、低いビットレートから高いビットレートへ、ビットレートと共にビデオの質を高めつつ、画像を符号化することが可能でなくてはならない。画像の階層的な表現を自然に与えることにより、ウェーブレット分解による変換は、従来の離散コサイン変換（ＤＣＴ）と比較して、スケーラブルなスキームに良く適すると思われる。
【０００３】
ウェーブレット分解により、元の入力信号が一組のサブバンド信号によって示されることが可能となる。実際に、各サブバンドは、所与の解像度で特定の周波数範囲内で元の信号を表わす。このような互いに関連しないサブバンドへの分解は、一般的には一組の単次元フィルタバンクを、まず現在画像のラインに適用し、次にフィルタ処理によって得られたカラムに適用することによって行われる。この例は、Ｓ．Ｓ．Ｇｏｈによる”Ｄｉｓｐｌａｃｅｍｅｎｔｓ ｉｎ ｗａｖｅｌｅｔ ｄｅｃｏｍｐｏｓｉｔｉｏｎ ｏｆ ｉｍａｇｅｓ”， Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ， ｖｏｌ． ４４， ｎｏ １， Ｊｕｎｅ １９９５， ｐｐ． ２７−３８に記載されている。実際は、画像の低周波成分と高周波成分とを分割するために、２つのフィルタ、即ち低域通過フィルタと高域通過フィルタが用いられる。この操作は、まずラインに対して行われ、続いて２倍でサブサンプリング操作が行われ、続いてサブサンプリングされた画像のカラムに対して行われ、得られた画像は２倍でダウンサンプリングされる。このようにして、元の画像の４分の１の大きさの４つの画像が得られる。即ち、当該の元の画像の最初の内容の主な部分を含み当該画像を近似する画像を表わす１つの低周波数のサブ画像（又は「平滑化された画像」）と、当該元の画像の水平、垂直、及び斜めの細部のみを含む３つの高周波数のサブ画像とが得られる。この分解処理は、最後の平滑化された画像から更なる有用な情報が得られないことが明らかとなるまで続けられる。
【０００４】
２次元（２Ｄ）ウェーブレット分解を用いた画像圧縮のための計算的に簡単な技術については、Ａ． Ｓａｉｄ ａｎｄ Ｗ．Ａ． Ｐｅａｒｌｍａｎによる”Ａ ｎｅｗ， ｆａｓｔ ａｎｄ ｅｆｆｉｃｉｅｎｔ ｉｍａｇｅ ｃｏｄｅｃ ｂａｓｅｄ ｏｎ ｓｅｔ ｐａｒｔｉｔｉｏｎｉｎｇ ｉｎ ｈｉｅｒａｒｃｈｉｃａｌ ｔｒｅｅｓ （＝ＳＰＩＨＴ）”， ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ ｆｏｒ Ｖｉｄｅｏ Ｔｅｃｈｎｏｌｏｇｙ， ｖｏｌ． ６， ｎｏ ３， Ｊｕｎｅ １９９６， ｐｐ． ２４３−２５０）に記載されている。この文献に記載されているように、元の画像は、ｘ及びｙを画素座標とすると一組の画素値ｐ（ｘ，ｙ）として定義され、階層サブバンド変換によって符号化され、これは以下の式（１）、
ｃ（ｘ，ｙ）＝Ω（ｐ（ｘ，ｙ））　　　　　　　　　（１）
によって表わされ、式中、Ωは変換を表し、各要素ｃ（ｘ，ｙ）は「画素座標（ｘ，ｙ）についての変換係数」と称される。
【０００５】
すると、主な目的は、最初に送信されるべき最も重要な情報を選択することであるため、上記の変換係数をその大きさに従って順序付けすることとなる（大きさの大きい係数は大きな情報内容を有し、最初に送信されるか、少なくともその最上位ビットが最初に送信されるべきである）。順序情報が復号化器へ明示的に送信される場合、画素座標の比較的小さい部分が送信されるとすぐにかなり良い質の画像が復元されうる。順序情報が明示的に送信されない場合、符号化アルゴリズムの実行パスが分岐点における比較の結果によって定義され、同じソートアルゴリズムを有する復号化器は大きさの比較の結果を受信すれば符号化器の実行パスを再現できると考えられる。順序情報は、実行パスから復元されうる。
【０００６】
上述のソートアルゴリズムの１つの重要な点は、全ての係数をソートする必要はなく、パス毎にｎをデクリメントさせつつ、２ｎ≦｜ｃｘ，ｙ｜＜２ｎ＋１の係数のみをソートすればよいことである。ｎが所与であり、｜ｃｘ，ｙ｜≧２ｎであれば（２ｎ＝有意水準と称する）、係数は有意であるといい、そうでなければ有意でないという。ソートアルゴリズムは、画素の集合を分割部分集合Ｔｍへ分割し、以下の大きさについてのテスト（２）、即ち、
【０００７】
【数１】
2004505520.tif 000003
を実行する。
【０００８】
復号化器が「否定（ｎｏ）」を受け取ると（当該の部分集合全体が有意でない）、この部分集合Ｔｍに含まれる全ての係数が有意でないことがわかる。テストの結果が「肯定（ｙｅｓ）」であれば（部分集合が有意である）、符号化器と復号化器によって共用される所定の規則を用いてＴｍが新しい部分集合ｍ，ｌへ分割され、更にこれらの新しい部分集合に対して有意性のテストが適用される。この集合分割処理は、夫々の有意な係数を同定し２値形式で符号化することを可能とするために、全ての単一座標の有意な部分集合に対して大きさのテストが行われるまで続く。
【０００９】
送信される大きさの比較の数（即ちメッセージビット数）を減少させるため、サブバンドピラミッドによって定義される階層における期待順序を用いる集合分割規則を定義してもよい。これは、有意でないと期待される部分集合が多数の要素を含み、有意であると期待される部分集合が１つの要素のみを含むよう、新しい分割規則を作ることを目的とする。大きさの比較とメッセージビットとの間の関係を明らかとするため、座標の部分集合Ｔの有意性を示すために、以下の式、
【００１０】
【数２】
2004505520.tif 000004
が用いられる。
【００１１】
更に、サブバンド間には空間的な自己相似性があることが知られており、空間的に同じ向きでピラミッドを１つ下に移動した場合に、係数は大きさによってより良く順序付けられると期待される。例えば、ピラミッドの最も高いレベルにおいて低いアクティビティの領域が同定されると期待されるとき、これらの低いアクティビティの領域は空間的に同じ位置でより低いレベルに複製される。空間的方向ツリーと称されるツリー構造は、ウェーブレット分解の階層ピラミッドに空間的な関係を定義する。図１は、反復的な４サブバンド分割を用いて構築されたピラミッドに、どのように空間的な方向ツリーが定義されるかを示す図である。ツリーの各ノードは、各ノードが子（葉）を全く有さないか４つの子を有し、常に２×２の隣接画素を形成するような、空間的に同じ向きの画素に対応する。図１中、矢印は親ノードからその子に向いている。ピラミッドの最も高いレベルにある画素は、ツリーの根であり、やはり２×２の隣接する画素としてまとめられる。しかしながら、子の分岐規則は異なり、各グループのうちの１つ（図１中は星印で示す）は全く子孫を有さない。
【００１２】
以下の座標の集合は、この符号化方法を表わすために用いられ、（ｘ，ｙ）は係数の位置を表わし、即ち、
０（ｘ，ｙ）：ノード（ｘ，ｙ）の全ての子の座標の集合；
Ｄ（ｘ，ｙ）：ノード（ｘ，ｙ）の全ての子孫の座標の集合；
Ｈ：全ての空間的な方向ツリーの根（ピラミッドの最も高いレベルのノード）の座標の集合；
Ｌ（ｘ，ｙ）＝Ｄ（ｘ，ｙ）−０（ｘ，ｙ）
である。
【００１３】
上述のように、部分集合の有意性についてテストする順序が重要であり、実際上は、有意な情報は３つの順序付けリスト、即ち、有意でない集合のリスト（ＬＩＳ）、有意でない画素のリスト（ＬＩＰ）、有意な画素のリスト（ＬＳＰ）として格納される。これらの全てのリストにおいて、各エントリは、座標（ｉ，ｊ）によって同定され、これらはＬＩＰ及びＬＳＰの場合は個々の画素を表わし、ＬＩＳの場合は集合Ｄ（ｉ，ｊ）又はＬ（ｉ，ｊ）を表わす（これらを区別するため、ＬＩＳのエントリは、Ｄ（ｉ，ｊ）を表わす場合はタイプＡ、Ｌ（ｉ，ｊ）を表わす場合はタイプＢであるとする）。ＳＰＩＨＴアルゴリズムは、実際に、３つのリストＬＩＳ、ＬＩＰ、ＬＳＰの操作に基づく。
【００１４】
２次元ＳＰＩＨＴアルゴリズムは、重要な概念に基づいており、即ち、自然画像に内在する自己相似性を用いることによってウェーブレット分解のスケールに亘って重要な情報の欠如を予測することに基づく。これは、ウェーブレット分解の最も低いスケールにおいて係数が有意でなければ、他のスケールにおいて同じ領域に対応する係数もまた有意でない可能性が高いことを意味する。基本的に、ＳＰＩＨＴアルゴリズムは、異なる解像度で同じ画像領域に対応する画素の集合を「有意水準」と称する値と比較する。
【００１５】
３次元ＳＰＩＨＴアルゴリズムは、２次元ＳＰＩＨＴアルゴリズムとあまり異なるものではない。３次元ウェーブレット分解は、フレーム群（ｇｒｏｕｐ ｏｆ ｆｒａｍｅｓ：ＧＯＦ）に対して行われる。時間的な方向に沿って、動き補償及び時間的なフィルタリングが行われる。空間的な集合（２次元）の代わりに、３次元の空間的・時間的な集合があり、空間的・時間的に同じ向きを有し親・子関係で関連付けられる係数を有するツリーを定義することもできる。図２は、３次元の場合のこれらの関係を示す図である。ツリーの根は最も低い解像度（「根」サブバンド）における近似サブバンドの画素で形成される。３次元ＳＰＩＨＴアルゴリズムでは、葉以外の全てのサブバンドにおいて、各画素は８つの子画素を有し、互いに、各画素は１つの親のみを有する。この規則では１つの例外があり、根の場合は８つのうち１つの画素は子を有さない。
【００１６】
２次元の場合と同様、空間的・時間的な方向ツリーは、階層的ウェーブレット分解についての空間的・時間的な関係を自然に定義し、以下の座標の組が用いられる。
【００１７】
０（ｘ，ｙ，ｚ，クロマ）：ノードの全ての子（ｘ，ｙ，ｚ，クロマ）の座標の集合；
Ｄ（ｘ，ｙ，ｚ，クロマ）：ノードの全ての子孫（ｘ，ｙ，ｚ，クロマ）の座標の集合；
Ｈ（ｘ，ｙ，ｚ，クロマ）：全ての空間的・時間的な方向ツリーの根（ピラミッドの最も高いレベルのノード）の座標の集合；
Ｌ（ｘ，ｙ，ｚ，クロマ）：Ｄ（ｘ，ｙ，ｚ，クロマ）−０（ｘ，ｙ，ｚ，クロマ）；
但し、（ｘ，ｙ，ｚ）は座標の位置を表わし、「クロマ」はＹ，Ｕ又はＶを示す。３つの順序リスト、即ち、ＬＩＳ（有意でない集合のリスト）、ＬＩＰ（有意でない画素のリスト）、ＬＳＰ（有意な画素のリスト）もまた定義される。これら全てのリストにおいて、各エントリは座標（ｘ，ｙ，ｚ，クロマ）で識別され、ＬＩＰ及びＬＳＰのときは個々の画素を表わし、ＬＩＳのときはＤ（ｘ，ｙ，ｚ，クロマ）集合又はＬ（ｘ，ｙ，ｚ，クロマ）集合を表わす。これらを区別するために、ＬＩＳエントリは、Ｄ（ｘ，ｙ，ｚ，クロマ）を表わす場合はタイプＡ、Ｌ（ｘ，ｙ，ｚ，クロマ）を表わす場合はタイプＢであるとする。２次元の場合について上述したように、３次元ＳＰＩＨＴはこれらの３つのリストＬＩＳ、ＬＩＰ及びＬＳＰの操作に基づく。
【００１８】
しかしながら、サブバンド間の冗長性を利用するＳＰＩＨＴアルゴリズムは、各サブバンド内の近傍画素間の依存性を失わせてしまう。一組の論理条件によって行われるリストＬＩＳ、ＬＩＰ、ＬＳＰの操作は、実際に、画素の順序の操作を殆ど予測可能でなくしてしまう。同じ３次元の子のツリーに属するが異なる空間的・時間的なサブバンドの画素は、符号化されリスト内で前後に配置され、それにより外部からのサブバンドの画素を混ぜる効果を有する。このように、同一のサブバンドの画素間の地理的な相互依存性は失われる。更に、空間的・時間的なサブバンドは時間的又は空間的なフィルタリングから生ずるため、フレームは細部の向きを与える特別な軸に沿ってフィルタリングされる。ＳＰＩＨＴアルゴリズムが適用される場合は、走査は地理的な順序に従わないため、この向き依存性は失われる。走査の順序を改善し同一のサブバンドの画素間に近傍の関係を再び確立するために、ＬＩＳの特別な初期編成と子を読み取るための特定の順序とが提案されている。
【００１９】
係数の地理的な走査を部分的に再び確立することを可能とし、本願の出願人によって２０００年４月４日に出願された欧州特許出願第００４００９３２．０号に記載された方法は、連続する所定の数の解像度レベルを生じさせる３次元（３Ｄ）ウェーブレット変換によりフレーム群（ｇｒｏｕｐｓ ｏｆ ｆｒａｍｅｓ）へ分割されたビデオシーケンスを圧縮するための符号化方法であって、方法は、ビデオシーケンスの元の画素集合から２値形式で符号化されたウェーブレット変換係数を生じさせる「集合分割階層ツリー（ｓｅｔ ｐａｒｔｉｔｉｏｎｉｎｇ ｉｎ ｈｉｅｒａｒｃｈｉｃａｌ ｔｒｅｅｓ：ＳＰＩＨＴ）」と称される階層サブバンド符号化処理に基づく方法であり、ウェーブレット変換係数は、有意でない集合のリスト（ＬＩＳ）、有意でない画素のリスト（ＬＩＰ）及び有意な画素のリスト（ＬＳＰ）と称される３つの順序付けリストによって表わされる画素を用いた大きさについてのテストによって、ツリーの形に編成され、各有意水準に対応する分割部分集合へ順序付けされ、テストは、夫々の有意な係数が２値表現で符号化されるまで続けられる分割処理によって元の画素集合を分割部分集合へ分割するために行われる符号化方法に関する。
【００２０】
より正確には、上述の特許出願明細書に記載された方法は、以下の段階を有することを特徴とする。
【００２１】
（Ａ）３次元ウェーブレット変換から生ずる空間的・時間的近似サブバンドは、ｚ＝０及びｚ＝１で示される時間的近似サブバンド中の２つのフレーム空間的近似サブバンドを含み、各画素はｘについて０からｓｉｚｅ＿ｘまで、ｙについて０からｓｉｚｅ＿ｙまで変化する座標（ｘ，ｙ，ｚ）を有し、リストＬＩＳは、ｚ＝０（ｍｏｄ２），ｘ＝０（ｍｏｄ２）及びｙ＝０（ｍｏｄ２）の形の座標を有する係数以外は上記の空間的・時間的近似サブバンドの係数で初期化され、ＬＩＳの初期化順序は、以下の通り、
（ａ）輝度成分Ｙについて、次にクロミナンス成分Ｕ及びＶについて、ｘ＝０（ｍｏｄ．２）及びｙ＝０（ｍｏｄ．２）及びｚ＝１を確実とする全ての画素をリストに入れ、
（ｂ）Ｙについて、次にＵ及びＶについて、ｘ＝１（ｍｏｄ．２）及びｙ＝０（ｍｏｄ．２）及びｚ＝０を確実とする全ての画素をリストに入れ、
（ｃ）Ｙについて、次にＵ及びＶについて、ｘ＝１（ｍｏｄ．２）及びｙ＝１（ｍｏｄ．２）及びｚ＝０を確実とする全ての画素をリストに入れ、
（ｄ）Ｙについて、次にＵ及びＶについて、ｘ＝０（ｍｏｄ．２）及びｙ＝１（ｍｏｄ．２）及びｚ＝０を確実とする全ての画素をリストに入れる。
【００２２】
（Ｂ）ウェーブレット分解の階層的サブバンドピラミッドにおける空間的・時間的な関係を定義する空間的・時間的な方向ツリーは、最も低い解像度レベルから最も高い解像度レベルへ近傍画素をまとめたままで細部の向きを考慮に入れつつ調べられ、この子係数を調べる処理は、４つの子の群について水平方向に次の群へ進むとき、４つの子の群のとき、また、最も低く微細な解像度レベルのときは、水平及び斜めの細部サブバンドの場合に係数の走査順序によって行われる。
【００２３】
エントロピー符号化モジュールでは、算術符号化は、得られる符号長が最適な長さに非常に近く、方法が特に適応モデルに適し（ソースの統計的な値が進行中に推定され）、２つの独立のモジュール（モデル化モジュール及び符号化モジュール）へ分割されうるため、ビデオ圧縮を行う場合に、ハフマン符号化よりも有効であり広く用いられている技術である。以下の説明は、主に、モデル化に関連し、一定のソース・ストリング事象及びそれらの文脈を決定すること（文脈は当該のソース・ストリングの完全な集合の冗長性を得るためのものである）と、それらの関連する統計的な値を推定する方法とを含む。
【００２４】
元のビデオシーケンスでは、画素の値は実際にそれを囲む画素の値に依存する。ウェーブレット分解の後、各時間的・空間的なサブバンドにおいて同じ性質の「幾何学的な」相互依存性が成り立つ。係数がそれらの依存性を維持するような順序で送られる場合、”Ａ ｕｎｉｖｅｒｓａｌ ｆｉｎｉｔｅ ｍｅｍｏｒｙ ｓｏｕｒｃｅ”， ｂｙ Ｍ．Ｊ． Ｗｅｉｎｂｅｒｇｅｒ ａｎｄ ａｌ．， ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， ｖｏｌ． ４１， ｎｏ３， Ｍａｙ １９９５， ｐｐ． ６３４−６５２といった文献に記載されているように、囲まれたメモリツリーソースのユニバーサル符号化の枠組みにおいて「地理的」情報を有利に用いることが可能である。有限メモリツリーソースは、次のシンボルの確率が最も最近のシンボル（文脈）の有限数の実際の値に依存するという性質を有する。有限メモリツリーソースについての２値逐次ユニバーサルソース符号化手順は、各ストリング（文脈）について当該の文脈が与えられている場合のゼロと１の発生回数を含む文脈ツリーを用いることが多い。このツリーは、ｄの先行するビットが与えられている場合に、シンボルの確率を推定することを可能とし、これは、
【００２５】
【数３】
2004505520.tif 000005
で表わされ、但しｘｎは推定されたビットの値であり、ｘｎ−１．．．ｘｎ−ｄは文脈、即ちｄのビットの先行するシーケンスを表わす。条件付け事象の数が増加した場合は、文脈希釈の問題又はモデルの費用により、推定は困難なタスクとなる。モデルの冗長性を減少させると共に適当な複雑性を維持してこの問題を解決する方法は、例えば”Ｔｈｅ ｃｏｎｔｅｘｔ−ｔｒｅｅ ｗｅｉｇｈｔｉｎｇ ｍｅｔｈｏｄ： ｂａｓｉｃ ｐｒｏｐｅｒｔｉｅｓ”， ｂｙ Ｆ．Ｍ．Ｊ． Ｗｉｌｌｅｍｓ ａｎｄ ａｌ．， ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ， ｖｏｌ． ４１， ｎｏ３， Ｍａｙ １９９５， ｐｐ． ６５３−６６４に記載される文脈ツリー重み付け方法（ｃｏｎｔｅｘｔ−ｔｒｅｅ ｗｅｉｇｈｔｉｎｇ ｍｅｔｈｏｄ：ＣＴＷ）である。
【００２６】
最終的な符号の長さを減少させるためのこの方法の原理は、調べたビットについて最も有効な文脈を用いて重み付けされた確率を推定することである（ビットを符号化するために短い文脈を用いるほうがよい場合がある。即ち、文脈の最後のビットが現在のビットに対して何らの影響も与えない場合はこれらを考慮に入れなくともよい）。ビットのソースシーケンスを
【００２７】
【数４】
2004505520.tif 000006
と表わし、符号化器と復号化器のいずれもが先行するｄのシンボル
【００２８】
【外１】
2004505520.tif 000007
にアクセスしうると想定する場合、ＣＴＷ方法は、２値シンボルの長さｋのストリングを表わす文脈ツリーの各ノードｓに対して、ツリーの葉から開始することによりノードの内在的な確率
【００２９】
【外２】
2004505520.tif 000008
に対してその２つの子で重み付けすることによって反復的に推定される重み付けされた確率
【００３０】
【外３】
2004505520.tif 000009
を関連付け、これは以下の式、
【００３１】
【数５】
2004505520.tif 000010
によって表わされる。このような重み付けされたモデルは、モデルの冗長性を最小限とすることが確かめられる。先行するシーケンス
【００３２】
【外４】
2004505520.tif 000011
によって与えられるシンボル０及び１の条件付き確率は、以下の式、
【００３３】
【数６】
2004505520.tif 000012
を用いて推定され、式中、ｎ０及びｎ１は夫々、シーケンス
【００３４】
【外５】
2004505520.tif 000013
中の０及び１のカウントである。このＣＴＷ方法は、算術符号化モジュールによって必要とされる確率を推定するために使用される。
【００３５】
本発明は、ビットストリームに寄与する情報ソースの作用の変化を反映するより効率的なビデオ符号化方法を提案することを目的とする。
【００３６】
このために、本発明は、本願の冒頭の段落に記載される符号化方法であって、各有意水準においてリスト中のシンボル０及び１の発生の確率を推定するために、４つの文脈ツリーによって表わされるＬＩＳ、ＬＩＰ、ＬＳＰ、及びサインに対応する４つのモデルが考えられ、更に、Ｕ係数とＶ係数と区別することなく輝度係数のモデルとクロミナンス係数のモデルとが更に識別される符号化方法に関する。
【００３７】
以下、添付の図面を参照して本発明について詳述する。ＳＰＩＨＴアルゴリズムを連続して実行する間、画素の座標は３つのリストＬＩＳ、ＬＩＰ、ＬＳＰのうちの１つからそのうちの他のリストへ動かされ、有意なビットが出力される。サイン（ｓｉｇｎ）ビットもまた、係数のビットを送る前にビットストリームに入れられる。統計的な観点から、３つのリストの作用及びサインビットマップの作用はかなり異なる。例えばリストＬＩＰは有意でない画素の集合を表わし、画素が有意でない画素によって囲まれる場合、その画素も有意でない可能性が高い。逆に、リストＬＳＰについては、所与の有意水準において画素の近傍のリファインメントビットが１（又はゼロ）であれば、調べられた画素のリファインメントビットもまた１（又はゼロ）であると想定するのは難しい。各有意水準においてこれらのリストでのシンボル０及び１の発生の推定確率を調べると、上述の仮定が証明されることがわかる。このことから、サインに対して与えられる追加的な独立なモデルについて考えねばならない。ここで、確率の推定のために４つの文脈ツリーによって表わされＬＩＳ、ＬＩＰ、ＬＳＰ及びサインに対応する４つの異なるモデルがあり、即ち、
ＬＩＳ→ＬＩＳ＿ＴＹＰＥ
ＬＩＰ→ＬＩＰ＿ＴＹＰＥ
ＬＳＰ→ＬＳＰ＿ＴＹＰＥ
ＳＩＧＮ→ＳＩＧＮ＿ＴＹＰＥ
である。輝度の係数についてのモデルとクロミナンスの係数についてのモデルとの間で他の識別がされねばならないが、クロミナンスの係数間でＵ平面とＶ平面とは区別されないようにされねばならない。即ち、これらの２つの色平面に属する係数は、共通の統計的な性質を共有するため、確率を推定するために同じ文脈ツリーが使用される。また、別個のモデルが考えられる場合、確率を正しく推定するのに十分な値はないであろう（Ｕ及びＶについてばらばらのモデルで行った実験は、より低い圧縮率を与える）。最終的に、８つの文脈ツリー（白黒ビデオでは４つのみである）が得られる。
【００３８】
図３に示すように、異なるビット平面上でのシンボルの発生の確率を考える場合、それらの間の差が観察され、予備的な実験により各ビット平面においてモデルを再初期化することにより更に良い圧縮結果が得られ、これによりビット平面毎に１つのモデルについて考えることについて正当化される。しかしながら、共通の特性を共用する幾つかのビット平面に対して同じモデルを用いることで、計算上の複雑さが減少され、符号化方法のパフォーマンスが改善されうる。
【００３９】
２×４のモデル（文脈ツリーによって表わされ条件付き確率を推定するために使用される）を識別すると、文脈（現在のものに先行し最も最近に読まれたｄのビットの単純なシーケンスである）に対して少なくとも同じことを行なう必要がある。しかしながら、Ｕ係数及びＶ係数の文脈は、ここでは識別される。実際は、Ｕ画像とＶ画像が同じ統計的な作用を有する（従って、Ｙ画像のものとは異なる同じ文脈ツリーを有する）という基本的な仮定がなされるが、各文脈はただ１つの色平面からのビットを含まねばならない。Ｕ係数とＶ係数に対して同じ文脈を使用することは、２つの異なる画像を混ぜる効果を有するが（同じシーケンスは、Ｕ画像とＶ画像に属する混合されたビットを含む）、これは回避できる。文脈に対する同じ識別は、各時間的サブバンドのフレームに対して行うことができる。これらは同一の統計的なモデルに従うと想定できる（この仮定はかなり強い仮定であるが、各時間的なサブバンドに対するモデル間の補足的な識別により、文脈ツリーの先行する集合を時間的なサブバンドの数で乗算することとなるため、膨大な記憶空間が必要となる）。
【００４０】
従って、文脈の集合は、Ｙ、Ｕ、Ｖ係数について、また、空間的・時間的な分解における各フレームについて識別される。実施のために、ｄのビットで形成されるこれらの文脈は、以下の構造に従って形成され、かかる構造は、
ＬＩＳ、ＬＩＰ、ＬＳＰから生ずる、又はサインビットマップから生ずるシンボルの種類；
色平面（Ｙ又は、Ｕ又は、Ｖ）；
時間的サブバンド中のフレーム、
である。これらの全ての要素の簡単な表現は、夫々の場合に最後のｄのビットのシーケンスで埋められた３次元構造ＣＯＮＴＥＸＴである。
【００４１】
ＴＹＰＥがＬＩＰ＿ＴＹＰＥ、ＴＩＰ＿ＴＹＰＥ、ＴＳＰ＿ＴＹＰＥ又はＳＩＧＮ＿ＴＹＰＥであり、クロマがＹ、Ｕ又はＶのとき、ＣＯＮＴＥＸＴ［ＴＹＰＥ］［クロマ］［フレーム番号］。
【００４２】
ＳＰＩＨＴアルゴリズムの実行が終了するたびに（有意水準を低下させる前であり、ビット平面の変化と共に）統計的モデルの変化を反映するために、文脈と文脈ツリーは再初期化され、これは各文脈ツリーについての確率のカウント及び文脈の配列の全てのエントリをゼロにリセットすることによって行われる。上述の変化を反映するために必要なこの段階は、実験によって確かめられており、即ち、実行が終了するたびに再初期化が行われた場合により良いレートが得られる。
【図面の簡単な説明】
【図１】
２次元の場合の空間な方向ツリーにおける親・子依存性の例を示す図である。
【図２】
３次元の場合の空間的・時間的な方向ツリーにおける親・子依存性の例を示す図である。
【図３】
例えば３０のビデオシーケンスに対して推定を行った場合に各モデルのタイプについてビット平面レベルに従ったシンボル１の発生の確率を示す図である。
【図３】
2004505520.tif 000014
【国際公開パンフレット】
2004505520.tif 000015
2004505520.tif 000016
2004505520.tif 000017
2004505520.tif 000018
2004505520.tif 000019
2004505520.tif 000020
2004505520.tif 000021
2004505520.tif 000022
2004505520.tif 000023
2004505520.tif 000024
2004505520.tif 000025
2004505520.tif 000026
2004505520.tif 000027
2004505520.tif 000028
2004505520.tif 000029
2004505520.tif 000030
【国際公開パンフレット（コレクトバージョン）】
2004505520.tif 000031
【国際調査報告】
2004505520.tif 000032
2004505520.tif 000033