• 1. 前言
• 2. 二进制算术编码
• 3. CABAC编码原理分析
  • 3.1. 自适应算术编码
    • 3.1.1. 算法流程流程
    • 3.1.2. 自适应
    • 3.1.3. 码流输出(区间缩放)
    • 3.1.4 自适应算术编码的计算复杂度及优化
      • 3.1.4.1 自适应概率模型背景
      • 3.1.4.2. 自适应概率模型设计
        • 3.1.4.2.1. 自适应概率模型量化
        • 3.1.4.2.1. 自适应概率模型概率更新
      • 3.1.4.3. 自适应概率模型乘法优化
      • 3.1.4.4 自适应算术编码优化算法流程
  • 3.2. 上下文模型
    • 3.2.1 算术编码生命期
    • 3.2.2 CABAC的上下文模型
  • 3.3. 对输入流预编码(二值化)
  • 3.4 上下文模型初始化
  • 3.5 结论
• 4. CABAC编码流程
• 5. 总结

1. 前言

前两篇算术编码文章介绍了算术编码原理和步骤。本篇文章介绍CABAC，基于上下文自适应的二进制算术编码。

2. 二进制算术编码

二进制算术编码和算术编码方法一样，只是输入序列只有“0”和“1”字符，即输入序列是二进制船。
二进制算术编码的步骤归纳描述如下:

1. 设输入符号串s, s中的符号分两种：最大概率符号MPS(most probability symbol)和最小概率符号LPS(low probability symbol)。
2. LPS出现的概率P_LPS, MPS出现的概率P_MPS=1-P_LPS。映射区间MPS在前，LPS在后
   
3. 在编码中进行映射区间大小R更新：

• 当前编码的是LPS：R_i+1=R_LPS=R_i * P_LPS
• 当前编码的是MPS：R_i+1=R_MPS=R_i - R_LPS

5. 映射区间下限L更新：

• 当前编码的是LPS：L_i+1 = L_i + R_i - R_LPS
• 当前编码的是MPS: L_i+1 = L_i
  

7. 重复步骤3，4，不断更新映射区间直到符号编码完成，即可得到最终的映射区间
8. 在最终的映射区间选择最短二进制小数

3. CABAC编码原理分析

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

3.1. 自适应算术编码

3.1.1. 算法流程流程

在算术编码的递进计算过程中，编码器必须保存一下变量装填：

1. 当前区间的下限L
2. 当前区间的大小R
3. 当前字符binval
4. 各个字符的概率P_x

L和R用于确定当前区间；P_x则是当前区间的的划分依据,在二进制编码中只有1和0两个字符，所以只需记录P1或者P0即可；最后确定bin字符所在的子区间作为下一个递进的当前区间。R的递进关系：R = R * P_x

3.1.2. 自适应

在实际过程中，输入流字符的概率分布是动态改变的，这需要维护一个概率表去记录概率的变化的信息。在做递进计算时，通过对概率表中的值估计当前字符的概率，当前字符处理后，需要更新概率表。这个过程表现为输入流字符的概率自适应。编码器和解码器按照相同的方法估计和更新概率表，从而保证编码后的麻溜可以被顺利解码

3.1.3. 码流输出(区间缩放)

在实际应用过程中，编码器并不是递进到最终的编码区间才输出码流。两个原因：

1. 在编码器递进计算中，如果没有输出，信道会出现空闲，形成浪费
2. 如果输入码流较长，最终得到的区间较小，必须以极高的精度记录L和R

在二进制编码中，区间的上下限以二进制形式表示，每当区间的下限L最高位和区间上限H最高位相同，可以移除这个比特。这样的方法可以保证编码器在递进计算的同时可以不断输出码流，并且以有限的精度去记录L和R。序列出现的可能性越大，区间就越长，确定该区间的比特术越少。上述方法就是上一篇文章熵编码(四)-算术编码(二) 进阶篇介绍的区间缩放，也叫做重归一化

3.1.4 自适应算术编码的计算复杂度及优化

从上文可以发现，算术编码的负载度主要体现在两个方面：

1. 概率的估计和更新；
2. 划分子区间时的乘法运算：R = R * P_x

3.1.4.1 自适应概率模型背景

假设输入流位T，当前字符是binval，在binval之前的字符流是z, z \(\in\) T, 条件概率P(binval|z)就是当前字符的概率估计值。随着条件因子z的增长，带来的计算量急剧增加，而且没处理一个字符，需要做两次类似的计算，因此必须要找到一个更好的法则来解决这个问题。
首先假设当前字符的概率估计值P_x不是取自P(binval|z)会有什么影响。首先，这会影响编码效率，P(binval|z)是取自一个较严格的概率模型，对应于它的输出流的码率能取得对信源熵率的最大逼近；其次，从解码可行性分析，只要保证编码和解码双发在划分当前区间是的得到相同的P_x，也就是通过相同的规则估计和更新概率，那么就可以顺利解码

3.1.4.2. 自适应概率模型设计

3.1.4.2.1. 自适应概率模型量化

CABAC在计算复杂度和编码效率之间做了折中，建立了基于查表的概率模型。将从0到0.5范围内的概率量化成64个值，这些概率对应于最小概率符号LPS，则最大概率符号MPS的概率是1-P_LPS。字符的概率估计值被限定在表内，概率的刷新也不是取计算P(binval|z)，而是按照某种法则在表中查找。
概率P_σ \(\in\) [0.01875, 0.5]，其中概率状态σ=0，1，2，3...,63。P_σ由下面两个公式得到：

1. P_σ = α * P_σ-1     σ=0，1，2，3...,63
2. α = [\(\frac{0.01875}{0.5}\)]^{$\frac{1}{63}$}

通过上述公式，可以由σ得到64个概率状态P₀=0.5, P₁=0.45, ..., P₆₃=0.01875。
因为二进制算术编码只有LPS和MPS，因此LPS概率确定了MPS概率也就确定了。又和P_σ是一一对应关系，P_σ的自适应变化表现就是σ值的变化，因此σ值的更新就代表着P_σ的更新。从而概率的自适应问题转变为概率状态σ的自适应问题

3.1.4.2.1. 自适应概率模型概率更新

自适应模型概率状态σ更新规则：当前处理字符binval是LPS时，则P_LPS变大，σ->σ-1，直到σ=0并且下一个处理的字符binval仍然是LPS，交换LPS和MPS字符，σ不变；当前处理字符binval是MPS时，则P_LPS变小，σ->σ+1，直到σ=62为止保持不变
注意CABAC建立的概率模型中σ值由三种特殊情况：

1. σ=0：LPS的概率已经达到了0.5，如果下一个处理字符仍然是LPS，则此时LPS和MPS的字符需要交换位置(因为LPS > 0.5，此时旧的LPS字符已经变成MPS高概率字符了)
2. σ=63：LPS的概率达到最小概率值，但是它并没有被纳入CABAC的概率估计和更新范围，这个值被用作特殊场合，传达特殊信息，如流的结束符
3. σ=62： 这是表中实际可用的最小的概率值，它对应的刷新值就是自身，当MPS连续出现，LPS的概率持续减小，直到σ=62，保持不变

自适应概率模型更新趋势图如下所示(LPS字符出现，σ向左移动；MPS字符出现，σ向右移动)：

3.1.4.3. 自适应概率模型乘法优化

CABAC概率模型有效的降低了概率的估计和更新的计算量，对于算术编码中的乘法运算R = R * P_x，CABAC也利用了相同的思想:

1. 量化区间大小R为ρ
2. CABAC建立量化后ρ和概率状态σ的二位模型表格TabRangeLPS[ρ, σ]

以H264为例，介绍H264的自适应概率模型乘法优化：
在H264/AVC中，通常使用10比特表示区间下限L，因为二进制算术编码概率最大不超过0.5，因此使用9比特表示区间大小R，区间大小R的范围是[2⁸, 2⁹)。为了降低复杂度，便于硬件实现，在区间划分时需要对R进行量化，量化规则: ρ = (R >> 6) & 3。因此R的取值范围是00b、01b、10b、11b四个数值。
综上所述，CABAC可以建立一个4*64的二维概率模型表格TabRangeLPS[ρ, σ]，存储提前计算好的乘法结果。每次需要进行乘法运算时，携带ρ、σ查表即可：R_LPS = TabRangeLPS[ρ, σ]

3.1.4.4 自适应算术编码优化算法流程

CABAC建立了4*64的概率模型之后，在递进计算过程中CABAC需要记录一下变量：

1. 区间下限L
2. 当前区间的大小R
3. 当前MPS字符ω
4. 当前LPS字符的概率状态编号σ

算法流程如下：

1. 递进计算区间划分L&R
2. 概率模型更新
3. 重归一化
   

3.2. 上下文模型

3.2.1 算术编码生命期

算术编码是对整个码流分配码字，但考虑到如果有某个比特丢失，编码和解码将会错位。为了将差错控制在一定范围内，CABAC将片(slice)作为算术编码的生命期。在每个片开始的时候，CABAC进行初始化，按照一定的法则为编码器初始化ω和σ，并初始化[0, 1)为当前编码区间。

3.2.2 CABAC的上下文模型

即使对片内数据，CABAC也不是当作整体进行处理的，而是继续分割成若干子部分分别进行编码。除了上文提到的差错控制的原因外，也是由于输入流过长，则要求L和R必须要有足够的精度和长度保存中间数据，这对编码器也是不小的负担。
下面以H264为例，介绍H264的上下文模型：
H264将一个片内可能出现的数据划分为399个上下文模型，每个模型以ctxIdx标记，在每个上下文内部进行概率的估计和更新。H264需要建立399个概率表，每个上下文模型都独立的使用对应的概率表维护概率状态。这些模型的划分精确到比特，几乎大多数的比特和它们邻进的比特处于不同的上下文模型中。
解码器对于输入流的每一个比特首先要做的工作是查找它处于哪一个上下文模型，然后查找该上下文模型对应的概率表以递进区间。查找某个比特对应的上下文模型有一下两个步骤：

1. 确定该比特所属的句法元素，H264对每个句法元素都分配了对应的上下文模型区间，该句法元素的每个比特对应的上下文模型的ctxIdx都在这一区间。下表描述了用CABAC编码的各句法元素所在上下文模型区间的起始ctxIdx。
   
2. 按照某个法则为当前比特在1)中查找到的上下文模型区间中找到对应的ctxIdx，该法则对于每个句法元素都不相同。该法则一般是用表来定义的，下表描述了大多数句法元素为所属各比特查找ctxIdx的法则。在这个表中，binIdx是各比特在句法元素中的序号，ctsOffset是上表6.15中所示各句法元素对应的上下文模型区间的起始偏移。我们可以看到，在某些比特对应多个上下文模型，这一般是在解码中需要根据前后宏块在空间上的相关再做进一步确定
   

3.3. 对输入流预编码(二值化)

CABAC围绕算术编码的特性做了许多优化，这其中也包括了从统计角度对输入流做的鱼编码。从上文可以分析出，当前处理的字符是MPS时，区间递进只是字区间长度R发生变化，而作为想象实际输出值的区间下限L不变。这意味着如果输入流中出现连续大量的MPS，或者MPS对LPS的概率比非常高，可以达到极高的压缩效果，算术编码对这种输入流的压缩性能达到最优，编码出的码率也更接近信源熵率。由此CABAC体系包含了一个预编码流程，将输入流重新编码后再进行算术编码。这个预编码流程叫做输入流的二进制化也叫二值化，经它输出的流时MPS概率极高的比特流。
CABAC对不同句法元素常用的四种二值化方法： 一元码(U)、截断一元码(TU)、k阶无指数哥伦布编码(UEGK)、定长编码(FL)

1. 一元码(U)
   对于一个给定的无符号整数x，在CABAC中一元码码字有x个1外加一个结尾的0组成。见下表，其中binIdx是编码后各比特的序号
   

2. 截断一元码(TU)
   一元码的变体，用在已知句法元素最大值cmax的情况。对于0 <= x < cmax范围内的取值，使用一元码进行编码。对于x >= cmax，其二进制化的比特流由1组成，长度是cmax。例如当cmax=5时，句法元素值是4的二进制比特流是11110b，句法元素值是5的二进制比特流是11111

3. K阶无指数哥伦布编码(UEGK)
   在熵编码(二)-指数哥伦布熵编码中详细讲述了K阶无指数哥伦布编码方法，这里就不叙述了

4. 定长编码(FL)
   用定长编码二进制的无符号句法元素，句法元素的cmax已知。定长编码的长度fixlength=floor(log₂(cmax + 1))，编码的值就是句法元素的值的二进制。定长编码用于近似均匀分布的句法元素的二值化，可以理解为十进制二进制化

不同的编码标准还有自己的二值化方法。
例如在H264中：mb_type与sub_mb_type特有的查表方式，详情请查看h.264白皮书中9.3.2.5小节

3.4 上下文模型初始化

上文提到，CABAC的生命期是片，每个片的开始需要对所有的上下文模型初始化。
以H264为例，需要对399种上下文模型初始化，初始化步骤如下；

1. 将递进区间复位到[0, 1)
2. 为每个上下文模型指定一个ω和σ，通过如下步骤获得：
   a). H264为每个上下文模型定义了初始化常量m、n，通过查表获得上下文的初始化常量m、n
   b). 按照如下方法计算ω和σ：

preCtxState = Clip3(1, 126, (m * SliceQPY >> 4) + n)
if (preCtxState <= 63) {
  σ = 63 - preCtxState
  ω = 0
} else {
  σ = preCtxState - 64
  ω = 1
}

式中，函数Clip3(a, b, c)表示将c的值限制在[a, b]之间，preCtxState是中间变量

3.5 结论

CABAC内建了大量的由大量的实验得到的概率模型。在编码过程中，CABAC根据当前所要编码的内容和先前编码好的内容，动态地选择概率模型来进行编码，并实时更新概率模型。并且，CABAC在计算量和编码速度速度上进行了优化，用了量化查表、移位、逻辑运算等方法代替复杂的概率估计和乘法运算。

4. CABAC编码流程

通过上文CABAC原理分析，CABAC编码流程可以分为以下几步：

1. 上下文模型初始化：CABAC在每个片的开始需要对所有的上下文模型初始化
2. 待编码句法元素二值化：对于非二进制句法元素进行二值化输出二进制字符串
3. 上下文建模（确定上下文索引）：根据句法元素类型和二进制字符串去定上下文模型索引ctxIdx
4. 算术熵编码：通过选择的上下文模型查表计算区间L&R，概率模型更新，再对区间大小R进行重归一化，输出码流
   

5. 总结

本文对CABAC的基本原理进行了详细的介绍和分析，下篇文章将会对H264编码中的CABAC熵编码的实际应用进行介绍