コンテキスト適応型バイナリ算術符号化

コンテキスト適応型バイナリ算術符号化（CABAC ）は、 H.264/MPEG-4 AVC ^{[1] [2]}および高効率ビデオ符号化（HEVC）標準で使用されるエントロピー符号化の一種です。これはロスレス圧縮技術ですが、これが使用されるビデオ符号化標準は、通常、非可逆圧縮アプリケーション向けです。CABACは、ビデオ符号化で使用される他のほとんどのエントロピー符号化アルゴリズムよりもはるかに優れた圧縮を提供することで有名であり、H.264/AVC符号化方式に以前のものよりも優れた圧縮機能を提供する重要な要素の1つです。^[3]

H.264/MPEG-4 AVCでは、CABAC は、標準のベースラインプロファイルで使用されるコンテキスト適応型可変長コーディング(CAVLC) と呼ばれるより単純な方式よりもデコードに大量の処理を必要とするため、標準のメイン プロファイル以上 (拡張プロファイルではない) でのみサポートされています。また、CABAC は並列化やベクトル化が難しいため、他の形式の並列処理 (空間領域並列処理など) と組み合わせて使用​​される場合があります。HEVC では、CABAC は標準のすべてのプロファイルで使用されます。

CABACは算術符号化をベースにしており、ビデオ符号化規格のニーズに適応するためにいくつかの革新と変更が加えられている。^[4]

• バイナリ シンボルをエンコードすることで、複雑さを低く抑え、任意のシンボルのより頻繁に使用されるビットの確率モデリングを可能にします。
• 確率モデルはローカルコンテキストに基づいて適応的に選択され、コーディングモードは通常ローカルでよく相関しているため、確率のより適切なモデリングが可能になります。
• 量子化された確率範囲と確率状態を使用することで、乗算を必要としない範囲除算を使用します。

CABAC には、さまざまなコンテキストに対応する複数の確率モードがあります。まず、すべての非バイナリシンボルをバイナリに変換します。次に、各ビットに対して、コーダが使用する確率モデルを選択し、近くの要素からの情報を使用して確率推定を最適化します。 最後に、算術符号化を適用してデータを圧縮します。

コンテキスト モデリングは、コーディング シンボルの条件付き確率の推定値を提供します。適切なコンテキスト モデルを使用すると、エンコードする現在のシンボルの近傍にある既にコーディングされたシンボルに応じて、異なる確率モデルを切り替えることで、特定のシンボル間の冗長性を活用することができます。コンテキスト モデリングは、CABAC がCAVLCエントロピー コーディング方式に比べてビット レートを約 10% 節約できる理由のほとんどです。

データ シンボルのコーディングには、次の段階が含まれます。

• 2 値化: CABAC は、バイナリ算術符号化を使用します。つまり、バイナリ決定 (1 または 0) のみがエンコードされます。非バイナリ値のシンボル (変換係数やモーション ベクトルなど) は、算術符号化の前に「2 値化」またはバイナリ コードに変換されます。このプロセスは、データ シンボルを可変長コードに変換するプロセスに似ていますが、バイナリ コードは送信前にさらに (算術コーダによって) エンコードされます。
• 2 値化されたシンボルの各ビット (または「ビン」) に対してステージが繰り返されます。
• コンテキスト モデルの選択: 「コンテキスト モデル」は、バイナリ化されたシンボルの 1 つ以上のビンの確率モデルです。このモデルは、最近コード化されたデータ シンボルの統計に応じて、利用可能なモデルの中から選択できます。コンテキスト モデルには、各ビンが「1」または「0」になる確率が格納されます。
• 算術符号化: 算術符号化器は、選択された確率モデルに従って各ビンを符号化します。各ビンには 2 つのサブ範囲 (「0」と「1」に対応) しかないことに注意してください。
• 確率の更新: 選択されたコンテキスト モデルは、実際のコード化された値に基づいて更新されます (たとえば、ビン値が「1」の場合、「1」の頻度カウントが増加します)。

1. x方向の動きベクトルの差の値MVDxを2値化します。

2 値化されたコードワードの最初のビットはビン 1、2 番目のビットはビン 2 などとなります。

2. 各ビンのコンテキスト モデルを選択します。ビン 1 には、以前にコード化された MVD 値に基づいて 3 つのモデルのうち 1 つが選択されます。以前にコード化された 2 つの値の L1 ノルム e _kが計算されます。

e _kが小さい場合、現在の MVD の大きさが小さくなる可能性が高くなります。逆に、e _kが大きい場合、現在の MVD の大きさが大きくなる可能性が高くなります。それに応じて確率テーブル (コンテキスト モデル) を選択します。残りのビンは、次の 4 つのコンテキスト モデルのいずれかを使用してコード化されます。

3. 各ビンをエンコードします。選択されたコンテキスト モデルは、ビンに「1」が含まれる確率とビンに「0」が含まれる確率の 2 つの確率推定値を提供します。これらの推定値によって、算術コーダがビンをエンコードするために使用する 2 つのサブ範囲が決まります。

4. コンテキスト モデルを更新します。たとえば、コンテキスト モデル 2 がビン 1 に選択され、ビン 1 の値が「0」だった場合、「0」の頻度カウントが増加します。つまり、このモデルが次に選択されたときに、「0」の確率がわずかに高くなります。モデルの発生総数がしきい値を超えると、「0」と「1」の頻度カウントが縮小され、実質的に最近の観測が優先されます。

算術デコーダーについては、標準で詳細に説明されています。算術デコーダーには、3 つの異なる特性があります。

1. 確率の推定は、「最小確率シンボル」(LPS、2 つのバイナリ決定「0」または「1」のうち最も確率が低いもの) の 64 個の個別の確率状態間の遷移プロセスによって実行されます。
2. 算術符号化器の現在の状態を表す範囲Rは、各ステップで新しい範囲を計算する前に、事前設定された値の小さな範囲に量子化され、ルックアップ テーブルを使用して新しい範囲を計算することが可能になります (つまり、乗算なし)。
3. ほぼ均一な確率分布を持つデータ シンボルに対して、簡略化されたエンコードおよびデコード プロセスが定義されます。

デコード プロセスの定義は、算術エンコードとデコードの低複雑度の実装を容易にするように設計されています。全体的に、CABAC は CAVLC ベースのコーディングと比較してコーディング効率が向上しますが、計算の複雑さは増します。

1986年、IBMの研究者であるKottappuram MA MohiuddinとJorma Johannen Rissanenは、乗算を必要としないバイナリ算術符号化アルゴリズムの特許を申請しました。 ^{[5] [6]} 1988年、RB Arps、TK Truong、DJ Lu、WB Pennebaker、L. Mitchell、GG Langdonを含むIBMの研究チームは、Q-Coderと呼ばれる適応型バイナリ算術符号化（ABAC）アルゴリズムを発表しました。^{[7] [8]}

上記の特許と研究論文は、IBMと三菱電機の他のいくつかの特許と研究論文とともに、 1992年にCCITTとJoint Photographic Experts GroupによってJPEG 画像圧縮形式の適応型2進算術符号化アルゴリズムの基礎として引用されました。 ^{[5]しかし、}ハフマン符号化と算術符号化の両方のオプションがあるJPEGファイル形式のエンコーダとデコーダは通常、ハフマン符号化オプションのみをサポートしています。これはもともと特許上の懸念によるものでしたが、JPEGの算術符号化特許^[9]はJPEG標準の古さにより期限切れになっています。^[10]動画圧縮における適応型2進算術符号化の使用が最初に報告されたのは、1989年にIBMの研究者がMPEGグループに提案したときでした。^{[11] [12]}この提案は、算術符号化の使用をJPEGフレーム内からビデオフレーム間符号化に拡張しました。

1999年、ヨンジュン・ユウ（テキサス・インスツルメンツ）、ヤング・ガップ・クォン、アントニオ・オルテガ（南カリフォルニア大学）は、コンテキスト適応型のバイナリ算術符号化を発表しました。^[13]現代のコンテキスト適応型バイナリ算術符号化（CABAC）アルゴリズムは、 2003年にH.264/MPEG-4 AVC形式で商業的に導入されました。 ^[14] AVC形式の特許の大部分は、パナソニック、合同会社IPブリッジ、LGエレクトロニクスが保有しています。^[15]

• 算術符号化
• データ圧縮
• ロスレス圧縮
• コンテキスト適応型可変長符号化 (CAVLC)