VC++数字图像压缩算法研究与实现(HUFFMAN编码)(3)
2.3图像压缩编码
目前图像编码压缩的方法很多，其分类方法根据出发点不同而有差异。根据解压重建后的图像和原始图像之间是否具有误差，图像编码压缩可分为无误差编码和有误差编码两大类。无损编码中删除的仅仅是图像数据中冗余的数据，经解码重建的图像和原始图像没有任何失真，常用于复制、保存十分珍贵的历史、文物图像等场合；有损编码是指解码重建的图像与原图像相比有失真，不能精确的复原，但视觉效果基本相同，是实现高压缩比的编码方法，数字电视、图像传输和多媒体等常采用这类编码方法。
图像压缩技术可分为以下几种：
1：无损压缩：a．霍夫曼编码 b．行程编码 c．算术编码
2：有损压缩：a．预测编码 b．变换编码 c．其他编码
Huffman编码：Huffman编码在无损压缩的编码方法中，它是一种有效的编码方法。它是霍夫曼博士在1952 年根据可变长最佳编码定理提出的。依据信源数据中各信号出现的频率分配不同长度的编码。Huffman码是一种变长码，其基本思想是：先统计图像(已经数字化)中各灰度出现的概率，出现概率较大的赋以较短的码字，而出现概率较小的则赋以较长的码字。在整个编码过程中，统计图像各灰度级出现的概率和编码这两步都很简单，关键的是Huffman树的构造。不但在编码的时候需要用到这颗树，解码的时候也必须有这颗树才能完成解码工作，因此，Huffman树还得完整的传输到解码端。
例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。
例如：假设信源符号为【a、b、c、d、e、f、g】，其出现的概率相应的为【0.25、0.025、0.025、0.05、0.35、0.25、0.05】，一共7个字符，对其进行huffman 编码，算法如下：
首先按照每个字符出现的频率大小从左到右排列：0.35、0.25、0.25、0.05、0.05、0.025、0.025；选出最小的两个值作为叶子节点构成一棵二叉树，值较大的叶子节点在左，两个叶子节点对应的频率之和作为根节点。把原排列中最小的两个节点删除，新的根节点插入排列保持大小从左到右的排列顺序不变；重复执行，直到最后得到值为1 的根节点。得到一棵huffman 树。
在得到的huffman 树上左分支标记1，右分支标记0，所有的字符根据其频率标记到对应的叶子节点上，从根节点到叶子节点路径上遇到的0、1 字符串即为对应叶子节点所在字符的编码。a、b、c、d、e、f、g七个字符的huffman 编码分别是：10、0001、0000、0011、11、01、0010，可以看到,符号只能出现在树叶上,任何一个字符的路径都不会是另一字符路径的前缀路径。
算术编码：算术编码的基本思想是将被编码的数据序列表示成0 和1 之间的一个间隔（也就是一个小数范围），该间隔的位置与输入数据的概率分布有关。信息越长，表示间隔就越小，因而表示这一间隔所需的二进制位数就越多（由于间隔是用小数表示的）。算术压缩算法中两个基本的要素为源数据出现的频率以及其对应的编码区间。其中，源数据的出现频率、编码区间则决定算术编码算法最终的输出数据。