多媒体信息的数据压缩

1.5多媒体数据压缩技术1.5.1多媒体数据的冗余类型1.5.2数据压缩方法1.5.3视频编码的国际标准1.5.1多媒体数据的冗余类型图像数据表示中存在着大量的冗余，图像数据压缩技术就是利用图像数据的冗余性来减少图像数据量的方法。常见图像数据冗余类型如下：1.空间冗余2.时间冗余3.视觉冗余空间冗余一幅图像表面上各采样点的颜色之间往往存在着空间连贯性，基于离散像素采样来表示物体表面颜色的像素存储方式可利用空间连贯性，达到减少数据量的目的。例如，在静态图像中有一块表面颜色均匀的区域，在此区域中所有点的光强和色彩以及饱和度都是相同的，因此数据有很大的空间冗余。时间冗余运动图像一般为位于一时间轴区间的一组连续画面，其中的相邻帧往往包含相同的背景和移动物体，只不过移动物体所在的空间位置略有不同，所以后一帧的数据与前一帧的数据有许多共同的地方，这种共同性是由于相邻帧记录了相邻时刻的同一场景画面，所以称为时间冗余。同理，语音数据中也存在着时间冗余。视觉冗余人类的视觉系统对图像场的敏感度是非均匀的。但是，在记录原始的图像数据时，通常假定视觉系统近似线性的和均匀的，对视觉敏感和不敏感的部分同等对待，从而产生比理想编码（即把视觉敏感和不敏感的部分区分开来的编码）更多的数据，这就是视觉冗余。数字压缩技术三个重要指标1、信息存储量之比大2、压缩的算法简单3、恢复效果好1.5.2数据压缩方法压缩处理一般是由两个过程组成：一是编码过程，即将原始数据经过编码进行压缩，以便存储与传输；二是解码过程，此过程对编码数据进行解码，还原为可以使用的数据。数据压缩可分为两种类型：一种叫做无损压缩，另一种叫做有损压缩。无损压缩混合压缩有损压缩什么是熵数据压缩不仅起源于40年代由ClaudeShannon首创的信息论，而且其基本原理即信息究竟能被压缩到多小，至今依然遵循信息论中的一条定理，这条定理借用了热力学中的名词“熵”(Entropy)来表示一条信息中真正需要编码的信息量：考虑用0和1组成的二进制数码为含有n个符号的某条信息编码，假设符号Fn在整条信息中重复出现的概率为Pn，则该符号的熵也即表示该符号所需的位数位为：En=-log2(Pn)整条信息的熵也即表示整条信息所需的位数为：E=∑En举个例子，对下面这条只出现了abc三个字符的字符串：aabbaccbaa字符串长度为10，字符abc分别出现了532次，则abc在信息中出现的概率分别为0.50.30.2，他们的熵分别为：Ea=-log2(0.5)=1Eb=-log2(0.3)=1.737Ec=-log2(0.2)=2.322整条信息的熵也即表达整个字符串需要的位数为：E=Ea*5+Eb*3+Ec*2=14.855位回想一下如果用计算机中常用的ASCII编码，表示上面的字符串我们需要整整80位呢！现在知道信息为什么能被压缩而不丢失原有的信息内容了吧。简单地讲，用较少的位数表示较频繁出现的符号，这就是数据压缩的基本准则。模型从上面的描述，我们明白，要压缩一条信息，首先要分析清楚信息中每个符号出现的概率。不同的压缩程序通过不同的方法确定符号的出现概率，对符号的概率计算得越准确，也就越容易得到好的压缩效果。在压缩程序中，用来处理输入信息，计算符号的概率并决定输出哪个或哪些代码的模块叫做模型。难道对信息中字符的出现概率这么难以估计以至于有各种不同的压缩模型吗？对上面的字符串我们不是很容易就知道每个字符的概率了吗？不过上面的字符串仅有10个字符长呀，那只是例子而已。考虑我们现实中要压缩的文件，大多数可是有几十K甚至几百K长，几M字节的文件不是也屡见不鲜吗？是的，我们可以预先扫描文件中的所有字符，统计出每个字符出现的概率，这种方法在压缩术语里叫做“静态统计模型”。但是，不同的文件中，字符有不同的分布概率，我们要么先花上大量的时间统计我们要压缩的所有文件中的字符概率，要么为每一个单独的文件保存一份概率表以备解压缩时需要。糟糕的是，不但扫描文件要消耗大量时间，而且保存一份概率表也使压缩后的文件增大了不少。所以，在实际应用中，“静态统计模型”应用的很少。真正的压缩程序中使用的大多是一种叫“自适应模型”的东西。自适应模型可以说是一台具有学习功能的自动机。他在信息被输入之前对信息内容一无所知并假定每个字符的出现概率均等，随着字符不断被输入和编码，他统计并纪录已经出现过的字符的概率并将这些概率应用于对后续字符的编码。也就是说，自适应模型在压缩开始时压缩效果并不理想，但随着压缩的进行，他会越来越接近字符概率的准确值，并达到理想的压缩效果。自适应模型还可以适应输入信息中字符分布的突然变化，可以适应不同的文件中的字符分布而不需要保存概率表。编码通过模型，我们已经确定了对某一个符号该用多少位二进制数进行编码。现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。最先被考虑的问题是，如果对a用3个二进制位就可以表示，而对b用4个二进制位就可以表示，那么，在解码时，面对一连串的二进制流，我怎么知道哪三个位是a，哪四个位是b呢？所以，必须设计出一种编码方式，使得解码程序可以方便地分离每个字符的编码部分。于是有了一种叫“前缀编码”的技术。该技术的主导思想是，任何一个字符的编码，都不是另一个字符编码的前缀。反过来说就是，任何一个字符的编码，都不是由另一个字符的编码加上若干位0或1组成。看一下前缀编码的一个最简单的例子符号编码A0B10C110D1110E11110有了上面的码表，你一定可以轻松地从下面这串二进制流中分辨出真正的信息内容了：1110010101110110111100010-DABBDCEAAB无损压缩无损压缩常用在原始数据的存档，如文本数据、程序以及珍贵的图片和图像等。其原理是统计压缩数据中的冗余(重复的数据)部分。常用的有：RLE(runlengthencoding)行程编码Huffman编码算术编码LZW(lempel-ziv-welch)编码Shannon-Fano编码讨论之前，我们假定要编码字符的出现概率已经由某一模型统计出来，例如，对下面这串出现了五种字符的信息(40个字符长):cabcedeacacdeddaaabaababaaabbacdebaceada五种字符的出现次数分别：a-16，b-7，c-6，d-6，e-5。Shannon-Fano编码的核心仍然是构造二叉树，构造的方式非常简单：Shannon-Fano编码进入Huffman先生构造的神奇二叉树之前，我们先来看一下它的前身，由ClaudeShannon和R.M.Fano两人提出的Shannon-Fano编码。讨论之前，我们假定要编码字符的出现概率已经由某一模型统计出来，例如，对下面这串出现了五种字符的信息(40个字符长):cabcedeacacdeddaaabaababaaabbacdebaceada五种字符的出现次数分别：a-16，b-7，c-6，d-6，e-5。Shannon-Fano编码的核心仍然是构造二叉树，构造的方式非常简单：1)将给定符号按照其频率从大到小排序。对上面的例子，应该得到：a-16b-7c-6d-6e-52)将序列分成上下两部分，使得上部频率总和尽可能接近下部频率总和。我们有：a-16b-7-----------------c-6d-6e-53)我们把第二步中划分出的上部作为二叉树的左子树，记0，下部作为二叉树的右子树，记1。4)分别对左右子树重复23两步，直到所有的符号都成为二叉树的树叶为止。现在我们有如下的二叉树：根(root)0|1+------+------+0|10|1+-----+-----++---+----+||||abc|0|1+-----+-----+||de于是我们得到了此信息的编码表：a-00b-01c-10d-110e-111可以将例子中的信息编码为：cabcedeacacdeddaaabaababaaabbacdebaceada1000011011111011100100010......码长共91位。考虑用ASCII码表示上述信息需要8*40=240位，我们确实实现了数据压缩Huffman编码Huffman编码构造二叉树的方法和Shannon-Fano正好相反，不是自上而下，而是从树叶到树根生成二叉树。现在，我们仍然使用上面的例子来学习Huffman编码方法。1)将各个符号及其出现频率分别作为不同的小二叉树（目前每棵树只有根节点）。a(16)b(7)c(6)d(6)e(5)2)在1中得到的树林里找出频率值最小的两棵树，将他们分别作为左、右子树连成一棵大一些的二叉树，该二叉树的频率值为两棵子树频率值之和。对上面的例子，我们得到一个新的树林：|(11)a(16)b(7)c(6)+---+---+||de3)对上面得到的树林重复2的做法，直到所有符号都连入树中为止。这一步完成后，我们有这样的二叉树：根(root)0|1+------+----------------+|0|1|+---------+-----------+|0|10|1a+-------+------++-------+-------+||||bcde由此，我们可以建立和Shannon-Fano编码略微不同的编码表：a-0b-100c-101d-110e-111对例子中信息的编码为：cabcedeacacdeddaaabaababaaabbacdebaceada101010010111111011101010101......码长共88位。这比使用Shannon-Fano编码要更短一点。让我们回顾一下熵的知识，使用我们在第二章学到的计算方法，上面的例子中，每个字符的熵为：Ea=-log2(16/40)=1.322Eb=-log2(7/40)=2.515Ec=-log2(6/40)=2.737Ed=-log2(6/40)=2.737Ee=-log2(5/40)=3.000信息的熵为：也就是说，表示该条信息最少需要86.601位。我们看到，Shannon-Fano编码和Huffman编码都已经比较接近该信息的熵值了。(1)、行程编码（RLE）RLE编码是将数据流中连续出现的字符用单一记号表示。例如,字符串AAABCDDDDDDDDBBBBB可以压缩为3ABC8D5B。RLE编码简单直观，编码/解码速度快，因此许多图形和视频文件，如.BMP.TIFF及AVI等格式文件的压缩均采用此方法.(3)、算术编码其方法是将被编码的信源消息表示成实数轴0-1之间的一个间隔，消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位数就越多。该方法实现较为复杂，常与其它有损压缩结合使用，并在图像数据压缩标准(如JPEG)中扮演重要角色。(4)、LZW编码LZW(Lempel-Ziv-Welch)压缩使用字典库查找方案。它读入待压缩的数据并与一个字典库(库开始是空的)中的字符串对比，如有匹配的字符串，则输出该字符串数据在字典库中的位置索引，否则将该字符串插入字典中。许多商品压缩软件如ARJ、PKZIR、ZOO、LHA等都采用了设方法。另外，.GIF和.TIF格式的图形文件也是按这一文件存储的。有损压缩图像或声音的频带宽、信息丰富，人类视觉和听觉器官对频带中某些频率成分不大敏感，有损压缩以牺牲这部分信息为代价，换取了较高的压缩比。常用的有损压缩方法有：PCM(脉冲编码调制)、预测编码、变换编码、插值与外推等。新一代的数据压缩方法有：矢量量化和子带编码、基于模型的压缩、分形压缩及小波变换等。预测编码：根据某一数据模型利用以往的样本值对新样本值进行预测，然后将样本实际值与预测值的差值进行编码。如果模型足够好，且样本序列的时间相关性较强，那么误差信号的幅度将远小于原始信号，可以用较少的值对其差值量化，得到较好的压缩效果。预测编码常用的是差分脉冲编码调制（DPCM）和自适应的差分脉冲编码调制（ADPCM）。分形编码：分形的方法是把一幅数字图像，通过一些图像处理技术，如颜色分割，边缘检测、频谱分析、统理变化分析等原始图像分成一些子图像。