7.5算术编码 算术编码( Arithmetic Coding)的概念最早由 J. Rissanen在1976年引入,与 Huffman编码不同,算术编 码是一种有记忆非分组编码方法,它用某个实数区间来表 示若干被编码的信息,用该实数区间对应的二进制码作为 编码输出。算术码的编码过程,实际上就是依据字符的发 生概率对码区间的分割过程,我们举例说明算术编码的原 理 设信源符号集为{a,b,c,d},其概率分布为 0.2,0.2,0.4,0.2}。 1)若对该信源进行 Huffman编码,可得其平均码长 为L=2.0bit/字符。 (2)若信源发出序列{b,c,a,b,d},算术编码过程如 下 2021年2月20日 数字图象处理演示稿纪玉波制作
2021年2月20日 数字图象处理演示稿 纪玉波制作 (C) 1 7.5算术编码 算术编码 (Arithmetic Coding) 的 概 念 最 早 由 J.Rissanen在1976年引入，与Huffman编码不同，算术编 码是一种有记忆非分组编码方法，它用某个实数区间来表 示若干被编码的信息，用该实数区间对应的二进制码作为 编码输出。算术码的编码过程，实际上就是依据字符的发 生概率对码区间的分割过程，我们举例说明算术编码的原 理。 设 信 源 符 号 集 为 {a,b,c,d}, 其 概 率 分 布 为 {0.2,0.2,0.4,0.2}。 （1）若对该信源进行Huffman编码，可得其平均码长 为L=2.0bit/字符。 （2）若信源发出序列{b,c,a,b,d}，算术编码过程如 下：
各数据符号在半封闭实数区间[0,1)内按概率进行赋值范 围设定为 a=[0.0,0.2),b=[0.2,0.4),C=[0.4,0.8),d=[0.8,1.0) 第一个信源符号为“b〃,取值区间变为[0.2,0.4)。 第二个信源符号“c〃,对取值区间[0.2,0.4)进行划分找 出对应于“c〃的区间,计算新的取值区间范围。 起始值=取值区间左端 +取值区间长度×当前符号的赋值区间左端 结束值=取值区间左端 取值区间长度×当前符号的赋值区间右端 计算得出新的取值区间为 0.2+0.2×0.4,0.2+0.2×0.8)=[0.28,0.36) 依次类推,第三个符符号“a",编码后的取值区间为 [0.28,0.296)。最终划分结果见下表 2021年2月20日 数字图象处理演示稿纪玉波制作
2021年2月20日 数字图象处理演示稿 纪玉波制作 (C) 2 各数据符号在半封闭实数区间［0,1)内按概率进行赋值范 围设定为 a=[0.0,0.2),b=[0.2,0.4),c=[0.4,0.8),d=[0.8,1.0) 第一个信源符号为“b” ，取值区间变为[0.2,0.4)。 第二个信源符号“ c” ，对取值区间[0.2,0.4)进行划分找 出对应于“ c”的区间，计算新的取值区间范围。 起始值=取值区间左端 +取值区间长度×当前符号的赋值区间左端 结束值=取值区间左端 +取值区间长度×当前符号的赋值区间右端 计算得出新的取值区间为 [0.2+0.2×0.4,0.2+0.2×0.8)= [0.28,0.36) 依次类推，第三个符符号“ a” ，编码后的取值区间为 [0.28,0.296)。最终划分结果见下表
码区间划分结果 数据流 编码区间 区间长度 [0.2,0.4) 0.2 bcabd [0.28,0.36) 0.08 [0.28,0.296) 0.016 [0.2832,0.2864) 0.0032 [0.28576,0.2864) 0.00064 2021年2月20日 数字图象处理演示稿纪玉波制作
2021 年 2 月20 日 数字图象处理演示稿 纪玉波制作 (C) 3
至此,信源序列{ bcabd}已被映射为一个实数区间 [0.28576,0.2864),或者说在[0.28576,0.2864)内 的任何一个实数均代表该序列。 例子 消息“ BILL GATES〃会有一个如下的概率分布 字符概率 空格1/10 A1/10 B1/10 E1/10 G1/10 I1/10 L2/10 1/10 T1/10 2021年2月20日 数字图象处理演示稿纪玉波制作
2021年2月20日 数字图象处理演示稿 纪玉波制作 (C) 4 至此，信源序列{bcabd}已被映射为一个实数区间 [0.28576,0.2864)，或者说在[0.28576,0.2864)内 的任何一个实数均代表该序列。 例子 消息“BILL GATES”会有一个如下的概率分布： 字符 概率 空格 1/10 A 1/10 B 1/10 E 1/10 G 1/10 I 1/10 L 2/10 S 1/10 T 1/10
用到的九个字符的符号集给出数值范围如下: 字符 概率 范围 空格 1/10 0.00≤r<0.10 1/100.10≤r<0.20 ABEGIL 1/100.20≤r<0.30 1/10 0.30≤r<0.40 1/10 0.40≤r<0.50 1/10 0.50≤r<0.60 2/10 0.60≤r<0.80 1/100.80≤r<0.90 1/10 0.90≤r<1.00 2021年2月20日 数字图象处理演示稿纪玉波制作
2021年2月20日 数字图象处理演示稿 纪玉波制作 (C) 5 用到的九个字符的符号集给出数值范围如下： 字符 概率 范围 空格 1/10 0.00≤r＜0.10 A 1/10 0.10≤r＜0.20 B 1/10 0.20≤r＜0.30 E 1/10 0.30≤r＜0.40 G 1/10 0.40≤r＜0.50 I 1/10 0.50≤r＜0.60 L 2/10 0.60≤r＜0.80 S 1/10 0.80≤r＜0.90 T 1/10 0.90≤r＜1.00
每个字符都赋值成0到1范围内与之出现概率相关 联的那部分。 算术编码的消息的最高有效部分属于第一个符号 或者说在消息“ BILL GATES”中的B。为了正确地 译码第一个字符,最终编码后的消息必须是一个大于 等于0.20并且小于0.30的数值。要编码成这个数值, 寻找它可能在的范围,在编码第一个字符后,这个范 围的底限是0.20,并且高限是0.30。编码过程的剩余 部分中,每个新符号将进一步限制输出数值的可能范 围,下一个将要编码的字符,字母I,拥有新的子范围 0.2到0.3中的范围0.50到060。使用上面的计算公式, 执行这个过程而产生的结论如下: 2021年2月20日 数字图象处理演示稿纪玉波制作
2021年2月20日 数字图象处理演示稿 纪玉波制作 (C) 6 每个字符都赋值成0到1范围内与之出现概率相关 联的那部分。 算术编码的消息的最高有效部分属于第一个符号 一或者说在消息“BILL GATES”中的B。为了正确地 译码第一个字符，最终编码后的消息必须是一个大于 等于0.20并且小于0.30的数值。要编码成这个数值， 寻找它可能在的范围，在编码第一个字符后，这个范 围的底限是0.20，并且高限是0.30。编码过程的剩余 部分中，每个新符号将进一步限制输出数值的可能范 围，下一个将要编码的字符，字母I，拥有新的子范围 0.2到0.3中的范围0.50到0.60。使用上面的计算公式， 执行这个过程而产生的结论如下：
新字符 低值 高值 0.0 1.0 0.20 0.30 0.25 0.26 0.256 0.258 0.2572 0.2576 空格 0.25720 0.25724 0.257216 0.257220 GATE 0.2572164 0.2572168 0.25721676 0.2572168 0.257216772 0.257216776 0.2572167752 0.2572167756 2021年2月20日 数字图象处理演示稿纪玉波制作
2021年2月20日 数字图象处理演示稿 纪玉波制作 (C) 7 新字符 低值 高值 0.0 1.0 B 0.20 0.30 I 0.25 0.26 L 0.256 0.258 L 0.2572 0.2576 空格 0.25720 0.25724 G 0.257216 0.257220 A O.2572164 0.2572168 T O.25721676 0.2572168 E O.257216772 0.257216776 S 0.2572167752 0.2572167756
这样,最终的低值2572167752将用于唯一地编码 消息“ BILL GATES〃。在译码过程中,通过查看哪 个符号拥有编码的消息所在的空间,就可以找到消息 中的第一个符号,由于0.2572167752在2到3之间,所 以第一个字符必须是B,之后,从要编码的数值中删 掉B,因为我们知道,B范围的上下限,所以通过把它 放入过程的逆过程可以消除它的影响。首先减去B的 低值,得到0572167752;之后除以B范围的宽度,即 0.1,得到值0.572167752;再后,计算下一个字母的 范围,字母Ⅰ,依此类推,可以译出其他字符 2021年2月20日 数字图象处理演示稿纪玉波制作
2021年2月20日 数字图象处理演示稿 纪玉波制作 (C) 8 这样，最终的低值2572167752将用于唯一地编码 消息“BILL GATES” 。在译码过程中，通过查看哪一 个符号拥有编码的消息所在的空间，就可以找到消息 中的第一个符号，由于0.2572167752在2到3之间，所 以第一个字符必须是B，之后，从要编码的数值中删 掉B，因为我们知道，B范围的上下限，所以通过把它 放入过程的逆过程可以消除它的影响。首先减去B的 低值，得到0572167752；之后除以B范围的宽度，即 0.1，得到值0.572167752；再后，计算下一个字母的 范围，字母I，依此类推，可以译出其他字符
BILL GATES"消息的译码进行情况如下: 编码了的数输出符号 低限 高限 范围 0.2572167752 0. 0.572167752 0. 0.6 0.1 0.72167752 0.6083876 0.041938 0.41938 0.1938 0.938 BILLEGATES 0.6 0.8 0.2 0.6 0.8 0.2 格 0.0 0.1 0.1 0.4 0.5 0.1 0. 0.2 0. 0.9 0. 0.38 0.3 0.4 0.1 0.8 0.8 0. 0.0 2021年2月20日 数字图象处理演示稿纪玉波制作
2021年2月20日 数字图象处理演示稿 纪玉波制作 (C) 9 “BILL GATES”消息的译码进行情况如下： 编码了的数 输出符号 低限 高限 范围 O.2572167752 B 0.2 0.3 0.1 0.572167752 I 0.5 0.6 0.1 0.72167752 L 0.6 0.8 0.2 0.6083876 L 0.6 0.8 0.2 0.041938 空格 O.O O.1 0.1 0.41938 G 0.4 0.5 0.1 0.1938 A O.1 0.2 0.1 0.938 T 0.9 1.0 0.1 0.38 E O.3 0.4 0.1 O.8 S 0.8 0.9 0.1 0.O
总之,编码过程只是用每个新符号来缩小可能数值的 范围。新范围是与相应于该符号的预定义的概率成正比的。 译码是反过程,范围扩展是与每个被抽取的符号的概率成 正比的 算术编码的最大优点之一在于它具有自适应性和高编 码效率,当信源符号概率比较接近时,使用算术编码效果 较好,因为此时霍夫曼编码的结果趋于定长码,效率不高。 事实上,JPEG小组测试过,对于许多实际图像,算术编码 的压缩效果优于霍夫曼编码5%~10%。在JPEG的扩展系统 中,已经用算术编码取代霍夫曼编码。但在实际上,算术 编码要比霍夫曼编码复杂,特别是硬件实现。 2021年2月20日 数字图象处理演示稿纪玉波制作
2021年2月20日 数字图象处理演示稿 纪玉波制作 (C) 10 总之，编码过程只是用每个新符号来缩小可能数值的 范围。新范围是与相应于该符号的预定义的概率成正比的。 译码是反过程，范围扩展是与每个被抽取的符号的概率成 正比的。 算术编码的最大优点之一在于它具有自适应性和高编 码效率，当信源符号概率比较接近时，使用算术编码效果 较好，因为此时霍夫曼编码的结果趋于定长码，效率不高。 事实上，JPEG小组测试过，对于许多实际图像，算术编码 的压缩效果优于霍夫曼编码5%～10%。在JPEG的扩展系统 中，已经用算术编码取代霍夫曼编码。但在实际上，算术 编码要比霍夫曼编码复杂，特别是硬件实现