cabac原理及其实现笔记

Context-BasedAdaptiveBinaryArithmeticCodingintheH.264/AVC简称Cabac，H264中的一种熵编码方式：基于上下文的自适应二进制算术编码内容安排：1，介绍算术编码2，介绍二进制算术编码3介绍Cabac及其一些实用的实现方式（参考JSVM代码，也可以参考JM）---张新发一，算术编码算术编码是一种常用的变字长编码，它是利用信源概率分布特性、能够趋近熵极限的编码方法。它与Huffman一样，也是对出现概率大的符号赋予短码，对概率小的符号赋予长码。但它的编码过程与Huffman编码却不相同，而且在信源概率分布比较均匀的情况下其编码效率高于Huffman编码。它和Huffman编码最大的区别在于它不是使用整数码。Huffman码是用整数长度的码字来编码的最佳方法，而算法编码是一种并不局限于整数长度码字的最佳编码方法。算术编码是把各符号出现的概率表示在单位概率[0，1]区间之中，区间的宽度代表概率值的大小。符号出现的概率越大对应于区间愈宽，可用较短码字表示；符号出现概率越小对应于区间愈窄，需要较长码字表示。举例如下：以符号3324SSSS为例在算术编码中通常采用二进制分数表示概率，每个符号所对应的概率区间都是半开区间，即该区间包括左端点，而不包括右端点，如S1对应[0,0.001)，S2对应[0.001,0.01)等。算术编码产生的码字实际上是一个二进制数值的指针，指向所编的符号对应的概率区间。符号序列3324SSSS……的第一个符号S3用指向第3个子区间的指针来代表，可以用这个区间内的任意一个小数来表示这个指针，这里约定这个区间的左端点代表这个指针，因此得到第一个码字.011。后续的编码将在前面编码指向的子区间内进行，将[.011,.111]区间再按概率大小划分为4份，第二个符号S3指向.1001(S3区间的左端），输出码字变为.1001。然后，S3对应的子区间又被划分为4份，开始对第三个符号S2进行编码，…….两个参量：编码点（指针所指处）C和区间宽度A。初始状态编码点（指针所指处）C=0区间宽度A=1.0新编码点C=原编码点C＋原区间A×Pi新区间A=原区间A×pi序列S3S3S2S4……的编码过程：第1个符号(S3):C=0+1×.011=.011A=1×.1=.1第2个符号(S3):C=.011+.1×.011=.1001A=.1×.1=.01第3个符号(S2):C=.1001+.01×.001=.10011A=.01×.01=.0001第4个符号(S4):C=.10011+.0001×.111=.1010011（输出的码字）A=.0001×.001=.0000001解码过程算法解码采取与编码过程相反的步骤把接收到的码字串指向其对应的子区间，得到此子区间对应的符号，即为解码后的符号。即从码字串中减去已解码符号的子区间的左端点的数值（累积概率），并将差值除以该子区间的宽度（概率值），得到新的码字串。上述例子当收到字码串(.1010011)时，其指向子区间[.011,.111]，对应于S3，因此，得到第1个符号为S3。新码字串：（.1010011-.011)÷(.1)=0.100011，新码字串仍然指向子区间[.011,.111]，因此，第2个符号仍为S3。其它符号依次类推二，二进制算术编码二进制算术编码的输入的字符只有两种，如果信源字符集内包含有多个字符，则先将这些字符经过一系列的二进判决，变成二进制字符串。这两个符号构成的序列的编码与算术编码基本原理相同，仍是不断划分概率子区间的递归过程。在两个输入字符中，出现概率较大的为MPS(MoreProbableSymbol)，MPS的概率为Pe；出现概率较小的为LPS(LessProbableSymbol)，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）例:信源符号序列110111110为LPSQe=1/8=（0.001）b1为MPSPe=7/8=（0.111）b初始状态：C=0(子区间起始位置)A=1（子区间宽度）1，第1个符号1为MPSC=C+AQe=0+10.001=0.001A=APe=10.111=0.1112，第2个符号1仍为MPSC=C+AQe=0.001+0.1110.001=0.001111A=APe=0.1110.111=0.1100013，第3个符号0为LPSC=C=0.001111A=AQe=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是被解码的值，初始值A=1Qe=0.001当c’落在0-QeA之间，解码符号为D=0，则C’=C’，A=QeA当c’落在QeA-A之间，解码符号为D=1，则C’=C’-QeA，A=A（1-Qe）1，c’=0.0101落在QeA-A之间，解码符号为D=1c’=c’-QeA=0.0101-0.001=0.0011，A=A（1-Qe）=0.1112，c’=0.0011落在QeA-A之间，解码符号为D=1c’=c’-QeA=0.0011-0.000111=0.000101，A=A（1-Qe）=0.1110.111=0.1100013，c’=0.000101落在0-QeA之间，解码符号为D=0c’=c’=0.000101A=AQe=0.1100010.001=0.000110001三，CABAC原理及其实现CABAC是H264的一种熵编码方案，相比如H264的另外一种熵编码方案CAVLC而言，在可接受的视频质量（30dB到38dB之间）内变化时，前者可节约平均9%到14%的码流。CABAC有以下几个特性：1，对多数符号使用了自适应概率模型。2，通过使用上下文关系，利用了符号相关性。3，限制为二进制算术编码（binaryarithmeticcoding），基于只用查表和移位方式的快速二进制算术编解码器。4，399种预定义的上下文模型，分成了各种不同的模型组，例如模型14-20用于帧间宏块类型的编码，模型的选择基于前面编码的信息（上下文关系），每个上下文模型适应实验分布。先大致介绍CABAC的实现过程，然后对一些技术做细节介绍下面是CABAC的编码流程图按上图可知，对一个符号编码有如下过程：1，转化成二进制(Binarization)CABAC使用二值算术编码，也就是说只对二进制的判决（0或者1）进行编码。非二进制符号（例如转换后的系数或者运动矢量）在编码前先要进行二进制转换。这一过程和变长编码（VLC）中将信息符号转化为变长编码一样，所不同的是，算术编码器在将信息送去传输之前还要进一步对这些二进制符号进行编码。2,选择基于内容的模型：“基于内容的模型”是二进制符号中一个或多个比特的概率模型。根据对先前已编码符号的统计，从可选模型中选择适当的概率模型。3,算术编码：根据选择的概率模型对每个比特进行算数编码。4,更新模型上图中的bypasscoding是指对于一些特定语法元素的二进制比特符号，为了加快编码速度而不使用上下文模型的形式。使用CABAC的熵编码方式在时间耗费方面大于CAVLC，为了达到一个折中，在实际编码中，并不是对所有的语法元素都使用CABAC编码方案，有许多表征视频序列本身固有参数特征的语法元素的熵编码还是使用CAVLC。下图是一些需要用CABAC编码的语法元素及对应的上下文模型索引。下面来具体介绍编码过程1，二进制化为了降低算术编码的复杂度，提高编码速度，采用二进制算术编码，即进行熵编码的符号是一系列的二进制符号，这得首先需要把编码语法元素转化成二进制串，包括基本方案和串接方案。UnaryBinarization：对于x=0的无符号整数值，由x个”1”和一个终结符合”0”组成。TruncatedUnaryBinarization（TU）：给定一个参数S,对于编码符号x，0=x=S有效，如果xS,则取x=S，对于xS时，二进制串由UnaryBinarization方案给出，对于x=S，UnaryBinarization方案中的那个终结符号”0”被忽略，此时输出二进制串为x个”1”。kthorderExp-Golom(EGK)Binarization：由一个前缀和一个后缀码字串接而成，对于给定x,下面是产生一个k阶指数格雷码的算法while(1){//unaryprfixpartofEGKif(x=(1k)){put(1)x=x-(1k)k++}else{put(0)//terminating“0”ofprefixpartwhile(k--)//binarysuffixpartofEGKput((xk)&0x01)break}}前缀是由对应值为2log(/21)kx的UnaryBinarization方案产生的二进制串组成，后缀由()2(12)klxx这个十进制值对应的二进制串组成。Fixed-Length(FL)Binarization：给定一个参数S，对于编码语法元素x，必须满足0=xS，输出二进制串为十进制值x对应的二进制数。ConcatenationofBasicBinarization：串接方案，有以下几种组合：1，编码codedblockpattern时，cbp代表了六个8x8块的编码系数情况(4个亮度，2个色度，具体会在后面讲到)，这时候，以4-bit的FL方案产生的二进制串作为前缀表征亮度部分，以S=2的TU方案产生的二进制串作为后缀表征色度部分。2，Unary/kthorderExp-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方式，后缀采用EG0方式，注意此时二进制化的语法元素coeff_abs_value_minus1=abs_level-1，对于abs_level=0的情况，我们用一个significancemap将其处理了。这和二进制化mvd比较相似，但此时并没有处理符号，符号是后面要单独处理的。下面是一个例子2,上下文模型假设对已编码符号有一个预定义的集T，即所谓的上下文模版，有一个上下文的相关集C={0，1，…，C-1}给出，这个上下文是通过操作在T上的一个模型函数F：T---C所定义的。对每一个即将要编码的符号x，可以利用它的已经编码的相邻符号zT的概率模型来估计一个条件概率p(x|F(z))，在CABAC中，符号是二进制形式，而且通过选择少数的上下文C使得算法变得更为简单。CABAC中有四种上下文模型的设计方式：第1种类型的模型必须根据它相邻的已编码的语法元素构成，一般是其左边和上边的对应语法元素来建立相应的概率模型，对当前语法元素进行模型预测。第