基于哈夫曼编码的图像压缩技术研究

2022-11-15

哈夫曼编码是一种常用的压缩编码算法, 采用变长码编码, 属于无损压缩算法的一种, 在无损压缩的编码范畴中, 哈夫曼 (Huffman) 编码方法是一种较有效的编码方法, 是哈夫曼在1952年根据香农在1948年和范若在1949年阐述的一种编码思想提出的一种不定长 (变长) 编码的方法, 也称霍夫曼编码。

哈夫曼编码在图像压缩应用中具有非常重要的意义, 哈夫曼编码是一种实用的无损压缩技术, 经过多年的不断改进, 已经形成了系统的理论和方法。目前主要有两种类型的哈夫曼编码方式, 即静态哈夫曼编码和动态哈夫曼编码。

图像压缩编码技术可以追溯到1948年提出的电视信号数字化, 到今天已经有60多年的历史了。在此期间出现了很多种图像压缩编码方法, 本课题主要研究基于哈夫曼编码对图像进行无损压缩, 基于哈夫曼编码的图像无损压缩过程通常分为两步, 即去除相关和编码。去除相关就是要去除图像数据的冗余部分, 降低信源熵, 这是对图像数据的压缩过程;编码就是对去除冗余后的图像数据重新用一种新的符号编码代替, 这也是对图像数据的重编码进行存储的过程。

1 哈夫曼编码原理

1.1 理论基础

为了节省空间, 在对数据进行编码时, 可以对那些经常出现的数据指定较少的位数表示, 而那些不常出现的数据指定较多的位数表示, 从而降低冗余, 这样从总的效果看就节省了存储空间。

基于哈夫曼编码图像压缩的基本原理是频繁使用的数据用较短的代码代替, 较少使用的数据用较长的代码代替, 每个数据的代码各不相同, 这是一种典型的无损编码方式。这些代码都是二进制码, 且码字长度是不均匀的、平均码率可以接近信息源熵值的一种编码。编码过程是先对图像数据扫描一遍, 计算出各种像素出现的概率, 按概率的大小建立最优二叉树 (二叉树的叶子节点刚好表示的图像中的某种像素) 并给二叉树的每个分支赋特定权值 (0或1) , 然后通过遍历二叉树读取从根节点到叶子节点的路径权值字符串, 即给每种像素指定了不同长度的唯一编码, 由此得到一张该图像所有像素的哈夫曼编码表。编码后的图像数据记录的是每个像素的码字, 而码字与实际像素值的对应关系记录在码表中, 码表是附在图像文件中的。

基于哈夫曼编码图像压缩技术借用了热力学中的名词“熵” (Entropy) 来表示一条信息中真正需要编码的信息量:如考虑用0和1组成的二进制数码为含有n个符号的某条信息编码, 假设符号En在整条信息中重复出现的概率为Pn, 则该符号的熵也即表示该符号所需的位数为:En=-log2 (Pn) , 整条信息的熵也即表示整条信息所需的位数:E=ΣEn。

1.2 编码具体过程

1.2.1 建立最优二叉树的过程

(1) 如下图所示, 在每个结点上标出信源字母的概率Pj, 1≤j≤8。

(2) 找出两个具有最小概率的节点, 在本例中是0.01和0.04, 把它们放在同一个父节点的两个字节点上。

(3) 在其父结点上标出子节点的概率之和, 如图所示, 应是0.01+0.04=0.05。进行下一轮找最小概率节点, 由于这个父节点代表了原来的两个节点, 因此现在只考虑7个节点。

(4) 在这7个节点中还没有产生父节点, 在其中找两个最小概率的, 这里是0.05和0.05, 把它们放在同一个父节点的两个子节点上, 并在其父节点上标上子节点的概率之和0.05+0.05=0.1。

(5) 继续这样的合并, 每一步都将两个节点合并到一个父节点之下, 对于两个概率相同的可以任意挑选一个, 直到形成的父节点为1为止, 此节点即为根节点。

1.2.2 编码过程

分别给建成的最优二叉树中每个节点的左右分支分别标0和1, 作为权值, 这样, 从根节点到每一个叶子节点有一条唯一的路径, 读出每条路径上的权值就会产生一个对应节点的唯一码字。如图1所示, 二叉树左右分支的0、1标号并不是确定的, 本例中左分支是1, 右分支是0, 也可以相反, 如图2所示。

上面这两种Huffman编码方式的平均码长分别为:

可见, 尽管这两种编码设定不同, 但它们都有相同的平均码长, 要真正实现压缩还得对新的编码进行按位存储。

2 哈夫曼编码具体实施

2.1 压缩思想

由于进行的是无损压缩, 所以要扫描图像的所有像素点, 压缩过程分为四步:①扫描统计像素出现的概率并按大小排列;②建立最优二叉树;③哈夫曼编码;④保存编码。

经过哈夫曼编码后的图像中的不同像素分别用不同长度二进制编码表示, 接下来的工作就是保存重编码后的像素, 由于无损压缩中编码前后一幅图像的像素点数是相同的, 如果仍然以像素为单位保存图像数据就无法实现压缩功能, 能够实现压缩是因为编码前后表示像素的二进制编码的位数有所变化, 所以, 应该对重编码后的二进制位按位存储, 由于VB6.0中没有移位运算, 但是可以通过乘2、除2操作实现左移、右移。当编码结束后, 各像素的哈夫曼编码存放在hufbm (1 to 256) 中, 在保存时, 把所有像素的哈夫曼编码连成一串, 然后每8位 (字节) 转换为整型数据, 存储的是转换后的整型数据。

2.2 解压思想

压缩文件的文件结构如表1在文件头部分可利用像素与文件头的偏移量距离位置计算文件头和全表的长度, 从而得到哈夫曼编码树的起始位置。

解码过程:

(1) 指向huffman树的树根。

(2) 根据当前一位编码为0或1从而指向左或右儿子节点。

(3) 判断该节点的左, 右儿子是否是空 (即为0) 不是则向后扫描一个编码, 执行上一步, 如是则完成一个解码, 该叶子节点的数组下标即为像素值, 继续解下一个。

在解码过程中需要把按位存储的编码读取出来, 这个过程就是按位读取, 由于压缩的文件长度大多小于30K, 那么编码部分必将小于30K, VB6.0中字符型 (string) 的变量最长可达65535个字符, 所以可将编码部分一次性读取, 构造一个自定义函数dtoo (s as byte) , 该函数的功能是将byte型的变量转变成8位二进制数。

至此, 关于哈夫曼编码的几个重要模块的实现算法已经介绍完, 通过模块测试都能达到预期效果, 把这几个模块集成即可形成一个基于哈夫曼编码的图像压缩系统 (其中使用了一些用户自定义类型、变量和关于图像的信息的常量, 都在程序的公用模块中有定义) 。

3 结语

图像压缩技术, 是当前很热门和实用的信息技术, 图像压缩技术研究了几十年, 取得了很大的成绩, 但还有许多不足, 值得我们进一步研究。Huffman编码压缩作为一种简单高效的编码方法, 在文本, 图像, 音频等压缩技术中都有着广泛的应用。从整个课题中可以看到, Huffman编码算法只对图像压缩一次, 要想提高压缩比, 可以对图像进行两次压缩或多次压缩。另外, 还可以与人眼视觉特性相结合实现有损压缩。总之, 图像压缩是一个非常有发展前途的研究领域, 这一领域的突破对于我们的信息生活和通信事业的发展有着深远的意义。

摘要：哈夫曼编码是一种数据编码方式, 以哈夫曼树——即最优二叉树, 用带权路径长度最小的二叉树, 对数据进行重编码, 经常应用于数据压缩。在计算机信息处理中, “哈夫曼编码”是一种一致性编码法 (又称“熵编码法”) , 用于数据的无损压缩。本文主要介绍了基于哈夫曼编码图像压缩技术的原理、算法、过程, 并利用VB6.0作为编程开发工具, 开发了一个对256色BMP图像进行压缩/解压缩的软件系统, 验证了算法的合理性和可行性。

关键词：哈夫曼编码,二叉树,熵,无损压缩