> 操作系统 > 正文
简单介绍哈夫曼图像压缩算法 随着网络与多媒体技术的兴起，人们需要存储和传输的数据越来越多，数据量越来越大，以前带宽有限的传输网络和容量有限的存储介质难以满足用户的需求。
1.哈夫曼图像压缩算法引言 随着网络与多媒体技术的兴起，人们需要存储和传输的数据越来越多，数据量越来越大，以前带宽有限的传输网络和容量有限的存储介质难以满足用户的需求。 特别是声音、图像和视频等媒体在人们的日常生活和工作中的地位日益突出，这个问题越发显得严重和迫切。如今，数据压缩技术早已是多媒体领域中的关键技术之一。 Huffman(哈夫曼)算法在上世纪五十年代初提出来了，它是一种无损压缩方法，在压缩过程中不会丢失信息熵，而且可以证明Huffman算法在无损压缩算法中是最优的。Huffman原理简单，实现起来也不困难，在现在的主流压缩软件得到了广泛的应用。对应用程序、重要资料等绝对不允许信息丢失的压缩场合，Huffman算法是非常好的选择。 2.哈夫曼图像压缩算法原理 Huffman编码是1952年由Huffman提出的对统计独立信源能达到最小平均码长的编码方法。这一年，他发表了著名论文“A Method for the Construction of Minimum Redundancy Codes”，即最短冗余码的构造方法.之后，Huffman编码及其一些改进方法一直是数据压缩领域的研究热点之一。 Huffman码是一种变长码，其基本思想是：先统计图像(已经数字化)中各灰度出现的概率，出现概率较大的赋以较短的码字，而出现概率较小的则赋以较长的码字。我们可以用下面的框图来表示Huffman编码的过程： 在整个编码过程中，统计图像各灰度级出现的概率和编码这两步都很简单，关键的是Huffman树的构造。不但编码的时候需要用到这颗树，解码的时候也必须有这颗树才能完成解码工作，因此，Huffman树还得完整的传输到解码端。 Huffman树的构造可以按照下面图2的流程图来完成。首先对统计出来的概率从小到大进行排序，然后将最小的两个概率相加;到这儿的时候，先把已经加过的两个概率作为树的两个节点，并把他们从概率队列中删除;然后把相加所得的新概率加入到队列中，对这个新队列进行排序。 如此反复，直到最后两个概率相加为1的时候停止。这样，Huffman树就建立起来了。 3. 哈夫曼图像压缩算法软件实现 这儿，我们以Turbo C为例来说明软件实现Huffman图像压缩算法的一些关键技术。 为了叙述方便，我们不妨假设处理的图像的灰度级变化范围从0到255，即具有256个灰度级。我们先来统计输入图像的概率，实际上是要统计各个灰度级在整幅图像中出现的次数。为此，我们先定义一个具有256个元素的数组。 然后对输入图像信号进行扫描，每出现一个灰度，就把它存入实现定义好的一个数组中的相应元素中(让这个元素的值自增1)。最后，通过读取数组中各元素的值就可以求出各个灰度出现的频数。 接下来就该构造Huffman树了。为了构造Huffman树，我们要用到C语言中链表的概念。我们必须用一个结构体来表示Huffman树的节点。对于每个节点而言我们需要这样几个信息：本节点的权重(就是灰度的频数)、指向父节点的指针和分别指向左右子叶节点的指针。于是，我们可以定义这样一个结构体： Struct Node{ Floatweight; Node * father; Node * left; Node * right;}Huffman_Node 我们需要先确定权最低的两个自由结点，这将是最初的left和right节点。然后建立这两个结点的父结点，并让它的权等于这两个结点的权之和。 接着将这个父结点增加到自由结点的序列中，而两个子结点则从序列中去掉。重复前面的步骤直到只剩下一个自由结点，这个自由结点就是Huffman树的根。 Huffman编码树作为一个二叉树从叶结点逐步向上建立。Huffman树建立好以后，为了把权、概率等数值转化码字，我们还得对整个Huffman树进行扫描。请注意，在建立Huffman树的时候，我们是从树叶开始的，而在对Huffman树分配码字的时候却刚好相反，是从树根开始，沿着各个树枝的走向“顺藤摸瓜”似的对各个系数进行编码。 对于一个节点的两个子节点(left和right)，其中一个节点对应的位为0，而另一个结点则人为地设置成为l。解码的时候也是完全相同的一颗Huffman树完成的。下面的循环是实现压缩的关键语句之一[ 1 ]。 for (i = length-1; i >= 0; DDi) { if ((current_code >> i) & 1) thebyte |= (char) (1 << curbit); if (--curbit < 0) { putc (thebyte, ofile); thebyte = 0; curbyte++; curbit = 7; } } 注意：这几行代码执行了数据压缩的功能，但是还没有生成编码和解码所需要的代码表。 4.哈夫曼图像压缩算法性能评价 我们主要从三方面[ 2 ]来评价Huffman的性能： (1)压缩比的大小; (2)恢复效果的好坏，也就是能否尽可能的恢复原始数据; (3)算法的简单易用性以及编、解码的速度。 首先分析一下对压缩比的影响因素(不同的著作中对压缩比的定义不尽相同，这儿我们采用如下定义：压缩比等于压缩之前的以比特计算的数据量比上压缩之后的数据量)。对于Huffman编码来说，我们因为要用额外的位保存和传输Huffman树而“浪费”掉一些存储位，也就是说，为了编、解码的方便，我们把本已减少的数据量又增加了一些。 如果文件比较大的话，这一点多余的数据根本算不了什么，所占比例很小。但是，如果压缩的文件本来就很小的话，那么这笔数据就很可观了。一般来说，经典的Huffman算法的压缩比不是很高，这是无损压缩的“通病”。 第二点就不用说了，由于它是无损压缩，能够完全恢复压缩之前图像的本来面貌。 最后，让我们来分析一下Huffman压缩方法的速度问题。大家在第三节中已经看到了，在压缩的过程中，我们进行了两次扫描，第一次是为了统计各个灰度出现的频数而扫描整幅图像，第二次则是为了分配码字而扫描整个Huffman树。 这样一来，对较大的文件进行编码时，频繁的磁盘读写访问必然会降低数据编码的速度，如果用于网络的话，还会因此带来一些延时，不利于实时压缩和传输。另外，Huffman算法的编码和解码的速度是不对称的，解码快于编码，因为解码不需要生成Huffman树的环节。 5.图像压缩算法结束语 Huffman算法目前已经得到了广泛的应用，软件和硬件都已经实现。基于Huffman经典算法的缺陷，不少人提出了一些自适应算法。前面的算法中，Huffman树是整个图像全部输入扫描完成后构造出来的，而自适应算法(或称动态算法)则不必等到全部图像输入完成才开始树的构造，并且可以根据后面输入的数据动态的对Huffman树进行调整。实际上，实用的Huffman树都是经过某种优化后的动态算法。
2009-10-14 14:51:28 来源： 编辑：中国软件网 作者： 评论：
相关热词搜索：哈夫曼图像压缩算法
