从最后的两概率值开始逐步向前给符号分配码字长，每一步有两个分支，以相同的规则各赋予一个二进制码。编码过程如表3.2所示。
表3.2哈夫曼编码中的码字分配过程 原始信源 符号 概率 0.02 0.04 0.06 0.12 0.16 0.2 0.4 码字 01111 01110 0110 010 001 000 1 0.06 0.06 0.12 0.16 0.2 0.4 0111 0110 010 001 000 1 0.12 0.12 0.16 0.2 0.4 011 010 001 000 1 0.16 0.2 0.24 0.4 001 000 01 1 0.24 01 0.36 00 0.4 1 0.4 0.6 1 0 按信源符号缩减逆向赋码字 1 2 3 4 5 a5 a4 a7 a3 a1 a6 a2 同时也可以计算与编码性能相关的几个参数： （1）信源的熵
H(A)???P(ai)log2P(ai)?2.325(3.1)
i?17
（2）哈夫曼编码的平均码字长
Lavg??l(i?17a)ip(a)i?3?0.1?6?10.?4?30.?12?...?4?0. 0 6 2. 380(3.2)
（3）哈夫曼编码的效率
H(A)2.325??0.97 7 ?? Lavg2.328(3.3)
4.1.3 哈夫曼编码特点
用哈夫曼编码方法压缩图像数据，对于不同的图像，其压缩效果和压缩效率是不同的。当各符号出现概率不同时，编码效率较高。而当各符号出现的概率相等时，实际上此时的哈夫曼编码就已退化成等长编码，编码效率较低。对灰度图像的无损压缩算法采用哈夫曼编码，即对原图像实行直接的编码，该算法在恢复
第 6 页 共 32 页
图像的质量上是极好的。但由于该算法对原图像直接使用不等长编码压缩，但没有处理图像各个像素间的相关性，从而使压缩效率并不是很高,因此必须结合其它的压缩方法同时使用以达到更高的压缩比。
4.2 香农-范诺编码
香农-范诺(Shannon-Fannon)编码也是一种常见的可变字长编码。与哈夫曼编码相似，当信源符号出现时的概率正好为2-i时，采用香农-范诺编码同样能达到100%的编码效果。
4.2.1 香农-范诺编码基本原理
香农-范诺编码的理论基础是符号的码字长度Ni完全由该符号出现的概率来决定，即 -logDPi?Ni?-logDPi+1，式中D为编码所用的数制。 4.2.2 香农-范诺编码步骤
（1）将信源符号Xi按其出现概率Pi从小到大排序：
?x1x2...xn?X1???;P1?P2?...?Pn?P1P1...Pn?(3.3)
（2）将X分成两个子集
?x1x2...xk??xk?1xk?2...xn?X1???X2???P1P1...PkPk?1Pk?2...Pn????(3.4)
并且保证
?P??P成立或差不多成立。在本图像压缩编码设计中是按前
iji?1j?k?1kn一个子集大于等于总和的一半来计算的。
（3）给两个子集赋不同的码元值，如X1中的符号赋“1”，X2中的符号就赋“0”。
（4）重复（2）、（3），即对每个子集再一分为二，并分别赋予不同码元值，直到每个子集仅含一个信源符号为止。
第 7 页 共 32 页
下面通过哈夫曼编码中用过的同样例子，说明上述编码过程。将信源
a4a7a3a1a6a2??a5A???0.020.040.060.120.160.20.4??(3.5)
记
为
：
?x1X???0.x202x30.x404x?x5? ?0.06(3.6)
则其编码过程如表3.3所示。
表3.3香农-范诺编码过程 码字 111111 111110 11110 1110 110 10 0 符号 X1 X2 X3 X4 X5 X6 X7 概率 0.02 0.04 0.06 0.12 0.16 0.2 0.4 0 0 0 1 1 0 1 1 0 1 1 0 4.2.3 香农-范诺编码特点
采用以上算法用VC具体实现对某一图像进行编码，同时对编码的有关评估参数如图像熵值、平均码长、编码效率进行计算。为了便于编码的显示设计了编码显示对话框，在其中进行编码运算并实现码字的显示。
4.3 行程编码
行程编码又称行程长度编码(Run Length Encoding, RLE)，是一种熵编码，其编码原理相当简单，即将具有相同值的连续串用其串长和一个代表值来代替，该连续串就称为行程，串长称为行程长度。RLE压缩编码尤其适用于计算机生成的图形图像，对减少存储容量很有效果。 4.3.1行程编码基本原理
行程编码分为定长和不定长编码两种。定长编码是指编码的行程长度所用的
第 8 页 共 32 页
二进制位数固定，而变长形成编码是指对不同范围的行程长度使用不同位数的二进制进行编码。使用变长行程编码需要增加标志位来表明所使用的二进制位数。
为了达到较好的压缩效果，一般不单独采用行程编码，而是和其他编码方法结合使用。例如，在JPEG中，就综合使用了行程编码、DCT、量化编码以及哈夫曼编码，先对图像作分块处理，再对这些分块图像进行离散余弦变换(DCT)，对变换后的频域数据进行量化并作Z字形扫描，接着对扫描结果作行程编码，对行程编码后的结果在作哈哈夫曼编码。 4.3.2行程编码步骤
PCX文件分为文件头和图像压缩数据两个部分。如果是256色图像，则还有一个256色调色板存于文件尾部。文件头全长128字节，包含了图像的大小和颜色以及PCX文件的版本标志等信息。其中头信息的具体结构为：
typedef struct{
char manufacturer; char version; char encoding; char bits_per_pixel; WORD xmin,ymin; WORD xmax,ymax; WORD hres; WORD vres; char palette[48]; char reserved;
char colour_planes; WORD bytes_per_line; WORD palette_type;
char filler[58]; }PCXHEAD;
其中值得注意的是以下几个数据：manufacturer为PCX文件的标志，必须为0x0a；xmin为最小的x坐标，xmax为最大的x坐标，所以图像的宽度为xmax-xmin+1,同样图像的高度为ymax-ymin+1；bits_per_pixel为每个编码行所占的字节数。
图像压缩数据紧跟在文件头后。如果没有使用调色板，那么图像压缩数据存储的是实际像素值；否则，存储的是调色板的索引值。当压缩数据是实际的像素值时，它们按颜色平面和扫描行存储，即每行先存储所有R分量，再存储所有G分量，最后存储所有B分量，一行数据存储完后，接着存储下一行数据。如果使用了调色板，则不会分解为单独的颜色平面存储。
第 9 页 共 32 页
下面以256色的PCX文件为例，说明PCX文件中的行程编码。
256色PCX文件中，每个像素占一个字节，压缩数据以字节为单位逐行进行编码，每行填充到偶数字节。PCX文件规定编码时的最大行程长度为63，如果行程长度大于63，则必须分多次存储。对于长度大于1的行程，编码时先存入其行程长度(长度L加上192即0xC0)，再存入该行程的代码值，行程长度和行程的代表值分别占一个字节。对于长度为1的行程，即单个像素，如果该像素的值小于或等于0xC0，则编码时直接存入该像素值，而不存储长度信息；否则，先存入0xC1，再存入该像素值，这样做的目的是为了避免该像素值被误认为长度信息。例如，连续100个灰度值为0x80的像素，其编码（以十六进制表示）应为FF 80 25 80。上面的编码中出现的FF的长度信息是由63与0xC0相加所得。 4.3.3行程编码特点
行程编码比较适合于二值图像（即图像的各像素只有两个值——黑或者白）的编码，一般用于量化后出现大量零系数连续的场合，用行程来表示连零码。如果图像是由很多块颜色或灰度相同的大面积区域组成的，那么采用行程编码可以达到很高的压缩比。如果图像中的数据非常分散，则行程编码不但不能压缩数据，反而会增加图像文件的大小。极端情况如果图像中每两个相邻点的颜色都不同，用这种算法不但不能压缩，反而数据量增加一倍。所以现在单纯采用行程编码的压缩算法用得并不多，PCX文件算是其中的一种。
五、实验内容:
5.1 哈夫曼编码
5.1.1 哈夫曼编码算法实现
资源文件HuffmanCoding.cpp中主要介绍哈夫曼编码的算法，首先要从视图类
CDImageProcessView中的OnHuffmancoding函数中得到0-255各灰度值出现的概率，在下面的算法中要基于这个概率值进行哈夫曼编码。
首先要对这个概率值进行从小到大的冒泡排序，然后从概率大于0处开始编码，灰度值较小的编为1，灰度值较大的编为0，再将最小的两个灰度值相加，将加后的值与其他灰度值放在一起重新按从小到大排序，重复以上的步骤直到概率
第 10 页 共 32 页