基于上下文的自适应二进制算术编码

基于上下文的自适应二进制算术编码（Context-based Adaptive Binary Arithmetic Coding，简称CABAC）是视频压缩标准H.264采用的算法。

原理

CABAC分为三个部分，Binarizer, Context Modeler和Arithmetic Coding Engine。CABAC的设计概念，对于发生几率P(x)>0.5的事件有效地编码，改进了传统算术编码（Arithmetic coding）需要大量的乘法运算的问题，而在性能与压缩效率上获取相当大的改善空间。CABAC的生命周期是slice，CABAC与UVLC最大的不同点在于其编码方式具有适应性（adaptive），对于编码过程中各个符号（symbol）出现的几率会一直动态地去统计并更新。

Arithmetic Coding中以Low及Range表示压缩过程的范围。Binarizer可将Codec分析后的句法元素（Syntax Element），转化成为比特字符串（bin string），每个比特称为一个bin，而bin即为传给Arithmetic Coder的Symbol。CABAC的符号（symbol）只有0或1两种，所以bin就是0或1。如果原本就是binary value，就不需要binarization。此一步骤的输出称为bin string。接下来要把这些bin sting做arithmetic coding，每个bin可能会有某种几率分布，如果不具有分布（regular），即是bin value，就进行Bypass Coding Engine，如果是regular，就前往Context Modeler选择目前这个bin的model。

Context Modeler再针对所要压缩的bin去作几率的估测（Probability Estimation）和更新（Binary Arithmetic Coding）。Regular Coding Engine利用bin的model和Context Index查表，并透过Markov Chain Model建表，随时更新Low与Range的数值，更可得出MPS（Most Probable Symbol）与Probability State。MPS表示几率大于0.5，另一个LPS（Least Probable Symbol）是几率小于0.5。

Bypass Coding Engine和Regular Coding Engine都是Binary Arithmetic coder，均会产生coded bits，形成bitstream，最后输出。

CABAC不同于Various Length Coding，因此更能够接近资料的熵编码（Entropy）。CABAC每个symbol和bitstream不再有一对一的绝对关系，N个symbol有可能使用小于N个bit.在几率估计准确的前提下，CABAC的算术编码（Arithmetic Coding）的压缩率可以大于Huffman Coding，也就是说CABAC善用了统计学的期望值，压缩的bin几率相当接近0.5，表示预测的效率相当低，可直接进行Bypass，直接输出，以降低memory access与计算。

目前CABAC不支持Baseline以及Extended profiles.另外，CABAC面临的问题是在于由于循序处理造成资料依存性（Data Dependency）偏高。

参考书目

H.264/MPEG-4 Part 10 White Paper, two page summary of MPEG CABAC, October 2002 [1]
E. G. Richardson, Iain. H.264 and MPEG-4 Video Compression: Video Coding for Next-generation Multimedia. Chichester: John Wiley & Sons Ltd. 2003.

外部链接

参见

CAVLC