《印刷专业-平面设计课件优秀PPT.ppt》由会员分享，可在线阅读，更多相关《印刷专业-平面设计课件优秀PPT.ppt（105页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、7.17.1图像编码的必要性与可能性图像编码的必要性与可能性 7.27.2图像编码分类图像编码分类 7.37.3图像编码评价准则图像编码评价准则 7.47.4图像编码模型图像编码模型 7.57.5无损压缩无损压缩 7.67.6有损压缩有损压缩 7.7JPEG7.7JPEG图像编码压缩标准图像编码压缩标准 7.8MPEG7.8MPEG视频编码压缩标准视频编码压缩标准 7.97.9小结小结第第7章章 图像编码与压缩图像编码与压缩7.1 图像编码的必要性与可能性7.1.1图像编码的必要性数字图像的浩大数据对计算机的处理速度、存储容量都提出过高的要求。因此必需把数据量压缩。从传送图像的角度来看，则更要
2、求数据量压缩。在信道带宽、通信链路容量确定的前提下，接受编码压缩技术，削减传输数据量，是提高通信速度的重要手段。图像编码的可能性组组成成图图像像的的各各像像素素之之间间，无无论论是是在在图图像像的的行行方方向还是在列方向，都存在着确定的相关性。向还是在列方向，都存在着确定的相关性。常常见见的的静静态态图图像像数数据据冗冗余余包包括括：空空间间冗冗余余 ，结结构构冗冗余余，学学问问冗冗余余，视视觉觉冗冗余余，图图像像区区域域的的相同性冗余，纹理的统计冗余相同性冗余，纹理的统计冗余 。7.2图像编码分类依依据据解解压压重重建建后后的的图图像像和和原原始始图图像像之之间间是是否否具具有有误误差差，可
3、可以以将将图图像像编编码码与与压压缩缩方方法法分分为为无无误误差差(亦亦称称无无失失真真、无无损损、信信息息保保持持)编编码码和和有有误误差差(有有失失真真或或有损有损)编码两大类。编码两大类。依依据据编编码码作作用用域域划划分分，图图像像编编码码分分为为空空间间域域编编码码和和变换域编码两大类。变换域编码两大类。若若从从具具体体编编码码技技术术来来考考虑虑，又又可可分分为为预预料料编编码码、变变换编码、统计编码、轮廓编码、模型编码等。换编码、统计编码、轮廓编码、模型编码等。7.3 图像编码评价准则在在图图像像压压缩缩编编码码中中，解解码码图图像像与与原原始始图图像像可可能能会会有差异，因此，
4、须要评价压缩后图像的质量。有差异，因此，须要评价压缩后图像的质量。描描述述解解码码图图像像相相对对原原始始图图像像偏偏离离程程度度的的测测度度一一般般称为保真度称为保真度(逼真度逼真度)准则。准则。常常用用的的准准则则可可分分为为两两大大类类：客客观观保保真真度度准准则则和和主主观保真度准则。观保真度准则。7.3.1 客观保真度准则 最最常常用用的的客客观观保保真真度度准准则则是是原原图图像像和和解解码码图图像像之间的之间的均方根误差均方根误差和和均方根信噪比均方根信噪比两种。两种。均方根误差均方根误差 :均方信噪比均方信噪比:对上式求平方根，就得到均方根信噪比。对上式求平方根，就得到均方根信
5、噪比。（7-2）（7-3）主观保真度准则具具有有相相同同客客观观保保真真度度的的不不同同图图像像，人人的的视视觉觉可可能能产产生生不不同同的的视视觉觉效效果果。这这是是因因为为客客观观保保真真度度是是一一种种统统计计平平均均意意义义下下的的度度量量准准则则，对对于于图图像像中的细微环节无法反映出来。中的细微环节无法反映出来。一一种种常常用用的的方方法法是是对对一一组组(不不少少于于2020人人)视视察察者者显显示示图图像像，并并将将他他们们对对该该图图像像的的评评分分取取平平均均，用来评价一幅图像的主观质量。用来评价一幅图像的主观质量。例如可用-3，-2，-1，0，1，2，3来代表主观评价很差
6、，较差，稍差，相同，稍好，较好，很好。评分评价说明1优秀图像质量非常好，如同人能想象出的最好质量2良好图像质量高，观看舒服，有干扰但不影响观看3可用图像质量可以接受，有干扰但不太影响观看4刚可看图像质量差，干扰有些妨碍观看，观察者希望改进5差图像质量很差，几乎无法观看6不能用图像质量极差，不能使用表表7.1 7.1 电视图像质量评价尺度电视图像质量评价尺度7.4 图像编码模型一个图像压缩系统包括两个不同的结构块：一个图像压缩系统包括两个不同的结构块：编码器和解码器。编码器和解码器。图图像像f f（x x，y y）输输入入到到编编码码器器中中，编编码码器器可可以以依依据据输输入入数数据据生生成成
7、一一组组符符号号。在在通通过过信信道道进进行行传传输输之之后后，将将经经过过编编码码的的表表达达符符号号送送入入解解码码器器，经过重构后，生成输出图像。经过重构后，生成输出图像。f(x,y)信源编码信道编码信道信道解码信源解码f(x,y)一个常用于图像压缩系统模型一个常用于图像压缩系统模型7.4.1信源编码器和信源解码器信信源源编编码码器器的的任任务务是是削削减减或或消消退退输输入入图图像像中中的的编码冗余、像素间冗余或心理视觉冗余。编码冗余、像素间冗余或心理视觉冗余。从原理来看主要分为三个阶段从原理来看主要分为三个阶段:第第一一阶阶段段将将输输入入数数据据转转换换为为可可以以削削减减输输入入
8、图图像中像素间冗余的数据的集合。像中像素间冗余的数据的集合。其次阶段设法去除原图像信号的相关性其次阶段设法去除原图像信号的相关性 。第三阶段是找一种编码方式第三阶段是找一种编码方式 。信信源源解解码码器器包包含含两两部部分分：符符号号解解码码器器和和反反向向转转换器。换器。编码器模型编码器模型f(x,y)转换器量化器 符号编码器信道信道符 号 解 码器反向转换器f(x,y)（a）信源编码器）信源编码器（b）信源解码器）信源解码器信道编码器和解码器当当信信道道带带有有噪噪声声或或易易于于出出现现错错误误时时，信信道道编编码码器器和和解解码码器器就就在在整整个个译译码码解解码码处处理理中中扮扮演演
9、了了重重要要的的角角色色。信信道道编编码码器器和和解解码码器器通通过过向向信信源源编编码码数数据据中中插插入入预预制制的的冗冗余余数数据据来来削削减减信信道道噪噪声声的影响的影响 最最 有有 用用 的的 种种 信信 道道 编编 码码 技技 术术 是是 由由 R R w wHammingHamming提提出出的的。这这种种技技术术是是基基于于这这样样的的思思想想，即即向向被被编编码码数数据据中中加加入入足足够够的的位位数数以以确确保保可可用用的码字间变更的位数最小。的码字间变更的位数最小。7.5无损压缩 无无损损压压缩缩可可以以精精确确无无误误地地从从压压缩缩数数据据中中复复原出原始数据。原出原
10、始数据。常常见见的的无无损损压压缩缩技技术术包包括括：基基于于统统计计概概率率的方法和基于字典的技术。的方法和基于字典的技术。1.1.基基于于统统计计概概率率的的方方法法是是依依据据信信息息论论中中的的变变长长编编码码定定理理和和信信息息熵熵有有关关学学问问，用用较较短短代代码码代代表表出出现现概概率率大大的的符符号号，用用较较长长代代码码代代表表出出现现概率小的符号，从而实现数据压缩。概率小的符号，从而实现数据压缩。统统计计编编码码方方法法中中具具有有代代表表性性的的是是利利用用概概率率分分布布特特性性的的著著名名的的霍霍夫夫曼曼(Huffman)(Huffman)编编码码方方法法 ,另一种
11、是算术编码。另一种是算术编码。2.2.2.2.基于字典技术的数据压缩技术有两种：基于字典技术的数据压缩技术有两种：基于字典技术的数据压缩技术有两种：基于字典技术的数据压缩技术有两种：一一一一种种种种是是是是游游游游程程程程编编编编码码码码(Running(Running(Running(Running Length Length Length Length Coding)Coding)Coding)Coding)，简简简简称称称称为为为为RLC RLC RLC RLC，适适适适用用用用于于于于灰灰灰灰度度度度级级级级不不不不多多多多、数数数数据据据据相相相相关关关关性性性性很很很很强强强强的的
12、的的图图图图像像像像数数数数据据据据的的的的压压压压缩缩缩缩。但但但但最最最最不不不不适适适适用用用用于于于于每每每每个个个个像像像像素都与它四周的像素不同的状况。素都与它四周的像素不同的状况。素都与它四周的像素不同的状况。素都与它四周的像素不同的状况。另另另另一一一一种种种种称称称称之之之之为为为为LZWLZWLZWLZW编编编编码码码码 ，LZWLZWLZWLZW在在在在对对对对数数数数据据据据文文文文件件件件进进进进行行行行编编编编码码码码的的的的同同同同时时时时，生生生生成成成成了了了了特特特特定定定定字字字字符符符符序序序序列列列列的的的的表表表表以以以以及及及及它们对应的代码。它们
13、对应的代码。它们对应的代码。它们对应的代码。7.5.1霍夫曼编码一个事务集合x1,x2,xn,处于一个基本概率空间，其相应概率为p1,p2,pn，且p1+p2+pn=1。每一个信息的信息量为:如定义在概率空间中每事务的概率不相等时的平均不愿定程度或平均信息量叫作熵H，则：1.1.理论基础理论基础（7-9）（7-10）n n 熵是编码所需比特数的下限，即编码所须熵是编码所需比特数的下限，即编码所须要最少的比特。要最少的比特。n n例例:设设8 8个随机变量具有同等概率为个随机变量具有同等概率为1 18 8，计，计算信息熵算信息熵H H。n n解解:依据公式依据公式7-107-10可得：可得：n
14、nH=8*-1/8*(log2(1/8)=-8*-1/8*H=8*-1/8*(log2(1/8)=-8*-1/8*(-3)=3(-3)=3 Huffman编码是1952年由Huffman提出的一种编码方法。这种编码方法依据信源数据符号发生的概率进行编码。在信源数据中出现概率越大的符号，相应的码越短；出现概率越小的符号，其码长越长，从而达到用完可能少的码符号表示源数据。它在变长编码方法中是最佳的。2.Huffman2.Huffman编码编码 设信源设信源A A的信源空间为：的信源空间为：其中其中 ，现用，现用r r个码符号的码符号集个码符号的码符号集 对信源对信源A A中的每个符号（中的每个符号
15、（i i1 1，2 2，N)N)进行编码。进行编码。具体编码的方法是具体编码的方法是:(1)(1)把信源符号按其出现概率的大小依次排列起来；把信源符号按其出现概率的大小依次排列起来；(2)(2)把最末两个具有最小概率的元素之概率加起来；把最末两个具有最小概率的元素之概率加起来；(3)(3)把该概率之和同其余概率由大到小排队，然后再把把该概率之和同其余概率由大到小排队，然后再把 两个最小概率加起来，再重新排队；两个最小概率加起来，再重新排队；(4)(4)重复重复(2)(2)直到最终只剩下两个概率为止。直到最终只剩下两个概率为止。HuffmanHuffman编码具体方法：编码具体方法：n n例例
16、:设有编码输入设有编码输入n n其频率分布分别为其频率分布分别为n n现求其最佳霍夫曼编码。现求其最佳霍夫曼编码。n n解解 :Huffman:Huffman编码过程下图所示：编码过程下图所示：符号 概率 x1 0.7x2 0.3x3 0.1x7 0.1x5 0.06x6 0.041 0.70.30.10.10.120.70.30.20.130.70.30.370.60.7本例中对本例中对0.60.6赐予赐予0 0，对，对0.40.4赐予赐予1 1，0.40.4传递到传递到x1x1，所以，所以x1x1的编码便是的编码便是1 1。0.60.6传递到前一级是两个传递到前一级是两个0.30.3相加，
17、大值是单独一个元素相加，大值是单独一个元素x2x2的概率，小值是两个元的概率，小值是两个元素概率之和，每个概率都小于素概率之和，每个概率都小于0.30.3，所以，所以x2x2赐予赐予0 0，0.20.2和和0.10.1求和的求和的0.30.3赐予赐予1 1。所以。所以x2x2的编码是的编码是0000，而，而剩余元素编码的前两个码应为剩余元素编码的前两个码应为0101。0.10.1赐予赐予1 1，0.20.2赐赐予予0 0。以此类推，最终得到诸元素的编码如下：。以此类推，最终得到诸元素的编码如下：n n经霍夫曼编码后，平均码长为：经霍夫曼编码后，平均码长为：n nn n=n n=0.71+0.3
18、02+0.13+0.17+0.065+0.07=0.71+0.302+0.13+0.17+0.065+0.075 5n n=2.20(bit)=2.20(bit)n n该信源的熵为该信源的熵为H H2.17bit2.17bit，编码后计算的平，编码后计算的平均码长为均码长为2.2bit,2.2bit,特别接近于熵。可见特别接近于熵。可见HuffmanHuffman编码是编码是种较好的编码。种较好的编码。留意留意:短码不作长码的起始部分。短码不作长码的起始部分。HuffmanHuffman编编码码是是最最佳佳的的 ，其其平平均均码码长长相相同同 ，不不影影响响编编码效率和数据压缩性能。码效率和数
19、据压缩性能。由由于于HuffmanHuffman码码的的码码长长参参差差不不齐齐，因因此此，存存在在一一个个输输入入、输输出出速速率率匹匹配配问问题题。解解决决的的方方法法是是设设置置确确定定容容量量的的缓冲存储器缓冲存储器 HuffmanHuffman码码在在存存储储或或传传输输过过程程中中，假假如如出出现现误误码码，可可能能会引起误码的连续传播会引起误码的连续传播 HuffmanHuffman编码对不同信源其编码效率也不尽相同。编码对不同信源其编码效率也不尽相同。HuffmanHuffman编编码码应应用用时时，均均须须要要与与其其他他编编码码结结合合起起来来运运用用，才能进一步提高数据压
20、缩比。才能进一步提高数据压缩比。HuffmanHuffman编码编码实现7.5.2 香农费诺编码由于霍夫曼编码法须要多次排序，当很多时特别不由于霍夫曼编码法须要多次排序，当很多时特别不便，为此费诺便，为此费诺(Fano)(Fano)和香农和香农(Shannon)(Shannon)分别单独提出分别单独提出类似的方法，使编码更简洁。具体编码方法如下：类似的方法，使编码更简洁。具体编码方法如下：把把 按概率由大到小、从上到下排成按概率由大到小、从上到下排成一列，然后把一列，然后把 分成两组分成两组 ，并使得并使得 把两组分别按把两组分别按0 0，1 1赋值。赋值。然后分组、赋值，不断反复，直到每组只
21、有一种输然后分组、赋值，不断反复，直到每组只有一种输入为止。将每个所赋的值依次排列起来就是费诺入为止。将每个所赋的值依次排列起来就是费诺香农编码。香农编码。n n以前面哈夫曼编码的例子进行香农费诺编码以前面哈夫曼编码的例子进行香农费诺编码 ：7.5.3 算术编码理理论论上上，用用HuffmanHuffman方方法法对对源源数数据据流流进进行行编编码码可可达达到到最最佳佳编编码码效效果果。但但由由于于计计算算机机中中存存储储、处处理理的的最最小小单单位位是是“位位”，因因此此，在在一一些些状状况况下下，实实际际压压缩缩比与理论压缩比的极限相去甚远。比与理论压缩比的极限相去甚远。算算术术编编码码没
22、没有有延延用用数数据据编编码码技技术术中中用用一一个个特特定定的的代代码码代代替替一一个个输输入入符符号号的的一一般般做做法法，它它把把要要压压缩缩处处理理的的整整段段数数据据映映射射到到一一段段实实数数半半开开区区间间00，11内内的的某某一一区区段段，构构造造出出小小于于1 1且且大大于于或或等等于于0 0的的数数值值。这这个个数值是输人数据流的唯数值是输人数据流的唯可译代码。可译代码。对一个5符号信源Aa1,a2,a3,a2,a7，各字符出现的概率和设定的取值范围如下：字符 概率 范围a3 0.20.0，0.2）a1 0.20.2，0.4）a2 0.40.4，0.8)a7 0.20.8，
23、1.0)“范围”给出了字符的赋值区间。这个区间是依据字符发生的概率划分的。具体把a1、a2、a3、a7安排在哪个区间范围，对编码本身没有影响，只要保证编码器和解码器对字符的概率区间有相同的定义即可。为探讨便利起见，假定有 式中Ns为新于区间的起始位置；Fl为前于区间的起始位置，当前符号的区间左端；Ne为新于区间的结束位置；Fe为前子区间的结束位置；当前符号的区间右端；L为前子区间的长度。按上述区间的定义，若数据流的第一个字符为a1，由字符概率取值区间的定义可知，代码的实际取值范围在0.2，0.4之间，即输入数据流的第一个字符确定了代码最高有效位取值的范围。接着对源数据流中的后续字符进行编码。每
24、读入一个新的符号，输出数值范围就进一步缩小。读入其次个符号a2取值范围在区间的0.4，0.8内。由于第一个字符a1已将取值区间限制在0.2，0.4的范围中，因此a2的实际取值是在前符号范围0.2，0.4的0.4，0.8处，从而字符a2的编码取值范围在0.28，0.36，而不是在0，1整个概率分布区间上。每输入一个符号，都将按事先对概率范围的定义，在逐步缩小的当前取值区间上确定新的范围上、下限。接着读入第三个符号a3受到前面巳编码的两个字符的限制，它的编码取值应在0.28，0.36中的0.0，0.2内，即0.28，0.296。重复上述编码过程，直到输入数据流结束。最终结果如下：输入字符 区间长度
25、 范围a1 0.2 0.2，0.4）a2 0.080.28，0.36）a3 0.016 0.28，0.296)a2 0.0067 0.2867，0.2928)a1 0.00128 0.2915，0.2928 随着字符的输入，代码的取值范围越来越小。可以用一个浮点数表示一个字符串，达到削减所需存储空间的目的。游程编码游游程程编编码码(RLC)(RLC)是是一一种种利利用用空空间间冗冗余余度度压压缩缩图图像像的的方方法法 ，属于统计编码类，属于统计编码类 。设设图图像像中中的的某某一一行行或或某某一一块块像像素素经经采采样样或或经经某某种种变变换换后后的的系系数数为为 ：某某一一行行或或某某一一块
26、块内内像像素素值值可可分分为为k k段段，长长度度为为 的的连连续续串串，每每个个串串具具有有相相同同的的值值，那那么么，该该图图像像的的某某一一行行或或某某一一块块可可由由下下面面偶对偶对 来表示：来表示：其其中中 为为每每个个串串内内的的代代表表值值，为为串串的的长长度度。串串长长就就是是游游程程长长度度(Runlength)(Runlength)，简简写写为为RLRL，即即由由灰灰度度值值构构成成的的数数据据流流中中各各灰灰度度值值重重复复出出现现而而形形成成的的长长度度。假假如如给给出出了了灰灰度度值值、对对应应长长度度及及位位置置，就就能能很很简洁地复原出原来的数据流。简洁地复原出原
27、来的数据流。RLRL的基本结构的基本结构 游程编码分为定长游程编码和变长游程编码两类。游程编码分为定长游程编码和变长游程编码两类。定定长长游游程程编编码码是是指指编编码码的的游游程程所所运运用用位位数数是是固固定定的的，即即RLRL位位数数是是固固定定的的。假假如如灰灰度度连连续续相相同同的的个个数数超超过过了了固固定定位位数数所所能能表表示示的的最最大大值值，则则进进入入下下一一轮轮游游程程编码。编码。变变长长游游程程编编码码是是指指对对不不同同范范围围的的游游程程运运用用不不同同位位数的编码，即表示数的编码，即表示RLRL位数是不固定的。位数是不固定的。X SC RL串字符串位置串长 游游
28、程程编编码码一一般般不不干干脆脆应应用用于于多多灰灰度度图图像像，但但比比较适合于二值图像的编码。较适合于二值图像的编码。为为了了达达到到较较好好的的压压缩缩效效果果，有有时时游游程程编编码码和和其其他他一一些些编编码码方方法法混混合合运运用用。RLCRLC比比较较适适合合二二值值图图像像数数据据序序列列，其其缘缘由由是是在在二二值值序序列列中中，只只有有“0”“0”和和“1”“1”两两种种符符号号；这这些些符符号号的的连连续续出出现现，就就形形成成了了“0”“0”游程：游程：L(0)L(0)，“1”“1”游程：游程：L(1)L(1)。定定义义了了游游程程和和游游程程长长度度之之后后，就就可可
29、以以把把任任何何二二元元序序列列变变换换成成游游程程长长度度的的序序列列，简简称称游游程程序序列列。这这一变换是可逆的，一一对应的。一变换是可逆的，一一对应的。7.5.5无损预料编码一一幅幅二二维维静静止止图图像像，设设空空间间坐坐标标(i(i，j)j)像像素素点点的的实实际际灰灰度度为为f(i,j)f(i,j)，是是依依据据以以前前已已出出现现的的像像素素点点的的灰灰度度对对该该点点的的预预料料灰灰度度，也也称称预预料料值值或或估估计计值值，计计算算预预料料值值的的像像素素，可可以以是是同同一一扫扫描描行行的的前前几几个个像像素素，或或者者是是前前几几行行上上的的像像素素，甚甚至至是是前前几
30、几帧帧的的邻邻近近像素。实际值和预料值之间的差值，以下式表示：像素。实际值和预料值之间的差值，以下式表示：（7-13）由图像的统计特性可知，相邻像素之间有着较强的相关性。因此，其像素的值可依据以前已知的几个像素来估计，即预料。预料编码是依据某一模型，利用以往的样本值对于新样本值进行预料，然后将样本的实际值与其预料值相减得到一个误差值，对于这一误差值进行编码。假如模型足够好且样本序列在时间上相关性较强，那么误差信号的幅度将远远小于原始信号。对差值信号不进行量化而干脆编码就称之为无损预料编码。无损预料编码器的工作原理图 如下：预测器源图像熵编码器编码表压缩源图像由从前三点预料可以定义为：其中a1，
31、a2,a3称预料系数，都是待定参数。假如预料器中预料系数是固定不变的常数，称之为线性预料。预料误差：（7-14）（7-15）设设a=f(i,j-1)a=f(i,j-1)，b=f(i-1,j),c=f(i-1,j-1)b=f(i-1,j),c=f(i-1,j-1)，的预料方法如右图所示，可有的预料方法如右图所示，可有8 8种选择方法：种选择方法：(a+b)/2例例：设设有有一一幅幅图图像像，f(i-1,j-1),f(i-1,j),f(i-1,j-1),f(i-1,j),f(i,j-1),f(i,j-1),f(i,j)f(i,j)的的灰灰度度值值分分别别为为253,252,253,255253,2
32、52,253,255，用用图图7-87-8第第四四种选择方法预料种选择方法预料f(i,j)f(i,j)的灰度值，并计算预料误差。的灰度值，并计算预料误差。解解：=a+b-c=a+b-c=f(i,j-1)+f(i,j-1)+f(i-1,j)-f(i-1,j)-f(i-1,j-f(i-1,j-1)=252+253-253=252 1)=252+253-253=252 预料误差预料误差 =255-252=3 =255-252=3明明显显，预预料料误误差差e(i,j)=2e(i,j)=2比比像像素素的的实实际际值值f(i,j)=255f(i,j)=255小小的的多多，对对2 2进进行行编编码码比比对对
33、255255干干脆脆编编码码将将占占用用更更少少的的比比特特位。位。7.5.6字典压缩算法n n字典编码方法是以类似查字典的方式进行编字典编码方法是以类似查字典的方式进行编码。它的基本原理是以较长的字符串或常常出现码。它的基本原理是以较长的字符串或常常出现的字母组合构成字典中的各个词条，并用相对较的字母组合构成字典中的各个词条，并用相对较短的数字或符号来表示的方法。短的数字或符号来表示的方法。n nn n字典编码按其构成的方式可分为静态字典方字典编码按其构成的方式可分为静态字典方法和动态字典方法。法和动态字典方法。n n1.LZ77 1.LZ77 1.LZ77 1.LZ77 算法算法算法算法n
34、 n LZ77 LZ77 LZ77 LZ77 是是是是Jacob Ziv Jacob Ziv Jacob Ziv Jacob Ziv 和和和和Abraham Lempel Abraham Lempel Abraham Lempel Abraham Lempel 在在在在1977 1977 1977 1977 年发表的一篇论文中提出的。利用该算法进行数年发表的一篇论文中提出的。利用该算法进行数年发表的一篇论文中提出的。利用该算法进行数年发表的一篇论文中提出的。利用该算法进行数据压缩、解压缩的过程，就像一个窗口在原始数据压缩、解压缩的过程，就像一个窗口在原始数据压缩、解压缩的过程，就像一个窗口在原
35、始数据压缩、解压缩的过程，就像一个窗口在原始数据中滑动过程，故也常称为基于滑动窗口的自适据中滑动过程，故也常称为基于滑动窗口的自适据中滑动过程，故也常称为基于滑动窗口的自适据中滑动过程，故也常称为基于滑动窗口的自适应的字典压缩方法。应的字典压缩方法。应的字典压缩方法。应的字典压缩方法。n n2 LZ78 2 LZ78 2 LZ78 2 LZ78 算法算法算法算法n n LZ78 LZ78 LZ78 LZ78 是是是是Jacob Ziv Jacob Ziv Jacob Ziv Jacob Ziv 和和和和Abraham Lempel Abraham Lempel Abraham Lempel A
36、braham Lempel 在在在在1978 1978 1978 1978 年发表的另一篇论文中提出的。年发表的另一篇论文中提出的。年发表的另一篇论文中提出的。年发表的另一篇论文中提出的。LZ78 LZ78 LZ78 LZ78 算法不同于算法不同于算法不同于算法不同于LZ77 LZ77 LZ77 LZ77 算法，它放弃了窗口概念，接受树形结构构算法，它放弃了窗口概念，接受树形结构构算法，它放弃了窗口概念，接受树形结构构算法，它放弃了窗口概念，接受树形结构构造字典和保存短语，从而确保文件中的内容均能造字典和保存短语，从而确保文件中的内容均能造字典和保存短语，从而确保文件中的内容均能造字典和保存短
37、语，从而确保文件中的内容均能反映到字典中。反映到字典中。反映到字典中。反映到字典中。n n3 LZW 3 LZW 3 LZW 3 LZW 算法算法算法算法n n 1987 1987 1987 1987 年，年，年，年，Terry A.Welch Terry A.Welch Terry A.Welch Terry A.Welch 在在在在LZ78 LZ78 LZ78 LZ78 的基础上进的基础上进的基础上进的基础上进行了改进，这就是著名的行了改进，这就是著名的行了改进，这就是著名的行了改进，这就是著名的LZW LZW LZW LZW 压缩算法。压缩算法。压缩算法。压缩算法。n n LZW LZW
38、 LZW LZW压缩算法是一种基于字典算法的编码方法压缩算法是一种基于字典算法的编码方法压缩算法是一种基于字典算法的编码方法压缩算法是一种基于字典算法的编码方法.他的基本思想是建立一个编码表他的基本思想是建立一个编码表他的基本思想是建立一个编码表他的基本思想是建立一个编码表(转换表转换表转换表转换表)也称串也称串也称串也称串表表表表,将输入字符串映射成定长的码子输出将输入字符串映射成定长的码子输出将输入字符串映射成定长的码子输出将输入字符串映射成定长的码子输出,通常码长通常码长通常码长通常码长设为设为设为设为12bit.12bit.12bit.12bit.n n 12 12 12 12 位可以
39、有位可以有位可以有位可以有7 0967 0967 0967 096个不同的个不同的个不同的个不同的12 12 12 12 位代码位代码位代码位代码,这就是说这就是说这就是说这就是说,转换表有转换表有转换表有转换表有7 0967 0967 0967 096个表项个表项个表项个表项,其中其中其中其中256 256 256 256 个表项用来存放个表项用来存放个表项用来存放个表项用来存放已定义的字符已定义的字符已定义的字符已定义的字符,剩下剩下剩下剩下3 8703 8703 8703 870个表项用来存放前缀个表项用来存放前缀个表项用来存放前缀个表项用来存放前缀n nLZWLZWLZWLZW编码算法
40、的具体执行步骤如下编码算法的具体执行步骤如下编码算法的具体执行步骤如下编码算法的具体执行步骤如下:n n步骤步骤步骤步骤1:1:1:1:起先时的词典包含全部可能的根起先时的词典包含全部可能的根起先时的词典包含全部可能的根起先时的词典包含全部可能的根(Root),(Root),(Root),(Root),而当前而当前而当前而当前前缀前缀前缀前缀P P P P 是空的是空的是空的是空的;n n步骤步骤步骤步骤2:2:2:2:当前字符当前字符当前字符当前字符(C):=(C):=(C):=(C):=字符流中的下一个字符字符流中的下一个字符字符流中的下一个字符字符流中的下一个字符;n n步骤步骤步骤步骤
41、3:3:3:3:推断缀推断缀推断缀推断缀2 2 2 2符串符串符串符串P+C P+C P+C P+C 是否在词典中是否在词典中是否在词典中是否在词典中n n (1)(1)(1)(1)假如假如假如假如“是是是是”:P:=P+CPP(”:P:=P+CPP(”:P:=P+CPP(”:P:=P+CPP(用用用用C C C C 扩展扩展扩展扩展P);P);P);P);n n (2)(2)(2)(2)假如假如假如假如“否否否否”n n把代表当前前缀把代表当前前缀把代表当前前缀把代表当前前缀P P P P 的码字输出到码字流的码字输出到码字流的码字输出到码字流的码字输出到码字流;n n把缀把缀把缀把缀2 2
42、 2 2符串符串符串符串P+C P+C P+C P+C 添加到词典添加到词典添加到词典添加到词典;n n令令令令P:=CPP(P:=CPP(P:=CPP(P:=CPP(现在的现在的现在的现在的P P P P 仅包含一个字符仅包含一个字符仅包含一个字符仅包含一个字符C);C);C);C);n n步骤步骤步骤步骤7:7:7:7:推断码字流中是否还有码字要译推断码字流中是否还有码字要译推断码字流中是否还有码字要译推断码字流中是否还有码字要译n n (1)(1)(1)(1)假如假如假如假如“是是是是”,”,”,”,就返回到步骤就返回到步骤就返回到步骤就返回到步骤2;2;2;2;n n (2)(2)(2
43、)(2)假如假如假如假如“否否否否”n n把代表当前前缀把代表当前前缀把代表当前前缀把代表当前前缀P P P P 的码字输出到码字流的码字输出到码字流的码字输出到码字流的码字输出到码字流;n n结束结束结束结束.压缩算法流程图n n举例：n n原始码流357667357678903335767837n n原理n n(1).准备一个数据字典(可以看做一个数组).数组的前256项初始化为0,1,2,.,255,后面的项为空白.为便利起见,我们管字典中的每一项叫模式.(2)起先对图像文件编码,图像文件从左向右扫描,把扫描得到的数据与字典中的模式进行比较.假如相同,就把这个模index(在数组中的位置
44、)作为码字输出.假如在字典中找不到与之匹配的模式,则在字典中创建一个新的模式(从第256项起先).原始码流357667357678903335767837n n起先编码起先编码:aa因为第一个数字是因为第一个数字是35,35,我们必定可以从字典中找到与之匹我们必定可以从字典中找到与之匹配的模式配的模式(也就是第也就是第3535个个),),但我们不急着用第但我们不急着用第3535个模式与之匹配个模式与之匹配,先看看其次个数字是先看看其次个数字是76,76,希望在字典中能找到一个更长的模式希望在字典中能找到一个更长的模式35763576这样的模式这样的模式,与之匹配与之匹配,但不幸的是我们没有找到
45、但不幸的是我们没有找到,所以所以只对第一个数字只对第一个数字3535编码编码,结果输出结果输出35;35;同时把同时把35763576加入字典加入字典的第的第256256项项,希望以后能遇到它希望以后能遇到它.bb同理同理,对对7676编码编码,输出输出76,76,同时把同时把76677667加入字典的第加入字典的第257257项项.cc同理同理,对对6767编码编码,输出输出67,67,同时把同时把67356735加入字典的第加入字典的第258258项项.dd这时留意了这时留意了:对对3535编码编码,是不是现在还输出是不是现在还输出3535呢呢?当然不当然不是是,我们发觉我们发觉3535后
46、面跟着后面跟着76,76,扫描字典扫描字典,可以发觉第可以发觉第256256个模式与个模式与之匹配之匹配,输出输出256.256.同时同时,将模式将模式357678357678加入到字典的第加入到字典的第259259项项.ee同理同理,接下来输出接下来输出78,90,33,259,37.78,90,33,259,37.n n所以输出的码流为所以输出的码流为35766725678903325937.35766725678903325937.参考文献n n11杨国梁杨国梁,张光年张光年.无损无损LZWLZW压缩算法及实现压缩算法及实现.首都师范首都师范高校学报高校学报(自然科学版自然科学版).20
47、07.12.25).2007.12.25卷，卷，11-1311-13n n22董雪丰董雪丰,严闪严闪.LZW.LZW压缩算法压缩算法.福建电脑福建电脑.2007.1,26-.2007.1,26-2727n n33林小竹，籍俊伟林小竹，籍俊伟.一种改进的一种改进的LZWLZW压缩算法压缩算法.计算机计算机工程工程.2005.7,.2005.7,第第3131卷，卷，199-201199-2017.6有损压缩有有损损编编码码是是以以丢丢失失部部分分信信息息为为代代价价来来换换取取高高压压缩比。缩比。有有损损压压缩缩方方法法主主要要有有有有损损预预料料编编码码方方法法、变变换换编码方法等。编码方法等。
48、7.6.1有损预料编码在在预预料料编编码码中中，对对差差值值信信号号进进行行量量化化后后再再进进行行编码就称之为有损预料编码。编码就称之为有损预料编码。有有损损预预料料方方法法有有多多种种，其其中中差差分分脉脉冲冲编编码码调调制制(Differential(Differential Pulse Pulse Code Code ModulationModulation，简简称称DPCM)DPCM)，是一种具有代表性的编码方法。，是一种具有代表性的编码方法。DPCM系统由编码器和解码器组成，它们各有一个相同的预料器。DPCM系统的工作原理如下图所示:量化器编码器预测器信道传输解码器输入输出预测器系
49、系统统包包括括发发送送、接接收收和和信信道道传传输输三三个个部部分分。发发送送端端由由编编码码器器、量量化化器器、预预料料器器和和加加减减法法器器组组成成；接接收收端端包包括括解解码码器器和和预预料料器器等等；信信道道传传送送以以虚虚线线表表示示。图图中中输输入入信信号号f(i,j)f(i,j)是是坐坐标标(i,j)(i,j)处处的的像像素素的的实实际际灰灰度度值值，是是由由已已出出现现从从前前相相邻邻像像素素点点的的灰灰度度值对该像素的预料灰度值。值对该像素的预料灰度值。e(i,j)e(i,j)是预料误差。是预料误差。DPCMDPCM包包含含量量化化器器，这这时时编编码码器器对对编编码码，量
50、量化化器器导导致致了了不不行行逆逆的的信信息息损损失失，这这时时接接收收端端经经解解码码复复原原出出的的灰灰度度信信号号不不是是真真正正的的f(i,j)f(i,j)，而而是是重重建建信信号号。可可见见引引入入量量化化器器会会引引起起确确定定程程度度的的信信息息损损失失，使使图图像像质质量量受受损损。但但是是可可以以利利用用人人眼眼的的视视觉觉特特性性，丢丢失失不不易易觉察的图像信息，不会引起明显失真觉察的图像信息，不会引起明显失真 。7.6.2变换编码 变变换换编编码码不不是是干干脆脆对对空空域域图图像像信信号号编编码码，而而是是首首先先将将图图像像数数据据经经过过某某种种正正交交变变换换（如