现代图像分析知识点 (33).pdf

《现代图像分析知识点 (33).pdf》由会员分享，可在线阅读，更多相关《现代图像分析知识点 (33).pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Modern Image Analysis6.4 霍夫曼编码霍夫曼编码是霍夫曼在1952年根据可变长最佳编码定理，提出的依据信源集中各信号出现的概率分配不同长度的即时码。戴维霍夫曼1925年出生于美国俄亥俄州霍夫曼是加利福尼亚大学计算机科学系的创始人和终身教授霍夫曼编码方案是他在麻省理工学院攻读博士学位期间的一篇学期报告中提出的。Modern Image Analysis6.4 霍夫曼编码假设接收到这样一组信号1 0 0 1 0 1 0 0 1对于定长码：（码长为3）1 0 0 1 0 1 0 0 1对于变长码则无法进行码字解析Modern Image Analysis6.4 霍夫曼编码即时码

2、必须是唯一可译码，对一组即时码来说，其中的任意一个码字都只能与一种信号存在对应关系，而且任意一个码字都不能是其他码字的前缀。10100100010000都是即时码即时码的产生常采用树型结构00001111Modern Image Analysis6.4 霍夫曼编码假设接收到这样一组信号1 0 0 1 0 1 0 0 1对于上述即时码，则可以唯一解析出以下4个码字：1 0 0 1 0 1 0 0 1Modern Image Analysis6.4 霍夫曼编码霍 夫 曼 编 码 的 过 程设有一图像序列，含有8个灰度级，其概率分别为p1 p2 p3 p4 p5 p6 p7 p8 0.4 0.18

3、0.10 0.10 0.07 0.06 0.05 0.04 18,.,xxModern Image Analysis6.4 霍夫曼编码0.400.400.180.180.100.100.100.100.070.070.060.061x2x3x4x5x6x7x8x0.050.050.040.040.400.400.180.180.100.100.100.100.090.090.070.070.060.060.400.400.180.180.130.130.100.100.100.100.090.090.400.400.190.190.180.180.130.130.100.100.400.400

4、.230.230.400.400.190.190.180.180.370.370.230.230.600.600.400.40Modern Image Analysis6.4 霍夫曼编码000000011111115x6x7x8x4x2x3x1x1x2x3x4x5x6x7x8x10010100000011001110001000011000000111111得到霍夫曼编码为：Modern Image Analysis6.4 霍夫曼编码霍夫曼编码的步骤将灰度等级按概率从大到小进行排序。取两个最小概率相加，作为一个新的概率集合，重新排序。重复此步骤，直到只有两个概率为止。同时构成霍夫曼树。根据霍夫

5、曼树，得到霍夫曼编码。Modern Image Analysis6.4 霍夫曼编码 灰 度 级 x1 x2 x3 x4 x5 x6 x7 x8 概 率ip 0.4 0.18 0.10 0.10 0.07 0.06 0.05 0.04 霍夫曼码 1 001 010 0000 0110 0111 00010 00011 码 长ip 1 3 3 4 4 4 5 5 1 12 23 34 45 56 67 78 8 0.4 1 0.18 3 0.10 3 0.10 4 0.07 40.06 4 0.05 5 0.04 52.61pppppppp 平 均 码 长 度Modern Image Analys

6、is6.4 霍夫曼编码222222220.4log 0.4 0.18log 0.18 0.1log 0.1 0.1log 0.1 0.07log 0.07 0.06log 0.06 0.05log 0.05 0.04log 0.04 2.55熵2.5597.7%2.61编码效率Modern Image Analysis6.4 霍夫曼编码(1)100%2.3%DR31.152.61RavgmCL霍夫曼编码是无失真编码中效率较高的一种编码方法。在分配码字过程中，随机赋“0”和“1”的不同，结果会使码字不同（不唯一），而码字长和平均码字长不会改变，它也是唯一可解码的。但其缺点是信源缩减过程复杂，运算量大。为克服这个缺点，人们也相继提出了一些改进方法。