JP5736032B2 - 算術符号化のための適応型２値化 - Google Patents

Description

[0001] 本発明は、算術符号化に関し、特に、適応的に確率を推定して有限精度環境で確率を正確に表し（account for）、シンボルとそれらシンボルを表すビット数との比を制限する算術符号化に関する。

[0002] 算術符号化は、画像や音声等の媒体データの圧縮に適用されて成功を収めている。ＩＴＵ−Ｔ及びＭＰＥＧにより提案される最新の映像符号化標準Ｈ．２６４／ＡＶＣ（参照により本明細書に組み込まれる）は、Ｈ．２６３やＭＰＥＧ２等の先行する符号化標準と比べて著しい性能の向上を実現する。Ｈ．２６４／ＡＶＣ標準は、２つの異なるエントロピー符号化方法、すなわちコンテクストに基づく適応型可変長符号化（Context-based Adaptive Variable Length Coding）（ＣＡＶＬＣ）及びコンテクストに基づく適応型２値算術符号化（Context-based Adaptive Binary Arithmetic Coding）（ＣＡＢＡＣ）に対応している。ＣＡＶＬＣと比較すると、ＣＡＢＡＣは、より高い符号化効率を提供し、ビットレートが平均で９％〜１４％節減される。Li Liu及びXinhua Zhuang、「CABAC Based Bit Estimation for First H.264 Rd Optimization Decision」（IEEE, 2009）を参照されたい。同文献は参照により本明細書に組み込まれる。

[0003] ＣＡＢＡＣの符号化処理の基本概念は反復的な区間分割である。ＣＡＢＡＣエンジンは２つのレジスタを維持する。第１のレジスタは、９ビットの範囲レジスタである。第２のレジスタは、通常モードでは９ビット、バイパスモードでは１０ビットのオフセットレジスタである。範囲レジスタは、現在の区間の幅を常に把握する。オフセットは、ビットストリームからのオフセットであり、範囲内の現在の位置を指す。ビン（bin）を復号する際、範囲は、そのビンに固有の出現確率に応じて、２つの部分区間に分割される。ビンの復号後、範囲及びオフセットが更新される。１つのビンを復号すると、範囲及びオフセットを再度正規化して、次のビンを復号するための精度を維持する。９ビットのレジスタ範囲の最上位ビットが常に１であることを保証する。

[0004] ＣＡＢＡＣが効率的な符号化方法であることは様々な理論が示しているが、ＣＡＢＡＣの実際的な実装は、特に符号化対象のシンボルの出現確率が高い場合にいくつかの技術的問題を呈する。例えば、計算に使用するレジスタの利用可能な長さにより精度桁数が制限される数に計算が行われるＣＡＢＡＣ符号化エンジンでは、符号化モデルで表される最も高い確率が、有限精度の制約によって制限される。有限精度の制約は、出現確率が高いシンボルの効率的な符号化を妨げる。これは、高い確率は、有限精度環境では正確に表現することができないためである。また、ＣＡＢＡＣでは、出現確率が高いシンボルは高度に圧縮され、したがって、高い出現確率のシンボルを符号化するために必要なビットがより少なくなる。しかし、デコーダの映像復号性能は、通例、所定の期間内に処理されるビット数で評価される。多数のシンボルが少数のビットに符号化される場合は、ＣＡＢＡＣの復号速度は向上するものの、デコーダにおける全体的な処理速度は低下する。

[0005] 出現確率が低いシンボルもＣＡＢＡＣの実際的な実装では技術的課題を呈する。ＭＰＥＧで使用される整数シンボル、例えば変換係数や動きベクトル差は、次の幾何分布でモデル化することができる。
ｐ（ｋ）＝（１−ｐ）^ｋ−１×ｐ
ｋはシンボルの絶対値であり、ｐはモデルパラメータであり、ｐ（ｋ）はシンボルの出現の確率である。この種の分布は、ｋ−１個の２値シンボルＡ、次いで１つの２値シンボルＢを使用して値ｋが符号化されるＣＡＢＡＣによる２値算術符号化に適している。理想的な算術コーダを用い、既知のパラメータｐを有する静的なソースの場合、値ｋを符号化するのに必要な予想ビット数は、
−（ｋ−１）×ｌｏｇ_２（１−ｐ）−ｌｏｇ２_ｐ
に等しい。

[0006] 実際の実装では、パラメータｐは通常既知でなく、またソースは静的でない場合もあるため、パラメータｐは、個々の２値シンボルの頻度に基づいて適応的に推定される。Ｈ．２６４／ＡＶＣはパラメータｐを利便に推定できる適応推定手法を提供するが、それらの手法は符号化の効率を犠牲にする。パラメータｐを適応的に推定するＣＡＢＡＣ符号化エンジンでは、静的ソースから値ｋを符号化するために使用されるビット数は、
−（ｋ−１）×ｌｏｇ_２（１−ｐ）−ｌｏｇ_２ｐ＋ｋ×ｚ
により概算することができ、ｚは、０．０１〜０．０２の範囲の値であり、推定処理に伴う非効率性を表す。ｋの予想値を１／ｐで表すことができるとすると、上記式は、

になる。したがって、パラメータｐが小さくなるにつれ、ｚに伴う非効率性が増し、値ｋを符号化するために使用されるビット数は理論的に必要なビット数よりもかなり多くなる。すなわち、パラメータｐが小さくなると、算術コーダはシンボルを効率的に圧縮することができなくなる。さらに、この非効率性は、有限精度環境で課される制約、すなわち、パラメータｐが小さい時に正確な符号化計算を行えないことにより増大する。

[0007] これらの問題に対処するために、Ｈ．２６４／ＡＶＣでは符号化処理に閾値ｔを導入した。ｋの値が閾値ｔ以下の場合、ｋの値はｋ−１個の２値シンボルＡ、次いで１つの２値シンボルＢを使用して符号化される。ｋの値が閾値ｔより大きい場合、値ｋは、ｔ個のシンボルＡ、次いでｋ−ｔを表すエスケープシーケンスを使用して符号化される。Ｈ．２６４／ＡＶＣでは、エスケープシーケンスは、指数Ｇｏｌｏｍｂ符号化によって形成される。しかし、この解決策は、閾値ｔがその場しのぎに予め決められたものであり、エスケープシーケンスの構造がソースの統計的性質を正確に表さない可能性があるため、最善とは言えない。

[0008] 従来の算術コーダに見られる上記の問題を鑑みて、本発明は、バイナライザ（binarizer）が、ソースの確率に合わせて適応的に可変である長さで２値シンボルを出力する適応的な２値化を初めに提供する。確率が低い場合は、２値シンボルの長さを低減して、算術符号化の効率を改善し、符号化計算の複雑度を低減することが望ましい。一方、確率が高い場合は、２値シンボルの長さを増大させて、デコーダの全体的な処理速度を向上させることが望ましい。

[0009] 具体的には、本発明は、１回の符号化のたびに、マッピング単位値を非２値シンボルから１つの２値シンボルに２値化するように構成されたバイナライザを備えた算術エンコーダを提供する。２値シンボルの数は、マッピング単位値の大きさに反比例する。マッピング単位値が大きくなった場合は、バイナライザからの２値シンボルの数は少なくなり、その逆も同様である。エンコーダは、複数回の符号化を通じて遷移することが可能な確率パラメータを使用して、バイナライザからの２値シンボルを１回の符号化のたびに１つ符号化するように構成された算術符号化エンジンをさらに備える。本発明では、マッピング単位値を可変にし、したがって、バイナライザからの２値シンボルの数も適応的に可変であり、マッピング単位値の関数となる。また、マッピング単位値も確率パラメータに合わせて適応的に可変である。したがって、本発明によれば、バイナライザからの２値シンボルの数は、確率パラメータに合わせて適応的に可変である。

[0010] 本発明は、確率パラメータに合わせて適応的に可変であるサイズパラメータを導入する。サイズパラメータがマッピング単位値を決定する。一実施形態では、１回の符号化のたびに確率パラメータを検査して、サイズパラメータを変更する必要があるかどうかを確認する。確率パラメータが低いことが判明した場合は、サイズパラメータを変更してマッピング単位値を増大させ、それにより、バイナライザからの２値シンボルの数を減らす。確率パラメータが高いことが判明した場合は、サイズパラメータを変更してマッピング単位値を減少させ、それにより、バイナライザからの２値シンボルの数を増す。いずれの場合も、確率パラメータを調整して断片値の変化を補償する。したがって、本発明では、確率パラメータは常に、有限精度の制約下でも確率が正確に表現される範囲にある。

[0011] 本発明は、上記の算術エンコーダと連携して動作する算術デコーダも提供する。本発明による算術デコーダは、複数回の復号を通じて遷移することが可能な確率パラメータを使用して、算術符号語を１回の復号のたびに１つ復号して２値シンボルにするように構成された算術復号エンジンを備える。エンコーダは、２値シンボルを１回の復号のたびに１つ逆２値化して、非２値シンボルを再構築するために合計されるマッピング単位値にするように構成されたデバイナライザも備え、マッピング単位値は、確率パラメータに合わせて適応的に可変である。一実施形態では、確率パラメータに合わせて適応的に可変であるサイズパラメータによってマッピング単位値が決定される。

[0012] このデコーダでは、確率パラメータに基づいて、１回の復号のたびに、サイズパラメータを変更する必要があるかどうかが判定される。確率パラメータが低い場合は、サイズパラメータを変更してマッピング単位値を増大させる。確率パラメータが高い場合は、サイズパラメータを変更してマッピング単位値を減少させる。いずれの場合も、確率パラメータを調整してマッピング単位値の変化を補償する。

[0013] 本発明を実施することが可能な例示的ハードウェアアーキテクチャを示すブロック図である。 [0014] 本発明を適用することが可能なビデオエンコーダの概略図を示すブロック図である。 [0015] 本発明を適用することが可能なビデオデコーダの概略図を示すブロック図である。 [0016] 本発明の実施形態によるエントロピーコーダの機能モジュールを示すブロック図である。 [0017] 本発明の別の実施形態によるエントロピーデコーダの機能モジュールを示すブロック図である。 [0018] 本発明の実施形態によるエントロピーコーダで実施される例示的な初期化処理を示すフローチャートである。 [0019] 本発明の別の実施形態による主要な符号化処理を示すフローチャートである。 [0020] 図７のステップ７０３及び７０５で行われる確率推定ｐを更新する処理を示すフローチャートである。 [0021] シンボルＮが符号化される図７のステップ７０６の処理を詳細に説明するフローチャートである。 [0022] 図９のステップ９０２の符号化処理を詳細に説明するフローチャートである。 [0023] サフィックスの大きさｓが更新される図９のステップ９０５で行われる処理を詳細に説明するフローチャートである。 [0024] 例示的バイパス符号化処理を示すフローチャートである。 [0025] サフィックスの大きさｓが更新される図９のステップ９０９で行われる処理を詳細に説明するフローチャートである。 [0026] 図１１と図１３の処理が組み合わせられたフローチャートである。 [0027] 本発明の別の実施形態によるエントロピーデコーダによって行われる初期化処理を示すフローチャートである。 [0028] エントロピーデコーダによって行われる主要な復号処理を示すフローチャートである。 [0029] 復号処理を示すフローチャートである。 [0030] 符号なしの整数Ｎを復号する例示的な処理を示すフローチャートである。 [0031] 例示的バイパス復号処理を示すフローチャートである。 [0032] 図１６のステップ１６０２及び図１８のステップ１８０５で行われる確率推定ｐを更新する処理を示すフローチャートである。 [0033] サフィックスの大きさｓが更新される図１８のステップ１８０６で行われる処理を詳細に説明するフローチャートである。 [0034] サフィックスの大きさｓが更新される図１８のステップ１８０９で行われる処理を詳細に説明するフローチャートである。 [0035] 本発明の実施形態の効率を示すグラフである。 [0036] 確率推定ｐ_０，ｐ_１，ｐ_２．．．がｐＳｔａｔｅＩｄｘの索引値と関連付けて記憶されるコンテクストモデルテーブルの例示的構造を示す図である。 [0037] ｐＳｔａｔｅＩｄｘの調整後の索引値がｐＳｔａｔｅＩｄｘの現在の索引値と関連付けて記憶される遷移テーブルの例示的構造を示す図である。 [0038] ｐＳｔａｔｅＩｄｘの更新後の索引値がｐＳｔａｔｅＩｄｘの現在の索引値と関連付けて記憶される更新テーブルの例示的構造を示す図である。

[0039] 図１は、本発明を実施することが可能なコンピュータ１００の例示的ハードウェアアーキテクチャを示す。図１に示すハードウェアアーキテクチャは、本発明の実施形態を実施するビデオエンコーダ及びビデオデコーダの両方に共通でよいことに留意されたい。コンピュータ１００は、ローカルインタフェース１０７を介して通信可能に結合された、プロセッサ１０１、メモリ１０２、記憶装置１０５、及び入力及び／又は出力（Ｉ／Ｏ）装置１０６（若しくは周辺装置）を含む。ローカルインタフェース１０５は当技術分野で知られるように、これらに限定されないが、例えば１つ若しくは複数のバス又は他の有線若しくは無線接続とすることができる。

[0040] プロセッサ１０１は、ソフトウェア、特にメモリ１０２に記憶されたソフトウェアを実行するハードウェア装置である。プロセッサ１０１は、任意の特別注文若しくは市販のプロセッサ、中央演算処理装置（ＣＰＵ）、コンピュータ１００に関連する数個のプロセッサのうちの補助プロセッサ、半導体を利用したマイクロプロセッサ（マイクロチップ若しくはチップセットの形態）、又は一般にソフトウェア命令を実行する任意の装置とすることができる。

[0041] メモリ１０２は、コンピュータ可読媒体からなり、コンピュータ可読媒体は、揮発性のメモリ要素（例えばランダムアクセスメモリ（ＤＲＡＭ、ＳＲＡＭ、ＳＤＲＡＭ等のＲＡＭ））、及び不揮発性のメモリ要素（例えばＲＯＭ、ハードドライブ、テープ、ＣＤＲＯＭ等）のいずれか１つ又は組み合わせを含むことができる。さらに、メモリ１０２には、電子、磁気、光学、及び／又は他の種の記憶媒体を採用することができる。コンピュータ可読媒体は、命令実行システム、装置、又はデバイスにより使用されるプログラム、又はそれらシステム、装置、デバイスに関連するプログラムを記憶、通信、伝搬、又は搬送することが可能な任意の手段とすることができる。メモリ１０２は分散アーキテクチャを有することができ、その場合、各種構成要素は互いから遠隔に位置するが、プロセッサ１０１からアクセスすることができることを留意されたい。

[0042] メモリ１０２内のソフトウェア１０３は１つ又は複数の別個のプログラムを含むことができ、各プログラムは、下記で説明するコンピュータ１００の論理的機能を実装する実行可能命令の順序付けられたリストを含んでいる。図１の例では、メモリ１０２のソフトウェア１０３は、本発明によるコンピュータ１００の映像符号化及び映像復号機能を定義する。また、これは必須ではないが、メモリ１０２がオペレーティングシステム（Ｏ／Ｓ）１０４を保持することが可能である。オペレーティングシステム１０４は基本的にコンピュータプログラムの実行を制御し、スケジューリング、入出力制御、ファイル及びデータの管理、メモリ管理、並びに通信の制御とそれに関連するサービスを提供する。

[0043] コンピュータ１００の記憶装置１０５は、固定記憶装置又は携帯可能記憶装置を含む、多くの異なる種類の記憶装置の１つとすることができる。一例として、記憶装置１０５は、磁気テープ、ディスク、フラッシュメモリ、揮発性メモリ、又は別種の記憶装置とすることができる。また、記憶装置１０５は、セキュアデジタルメモリカードや他の取り外し可能記憶装置１０５とすることができる。

[0044] Ｉ／Ｏ装置１０６は、これらに限定されないが、タッチスクリーン、キーボード、マウス、スキャナ、マイクロフォン、又は他の入力装置等の入力装置を含むことができる。さらに、Ｉ／Ｏ装置１０６は出力装置、これらに限定されないが、例えばディスプレイ、又は他の出力装置も含むことができる。Ｉ／Ｏ装置１０６は、入力と出力の両方を介して通信する装置、例えば、これらに限定されないが、変調器／復調器（別の装置、システム、又はネットワークにアクセスするためのモデム）、無線周波（ＲＦ）、ワイヤレス、又は他のトランシーバ、電話インタフェース、ブリッジ、ルータ、又は入力と出力の両方として機能する他の装置をさらに含むことができる。

[0045] 当業者にはよく知られるように、映像の圧縮は、映像シーケンス中の冗長な情報を取り除くことによって実現される。多くの異なる映像符号化標準が存在しており、その例にはＭＰＥＧ−１、ＭＰＥＧ−２、ＭＰＥＧ−４、Ｈ．２６１、Ｈ．２６３、及びＨ．２６４／ＡＶＣが含まれる。本発明は、特定の映像符号化標準の適用に限定される意図はないことに留意されたい。ただし、最新の映像符号化標準であるため、以下ではＨ．２６４／ＡＶＣ標準の例を使用して本発明を説明する。Ｈ．２６４／ＡＶＣでは、映像の各フレーム又はピクチャを数個のスライスに分割することができる。そしてスライスを、マクロブロックと呼ばれる１６×１６画素のブロックに分割し、そのマクロブロックをさらに、８×１６、１６×８、８×８、４×８、８×４、そして４×４までのブロックに分割することができる。

[0046] 図２に、本発明を適用することができるビデオエンコーダの概略図を示す。図に示すブロックは、プロセッサ１０１がメモリ１０２のソフトウェア１０３を実行することによって実現される機能モジュールを表す。ビデオフレーム２００のピクチャがビデオプリコーダ２０１に供給される。ビデオプリコーダは、ピクチャ２００をマクロブロック２００Ａ単位で処理する。各マクロブロックは、ピクチャ２００の数個のピクチャサンプルを含んでいる。各マクロブロックに対して変換係数への変換が行われ、次いで、変換係数レベルへの量子化が行われる。さらに、符号化ステップを直接画素データに行うのではなく、画素データと予測画素値との差に行うために、フレーム内予測又は動き保証を使用し、それにより、より容易に圧縮できる小さな値を実現する。

[0047] 各スライスに対して、プリコーダ２０１はいくつかの構文要素を生成し、その構文要素が、個々のスライスのマクロブロックを符号化したバージョンを形成する。構文要素中のすべての残余データ要素（変換係数レベルや、スキップされた変換係数レベルを示す重要度マップ等、変換係数の符号化に関連する）を残余データ構文要素と呼ぶ。この残余データ構文要素の他に、プリコーダ２０１によって生成される構文要素は、各マクロブロックがどのように符号化され、どのように復号すべきかについての制御情報をそれぞれ含む制御情報構文要素を含んでいる。すなわち、構文要素は２つのカテゴリに分けることができる。第１のカテゴリでは、制御情報構文要素は、例えば、マクロブロックの種類、部分マクロブロックの種類に関係する要素、空間タイプと時間タイプ両方の予測モードについての情報、スライス単位及びマクロブロック単位の制御情報を含む。第２のカテゴリでは、量子化された変換係数のブロック内のすべての有意係数の位置を示す重要度マップや、有意係数の値（量子化ステップに対応するレベルを単位として示される）等のすべての残余データ要素が組み合わせられ、残余データ構文要素になる。

[0048] プリコーダ２０１は構文要素をエントロピーコーダ２０２に出力する。エントロピーコーダ２０２は、ＣＡＢＡＣエンコーダであり、下記でより詳細に説明する。エントロピーコーダ２０２は、各スライスの算術符号語を生成する。スライスの算術符号語を生成する際、エントロピーコーダ２０２は、映像信号のビットストリーム中の構文要素のデータ値間の統計的依存関係を利用する。エントロピーコーダ２０２は、ピクチャ２００のスライスの算術符号語を図３に示すエントロピーデコーダに出力する。

[0049] 図３は、本発明を適用することが可能なビデオデコーダの概略図である。上記と同様に、図３に示すブロックは、プロセッサ１０１がメモリ１０２のソフトウェア１０３を実行することによって実現される機能モジュールを表す。エントロピーデコーダ３０１は、ＣＡＢＡＣデコーダであり、下記でより詳細に説明するが、算術符号語を受け取り、符号語を復号して構文要素に戻す。プリコードデコーダ３０２は、マクロブロック単位、次いでスライス単位でピクチャ３００内の画素のピクチャサンプルを取得するために構文要素を使用する。

[0050] 図４は、構文要素を符号化して算術符号語にするエントロピーコーダ２０２の機能モジュールを示す。これらの機能モジュールは、プロセッサ１０１がメモリ１０２のソフトウェア１０３を実行することによって実現される。シンボルのＣＡＢＡＣ符号化処理は、３段階の処理、すなわち、２値化、コンテクストのモデル化、及び２値算術符号化、からなる。第１段階の処理を行うために、エントロピーコーダ２０２はバイナライザ４０１を備える。バイナライザ４０１の入力は、スイッチ４０３を介して入力４０２に接続される。入力４０２は、エントロピーコーダ２０２で符号化する構文要素を提供する。スイッチ４０３は、入力４０２に到着する構文要素を、バイナライザ４０１又は２値化出力４０４のいずれかに渡すことができ、それによりバイナライザ４０１を迂回（バイパス）する。スイッチ４０３は、２値でない構文要素はバイナライザ４０１に渡すように機能する。２値化形態にない構文要素の例は、動きベクトル差及び変換係数レベルである。スイッチ４０３はまた、構文要素がすでに２値化形態である場合は、入力４０２からの構文要素を２値化出力４０４に直接渡すように機能する。

[0051] バイナライザ４０１は、非２値の構文要素をビン列に対応付ける。「ビン（bin）」とは、非２値をビット列に対応付ける２値化マッピングを定義する符号化ツリーのノードにおいて、符号化ツリーの根ノードから、２値化しようとする非２値構文要素の非２値に対応する符号化ツリーの葉ノードに遷移する際に行わなければならない二分決定を意味する。したがって、ビン列は、ビン又は二分決定のシーケンスであり、各ビットが二分決定の結果である同数のビットを有する符号語に対応する。ビン列は、非常に効率的な２値算術符号化を可能にするように、構文要素の確率分布に合わせて適合される。

[0052] バイナライザ４０１から出力されたビン列は、直接２値化出力４０４に渡してはならず、バイナライザ４０１から出力されるビン列と、すでに２値化された構文要素とを併合するために、バイナライザ４０１の出力と出力４０４との間に配置されたビンループオーバー手段４０５によって出力４０４に制御可能に渡され、それにより、バイナライザ４０１を迂回して出力４０４で単一のビットストリームにする。

[0053] 第２段階の処理を行うために、エントロピーコーダ２０２は、コンテクストモデラー４０６とスイッチ４０７を備える。コンテクストモデラー４０６の入力は、スイッチ４０７を介して２値化出力４０４に接続される。コンテクストモデラー４０６の出力は、通常符号化エンジン４０８に接続される。スイッチ４０７は、ビンシーケンスのビット又はビンをコンテクストモデラー４０６又はバイパス符号化エンジン４０９のいずれかに渡すように機能し、それによりコンテクストモデラー４０６を迂回する。

[0054] 到着する各ビンについて、コンテクストモデラー４０６はコンテクストモデルを選択し、コンテクストモデルは、ビン列中のビンの値間の統計的依存関係をモデル化する確率分布を近似し、ビン列中での個々のビンの出現頻度を推定するために通常符号化エンジン４０８で使用される。各ビンには数個のコンテクストが割り当てられ、所与のビンを符号化するために選択されるコンテクストは、処理中の構文要素によって記述される現在のマクロブロックの前後にあるマクロブロックの特性に応じて決まる。コンテクストモデルへのビンの割り当ては、同じコンテクストモデルに属するビンの実際の確率分布が同一又は類似した振る舞いを示すようになされ、特定のコンテクストモデルによるビン値の確率推定が、そのコンテクストモデルに割り当てられたすべてのビンの実際の確率の良好な近似となるようにする。

[0055] ビン値の確率分布は符号化の開始時には未知であり、異なる映像シーケンスごとに異なることに留意されたい。その結果、ＣＡＢＡＣに高い符号化効率をもたらす特性の１つは、符号化対象のビンの確率を記憶するコンテクストが適応的であることである。具体的には、符号化中に、ビン確率の正確な推定を実現するためにコンテクストが更新される。コンテクストの更新は、先に符号化されたビンの値に応じて行われる。同じビン又は同じ構文要素はビン内で数回出現するが、先に符号化されたビンに応じて、出現のたびに異なるコンテクストモデルに割り当てることができる。２値算術符号化に使用される確率推定が符号化の効率を決定するので、符号化中に確率推定が常に実際の確率を非常に有効に近似するように、ビン値間の統計的依存関係を高度に活用する適切なコンテクストモデルを持つことが重要である。

[0056] 入力されたビンにコンテクストモデルを割り当てると、コンテクストモデラー４０６は、そのビンを、ビンが割り当てられたコンテクストモデルと共に通常符号化エンジン４０８に渡す。通常符号化エンジン４０８は、第３段階の処理を行い、コンテクストモデラー４０６から渡されたビンの値を、同じくコンテクストモデラー４０６から渡されたコンテクストモデルを使用して算術符号化する。さらに、通常符号化エンジン４０８は、コンテクストモデルを更新するためのビン値を、フィードバック線４１０を通じてコンテクストモデラー４０６に渡す。

[0057] 通常符号化エンジン４０８は、コンテクストモデラー４０６からビンを受け取るたびに、同じくコンテクストモデラー４０６から受け取られるコンテクストモデルに従って、ビン値の出現確率を推定する。そして、通常符号化エンジン４０８は、その確率の推定を使用してビンを算術符号化する。また、ビンを符号化するたびに、通常符号化エンジン４０８は、先に符号化された少なくとも１つのビンの値に基づいて、次のビンの符号化のための確率推定を適応的に更新する。一実施形態では、通常符号化エンジン４０８は、先に符号化した少なくとも１つのビンの値に基づいて、受け取ったコンテクストモデルに従って確率推定を計算する。

[0058] 別の実施形態では、通常符号化エンジン４０８は、Ｈ．２６４／ＡＶＣで定義されるように有限状態機械であり、コンテクストモデルに関連するテーブルを有する。各コンテクストモデルテーブルには確率推定が記憶されている。有限状態機械であるため、通常符号化エンジン４０８は確率推定の計算は行わない。代わりに、通常符号化エンジン４０８は、すべての確率推定を事前定義された定数としてコンテクストモデルテーブルに有する。各コンテクストモデルテーブルに記憶された確率推定は、選択的に確率索引で識別される。したがって、コンテクストモデラー４０６からビン及びコンテクストモデルを受け取るたびに、通常符号化エンジン４０８は、まず、受け取ったコンテクストモデルに関連付けられたテーブルを選択する。そして、通常符号化エンジン４０８は、そのテーブルを探索し、確率索引を使用して、ビンを符号化するために必要な確率推定をテーブルから見つける。また、通常符号化エンジン４０８は、構文要素又はビンがそこから導出されたピクチャ又はビデオフレームの特性又は属性に合わせて確率推定を適応させるために、確率索引を更新することで確率推定を更新する。確率索引の更新も、同様に、先に符号化された少なくとも１つのビンに基づく。

[0059] バイパス符号化エンジン４０９は、静的な所定の確率推定を使用してビン列を算術符号化するものである。バイナライザ４０１から出力されるビン列中のビンの一部は、確率が等しい分布を示す。これは、１つのビン列中のビンに対応するビットが半々の確率で１又は０であることを意味する。これらのビンがバイパス符号化エンジン４０９に供給され、確率が等しい確率推定を使用して算術符号化される。確率が等しい確率推定は一定であり、したがって、コンテクストモデルの選択と確率推定の更新に伴う計算オーバーヘッドを解消する。

[0060] 通常符号化エンジン４０８及びバイパス符号化エンジン４０９から出力される符号化ビットはスイッチ４１２により出力４１１で併合されて１つのビットストリームとなる。このビットストリームは、入力端子４０２に入力された構文要素の２値算術符号語に相当する。通常符号化エンジン４０８及びバイパス符号化４０９は、適応的又は静的な確率推定に基づく算術符号化を行うために協働する。

[0061] 図５は、算術符号語を復号して構文要素に戻すエントロピーデコーダ３０１の機能モジュールを示す。これらのモジュールは、プロセッサ１０１がメモリ１０２のソフトウェア１０３を実行することによって実現される。図５で、算術符号語は、スイッチ５０３の動作により、通常復号エンジン５０１又はバイパス復号エンジン５０２のいずれかで受け取られる。スイッチ５０３は、通常符号化エンジン４０８で符号化された算術符号語を選択的に通常復号エンジン５０１に渡し、バイパス符号化エンジン４０９で符号化された算術符号語をバイパス復号エンジン５０２に渡すように機能する。通常復号エンジン５０１は、コンテクストモデラー５０４から提供されるコンテクストモデルに従った適応確率推定を使用して、受け取った符号語を復号して復号ビンにする。バイパス復号エンジン５０２は、確率が等しい静的確率推定を使用して、受け取った符号語を復号して復号ビンにする。復号されたビンは、スイッチ５０６の動作により、逆２値化のためにデバイナライザ（de-binarizer）５０５に進むか、又はデバイナライザ５０５を迂回する。デバイナライザ５０５は、復号されたビンを逆２値化して構文要素にする。構文要素は、通常復号エンジン５０１に提供されるコンテクストモデルの更新のために、コンテクストモデラー５０４にフィードバックされる。符号語を復号するたびに、通常復号エンジン５０１は、先に復号された少なくとも１つのビンに基づいて確率推定を更新する。

[0062] 一実施形態では、通常復号エンジン５０１は、先に復号された少なくとも１つのビンに基づいて、受け取ったコンテクストモデルに従って確率推定を計算する。別の実施形態では、通常復号エンジン５０１は、Ｈ．２６４／ＡＶＣで定義されるように有限状態機械であり、コンテクストモデルに関連付けられたテーブルを有する。各コンテクストモデルテーブルには確率推定が記憶されている。有限状態機械であるため、通常復号エンジン５０１は確率推定の計算は行わない。代わりに、通常復号エンジン５０１は、すべての確率推定を事前定義された定数としてコンテクストモデルテーブルに有する。各コンテクストモデルテーブルに記憶された確率推定は、確率索引で選択的に識別される。したがって、算術符号語及びコンテクストモデルを受け取るたびに、通常復号エンジン５０１は、まず、受け取ったコンテクストモデルに関連付けられたテーブルを選択する。そして、通常復号エンジンは、テーブルを探索し、確率索引を使用して、符号語の符号化に必要な確率推定をテーブルから見つける。また、通常復号エンジン５０１は、確率索引を更新することにより、確率推定を更新する。確率索引の更新は、先に復号された少なくとも１つのビンに基づく。

[0063] 次いで、エントロピーコーダ２０２及びエントロピーデコーダ３０１の詳細な動作を説明するために、添付のフローチャートに、ＣＡＢＡＣ符号化及び復号用のエントロピーコーダ２０２及びエントロピーデコーダ３０１によって行われるソフトウェア処理を示す。添付のフローチャートに記載される符号化及び復号処理は、プロセッサ１０１がメモリ１０２のソフトウェア１０３を実行することによって実現される図４及び図５に示すエントロピーコーダ２０２及びエントロピーデコーダ３０１の機能モジュールが共同して行うことを理解されたい。また、以下の説明では、まずテーブルを使用せずに確率を計算する実施形態を使用し、次いで、テーブルを使用して確率を得る有限状態機械を採用した別の実施形態を使用して本発明を説明することに留意されたい。

[0064] 以下の説明では、２値シンボルは、Ａ又はＢいずれかの値をとる。これらの値は、単に、２値シンボルがとる２つの可能な値を区別するために使用する。また、２値シンボルを算術符号化する処理では確率推定ｐが使用され、確率推定ｐは、シンボルＢに関連付けられた確率を表す。或いは、確率推定ｐはｑ（＝１−ｐ）に置き換えてもよく、ｐの更新もそれに応じて変更される。

[0065] 図６は、エントロピーコーダ２０２で実施される例示的な初期化処理を示すフローチャートである。初期化処理では、ステップ６０１で確率推定ｐが初期確率推定ｐ_０に初期化される。初期確率推定ｐ_０は、予め決められた値である。一実施形態では、初期確率推定ｐ_０は、０より大きく、１より小さい確率の固定小数点表現である。ステップ６０２で、サフィックス（suffix）の大きさｓも初期サフィックスの大きさｓ_０に初期化する。サフィックスの大きさｓは、符号化するビン列の長さを決定し、本発明では、切捨て単項２値化処理と同様の処理で導出される。サフィックスの大きさｓが大きくなるとビン列の長さが短くなり、その逆も同様である。一実施形態では、初期サフィックスの大きさｓ_０は０（「ゼロ」）である。

[0066] ステップ６０３で、確率推定ｐを所定の閾値Ｔｈ_ｌｏｗと比較する。一実施形態では、閾値Ｔｈ_ｌｏｗは、値１／８の固定小数点表現に相当する。確率推定ｐが閾値Ｔｈ_ｌｏｗ以上である場合、初期化処理は終了する。確率推定ｐが閾値Ｔｈ_ｌｏｗより小さい場合、処理は、ステップ６０４に進み、２×ｐ−（ｐの２乗）を確率推定ｐに代入する。そして、ステップ６０５で、サフィックスの大きさｓを１増分する。その後流れは比較ステップ（ステップ６０３）に戻る。ステップ６０４及び６０５は、確率推定ｐが閾値Ｔｈ_ｌｏｗ以上になるまで繰り返される。図６に示す初期化処理のためのＣ言語式の擬似コードを下記に示す。
init_suffix(context) (
suffix_size[context] = 0;
while (p[context] < 0x2000) (
suffix_size[context]++;
p[context] = 2*p[context] - ((p[context]*p[context] +
0x8000) >> 16);
)
)

[0067] 本発明では、確率推定ｐの値に基づいてサフィックスの大きさｓを適応的に変更する。確率推定ｐが小さい時は、サフィックスの大きさｓを増して符号化するビン列の長さを短くすることが望ましい。ＣＡＢＡＣでは、部分範囲Ｒ０は範囲レジスタの値と確率推定ｐの積であるため、確率推定ｐが小さい場合は部分範囲Ｒ０が小さくなる。また、ＣＡＢＡＣでは部分範囲Ｒ０を求める処理は反復的であり、符号化するビン列中のビンの数に等しい回数繰り返され、部分範囲Ｒ０は、ビン列のビンに符号化が進行するにつれて反復的に小さくなる。したがって、確率推定ｐが小さい場合は、反復的に小さくなっていく部分範囲Ｒ０が、有限精度の制約下では符号化エンジンで正確に表現されなくなり、結果として符号化の非効率性を増大させ、計算量を増加させる。本発明では、確率推定ｐが小さい場合は、サフィックスの大きさｓを大きくするように変更して、符号化するビン列を短くし、それにより、部分範囲Ｒ０の反復的な減少の回数を減らす。したがって、サフィックスの大きさｓが増加すると、結果として算術符号化の効率が向上し、その複雑度が低減することが予想される。

[0068] しかし、サフィックスの大きさｓを増分すると、確率推定ｐの調整が必要となる。サフィックスの大きさｓを１だけ増分することにより、確率推定ｐで別個に符号化されるはずのビン列中の２つの２値シンボル又はビンが共に符号化される。下記で述べるように、本発明によるシンボルの２値化では、一連の２値シンボルＡが得られ、これは、切捨て単項２値化処理と同様の処理で導出される。また、上記のように、確率推定ｐは、シンボルＢに関連付けられた確率を表すように定義される。したがって、それぞれが確率推定（１−ｐ）に関連付けられた２つの２値シンボルＡを共に符号化するために使用される調整後の確率推定（１−ｐ’）は、
（１−ｐ’）＝（１−ｐ）^２又はｐ’＝２ｐ−ｐ^２
となる。

[0069] 別の実施形態では、初期確率推定ｐ_０及び初期サフィックスの大きさｓ_０は、ステップ６０３、６０４及び６０５の補正ループを不要にするように選択することができる。別の実施形態では、ｐ及びｓの値をユーザが選択できるようにし、エンコーダからデコーダに送信される。さらに別の実施形態では、ｐ及びｓの値は、量子化ステップ又はフレームサイズの関数とすることができる。量子化の刻みを小さくすると変換係数が大きくなり、フレームサイズを大きくすると動きベクトル値が大きくなる。

[0070] 図７は、エントロピーコーダ２０２によって行われる、本発明の一実施形態による符号化処理を示すフローチャートである。このフローチャートに示す符号化処理は整数シンボルＮを符号化することを想定し、シンボルＮは符号付きである場合も、符号なしの場合もある。整数シンボルＮは、画像コーデック、映像コーデック、若しくは音声コーデックの変換係数の値、映像コーデック中の動きベクトル差、又は他の類似の整数データを表すことができる。図７に示すフローチャートでは、ステップ７０１でＮの値を０（「ゼロ」）と比較する。Ｎの値が０に等しい場合は、ステップ７０２で確率推定ｐを使用して２値シンボルＢを符号化し、ステップ７０２で確率推定ｐを更新し、その後流れが終了する。Ｎの値が０に等しくない場合は、ステップ７０４で確率推定ｐを使用して２値シンボルＡを符号化し、ステップ７０５で確率推定ｐを更新する。

[0071] 図８は、図７のステップ７０３及び７０５で行われる確率推定ｐの更新処理を示すフローチャートである。図８のステップ８０１で、前回符号化されたシンボルがシンボルＡであるかどうかを判定する。最後の符号化シンボルがシンボルＡである場合、ステップ８０２で確率推定ｐの現在の値に定数ａの値を乗算する。最後の符号化シンボルがシンボルＡでない場合は、ステップ８０３で確率推定ｐの現在の値に定数ａの値を乗算し、（１−定数ａの値）を足す。定数ａの値は、０より大きく、１より小さい。定数ａの値は、確率推定ｐがどれほど迅速に基礎となるソースの確率分布に合わせて適応されるかを決定する。定数ａの値が小さいほど、適応が速くなる。一実施形態では、定数ａは、１−２^−ｍで定義することができ、ｍは、更新処理で乗算の算術演算を回避するように正の整数から選択される。ｍは、５などの所定の値とするか、又はエンコーダからデコーダに送信することができる。確率推定ｐを更新するためのＣ言語式の擬似コードを下記に示す。
update(context, symbol) (
if (val == 0)
p[context] += (Oxffff - p[context] + round) >> loss rate;
else
p[context] -= (p[context] + round) >> loss_rate;
)

[0072] 図７に戻り、ステップ７０２又は７０４で符号化されたシンボルＡ又はＢは、符号化されたシンボルが非ゼロの整数であるか、又はゼロに等しいかをデコーダに知らせるヘッダ情報として機能する。ステップ７０５の後、処理はステップ７０６に進み、Ｎの絶対値を符号化する。Ｎの絶対値を符号化する処理については、図９を参照して下記で詳細に説明する。引き続き図７で、シンボルＮが符号付き整数の場合は、ステップ７０７で符号値を符号化する。符号値は、負のシンボルの場合は１の値を有する１ビットの符号シンボルで表される。１ビットの符号シンボルは、図４に示すバイパス符号化エンジン４０９を通じて算術符号化される。

[0073] 図９は、図７のステップ７０６の処理を詳細に示すフローチャートであり、このステップではシンボルＮの絶対値が符号化される。図９のステップ９０１で、値Ｎが２の（サフィックスの大きさｓ）乗と比較される。演算子「＜＜」は、ビット単位の左シフトを要求し、「１＜＜ｓ」は、２の（サフィックスの大きさｓ）乗の数学演算を要求する。シンボルＮの絶対値が２の（サフィックスの大きさｓ）乗より大きい場合、流れはステップ９０２に進み、確率推定ｐを使用して２値シンボルＡを符号化する。そして、ステップ９０３でＮの値から２の（サフィックスの大きさｓ）乗を引く。２値化は、非２値シンボルを２値シンボルの列にマッピングする処理である。ステップ９０３は、シンボルＮの値から取り出された（１＜＜ｓ）の値が１つの２値シンボル又はビンにマッピングされることを示唆する。したがって、（１＜＜ｓ）の値は、１つのビン当たりのマッピング値又はマッピング単位値を表す。

[0074] 次いで、ステップ９０４で、図８に示す上記処理を通じて確率推定ｐを更新する。ステップ９０５でサフィックスの大きさｓも更新する。その後、流れはステップ９０１に戻り、値Ｎを２の（サフィックスの大きさｓ）乗、すなわちマッピング単位値と比較する。したがって、ステップ９０１、９０２、９０３、９０４及び９０５の処理ループは、値Ｎがマッピング単位値以下になるまで繰り返される。本発明では、符号化及び２値化は、１回の符号化ごとに並行して行われる。符号化のたびに、ステップ９０３でマッピング単位値がシンボルＮの値から反復的に取り出され、１つのビンにマッピングされ、ステップ９０２でそのビンを符号化する。

[0075] 図１０は、図９に示すステップ９０２の符号化処理を詳細に説明するフローチャートである。ステップ１００１で、範囲レジスタの現在の値Ｒに確率推定ｐを乗算することにより２値シンボルＢの部分範囲値Ｒ０を計算する。そして、ステップ１００２で符号化対象の２値シンボルがシンボルＢであるかどうかを判定する。符号化対象の２値シンボルがシンボルＢである場合は、ステップ１００３で範囲レジスタを部分範囲値Ｒ０に設定する。符号化対象の２値シンボルがシンボルＡである場合は、ステップ１００４で、範囲レジスタの現在の値Ｒから部分範囲Ｒ０を減算する。また、ステップ１００４で、オフセットレジスタの現在の値Ｌに部分範囲値Ｒ０を加算する。図９のステップ９０２では２値シンボルＡを符号化するため、図１０のステップ１００２で行われる判定はステップ１００４に至ることに留意されたい。ステップ１００３又は１００４で範囲レジスタ及びオフセットレジスタを更新した後、ステップ１００５で再正規化を行う。当業者は再正規化処理について知っていると思われるため、この処理については本明細書ではこれ以上詳細には説明しない。

[0076] 図１１は、サフィックスの大きさｓが更新される図９のステップ９０５で行われる処理を詳細に説明するフローチャートである。図１１に示すフローチャートは、図９のステップ９０２で２値シンボルＡが符号化された後に呼び出される。ステップ１１０１で、確率推定ｐを、図６に示す初期化処理で使用される閾値Ｔｈ_ｌｏｗと比較する。閾値Ｔｈ_ｌｏｗとは異なる値をステップ１１０１の比較ステップで使用してもよい。確率推定ｐが閾値Ｔｈ_ｌｏｗ以上の場合、処理は終了する。確率推定ｐが閾値Ｔｈ_ｌｏｗより小さい場合は、ステップ１１０２で確率推定ｐを調整し、ステップ１１０３でサフィックスの大きさｓを１増分する。サフィックスｓが増分されると、（１＜＜ｓ）のマッピング単位値が増し、シンボルＮは、より少ない数のビンにマッピングされる。図９のステップ９０３を参照されたい。すなわち、ステップ１１０３でサフィックスｓが増分されると、２値化の結果得られるビン列が短くなる。

[0077] 図６に示す初期化処理で述べたように、確率推定ｐが小さい場合は、サフィックスの大きさｓを増して算術符号化の効率を改善し、その複雑度を低減させることが望ましい。確率推定ｐは、サフィックスの大きさｓの増分のために調整する必要がある。ただし、図６のステップ６０４で確率推定ｐに行われる調整処理と異なり、ステップ１１０２で行われる調整処理は、乗算の演算を回避するために簡略化されている。具体的には、ステップ１１０２では、２×ｐ−定数ｋを確率推定ｐに代入する。定数ｋの値は、（Ｔｈ_ｌｏｗ）^２の値に近似するように選択する。この簡略化は、ステップ１１０１で確率推定ｐが閾値Ｔｈ_ｌｏｗより小さいと判定された時に確率推定ｐが閾値Ｔｈ_ｌｏｗに近くなることに基づく。一実施形態では、閾値Ｔｈ_ｌｏｗ及び定数ｋは、それぞれ１／８や１／６４などの１６ビットの固定小数点数を用いて表現される。

[0078] 図９に戻り、ステップ９０１でシンボルＮの値が２の（サフィックスの大きさｓ）乗より大きくないと判定された場合は、ステップ９０６で確率推定ｐを使用して２値シンボルＢを符号化する。２値シンボルＢは、図１０に示す符号化処理を通じて符号化される。符号化された２値シンボルＢは、ビン列中でプレフィックスとサフィックスを分離するための分離ビットとして機能する。次いで処理はステップ９０７に進み、ｓビットを使用してＮ−１の値を２値化してサフィックスを表すビン列にし、それを符号化する。より具体的には、ステップ９０７では、長さＳの固定長符号を使用してＮ−１の値を２値化する。サフィックスを生成するためのＣ言語型の擬似コードを以下に示す。
while (s--)
put(((N-1)>>s) & 0x01)

[0079] 次いで、生成されたサフィックスを図４のバイパス符号化エンジン２１２で符号化する。サフィックスの大きさｓが０（「ゼロ」）の場合は、値の符号化はない。この段階で、シンボルＮの最大値は２の（サフィックスの大きさｓ）乗であり、シンボルＮの最小値は１であるので、シンボルＮの値を正確に符号化するにはｓビットで足りる。次いで、図８に示す処理を通じて、ステップ９０８で確率推定ｐを更新する。

[0080] 図１２は、図７のステップ７０７及び図９のステップ９０７で行われる迂回符号化の処理を示すフローチャートである。図１２のステップ１２０１で、オフセットレジスタの現在の値について値「１」をビット単位で左シフトし、オフセットレジスタに代入する。次いで、ステップ１２０２で、符号化対象の２値シンボルがシンボルＢであるかどうかを判定する。符号化対象の２値シンボルがシンボルＢである場合は、流れはステップ１２０４に進み、再正規化を行う。符号化対象の２値シンボルがシンボルＡである場合は、ステップ１２０３で、オフセットレジスタの現在の値Ｌに部分範囲値Ｒ０を加算する。オフセットレジスタを更新した後、ステップ１２０４で再正規化を行う。

[0081] 図９に戻り、ステップ９０９で図１３に示す処理を通じてサフィックスの大きさｓも更新する。図１３の処理は、前回符号化された２値シンボルが２値シンボルＢである時に呼び出される。

[0082] 図１３で、ステップ１３０１で、確率推定ｐを閾値Ｔｈ_ｈｉｇｈと比較し、サフィックスの大きさｓを０と比較する。一実施形態では、閾値Ｔｈ_ｈｉｇｈは、２×Ｔｈ_ｌｏｗ−ｋ（２Ｔｈ_ｌｏｗ−ｋ）に設定される。確率推定ｐが閾値Ｔｈ_ｈｉｇｈ以下で、サフィックスの大きさｓが０（「ゼロ」）に等しい場合は、処理は終了する。確率推定ｐが閾値Ｔｈ_ｈｉｇｈより大きく、サフィックスの大きさｓが０（「ゼロ」）より大きい場合は、処理はステップ１３０２及び１３０３に進み、サフィックスの大きさｓを１減分し、確率推定ｐを（ｐ＋ｋ）／２に調整する。ステップ１３０２で行われる確率の調整は、図１１のステップ１１０２に示す調整操作の逆であることに留意されたい。サフィックスｓを減分すると、（１＜＜ｓ）のマッピング単位値が減少し、シンボルＮがより多くのビンにマッピングされる。図９のステップ９０３を参照されたい。すなわち、ステップ１３０３でサフィックスｓが減分されると、２値化の結果得られるビン列が長くなる。

[0083] 確率推定ｐが小さいと符号化の効率が損なわれることは図１１で説明した。本発明では、確率推定ｐが低い場合はサフィックスの大きさｓを増分して符号化効率を向上させる。一方、確率推定ｐが高い場合は、ビンのストリームをより少ないビットで符号化することができ、符号化の効率が向上する。しかし、多数のシンボルを少数のビットに符号化すると、符号化効率は向上するが、デコーダにおける全体的な処理速度は低下する。本発明では、確率推定ｐが高い場合は、サフィックスの大きさｓを減らしてビンストリーム中のビン数を増し、それにより符号化効率を下げる。サフィックスの大きさｓを下げると符号化の効率は低下するが、デコーダにおける全体的な処理速度を向上させることが予想される。

[0084] 図１１及び１３に示す処理は組み合わせて図１４に示すような単一の処理としてもよいことに留意されたい。図１４では、図１１及び１３で用いる番号と同じ番号でステップを参照する。サフィックスの大きさｓを更新するためのＣ言語型の擬似コードを以下に示す。
update_suffix(context) (
if (p[context] < 0x2000) (
p[context) = 2*p[context] - 0x400;
suffix_size(context)++;
)
else if (p[context] > 0x3c00 && suffix_size[context] != 0) (
p[context] = (p[context] + 0x400) >> 1;
suffix_size[context]--;
)
)

[0085] 次いで、本発明による復号処理を説明する。添付のフローチャートにエントロピーデコーダ３０１によって行われる復号処理を示す。復号処理では、算術符号語を復号してビン列に戻し、ビン列を逆２値化してシンボルＮにする。復号処理は基本的に符号化処理の逆であり、エントロピーエンコーダ２０２でシンボルＮに行われた処理を元に戻すものである。フローチャートに示す復号処理は、図５に示す機能モジュールが共同して実装し、それらの機能モジュールは、上述のように、プロセッサ１０１がメモリ１０２のソフトウェア１０３を実行することによって実現されることに留意されたい。

[0086] 図１５は、エントロピーデコーダ３０１によって行われる初期化処理を示すフローチャートである。初期化処理では、ステップ１５０１で、確率推定ｐを初期化して初期確率推定ｐ_０にする。初期確率推定ｐ_０は予め決められた値である。一実施形態では、初期確率推定ｐ_０は、０より大きく１より小さい確率の固定小数点表現である。ステップ１５０２で、サフィックスの大きさｓも初期化して初期サフィックスの大きさｓ_０とする。サフィックスの大きさｓは、ビン列中のビンの遷移を正確に追跡するためにデコーダ３０１で使用される。一実施形態では、初期サフィックスの大きさｓ_０は０（「ゼロ」）である。ステップ１５０３で、確率推定ｐを所定の閾値Ｔｈ_ｌｏｗと比較する。閾値Ｔｈ_ｌｏｗは、図６に示す閾値と同じ値とするべきである。一実施形態では、閾値Ｔｈ_ｌｏｗは、値１／８の固定小数点表現に相当する。

[0087] 確率推定ｐが閾値Ｔｈ_ｌｏｗ以上である場合、初期化処理は終了する。確率推定ｐが閾値Ｔｈ_ｌｏｗより小さい場合は、処理はステップ１５０４に進み、（２×ｐ−ｐの２乗）を確率推定ｐに代入する。次いで、ステップ１５０５でサフィックスの大きさｓを１増分する。流れはその後比較ステップ（ステップ１５０２）に戻る。ステップ１５０４及び１５０５は、確率推定ｐが閾値Ｔｈ_ｌｏｗ以上になるまで繰り返される。ステップ１５０４及び１５０５に示す動作の原理は、図６で説明したものと同じであり、そのためここでは繰り返さない。

[0088] 図１６は、エントロピーデコーダ３０１によって行われる主要な復号処理を示すフローチャートである。ステップ１６０１で、１番目の算術符号語を復号して、シンボルＮの値が０（「ゼロ」）であるかどうかを判定する。この復号処理は図１７に示す。ステップ１６０２で、図１８に示す処理を通じて確率推定ｐを更新する。次いで、ステップ１６０３で、１番目の符号語の復号で２値シンボルＢが得られたかどうかを判定する。復号で２値シンボルＢが得られた場合は、ステップ１６０４でシンボルＮを０（「ゼロ」）に設定し、処理は終了する。

[0089] 図１７は、図５に示す算術デコーダ５０１によって行われる復号処理を示すフローチャートである。ステップ１７０１で、範囲レジスタの値Ｒに確率推定ｐを乗算することにより、部分範囲値Ｒ０を計算する。次いで、ステップ１７０２で、部分範囲値Ｒ０を値レジスタの値Ｖと比較する。部分範囲値Ｒ０が値レジスタの値Ｖより大きい場合は、ステップ１７０３で範囲レジスタを部分範囲値Ｒ０に設定し、ステップ１７０４で２値シンボルＢを放出する。部分範囲値Ｒ０が値レジスタの値Ｖ以下である場合は、ステップ１７０５で範囲レジスタから部分範囲値Ｒ０を減算し、値レジスタから部分範囲値Ｒ０を減算する。次いでステップ１７０６で２値シンボルＡを放出する。流れはステップ１７０７に進み、再正規化を行う。当業者は再正規化処理を知っていると思われるため、この処理については本明細書ではこれ以上詳細には説明しない。

[0090] 図１６に戻り、算術符号語の復号で２値シンボルＡが得られた場合は、流れはステップ１６０５に進み、図１８に示す処理を通じてシンボルＮの絶対値を復号する。次いで、ステップ１６０６で、図１９に示すバイパス復号処理を通じて、符号化された１ビットの符号シンボルを復号する。図１９の処理は、図５に示すバイパス復号エンジン５０２によって行われる。２値シンボル又はビンを復号するためのＣ言語式の擬似コードを以下に示す。
decode_symbol(context) (
R0 = (R * p[context] + 0x8000) >> 16;
R0 = R0 << 15;
if (V < R0) (
symbol = 0;
R = R0;
)
else (
symbol = 1;
R = R - R0;
V = V - R0;
)

while (R < 0x8000) (
R = 2*R;
V = 2*V + getbits(1);
)

update(context, symbol);

return symbol;
)

[0091] 図１８は、符号なしの整数Ｎを復号する例示的処理を示すフローチャートである。ステップ１８０１でＮの値を１に設定する。ステップ１８０２で、図１７に示す復号処理を通じて、確率推定ｐを使用して次の算術符号語を復号する。次いでステップ１８０３で、当該次の算術符号語の復号で２値シンボルＡが得られるかどうかを判定する。当該次の符号語の復号で２値シンボルＡが得られた場合は、流れはステップ１８０４に進み、２の（サフィックスの大きさｓ）乗をＮの値に加算する。ステップ１８０４は、逆２値化により１つのビンが再度マッピング単位値（１＜＜ｓ）にマッピングされることを意味する。次いで、ステップ１８０５で、図２０に示す処理により確率推定ｐを更新する。ステップ１８０６で、図２１に示す処理を通じてサフィックスの大きさｓも更新する。流れはステップ１８０２に戻り、次の算術符号語を復号する。ステップ１８０２〜１８０６の処理ループは算術符号語の復号でビン列のプレフィックスとサフィックスを分離する２値シンボルＢが得られるまで繰り返される。本発明では、復号と逆２値化は、１回の復号のたびに並行して行われる。

[0092] 図１９は、図５に示すバイパス復号エンジン５０２によって行われる例示的なバイパス復号処理を示すフローチャートである。ステップ１９０１で、値レジスタの値Ｖに等しい回数だけ１の２進値をビット単位で左シフトし、値レジスタに代入する。次いで、ステップ１９０２で、部分範囲値Ｒ０を値レジスタの値Ｖと比較する。部分範囲値Ｒ０が値レジスタの値Ｖより大きい場合は、ステップ１９０３で２値シンボルＢを放出する。部分範囲値Ｒ０が値レジスタの値Ｖ以下の場合は、ステップ１９０４で、範囲レジスタから部分範囲値Ｒ０を減算する。次いでステップ１９０５で２値シンボルＡを放出する。

[0093] 図２０は、図１６のステップ１６０２及び図１８のステップ１８０５で行われる確率推定ｐの更新の処理を示すフローチャートである。図２０のステップ２００１で、最後に復号されたシンボルがシンボルＡであるかどうかを判定する。ステップ２００２及び２００３の処理の説明は、上記の図８を説明した段落で得ることができ、そのためここでは繰り返さない。

[0094] 図２１は図１８のステップ１８０６で行われる、サフィックスの大きさｓの更新の処理を詳細に説明するフローチャートである。図２１に示すフローチャートは、算術符号語の復号で２値シンボルＡが得られると呼び出される。ステップ２１０１、２１０２、及び２１０３の説明は、図１１を説明した段落で得ることができ、ここでは繰り返さない。

[0095] 図１８に戻り、ステップ１８０３で復号された２値シンボルが２値シンボルＡでない場合は、流れはステップ１８０７に進み、ｓ個のビンを復号してｓビットの符号なしの整数値を形成し、その値をＮの値に足すことにより、図１９に示すバイパス復号処理で残りの算術符号語を復号する。ステップ１８０８で、図２０に示す処理を通じて確率推定ｐを更新する。ステップ１８０９で、図２２に示す処理を通じてサフィックスの大きさｓも更新する。図２２のステップ２２０１〜２２０３で行われる処理の説明は、上記の図１３を説明した段落で得ることができ、ここでは繰り返さない。整数シンボルを復号するためのＣ言語式の擬似コードを以下に示す。
decode_symbol_unary(context) (
symbol = 1;

while (decode_symbol (context) == 1) (
symbol += 1 << suffix_size[context];
update_suffix(context);
)

for (i=suffix_size[context]-1; i>=0; i--)
symbol += decode_symbol_fixed() << i;

update_suffix(context);

return symbol;
)

[0096] 図２３は本発明の効率を示すグラフである。横軸はソースのパラメータｐを表す。縦軸は、本発明に係るモデルで生成したビットと、最適モデル又はソースのエントロピーで生成したビットとの比を表す。グラフには２つの曲線を示す。「黒塗り四角」をつなぐ曲線は、本発明による調整可能なサフィックスの大きさｓを使用しない従来モデルで示される性能曲線である。「黒塗り三角」をつなぐ曲線は、サフィックスの大きさｓが１に等しい、本発明を使用したモデルで示される性能曲線である。パラメータｐが高い値をとる時は従来モデルが本発明によるモデルより効率的であるのに対し、パラメータｐの値が低くなると本発明によるモデルが従来モデルより効率的になることが見て取れる。

[0097] 上記のように、図４に示す通常の符号化エンジン４０８及び図５に示す通常の復号エンジン５０１は、有限状態機械であってもよい。有限状態機械は、コンテクストモデルに関連するテーブルを有する。各コンテクストモデルテーブルには確率推定が記憶されている。有限状態機械は確率推定を計算しない。代わりに、有限状態機械は、すべての確率推定を事前定義された定数としてコンテクストモデルテーブルに備える。各コンテクストモデルテーブルに記憶された確率推定は、確率の索引で選択的に識別される。上記で説明したフローチャートの処理を以下のように変更すると、有限状態機械によって行われる処理の記述を提供することができる。

[0098] 本発明による有限状態機械はｐＳｔａｔｅＩｄｘ及びＴｈＳｔａｔｅＩｄｘを使用する。ｐＳｔａｔｅＩｄｘは、コンテクストモデルテーブル中で索引付けされた確率推定の中から確率推定を識別する確率状態索引である。コンテクストモデルテーブルの例示的構造を図２４に示し、索引０，１，２．．．、すなわちｐＳｔａｔｅＩｄｘの索引値と関連付けて確率推定ｐ_０，ｐ_１，ｐ_２．．．が記憶されている。

[0099] 図６を以下のように変更して、有限状態機械の初期化処理を説明する。ステップ６０１の初期確率推定ｐ_０はｐ（ｐＳｔａｔｅＩｄｘ_０）になる。ｐＳｔａｔｅＩｄｘ_０は、図２４に示すようなコンテクストモデルテーブルに記憶された初期確率推定ｐ_０を識別する索引に相当する。ステップ６０３の比較演算「ｐ＜Ｔｈ_ｌｏｗ」は、「ｐ（ｐＳｔａｔｅＩｄｘ）＜ｐ（ＴｈｌｏｗＳｔａｔｅＩｄｘ）」に置き換えられる。ｐ（ｐＳｔａｔｅＩｄｘ）は、ｐＳｔａｔｅＩｄｘの現在の索引値で識別されるコンテクストモデルテーブルに記憶された確率推定である。ｐ（ＴｈｌｏｗＳｔａｔｅＩｄｘ）は、閾値_（低）を表す確率である。ｐＳｔａｔｅＩｄｘとｐ（ｐＳｔａｔｅＩｄｘ）の間、及びＴｈｌｏｗＳｔａｔｅＩｄｘとｐ（ＴｈｌｏｗＳｔａｔｅＩｄｘ）の間で、Ｈ．２６４／ＡＶＣに定義されるように索引値が大きくなるとｐ（ｐＳｔａｔｅＩｄｘ）及びｐ（ＴｈｌｏｗＳｔａｔｅＩｄｘ）が小さくなる関係が成立する場合は、ステップ６０３の比較は「ｐＳｔａｔｅＩｄｘ＞ＴｈｌｏｗＳｔａｔｅＩｄｘ」に置き換えることができる。ステップ６０４における「ｐ←２ｐ−ｐ×ｐ」の更新動作は、「ｐＳｔａｔｅＩｄｘ←ＴｒａｎｓＩｄｘ（ｐＳｔａｔｅＩｄｘ）」に置き換えられる。有限状態機械は、また、図２６に示すような遷移テーブルを有し、ｐＳｔａｔｅＩｄｘの調整後の索引値がｐＳｔａｔｅＩｄｘの現在の索引値と関連付けて記憶される。遷移テーブルは、ｐＳｔａｔｅＩｄｘの現在の値で識別される確率推定ｐについて、ＴｒａｎｓＩｄｘｄｘ（ｐＳｔａｔｅＩｄｘ）が、値「２ｐ−ｐ×ｐ」が記憶されているコンテクストテーブルの位置を識別する調整後の索引を提供するように機能する。

[0100] 図７では、ステップ７０２及び７０４の「確率ｐを使用する」演算を「確率ｐ（ｐＳｔａｔｅＩｄｘ）を使用する」演算に置き換える。ステップ７０３及び７０５の「ｐを更新する」動作は「ｐＳｔａｔｅＩｄｘの更新」に置き換える。

[0101] 図８のステップ８０２の「ｐ←ａ×ｐ」及びステップ８０３の「ｐ←ａ×ｐ＋（１−ａ）」の更新動作は、それぞれ「ｐＳｔａｔｅＩｄｘ←ｐＵｐｄａｔｅＩｄｘＢ（ｐＳｔａｔｅＩｄｘ）」及び「ｐＳｔａｔｅＩｄｘ←ｐＵｐｄａｔｅＩｄｘＡ（ｐＳｔａｔｅＩｄｘ）」に置き換える。有限状態機械はまた、図２６に示すような更新テーブルを有し、ｐＳｔａｔｅＩｄｘの更新された索引値がｐＳｔａｔｅＩｄｘの現在の索引値と関連付けて記憶される。更新テーブルは、ｐＳｔａｔｅＩｄｘの現在の値で識別される確率推定ｐについて、ｐＵｐｄａｔｅＩｄｘＡ（ｐＳｔａｔｅＩｄｘ）が、値「ｐ←ａ×ｐ＋（１−ａ）」が記憶されたコンテクストテーブルの位置を識別する更新後の索引を提供し、ｐＵｐｄａｔｅＩｄｘＢ（ｐＳｔａｔｅＩｄｘ）が、値「ｐ←ａ×ｐ」が記憶されたコンテクストテーブルの位置を識別する更新後の索引を提供するように機能する。

[0102] 図９では、ステップ９０２、９０４、９０６、及び９０８の動作を、図７のステップ７０３、７０４、７０４、及び７０５と同様に変更する。図１０では、「Ｒ０←Ｒ×ｐ」の演算を「Ｒ０←Ｒ×ｐ（ｐＳｔａｔｅＩｄｘ）」に置き換える。

[0103] 図１１では、ステップ１１０２の「ｐ←２ｐ−ｋ」の演算を「ｐＳｔａｔｅＩｄｘ←ＴｒａｎｓＩｄｘ（ｐＳｔａｔｅＩｄｘ）」に置き換えることができる。これは、「ｐ←２ｐ−ｋ」は「２ｐ−ｐ×ｐ」の近似であるためである。上記で説明したように、図２６に示すような遷移テーブルには、ｐＳｔａｔｅＩｄｘの調整された索引値がｐＳｔａｔｅＩｄｘの現在の索引値と関連付けて記憶される。ステップ１１０２の演算をそのように置き換えた場合は、図１３のステップ１３０２の「ｐ←（ｐ＋ｋ）／２」の演算が「ｐＳｔａｔｅＩｄｘ←ＴｒａｎｓＩｄｘ^−１（ｐＳｔａｔｅＩｄｘ）」に置き換えられる。ＴｒａｎｓＩｄｘ^−１（ｐＳｔａｔｅＩｄｘ）は、ＴｒａｎｓＩｄｘ（ｐＳｔａｔｅＩｄｘ）を行う際のテーブルの参照方向と逆の方向に遷移テーブルを参照することを意味する。ステップ１１０２の「ｐ←２ｐ−ｋ」の演算は、「ｐＳｔａｔｅＩｄｘ←ｐＳｔａｔｅＩｄｘ−ｋＳｔａｔｅＩｄｘ」に置き換えることができ、ｋＳｔａｔｅＩｄｘは、ｐＳｔａｔｅＩｄｘの現在の索引値と、その調整後の索引値との差を表す。ステップ１１０２の演算をそのように置き換えた場合は、図１３のステップ１３０２の「ｐ←（ｐ＋ｋ）／２」の演算は「ｐＳｔａｔｅＩｄｘ←ｐＳｔａｔｅＩｄｘ＋ｋＳｔａｔｅＩｄｘ」に置き換えられる。図１３のステップ１３０１の演算「ｐ＞Ｔｈ_ｈｉｇｈ」は、「ｐＳｔａｔｅＩｄｘ＜ＴｈｈｉｇｈＳｔａｔｅＩｄｘ」に置き換えられる。ｐ（ＴｈｈｉｇｈＳｔａｔｅＩｄｘ）は、閾値_（高）を表す確率である。図１３のステップ１３０１の演算「ｐ＞Ｔｈ_ｈｉｇｈ」は、「ｐＳｔａｔｅＩｄｘ＜ＴｈｌｏｗＳｔａｔｅＩｄｘ−ｋＳｔａｔｅＩｄｘ」に置き換えることができる。

[0104] 図１５のステップ１５０１、１５０３、及び１５０４は、図６の対応するステップと同様に変更される。図１６のステップ１６０１及び１６０２は、図７ステップ７０２及び７０３と同様に変更される。図１７のステップ１７０１は、図１０のステップ１００１と同様に変更される。ステップ１８０２、１８０５、及び１８０８は、図９の対応するステップと同様に変更される。図２０は図８と同様に変更される。図２１及び２２はそれぞれ図１１及び１３と同様に変更される。

[0105] 図９及び１８に示すように、上記の実施形態では、２値シンボルを符号化又は復号するたびに（サフィックスの大きさｓを更新するステップ９０５及びステップ１８０６）。サフィックスの大きさｓの更新頻度はより少なくしてもよい。例えば、サフィックスの大きさｓの更新は、個々の整数シンボルＮの符号化又は復号中に一度だけ行うのでもよい。

[0106] 前述の説明を読むと当業者には本発明の多くの改変及び変更が明らかになると思われるが、例示として図示及び記載される特定の実施形態は制限的と解釈すべきものでないことを理解されたい。したがって、各種実施形態の詳細の参照は、特許請求の範囲を制限するものではなく、特許請求の範囲自体は、本発明に必須と見なされる特徴のみを記載する。

Claims (22)

1. １回の符号化のたびに、１つの２値シンボルにマッピングされる非２値シンボルの値であるマッピング単位値を、非２値シンボルから１つの２値シンボルに２値化するように構成されたバイナライザと、
   ２値シンボルの値の出現確率である確率パラメータであって複数回の符号化を通じて遷移することが可能な確率パラメータを使用して、前記バイナライザからの２値シンボルを１回の符号化のたびに１つ符号化するように構成された算術符号化エンジンと、
   を備え、
   前記非２値シンボルからの前記マッピング単位値は、前記確率パラメータに合わせて適応的に可変である、
   算術エンコーダ。
2. ビデオエンコーダのプロセッサによって実行されて、
   １回の符号化のたびに、１つの２値シンボルにマッピングされる非２値シンボルの値であるマッピング単位値を、非２値シンボルから１つの２値シンボルに２値化するステップと、
   ２値シンボルの値の出現確率である確率パラメータであって複数回の符号化を通じて遷移することが可能な確率パラメータを使用して、２値シンボルを１回の符号化のたびに１つ符号化するステップと、
   を実施させるコンピュータ実行可能ステップを含み、
   前記マッピング単位値は、前記確率パラメータに合わせて適応的に可変である、
   算術符号化方法。
3. 前記確率パラメータに合わせて適応的に可変のサイズパラメータを使用して、前記サイズパラメータの大きさに基づいて決定される前記マッピング単位値を求めるステップをさらに含む、請求項２に記載の算術符号化方法。
4. 前記非２値シンボルの残り値が前記マッピング単位値以下になるまで、１回の符号化のたびに前記非２値シンボルから前記マッピング単位値を反復的に減算するステップをさらに含む、請求項３に記載の算術符号化方法。
5. １回の符号化のたびに前記確率パラメータを更新するステップをさらに含む、請求項２に記載の算術符号化方法。
6. 前記確率パラメータが所定の閾値よりも小さいか又は大きいかに基づいて、前記サイズパラメータを変更する必要があるかどうかを１回ごとに判定するステップをさらに含む、請求項３に記載の算術符号化方法。
7. 前記確率パラメータが所定の閾値よりも小さい場合に前記サイズパラメータを変更することにより前記マッピング単位値を増大させるステップをさらに含む、請求項３に記載の算術符号化方法。
8. 前記確率パラメータを調整して前記所定の閾値に近づけることで前記マッピング単位値の増大を補償するステップをさらに含む、請求項７に記載の算術符号化方法。
9. 前記確率パラメータが所定の閾値よりも大きい場合に前記サイズパラメータを変更して前記マッピング単位値を減少させるステップをさらに含む、請求項３に記載の算術符号化方法。
10. 前記確率パラメータを調整して前記所定の閾値に近づけることで前記マッピング単位値の減少を補償するステップをさらに含む、請求項９に記載の算術符号化方法。
11. 前記非２値シンボルの前記残り値が前記マッピング単位値以下になった時に、前記サイズパラメータを使用して前記非２値シンボルの前記残り値をサフィックスの２値シンボルに変換し、前記サフィックスの２値シンボルを符号化するステップをさらに含む、請求項４に記載の算術符号化方法。
12. ２値シンボルの値の出現確率である確率パラメータであって複数回の復号を通じて遷移することが可能な確率パラメータを使用して、算術符号語を１回の復号のたびに１つ復号して２値シンボルにするように構成された算術復号エンジンと、
    前記２値シンボルを１回の復号のたびに１つ逆２値化して、非２値シンボルを再構築するために合計される、１つの２値シンボルにマッピングされる非２値シンボルの値であるマッピング単位値にするように構成されたデバイナライザと、
    を備え、
    前記マッピング単位値は、前記確率パラメータに合わせて適応的に可変である、
    算術デコーダ。
13. ビデオデコーダのプロセッサによって実行されて、
    ２値シンボルの値の出現確率である確率パラメータであって複数回の復号を通じて遷移することが可能な確率パラメータを使用して、算術符号語を１回の復号のたびに１つ復号して２値シンボルにするステップと、
    前記２値シンボルを１回の復号のたびに１つ逆２値化して、非２値シンボルを再構築するために合計される、１つの２値シンボルにマッピングされる非２値シンボルの値であるマッピング単位値にするステップと、
    を実施させるコンピュータ実行可能ステップを含み、
    前記マッピング単位値は、前記確率パラメータに合わせて適応的に可変である、
    算術復号方法。
14. 前記確率パラメータに合わせて適応的に可変のサイズパラメータを使用して、前記サイズパラメータの大きさに基づいて決定される前記マッピング単位値を求めるステップをさらに含む、請求項１３に記載の算術復号方法。
15. １回の符号化のたびに前記確率パラメータを更新するステップをさらに含む、請求項１３に記載の算術復号方法。
16. 前記確率パラメータが所定の閾値よりも小さいか又は大きいかに基づいて、１回の復号のたびに、前記サイズパラメータを変更する必要があるかどうかを判定するステップをさらに含む、請求項１４に記載の算術復号方法。
17. 前記確率パラメータが所定の閾値よりも小さい場合に前記サイズパラメータを変更することにより前記マッピング単位値を増大させるステップをさらに含む、請求項１４に記載の算術復号方法。
18. 前記確率パラメータを調整して前記所定の閾値に近づけることで前記マッピング単位値の増大を補償するステップをさらに含む、請求項１７に記載の算術復号方法。
19. 前記確率パラメータが所定の閾値よりも大きい場合に前記サイズパラメータを変更して前記マッピング単位値を減少させるステップをさらに含む、請求項１４に記載の算術復号方法。
20. 前記確率パラメータを調整して前記所定の閾値に近づけることで前記マッピング単位値の減少を補償するステップをさらに含む、請求項１９に記載の算術復号方法。
21. 前記２値シンボルにするステップからの２値シンボルが、分離点となる２値シンボルである時に、残りの算術符号語を復号してサフィックスの２値シンボルにするステップをさらに含む、請求項１３に記載の算術復号方法。
22. 前記サフィックスの２値シンボルを逆２値化して、前記非２値シンボルを再構築するために加算される値にするステップをさらに含む、請求項２１に記載の算術復号方法。

Images