An Empirical Study of Entropy-Conserving Binarization in H.264/AVC CABAC

技術要約：H.264/AVC CABACにおけるエントロピー保存型二値化に関する実証的研究

問題提起
現代のビデオコーデック（H.264/AVC、HEVC、VVC）は、シンボル列を圧縮するためにコンテキスト適応型バイナリ算術符号化（CABAC）に依存している。CABACは2つのステージで動作する。すなわち、マルチシンボル値をバイナリ決定（ビン）に変換する二値化スキームと、適応型コンテキストモデルを用いてこれらのビンを圧縮するバイナリ算術符号化器（M-coder）である。H.264規格は、幾何分布の裾を持つ分布に最適化された、切断型単項（Truncated Unary）および$k$次指数ゴロム（Exp-Golomb）スキームを採用している。理論的な代替案（標準的なハフマン符号やSrivastavaのエントロピー保存型二値化（ECB）など）は存在するものの、プロダクショングレードのCABACパイプライン内におけるそれらの実証的な性能は未検証である。特にECBは、$m$元ソースを$m-1$個のバイナリ文字列にマッピングする際、理論上は$m$元ソースの総エントロピーを保存するが、適応型コンテキストモデリングとの相互作用やそのデコーダの複雑さは、標準的な実装と比較して厳密にベンチマークされていない。さらに、二値化スキーム間のレート差のうち、どの程度が二値化そのものに起因し、どの程度が生成されたビン列へのコンテキスト割り当て戦略に起因するのかも不明である。

手法
著者らは、ITU-T H.264 セクション9.3に厳密に従い、Javaを用いてH.264/AVC CABACのエンコーダおよびデコーダをゼロから実装した。この実装は、4つの差し替え可能な二値化構成を備えた共有M-coderバックエンドを特徴とする。

1. UEG: 標準的なH.264スキーム（切断型単項プレフィックス + 指数ゴロムサフィックス）。
2. ECB: $m$元シンボルを$m-1$個のバイナリ文字列にマッピングする、Srivastavaのエントロピー保存型スキーム。
3. Huffman: すべてのビン位置に対して単一の共有コンテキストを使用する標準的なハフマン符号。
4. HuffmanPos: 各ビン位置ごとに1つのコンテキストを使用する標準的なハフマン符号。

この設計により、2つの変数を分離している。すなわち、二値化の選択（UEG vs ECB vs Huffman）と、コンテキスト割り当て戦略（単一コンテキスト vs 位置ごとのコンテキスト）である。HuffmanとHuffmanPosは同一のコード語（したがって同一のシンボルあたりのビン数）を共有しているが、コンテキストの配線のみが異なっており、これにより著者らはビン数とコンテキスト適応の効果を切り離すことが可能となった。

本研究では、以下の3つのソースクラスを用いてスキームを評価した。

• 合成分布: 一様分布、偏った分布、幾何分布、およびラプラス分布（$N=10,000$）。
• プロシージャルDCT残差: 256×256のプロシージャル生成画像（正弦波状のグラデーション、ガウス型の隆起、矩形）を、ステップ $Q \in \{2, 4, 8, 16, 32\}$ で量子化したもの。
• Kodak自然写真: 同一のDCTパイプラインで処理された、Kodak True Color Image Suiteの全24枚の画像。

ベンチマークは2,480回のラウンドトリップ試行で構成され、すべてビット完全な正確性が検証された。性能は、経験的な一次シャノンエントロピーに対する符号化オーバーヘッド（$\eta$）およびデコーダレイテンシによって測定された。

主な結果

• スパース性によるクロスオーバー: プロシージャル画像において、$Q=8$でクロスオーバーポイントが特定された。これより低い値（より豊かな分布）では、単一コンテキストのHuffmanがECBを上回った。これより高い値（より疎な分布）では、ECBがHuffmanを大幅に上回り、$Q=32$において27パーセントポイントの優位性に達した。しかし、自然なKodak画像では、このクロスオーバーはテスト範囲よりも低い位置に移動した。ECBはテストされたすべての量子化ステップにおいて単一コンテキストのHuffmanを上回り、その差は$Q$が増加するにつれて拡大した。
• コンテキスト割り当ての支配性: HuffmanとHuffmanPosの比較により、低エントロピー時におけるレート効率の支配的な要因は、ビン数ではなくコンテキスト割り当て戦略であることが明らかになった。HuffmanPos（Huffmanと同じビン数を使用しているが、位置ごとのコンテキストを使用）は、単一コンテキストのHuffmanよりも一貫して優れた性能を示し、多くのソースセルにおいてECBの性能に匹敵またはそれをわずかに上回った。プロシージャル画像の$Q=32$において、HuffmanPosは $\eta = -0.83\%$ を達成し、劣った単一コンテキストのHuffmanを使用しているにもかかわらず、ECBの $-0.69\%$ と統計的に区別がつかない性能を示した。
• デコーダレイテンシのトレードオフ: ECBのレート効率は、多大な計算コストを伴う。現在のECB実装は $O(N \cdot m)$ のデコーダ複雑度を持ち、シンボル配列に対して $m-1$ 回のパスを必要とする。大きなアルファベット（例：$m=834$）において、ECBはUEGよりも7〜10倍遅かった。対照的に、HuffmanPosは定数倍のオーバーヘッド（単一コンテキストのHuffmanより6〜28%遅い）のみで、ECBと同等のレート効率を実現した。
• サブエントロピー符号化: いくつかのスキーム（ECB、HuffmanPos、およびKodakにおけるUEG）は、負のオーバーヘッド（$\eta < 0$）を達成し、経験的な一次エントロピーを下回る符号化を行った。著者らは、これはソース符号化限界の違反ではなく、M-coderが（限界エントロピー推定器が無視する）空間的相関（DCTブロック内およびブロック間の相関）を捉えているためであるとしている。

意義と主張
本論文は、プロダクションレベルのバイナリ算術符号化器内におけるECBの最初の実証的評価を提供すると主張している。主要な貢献は、レート差を駆動するメカニズムの特定にある。すなわち、低ソースエントロピーにおいては、二値化のシンボルあたりのビン数よりも、コンテキスト割り当て戦略の方が重要であることを示した点である。本研究は、適切な位置ごとのコンテキスト割り当て戦略（HuffmanPos）と組み合わせることで、標準的な二値化（Huffman）が理論的に最適な二値化（ECB）のレート効率を達成できることを示している。

著者らは、ECBは理論的な利点を提供するものの、現在の $O(N \cdot m)$ の実装は実用には高コストすぎると控えめに結論付けている。彼らは、インターリーブされたシングルパス・デコーダを用いれば、理論的にはこのレイテンシの差を $O(N)$ に縮めることができると考えているが、このバリアントは本研究では実装されていない。本研究は、自然画像においては、HuffmanPosがテストされたスキームの中でレート効率とデコーダ複雑性の間で最も有利なトレードオフを代表することを示唆している。すべてのコード、ベンチマーク、および生データはオープンソースとして公開されている。