多媒体技术-图像与视频压缩(1).pptVIP

二、D进制哈夫曼编码 1. 编码步骤 同二进制，但需注意两点： ①每次取最小的D个概率,分别赋以0,1,…, D-1； ②信源符号个数r必须满足：r=(D-1)θ+D. 当r不满足时，在信源符号集中补充一些对应概率为0的符号. 哈夫曼（Huffman）码 2.例题 某离散无记忆信源符号集{a1,a2,a3,a4,a5,a6,a7,a8，a9}，已知所对应的概率，试对其进行四元编码！ 哈夫曼（Huffman）码 解： 其中D=4. 若取θ=2可得大于9但与9最接近 的正整数10，因此在编码时加入一个零概 率符号. 对其进行四元编码： 哈夫曼（Huffman）码 哈夫曼码考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩； 哈夫曼码的编码方法都不惟一； 哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，因此综合性较优. 哈夫曼（Huffman）码 Huffman码在具体实用时，设备较复杂.在编码器中需要增加缓冲寄存器，因为每个信源符号所对应的码符号长度不一，负责会造成输入和输出不能保持平衡. 优点：提高编码效率； 缺点：需要大量缓冲设备来存储这些变长码，然后再以恒定的码率进行传送；在传输的过程中如果出现了误码，容易引起错误扩散，所以要求有优质的信道。 哈夫曼（Huffman）码 哈夫曼码也是译码的工具： 哈夫曼（Huffman）码 0.60 01 0.09 0.13 0.19 0.23 0.37 1.0 01 01 01 01 01 01 0100 x5 0.07 0101 x6 0.06 00010 x7 0.05 00011 x8 0.04 011 x3 0.1 0000 x4 0.1 001 x2 0.18 1 x1 0.40 哈夫曼（Huffman）码 4.例题X:p(x)~(0.4,0.18,0.1,0.1,0.07, 0.06,0.05,0.04) 1 001 011 0101 0100 0000 00010 00011 哈夫曼（Huffman）码 4.例题 X:p(x)~(0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04) 若接收的字符串是： 00010100101100011 00010100101100011 00010100101100011 00010100101100011 统计编码 香农-费诺编码 哈夫曼编码 算术编码 算术编码 算法思想 Huffman编码中每个符号都用整数个bits来表示，影响编码效率。 若能把一串符号作为编码单位，则效率还可提高。 符号串的区间表示法 设符号串为： bacedbbdea 则它可以映射成为［0，1）中的唯一的一个子 区间。 0 0.2 0.5 0.6 0.8 1 a b c d e a b c d e a b c d e a b c d e 0.2 b 0.5 a 0.26 0.236 0.2 0.23 字符 a b c d e 概率 0.2 0.3 0.1 0.2 0.2 范围 [0,0.2) [0.2,0.5) [0.5,0.6) [0.6,0.8) [0.8,1.0) high为编码区间的高端,low为低端,range为区间长度, lowrange为字符分配区间的低端 highrange 为区间的高端。 初始化： high=1,low=0,range=high-low=1 一个字符编码后新的low和high为： Low=low+range* lowrange High=low+range* highrange 0 子区间 1 low highrange lowrange high 计算过程： 1）将 [0，1）区间按照概率的比例分配给五个字符，即（如图形表示）： a= [ 0，0.2]， b= [ 0.2，0.5], c= [ 0.5，0.6] d= [ 0.6，0.8] e= [ 0.8，1) high=1,low=0,range=high-low=1 2)输入第一个字符 b，得 b.high=0.5,b.low=0.2 b.range=b.high-b.low=0.3 3)将 [0.2，0.5）区间按照概率的比例分配给五个字符，如图形表示。 4)输入第二个字符 a，得 a.high=0.26,a.low=0.2 a.range=a.high-a.low=0.06 5)将 [0.2，0.26）区间按照概率的比例分配给五个字符，如图形表示。 6)输入第三个字符