Huffman编码

《信息论与信源编码》实验报告

1、实验目的

(1) 理解信源编码的基本原理；

(2) 熟练掌握Huffman编码的方法；

(3) 理解无失真信源编码和限失真编码方法在实际图像信源编码应用中的差异。

2、实验设备与软件

(1) PC计算机系统

(2) VC++6.0语言编程环境

(3) 基于VC++6.0的图像处理实验基本程序框架imageprocessing_S

(4) 常用图像浏览编辑软件Acdsee和数据压缩软件winrar。

(5) 实验所需要的bmp格式图像（灰度图象若干幅）

3、实验内容与步骤

(1) 针对“图像1.bmp”、“图像2.bmp”和“图像3.bmp”进行灰度频率统计（即计算图像灰度直方图），在此基础上添加函数代码构造Huffman码表，针对图像数据进行Huffman编码，观察和分析不同图像信源的编码效率和压缩比。

(2) 利用图像处理软件Acdsee将“图像1.bmp”、“图像2.bmp”和“图像

3.bmp”转换为质量因子为10、50、90的JPG格式图像（共生成9幅JPG图像），比较图像格式转换前后数据量的差异，比较不同品质因素对图像质量的影响；

(3) 数据压缩软件winrar将“图像1.bmp”、“图像2.bmp”和“图像3.bmp”分别生成压缩包文件，观察和分析压缩前后数据量的差异；

(4) 针对任意一幅图像，比较原始BMP图像数据量、Huffman编码后的数据量（不含码表）、品质因素分别为10、50、90时的JPG文件数据量和rar压缩包的数据量，分析不同编码方案下图像数据量变化的原因。

4、 实验结果及分析

(1)在VC环境下，添加代码构造Huffman编码表，对比试验结果如下：

a.图像1.bmp：

图1 图像1.bmp

图像的像素点个数共640×480个，原图像大小为301KB，图像信息熵为

5.92bit/符号，通过Huffman编码后，其编码后的平均码长为5.960码元/信源符号，编码效率为99.468%，编码后的图像大小为228.871KB，压缩比为1.342。

b.图像2.bmp：

图2 图像2.bmp

图像的像素点个数共640×480个，原图像大小为301KB，图像信息熵为

4.410bit/符号，通过Huffman编码后，其编码后的平均码长为4.444码元/信源符号，编码效率为99.237%，编码后的图像大小为170.634KB，压缩比为1.800。

c.图像3.bmp：

图3 图像3.bmp

图像的像素点个数共640×480个，原图像大小为301KB，图像信息熵为

6.709bit/符号，通过Huffman编码后，其编码后的平均码长为6.734码元/信源符号，编码效率为99.628%，编码后的图像大小为258.572KB，压缩比为1.188。

(2)Acdsee处理图像结果对比

a.图像1.bmp

利用Acdsee处理，质量因子分别取10、50、90，所得结果如下所示：

图4.原始BMP图像（301KB） 图5.质量因子为10的JPEG图像

(34KB)

图6.质量因子为50的JPEG图像(52KB) 图7.质量因子为90的JPEG图像(141KB)

b.图像2.bmp

利用Acdsee处理，质量因子分别取10、50、90，所得结果如下所示：

图8.原始BMP图像（301KB） 图9.质量因子为10的JPEG图像(32KB)

图10.质量因子为50的JPEG图像(48KB) 图11.质量因子为90的JPEG图像(113KB)

c.图像3.bmp

利用Acdsee处理，质量因子分别取10、50、90，所得结果如下所示：

图12.原始BMP图像（301KB） 图13.质量因子为10的JPEG图像(47KB)

图14.质量因子为50的JPEG图像(52KB) 图15.质量因子为90的JPEG图像(113KB)

通过人眼对这3组图进行观察对比，每组图像几乎一样，觉察不出有什么不同，但是将这3组幅图像的大小进行对比可以发现BMP格式的图片数据量最大，JPEG格式的图片数据量都比较小，其中质量因子越小，大小也越小，这正是限失真信源编码的基本应用，实现了高效的数据压缩，。

(3)用winrar压缩三幅图像

通过winrar压缩压缩这三幅图像，压缩后文件大小分别为147KB、123KB、217KB，数据压缩比为2.06、2.46、1.39。

因为这三幅图像的熵不一样，也就是说灰度直方图也不一样，这也代表了三副图的可压缩的程度，熵越小，可压缩的程度越大，其中图像2的熵最小，灰度分布最不均匀，所以压缩比最大。图像3的熵最大，灰度分布比较均匀，所以压缩比最小。

(4)数据量对比

针对第一幅图：

原始BMP图像数据量：301KB Huffman编码后的数据量（不含码表）:229KB 品质因素分别为10、50、90时的JPG文件数据量:32KB,54KB,141KB

rar压缩包的数据量:147KB

从中可以看出JPG的压缩程度最大，RAR次之，Huffman编码最小

分析：

a.Huffman编码采用统计编码

统计编码也称为熵编码，它是一类根据信息熵原理进行的信息保持型变字长编码。编码时对出现概率高的事件（被编码的符号）用短码表示，对出现概率低的事件用长码表示。是用无损的方式做压缩。

b.JPEG压缩原理

JPEG 是 Joint Photographic Experts Group 的缩写，即 ISO 和 IEC 联合图像专家组，负责静态图像压缩标准的制定，这个专家组开发的算法就被称为 JPEG 算法，并且已经成为了大家通用的标准，即 JPEG 标准。 JPEG 压缩是有损压缩，但这个损失的部分是人的视觉不容易察觉到的部分，它充分利用了人眼对计算机色彩中的高频信息部分不敏感的特点，相对于Huffman编码来说，大大节省了需要处理的数据信息。它主要包括两个步骤：

去除视觉上的多余信息，即空间冗余度

去除数据本身的多余信息，即结构（静态）冗余度

c. RAR压缩原理

RAR采用字典压缩技术，也是应用最为广泛的一种压缩技术。该技术搜索文件中重复出现的字符串，如“中华人民共和国”、“改革开放”等，记录后（记录后的内容被称为“字典”）在正文中使用另一个简短的编码来代替它。所以相对于Huffman编码来说压缩程度高，而比JPEG这种有损压缩低。

4.实验体会

这次实验虽然时间比较匆忙，但在教员的讲解下与自己的努力下，对信源编码的基本原理有了较为深刻的认识。信源编码是以提高信息传输的有效性为目的的，通常通过压缩信源的冗余度来实现。采用的方法一般是压缩每个信源符号的平均比特数或信源码率，使传输同样多的信息能用较少的码率来实现，从而使单位时间内传送的平均信息量增加。

这次实验主要实现了Huffman编码，霍夫曼码是一种效率比较高的变长、无失真信源编码方法。首先介绍二进制霍夫曼码的方法，其编码步骤如下：

（1）将信源符号按概率从大到小的顺序排列，为方便起见，令

p(x1)≥p(x2)≥ ≥p(xn)

（2）给两个概率最小的信源符号p(xn-1) 和p(xn)各分配一个码位“0”和“1”，

将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。

（3）将缩减信源S1的符号仍按概率从大到小的顺序排列，重复步骤2，得到只含(n－2)个符号的缩减信源。

（4）重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字

通过Huffman编码和JPEG压缩后的图像对比，可以看出无失真信源编码 和限失真编码方法在压缩性能上的差异以及图像感官上的差异。Huffman编码是无失真信源编码的一种典型应用，它产生的是最优码，编码时对出现概率高的事件（被编码的符号）用短码表示，对出现概率低的事件用长码表示，用无损的方式进行压缩。而JPEG是有损压缩，但这个损失的部分是人的视觉不容易察觉到的部分，它是限失真编码方法的一种典型应用，充分利用了人眼对计算机色

彩中的高频信息部分不敏感的特点。相对于Huffman编码来说，JPEG和WINRAR大大节省了需要处理的数据信息。

5.课程体会

本课程主要讨论Shannon信息理论中的基本概念和问题，了解了信息理论的主要研究内容、发展历史、和现状。对两个最重要的基本概念即信息熵和互信息的定义与性质有了深刻的了解，知道了平均互信息与信源概率分布和信道转移概率分布的凸性关系。

实际的信源总是或多或少地存在冗余，往往不能直接满足高效率传输信息的要求。为了实现信息的高效率传输，需要对信源产生冗余的原因进行分析，在此基础上对信源进行针对性的改造，使信源原有的信息含量从效率不高的情形转变为较高或尽可能高的情形，做到单位时间或单位符号所传输的信息量尽可能大。

本节通过对离散无记忆平稳信源及其扩展信源、离散有记忆平稳信源和马尔可夫信源三种典型信源的讨论，分析信源产生冗余的基本原因，知道了信息冗余的产生与信息符号的不等概和信源符号之间的相关性有关，并提出对信源进行编码改造，提高信息传输有效性的基本思路。

一般来说，提高抗干扰能力（降低失真或错误概率）往往是以降低信息传输率为代价的；反之，要提高信息传输率，又常常会使抗干扰能力减弱。因此，提高抗干扰能力和提高信息传输率是相矛盾的。然而，在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息。所以着重讨论了对离散信源进行无失真信源编码的要求、方法及理论极限，对变长编码基本方法霍夫曼编码和香农—范诺编码有了基本了解，并得出一个重要的极限定理——香农第一定理。依据互信息的下凸性关系和失真度量方法，讨论了信息率失真函数的定义和性质，阐述了限失真信源编码定理，并介绍了限失真信源编码的基本定理与方法，对预测编码和正交变换法有了一定的了解。

虽然我们只学习了十个星期的课程，但对信源编码有了深刻的了解，对信源编码的模型有了构架，这些都是在许教员的悉心教导下才有的，祝福教员合家快乐。

6.研讨课体会

我们小组被分配了关于互信息的课题，面对十来篇的文章，我们进行了大概的浏览，最终确定了《基于互信息的中文姓名识别方法》这篇作为我们的主要文

章。确定了文章后，我们把文章仔细阅读了两遍，又到网上搜索相关的文章，进行了仔细比较，在两者讲述相当概念时，我们选择了能较好被大家理解的讲法，以中文姓名识别的流程作为我们讲述的流程，一步一步的讲述步骤，并在这之中引入了上下文互信息与内部互信息，以及上下文互信息评价函数和姓名内部互信息的评价函数，并处理了交叉的潜在姓名，使我们对中文姓名识别有了较深的理解。

当然我也听了其他小组讲的内容，对于课程知识的应用领域有了很大的了解，对于信源编码的了解也更近了一步，对交叉熵、最大熵，互信息的的各种形式都有了了解。

这次研讨课让我知道了如何对一篇文章进行快速深刻的了解并转换为自己的知识的方法，并锻炼了我如何搜索文献的能力。总之，这次研讨课让我受益匪浅，希望以后还有机会的话能再进行。