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

1、第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法2. 音频的紧缩3. 视觉类媒体紧缩第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 1 数据紧缩技术的性能目的评价数据紧缩技术的3个关键目的：紧缩比：输入、输出数据量之比。质量：无损和有损。无损没有信息的损失，所以质量不是衡量的规范。有损：经过损失一些细节的、对人的感观来说不重要的信息提高紧缩比，分为客观评价和客观评价。客观评价：方差、新噪比等。紧缩和解紧缩的速度：实时的采集系统中，紧缩速度很重要。否那么会丧失信息。而存储回放中，结紧缩的速度显得比紧缩的速度重要，由于解紧缩面对大多数用户的实时需求。第 三 章 多媒体数据紧缩

2、1. 数据紧缩的根本原理和方法1. 2 数据冗余的类型与紧缩方法分类需求紧缩的缘由是由于信息数据存在着冗余。冗余，数据量和信息量不成正比。空间冗余：例如，相邻象素(程度和垂直方向)有同样的值。时间冗余：时间相关媒体，帧与帧一样。编码冗余：同样长度的编码可以表示不同的信息。如黑白图像假设每个象素点用8位表示；构造冗余：对称的构造假设都加以记录的话就出现构造冗余。另外，很多成分相对于人的觉得来说重要性不一样。因此，紧缩方法就是充分利用这些冗余和特性。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 2 数据冗余的类型与紧缩方法分类数据紧缩方法的分类根据解码后数据与原始数据能否完全一致进

3、展分类，紧缩方法可被分为两大类： 有损紧缩：减少信息量，损失的信息不能再恢复 无损紧缩：可100复原第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理信源：S S1,，Sn熵的概念：熵是信息量的度量方法，它表示某一事件出现的音讯越多，事件发生的能够性就越小，相应的，这个信息出现的概率小。某个事件的信息量，用Ii log 2 Pi表示。其中，Pi 表示第i个事件的概率。1. 3. 1 根本概念第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理信源S的熵定义为：1. 3. 1 根本概念第 三 章 多媒体数据紧缩1.

4、 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理编码：一个信源符号集转换为另一个符号集信源符号的集合：S S1,，Sn概率： P1，,Pn码符号集合：码字中的元素，二进制编码那么为 X，。码字的集合：W W1,，Wn编码长度： L1, ，Ln，可分为变长码及定长码1. 3. 1 根本概念第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理独一可译码：恣意有限长，不需分隔符的码符号序列，能独一译码非前缀码：W中恣意码字Wi都不是其他码字的前缀。非前缀码一定是独一可译码例：编码方法A：具有独一可译码性编码方法C：非前缀码编码方法D：具有可独一译

5、码性，但不符合非前缀码的条件。1. 3. 1 根本概念第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理非前缀码一定是独一可译码。反之那么不然。1. 3. 1 根本概念信源符号概率编码方法A编码B编码C编码DHuffman 1Huffman 2A10.400000010000A20.150011011011100100A30.1501000001010110110A40.100110110010111111010A50.10100101011000010101011A60.051011111010001101101110A70.041100001110

6、1001010111011110A80.0111100111111001110111111111平均编码长度 编码方法A：3； 编码方法B：1.5编码方法C : 2.9；编码方法D : 2.85 Huffman编码：2.56第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理给定信源符号集合S及码符号集X，可以构造多个独一可译码。多个编码的比较规范：平均编码长度低。假设我们用 lj 表示信源符号aj的二进制编码长度，根据它的统计信息，平均编码长度：1. 3. 1 根本概念结论：对二进制编码方式 即码符号的取值只需0 ，1 两种情况平均编码长度满足码字的平

7、均长度不能小于信源熵。假设采用非等长编码：能找到一种编码，平均长度为信源熵 1第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 1 根本概念第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理包括行程编码、LZW编码、huffman编码等。1. 3. 2 统计编码熵编码第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理行程编码：检测反复的比特或者字符序列，并用字符，反复次数来表示。思索的问题：字符的值反复次数，二者之间能否运用分隔符，反复的次数如何编码运用变长

8、码还是定长码等1. 3. 2 统计编码第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理Huffman编码：于1952年提出的对统计独立信源能到达最小平均码长的编码方法。Huffman编码的过程：构造一棵编码树。 构造方法：首先找出两个具有最小概率的节点，构造一个二叉树，以这两个节点为这棵树的叶子节点，根节点看作为新的节点，它的概率为两个叶子节点概率之和；此跟节点与未处置的节点构成新的节点集合，反复上面的过程，直到节点集合中只剩一个节点为止。1. 3. 2 统计编码第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本

9、原理Huffman编码当信源符号概率是2的负幂次方时，编码效率到达100%缺陷：Huffman编码方法没有错误维护的功能，在译码时，假设码串中没有错误，那么就能一个接一个地正确译出代码。假设出现错误，哪怕仅仅是一位的错误，不但这个码本身会发生错误，并且会导致其他代码出错，这种景象称为错误传播error propagation。计算机也无法去发现错误纠正错误。(2) Huffman码是变长度码，且没有额外同步码，因此很难随意查找或调用紧缩文件中间的内容，然后再译码。1. 3. 2 统计编码规范中的编码3类规范及4类规范CCITT Group 3 1D/2D ：扫描、尺寸和传输：扫描：每行1728

10、个象素。规范扫描行宽215mm，垂直方向3.85行/mm,或7.7行/mm.尺寸：A4幅面传输：用于传输每行扫描编码后构成的数据位、填充位、行终了符号的时间总和，最大20ms第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码规范中的编码3类规范CCITT Group 3 1D及4类规范：3类编码方法采用一维编码，扫描时统计游程，并将游程分为白游程及黑游程，白游程和黑游程再采用Huffman编码。假设每行的第一个行程是白色的假设不是，那么发出一个长度为0的白色游程码，每行的结尾发出一个EOL信号码。第 三 章 多媒体数据紧缩1.

11、数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码3类规范CCITT Group 3 1D码表中的游程，064，称为终止码。终止码用于表示小于64个像素的游程。64，128，192，256，320，1728，64的倍数，称为编排码，编排码用于表示是64个像素倍数的游程。 第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码白色游程码字黑色游程码字0001101010000011011

12、1100011110102011121131000310630011010063EOL000000000001终止码第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码白色游程码字黑色游程码字64110116412810010128192010111192256011011125617280100110111728编排码3类规范CCITT Group 3 1D例如，13471344+3个白像素的游程编码用以下两种代码进展编码：13446421个白像素的编排码0110110103个白像素的终止码1000那么，1347个白像素的紧缩位

13、流是0110110101000第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码4类规范CCITT Group 3 2D将扫描线每K条放在一同进展处置。每组K条线中的第一条用CCITT Group 3 1D方法编码，这条线就成为下一条线的参考线，然后运用二维方法和一 维方法为这组K条线中的其他扫描线编码。 缘由：横跨相邻两条扫描线的图像数据能够是冗余的。假设在一指定线上出现了黑白过渡，那么有能够在下一扫描线上加或减三个像素之间的位置上也出现一样的过渡。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩

14、方法的根本原理1. 3. 2 统计编码4类规范CCITT Group 3 2D编码方法：每个K组的第一条线采用Group3 1D方式编码，以作为这组K条线中其他线的扫描线。2D方法运用了一些附加码的组合为这组K条线中的每一条编码。附加码有3种：垂直码，越过码，程度码。 第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码4类规范CCITT Group 3 2D越过码固定取值：0001程度码也固定取值：001垂直码有7类，它的值由参考线中变化像素的位置与编码线重变化像素的位置之间的差距决议。 第 三 章 多媒体数据紧缩1. 数据紧缩

15、的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码位置差异垂直码30000010200001010100110112000011300000114类规范CCITT Group 3 2D二维编码：一种循环算法，依托a0, a1,a2,b1,b2 五个参数的更新来循环。如下例所示。a0表示预备编码的行程起始位置的像素点，a1为当前行下一个行程起始位置的像素点，a2表示再下一个行程起始位置的象素点。b1为参考行上位于a0位置右边行程起始位置的像素点，其颜色与a1一致，b2为参考行a0之后下一个行程起始位置的象素点。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1.

16、 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码4类规范CCITT Group 3 2D编码过程：1.假设b2不是严厉的位于a1左边，那么进入第二步。当b2位于a1的左边时，输出越过码0001。把a0挪动致b2这一列，更新其他四个参数其中a1和a2不会改动，然后反复这一步。2.比较a1和b1，位置差值大于3，那么进入第三步。否那么，运用垂直码编码。对a1-b1进展编码。把a0移到a1位置，更新其他4个参数，回到第一步。3.运用程度码编码，即输出001+MH(a0a1)+MH(a1a2).把a0挪动到a2刚刚的位置，并相应的更新4个参数，前往第一步。第 三 章 多媒体数据紧缩1. 数据紧

17、缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码位置差异垂直码3000001020000101010011011200001130000011算术编码算术编码在图像的紧缩中被广泛的运用。在算术编码中，音讯用0到1之间的实数进展编码。算术编码用到两个根本的参数：信源符号出现的概率和编码的间隔。例：A,B,C,D概率分别为：0.1,0.4,0.2,0.3第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3.

18、 2 统计编码信源符号概率初始编码间隔A0.10,0.1)B0.40.1,0.5)C0.20.5,0.7)D0.30.7,1)29算术编码在实践运用中，用二进制小数表示算术编码的结果。初始条件：思索一个有M个符号的字符表集a1, ，am，假设概率p(ai)Pi 。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码算术编码算法描画：步骤1假设输入符号X1ai ， i 1， ，M，那么初始子区间定义为 这里 P0 0设 L l1 ，R r1 ， d1 r1 l1，j =1 第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1.

19、 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码算术编码算法描画：步骤2 将L 和 R 转换为二进制小数方式，对k = j, j+1, ，依次比较Uk=Vk? ， 假设相等，那么输出 Uk, j = j+1；否那么，转步骤3第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码算术编码算法描画：步骤(3) n n1，读入下一符号， Xn ai，将区间细分，第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法

20、1. 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码nXn aiInL (二进制)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由于实践的计算机的精度不能够无限长，运算中出现溢出是一个明显的问题，在编码的时候必需留意，可以采用一些方法来处理。2算术编码器对整个音讯只产生一个码字，这个码字是在间隔0，1中的一个

21、实数，因此译码器在接遭到表示这个实数的一切位之前不能进展译码。3算术编码是一种对错误和敏感的编码方法，假设有一位发生错误就会导致整个音讯译码错误。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 2 统计编码前面所引见的无损编码技术只能在己知信源的统计规律是有效运用，但在紧缩的很多时候事先并不知道这些规律。因此，编码器事先不知道数据源的概率时，可以在数据流中凭阅历逐渐准确地估测。必需满足的几个条件：编码器自顺应程序呵斥的延迟和复杂性必需可以被系统所接受；信源的统计特征必需足够平稳；在编码器和解码器中事先一致好自顺应程序，使解码器在无损的解码

22、数据流中坚持与编码器同步，而不需求编码器另送一组信息来描画其顺应过程。 第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ编码：LZ编码是一种被广泛运用的自顺应的编码方法，它有许多变体。 划分：许多灵敏的无损编码方案都是把信源符号划分成一系列的段，然后产生紧缩编码代表这些段。LZ算法的变体，典型的两种，LZ77和LZ78，运用的划分方法有所不同。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ77紧缩为了更好地阐明LZ77算法的原理，首先

23、引见算法中用到的几个术语：输入数据流(input stream)：要被紧缩的字符序列。 字符(character)：输入数据流中的根本单元。 3.编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开场字符。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ77紧缩前向缓冲存储器(Lookahead buffer)：存放从编码位置到输入数据流终了的字符序列的存储器。 窗口(window)：指包含W个字符的窗口，字符是从编码位置开场向后数也就是最后处置的字符数。 6.指针(

24、pointer)：指向窗口中的匹配串且含长度的指针。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ77紧缩LZ77编码算法的中心是查找从前向缓冲存储器开场的最长的匹配串。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ77紧缩编码算法的详细执行步骤：把编码位置设置到输入数据流的开场位置。 查找窗口中最长的匹配串。 以“(Pointer, Length) Characters的格式输出，其中Pointer是指向窗口中匹配串的指针，Len

25、gth表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。假设前向缓冲存储器不是空的，那么把编码位置和窗口向前移(Length+1)个字符，然后前往到步骤2。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ77紧缩例第一次输出第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ77紧缩第二次输出第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源

26、编码LZ77紧缩第三次输出第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ77紧缩第四次输出第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ77紧缩第五次输出第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ77紧缩真正实现 LZ77 算法时还有许多复杂的问题需求处理，如： 对“(Back_chars, Chars_length) Explicit_chara

27、cter三元组的编码方法 如何查找最长匹配串 窗口的最大长度第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZSS编码LZ77经过输出真实字符处理了在窗口中出现没有匹配串的问题，但这个处理方案包含有冗余信息。冗余信息表如今两个方面：一是空指针；二是编码器输出额外的字符，这种字符是能够包含在下一个匹配串中的字符。LZSS算法以比较有效的方法处理两个冗余。它的思想是假设匹配串的长度比指针本身的长度长就输出指针，否那么就输出真实字符。缺陷：由于输出的紧缩数据流中包含有指针和字符本身，为了区分它们就需求有额外的标志位。第 三

28、 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ78编码与LZ77相比，LZ78方法维护了一张“词典。但是，在紧缩后的数据流中，并不需求保管这张词典。在译码的过程中，从码字流中重构词典。以二进制串为例，引见LZ78编码。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ78编码00010110000010100100100010011LZ78划分结果：0，00，1，01，10，000，010，编码的过程中可以构造出一颗LZ78树即词典，编码器输

29、出节点的序号和“向左或“向右的信息。在编码器和解码器端都遵守事先商定的构建方法。段K：可以用编码树中其父节点的序列以及其位于其父节点的左支还是右支来表示，这样，编码器就可以向解码器准确的指出下一段。同时，解码器也能与编码器同步的建立LZ78树。解码器建立树的信息被包含在延续的段中。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ78编码00010110000010100100100010011LZ78划分结果：0，00，1，01，10，000，010，编码的过程中可以构造出一颗LZ78树即词典，编码器，输出节点的序

30、号和“向左或“向右的信息。在编码器和解码器端都遵守事先商定的构建方法。段K：可以用编码树中其父节点的序列以及其位于其父节点的左支还是右支来表示，这样，编码器就可以向解码器准确的指出下一段。同时，解码器也能与编码器同步的建立LZ78树。解码器建立树的信息被包含在延续的段中。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理LZ78编码编码器中

31、指定段K需求多少二进制数？在编码器开场划分K段时，树上曾经有K个节点了根节点，节点1到节点K1。最简单的编码方法，log2k可以描画其父节点，然后在加上最后一位，log2k+1可以描画这个段。上例的编码效率：28位，编码以后必需用40个二进制书来表示这个28位的序列第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ78编码改良：在二进制数字的划分中，当一个节点第二次被指定为新段的父节点时，表示这个段将有一个新的终结节点，原来的这个父节点不能够第三次的被指定为父节点，同时，不用记录最后表示“方向的这一位，一定是“填空。

32、这样就可以紧缩掉一位。紧缩最后一位的改良法被称为LZ78S。上例中，段3是根节点的最后一个子节点，段4是节点1的最后一个后代，段11是节点2的最后一个后代。可以运用40-337个二进制数来编码28个源字符。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ78E编码LZ78E：一个节点不会被第三次指定为“父节点。左右都曾经有节点的节点，称为“死节点。我们可将“死节点截去，解码器知道什么时候节点死掉，也就知道什么时候把节点截去，只需编码器和解码器采用一样的方法。上例中，LZ78E描画11段所需的二进制数字的编码位数为3

33、6。LZ78SE：将LZ78E和LZ78S结合。进一步降低编码所需求的二进制位。在本例中，LZ78SE需求33位二进制数来完成编码。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZ78EP编码和LZ78SEP编码试图用一个更小的数表示Lk，以描画LZ78划分。将活节点进展前缀编码，不思索它们的概率特性假设概率相等。 第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZW编码W表示一个人的姓。LZW的一个重要特征是采用了Welch修正，其目的

34、是抑制发送每段最后一个未紧缩字符呵斥的低效率。解码器比编码器晚一步更新。LZW树开场时由根节点和一切的单字符量构成。在二进制数据中，LZW树最初由根节点以及表示0、1的两个子节点构成。第K个LZW段是从未划分部分的第一个字符开场，在当前的LZW树中找出一个最长的匹配，第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZW编码在划分出 之后，编码器就对LZW树进展更新；在 所对应的节点再扩展出一个分支节点。这个子节点的数字等于要划分的数据部分的第一个字符。解码器在相应的时辰并不知道此信息，但可以根据接下来的 的信息进展相

35、应的LZW树构造。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZW编码例： 00010110000010100100100010011见LZW编解码表示图第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无损信源编码LZW编码效率分析：要用 log2(k+2) 个二进制数表示。LZWE ：截去“死节点LZWEP：在LZWE根底上采用前缀编码第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 3 通用无

36、损信源编码预测编码是根据原始的离散信号之间存在着一定的关联性的特点，利用前面的一个或多个信号对下一个信号进展预测，然后对实践值和预测值的差进展编码。假设预测比较准确，那么误差会接近0。这样，再同等精度要求的条件下，可以用较少的位数进展编码，到达紧缩数据的目的。两种典型的预测编码：DPCM和ADPCM第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 4 预测编码DPCM编码：量化实践值和预测值的差，到达紧缩的目的。ADPCM编码：采用自顺应量化或自顺应预测。在一定的量化级数下减少量化误差或在同样的误差条件下紧缩数据率，根据信号分布均匀的特点，

37、系统具有随输入信号的变化而改动量化区间大小，以坚持输入给量化器的信号根本均匀的才干，这种才干称为自顺应量化。预测参数的最正确化依赖于信源的统计特性，要得到最正确预测参数是一件繁琐的任务，而采用固定的预测参数往往又得不到较好性能。自顺应预测：随着编码区间的不同，预测参数自顺应地变化。第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 4 预测编码变换编码是有失真编码的一种重要的编码类型。在变换编码中，原始数据从初始空间或者时间域进展变换，使得信号中最重要的部分在变换后的域中易于识别，并且集中出现，便于编码。变换编码系统中紧缩数据的三个主要步骤：

38、变换变换域采样量化第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 5 变换编码经过对数据源的分析，将其分解成一系列更适宜表示的“基元，或从中提取出假设干具有更本质意义的参数，编码仅对这些根本单元或特征参数进展。译码时那么借助于一定的规那么或模型，按照一定的算法将这些基元或参数再“综合成原数据的一个逼近。 量化编码 小波变换编码 分形图像编码 子带编码第 三 章 多媒体数据紧缩1. 数据紧缩的根本原理和方法1. 3 常用数据紧缩方法的根本原理1. 3. 6 分析合成编码第 三 章 多媒体数据紧缩2. 音频的紧缩2. 1 音频紧缩编码的根本方

39、法2. 1. 1 概述第 三 章 多媒体数据紧缩2. 音频的紧缩2. 1 音频紧缩编码的根本方法2. 1. 2 波形编译码不利用生成话音信号的任何知识而企图产生一种重构信号，它的波形与原始话音波形尽能够一致。普通来说，这种编译码器的复杂程度比较低，数据速率在16Kbps时可以获得较好的质量。但假设数据率达不到这个要求，音质就会下降很快。波形编译码又可以分为时域法time domain approach和频域法(frequency domain approach)两类。第 三 章 多媒体数据紧缩2. 音频的紧缩2. 1 音频紧缩编码的根本方法2. 1. 2 波形编译码时域法：PCM、DPCM、

40、ADPCM频域法：子带编码时域法中，最简单的波形编码是脉冲编码调制pulse code modulation ,PCM，对输入信号进展采样和量化。第 三 章 多媒体数据紧缩2. 音频的紧缩2. 1 音频紧缩编码的根本方法2. 1. 2 波形编译码PCM均匀量化：假设采用相等的量化间隔对采样得到的信号作量化，那么这种量化方法称为均匀量化。用这种方法量化输入信号时，无论对大的输入信号还是小的输入信号一概都采用一样的量化间隔。均匀量化面临的问题：为了顺应幅度大的输入信号，同时又要满足精度要求，就需求添加样本的位数。但是，对话音信号来说，大信号出现的时机并不多，添加的样本位数就没有充分利用。为了抑制这

41、个缺乏，就出现了非均匀量化的方法，也叫做非线性量化。第 三 章 多媒体数据紧缩2. 音频的紧缩2. 1 音频的紧缩编码方法2. 1. 2 波形编译码PCM非均匀量化：对输入信号进展量化时，出现频率小的信号通常是一些极大的信号采用大的量化间隔，出现概率高的信号的区域，采用小的量化间隔。这样就可以在满足精度要求的情况下用较少的位数来完成量化。在非均匀量化中， 输入信号幅度和量化输出数据之间定义一种对应关系。如今较常用的有两种，律和A律。律对数PCM。A律，分段函数。第 三 章 多媒体数据紧缩2. 音频的紧缩2. 1 音频的紧缩编码方法2. 1. 2 波形编译码DPCM: differential

42、pulse code modulation，差分脉冲编码调制在话音编码中，一种普遍运用的技术叫做预测技术，这种技术是企图从过去的样本来预测下一个样本的值。根据：以为在话音样本之间存在相关性。假设样本的预测值与样本的实践值比较接近，它们之间的差值幅度的变化就比原始话音样本幅度值的变化小，因此量化这种差值信号时就可以用比较少的位数来表示差值。这就是差分脉冲编码调制的根底对预测的样本值与原始的样本值之差进展编码。第 三 章 多媒体数据紧缩2. 音频的紧缩2. 1 音频的紧缩编码方法2. 1. 2 波形编译码DPCM: differential pulse code modulation，差分脉冲编码

43、调制DPCM这种编译码器对幅度急剧变化的输入信号会产生比较大的噪声。改良的方法之一就是运用自顺应的预测器和量化器，这就产生了自顺应差分脉冲编码调制ADPCMadaptive differential PCM, ADPCM 。第 三 章 多媒体数据紧缩2. 音频的紧缩2. 1 音频的紧缩编码方法2. 1. 2 波形编译码频域法：子带编码。带宽：频率的变化范围。子带编码的主要过程：运用一组带通滤波器band-pass filter, BPF把输入音频信号的频带分成假设干个延续的频段，每个频段称为子带。对每个子带中的音频信号采用单独的编码方案去编码。在信道上传送时，将每个子带的代码复合起来。在接纳端

44、译码时，将每个子带的代码单独译码，然后把他们组合起来，复原成原来的音频信号。第 三 章 多媒体数据紧缩2. 音频的紧缩2. 1 音频的紧缩编码方法2. 1. 2 波形编译码子带编码的优点：1. 可以对每个子带分别进展控制，例如在进展自顺应控制时量化阶的大小可以按照每个子带的能量电平加以调理。2. 可根据每个子带信号在觉得上的重要性，对每个子带采用不同的编码方法。第 三 章 多媒体数据紧缩2. 音频的紧缩2. 2 质量的紧缩规范质量采样频率 kHz样本精度 b声道数据率（未压缩） kbps电话88单声道64AM110258单声道88FM220516立体声705.6CD44.116立体声1411.

45、2第 三 章 多媒体数据紧缩2. 音频的紧缩2. 3 调幅广播质量的音频紧缩规范标准速率（Kbps）算法应用G71164PCM公共网G72132ADPCM公共网G72264SBADPCMISDN，广播MPEG32448MPEG多媒体系统第 三 章 多媒体数据紧缩2. 音频的紧缩2. 4 MPEG音频编码方法MPEG音频紧缩规范为许多音频数据定义了许多算法，都采用了子带紧缩并充分利用人听觉的特点。在不用的运用需求中可以运用不同的算法。层次：MPEG音频规范定义了不同的附加规定来为不同的运用节省代价，MPEG音频中附加规定称为层，从13，复杂度添加。对于音乐和声音数据，双声道能在第三层以约64Kb

46、ps速率很好地编码。对于层次2为每通道128Kbps，层次1为192Kbps。 第 三 章 多媒体数据紧缩2. 音频的紧缩2. 4 MPEG音频编码方法第 三 章 多媒体数据紧缩2. 音频的紧缩2. 4 MPEG音频编码方法在MPEG2规范中，对音频编码进展了扩展。MPEG2在音频方面定义了两种声音数据紧缩格式，一种在规范中称为MPEG2 Audio，是以MPEG-1Audio兼容的，又称为MPEG-2 BC(backward compatible)。另一种称为MPEG2 AAC(Advanced Audio Coding)，它与MPEG1声音格式不兼容。 第 三 章 多媒体数据紧缩3. 视觉

47、类媒体紧缩3. 1 概述第 三 章 多媒体数据紧缩3. 视觉类媒体紧缩3. 2 有损编码方法截断：最简单的紧缩方法是经过减少每个象素的位数来减少数据。这种方法称为截断法。例如，32位系统，RGB种的每个分类用8Bits表示，通常情况下都可以将其截断为5：5：5。 颜色查找表：产生颜色表，图像的每个象素点记录一个表的位置号。可以用较少的位数表示图像的颜色。当图像颜色较少是采用这种方法可以得到很好的紧缩效果。大面积着色：在亮度/色度分量的方式的图像中，多个像素点共用色度信号。第 三 章 多媒体数据紧缩3. 视觉类媒体紧缩3. 3 JPEG混合紧缩JPEG的称号：Joint Photographic

48、 Coding Experts Group 结合图片专家组 ，它是由ISO规范化组织下的小组和CCITT 结合成立的，努力于静止图像的紧缩研讨。其发布的规范称为JPEG规范。JPEG紧缩，静态灰度或彩色图像的一种规范紧缩算法。是一种混合的紧缩算法，在这种紧缩算法中，采用了多种有损及无损紧缩技术。CCITT Group 3/ CCITT Group 4 是一种二值图像的紧缩方法，而JPEG是一种静止彩色图像和灰度图像的紧缩规范。JPEG曾经作为ISO规范公布。近年来新的规范：JPEG 2000。第 三 章 多媒体数据紧缩3. 视觉类媒体紧缩3. 3 JPEG混合紧缩JPEG的无损预测编码算法采用

49、预测器的方法进展编码。选择值预测选择值预测0非预测4a+b-c1a5a+(b-c)/22b6b+(a-c)/23C7(a+b)/2第 三 章 多媒体数据紧缩3. 视觉类媒体紧缩3. 3 JPEG混合紧缩JPEG中基于DCT的紧缩算法的主要步骤：1DCT 变换2对DCT系数进展量化3对量化后的系数进展编码译码或者叫做解紧缩的过程与紧缩编码过程正好相反。85第 三 章 多媒体数据紧缩3. 视觉类媒体紧缩3. 3 JPEG混合紧缩紧缩过程：1 分块：按序分块，将 图像分成 8 * 8 的子块。JPEG处置的是单独的彩色分量。2 FDCT变换(正向离散余弦变换，forward discrete cos

50、ine transform)：对每一个子块，进展FDCT变换，得到DCT系数矩阵。3 量化：量化是一种降低精度的过程，因此就减少了存储整数所需的位数。量化的过程：试图确定什么信息可以平安地消去，而没有任何明显的视觉保真度损失。DCT系数矩阵被量化以减少系数的精度，因此提高了紧缩率。 第 三 章 多媒体数据紧缩3. 视觉类媒体紧缩3. 3 JPEG混合紧缩紧缩过程：4 对量化后的值进展Z扫描：量化后的矩阵，右下角的部分接近0，把这个矩阵中的值重新陈列游程，可以使游程中0值的长度添加，以此进一步提高紧缩率。JPEG提出用之字形序列的方法为量化后的DCT系数排序。5对扫描后的数列进展编码：矩阵0，0

51、位置上的系数称为DC系数，矩阵中其他63个系数称为AC系数。DC系数与AC系数分别进展编码。DC系数编码：对相邻图像块之间的DC系数的差值进展编码。AC系数编码：游程长度编码第 三 章 多媒体数据紧缩第 三 章 多媒体数据紧缩3. 视觉类媒体紧缩3. 3 JPEG混合紧缩紧缩过程：5对扫描后的数列进展编码：矩阵0，0位置上的系数称为DC系数，矩阵中其他63个系数称为AC系数。DC系数与AC系数分别进展编码。DC系数编码：对相邻图像块之间的DC系数的差值进展编码。AC系数编码：游程长度编码6熵编码：对编码后的DC系数和AC系数进一步紧缩。7组成位数据流第 三 章 多媒体数据紧缩3. 视觉类媒体紧

52、缩3. 3 JPEG2000简介JPEG 2000， 正式称号为 “ISO 15444 ，同样是由JPEG 组织担任制定。JPEG 2000对于以往的JPEG规范有一个很大的飞跃。JPEG2000的原理： JPEG 2000 与传统 JPEG 最大的不同，在于它放弃了 JPEG 所采用的以离散余弦转换(Discrete Cosine Transform) 为主的区块编码方式，而采用以小波转换(Wavelet transform) 为主的多解析编码方式。第 三 章 多媒体数据紧缩3. 视觉类媒体紧缩3. 3 JPEG2000简介JPEG 2000能实现Loseless Compression无损

53、紧缩。在实践运用中，有一些重要的图像，如卫星遥感图像、医学图像、文物照片等，通常需求进展无损紧缩。对图像进展无损编码的经典方法预测法曾经开展成熟，并且作为一个规范写入了JPEG 2000 中。第 三 章 多媒体数据紧缩3. 视觉类媒体紧缩3. 3 JPEG2000简介JPEG 2000 能实现Progressive Transmission渐进传输。这是JPEG 2000的一个极其重要的特征。它先传输图像的轮廓，然后逐渐传输数据，不断提高图像质量，以满足用户的需求。这在网络传输中有着艰苦的意义。第 三 章 多媒体数据紧缩3. 视觉类媒体紧缩3. 3 JPEG2000简介JPEG 2000另一个

54、极其重要的优点：ROIRegion of Interest，即感兴趣区域。他可以指定感兴趣区域，在这些区域，他可以在紧缩时指定特定的紧缩质量，或在恢复时指定特定的解紧缩要求。JPEG 2000还思索了人的视觉特性，添加了视觉权重和掩膜。这样在不损害视觉效果的情况下，大大提高了效率。第 三 章 多媒体数据紧缩3. 视觉类媒体紧缩3. 4 视听通讯编解码规范H.26XITU:ISO/IEC:H.261H.262H.263H.263+H.264MPEG1MPEG2MPEG4 (Part2)MPEG7MPEG21MPEG4(Part10)第 三 章 多媒体数据紧缩3. 视觉类媒体紧缩3. 4 视听通讯

55、编解码规范H.26XH.261p64kb/s视频编码标准 时间1990年12月输入176144(QCIF) 352288(CIF)帧速率可变H.263MPEG2压缩算法运动补偿帧间预测（单双向预测）DCT 局部算法改进 可伸缩性应用通用电话交换网、局域网的视频通信第 三 章 多媒体数据紧缩3. 视觉类媒体紧缩3. 4 视听通讯编解码规范H.26XMPEG4(Part 2)MPEG4 Visual甚低码率活动图像及其伴音编码标准时间1999年输入176144的多种分辨率格式 输出4.6Kb/s64Kb/s压缩率 100压缩算法基于对象的新一代编码技术，注重交互性，即可包含自然对象，又可包含人工合

56、成对象应用可应用范围很广、目前多用于因特网视频传输、流媒体应用第 三 章 多媒体数据紧缩3. 视觉类媒体紧缩3. 4 视听通讯编解码规范H.26XH.264MPEG4(Part10)MPEG4 AVC时间2003年5月输入多种分辨率格式 输出压缩率压缩率最高的视频压缩标准，比MPEG4 Visual节约50的码率压缩算法基于传统框架的混合编码系统，只是做了局部优化。更注重编码效率和可靠性应用视频广播、视频通信和存储媒体（CD DVD）等多种应用第 三 章 多媒体数据紧缩3. 视觉类媒体紧缩3. 4 视听通讯编解码规范H.26XH.261规范是视频图像紧缩编码国际规范。用于传输率在p64Kbpsp64kbpsp130的视听效力的视频编码器。主要用于视频和电视会议。数字视频紧缩首先是用于电视会议和视频领域的。视频信号经过数字通道传送，利用的就是系统提供的每秒n64Kb数据传输率的通道。ITUT将这些效力开展为视频紧缩规范，就是ITUT H