哈夫曼编码在图像压缩中的应用与分析

吕姣霖，徐 艳

（四川大学锦城学院计算机与软件学院，四川 成都 611731）

0 引言

在各个行业之间进行信息传输时，由于数据、图像的传输需要占据较大的信道容量，因此在数据、图像传输的过程中，会由于信道容量的大量被占用，导致网络卡顿。为了解决这一问题，研究出了文件压缩、图像压缩等方式，在对数据和图像进行传输之前，首先对其进行压缩，使其传输过程中只需要占用比较小的内存，在接收信息后，再对文件和图像等进行解压。本文所研究的重点是常用的图像压缩技术-哈夫曼编码，通过C++语言对编码算法进行实现，从而对图像压缩的相关技术进行研究，通过哈夫曼编码实现对图像的压缩和对比分析。

1 哈夫曼编码简介

哈夫曼编码出现于19世纪60年代，是国际有效的二进制编码之一，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，被认为是接近于压缩比上限的最佳编码方法之一[1]。哈夫曼编码是常用的编码方式，亦称为最佳编码、熵编码，适用于无损耗的数据压缩[2]。在使用哈夫曼编码实现对图像的压缩过程中，首先实现的是对图像中所分解出来的数据进行扫描，计算出图像上各个像素所出现的概率，并根据各个数据出现概率的不同，指定哈夫曼编码中的惟一码字与各个不同概率的像素一一对应，并将所有码字组成哈夫曼码表，在图像加压的过程中，可以通过压缩时所组成的哈夫曼码表的对应关系，实现源图像数据的还原。

2 哈夫曼编码实现图像压缩

2.1 哈夫曼编码实现图像压缩算法

本文以C++为基础语言，结合哈夫曼编码的思想，使编码符号与被压缩的图像数据一一对应，利用二叉树的构造方法，不断置新新的根节点，使得最终的数据编码由两个子节点和一个根节点构成，算法如下：

（1）定义哈夫曼树节点

哈夫曼树主要由一个根节点和两个子节点，一共三个节点构成，因此本次哈夫曼树类型的构建一共定义4个整型成员，分别表示树根节点、左节点、右节点和数量。

（2）构建哈夫曼树

按照哈夫曼树的构建步骤，按照出现概率的大小顺序对字符进行排序，将字符出现次数最少的两个节点构成哈夫曼树新的节点，使用循环，不断抽取排序中出现数量最少的节点，不断合并组成新节点，直到最后只剩下两组节点，构成最后的二叉树[3]。

（3）定义有关图片压缩的功能函数

结合哈夫曼树思想实现图片的压缩功能，通过对本次系统需要实现的功能进行分析，定义的函数需要实现创建哈夫曼树、递归、哈夫曼编码转换、计算字节长度、解析字符串、读取文件、读取图片、复制图片信息、写入图片等功能。

（4）主函数中调用定义的方法

在主函数中，首先输入图片的路径，读取出图片的信息，再将读取到的图片的信息进行哈夫曼编码转换，调用函数对转换后的编码进行排序，调用构建哈夫曼树函数，构建出与本次图片压缩相关的哈夫曼树[4]。最后调用解析函数，对数据进行解析，并将解析后的数据以压缩图的形式输出。

2.2 哈夫曼编码实现图像压缩关键代码

在哈夫曼树构建时，对已经排序的编码出现的数量进行比较，筛选出出现次数最少的字符，在排序长度之内对字符编码出现的次数进行比较，若当前比较的编码出现的次数小于当前编码出现的次数，将该编码赋值给当前标记编码。

在对哈夫曼编码进行处理时，主要调用递归函数中的方法，获取到图像数据所对应的编码表，并对哈夫曼树左右子节点相对应的编码进行递归，关键代码如下：

进行哈夫曼编码转换的流程为：先对读取图片所获得的数组进行初始化，再通过for 循环对哈夫曼树所需要的编码进行遍历，获取到图片对应的所有哈夫曼编码，对哈夫曼树左右两个子节点依次进行转换。

对创建哈夫曼树所需要的编码进行转换后，创建哈夫曼树，调用函数获取哈夫曼树编码表，对编码进行遍历，并将遍历得出的编码存储于编码表文件，关键代码如下：

在使图片数据与哈夫曼编码一一对应，创建好哈夫曼树后，打开文件，对哈夫曼编码表进行读取，解析哈夫曼编码中的文件内容。

解析哈夫曼编码中的文件内容后，读取图像压缩后的文件，并存储读取压缩文件后的信息，将图片压缩后的信息输出，关键代码如下：

2.3 图片压缩前后对比分析

在完成哈夫曼编码实现对图片压缩功能的程序部分后，用于测试的图像为如图1所示黑底背景的绿色水壶。

图1 测试图

图1所示测试图通过本次所设计的基于哈夫曼编码的图像压缩系统进行压缩后，得到压缩图。对测试图原图和压缩图进行比较后发现，压缩图与原图文件大小基本一致，且压缩图与原图相比，压缩图的外观形状、大小等特性与原图相同，可视清晰度也与原图相同。

3 结束语

本文以C++为系统开发的基础语言，以哈夫曼编码构成哈夫曼树，以及哈夫曼树逆向解码过程为本次图像压缩系统设计的思想，设计并完成了基于哈夫曼编码对图片压缩的功能。本文选用测试图对其核心的图片压缩功能进行了测试，测试图通过本次所设计系统压缩功能的压缩后，所得到的压缩图与原图文件大小基本一致，且视觉效果一致。通过对测试图原图与压缩图进行比较，确定本次所设计的图像压缩功能，具有无损压缩特性，在压缩的过程中，并不会存在数据的损坏与丢失。因此通过哈夫曼编码与哈夫曼原理所设计出的图像压缩系统，也是对需要压缩的图像的数据进行采集，并将采集后的数据通过哈夫曼编码进行一一转化，使编码符号与数字字符产生一一对应的关系，而不会因丢失图片的数据，导致图片的变形或受损[5]。