cabac原理及其实现笔记

1、Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC简称Cabac，H264中的一种熵编码方式：基于上下文的自适应二进制算术编码内容安排：1，介绍算术编码 2，介绍二进制算术编码 3介绍Cabac及其一些实用的实现方式（参考JSVM代码，也可以参考JM） -张新发一，算术编码算术编码是一种常用的变字长编码，它是利用信源概率分布特性、能够趋近熵极限的编码方法。它与 Huffman 一样，也是对出现概率大的符号赋予短码，对概率小的符号赋予长码。但它的编码过程与 Huffman 编码却不相同，而且在信源概率分布比较均匀的情况

2、下其编码效率高于 Huffman 编码。它和 Huffman 编码最大的区别在于它不是使用整数码。Huffman 码是用整数长度的码字来编码的最佳方法，而算法编码是一种并不局限于整数长度码字的最佳编码方法。算术编码是把各符号出现的概率表示在单位概率 0，1 区间之中，区间的宽度代表概率值的大小。符号出现的概率越大对应于区间愈宽，可用较短码字表示；符号出现概率越小对应于区间愈窄，需要较长码字表示。 举例如下： 以符号为例 在算术编码中通常采用二进制分数表示概率，每个符号所对应的概率区间都是半开区间，即该区间包括左端点，而不包括右端点，如 S1对应 0, 0.001)，S2 对应 0.001, 0

3、.01) 等。算术编码产生的码字实际上是一个二进制数值的指针，指向所编的符号对应的概率区间。n 符号序列 的第一个符号 S3 用指向第 3 个子区间的指针来代表，可以用这个区间内的任意一个小数来表示这个指针，这里约定这个区间的左端点代表这个指针，因此得到第一个码字.011。n 后续的编码将在前面编码指向的子区间内进行，将 .011, .111 区间再按概率大小划分为 4 份，第二个符号 S3 指向 .1001 (S3 区间的左端），输出码字变为 .1001。n 然后，S3 对应的子区间又被划分为 4 份，开始对第三个符号 S2 进行编码，. n 两个参量：编码点（指针所指处）C 和区间宽度 A

4、。³ 初始状态 编码点（指针所指处）C = 0 区间宽度 A = 1.0³ 新编码点 C = 原编码点 C 原区间 A×Pi 新区间 A = 原区间 A×pi n 序列 S3S3S2S4 的编码过程：³ 第1个符号 (S3): C = 0 + 1×.011 = .011 A = 1×.1 = .1 ³ 第2个符号 (S3): C = .011 + .1×.011 = .1001 A = .1×.1 = .01³ 第3个符号 (S2): C = .1001 + .01×.001

5、 = .10011 A = .01×.01 = .0001³ 第4个符号 (S4): C = .10011 + .0001×.111 = .1010011 （输出的码字） A = .0001×.001 = .0000001解码过程n 算法解码采取与编码过程相反的步骤³ 把接收到的码字串指向其对应的子区间，得到此子区间对应的符号，即为解码后的符号。³ 即从码字串中减去已解码符号的子区间的左端点的数值（累积概率），³ 并将差值除以该子区间的宽度（概率值），得到新的码字串。n 上述例子³ 当收到字码串 (.1010011

6、) 时，其指向子区间 .011, .111，对应于 S3，因此，得到第 1 个符号为 S3。³ 新码字串：（.1010011 - .011) ÷ (.1) = 0.100011 ，新码字串仍然指向子区间 .011, .111，因此，第 2 个符号仍为 S3。³ 其它符号依次类推二，二进制算术编码二进制算术编码的输入的字符只有两种，如果信源字符集内包含有多个字符，则先将这些字符经过一系列的二进判决，变成二进制字符串。这两个符号构成的序列的编码与算术编码基本原理相同，仍是不断划分概率子区间的递归过程。在两个输入字符中，出现概率较大的为 MPS (More Probab

7、le Symbol)，MPS 的概率为 Pe；出现概率较小的为 LPS (Less Probable Symbol)，LPS 的概率为 Qe，Pe=1-Qe。编码初始化子区间为 0，1，MPS与 LPS 分配如图所示：编码时，设置两个专用寄存器（C，A）C 寄存器的值为编码点（指针所指处），初时化为0A 寄存器的值为子区间的宽度 (该宽度恰好是已输入符号串的概率)，初时化为1随着被编码数据源输入，C 和 A 的内容按以下编码规则修正：当低概率符号 LPS 到来时： C=C ， A=AQe 当高概率符号MPS到来时： C=C + AQe ， A=Ape = A（1-Qe）例: 信源符号序列 11

8、011111 0 为 LPS Qe = 1/8 =（0.001）b 1 为 MPS Pe = 7/8 =（0.111）b初始状态：C=0 (子区间起始位置) A=1 （子区间宽度）1， 第1个符号1为 MPS C = C + AQe = 0 + 1 ´0.001 = 0.001 A = APe = 1 ´0.111 = 0.1112， 第2个符号1仍为 MPS C=C+AQe = 0.001 + 0.111 ´0.001=0.001111 A=APe= 0.111 ´0.111 =0.1100013， 第3个符号0为 LPS C=C=0.001111 A

9、=A Qe = 0.110001 ´0.001 =0.0001100014， 继续下去. 最后得C= 0.010001111110111100000001A= 0.000011001001000010111111此时区间的尾为C+A=0.010101000111111111000000，编码区间C, C+A)编码输出可以是最后一个编码区间中的任意小数值，但为了取得最好的编码效率，选择的小数应有最短的比特长度。上面区间我们可取0.0101,即输出为0101解码过程按 Qe、Pe 分成两个子区间，判断被解码的码字落在哪个区间，并赋予对应符号。设 c =（0.0101) b是被解码的值，初

10、始值 A=1 Qe = 0.001当 c 落在 0-QeA 之间，解码符号为 D=0，则C = C， A = Qe A当 c 落在 QeA-A 之间，解码符号为 D=1，则C = C-Qe A ，A = A（1-Qe）1， c = 0.0101落在 Qe A -A 之间，解码符号为 D = 1 c = c-QeA = 0.0101 - 0.001 = 0.0011 ， A = A（1-Qe）= 0.1112， c= 0.0011 落在 Qe A -A 之间，解码符号为 D=1 c=c-QeA= 0.0011 -0.000111=0.000101 ，A=A（1-Qe）= 0.111´0

11、.111=0.110001 3，c = 0.000101 落在 0-QeA 之间，解码符号为 D = 0 c = c = 0.000101 A = AQe = 0.110001´0.001 = 0.000110001 三，CABAC原理及其实现CABAC是H264的一种熵编码方案，相比如H264的另外一种熵编码方案CAVLC而言，在可接受的视频质量（30dB到38dB之间）内变化时，前者可节约平均9%到14%的码流。CABAC有以下几个特性：1， 对多数符号使用了自适应概率模型。2， 通过使用上下文关系，利用了符号相关性。3， 限制为二进制算术编码（binary arithmetic

12、 coding），基于只用查表和移位方式的快速二进制算术编解码器。4， 399 种预定义的上下文模型，分成了各种不同的模型组，例如模型 14-20 用于帧间宏块类型的编码，模型的选择基于前面编码的信息（上下文关系），每个上下文模型适应实验分布。先大致介绍CABAC的实现过程，然后对一些技术做细节介绍下面是CABAC的编码流程图按上图可知，对一个符号编码有如下过程：1，转化成二进制(Binarization)CABAC使用二值算术编码，也就是说只对二进制的判决（0或者1）进行编码。非二进制符号（例如转换后的系数或者运动矢量）在编码前先要进行二进制转换。这一过程和变长编码（VLC）中将信息符号转化

13、为变长编码一样，所不同的是，算术编码器在将信息送去传输之前还要进一步对这些二进制符号进行编码。 2, 选择基于内容的模型：“基于内容的模型”是二进制符号中一个或多个比特的概率模型。根据对先前已编码符号的统计，从可选模型中选择适当的概率模型。3, 算术编码：根据选择的概率模型对每个比特进行算数编码。4, 更新模型上图中的bypass coding是指对于一些特定语法元素的二进制比特符号，为了加快编码速度而不使用上下文模型的形式。使用CABAC的熵编码方式在时间耗费方面大于CAVLC，为了达到一个折中，在实际编码中，并不是对所有的语法元素都使用CABAC编码方案，有许多表征视频序列本身固有参数特征

14、的语法元素的熵编码还是使用CAVLC。下图是一些需要用CABAC编码的语法元素及对应的上下文模型索引。下面来具体介绍编码过程1，二进制化为了降低算术编码的复杂度，提高编码速度，采用二进制算术编码，即进行熵编码的符号是一系列的二进制符号，这得首先需要把编码语法元素转化成二进制串，包括基本方案和串接方案。Unary Binarization：对于x>=0的无符号整数值，由x个”1”和一个终结符合”0”组成。Truncated Unary Binarization（TU）：给定一个参数S,对于编码符号x，0<=x<=S有效，如果x>S,则取x=S，对于x<S时，二进制串

15、由Unary Binarization 方案给出，对于x=S，Unary Binarization 方案中的那个终结符号”0”被忽略，此时输出二进制串为x个”1”。kth order Exp-Golom(EGK) Binarization：由一个前缀和一个后缀码字串接而成，对于给定x,下面是产生一个k阶指数格雷码的算法while(1) /unary prfix part of EGK if (x>=(1<<k) put(1) x=x-(1<<k) k+ else put(0) /terminating “0” of prefix part while(k-) /b

16、inary suffix part of EGK put(x>>k)&0x01) break 前缀是由对应值为的Unary Binarization方案产生的二进制串组成，后缀由这个十进制值对应的二进制串组成。Fixed-Length(FL)Binarization：给定一个参数S，对于编码语法元素x，必须满足0<=x<S，输出二进制串为十进制值x对应的二进制数。Concatenation of Basic Binarization：串接方案，有以下几种组合：1，编码coded block pattern时，cbp代表了六个8x8块的编码系数情况(4个亮度，2个

17、色度，具体会在后面讲到)，这时候，以4-bit的FL方案产生的二进制串作为前缀表征亮度部分，以S=2的TU方案产生的二进制串作为后缀表征色度部分。2，Unary/kth order Exp-Golomb(UEGK)，这种串接方式应用于mvd和变换系数的绝对值的二进制化。对于mvd, 前缀是S=9，x=min(|mvd|,9)的TU方式。当|mvd|>9时，后缀是x=|mvd|-9的EG3的方案输出的二进制串，mvd的符号为正时用”1”表征，为负时用”0”表征，当0<|mvd|<9时，后缀仅由表征mvd符号的比特生成。3，对于变换系数绝对值的二进制化，前缀采用S=14的TU方式

18、，后缀采用EG0方式，注意此时二进制化的语法元素coeff_abs_value_minus1=abs_level-1，对于abs_level=0的情况，我们用一个significance map将其处理了。这和二进制化mvd比较相似，但此时并没有处理符号，符号是后面要单独处理的。下面是一个例子 2, 上下文模型假设对已编码符号有一个预定义的集T，即所谓的上下文模版，有一个上下文的相关集C=0，1，C-1给出，这个上下文是通过操作在T上的一个模型函数F：T->C所定义的。对每一个即将要编码的符号x，可以利用它的已经编码的相邻符号 的概率模型来估计一个条件概率p(x|F(z)，在CABAC中

19、，符号是二进制形式，而且通过选择少数的上下文C使得算法变得更为简单。CABAC中有四种上下文模型的设计方式：第1种类型的模型必须根据它相邻的已编码的语法元素构成，一般是其左边和上边的对应语法元素来建立相应的概率模型，对当前语法元素进行模型预测。第2种模型仅局限于对宏块类型和子宏块类型的应用，其中第n比特的概率模型的选定要参考前面已编码n-1比特所采用的模型。第3种和第4种模型仅用于残余数据的编码，这两种模型都依赖编码块的类型，其中第3种模型依赖的不是已编码的系数，而是系数在扫描路径中的位置。第4种模型则要计算该比特所在系数之前已编码的系数数目。在CABAC中除了这些条件上下文模型之外，还有一些

20、固定概率模型，它们对待编码的比特提供固定的概率预测，已编码比特的模型不加以应用。 每个概率模型都对应一个索引，每个概率模型由两个值决定：一个6比特的概率状态索引，以及一个1比特的MPS符号。 从0到72的索引值与宏块类型，子宏块类型，空域和时域的预测模式，以及基于宏块和slice的控制信息的语法元素有关，在这种情况下的上下文索引值通过下式来计算 从73到398的模型索引通过下式来计算其中表示各种语法元素对应得模型索引的偏移量，也就是前文给出的那个索引表里的所定义的一些下限值，例如，对于mb_qp_delta而言，这个值就是60。在实际的程序设计时，我们可以不用考虑设计这个值，而是将不同类型的语

21、法元素单独设计一套模型索引值，即此时这个偏移量对于不同的模型类型都为0。取决于当前二进制符号的索引，这个值反映了上下文模型的概念，它由当前编码而进制字符的上下文模型的四种设计方式决定。 反映了模型类别，其取值规则如下：在JSVM中，定义了下列一些模型类型m_cBLFlagCCModel;m_cBLSkipCCModel;m_cBLQRefCCModel;m_cBCbpCCModel;m_cMapCCModel;m_cLastCCModel;m_cRefCCModel;m_cSigCCModel;m_cOneCCModel;m_cAbsCCModel;m_cChromaPredCCModel;m

22、_cMbTypeCCModel;m_cBlockTypeCCModel;m_cMvdCCModel; m_cRefPicCCModel;m_cBLPredFlagCCModel;m_cResPredFlagCCModel;m_cDeltaQpCCModel;m_cIntraPredCCModel;m_cCbpCCModel;m_cBCbpEnhanceCCModel;m_cCbpEnhanceCCModel;m_cTransSizeCCModel;每个模型类型里都定义一定数量的模型对这些模型进行初始化，以Intra型的m_cDeltaQpCCModel 为例，根据索引表可知，这个模型类型有4个

23、模型，其索引是从60到63，在设计的时候，因为我们单独设计了这个模型类型，因此其索引是从0到4，对应这四种模型我们定义一个数组static const Short INIT_DELTA_QP_I1142= /- model 0 - 0, 41 , 0, 63 , 0, 63 , 0, 63 , ; 根据这个数组来初始化这四个模型，注意这个数组里的0,41等数据对是根据一系列的训练序列得到的，它并不是我们前面提及的表征一个模型的数据对，我们将这个数组里的数据对记为,初始化就是由得到每个模型的初始的，转化原则如下这里还要注意的是这个参数，它表征的是二进制符号的概率，在CABAC中，符号的概率由LP

24、S的64个量化概率值表征， ，这个值范围由下面这个式子得到从上面的介绍我们可以看出，在预测当前符号的概率模型时，最主要的是根据前面介绍的四种上下文模型的设计方式来预测当前的概率模型，即主要是求出这个值，得到后，当前符号的模型索引确定，根据这个索引值，再已经初始化或已经更新了的模型系列中找到当前符号的预测概率模型，在这个模型里得到概率状态和MPS，即，对，利用这两个值进行算数编码，这在后面介绍算术编码时再具体介绍。下面我们介绍不同的语法元素的的求取方法，（注意：每个模型都是针对一个二进制化后的二进制符来说的，而不是针对语法元素本身的值，但有的语法元素的值直接可以用一个二进制符来表征）这里体现了上

25、下文的思想：A 宏块类型，预测模式，控制信息等语法元素1） 宏块和子宏块类型包含的语法元素有，mb_skip_flag，mb_type，sub_mb_type(仅讨论SP/P Slice) mb_skip_flag：相邻宏块编码特性被用来设计当前宏块的概率模型，对于一个给定的当前宏块C，设其左边宏块为A，上边宏块为B，则A和B的mb_skip_flag值被用来设计当前宏块mb_skip_flag对应的二进制字符的上下文模型，具体是用他们的值来求，如下所示如果A或B不可得，则将不可得的那个宏块的mb_skip_flag设为0。Mb_type和sub_mb_type：概率模型是固定的，与已编码的宏

26、块或子宏块无关，即对于一定的mb_type或sub_mb_type，有确定的值与它相对应。2） 预测模式Luma4x4的Intra预测模式：有两个句法元素，prev_intra4x4_pred_mode_flag和rem_intra4x4_pred_mode_flag，由前面的表可以看到，这两个语法元素对应的概率模型序号为68和69，即在程序设计时，可以把分别设计为0和1。在JSVM中，由m_cIntraPredCCModel这个模型类型表征。Chroma中的Intra预测模式：chroma_pred_flag，这个语法元素值经过TU方式的二进制化之后有3个字符，其中第一个二进制字符的概率模型

27、由下式决定：其中C表示当前色度块，A表示左边色度块，B表示上边色度块，ChPredInDCMode表示某个色度块的预测方式是否是DC Mode （用0表示），有上面的表达式可以看出，第一个二进制字符的概率模型有3种。在CABAC中，第一个二进制字符之后的两个二进制符采用固定的概率模型，故这种类型的概率模型共有4种，JSVM中用m_cChromaPredCCModel成员类来表征这种类型的概率模型，这个成员类里有一个长度为4的一维概率模型变量。参考图象索引：ref_idx，也是对这个语法元素值所对应的第一个二进制字符进行概率模型预测，是用上下文思想，其后的字符采用固定的模型。RefIdxZero

28、Flag表示某个分割块其参考帧索引是否为0。MVd：对于某个分割，用mvd(X,cmp)来表示其mvd，cmp是mvd的横纵座标值，即horizontal，vertical，则mvd对应的第一个二进制字符的概率模型由下式决定：前面介绍过,mvd的二进制化是用的是S=9的UEG3的方式，在编码余下的二进制字符时，使用如下方案，前缀中剩下的8个字符使用另外的四个固定的模型，后缀中的字符使用bypass编码方式，即不使用概率模型。3）控制信息：mb_qp_delta，end_of_slice_flag，mb_field_decoding_flag第三个我很少用到，只介绍前两个mb_qp_delta:

29、 在二进制化这个语法元素值x(c)之前，将它的值作一个转化x(c)=2|x(c)|-(x(c)>0)?1:0) 然后再对x(c)使用Unary方式的二进制化，二进制化后的第一个字符的模型由下式决定(x(P)!=0)，P表示C的下一个解码宏块。剩下的二进制符使用两个固定的概率模型。 end_of_slice_flag:使用一个特定的非自适应概率模型。B 残差数据的编码1）有以下一些特征：1 在一个给定的dct变换块中，1比特的coded_block_flag表示是否有非零系数出现，一个二进制值significance map表征非零系数的位置。2 非零系数以反扫描顺序编码。3 非零系数编码

30、上下文模型的选择基于已编码的非零系数数目（注意编码顺序是反扫描顺序）2）编码流程：首先，一个1比特的参数coded_block_flag被传送。如果coded_block_flag为0，则这个块将不会传送任何其他信息，否则，一个标示非零系数位置的significance map将会被编码。最后，各个非零系数的绝对值及其符号被编码，注意这些符合以反扫描次序被传送。下图是一个编码过程图Coded Block Pattern:对于除了Intra16x16的nonskip模式的宏块，coded_block_pattern标示了6个8x8块，其中4个Luma块，2个Chroma块，这个参数的二进制化采用

31、的方案是4-bit FL+TU(S=2)。标示这六个块中哪些块含有非零的变换系数。Coded Block Flag：是一个1比特符号，标示一个变换块是否有非零系数。Significance Map：对于扫描次序中的每个系数，一个1比特的符号significant_coeff_flag被传送，如果significant_coeff_flag为1，另外一个1比特的符号last_significant_coeff_flag也被传送，这个符号标示是否当前sig系数是最后一个sig系数，下图是一个sig map 的一个例子Level Information：sig 系数是用两个符号，coeff_abs_

32、level_minus1和coeff_sign_flag，一个标示系数的绝对值，一个标示系数值的符号。注意，系数的编码顺序是反扫描顺序，这可以用来合理地去调整上下文模型，下面会讲到。 3）残差数据的上下文模型如下图所示，将所有的block类型分为5大类型，Coded Block Pattern：将coded_block_pattern二进制化后有6个二进制字符，前4个代表Luma，后2个代表Chroma，前四个字符的概率模型由下式决定其中bin_idx表示字符索引，后两个字符的概率模型的获取方式和前四个字符的概率模型获取方式一样。Coded Block Flag：对于上表中的5种类型，每种类型

33、都采用4种概率模型，获取方式如下式： A表示当前块左边的块，B表示当前块上边的块 这里有几个问题需要注意： 上面这个式子只适用上表中所标示的同类型的块，若相邻块不是同类型的块，例如当前块属于Intra16x16，而相邻块X是以Inter方式编码，那么这时候的coded_block_flag(X)取值0；如果当前块的相邻块不属于当前块的Slice（当然，这也包含相邻块不存在的情况），这时候coded_block_flag(X)取缺省值，这个缺省值有两种取法，当前块是Intra型时，这个缺省值取1，否则取0。由此可见，对于coded block flag总共有5x4=20种概率模型供选择。Sign

34、ificance map：significant_coeff_flag和last_significant_coeff_flag总共有15种不同的概率模型供选择，他们的选择方式取决于当前系数的扫描位置，如下：Level Information：反的扫描顺序可以提供一个更为准确的概率估计，因为在这种反扫描路径的最后，很容易出现连续的trailing 1的情况。编码coeff_abs_level_minus1的时候，用到两种模型，一种是二进制化后的第一个字符用到的概率模型，另一种是编码UEG0的剩余前缀字符（1到13）用到的。NumT1(i)表示已编码的trailing 1个数，NumLgt1(i)

35、表示已编码完的绝对值大于1的系数个数，i表示当前系数的扫描位置，而编码次序是反扫描次序，这意味着这两个值随着i的减小而增大，则coeff_abs_level_minus1的第一个字符的概率模型由当前的NumT1决定，但如果NumT1的值大于3了，则编码剩余系数时所选取的 的值总是3。如果NumLgt10，则后面系数选取总为4。对于bin_index>0的情况（1<=bin_index<=13）,如果有NumLgt10，则为5+min(4,NumLgt1(i)；下表给出了个例子：注意上面这个表的编码顺序是从i=9到i=1的。对于UEG0的后缀部分及非零系数的符号信息的编码都采用

36、bypass coding。C 二进制编码由上面所述可以得到当前字符的概率模型，也就是得到了当前模型中的LPS的索引以及MPS字符，再结合上一次编码所提供的Interval的Range值R，下一步就是要对当前的字符进行二进制编码，这里的二进制编码和第二部分所讲的就大致相同了，过程如下：随着一个即将编码字符的到来，原有的Interval将会被分割成两个subInterval，一个Interval的宽度为，这与LPS相关，另外一个是，这与MPS相关，是与得到的概率模型中的LPS索引对应的，根据当前的字符是MPS还是LPS划分出一个新的Interval，这就与第二部分所述的二进制算术编码完全一致了。

37、为了简化计算以及减少乘法运算带来的复杂度，CABAC中做了如下处理：将R的值限定在1<<8到1<<9（即256到512之间），初时化R为512，将R值量化成4个值。由于是与对应的，有64个值，这样上面的乘法就只有4x64个值，将这个乘法运算做成一个以R和为索引的二维数组，由于R的值较大，而R索引实际只有四个，故对R做一个处理(R>>6)&3，这样上面的乘法运算结果就合成到一个TabRangeLPS644的数组中，就这样得到概率模型后，二进制编码可用下图流程来说明：writeSymbol( UInt uiSymbol, CabacContextMode

38、l& rcCCModel );传递一个即将编码的字符以及其对应的ModelUInt uiLow = m_uiLow;UInt uiRange = m_uiRange;UInt uiLPS = g_aucLPSTable64x4rcCCModel.getState()(uiRange>>6) & 3; /compute the Interval of LPS,that's Rlps AOT_DBG( 1 < uiSymbol ); rcCCModel.incrementCount(); uiRange -= uiLPS; if( uiSymbol != rcCCModel.getMps() ) /for the first time,the default MPS uiLow += uiRange; uiRange = uiLPS; if( ! rcCCModel.getState() ) rcCCModel.toggleMps(); rcCCModel.setState( g_aucACNextStateLPS64rcCCModel.getSt