(57)【要約】      （修正有）【課題】本発明は、簡易に又効率的に  算術符号化・復号化する方法・装置を提供する。【解決手段】バイナリ状態の符号化されるべきシンボルを算術的に符号化する方法において、確率は代表的確率状態中から１つの確率指標により表現され、方法はシンボルを符号化するステップを含み、このステップは、現時点の区間幅を、複数の代表的量子化指標の中から１つの量子化指標へとマッピングするサブステップと、量子化指標と確率指標とを用いて区間分割表へアクセスすることで、区間分割を実行して部分区間幅の値を得るサブステップとを含み、確率モデルの初期化は、量子化パラメータSliceQPとプリセットされたモデルパラメータｍおよびｎとに依存して実行される。【選択図】図６
2006050605.tif 000002
【特許請求の範囲】
【請求項１】
バイナリ状態を持ち符号化されるべきシンボルを、現時点の区間幅Ｒと上記符号化されるべきシンボルのための確率予測を表現する確率とに基づいて算術的に符号化するための方法において、
上記確率は、複数の代表的確率状態の中から１つの確率状態を示す１つの確率指標によって表現され、
上記方法は、上記符号化されるべきシンボルを符号化するステップを含み、この符号化のステップは、
上記現時点の区間幅を、複数の代表的な量子化指標の中から１つの量子化指標へとマッピングするサブステップと、
上記量子化指標と上記確率指標とを用いて区間分割表へアクセスすることで、区間分割を実行して部分区間幅の値を得るサブステップと、を含み、
確率モデルの初期化は、量子化パラメータSliceQP と、プリセットされたモデルパラメータｍおよびｎとに依存して実行され、このSliceQP はスライスの始めにプリセットされた上記量子化パラメータを示し、ｍおよびｎは上記モデルパラメータを示すことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、上記符号化の方法はさらに、
上記現時点の区間幅を上記部分区間幅の値を利用して更新し、更新された新たな区間幅を得るステップを含むことを特徴とする方法。
【請求項３】
請求項１または２に記載の方法において、
上記部分区間幅の値は、符号化されるべきシンボルのための部分区間の幅を、現時点の区間幅を持つ現時点の区間の低い確率状態で特定することを特徴とする方法。
【請求項４】
請求項１乃至３のいずれかに記載の方法において、
上記符号化されるべきシンボルの上記バイナリ状態に依存して、上記現時点の区間幅の更新がさらに実行されることを特徴とする方法。
【請求項５】
請求項１乃至４のいずれかに記載の方法において、
上記符号化の方法はさらに、
上記確率予測の適応のステップであって、この確率予測の適応のステップは、
上記符号化されるべきシンボルの確率状態が低い場合には、上記確率指標を用いて、ＬＰＳ変換規則表(Next＿State＿LPS)内のルックアップを実行して新たな確率指標を獲得し、
上記符号化されるべきシンボルの確率状態が高い場合には、上記確率指標を用いて、ＭＰＳ変換規則表(Next＿State＿MPS)内のルックアップを実行して新たな確率指標を獲得するステップを含むことを特徴とする方法。
【請求項６】
請求項５に記載の方法において、
上記符号化の方法はさらに、上記確率指標が所定の確率指標であり、上記符号化されるべきシンボルが最初に示された状態とは異なるバイナリ状態を持つ場合には、上記符号化されるべきシンボルの上記バイナリ状態に対して最初に示された状態の上記高い確率状態を示す値を適合させるステップを含むことを特徴とする方法。
【請求項７】
請求項１乃至６のいずれかに記載の方法において、
上記現時点の区間幅を更新するサブステップは、
上記新たな区間幅を、上記現時点の区間幅から上記部分区間幅の値を引き算した差と同等にするステップと、
次に、もし上記符号化されるべきシンボルの確率状態が低い場合には、上記新たな区間幅を、上記部分区間幅の値と同等とするステップと、
を含むことを特徴とする方法。
【請求項８】
請求項１乃至７のいずれかに記載の方法において、
上記現時点の区間は上記現時点の区間幅と現時点のオフセットポイントとによって表され、
上記符号化の方法はさらに
上記符号化されるべきシンボルの確率状態が低い場合には、上記現時点のオフセットポイントと、現時点の区間幅と部分区間幅の値との差とを累積し、更新された新たなオフセットポイントを得るステップを含むことを特徴とする方法。
【請求項９】
符号化されバイナリ状態を持つシンボルを、現時点の区間幅Ｒと、上記符号化されたシンボルのための確率予測を表現する確率とに基づいて算術的に復号化するための方法において、
上記確率は、複数の代表的確率状態から１つの確率状態を示す１つの確率指標によって表現され、
上記方法は、上記符号化されたシンボルを復号化するステップを含み、この復号化のステップは、
上記現時点の区間幅Ｒを複数の代表的な量子化指標から１つの量子化指標へとマッピングするサブステップと、
上記量子化指標と上記確率指標とを用いて区間分割表へアクセスすることで、区間分割を実行して部分区間幅の値を得るサブステップと、を含み、
確率モデルの初期化は、量子化パラメータSliceQP と、プリセットされたモデルパラメータｍおよびｎとに依存して実行され、このSliceQP はスライスの始めにプリセットされた上記量子化パラメータを示し、ｍおよびｎは上記モデルパラメータを示すことを特徴とする方法。
【請求項１０】
請求項９に記載の方法において、上記復号化の方法はさらに、
上記現時点の区間幅を上記部分区間幅の値を利用して更新し、更新された新たな区間幅を得るステップを含むことを特徴とする方法。
【請求項１１】
請求項９または１０に記載の方法において、
上記部分区間幅の値は、符号化されたシンボルのための部分区間の幅を、現時点の区間幅を持つ現時点の区間の低い確率状態で特定することを特徴とする方法。
【請求項１２】
請求項９乃至１１のいずれかに記載の方法において、
上記現時点の部分区間幅と新たな部分区間内の値とによって特徴付けられた上記新たな部分区間内の値に依存して、上記現時点の区間幅の更新がさらに実行されることを特徴とする方法。
【請求項１３】
請求項１２に記載の方法において、
上記復号化はさらに、
上記新たな部分区間内の値が、上記現時点の区間幅と部分区間幅の値との差と比較して大きいか小さいかに依存して、上記符号化されたシンボルのバイナリ状態を、確率が低い状態かまたは高い状態かのいずれか１つと同等にするステップを含むことを特徴とする方法。
【請求項１４】
請求項１２または１３に記載の方法において、上記復号化はさらに、上記新たな部分区間内の値を、読み込まれるべき次のビットを用いて更新するステップを含むことを特徴とする方法。
【請求項１５】
請求項１２乃至１４のいずれかに記載の方法において、
上記復号化の方法はさらに、
上記確率予測を更新するステップであって、この確率予測を更新するステップは、上記新たな部分区間内の値が上記現時点の区間幅と部分区間幅の値との差よりも大きい場合には、上記確率指標を用いて、ＬＰＳ変換規則表(Next＿State＿LPS)内のルックアップを実行して新たな確率指標を獲得し、
上記新たな部分区間内の値が上記現時点の区間幅と部分区間幅の値との差よりも小さい場合には、上記確率指標を用いて、ＭＰＳ変換規則表(Next＿State＿MPS)内のルックアップを実行して新たな確率指標を獲得するステップを含むことを特徴とする方法。
【請求項１６】
請求項１２乃至１５のいずれかに記載の方法において、
上記復号化の方法はさらに、
上記確率指標が所定の確率指標であり、上記新たな部分区間内の値が上記現時点の区間幅と部分区間幅の値との差よりも大きい場合には、上記符号化されたシンボルの異なるバイナリ状態に対して最初に示された状態の上記高い確率状態を示す値を適合させるステップを含むことを特徴とする方法。
【請求項１７】
請求項１乃至１６のいずれかに記載の方法において、
上記現時点の区間幅はｂビットの精度で表現され、上記区間分割表から得られた上記部分区間幅の値はｂ−２ビットの精度で表現されることを特徴とする方法。
【請求項１８】
請求項１乃至１７のいずれかに記載の方法において、
上記マッピングのサブステップは、上記現時点の区間幅のコンピュータ内部バイナリ表現に対してシフトおよびビットマスキング操作を適用することを含むことを特徴とする方法。
【請求項１９】
請求項１乃至１８のいずれかに記載の方法において、
上記マッピングのサブステップは、上記現時点の区間幅のコンピュータ内部バイナリ表現に対してシフト操作を適用して上記現時点の区間幅のための量子化された値を得ることと、表（Ｑtab）への下流方向アクセスにより量子化の指標を得ることを含むことを特徴とする方法。
【請求項２０】
請求項１乃至１９のいずれかに記載の方法において、
上記区間分割表内には、出現可能な全ての量子化指標と出現可能な全ての確率指標とに対応する上記現時点の区間幅のための値が、量子化の指標と表Ｒtab 内の確率指標との生成値としてファイリングされることを特徴とする方法。
【請求項２１】
請求項１乃至２０のいずれかに記載の方法において、
上記確率予測を更新するステップであって、
この確率予測の更新は変換規則によって実行され、この変換規則は、上記符号化されるべきシンボルおよび／または符号化されたシンボルに基づいて、複数の確率状態からいずれの新たな確率状態が次の符号化されるべきシンボルおよび／または符号化されたシンボルのために使用されるべきかを特定するステップをさらに含むことを特徴とする方法。
【請求項２２】
請求項１乃至２１のいずれかに記載の方法において、
上記確率予測を更新するステップであって、
この確率予測の更新は、上記確率指標を用いて、変換規則表(Next＿State＿LPS)内のルックアップを実行して新たな確率指標を得ることを含むステップをさらに含むことを特徴とする方法。
【請求項２３】
請求項１乃至２２のいずれかに記載の方法において、
上記出現可能な量子化指標の数および／または上記確率状態の数が、上記符号化のプリセットされた精度および／または有効情報蓄積容量に依存して選択されることを特徴とする方法。
【請求項２４】
請求項１乃至２３のいずれかに記載の方法において、
上記更新された新たなオフセットポイントと上記更新された新たな区間幅とを再正規化するサブステップをさらに含むことを特徴とする方法。
【請求項２５】
請求項９乃至２４のいずれかに記載の方法において、上記復号化は、
１．ＬＰＳの決定のステップと、
２．Ｒの量子化のステップと、
q_index = Qtab[R≫q]
３．ＲLPSとＲの決定のステップと、
RLPS = Rtab [q＿index, p＿state]
R = R−RLPS 
４．上記部分区間の位置に依存するビットの決定のステップであって、
(V ≧ R)のとき、
bit ← LPS
V ← V − R
R ← RLPS
(p_state = 0) のときvalMPS ← 1 - valMPS
p_state ← Next_State_LPS[p_state]
その他は
bit ← MPS
p_state ← Next_State_MPS [p_state] となるステップと、
５．Ｒの再正規化と、１ビットの読み出しと、Ｖの更新のステップであって、
q_index はＱtab から読み出された量子化値の指標を示し、
p_state は上記現時点の確率状態を示し、
RLPSは上記ＬＰＳに対応する区間幅を示し、
ValMPSは上記ＭＰＳに対応するビットを示し、
V は上記現時点の部分区間の内部からの値を示すステップと、
を含むことを特徴とする方法。
【請求項２６】
請求項１乃至２５のいずれかに記載の方法において、
符号化および／または復号化において、上記量子化の指標q＿index へのマッピングが次の計算規則：
q_index = (R≫q) ＆ Qmask
に従って実行され、Qmaskは確率状態の数に依存して適切に選択されたビットマスクを示し、Ｒは上記現時点の区間幅を示し、q はビットの数を示すことを特徴とする方法。
【請求項２７】
請求項１乃至２６のいずれかに記載の方法において、
もし均一な確率分布が存在している場合には、
符号化において、以下に示す計算規則：
R ← R ≫ 1 
(bit = 1) のとき
L ← L + R
が実行されるか、または、以下に示す計算規則：
L ← L ≪ 1
(bit = 1)のとき 
L ← L + R
が実行され、最後の段階で２倍の決定しきい値を用いた再正規化が実行され、ＬとＲとは２倍されず、かつ、請求項９に記載の復号化において、以下に示す計算規則：
R ← R ≫ 1 
(V ≧ R)のとき、
bit← 1
V ← V− R
その他は
bit← 0 
が実行されるか、または、以下に示す計算規則：
１．１つのビットの読み出しとＶの更新
２．上記部分区間の位置に従うビットの決定: 
(V ≧ R)のとき、
bit← 1
V ← V− R
その他は
bit← 0 
が実行されることを特徴とする方法。
【請求項２８】
請求項１乃至２７のいずれかに記載の方法において、
上記確率モデルの初期化が次のステップ：
１．preState = min(max(1, ((m * SliceQP)≫4)+n),2*N)
２. (preState ＜＝ N) のとき
p_state = N − preState 
valMPS = 0 
その他は
p_state = preState−(N＋1)
valMPS = 1
を含み、valMPSはＭＰＳに対応するビットを示し、SliceQP はスライスの始めにプリセットされた上記量子化パラメータを示し、ｍおよびｎは上記モデルパラメータを示すことを特徴とする方法。
【請求項２９】
請求項１乃至２８のいずれかに記載の方法において、
上記確率状態の上記確率予測が有限状態機械（ＦＳＭ）を用いて実行されることを特徴とする方法。
【請求項３０】
請求項１乃至２９のいずれかに記載の方法において、
上記確率状態の生成はオフラインで実行されることを特徴とする方法。
【請求項３１】
請求項１乃至３０のいずれかに記載の方法において、
上記確率状態の選択は、符号化されるべきデータの統計および／または上記確率状態の数に依存することを特徴とする方法。
【請求項３２】
バイナリ状態を持ち符号化されるべきシンボルを、現時点の区間幅Ｒと上記符号化されるべきシンボルのための確率予測を表現する確率とに基づいて算術的に符号化するための装置において、
上記確率は、複数の代表的確率状態の中から１つの確率状態を示す１つの確率指標によって表現され、
上記装置は、上記符号化されるべきシンボルを符号化する手段を含み、この手段は、
上記現時点の区間幅を、複数の代表的な量子化指標の中から１つの量子化指標へとマッピングする手段と、
上記量子化指標と上記確率指標とを用いて区間分割表へアクセスすることで、上記区間分割を実行して部分区間幅の値を得る手段と、を含み、
確率モデルの初期化は、量子化パラメータSliceQP と、プリセットされたモデルパラメータｍおよびｎとに依存して実行され、このSliceQP はスライスの始めにプリセットされた上記量子化パラメータを示し、ｍおよびｎは上記モデルパラメータを示すことを特徴とする装置。
【請求項３３】
バイナリ状態を持ち符号化されたシンボルを、現時点の区間幅Ｒと上記符号化されたシンボルのための確率予測を表現する確率とに基づいて算術的に復号化するための装置において、
上記確率は、複数の代表的確率状態の中から１つの確率状態を示す１つの確率指標によって表現され、
上記装置は、上記符号化されたシンボルを復号化する手段を含み、この手段は、
上記現時点の区間幅を、複数の代表的な量子化指標の中から１つの量子化指標へとマッピングする手段と、
上記量子化指標と上記確率指標とを用いて区間分割表へアクセスすることで、上記区間分割を実行して部分区間幅の値を得る手段と、を含み、
確率モデルの初期化は、量子化パラメータSliceQP と、プリセットされたモデルパラメータｍおよびｎとに依存して実行され、このSliceQP はスライスの始めにプリセットされた上記量子化パラメータを示し、ｍおよびｎは上記モデルパラメータを示すことを特徴とする装置。
【請求項３４】
コンピュータが請求項１または９に記載の方法を実行できるように、コンピュータを作動させるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、バイナリ状態を算術的に符号化および復号化するための方法と装置、および対応するコンピュータプログラムに関するものであり、特にこれらは、デジタルデータ圧縮のために使用可能なものである。
【背景技術】
【０００２】
本発明は、バイナリ算術符号化のための新規で効果的な方法を提案するものである。デジタルデータ圧縮の様々な適用分野の多くの分野において、バイナリ算術符号化に対する需要がある。特に、デジタル画像圧縮の分野における適用は強い関心を呼んでいる。例えばＪＰＥＧ−２０００，ＪＰＥＧ−ＬＳ，ＪＰＩＧ等の、画像符号化のための多くの規格の中で、バイナリ算術符号化のための方法が定義されている。より新しい規格化活動の中でも、これらの符号化技術がビデオ符号化の分野において将来的にも使用されるであろうことが明らかである（非特許文献１のＨ．２６４／ＡＶＣにおけるＣＡＢＡＣを参照）。
【０００３】
これまで現実に使用されて来たハフマン符号化（非特許文献２参照）とは対照的に、算術符号化（ＡＣ）は、基本的に下記３つの特徴を備えるものである。
１．算術符号化を用いることにより、現在のソース（情報源）統計に対するダイナミックな適応が、簡素な適応メカニズムによって達成できる。
２．算術符号化によって、符号化されるべき各々のシンボルに対する非整数個のビット割り当てが可能になる。そのため、エントロピーの近似を、理論的に付与されたより低位のバウンド（エントロピー近似）として示す符号化結果を達成するのに適切と言える（非特許文献３参照）。
３．適切なコンテキストモデルを使用することで、さらなるデータ削減のためのシンボル間の統計的結合が、算術符号化において使用可能となる（シンボル間の冗長性）（非特許文献４参照）。
【０００４】
算術符号化の適用の欠点として、一般的にハフマン符号化と比較して計算量が増大することがあげられる。
【０００５】
算術符号化の概念は、シャノンによる情報理論に関する基本的な文書（非特許文献５参照）に遡るものである。最初の概念的な構築方法は、まずエリアスによって出版された（非特許文献６参照）。算術符号化の最初のＬＩＦＯ（後入れ先出し）の異型は、リサネンによって構築され（非特許文献７参照）、その後別の著者によってＦＩＦＯ（先入れ先出し）の実装へと修正された（非特許文献８、９、１０参照）。
【０００６】
上述の全ての文献は、共通して再帰的部分区間分解(recursive partial interval decomposition)について言及している。バイナリアルファベットの２つの結果｛“０”，“１”｝の、与えられた確率P（“０”）とP（“１”）とに対応して、最初に付与された区間、例えば区間［０，１］が、個々のイベントの出現に依存する部分区間(partial interval)へと再帰的に分解される。このとき、出現する個々のイベントの確率（出現率）の結果として生じる部分区間のサイズは、個々のイベントのシーケンスの確率に比例している。各イベントＳiは、確率Ｐ（Ｓi）により、全体的な割合に対し、Ｓiの理論的情報コンテントＨ（Ｓi）のＨ（Ｓi）＝−log（Ｐ（Ｓi））分だけ寄与を加えるので、部分区間を現すためのビット数ＮBitと、個々のイベントのシーケンスのエントロピーとの間の関係は、次の方程式の右側に示される。
【数１】
2006050605.tif 000003
【０００７】
しかし、基本原則は、結果として生じる部分区間の表現において、第１に（理論的に）無限の正確性を要求する。また、上記の方法は次の欠点を持つ。即ち、結果として生じる部分区間を現すためのビットは、最後の結果の符号化が終わるまで出力されないということである。現実的な適用を目的とするとき、ビットの増分出力のためのメカニズムであって所定の正確性の数値を持つ表現を同時的に出力できるものを開発することが極めて重要であった。これらは、非特許文献３、７、１１で初めて紹介されたものである。
【０００８】
図１には、バイナリ算術符号化の基本操作が示されている。図示された操作の中では、現時点の部分区間は２つの値ＬとＲとで表現されている。このＬはオフセットポイント（下限値）を表し、Ｒはその部分区間のサイズ（幅）を表し、どちらの量もそれぞれｂビット整数を用いて表現されている。ビット∈｛０，１｝の符号化は、基本的に次の５つのサブステップで実行される。第１ステップでは、確率予測(probability estimation) を用いて、確率がより低いシンボルの値が決定される。このシンボルは、ＭＰＳ（最高確率シンボル）に対するＬＰＳ（最低確率シンボル）とも呼ばれるものであり、第２ステップでは、対応する部分区間の幅ＲLPS を計算するために確率予測ＰLPS が使用される。第３ステップでは、符号化されるべきビットの値に依存して、２つの値ＬとＲとが更新される。第４ステップでは、この符号化されたばかりのビットの値に依存して確率予測が更新され、最後のステップにおいては、コード区間(code interval) Ｒに対していわゆる再正規化(renormalization)が実行される。すなわち、条件Ｒ∈｛２b-2，２b-1｝が満たされるように、Ｒは例えば再スケーリングされる。このとき、各スケーリング操作について１ビットが出力される。さらなる詳細に関しては、非特許文献１０を参照されたい。
【０００９】
上述した方法の主な欠点は、区間幅(interval width)ＲLPSを計算する時に、符号化されるべき各シンボルについて乗算が必要とされる点が挙げられる。一般に、乗算の操作は、特にそれらがハードウエアの中で実行された場合、コストがかさみ、時間も掛かる要因となる。複数の研究論文の中で、この乗算の操作を適切な近似化に置き換える方法が模索されている（非特許文献１１、１２、１３、１４を参照）。そして、この点に言及して発表された方法は、概ね次の３つの種類に分類することができる。
【００１０】
乗算を含まないバイナリ算術符号化のための提案の第１グループは、予測された確率ＰLPSを近似して、図１内の第２ステップでの乗算を１個（または複数個）のシフトおよび加算操作(shift and addition operation)によって置き換える方法に基づいている（非特許文献１１、１４）。このため、最も簡単な場合、確率ＰLPS は２-qの形式で示され整数ｑ＞０となる値によって近似される。
【００１１】
近似を用いる方法の第２のカテゴリでは、Ｒの値領域を（１／２−ｒ）の形式で示される離散値で近似することが提案されている。この場合、ｒ∈｛０｝∪｛２-k｜ｋ＞０，ｋは整数｝が選択される（非特許文献１５、１６を参照）。
【００１２】
近似を用いる方法の第３のカテゴリに関しては、いかなる算術操作も表へのアクセスに置き換えられるという事実が知られている。この方法のグループには、一方ではＪＰＥＧ標準内で使用されるＱ−コーダおよび関連する方法、例えばＱＭ−コーダおよびＭＱ−コーダが帰属し（非特許文献１２を参照）、他方では準算術コーダが帰属している（非特許文献１３を参照）。準算術コーダの方法では、許容可能な規模の表を得るために、Ｒを表すために使用されるビット数ｂの劇的な制限が実行される。他方Ｑ−コーダでは、Ｒが少なくとも概算して１で近似されてもよいように、Ｒの再正規化が実行される。このようにして、ＲLPSを決定するための乗算が回避される。加えて、有限状態機械(finite state machines)の形式をもつ表を使用した確率予測が実行される。さらなる詳細は、非特許文献１２を参照されたい。
【非特許文献１】T. Wiegand, G. Sullivan 共著、「合同ビデオ国際規格最終草案（ＦＤＩＳ）」ＩＴＵ−Ｔ（国際電気通信連合−電気通信標準化部門）のＨ．２６４検討部会とＩＳＯ／ＩＥＣ  １４４９６−１０  ＡＶＣ（国際標準化機構−動画像符号化部門）とで構成される合同検討チーム（ＪＴＶ−Ｇ０５０）により２００３年３月発行
【非特許文献２】D. A. Huffman著、「最小冗長性符号」Proc. IRE, 第４０号、１０９８−１１０１頁、１９５２年発行
【非特許文献３】I.H. Witten,  R.M. Neal, J.G. Cleary 共著、「データ圧縮のための算術符号化」Communication of the ACM、第３０号、６番、５２０−５４０頁、１９８７年発行
【非特許文献４】G. G. Langdon, J. Rissanen 共著、「簡素で一般的なバイナリ情報源符号」IEEE 情報理論部会の会報、第２８号、８００-８０３頁、１９８２年発行
【非特許文献５】C. E. Shannon著、「コミュニケーションの数学的理論」ベルシステム技術ジャーナル第２７号、３７９-４２３、６２３−６５６頁、１９４８年発行
【非特許文献６】P. Elias著、「情報理論と符号化」N. Abramson(編者) 内、New York、Mc-Gra-Hill社、１９６３年発行
【非特許文献７】J. Rissanen著、「一般的クラフトの不等と算術符号化」IBM  J. Res. Develop. 第２０号、１９８−２０３頁、１９７６年発行
【非特許文献８】R. C. Pasco著、「情報源符号化と高速データ圧縮のためのアルゴリズム」米国スタンフォード大学博士論文、１９７６年発行
【非特許文献９】G. G. Langdon著、「算術符号化入門」IBM J. Res. Develop. 第２８号、１３５−１４９頁、１９８４年発行
【非特許文献１０】A. Moffat, R. M. Neal, I. H. Witten共著、「算術符号化再考」Proc. IEEEデータ圧縮会議、Snowbird（米国）２０２−２１１頁１９９６年発行
【非特許文献１１】J. Rissanen, K. M. Mohiuddin共著、「乗算を含まないマルチアルファベット算術符号」IEEE コミュニケーション部会の会報、第３７号、９３−９８頁、１９８９年発行
【非特許文献１２】W. B. Pennebaker, J. L. Mitchell, G.G.Langdon, R. B. Arps共著、「Ｑコーダ適応型バイナリ算術コーダの基本原理概説」IBM J. Res. Develop. 第３２号、７１７−７２６頁、１９８８年発行
【非特許文献１３】P. G. Howard, J. S. Vitter共著、「算術符号化の現実的応用」、「イメージとテキスト圧縮」J. Storer（編者）内、Norwell（米国）、Kluwer社１９９２年発行
【非特許文献１４】L. Huynh, A. Moffat共著、「バイナリ算術符号化を近似するための出現率−割合アプローチ」IEEE 情報理論部会の会報、第４３号、１６５８−１６６２頁、１９９７年発行
【非特許文献１５】D. Chevion, E. D. Karnin, E. Walach共著、「高効率で乗算を含まない算術符号化の近似法」Proc. IEEEデータ圧縮会議、Snowbird（米国）４３−５２頁１９９１年発行
【非特許文献１６】G. Feygin, P. G. Gulak, P. Chow共著、「乗算を含まない算術符号化の近似法における過符号長およびVLSI複雑性の最小化」情報処理マガジン第３０号、８０５−８１６頁、１９９４年発行
【非特許文献１７】D. L. Duttweiler, Ch. Chamzas共著、「算術および適応型−ハフマンエントロピーコーダにおける確率予測」IEEE イメージ処理部会の会報、第４号、２３７−２４６頁、１９９５年発行
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明の目的は、上述の欠点が解消できるような、バイナリ状態を算術的に符号化および復号化するための方法と装置、および対応するコンピュータプログラムと対応するコンピュータで解読可能な情報蓄積媒体とを提供することであり、特にこれらは、（ａ）乗算を必要とせず、（ｂ）計算労力を必要とせずに確率予測ができ、（ｃ）同時に、典型的に生起するシンボル確率の広い領域に対し、最大の符号化効率を保証するものである。
【課題を解決するための手段】
【００１４】
本発明によれば、この目的は請求項１, ９, ３２〜３４に記載の特徴と序文に記載の特徴との組み合わせにより達成される。本発明の望ましい実施例は、従属項の中で示される。
【００１５】
バイナリ状態を算術的に符号化および復号化するための１つの方法は、以下のように実行されることが望ましい。即ち、第１ステップで、区間幅Ｒの特定 (specification)のためのプリセット（事前設定）可能な値領域をＫ個の代表的区間幅(representative interval widths)｛Ｑ1，．．．，Ｑk｝に分割し、確率の特定のためのプリセット可能な値領域をＮ個の代表的確率状態(representative probability states)｛Ｐ1，．．．，Ｐn｝に分割し、全ての各区間幅Ｒに対して１つのＱk（１≦ｋ≦Ｋ）を割り当てかつ全ての各確率に対して１つのＰn（１≦ｎ≦Ｎ）を割り当てる割当規則を付与し、次に第２ステップでは、符号化プロセスまたは復号化プロセスの中でそれぞれ得られるべき新たな区間幅を代表的区間幅Ｑk（１≦ｋ≦Ｋ）と代表的確率状態Ｐn（１≦ｎ≦Ｎ）とを用いて乗算と除算以外の算術操作によって計算することで、バイナリ状態の符号化または復号化を実行し、このとき代表的区間幅Ｑkは基礎になる区間幅Ｒによって決定され、代表的確率状態Ｐnは符号化または復号化されるべきシンボルの根底にある確率予測を用いて上記付与された割当規則に従って決定される。
【００１６】
本発明の他の望ましい実施例は、以下の特徴を持つ。すなわち、関連する区間幅Ｑkを決定するための幅Ｒを備えた現時点に評価されるべき区間に基づいて、Ｒのコンピュータ内部バイナリ表現に対して適用されるシフトおよびビットマスキング操作により、指標q_indexが決定される。
【００１７】
また、関連する区間幅Ｑkを決定するための幅Ｒを備えた現時点に評価されるべき区間に基づいて、Ｒのコンピュータ内部バイナリ表現に対して適用されるシフト操作と表Ｑtabへの下流方向アクセスとにより指標q_indexが決定され、このとき表Ｑtabは、シフト操作によって予め量子化されたＲの値に対応する区間幅の指標を含む場合も、好都合である。
【００１８】
符号化または復号化されるべきシンボルの根底にある確率予測が、指標p_state を用いて確率状態Ｐnに関連づけられるとき、特に有利となる。
【００１９】
ＬＰＳに対応する区間幅ＲLPSの決定が表Ｒtabへのアクセスにより実行される時もまた、有利となる。この時、表Ｒtabは、ＲのＫ個の全ての量子化された値に対応する値と、区間幅ＲLPSのＮ個の異なる確率状態に対応する値とを、生成値(product values)（Ｑk*Ｐn）として含む。ＬＰＳに対応する区間幅ＲLPSの決定が表Ｒtabへのアクセスにより実行され、この時、上記の表を評価するために量子化の指標q_indexと確率状態の指標p_state とが使用される場合、計算量は特に低減される。
【００２０】
本発明の方法はさらに、Ｎ個の異なる代表的確率状態について、変換規則(transition rules)を提案している。この変換規則は、符号化または復号化された現時点のシンボルに基づき、符号化または復号化されるべき次のシンボルのために、新たな確率状態のいずれを使用すべきかを示す。よって、最低確率シンボル（ＬＰＳ）が発生した時、現時点に付与された確率状態Ｐnの指標ｎに加えて新たな確率状態Ｐmの指標ｍを含む表Next_State_LPSが作成される場合、および／または最高確率シンボル（ＭＰＳ）が発生した時、現時点に付与された確率状態Ｐnの指標ｎに加えて新たな確率状態Ｐmの指標ｍを含む表Next_State_MPSが作成される場合は、好都合となる。
【００２１】
表を利用した(table-aided)バイナリ算術符号化および復号化のための方法の最適化は、特に、Ｋ個の全ての区間幅と、Ｎ個の全ての異なる確率状態とに対応する区間幅ＲLPSの値が、表Ｒtab内に生成値（Ｑk*Ｐn）としてファイリングされるという事実から達成される。
【００２２】
量子化値の数Ｋおよび／または代表的確率状態の数Ｎが、事前に設定された符号化の精度および／または有効情報蓄積容量に依存して選択される場合、さらなる最適化が達成される。
【００２３】
本発明の符号化方法のある特別な実施例は、以下のステップを含む：
１．ＬＰＳの決定
２．Ｒの量子化：
q_index = Qtab[R≫q]
３．ＲLPS とＲの決定：
ＲLPS = Ｒtab [q_index, p_state]
Ｒ = Ｒ −ＲLPS
４．新部分区間の計算
（bit : ＬＰＳ）のとき
L ← L + R
Ｒ ← ＲLPS
p_state ←Next_State_LPS [p_state]
(p_state = 0) のとき valMPS ←1 − valMPS 
その他は
p_state ← Next_State_MPS [p_state]
５．ＬとＲの再正規化とビットの書き込み、このとき
q_index はＱtab から読み出された量子化値の指標を示し、
p_state  は現時点の確率状態を示し、
RLPS はＬＰＳに対応する区間幅を示し、
ValMPS  はＭＰＳに対応するビットを示す。
【００２４】
本発明の復号化方法のある特別な実施例は、以下のステップを含む：
１．ＬＰＳの決定
２．Ｒの量子化：
q_index = Qtab[R≫q]
３．ＲLPS とＲの決定：
RLPS = Rtab [q_index, p_state]
R = R - RLPS
４．部分区間の位置に依存するビットの決定
（Ｖ ≧ Ｒ）のとき
bit ← LPS
V ← V − R
R ← RLPS
(p_state = 0) のときvalMPS ← 1 - valMPS
p_state ← Next_State_LPS[p_state]
その他は
bit ← MPS
p_state ← Next_State_MPS [p_state]
５．Ｒの再正規化と、１ビットの読み出しと、Ｖの更新、このとき
q_index はＱtab から読み出された量子化値の指標を示し、
p_state  は現時点の確率状態を示し、
RLPS はＬＰＳに対応する区間幅を示し、
ValMPS  はＭＰＳに対応するビットを示し、
Vは現時点の部分区間の内部からの値を示す。
【００２５】
本発明の方法の他の特別な実施例においては、符号化および／または復号化において、量子化の指標q_indexの計算が次の計算規則に従い、第２サブステップで実行される。
q_index = (R ≫ q) ＆ Qmask
ここでQmask とはＫに依存して適切に選択されたビットマスクを示す。
【００２６】
もし均一な確率分布(probability distribution)が存在している場合には、表を利用したバイナリ算術符号化および復号化のための方法のさらなる最適化は、符号化において、以下に示す計算規則、即ち、
R ← R ≫ 1
(bit = 1)のとき
L ← L + R
という計算規則に従って実行されるか、または、以下に示す計算規則、即ち、
L ← L ≪ 1
(bit = 1)のとき
L ← L + R
に従って実行され、最後の段階において、再正規化が２倍された決定しきい値(doubled decision threshold)を用いて実行され、ＬとＲとは２倍されないという計算規則に従って実行され、かつ、請求項２５に記載の復号化においては、サブステップ１〜４が以下に示す計算規則、即ち、
R ← R ≫ 1 
(V ≧ R)のとき、
bit← 1
V ← V− R
その他は
bit← 0 
という計算規則に従って実行されるか、または、請求項２５に記載の復号化においては、サブステップ１〜５が以下に示す計算規則、即ち、
1.１つのビットの読み出しとＶの更新
2.部分区間の位置に従うビットの決定:
(V ≧ R) のとき
bit← 1
V ← V− R
その他は
bit ← 0
という計算規則に従って実行されるという事実から達成される。
【００２７】
さらに、確率モデルの初期化が量子化パラメータSliceQPと、プリセットされたモデルパラメータｍおよびｎとに依存して実行される場合は好都合である。このとき、SliceQPはスライスの始めにプリセットされた量子化パラメータを示し、ｍおよびｎはモデルパラメータを示している。
【００２８】
また、確率モデルの初期化が次のステップを含む場合は有利である。
１．preState = min(max(1, ((m * SliceQP)≫4)+n),2*N)
２. (preState ＜＝ N) のとき
p＿state = N − preState 
valMPS = 0 
その他は
p＿state = preState−(N＋1)
valMPS = 1
このときvalMPS はＭＰＳに対応するビットを示し、SliceQPはスライスの始めにプリセットされた量子化パラメータを示し、ｍおよびｎはモデルパラメータを示している。
【００２９】
バイナリ状態の算術的符号化および復号化のためのある装置は、少なくとも１つのプロセッサを備え、このプロセッサは、算術的符号化および復号化のための以下の方法を実行できる。即ち、第１ステップでは、区間幅Ｒの特定のためのプリセット可能な値領域をＫ個の代表的区間幅｛Ｑ1，．．．，ＱK｝に分割し、確率の特定のためのプリセット可能な値領域をＮ個の代表的確率状態｛Ｐ1，．．．，ＰN｝に分割し、全ての各区間幅Ｒに対して１つのＱk（１≦ｋ≦Ｋ）を割り当てかつ全ての各確率に対して１つのＰn（１≦ｎ≦Ｎ）を割り当てる割当規則を付与する。次に第２ステップでは、符号化プロセスまたは復号化プロセスの中でそれぞれ得られるべき新たな区間幅を代表的区間幅Ｑk（１≦ｋ≦Ｋ）と代表的確率状態Ｐn（１≦ｎ≦Ｎ）とを用いて乗算と除算以外の算術操作によって計算することで、バイナリ状態の符号化または復号化を実行し、このとき代表的区間幅Ｑkは基礎になる区間幅Ｒによって決定され、代表的確率状態Ｐnは符号化または復号化されるべきシンボルの根底にある確率予測を用いて上記付与された割当規則に従って決定される。
【００３０】
バイナリ状態の算術的符号化および復号化のための１つのコンピュータプログラムは、それがコンピュータのメモリに記憶された後には、そのコンピュータが算術的符号化および復号化のための以下の方法を実行できるようにする。即ち、第１ステップで、区間幅Ｒの特定のためのプリセット可能な値領域をＫ個の代表的区間幅｛Ｑ1，．．．，ＱK｝に分割し、確率の特定のためのプリセット可能な値領域をＮ個の代表的確率状態｛Ｐ1，．．．，ＰN｝に分割し、全ての各区間幅Ｒに対して１つのＱk（１≦ｋ≦Ｋ）を割り当てかつ全ての各確率に対して１つのＰn（１≦ｎ≦Ｎ）を割り当てる割当規則を付与する。次に第２ステップでは、符号化プロセスまたは復号化プロセスの中でそれぞれ得られるべき新たな区間幅を代表的区間幅Ｑk（１≦ｋ≦Ｋ）と代表的確率状態Ｐn（１≦ｎ≦Ｎ）とを用いて乗算と除算以外の算術操作によって計算することで、バイナリ状態の符号化または復号化を実行し、このとき代表的区間幅Ｑkは基礎になる区間幅Ｒによって決定され、代表的確率状態Ｐnは符号化または復号化されるべきシンボルの根底にある確率予測を用いて上記付与された割当規則に従って決定される。
【００３１】
このようなコンピュータプログラムは、例えば、（有料または無料で自由にアクセス可能かまたはパスワードで保護された状態で）データあるいはコミュニケーションネットワークの中にダウンロードできるよう提供可能である。また、このように提供されるコンピュータプログラムは、次の方法により使用可能となる。すなわち、請求項３４に記載のコンピュータプログラムが、例えばインターネット等の送信用ネットワークからそのネットワークに接続されたデータ処理手段へとダウンロードされる方法である。
【００３２】
バイナリ状態の算術的符号化および復号化のための方法を実行するためには、望ましくはコンピュータが解読できる情報蓄積媒体が使用され、この情報蓄積媒体にプログラムが蓄積され、そのプログラムは、それがコンピュータのメモリに記憶された後には、そのコンピュータが算術的符号化および復号化のための以下の方法を実行できるようにする。即ち、第１ステップで、区間幅Ｒの特定のためのプリセット可能な値領域をＫ個の代表的区間幅｛Ｑ1，．．．，ＱK｝に分割し、確率の特定のためのプリセット可能な値領域をＮ個の代表的確率状態｛Ｐ1，．．．，ＰN｝に分割し、全ての各区間幅Ｒに対して１つのＱk（１≦ｋ≦Ｋ）を割り当てかつ全ての各確率に対して１つのＰn（１≦ｎ≦Ｎ）を割り当てる割当規則を付与する。次に第２ステップでは、符号化プロセスまたは復号化プロセスの中でそれぞれ得られるべき新たな区間幅を代表的区間幅Ｑk（１≦ｋ≦Ｋ）と代表的確率状態Ｐn（１≦ｎ≦Ｎ）とを用いて乗算と除算以外の算術操作によって計算することで、バイナリ状態の符号化または復号化を実行し、このとき代表的区間幅Ｑkは基礎になる区間幅Ｒによって決定され、代表的確率状態Ｐnは符号化または復号化されるべきシンボルの根底にある確率予測を用いて上記付与された割当規則に従って決定される。
【００３３】
本発明の新たな方法は、次の３つの特徴の組み合わせにより顕著性を有する。まず、Ｑ-コーダの場合と同様に、確率予測が有限状態機械（ＦＳＭ）を用いて実行され、有限状態機械のＮ個の代表的な状態の生成はオフラインで実行される。対応する変換規則は表の形式でファイリングされる。
【００３４】
本発明の２つ目の特徴は、区間幅ＲをＫ個の予め定義された量子化値へ事前量子化 (prequatization)することである。このため、ＫとＮとを適切に数値設定することで、乗算を含まないＲLPS決定のために、予め計算された生成値Ｒ×ＰLPSのＫ×Ｎ個の全ての組み合わせを含む表が生成可能となる。
【００３５】
本発明が、異なるコンテキストモデルが使用されかつ（略）均一の確率分布が割り当てられた環境の中で使用される場合のために、追加的（選択的）要素として、符号器の中に別の分枝が準備され、この分枝においては、同等の確率分布を想定し、変数ＬおよびＲの決定と再正規化とが、計算労力において大きく低減される。
【００３６】
全体として、本発明は特に、一方では高い符号化効率を、他方では計算労力の低減を、同時に実現できるという長所を提供できる。
【図面の簡単な説明】
【００３７】
以下に、図に示された実施例を参照しながら本発明を詳細に説明する。
【図１】バイナリ算術符号化のための基本的な操作を示す図である。
【図２】表を利用した算術符号化のための修正された構成を示す図である。
【図３】表を利用した算術復号化の原理を示す図である。
【図４】均一の確率分布を持つバイナリデータを符号化または復号化する原理をそれぞれ示す図である。
【図５】均一の確率分布を持つバイナリデータを符号化または復号化する他の実施例の原理をそれぞれ示す図である。
【図６】量子化パラメータＳliceＱＰと、プリセットされたモデルパラメータｍおよびｎとに依存した確率モデルの初期化を示す図である。
【発明を実施するための最良の形態】
【００３８】
まず、理論的背景について詳細に説明する。
【００３９】
表を利用した確率予測
既に上述したように、算術符号化の効果は、符号化されるべきシンボルの出現確率の予測に依存するものであり、この予測はできるだけ正確なことが望ましい。動的情報源統計(non-stationary source statistics)への適応を可能にするため、この出現確率の予測は、符号化プロセスの過程において更新されてゆく必要がある。この目的のために使用される通常の方法では、符号化結果のスケールされた出現頻度カウンタ(frequency counter)を用いた操作が一般的である（非特許文献１７参照）。ＣLPSおよびＣMPSがＬＰＳおよびＭＰＳの出現頻度のカウンタを示す場合には、これらのカウンタを用いて、上記出現確率の予測は次の式により実行されてもよい。
【数２】
2006050605.tif 000004
【００４０】
またこの後、図１に示された区間分割の操作が実行されてもよい。現実的な目的から、式（１）で必要とされる割算は不利になる。しかし、全体的カウンタＣTotal = ＣMPS + ＣLPSの予め決定されたしきい値Ｃmaxを超えた時には、カウンタ読み取りの再スケーリングを実行することがしばしば好都合であり必要とされる。（このとき注目すべきは、ＬとＲとをｂビット表示した場合、正確に示されることが可能な最小確率は２-b+2であり、その結果、この最小確率を下回ることを回避するためには、カウンタ読み取りの再スケーリングが必要になる。）Ｃmaxを適切に選択することで、ＣTotalの逆数(reciprocal values) は表に示されることが可能になり、その結果、式（１）で要求された割算は、表へのアクセスと、乗算とシフト操作とによって置き換えることが可能となる。しかし、これらの算術も回避するために、本発明においては、完全に表を利用した方法が確率予測に使用される。
【００４１】
この目的のために、試行段階(training phase)において、代表的確率状態 {ＰK｜０≦ k ＜Ｎmax}が予め選択される。このとき、上記確率状態の選択は、一方では符号化されるべきデータの統計に依存し、他方では確率状態のデフォルト最大数Ｎmaxのサイド条件(side conditions)に依存する。加えて、変換規則が定義され、この規則は、現時点に符号化されたシンボルに基づき、符号化されるべき次のシンボルのためにどのような新たな状態が使用されるべきかを示す。これらの変換規則は、２つの表、即ち{Next_State_LPSk｜0 ≦ k ＜ Ｎmax}と{Next_State_MPSk｜０≦ k ＜Ｎmax}という形で提供されており、これらの表は、現時点に付与された確率状態の指標ｎに対し、ＬＰＳまたはＭＰＳが発生した時、新たな確率状態Ｐmの指標ｍをそれぞれ提供する。ここで注意すべきは、算術符号器または算術復号器におけるそれぞれの確率予測は、ここで提案するように、確率状態の明示的な表作成を必要としないということである。後述するように、確率状態は、むしろそれぞれの指標を用いて潜在的に示されるだけである。変換規則に加えて、ＬＰＳおよびＭＰＳの値がどの確率状態で交換される必要があるかを特定する必要がある。一般的に、その指標p_stateを用いて識別されることができるような良好な確率状態は１つしかないであろう。
【００４２】
表を利用した区間分割
図２は、ここで提案するように表を利用した算術符号化のための修正された構成を示す。ＬＰＳの決定の後、まず表作成されたマッピングＱtab と適切な（ｑビットによる）シフト操作とを用いて、区間幅Ｒが量子化値Ｑへとマッピングされる。他の方法として、上記量子化は特別な場合には、表作成されたマッピングＱtabを使用せず、シフトおよびマスキング操作の組み合わせのみを用いることで実行されてもよい。一般的に、ここではＫ＝２ … ８の代表値への比較的精度が低い量子化を実行する。また、確率予測の場合と同様に、Ｑの明示的な決定は実行せず、代わりに、指標q_index をＱに変換するだけである。この時、この指標q_indexは、現時点の確率状態を特徴付ける指標p_stateと共に、区間幅ＲLPSを決定するために使用される。そのために、表Ｒtabが対応して導入される。ここで、Ｒの幅を持つ全てのＫ個の量子化値とＮmax個の異なる確率状態とに対応したＫ・Ｎmax個の生成値Ｒ×ＰLPSは、一般的にはｂ−２ビットの精度を備えた整数値として導入される。ここで、現実的な実施のために、表サイズに係る情報蓄積容量に対する必要条件と、最終的には符号化効率決定の一要素となる算術精度との間のバランスを取ることを、１つの可能性として提案する。蓄積容量と算術精度との両方の目的とする変数は、ＲとＰLPS の表現の緻密度(granularity)により決定される。
【００４３】
図２に示される第４ステップにおいては、上述の符号化されたイベントビットに依存して、確率状態p_stateの更新がどのように実行されるかを示す。ここでは、上述の「表を利用した確率予測」の章の中で既に説明した変換表Next_State_LPS と Next_State_MPSとを使用する。これらの操作は、図１のステップ４で示した更新プロセスに対応するので、さらなる説明は省略する。
【００４４】
図３は、表を利用した算術復号化に対応するフローチャートを示す。復号器の中で現時点の部分区間を特徴づけるために、区間幅Ｒと値Ｖとが使用される。値Ｖは部分区間内に存在し、読み出された全てのビット毎に連続的に更新される。図３から分かるように、確率予測のための操作と、区間幅Ｒを決定するための操作とは、符号化器の中でのこれらに対応する操作と同様の方法で実行される。
【００４５】
均一の確率分布を持つ場合の符号化
例えば、正負符号が付された値であってその確率分布がゼロを中心に対称的に分布している値を符号化する場合、正負符号の情報を符号化するためには一般的には同一の確率分布が推定される。この情報は算術ビットストリームの中に組み込まれるべきものである一方で、他方では、ｐ≒0.5の確率を持つ場合に対して表を利用した確率予測と区間分割の比較的コンパクトな装置を使用することは賢明な方法とは言えないことから、この特別な場合に対しては、選択的に下記のような特別な符号器／復号器における工程を使用することを提案する。
【００４６】
この特別な場合には、新たな部分区間の区間幅は、符号器内において、元の区間Ｒの幅の２等分に対応する簡素なシフト操作によって決定されてもよい。符号化されるべきビットの値に依存して、Ｒの上半分または下半分が、それぞれ、新たな部分区間として選択される（図４参照）。後続の再正規化およびビットの出力は、上述の表を利用した場合と同様に実行される。
【００４７】
対応する復号器において必要とされる操作は減少し、簡単な比較操作によってＶの値を現時点の区間幅Ｒに対して相対的に使用して、復号化されるべきビットを決定すればよい。復号化されたビットが設定されている場合には、値ＶはＲの総量分だけ減少させられる。図４に記載のように、復号化は、再正規化と次に読み込まれるべきビットを用いたＶの更新とによって終了する。
【００４８】
均一の確率分布を持つイベントを符号化する他の方法を、図５に示す。この典型的な実施例においては、現時点の区間幅Ｒは修正されない。代わりに、符号器内で値Ｖがまずシフト操作によって２倍される。次に上述の例と同様に、符号化されるべきビットの値に依存して、Ｒの上半分または下半分が、それぞれ、新たな部分区間として選択される（図５参照）。後続の再正規化およびビットの出力は、上述の表を利用した場合と同様に実行されるが、この場合には以下の点で異なっている。すなわち、ＲとＬとを２倍することは実行されず、対応する比較操作は２倍されたしきい値を用いて実行される。
【００４９】
上記の他の符号化方法に対応する復号器においては、まずビットが読み出され、Ｖが更新される。第２ステップは、図４に記載のステップ１と同様に実行される。すなわち、簡単な比較操作によってＶの値を現時点の区間幅Ｒに対して相対的に使用して、復号化されるべきビットが決定される。また、復号化されたビットが設定されている場合には、値ＶはＲの総量分だけ減少させられる（図５参照）。
【００５０】
確率モデルの提示と初期化
全ての確率モデルは、本発明の上述した説明でも分かるように、２個のパラメータを用いて表示される。即ち、（１）ＬＰＳの確率状態を特徴付ける指標ｐ_stateと、（２）ＭＰＳの値valMPSである。これらの変数はいずれも、完全な符号化ユニット内の（約１スライスのビデオ符号化の過程において）符号化または復号化の最初に、それぞれ初期化される必要がある。そのため、図６に例として示すように、初期化の値は、例えば（スライスの）量子化パラメータのように、制御情報から得られてもよい。
【００５１】
前方向に制御された初期化プロセス
モデルのスタート分布の適応のさらなる可能性として、以下の方法が提供できる。モデルの初期化のより良い適応を保証するために、符号器の中では、モデルの所定のスタート値が選択されるようにしてもよい。これらのモデルは、スタート分布のグループへと結合されても良く、指標を用いて示されても良い。その結果、符号器内において、スタート値のグループの適応型選択が実行され、復号器に対しページ情報として指標の形式で送信されてもよい。この方法は、前方向に制御された初期化プロセスと呼ばれるものである。
【図１】
2006050605.tif 000005
【図２】
2006050605.tif 000006
【図３】
2006050605.tif 000007
【図４】
2006050605.tif 000008
【図５】
2006050605.tif 000009
【図６】
2006050605.tif 000010