第六章多媒体数据压缩

2023/2/61多媒体技术22023/2/6第6章多媒体数据压缩常用的无损数据压缩方法6.3常用的有损数据压缩方法6.4多媒体数据压缩概述6.1数据压缩的技术基础6.232023/2/66.1多媒体数据压缩概述6.1.1多媒体数据压缩的必要性⑴原始采样的媒体数据量巨大⑵有效利用存储器存储容量⑶提高通信线路的传输效率⑷消除计算机系统处理视频I/O瓶颈42023/2/66.1多媒体数据压缩概述6.1.2多媒体数据压缩的可能性常见的图像数据冗余种类：⑴空间冗余⑵时间冗余⑶结构冗余⑷知识冗余⑸视觉冗余52023/2/6空间冗余

在任何一幅图像中，均有由许多灰度或颜色都相同的邻近像素组成的区域，它们形成了一个性质相同的集合块，即它们相互之间具有空间上的强相关性，在图像中就表现为空间冗余。例如，一块表面颜色均匀的区域中所有点的光强和色彩以及饱和度都是相同的，这就是空间冗余。62023/2/6时间冗余这是序列图像（电视图像、运动图像）表示中经常包含的冗余。图像序列中两幅相邻的图像有较大的相关，这反映为时间冗余。运动图像的相邻帧往往包含相同的背景和移动物体，只不过物体所在的位置略有不同，由于相邻帧记录了相邻时刻的同一场景，所以称为时间冗余。72023/2/6结构冗余在有些图像的纹理区，图像的像素值存在着明显的分布模式。例如，方格状的板图案等，我们称此为结构冗余。已知分布模式，可以通过某一过程生成图像。82023/2/6知识冗余有些图像的理解与某些知识有相当大的相关性。例如：狗的图像有固定的结构，狗有四条腿，头部有眼、鼻、耳朵，有尾巴等。这类规律性的结构可由先验知识和背景知识得到，我们称此类冗余为知识冗余。92023/2/6视觉冗余人类的视觉系统对图像场的敏感度是非均匀的。但是，在记录原始的图像数据时，通常假定视觉系统近似线性的和均匀的，对视觉敏感和不敏感的部分同等对待，从而产生比理想编码（即把视觉敏感和不敏感的部分区分开来的编码）更多的数据，这就是视觉冗余。人类视觉系统的一般分辨能力估计为26灰度等级，而一般图像的量化采用的是28的灰度等级。这也被称之为视觉冗余。102023/2/66.1多媒体数据压缩概述6.1.3多媒体数据压缩的原理1.图像数据压缩的主要依据有两个一是图像数据中有许多重复的数据，使用数学方法来表示这些重复数据就可以减少数据量；另一个依据是人眼睛对图像细节和颜色的辨认有一个极限，把超过极限的部分去掉，这也就达到了数据压缩的目的。基于数据冗余的压缩技术是无损压缩技术基于人眼视觉特性的压缩技术是有损压缩技术112023/2/66.1.3多媒体数据压缩的原理2.图像压缩说明视频压缩与语音相比，语音的数据量较小，且基本压缩方法已经成熟，目前的数据压缩研究主要集中于图像和视频信号的压缩方面。压缩处理过程有两个过程，编码过程是将原始数据经过编码进行压缩，以便存储与传输；解码过程是对编码数据进行解码，还原为可以使用的数据。122023/2/66.1.3多媒体数据压缩的原理3.与压缩相关的指标衡量一种数据压缩技术的好坏有四个重要的指标：⑴压缩比大：即压缩前后所需要的信息存储量之比要大。⑵算法简单：实现压缩的算法简单，压缩、解压速度快，尽可能地做到实时压缩解压。⑶恢复效果好：恢复效果好，要尽可能地恢复原始数据。⑷压缩能否用硬件实现。132023/2/66.1.3多媒体数据压缩的原理142023/2/66.1.3多媒体数据压缩的原理⑴冗余压缩法也称无损压缩法，是指使用压缩后的数据可以解压缩，且解压之后的数据与原来的数据完全相同。它利用数据的统计冗余进行压缩，可完全恢复原始数据而不引入任何失真，但压缩率受到数据统计冗余度的理论限制，一般为2:1到5:1。152023/2/66.1.3多媒体数据压缩的原理⑵熵压缩法也称有损压缩法，有失真压缩，是指使用压缩后的数据进行解压缩，解压之后的数据与原来的数据有所不同，但不会让人对原始资料表达的信息造成误解。162023/2/66.1.3多媒体数据压缩的原理⑶熵压缩法与冗余压缩法的比较在图像压缩系统组成中，变换和编码是无损耗的，而量化是有损耗的。无损压缩方法仅利用了统计冗余，而没有利用量化器。有损压缩方法既利用了统计冗余又采用了量化器，利用了心理视觉冗余。172023/2/66.1.4数据压缩方法的分类1.根据编、解码后数据是否一致来进行分类，数据压缩的方法一般被划分为两类：可逆编码（无损编码）。此种方法的解码图像与原始图像严格相同，压缩比大约在2:1~5:1之间。主要编码有Huffman编码、算术编码、行程长度编码等。不可逆编码（有损编码）。此种方法的解码图像与原始图像存在一定的误差，但视觉效果一般可以接受，压缩比可以从几倍到上百倍调节。常用的编码有变换编码和预测编码。182023/2/66.1.4数据压缩方法的分类2.根据压缩方法的原理，可将其具体划分为以下几种：⑴量化与向量量化编码⑵预测编码

⑶变换编码⑷信息熵编码⑸混合编码变换编码与预测编码相结合192023/2/6量化与向量量化编码对像元点进行量化时，除了每次仅量化一个点的方法外，也可以考虑一次量化多个点的做法，这种方法称为向量量化。即利用相邻数据间的相关性，将数据系列分组进行量化。202023/2/6预测编码预测编码预测编码是根据离散信号之间存在着一定关联性的特点，利用前面一个或多个信号预测下一个信号进行，然后对实际值和预测值的差（预测误差）进行编码。如果预测比较准确，误差就会很小。在同等精度要求的条件下，就可以用比较少的比特进行编码，达到压缩数据的目的。如：增量调制（DM）、差分脉冲编码调制（DPCM）、自适应增量调制（ADPCM）等。主要用于声音编码。212023/2/6变换编码变换编码将图像时域信号转换为频域信号进行处理。数据处理时可以将主要的注意力集中在相对较小的区域，从而实现数据压缩。一般采用正交变换，如：离散余弦变换（DCT）、离散傅立叶变换（DFT）222023/2/6信息熵编码信息熵原理让出现概率大的信号用较短的码字表示，反之用较长的码字表示。常见的编码方法Huffman编码Shannon编码算术编码232023/2/66.2数据压缩的技术基础6.2.1熵的概念表示一条信息中真正需要编码的信息量，即数据压缩的理论极限。对于任何一种无损数据压缩，最终的数据量一定大于信息熵，数据量越接近于熵值，说明其压缩效果越好。242023/2/66.2数据压缩的技术基础6.2.2信息熵的计算1.信息量信息量是指从N个等概率事件中选出一个事件所需要的信息含量。设从N个数中选定任一个数xj的概率为p(xj)，假定选定任意一个数的概率都相等，即p(xj)＝1/N，因此定义信息量如下：概率相等概率不等252023/2/66.2.2信息熵的计算2.信息熵:平均信息量信源X发出的xj（j=1,2,…,n）共n个随机事件，每个事件产生的平均信息量为：H(X)称为信源X的“熵”，即信源X发出任意一个随机变量的平均信息量。其中：等概率事件的熵最大，假设有N个事件，则此时熵为：最大熵概率×信息量262023/2/66.2.3信息熵的范围当P(x1)＝1时，P(x2)＝P(x3)＝…＝P(xj)＝0，则此时熵为：由上可得熵的范围为：最小熵272023/2/66.2.4平均码长在编码中用熵值来衡量是否为最佳编码。若以Lc表示编码器输出码字的平均码长，则当Lc≥H(X)有冗余，不是最佳。Lc＜H(X)不可能。Lc＝H(X)最佳编码（Lc稍大于H(X)）。熵值为平均码长Lc的下限。平均码长Lc的计算公式为：（j=1,2,…,n）其中：P(xj)是信源X发出xj的概率，L(xj)为xj的编码长。282023/2/66.2.5冗余度、编码效率与压缩比在数字图像通信系统中，冗余度、编码效率与压缩比是衡量信源特性以及编解码设备性能的重要指标。设原图像的平均码长为L，熵为H(X)，压缩后图像的平均码长为Lc，则编码效率为：冗余度为：1-压缩比为：Lc292023/2/66.3常用的无损数据压缩方法6.3.1Huffman编码6.3.2算术编码6.3.3行程RLE编码6.3.4词典编码302023/2/66.3.1Huffman编码基本原理依据信源字符出现的概率大小来构造代码，对出现概率较大的信源字符，给予较短码长，而对于出现概率较小的信源字符，给予较长的码长，最后使得编码的平均码字最短。312023/2/66.3.1Huffman编码具体的编码步骤将信源出现的概率由大到小排序。将两处最小概率组合相加，形成新概率。将新概率与未编码的字符一起重新排序。重复步骤2、3，直到出现的概率和为1。分配代码代码分配从最后一步开始反向进行，对最后两个概率一个赋予0代码，一个赋予1代码。记录下从树的根到每个信源符号终节点的0和1序列。至于哪个为“1”哪个为“0”则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。322023/2/66.3.1Huffman编码Huffman编码中求平均码长的方法：概率×码长332023/2/66.3.1Huffman编码Huffman编码练习一:设输入图像的灰度级{a1,a2,a3,a4,a5,a6}出现的概率分别是0.4、0.2、0.12、0.15、0.1、0.03。试进行哈夫曼编码，并计算平均码字长度。342023/2/66.3.1Huffman编码Huffman编码练习二:信源符号的概率如下，请按要求作答：画出其Huffman编码的编码树给出各信源符号的码字与码长计算该信源的平均码长。（说明：大概率符号赋予0，小概率符号赋予l，相同概率情况下上面的是0，下面的是1。）XX1X2X3X4X5X6P(X)0.350.250.200.10.050.05352023/2/6Huffman编码练习一答案最终编码结果为：a1=1,a2=011,a3=001,a4=010,

a5=0001,a6=00001010010362023/2/6Huffman编码练习一答案据公式图像信源熵为：H(X)=-(0.4×log20.4+0.2×log20.2+0.12×log20.12+0.15×log20.15+0.1×log20.1+0.03×log20.03)=2.25bit根据哈夫曼编码结果，平均码字长度：Lc=0.4×1+0.2×3+0.15×3+0.12×3+0.1×4+0.03×4=2.33编码效率、压缩比和冗余度分别为：96.6%、1.2、3.4%r=1-η=3.4%372023/2/6Huffman编码练习二答案382023/2/66.3.1Huffman编码Huffman编码注意事项哈夫曼编码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个的正确译出代码。但如果码串中有错误，哪怕仅是1位出现错误，不但这个码本身译错，后面的译码可能全错，这种现象称为错误传播（ErrorPropagation）。哈夫曼编码是可变长度码，很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。392023/2/66.3.2算术编码算术编码（arithmeticcodingAC）是利用0和1之间的间隔来表示信源编码的一种方法，其编码值是间隔的上、下限包含的相同二进制。编码过程中的间隔决定了符号压缩后的输出。算术编码用到两个基本的参数符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。402023/2/66.3.2算术编码编码过程:设信源符号为{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)表示半开放间隔，即包含x不包含y，如下表所示。符号ABCD概率0.10.40.20.3初始编码间隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1]412023/2/66.3.2算术编码如果消息序列的输入为：CADACDB，其编码过程如下：首先输入的符号是C，找到它的编码范围是[0.5,0.7)；由于消息中第2个符号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)

，…。422023/2/66.3.2算术编码符号ABCD概率0.10.40.20.3初始编码间隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1]432023/2/66.3.2算术编码消息的编码输出可以是最后一个间隔中的任意数，整个编码过程如下图所示。最后在[0.5143876,0.514402)中选择一个数作为编码输出值：0.51439。解码时，解码器由编码输出值：0.51439，可马上解得一个字符为C，然后依次得到唯一解A,D,A,C,D,B。442023/2/66.3.2算术编码步骤译码间隔译码10.51439在间隔[0.5,0.7)1020.51439在间隔[0.5,0.7)的第1个1/100030.51439在间隔[0.5,0.52)的第7个1/101140.51439在间隔[0.514,0.52)的第1个1/100050.51439在间隔[0.514,0.5146)的第5个1/101060.51439在间隔[0.5143,0.51442)的第7个1/101170.51439在间隔[0.51439,0.5143948)的第1个1/10018译码消息：10001100101101

译码过程如下：452023/2/66.3.2算术编码在算术编码中需要注意的几个问题：由于计算机精度不可能无限长，运算中容易出现溢出，但多数机器都有16位、32位或者64位的精度，因此可使用比例缩放方法解决。算术编码器对整个消息只产生一个码字，这个码字是在间隔[0,1)中的一个实数，因此译码器在接受到所有位之前不能进行译码。算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。462023/2/66.3.2算术编码算术编码练习一:假设有4个符号的信源，它门的概率如下表所示：输入序列为Xn:a2,a1,a3,…。试画出它的编码过程信源符号aia1a2a3a4概率PiP1＝0.5P2＝0.25P3＝0.125P4＝0.125初始编码间隔[0,0.5)[0.5,0.75)[0.75,0.875)[0.875,1)472023/2/66.3.2算术编码算术编码练习二：假设信源符号为{1,0}，如果消息序列的输入为1101。这些符号的概率分别为:画出其编码过程！！信源01概率1/43/4编码间隔[0,1/4)[1/4,1]482023/2/6算术编码练习一答案最后的编码结果是：[0.59375,0.609375]492023/2/6算术编码练习二答案最后的编码结果是：[121/256,37/64)502023/2/66.3.3行程长度编码RLE（Run-LengthEncoding）是一个针对包含有顺序排列的多次重复的数据的压缩方案。其原理就是把一系列的重复值用一个单独的值再加上一个计数值来取代，行程长度就是连续且重复的单元数目。如果想得到原始数据，只需展开这个编码就可以了。512023/2/66.3.3行程长度编码例如，计算机制作图像中，不需要存储每一个像素的颜色值，而仅存储一个像素的颜色值以及具有相同颜色的像素数目就可以，或者存储一个像素的颜色值，以及具有相同颜色值的行数，这种压缩编码称为行程编码。具有相同颜色的连续的像素数目称为行程长度。522023/2/66.3.3行程长度编码如图所示，假定一幅灰度图像，第n行的像素值为：用RLE编码方法得到的代码为：3150841160。代码红色斜体表示的数字是行程长度，后面的数字代表像素的颜色值。例如红色斜体字50代表有连续50个像素具有相同的颜色值，它的颜色值是8。532023/2/66.3.3行程长度编码对比RLE编码前后的代码数可以发现，在编码前要用73个代码表示这一行的数据，而编码后只要用10个代码表示代表原来的73个代码，压缩前后的数据量之比约为7:1，即压缩比为7:1。这说明RLE确实是一种压缩技术，而且编码技术实用。542023/2/66.3.3行程长度编码RLE的性能好坏主要取决于图像本身的特点。RLE压缩编码尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。然而，由于颜色丰富的自然图像在同一行上具有相同颜色的连续像素往往很少，而连续几行都具有相同颜色值的连续行数就更少，如果仍然使用RLE编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。552023/2/66.3.3行程长度编码译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。因此，RLE属于无损压缩技术。它被用于BMP、JPEG/MPEG、TIFF和PDF等编码之中，还被用于传真机。562023/2/66.3.4词典编码词典编码属于无损压缩技术，其根据是数据本身包含有重复代码序列这个特性。词典编码的种类较多，归纳起来有两类。第一类词典编码LZ77、LZSS第二类词典编码LZ78、LZW572023/2/6第一类词典编码第一类词典编码的基本思想是查找正在压缩的字符序列是否在前面输入的数据中出现过，如果是，则用指向早期出现过的字符串的“指针”替代重复的字符串。582023/2/6第一类词典编码这里所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。这类编码中的所有算法都是以AbrahamLempel和JakobZiv在1977年开发和发表的称为LZ77算法为基础的。LZSS算法——LZ77的改进方法

592023/2/6LZ77算法输入数据流(inputstream):待压缩的字符序列字符(character):输入数据流中的基本单元。编码位置(codingposition):输入数据流中当前要编码的字符位置，前向缓冲器的开始字符。前向缓冲器(lookaheadbuffer):存放从编码位置到输入数据流结束的字符序列的存储器。窗口(Window):包含W个字符的窗口，字符从编码位置开始向后数。指针(Pointer):指向窗口中的匹配串且含长度。602023/2/6LZ77算法LZ77编码算法的核心是查找从前向缓冲器开始的最长的匹配串。具体执行步骤如下：把编码位置设置到输入数据流的开始。查找窗口中最长的匹配串。输出(Pointer，Length)Characters，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲器中第1个不匹配的字符。如果前向缓冲器不是空的，则把编码位置和窗口向前移Length+1个字符，然后返回到步骤2。612023/2/6LZ77算法待编码的数据流

位置12345678910字符A

A

B

C

BBABCC编码过程

步骤位置匹配串字符输出11--A

(0，0)A

22A

B

(1，1)B

34--C

(0，0)C

45B

B

(2，1)B

57ABC

C

(5，3)C

告诉译码器回退5个字符,然后拷贝3个字符“ABC”622023/2/6LZ77算法“步骤”栏表示编码步骤。“位置”栏表示编码位置。“匹配”栏表示窗口中找到的最长的匹配串。“字符”栏表示匹配之后在前向缓冲器中的第1个字符“输出”栏以(Back_chars，Chars_length)Explicit_character格式输出。其中(Back_chars，Chars_length)是指指向匹配串的指针，告诉译码器“在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出”，Explicit_character是真实字符。例如，输出“(5，2)C”告诉译码器回退5个字符，然后拷贝2个字符“AB”632023/2/6LZ77算法解压算法——解码当碰到编码字符串时，解压算法使用<指针>，和<长度>，字段将编码替换成实际的正文字符串。642023/2/6LZ77算法练习给定一个报文:abcdbbccaaabaeaaabaee，请用LZ77算法对该报文序列进行编码！Output:(0,0,a)(0,0,b)(0,0,c)(0,0,d)(3,1,b)(4,1,c)(8,1,a)(10,2,a)(0,0,e)(6,6,e)abcdbbccaaabaeaaabaee652023/2/6LZSS算法LZ77冗余信息空指针和编码器可能输出额外的字符，这种字符可能包含在下一个匹配串中。LZSS算法以比较有效的方法解决这个问题，它的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。指针长度为2662023/2/6LZSS算法把编码位置置于输入数据流的开始位置。在前向缓冲存储器中查找与窗口中最长的匹配串

Pointer：=匹配串指针。Length：=匹配串长度。判断匹配串长度是否大于等于最小匹配串长度如果“是”：输出指针，然后把编码位置向前移动Length个字符。如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。如前向缓冲存储器不是空的，就返回到步骤2。

672023/2/6LZSS算法举例待编码的数据流

位置1234567891011字符A

A

B

B

CBBAABC编码过程

步骤位置匹配串输出11--A22A

A33--B

44B

B55--C66BB(3,2)78AAB(7,3)811CC682023/2/6LZSS解码与LZ77一样完全可逆692023/2/6LZSS算法在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip,ARJ,LHArc和ZOO等等。LZSS同样可以和熵编码联合使用例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用。702023/2/6第二类词典编码第二类算法的思想是从输入的数据中创建一个“短语词典”（dictionaryofthephrases）（可能是任意字符的组合）。编码数据过程中，遇到已经在词典中出现的“短语”时，编码器就输出这个词典中该短语的“索引号”，而不是短语本身，如图。712023/2/6第二类词典编码722023/2/6第二类词典编码——LZW与LZ78LZ78是首个第二类词典编码，1984年提出的LZW压缩编码也属于这类编码LZW是对LZ78进行了实用性修正后提出的一种逻辑简单、速度快、硬件实现廉价的压缩算法，被GIF和PNG格式的图像压缩所采用，并被广泛应用于文件的压缩打包（如ZIP和RAR）和磁盘压缩。732023/2/6LZ78算法LZ78算法的有关术语和符号字符流(Charstream)：要被编码的数据序列。前缀(Prefix)：在一个字符之前的字符序列。缀-符串(String)：前缀＋字符。码字(Codeword)：码字流中的基本数据单元，代表词典中的一串字符。码字流(Codestream)：码字和字符组成的序列，是编码器的输出。词典(Dictionary)：缀-符串表。按照词典中的索引号对每条缀-符串(String)指定一个码字(Codeword)。742023/2/6LZ78编码算法在开始时，词典和当前前缀P都是空的。当前字符C:=字符流中的下一个字符。判断P+C是否在词典中：如果“是”：用C扩展P，让P:=P+C；如果“否”：输出与当前前缀P相对应的码字和当前字符C；把字符串P+C添加到词典中。令P:=空值。判断字符流中是否还有字符需要编码如果“是”：返回到步骤2。如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，然后结束编码。752023/2/6LZ78编码举例位置123456789字符ABBCBCABA步骤位置词典输出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)编码字符串：

编码过程：与LZ77相比，LZ78的最大优点是在每个编码步骤中减少了缀-符串(String)比较的数目，而压缩率与LZ77类似。

762023/2/6LZ78解码词典序列即输入的字符序列772023/2/6LZW算法在LZW算法中使用的术语与LZ78使用的相同，仅增加了一个术语—前缀根(Root)，它是由单个字符串组成的缀-符串(String)。在编码原理上，LZW与LZ78有如下差别：LZW在开始时词典必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)。由于所有可能出现的单个字符都事先包含在词典中，因此在词典中搜索的第1个缀-符串有两个字符。

782023/2/6LZW编码算法的具体执行步骤步骤1：开始的词典包含所有可能根，而前缀P为空；步骤2：当前字符(C)=字符流中的下一个字符；步骤3：判断缀字符串P+C是否在词典中

(1)如果“是”：P=P+C，即用C扩展P；

(2)如果“否”

①把代表当前前缀P的码字输出到码字流;

②把缀字符串P+C添加到词典;

③令P=C，即现在的P仅包含一个字符C;步骤4：判断码字流中是否还有码字要译

(1)如果“是”，就返回到步骤2；

(2)如果“否”

①把代表当前前缀P的码字输出到码字流;

②结束。792023/2/6LZW算法举例被编码的字符串LZW的编码过程

步骤位置词典输出(1)A

(2)B

(3)C

11(4)AB

(1)22(5)BB

(2)

33(6)BA

(2)44(7)ABA

(4)

56(8)ABAC

(7)

69----(3)

位置字符1A2B3B4A5B6A7B8A9C802023/2/6LZW算法举例被编码的字符串LZW的译码过程

步骤代码词典输出(1)A

(2)B

(3)C

1(1)

(4)AB

A2(2)(5)BB

B3(2)(6)BA

B4(4)(7)ABA

AB5(7)(8)ABAC

ABA6(3)----C位置字符1A2B3B4A5B6A7B8A9C812023/2/6LZW算法练习编码字符：位置12345678910111213141516字符ababcbababaaaaaa编码过程：步骤位置词典输出(1)A

(2)B

(3)C

1(4)2(5)…………822023/2/66.4常用的有损数据压缩方法6.4.1预测编码预测编码是根据离散信号之间存在着一定关联性的特点，利用前面一个或多个信号对下一个信号进行预测，然后对实际值和预测值的差（预测误差）进行编码。832023/2/66.4.1预测编码1.脉冲编码调制PCM842023/2/6脉冲编码调制PCM输入的模拟信号输入信号在时间轴上的数字化均匀量化或非均匀量化量化的信号电平转换成二进制码组离散的二进制输出序列采样时钟信号相乘852023/2/6脉冲编码调制PCM均匀量化：采用相同的“等分尺”来度量采样得到的幅度，也称为线性量化，如图所示。量化后的样本值Y和原始值X的差E=Y-X称为量化误差或量化噪声。862023/2/6均匀量化为了适应幅度大的输入信号，同时又要满足精度要求，就需要增加样本的位数。但是，对话音信号来说，大信号出现的机会并不多，增加的样本位数就没有充分利用。为了克服这个不足，就出现了非均匀量化的方法，这种方法也叫做非线性量化。872023/2/6非均匀量化对输入信号进行量化时，大的输入信号采用大的量化间隔，小的输入信号采用小的量化间隔，如下图所示。882023/2/66.4.1预测编码2.增量调制DM增量调制也称△调制(deltamodulation，DM)，是一种预测编码技术，是PCM编码的一种变形。PCM是对每个采样信号的整个幅度进行量化编码，它具有对任意波形进行编码的能力；DM是对实际的采样信号与预测的采样信号之差的极性进行编码，将极性变成“0”和“1”这两种可能的取值之一。如果实际的采样信号与预测的采样信号之差的极性为“正”，则用“1”表示；相反则用“0”表示，或者相反。由于DM编码只须用1位进行编码，所以它是二进制一位编码，每个码组不是表示信号的幅度，而是表示幅度的增量。892023/2/6DM波形编码示意图X[i]表示在i点的编码输出i表示采样点的位置输入信号的实际值输入信号的预测值902023/2/6“斜率过载”与“粒状噪声”斜率过载——与量化阶△相比，在开始阶段当实际波形幅度发生急剧变化时，DM不能充分跟踪这种快速变化而产生的失真。粒状噪声——在输入信号缓慢变化部分，即输入信号与预测信号的差值接近零的区域，DM出现随机交变的“0”和“