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

研究生多媒体03多媒体数据压缩b2024/3/25研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.1数据压缩技术的性能指标评价数据压缩技术的3个关键指标：压缩比：输入、输出数据量之比。质量：无损和有损。无损没有信息的损失，所以质量不是衡量的标准。有损：通过损失一些细节的、对人的感观来说不重要的信息提高压缩比，分为主观评价和客观评价。客观评价：方差、新噪比等。压缩和解压缩的速度：实时的采集系统中，压缩速度很重要。否则会丢失信息。而存储回放中，结压缩的速度显得比压缩的速度重要，因为解压缩面对大多数用户的实时需求。研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

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

1.数据压缩的基本原理和方法

1.2数据冗余的类型与压缩方法分类数据压缩方法的分类根据解码后数据与原始数据是否完全一致进行分类，压缩方法可被分为两大类：有损压缩：减少信息量，损失的信息不能再恢复无损压缩：可100％还原研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理信源：S＝{S1,……，Sn}

熵的概念：熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，相应的，这个信息出现的概率小。某个事件的信息量，用 Ii＝－log2Pi

表示。其中，Pi表示第i个事件的概率。 1.3.1基本概念研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理信源S的熵定义为： 1.3.1基本概念研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理编码：一个信源符号集转换为另一个符号集

信源符号的集合： S＝{S1,……，Sn} 概率：P1，……,Pn 码符号集合：码字中的元素，二进制编码则为X＝｛０，１｝。 码字的集合： W＝{W1,……，Wn} 编码长度： L1,……，Ln，可分为变长码及定长码 1.3.1基本概念研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理唯一可译码：任意有限长，不需分隔符的码符号序列，能唯一译码非前缀码：W中任意码字Wi都不是其余码字的前缀。非前缀码一定是唯一可译码 例：编码方法A：具有唯一可译码性编码方法C：非前缀码编码方法D：具有可唯一译码性，但不符合非前缀码的条件。 1.3.1基本概念研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理非前缀码一定是唯一可译码。反之则不然。 1.3.1基本概念信源符号概率编码方法A编码B编码C编码DHuffman1Huffman2A10.400000010000A20.150011011011100100A30.1501000001010110110A40.100110110010111111010A50.10100101011000010101011A60.051011111010001101101110A70.0411000011101001010111011110A80.0111100111111001110111111111平均编码长度编码方法A：3；编码方法B：1.5编码方法C:2.9；编码方法D:2.85Huffman编码：2.56研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理给定信源符号集合S及码符号集X，可以构造多个唯一可译码。多个编码的比较标准：平均编码长度低。如果我们用lj表示信源符号aj的二进制编码长度，根据它的统计信息，平均编码长度： 1.3.1基本概念研究生多媒体03多媒体数据压缩b

结论： 对二进制编码方式（即码符号的取值只有0，1两种情况） 平均编码长度满足 码字的平均长度不能小于信源熵。 若采用非等长编码：能找到一种编码，平均长度为信源熵＋1第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.1基本概念研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理包括行程编码、LZW编码、huffman编码等。 1.3.2统计编码（熵编码）研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理行程编码：检测重复的比特或者字符序列，并用（字符，重复次数）来表示。考虑的问题：字符的值重复次数，二者之间是否使用分隔符，重复的次数如何编码（使用变长码还是定长码）等 1.3.2统计编码研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理Huffman编码：于1952年提出的对统计独立信源能达到最小平均码长的编码方法。Huffman编码的过程：构造一棵编码树。

构造方法：首先找出两个具有最小概率的节点，构造一个二叉树，以这两个节点为这棵树的叶子节点，根节点看作为新的节点，它的概率为两个叶子节点概率之和；此跟节点与未处理的节点形成新的节点集合，重复上面的过程，直到节点集合中只剩一个节点为止。 1.3.2统计编码研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理Huffman编码当信源符号概率是2的负幂次方时，编码效率达到100%缺点：Huffman编码方法没有错误保护的功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。如果出现错误，哪怕仅仅是一位的错误，不但这个码本身会发生错误，并且会导致其他代码出错，这种现象称为错误传播（errorpropagation）。计算机也无法去发现错误纠正错误。(2)Huffman码是变长度码，且没有额外同步码，因此很难随意查找或调用压缩文件中间的内容，然后再译码。 1.3.2统计编码研究生多媒体03多媒体数据压缩b传真标准中的编码（3类传真标准及4类传真标准CCITTGroup31D/2D）：扫描、尺寸和传输：扫描：每行1728个象素。标准扫描行宽215mm，垂直方向3.85行/mm,或7.7行/mm.尺寸：A4幅面传输：用于传输每行扫描编码后形成的数据位、填充位、行结束符号的时间总和，最大20ms第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码研究生多媒体03多媒体数据压缩b传真标准中的编码（3类传真标准CCITTGroup31D及4类传真标准）：3类编码方法采用一维编码，扫描时统计游程，并将游程分为白游程及黑游程，白游程和黑游程再采用Huffman编码。假设每行的第一个行程是白色的（如果不是，则发出一个长度为0的白色游程码），每行的结尾发出一个EOL信号码。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码研究生多媒体03多媒体数据压缩b3类传真标准CCITTGroup31D码表中的游程，0~64，称为终止码。终止码用于表示小于64个像素的游程。64，128，192，256，320……，1728，64的倍数，称为编排码，编排码用于表示是64个像素倍数的游程。

第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码白色游程码字黑色游程码字00011010100000110111100011110102011121131000310……630011010063……EOL000000000001终止码研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码白色游程码字黑色游程码字641101164……12810010128……192010111192……2560110111256………………17280100110111728……编排码研究生多媒体03多媒体数据压缩b3类传真标准CCITTGroup31D例如，1347（1344+3）个白像素的游程编码用以下两种代码进行编码：1344（64×21）个白像素的编排码——0110110103个白像素的终止码——1000那么，1347个白像素的压缩位流是0110110101000第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码研究生多媒体03多媒体数据压缩b4类传真标准CCITTGroup32D将扫描线每K条放在一起进行处理。每组K条线中的第一条用CCITTGroup31D方法编码，这条线就成为下一条线的参考线，然后使用二维方法和一维方法为这组K条线中的其余扫描线编码。

原因：横跨相邻两条扫描线的图像数据可能是冗余的。如果在一指定线上出现了黑白过渡，那么有可能在下一扫描线上加或减三个像素之间的位置上也出现相同的过渡。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码研究生多媒体03多媒体数据压缩b4类传真标准CCITTGroup32D编码方法：每个K组的第一条线采用Group31D方式编码，以作为这组K条线中其余线的扫描线。2D方法使用了一些附加码的组合为这组K条线中的每一条编码。附加码有3种：垂直码，越过码，水平码。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码研究生多媒体03多媒体数据压缩b4类传真标准CCITTGroup32D越过码固定取值：0001水平码也固定取值：001垂直码有7类，它的值由参考线中变化像素的位置与编码线重变化像素的位置之间的差距决定。

第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码位置差异垂直码300000102000010101001－1011－2000011－30000011研究生多媒体03多媒体数据压缩b4类传真标准CCITTGroup32D二维编码：一种循环算法，依靠a0,a1,a2,b1,b2五个参数的更新来循环。如下例所示。a0表示准备编码的行程起始位置的像素点，a1为当前行下一个行程起始位置的像素点，a2表示再下一个行程起始位置的象素点。b1为参考行上位于a0位置右边行程起始位置的像素点，其颜色与a1一致，b2为参考行a0之后下一个行程起始位置的象素点。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码研究生多媒体03多媒体数据压缩b4类传真标准CCITTGroup32D编码过程：

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.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码位置差异垂直码300000102000010101001－1011－2000011－30000011研究生多媒体03多媒体数据压缩b算术编码算术编码在图像的压缩中被广泛的使用。在算术编码中，消息用0到1之间的实数进行编码。算术编码用到两个基本的参数：信源符号出现的概率和编码的间隔。例：{A,B,C,D}概率分别为：{0.1,0.4,0.2,0.3}第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码信源符号概率初始编码间隔A0.1[0,0.1)B0.4[0.1,0.5)C0.2[0.5,0.7)D0.3[0.7,1)研究生多媒体03多媒体数据压缩b研究生多媒体03多媒体数据压缩b算术编码在实际应用中，用二进制小数表示算术编码的结果。初始条件：考虑一个有M个符号的字符表集{a1,……，am}，假设概率p(ai)＝Pi。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码研究生多媒体03多媒体数据压缩b算术编码算法描述：步骤（1）若输入符号X1＝ai，（i＝1，……，M），那么初始子区间定义为这里P0＝0设L＝l1，R＝r1，d1＝r1－l1，j=1

第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码研究生多媒体03多媒体数据压缩b算术编码算法描述：步骤（2）将L和R转换为二进制小数形式，对k=j,j+1,……，依次比较Uk=Vk?，若相等，则输出Uk,j=j+1； 否则，转步骤（3）第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码研究生多媒体03多媒体数据压缩b算术编码算法描述：步骤(3)n＝n＋1，读入下一符号，Xn＝ai，将区间细分，第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

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-------3[0.59375,0.609375)0.100110.1001110.01562530,j++41,j++51,j++6------研究生多媒体03多媒体数据压缩b算术编码应注意的几个问题：（1）由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，在编码的时候必须注意，可以采用一些方法来解决。（2）算术编码器对整个消息只产生一个码字，这个码字是在间隔0，1中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。（3）算术编码是一种对错误和敏感的编码方法，如果有一位发生错误就会导致整个消息译码错误。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.2统计编码研究生多媒体03多媒体数据压缩b前面所介绍的无损编码技术只能在己知信源的统计规律是有效应用，但在压缩的很多时候事先并不知道这些规律。因此，编码器事先不知道数据源的概率时，可以在数据流中凭经验逐步精确地估测。必须满足的几个条件：编码器自适应程序造成的延迟和复杂性必须能够被系统所接受；信源的统计特征必须足够平稳；在编码器和解码器中事先统一好自适应程序，使解码器在无损的解码数据流中保持与编码器同步，而不需要编码器另送一组信息来描述其适应过程。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZ编码：LZ编码是一种被广泛使用的自适应的编码方法，它有许多变体。

划分：许多灵活的无损编码方案都是把信源符号划分成一系列的段，然后产生压缩编码代表这些段。LZ算法的变体，典型的两种，LZ77和LZ78，使用的划分方法有所不同。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZ77压缩为了更好地说明LZ77算法的原理，首先介绍算法中用到的几个术语：输入数据流(inputstream)：要被压缩的字符序列。

字符(character)：输入数据流中的基本单元。3. 编码位置(codingposition)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZ77压缩前向缓冲存储器(Lookaheadbuffer)：存放从编码位置到输入数据流结束的字符序列的存储器。窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。6. 指针(pointer)：指向窗口中的匹配串且含长度的指针。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZ77压缩LZ77编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZ77压缩编码算法的具体执行步骤：把编码位置设置到输入数据流的开始位置。查找窗口中最长的匹配串。以“(Pointer,Length)Characters”的格式输出，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤2。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZ77压缩例第一次输出第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZ77压缩第二次输出第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZ77压缩第三次输出第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZ77压缩第四次输出第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZ77压缩第五次输出第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZ77压缩真正实现LZ77算法时还有许多复杂的问题需要解决，如：对“(Back_chars,Chars_length)Explicit_character”三元组的编码方法如何查找最长匹配串窗口的最大长度第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZSS编码LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面：一是空指针；二是编码器输出额外的字符，这种字符是可能包含在下一个匹配串中的字符。LZSS算法以比较有效的方法解决两个冗余。它的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。缺点：由于输出的压缩数据流中包含有指针和字符本身，为了区分它们就需要有额外的标志位。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZ78编码与LZ77相比，LZ78方法维护了一张“词典”。但是，在压缩后的数据流中，并不需要保存这张词典。在译码的过程中，从码字流中重构词典。以二进制串为例，介绍LZ78编码。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

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

1.数据压缩的基本原理和方法

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

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理研究生多媒体03多媒体数据压缩bLZ78编码编码器中指定段K需要多少二进制数？在编码器开始划分K段时，树上已经有K个节点了（根节点，节点1到节点K－1）。最简单的编码方法，[log2k]能够描述其父节点，然后在加上最后一位，[log2k]+1可以描述这个段。上例的编码效率：28位，编码以后必须用40个二进制书来表示这个28位的序列第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZ78编码改进：在二进制数字的划分中，当一个节点第二次被指定为新段的父节点时，表示这个段将有一个新的终结节点，原来的这个父节点不可能第三次的被指定为父节点，同时，不用记录最后表示“方向”的这一位，一定是“填空”。这样就可以压缩掉一位。压缩最后一位的改进法被称为LZ78S。上例中，段3是根节点的最后一个子节点，段4是节点1的最后一个后代，段11是节点2的最后一个后代。可以使用40-3＝37个二进制数来编码28个源字符。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZ78E编码LZ78E：一个节点不会被第三次指定为“父节点”。左右都已经有节点的节点，称为“死节点”。我们可将“死”节点截去，解码器知道什么时候节点死掉，也就知道什么时候把节点截去，只要编码器和解码器采用相同的方法。上例中，LZ78E描述11段所需的二进制数字的编码位数为36。LZ78SE：将LZ78E和LZ78S结合。进一步降低编码所需要的二进制位。在本例中，LZ78SE需要33位二进制数来完成编码。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZ78EP编码和LZ78SEP编码试图用一个更小的数表示L（k），以描述LZ78划分。将活节点进行前缀编码，不考虑它们的概率特性（假设概率相等）。

第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZW编码W表示一个人的姓。LZW的一个重要特征是采用了Welch修正，其目的是克服发送每段最后一个未压缩字符造成的低效率。解码器比编码器晚一步更新。LZW树开始时由根节点和所有的单字符量构成。在二进制数据中，LZW树最初由根节点以及表示0、1的两个子节点构成。第K个LZW段是从未划分部分的第一个字符开始，在当前的LZW树中找出一个最长的匹配，第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZW编码在划分出之后，编码器就对LZW树进行更新；在所对应的节点再扩展出一个分支节点。这个子节点的数字等于要划分的数据部分的第一个字符。解码器在相应的时刻并不知道此信息，但可以根据接下来的的信息进行相应的LZW树构造。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZW编码例：00010110000010100100100010011见LZW编解码示意图第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩bLZW编码效率分析： 要用[log2(k+2)]个二进制数表示。LZWE：截去“死”节点LZWEP：在LZWE基础上采用前缀编码第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.3通用无损信源编码研究生多媒体03多媒体数据压缩b预测编码是根据原始的离散信号之间存在着一定的关联性的特点，利用前面的一个或多个信号对下一个信号进行预测，然后对实际值和预测值的差进行编码。如果预测比较准确，则误差会接近0。这样，再同等精度要求的条件下，可以用较少的位数进行编码，达到压缩数据的目的。两种典型的预测编码：DPCM和ADPCM第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.4预测编码研究生多媒体03多媒体数据压缩bDPCM编码：量化实际值和预测值的差，达到压缩的目的。ADPCM编码：采用自适应量化或自适应预测。在一定的量化级数下减少量化误差或在同样的误差条件下压缩数据率，根据信号分布均匀的特点，系统具有随输入信号的变化而改变量化区间大小，以保持输入给量化器的信号基本均匀的能力，这种能力称为自适应量化。预测参数的最佳化依赖于信源的统计特性，要得到最佳预测参数是一件繁琐的工作，而采用固定的预测参数往往又得不到较好性能。自适应预测：随着编码区间的不同，预测参数自适应地变化。第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.4预测编码研究生多媒体03多媒体数据压缩b变换编码是有失真编码的一种重要的编码类型。在变换编码中，原始数据从初始空间或者时间域进行变换，使得信号中最重要的部分在变换后的域中易于识别，并且集中出现，便于编码。变换编码系统中压缩数据的三个主要步骤：变换变换域采样量化第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.5变换编码研究生多媒体03多媒体数据压缩b通过对数据源的分析，将其分解成一系列更适合表示的“基元”，或从中提取出若干具有更本质意义的参数，编码仅对这些基本单元或特征参数进行。译码时则借助于一定的规则或模型，按照一定的算法将这些基元或参数再“综合”成原数据的一个逼近。量化编码小波变换编码分形图像编码子带编码第三章多媒体数据压缩

1.数据压缩的基本原理和方法

1.3常用数据压缩方法的基本原理 1.3.6分析－合成编码研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

2.音频的压缩

2.1音频压缩编码的基本方法 2.1.1概述研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

2.音频的压缩

2.1音频压缩编码的基本方法 2.1.2波形编译码不利用生成话音信号的任何知识而企图产生一种重构信号，它的波形与原始话音波形尽可能一致。一般来说，这种编译码器的复杂程度比较低，数据速率在16Kbps时可以取得较好的质量。但如果数据率达不到这个要求，音质就会下降很快。波形编译码又可以分为时域法（timedomainapproach）和频域法(frequencydomainapproach)两类。研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

2.音频的压缩

2.1音频压缩编码的基本方法 2.1.2波形编译码时域法：PCM、DPCM、ADPCM频域法：子带编码时域法中，最简单的波形编码是脉冲编码调制（pulsecodemodulation,PCM），对输入信号进行采样和量化。研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

2.音频的压缩

2.1音频压缩编码的基本方法 2.1.2波形编译码PCM均匀量化：如果采用相等的量化间隔对采样得到的信号作量化，那么这种量化方法称为均匀量化。用这种方法量化输入信号时，无论对大的输入信号还是小的输入信号一律都采用相同的量化间隔。均匀量化面临的问题：为了适应幅度大的输入信号，同时又要满足精度要求，就需要增加样本的位数。但是，对话音信号来说，大信号出现的机会并不多，增加的样本位数就没有充分利用。为了克服这个不足，就出现了非均匀量化的方法，也叫做非线性量化。研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

2.音频的压缩

2.1音频的压缩编码方法 2.1.2波形编译码PCM非均匀量化：对输入信号进行量化时，出现频率小的信号（通常是一些极大的信号）采用大的量化间隔，出现概率高的信号的区域，采用小的量化间隔。这样就可以在满足精度要求的情况下用较少的位数来完成量化。在非均匀量化中，输入信号幅度和量化输出数据之间定义一种对应关系。现在较常用的有两种，μ律和A律。μ律——对数PCM。A律，分段函数。研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

2.音频的压缩

2.1音频的压缩编码方法 2.1.2波形编译码DPCM:differentialpulsecodemodulation，差分脉冲编码调制在话音编码中，一种普遍使用的技术叫做预测技术，这种技术是企图从过去的样本来预测下一个样本的值。根据：认为在话音样本之间存在相关性。如果样本的预测值与样本的实际值比较接近，它们之间的差值幅度的变化就比原始话音样本幅度值的变化小，因此量化这种差值信号时就可以用比较少的位数来表示差值。这就是差分脉冲编码调制的基础——对预测的样本值与原始的样本值之差进行编码。研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

2.音频的压缩

2.1音频的压缩编码方法 2.1.2波形编译码DPCM:differentialpulsecodemodulation，差分脉冲编码调制DPCM这种编译码器对幅度急剧变化的输入信号会产生比较大的噪声。改进的方法之一就是使用自适应的预测器和量化器，这就产生了自适应差分脉冲编码调制ADPCM（adaptivedifferentialPCM,ADPCM）。研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

2.音频的压缩

2.1音频的压缩编码方法 2.1.2波形编译码频域法：子带编码。带宽：频率的变化范围。子带编码的主要过程：使用一组带通滤波器（band-passfilter,BPF）把输入音频信号的频带分成若干个连续的频段，每个频段称为子带。对每个子带中的音频信号采用单独的编码方案去编码。在信道上传送时，将每个子带的代码复合起来。在接收端译码时，将每个子带的代码单独译码，然后把他们组合起来，还原成原来的音频信号。研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

2.音频的压缩

2.1音频的压缩编码方法 2.1.2波形编译码子带编码的优点：1.可以对每个子带分别进行控制，例如在进行自适应控制时量化阶的大小可以按照每个子带的能量电平加以调节。2.可根据每个子带信号在感觉上的重要性，对每个子带采用不同的编码方法。研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

2.音频的压缩

2.2电话质量的压缩标准质量采样频率kHz样本精度b声道数据率（未压缩）kbps电话88单声道64AM11．0258单声道88FM22．0516立体声705.6CD44.116立体声1411.2研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

2.音频的压缩

2.3调幅广播质量的音频压缩标准标准速率（Kbps）算法应用G．71164PCM公共网G．72132ADPCM公共网G．72264SB－ADPCMISDN，广播MPEG32－448MPEG多媒体系统研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

2.音频的压缩

2.4MPEG音频编码方法MPEG音频压缩标准为许多音频数据定义了许多算法，都采用了子带压缩并充分利用人听觉的特点。在不用的应用需求中可以使用不同的算法。层次：MPEG音频标准定义了不同的附加规定来为不同的应用节省代价，MPEG音频中附加规定称为层，从1～3，复杂度增加。对于音乐和声音数据，双声道能在第三层以约64Kbps速率很好地编码。对于层次2为每通道128Kbps，层次1为192Kbps。

研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

2.音频的压缩

2.4MPEG音频编码方法研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

2.音频的压缩

2.4MPEG音频编码方法在MPEG－2标准中，对音频编码进行了扩充。MPEG－2在音频方面定义了两种声音数据压缩格式，一种在标准中称为MPEG－2Audio，是以MPEG-1Audio兼容的，又称为MPEG-2BC(backwardcompatible)。另一种称为MPEG－2AAC(AdvancedAudioCoding)，它与MPEG－1声音格式不兼容。

研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.1概述研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.2有损编码方法截断：最简单的压缩方法是通过减少每个象素的位数来减少数据。这种方法称为截断法。例如，32位系统，RGB种的每个分类用8Bits表示，通常情况下都可以将其截断为5：5：5。

颜色查找表：产生颜色表，图像的每个象素点记录一个表的位置号。可以用较少的位数表示图像的颜色。当图像颜色较少是采用这种方法可以得到很好的压缩效果。大面积着色：在亮度/色度分量的形式的图像中，多个像素点共用色度信号。研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.3JPEG——混合压缩JPEG的名称：JointPhotographicCodingExpertsGroup（联合图片专家组

），它是由ISO标准化组织下的小组和CCITT联合成立的，致力于静止图像的压缩研究。其发布的标准称为JPEG标准。JPEG压缩，静态灰度或彩色图像的一种标准压缩算法。是一种混合的压缩算法，在这种压缩算法中，采用了多种有损及无损压缩技术。CCITTGroup3/CCITTGroup4是一种二值图像的压缩方法，而JPEG是一种静止彩色图像和灰度图像的压缩标准。JPEG已经作为ISO标准公布。近年来新的标准：JPEG2000。研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.3JPEG——混合压缩JPEG的无损预测编码算法采用预测器的方法进行编码。选择值预测选择值预测0非预测4a+b-c1a5a+(b-c)/22b6b+(a-c)/23C7(a+b)/2研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.3JPEG——混合压缩JPEG中基于DCT的压缩算法的主要步骤：（1）DCT变换（2）对DCT系数进行量化（3）对量化后的系数进行编码译码或者叫做解压缩的过程与压缩编码过程正好相反。研究生多媒体03多媒体数据压缩b85研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.3JPEG——混合压缩压缩过程：（1）分块：按序分块，将图像分成8*8的子块。JPEG处理的是单独的彩色分量。（2）FDCT变换(正向离散余弦变换，forwarddiscretecosinetransform)：对每一个子块，进行FDCT变换，得到DCT系数矩阵。（3）量化：量化是一种降低精度的过程，因此就减少了存储整数所需的位数。量化的过程：试图确定什么信息可以安全地消去，而没有任何明显的视觉保真度损失。DCT系数矩阵被量化以减少系数的精度，因此提高了压缩率。

研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.3JPEG——混合压缩压缩过程：（4）对量化后的值进行Z扫描：量化后的矩阵，右下角的部分接近0，把这个矩阵中的值重新排列游程，可以使游程中0值的长度增加，以此进一步提高压缩率。JPEG提出用之字形序列的方法为量化后的DCT系数排序。（5）对扫描后的数列进行编码：矩阵（0，0）位置上的系数称为DC系数，矩阵中其他63个系数称为AC系数。DC系数与AC系数分别进行编码。DC系数编码：对相邻图像块之间的DC系数的差值进行编码。AC系数编码：游程长度编码研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.3JPEG——混合压缩压缩过程：（5）对扫描后的数列进行编码：矩阵（0，0）位置上的系数称为DC系数，矩阵中其他63个系数称为AC系数。DC系数与AC系数分别进行编码。DC系数编码：对相邻图像块之间的DC系数的差值进行编码。AC系数编码：游程长度编码（6）熵编码：对编码后的DC系数和AC系数进一步压缩。（7）组成位数据流研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.3JPEG2000简介JPEG2000，正式名称为“ISO15444”，同样是由JPEG组织负责制定。JPEG2000对于以往的JPEG标准有一个很大的飞跃。JPEG2000的原理：JPEG2000与传统JPEG最大的不同，在于它放弃了JPEG所采用的以离散余弦转换(DiscreteCosineTransform)为主的区块编码方式，而采用以小波转换(Wavelettransform)为主的多解析编码方式。研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.3JPEG2000简介JPEG2000能实现LoselessCompression（无损压缩）。在实际应用中，有一些重要的图像，如卫星遥感图像、医学图像、文物照片等，通常需要进行无损压缩。对图像进行无损编码的经典方法——预测法已经发展成熟，并且作为一个标准写入了JPEG2000中。研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.3JPEG2000简介JPEG2000能实现ProgressiveTransmission（渐进传输）。这是JPEG2000的一个极其重要的特征。它先传输图像的轮廓，然后逐步传输数据，不断提高图像质量，以满足用户的需要。这在网络传输中有着重大的意义。研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.3JPEG2000简介JPEG2000另一个极其重要的优点：ROI（RegionofInterest，即感兴趣区域）。你可以指定感兴趣区域，在这些区域，你可以在压缩时指定特定的压缩质量，或在恢复时指定特定的解压缩要求。JPEG2000还考虑了人的视觉特性，增加了视觉权重和掩膜。这样在不损害视觉效果的情况下，大大提高了效率。研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.4视听通信编解码标准H.26XITU:ISO/IEC:H.261H.262H.263H.263+H.264MPEG1MPEG2MPEG4(Part2)MPEG7MPEG21MPEG4(Part10)研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.4视听通信编解码标准H.26XH.261p×64kb/s视频编码标准

时间1990年12月输入176×144(QCIF)352×288(CIF)帧速率可变<=30输出p×64kb/s(p=1,2,…,32)压缩率20~30小于MPEG1压缩算法运动补偿帧间预测与分块DCT相结合的混合编码应用可视电话、视频会议等对称应用研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.4视听通信编解码标准H.26XMPEG1数据传输速率为1.5Mb/s的数字存储媒体运动图像及其伴音编码标准时间1992年输入视频：352×240×30，352×288×25音频：32、44.1、48kHz的线性PCM输出1.5Mb/s、32-384Kb/s(音频)压缩率20~30压缩算法运动补偿帧间预测（单向预测＋双向预测）＋DCT应用VCD、MP3、局域网视频传输研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.4视听通信编解码标准H.26XMPEG2H.262运动图像及其伴音通用编码标准(ITU与MPEG联合发布)

时间1993年11月输入352×288～1920×1152采用频率为16、22.05、24、32、44.1、48kHz的线性PCM、支持5.1声道

输出1.5－80Mb/s、8-640Kb/s(音频)压缩率30－40压缩算法运动补偿帧间预测（单双向预测）＋DCT、可伸缩性、前向兼容应用DVD、DVB、HDTV研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.4视听通信编解码标准H.26XH.263H.263+甚低码率通信的视频编码标准时间1996年3月、1998年1月输入QCIF、CIF、128×96(SubQCIF)、704×576(4CIF)、1408×1152(16CIF)输出30kb/s～压缩率H.263+>H.263>MPEG2压缩算法运动补偿帧间预测（单双向预测）＋DCT局部算法改进可伸缩性应用通用电话交换网、局域网的视频通信研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.4视听通信编解码标准H.26XMPEG4(Part2)MPEG4Visual甚低码率活动图像及其伴音编码标准时间1999年输入≧176×144的多种分辨率格式输出4.6Kb/s～64Kb/s压缩率≧100压缩算法基于对象的新一代编码技术，注重交互性，即可包含自然对象，又可包含人工合成对象应用可应用范围很广、目前多用于因特网视频传输、流媒体应用研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.4视听通信编解码标准H.26XH.264MPEG4(Part10)MPEG4AVC时间2003年5月输入多种分辨率格式输出压缩率压缩率最高的视频压缩标准，比MPEG4Visual节约50％的码率压缩算法基于传统框架的混合编码系统，只是做了局部优化。更注重编码效率和可靠性应用视频广播、视频通信和存储媒体（CDDVD）等多种应用研究生多媒体03多媒体数据压缩b第三章多媒体数据压缩

3.视觉类媒体压缩

3.4视听通信编解码标准H.26XH.261标准是视频图像压缩编码国际标准。用于传输率在p×64Kbpsp×64kbps（p＝1～30）的视听服务的视频编码器。主要用于视频电话和电视会议。数字视频