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

第三章多媒体数据压缩1.数据压缩的基本原理和方法2.音频的压缩3.视觉类媒体压缩第三章多媒体数据压缩1.数据压缩的基本原理和方法1.1数据压缩技术的性能指标评价数据压缩技术的3个关键指标：压缩比：输入、输出数据量之比。质量：无损和有损。无损没有信息的损失，所以质量不是衡量的标准。有损：通过损失一些细节的、对人的感观来说不重要的信息提高压缩比，分为主观评价和客观评价。客观评价：方差、新噪比等。压缩和解压缩的速度：实时的采集系统中，压缩速度很重要。否则会丢失信息。而存储回放中，结压缩的速度显得比压缩的速度重要，因为解压缩面对大多数用户的实时需求。第三章多媒体数据压缩1.数据压缩的基本原理和方法1.2数据冗余的类型与压缩方法分类需要压缩的原因是因为信息数据存在着冗余。冗余，数据量和信息量不成正比。空间冗余：例如，相邻象素(水平和垂直方向)有同样的值。时间冗余：时间相关媒体，帧与帧相同。编码冗余：同样长度的编码可以表示不同的信息。如黑白图像若每个象素点用8位表示；结构冗余：对称的结构如果都加以记录的话就出现结构冗余。另外，很多成分相对于人的感觉来说重要性不一样。因此，压缩方法就是充分利用这些冗余和特性。第三章多媒体数据压缩1.数据压缩的基本原理和方法1.2数据冗余的类型与压缩方法分类数据压缩方法的分类根据解码后数据与原始数据是否完全一致进行分类，压缩方法可被分为两大类：有损压缩：减少信息量，损失的信息不能再恢复无损压缩：可100％还原第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理信源：S＝{S1,……，Sn}熵的概念：熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，相应的，这个信息出现的概率小。某个事件的信息量，用Ii＝－log2Pi表示。其中，Pi表示第i个事件的概率。1.3.1基本概念第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理信源S的熵定义为：i2n1ii1/PlogPH(S)1.3.1基本概念第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理编码：一个信源符号集转换为另一个符号集信源符号的集合：S＝{S1,……，Sn}概率：P1，……,Pn码符号集合：码字中的元素，二进制编码则为X＝｛０，１｝。码字的集合：W＝{W1,……，Wn}编码长度：L1,……，Ln，可分为变长码及定长码1.3.1基本概念第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理唯一可译码：任意有限长，不需分隔符的码符号序列，能唯一译码非前缀码：W中任意码字Wi都不是其余码字的前缀。非前缀码一定是唯一可译码例：编码方法A：具有唯一可译码性编码方法C：非前缀码编码方法D：具有可唯一译码性，但不符合非前缀码的条件。1.3.1基本概念第三章多媒体数据压缩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第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理给定信源符号集合S及码符号集X，可以构造多个唯一可译码。多个编码的比较标准：平均编码长度低。如果我们用lj表示信源符号aj的二进制编码长度，根据它的统计信息，平均编码长度：MjjjlPl11.3.1基本概念结论：对二进制编码方式（即码符号的取值只有0，1两种情况）平均编码长度满足码字的平均长度不能小于信源熵。若采用非等长编码：能找到一种编码，平均长度为信源熵＋1第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理LSH)(1.3.1基本概念第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理包括行程编码、LZW编码、huffman编码等。1.3.2统计编码（熵编码）第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理行程编码：检测重复的比特或者字符序列，并用（字符，重复次数）来表示。考虑的问题：字符的值重复次数，二者之间是否使用分隔符，重复的次数如何编码（使用变长码还是定长码）等1.3.2统计编码第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理Huffman编码：于1952年提出的对统计独立信源能达到最小平均码长的编码方法。Huffman编码的过程：构造一棵编码树。构造方法：首先找出两个具有最小概率的节点，构造一个二叉树，以这两个节点为这棵树的叶子节点，根节点看作为新的节点，它的概率为两个叶子节点概率之和；此跟节点与未处理的节点形成新的节点集合，重复上面的过程，直到节点集合中只剩一个节点为止。1.3.2统计编码第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理Huffman编码当信源符号概率是2的负幂次方时，编码效率达到100%缺点：(1)Huffman编码方法没有错误保护的功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。如果出现错误，哪怕仅仅是一位的错误，不但这个码本身会发生错误，并且会导致其他代码出错，这种现象称为错误传播（errorpropagation）。计算机也无法去发现错误纠正错误。(2)Huffman码是变长度码，且没有额外同步码，因此很难随意查找或调用压缩文件中间的内容，然后再译码。1.3.2统计编码传真标准中的编码（3类传真标准及4类传真标准CCITTGroup31D/2D）：扫描、尺寸和传输：扫描：每行1728个象素。标准扫描行宽215mm，垂直方向3.85行/mm,或7.7行/mm.尺寸：A4幅面传输：用于传输每行扫描编码后形成的数据位、填充位、行结束符号的时间总和，最大20ms第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理1.3.2统计编码传真标准中的编码（3类传真标准CCITTGroup31D及4类传真标准）：3类编码方法采用一维编码，扫描时统计游程，并将游程分为白游程及黑游程，白游程和黑游程再采用Huffman编码。假设每行的第一个行程是白色的（如果不是，则发出一个长度为0的白色游程码），每行的结尾发出一个EOL信号码。第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理1.3.2统计编码3类传真标准CCITTGroup31D码表中的游程，0~64，称为终止码。终止码用于表示小于64个像素的游程。64，128，192，256，320……，1728，64的倍数，称为编排码，编排码用于表示是64个像素倍数的游程。第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理1.3.2统计编码第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理1.3.2统计编码白色游程码字黑色游程码字00011010100000110111100011110102011121131000310……630011010063……EOL000000000001终止码第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理1.3.2统计编码白色游程码字黑色游程码字641101164……12810010128……192010111192……2560110111256………………17280100110111728……编排码3类传真标准CCITTGroup31D例如，1347（1344+3）个白像素的游程编码用以下两种代码进行编码：1344（64×21）个白像素的编排码——0110110103个白像素的终止码——1000那么，1347个白像素的压缩位流是0110110101000第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理1.3.2统计编码4类传真标准CCITTGroup32D将扫描线每K条放在一起进行处理。每组K条线中的第一条用CCITTGroup31D方法编码，这条线就成为下一条线的参考线，然后使用二维方法和一维方法为这组K条线中的其余扫描线编码。原因：横跨相邻两条扫描线的图像数据可能是冗余的。如果在一指定线上出现了黑白过渡，那么有可能在下一扫描线上加或减三个像素之间的位置上也出现相同的过渡。第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理1.3.2统计编码4类传真标准CCITTGroup32D编码方法：每个K组的第一条线采用Group31D方式编码，以作为这组K条线中其余线的扫描线。2D方法使用了一些附加码的组合为这组K条线中的每一条编码。附加码有3种：垂直码，越过码，水平码。第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理1.3.2统计编码4类传真标准CCITTGroup32D越过码固定取值：0001水平码也固定取值：001垂直码有7类，它的值由参考线中变化像素的位置与编码线重变化像素的位置之间的差距决定。第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理1.3.2统计编码位置差异垂直码300000102000010101001－1011－2000011－300000114类传真标准CCITTGroup32D二维编码：一种循环算法，依靠a0,a1,a2,b1,b2五个参数的更新来循环。如下例所示。a0表示准备编码的行程起始位置的像素点，a1为当前行下一个行程起始位置的像素点，a2表示再下一个行程起始位置的象素点。b1为参考行上位于a0位置右边行程起始位置的像素点，其颜色与a1一致，b2为参考行a0之后下一个行程起始位置的象素点。第三章多媒体数据压缩1.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理1.3.2统计编码4类传真标准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统计编码第三章多媒体数据压缩a0a1a2b1b2越过码：0001a1a2b1b2a0垂直码：000010a1a2b1b2a0水平码：001＋4个黑色像素＋6个白色像素a1b1a0垂直码：11.数据压缩的基本原理和方法1.3常用数据压缩方法的基本原理1.3.2统计编码位置差异垂直码300000102000010101001－1011－2000011－30000011算术编码算术编码在图像的压缩中被广泛的使用。在算术编码中，消息用0到1之间的实数进行编码。算术编码用到两个基本的参数：信源符号出现的概率和编码的间隔。例：{A,B,C,D}概率分别为：{0.1,0.4,0.2,0.3}第三章多媒体数据压缩1.数据压缩的基本原理和