CABAC 基础二-算术编码

2. 算术编码与变长编码不同算术编码的本质是为整个输入序列分配一个码字而不是给每个字符分别指定码字因此平均意义上可以为单个字符分配码长小于1的码字。算术编码用到两个基本的参数符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率也决定编码过程中信源符号的间隔而这些间隔包含在L到H之间。编码过程中的间隔决定了符号压缩后的输出。给定事件序列的算术编码步骤如下1. 编码器在开始时将“当前间隔”设置为[ L H)2. 对每一事件编码器按步骤a和b进行处理a) 编码器将“当前间隔”分为子间隔每一个事件一个b) 一个子间隔的大小与下一个将出现的事件的概率成比例编码器选择子间隔对应于下一个确切发生的事件相对应并使它成为新的“当前间隔”3. 最后输出的“当前间隔”的下边界和上边界之间的一个合适的值就是该给定事件序列的算术编码。2.1. 浮点算术编码在做算术编码前需要定义一个模型有很多定义模型的算法其主要目的都是为了能够精确的估计符号出现的概率同时保证编码和解码的概率是一致的。为了简单起见本节定义一个静态的概率模型假设我们对大写字母进行编码且前24个字母的概率为均为0.04最后2个字母的概率均为0.02如此26个字母的概率之和为1。按照以上定义我们将[01)区间划分为26份其中A拥有区间[00.04)B拥有区间[0.040.08)…M拥有区间[0.480.52)…Y拥有区间[0.960.98) Z拥有区间[0.981)。算术编码时采用了子区间划分的方法计算公式如下range high – low (1)high low range * prob_high; (2)low low range * prob_low (3)其中range表示当前编码是区间大小low和high分别表示当前区间的最小值和最大值prob_low和prob_high分别表示当前待编码字符的概率区间的最小值和最大值。假设我们编码“PASS”由上述定义可知“P”对应区间[0.60.64)“A”对应区间[00.04)“S”对应区间[0.720.76)计算过程如图2所示。1) 当编码“P”时按照公式(1)、(2)和(3)计算如下range 1.0 – 0 1high 0 1 * 0.64 0.64low 0 1 * 0.6 0.62) 当编码“A”时按照公式计算如下range 0.64 – 0.6 0.04high 0.6 0.04 * 0.04 0.6016low 0.6 0.04 * 0 0.63) 当编码“S”时按照公式计算如下range 0.6016 – 0.6 0.0016high 0.6 0.0016 * 0.76 0.601216low 0.6 0.0016 * 0.72 0.6011524) 当编码“S”时按照公式计算如下range 0.601216 – 0.601152 0.000064high 0.601152 0.000064 * 0.76 0.60120064low 0.601152 0.000064 * 0.72 0.60119808图2. 编码“PASS”过程从最后的结果可以看出字符串“PASS”编码后的区间是[0.601198080.60120064)从该区间中选择一个合适的值即可作为字符串“PASS”最终的算术编码值。解码时使用和编码时类似的公式如公式(4)、(5)、(6)和(7)。range high – low (4)c (val - low) / range (5)high low range * c_prob_high (6)low low range * c_prob_low (7)假设我们最终选择了0.6012作为“PASS”算术编码后的值。其对应的解码过程如下所示1) high 1low 0val 0.6012range high – low 1c (val - low) / range (0.6012 - 0) / 1 0.6012可知0.6012∈[0.60.64)对应字符“P”因此解码的第一个字符为“P”high low range * c_prob_high 0 1 * 0.64 0.64low low range * c_prob_low 0 1 * 0.6 0.62) high 0.64low 0.6val 0.6012range high – low 0.04c (val - low) / range (0.6012 – 0.6) / 0.04 0.03可知0.003∈[00.04)对应字符“A”因此解码的第二个字符为“A”high low range * c_prob_high 0.60 0.04 * 0.04 0.6016low low range * c_prob_low 0.60 0.04 * 0 0.603) high 0.6016low 0.60val 0.6012range high – low 0.0016c (val - low) / range (0.6012 – 0.60) / 0.0016 0.75可知0.75∈[0.720.76)对应字符“S”因此解码的第三个字符为“S”high low range * c_prob_high 0.60 0.0016 * 0.76 0.601216low low range * c_prob_low 0.60 0.0016 * 0.72 0.6011524) high 0.601216low 0.601152val 0.6012range high – low 0.000064c (val - low) / range (0.6012 –0.601152) / 0.000064 0.75可知0.75∈[0.720.76)对应字符“S”因此解码的第四个字符为“S”high low range * c_prob_high 0.601152 0.000064 * 0.76 0.60120064low low range * c_prob_low 0.601152 0.000064 * 0.72 0.60119808经过以上步骤就解码出了“PASS”字符串但由于计算机的精度问题浮点算术编码在实际情况下回带来诸多不便因此在实际中使用的基本都是基于定点数的算术编码。2.2. 定点算术编码在浮点数编码时区间被限定在[01)之间做定点算术编码时区间范围视寄存器位数而定本节假设为32位的定点算术编码。在浮点算术编码中low0high1.0在32位定点算术编码中由于寄存器只能表示整数因此我们假想在low和high的最前面有一个小数点存在。即low 0high 0xFFFFFFFFU可以被假想为low 0.0high 0x0.FFFFFFFFU由于寄存器位数有限(本节假设为32位)但是算术编码时需要的是一个无限趋近于1的一个数因此low 0.0high 0x0.FFFFFFFFU进一步可以被假想为low 0.00000000…high 0x0.FFFFFFFF…U也就是说我们可以假设在寄存器有限的精度之后还存在着无限多个后缀low之后存在无限多个0high之后存在无限多个F(针对16进制)或者无限多个1(针对二进制)每次当寄存器中low的高位移出之后低位都补0high高位移出之后低位都补1(因为前面说high后有无限个F是针对16进制而言针对移位操作而言高位每移出一位二进制数低位就补1)。在浮点算术编码中我们可以发现随着编码的进行在编码过程中将满足三个不变式a) low将单步递增b) high将单步递减c) high low在满足以上三个条件的基础上一旦high的二进制最高位为0那么它将在以后的编码过程中保持不变同理low的二进制最高位为1那么它在以后的编码过程中也不会发生变化。由于寄存器的位数有限为了充分的利用寄存器进行接下来的编码当high和low的二进制最高位相同的时候可以将他们移出寄存器保存起来然后将low末尾的无穷个0移进一位到low的最低位从high末尾的无限个1移进一位到high的末尾如此这样可以保证寄存器的位数被充分利用且不会造成算法错误。下面以定点算术编码方式来编码上面的“PASS”字符串如下1) 编码“P”字符时low和high值如下这里为了简单直接用概率与区间大小相乘编码后寄存器状态如图3所示range 0xfffffffflow 0.6 *0xffffffff 0x99999999high 0.64 * 0xffffffff 0xa3d70a3c图3. 编码“P”字符后寄存器状态由上面分析可知low和high的前两位都不再发生变化因此可以直接移出寄存器存储起来同时将尾部的0移入low将尾部的1移入high。经过移出和移入操作后low和high值如下low 0x66666664high 0x8f5c28f32) 编码“A”字符时low和high值如下公式所示移出移入后寄存器状态如图4所示“Emitted”部分移出了6个比特其中最高2比特是在第一步操作中移出的range high – low 0x8f5c28f3 – 0x6666664 0x28f5c28fhigh low 0.04 * range 0x66666664 0.04 * 0x28f5c28f 0x6809d493low low 0 * range 0x66666667图4. 编码字符“A”后寄存器状态按照同样的原理可以得出编码第一个字符“S”和第二个字符“S”后寄存器状态如图5(a)和5(b)所示。(a)编码第一个字符“S”后寄存器状态(b)编码第二个字符“S”后寄存器状态图5. 编码字符“S”后寄存器状态2.3. 区间缩放为了充分利用寄存器有限的位宽保证计算精度定点算术编码的同时结合了区间缩放。在上一节中提到的当low和high最高位相同时可以移出寄存器同时在末尾移入0或1就属于区间缩放中的两种情况。定点数算术编码中区间缩放一共分为三种。1) 当low的最高位为1时也就是low mid时由于high low这个不变式一直成立因此high的最高位也是1此时可以将high和low的最高位移出也就是将high和low左移一位同时低位补上相应的1和0。由于high和low都左移一位相当于对区间进行了第一种情况的缩放如图6(a)所示。此时类似于low (low – 0.5) * 2high (high – 0.5 * 2图3中编码后移出了二进制“10”其中最高位移出的“1”就是这种情况。2) 当high的最高位为0时也就是high mid时由于high low这个不变式一直成立因此low的最高位也是0此时可以将high和low的最高位移出也就是将high和low左移一位同时低位补上相应的1和0。由于high和low都左移一位相当于对区间进行了第二种情况的缩放如图6(b)所示。此时类似于low low * 2high high * 2图3中编码后移出了二进制“10”其中次高位移出的“0”就是这种情况。3) 当high的最高两位为“10”而low的最高两位为“01”时也就是low属于[1/4 full range1/2 full range)这个区间而high属于[1/2 full range3/4 full range)时需要将high的次高位“0”和low的次高位“1”移出寄存器最高位都保持不变同时记录下次高位移出的次数cnt。当遇到第一种方式的区间扩展时向缓冲区输出一个1和cnt个0作为算术编码的结果当遇到第二种区间扩展方式时向缓冲区输出一个0和cnt个1作为算术编码的结果。如图6(c)所示其对应的公式如下。low (low – 0.25) * 2high (high – 0.25 * 2(a) 第一种区间缩放(b) 第二种区间缩放(c) 第三种区间缩放图6. 算术编码区间缩放对于第三种缩放形式通过如下的例子来进行说明。我们仍然采用浮点数算术编码部分的概率模型假设我们编码字符串“MMMMMMM”也就是连续编码7个字符“M”按照定点数算术编码的方式进行计算可以得到如下结果。编码第一个字符“M”之后low 0x7ae147ad high 0x851eb851 range 171798692编码第二个字符“M”之后low 0x7fcb9239 high 0x80346dc4 range 6871947编码第三个字符“M”之后low 0x7ffde71f high 0x800218dd range 274878编码第四个字符“M”之后low 0x7fffea84 high 0x80001577 range 10995编码第五个字符“M”之后low 0x7fffff21 high 0x 800000d9 range 440编码第六个字符“M”之后low 0x7ffffff4 high 0x80000005 range 17编码第七个字符“M”之后low 0x7ffffffc high0x7ffffffc range 0。从上面的编码字符“M”之后的low和high可以看出前六次编码后的结果low和high都没有相同的最高位且low和high无限趋近于中点值mid0x80000000同时还可以看出第六次之后range17但概率模型中一共存在26种字符(“A”~“Z”)该range值太小会导致无法为每个字符都分配独立的概率区间因此是需要缩放的且每次编码字符“M”后low的最高两位是“01”high的最高两位是“10”从第七次的编码结果来看low和high最终的结果是0x7ffffffc可以知道这也是符合第三种缩放的算法的即一个0后有cnt个1或者一个1后有cnt个0至于cnt的数值大小这里不再计算可以按照第三种缩放算法的方式自行计算。