cabac原理及其实现重点笔记.doc

Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC简称Cabac，H264中一种熵编码方式：基于上下文自适应二进制算术编码内容安排：1，简介算术编码 2，简介二进制算术编码 3简介Cabac及其某些实用实现方式（参照JSVM代码，也可以参照JM） -张新发一，算术编码算术编码是一种惯用变字长编码，它是运用信源概率分布特性、可以趋近熵极限编码办法。它与 Huffman 同样，也是对浮现概率大符号赋予短码，对概率小符号赋予长码。但它编码过程与 Huffman 编码却不相似，并且在信源概率分布比较均匀状况下其编码效率高于 Huffman 编码。它和 Huffman 编码最大区别在于它不是使用整数码。Huffman 码是用整数长度码字来编码最佳办法，而算法编码是一种并不局限于整数长度码字最佳编码办法。算术编码是把各符号浮现概率表达在单位概率 0，1 区间之中，区间宽度代表概率值大小。符号浮现概率越大相应于区间愈宽，可用较短码字表达；符号浮现概率越小相应于区间愈窄，需要较长码字表达。 举例如下： 以符号为例 在算术编码中普通采用二进制分数表达概率，每个符号所相应概率区间都是半开区间，即该区间涉及左端点，而不涉及右端点，如 S1相应 0，0.001)，S2 相应 0.001，0.01) 等。算术编码产生码字事实上是一种二进制数值指针，指向所编符号相应概率区间。n 符号序列 第一种符号 S3 用指向第 3 个子区间指针来代表，可以用这个区间内任意一种小数来表达这个指针，这里商定这个区间左端点代表这个指针，因而得到第一种码字.011。n 后续编码将在前面编码指向子区间内进行，将 .011，.111 区间再按概率大小划分为 4 份，第二个符号 S3 指向 .1001 (S3 区间左端），输出码字变为 .1001。n 然后，S3 相应子区间又被划分为 4 份，开始对第三个符号 S2 进行编码，. n 两个参量：编码点（指针所指处）C 和区间宽度 A。 初始状态 编码点（指针所指处）C = 0 区间宽度 A = 1.0 新编码点 C = 原编码点 C 原区间 APi 新区间 A = 原区间 Api 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 = .10011 A = .01.01 = .0001 第4个符号 (S4)： C = .10011 + .0001.111 = .1010011 （输出码字） A = .0001.001 = .0000001解码过程n 算法解码采用与编码过程相反环节 把接受到码字串指向其相应子区间，得到此子区间相应符号，即为解码后符号。 即从码字串中减去已解码符号子区间左端点数值（累积概率）， 并将差值除以该子区间宽度（概率值），得到新码字串。n 上述例子 当收到字码串 (.1010011) 时，其指向子区间 .011，.111，相应于 S3，因而，得到第 1 个符号为 S3。 新码字串：（.1010011 - .011) (.1) = 0.100011 ，新码字串依然指向子区间 .011，.111，因而，第 2 个符号仍为 S3。 其他符号依次类推二，二进制算术编码二进制算术编码输入字符只有两种，如果信源字符集内包具有各种字符，则先将这些字符通过一系列二进判决，变成二进制字符串。这两个符号构成序列编码与算术编码基本原理相似，仍是不断划分概率子区间递归过程。在两个输入字符中，浮现概率较大为 MPS (More Probable 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）例： 信源符号序列 11011111 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=A Qe = 0.110001 0.001 =0.4， 继续下去. 最后得C= 0.A= 0.此时区间尾为C+A=0.，编码区间C，C+A)编码输出可以是最后一种编码区间中任意小数值，但为了获得最佳编码效率，选取小数应有最短比特长度。上面区间咱们可取0.0101,即输出为0101解码过程按 Qe、Pe 提成两个子区间，判断被解码码字落在哪个区间，并赋予相应符号。设 c =（0.0101) b是被解码值，初始值 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.1110.111=0.110001 3，c = 0.000101 落在 0-QeA 之间，解码符号为 D = 0 c = c = 0.000101 A = AQe = 0.1100010.001 = 0. 三，CABAC原理及其实现CABAC是H264一种熵编码方案，相例如H264此外一种熵编码方案CAVLC而言，在可接受视频质量（30dB到38dB之间）内变化时，前者可节约平均9%到14%码流。CABAC有如下几种特性：1， 对多数符号使用了自适应概率模型。2， 通过使用上下文关系，运用了符号有关性。3， 限制为二进制算术编码（binary arithmetic coding），基于只用查表和移位方式迅速二进制算术编解码器。4， 399 种预定义上下文模型，提成了各种不同模型组，例如模型 14-20 用于帧间宏块类型编码，模型选取基于前面编码信息（上下文关系），每个上下文模型适应实验分布。先大体简介CABAC实现过程，然后对某些技术做细节简介下面是CABAC编码流程图按上图可知，对一种符号编码有如下过程：1，转化成二进制(Binarization)CABAC使用二值算术编码，也就是说只对二进制判决（0或者1）进行编码。非二进制符号（例如转换后系数或者运动矢量）在编码前先要进行二进制转换。这一过程和变长编码（VLC）中将信息符号转化为变长编码同样，所不同是，算术编码器在将信息送去传播之前还要进一步对这些二进制符号进行编码。 2，选取基于内容模型：“基于内容模型”是二进制符号中一种或各种比特概率模型。依照对先前已编码符号记录，从可选模型中选取恰当概率模型。3，算术编码：依照选取概率模型对每个比特进行算数编码。4，更新模型上图中bypass coding是指对于某些特定语法元素二进制比特符号，为了加快编码速度而不使用上下文模型形式。使用CABAC熵编码方式在时间耗费方面不不大于CAVLC，为了达到一种折中，在实际编码中，并不是对所有语法元素都使用CABAC编码方案，有许多表征视频序列自身固有参数特性语法元素熵编码还是使用CAVLC。下图是某些需要用CABAC编码语法元素及相应上下文模型索引。下面来详细简介编码过程1，二进制化为了减少算术编码复杂度，提高编码速度，采用二进制算术编码，即进行熵编码符号是一系列二进制符号，这得一方面需要把编码语法元素转化成二进制串，涉及基本方案和串接方案。Unary Binarization：对于x=0无符号整数值，由x个”1”和一种终结符合”0”构成。Truncated Unary Binarization（TU）：给定一种参数S,对于编码符号x，0=xS,则取x=S，对于x=(1k) put(1) x=x-(1k)&0x01) break 前缀是由相应值为Unary Binarization方案产生二进制串构成，后缀由这个十进制值相应二进制串构成。Fixed-Length(FL)Binarization：给定一种参数S，对于编码语法元素x，必要满足0=x9时，后缀是x=|mvd|-9EG3方案输出二进制串，mvd符号为正时用”1”表征，为负时用”0”表征，当0|mvd|C所定义。对每一种即将要编码符号x，可以运用它已经编码相邻符号 概率模型来预计一种条件概率p(x|F(z)，在CABAC中，符号是二进制形式，并且通过选取少数上下文C使得算法变得更为简朴。CABAC中有四种上下文模型设计方式：第1种类型模型必要依照它相邻已编码语法元素构成，普通是其左边和上边相应语法元素来建立相应概率模型，对当前语法元素进行模型预测。第2种模型仅局限于对宏块类型和子宏块类型应用，其中第n比特概率模型选定要参照前面已编码n-1比特所采用模型。第3种和第4种模型仅用于残存数据编码，这两种模型都依赖编码块类型，其中第3种模型依赖不是已编码系数，而是系数在扫描途径中位置。第4种模型则要计算该比特所在系数之前已编码系数数目。在CABAC中除了这些条件上下文模型之外，尚有某些固定概率模型，它们对待编码比特提供固定概率预测，已编码比特模型不加以应用。 每个概率模型都相应一种索引，每个概率模型由两个值决定：一种6比特概率状态索引，以及一种1比特MPS符号。 从0到72索引值与宏块类型，子宏块类型，空域和时域预测模式，以及基于宏块和slice控制信息语法元素关于，在这种状况下上下文索引值通过下式来计算 从73到398模型索引通过下式来计算其中表达各种语法元素相应得模型索引偏移量，也就是前文给出那个索引表里所定义某些下限值，例如，对于mb_qp_delta而言，这个值就是60。在实际程序设计时，咱们可以不用考虑设计这个值，而是将不同类型语法元素单独设计一套模型索引值，即此时这个偏移量对于不同模型类型都为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_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个模型，其索引是从60到63，在设计时候，由于咱们单独设计了这个模型类型，因而其索引是从0到4，相应这四种模型咱们定义一种数组static const Short INIT_DELTA_QP_I1142= /- model 0 - 0， 41 ， 0， 63 ， 0， 63 ， 0， 63 , ；依照这个数组来初始化这四个模型，注意这个数组里0,41等数据对是依照一系列训练序列得到，它并不是咱们前面提及表征一种模型数据对，咱们将这个数组里数据对记为,初始化就是由得到每个模型初始，转化原则如下这里还要注意是这个参数，它表征是二进制符号概率，在CABAC中，符号概率由LPS64个量化概率值表征， ，这个值范畴由下面这个式子得到从上面简介咱们可以看出，在预测当前符号概率模型时，最重要是依照前面简介四种上下文模型设计方式来预测当前概率模型，即重要是求出这个值，得到后，当前符号模型索引拟定，依照这个索引值，再已经初始化或已经更新了模型系列中找到当前符号预测概率模型，在这个模型里得到概率状态和MPS，即，对，运用这两个值进行算数编码，这在背面简介算术编码时再详细简介。下面咱们简介不同语法元素求取办法，（注意：每个模型都是针对一种二进制化后二进制符来说，而不是针对语法元素自身值，但有语法元素值直接可以用一种二进制符来表征）这里体现了上下文思想：A 宏块类型，预测模式，控制信息等语法元素1） 宏块和子宏块类型包括语法元素有，mb_skip_flag，mb_type，sub_mb_type(仅讨论SP/P Slice) mb_skip_flag：相邻宏块编码特性被用来设计当前宏块概率模型，对于一种给定当前宏块C，设其左边宏块为A，上边宏块为B，则A和Bmb_skip_flag值被用来设计当前宏块mb_skip_flag相应二进制字符上下文模型，详细是用她们值来求，如下所示如果A或B不可得，则将不可得那个宏块mb_skip_flag设为0。Mb_type和sub_mb_type：概率模型是固定，与已编码宏块或子宏块无关，即对于一定mb_type或sub_mb_type，有拟定值与它相相应。2） 预测模式Luma4x4Intra预测模式：有两个句法元素，prev_intra4x4_pred_mode_flag和rem_intra4x4_pred_mode_flag，由前面表可以看到，这两个语法元素相应概率模型序号为68和69，即在程序设计时，可以把分别设计为0和1。在JSVM中，由m_cIntraPredCCModel这个模型类型表征。Chroma中Intra预测模式：chroma_pred_flag，这个语法元素值通过TU方式二进制化之后有3个字符，其中第一种二进制字符概率模型由下式决定：其中C表达当前色度块，A表达左边色度块，B表达上边色度块，ChPredInDCMode表达某个色度块预测方式与否是DC Mode （用0表达），有上面表达式可以看出，第一种二进制字符概率模型有3种。在CABAC中，第一种二进制字符之后两个二进制符采用固定概率模型，故这种类型概率模型共有4种，JSVM中用m_cChromaPredCCModel成员类来表征这种类型概率模型，这个成员类里有一种长度为4一维概率模型变量。参照图象索引：ref_idx，也是对这个语法元素值所相应第一种二进制字符进行概率模型预测，是用上下文思想，其后字符采用固定模型。RefIdxZeroFlag表达某个分割块其参照帧索引与否为0。MVd：对于某个分割，用mvd(X,cmp)来表达其mvd，cmp是mvd横纵座标值，即horizontal，vertical，则mvd相应第一种二进制字符概率模型由下式决定：前面简介过,mvd二进制化是用是S=9UEG3方式，在编码余下二进制字符时，使用如下方案，前缀中剩余8个字符使用此外四个固定模型，后缀中字符使用bypass编码方式，即不使用概率模型。3）控制信息：mb_qp_delta，end_of_slice_flag，mb_field_decoding_flag第三个我很少用到，只简介前两个mb_qp_delta：在二进制化这个语法元素值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 非零系数编码上下文模型选取基于已编码非零系数数目（注意编码顺序是反扫描顺序）2）编码流程：一方面，一种1比特参数coded_block_flag被传送。如果coded_block_flag为0，则这个块将不会传送任何其她信息，否则，一种标示非零系数位置significance map将会被编码。最后，各个非零系数绝对值及其符号被编码，注意这些符合以反扫描顺序被传送。下图是一种编码过程图Coded Block Pattern:对于除了Intra16x16nonskip模式宏块，coded_block_pattern标示了6个8x8块，其中4个Luma块，2个Chroma块，这个参数二进制化采用方案是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_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种类型，每种类型都采用4种概率模型，获取方式如下式： A表达当前块左边块，B表达当前块上边块 这里有几种问题需要注意： 上面这个式子只合用上表中所标示同类型块，若相邻块不是同类型块，例如当前块属于Intra16x16，而相邻块X是以Inter方式编码，那么这时候coded_block_flag(X)取值0；如果当前块相邻块不属于当前块Slice（固然，这也包括相邻块不存在状况），这时候coded_block_flag(X)取缺省值，这个缺省值有两种取法，当前块是Intra型时，这个缺省值取1，否则取0。由此可见，对于coded block flag总共有5x4=20种概率模型供选取。Significance 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)表达已编码完绝对值不不大于1系数个数，i表达当前系数扫描位置，而编码顺序是反扫描顺序，这意味着这两个值随着i减小而增大，则coeff_abs_level_minus1第一种字符概率模型由当前NumT1决定，但如果NumT1值不不大于3了，则编码剩余系数时所选用 值总是3。如果NumLgt10，则背面系数选用总为4。对于bin_index0状况（1=bin_index=13）,如果有NumLgt10，则为5+min(4,NumLgt1(i)；下表给出了个例子：注意上面这个表编码顺序是从i=9到i=1。对于UEG0后缀某些及非零系数符号信息编码都采用bypass coding。C 二进制编码由上面所述可以得到当前字符概率模型，也就是得到了当前模型中LPS索引以及MPS字符，再结合上一次编码所提供IntervalRange值R，下一步就是要对当前字符进行二进制编码，这里二进制编码和第二某些所讲就大体相似了，过程如下：随着一种即将编码字符到来，原有Interval将会被分割成两个subInterval，一种Interval宽度为，这与LPS有关，此外一种是，这与MPS有关，是与得到概率模型中LPS索引相应，依照当前字符是MPS还是LPS划分出一种新Interval，这就与第二某些所述二进制算术编码完全一致了。为了简化计算以及减少乘法运算带来复杂度，CABAC中做了如下解决：将R值限定在18到16)&3，这样上面乘法运算成果就合成到一种TabRangeLPS644数组中，就这样得到概率模型后，二进制编码可用下图流程来阐明：writeSymbol( UInt uiSymbol，CabacContextModel& rcCCModel );传递一种即将编码字符以及其相应ModelUInt uiLow = m_uiLow;UInt uiRange = m_uiRange;UInt uiLPS = g_aucLPSTable64x4rcCCModel.getState()(uiRange6) & 3； /compute the Interval of LPS,thats 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.getState() ); else rcCCModel.setState( g_aucACNextStateMPS64rcCCModel.getState() ); while( uiRange = HALF ) RNOK( xWriteBitAndBitsToFollow( 1 ) ); uiLow -= HALF; else if( uiLow QUARTER ) RNOK( xWriteBitAndBitsToFollow( 0 ) ); else m_uiBitsToFollow+; uiLow -= QUARTER; uiLow = 1; uiRange = 1; m_uiLow = uiLow; m_uiRange = uiRange; return Err:m_nOK;以上就是用C+实现编码过程。上面有个函数是setState( UChar ucState )即编完当前字符后对概率更新过程。toggleMps（）是重新设立MPS。D 概率模型更新上面是LPS概率状态转移图，概率状态转移遵循如下原则为了减少乘法运算带来复杂度，将概率转移转化为概率索引转移，又将转移用两个数组表达出来const UChar g_aucACNextStateMPS6464 =1，2，3，4，5，6，7，8，9,10,11,12,13,14,15,16,17,18,19,20, 21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,62,63; const UChar g_aucACNextStateLPS6464 = 0，0，1，2，2，4，4，5，6，7,8，9，9,11,11,12,13,13,15,15, 16,16,18,18,19,19,21,21,22,22,23,24,24,25,26,26,27,27,28,29, 29,30,30,30,31,32,32,33,33,33,34,34,35,35,35,36,36,36,37,37,37,38,38,63; 由数组可看出，当前字符为MPL时，LPS状态索引只是简朴地加1，但当前字符为LPS时候，变化就复杂多了。需要注意是，当在=62处，在这里LPS概率到达最小，或者说MPS最大概率到达，如果这时候即将编码依然是一种MPS，则概率索引值62将不会变化，除非有一种LPS浮现，这时候按照LPS状态转移规则进行转移，咱们可以看到，这时候状态63事实上是没有用到。当在=0时候，当前即将编码符号依然是LPS，则状态索引不变，但模型MPS值将要变化，这就导致了随后LPS与MPS定义互换，这就是函数toggleMps（）作用。