1 案例背景
一幅普通的未经压缩的图片可能需要占几兆的存储空间，一个时长仅为1秒的未经压缩的视频文件所占的存储空间甚至能达到上百兆字节，这给普通PC的存储空间和常用网络的传输带宽带来了巨大的压力。其中，静止图像是不同媒体的构建基础，对其进行压缩不仅是各种媒体压缩和传输的基础，其压缩效果也是影响媒体压缩效果好坏的关键因素。基于这种考虑，本案例主要研究静止图像的压缩技术。随着人们对图像压缩技术的重视，目前已经提出了多种压缩编码方法。如果以不同种类的媒体信息为处理对象，则每种压缩编码方法都有其自身的优势和特点，如编码复杂度和运行效率的改善、解码正确性的提高、图像恢复的质量提升等"。特别是，随着互联网信息量的不断增大，高效能信息检索的质量也与压缩编码方法存在越来越紧密的联系。从发展的现状来看，采用分形和小波混合图像编码方法能充分发挥小波和分形编码的优点，弥补相互的不足，因此成为图像压缩的一个重要研究方向，但是依然存在某些不足之处，有待进一步提高。
2 理论基础
压缩，根据编码前后数据损失的角度可分为无损压缩编码和有损压缩编码；根据已知编码方法分类的实用性角度可分为统计编码、预测编码和变换编码。所谓无损压缩，就是利用数据的统计冗余信息进行压缩，且能够在不引起任何失真的前提下完全恢复原始数据。无损压缩法广泛用于文本、程序和特殊应用场合的图像数据(如指纹图像、医学图像等) 的压缩。常用的无损压缩编码方法有香农(Shannon-Fano) 编码、霍夫曼(Huffman)编码、行程(Run-length) 编码、LZW(Lempel-Ziv-Welch) 编码和算术编码等。霍夫曼编码完全依据字符出现的概率来构造异字头的平均长度最短的码字，有时称之为最佳编码。霍夫曼编码将使用次数较多的代码用长度较短的编码代替，将使用次数较少的代码用较长的编码代替，并且确保编码的唯一可解性。其根本原则是压缩编码的长度(即字符的统计数字x字符的编码长度)最小，也就是权值和最小。
3 霍夫曼编码的步骤
霍夫曼图像压缩重建，过程为：1.符号概率 2.合并概率 3.更新概率 4.分配码字 。
霍夫曼编码是一种无损压缩方法，其一般算法如下。
（1）符号概率
统计信源中各符号出现的概率，按符号出现的概率从大到小排序。
（2）合井概率
提取最小的两个概率并将其相加，合并成新的概率，再将新概率与剩余的概率组成新的概率集合，
（3）更新概率
将合并后的概率集合重新排序，再次提取其中最小的两个概率，相加得到新的概率，进而组成新的概率集合。如此重复进行，直到剩余最后两个概率之和为1.
（4）分配码字
分配码字从最后一步开始逆向进行，对于每次相加的两个概率，大概率赋0，小概率赋1，当然也可以反过来赋值，即大概率赋1，小概率赋0；特别是，如果两个概率相等，则从中任选一个赋0，另一个赋1.依次重复该步骤，从第一次赋值开始进入循环处理，直到最后的码字概率和为1时结束。将中间过程中所遇到的0和1按从最低位到最高位的顺序排序，就得到了符号的霍夫曼编码。
4 霍夫曼编码的特点
霍夫曼编码是最佳的变长编码，其特点如下回。
（1）可重复性
霍夫曼编码不唯一，具有可重复性。
（2）效率差异性
霍夫曼编码对于不同的信源往往具有不同的编码效率，具有效率差异性。
（3）不等长性
霍夫曼编码的输出内容不等长，因此给硬件实现带来一定的困难，也在一定程度上造成了误码传播的严重性。
（4）信源依赖性
霍夫曼编码的运行效率往往要比其他编码算法高，是最佳的变长编码。但是，霍夫曼编码以信源的统计特性为基础，必须先统计信源的概率特性才能编码，因此具有对信源的依赖性，这也在一定程度上限制了霍夫曼编码的实际应用。
如图所示是一个霍夫曼编码的例子。从图中二叉树的形状分步可以发现，符号只能出现在树叶上，且每个字符的路径都不允许是其他字符路径的前缀路径，因此能够成功构造前缀编码。该二叉树在数据结构中被称为霍夫曼树，一般应用于最佳判定的场景，是最优二叉树的一种，而且带权路径长度最短。其中，二叉树的带权路径长度由树中所有叶节点的权值乘以其到根节点的路径长度来获得，假设根节点为0层，则叶节点到根节点的路径长度就是叶节点的层数值。因此， 二叉树的带权路径长度记作WPL， 其计算公式为：WPL=(WxL+Wx Ly+…+W、xLy) .如果由N个权值W(i=1， 2， …， n) 构成的一棵包含N个节点的二叉树，则相应树节点的路径长度为L(i=1，2，…，n)，选择霍夫曼编码得出的
WPL值最小。
图13-1霍夫曼编码实例
在实际应用中，霍夫曼编码在预处理之前需要知道叶节点(即信源数据符号)的概率，这往往会对实时性要求较高的应用场景带来困扰。因此，人们在实时编码的应用场景中往往会采用所谓的准可变字长码，如采用双字长编码，并且通过从短码集合中选出一个码字，作为长码字头，进而保证码字的非续长特性2]。此外，在数字图像通信中所使用的三类传真机中包含的MH码采用了多字长VLC技术， 该技术根据一系列标准图像进行统计数据分析而得出，通过预先在其IC芯片中加入号码表，使得实际的编码解码过程简化为一个查表过程，从而确保了高速、实时应用场景的需要。
1 matlab版本
2014a
2 参考文献
[1] 蔡利梅.MATLAB图像处理——理论、算法与实例分析[M].清华大学出版社，2020.
[2]杨丹,赵海滨,龙哲.MATLAB图像处理实例详解[M].清华大学出版社，2013.
[3]周品.MATLAB图像处理与图形用户界面设计[M].清华大学出版社，2013.
[4]刘成龙.精通MATLAB图像处理[M].清华大学出版社，2015.