521 Huffman编码 1.前缀码( Prefix code) 4层树形结构的编码情况 C I J K
5.2.1 Huffman编码 • 1．前缀码（Prefix Code） 4层树形结构的编码情况
2. Huffman编码 算法: ①将图像的灰度等级按概率大小进行升序排序 ②在灰度级集合中取两个最小概率相加,合成一个概率。 ③新合成的概率与其他的概率成员组成新的概率集合。 ④在新的概率集合中,仍然按照步骤②~③的规则,直至 新的概率集合中只有一个概率为的成员。这样的归并过程 可以用二叉树描述。 ⑤从根节点按前缀码的编码规则进行二进制编码
2．Huffman编码 算法： • ① 将图像的灰度等级按概率大小进行升序排序。 • ② 在灰度级集合中取两个最小概率相加，合成一个概率。 • ③ 新合成的概率与其他的概率成员组成新的概率集合。 • ④ 在新的概率集合中，仍然按照步骤②～③的规则，直至 新的概率集合中只有一个概率为1的成员。这样的归并过程 可以用二叉树描述。 • ⑤ 从根节点按前缀码的编码规则进行二进制编码
Huffman编码示意图 左图所示为建立码的过程 ·右图所示为从根开始,经各中间节点到叶节点的路径采用 二进制编码的情况 0 符号集经排序的第一次第二次第三次第四次第五次 概率分布介并应介开后介并后合并后合并后x 0.400.400.400.40r0.601r1.00 0.200.20r0.23r0.370.40 0.12r0.170.200.23 0.110.120.17 00901 0.08
Huffman编码示意图 • 左图所示为建立码的过程 • 右图所示为从根开始，经各中间节点到叶节点的路径采用 二进制编码的情况
編码过程举例 ·第1行和第2行列举了一个信源的统计特性 结果如第三行所示 符号集{x}x1 概率分布}0.400.200.20.1009008 Huffman编码10100000010110011
编码过程举例 • 第1行和第2行列举了一个信源的统计特性 • 结果如第三行所示 符号集{xi } x1 x2 x3 x4 x5 x6 概率分布{pi } 0.40 0.20 0.12 0.11 0.09 0.08 Huffman编码 1 010 000 001 0110 0111
3. Huffman编码的性能 优点: 实现 Huffman编码的基础是统计源数据集中各信号的概率分 布。 Huffman编码在无失真的编码方法中效率优于其他编码方法, 是一种最佳变长码,其平均码长接近于熵值。 缺点: 当信源数据成分复杂时,庞大的信源集致使 Huffman码表较 大,码表生成的计算量增加,编译码速度相应变慢 不等长编码致使硬件译码电路实现困难。上述原因致使 Huffman编码的实际应用受到限制
3．Huffman编码的性能 • 优点： – 实现Huffman编码的基础是统计源数据集中各信号的概率分 布。 – Huffman编码在无失真的编码方法中效率优于其他编码方法， 是一种最佳变长码，其平均码长接近于熵值。 • 缺点： – 当信源数据成分复杂时，庞大的信源集致使Huffman码表较 大，码表生成的计算量增加，编译码速度相应变慢 – 不等长编码致使硬件译码电路实现困难。上述原因致使 Huffman编码的实际应用受到限制