2.3.2 图像压缩基本算法
各种图像压缩算法均非单一的算法，而是若干不同算法的组合，以此尽可能提升数据的压缩效率。本节简单介绍无损编码中使用的游程编码和哈夫曼编码。
1.游程编码
游程编码（Run-Length Coding）是所有数据压缩算法中最简单的一种，特别适合处理信息元素集合较小（如二值化的图像，只包含0和1两个信息元）的信息。游程编码压缩数据量的主要思路为将一串连续的、重复的字符使用“数目”+“字符”的形式表示。例如，有一串未压缩的原始字符串如下：
在这个字符串中，5个连续的字符“A”可被称作一个“Run”。类似的，这个字符串共有6个“Run”，分别为5个“A”、2个“B”、6个“C”、2个“D”、1个“A”和2个“E”。因此，这个字符串可以用游程编码表示如下：
对于信息元素集合较大的数据，出现连续相同字符的概率很低，因此游程编码难以提供很高的压缩比率。进一步，如果信息具有较高的随机性，则游程编码甚至可能会增大编码后数据的体积。而在图像与语音信号中，出现连续字符串的情况较为常见（如语音中用连续的0表示静默音频、图像中的单色或相近色的背景等）。由于运算极为简单，所以游程编码在无损压缩中应用较为广泛，如在BMP图像中可择选游程编码对像素数据进行压缩。
2.哈夫曼编码
1952年，戴维·哈夫曼在麻省理工学院攻读博士学位时，发明了一种基于有序频率二叉树的编码方法，该方法的编码效率超过了他的导师罗伯特·费诺和信息论之父香农的研究成果，因此又被称作“最优编码方法”。
哈夫曼编码是可变长编码方法的一种，该方法完全依赖于码字出现的概率，是一种构造整体平均长度最短的编码方法。哈夫曼编码的关键步骤是建立符合哈夫曼编码规则的二叉树，该二叉树又被称作哈夫曼树。
哈夫曼树是一种特殊的二叉树，其终端节点的个数与待编码的码元个数相同，而且在每个终端节点上都带有各自的权值。每个终端节点的路径长度乘以该节点的权值的总和为整个二叉树的加权路径长度。在满足条件的各种二叉树中，路径长度最短的二叉树即为哈夫曼树。
在使用哈夫曼编码对码元进行实际编码的过程中，码元的权值可以被设置为其概率值，即可以根据其权值来构建哈夫曼树。我们假设使用哈夫曼编码对表2-1中的码字进行编码。
表2-1
根据概率表构建哈夫曼树的过程如图2-7所示。
图2-7
最终可以得到如图2-8所示的哈夫曼树。
图2-8
在构建哈夫曼树后，便可以得到每一个码元的哈夫曼编码的码字。具体方法是：从哈夫曼树的根节点开始遍历，直至每一个终端节点，当访问某节点的左子树时赋予码字0，当访问其右子树时赋予码字1（反之亦可），直到遍历到终端节点，这一路径所代表的0和1的串便是该码元的哈夫曼编码码字。
例如，对于图2-8中的哈夫曼树，首先，根节点访问左子树ABCF，赋予码字0；然后，访问左子树ABC，赋予码字0，此时整个码字为00；接着，访问右子树得到终端节点C，赋予码字 1，此时便可以得到 C 的哈夫曼编码码字 001。依次类推，六个元素的码元集合的编码码表如下所示。
◎ A:0000.
◎ B:0001.
◎ C:001.
◎ D:10.
◎ E:11.
◎ F:01.
从这个码表中可以看出另外一个规律，即哈夫曼编码的任意一个码字，都不可能是其他码字的前缀。因此通过哈夫曼编码的信息可以紧密排列且连续传输，而不用担心解码时出现歧义。