AV1的熵编码器

今天接着前文介绍过的AV1量化过程，来看看作为AV1编码器最后一步的熵编码，有哪些新东西。

大家知道，在H.265/H.266视频编码器中熵编码使用的是CABAC(Context-Adaptive Binary Arithmetic Coding)，显然它属于二进制算术编码。但在AV1里采用的是multi-symbol多符号算术编码，是非二进制算术编码。这二者之间有哪些异同呢？请看下文。

1.算术编码

上下文自适应二进制算术编码和多符号算术编码的区别暂且不谈，但明显二者都属于算术编码。

算术编码是一种基于概率方法的无损压缩熵编码，如果大家看相关资料，会发现常常是把它和霍夫曼编码放在一起来介绍和对比。在视频编码器中应用算术编码，有一篇发表于1987年的经典论文Arithmetic coding for data compression，如果感兴趣的话可以看看。

算术编码的算法，在原理和实现还是相对比较简单的，它可将输入的一串符号流，输出一个浮点数。其编码算法如下图：

算法核心是对symbol的概率区间，递归分割为互不重叠的子区间，要分割的次数等于待编码序列中符号个数。这个算法可以由Low(lower)，Range，Symbols(q)和Probabilities(p)这4个变量来控制，它们所表示的意义，下面举个例子加以说明。

下图是3阶段算术编码的一个示意图，表示的是对符号’1’使用固定概率算术编码的例子。

其中变量Low对应上图a中的0，上图b中的0.22，上图c中的0.88；Low+Range对应上图a中的最大值1，上图b中的最大值0.44；上图中使用蓝色的数字0，1，2来表示symbol，而它们下方的黑色数字就是符号对应的Probabilities，黑色概率之间的小数字是累积概率值。

视频编码器里的算术编码，在每个待编码符号到来时，会不断地更新变量Range和Low的值并产生bitstream。Range和Low的更新方式如下：

其中i表示当前被编码的symbol，Psymb表示当前symbol的概率，Csymb则表示累积概率。

上图产生symbol ‘1’的bitstream的过程是这样的：要编码symbol ‘1’，这里是有一个0.5≤Range≤1.0的目标规则，并通过renormalization过程来实现这个目标。

具体是，通过不断给Low和Range值乘以2，直到Range满足了上述条件。如果在renormalization过程中，Low的值大于等于1.0了，那么此时输出的bit就是1，并让Low=Low-1，否则输出bit就是0。

上图c就是symbol ‘1’最终的概率，在进行了2次renormalization以后，由于每次Low值都是小于1.0的，所以symbol ‘1’对应的bitstream就是’000’。

2.AV1多符号算术编码

AV1的多符号算术编码，主要通过2个处理过程来压缩输入的符号序列，这两个处理分别是CDF(Cumulative Distribution Function)和Boolean操作。

AV1多符号算术编码器的输入主要是变量symbol，nsyms，FL和FH。其中FL和FH表示符号概率的最小值和最大值，占15个bit。此外，AV1算术编码里的Range变量占16个bit，Low变量占24个bit。

下图是AV1的4阶段算术编码器流程图。

第一阶段：预计算

这个阶段主要做的处理如下：

其中s是symbol。

第二阶段：Range变量更新

分为CDF和Bool：

同样分为CDF和Bool:

第四阶段：产生bitstream

3.AV1的CDF

如前文所述，AV1里的多符号算术编码包括CDF和Boolean处理，具体地：

下面举个例子说明二进制算术编码和多符号算术编码的差异。假设我们有一个待压缩的二进制序列”001011010010010″。

对多符号算术编码来说，这个序列可以看成1个’001’，1个’011’和3个’010’。这样计算下来这个序列编码只要7个bit。

由此可以看出，如果我们能将二进制值组合成更高层次的symbol，就可以减少待编码序列里的符号个数，以及熵编码需要的bit数。

在liaom里多符号算术编码技术是下图这样的：

即AV1码流里面的语法元素，是和包含M个symbol的alphabet关联，M可取2~16的整数值。AV1熵编码器的输入是由M种symbol所组成的待编码序列以及其概率组成的上下文。在每个语法编码或者解码以后，占15个bit的CDF概率值会被更新。

累积概率CDF用一个整数数组来表示，因为这里的算术编码使用了定点算术编码，CDF本应该是0.0~1.0的浮点数范围，所以Cn/32768才是真正的累积概率值。

小结

AV1里面的多符号算术编码器，是来自于Mozilla基金会的Daala视频编码标准。如果要选出一个模块来代表视频编码器的水平，我个人觉得是熵编码。

本文仅简单地介绍了AV1的熵编码器，由于才疏学浅，如有错误，欢迎指正。它里面的更多技术细节和优缺点我们下回再说。

如果你也从事视频编解码研究和工作，欢迎加我微信，拉群交流。

参考文献

1.D.Marpe,H.Schwarz,andT.Wiegand,”Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard”

2.T. P. Bitencourt, F. L. L. Ramos, and S. Bampi, “High-Throughput and Low-Power Architectures for the AV1 Arithmetic Encoder”

3.https://github.com/tuliopereirab/arithmetic-encoder-av1