研究生多媒体03_多媒体数据压缩

1、1. 数据压缩的基本原理和方法数据压缩的基本原理和方法2. 音频的压缩音频的压缩3. 视觉类媒体压缩视觉类媒体压缩1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 1 数据压缩技术的性能指标数据压缩技术的性能指标评价数据压缩技术的评价数据压缩技术的3个关键指标：个关键指标：p压缩比：输入、输出数据量之比。压缩比：输入、输出数据量之比。p质量：无损和有损。无损没有信息的损失，所以质量不是衡量的标准。质量：无损和有损。无损没有信息的损失，所以质量不是衡量的标准。有损：通过损失一些细节的、对人的感观来说不重要的信息提高压缩比，有损：通过损失一些细节的、对人的感观来说不重要的信息提高压缩比，

2、分为主观评价和客观评价。客观评价：方差、新噪比等。分为主观评价和客观评价。客观评价：方差、新噪比等。p压缩和解压缩的速度：实时的采集系统中，压缩速度很重要。否则会丢压缩和解压缩的速度：实时的采集系统中，压缩速度很重要。否则会丢失信息。而存储回放中，结压缩的速度显得比压缩的速度重要，因为解压失信息。而存储回放中，结压缩的速度显得比压缩的速度重要，因为解压缩面对大多数用户的实时需求。缩面对大多数用户的实时需求。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 2 数据冗余的类型与压缩方法分类数据冗余的类型与压缩方法分类需要压缩的原因是因为信息数据存在着冗余。冗余，数据量和信息量不成正比。

3、需要压缩的原因是因为信息数据存在着冗余。冗余，数据量和信息量不成正比。空间冗余：例如，相邻象素空间冗余：例如，相邻象素(水平和垂直方向水平和垂直方向)有同样的值。有同样的值。时间冗余：时间相关媒体，帧与帧相同。时间冗余：时间相关媒体，帧与帧相同。编码冗余：同样长度的编码可以表示不同的信息。如黑白图像若每个象素点用编码冗余：同样长度的编码可以表示不同的信息。如黑白图像若每个象素点用8位位表示；表示；结构冗余：对称的结构如果都加以记录的话就出现结构冗余。结构冗余：对称的结构如果都加以记录的话就出现结构冗余。另外，很多成分相对于人的感觉来说重要性不一样。因此，压缩方法就是充分利用另外，很多成分相对于

4、人的感觉来说重要性不一样。因此，压缩方法就是充分利用这些冗余和特性。这些冗余和特性。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 2 数据冗余的类型与压缩方法分类数据冗余的类型与压缩方法分类数据压缩方法的分类数据压缩方法的分类根据解码后数据与原始数据是否完全一致进行分类，压缩方法根据解码后数据与原始数据是否完全一致进行分类，压缩方法可被分为两大类：可被分为两大类：p 有损压缩：减少信息量，损失的信息不能再恢复有损压缩：减少信息量，损失的信息不能再恢复p 无损压缩：可无损压缩：可100还原还原1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理

5、常用数据压缩方法的基本原理信源：信源：S S1,，Sn熵的概念：熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发熵的概念：熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，相应的，这个信息出现的概率小。生的可能性就越小，相应的，这个信息出现的概率小。某个事件的信息量，用某个事件的信息量，用Ii log 2 Pi表示。其中，表示。其中，Pi 表示第表示第i个事件的概率。个事件的概率。1. 3. 1 基本概念基本概念1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理信源信源S的熵定义为：的熵定义为

6、：i2n1ii1/PlogPH(S)1. 3. 1 基本概念基本概念1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理编码：一个信源符号集转换为另一个符号集编码：一个信源符号集转换为另一个符号集信源符号的集合：信源符号的集合：S S1,，Sn概率：概率： P1，,Pn码符号集合：码字中的元素，二进制编码则为码符号集合：码字中的元素，二进制编码则为 X，。，。码字的集合：码字的集合：W W1,，Wn编码长度：编码长度： L1, ，Ln，可分为变长码及定长码，可分为变长码及定长码1. 3. 1 基本概念基本概念1. 数据压缩的基本原

7、理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理唯一可译码：任意有限长，不需分隔符的码符号序列，能唯一译码唯一可译码：任意有限长，不需分隔符的码符号序列，能唯一译码非前缀码：非前缀码：W中任意码字中任意码字Wi都不是其余码字的前缀。非前缀码一定是唯一可译码都不是其余码字的前缀。非前缀码一定是唯一可译码例：例：编码方法编码方法A：具有唯一可译码性：具有唯一可译码性编码方法编码方法C：非前缀码：非前缀码编码方法编码方法D：具有可唯一译码性，但不符合非前缀码的条件。：具有可唯一译码性，但不符合非前缀码的条件。1. 3. 1 基本概念基本概念1. 数据压缩

8、的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理非前缀码一定是唯一可译码。反之则不然。非前缀码一定是唯一可译码。反之则不然。1. 3. 1 基本概念基本概念信源符号信源符号概率概率编码方法编码方法A编码编码B编码编码C编码编码DHuffman 1Huffman 2A10.400000010000A20.150011011011100100A30.1501000001010110110A40.100110110010111111010A50.10100101011000010101011A60.051011111010001101101110

9、A70.0411000011101001010111011110A80.0111100111111001110111111111平均编码长度 编码方法A：3； 编码方法B：1.5编码方法C : 2.9；编码方法D : 2.85 Huffman编码：2.561. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理给定信源符号集合给定信源符号集合S及码符号集及码符号集X，可以构造多个唯一可译码。，可以构造多个唯一可译码。多个编码的比较标准：多个编码的比较标准：平均编码长度平均编码长度低。如果我们用低。如果我们用 lj 表示信源符号表示信源

10、符号aj的二进制编的二进制编码长度，根据它的统计信息，平均编码长度：码长度，根据它的统计信息，平均编码长度：MjjjlPl11. 3. 1 基本概念基本概念结论：结论：对二进制编码方式（对二进制编码方式（ 即码符号的取值只有即码符号的取值只有0 ，1 两种情况）两种情况）平均编码长度满足平均编码长度满足码字的平均长度不能小于信源熵。码字的平均长度不能小于信源熵。若采用非等长编码：能找到一种编码，平均长度为信源熵若采用非等长编码：能找到一种编码，平均长度为信源熵 11. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理LSH)(1.

11、3. 1 基本概念基本概念1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理包括行程编码、包括行程编码、LZW编码、编码、huffman编码等。编码等。1. 3. 2 统计编码（熵编码）统计编码（熵编码）1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理行程编码：行程编码：检测重复的比特或者字符序列，并用（字符，重复次数）来检测重复的比特或者字符序列，并用（字符，重复次数）来表示。表示。考虑的问题：字符的值重复次数，二者之间是否使用分隔符，重复的次数考虑的问题：字

12、符的值重复次数，二者之间是否使用分隔符，重复的次数如何编码（使用变长码还是定长码）等如何编码（使用变长码还是定长码）等1. 3. 2 统计编码统计编码1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理Huffman编码：编码：于于1952年提出的对统计独立信源能达到最小平均码长的年提出的对统计独立信源能达到最小平均码长的编码方法。编码方法。Huffman编码的过程：构造一棵编码树。编码的过程：构造一棵编码树。 构造方法：构造方法：首先找出两个具有最小概率的节点，构造一个二叉树，以这两个节点为这棵树的叶首先找出两个具有最小概率的节

13、点，构造一个二叉树，以这两个节点为这棵树的叶子节点，根节点看作为新的节点，它的概率为两个叶子节点概率之和；此跟节点与子节点，根节点看作为新的节点，它的概率为两个叶子节点概率之和；此跟节点与未处理的节点形成新的节点集合，重复上面的过程，直到节点集合中只剩一个节点未处理的节点形成新的节点集合，重复上面的过程，直到节点集合中只剩一个节点为止。为止。1. 3. 2 统计编码统计编码1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理Huffman编码编码当信源符号概率是当信源符号概率是2的负幂次方时，编码效率达到的负幂次方时，编码效率达到

14、100%缺点：缺点：Huffman编码方法没有错误保护的功能，在译码时，如果码串中没有错误，那编码方法没有错误保护的功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。如果出现错误，哪怕仅仅是一位的错误，么就能一个接一个地正确译出代码。如果出现错误，哪怕仅仅是一位的错误，不但这个码本身会发生错误，并且会导致其他代码出错，这种现象称为错误传不但这个码本身会发生错误，并且会导致其他代码出错，这种现象称为错误传播（播（error propagation）。计算机也无法去发现错误纠正错误。）。计算机也无法去发现错误纠正错误。(2) Huffman码是变长度码，且没有额外同步码，因此很

15、难随意查找或调用压缩文码是变长度码，且没有额外同步码，因此很难随意查找或调用压缩文件中间的内容，然后再译码。件中间的内容，然后再译码。1. 3. 2 统计编码统计编码传真标准中的编码（传真标准中的编码（3类传真标准及类传真标准及4类传真标准类传真标准CCITT Group 3 1D/2D ）：）：扫描、尺寸和传输：扫描、尺寸和传输：扫描：每行扫描：每行1728个象素。标准扫描行宽个象素。标准扫描行宽215mm，垂直方向，垂直方向3.85行行/mm,或或7.7行行/mm.尺寸：尺寸：A4幅面幅面传输：用于传输每行扫描编码后形成的数据位、填充位、行结传输：用于传输每行扫描编码后形成的数据位、填充位

16、、行结束符号的时间总和，最大束符号的时间总和，最大20ms1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码传真标准中的编码（传真标准中的编码（3类传真标准类传真标准CCITT Group 3 1D及及4类传类传真标准）：真标准）：3类编码方法采用一维编码，扫描时统计游程，并将游程分为白游程及黑游类编码方法采用一维编码，扫描时统计游程，并将游程分为白游程及黑游程，白游程和黑游程再采用程，白游程和黑游程再采用Huffman编码。编码。假设每行的第一个行程是白色的（如果不是，则发出一个长度为假设每行的

17、第一个行程是白色的（如果不是，则发出一个长度为0的白色游的白色游程码），每行的结尾发出一个程码），每行的结尾发出一个EOL信号码。信号码。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码3类传真标准类传真标准CCITT Group 3 1D码表中的游程，码表中的游程，064，称为终止码。，称为终止码。终止码用于表示小于终止码用于表示小于64个像素的游程。个像素的游程。64，128，192，256，320，1728，64的倍数，称为编排码，编排码用于表示的倍数，称为编排码，编排码用于表示是是64个

18、像素倍数的游程。个像素倍数的游程。 1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码白色游程码字黑色游程码字00011010100000110111100011110102011121131000310630011010063EOL000000000001终止码终止码1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基

19、本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码白色游程码字黑色游程码字6411011641281001012819201011119225617280100110111728编排码编排码3类传真标准类传真标准CCITT Group 3 1D例如，例如，1347（1344+3）个白像素的游程编码用以下两种代码进行编码：）个白像素的游程编码用以下两种代码进行编码：1344（6421）个白像素的编排码）个白像素的编排码0110110103个白像素的终止码个白像素的终止码1000那么，那么，1347个白像素的压缩位流是个白像素的压缩位流是01101101010001. 数据压缩的基本

20、原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码4类传真标准类传真标准CCITT Group 3 2D将扫描线每将扫描线每K条放在一起进行处理。每组条放在一起进行处理。每组K条线中的第一条用条线中的第一条用CCITT Group 3 1D方方法编码，这条线就成为下一条线的参考线，然后使用二维方法和一法编码，这条线就成为下一条线的参考线，然后使用二维方法和一 维方法为这组维方法为这组K条线中的其余扫描线编码。条线中的其余扫描线编码。 原因：横跨相邻两条扫描线的图像数据可能是冗余的。如果在一指定线上出现了黑原因：横跨相

21、邻两条扫描线的图像数据可能是冗余的。如果在一指定线上出现了黑白过渡，那么有可能在下一扫描线上加或减三个像素之间的位置上也出现相同的过白过渡，那么有可能在下一扫描线上加或减三个像素之间的位置上也出现相同的过渡。渡。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码4类传真标准类传真标准CCITT Group 3 2D编码方法：每个编码方法：每个K组的第一条线采用组的第一条线采用Group3 1D方式编码，以作为这组方式编码，以作为这组K条线中其条线中其余线的扫描线。余线的扫描线。2D方法使用了一些附

22、加码的组合为这组方法使用了一些附加码的组合为这组K条线中的每一条编码。附加码有条线中的每一条编码。附加码有3种：垂种：垂直码，越过码，水平码。直码，越过码，水平码。 1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码4类传真标准类传真标准CCITT Group 3 2D越过码固定取值：越过码固定取值：0001水平码也固定取值：水平码也固定取值：001垂直码有垂直码有7类，它的值由参考线中变化像素的类，它的值由参考线中变化像素的位置与编码线重变化像素的位置之间的差距决位置与编码线重变化像素的位置之间

23、的差距决定。定。 1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码位置差异垂直码30000010200001010100110112000011300000114类传真标准类传真标准CCITT Group 3 2D二维编码：一种循环算法，依靠二维编码：一种循环算法，依靠a0, a1,a2,b1,b2 五个参数的更新来循环。如下例所五个参数的更新来循环。如下例所示。示。a0表示准备编码的行程起始位置的像素点，表示准备编码的行程起始位置的像素点，a1为当前行下一个行程起始位置的像素点，为当前行下一个

24、行程起始位置的像素点，a2表示再下一个行程起始位置的象素点。表示再下一个行程起始位置的象素点。b1为参考行上位于为参考行上位于a0位置右边行程起始位置的像素点，其颜色与位置右边行程起始位置的像素点，其颜色与a1一致，一致，b2为参考行为参考行a0之后下一个行程起始位置的象素点。之后下一个行程起始位置的象素点。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码4类传真标准类传真标准CCITT Group 3 2D编码过程：编码过程：1.如果如果b2不是严格的位于不是严格的位于a1左边，则进入第二步。

25、当左边，则进入第二步。当b2位于位于a1的左边时，输出越的左边时，输出越过码过码0001。把。把a0移动致移动致b2这一列，更新其他四个参数（其中这一列，更新其他四个参数（其中a1和和a2不会改变），不会改变），然后重复这一步。然后重复这一步。2.比较比较a1和和b1，位置差值大于，位置差值大于3，则进入第三步。否则，使用垂直码编码。对，则进入第三步。否则，使用垂直码编码。对a1-b1进行编码。把进行编码。把a0移到移到a1位置，更新其他位置，更新其他4个参数，回到第一步。个参数，回到第一步。3.使用水平码编码，即输出使用水平码编码，即输出001+MH(a0a1)+MH(a1a2).把把a0移

26、动到移动到a2刚才的位置，刚才的位置，并相应的更新并相应的更新4个参数，返回第一步。个参数，返回第一步。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码位置差异垂直码3000001020000101010011011200001130000011算术编码算术编码算术编码在图像的压缩中被广泛的使用。在算术编码中，消息用算术编码在图像的压缩中被广泛的使用

27、。在算术编码中，消息用0到到1之间的实数进之间的实数进行编码。算术编码用到两个基本的参数：信源符号出现的概率和编码的间隔。行编码。算术编码用到两个基本的参数：信源符号出现的概率和编码的间隔。例：例：A,B,C,D概率分别为：概率分别为：0.1,0.4,0.2,0.31. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码信源符号信源符号概率概率初始编码间隔初始编码间隔A0.10,0.1)B0.40.1,0.5)C0.20.5,0.7)D0.30.7,1)01ADCB输输入入C0.50.7A0.50.52

28、D0.5140.52A0.5140.5146C0.51430.51442D0.514384B0.514420.51438760.514402输输出出算术编码算术编码在实际应用中，用二进制小数表示算术编码的结果。在实际应用中，用二进制小数表示算术编码的结果。初始条件：初始条件：考虑一个有考虑一个有M个符号的字符表集个符号的字符表集a1, ，am，假设概率，假设概率p(ai)Pi 。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码11miip算术编码算术编码算法描述：算法描述：步骤（步骤（1）若输入

29、符号）若输入符号X1ai ， （i 1， ，M），那么初始子区间定义），那么初始子区间定义为为 这里这里 P0 0设设 L l1 ，R r1 ， d1 r1 l1，j =1 1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码iiiiiipprlI111111,算术编码算术编码算法描述：算法描述：步骤（步骤（2） 将将L 和和 R 转换为二进制小数形式，转换为二进制小数形式，对对k = j, j+1, ，依次比较，依次比较Uk=Vk? ， 若相等，则输出若相等，则输出 Uk, j = j+1；否则，

30、转步骤（否则，转步骤（3）1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码112,2kkkkkkvRuL算术编码算术编码算法描述：算法描述：步骤步骤(3) n n1，读入下一符号，读入下一符号， Xn ai，将区间细分，将区间细分，1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码iiinniiinnnnnpdlpdlrlI1111111,）。转（令2,nnnnnlrdrRlL1. 数据压缩的基本原

31、理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码nXn aiL (二进制)R(二进制)dnj输出1X1 a2 0.5 , 0.75)0.100.110.2511,j+2-2X2 a1 0.5 , 0.625)0.1000.1010.12520, j+3-30.59375 , 0.609375)0.100110.1001110.01562530,j+41,j+51,j+6-算术编码算术编码应注意的几个问题：应注意的几个问题：（1）由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，）由于实际的计算机的精

32、度不可能无限长，运算中出现溢出是一个明显的问题，在编码的时候必须注意，可以采用一些方法来解决。在编码的时候必须注意，可以采用一些方法来解决。（2）算术编码器对整个消息只产生一个码字，这个码字是在间隔）算术编码器对整个消息只产生一个码字，这个码字是在间隔0，1中的一个实中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。（3）算术编码是一种对错误和敏感的编码方法，如果有一位发生错误就会导致整）算术编码是一种对错误和敏感的编码方法，如果有一位发生错误就会导致整个消息译码错误。个消息译码错误。1. 数据压缩的基本原理和方法

33、数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 2 统计编码统计编码前面所介绍的无损编码技术只能在前面所介绍的无损编码技术只能在己知信源的统计规律己知信源的统计规律是有效应用，但在是有效应用，但在压缩的很多时候事先并不知道这些规律。压缩的很多时候事先并不知道这些规律。因此，编码器事先不知道数据源的概率时，可以在数据流中凭经验逐步精因此，编码器事先不知道数据源的概率时，可以在数据流中凭经验逐步精确地估测。确地估测。必须满足的几个条件：必须满足的几个条件：p编码器自适应程序造成的延迟和复杂性必须能够被系统所接受；编码器自适应程序造成的延迟和复杂性必

34、须能够被系统所接受；p信源的统计特征必须足够平稳；信源的统计特征必须足够平稳；p在编码器和解码器中事先统一好自适应程序，使解码器在无损的解码数在编码器和解码器中事先统一好自适应程序，使解码器在无损的解码数据流中保持与编码器同步，而不需要编码器另送一组信息来描述其适应过据流中保持与编码器同步，而不需要编码器另送一组信息来描述其适应过程。程。 1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ编码：编码：LZ编码是一种被广泛使用的自适应的编码方法，它有许多变体。编码是一种被广泛使用

35、的自适应的编码方法，它有许多变体。 划分：许多灵活的无损编码方案都是把信源符号划分成一系列的段，然后划分：许多灵活的无损编码方案都是把信源符号划分成一系列的段，然后产生压缩编码代表这些段。产生压缩编码代表这些段。LZ算法的变体，典型的两种，算法的变体，典型的两种，LZ77和和LZ78，使用的划分方法有所不同。使用的划分方法有所不同。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ77压缩压缩为了更好地说明为了更好地说明LZ77算法的原理，首先介绍算法中用到的几个术语：算法的原

36、理，首先介绍算法中用到的几个术语：输入数据流输入数据流(input stream)：要被压缩的字符序列。：要被压缩的字符序列。 字符字符(character)：输入数据流中的基本单元。：输入数据流中的基本单元。 3. 编码位置编码位置(coding position)：输入数据流中当前要编码的字符位置，指：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。前向缓冲存储器中的开始字符。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ77压缩压缩前向缓冲存储器前向缓

37、冲存储器(Lookahead buffer)：存放从编码位置到输入数据流结：存放从编码位置到输入数据流结束的字符序列的存储器。束的字符序列的存储器。 窗口窗口(window)：指包含：指包含W个字符的窗口，字符是从编码位置开始向后数个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。也就是最后处理的字符数。 6. 指针指针(pointer)：指向窗口中的匹配串且含长度的指针。：指向窗口中的匹配串且含长度的指针。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ77压

38、缩压缩LZ77编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ77压缩压缩编码算法的具体执行步骤：编码算法的具体执行步骤：把编码位置设置到输入数据流的开始位置。把编码位置设置到输入数据流的开始位置。 查找窗口中最长的匹配串。查找窗口中最长的匹配串。 以以“(Pointer, Length) Characters”的格式输出，其中的格式输出，其中Pointer是指向窗

39、是指向窗口中匹配串的指针，口中匹配串的指针，Length表示匹配字符的长度，表示匹配字符的长度，Characters是前向是前向缓冲存储器中的不匹配的第缓冲存储器中的不匹配的第1个字符。个字符。1. 如果前向缓冲存储器不是空的，则把编码位置和窗口向前移如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤个字符，然后返回到步骤2。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ77压缩压缩例例第一次输出第一次输出1. 数据压缩的基本原理

40、和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ77压缩压缩第二次输出第二次输出1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ77压缩压缩第三次输出第三次输出1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ77压缩压缩第四次输出第四次输出1. 数据压缩的基本原理

41、和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ77压缩压缩第五次输出第五次输出1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ77压缩压缩真正实现真正实现 LZ77 算法时还有许多复杂的问题需要解决，如：算法时还有许多复杂的问题需要解决，如：& 对对“(Back_chars, Chars_length) Explicit_character”三元组的编三元组的编码方法码方

42、法& 如何查找最长匹配串如何查找最长匹配串& 窗口的最大长度窗口的最大长度1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZSS编码编码LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面：决方案包含有冗余信息。冗余信息表现在两个方面：一是空指针；二是编码器输出额外的字符，这种字符是可能包含在下一个一是空指针；二是编码器输出额外的字符，这种字符

43、是可能包含在下一个匹配串中的字符。匹配串中的字符。LZSS算法以比较有效的方法解决两个冗余。它的思想是如果匹配串的长度算法以比较有效的方法解决两个冗余。它的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。缺点：由于输比指针本身的长度长就输出指针，否则就输出真实字符。缺点：由于输出的压缩数据流中包含有指针和字符本身，为了区分它们就需要有额外出的压缩数据流中包含有指针和字符本身，为了区分它们就需要有额外的标志位。的标志位。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无

44、损信源编码LZ78编码编码与与LZ77相比，相比，LZ78方法维护了一张方法维护了一张“词典词典”。但是，在压缩后的数据流中，并不。但是，在压缩后的数据流中，并不需要保存这张词典。在译码的过程中，从码字流中重构词典。需要保存这张词典。在译码的过程中，从码字流中重构词典。以二进制串为例，介绍以二进制串为例，介绍LZ78编码。编码。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ78编码编码00010110000010100100100010011LZ78划分结果：划分结果：0，

45、00，1，01，10，000，010，编码的过程中可以构造出一颗编码的过程中可以构造出一颗LZ78树（即词典），编码器输出节点的序号和树（即词典），编码器输出节点的序号和“向左向左”或或“向右向右”的信息。在编码器和解码器端都遵守事先约定的构建方法。的信息。在编码器和解码器端都遵守事先约定的构建方法。段段K：可以用编码树中其父节点的序列以及其位于其父节点的左支还是右支来表示，：可以用编码树中其父节点的序列以及其位于其父节点的左支还是右支来表示，这样，编码器就可以向解码器精确的指出下一段。同时，解码器也能与编码器同步这样，编码器就可以向解码器精确的指出下一段。同时，解码器也能与编码器同步的建立的

46、建立LZ78树。解码器建立树的信息被包含在连续的段中。树。解码器建立树的信息被包含在连续的段中。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ78编码编码00010110000010100100100010011LZ78划分结果：划分结果：0，00，1，01，10，000，010，编码的过程中可以构造出一颗编码的过程中可以构造出一颗LZ78树（即词典），编码器，输出节点的序号和树（即词典），编码器，输出节点的序号和“向向左左”或或“向右向右”的信息。在编码器和解码器端都遵守

47、事先约定的构建方法。的信息。在编码器和解码器端都遵守事先约定的构建方法。段段K：可以用编码树中其父节点的序列以及其位于其父节点的左支还是右支来表示，：可以用编码树中其父节点的序列以及其位于其父节点的左支还是右支来表示，这样，编码器就可以向解码器精确的指出下一段。同时，解码器也能与编码器同步这样，编码器就可以向解码器精确的指出下一段。同时，解码器也能与编码器同步的建立的建立LZ78树。解码器建立树的信息被包含在连续的段中。树。解码器建立树的信息被包含在连续的段中。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通

48、用无损信源编码通用无损信源编码1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理LZ78编码编码编码器中指定段编码器中指定段K需要多少二进制数？需要多少二进制数？在编码器开始划分在编码器开始划分K段时，树上已经有段时，树上已经有K个节点了（根节点，节点个节点了（根节点，节点1到节点到节点K1）。最简单的编码方法，）。最简单的编码方法，log2k能够描述其父节点，然后在加上最后一能够描述其父节点，然后在加上最后一位，

49、位，log2k+1可以描述这个段。可以描述这个段。上例的编码效率：上例的编码效率：28位，编码以后必须用位，编码以后必须用40个二进制书来表示这个个二进制书来表示这个28位的位的序列序列1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ78编码编码改进：在二进制数字的划分中，当一个节点第二次被指定为新段的父节点改进：在二进制数字的划分中，当一个节点第二次被指定为新段的父节点时，表示这个段将有一个新的终结节点，原来的这个父节点不可能第三次时，表示这个段将有一个新的终结节点，原来的

50、这个父节点不可能第三次的被指定为父节点，同时，不用记录最后表示的被指定为父节点，同时，不用记录最后表示“方向方向”的这一位，一定是的这一位，一定是“填空填空”。这样就可以压缩掉一位。这样就可以压缩掉一位。压缩最后一位的改进法被称为压缩最后一位的改进法被称为LZ78S。上例中，段上例中，段3是根节点的最后一个子节点，段是根节点的最后一个子节点，段4是节点是节点1的最后一个后代，段的最后一个后代，段11是节点是节点2的最后一个后代。可以使用的最后一个后代。可以使用40-337个二进制数来编码个二进制数来编码28个源个源字符。字符。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用

51、数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ78E编码编码LZ78E：一个节点不会被第三次指定为：一个节点不会被第三次指定为“父节点父节点”。左右都已经有节点的节点，称。左右都已经有节点的节点，称为为“死节点死节点”。我们可将。我们可将“死死”节点截去，解码器知道什么时候节点死掉，也就知节点截去，解码器知道什么时候节点死掉，也就知道什么时候把节点截去，只要编码器和解码器采用相同的方法。道什么时候把节点截去，只要编码器和解码器采用相同的方法。上例中，上例中，LZ78E描述描述11段所需的二进制数字的编码位数为段所需的二进制数字的编码位数为3

52、6。LZ78SE：将：将LZ78E和和LZ78S结合。进一步降低编码所需要的二进制位。在本例中，结合。进一步降低编码所需要的二进制位。在本例中，LZ78SE需要需要33位二进制数来完成编码。位二进制数来完成编码。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZ78EP编码和编码和LZ78SEP编码编码试图用一个更小的数表示试图用一个更小的数表示L（k），以描述），以描述LZ78划分。将活节点进行前缀编划分。将活节点进行前缀编码，不考虑它们的概率特性（假设概率相等）。码，不考虑

53、它们的概率特性（假设概率相等）。 1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZW编码编码W表示一个人的姓。表示一个人的姓。LZW的一个重要特征是采用了的一个重要特征是采用了Welch修正，其目的是克服发送修正，其目的是克服发送每段最后一个未压缩字符造成的低效率。解码器比编码器晚一步更新。每段最后一个未压缩字符造成的低效率。解码器比编码器晚一步更新。LZW树开始时由根节点和所有的单字符量构成。在二进制数据中，树开始时由根节点和所有的单字符量构成。在二进制数据中，LZW树最初

54、由根树最初由根节点以及表示节点以及表示0、1的两个子节点构成。的两个子节点构成。第第K个个LZW段是从未划分部分的第一个字符开始，在当前的段是从未划分部分的第一个字符开始，在当前的LZW树中找出一个最长树中找出一个最长的匹配，的匹配，1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码kLZW编码编码在划分出在划分出 之后，编码器就对之后，编码器就对LZW树进行更新；在树进行更新；在 所对应的节点再扩展出所对应的节点再扩展出一个分支节点。这个子节点的数字等于要划分的数据部分的第一个字

55、符。一个分支节点。这个子节点的数字等于要划分的数据部分的第一个字符。解码器在相应的时刻并不知道此信息，但可以根据接下来的解码器在相应的时刻并不知道此信息，但可以根据接下来的 的信息进行相应的信息进行相应的的LZW树构造。树构造。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码kk1kLZW编码编码例：例： 00010110000010100100100010011见见LZW编解码示意图编解码示意图1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基

56、本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码LZW编码编码效率分析：效率分析：要用要用 log2(k+2) 个二进制数表示。个二进制数表示。LZWE ：截去：截去“死死”节点节点LZWEP：在：在LZWE基础上采用前缀编码基础上采用前缀编码1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 3 通用无损信源编码通用无损信源编码k预测编码是根据原始的离散信号之间存在着一定的关联性的特点，利用前面的一个预测编码是根据原始的离散信号之间存在着一定的关联性的特点，利用前面的一个或多个信号对下

57、一个信号进行预测，然后对实际值和预测值的差进行编码。或多个信号对下一个信号进行预测，然后对实际值和预测值的差进行编码。如果预测比较准确，则误差会接近如果预测比较准确，则误差会接近0。这样，再同等精度要求的条件下，可以用较。这样，再同等精度要求的条件下，可以用较少的位数进行编码，达到压缩数据的目的。少的位数进行编码，达到压缩数据的目的。两种典型的预测编码：两种典型的预测编码：DPCM和和ADPCM1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 4 预测编码预测编码DPCM编码：量化实际值和预测值的差，达到压缩的目的。

58、编码：量化实际值和预测值的差，达到压缩的目的。ADPCM编码：采用自适应量化或自适应预测。在一定的量化级数下减少量化误差编码：采用自适应量化或自适应预测。在一定的量化级数下减少量化误差或在同样的误差条件下压缩数据率，根据信号分布均匀的特点，系统具有随输入信或在同样的误差条件下压缩数据率，根据信号分布均匀的特点，系统具有随输入信号的变化而改变量化区间大小，以保持输入给量化器的信号基本均匀的能力，这种号的变化而改变量化区间大小，以保持输入给量化器的信号基本均匀的能力，这种能力称为自适应量化。能力称为自适应量化。预测参数的最佳化依赖于信源的统计特性，要得到最佳预测参数是一件繁琐的工作，预测参数的最佳

59、化依赖于信源的统计特性，要得到最佳预测参数是一件繁琐的工作，而采用固定的预测参数往往又得不到较好性能。自适应预测：随着编码区间的不同，而采用固定的预测参数往往又得不到较好性能。自适应预测：随着编码区间的不同，预测参数自适应地变化。预测参数自适应地变化。1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 4 预测编码预测编码变换编码是有失真编码的一种重变换编码是有失真编码的一种重要的编码类型。在变换编码中，要的编码类型。在变换编码中，原始数据从初始空间或者时间域原始数据从初始空间或者时间域进行变换，使得信号中最重要的进行

60、变换，使得信号中最重要的部分在变换后的域中易于识别，部分在变换后的域中易于识别，并且集中出现，便于编码。并且集中出现，便于编码。变换编码系统中压缩数据的三个变换编码系统中压缩数据的三个主要步骤：主要步骤：变换变换变换域采样变换域采样量化量化1. 数据压缩的基本原理和方法数据压缩的基本原理和方法1. 3 常用数据压缩方法的基本原理常用数据压缩方法的基本原理1. 3. 5 变换编码变换编码通过对数据源的分析，将其分解成一系列更适合表示的通过对数据源的分析，将其分解成一系列更适合表示的“基元基元”，或从中提取出若，或从中提取出若干具有更本质意义的参数，编码仅对这些基本单元或特征参数进行。干具有更本质意义的参数，编码仅对这