《多媒体数据压缩编码介绍(ppt-77页)课件》由会员分享，可在线阅读，更多相关《多媒体数据压缩编码介绍(ppt-77页)课件（77页珍藏版）》请在金锄头文库上搜索。
1、第第2章章多媒体数据压缩基础多媒体数据压缩基础2.1 2.1 数据压缩编码简介数据压缩编码简介数据压缩编码简介数据压缩编码简介2.2 2.2 统计编码统计编码统计编码统计编码2.3 2.3 词典编码词典编码词典编码词典编码2.4 2.4 预测编码预测编码预测编码预测编码2.5 2.5 变换编码变换编码变换编码变换编码2.1 2.1 数据压缩编码简介数据压缩编码简介数据压缩编码简介数据压缩编码简介2.1.12.1.1 数据压缩的必要性数据压缩的必要性数据压缩的必要性数据压缩的必要性 文本文本文本文本: : 若若若若10247681024768显示分辨率、显示分辨率、显示分辨率、显示分辨率、161
2、61616点阵文字、点阵文字、点阵文字、点阵文字、4 Byte/4 Byte/字，则一屏汉字的总字，则一屏汉字的总字，则一屏汉字的总字，则一屏汉字的总数据量为数据量为数据量为数据量为: : (1024/16)(768/16)4 = 12288 Byte (12KB) (1024/16)(768/16)4 = 12288 Byte (12KB) 图片图片图片图片：若采用：若采用：若采用：若采用10247681024768显示分辨率，则满屏图像的总数据量为显示分辨率，则满屏图像的总数据量为显示分辨率，则满屏图像的总数据量为显示分辨率，则满屏图像的总数据量为: : 1024768248 = 2359
3、296Byte (2304 KB) 1024768248 = 2359296Byte (2304 KB) 音频：音频：音频：音频： 若采样频率为若采样频率为若采样频率为若采样频率为44100Hz44100Hz，16bit (2Byte)16bit (2Byte)，立体声，立体声，立体声，立体声 (2(2声道声道声道声道) )， 则则则则1 1分钟的总数据量为分钟的总数据量为分钟的总数据量为分钟的总数据量为: : 441002 Byte2 (STEREO) 60s = 10336 KB (10MB) 441002 Byte2 (STEREO) 60s = 10336 KB (10MB) 视频：视
4、频：视频：视频：若图像分辨率为若图像分辨率为若图像分辨率为若图像分辨率为352240352240，2424位色彩，帧率为位色彩，帧率为位色彩，帧率为位色彩，帧率为2525帧帧帧帧/ /秒，秒，秒，秒， 则则则则1 1分钟的总数据量为分钟的总数据量为分钟的总数据量为分钟的总数据量为: : 352240 3 Byte2560s = 371250 KB (362.55MB) 352240 3 Byte2560s = 371250 KB (362.55MB)分钟分钟数字数字音音频信号需要的存储空间频信号需要的存储空间1 1分钟数字视频信号需要的存储空间分钟数字视频信号需要的存储空间1 12.1.22.
5、1.2 数据压缩的可能性数据压缩的可能性数据压缩的可能性数据压缩的可能性 数据存在冗余数据存在冗余数据存在冗余数据存在冗余 ( (重复数据、可忽略数据重复数据、可忽略数据重复数据、可忽略数据重复数据、可忽略数据) ) 不敏感因素不敏感因素不敏感因素不敏感因素 ( (颜色、亮度、频率、细节颜色、亮度、频率、细节颜色、亮度、频率、细节颜色、亮度、频率、细节) )24 24 位颜色位颜色位颜色位颜色 (16,777,216(16,777,216色色色色) )8 8位颜色位颜色位颜色位颜色 (256(256色色色色) )数据冗余数据冗余l基本概念：基本概念：基本概念：基本概念：l冗余冗余冗余冗余 信息
6、所具有的各种性质中多余的无信息所具有的各种性质中多余的无信息所具有的各种性质中多余的无信息所具有的各种性质中多余的无用内容用内容用内容用内容l冗余度冗余度冗余度冗余度 多余的无用内容的程度多余的无用内容的程度多余的无用内容的程度多余的无用内容的程度信息量与冗余的关系信息量与冗余的关系信息量与冗余的关系信息量与冗余的关系I = D duI I 信息量信息量信息量信息量 D D 数据量数据量数据量数据量 du du 冗余量，包含在冗余量，包含在冗余量，包含在冗余量，包含在D D中中中中数据冗余类型数据冗余类型l常见的冗余类型：常见的冗余类型：常见的冗余类型：常见的冗余类型：1 1、空间冗余、空间冗
7、余、空间冗余、空间冗余2 2、时间冗余、时间冗余、时间冗余、时间冗余3 3、结构冗余、结构冗余、结构冗余、结构冗余4 4、视觉冗余、视觉冗余、视觉冗余、视觉冗余5 5、知识冗余、知识冗余、知识冗余、知识冗余6 6、信息熵冗余、信息熵冗余、信息熵冗余、信息熵冗余1.1.1.1.空间冗余空间冗余空间冗余空间冗余 规则物体的物理相关性规则物体的物理相关性规则物体的物理相关性规则物体的物理相关性2.2.2.2.时间冗余时间冗余时间冗余时间冗余 视频、动画前后画面间的相视频、动画前后画面间的相视频、动画前后画面间的相视频、动画前后画面间的相关性关性关性关性3.3.3.3.结构冗余结构冗余结构冗余结构冗余
8、 规则纹理、相互重叠的结构表规则纹理、相互重叠的结构表规则纹理、相互重叠的结构表规则纹理、相互重叠的结构表面面面面2 22424色色色色2 28 8色色色色4.4.4.4. 视觉冗余视觉冗余视觉冗余视觉冗余 视觉敏感度非均匀、非线性视觉敏感度非均匀、非线性视觉敏感度非均匀、非线性视觉敏感度非均匀、非线性5.5.5.5. 知识冗余知识冗余知识冗余知识冗余 凭借经验识别凭借经验识别凭借经验识别凭借经验识别6.6.6.6. 信息熵冗余信息熵冗余信息熵冗余信息熵冗余l也称编码冗余：也称编码冗余：也称编码冗余：也称编码冗余：l如果表示多媒体内容使用的平均比特数如果表示多媒体内容使用的平均比特数如果表示多
9、媒体内容使用的平均比特数如果表示多媒体内容使用的平均比特数大于该消息的信息熵，则信源中存在冗大于该消息的信息熵，则信源中存在冗大于该消息的信息熵，则信源中存在冗大于该消息的信息熵，则信源中存在冗余，即信息熵冗余。余，即信息熵冗余。余，即信息熵冗余。余，即信息熵冗余。l例如：图像中平均每个像素使用的比特例如：图像中平均每个像素使用的比特例如：图像中平均每个像素使用的比特例如：图像中平均每个像素使用的比特数大于该图像的信息熵，则图像中存在数大于该图像的信息熵，则图像中存在数大于该图像的信息熵，则图像中存在数大于该图像的信息熵，则图像中存在冗余，这种冗余即为信息熵冗余。冗余，这种冗余即为信息熵冗余。
10、冗余，这种冗余即为信息熵冗余。冗余，这种冗余即为信息熵冗余。2.1.32.1.3 数据压缩技术的重要指标数据压缩技术的重要指标数据压缩技术的重要指标数据压缩技术的重要指标 压缩比压缩比压缩比压缩比: : 压缩过程中输入数据量与输出数据量之比压缩过程中输入数据量与输出数据量之比压缩过程中输入数据量与输出数据量之比压缩过程中输入数据量与输出数据量之比 恢复质量（失真度）恢复质量（失真度）恢复质量（失真度）恢复质量（失真度）: : 解压后的恢复效果要好解压后的恢复效果要好解压后的恢复效果要好解压后的恢复效果要好 算法的复杂性和运算速度算法的复杂性和运算速度算法的复杂性和运算速度算法的复杂性和运算速度
11、2.1.42.1.4 数据压缩编码方法分类数据压缩编码方法分类数据压缩编码方法分类数据压缩编码方法分类分类方法一：根据解码后是否能够完全无失真地恢复进行分类分类方法一：根据解码后是否能够完全无失真地恢复进行分类分类方法一：根据解码后是否能够完全无失真地恢复进行分类分类方法一：根据解码后是否能够完全无失真地恢复进行分类1 1）无损压缩（可逆压缩）无损压缩（可逆压缩）无损压缩（可逆压缩）无损压缩（可逆压缩）冗余压缩冗余压缩冗余压缩冗余压缩 其原理是在压缩时去除或减少冗余值，而在解压缩时其原理是在压缩时去除或减少冗余值，而在解压缩时其原理是在压缩时去除或减少冗余值，而在解压缩时其原理是在压缩时去除或
12、减少冗余值，而在解压缩时重新将这些值插入到数据中，恢复原始数据。重新将这些值插入到数据中，恢复原始数据。重新将这些值插入到数据中，恢复原始数据。重新将这些值插入到数据中，恢复原始数据。 压缩比较低，一般在压缩比较低，一般在压缩比较低，一般在压缩比较低，一般在2 2：1515：1 1，多用于文本数据，多用于文本数据，多用于文本数据，多用于文本数据的压缩。的压缩。的压缩。的压缩。 典型的编码方法有：香农典型的编码方法有：香农典型的编码方法有：香农典型的编码方法有：香农- -范诺码、范诺码、范诺码、范诺码、HuffmanHuffman编码、编码、编码、编码、算术编码、行程编码、算术编码、行程编码、算
13、术编码、行程编码、算术编码、行程编码、 LZW LZW 编码编码编码编码2.1.42.1.4 数据压缩编码方法分类数据压缩编码方法分类数据压缩编码方法分类数据压缩编码方法分类分类方法一：根据解码后是否能够完全无失真地恢复进行分类分类方法一：根据解码后是否能够完全无失真地恢复进行分类分类方法一：根据解码后是否能够完全无失真地恢复进行分类分类方法一：根据解码后是否能够完全无失真地恢复进行分类 2 2）有损压缩）有损压缩）有损压缩）有损压缩 指使用压缩后的数据进行重构，重构后的数据与原指使用压缩后的数据进行重构，重构后的数据与原指使用压缩后的数据进行重构，重构后的数据与原指使用压缩后的数据进行重构，
14、重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的来的数据有所不同，但不影响人对原始资料表达的来的数据有所不同，但不影响人对原始资料表达的来的数据有所不同，但不影响人对原始资料表达的信息造成误解。信息造成误解。信息造成误解。信息造成误解。 图像和声音的压缩就可以采用有损压缩，因为其中图像和声音的压缩就可以采用有损压缩，因为其中图像和声音的压缩就可以采用有损压缩，因为其中图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所包含的数据往往多于我们的视觉系统和听觉系统所包含的数据往往多于我们的视觉系统和听觉系统所包含的数据往往多于我们的视觉系统和听觉系统
15、所能接收的信息，丢掉一些数据而不至于对声音或者能接收的信息，丢掉一些数据而不至于对声音或者能接收的信息，丢掉一些数据而不至于对声音或者能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。图像所表达的意思产生误解，但可大大提高压缩比。图像所表达的意思产生误解，但可大大提高压缩比。图像所表达的意思产生误解，但可大大提高压缩比。 典型的编码方法有：典型的编码方法有：典型的编码方法有：典型的编码方法有：PCM PCM 编码、预测编码、变换编码、预测编码、变换编码、预测编码、变换编码、预测编码、变换编码、子带编码等。编码、子带编码等。编码、子带编码等。编码、子带编码
16、等。2.1.42.1.4 数据压缩编码方法分类数据压缩编码方法分类数据压缩编码方法分类数据压缩编码方法分类分类方法二：压缩编码方法的原理进行分类分类方法二：压缩编码方法的原理进行分类分类方法二：压缩编码方法的原理进行分类分类方法二：压缩编码方法的原理进行分类1 1）统计编码）统计编码）统计编码）统计编码: Huffman: Huffman，ShannonShannon，REL,REL,词典编码词典编码词典编码词典编码2 2）预测编码）预测编码）预测编码）预测编码: PCM: PCM，DPCMDPCM，DMDM，LPCLPC 变换编码变换编码变换编码变换编码: DCT: DCT 子带（子带（子带
17、（子带（sub-band)sub-band)编码编码编码编码 模型编码模型编码模型编码模型编码压缩技术分类通用数据压缩（均为无损压缩）通用数据压缩（均为无损压缩）通用数据压缩（均为无损压缩）通用数据压缩（均为无损压缩）多媒体数据压缩（无损和有损压缩）多媒体数据压缩（无损和有损压缩）多媒体数据压缩（无损和有损压缩）多媒体数据压缩（无损和有损压缩）基于统计模型基于统计模型基于统计模型基于统计模型的压缩技术的压缩技术的压缩技术的压缩技术基于字典模型基于字典模型基于字典模型基于字典模型的压缩技术的压缩技术的压缩技术的压缩技术HuffmanHuffman编码编码编码编码算术编码算术编码算术编码算术编码L
18、Z77LZ77LZ78LZ78LZWLZW图像压缩图像压缩图像压缩图像压缩音频和视频压缩音频和视频压缩音频和视频压缩音频和视频压缩MPEGMPEG等等等等二值图像二值图像二值图像二值图像CCITTCCITTJBIGJBIG等等等等灰度图像灰度图像灰度图像灰度图像FELICSFELICSJPEGJPEG等等等等彩色图像彩色图像彩色图像彩色图像RLERLE编码编码编码编码JPEGJPEG等等等等矢量图像矢量图像矢量图像矢量图像PostScriptPostScriptWMFWMFCADCAD等等等等压缩技术的应用压缩技术的应用电报、传真电报、传真(CCITT)通讯通讯(Modem/网络协议网络协议)
19、存储存储(压缩池压缩池)文件系统文件系统(压缩扇区压缩扇区)图像图像(GIF/TIFF/JPEG)音频音频(MP3)视频视频(MPEG/RM)数据库数据库(B+树树)归档归档(TAR/ZIP)密码学密码学(消除数据的原始特征消除数据的原始特征)全文索引全文索引(倒排索引表倒排索引表)编译编译(JAVA)程序设计程序设计(算法算法/空间和时间效空间和时间效率率)人工智能人工智能(专家系统专家系统/知识树知识树)2.2.1 2.2.1 信息熵及基本概念信息熵及基本概念信息熵及基本概念信息熵及基本概念 1信息量信息量信息量是指从N个相等的可能事件中选出一个事件所需要的信息度量或含量，也就是在辨识N个
20、事件中特定的一个事件的过程中所需要提问“是或否”的最少次数。 设从N个数中选定任一个数xj的概率为p（xj），假定选定任意一个数的概率都相等，即p（ xj ）1/N，因此定义其信息量为:式中，P(xj)是信源X发出xj的概率。I(xj)的含义是，信源X发出xj这个消息（随机事件）后，接收端收到的信息的量度。2.2 2.2 统计编码统计编码统计编码统计编码信息熵信息熵熵熵来源于40年代由Claude Shannon创立的信息论中的一条定理，这一定理借用了热力学中的名词“熵”( Entropy )来表示一条信息中真正需要编码的信息量。信源S发出的xj（j=1,2,n）共n个随机事件的自信息统计平均
21、，即H(X)称为信源X的“熵”，即信源X发出任意一个随机变量的平均信息量。其中：等概率事件信源的熵最大，为：当P(x1)1时，P(x2)P(x3)P(xj)0，由（4-6）式得此时熵为由上可得熵的范围为：由上可得熵的范围为：在编码中用熵值来衡量是否为最佳编码。若以Lc表示编码器输出码字的平均码长，则当LcH(S) 有冗余，不是最佳。LcH(S) 不可能。LcH(S) 最佳编码（Lc稍大于H(S)）。熵值为平均码长Lc的下限。平均码长Lc的计算公式为：（j=1,2,n）其中：P(xj) 是信源X发出xj的概率，L(xj)为xj的编码长度。平均码长与熵关系平均码长与熵关系熵的计算范例熵的计算范例例
22、：对信息例：对信息例：对信息例：对信息aabbaccbaaaabbaccbaa，字符串长度为字符串长度为字符串长度为字符串长度为 10 10，字符，字符，字符，字符a a、b b、c c分别出现了分别出现了分别出现了分别出现了5 5、3 3、2 2次，则次，则次，则次，则I Ia a=-log=-log2 2(0.5)=1(0.5)=1比特比特比特比特 I Ib b=-log=-log2 2(0.3)=1.737 (0.3)=1.737 比特比特比特比特 I Ic c=-log=-log2 2(0.2)=2.322 (0.2)=2.322 比特比特比特比特HH（S S）= 0.5I= 0.5I
23、a a +0. 3I +0. 3Ib b +0. 2I +0. 2Ic c =1.4855 =1.4855比特比特比特比特/ /符号符号符号符号如采用等长编码，则每个字符需要位；如采用等长编码，则每个字符需要位；如采用等长编码，则每个字符需要位；如采用等长编码，则每个字符需要位；总的码长总的码长总的码长总的码长: L=5*: L=5*+3* +3* +2*+2* = = 位位位位对比一下，我们用对比一下，我们用对比一下，我们用对比一下，我们用ASCIIASCII编码表示该信息需要编码表示该信息需要编码表示该信息需要编码表示该信息需要8080位。位。位。位。l基本思想：基本思想：主要针对无记忆信
24、源，根主要针对无记忆信源，根据信息（符号）出现概率的分布特征据信息（符号）出现概率的分布特征进行压缩编码，寻找概率与码字长度进行压缩编码，寻找概率与码字长度之间的最佳匹配之间的最佳匹配:l主要方法：主要方法：包括哈夫曼编码、算术编包括哈夫曼编码、算术编码、行程编码等码、行程编码等统计编码原理统计编码原理统计编码原理统计编码原理2.2.1 2.2.1 哈夫曼编码哈夫曼编码哈夫曼编码哈夫曼编码l哈夫曼哈夫曼1952年提出年提出l主要思想：主要思想：在变字长编码中，对于出现在变字长编码中，对于出现概率大的信息符号编以短字长的码，对概率大的信息符号编以短字长的码，对于概率小的符号编以长字长的码。于概率
25、小的符号编以长字长的码。l最佳性：最佳性：如果码字长度严格按所对应符如果码字长度严格按所对应符号出现概率大小逆序排列，则平均码字号出现概率大小逆序排列，则平均码字长度一定小于其他以任何符号顺序排列长度一定小于其他以任何符号顺序排列方式得到的平均码字长度。方式得到的平均码字长度。1.将符号按出现概率由大到小排列，给最后两将符号按出现概率由大到小排列，给最后两个符号赋予一个二进制码，概率大的赋个符号赋予一个二进制码，概率大的赋1，小的赋小的赋0（反之亦可）（反之亦可）2.把最后两个符号的概率合成一个概率，重复把最后两个符号的概率合成一个概率，重复上一步上一步3.重复步骤重复步骤2，直到最后只剩下两
26、个概率为止，直到最后只剩下两个概率为止4.将每个符号所对应的分支的将每个符号所对应的分支的0,1反序排出即反序排出即可可哈夫曼编码步骤哈夫曼编码步骤0.230.230.210.210.180.180.150.150.130.130.070.070.030.03概率概率概率概率 1 1 0 00.100.101 1 0 00.230.23 1 1 0 00.330.33 1 1 0 00.440.44 1 1 0 00.560.560 0 1 11 1编码编码编码编码 01 01 00 00 111 111 110 110 101 1011001100110001000可以看出，概率大的符号其编
27、码短，概率小的符号其可以看出，概率大的符号其编码短，概率小的符号其可以看出，概率大的符号其编码短，概率小的符号其可以看出，概率大的符号其编码短，概率小的符号其编码长，符号使用其编码来表示，达到数据压缩目的编码长，符号使用其编码来表示，达到数据压缩目的编码长，符号使用其编码来表示，达到数据压缩目的编码长，符号使用其编码来表示，达到数据压缩目的A1A1A2A2A3A3A4A4A5A5A6A6A7A7符号符号符号符号哈夫曼编码举例哈夫曼编码举例编码编码编码编码 01 01 00 00 111 111 110 110 101 1011001100110001000码长码长码长码长 2 2 2 2 3
28、3 3 3 3 3 4 4 4 4码字的平均长度：码字的平均长度：可见，哈夫曼编码结果，其平可见，哈夫曼编码结果，其平均长度接近于信息符号的熵值，均长度接近于信息符号的熵值，但是仍有冗余但是仍有冗余哈夫曼编码性能分析哈夫曼编码性能分析信源的信息熵：信源的信息熵：哈夫曼编码练习哈夫曼编码练习哈夫曼编码特点哈夫曼编码特点l优点：优点：当信源符号概率是当信源符号概率是2的负幂次方时，的负幂次方时， Huffman 编码法编码效率达到编码法编码效率达到100%。一般。一般情况下，它的编码效率要比其它编码方法的情况下，它的编码效率要比其它编码方法的效率高，是最佳变长码。效率高，是最佳变长码。l 缺点：缺
29、点：Huffman 码依赖于信源的统计特性，码依赖于信源的统计特性，必须先统计得到信源的概率特性才能编码，必须先统计得到信源的概率特性才能编码，这就限制了实际的应用。通常可在经验基础这就限制了实际的应用。通常可在经验基础上预先提供上预先提供Huffman码表，此时性能有所下码表，此时性能有所下降。降。2.2.2 2.2.2 行程编码行程编码行程编码行程编码l最简单的编码方法之一。最简单的编码方法之一。l主要思想：主要思想：检测重复出现的比特或字符序检测重复出现的比特或字符序列，并用一个单独的值和一个计数值来取列，并用一个单独的值和一个计数值来取代。代。行程编码原理行程编码原理行程编码原理行程编
30、码原理 如图所示，假定一幅灰度图像，第如图所示，假定一幅灰度图像，第如图所示，假定一幅灰度图像，第如图所示，假定一幅灰度图像，第n n行的像素值为：行的像素值为：行的像素值为：行的像素值为： 用用用用RLERLE编码方法得到的代码为：编码方法得到的代码为：编码方法得到的代码为：编码方法得到的代码为：3 31 150508 84 41 116160 0。 代码斜体表示的数字是行程长度，斜体字后面的数字代代码斜体表示的数字是行程长度，斜体字后面的数字代代码斜体表示的数字是行程长度，斜体字后面的数字代代码斜体表示的数字是行程长度，斜体字后面的数字代表像素的颜色值。例如斜体字表像素的颜色值。例如斜体字
31、表像素的颜色值。例如斜体字表像素的颜色值。例如斜体字5050代表有连续代表有连续代表有连续代表有连续5050个像素具个像素具个像素具个像素具有相同的颜色值，它的颜色值是有相同的颜色值，它的颜色值是有相同的颜色值，它的颜色值是有相同的颜色值，它的颜色值是8 8。 对比对比对比对比RLERLE编码前后的代码数可以发现，在编码前要用编码前后的代码数可以发现，在编码前要用编码前后的代码数可以发现，在编码前要用编码前后的代码数可以发现，在编码前要用7373个代个代个代个代码表示这一行的数据，而编码后只要用码表示这一行的数据，而编码后只要用码表示这一行的数据，而编码后只要用码表示这一行的数据，而编码后只要
32、用1010个代码表示代表原来个代码表示代表原来个代码表示代表原来个代码表示代表原来的的的的7373个代码，压缩前后的数据量之比约为个代码，压缩前后的数据量之比约为个代码，压缩前后的数据量之比约为个代码，压缩前后的数据量之比约为7:17:1，即压缩比为，即压缩比为，即压缩比为，即压缩比为7:17:1。这说明这说明这说明这说明RLERLE确实是一种压缩技术，而且编码技术实用。确实是一种压缩技术，而且编码技术实用。确实是一种压缩技术，而且编码技术实用。确实是一种压缩技术，而且编码技术实用。消零(或消空白)法 将数字中连续的将数字中连续的“0”或文本中连续或文本中连续的空白用一个标识符的空白用一个标识
33、符(或特殊字符或特殊字符)后跟数后跟数字字N(连续连续“0”的个数的个数)来代替来代替。 如数字序列：如数字序列： 742300000000000000000055 编码为：编码为： 7423Z1855行程编码示例行程编码示例行程编码示例行程编码示例 RLERLE的性能好坏主要取决于图像本身的特点。的性能好坏主要取决于图像本身的特点。的性能好坏主要取决于图像本身的特点。的性能好坏主要取决于图像本身的特点。RLERLE压压压压缩编码尤其适用于计算机生成的图像，对减少图像文缩编码尤其适用于计算机生成的图像，对减少图像文缩编码尤其适用于计算机生成的图像，对减少图像文缩编码尤其适用于计算机生成的图像，
34、对减少图像文件的存储空间非常有效。件的存储空间非常有效。件的存储空间非常有效。件的存储空间非常有效。 然而，由于颜色丰富的自然图像在同一行上具有相同然而，由于颜色丰富的自然图像在同一行上具有相同然而，由于颜色丰富的自然图像在同一行上具有相同然而，由于颜色丰富的自然图像在同一行上具有相同颜色的连续像素往往很少，而连续几行都具有相同颜颜色的连续像素往往很少，而连续几行都具有相同颜颜色的连续像素往往很少，而连续几行都具有相同颜颜色的连续像素往往很少，而连续几行都具有相同颜色值的连续行数就更少，如果仍然使用色值的连续行数就更少，如果仍然使用色值的连续行数就更少，如果仍然使用色值的连续行数就更少，如果仍
35、然使用RLERLE编码方法，编码方法，编码方法，编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据不仅不能压缩图像数据，反而可能使原来的图像数据不仅不能压缩图像数据，反而可能使原来的图像数据不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。变得更大。变得更大。变得更大。 译码时按照与编码时采用的相同规则进行，还原后得译码时按照与编码时采用的相同规则进行，还原后得译码时按照与编码时采用的相同规则进行，还原后得译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。因此，到的数据与压缩前的数据完全相同。因此，到的数据与压缩前的数据完全相同。因此，到的数据与压缩前的
36、数据完全相同。因此，RLERLE属于属于属于属于无损压缩技术。无损压缩技术。无损压缩技术。无损压缩技术。行程编码的应用行程编码的应用行程编码的应用行程编码的应用2.2.3 2.2.3 算术编码（算术编码（算术编码（算术编码（arithmetic coding ACarithmetic coding AC）l20世纪世纪60年代初，年代初，Elias提出了算术编码概提出了算术编码概念；念；1976年，年， Rissanen和和Pasco首次介绍首次介绍了它的实用技术。了它的实用技术。l基本原理：基本原理：将编码的信息序列表示成实数将编码的信息序列表示成实数0和和1之间的一个间隔之间的一个间隔(I
37、nterval)，信息序列，信息序列越长，编码表示它的间隔就越小，表示这越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。一间隔所需的二进制位就越多。假设某个字符的出现概率为假设某个字符的出现概率为 80%，该字符事实上只需要，该字符事实上只需要 -log2(0.8) = 0.322 个二进制位进行编码。个二进制位进行编码。难道真的能只输出难道真的能只输出 0.322 个个 0 或或 0.322 个个 1 吗？吗？算术编码的输出是：一个小数算术编码的输出是：一个小数算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而算术编码对整条信息（无论信息有多么长），其输出仅仅是一
38、个数，而且是一个介于且是一个介于0和和1之间的二进制小数。之间的二进制小数。例如算术编码对某条信息的输出为例如算术编码对某条信息的输出为1010001111，那么它表示小数，那么它表示小数0.1010001111，也即十进制数，也即十进制数0.64算术编码算术编码算术编码算术编码例：例：假设信源符号为假设信源符号为A, B, C, D，这些符号的概率分别为，这些符号的概率分别为 0.1, 0.4, 0.2, 0.3 ，根据这些概率可把间隔，根据这些概率可把间隔0, 1分成分成4个子间隔：个子间隔：0, 0.1）, 0.1, 0.5）, 0.5, 0.7）, 0.7, 1），其中），其中x,y）
39、表示半开放间隔，即包含表示半开放间隔，即包含x不包含不包含y，如表，如表2-1所示。所示。符号符号A AB BC CD D概率概率0.10.10.40.40.20.20.30.3初始编码间隔初始编码间隔0,0.10,0.1）0.1,0.50.1,0.5）0.5,0.70.5,0.7） 0.7,10.7,1）表表2-1 信源符号、概率和初始编码间隔信源符号、概率和初始编码间隔如果消息序列的输入为：如果消息序列的输入为：CADACDB，其编码过程如下：，其编码过程如下：首先输入的符号是首先输入的符号是C，找到它的编码范围是，找到它的编码范围是0.5, 0.7）；）；由于消息中第由于消息中第2个符号
40、个符号A的编码范围是的编码范围是0, 0.1），因此它的间隔就取），因此它的间隔就取0.5, 0.7）的第一个）的第一个1/10作为新间隔作为新间隔0.5, 0.52）；）；编码第编码第3个符号个符号D时取新间隔为时取新间隔为0.514, 0.52）；）；编码第编码第4个符号个符号A时，取新间隔为时，取新间隔为0.514, 0.5146），），。算术编码过程算术编码过程算术编码过程算术编码过程消息的编码输出可以是最后一个间隔中的任意数，整个编码过程如图消息的编码输出可以是最后一个间隔中的任意数，整个编码过程如图4-3所所示。最后在示。最后在0.5143876,0.514402）中选择一个数作为
41、编码输出值：中选择一个数作为编码输出值：0.5143876。解码时，解码器由编码输出值：解码时，解码器由编码输出值：0.5143876，可马上解得一个字符，可马上解得一个字符为为C，然后依次得到唯一解，然后依次得到唯一解A,D,A,C,D,B。Character probability Range (space) 1/10 A 1/10 B 1/10 E 1/10 G 1/10 I 1/10 L 2/10 S 1/10 T 1/10算术编码示例算术编码示例算术编码示例算术编码示例0.01.00.20.2560.2580.250.10.50.60.80.90.20.30.4TGILSABE0.3
42、0.260.250.26ILL0.2560.2580.25720.25760.25720.25760.25724算术编码示例算术编码示例算术编码示例算术编码示例( (续续续续) )编码输入符号序列编码输入符号序列编码输入符号序列编码输入符号序列: BILL: BILL GATES GATESNew character Low value High valueB 0.2 0.3I 0.25 0.26L 0.256 0.258L 0.2572 0.2576(space) 0.25720 0.25724G 0.257216 0.257220A 0.2572164 0.2572168T 0.25721
43、676 0.2572168E 0.257216772 0.257216776S 0.2572167752 0.2572167756算术编码示例算术编码示例算术编码示例算术编码示例( (续续续续) )最终编码（标签）是最终编码（标签）是0.2572167752-0.25721677560.2572167752-0.2572167756之间的任意数值，之间的任意数值，它可以通过解码还原初始序列它可以通过解码还原初始序列 解码是编码的逆过程解码是编码的逆过程解码是编码的逆过程解码是编码的逆过程 因为因为因为因为 0.2572167752 0.2572167752 位于位于位于位于 0.2 0.2 至
44、至至至 0.30.3之间之间之间之间, , 所以解码的第所以解码的第所以解码的第所以解码的第一个字符是一个字符是一个字符是一个字符是 B. B. 通过减去通过减去通过减去通过减去 BB的最低值，去除的最低值，去除的最低值，去除的最低值，去除 BB的影响。码值变的影响。码值变的影响。码值变的影响。码值变为：为：为：为：0.0572167752.0.0572167752. 码值除以码值除以码值除以码值除以 BB的范围的范围的范围的范围0.10.1，码值变为：，码值变为：，码值变为：，码值变为： 0.572167752. 0.572167752. 码值落入码值落入码值落入码值落入 I I的范围的范围
45、的范围的范围 重复上述过程，直到重复上述过程，直到重复上述过程，直到重复上述过程，直到0 0值或字符序列长度为止值或字符序列长度为止值或字符序列长度为止值或字符序列长度为止解码过程解码过程解码过程解码过程解码结果解码结果解码结果解码结果rcLowHighrange 0.2572167752 B0.20.30.10.572167752I0.50.60.10.72167752L0.60.80.2 0.6083876L0.60.80.20.041938(space)0.00.10.10.41938G0.40.50.10.1938A0.20.30.10.938T0.91.00.10.38E0.30.4
46、0.10.8S0.80.90.12.3 2.3 词典编码词典编码词典编码词典编码l通用编码技术：通用编码技术：有许多场合，开始时有许多场合，开始时不知道要编码数据的统计特性，也不不知道要编码数据的统计特性，也不一定允许你事先知道它们的统计特性。一定允许你事先知道它们的统计特性。l词典编码：词典编码：主要利用数据本身包含有主要利用数据本身包含有重复代码这个特性。例如文本文件和重复代码这个特性。例如文本文件和光栅图像就具有这种特性。光栅图像就具有这种特性。l词典编码法分类：词典编码法分类：l指针法指针法l索引法索引法2.3 2.3 词典编码词典编码词典编码词典编码l通用编码技术：通用编码技术：有许
47、多场合，开始时有许多场合，开始时不知道要编码数据的统计特性，也不不知道要编码数据的统计特性，也不一定允许你事先知道它们的统计特性。一定允许你事先知道它们的统计特性。l词典编码：词典编码：主要利用数据本身包含有主要利用数据本身包含有重复代码这个特性。例如文本文件和重复代码这个特性。例如文本文件和光栅图像就具有这种特性。光栅图像就具有这种特性。l词典编码法分类：词典编码法分类：l指针法指针法l索引法索引法指针法指针法查找正在压缩的字符序列是否在以前输入的数据中查找正在压缩的字符序列是否在以前输入的数据中查找正在压缩的字符序列是否在以前输入的数据中查找正在压缩的字符序列是否在以前输入的数据中出现过，
48、然后用已经出现过的字符串替代重复的出现过，然后用已经出现过的字符串替代重复的出现过，然后用已经出现过的字符串替代重复的出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串部分，它的输出仅仅是指向早期出现过的字符串部分，它的输出仅仅是指向早期出现过的字符串部分，它的输出仅仅是指向早期出现过的字符串的的的的“ “指针指针指针指针” ”。典型算法为。典型算法为。典型算法为。典型算法为LZ77LZ77算法及算法及算法及算法及LZSSLZSS算法。算法。算法。算法。索引法索引法从输入的数据中创建一个从输入的数据中创建一个从输入的数据中创建一个从输入的数据中创建一个“ “短
49、语词典短语词典短语词典短语词典(dictionary of the (dictionary of the phrases)”phrases)”，这种短语不一定是像，这种短语不一定是像，这种短语不一定是像，这种短语不一定是像“ “严谨勤奋求实创新严谨勤奋求实创新严谨勤奋求实创新严谨勤奋求实创新” ”和和和和“ “国泰民安是坐稳总统宝座的根本国泰民安是坐稳总统宝座的根本国泰民安是坐稳总统宝座的根本国泰民安是坐稳总统宝座的根本” ”这类具有具这类具有具这类具有具这类具有具体含义的短语，它可以是任意字符的组合。编码数据体含义的短语，它可以是任意字符的组合。编码数据体含义的短语，它可以是任意字符的组合。
50、编码数据体含义的短语，它可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的过程中当遇到已经在词典中出现的过程中当遇到已经在词典中出现的过程中当遇到已经在词典中出现的“ “短语短语短语短语” ”时，编码时，编码时，编码时，编码器就输出这个词典中的短语的器就输出这个词典中的短语的器就输出这个词典中的短语的器就输出这个词典中的短语的“ “索引号索引号索引号索引号” ”，而不是短，而不是短，而不是短，而不是短语本身。语本身。语本身。语本身。LZ77算法算法(指针法指针法)字典模型：现代汉语词典以及下面的例子字典模型：现代汉语词典以及下面的例子L77算法算法主要术语：主要术语：输入数据流输入数
51、据流输入数据流输入数据流(input stream)(input stream)：要被压缩的字符序：要被压缩的字符序：要被压缩的字符序：要被压缩的字符序列。列。列。列。 字符字符字符字符(character)(character)：输入数据流中的基本单元。：输入数据流中的基本单元。：输入数据流中的基本单元。：输入数据流中的基本单元。 编码位置编码位置编码位置编码位置(coding position)(coding position)：输入数据流中当前：输入数据流中当前：输入数据流中当前：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开要编码的字符位置，指前向缓冲存储器中的开要编码的字符
52、位置，指前向缓冲存储器中的开要编码的字符位置，指前向缓冲存储器中的开始字符。始字符。始字符。始字符。 前向缓冲存储器前向缓冲存储器前向缓冲存储器前向缓冲存储器(Lookahead buffer)(Lookahead buffer)：存放从编：存放从编：存放从编：存放从编码位置到输入数据流结束的字符序列的存储器。码位置到输入数据流结束的字符序列的存储器。码位置到输入数据流结束的字符序列的存储器。码位置到输入数据流结束的字符序列的存储器。 窗口窗口窗口窗口(window)(window)：指包含已编码：指包含已编码：指包含已编码：指包含已编码WW个字符的窗口。个字符的窗口。个字符的窗口。个字符的窗
53、口。 指针指针指针指针(pointer)(pointer)：指向窗口中的匹配串且含长度：指向窗口中的匹配串且含长度：指向窗口中的匹配串且含长度：指向窗口中的匹配串且含长度的指针。的指针。的指针。的指针。LZ77编码算法编码算法编码算法的具体执行步骤如下：（）把编码位置设置到输入数据流的开始位置。 （）查找窗口中最长的匹配串。 （）以“(Pointer, Length) Characters”的格式输出，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。 （）如果前向缓冲存储器不是空的，则把编码位置和窗口向前移
54、(Length+1)个字符，然后返回到步骤2。LZ77编码示例说明编码示例说明 “ “步骤步骤步骤步骤” ”栏表示编码步骤。栏表示编码步骤。栏表示编码步骤。栏表示编码步骤。 “ “位置位置位置位置” ”栏表示编码位置，输入数据流中的第栏表示编码位置，输入数据流中的第栏表示编码位置，输入数据流中的第栏表示编码位置，输入数据流中的第1 1个字符为编码位置个字符为编码位置个字符为编码位置个字符为编码位置1 1。 “ “匹配串匹配串匹配串匹配串” ”栏表示窗口中找到的最长的匹配串。栏表示窗口中找到的最长的匹配串。栏表示窗口中找到的最长的匹配串。栏表示窗口中找到的最长的匹配串。 “ “字符字符字符字符”
55、 ”栏表示匹配之后在前向缓冲存储器中的第栏表示匹配之后在前向缓冲存储器中的第栏表示匹配之后在前向缓冲存储器中的第栏表示匹配之后在前向缓冲存储器中的第1 1个字符。个字符。个字符。个字符。 “ “输出输出输出输出” ”栏以栏以栏以栏以“ “(Back_chars, Chars_length) Explicit_character”(Back_chars, Chars_length) Explicit_character”格式输出。其中，格式输出。其中，格式输出。其中，格式输出。其中，(Back_chars, Chars_length)(Back_chars, Chars_length)是指向匹配
56、串的指是指向匹配串的指是指向匹配串的指是指向匹配串的指针，告诉译码器针，告诉译码器针，告诉译码器针，告诉译码器“ “在这个窗口中向后退在这个窗口中向后退在这个窗口中向后退在这个窗口中向后退Back_charsBack_chars个字符然后拷个字符然后拷个字符然后拷个字符然后拷贝贝贝贝Chars_lengthChars_length个字符到输出个字符到输出个字符到输出个字符到输出” ”，Explicit_characterExplicit_character是真实字符。是真实字符。是真实字符。是真实字符。步骤位置匹配串 字符 输出 11-A(0,0) A22-B(0,0) B33BC(1,1)
57、C45ABBB(4,3) B59C-(5,1)编码举例编码举例位置位置123456789字符ABBCABBBC步骤位置匹配串 字符 输出 11-A(0,0) A22-B(0,0) B33BC(1,1) C45ABBB(4,3) B59C-(5,1)译码演示译码演示位置位置123456789字符ABBCABBBC步骤位置编码流 输出 11(0,0) AA22(0,0) BB33(1,1) CBC45(4,3) BABBB59(5,1)CLZW算法算法( 索引法索引法)LZWLZWLZWLZW算法：算法：算法：算法：J.ZivJ.Ziv和和和和A.LempelA.Lempel在在在在1978197
58、8年首次年首次年首次年首次发表了介绍第二类词典编码算法的文章。发表了介绍第二类词典编码算法的文章。发表了介绍第二类词典编码算法的文章。发表了介绍第二类词典编码算法的文章。在他们的研究基础上，在他们的研究基础上，在他们的研究基础上，在他们的研究基础上，Terry A.WelchTerry A.Welch在在在在19841984年发表了改进这种编码算法的文章，年发表了改进这种编码算法的文章，年发表了改进这种编码算法的文章，年发表了改进这种编码算法的文章，因此把这种编码方法称为因此把这种编码方法称为因此把这种编码方法称为因此把这种编码方法称为LZW(Lempel-LZW(Lempel-Ziv Wal
59、ch)Ziv Walch)压缩编码。压缩编码。压缩编码。压缩编码。主要思想：主要思想：主要思想：主要思想： 通过管理这个词典完成输入通过管理这个词典完成输入通过管理这个词典完成输入通过管理这个词典完成输入与输出之间的转换。与输出之间的转换。与输出之间的转换。与输出之间的转换。LZWLZW编码器的输入编码器的输入编码器的输入编码器的输入是字符流是字符流是字符流是字符流(Char stream)(Char stream)，字符流可以是用，字符流可以是用，字符流可以是用，字符流可以是用8 8位位位位ASCIIASCII字符组成的字符串，而输出是字符组成的字符串，而输出是字符组成的字符串，而输出是字符
60、组成的字符串，而输出是用用用用n n位位位位( (例如例如例如例如1212位位位位) )表示的码字流表示的码字流表示的码字流表示的码字流 (Code (Code stream)stream)，码字代表单个字符或多个字符组，码字代表单个字符或多个字符组，码字代表单个字符或多个字符组，码字代表单个字符或多个字符组成的字符串成的字符串成的字符串成的字符串(String)(String)。LZW编码算法编码算法步骤步骤步骤步骤1 1：将词典初始化为包含所有可能的单字符，当前前：将词典初始化为包含所有可能的单字符，当前前：将词典初始化为包含所有可能的单字符，当前前：将词典初始化为包含所有可能的单字符，当
61、前前缀缀缀缀P P初始化为空。初始化为空。初始化为空。初始化为空。步骤步骤步骤步骤2 2：当前字符：当前字符：当前字符：当前字符C:=C:=字符流中的下一个字符。字符流中的下一个字符。字符流中的下一个字符。字符流中的下一个字符。步骤步骤步骤步骤3 3：判断：判断：判断：判断P PC C是否在词典中是否在词典中是否在词典中是否在词典中 （1 1）如果）如果）如果）如果“ “是是是是” ”，则用，则用，则用，则用C C扩展扩展扩展扩展P P，即让，即让，即让，即让P:=PP:=PC C，返回，返回，返回，返回到步骤到步骤到步骤到步骤2 2。 （2 2）如果）如果）如果）如果“ “否否否否” ”，则
62、，则，则，则 输出与当前前缀输出与当前前缀输出与当前前缀输出与当前前缀P P相对应的码字相对应的码字相对应的码字相对应的码字WW； 将将将将P PC C添加到词典中；添加到词典中；添加到词典中；添加到词典中； 令令令令P:=CP:=C，并返回到步骤，并返回到步骤，并返回到步骤，并返回到步骤2 2LZW编码举例编码举例位置位置位置位置1 12 23 34 45 56 67 78 89 9字符字符字符字符A AB BC CA AB BA AB BA AA A步骤步骤步骤步骤位置位置位置位置码字码字码字码字词典词典词典词典输出输出输出输出（1 1）A A（2 2）B B（3 3）C C1 11 1（
63、4 4）ABAB（1 1）2 22 2（5 5）BCBC（2 2）3 33 3（6 6）CACA（3 3）4 44 4（7 7）ABAABA（4 4）5 56 6（8 8）ABAAABAA（7 7）6 6（1 1）输入数据流：输入数据流：编码过程：编码过程：LZW译码算法译码算法两个术语：两个术语：两个术语：两个术语： 1. 1.当前码字：当前正在处理的码字，当前码字：当前正在处理的码字，当前码字：当前正在处理的码字，当前码字：当前正在处理的码字，cWcW表示当前码字，表示当前码字，表示当前码字，表示当前码字，string.cWstring.cW表示当前缀表示当前缀表示当前缀表示当前缀- -符
64、串（前缀符串（前缀符串（前缀符串（前缀+ +字符）字符）字符）字符） 2. 2.先前码字：先于当前码字的码字，用先前码字：先于当前码字的码字，用先前码字：先于当前码字的码字，用先前码字：先于当前码字的码字，用pWpW表示，表示，表示，表示，string.pWstring.pW表示先前缀表示先前缀表示先前缀表示先前缀- -符串符串符串符串LZWLZW译码算法：先记住先前码字译码算法：先记住先前码字译码算法：先记住先前码字译码算法：先记住先前码字(pW)(pW)，从码字流中读当，从码字流中读当，从码字流中读当，从码字流中读当前码字前码字前码字前码字(cW)(cW)之后，输出当前缀之后，输出当前缀之
65、后，输出当前缀之后，输出当前缀- -符串符串符串符串string.cWstring.cW，然后把，然后把，然后把，然后把用用用用string.cWstring.cW的第一个字符扩展的先前缀的第一个字符扩展的先前缀的第一个字符扩展的先前缀的第一个字符扩展的先前缀- -符串符串符串符串string.pWstring.pW添加到词典中。添加到词典中。添加到词典中。添加到词典中。LZW译码算法译码算法步骤步骤步骤步骤1 1：在开始译码时包含所有可能的前缀根。：在开始译码时包含所有可能的前缀根。：在开始译码时包含所有可能的前缀根。：在开始译码时包含所有可能的前缀根。步骤步骤步骤步骤2 2：cW:=cW:
66、=码字流中的第一个码字。码字流中的第一个码字。码字流中的第一个码字。码字流中的第一个码字。步骤步骤步骤步骤3 3：输出当前缀：输出当前缀：输出当前缀：输出当前缀- -符串符串符串符串string.cWstring.cW到字符流。到字符流。到字符流。到字符流。步骤步骤步骤步骤4 4：先前码字：先前码字：先前码字：先前码字pW:=pW:=当前码字当前码字当前码字当前码字cWcW步骤步骤步骤步骤5 5：当前码字：当前码字：当前码字：当前码字cW:=cW:=码字流中的下一个码字。码字流中的下一个码字。码字流中的下一个码字。码字流中的下一个码字。步骤步骤步骤步骤6 6：判断当前缀：判断当前缀：判断当前缀
67、：判断当前缀- -符串符串符串符串string.cWstring.cW是否在词典中。是否在词典中。是否在词典中。是否在词典中。 （1 1）如果）如果）如果）如果“ “是是是是” ”，则，则，则，则 a. a. 把当前字符串把当前字符串把当前字符串把当前字符串string.cWstring.cW输出到字符流输出到字符流输出到字符流输出到字符流 b. b. 当前前缀当前前缀当前前缀当前前缀P:=P:=先前缀先前缀先前缀先前缀- -符串符串符串符串string.pWstring.pW c. c. 当前字符当前字符当前字符当前字符C:=C:=当前缀当前缀当前缀当前缀- -符串符串符串符串string.
68、cWstring.cW的第一个字符的第一个字符的第一个字符的第一个字符 d. d. 把缀把缀把缀把缀- -符串符串符串符串P+CP+C添加到词典添加到词典添加到词典添加到词典 (2) (2) 如果如果如果如果“ “否否否否” ”，则，则，则，则 a. a. 当前前缀当前前缀当前前缀当前前缀P:=P:=先前缀先前缀先前缀先前缀- -符串符串符串符串string.pWstring.pW b. b. 当前字符当前字符当前字符当前字符C:=C:=先前缀先前缀先前缀先前缀- -符串符串符串符串string.pWstring.pW的第一个字符的第一个字符的第一个字符的第一个字符 c. c. 输出缀输出缀输
69、出缀输出缀- -符串符串符串符串P+CP+C到字符流，然后把它添加到词典中。到字符流，然后把它添加到词典中。到字符流，然后把它添加到词典中。到字符流，然后把它添加到词典中。步骤步骤步骤步骤7 7：判断码字流中是否还有码字要译：判断码字流中是否还有码字要译：判断码字流中是否还有码字要译：判断码字流中是否还有码字要译 (1) (1) 如果如果如果如果“ “是是是是” ”，返回到步骤，返回到步骤，返回到步骤，返回到步骤4 4 (2) (2) 如果如果如果如果“ “否否否否” ”，结束。，结束。，结束。，结束。LZW译码举例译码举例步骤步骤步骤步骤输入码字输入码字输入码字输入码字词典词典词典词典输出输
70、出输出输出码字码字码字码字字串字串字串字串（1 1）A A（2 2）B B（3 3）C C1 1（1 1）A A2 2（2 2）（4 4）ABABB B3 3（3 3）（5 5）BCBCC C4 4（4 4）（6 6）CACAABAB5 5（7 7）（7 7）ABAABAABAABA6 6（1 1）（8 8）ABAAABAAA A译码过程：译码过程：LZW算法优势算法优势lLZWLZW算法得到普遍采用，它的速度比使用算法得到普遍采用，它的速度比使用算法得到普遍采用，它的速度比使用算法得到普遍采用，它的速度比使用LZ77LZ77算算算算法的速度快，因为它不需要执行那么多的缀法的速度快，因为它不需
71、要执行那么多的缀法的速度快，因为它不需要执行那么多的缀法的速度快，因为它不需要执行那么多的缀- -符串比符串比符串比符串比较操作。对较操作。对较操作。对较操作。对LZWLZW算法进一步的改进是增加可变的码算法进一步的改进是增加可变的码算法进一步的改进是增加可变的码算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀字长度，以及在词典中删除老的缀字长度，以及在词典中删除老的缀字长度，以及在词典中删除老的缀- -符串。在符串。在符串。在符串。在GIFGIF图图图图像格式和像格式和像格式和像格式和UNIXUNIX的压缩程序中已经采用了这些改进措的压缩程序中已经采用了这些改进措的压缩程序中已经
72、采用了这些改进措的压缩程序中已经采用了这些改进措施之后的施之后的施之后的施之后的LZWLZW算法。算法。算法。算法。lLZWLZW算法取得了专利，专利权的所有者是美国的一算法取得了专利，专利权的所有者是美国的一算法取得了专利，专利权的所有者是美国的一算法取得了专利，专利权的所有者是美国的一个大型计算机公司个大型计算机公司个大型计算机公司个大型计算机公司Unisys(Unisys(优利系统公司优利系统公司优利系统公司优利系统公司) )，除了商，除了商，除了商，除了商业软件生产公司之外，可以免费使用业软件生产公司之外，可以免费使用业软件生产公司之外，可以免费使用业软件生产公司之外，可以免费使用LZ
73、WLZW算法算法算法算法。这是一种针对空间冗余和时间冗余的压缩方法。这是一种针对空间冗余和时间冗余的压缩方法。这是一种针对空间冗余和时间冗余的压缩方法。这是一种针对空间冗余和时间冗余的压缩方法。这种编码技这种编码技这种编码技这种编码技 术比较成熟、简便，目前大多数语音、术比较成熟、简便，目前大多数语音、术比较成熟、简便，目前大多数语音、术比较成熟、简便，目前大多数语音、图像编码中都采用这种编码技术。图像编码中都采用这种编码技术。图像编码中都采用这种编码技术。图像编码中都采用这种编码技术。主要思想：利用原始的离散信号之间存在着一定主要思想：利用原始的离散信号之间存在着一定主要思想：利用原始的离散
74、信号之间存在着一定主要思想：利用原始的离散信号之间存在着一定的相关性的特点，建立一个预测模型，然后根据的相关性的特点，建立一个预测模型，然后根据的相关性的特点，建立一个预测模型，然后根据的相关性的特点，建立一个预测模型，然后根据这个模型及以往的样本值，预测下一个信号的值，这个模型及以往的样本值，预测下一个信号的值，这个模型及以往的样本值，预测下一个信号的值，这个模型及以往的样本值，预测下一个信号的值，然后由实际值和预测值计算出预测误差，再对这然后由实际值和预测值计算出预测误差，再对这然后由实际值和预测值计算出预测误差，再对这然后由实际值和预测值计算出预测误差，再对这个误差进行编码后发送到接收端
75、，接收端通过预个误差进行编码后发送到接收端，接收端通过预个误差进行编码后发送到接收端，接收端通过预个误差进行编码后发送到接收端，接收端通过预测值加差值信号来重建原信号。测值加差值信号来重建原信号。测值加差值信号来重建原信号。测值加差值信号来重建原信号。如果预测比较准确，那么误差信号就会很小，就如果预测比较准确，那么误差信号就会很小，就如果预测比较准确，那么误差信号就会很小，就如果预测比较准确，那么误差信号就会很小，就可以用较少的码位进行编码，以达到数据压缩的可以用较少的码位进行编码，以达到数据压缩的可以用较少的码位进行编码，以达到数据压缩的可以用较少的码位进行编码，以达到数据压缩的目的。目的。
76、目的。目的。2.4 2.4 预测编码预测编码预测编码预测编码空间冗余 静态图像中存在的最主要的一种静态图像中存在的最主要的一种静态图像中存在的最主要的一种静态图像中存在的最主要的一种数据冗余数据冗余数据冗余数据冗余 在同一幅图像中，规则物体和规在同一幅图像中，规则物体和规在同一幅图像中，规则物体和规在同一幅图像中，规则物体和规则背景的表面物理特性具有相关则背景的表面物理特性具有相关则背景的表面物理特性具有相关则背景的表面物理特性具有相关性性性性 即对同一景物表面上采样点的颜即对同一景物表面上采样点的颜即对同一景物表面上采样点的颜即对同一景物表面上采样点的颜色之间存在着空间连贯性色之间存在着空间
77、连贯性色之间存在着空间连贯性色之间存在着空间连贯性 例如：图像中一片连续的区域，例如：图像中一片连续的区域，例如：图像中一片连续的区域，例如：图像中一片连续的区域，其像素为相同其像素为相同其像素为相同其像素为相同/ /相近的颜色相近的颜色相近的颜色相近的颜色空间空间空间空间冗余冗余冗余冗余时间冗余序列图像序列图像序列图像序列图像( (电视图像、动画电视图像、动画电视图像、动画电视图像、动画) )和语音数据中所和语音数据中所和语音数据中所和语音数据中所经常包含的冗余经常包含的冗余经常包含的冗余经常包含的冗余一组连续的画面之间往往存在着时间和空一组连续的画面之间往往存在着时间和空一组连续的画面之间
78、往往存在着时间和空一组连续的画面之间往往存在着时间和空间的相关性间的相关性间的相关性间的相关性例如：唱歌的歌手例如：唱歌的歌手例如：唱歌的歌手例如：唱歌的歌手lPCMPCM(Pulse Code Modulation)(Pulse Code Modulation)：原始的模拟信号经过时间采样，然后对每一样值原始的模拟信号经过时间采样，然后对每一样值原始的模拟信号经过时间采样，然后对每一样值原始的模拟信号经过时间采样，然后对每一样值进行量化，作为数字信号传输。进行量化，作为数字信号传输。进行量化，作为数字信号传输。进行量化，作为数字信号传输。lDPCMDPCM：l不对每一样值都进行量化，而是预测
79、下一样值，不对每一样值都进行量化，而是预测下一样值，不对每一样值都进行量化，而是预测下一样值，不对每一样值都进行量化，而是预测下一样值，并量化实际值和预测值之间的差。并量化实际值和预测值之间的差。并量化实际值和预测值之间的差。并量化实际值和预测值之间的差。lDPCMDPCM是基本的编码方法之一，在大量的压缩是基本的编码方法之一，在大量的压缩是基本的编码方法之一，在大量的压缩是基本的编码方法之一，在大量的压缩算法中被采用，比如算法中被采用，比如算法中被采用，比如算法中被采用，比如JPEGJPEG的的的的DCDC分量就是采用分量就是采用分量就是采用分量就是采用DPCMDPCM编码的。编码的。编码的
80、。编码的。预测编码差分脉码调制(DPCM)DPCM示例图像预测编码原理图像重构图像预测编码实例预测误差影像预测误差影像还原还原影像影像l主主主主要要要要思思思思想想想想：不不不不直直直直接接接接对对对对信信信信号号号号进进进进行行行行编编编编码码码码，而而而而是是是是在在在在数数数数据据据据压压压压缩缩缩缩前前前前先先先先对对对对原原原原始始始始输输输输入入入入数数数数据据据据作作作作某某某某种种种种正正正正交交交交变变变变换换换换，把把把把信信信信号号号号映映映映射射射射变变变变换换换换到到到到另另另另外外外外一一一一个个个个正正正正交交交交向向向向量量量量空空空空间间间间，产产产产生生生生
81、一一一一批批批批变换系数，然后再对这些变换系数进行量化压缩。变换系数，然后再对这些变换系数进行量化压缩。变换系数，然后再对这些变换系数进行量化压缩。变换系数，然后再对这些变换系数进行量化压缩。例如：例如：例如：例如：将时域信号变换到频域信号，因为声音、将时域信号变换到频域信号，因为声音、将时域信号变换到频域信号，因为声音、将时域信号变换到频域信号，因为声音、图像大部分信号都是低频信号，在频域中信号的图像大部分信号都是低频信号，在频域中信号的图像大部分信号都是低频信号，在频域中信号的图像大部分信号都是低频信号，在频域中信号的能量较集中，再进行采样、编码，来实现压缩数能量较集中，再进行采样、编码，
82、来实现压缩数能量较集中，再进行采样、编码，来实现压缩数能量较集中，再进行采样、编码，来实现压缩数据。据。据。据。2.5 2.5 变换编码变换编码变换编码变换编码一个输入序列经过转换矩阵，转换为另一个输出一个输入序列经过转换矩阵，转换为另一个输出一个输入序列经过转换矩阵，转换为另一个输出一个输入序列经过转换矩阵，转换为另一个输出序列。该序列包含的信息主要集中于个别元素序列。该序列包含的信息主要集中于个别元素序列。该序列包含的信息主要集中于个别元素序列。该序列包含的信息主要集中于个别元素 通过抛弃输出序列中包含信息少的元素，可以获通过抛弃输出序列中包含信息少的元素，可以获通过抛弃输出序列中包含信息
83、少的元素，可以获通过抛弃输出序列中包含信息少的元素，可以获得很高的数据压缩比得很高的数据压缩比得很高的数据压缩比得很高的数据压缩比. .XnYnTransformY=AX变换编码原理变换编码原理Discrete Fourier Transform (DFT)Transform Inverseand f(j.k) is the input sequence.图像压缩常用变换（一）图像压缩常用变换（一）离散傅立叶变换离散傅立叶变换Discrete Fourier Transform (DFT) Discrete Fourier Transform (DFT) 有快速算法有快速算法有快速算法有快速算
84、法 (FFT)(FFT) O(nlogn) O(nlogn)图像压缩不常用，原因是：图像压缩不常用，原因是：图像压缩不常用，原因是：图像压缩不常用，原因是： 性能不够好性能不够好性能不够好性能不够好 复数变换，计算负载大复数变换，计算负载大复数变换，计算负载大复数变换，计算负载大图像压缩常用变换（一）图像压缩常用变换（一）离散傅立叶变换离散傅立叶变换Discrete Cosine Transform (DCT)Discrete Cosine Transform (DCT)余弦函数作为基函数余弦函数作为基函数余弦函数作为基函数余弦函数作为基函数性能接近性能接近性能接近性能接近 KLTKLT存在快
85、速算法存在快速算法存在快速算法存在快速算法图像压缩中非常流行图像压缩中非常流行图像压缩中非常流行图像压缩中非常流行为为为为 JPEGJPEG采纳采纳采纳采纳图像压缩常用变换（二）图像压缩常用变换（二）离散余弦变换离散余弦变换对每个单独的彩色图像分量，把整个分量图像分对每个单独的彩色图像分量，把整个分量图像分对每个单独的彩色图像分量，把整个分量图像分对每个单独的彩色图像分量，把整个分量图像分成成成成8888的图像块，并作为两维离散余弦变换的图像块，并作为两维离散余弦变换的图像块，并作为两维离散余弦变换的图像块，并作为两维离散余弦变换DCTDCT的输入。通过的输入。通过的输入。通过的输入。通过DC
86、TDCT变换，把能量集中在少数几个变换，把能量集中在少数几个变换，把能量集中在少数几个变换，把能量集中在少数几个系数上。系数上。系数上。系数上。图像压缩常用变换（二）图像压缩常用变换（二）离散余弦变换离散余弦变换DCTDCT变换使用下式计算变换使用下式计算变换使用下式计算变换使用下式计算逆变换使用下式计算逆变换使用下式计算逆变换使用下式计算逆变换使用下式计算C(u), C(v) = 1/ , C(u), C(v) = 1/ , 当当当当u, v = 0u, v = 0；C(u), C(v) = 1, C(u), C(v) = 1, 其他。其他。其他。其他。 图像压缩常用变换（二）图像压缩常用变
87、换（二）离散余弦变换离散余弦变换离散余弦变换示例离散余弦变换示例（第14讲）考场作文开拓文路能力分解层次(网友来稿)江苏省镇江中学 陈乃香说明：本系列稿共24讲，20XX年1月6日开始在资源上连载【要义解说】文章主旨确立以后，就应该恰当地分解层次，使几个层次构成一个有机的整体，形成一篇完整的文章。如何分解层次主要取决于表现主旨的需要。【策略解读】一般说来，记人叙事的文章常按时间顺序分解层次，写景状物的文章常按时间顺序、空间顺序分解层次；说明文根据说明对象的特点，可按时间顺序、空间顺序或逻辑顺序分解层次；议论文主要根据“提出问题分析问题解决问题”顺序来分解层次。当然，分解层次不是一层不变的固定模
88、式，而应该富于变化。文章的层次，也常常有些外在的形式：1小标题式。即围绕话题把一篇文章划分为几个相对独立的部分，再给它们加上一个简洁、恰当的小标题。如世界改变了模样四个小标题：寿命变“长”了、世界变“小”了、劳动变“轻”了、文明变“绿”了。 2序号式。序号式作文与小标题作文有相同的特点。序号可以是“一、二、三”，可以是“A、B、C”，也可以是“甲、乙、丙”从全文看，序号式干净、明快；但从题目上看，却看不出文章内容，只是标明了层次与部分。有时序号式作文，也适用于叙述性文章，为故事情节的展开，提供了明晰的层次。 3总分式。如高考佳作人生也是一张答卷。开头：“人生就是一张答卷。它上面有选择题、填空题
89、、判断题和问答题，但它又不同于一般的答卷。一般的答卷用手来书写，人生的答卷却要用行动来书写。”主体部分每段首句分别为：选择题是对人生进行正确的取舍，填空题是充实自己的人生，判断题是表明自己的人生态度，问答题是考验自己解决问题的能力。这份“试卷”设计得合理而且实在，每个人的人生都是不同的，这就意味着这份人生试卷的“答案是丰富多彩的”。分解层次，应追求作文美学的三个价值取向：一要匀称美。什么材料在前，什么材料在后，要合理安排；什么材料详写，什么材料略写，要通盘考虑。自然段是构成文章的基本单位，恰当划分自然段，自然就成为分解层次的基本要求。该分段处就分段，不要老是开头、正文、结尾“三段式”，这种老套
90、的层次显得呆板。二要波澜美。文章内容应该有张有弛，有起有伏，如波如澜。只有这样才能使文章起伏错落，一波三折，吸引读者。三要圆合美。文章的开头与结尾要遥相照应，把开头描写的事物或提出的问题，在结尾处用各种方式加以深化或回答，给人首尾圆合的感觉。【例文解剖】 话题：忙忙，不亦乐乎 忙，是人生中一个个步骤，每个人所忙的事务不同，但是不能是碌碌无为地白忙，要忙就忙得精彩，忙得不亦乐乎。 忙是问号。忙看似简单，但其中却大有学问。忙是人生中不可缺少的一部分，但是怎么才能忙出精彩，忙得不亦乐乎，却并不简单。人生如同一张地图，我们一直在自己的地图上行走，时不时我们眼前就出现一个十字路口，我们该向哪儿，面对那纵
91、轴横轴相交的十字路口，我们该怎样选择?不急，静下心来分析一下，选择适合自己的坐标轴才是最重要的。忙就是如此，选择自己该忙的才能忙得有意义。忙是问号，这个问号一直提醒我们要忙得有意义，忙得不亦乐乎。 忙是省略号。四季在有规律地进行着冷暖交替，大自然就一直按照这样的规律不停地忙，人们亦如此。为自己找一个目标，为目标而不停地忙，让这种忙一直忙下去。当目标已达成，那么再找一个目标，继续这样忙，就像省略号一样，毫无休止地忙下去，翻开历史的长卷，我们看到牛顿在忙着他的实验；爱迪生在忙着思考；徐霞客在忙着记载游玩；李时珍在忙着编写本草纲目。再看那位以笔为刀枪的充满着朝气与力量的文学泰斗鲁迅，他正忙着用他独有
92、的刀和枪在不停地奋斗。忙是省略号，确定了一个目标那么就一直忙下去吧!这样的忙一定会忙出生命灵动的色彩。 忙是惊叹号。世界上的人都在忙着自己的事，大自然亦如此，小蜜蜂在忙，以蜂蜜为回报。那么人呢?居里夫人的忙，以放射性元素的发现而得到了圆满的休止符；爱因斯坦在忙，以相对论的问世而画上了惊叹号；李白的忙，以那豪放的诗歌而有了很大的成功；张衡的忙，因为那地动仪的问世而让世人仰慕。每个人都应该有效率的忙，而不是整天碌碌无为地白忙。人生是有限的、短暂的，因此，每个人都应该在有限的生命里忙出属于他的惊叹号；都应在有限的生命里忙出他的人生精彩篇章。 忙是万物、世界、人生中都不可缺少的一部分。作为这世上最高级
93、动物的我们，我们在忙什么呢?我们要忙得有意义，有价值，我们要忙出属于我们的精彩。我们的忙不能永远是问号，而应是省略号和感叹号。忙就要忙得精彩，忙得不亦乐乎。 解剖：本文将生活中的一句口头禅“忙得不亦乐乎”机智翻新，拟作标题，亮出一道美丽的风景。并据此展开述说，让人神清气爽。文章开篇扣题，亮出观点：忙，是人生中一个个步骤，不能碌碌无为地白忙，要忙就忙得精彩，忙得不亦乐乎。然后，作者分别用问号、省略号、惊叹号巧妙设喻，抓住这三种标点符号的特征，摆实事，讲道理，入情入理，入理入心。深刻地阐明人生忙，忙要像问号一样，经常问问自己，不能盲目，不能瞎忙，要忙得有意义；人生如四季一样是有规律的，要选准目标，
94、像省略号一样，毫无休止地忙下去，忙出生命灵动的色彩；而人生有限，每个人都应有限的生命里忙出属于他的惊叹号，忙出人生精彩的篇章。结尾，作者用一个段落总结全文，照应开头，照应题目，有力收束。【精题解析】阅读下面的材料，根据要求作文。在一处地势十分险恶的峡谷，谷底奔腾着咆哮的急流，峡谷间有一座索桥，几根光秃秃、晃悠悠的铁索横在峡谷间，它是通过这个地方的唯一路径，这里经常有人因为失足而跌入深谷。有一天，有三个人来到了这里。一个聋子，一个瞎子，还有一个健康的人。聋子看看这座桥，很害怕，但是他听不到急流的声音，他用眼睛看着脚下步伐，很顺利地过去了。瞎子不知峡谷的险恶，他心平气和，十分稳妥地通过了。第三个人是健康人，一直犹豫不敢走这索桥，可是又没有其他路可走。于是，他十分紧张地硬着头皮走上索桥，到了桥中央，他看到脚下万丈深渊，云雾升腾，听到谷底急流咆哮，早已两腿颤颤，面如土色，一不小心跌下桥去。请就“不要把困难看得太明白”为话题写一篇文章。注意所写内容必须在话题范围之内。试题引用的材料，考生在文章中可用也可不用。立意自定。文体自选。题目自拟。不少于800字。不得抄袭。解析：有时候，把困难看得太明白，分析得太透彻，反而会被困难吓倒以至于阻拦我们前进的脚步。倒是那些未把困难完全看清楚而勇往直前的人，更容易达到终点。 作者邮箱： 13952865227谢谢观赏谢谢观赏
