5、 交流系数的编码
量化AC系数的特点是1×64矢量中包含有 许多“0”系数，并且许多“0”是连续的，因 此使用非常简单和直观的游程长度编码 (RLE)对它们进行编码。 JPEG使用了1个 字节的高4位来表示连续“0”的个数，而使 用它的低4位来表示编码下一个非“0”系数 所需要的位数，跟在它后面的是量化AC系 数的数值。

数学上可以证明，符号序列{ si }的任
何一种编码方案，其平均码长必定大于 或等于H。也就是说，H是该符号序列的 理想最小平均码长。平均码长越接近H，
我们说该编码方案越好。
数学上还可以证明，在可变字长编码 中，对于出现概率大的符号编码成短字长 的编码，对于概率小的符号，编以较长的 字长编码。如果码字长严格按照所对应符 号的出现概率的大小逆序列排列，则平均 码长一定小于其他任何符号顺序方式，即 这是一种最接近于熵值的“最佳编码”。 霍夫曼编码是实现上述最佳编码的一 种算法。下面看一个示例。
将5个字符按其概率大小排序，然后把 最小的两项的概率值相加，归并成新的一 项。然后再选最小的两项合并，一直重复 作到只剩最后一项为止。本例实现过程参 见图3.4。 下面再来构造霍夫曼编码树。这是一 棵二叉树，我们从图3.5中的右方开始向左 取值，根结点概率为1.0，以下左分枝取概 率小的项，右分枝取概率大的项。对于归 并项，按此规则一直分解到最右方为止。 如图3.5所示为构造好的霍夫曼编码树。
1.正向离散余弦变换 （1）对每个单独的彩色图像分量，把整个分量图 像分成若干个8×8的图像块，如图所示，并作为 两维离散余弦变换DCT的输入。通过DCT变换， 把能量集中在少数几个系数上。 （2）DCT变换使用下式计算： 它的逆变换使用 下式计算： 上面两式中， C(u)，C(v) = (2)-1/2， 当u, v = 0； C(u)，C(v) = 1，其他。 f(i, j)经DCT 变换之后，F(0，0)是直流系数，其他为交流系数。 （3）在计算两维的DCT变换时，可使用下面的计 算式把两维的DCT变换变成一维的DCT变换：
压缩算法的简单示例
对原始数据ABCCAABCDDAACCDB进行 LZW压缩 原始数据中，只包括4个字符 (Character),A,B,C,D,四个字符可以用一个 2bit的数表示，0-A,1-B,2-C,3-D,从最直观的 角度看，原始字符串存在重复字符： ABCCAABCDDAACCDB，用4代表AB,5代 表CC，上面的字符串可以替代表示 为:45A4CDDAA5DB,
2

霍夫曼编码
霍夫曼编码是无损编码的一种，是一种 基于统计特性的可变字长的编码方法。属 于无损编码的还有行程编码、算术编码等。 下面来看霍夫曼编码。


设被编码的符号如下。
s1，s2，s3，…，sn


它们出现的概率分别为：
p1，p2，p3，…，pn
假设采用不等字长编码，每个符号的 码长分别为： m1，m2，m3，…，mn
补充：几种图像压缩算法
1.
图像数据压缩方法的分类 数据压缩的任务在不影响或少影响图像
质量的前提下，尽量设法减少图像数据中
的数据量。其首要任务是设法去掉各种冗
余的数据。

数据压缩实际是一个编码的过程，即
将原始数据进行编码压缩。数据解压缩是
数据压缩的逆过程，即将经过压缩的数据
还原成原始数据。因此数据压缩方法也称
行程编码原理
在给定的图像数据中寻找连续重复的数值， 然后用两个字符值取代这些连续值 “aaabbbbccccddd”=>”3a4b4c3d” 处理包含大量重复信息时可以得到很好的 压缩效率，但在连续重复数据少时效果差 PCX图像文件的RLE压缩算法
4

预 测 编 码
预测编码用于图像编码时与声音的压缩编码很 类似，它也是根据过去已编码的像素（也称为参 考像素）来预测当前的像素值（称为预测值）， 然后对当前的像素值与预测值之差进行编码，这 就是差分编码（DPCM）。这种编码是利用图像 本身的相关性及视觉的差值灵敏度特性，差值大 时，可以粗量化。图像编码用地较多的是二维预 测，如图3.6所示。
4、直流系数的编码
8×8图像块经过DCT变换之后得到的DC直 流系数有两个特点，一是系数的数值比较 大，二是相邻8×8图像块的DC系数值变化 不大。根据这个特点，JPEG算法使用了差 分脉冲调制编码（DPCM）技术，对相邻图 像块之间量化DC系数的差值（Delta）进行 编码。 Delta＝DC(0,0)k-DC(0,0)k-1
6、熵编码
使用熵编码还可以对DPCM编码后的直流 DC系数和RLE编码后的交流AC系数作进一 步的压缩。 在JPEG有损压缩算法中，使用 霍夫曼编码器来减少熵。使用霍夫曼编码 器的理由是可以使用很简单的查表 （Lookup Table）方法进行编码。压缩数 据符号时，霍夫曼编码器对出现频度比较 高的符号分配比较短的代码，而对出现频 度较低的符号分配比较长的代码。这种可 变长度的霍夫曼码表可以事先进行定义。

（3）实现难度：即实现压缩及还原算
法的难易程度，亦即完成压缩所需要的时 间与空间开销或硬件实现的复杂性。 压缩的方法主要有以下几种（见图
3.3）。
无损编码可以完全恢复原始图像而不 引入失真，它利用数据的统计特性来进行 数据压缩，解压缩后的还原图像与原始图 像完全一致。有损编码不能完全恢复原始 数据，而是利用人的视觉特性使解压缩后 的图像和原来一样。把上述方法结合起来 即为混合方法。 下面介绍几种常用的压缩方法。
LZW压缩算法 LZW压缩算法是一种新颖的压缩方法，由 Lemple-Ziv-Welch 三人共同创造，用他们 的名字命名。它采用了一种先进的串表压 缩，将每个第一次出现的串放在一个串表 中，用一个数字来表示串，压缩文件只存 贮数字，则不存贮串，从而使图象文件的 压缩效率得到较大的提高。奇妙的是，不 管是在压缩还是在解压缩的过程中都能正 确的建立这个串表，压缩或解压缩完成后， 这个串表又被丢弃。
JPEG编码 二、JPEG算法的主要计算步骤 JPEG压缩编码算 法的主要计算步骤如下：
（1）正向离散余弦变换（FDCT）。 （2）量化（Quantization）。 （3）Z字形编码（Zigzag Scan）。 （4）使用差分脉冲编码调制（Differential Pulse Code Modulation，DPCM)对直流系数(DC)进行编码。 （ 5 ） 使 用 行 程 长 度 编 码 （ Run-Length Encoding ， RLE）对交流系数（AC）进行编码。 （6）熵编码（Entropy Eoding）。
编码方法。 评价压缩方法的优劣主要从以下3个
方面来衡量。
（1）压缩比：压缩比指原始图像经 A/D转换后未经压缩所产生的数据量与经压 缩所产生的数据量之比。 （2）图像质量：还原出来的图像质量 比原始图像有多大失真，一般采用人的视 觉效果和信噪比两个方法。前者是通过人 在两米内观察所作的评价，后者通过仪器 测量。

3、Z字形编排
量化后的系数要重新编排，目的是为了增 加连续的“0”系数的个数，就是“0”的游程 长度，方法是按照Z字形的式样编排，如下 图所示。这样就把一个8×8的矩阵变成一 个1×64的矢量，频率较低的系数放在矢量 的顶部。 量化DCT系数序号 0 1 5 6 14 15 27 25 2 4 7 13 16 26 29 42 3 8 12 17 25 30 41 43 9 11 18 24 31 40 44 53 10 19 23 32 39 45 52 54 20 22 33 38 46 51 55 60 21 34 37 47 50 56 59 61 35 36 48 49 57 58 62 63
7、组成位数据流
JPEG编码的最后一个步骤是把各种标记代 码和编码后的图像数据组成一帧一帧的数 据，这样做的目的是为了便于传输、存储 和译码器进行译码，这样的组织的数据通 常称为JPEG位数据流（JPEG bitstream）。
LZW算法中，首先建立一个字符串表，把每一个 第一次出现的字符串放入串表中，并用一个数字 来表示，这个数字与此字符串在串表中的位置有 关，并将这个数字存入压缩文件中，如果这个字 符串再次出现时，即可用表示它的数字来代替， 并将这个数字存入文件中。压缩完成后将串表丢 弃。如"print" 字符串，如果在压缩时用266表示， 只要再次出现，均用266表示，并将"print"字符串 存入串表中，在图象解码时遇到数字266，即可 从串表中查出266所代表的字符串"print"，在解压 缩时，串表可以根据压缩数据重新生成。
如图3.5所示，我们给每个左分枝标以0， 给每个右分枝标以1，则从根结点至每个叶结点 的路径即为该叶结点代表字符的编码。如图3.5 右方所示。 本例中熵的值为2.09，编码的平均码长为 2.15，非常接近。 霍夫曼编码的优点是简单易行，缺点是解 码时必须知道所使用的码表，这给存储和通信 带来不便。另一个缺点是它依赖于原始数据的 概率，这在实际应用中受到许多限制。
2、量化 量化是对经过FDCT变换后的频率系数进行量化。 量化的目的是减小非“0”系数的幅度以及增加“0” 值系数的数目。量化是图像质量下降的最主要原 因。 对于有损压缩算法，JPEG算法使用如下图 所示的均匀量化器进行量化，量化步距是按照系 数所在的位置和每种颜色分量的色调值来确定。 因为人眼对亮度信号比对色差信号更敏感，因此 使用了两种量化表：亮度量化值和色差量化值。 此外，由于人眼对低频分量的图像比对高频分量 的图像更敏感，因此图中的左上角的量化步距要 比右下角的量化步距小。下面2个表中的数值对 CCIR 601标准电视图像已经是最佳的。如果不使 用这两种表，你也可以把自己的量化表替换它们。 亮度量化值表和色度量化值表
3.行程长度编码
编码实例(16色bmp数据)： 5个 第一行：24 24 24 30 60 40 09 22…46…46 第二行：64 65 67 88 88 88 88 … 90 78