JP4054345B2 - バイナリ状態を符号化および復号化するための方法と装置および対応するコンピュータプログラム - Google Patents

Description

本発明は、バイナリ状態を算術的に符号化および復号化するための方法と装置、および対応するコンピュータプログラムに関するものであり、特にこれらは、デジタルデータ圧縮のために使用可能なものである。

本発明は、バイナリ算術符号化のための新規で効果的な方法を提案するものである。デジタルデータ圧縮の様々な適用分野の多くの分野において、バイナリ算術符号化に対する需要がある。特に、デジタル画像圧縮の分野における適用は強い関心を呼んでいる。例えばＪＰＥＧ−２０００，ＪＰＥＧ−ＬＳ，ＪＰＩＧ等の、画像符号化のための多くの規格の中で、バイナリ算術符号化のための方法が定義されている。より新しい規格化活動の中でも、これらの符号化技術がビデオ符号化の分野において将来的にも使用されるであろうことが明らかである（非特許文献１のＨ．２６４／ＡＶＣにおけるＣＡＢＡＣを参照）。

これまで現実に使用されて来たハフマン符号化（非特許文献２参照）とは対照的に、算術符号化（ＡＣ）は、基本的に下記３つの特徴を備えるものである。
１．算術符号化を用いることにより、現在のソース（情報源）統計に対するダイナミックな適応が、簡素な適応メカニズムによって達成できる。
２．算術符号化によって、符号化されるべき各々のシンボルに対する非整数個のビット割り当てが可能になる。そのため、エントロピーの近似を、理論的に付与されたより低位のバウンド（エントロピー近似）として示す符号化結果を達成するのに適切と言える（非特許文献３参照）。
３．適切なコンテキストモデルを使用することで、さらなるデータ削減のためのシンボル間の統計的結合が、算術符号化において使用可能となる（シンボル間の冗長性）（非特許文献４参照）。

算術符号化の適用の欠点として、一般的にハフマン符号化と比較して計算量が増大することがあげられる。

算術符号化の概念は、シャノンによる情報理論に関する基本的な文書（非特許文献５参照）に遡るものである。最初の概念的な構築方法は、まずエリアスによって出版された（非特許文献６参照）。算術符号化の最初のＬＩＦＯ（後入れ先出し）の異型は、リサネンによって構築され（非特許文献７参照）、その後別の著者によってＦＩＦＯ（先入れ先出し）の実装へと修正された（非特許文献８、９、１０参照）。

上述の全ての文献は、共通して再帰的部分区間分解(recursive partial interval decomposition)について言及している。バイナリアルファベットの２つの結果｛“０”，“１”｝の、与えられた確率Ｐ（“０”）とＰ（“１”）とに対応して、最初に付与された区間、例えば区間［０，１］が、個々のイベントの出現に依存する部分区間(partial interval)へと再帰的に分解される。このとき、出現する個々のイベントの確率（出現率）の結果として生じる部分区間のサイズは、個々のイベントのシーケンスの確率に比例している。各イベントＳi は、確率Ｐ（Ｓi ）により、全体的な割合に対し、Ｓi の理論的情報コンテントＨ（Ｓi ）のＨ（Ｓi ）＝−log （Ｐ（Ｓi ））分だけ寄与を加えるので、部分区間を現すためのビット数Ｎ_Bit と、個々のイベントのシーケンスのエントロピーとの間の関係は、次の方程式の右側に示される。

しかし、基本原則は、結果として生じる部分区間の表現において、第１に（理論的に）無限の正確性を要求する。また、上記の方法は次の欠点を持つ。即ち、結果として生じる部分区間を現すためのビットは、最後の結果の符号化が終わるまで出力されないということである。現実的な適用を目的とするとき、ビットの増分出力のためのメカニズムであって所定の正確性の数値を持つ表現を同時的に出力できるものを開発することが極めて重要であった。これらは、非特許文献３、７、１１で初めて紹介されたものである。

図１には、バイナリ算術符号化の基本操作が示されている。図示された操作の中では、現時点の部分区間は２つの値ＬとＲとで表現されている。このＬはオフセットポイント（下限値）を表し、Ｒはその部分区間のサイズ（幅）を表し、どちらの量もそれぞれｂビット整数を用いて表現されている。ビット∈｛０，１｝の符号化は、基本的に次の５つのサブステップで実行される。第１ステップでは、確率推定(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)｛Ｑ₁ ，．．．，Ｑ_k ｝に分割し、確率の特定のためのプリセット可能な値領域をＮ個の代表的確率状態(representative probability states) ｛Ｐ₁ ，．．．，Ｐ_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 は現時点の確率状態を示し、
R_LPS はＬＰＳに対応する区間幅を示し、
ValMPS はＭＰＳに対応するビットを示す。

本発明の復号化方法のある特別な実施例は、以下のステップを含む：
１．ＬＰＳの決定
２．Ｒの量子化：
q_index = Qtab[R≫q]
３．Ｒ_LPS とＲの決定：
R_LPS = Rtab [q_index, p_state]
R = R - R_LPS
４．部分区間の位置に依存するビットの決定
（Ｖ ≧ Ｒ）のとき
bit ← LPS
V ← V − R
R ← R_LPS
(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 は現時点の確率状態を示し、
R_LPS はＬＰＳに対応する区間幅を示し、
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 はスライスの始めにプリセットされた量子化パラメータを示し、ｍおよびｎはモデルパラメータを示している。

バイナリ状態の算術的符号化および復号化のためのある装置は、少なくとも１つのプロセッサを備え、このプロセッサは、算術的符号化および復号化のための以下の方法を実行できる。即ち、第１ステップでは、区間幅Ｒの特定のためのプリセット可能な値領域をＫ個の代表的区間幅｛Ｑ₁ ，．．．，Ｑ_K ｝に分割し、確率の特定のためのプリセット可能な値領域をＮ個の代表的確率状態｛Ｐ₁ ，．．．，Ｐ_N ｝に分割し、全ての各区間幅Ｒに対して１つのＱ_k （１≦ｋ≦Ｋ）を割り当てかつ全ての各確率に対して１つのＰ_n （１≦ｎ≦Ｎ）を割り当てる割当規則を付与する。次に第２ステップでは、符号化プロセスまたは復号化プロセスの中でそれぞれ得られるべき新たな区間幅を代表的区間幅Ｑ_k （１≦ｋ≦Ｋ）と代表的確率状態Ｐ_n （１≦ｎ≦Ｎ）とを用いて乗算と除算以外の算術操作によって計算することで、バイナリ状態の符号化または復号化を実行し、このとき代表的区間幅Ｑ_k は基礎になる区間幅Ｒによって決定され、代表的確率状態Ｐ_n は符号化または復号化されるべきシンボルの根底にある確率推定を用いて上記付与された割当規則に従って決定される。

バイナリ状態の算術的符号化および復号化のための１つのコンピュータプログラムは、それがコンピュータのメモリに記憶された後には、そのコンピュータが算術的符号化および復号化のための以下の方法を実行できるようにする。即ち、第１ステップで、区間幅Ｒの特定のためのプリセット可能な値領域をＫ個の代表的区間幅｛Ｑ₁ ，．．．，Ｑ_K ｝に分割し、確率の特定のためのプリセット可能な値領域をＮ個の代表的確率状態｛Ｐ₁ ，．．．，Ｐ_N ｝に分割し、全ての各区間幅Ｒに対して１つのＱ_k （１≦ｋ≦Ｋ）を割り当てかつ全ての各確率に対して１つのＰ_n （１≦ｎ≦Ｎ）を割り当てる割当規則を付与する。次に第２ステップでは、符号化プロセスまたは復号化プロセスの中でそれぞれ得られるべき新たな区間幅を代表的区間幅Ｑ_k （１≦ｋ≦Ｋ）と代表的確率状態Ｐ_n （１≦ｎ≦Ｎ）とを用いて乗算と除算以外の算術操作によって計算することで、バイナリ状態の符号化または復号化を実行し、このとき代表的区間幅Ｑ_k は基礎になる区間幅Ｒによって決定され、代表的確率状態Ｐ_n は符号化または復号化されるべきシンボルの根底にある確率推定を用いて上記付与された割当規則に従って決定される。

このようなコンピュータプログラムは、例えば、（有料または無料で自由にアクセス可能かまたはパスワードで保護された状態で）データあるいはコミュニケーションネットワークの中にダウンロードできるよう提供可能である。また、このように提供されるコンピュータプログラムは、次の方法により使用可能となる。すなわち、請求項３３に記載のコンピュータプログラムが、例えばインターネット等の送信用ネットワークからそのネットワークに接続されたデータ処理手段へとダウンロードされる方法である。

バイナリ状態の算術的符号化および復号化のための方法を実行するためには、望ましくはコンピュータが読み取りできる情報記憶媒体が使用され、この情報記憶媒体にプログラムが記録され、そのプログラムは、それがコンピュータのメモリに記憶された後には、そのコンピュータが算術的符号化および復号化のための以下の方法を実行できるようにする。即ち、第１ステップで、区間幅Ｒの特定のためのプリセット可能な値領域をＫ個の代表的区間幅｛Ｑ₁ ，．．．，Ｑ_K ｝に分割し、確率の特定のためのプリセット可能な値領域をＮ個の代表的確率状態｛Ｐ₁ ，．．．，Ｐ_N ｝に分割し、全ての各区間幅Ｒに対して１つのＱ_k （１≦ｋ≦Ｋ）を割り当てかつ全ての各確率に対して１つのＰ_n （１≦ｎ≦Ｎ）を割り当てる割当規則を付与する。次に第２ステップでは、符号化プロセスまたは復号化プロセスの中でそれぞれ得られるべき新たな区間幅を代表的区間幅Ｑ_k （１≦ｋ≦Ｋ）と代表的確率状態Ｐ_n （１≦ｎ≦Ｎ）とを用いて乗算と除算以外の算術操作によって計算することで、バイナリ状態の符号化または復号化を実行し、このとき代表的区間幅Ｑ_k は基礎になる区間幅Ｒによって決定され、代表的確率状態Ｐ_n は符号化または復号化されるべきシンボルの根底にある確率推定を用いて上記付与された割当規則に従って決定される。

本発明の新たな方法は、次の３つの特徴の組み合わせにより顕著性を有する。まず、Ｑ−コーダの場合と同様に、確率推定が有限状態機械（ＦＳＭ）を用いて実行され、有限状態機械のＮ個の代表的な状態の生成はオフラインで実行される。対応する変換規則は表の形式でファイリングされる。

本発明の２つ目の特徴は、区間幅ＲをＫ個の予め定義された量子化値へ事前量子化 (prequatization) することである。このため、ＫとＮとを適切に数値設定することで、乗算を含まないＲ_LPS 決定のために、予め計算された積の値Ｒ×Ｐ_LPS のＫ×Ｎ個の全ての組み合わせを含む表が生成可能となる。

本発明が、異なるコンテキストモデルが使用されかつ（略）均一の確率分布が割り当てられた環境の中で使用される場合のために、追加的（選択的）要素として、符号器の中に別の分枝が準備され、この分枝においては、同等の確率分布を想定し、変数ＬおよびＲの決定と再正規化とが、計算労力において大きく低減される。

全体として、本発明は特に、一方では高い符号化効率を、他方では計算労力の低減を、同時に実現できるという長所を提供できる。

以下に、図に示された実施例を参照しながら本発明を詳細に説明する。
バイナリ算術符号化のための基本的な操作を示す図である。 表を利用した算術符号化のための修正された構成を示す図である。 表を利用した算術復号化の原理を示す図である。 均一の確率分布を持つバイナリデータを符号化または復号化する原理をそれぞれ示す図である。 均一の確率分布を持つバイナリデータを符号化または復号化する他の実施例の原理をそれぞれ示す図である。 量子化パラメータＳliceＱＰと、プリセットされたモデルパラメータｍおよびｎとに依存した確率推定の初期化を示す図である。

まず、理論的背景について詳細に説明する。

表を利用した確率推定
既に上述したように、算術符号化の効果は、符号化されるべきシンボルの出現確率の推定に依存するものであり、この推定はできるだけ正確なことが望ましい。動的情報源統計(non-stationary source statistics)への適応を可能にするため、この出現確率の推定は、符号化プロセスの過程において更新されてゆく必要がある。この目的のために使用される通常の方法では、符号化結果のスケールされた出現頻度カウンタ(frequency counter) を用いた操作が一般的である（非特許文献１７参照）。Ｃ_LPS およびＣ_MPS がＬＰＳおよびＭＰＳの出現頻度のカウンタを示す場合には、これらのカウンタを用いて、上記出現確率の推定は次の式により実行されてもよい。

またこの後、図１に示された区間分割の操作が実行されてもよい。現実的な目的から、式（１）で必要とされる割算は不利になる。しかし、全体的カウンタＣ_Total = Ｃ_MPS + Ｃ_LPS の予め決定されたしきい値Ｃ_max を超えた時には、カウンタ読み取りの再スケーリングを実行することがしばしば好都合であり必要とされる。（このとき注目すべきは、ＬとＲとをｂビット表示した場合、正確に示されることが可能な最小確率は２^-b+2であり、その結果、この最小確率を下回ることを回避するためには、カウンタ読み取りの再スケーリングが必要になる。）Ｃ_max を適切に選択することで、Ｃ_Total の逆数(reciprocal values) は表に示されることが可能になり、その結果、式（１）で要求された割算は、表へのアクセスと、乗算とシフト操作とによって置き換えることが可能となる。しかし、これらの算術も回避するために、本発明においては、完全に表を利用した方法が確率推定に使用される。

この目的のために、試行段階(training phase)において、代表的確率状態｛Ｐ_K ｜０≦ｋ＜Ｎ_max ｝が予め選択される。このとき、上記確率状態の選択は、一方では符号化されるべきデータの統計に依存し、他方では確率状態のデフォルト最大数Ｎ_max のサイド条件(side conditions) に依存する。加えて、変換規則が定義され、この規則は、現時点に符号化されたシンボルに基づき、符号化されるべき次のシンボルのためにどのような新たな状態が使用されるべきかを示す。これらの変換規則は、２つの表、即ち｛Next＿State ＿LPS _k ｜０≦ｋ＜Ｎ_max ｝と｛Next＿State ＿MPS _k ｜０≦ｋ＜Ｎ_max ｝という形で提供されており、これらの表は、現時点に付与された確率状態の指標ｎに対し、ＬＰＳまたはＭＰＳが発生した時、新たな確率状態Ｐm の指標ｍをそれぞれ提供する。ここで注意すべきは、算術符号器または算術復号器におけるそれぞれの確率推定は、ここで提案するように、確率状態の明示的な表作成を必要としないということである。後述するように、確率状態は、むしろそれぞれの指標を用いて潜在的に示されるだけである。変換規則に加えて、ＬＰＳおよびＭＰＳの値がどの確率状態で交換される必要があるかを特定する必要がある。一般的に、その指標p ＿state を用いて識別されることができるような良好な確率状態は１つしかないであろう。

表を利用した区間分割
図２は、ここで提案するように表を利用した算術符号化のための修正された構成を示す。ＬＰＳの決定の後、まず、表作成されたマッピングQtabと適切な（ｑビットによる）シフト操作とを用いて、区間幅Ｒが量子化値Ｑへとマッピングされる。他の方法として、上記量子化は特別な場合には、表作成されたマッピングQtabを使用せず、シフトおよびマスキング操作の組み合わせのみを用いることで実行されてもよい。一般的に、ここではＫ＝２…８の代表値への、比較的精度が低い量子化を実行する。また、確率推定の場合と同様に、Ｑの明示的な決定は実行せず、代わりに、指標q ＿index をＱに変換するだけである。この時、この指標q ＿index は、現時点の確率状態を特徴付ける指標p ＿state と共に、区間幅Ｒ_LPS を決定するために使用される。そのために、表Rtabが対応して導入される。ここで、Ｒの幅を持つ全てのＫ個の量子化値とＮ_max 個の異なる確率状態とに対応したＫ×Ｎ_max 個の積の値Ｒ×Ｐ_LPS は、一般的にはｂ−２ビットの精度を備えた整数値として導入される。ここで、現実的な実施のために、表サイズに係る情報記憶容量に対する必要条件と、最終的には符号化効率決定の一要素となる算術精度との間のバランスを取ることを、１つの可能性として提案する。記憶容量と算術精度との両方の目的とする変数は、ＲとＰ_LPS の表現の緻密度(granularity) により決定される。

図２に示される第４ステップにおいては、上述の符号化されたイベントビットに依存して、確率状態p ＿state の更新がどのように実行されるかを示す。ここでは、上述の「表を利用した確率推定」の章の中で既に説明した変換表Next＿State ＿LPS と Next ＿State ＿MPS とを使用する。これらの操作は、図１のステップ４で示した更新プロセスに対応するので、さらなる説明は省略する。

図３は、表を利用した算術復号化に対応するフローチャートを示す。復号器の中で現時点の部分区間を特徴づけるために、区間幅Ｒと値Ｖとが使用される。値Ｖは部分区間内に存在し、読み出された全てのビット毎に連続的に更新される。図３から分かるように、確率推定のための操作と、区間幅Ｒを決定するための操作とは、符号化器の中でのこれらに対応する操作と同様の方法で実行される。

均一の確率分布を持つ場合の符号化
例えば、正負符号が付された値であってその確率分布がゼロを中心に対称的に分布している値を符号化する場合、正負符号の情報を符号化するためには一般的には同一の確率分布が推定される。この情報は算術ビットストリームの中に組み込まれるべきものである一方で、他方では、ｐ≒0.5 の確率を持つ場合に対して表を利用した確率推定と区間分割の比較的コンパクトな装置を使用することは賢明な方法とは言えないことから、この特別な場合に対しては、選択的に下記のような特別な符号器／復号器における工程を使用することを提案する。

この特別な場合には、新たな部分区間の区間幅は、符号器内において、元の区間Ｒの幅の２等分に対応する簡素なシフト操作によって決定されてもよい。符号化されるべきビットの値に依存して、Ｒの上半分または下半分が、それぞれ、新たな部分区間として選択される（図４参照）。後続の再正規化およびビットの出力は、上述の表を利用した場合と同様に実行される。

対応する復号器において必要とされる操作は減少し、簡単な比較操作によってＶの値を現時点の区間幅Ｒに対して相対的に使用して、復号化されるべきビットを決定すればよい。復号化されたビットが設定されている場合には、値ＶはＲの総量分だけ減少させられる。図４に記載のように、復号化は、再正規化と次に読み込まれるべきビットを用いたＶの更新とによって終了する。

均一の確率分布を持つイベントを符号化する他の方法を、図５に示す。この典型的な実施例においては、現時点の区間幅Ｒは修正されない。代わりに、符号器内で値Ｖがまずシフト操作によって２倍される。次に上述の例と同様に、符号化されるべきビットの値に依存して、Ｒの上半分または下半分が、それぞれ、新たな部分区間として選択される（図５参照）。後続の再正規化およびビットの出力は、上述の表を利用した場合と同様に実行されるが、この場合には以下の点で異なっている。すなわち、ＲとＬとを２倍することは実行されず、対応する比較操作は２倍されたしきい値を用いて実行される。

上記の他の符号化方法に対応する復号器においては、まずビットが読み出され、Ｖが更新される。第２ステップは、図４に記載のステップ１と同様に実行される。すなわち、簡単な比較操作によってＶの値を現時点の区間幅Ｒに対して相対的に使用して、復号化されるべきビットが決定される。また、復号化されたビットが設定されている場合には、値ＶはＲの総量分だけ減少させられる（図５参照）。

確率推定の提示と初期化
全ての確率推定は、本発明の上述した説明でも分かるように、２個のパラメータを用いて表示される。即ち、（１）ＬＰＳの確率状態を特徴付ける指標ｐ＿state と、（２）ＭＰＳの値valMPSである。これらの変数はいずれも、完全な符号化ユニット内の（約１スライスのビデオ符号化の過程において）符号化または復号化の最初に、それぞれ初期化される必要がある。そのため、図６に例として示すように、初期化の値は、例えば（スライスの）量子化パラメータのように、制御情報から得られてもよい。

前方向に制御された初期化プロセス
確率推定のスタート分布の適応のさらなる可能性として、以下の方法が提供できる。確率推定の初期化のより良い適応を保証するために、符号器の中では、確率推定の所定のスタート値が選択されるようにしてもよい。これらの確率推定は、スタート分布のグループへと結合されても良く、指標を用いて示されても良い。その結果、符号器内において、スタート値のグループの適応型選択が実行され、復号器に対しページ情報として指標の形式で送信されてもよい。この方法は、前方向に制御された初期化プロセスと呼ばれるものである。

Claims (33)

1. バイナリ状態を持ち符号化されるべきシンボルを、現時点の区間幅Ｒと上記符号化されるべきシンボルのための確率推定を表現する確率とに基づいて算術的に符号化するための方法において、
   上記確率は、複数の代表的確率状態の中から１つの確率状態を示す１つの確率指標によって表現され、
   上記方法は、上記符号化されるべきシンボルを符号化するステップを含み、この符号化のステップは、
   上記現時点の区間幅を、複数の代表的な量子化指標の中から１つの量子化指標へとマッピングするサブステップと、
   上記量子化指標と上記確率指標とを用いて区間分割表へアクセスすることで、区間分割を実行して部分区間幅の値を得るサブステップと、を含み、
   上記確率推定の初期化は、量子化パラメータSliceQP と、プリセットされたモデルパラメータｍおよびｎとに依存して実行され、このSliceQP はスライスの始めにプリセットされた上記量子化パラメータを示し、ｍおよびｎは上記モデルパラメータを示すことを特徴とする方法。
2. 請求項１に記載の方法において、上記符号化の方法はさらに、
   上記現時点の区間幅を上記部分区間幅の値を利用して更新し、更新された新たな区間幅を得るステップを含むことを特徴とする方法。
3. 請求項１または２に記載の方法において、
   上記部分区間幅の値は、符号化されるべきシンボルのための部分区間の幅を、現時点の区間幅を持つ現時点の区間の低い確率状態で特定することを特徴とする方法。
4. 請求項１乃至３のいずれかに記載の方法において、
   上記符号化されるべきシンボルの上記バイナリ状態に依存して、上記現時点の区間幅の更新がさらに実行されることを特徴とする方法。
5. 請求項１乃至４のいずれかに記載の方法において、
   上記符号化の方法はさらに、
   上記確率推定の適応のステップであって、この確率推定の適応のステップは、
   上記符号化されるべきシンボルの確率状態が低い場合には、上記確率指標を用いて、ＬＰＳ変換規則表(Next ＿State ＿LPS)内のルックアップを実行して新たな確率指標を獲得し、
   上記符号化されるべきシンボルの確率状態が高い場合には、上記確率指標を用いて、ＭＰＳ変換規則表(Next ＿State ＿MPS)内のルックアップを実行して新たな確率指標を獲得するステップを含むことを特徴とする方法。
6. 請求項５に記載の方法において、
   上記符号化の方法はさらに、上記確率指標が所定の確率指標であり、上記符号化されるべきシンボルが最初に示された状態とは異なるバイナリ状態を持つ場合には、上記符号化されるべきシンボルの上記バイナリ状態に対して最初に示された状態の上記高い確率状態を示す値を適合させるステップを含むことを特徴とする方法。
7. 請求項１乃至６のいずれかに記載の方法において、
   上記現時点の区間幅を更新するサブステップは、
   上記新たな区間幅を、上記現時点の区間幅から上記部分区間幅の値を引き算した差と同等にするステップと、
   次に、もし上記符号化されるべきシンボルの確率状態が低い場合には、上記新たな区間幅を、上記部分区間幅の値と同等とするステップと、
   を含むことを特徴とする方法。
8. 請求項１乃至７のいずれかに記載の方法において、
   上記現時点の区間は上記現時点の区間幅と現時点のオフセットポイントとによって表され、
   上記符号化の方法はさらに
   上記符号化されるべきシンボルの確率状態が低い場合には、上記現時点のオフセットポイントと、現時点の区間幅と部分区間幅の値との差とを累積し、更新された新たなオフセットポイントを得るステップを含むことを特徴とする方法。
9. 符号化されバイナリ状態を持つシンボルを、現時点の区間幅Ｒと、上記符号化されたシンボルのための確率推定を表現する確率とに基づいて算術的に復号化するための方法において、
   上記確率は、複数の代表的確率状態から１つの確率状態を示す１つの確率指標によって表現され、
   上記方法は、上記符号化されたシンボルを復号化するステップを含み、この復号化のステップは、
   上記現時点の区間幅Ｒを複数の代表的な量子化指標から１つの量子化指標へとマッピングするサブステップと、
   上記量子化指標と上記確率指標とを用いて区間分割表へアクセスすることで、区間分割を実行して部分区間幅の値を得るサブステップと、を含み、
   上記確率推定の初期化は、量子化パラメータSliceQP と、プリセットされたモデルパラメータｍおよびｎとに依存して実行され、このSliceQP はスライスの始めにプリセットされた上記量子化パラメータを示し、ｍおよびｎは上記モデルパラメータを示すことを特徴とする方法。
10. 請求項９に記載の方法において、上記復号化の方法はさらに、
    上記現時点の区間幅を上記部分区間幅の値を利用して更新し、更新された新たな区間幅を得るステップを含むことを特徴とする方法。
11. 請求項９または１０に記載の方法において、
    上記部分区間幅の値は、符号化されたシンボルのための部分区間の幅を、現時点の区間幅を持つ現時点の区間の低い確率状態で特定することを特徴とする方法。
12. 請求項９乃至１１のいずれかに記載の方法において、
    上記現時点の部分区間幅と新たな部分区間内の値とによって特徴付けられた上記新たな部分区間内の値に依存して、上記現時点の区間幅の更新がさらに実行されることを特徴とする方法。
13. 請求項１２に記載の方法において、
    上記復号化はさらに、
    上記新たな部分区間内の値が、上記現時点の区間幅と部分区間幅の値との差と比較して大きいか小さいかに依存して、上記符号化されたシンボルのバイナリ状態を、確率が低い状態かまたは高い状態かのいずれか１つと同等にするステップを含むことを特徴とする方法。
14. 請求項１２または１３に記載の方法において、上記復号化はさらに、上記新たな部分区間内の値を、読み込まれるべき次のビットを用いて更新するステップを含むことを特徴とする方法。
15. 請求項１２乃至１４のいずれかに記載の方法において、
    上記復号化の方法はさらに、
    上記確率推定を更新するステップを含み、この確率推定を更新するステップは、上記新たな部分区間内の値が上記現時点の区間幅と部分区間幅の値との差よりも大きい場合には、上記確率指標を用いて、ＬＰＳ変換規則表(Next ＿State ＿LPS)内のルックアップを実行して新たな確率指標を獲得し、
    上記新たな部分区間内の値が上記現時点の区間幅と部分区間幅の値との差よりも小さい場合には、上記確率指標を用いて、ＭＰＳ変換規則表(Next ＿State ＿MPS)内のルックアップを実行して新たな確率指標を獲得するステップを含むことを特徴とする方法。
16. 請求項１２乃至１５のいずれかに記載の方法において、
    上記復号化の方法はさらに、
    上記確率指標が所定の確率指標であり、上記新たな部分区間内の値が上記現時点の区間幅と部分区間幅の値との差よりも大きい場合には、上記符号化されたシンボルの異なるバイナリ状態に対して最初に示された状態の上記高い確率状態を示す値を適合させるステップを含むことを特徴とする方法。
17. 請求項１乃至１６のいずれかに記載の方法において、
    上記現時点の区間幅はｂビットの精度で表現され、上記区間分割表から得られた上記部分区間幅の値はｂ−２ビットの精度で表現されることを特徴とする方法。
18. 請求項１乃至１７のいずれかに記載の方法において、
    上記マッピングのサブステップは、上記現時点の区間幅のコンピュータ内部バイナリ表現に対してシフト操作を適用して上記現時点の区間幅のための量子化された値を得ることと、表（Ｑtab ）への下流方向アクセスにより量子化の指標を得ることを含むことを特徴とする方法。
19. 請求項１乃至１８のいずれかに記載の方法において、
    上記区間分割表内には、出現可能な全ての量子化指標と出現可能な全ての確率指標とに対応する上記現時点の区間幅のための値が、量子化の指標と表Ｒtab 内の確率指標との積の値としてファイリングされることを特徴とする方法。
20. 請求項１乃至１９のいずれかに記載の方法において、
    上記確率推定を更新するステップを含み、
    この確率推定の更新は変換規則によって実行され、この変換規則は、上記符号化されるべきシンボルおよび／または符号化されたシンボルに基づいて、複数の確率状態からいずれの新たな確率状態が次の符号化されるべきシンボルおよび／または符号化されたシンボルのために使用されるべきかを特定することを特徴とする方法。
21. 請求項１乃至２０のいずれかに記載の方法において、
    上記確率推定を更新するステップを含み、
    この確率推定の更新は、上記確率指標を用いて、変換規則表(Next ＿State ＿LPS)内のルックアップを実行して新たな確率指標を得るステップをさらに含むことを特徴とする方法。
22. 請求項１乃至２１のいずれかに記載の方法において、
    上記出現可能な量子化指標の数および／または上記確率状態の数が、上記符号化のプリセットされた精度および／または有効情報記憶容量に依存して選択されることを特徴とする方法。
23. 請求項１乃至２２のいずれかに記載の方法において、
    上記更新された新たなオフセットポイントと上記更新された新たな区間幅とを再正規化するサブステップをさらに含むことを特徴とする方法。
24. 請求項９乃至２３のいずれかに記載の方法において、上記復号化は、
    １．ＬＰＳの決定のステップと、
    ２．Ｒの量子化のステップと、
    q_index = Qtab[R≫q]
    ３．Ｒ_LPSとＲの決定のステップと、
    R_LPS = Rtab [q＿index, p＿state]
    R = R−R_LPS
    ４．上記部分区間の位置に依存するビットの決定のステップであって、
    (V ≧ R)のとき、
    bit ← LPS
    V ← V − R
    R ← R_LPS
    (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 は上記現時点の確率状態を示し、
    R_LPSは上記ＬＰＳに対応する区間幅を示し、
    ValMPSは上記ＭＰＳに対応するビットを示し、
    V は上記現時点の部分区間の内部からの値を示すステップと、
    を含むことを特徴とする方法。
25. 請求項１乃至２４のいずれかに記載の方法において、
    符号化および／または復号化において、上記量子化の指標q ＿index へのマッピングが次の計算規則：
    q ＿index = (R≫q)＆ Qmask
    に従って実行され、Qmask は確率状態の数に依存して適切に選択されたビットマスクを示し、Ｒは上記現時点の区間幅を示し、q はビットの数を示すことを特徴とする方法。
26. 請求項１乃至２５のいずれかに記載の方法において、
    もし均一な確率分布が存在している場合には、
    符号化において、以下に示す計算規則：
    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
    が実行されることを特徴とする方法。
27. 請求項１乃至２６のいずれかに記載の方法において、
    上記確率推定の初期化が次のステップ：
    １．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 はスライスの始めにプリセットされた上記量子化パラメータを示し、ｍおよびｎは上記モデルパラメータを示すことを特徴とする方法。
28. 請求項１乃至２７のいずれかに記載の方法において、
    上記確率状態の上記確率推定が有限状態機械（ＦＳＭ）を用いて実行されることを特徴とする方法。
29. 請求項１乃至２８のいずれかに記載の方法において、
    上記確率状態の生成はオフラインで実行されることを特徴とする方法。
30. 請求項１乃至２９のいずれかに記載の方法において、
    上記確率状態の選択は、符号化されるべきデータの統計および／または上記確率状態の数に依存することを特徴とする方法。
31. バイナリ状態を持ち符号化されるべきシンボルを、現時点の区間幅Ｒと上記符号化されるべきシンボルのための確率推定を表現する確率とに基づいて算術的に符号化するための装置において、
    上記確率は、複数の代表的確率状態の中から１つの確率状態を示す１つの確率指標によって表現され、
    上記装置は、上記符号化されるべきシンボルを符号化する手段を含み、この手段は、
    上記現時点の区間幅を、複数の代表的な量子化指標の中から１つの量子化指標へとマッピングする手段と、
    上記量子化指標と上記確率指標とを用いて区間分割表へアクセスすることで、上記区間分割を実行して部分区間幅の値を得る手段と、を含み、
    上記確率推定の初期化は、量子化パラメータSliceQP と、プリセットされたモデルパラメータｍおよびｎとに依存して実行され、このSliceQP はスライスの始めにプリセットされた上記量子化パラメータを示し、ｍおよびｎは上記モデルパラメータを示すことを特徴とする装置。
32. バイナリ状態を持ち符号化されたシンボルを、現時点の区間幅Ｒと上記符号化されたシンボルのための確率推定を表現する確率とに基づいて算術的に復号化するための装置において、
    上記確率は、複数の代表的確率状態の中から１つの確率状態を示す１つの確率指標によって表現され、
    上記装置は、上記符号化されたシンボルを復号化する手段を含み、この手段は、
    上記現時点の区間幅を、複数の代表的な量子化指標の中から１つの量子化指標へとマッピングする手段と、
    上記量子化指標と上記確率指標とを用いて区間分割表へアクセスすることで、上記区間分割を実行して部分区間幅の値を得る手段と、を含み、
    上記確率推定の初期化は、量子化パラメータSliceQP と、プリセットされたモデルパラメータｍおよびｎとに依存して実行され、このSliceQP はスライスの始めにプリセットされた上記量子化パラメータを示し、ｍおよびｎは上記モデルパラメータを示すことを特徴とする装置。
33. コンピュータが請求項１または９に記載の方法を実行できるように、コンピュータを作動させるコンピュータプログラム。

Images