算术编码 算术编码：采用0到1区间上一个浮点数来代替一串输入符号。本质是为整个输入流分配一个码字，而不是给输入流中的每个字符分别指定码字。

Presentation on theme: "算术编码 算术编码：采用0到1区间上一个浮点数来代替一串输入符号。本质是为整个输入流分配一个码字，而不是给输入流中的每个字符分别指定码字。"— Presentation transcript:

1 算术编码 算术编码：采用0到1区间上一个浮点数来代替一串输入符号。本质是为整个输入流分配一个码字，而不是给输入流中的每个字符分别指定码字。
原理：根据符号概率，区间递进。从第一个符号确定的初始区间（0，1）开始，逐个字符地读入输入流，在每一个新的字符出现后递归地划分当前区间。划分地根据是各个字符地概率，将当前区间按照各个字符地概率划分成若干子区间，将当前字符对应的子区间取出，作为处理下一个字符时的当前区间。处理完最后一个字符后，得到最终区间，在最终区间中任意挑选一个数作为输出。 算法流程：在二进制编码中，只有0和1两个字符。

2 Binval=0? yes no L=L; R=R*P0 L=L+R*P0; R=R*P1 当前字符结束 L：当前区间的下限 R：当前区间的大小 binval：当前字符 Px：各个字符的概率

3 举例： 概率范围图： 设输入序列为abaca： (1)初始范围： (2)当第一个字符a被传送时，范围： 0.5 0.75 1 c a b 1

4 (3) 当第二个字符b被传送时，范围： 对a编码后，编码范围[0,1)变为[0,0.5)
由概率表，b概率范围[0.50,0.75),H=0.75,L=0.50 L2=L1+R1*L=0.25 H2=L1+R1*H=0.375 R2=H2-L2 对ab编码后，编码范围[0,0.5)变为[0.25,0.375) R1 0.5 L1 H1 R2 0.25 0.375 L2 H2

5 依次类推： 解码过程如下：根据各符号出现的概率范围图 （4）对aba编码后，编码范围为[0.25，0.3125)
（5）对abac编码后，编码范围为[ ，0.3125) （6）对abaca编码后，编码范围为[ ， ) 最后输出的码字为： 。即用浮点数 代替abaca 解码过程如下：根据各符号出现的概率范围图 （1）接收到浮点数 ，在概率范围图内查得第一个字符为a，其概率0.5 （2）从接收值减去a在概率范围图中的L，并除以P(a),得： （ －0.00）/0.5＝ 该值为下一字符概率范围内的值。 （3） 在概率范围图[0.50,0.75）之间，所以为b 减去b在概率范围中的L，并除以P(b),得： （ －0.50）/0.25＝0.4375 依此类推，解码得到序列abaca

6 基于上下文的自适应二进制算术编码（CABAC）
熵编码的效率取决于概率模型的准确性。 CABAC特点：1.依据元素的上下文，对每个符号选择概率模型。2. 采用基于局部统计的概率估算。3.使用算术编码 。 自适应：在实际过程中，输入流中字符的概率分布是动态改变的，这需要维护一个概率表去记录概率变化的信息。作递进计算时，通过概率表中的值估计当前字符的概率，当前字符处理后，需要重新刷新概率表。编码器和解码器按同样的方法估计和刷新概率表，保证顺利解码。 具体采用如下步骤来编码数据符号： 1.二进制化：四种方法:U,TU,UEGK和FL。根据相应的码表，进行二进制化。 2.选择上下文模型：上下文模型是一种对二制化符号的一或多位的概率模型，依据最近编码数据符号的统计，从现有的模型中选择一种模型。上下文模型通过统计1或0来记忆每个位的概率。 3.算术编码 4.修改概率：依据实际编码的值修改已确定的上下文模型。

7

8 CABAC的上下文模型 H.264将一个片内可能出现的数据划分为399个上下文模型，每个模型以ctxIdx标识，在每个模型内部进行概率的查找和更新。H.264共要建399个概率表，每个上下文模型都独立地使用对应地表维护概率状态。 解码器对于输入地每一个比特首先要做的工作是查找它属于哪个上下文模型，然后查找该上下文模型所对应地 概率表以递进区间。查找某个比特所对应的上下文模型一般有以下两个步骤： (1)确定该比特的句法元素， H.264对每个句法元素都分配了一个上下文模型的区间，该句法元素中的每个比特的上下文模型的ctxIdx都在这一区间内。 (2)按照某个法则为当前比特在步骤（1）中得到的区间中找到对应的ctxIdx。

9 自适应算术算法的计算复杂度及优化 算术编码的计算复杂度主要体现在两个方面： 概率的估计，更新； 划分子区间时的乘法运算：R＝R*P(x)
(1)概率模型 只要保证编码和解码双方在划分当前区间时能得到同样的P(x)，也就是通过同样的法则估计和更新P(x)，就能顺利解码。 CABAC建立了一个基于查表的概率模型：将0－0.5范围内的概率量化为64个值，这些概率对应于LPS字符，则MPS字符的概率为1-P(lps).概率的刷新按照某种法则在表中查找。 (2)乘法优化 CABAC首先建立一个4×64的二维表格，用于存储预先计算好的乘法结果。表格的入口参数一个来自P(x),另一个来自R。 P(x)可以直接以 σ作为参数；R的量化方法：ρ=(R>>6)&3. 每次在需要做乘法运算时，携带ρ和σ进行查表操作就得到结果。

10 结论 CABAC中内建了由大量实验统计而得到的概率模型。在编码过程中，CABAC根据当前所要编码的内容以及先前已编码好的内容，动态地选择概率模型来进行编码，并实时更新相对应地概率模型。并且，CABAC在计算量和编码速度上进行了优化，用了量化查表，移位，逻辑运算等方法代替复杂的概率估计和乘法运算。在实际应用中,CABAC与其他主流的熵编码方式相比有更高的编码效率。

11 图中，蓝色部分是概率的刷新部分。表TabRangeLPS存储预先计算好的乘法结果，表TransIdxLPS是与CABAC概率估计和刷新模型对应的概率表。

12 图2的理解 条件：首先估计出MPS字符 查表得Rlps，并使R1＝R-Rlps 判断当前字符是否为MPS
不是：L1＝L＋ R-Rlps 且R1＝Rlps 是： L1＝L且R1＝R-Rlps 1－Plps 1 MPS LPS L R Rlps

13 码流输出 在实际过程中，编码器并不是等递进到最终区间才输出码字的，这里有两个方面的原因，一个是在编码器在递过运算过程中，如果没有输出，信道会出现空闲，形成浪费，二是输入流较长时，最终区间非常小，必须以极高的精度来记录L和R，幸运的是，在二进制编码中，区间的上下限以二进制形式表示，每当下限的最高有效位与上限的最高有效位一样时，就可以移出这个比特。　这样的方法可以保证编码器在递进的同时不断的输出码流。序列出现的可能性越大，区间就越长，确定该区间所需要的比特数就越少。

14 实际上，编码过程中所有变量的值都不超过1，编码器中只保存小数点后的数字仍然可以正确编码，这样我们就可以用整数运算来完成上述算法。
更进一步我们可以看到，在编码过程中随着概率区间的不断减小，上限和下限会越来越接近，一旦两者的最高有效位的值相等，这一位上的数值就不再改变。这时我们就可以将该有效位输出，同时将上限和下限左移一位，并将上限的最低有效位置9，下限的最低有效位置0，这个过程称为归一化，实际上是将编码器中序列的概率区间放大以保证编码器的精度。然后对下一符号编码，直至序列结束。经过上述改进，算术编码就可以在实际中应用了。

15 但是，新的问题又出现了。在使用上述算法进行编码时，可能会遇到这样的情况：假设上、下限用6 位数表示，上限值为500004，下限值为499997，由于最高位不相等不能输出，而序列对应的区间却已经非常小了，继续编码，可能会出现上限值为500000，下限值为499999，这时无论再输入什么符号，上、下限都不再改变，因此编码器也不会有任何输出，这种情况就称为编码器下溢。我们假设上限值为500004，下限值为 来说明解决下溢的方法。每次循环中对上、下限的次高有效位进行检查， 如果（1）上限的次高有效位为0，（2）下限的次高有效位为9，这就表示编码器存在下溢的可能，这时将上、下限的次高有效位都去掉，并将剩余有效位都左移一位，上限的最低有效位移进一个9，下限的最低有效位移进一个0，继续对上、下限的次高有效位进行检查。

16 如果（1）（2）两个条件仍然满足，继续上述操作，否则记下从次高有效位移出比特数m，例子中m=4，经过多次循环，上、下限的值分别等于 和470000，继续下一符号的编码直至有数字输出,显然编码器输出的下一个数字是4 和5 中的一个。假设输出4，编码器接着要再输出m 个9，将m 置0 后，继续对下一符号编码；相反地如果输出5，就接着输出m 个0。这个方法的实质是在编码器没有输出情况下，扩大编码区间长度以保证编码器的精度

17 初始化 CABAC的生命期是片，每个片开始，要对399种上下文模型全部过行初始化工作，初始化的步骤是： 1， 将过区间复位到[0,1]
1， 将过区间复位到[0,1] 2， 为每一个上下文模型指定一个初始w 和σ (a) h.264 为每个上下文模型定义了初始常量m,n,通过查表可得上下文模型相对应的m,n (b) 按照如下算法计算w， σ. preCtxState = Clip3( 1, 126, ( ( m * SliceQPY ) >> 4 ) + n ) if( preCtxState <= 63 ) { pStateIdx = 63 - preCtxState valMPS = 0 } else { pStateIdx = preCtxState - 64 valMPS = 1 其中clip3(a, b ,c )表示将c 的值限制在［a ,b］之间。