数字图像处理探索霍夫曼编码.docx

探索霍夫曼编码
一、绪论
在学习完了本学期的数字图像处理课程后，我对图像压缩这部分内容产生了兴趣，通过深入学习，我用matlab实现了霍夫曼编码，成功地压缩了图像。
随着信息时代的来临，多媒体已经被人们广泛的应用于生活的各个领域。我们每天接受的信息开始以Gb计，众所周知Gb是一个很大的单位，多媒体是指文字、声音、图形和图像等各种媒体，它能比单纯文字传输更多、更生动的信息，与此同时它的数据量也比文字要大得多，例如一幅分辨率为1024×768、颜色24位的图像将占到2.3MB的存储空间，1秒钟没有任何压缩的数字视频图像需要上百兆字节的存储空间，这是目前的存储空间和传输宽带不能承受的。采用数据压缩技术去除不必要的冗余数据以减少所需传输的数据量是必然的选择。而我正是对如何编码使图像压缩而不至于影响人的体验产生兴趣的。
上课时我了解到图像数据存在3种冗余：结构冗余、统计冗余、以及心里视觉冗余。通过上网搜寻资料我也了解到编码也是分3种的：统计编码、预测编码，以及变换编码。我主要深入学习了用统计编码的方法来去除统计冗余。
二、霍夫曼编码概述
赫夫曼（Huffman）编码是1952年提出的，是一种比较经典的信息无损熵编码，该编码依据变长最佳编码定理，应用Huffman算法而产生。Huffman编码是一种基于统计的无损编码。
根据变长最佳编码定理，Huffman编码步骤如下：
（1）将信源符号xi按其出现的概率，由大到小顺序排列。
（2）将两个最小的概率的信源符号进行组合相加，并重复这一步骤，始终将较大的概率分支放在上部，直到只剩下一个信源符号且概率达到1.0为止；
（3）对每对组合的上边一个指定为1，下边一个指定为0（或相反：对上边一个指定为0，下边一个指定为1）；
（4）画出由每个信源符号到概率1.0处的路径，记下沿路径的1和0；
（5）对于每个信源符号都写出1、0序列，则从右到左就得到非等长的Huffman码。
Huffman编码的特点是：
（1）Huffman编码构造程序是明确的，但编出的码不是唯一的，其原因之一是两个概率分配码字“0”和“1”是任意选择的（大概率为“0”，小概率为“1”，或者反之）。第二原因是在排序过程中两个概率相等，谁前谁后也是随机的。这样编出的码字就不是唯一的。
（2）Huffman编码结果，码字不等长，平均码字最短，效率最高，但码字长短不一，实时硬件实现很复杂（特别是译码），而且在抗误码能力方面也比较差。
（3）Huffman编码的信源概率是2的负幂时，效率达100%，但是对等概率分布的信源，产生定长码，效率最低，因此编码效率与信源符号概率分布相关，故Huffman编码依赖于信源统计特性，编码前必须有信源这方面的先验知识，这往往限制了霍夫曼编码的应用。
（4）Huffman编码只能用近似的整数位来表示单个符号，而不是理想的小数，这也是Huffman编码无法达到最理想的压缩效果的原因
假设一个文件中出现了8种符号S0，S1，S2，S3，S4，S5，S6，S7，那么每种符号要编码，至少需要3比特。假设编码成000，001，010，011，100，101，110，111那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成，共用了42比特。我们发现S0，S1，S2这三个符号出现的频率比较大，其它符号出现的频率比较小，如果我们采用一种编码方案使得S0，S1，S2的码字短，其它符号的码字长，这样就能够减少占用的比特数。例如，我们采用这样的编码方案：S0到S7的码字分别01，11，101，0000，0001，0010，0011，100，那么上述符号序列变成，共用了39比特，尽管有些码字如S3，S4，S5，S6变长了(由3位变成4位)，但使用频繁的几个码字如S0，S1变短了，所以实现了压缩。
可由下面的步骤得到霍夫曼码的码表
首先把信源中的消息出现的频率从小到大排列。
每一次选出频率最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。
重复(2)，直到最后得到和为1的根节点。
将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0，1序列串起来，就得到了各个符号的编码。
上面的例子用Huffman编码的过程如图下图所示，其中圆圈中的数字是新节点产生的顺序。

Huffman编码的二叉树示意图
信源的各个消息从S0到S7的出现概率分别为4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。计算编码效率为98.5%，编码的冗余只有1.5%，可见霍夫曼编码效率很高。
产生Huffman编码需要对原始数据扫描两遍。第一遍扫描要精确地统计出原始数据中，每个值出现的频率，第二遍是建立Huffman树