251,251,252,255。表示250需要8个比特,而表示2只需要两个比特,这样就实现了压 缩 常用的预测编码有Δ调制( Delta modulation,简称DM);微分预测编码( Differential Pulse Code Modulation,DPCM),具体的细节在此就不详述了。 所谓变换编码是指,将给定的图象变换到另一个数据域(如频域)上,使得大量的信息能用较 少的数据来表示,从而达到压缩的目的。变换编码有很多,如(1)离散傅立叶变换( Discrete Fourier Transform,简称DFT):(2)离散余弦变换( Discrete Cosine Transform,简称DCT):(3) 离散哈达玛变换( Discrete Hadamard Transform,简称DHI)。 其它的编码方法也有很多,如混合编码( Hybird Coding)、矢量量化( Vector Quantize,ⅴQ LZW算法。在这里,我们只介绍LZW算法的大体思想。 值得注意的是,近些年来出现了很多新的压缩编码方法,如使用人工神经元网络( Artificial Neural Network,简称ANN)的压缩编码算法、分形( fract))、小波( Wavelet)、基于对象( Object Based)的压缩编码算法、基于模型( Model- Based)的压缩编码算法(应用在MPEG4及未来的 视频压缩编码标准中)。这些都超出了本书的范围。 本章的最后,我们将以JPEG压缩编码标准为例,看看上面的几种编码方法在实际的压缩编 码中是怎样应用的 91哈夫曼编码 哈夫曼( Huffman)编码是一种常用的压缩编码方法,是 Huffman于1952年为压缩文本文件建 立的。它的基本原理是频繁使用的数据用较短的代码代替,较少使用的数据用较长的代码代 替,每个数据的代码各不相同。这些代码都是二进制码,且码的长度是可变的。举个例子: 假设一个文件中出现了8种符号S0SIS2,S3,S4S5,S6,S7,那么每种符号要编码,至少需要 3比特。假设编码成000001010.011,100101,110,111称做码字)。那么符号序列 SOSIS7SOSIS6S2S2S3S4S5SOSOS 1 编 码 后 0000011000011000100110010100000001,共用了42比特。我们发现S0,S1,S2 这三个符号出现的频率比较大,其它符号出现的频率比较小,如果我们采用一种编码方案使 得S0,S1,S2的码字短,其它符号的码字长,这样就能够减少占用的比特数。例如,我们 采用这样的编码方案:S0到S7的码字分别01,11,101,000000001,10,那么上述符 号序列变成01101101010100000010010010111,共用了39比特,尽管有些码字 如S3,S4,S5,S6变长了(由3位变成4位),但使用频繁的几个码字如S0,S1变短了,所 以实现了压缩。 上述的编码是如何得到的呢?随意乱写是不行的。编码必须保证不能出现一个码字和另一个 的前几位相同的情况,比如说,如果S0的码字为01,S2的码字为011,那么当序列中出现 01时,你不知道是S0的码字后面跟了个1,还是完整的一个S2的码字。我们给出的编码 能够保证这一点 下面给出具体的 Huffman编码算法。251，251，252，255。表示 250 需要 8 个比特，而表示 2 只需要两个比特，这样就实现了压 缩。 常用的预测编码有Δ调制(Delta Modulation，简称 DM)；微分预测编码(Differential Pulse Code Modulation，DPCM)，具体的细节在此就不详述了。 所谓变换编码是指，将给定的图象变换到另一个数据域(如频域)上，使得大量的信息能用较 少的数据来表示，从而达到压缩的目的。变换编码有很多，如(1)离散傅立叶变换(Discrete Fourier Transform，简称 DFT)；(2)离散余弦变换(Discrete Cosine Transform，简称 DCT)；(3) 离散哈达玛变换(Discrete Hadamard Transform，简称 DHT)。 其它的编码方法也有很多，如混合编码(Hybird Coding)、矢量量化(Vector Quantize，VQ) 、 LZW 算法。在这里，我们只介绍 LZW 算法的大体思想。 值得注意的是，近些年来出现了很多新的压缩编码方法，如使用人工神经元网络(Artificial Neural Network，简称 ANN)的压缩编码算法、分形(Fractl)、小波(Wavelet) 、基于对象(Object Based)的压缩编码算法、基于模型(Model –Based)的压缩编码算法(应用在 MPEG4 及未来的 视频压缩编码标准中)。这些都超出了本书的范围。 本章的最后，我们将以 JPEG 压缩编码标准为例，看看上面的几种编码方法在实际的压缩编 码中是怎样应用的。 9.1 哈夫曼编码 哈夫曼(Huffman)编码是一种常用的压缩编码方法，是 Huffman 于 1952 年为压缩文本文件建 立的。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代 替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。举个例子： 假设一个文件中出现了 8 种符号 S0,S1,S2,S3,S4,S5,S6,S7，那么每种符号要编码，至少需要 3 比特。假设编码成 000,001,010,011,100,101,110,111( 称做码字 ) 。那么符号序列 S0S1S7S0S1S6S2S2S3S4S5S0S0S1 编码后变成 000001111000001110010010011100101000000001，共用了 42 比特。我们发现 S0，S1，S2 这三个符号出现的频率比较大，其它符号出现的频率比较小，如果我们采用一种编码方案使 得 S0，S1，S2 的码字短，其它符号的码字长，这样就能够减少占用的比特数。例如，我们 采用这样的编码方案：S0 到 S7 的码字分别 01,11,101,0000,0001,0010,0011,100，那么上述符 号序列变成 011110001110011101101000000010010010111，共用了 39 比特，尽管有些码字 如 S3，S4，S5，S6 变长了(由 3 位变成 4 位)，但使用频繁的几个码字如 S0，S1 变短了，所 以实现了压缩。 上述的编码是如何得到的呢？随意乱写是不行的。编码必须保证不能出现一个码字和另一个 的前几位相同的情况，比如说，如果 S0 的码字为 01，S2 的码字为 011，那么当序列中出现 011 时，你不知道是 S0 的码字后面跟了个 1，还是完整的一个 S2 的码字。我们给出的编码 能够保证这一点。 下面给出具体的 Huffman 编码算法