【Codecs】CABAC熵编码详解

###Date: 2018.5.9

========================================================

转载自：https://blog.csdn.net/listener51/article/details/60970635


    整理网址：http://www.cnblogs.com/TaigaCon/p/5304563.html 
　整理网址：http://blog.csdn.net/shakingwaves/article/details/52426244 
　表格生成：http://pressbin.com/tools/excel_to_html_table/index.html 
　 
　在视频数据压缩种，按照压缩前后图像信息量是否有损失，可以将压缩方法分为两类：一类是无失真编码或熵编码；另一类是有限失真编码。 
　基于混合编码的视频压缩标准中，变换、预测后的量化处理属于有限失真编码，消除的是信源空间和时间的冗余度。而对量化后的预测残差变换系数形成的语法元素，采用的熵编码消除的是码字之间的冗余度，属于无失真编码。　 
　　

1. 信息熵的概念

　信息熵是指信号源（信源）的信息量。设有一个离散信源，这里写图片描述，它产生消息的概率是已知的，记为 ，这里写图片描述，（ 这里写图片描述），则信息量定义为： 

这里写图片描述 （bit） （１）

　信息量仅反映了一个符号的信息量的大小，而信源都是由若干个符号所组成，如二进制信源由0和1两个符号，因此，用平均信息量，称为“熵”（entropy）来表示由多个符号所组成信源所携带的信息量，定义为： 
这里写图片描述

　上式取以2为底的对数时，单位是比特： 
这里写图片描述（比特/符号） （２）
　

２. 定长编码

　定长编码也称为等长编码，即为每个编码符号分配一个等长比特的码字。常用的二进制码如表1： 

这里写图片描述
　 
　在HEVC中，描述子f(n)表示有一个固定n比特的预定义值。具体到某一具体语法元素forbiden_zero_bit,它是一个f(1)码字，即1比特长度，其值为0。这种定长编码主要用于NAL单元头，slice分割头以及SPS/PPS中。 
　

３. 变长编码

　变长编码为各个编码符号分配的比特数不一定相等，常见的变长编码有哈夫曼、香浓、指数哥伦布编码等。变长编码的优势是编码的平均长度比定长编码短。例如概率分布为2的负幂次方的序列符号，具体如下： 

这里写图片描述 
图 3 概率分布为2的负幂次方的序列符号
　

3.1 哈夫曼编码

　对图3采用哈夫曼如图： 

这里写图片描述

　按照公式这里写图片描述计算其平均码长为： 
这里写图片描述

　若采用定长编码，则需要3位二进制等长码。 
　

3.2 算术编码　

3.2.1 传统编码方法

　传统编码是通过符号映射实现的。映射包含符号（symbol）与码字（codeword）两个要素，如下面的例子 

symbol e h l o
codeword 00 01 10 11


　通过上述的映射表，我们可以把“hello”编码成码流 01 00 10 10 11。 
　而诸如Haffuman，Shannon这些编码方法也没脱离这种编码模式，他们只是通过符号出现的概率对码字进行调优。 
　

3.2.2 算术编码

　从理论上讲，对信源数据采用哈夫曼熵编码方法可以获得最佳编码效果，但是在实际中，由于在计算机中存储和处理的最小数据单位是1bit，无法表示小数比特。例如两符号信源{x,y}，其对应的概率为{2/3,1/3}, 根据信息熵计算，x的最佳码长=−log2(2/3)bit=0.588bit−log2(2/3)bit=0.588bit,y的最佳码长=−log2(1/3)bit=1.588bit−log2(1/3)bit=1.588bit，平均码长=0.588X(2/3)+1.588X(1/3)0.588X(2/3)+1.588X(1/3)=0.961bit=0.961bit。而计算机中不可能有非整数位出现，即采用哈夫曼对x,y编码，得到{x，y}的码字分别为0和1，可见对于出现概率大的符号x并未赋予较短的码字。而算术编码的产生正是为了解决计算机中必须以整数位进行编码的问题。 
　算术编码的思想是用0到1的区间上的一个数字来表示一个字符输入流，本质是为了整个输入流分配一个码字，而不是给输入流中的每个字符分别指定码字，算术编码是用区间递进的方法来为输入流寻找这个码字的，从第一个符号确定的初始区间0,1开始，逐个字符地读入输入流，在每一个新的字符出现后递归地划分当前区间，划分的根据就是各个字符的概率，将当前区间按照各个字符的概率划分为若干子区间，将当前字符对应的子区间取出，作为下一个字符时的当前区间，当处理完最后一个字符后，得到了最终区间，在最终区间中挑选一个数字作为输出。 
　算术编码分为浮点算术编码与定点算术编码，例如对浮点算术编码而言：用[0, 1]的概率区间，对一串字符编码后，得到了最终区间，在最终区间挑选一个数字作为编码输出，而这个数字是一个小数，受计算机精度的影响；为了避免这种影响，在实际使用中采用定点算术编码，且根据计算机的精度采用比例缩放的方法la来解决。在H264/H265中将[0, 1]区间放到至[0,210210]，采用32位的寄存器实现。 
　 
　算术编码有如下编码步骤：

1.　首先我们需要根据概率设定各符号在[0,1)上的初始区间，其中区间的起点为表中前面的符号的累计概率
symbol e h l o
sum of probability 0 0.1 0.1+0.2 0.1+0.2+0.3
interval [0,0.1) [0.1,0.3) [0.3,0.6) [0.6,1

　“hello”的第一个符号为“h”，那么映射的区间为[0.1,0.3)。

2.　接下来我们需要根据符号的概率分割[0.1,0.3)上的区间，得到的结果如下
symbol e h l o
interval [0.1,0.12) [0.12,0.16) [0.16,0.22) [0.22,0.3)

　“hello”的第二个符号为“e”，那么映射的区间为[0.1,0.12)。

3.　 按照这种方式继续进行区间映射，最终“hello”映射到的区间是[0.10888,0.1096)
映射区间 区间大小
初始值 [0,1) 1
编码完h后 [0.1,0.3) 0.2
编码完e后 [0.1,0.12) 0.02
编码完l后 [0.106,0.112) 0.006
编码完l后 [0.1078,0.1096) 0.0018
编码完o后 [0.10888,0.1096) 0.00072

4.　 从区间[0.10888,0.1096)中任取一个代表性的小数，如“0.109”就是编码“hello”后的输出值*

　算术编码的总体的编码流程可以参考下图 
这里写图片描述

　算术编码总体上可以按照如下进行描述：

  • 设输入符号串为ss，ss中的符号值取自符号集S={a1,a2,a3,…,am}S={a1,a2,a3,…,am}
  • 这些符号出现的概率分别为p(ak)={p1,p2,p3,…,pm}p(ak)={p1,p2,p3,…,pm}
  • 这些符号的累计概率为P(ak)=∑1i−1pkP(ak)=∑1i−1pk。累计概率可以理解为，如果区间为[0,1)时，该符号的区间起点的位置<端点>。
  • 区间大小更新为Ri+1=Rip(ak)Ri+1=Rip(ak)，初始值为R0=1R0=1 
    即新活动区间=前活动区间 X “akak”的概率
  • 区间的起点更新为Li+1=Li+P(ak)RiLi+1=Li+P(ak)Ri，初始值为L0=0L0=0 
    即新端点=前端点+前活动区间 X”akak”的端点

．当处理符号akak时，区间RR宽度根据akak出现概率p(ak)p(ak)而变窄，符号序列越长，相应的子区间越窄，编码的位数越多。 
　算术解码就只是需要判断代表性的小数在哪个区间，相应地就知道输入的符号了

3.2.3 二进制算术编码

　二进制算术编码的编码方法跟算术编码是一样的，但是输入只有两个符号：“0”，“1”，也就是说输入的是二进制串。 
　除了是对二进制串进行编码这个特征外，二进制算术编码跟普通的算术编码还有一些区别，总体上可以按照如下进行描述：

  1. 设输入符号串为ss，ss中的符号分为两种：MPS(Most Probability Symbol)，LPS(Low Probality Symbol)，分别代表出现概率大小的符号，需要根据实际情况进行调整。如果输入的二进制串中的“0”较多，“1”较少，那么MPS = “0”，LPS =“1”
  2. LPS出现的概率为pLPSpLPS，MPS出现的概率为pMPS=1−pLPSpMPS=1−pLPS
  3. 在编码中进行区间选择时，MPS在前，LPS在后，因此 
    • LPS的累计概率为PLPS=pMPS=1−pLPSPLPS=pMPS=1−pLPS
    • MPS的累计概率为PMPS=0PMPS=0 
      这里写图片描述
  4. 区间的大小更新为 
    • 如果当前编码的是LPS：Ri+1=RLPS=Ri⋅pLPSRi+1=RLPS=Ri⋅pLPS
    • 如果当前编码的是MPS：Ri+1=RMPS=Ri−RLPS=Ri–(Ri⋅pLPS)Ri+1=RMPS=Ri−RLPS=Ri–(Ri⋅pLPS)
  5. 区间的起点更新为 
    • 如果当前编码的是LPS：Li+1=Li+RMPSLi+1=Li+RMPS
    • 如果当前编码的是MPS：Li+1=LiLi+1=Li

4. CABAC编码

　CABAC采用的是二进制算术编码，在编码过程中需要传入二进制串，输出的也是二进制串。 
　在h.264标准中，CABAC在语法结构中用ae表示，它只用于编码slice_data中的语法元素（包括slice_data内部的子模块的语法元素） 
　CABAC实现分为四个部分

  • 上下文变量的初始化
  • 待编码语法元素二值化
  • 上下文建模（确定上下文索引）
  • 算术编码

4.1 上下文变量的初始化

　初始化执行于slice开始之前，另外如果在编码过程中某个宏块是PCM宏块，那么在PCM宏块之后，编码下一个宏块之前也需要进行初始化。 
　初始化主要工作就是确定所有上下文的初始MPS以及初始状态pStateIdx。求解方法如下

preCtxState = Clip3( 1, 126, ( ( m ∗ Clip3( 0, 51, SliceQPY ) ) >> 4 ) + n )

if( preCtxState <= 63 ) {
    pStateIdx = 63 − preCtxState
    valMPS = 0                          　　　　　　　　　　　　　　　　　　　　　　 ( 9-5)
} else {
    pStateIdx = preCtxState − 64
    valMPS = 1
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

　上面的计算依赖于SliceQPY，m，n三个变量，其中不同的上下文索引（contex Index）对应不同的m、n，具体的m、n的取值请参考标准9.3.1中的各个表格。上下文索引是基于语法元素以及二值化后的二进制串的索引binIdx，我们将在下一小节进行阐述。 
　在CABAC的初始化过程的结果会得到所有上下文索引对应的MPS与pStateIdx的初始值。如果确定了MPS为“0”，那么LPS为“1”，反之如果MPS为“1”，那么LPS为“0”。状态pStateIdx是什么呢？ 
　

4.1.1 LPS的概率　

　状态pStateIdx是LPS出现的概率pLPSpLPS的索引。在CABAC中规定了LPS的概率取值范围是pLPS∈[0.01875,0.5]pLPS∈[0.01875,0.5]，由于LPS是小概率符号，因此它的概率肯定是小于0.5的，如果某个小概率符号在状态转换的过程中超出了0.5，此时我们就需要把MPS与LPS进行交换。 
　CABAC的状态机中共有64个状态，pStateIdx = 0,1,2,…,63，分别代表64个不同的概率，除了pStateIdx = 63外，其他的63个状态都满足上述状态转换规则，其中 

{p0LPS=0.5p62LPS=0.01875{p0LPS=0.5p62LPS=0.01875

　结合4.1.2状态机的转换规则，我们可以得到状态转换参数 

α=(0.018750.5)1/63≈0.95α=(0.018750.5)1/63≈0.95
　

4.1.2 概率状态的更新

　算术编码中最重要的要素就是符号的概率，CABAC是自适应的算术编码，也就是说符号的概率会随着符号的输入而改变，这种变化就是一种状态机，如果输入的是LPS的话，状态（概率）会怎样变化，如果输入的是MPS的话，状态（概率）又会怎么变化。CABAC的状态机转换的规则由HOWARD与VITTER的”exponential aging”模型借鉴而来，转换规则如下 

p(t+1)LPS={α⋅ptLPSα⋅ptLPS+(1−α)if an MPS occursif an LPS occursp(t+1)LPS={α⋅ptLPSif an MPS occursα⋅ptLPS+(1−α)if an LPS occurs

　CABAC状态机的状态转换如下图（黑色实线代表输入的是MPS，红色虚线代表输入的是LPS），具体的pStateIdx变换请参考标准的表9-45 

这里写图片描述
　

4.2 待编码语法元素二值化

　CABAC编码的是slice data中的语法元素，在进行算术编码前，需要把这些语法元素按照一定的方法转换成适合进行二进制算术编码的二进制串，这个转换的过程被称为二值化（binarization）。 
　二值化的方案共有７种 
　

4.2.1 一元码（Unary）

　对于一个非二进制的无符号整数值符号x⩾0x⩾0，在CABAC中的一元码码字由xx个“1”位外加一个结尾的“0”组成，见下表。例如，输入的语法元素值为3，其二值化结果为110。解码器靠搜索一个”0”来判断何时语法元素结束。 
这里写图片描述

4.2.2 截断一元码（TU，Truncated Unary）

　一元码的变体，用在已知语法元素的最大值cMax的情况。对于0⩽x<cMax0⩽x<cMax的范围内的取值，使用一元码进行二值化。对于x=cMaxx=cMax，其二值化的二进制串全部由“1”组成，长度为cMax。对于x>cMaxx>cMax，则取x=cMazx=cMaz进行编码。例如，当cMax=5时，语法元素值为4的二进制串为11110，语法元素值为5的二进制串为11111。

4.2.3 截断莱斯码(TR, Truncated-Rice)

　在已知门限值cMax、莱斯参数R和语法元素值V的情况下，即可获得截断莱斯二元码串。截断莱斯码由前缀和后缀串接而成，前缀值P的计算方法为： 
　

P=V>>RP=V>>R

　则其对应的前缀码获取过程是：若PP小于值（cMax>>RcMax>>R），则前缀码由PP个1和一个0组成，长度为P+1P+1；若PP大于等于值(cMax>>RcMax>>R)，则前缀码由(cMax>>RcMax>>R)个1组成，长度为(cMax>>RcMax>>R)。当语法元素V小于cMax时，其后缀值S为： 
　
S=V−(P<<R)S=V−(P<<R)

　后缀码为S的二元化串，长度为R。当语法元素V大于等于cMax时，无后缀码。 
　

4.2.4 k阶指数哥伦布编码（kth order Exp-Golomb，EGk）

　一、指数哥伦布编码映射关系 
　指数哥伦布码是一种压缩编码算法。指数哥伦布编码有四种映射关系，从Ｖ到code_num，其中，code_num是码字的编号，V是有符号数或无符号数。 
　ue：无符号整数指数哥伦布编码的语法元素，这种映射关系应用在宏快类型、参考帧索引等。映射关系为：code_num=Ｖ； 
　se：有符号整数指数哥伦布编码的语法元素，左位在先，这种映射关系应用在运动矢量插值、量化参数插值等。 
　映射关系为：

code_num=2|Ｖ| (Ｖ <= 0)

code_num=2|Ｖ|-1 (Ｖ > 0)

　te：舍位指数哥伦布编码的语法元素； 
　me：映射的指数哥伦布编码的语法元素，左位在先。参数k通过指定的表格映射到code_num。这种映射关系应用于coded_block_parttern参数。 
　每种映射关系被设计成对出现频率高的值使用较短的码字，对出现频率低的值使用较长的码字。 
　 
　二、指数哥伦布编码的逻辑结构 
　指数哥伦布编码的逻辑结构为：[M个 Zeros] [1] [INFO]，包括前缀码和信息位两个部分。其中，INFO是M个bit所携带的信息。例如，如下码字： 
这里写图片描述

　code_num 0 没有前缀码和INFO，code_num1 和 2 有1 bitINFO，code_num 3到6有两 bit INFO。每个哥伦布码字的长度为2M+1，并且基于code_num，每个codeword可以被重构，通过下面的公式： 
M = floor[log2(code_num + 1)]

INFO = code_num + 1 - 2^M

　一个codeword可以通过下面的方式来解码： 
　　（1）读入M个bit的前缀0，紧接着是1； 
　　（2）读入M个bit的INFO； 
　　（3）code_num = 2^M + INFO -1 (对于codework 0，M和INFO都为0). 
　　 
　三、K阶指数哥伦布码 
　K阶级指数哥伦布码如下表所示，表中给出了0阶、1阶、2阶和3阶的指数哥伦布码。 
这里写图片描述

　k阶哥伦布编码的逻辑结构：[(M-k) Zeros] [1] [M bits INFO] 
M = floor[log2(code_num + 2^k)]

INFO = code_num + 2^k - 2^M

　码字长度：L = (M - K) + 1 + M = 2 * M - K + 1 
　 
　四、k阶哥伦布码的编码过程 
　用来表示非负整数的k阶指数哥伦布码，可以通过下面的方式获得： 
　　（1）将数字以二进制的形式写出，去掉最低的k个比特位，然后加1； 
　　（2）计算剩下的比特数，将此数减1，即得前缀0的个数M-k；

　五、k阶哥伦布码的解码过程 
　解析k阶指数哥伦布码时，首先从比特流的当前位置开始寻找第一个非零比特leadingZeroBits，然后根据公式计算出code_num的值： 

code_num = 2^(leadingZeroBits + k) - 2^k + values;

　其中，values为第一个非零比特其后的(leadingZeroBits + k)个比特的值。 
　

4.2.5 定长编码（FL，Fixed-Length）

　用定长编码二进制的无符号语法元素， 语法元素的最大值cMax已知，那么定长编码的长度为fixlength=⌈log2(cMax+1)⌉fixlength=⌈log2(cMax+1)⌉，其中值就是语法元素的值的二进制。定长编码用于近似均匀分布的语法元素的二值化。 
　给定一个参数cMax，对于编码语法元素值x，必须满足0≤x<cMax0≤x<cMax，输出二进制串为十进制值x对应的二进制数，其最小长度固定为lFZ=⌊log2(cMax)⌋lFZ=⌊log2(cMax)⌋，最高位比特(MSB)标注在最低位比特之前（LSB）。一个3比特长的定长码的码表见下表： 

表 4.2.5 定长码一例(cMax=8cMax=8) 
这里写图片描述

　

4.2.6 4位FL与截断值为2的TU联合二值化方案

　这种方案只用于对语法元素CBP的二值化。4位的FL（cMax=15）的前缀用于编码亮度CBP，2位的TU用于编码色度CBP（当色彩格式为4:2:0或4:2:2时才会存在这个后缀） 
　

4.2.7 TU与EGk的联合二值化方案（UEGk，Unary/kth order Exp-Golomb）

　这种方案的前缀使用一元截断码，后缀使用k阶哥伦布编码。但是在取值较小的范围内，只用一元码表示（即只有前缀部分）。对于不同的语法元素，有不同的截断值与阶数。如下表为abs_level_minus1的二值化表(cMax=14的TU、0阶哥伦布编码) 
这里写图片描述
　具体哪个语法元素选择哪种二值化方案，请查看标准9.3.2中第一个表格。 
　　

4.3 上下文建模（确定上下文索引）

　在前面初始化的时候就出现了上下文这个概念，那么上下文所指的是什么？ 
　以JM中的上下文结构体为例

 //! struct for context management
struct bi_context_type   
{ 
   unsigned long  count;  
   byte state; //uint16 state;         // index into state-table CP
   unsigned char  MPS;           // Least Probable Symbol 0/1 CP  
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

　上下文包含两个变量：MPS、pStateIdx（count只是用于计数）。在CABAC编码的过程中会碰到需要修改这两个值的情况（如上面的状态变换），这些修改都是以上下文为单位的。 
　语法元素在经过二值化后形成二进制串，二进制串中不同binIdx位置上的MPS（出现频率高的符号）可能会有所不同，并且概率也可能会不同，因此需要用一个概念来表示特定语法元素的二进制串中特定binIdx的MPS与pStateIdx，上下文就是这样的概念。 
　在h.264标准中，用一个上下文索引ctxIdx来代表上下文，ctxIdx的取值为0~1023，就是说h.264的上下文一共有1024个。 
　ctxIdx的计算方式分为两种 
　如果语法元素为coded_block_flag、significant_coeff_flag、last_significant_coeff_flag、coeff_abs_level_minus1，即残差系数部分的语法元素，则 

ctxIdx = ctxIdxOffset + BlockCatOffset(ctxBlockCat) + ctxIdxInc(ctxBlockCat)

　否则 
ctxIdx = ctxIdxOffset + ctxIdxInc

　其中的变量有

  • ctxIdxOffset 每个语法元素都有一个ctxIdxOffset，甚至一些语法元素在二值化后分为前后缀，这种语法元素可能会有两个ctxIdxOffset，如下表格部分摘自h.264标准9.3.2的第一个表格 
    这里写图片描述

    　表9-25中，maxBinIdxCtx以及ctxIdxOffset列中的某些单元格含有前缀、后缀的字样，例如语法元素列的mb_type（P, SP slices only），其二进制序列类型中含有前缀以及后缀，具体参见9.3.2.5节的规定：在 P 和 SP 条带中的 I 宏块类型二进制码串，对应 mb_type 的值从 5 到 30，包含了前缀和后缀的串联，这里前缀包含了表 9-28 中规定的值为 1 的单个比特，后缀在 9-27 中规定，通过 mb_type 减 5 所得的值索引。 
    这里写图片描述
  • ctxIdxInc 在特定的语法元素二值化后，会形成以binIdx为索引的二进制串，尽管是同一个二进制串，但是不同的binIdx上的上下文（MPS，pStateIdx）可能会有所不同，ctxIdxInc就是在这种情况下产生的一个值，它用于划分二进制串上不同的上下文。如下面一项表格摘自h.264标准9.3.3.1的第一个表格 
    这里写图片描述

    　表9-30中当ctxIdxOffset取值为14时，binIdx取值为2时，ctxIdxInc可取2也可取3，具体参见9.3.3.1.2小节的第一个表格 
    这里写图片描述

    　表９-32中ctxIdxInc列的b1、b3对应表9-25中二进制序列的相关类型，具体参见9.3.2.5小节： 
    这里写图片描述
  • BlockCatOffset(ctxBlockCat) 其中ctxBlockCat的范围为0~13，分别代表不同残差块类型，如下表 
    这里写图片描述

    　在残差系数部分，上下文是会根据不同的残差块类型做出不同选择的，BlockCatOffset就代表了不同的残差块类型的索引偏移，具体偏移值可以查看标准中的相关表格。

4.4 算术编码

　算术编码是基于区间划分的，普通的概率划分需要使用到多位乘法。CABAC的算术编码为了降低计算复杂度，并便于硬件实现，采取了如下一些方法：

  1. 总是估计小概率符号LPS（pLPS<0.5pLPS<0.5）的概率，并将其概率离散化成64个不同概率状态。概率估计转换成基于表格的概率状态的转换（见初始化部分的描述）。
  2. 使用9bit的变量RR与10bit的LL表示当前区间，其中LL为区间的起点，RR为区间长度
  3. 每当输入新符号时，会对区间的起点LL以及区间的长度RR进行更新，在前面的二进制算术编码时，我们已经得知两者的更新方法，其中RR与LL的更新包含了浮点数乘法Ri⋅pRi⋅p，为了降低运算复杂度，CABAC把乘法换算成了查表的形式。换算方法如下： 
    • 离散化的状态pStateIdx代表了符号的概率pp
    • 9个bit的区间长度RR通过(R>>6)&3被量化成2个bit，即{0，1，2，3}{0，1，2，3}（因为RR总是大于等于2828小于2929，在后面的归一化可以看出 来）
    • 有了上述两个离散的变量，区间更新所需要的乘法就能转换成查表操作，表格请查看标准9.3.3.2中的第一个表格。
  4. 在算术编码的过程中，尽管是同一上下文，但是概率并不是固定的，每次输入一个新符号都会改变相应上下文的概率，也就是会进行状态转换（见初始化部分的描述）
  5. 对近似均匀分布的语法元素，在编码和解码时选择盘路（bypass）模式，可以免除上下文建模，提高编解码的速度。
  6. 由于编码区间是有限位表示的，因此在输入一个符号进行区间更新后，需要进行重归一化以保证编码精度。

4.4.1 算术编码过程

这里写图片描述

　该过程可分为5个步骤

  1. 通过当前编码器区间范围RR得到其量化值ρρ作为查表索引，然后利用状态索引pStateIdxpStateIdx与ρρ进行查表得出RLPSRLPS的概率区间大小。
  2. 根据要编码的符号是否是MPS来更新算术编码中的概率区间起点LL以及区间范围RR
  3. pStateIdx==0pStateIdx==0表明当前LPS在上下文状态更新之前已经是0.5的概率，那么此时还输入LPS，表明它已经不是LPS了，因此需要进行LPS、MPS的转换
  4. 更新上下文模型概率状态
  5. 重归一化，输出编码比特。

4.４.2 重归一化分析

　在区间划分结束后，如果新的区间不在[28,29)[28,29)之内，即R<256R<256，256是最大编码区间的1414，那么就需要进行重归一化操作（incremental output and interval expansion），输出一位或多位编码比特。重归一化过程如下图所示。 

这里写图片描述

　在CABAC编码过程中，在输入符号后，进行区间更新，接下来就是重归一化过程。下面就以[0,210)[0,210)表示区间[0,1)[0,1)为例，分析重归一化过程 
（请注意，在该过程中，[0,210)[0,210)只起到辅助作用，实际的区间为RR）

  1. R<28R<28的情况，如果L<28L<28，则可知R+L<29R+L<29，那么可以确定编码区间[L,L+R)[L,L+R)在区间[0,0.5)[0,0.5)上，用二进制表示这个区间即为0.0x0.0x，因此输出00（只记录小数点后面的二进制）。最后用[0,210)[0,210)来表示区间[0,0.5)[0,0.5)，也就是将原本的[0,29)[0,29)线性扩增到[0,210)[0,210)
  2. R<28R<28的情况，如果L⩾29L⩾29，那么就可以确定编码区间[L,L+R)[L,L+R)在区间[0.5,1)[0.5,1)上，用二进制表示这个区间即为0.1x0.1x，因此输出11。最后用[0,210)[0,210)来表示区间[0.5,1)[0.5,1)，也就是将原本的[29,210)[29,210)线性扩增到[0,210)[0,210)
  3. R<28R<28的情况，如果28⩽L<2928⩽L<29，则28<R+L<29+2828<R+L<29+28，编码区间[L,L+R)[L,L+R)可能在[0,0.5)[0,0.5)区间内，也有可能跨越[0,0.5)[0,0.5)与[0.5,1)[0.5,1)两个区间，即可能是0.01x0.01x，也可能是0.10x0.10x。此时可以先暂缓输出，用[0,210)[0,210)来表示区间[0.25,0.75)[0.25,0.75)，也就是将原本的[28,28+29)[28,28+29)线性扩增到[0,210)[0,210)，然后进入重归一化的下一个循环继续判断。
  4. R⩾28R⩾28的情况，无法通过L<28L<28来确定编码区间，需要通过输入下一个符号来对RR与LL进行更新后再继续进行判断，因此当前符号的编码流程结束。由于这个原因，因此在一个符号编码结束后，另一个符号编码开始前，总是28⩽R<2928⩽R<29。 
    这里写图片描述

4.４.3 输出

　在编码输出“0”或者“1”的阶段，用PutBit(B)表示 
　　

这里写图片描述

　关于PutBit(B)的分析，参考上面重归一化的区间图，可以看到有三种情况

  1. 情况1，走PutBit(0)，直接输出“0”
  2. 情况2，走PutBit(1)，直接输出“1”
  3. 情况3，输出可能为“10”或者“01”，因此不能直接输出，走bitsOutstanding++的步骤。在下一次编码符号时，符合情况2，走PutBit(1)，此时bitsOutstanding = 1，因此输出“10”

．另外，PutBit(B)不会编码第一个bit。原因是CABAC在初始化的时候，会以[0,210)[0,210)表示区间[0,1)[0,1)，而在初始化区间时R=510，L=0R=510，L=0，这意味着已经进行了第一次区间选择，区间为[0,0.5)[0,0.5)，需要输出“0”。PutBit(B)在此阻止这个“0”的输出，这样就能得到正确的算术编码结果了。

4.5 旁路(bypass)编码

　有些语法元素在二值化后选择的可能不是上述的算术编码，而是旁路编码，具体情况请查看h.264标准9.3.2的第一个表格。旁路编码中，假设待编码的符号符合近似的均匀分布。下图给出了旁路模式下的编码过程。 
　旁路模式有几个特点：符号均匀分布，无需对RR进行量化与查表；每编码完一个符号后，RR总是会小于2828，因此每次都需要对概率区间进行放大；把对把对L的移位操作提到了前面，因此旁路编码的重归一化的区间可以看作由的移位操作提到了前面，因此旁路编码的重归一化的区间可以看作由[0,2^{10})变成了变成了[0,2^{11}]$。 

这里写图片描述

　下面是旁路编码的一个例子 
这里写图片描述

4.6 编码结束 EncodeTerminate

　在编码语法元素end_of_slice_flag（ctxIdx = 276）以及I_PCM mb_type时会调用EncodeTerminate这个编码过程。在EncodeTerminate中，采用的是pStateIdx = 63的状态，这个状态表示的是当前宏块是否为该slice的最后一个宏块的概率。在该状态下，对概率区间的划分跟概率区间量化值无关。在编码end_of_slice_flag以及I_PCM的mb_type时，概率区间固定为RLPS=2RLPS=2。如果当前宏块为slice的最后一个宏块（end_of_slice_flag = 1）或者当前编码为PCM宏块并且编码它的mb_type I_PCM时，结束CABAC编码，调用EncodeTerminate中的EncodeFlush。具体情况请参考标准中的9.3.4.5小节。 

这里写图片描述

　在编码完成slice的最后一个宏块后，将会调用字节填充过程。该过程会往NAL单元写入0个或者更多个字节（cabac_zero_word），目的是完成对NAL单元的封装（标准9.3.4.6）。这里有计算如下 
这里写图片描述

　如果k>0k>0，则需要将3字节长的0x000003添加到NAL单元kk次。这里的前两字节0x0000代表了cabac_zero_word，第三个字节0x03代表一个emulation_prevention_three_byte。 
　如果k⩽0k⩽0，则无需添加字节到NAL单元。 
　式子中的各个变量所代表的意思请查看标准


【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/SoaringLee/p/10532499.html