自适应霍夫曼编码
哈尔滨工业大学（威海）
自适应霍夫曼编码
信息论论文
隋沛君
10S030092
一、霍夫曼编码概述：
Huffman 算法是一种用于数据压缩的算法，由D.A. Huffman 最先提出。它完全依据字符出现概率来构造平均长度最短的编码，有时称之为最佳编码，一般叫做Huffman编码。频繁使用的数据用较短的代码代替，较少使用的数
据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。
该编码的核心部分为Huffman编码树，一棵满二叉树。所有可能的输入
符（通常对应为字节）在Huffman编码树上对应为一个叶节点，叶节点的位
置就是该符号的Huffman编码。具体来说，一个符号对应的Huffman 编码就是从根节点开始，沿左字节点0或右子节点1前进，一直找到该符号叶节点为止的路径对应的二进制编码。在Huffman编码树的基础上，该算法的编码部
分输入一系列的符号，根据Huffman树对符号进行翻译，以符号在Huffman
树上的位置作为编码结果。解码部分反之，根据输入的Huffman编码，通过
查询Huffman树翻译回原始符号。
现在使用中的霍夫曼编码大致分为两种：静态霍夫曼编码和自适应霍夫曼编码。
二、静态霍夫曼编码简介：
编码步骤：
第一，将信源符号按照权重（即该符号出现的概率）递减顺序排序。
第二，取出权重最小的两个集合元素作为叶节点组成一棵子树，子树的根节点权重值为两个叶节点的权重值之和。然后将新产生的子树的根节点元
素替代原两个叶子节点元素放回原来的集合，并保持集合有序。每次形成子树时，将两个叶子节点分别赋予1和0或0和1。
第三，重复上述步骤，直至集合中只剩下一个元素，则Huffman 编码树构造完成。
第四，对每一个信源符号写出从编码树的根节点到叶子节点的1,0序列。
编码实例：abcddbb
最终编码结果：1000101111100
三、自适应霍夫曼编码提出的目的和意义：
在静态霍夫曼编码中，要构造编码树必须提前统计被编码对象中的符号出现概率，因此必须对输入符号流进行两遍扫描，第一遍统计符号出现概率并构造编码树，第二遍进行编码，这在很多实际应用的场合中之不能接受的。其次，在存储和传送霍夫曼编码时，必须先存储和传送霍夫曼编码树。再次，静态编码树构造方案不能对输入符号流的局部统计规律变化做出反应。这些问题使得静态霍夫曼编码在实际中并未得到广泛的应用。
为了解决静态Huffman编码的缺点，人们提出了自适应Huffman编码，
这种方案不需要事先扫描输入符号流，而是随着编码的进行同时构造Huffman树，因此，只需要进行一次扫描即可。在接收端伴随着解码过程同时进行着编码树的构造。自适应霍夫曼编码解决了静态编码树所面临的主要问题，因此在实际领域比如在高质量的图像和视频流传输中中获得了广泛的应用。
四、自适应霍夫曼编码的原理：
这种方案在不需要事先构造Huffman 树，而是随着编码的进行，逐步构造Huffman 树。同时，这种编码方案对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变（变得更长或更短）。
在构造动态霍夫曼编码树的过程中，需要遵循两条重要原则：
（1）权重值大的节点，节点编号也较大。
（2）父节点的节点编号总是大于子节点的节点编号。
以上两点称为兄弟属性（sibling property）。在每一次调整节点权重值时，都需要相应的调整节点编号，以避免兄弟属性被破坏。在对某一个节点权重值进行“加一操作”时，应该首先检查该节点是否具有所在的块中的最大节点编号，如果不是，则应该将该节点与所在块中具有最大节点编号的节点交换位置。然后再对节点的权重值加。这样，由于该节点的节点编号已经处于原来所属块中的最大值，因此权重值加一之后兄弟属性仍然得到满足。最后，由于节点的权重发生了变化，必须递归地对节点的父节点进行加一操作。
初始化编码树时，由于只允许对待编码数据流进行单遍扫描，因此不可能预先知道各种符号的出现频率。为了对所有符号一致对待，编码树的初始
状态只包含一个叶节点，包含符号NYT（Not Yet Transmitted，尚未传送），权重值为0。NYT是一个逸出码（escape code），不同于任何一个将要传送的符号。当有一个尚未包含在编码树中的符号需要被编码时，系统就输出NYT 编码，然后跟着符号的原始表达。当解码器解出一个NYT 之后，它就知道下面的内容暂时不再是Huffman 编码，而是一个从未在编码数据流中出现过的原始符号。这样，任何符号都可以在增加到编码树之前进行传送。
在需要插入一个新符号时，总是先构造一个新的子树，子树包含NYT 符号与新符号两个叶节点，然后将旧的NYT 节点由这个子树替代。由于包含NYT 符号的节点权重值为0，而包含新符号的叶节点的权重值为1，因此最终效果相当于原NYT 节点位置的权重值由0 变为1。因此，下一步将试图对其父节点执行权重值“加一操作”。
对符号编码的方法与静态霍夫曼编码一致，每次符号编码完成以后，也将对包含符号的节点权值进行加一操作。
将一个新的符号插入编码树或者输出某一个已编码符号后，相应的符号的出现次数增加了1，继而编码树中各种符号的出现频率发生了改变，不一定符合兄弟属性，按照上述方法进行调整，使其符合要求。
五、自适应霍夫曼编码流程图：
六、自适应霍夫曼编码实例：
输入序列：abcddbb
步骤一：初始状态，仅有唯一的YNT节点，
节NYT点的权重为0。
步骤二：输入符号：a
输出编码：a
使用包含新NYT节点和字符a节
点的子树，替换旧的NYT节点。步骤三：输入符号：b
输出符号：0b
使用包含新NYT节点和字符b节
点的子树，替换旧的NYT节点。
对51号节点（根节点）执行权重
值加一操作。
步骤四：
输入符号：c
输出编码：00c
使用包含新NYT节点和字符c节
点的子树，替换旧的NYT节点。
步骤五：
将要对49号节点执行权重值加一操
作，但49号节点不具有所在的块中
的最大节点编号，因此需要先与50
号节点进行交换位置操作。
新的50号节点权重值加一。
对51号节点执行权重值加一操作。步骤六：输入符号：d
输出编码：100d
使用包含新NYT节点和字符d节点
的子树，替换旧的NYT节点。
将要对47号节点执行权重加一操作，
但是47号节点不具有所在块中的最
大节点编号，因此需要先与49号节
点进行交换位置操作。
步骤七：
新的49号节点权重值加一。
对51号节点执行权重值加一操作。
步骤八：输入符号：d
输出编码：001
将要对44号节点执行权重值加一操
作，但44号节点不具有所在的块中
的最大的节点编号，因此需要先与
48号节点进行交换位置操作。
步骤九：
新的48号节点权重值加一。
对50号节点执行权重值加一操作。
对51号节点执行权重值加一操作。
步骤十：输入符号：b
输出编码：001
要对44号节点执行权重值加一操作，
但44号节点不具有所在的块中的最
大节点编号，因此需要先与47号节
点进行位置交换操作。
步骤十一：
新的47号节点权重值加一。
对50号节点执行权重值加一操作。
对51号节点执行权重值加一操作。
步骤十二：输入符号：b
输出编码：10
将要对47号节点执行权重值加一
操作，但47号节点不具有所在块中
的最大节点编号，因此需要先与49
号节点进行交换位置操作。
步骤十三：
新的49号节点权重值加一。
对51号节点执行权重值加一的
操作。
至此编码完成，输出编码为：a0b00c100d00100110
七、自适应霍夫曼编码特征：
通过观察以上步骤，容易发现自适应Huffman 编码的几个特征：
(1) 在步骤13 得到的编码树与静态Huffman 编码树基本相同，除了NYT 节点和符号a节点组成的子树替代了静态Huffman 编码树中的符号
a 的叶节点之外；
(2) 在每一次输入新的符号之前，Huffman 树都处于完整可用的正常状态；
(3) 同一个输入符号，可能产生多种不同的输出。例如三次输入的符号b，产生的输出分别为0b、001 和10；
(4) 同样的输出结果，可能由不同的输入产生。例如第二次输入的符号d 与第二次输入的符号b，都产生了001 作为输出结果。
这些特征首先说明了自适应Huffman 编码树与静态Huffman 编码树
等同，完全符合Huffman 树的定义。同时，由于每一个输入符号都对编码树产生了影响，因此解码过程无法从Huffman 编码数据流的某一个中间位置开始进行，而必须从头至尾逐bit 处理。由于自适应Huffman 编码算法采用了先编码，后调整编码树的方案，相应的解码算法比较简单。解码算法也使用仅有唯一的NYT 节点的编码树作为初始状态，然后根据Huffman编码数据流，对符号进行还原。每次处理完一个符号，就使用这个符号调整编码树。这样，在每一次输入新的符号之前，Huffman 树都处于与进行编码时使用的Huffman 树完全相同的状态，保证了解码的正确性。
八、总结
自适应霍夫曼编码是一种扩展的熵编码方法，相比于先前的静态霍夫曼编码，自适应霍夫曼编码具有仅需单遍扫描、无需传送编码树、能够对输入符号流的局部统计规律变化做出反应等一系列优点，具有更高的压缩效率。这些优点使得它在一些实时性、可靠性要求比较高的场合得到了广泛的应用，被称为近代压缩算法的灵魂。
九、参考文献
[1] 数据结构与算法分析, Clifford A. Shaffer, 张铭、刘晓丹译, 电子工业出版社, 1998.
[2] Huffman 编码简介,联合程序开发网论坛,2010
[3] Adaptive Huffman Compression, AdaptiveHuff.html, Ze-Nian Li, 2006.
[4] 笨笨数据压缩教程, https://www.wendangku.net/doc/ac2658483.html,/wangyg/a/tutorial/benben.
html, 王咏刚, 2003.
霍夫曼编码表
附录二 表1. 传真用的修正霍夫曼编码表 构造码 64 11011 0000001111 960 011010100 0000001110011 128 10010 000011001000 1024 011010101 0000001110100 192 010111 000011001001 1088 011010110 0000001110101 256 0110111 000001011011 1152 011010111 0000001110110 320 00110110 000000110011 1216 011011000 0000001110111 384 00110111 000000110100 1280 011011001 0000001010010 448 01100100 000000110101 1344 011011010 0000001010011 512 01100101 0000001101100 1448 011011011 0000001010100 576 01101000 0000001101101 1472 010011000 0000001010101 640 01100111 0000001001010 1536 010011001 0000001011010 704 011001100 0000001001011 1600 010011010 0000001011011 768 011001101 0000001001100 1664 011000 0000001100100 832 011010010 0000001001101 1728 010011011 0000001100101 896 011010011 0000001110010 EOL 000000000001 000000000001 结尾码 游程长度 白游程编码 黑游程编码 游程长度白游程编码 黑游程编码 0 00110101 0000110111 32 000111011 000001101010 1 000111 010 33 00010010 000001101011 2 0111 11 34 00010011 000011010010 3 1000 10 35 00010100 000011010011 4 1011 011 36 00010101 000011010100 5 1100 0011 37 00010110 000011010101 6 1110 0010 38 00010111 000011010110 7 1111 00011 39 00101000 000011010111 8 10011 000101 40 00101001 000001101100 9 10100 000100 41 00101010 000001101101 10 00111 0000100 42 00101011 000011011010 11 01000 0000101 43 00101100 000011011011 12 001000 0000111 44 00101101 000001010100 13 000011 00000100 45 00000100 000001010101 14 110100 00000111 46 00000101 000001010110 15 110101 000011000 47 00001010 000001010111 16 101010 0000010111 48 00001011 000001100100 17 101011 0000011000 49 01010010 000001100101 18 0100111 0000001000 50 01010011 000001010010 19 0001100 00001100111 51 01010100 000001010011 20 0001000 00001101000 52 01010101 000000100100 21 0010111 00001101100 53 00100100 000000110111 22 0000011 00000110111 54 00100101 000000111000 23 0000100 00000101000 55 01011000 000000100111 24 0101000 00000010111 56 01011001 000000101000 25 0101011 00000011000 57 01011010 000001011000 26 0010011 000011001010 58 01011011 000001011001 27 0100100 000011001011 59 01001010 000000101011 28 0011000 000011001100 60 01001011 000000101100 29 00000010 000011001101 61 00110010 000001011010 30 00000011 000001101000 62 00110011 000001100110 31 00011010 000001101001 63 00110100 000001100111 205
三进制霍夫曼编码
三进制霍夫曼编码 Prepared on 22 November 2020
题目：将霍夫曼编码推广至三进制编码，并证明它能产生最优编码。 ※将霍夫曼编码推广至三进制编码 设一个数据文件包含Q个字符：A1，A2，……，Aq，每个字符出现的频度对应为P：P1，P2，……，Pq。 1.将字符按频度从大到小顺序排列，记此时的排列为排列1。 2.用一个新的符号(设为S1)代替排列1中频度值最小的Q-2k(k为(Q-1)/2取整)个字符，并记其频度值为排列1中最小的Q-2k个频度值相加，再重新按频度从大到小顺序排列字符，记为排列2。(注：若Q-2k=0，则取其值为2，若Q-2k=1，则取其值为 3.) 3.对排列2重复上述步骤2，直至最后剩下3个概率值。 4.从最后一个排列开始编码，根据3个概率大小，分别赋予与3个字符对应的值：0、1、2，如此得到最后一个排列3个频度的一位编码。 5.此时的3个频度中有一个频度是由前一个排列的3个相加而来，这3个频度就取它的一位编码后面再延长一位编码，得到二位编码，其它不变。 6.如此一直往前，直到排列1所有的频度值都被编码为止。 举例说明如下（假设Q=9）：
频度中的黑体为前一频度列表中斜体频度相加而得。编码后字符A1~A9的码字依次为：2,00,02,10,11,12,010,011,012。 构造三进制霍夫曼编码伪码程序如下： HUFFMAN(C) 1 n ←∣C ∣ 2 Q ← C 3 for i ← 1 to n-1 4 do allocate a new node s 5 left[s] ← x ← EXTRACT-MIN(Q) 6 middle[s] ← y ← EXTRACT-MIN(Q) 7 right[s] ← z ← EXTRACT-MIN(Q) 8 f[s] ← f[x]+f[y]+f[z] 9 INSERT(Q，z) 10 return EXTRACT-MIN(Q) ※霍夫曼编码（三进制）最优性证明 在二进制霍夫曼编码中，文件的最优编码由一棵满二叉树表示，树中每个非叶子结点都有两个子结点。在此与之相对应，构造一棵满三叉树来表示三进制的霍夫曼编码，树中每个非叶子结点都有三个子结点。对文件中A中的每个字符a，设f(a)表示a在文件中出现的频度，d T(a)表示字符a的编码长度，亦即a 的叶子在树中的深度。这样，编码一个文件所需的位数就是 B(T)=∑f(a)d T(a) 设A为一给定文件，其中每个字符都定义有频度f[a]。设x，y和z是A中具有最低频度的两个字符。并设A'为文件A中移去x，y和z，再加上新的字符s后的文件，亦即A'=A-{x,y,z}∪{s}；如A一样为A'定义f，其中f[s]=f[x]+f[y]+f[z]。设T'为文件A'上最优
基于MATLAB的图像Huffman编码研究.docx
中国矿业大学2015-2016学年第二学期 《数字视频技术》课程小设计考核 图像的Huffman编码研究 专业班级：信息13-04班 学生姓名：王振宇、龙航、王一鸣 学生学号：04131407、04131403、04131406 本人郑重声明：本人认真、独立完成了查找资料、完成作业、编写程序等考核任务，无抄袭行为。 签字： 日期：2016.05.17
1.引言 1.1图像数据压缩的目的 数字图像通常要求很大的比特数，这给图像的传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。一般原始图像存在很大的冗余度。所以，对图像数据压缩显得非常重要。 1.2图像数据压缩的原理 对数字图像压缩主要运用两个基本原理：一是图像的相关性。在图像同一相邻像素之间，活动图像的相邻帧的对应像素之间往往存在很强的相关性，去除或减少这些相关性，也就除去或减少图像信息中的冗余度，继而实现对数字图像的压缩。二是人的视觉心理特征，人的视觉对于边缘急剧变化不敏感，对颜色分辨力弱，利用这些特征在相应部分降低编码精度而使人从视觉上感觉不到图像质量的下降，从而达到对数字图像压缩的目的。 1.3Huffman编码 Huffman编码是一种编码方式，是一种用于无损数据压缩的熵编码算法。它是Huffman 在1952年根据Shannon在1948年和Fano在1949年阐述的这种编码思想下提出的一种不定长编码的方法，有时也称之为最佳编码。依据信源数据中各信号出现的频率分配不同长度的编码。其基本思想是在编码过程中，对出现频率越高的值，分配越短的编码长度，相应地对出现频率越低的值则分配较长的编码长度，完全依据字符出现概率来构造异字头的平均长度最短的码字。哈夫曼编码方法的实质是针对统计结果对字符本身重新编码，而不是对重复字符或重复子串编码，得到的单位像素的比特数最接近图像的实际熵值。 2.设计任务 2.1设计任务 研究实现灰度图像的Huffman编码和解码恢复。 2.2设计目的 (1)了解Huffman编码的基本原理及其特点； (2)理解并熟练对图像进行哈夫曼编码的算法； (3)学习和熟悉MA TLAB图像处理工具箱； (4)熟悉和掌握MA TLAB程序设计方法； 2.3设计要求 现灰度图像的Huffman编码和解码恢复图像；处理结果要求最终图像显示，且计算图像的信息熵，平均码字长度，编码效率，压缩比。 3.总体设计方案 3.1系统运行环境 Windows 8.1/10系统 3.2编程软件平台 MATLAB R2013a/R2014a 3.3Huffman编码算法原理 哈夫曼编码的基本方法是先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字，由此得到一张该图像的哈夫曼码表。编码后的图像数据记录的是每个像素的码字，而码字与实际像素值的对应关系记录在码表中。 (1)计算信源符号出现的概率； (2)将信源符号按其出现的概率，由小到大顺序排列，并从左至右排列为叶节点[1]；
霍夫曼编码
霍夫曼编码 霍夫曼编码(Huffman Coding)是一种编码方法，霍夫曼编码是可变字长编码(VLC)的一种。1952年，David A. Huffman在麻省理工攻读博士时所提出一种编码方法，并发表于《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。 该方法完全依据字符出现概率来构造异字头的平均长度最短的 码字，有时称之为最佳编码，一般就叫作Huffman编码。 在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。1951年，霍夫曼和他 在MIT信息论的同学需要选择是完成学期报告还是期末考试。 导师Robert M. Fano给他们的学期报告的题目是，查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者克劳德·香农共同研究过类似编码的导师。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。 霍夫曼（Huffman）编码是一种统计编码。属于无损（lossless）压缩编码。
以霍夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 ←根据给定数据集中各元素所出现的频率来压缩数据的 一种统计压缩编码方法。这些元素(如字母)出现的次数越 多，其编码的位数就越少。 ←广泛用在JPEG, MPEG, H.2X等各种信息编码标准中。霍夫曼编码的步骤 霍夫曼编码的具体步骤如下： １）将信源符号的概率按减小的顺序排队。 ２）把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在上部，直到最后变成概率１。 3）将每对组合的上边一个指定为1，下边一个指定为0（或相反）。４）画出由概率１处到每个信源符号的路径，顺序记下沿路径的０和１，所得就是该符号的霍夫曼码字。 信源熵的定义： 概率空间中每个事件所含有的自信息量的数学期望称信源熵或简称熵(entropy)，记为： 例：现有一个由5个不同符号组成的30个符号的字 符串：BABACACADADABBCBABEBEDDABEEEBB 计算 (1) 该字符串的霍夫曼码 (2) 该字符串的熵 (3) 该字符串的平均码长
图像压缩编码实验报告
图像压缩编码实验报告 一、实验目的 1.了解有关数字图像压缩的基本概念，了解几种常用的图像压缩编码方式； 2.进一步熟悉JPEG编码与离散余弦变换（DCT）变换的原理及含义； 3.掌握编程实现离散余弦变换（DCT）变换及JPEG编码的方法； 4.对重建图像的质量进行评价。 二、实验原理 1、图像压缩基本概念及原理 图像压缩主要目的是为了节省存储空间，增加传输速度。图像压缩的理想标准是信息丢失最少，压缩比例最大。不损失图像质量的压缩称为无损压缩，无损压缩不可能达到很高的压缩比；损失图像质量的压缩称为有损压缩，高的压缩比是以牺牲图像质量为代价的。压缩的实现方法是对图像重新进行编码，希望用更少的数据表示图像。应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分为以下3类： （1）无损压缩编码种类 哈夫曼（Huffman）编码，算术编码，行程（RLE）编码，Lempel zev编码。（2）有损压缩编码种类 预测编码，DPCM，运动补偿； 频率域方法：正交变换编码(如DCT)，子带编码； 空间域方法：统计分块编码； 模型方法：分形编码，模型基编码； 基于重要性：滤波，子采样，比特分配，向量量化； （3）混合编码 JBIG，H.261，JPEG，MPEG等技术标准。 2、JPEG 压缩编码原理 JPEG是一个应用广泛的静态图像数据压缩标准，其中包含两种压缩算法(DCT和DPCM)，并考虑了人眼的视觉特性，在量化和无损压缩编码方面综合权衡，达到较大的压缩比(25:1以上)。JPEG既适用于灰度图像也适用于彩色图像。其中最常用的是基于DCT变换的顺序式模式，又称为基本系统。JPEG 的压缩编码大致分
哈夫曼编码步骤
哈夫曼编码步骤： 一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。） 二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 四、重复二和三两步，直到集合F中只有一棵二叉树为止。 /*------------------------------------------------------------------------- * Name: 哈夫曼编码源代码。 * Date: 2011.04.16 * Author: Jeffrey Hill+Jezze(解码部分) * 在Win-TC 下测试通过 * 实现过程：着先通过HuffmanTree() 函数构造哈夫曼树，然后在主函数main()中 * 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在 * 父结点左侧，则置码为0,若在右侧,则置码为1。最后输出生成的编码。*------------------------------------------------------------------------*/ #include
霍夫曼图像压缩编码源程序
clear X=imread('lena512.bmp'); data=uint8(X); [zipped,info]=huffencode(data); %调用Huffman编码程序进行压缩 unzipped=huffdecode(zipped,info,data); %调用Huffman编码程序进行解码 %显示原始图像和经编码后的图像，显示压缩比，并计算均方根误差得erms=0，表示是Huffman是无失真编码 subplot(121);imshow(data); subplot(122);imshow(unzipped); %erms=compare(data(:),unzipped(:)) cr=info.ratio whos data unzipped zipped function [zipped, info] = huffencode(vector) % 输入和输出都是uint8 格式 % info 返回解码需要的结构信息 % info.pad 是添加的比特数 % info.huffcodes 是Huffman 码字 % info.rows 是原始图像行数 % info.cols 是原始图像列数 % info.length 是原始图像数据长度 % info.maxcodelen 是最大码长 if ~isa(vector, 'uint8') error('input argument must be a uint8 vector'); end [m, n] = size(vector); vector = vector(:)'; f = frequency(vector); %计算各符号出现的概率 symbols = find(f~=0); f = f(symbols); [f, sortindex] = sort(f); %将符号按照出现的概率大小排列 symbols = symbols(sortindex); len = length(symbols); symbols_index = num2cell(1:len); codeword_tmp = cell(len, 1); % 生成Huffman 树，得到码字编码表 while length(f)>1 index1 = symbols_index{1}; index2 = symbols_index{2}; codeword_tmp(index1) = addnode(codeword_tmp(index1), uint8(0)); codeword_tmp(index2) = addnode(codeword_tmp(index2), uint8(1));
实验四dct变换huffman编码图像压缩
实验四图像压缩 姓名：学号：邮箱： 一、实验目的 1.掌握DCT变换的原理 2.了解DCT变化在图像压缩中的应用 3.掌握图像压缩的基本原理及方法 4.了解霍夫曼编码原理 5.熟悉图像压缩的MATLAB编程 二、实验原理 DCT是目前比较好的图像变换，它有很多优点。DCT是正交变换，它可以将8x8图像空间表达式转换为频率域，只需要用少量的数据点表示图像；DCT产生的系数很容易被量化，因此能获得好的块压缩；DCT算法的性能很好，它有快速算法，如采用快速傅立叶变换可以进行高效的运算，因此它在硬件和软件中都容易实现；而且DCT算法是对称的，所以利用逆DCT算法可以用来解压缩图像。 由于DCT主要应用在数据和图像的压缩，因此希望原信号的能量在变换后能尽量集中在少数系数上，且这些大能量的系数能处在相对集中的位置，这将有利于进一步的量化和编码。但是如果对整段的数据或整幅图像来做DCT，那就很难保证大能量的系数能处在相对集中的位置。因此，在实际应用中，一般都是将数据分成一段一段来做，一般分成8x8或16x16的方块来做。 二维DCT正交变换的公式为： 二维DCT逆变换公式： 其中
三、实验要求 利用DCT变换对图像进行压缩，对比不同压缩比下的结果，对比不同压缩比下图像大小的变化。压缩过程如下图所示： 四、实验过程与结果 实验程序如下：（先给出主程序，然后给出各功能子函数的程序） 主程序： clear load('')%调入170*170大小的一幅彩色lena图像 l=imresize(lena,[256 256]);%将图像变换为8的整数倍大小 X=rgb2gray(l); Y1=double(X);%读入图像数据lianghua=[16 11 10 16 24 40 51 61;%量化矩阵，量化的程度序决定压缩比 12 12 14 19 26 58 60 55; 14 13 16 24 40 57 69 56; 14 17 22 29 51 87 80 62; 18 22 37 56 68 109 103 77; DCT变换 量化huffman编码
哈夫曼树的编码和译码
#include"stdafx.h" #include"stdio.h" #include"conio.h" #include
霍夫曼编码
霍夫曼编码的matlab实现 一、实验内容： 用Matlab语言编程实现霍夫曼（Huffman）编码。 二、实验原理及编码步骤： 霍夫曼（Huffman）编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号，而将较短的编码码字分配给较大概率的信源输出。算法是：在信源符号集合中，首先将两个最小概率的信源输出合并为新的输出，其概率是两个相应输出符号概率之和。这一过程重复下去，直到只剩下一个合并输出为止，这个最后的合并输出符号的概率为1。这样就得到了一张树图，从树根开始，将编码符号1 和0 分配在同一节点的任意两分支上，这一分配过程重复直到树叶。从树根到树叶途经支路上的编码最后就构成了一组异前置码，就是霍夫曼编码输出。以本教材P74例题3-18信源为例： 信源： X x1 x2 x3 x4 x5 q(X) = 0.4 0.2 0.2 0.1 0.1 解：
通过上表的对信源缩减合并过程，从而完成了对信源的霍夫曼编码。 特点：霍夫曼编码在三种编码方法中编码效率最高 基本步骤：p72 三、实验程序及运行结果 （见附录6） 程序流程图：XXXXXXXXXXXX 四 分析结果 由程序运行结果可知： 方法一（概率之和往上排）： 码字：11 01 00 101 100 编码效率： %4.962 .212 .21log 2 .22.038.0212 .2)(log ) (log )(log n 5 11≈= ==?+?==-= = ∑ηη所以：） （D n X H D n xm q xm q D X H
码长均值：2.22.038.02n 1=?+?= 码长均方差：{}16.02.0)2.23(8.0)2.22()2221=?-+?-=-n n E （ 方法二（概率之和往下排）： 码字：0 10 111 1101 1100 编码效率： %4.962 .212 .21log 2.22.042.032.024.0112.2)(log ) (log )(log n 5 12≈= ==?+?+?+?==-= =∑ηη所以：） （D n X H D n xm q xm q D X H 码长均值：2.22.042.032.024.01n 2=?+?+?+?= 码长均方差： { }36 .12.02.2-42.02.2-32.0)2.22(4.0)2.21()2 2222 22=?+?+?-+?-=-）（）（（n n E 比较方法一和方法二可知：两张编码方法平均码长相等，但方法二均方差较大，一般取均方 差小的编码方法，这样译码会更简单。
哈夫曼编码的方法
1．哈夫曼编码的方法 编码过程如下: (1) 将信源符号按概率递减顺序排列; (2) 把两个最小的概率加起来, 作为新符号的概率; (3) 重复步骤(1) 、(2), 直到概率和达到1 为止; (4) 在每次合并消息时，将被合并的消息赋以1和0或0和1； (5) 寻找从每个信源符号到概率为1处的路径，记录下路径上的1和0； (6) 对每个符号写出"1"、"0"序列（从码数的根到终节点）。 2．哈夫曼编码的特点 ①哈夫曼方法构造出来的码不是唯一的。 原因 ·在给两个分支赋值时, 可以是左支( 或上支) 为0, 也可以是右支( 或下支) 为0, 造成编码的不唯一。 ·当两个消息的概率相等时, 谁前谁后也是随机的, 构造出来的码字就不是唯一的。 ②哈夫曼编码码字字长参差不齐, 因此硬件实现起来不大方便。 ③哈夫曼编码对不同的信源的编码效率是不同的。 ·当信源概率是2 的负幂时, 哈夫曼码的编码效率达到100%; ·当信源概率相等时, 其编码效率最低。 ·只有在概率分布很不均匀时, 哈夫曼编码才会收到显著的效果, 而在信源分布均匀的情况下, 一般不使用哈夫曼编码。 ④对信源进行哈夫曼编码后, 形成了一个哈夫曼编码表。解码时, 必须参照这一哈夫编码表才能正确译码。 ·在信源的存储与传输过程中必须首先存储或传输这一哈夫曼编码表在实际计算压缩效果时, 必须考虑哈夫曼编码表占有的比特数。在某些应用场合, 信源概率服从于某一分布或存在一定规律
使用缺省的哈夫曼编码表有
解：为了进行哈夫曼编码, 先把这组数据由大到小排列, 再按上方法处理 （1）将信源符号按概率递减顺序排列。 （2）首先将概率最小的两个符号的概率相加，合成一个新的数值。 （3）把合成的数值看成是一个新的组合符号概率，重复上述操作，直到剩下最后两个符号。 5．4．2 Shannon-Famo编码 Shannon-Famo(S-F) 编码方法与Huffman 的编码方法略有区别, 但有时也能编 出最佳码。 1．S－F码主要准则 符合即时码条件; 在码字中,1 和0 是独立的, 而且是( 或差不多是)等概率的。 这样的准则一方面能保证无需用间隔区分码字,同时又保证每一位码字几乎有 1位的信息量。 2．S－F码的编码过程 信源符号按概率递减顺序排列; 把符号集分成两个子集, 每个子集的概率和相等或近似相等;
霍夫曼编码原理
霍夫曼编码 四川大学计算机学院2009级戚辅光 【关键字】 霍夫曼编码原理霍夫曼译码原理霍夫曼树霍夫曼编码源代码霍夫曼编码分析霍夫曼编码的优化霍夫曼编码的应用 【摘要】 哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman 编码。哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。它属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。 【正文】 引言 哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 霍夫曼编码原理： 霍夫曼编码的基本思想：输入一个待编码的串，首先统计串中各字符出现的次数，称之为频次，假设统计频次的数组为count[]，则霍夫曼编码每次找出count数组中的值最小的两个分别作为左右孩子，建立他们的父节点，循环这个操作2*n-1-n（n是不同的字符数）次，这样就把霍夫曼树建好了。建树的过程需要注意，首先把count数组里面的n个值初始化为霍夫曼树的n个叶子节点，他们的孩子节点的标号初始化为-1，父节点初始化为他本身的标号。接下来是编码，每次从霍夫曼树的叶子节点出发，依次向上找，假设当前的节点标号是i，那么他的父节点必然是myHuffmantree[i].parent，如果i是myHuffmantree[i].parent 的左节点，则该节点的路径为0，如果是右节点，则该节点的路径为1。当向上找到一个节点，他的父节点标号就是他本身，就停止（说明该节点已经是根节点）。还有一个需要注意的地方：在查找当前权值最小的两个节点时，那些父节点不是他本身的节点不能考虑进去，因为这些节点已经被处理过了。 霍夫曼树：
三进制霍夫曼编码
题目：将霍夫曼编码推广至三进制编码，并证明它能产生最优编码。 ※将霍夫曼编码推广至三进制编码 设一个数据文件包含Q个字符：A1，A2，……，Aq，每个字符出现的频度对应为P：P1，P2，……，Pq。 1.将字符按频度从大到小顺序排列，记此时的排列为排列1。 2.用一个新的符号(设为S1)代替排列1中频度值最小的Q-2k(k为(Q-1)/2取整)个字符，并记其频度值为排列1中最小的Q-2k个频度值相加，再重新按频度从大到小顺序排列字符，记为排列2。(注：若Q-2k=0，则取其值为2，若Q-2k=1，则取其值为 3.) 3.对排列2重复上述步骤2，直至最后剩下3个概率值。 4.从最后一个排列开始编码，根据3个概率大小，分别赋予与3个字符对应的值：0、1、2，如此得到最后一个排列3个频度的一位编码。 5.此时的3个频度中有一个频度是由前一个排列的3个相加而来，这3个频度就取它的一位编码后面再延长一位编码，得到二位编码，其它不变。 6.如此一直往前，直到排列1所有的频度值都被编码为止。 举例说明如下（假设Q=9）： 字符A1 A2 A3 A4 A5 A6 A7 A8 A9 频度0.22 0.18 0.15 0.13 0.10 0.07 0.07 0.05 0.03 字符频度编码频度编码频度编码频度编码A1 0.22 2 0.22 2 0.30 1 0.480 A2 0.18 00 0.18 00 0.22 2 0.30 1 A3 0.15 02 0.1501 0.18 00 0.22 2 A4 0.13 10 0.15 02 0.15 01 A5 0.10 11 0.13 10 0.15 02 A6 0.07 12 0.10 11 A7 0.07 010 0.07 12 A8 0.05 011 A9 0.03 012 频度中的黑体为前一频度列表中斜体频度相加而得。编码后字符A1~A9的码字依次为：2,00,02,10,11,12,010,011,012。 构造三进制霍夫曼编码伪码程序如下： HUFFMAN(C) 1 n ←∣C ∣ 2 Q ← C 3for i ←1 to n-1 4 do allocate a new node s
图像的无损压缩程序设计 霍夫曼编码
成绩评定表
课程设计任务书
摘要 哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。 本课题通过MATLAB编写适当的函数，对一个随机信源进行哈夫曼编码，得出码字，平均码长和编码效率。从而理解信源编码的基本思想与目的以及哈夫曼编码方法的基本过程与特点，并且提高综合运用所学理论知识独立分析和解决问题的能力。 关键字：哈夫曼；信源编码；MATLAB
目录 1设计目的及相关知识 (1) 1.1设计目的 (1) 1.2图像的霍夫曼编码概念 (1) 1.3Matlab图像处理通用函数 (1) 2课程设计分析 (3) 2.1 图像的霍夫曼编码概述 (3) 2.2 图像的霍夫曼编码举例 (4) 3仿真 (6) 4结果及分析 (9) 5附录 (12) 结束语 (15) 参考文献 (16)
1设计目的及相关知识 1.1设计目的 1）了解霍夫曼编码的原理。 2）理解图像的霍夫曼编码原理，了解其应用，掌握图像的霍夫曼编码的方法。3）对图像编码程序设计进行较深入的认识，对知识牢固掌握。 4）掌握图像霍夫曼编码的整个过程及其中的注意事项。 5）了解图像无损压缩的目的及好处。 1.2图像的霍夫曼编码概念 所谓霍夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”，将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码 1.3 Matlab图像处理通用函数 colorbar 显示彩色条 语法：colorbar \ colorbar('vert') \ colorbar('horiz') \ colorbar(h) \ h=colorbar(...) \ colorbar(...,'peer',axes_handle) getimage从坐标轴取得图像数据 语法：A=getimage(h) \ [x,y,A]=getimage(h) \ [...,A,flag]=getimage(h) \ [...]=getimage imshow显示图像 语法：imshow(I,n) \ imshow(I,[low high]) \ imshow(BW) \ imshow(X,map) \ imshow(RGB)\ imshow(...,display_option) \ imshow(x,y,A,...) \ imshow filename \ h=imshow(...) montage 在矩形框中同时显示多幅图像 语法：montage(I) \ montage(BW) \ montage(X,map) \ montage(RGB) \ h=montage(...)
霍夫曼编码
以下是Huffman编码原理简介： 霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。 对于学多媒体的同学来说，需要知道Huffman编码过程的几个步骤： l）将信号源的符号按照出现概率递减的顺序排列。（注意，一定要递减） 2）将最下面的两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。 3）重复进行步骤1和2直到概率相加的结果等于1为止。 4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。 5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。 下面我举个简单例子: 一串信号源S＝{s1,s2,s3,s4,s5}对应概率为p＝{40，30，15，10，5}，（百分率） 按照递减的格式排列概率后，根据第二步，会得到一个新的概率列表，依然按照递减排列，注意：如果遇到相同概率，合并后的概率放在下面！ 最后概率最大的编码为0，最小的编码为1。如图所示： 所以，编码结果为 s1=1 s2=00 s3=010 s4=0110 s5=0111 霍夫曼编码具有如下特点： 1) 编出来的码都是异字头码，保证了码的唯一可译性。 2) 由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。 3) 编码长度不统一，硬件实现有难度。 4) 对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100％的编码效率；若信号源符号的概率相等，则编码效率最低。 5) 由于0与1的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。
图像压缩编码
多媒体技术实验—图像压缩编码 一、实验目的 1.了解有关数字图像压缩的基本概念，了解几种常用的图像压缩编码方式； 2.进一步熟悉JPEG编码与离散余弦变换（DCT）变换的原理及含义； 3.掌握编程实现离散余弦变换（DCT）变换及JPEG编码的方法； 4.对重建图像的质量进行评价。 二、实验原理 1、图像压缩基本概念及原理 图像压缩主要目的是为了节省存储空间，增加传输速度。图像压缩的理想标准是信息丢失最少，压缩比例最大。不损失图像质量的压缩称为无损压缩，无损压缩不可能达到很高的压缩比；损失图像质量的压缩称为有损压缩，高的压缩比是以牺牲图像质量为代价的。压缩的实现方法是对图像重新进行编码，希望用更少的数据表示图像。应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分为以下3类： (1)无损压缩编码种类 哈夫曼（Huffman）编码，算术编码，行程（RLE）编码，Lempel zev编码。(2)有损压缩编码种类 预测编码，DPCM，运动补偿； 频率域方法：正交变换编码(如DCT)，子带编码； 空间域方法：统计分块编码； 模型方法：分形编码，模型基编码； 基于重要性：滤波，子采样，比特分配，向量量化； (3)混合编码 JBIG，H.261，JPEG，MPEG等技术标准。 2、JPEG 压缩编码原理 JPEG是一个应用广泛的静态图像数据压缩标准，其中包含两种压缩算法(DCT 和DPCM)，并考虑了人眼的视觉特性，在量化和无损压缩编码方面综合权衡，达到较大的压缩比(25:1以上)。JPEG既适用于灰度图像也适用于彩色图像。其
中最常用的是基于DCT变换的顺序式模式，又称为基本系统。JPEG 的压缩编码大致分成三个步骤： (1)使用正向离散余弦变换(forward discrete cosine transform，FDCT)把空间域表示的图变换成频率域表示的图。 (2)使用加权函数对DCT系数进行量化，该加权函数使得压缩效果对于人的视觉系统最佳。 (3)使用霍夫曼可变字长编码器对量化系数进行编码。 3、离散余弦变换（DCT）变换原理 离散余弦变换（DCT）是一种实数域变换，其变换核为实数余弦函数，图像处理运用的是二维离散余弦变换，对图像进行DCT，可以使得图像的重要可视信息都集中在DCT的一小部分系数中。二维DCT变换是在一维的基础上再进行一次DCT变换，公式如下： 11 (0.5)(0.5) (,)()()(,)cos cos () N N i j i j F u v c u c v f i j u v N N u c u u ππ == ++ ???? =???? ???? = = ≠ ∑∑ (1) f为原图像，经DCT 变换之后，F为变换矩阵。(0,0) F是直流分量，其他为交流分量。上述公式可表示为矩阵形式： (0.5) (,)()cos T F AfA j A i j c i i N π = + ?? =?? ?? (2) 其中A是变换系数矩阵，为正交阵。 逆DCT 变换： (,)(,) T f i j A F u v A = (3) 这里我们只讨论两个N相等的情况，即图像为方形(行列数相等)，在实际应用中对不是方阵的数据都应先补齐再进行变换的。 4、图象质量评价 保真度准则是压缩后图象质量评价的标准。客观保真度准则：原图象和压缩图象