1、 第七讲 图像的编码与压缩 数据压缩最初是信息论研究中的一个重要课题，在信数据压缩最初是信息论研究中的一个重要课题，在信息论中数据压缩被称为信源编码。但近年来，数据压缩不息论中数据压缩被称为信源编码。但近年来，数据压缩不仅限于编码方法的研究与探讨，己逐步形成较为独立的体仅限于编码方法的研究与探讨，己逐步形成较为独立的体系。系。它主要研究数据的表示、传输、变换和编码方法，目它主要研究数据的表示、传输、变换和编码方法，目的是减少存储数据所需的空间和传输所用的时间。的是减少存储数据所需的空间和传输所用的时间。 一、引言一、引言1. 为什么要压缩？为什么要压缩？图像作为信息的重要表现形式，其具有数据量
2、大、带宽宽图像作为信息的重要表现形式，其具有数据量大、带宽宽等特点。等特点。 需要增加信道，但这很有限，因为信道的增加永远赶不上需要增加信道，但这很有限，因为信道的增加永远赶不上信息的爆炸式增长，况且还要受到环境的限制。信息的爆炸式增长，况且还要受到环境的限制。 必须减少表示图像的数据量，以达到压缩图像数据的目的。必须减少表示图像的数据量，以达到压缩图像数据的目的。 图像数据的特点之一是信息量大。以像幅为23cm23cm的航摄影像为例，若按采样间隔25um、每象素8bit扫描，其数据量为84.5MB；一颗卫星每半小时发回次全波段(五个波段)数据，每个波段图像大小为22922190字节约4.90
3、MB，每天的数据量高达1.2GB。如此海量数据需要巨大的存储空间。在多媒体中，海量图像数据的存储和处理是难点之一。根据计算，一张600M字节的光盘，能存放20秒左右的640480像素的图像画面信息，如不进行编码压缩处理，多媒体信息保存有多么困难是可想而知的。 在现代通信中，图像传输已成为重要内容。除要求设备可靠、图像保真度高以外，实时性将是重要技术指标之一。很显然，在信道带宽、通信链路容量一定的前提下，采用编码压缩技术，减少传输数据量，是提高通信速度的重要手段。 没有图像编码压缩技术的发展，大容量图像信息的存储与传输是难以实现的，多媒体、高速信息公路等新技术在实际中的应用会碰到很大困难。 2.
4、 2. 为什么能压缩？为什么能压缩？ 一般图像中，存在很大的冗余度。 到底能压缩多少，除了和图像本身存在的冗余度多少有关外，很大程度取决于对图像质量的要求。 例如：广播电视要考虑艺术欣赏，对图像质量要求就很高，例如：广播电视要考虑艺术欣赏，对图像质量要求就很高，用目前的编码技术，即使压缩比达到用目前的编码技术，即使压缩比达到3 31 1都是很困难的。而对可都是很困难的。而对可视电话，因画面活动部分少，对图像质量要求也低，可采用高效视电话，因画面活动部分少，对图像质量要求也低，可采用高效编码技术，使压缩比高达编码技术，使压缩比高达150015001 1以上。以上。 目前高效图像压缩编码技术已能用
5、硬件实现实时处理，在广目前高效图像压缩编码技术已能用硬件实现实时处理，在广播电视、工业电视、电视会议、可视电话、传真和互连网、遥感播电视、工业电视、电视会议、可视电话、传真和互连网、遥感等多方面得到应用。等多方面得到应用。空间冗余：图像内部相邻像素之间存在较强的相关性所造成的冗余。时间冗余： 视频图像序列中的不同帧之间的相关性所造成的冗余。视觉冗余： 是指人眼不能感知或不敏感的那部分图像信息。数字图像的冗余主要表现为以下几种形式：数字图像的冗余主要表现为以下几种形式：空间冗余、时间冗余、视觉冗余、空间冗余、时间冗余、视觉冗余、 信息熵冗余、结构冗余。信息熵冗余、结构冗余。信息熵冗余：也称编码冗
6、余，如果图像中平均每个像素使用的比特数大于该图像的信息熵，则图像中存在冗余，这种冗余称为信息熵冗余。结构冗余： 是指图像中存在很强的纹理结构或自相似性。图像数据的这些冗余信息为图像压缩编码提供了依据。图像数据的这些冗余信息为图像压缩编码提供了依据。 例如，利用人眼对蓝光不敏感的视觉特性，在对彩色图像编码时，例如，利用人眼对蓝光不敏感的视觉特性，在对彩色图像编码时，就可以用较低的精度对蓝色分量进行编码。就可以用较低的精度对蓝色分量进行编码。 图像编码的目的就是充分利用图像中存在的各种冗余信息，图像编码的目的就是充分利用图像中存在的各种冗余信息，特别是空间冗余、时间冗余以及视觉冗余，以尽量少的比特
7、别是空间冗余、时间冗余以及视觉冗余，以尽量少的比特数来表示图像。特数来表示图像。 利用各种冗余信息，利用各种冗余信息， 压缩编码技术能够很好地解决在将模拟信号压缩编码技术能够很好地解决在将模拟信号转换为数字信号后所产生的带宽需求增加的问题，转换为数字信号后所产生的带宽需求增加的问题， 它是使数字信号它是使数字信号走上实用化的关键技术之一，下表中列出了几种常见应用的码率。走上实用化的关键技术之一，下表中列出了几种常见应用的码率。 图像压缩编码的概念图像数据的压缩和编码表示。图像数据的压缩和编码表示。图像压缩编码系统：图像压缩编码系统：图像编码图像编码: : 对图像信息进行压缩和编码，在存储、处对
8、图像信息进行压缩和编码，在存储、处理和传输前进行，也称图像压缩；理和传输前进行，也称图像压缩；图像解码：对压缩图像进行解压以重建原图像或其近图像解码：对压缩图像进行解压以重建原图像或其近似图像。似图像。二、二、 图像编码评价图像编码评价随着众多图像压缩算法的出现，如何评价图像压缩算法就随着众多图像压缩算法的出现，如何评价图像压缩算法就成为重要的课题。一般说来，评价图像压缩算法的优劣主要有成为重要的课题。一般说来，评价图像压缩算法的优劣主要有以下以下4 4个参数。个参数。 1 1） 算法的编码效率算法的编码效率 算法的编码效率通常有几种表现形式：算法的编码效率通常有几种表现形式：平均码字长度（平
9、均码字长度（R R），）， 图像的压缩比（图像的压缩比（raterate，r r），每秒钟所需的传输比特数（），每秒钟所需的传输比特数（bits bits per secondper second，bpsbps），图像熵与平均码长之比（），图像熵与平均码长之比（）。）。设一幅灰度级为设一幅灰度级为N N的图像，图像中第的图像，图像中第k k级灰度出现的概率为级灰度出现的概率为P Pk k， 图像大小为图像大小为N Nx xN Ny y，每个像素用，每个像素用d d比特表示，每两帧图像间隔比特表示，每两帧图像间隔t t，则按信息论中信息熵的定义，数字图像的熵则按信息论中信息熵的定义，数字图像的熵
10、H H由下式定义：由下式定义：11NkkkHP gP 由此可见，图像熵由此可见，图像熵H H表示各灰度级比特数的统计平均值。表示各灰度级比特数的统计平均值。 对于一种图像编码方法，设第对于一种图像编码方法，设第k k级灰度的码字长度为级灰度的码字长度为B Bk k，则，则该图像的平均码字长度该图像的平均码字长度R R为为 NkkkPBR1于是，可定义编码效率于是，可定义编码效率为为 %100RH 每秒钟所需的传输比特数每秒钟所需的传输比特数bpsbps为为 tRNNbpsyx压缩比压缩比r r为为 Rdr 由于同一压缩算法对不同图像的编码效率会有所不同，因此由于同一压缩算法对不同图像的编码效率
11、会有所不同，因此常需定义一些常需定义一些“标准图像标准图像”，一般通过测量不同压缩算法对同一，一般通过测量不同压缩算法对同一组组“标准图像标准图像”的编码性能来评价各图像压缩算法的编码效率。的编码性能来评价各图像压缩算法的编码效率。 2 2） 编码图像的质量编码图像的质量 图像质量评价可分为客观质量评价和主观质量评价。最图像质量评价可分为客观质量评价和主观质量评价。最常用的客观质量评价指标是均方误差（常用的客观质量评价指标是均方误差（MSEMSE）和峰值信噪比）和峰值信噪比（PSNRPSNR），其定义如下），其定义如下： MSEPSNRjifjifNNMSEyxNjNiyx255255lg10
12、),(),(1020主观质量评价是指由一批观察者对编码图像进行观察并打主观质量评价是指由一批观察者对编码图像进行观察并打分，然后综合所有人的评判结果，给出图像的质量评价。分，然后综合所有人的评判结果，给出图像的质量评价。客观质量评价能够快速有效地评价编码图像的质量，但符客观质量评价能够快速有效地评价编码图像的质量，但符合客观质量评价指标的图像不一定具有较好的主观质量。主观合客观质量评价指标的图像不一定具有较好的主观质量。主观质量评价能够与人的视觉效果相匹配，但其评判过程缓慢费时。质量评价能够与人的视觉效果相匹配，但其评判过程缓慢费时。 3 3） 算法的适用范围算法的适用范围特定的图像编码算法具
13、有其相应的适用范围，并不对所有特定的图像编码算法具有其相应的适用范围，并不对所有图像都有效。图像都有效。 一般说来，大多数基于图像信息统计特性的压缩算法具有一般说来，大多数基于图像信息统计特性的压缩算法具有较广的适用范围，而一些特定的编码算法的适用范围较窄，如较广的适用范围，而一些特定的编码算法的适用范围较窄，如分形编码主要用于自相似性高的图像。分形编码主要用于自相似性高的图像。 4 4） 算法的复杂度算法的复杂度算法的复杂度即指完成图像压缩和解压缩所需的运算量和算法的复杂度即指完成图像压缩和解压缩所需的运算量和硬件实现该算法的难易程度。硬件实现该算法的难易程度。 优秀的压缩算法要求有较高的压
14、缩比，压缩和解压缩快，优秀的压缩算法要求有较高的压缩比，压缩和解压缩快，算法简单，易于硬件实现，还要求解压缩后的图像质量较好。算法简单，易于硬件实现，还要求解压缩后的图像质量较好。 选用编码方法时一定要考虑图像信源本身的统计特性、多选用编码方法时一定要考虑图像信源本身的统计特性、多媒体系统媒体系统( (硬件和软件产品硬件和软件产品) )的适应能力、的适应能力、 应用环境以及技术应用环境以及技术标准。标准。 三三 图像压缩方法分类图像压缩方法分类 按压缩前及解压后的信息保持程度和方法的原理来分类按压缩前及解压后的信息保持程度和方法的原理来分类 按照压缩前及解压后的信息保持程度分成三类：按照压缩前
15、及解压后的信息保持程度分成三类： 信息保持（存）型信息保持（存）型 压缩、解压中无信息损失，主要用于图像存档，其特点是信息无压缩、解压中无信息损失，主要用于图像存档，其特点是信息无失真，但压缩比有限，也称无失真无损可逆型编码。失真，但压缩比有限，也称无失真无损可逆型编码。 信息损失型信息损失型 牺牲部分信息，来获取高压缩比，数字电视、图像传输和多媒体牺牲部分信息，来获取高压缩比，数字电视、图像传输和多媒体等应用场合常用这类压缩，其特点是通过忽略人的视觉不敏感的等应用场合常用这类压缩，其特点是通过忽略人的视觉不敏感的次要信息来提高压缩比，也称有损压缩。次要信息来提高压缩比，也称有损压缩。 特征抽
16、取型特征抽取型 仅对于实际需要的（提取）特征信息进行编码，而丢掉其它非特仅对于实际需要的（提取）特征信息进行编码，而丢掉其它非特征信息，属于信息损失型。征信息，属于信息损失型。 这里的第三类是针对特殊的应用场合，因此，一般就将图像压缩这里的第三类是针对特殊的应用场合，因此，一般就将图像压缩编码分成无损和有损两大类。编码分成无损和有损两大类。按照图像压缩的方法原理可分成四类按照图像压缩的方法原理可分成四类像素编码：像素编码：编码时只对每个像素单独处理。如脉冲编编码时只对每个像素单独处理。如脉冲编码调制、熵编码、行程编码等。码调制、熵编码、行程编码等。预测编码：预测编码：通过去除相邻像素之间的相关
17、性和冗余性，通过去除相邻像素之间的相关性和冗余性，只对新的信息进行编码。常用的有差分脉冲编码调制。只对新的信息进行编码。常用的有差分脉冲编码调制。变换编码：变换编码：对给定图像采用某种变换，使得大量的信对给定图像采用某种变换，使得大量的信息能用较少的数据来表示。通常采用的变换包括：离散息能用较少的数据来表示。通常采用的变换包括：离散傅立叶变换傅立叶变换(DFT(DFT(DFT(DFT），离散余弦变换），），离散余弦变换），(DCT)(DCT)(DCT)(DCT)和离散小波变换和离散小波变换(DWT)(DWT)(DWT)(DWT)。其它方法：其它方法：早期的编码，如混合编码、矢量量化、早期的编码
18、，如混合编码、矢量量化、LZWLZWLZWLZW算法。算法。 近些年来也出现了很多新的压缩编码方法，如使用近些年来也出现了很多新的压缩编码方法，如使用人工神经元网络的压缩编码算法、分形、小波、基于对人工神经元网络的压缩编码算法、分形、小波、基于对象的压缩编码算法、基于模型的压缩编码算法等。象的压缩编码算法、基于模型的压缩编码算法等。行程编码（行程编码（RLERLE） 在一个逐行存储的图像中，具有相同灰度值的一些象在一个逐行存储的图像中，具有相同灰度值的一些象素组成的序列称为一个行程。在编码时，对于每个行程只素组成的序列称为一个行程。在编码时，对于每个行程只存储一个灰度值的码，再紧跟着存储这个行
19、程的长度。这存储一个灰度值的码，再紧跟着存储这个行程的长度。这种按照行程进行的编码被称为行程编码（种按照行程进行的编码被称为行程编码（Run Length Run Length EncodingEncoding）。）。 行程编码对于仅包含很少几个灰度级的图像，特别是二值图像，行程编码对于仅包含很少几个灰度级的图像，特别是二值图像，比较有效。比较有效。3.1 无损编码无损编码1、行程编码基本方法行程编码基本方法 行程编码又称行程长度编码，是一种熵编码，其编码原理相行程编码又称行程长度编码，是一种熵编码，其编码原理相当简单，即将具有相同值的连续串用其串长和一个代表值来代替，当简单，即将具有相同值的
20、连续串用其串长和一个代表值来代替，该连续串就称为行程，串长称为行程长度。例如，有一字符串该连续串就称为行程，串长称为行程长度。例如，有一字符串“aabbbcdddddaabbbcddddd”，则经行程长度编码后，该字符串可以只用，则经行程长度编码后，该字符串可以只用“2a3b1c5d2a3b1c5d”来表示。来表示。 行程编码分为行程编码分为定长和不定长定长和不定长编码两种。定长编码是指编码的编码两种。定长编码是指编码的行程长度所用的二进制位数固定，而变长行程编码是指对不同范行程长度所用的二进制位数固定，而变长行程编码是指对不同范围的行程长度使用不同位数的二进制位数进行编码。使用变长行围的行程
21、长度使用不同位数的二进制位数进行编码。使用变长行程编码需要增加标志位来表明所使用的二进制位数。程编码需要增加标志位来表明所使用的二进制位数。 行程编码比较适合于二值图像的编码，一般用于量化后出现大量零系数连续的场合，用行程来表示连零码。如果图像是由很多块颜色或灰度相同的大面积区域组成的，那么采用行程编码可以达到很高的压缩比。如果图像中的数据非常分散，则行程编码不但不能压缩数据，反而会增加图像文件的大小。 为了达到较好的压缩效果，一般不单独采用行程编码， 而是和其他编码方法结合使用。例如，在JPEG中，就综合使用了行程编码、DCT、量化编码以及哈夫曼编码，先对图像作分块处理，再对这些分块图像进行
22、离散余弦变换（DCT），对变换后的频域数据进行量化并作Z字形扫描，接着对扫描结果作行程编码， 对行程编码后的结果再作哈夫曼编码。 2 2、PCXPCX文件中的行程编码文件中的行程编码 PCXPCX文件分为文件头和图像压缩数据两个部分。文件分为文件头和图像压缩数据两个部分。如果是如果是256256色图像，则还有一个色图像，则还有一个256256色调色板存于文件尾部。文件头全色调色板存于文件尾部。文件头全长长128128字节，包含了图像的大小和颜色以及字节，包含了图像的大小和颜色以及PCXPCX文件的版本标识文件的版本标识等信息，图像压缩数据紧跟在文件头之后。如果没有使用调色等信息，图像压缩数据紧
23、跟在文件头之后。如果没有使用调色板，板， 那么图像压缩数据存储的是实际像素值；否则，存储的是那么图像压缩数据存储的是实际像素值；否则，存储的是调色板的索引值。调色板的索引值。在在256256色色PCXPCX文件中，每个像素占一字节，文件中，每个像素占一字节， 压缩数据以字节为压缩数据以字节为单位逐行进行编码，每行填充到偶数字节。单位逐行进行编码，每行填充到偶数字节。PCXPCX文件规定编码时的文件规定编码时的最大行程长度为最大行程长度为6363，如果行程长度大于，如果行程长度大于6363，则必须分多次存储。，则必须分多次存储。对于长度大于对于长度大于1 1的行程，编码时先存入其行程长度（长度的
24、行程，编码时先存入其行程长度（长度L L加加上上192192即即0 xC00 xC0），再存入该行程的代表值，），再存入该行程的代表值，行程长度和行程的代表行程长度和行程的代表值分别占一字节。值分别占一字节。对于长度为对于长度为1 1的行程，即单个像素，如果该像素的值小于或的行程，即单个像素，如果该像素的值小于或等于等于0 xC00 xC0， 则编码时直接存入该像素值，而不存储长度信息；否则编码时直接存入该像素值，而不存储长度信息；否则，先存入则，先存入0 xC10 xC1，再存入该像素值，这样做的目的是为了避免该，再存入该像素值，这样做的目的是为了避免该像素值被误认为长度信息。像素值被误认为
25、长度信息。例如，连续例如，连续100100个灰度值为个灰度值为0 x800 x80的像素，其编码的像素，其编码( (以十六进制表示以十六进制表示) )应为应为FF FF 80 25 8080 25 80。上面的编码中出现。上面的编码中出现FFFF的长度信息是由的长度信息是由6363与与0 xC00 xC0相加所得。相加所得。对对256256色色PCXPCX文件解码时，首先从压缩数据部分读取一个字节，文件解码时，首先从压缩数据部分读取一个字节，判断该值是否大于判断该值是否大于0 xC00 xC0，如果是，则表明该字节是行程长度信，如果是，则表明该字节是行程长度信息，息， 取其低六位（相当于减去取
26、其低六位（相当于减去0 xC00 xC0）作为行程长度）作为行程长度L L，读取下，读取下一个字节作为像素值并重复一个字节作为像素值并重复L L次存入图像数据缓冲区；否则，次存入图像数据缓冲区；否则， 直接将该字节存入图像数据缓冲区。直接将该字节存入图像数据缓冲区。几乎所有的图像应用软件都支持几乎所有的图像应用软件都支持PCXPCX文件格式，但由于它的压缩文件格式，但由于它的压缩比不高，比不高， 因而现在用得不是很多。因而现在用得不是很多。LZW编码 LZW（Lempel-Ziv & Welch）编码又称字串表编码， 属于一种无损编码，是Welch将Lempel和Ziv所提出的无损压缩技术改进
27、后的压缩方法。LZW编码与行程编码类似， 也是对字符串进行编码从而实现压缩，但它在编码的同时还生成了特定字符串以及与之对应的索引字符串表。LZWLZW编码的基本思想是：在编码过程中，将所遇到的字符串编码的基本思想是：在编码过程中，将所遇到的字符串建立一个字符串表，表中的每个字符串都对应一个索引，编码建立一个字符串表，表中的每个字符串都对应一个索引，编码时用该字符串在字串表中的索引来代替原始的数据串。时用该字符串在字串表中的索引来代替原始的数据串。 例如，一幅例如，一幅8 8位的灰度图像，我们可以采用位的灰度图像，我们可以采用1212位来表示每个字符串的索位来表示每个字符串的索引，前引，前256
28、256个索引用于对应可能出现的个索引用于对应可能出现的256256种灰度，由此可建立一个初始的字种灰度，由此可建立一个初始的字符串表，而剩余的符串表，而剩余的38403840个索引就可分配给在压缩过程中出现的新字符串，这个索引就可分配给在压缩过程中出现的新字符串，这样就生成了一个完整的字符串表，压缩数据就可以只保存它在字符串表中的样就生成了一个完整的字符串表，压缩数据就可以只保存它在字符串表中的索引，从而达到压缩数据的目的。索引，从而达到压缩数据的目的。 字符串表是在压缩过程中动态生成的，不必将它保存在压缩字符串表是在压缩过程中动态生成的，不必将它保存在压缩文件里，文件里，因为解压缩时字符串表
29、可以由压缩文件中的信息重新因为解压缩时字符串表可以由压缩文件中的信息重新生成。生成。 GIFGIF（Graphics Interchange FormatGraphics Interchange Format）最初于）最初于19871987年开发年开发的一种压缩位图格式。的一种压缩位图格式。它可支持多达它可支持多达 256 256 种的颜色，具有极佳种的颜色，具有极佳的压缩效率，已成为的压缩效率，已成为Internet Internet 上一种流行的文件格式。上一种流行的文件格式。 GIF GIF图像文件采用的是一种改良的图像文件采用的是一种改良的LZWLZW压缩算法，压缩算法， 通常称为通常
30、称为GIF-LZWGIF-LZW压缩算法。压缩算法。GIFGIF图像文件以块（又称为区域结构）的方图像文件以块（又称为区域结构）的方式来存储图像相关的信息。式来存储图像相关的信息。 设设S1S1、S2S2为两个存放字符串的临时变量，为两个存放字符串的临时变量，LZW_CLEARLZW_CLEAR和和LZW_EOILZW_EOI分别为字符表初始化标志和编码结束标志，分别为字符表初始化标志和编码结束标志，GIF-LZWGIF-LZW的的编码步骤如下：编码步骤如下：（1 1）根据图像中使用的颜色数初始化一个字串表，字串表中）根据图像中使用的颜色数初始化一个字串表，字串表中的每个颜色对应一个索引。在初
31、始字串表的末尾再添加两个符的每个颜色对应一个索引。在初始字串表的末尾再添加两个符号（号（LZW_CLEARLZW_CLEAR和和LZW_EOILZW_EOI）的索引。设置字符串变量）的索引。设置字符串变量S1S1、 S2S2并并初始化为空。初始化为空。 （2 2） 接着输出接着输出LZW_CLEARLZW_CLEAR在字串表中的索引。在字串表中的索引。 （3 3）从图像数据流中第一个字符（假设数据以字符串表示）从图像数据流中第一个字符（假设数据以字符串表示）开始，开始， 每次读取一个字符，将其赋给字符串变量每次读取一个字符，将其赋给字符串变量S2S2。 （4 4）判断）判断“S1+S2S1+S
32、2”是否已存在于字串表中。如果字串表中是否已存在于字串表中。如果字串表中存在存在“S1+S2S1+S2”，则，则S1=S1+S2S1=S1+S2；否则，输出；否则，输出S1S1在字串表中的索引，在字串表中的索引， 并在字串表末尾为并在字串表末尾为“S1+S2”S1+S2”添加索引，同时，添加索引，同时，S1=S2S1=S2。（5 5）重复第）重复第3 3和第和第4 4步，步， 直到所有字符读完为止。直到所有字符读完为止。 （6 6）输出）输出S1S1中的字符串在字串表中的索引，然后输出结束中的字符串在字串表中的索引，然后输出结束标志标志LZW_EOILZW_EOI的索引，编码完毕。的索引，编码
33、完毕。 GIF-LZWGIF-LZW的解码过程比较复杂，它和编码过程正好相反，即的解码过程比较复杂，它和编码过程正好相反，即将编码后的码字转换成对应的字符串，重新生成字串表，然后将编码后的码字转换成对应的字符串，重新生成字串表，然后依次输出对应的字符串即可。依次输出对应的字符串即可。LZWLZW编码实例编码实例 设有一来源于设有一来源于4 4色（以色（以a a、b b、c c、d d表示）图像的数据流表示）图像的数据流aabcabbbbdaabcabbbbd，现对其进行，现对其进行LZWLZW编码。编码过程如下：编码。编码过程如下： 编码前，首先需要初始化一个字符串表编码前，首先需要初始化一个
34、字符串表。由于图像中只有。由于图像中只有四种颜色，因而我们可以只用四种颜色，因而我们可以只用4 4比特表示字符串表中每个字符串比特表示字符串表中每个字符串的索引，表中的前的索引，表中的前4 4项代表项代表4 4种颜色，后两项分别表示初始化和种颜色，后两项分别表示初始化和图像结束标志，建立的初始化字符串表如表所示。接着把图像结束标志，建立的初始化字符串表如表所示。接着把S1S1和和S2S2初始化为空（即初始化为空（即NULLNULL），输出），输出LZW_CLEARLZW_CLEAR的在字符串表中的索的在字符串表中的索引值引值4H4H， 接下来是对图像数据的编码。接下来是对图像数据的编码。初始化
35、字符串表初始化字符串表 字符串索引a0Hb1Hc2 H d3HLZW_CLEAR4HLZW_EOI5H读取图像数据流的第一个字符读取图像数据流的第一个字符“a a”，赋给，赋给S2S2， 因因S1+S2=S1+S2=“a a”已存在字串表中，所以已存在字串表中，所以S1=S1+S2=“a”S1=S1+S2=“a”。 接着读入下一个字符接着读入下一个字符“a a”赋给赋给S2S2， 因因S1+S2=S1+S2=“aaaa”不存在不存在于字串表中，于字串表中， 所以输出所以输出S1=S1=“a a”的索引的索引0H0H，同时在字符串表末，同时在字符串表末尾添加新字符串尾添加新字符串“aaaa”的索
36、引的索引6H6H， 并使并使S1=S2=S1=S2=“a a”。 依次读取数据流中的每个字符，如果依次读取数据流中的每个字符，如果S1+S2S1+S2没有出现在字符串没有出现在字符串表中，则输出表中，则输出S1S1中的字符串的索引，并在字符串表末尾为新字符中的字符串的索引，并在字符串表末尾为新字符串串S1+S2S1+S2添加索引，并使添加索引，并使S1=S2S1=S2； 否则，不输出任何结果，只是否则，不输出任何结果，只是使使S1=S1+S2S1=S1+S2。所有字符处理完毕后，输出。所有字符处理完毕后，输出S1S1中的字符串的索引，中的字符串的索引，最后输出结束标志最后输出结束标志LZW_E
37、OILZW_EOI的索引。至此，编码完毕，完整的编的索引。至此，编码完毕，完整的编码过程如下表所示，最后的编码结果为码过程如下表所示，最后的编码结果为“4001271B35”4001271B35”（以十六（以十六进制表示）。进制表示）。GIF-LZW编码过程编码过程 HuffmanHuffman编码编码 Huffman Huffman编码是编码是5050年代提出的一种基于统计的无损编码方年代提出的一种基于统计的无损编码方法，它利用变长的码来使冗余量达到最小。法，它利用变长的码来使冗余量达到最小。 HuffmanHuffman编码原理：常出现的字符用较短的码代表，不常编码原理：常出现的字符用较短
38、的码代表，不常出现的字符用较长的码代表。出现的字符用较长的码代表。静态静态HuffmanHuffman编码使用一棵依据编码使用一棵依据字符出现的概率事先生成好的编码树进行编码。而动态字符出现的概率事先生成好的编码树进行编码。而动态HuffmanHuffman编码需要在编码的过程中建立编码树。编码需要在编码的过程中建立编码树。 由于由于HuffmanHuffman编码所得到的平均码字长度可以接近信源的编码所得到的平均码字长度可以接近信源的熵，因此在变长编码中是最佳的编码方法，故也称为熵，因此在变长编码中是最佳的编码方法，故也称为熵编码熵编码。1 1、哈夫曼编码的理论基础、哈夫曼编码的理论基础 根
39、据信息论中信源编码理论，当平均码长根据信息论中信源编码理论，当平均码长R R大于等于图像熵大于等于图像熵H H时，总可设计出一种无失真编码。时，总可设计出一种无失真编码。 当平均码长等于或很接近于（但不大于）图像熵时，称此编当平均码长等于或很接近于（但不大于）图像熵时，称此编码方法为最佳编码，此时不会引起图像失真；当平均码长大于图码方法为最佳编码，此时不会引起图像失真；当平均码长大于图像熵时，压缩比较高，但会引起图像失真。像熵时，压缩比较高，但会引起图像失真。 在变长编码中，如果码字长度严格按照对应符号出现的概率在变长编码中，如果码字长度严格按照对应符号出现的概率大小逆序排列，则其平均码字长度
40、为最小，这就是变长最佳编码大小逆序排列，则其平均码字长度为最小，这就是变长最佳编码定理。定理。变长最佳编码定理是哈夫曼编码的理论基础。设变长最佳编码定理是哈夫曼编码的理论基础。设D D为编码所为编码所使用的数制，则变长最佳编码的平均码字长度使用的数制，则变长最佳编码的平均码字长度R R的范围为的范围为 111HHRgDgD 2 2、哈夫曼编码算法、哈夫曼编码算法 （1 1）首先统计信源中各符号出现的概率，按符号出现的概）首先统计信源中各符号出现的概率，按符号出现的概率从大到小排序。率从大到小排序。 （2 2）把最小的两个概率相加合并成新的概率，）把最小的两个概率相加合并成新的概率， 与剩余的概
41、与剩余的概率组成新的概率集合。率组成新的概率集合。 （3 3） 对新的概率集合重新排序，对新的概率集合重新排序， 再次把其中最小的两个再次把其中最小的两个概率相加，概率相加， 组成新的概率集合。如此重复进行，直到最后两个组成新的概率集合。如此重复进行，直到最后两个概率的和为概率的和为1 1。（4 4） 分配码字。码字分配从最后一步开始反向进行，分配码字。码字分配从最后一步开始反向进行， 对对于每次相加的两个概率，给大的赋于每次相加的两个概率，给大的赋“0 0”， 小的赋小的赋“1 1”（也可（也可以全部相反，以全部相反， 如果两个概率相等，如果两个概率相等， 则从中任选一个赋则从中任选一个赋“
42、0 0”， 另一个赋另一个赋“1 1”即可），即可）， 读出时由该符号开始一直走到最后的读出时由该符号开始一直走到最后的概率和概率和“1 1”， 将路线上所遇到的将路线上所遇到的“0 0”和和“1”1”按最低位到最按最低位到最高位的顺序排好，就是该符号的哈夫曼编码。高位的顺序排好，就是该符号的哈夫曼编码。例例设一幅灰度级为8（分别用S0、S1、S2、S3、S4、S5、S6、S7表示）的图像中，各灰度所对应的概率分别为0.40、0.18、0.10、0.10、0.07、0.06、0.05、0.04。现对其进行哈夫曼编码编码过程如图所示，具体步骤如下：(1)首先对信源概率从大到小排序，选出最小的两个
43、概率（0.04和0.05），相加得0.09，与其他概率组成新的概率集合0.40，0.18，0.10，0.10，0.07，0.06，0.09。(2)对新的概率集合重新排序，选出最小的两个概率（0.06和0.07），相加得0.13，组成新的概率集合0.40，0.18，0.10，0.10，0.09，0.13。(3)对新的概率集合重新排序，选出最小的两个概率（0.10和0.09），相加得0.19，组成新的概率集合0.40，0.18，0.13，0.10，0.19。(4)对新的概率集合重新排序，选出最小的两个概率（0.13和0.10），相加得0.23，组成新的概率集合0.40，0.19，0.18，0.23
44、。(5)对新的概率集合重新排序，选出最小的两个概率（0.19和0.18），相加得0.37，组成新的概率集合0.40，0.23，0.37。(6)对新的概率集合重新排序，选出最小的两个概率（0.23和0.37），相加得0.60，组成新的概率集合0.40，0.60。(7)直到最后两个概率（0.60和0.40）相加和为1。(8)分配码字。从最后一步反向进行，首先给最后相加的两个概率（0.60和0.40）分配码字，由于0.60大于0.40，于是给0.60赋“0”，给0.40赋“1”。如此依次给每次相加的两个概率分配码字。(9)最后写出每个符号的哈夫曼编码。以符号S1（对应的概率为0.18）为例，在从0.
45、18到1.0的路径上，它所遇到的赋值（“0”或“1”）依次为1、0、0，将其反向排列成“001”，于是就形成了符号S1的哈夫曼码字“001”。哈夫曼编码过程1S00.400.180.100.100.070.060.050.040.090.130.190.230.370.601.00011111100000010010110000010001010001000011码字信源符号 出现概率S1S2S3S4S5S6S7上述哈夫曼编码方法形成的码字是可识别的，即能够保证一个符号的码字不会与另一个符号的码字的前几位相同。比如说，如果S0的码字为1，S1的码字为001，而S2的码字为011，则当编码序列中
46、出现0011时，就不能判别它是S2的码字还是S1的码字后面跟了一个S0的码字1。下面来看一下哈夫曼编码的编码效率。平均码长R为61. 204. 0505. 0506. 0407. 0410. 0410. 0318. 0340. 011NkkkPBR数字图像的熵H为11(0.4 1 0.40.18 1 0.180.1 1 0.1 0.1 1 0.10.07 1 0.40.06 1 0.060.05 1 0.050.04 1 0.04)2.55NkkkHP gPgggggggg 则哈夫曼编码的编码效率为%8 .97%10061. 255. 2%100RH由此可见，哈夫曼编码的编码效率是相当高的，其
47、冗余度只由此可见，哈夫曼编码的编码效率是相当高的，其冗余度只有有2.2%2.2%。如果采用等长编码，由于有。如果采用等长编码，由于有8 8种灰度级，则每种灰度级种灰度级，则每种灰度级别至少需要别至少需要3 3比特来表示，对于例中的图像而言，其编码的平均比特来表示，对于例中的图像而言，其编码的平均码长为码长为3 3，编码效率为，编码效率为85%85%。 对不同概率分布的信源，哈夫曼编码的编码效率有所差别。对不同概率分布的信源，哈夫曼编码的编码效率有所差别。根据信息论中信源编码理论，对于二进制编码，当信源概率为根据信息论中信源编码理论，对于二进制编码，当信源概率为2 2的负幂次方时，哈夫曼编码的编
48、码效率可达的负幂次方时，哈夫曼编码的编码效率可达100%100%，其平均码字长，其平均码字长度也很短，而当信源概率为均匀分布时，其编码效果明显降低。度也很短，而当信源概率为均匀分布时，其编码效果明显降低。在下表中，显然，第二种情况的概率分布也服从在下表中，显然，第二种情况的概率分布也服从2 2的负幂次方，的负幂次方，故其编码效率故其编码效率也可以达到也可以达到100%100%， 但由于它服从均匀分布，其但由于它服从均匀分布，其熵最大，平均编码长度很大，因此从其他指标看（如，熵最大，平均编码长度很大，因此从其他指标看（如， 压缩比压缩比r r），其编码效率最低。），其编码效率最低。也就是说，在信
49、源概率接近于均匀分布也就是说，在信源概率接近于均匀分布时，一般不使用哈夫曼编码。时，一般不使用哈夫曼编码。 啥夫曼编码在不同概率分布下的编码效果对比啥夫曼编码在不同概率分布下的编码效果对比 3.2 有损编码有损编码 量化量化 将图像用较少的灰度级别来表示是最简单的减小数将图像用较少的灰度级别来表示是最简单的减小数据量的方法，这种方法就是标量量化方法。更一般的情据量的方法，这种方法就是标量量化方法。更一般的情况是，针对连续量的采样过程，量化是用有限个状态来况是，针对连续量的采样过程，量化是用有限个状态来表示连续值。表示连续值。预测编码预测编码 预测编码根据数据在时间和空间上的相关性，根据统计预测
50、编码根据数据在时间和空间上的相关性，根据统计模型利用已有样本对新样本进行预测，将样本的实际值与其模型利用已有样本对新样本进行预测，将样本的实际值与其预测值相减得到误差值，再对误差值进行编码。由于通常误预测值相减得到误差值，再对误差值进行编码。由于通常误差值比样本值小得多，因而可以达到数据压缩的效果。差值比样本值小得多，因而可以达到数据压缩的效果。 模拟量到数字量的转换过程是脉冲编码调制过程模拟量到数字量的转换过程是脉冲编码调制过程PCM PCM ，也称也称PCMPCM编码。对于图像而言，直接以编码。对于图像而言，直接以PCMPCM编码，存储量很大编码，存储量很大。预测编码可以利用相邻象素之间的
