图像的霍夫曼编码讲解.docVIP

序号： 图像的霍夫曼编码 姓 名： 班 级： 学 号： 专 业： 指导老师： 完成时间： 湖南理工学院物理与电子学院 目 录 摘要： 1 一、引言 1 二、霍夫曼编码简介 1 三、 霍夫曼编码 2 1、霍夫曼编码规则 2 2、霍夫曼树 3 （1）霍夫曼树的相关概念 3 （2）霍夫曼算法 3 （3）霍夫曼树的构建 4 3. 霍夫曼的局限性 5 四、霍夫曼编码分类 6 1、 截断霍夫曼编码 6 2、 自适应霍夫曼编码 6 五、 仿真 8 六、 结论 12 参考文献 12 摘要： 霍夫曼编码是一种常用的无损编码，他基于不同符号的概率分布，在信息源中出现概率越大的符号，相应的码越短；出现概率越小的符号，其码越长，从而达到用尽可能少的码符号表示源数据。本文介绍了霍夫曼编码的原理、方法、特点、应用、霍夫曼树的生成过程，霍夫曼编码的产生，霍夫曼表的构建，霍夫曼编码的结果以及怎样用MATLAB实现霍夫曼编码。? 关键字：无损编码 霍夫曼编码? 霍夫曼树? MATLAB 一、引言 随着科学技术的发展和需求，人们广泛致力于对各种文本、图片、图形、语言、声音、活动图像和影视信号等实际信源进行了实用压缩方法和技术研究，使信源的数据压缩技术得以蓬勃发展和逐渐走向成熟。在信息化高度发达的当今社会，我们必须对信息的传递有着较高的要求，我们希望信息在传递的过程中，能够保持节省性和必威体育官网网址性和无损性，而著名的霍夫曼编码就能够达到这样的要求。因此研究霍夫曼编码对信息的压缩和解压是相当有必要的。 二、霍夫曼编码简介 1952年，David?A.?Huffman在麻省理工攻读博士时，根据香农（Shannon）在1948年和范若（Fano）在1949年阐述的编码思想提出了一种不定长编码的方法——霍夫曼编码，并发表于《一种构建极小多余编码的方法》一文。霍夫曼编码是常用的无损编码方法，广泛应用于图像压缩技术。JPEG标准中的基准模式采用的就是霍夫曼编码。?霍夫曼编码是不定长编码，即代表各元素的码字长度不等。该编码是基于不同符号的概率分布，在信息源中出现概率越大的符号，相应的码越短；出现概率越小的符号，其码越长，从而达到用尽可能少的码符号表示源数据。它在变长编码中是最佳的。在计算机信息处理中，“霍夫曼编码”是一种一致性编码法（又称熵编码法） 霍夫曼编码的基本方法是先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字，由此得到一张该图像的霍夫曼码表。编码后的图像数据记录的是每个像素的码字，而码字与实际像素值的对应关系记录在码表中。 设信源X的信源空间为： 其中，，现用二进制对信源中的每一个符号进行编码 将信源符号xi按其出现的概率，由大到小顺序排列。? 将两个最小的概率的信源符号进行组合相加，并重复这一步骤，始终将较大的概率分支放在上部，直到只剩下一个信源符号且概率达到1.0为止；? 对每对组合的上边一个指定为1，下边一个指定为0（或相反：对上边一个指定为0，下边一个指定为1）；? 画出由每个信源符号到概率1处的路径，记下沿路径的1和0 a1 a2 a3 a4 a5 a6 a7 a8 次数 2 2 3 4 3 3 3 1 概率 0.1 0.1 0.15 0.2 0.15 0.15 0.1 0.05 具体过程是这样的，先将所有符号排成一行构成8个最底层节点。首先将这些节点中最小两个概率值相加：0.05+0.1=0.15, 得到新的节点，这时拥有的概率值为0.2, 0.1, 0.1, 0.15, 0.15, 0.15, 0.15。再将两个最小的概率值相加得到新的节点... ... 直到得到根节点概率为1.0为止。相加时，对于概率值相等的多个节点，可以任意选取。除根节点外，设节点左边分支为0，右边分支为1（也可以反过来）。根据表一生成的霍夫曼树如图1所示。 图1 对于各值（码值）的代码（码字）就是从根节点出发到底层节点所经历的分支序列。如a4的代码（码字）为00，a6的码字为111... ...通常a4和a6等称为码值，00和111等称为码字。所有码值和码字对应关系如表2所示。 霍夫曼的局限性 a. 利用霍夫曼编码，每个符号的编码长度只能为整数，所以如果源符号集的概率分布不是2负n次方的形式，则无法达到熵极限。 b. 输入符号