范氏哈夫曼编码在图像压缩中的应用

宦晖

关键词：图像压缩；哈夫曼编码；范氏哈夫曼编码

1引言

近年来，图像压缩技术快速发展，各种新技术得以应用。但哈夫曼编码作为一种传统的基础算法[1-2]，一直在图像压缩技术中占有重要地位。

哈夫曼编码基于数据的统计特性，可以实现无损的图像压缩与解压缩。范氏哈夫曼编码是对传统哈夫曼编码的优化改进，通过对编码规则约定限制，能更加高效地对哈夫曼树进行编码，减少编解码过程所消耗的计算资源与存储空间。

对范氏哈夫曼编码在图像压缩中的实际效果进行验证分析，是本文研究的出发点。通过对多组24位BMP图像文件以及不同格式的BMP图像文件进行压缩与解压缩，并对最终的压缩效率进行对比，以得出相关结论。

2哈夫曼编码

哈夫曼编码是基于数据源的统计特性建立哈夫曼树，再进行编码的算法。建立哈夫曼树是一个循环迭代的过程，每一步骤中的工作过程相同，具体过程为：编码器获取所有符号（ Symbol）的统计频率，并将所有符号放置在一个集合中：从集合中选取统计频率最低的两个符号作为节点，并创建一个新的内部节点且放回集合中，原来的两个节点被新创建的节点代替，新创建节点的统计频率为所选两个节点的统计频率之和：将所选的两个节点与新创建节点构成一个最小二叉樹。如此不断地循环迭代，直到集合中只剩下一个节点（根节点），此时哈夫曼树构建完成。

哈夫曼编码压缩后的数据量等于哈夫曼树带权路径长度（Weighted Path Length，WPL）。哈夫曼树的带权路径长度指的是所有节点的带权路径长度之和。n个编码长度为Li（i=1，2，…，n）的叶节点的哈夫曼树的带权路径长度为：

哈夫曼树是带权路径长度最小的二叉树，是最优二叉树。在哈夫曼编码表的结构中，每一棵最小二叉树的左右子节点位置是随机的，如果将哈夫曼树中的任意一个最小二叉树的左右节点位置互换，只会导致某些字符的具体编码改变，但整个哈夫曼树的带权路径总长度并不会发生变化，也不会影响哈夫曼编码的压缩率。如果能约定规则，限制哈夫曼树中的最小二叉树左右节点位置的不确定性，则表明哈夫曼树所需的数据量可以有效降低。另外，传统的哈夫曼编码是通过将出现频率较高的符号以较短编码，从而提高压缩率。但该方法有两大缺点：首先，每一个树节点都要储存其父节点与子节点等相关信息，符号集合包含很多不同概率的符号，其数量越多，对应存储空间将会增加越多；其次，哈夫曼树的跟踪和维护需要消耗非常大的计算资源。由于这两个原因，传统哈夫曼编码在储存空间以及计算效率上都需要提升、优化。

3范氏哈夫曼编码

范氏哈夫曼编码（Canonical Huffman Code）是施瓦兹（SCHWARTZ E S）提出的[4]，对传统哈夫曼编码进行优化的算法，通过对符号和编码的下列三个数字序列属性进行编码规则约定限制，从而可以更加高效地对哈夫曼树进行编码。

范氏哈夫曼编码约束规则如下。

（1）具有相同哈夫曼编码长度的符号编码是连续二进制整数，对应原码的值越小，则对应哈夫曼编码也越小。

（2）编码长度为i的第一个符号的编码H（i）与长度为i-l的最后～个符号的编码H（i-l）的关系满足以下公式：

该约束公式的含义是，长度为i第一个符号的编码，是将长度为i-l的最后一个符号的编码进行左移一位并补零。

（3）哈夫曼编码长度最小的第一个符号从0开始。第一个符号的编码方式是依照符号的编码长度分配相同长度的“0”值。

根据以上三个约束规则，可按顺序为确定了长度的每个符号分配唯一可译码（unique decodable code）。如此，就把存储整个哈夫曼树编码表的任务简化为存储每个符号编码长度的任务。

范氏霍夫曼编码要求相同长度编码必须是连续的[5]：为尽可能减小储存空间，编码长度为i的第一个符号可以从编码长度为i-1的最后一个符号所获得。另外，最小编码长度的第一个编码必须从0开始。范氏哈夫曼编码通过其约束规则，可以根据每个符号的长度，按照范氏哈夫曼编码的规则重构出整个编码表。

在图像数据的压缩过程中，应实现两方面的最小化，即存储编码表和哈夫曼树的存储空间最小化：编解码过程所消耗的计算资源的最小化。范式哈夫曼编码技术能同时满足这两方面的需求，比传统的哈夫曼编码技术更加有效[6]。

4对位图文件进行压缩、解压缩

在本文研究中，以范氏哈夫曼编码取代传统哈夫曼编码，对BMP图像文件进行压缩与解压缩，并观察实际的压缩效率。

BMP是位图（Bit Map）的简称，是未实行压缩处理的原始图像，存储格式是位映射。在Windows操作系统自带的画图软件中可按单色、16色、256色、24位四种格式保存BMP图像。BMP图像主要有三个特点：一是格式简单：二是图像信息量丰富：三是存储时所占用的内存较大。BMP图像由四部分组成，如表1所列。

传统哈夫曼编码必须保存哈夫曼树，本文研究中采用静态数组实现哈夫曼树的构建，哈夫曼树节点包括权值、父节点、左右子节点，数据结构如下所示：

与传统哈夫曼编码相比，范式哈夫曼编码节省了保存哈夫曼树本身所需的数据量。

本文研究中的图像压缩解压缩程序采用C++语言编写，在CPU为Intel Core i5-102IOU，RAM为16CB的个人计算机上运行。

该程序的流程图如图1所示。

以24位位图为样本，对多组24位位图进行测试，并选取三组不同压缩效果的测试结果进行对比，如表2所列。

对于不同内容的图像，压缩率会根据内容而变化，这与图像数据的统计特性有关[7]。统计上冗余信息较多的图像，压缩率较高。

在本文研究中，针对同一幅图像，转换为四种BMP格式，分别为单色位图、16色位图、256色位图、24位位图，然后进行压缩与解压测试，相应的测试数据如表3所列。

对同一幅图像的不同位图格式的压缩率进行对比，程序对单色位图的压缩效果最好，对16色位图的压缩效果也较为理想，对256色位图也有较高的压缩率，而对24位位图的压缩效果最差。

就压缩耗时与解压耗时而言，对于字节长度较小的文件，压缩耗时比解压耗时长；对于字节长度较大的文件，压缩耗时比解压耗时短。

5结束语

本文研究使用范式哈夫曼编码对BMP图像进行压缩处理，并得到相关测试数据。在相关程序的哈夫曼编码过程中，判断图像是否全部出现256个颜色像素点后，仅让有权值的像素点作为哈夫曼树的叶结点，未出现的像素点不涉及哈夫曼树的构建，由此可提高哈夫曼编码的压缩效率。由程序测试结果可知，属于无损压缩算法的范氏哈夫曼编码的确能够很好地无失真还原图像压缩文件。

在使用范氏哈夫曼编码进行图像压缩的过程中，硬件平台对于软件算法上也有影响，可以针对不同硬件平台的数据吞吐量和缓存资源来改进和优化算法。