04数据压缩基础课件.ppt

1、数据压缩基础. . .数据压缩编码技术概述多媒体数据压缩的必要性和可行性衡量多媒体数据压缩技术的指标：压缩比算法简单，压缩解压缩速度快尽可能地恢复原始数据压缩方法分类无损压缩：Huffman编码、游程编码、算术编码、LZW编码有损压缩：预测编码、变换编码、模型编码、基于重要性的编码、混合编码新一代的数据压缩方法：矢量量化和子代编码、基于模型的压缩、分形压缩、小波变换压缩等等。. . .压缩的必要性音频、视频的数据量很大，如果不进行处理，计算机系统几乎无法对它进行存取和交换。例如，一幅具有中等分辨率（640480）的真彩色图像（24b/像素），它的数据量约为7.37Mb/帧，一个700MB（By

2、te）的硬盘只能存放约100帧图像。若要达到每秒25帧的全动态显示要求，每秒所需的数据量为184Mb，而且要求系统的数据传输率必须达到184Mb/s。对于声音也是如此，若采用16b样值的PCM编码，采样速率选为44.1kHZ，则双声道立体声声音每秒将有176KB的数据量。. . .数据压缩的好处时间域压缩迅速传输媒体信源频率域压缩并行开通更多业务空间域压缩降低存储费用能量域压缩降低发射功率. . .数据压缩技术实现的衡量标准 压缩比要大恢复后的失真小压缩算法要简单、速度快压缩能否用硬件实现. . .多媒体数据压缩技术分类平均信息量编码可逆压缩去冗余 统计特性源编码不可逆压缩有失真编码特征提取等

3、两种压缩技术不互斥，两种压缩技术的结合，可以达到最高可能的压缩率。. . .多媒体数据压缩技术分类无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不会使人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。. . .无损数据压缩主要介绍目前用得最多和技术最成熟的无损压缩编码技术，包括：霍夫曼编码算术编码游程编码RLE词典编码LZW. . .霍夫曼(Huffman)编码霍夫曼(Huffma

4、n)在1952年提出了另一种编码方法，即从下到上的编码方法。几个个问题值得注意：1.霍夫曼码没有错误保护功能；2.霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码;3.接收端需保存一个与发送端相同的霍夫曼码表。. . .字母频率编码A25%01B15%110C10%111D20%10E30%00霍夫曼(Huffman)编码. . .信源消减 信源符号集 B = b1 , b2 , b3 , b4 概率矢量 u = 0.1，0.38，0.22，0.3 步骤1：信源消减. . .步骤2：对信源符号赋值平均码长 L avg=1.946. . .霍夫曼码的特点 1，块码（组码

5、） 2，即时码 3，唯一可解码. . .霍夫曼码改型 亚最优 牺牲编码效率来换取编码速度截断霍夫曼码 前M个符号用霍夫曼编码 其余用前缀码+定长码（自然码）平移霍夫曼码 分组：相同符号数 用霍夫曼编码编第1组 其余组用平移符号+第一组霍夫曼码. . .霍夫曼码改型 . . .霍夫曼(Huffman)编码依赖于信源的统计特性，必须先统计得到信源的概率特性才能编码，这就限制了实际的应用。缺乏构造性，即它不能用某种数学方法建立起消息和码字之间的一一对应关系，而只能通过某种查表的方法建立起它们的对应关系。如果消息数目很多，那么所需存储的码表也很大，这将影响系统的存储量及编、译码速度。. . .练习初始

6、信源：a1：0.1，a2：0.4，a3:：0.06，a4: 0.1，a5： 0.04，a6： 0.3. . .练习. . .算术编码 只需要用到加法和位移运算 从整个符号序列出发算术编码不再是块码，采用递推形式连续编码 . . .算术编码的特点： 1种从整个符号序列出发，采用递推形式连续编码的方法 不存在源符号和码字间的一一对应关系 1个算术码字要赋给整个信源符号序列，而每个码字本身确定了0和1之间的1个实数区间 算术编码过程只需用到加法和移位运算 . . .算术编码 b1=0.1b2=0.38b3=0.22b4=0.30.0000100120.0351562510码串： b1； b2； b3

7、； b4. . .算术编码在算术编码中需要注意的几个问题：1. 由于实际计算机精度不可能无限长，运算中溢出是明显的问题，但多数机器都有16位、32位或者64位的精度，因此可使用比例缩放法解决。2. 算术编码器对消息只产生一个码字，这个码字是在0, 1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。3. 算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。. . .算数编码练习初始信源：a1：0.1，a2：0.4，a3：0.5，码串：a1，a1，a2，a3. . .游程RLE编码RLE(run length encoding）编码的概念用RLE

8、编码方法得到的代码为：8 803 31505084 418 80。代码中用黑体表示的数字是行程长度，黑体字后面的数字代表象素的颜色值。例如黑体字50代表有连续50个象素具有相同的颜色值，它的颜色值是8。译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。00000000 111 888 888 1111 00000000 8个0 3个1 50个8 4个1 8个0. . .词典编码词典编码的思想第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。. . .词典

9、编码词典编码的思想第二类算法的想法是企图从输入的数据中创建一个“短语词典(dictionary of thephrases)”，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。. . .词典编码J.Ziv和A.Lempel在1978年首次发表了介绍上述第二类编码方法的文章。在他们的研究基础上，Terry A.Welch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW(Lempel-Ziv Walch)压缩编码，LZW算法在编码原理上，LZW与LZ78相比有如下差别：LZW只输出代表词

10、典中的缀-符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)。由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-character prefix)，因此在词典中搜索的第1个缀-符串有两个字符。LZW编码是围绕称为词典的转换表来完成的。. . .词典编码LZW算法LZW编码器使用了一种很实用的分析(parsing)算法，称为贪婪分析算法(greedy parsing algorithm)。在贪婪分析算法中，每一次分析都要串行地检查来自字符流(Charstream

11、)的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀(Prefix)。用已知的前缀(Prefix)加上下一个输入字符C也就是当前字符(Current character)作为该前缀的扩展字符，形成新的扩展字符串缀-符串(String)：Prefix.C。这个新的缀-符串(String)是否要加到词典中，还要看词典中是否存有和它相同的缀-符串String。如果有，那么这个缀-符串(String)就变成前缀(Prefix)，继续输入新的字符，否则就把这个缀-符串(String)写到词典中生成一个新的前缀(Prefix)，并给一个代码。. . .词典编码LZW算法LZW算

12、法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司Unisys(优利系统公司)，除了商业软件生产公司之外，可以免费使用LZW算法。. . .词典编码压缩算法基于以下的中心思想1.为原始文本文件中的每个字母分配一个代码并存储到一个代码表中2.设置一个循环，每次从文件中获取一个字符。将使用一个缓冲字符串，把从文件中取出的字符连接在一起3.在每

13、次循环中，读取一个字符接到缓冲字符串的后面，形成一个新的临时字符串。如果该临时字符串以前曾经出现过就把它移到缓冲区里4.如果临时字符串不出现在代码表中，就为它分配一个代码，并把字符串和代码存储到代码表中，同时发送缓冲字符串所对应的代码重新设置缓冲字符串为刚刚读取的单个字符。. . .JPEG算法概要JPEG(Joint Photographic Experts Group) 是一个由 ISO和IEC两个组织机构联合组成的一个专家组，负责制定静态的数字图像数据压缩编码标准，这个专家组开发的算法称为JPEG算法，并且成为国际上通用的标准，因此又称为JPEG标准。JPEG是一个适用范围很广的静态图像

14、数据压缩标准，既可用于灰度图像又可用于彩色图像。使用有损压缩算法时，在压缩比为25:1的情况下，压缩后还原得到的图像与原始图像相比较，非图像专家难于找出它们之间的区别，因此得到了广泛的应用。V-CD、DVD-Video。图像和视频的压缩技术. . .图像和视频的压缩技术JPEG压缩的三个阶段离散余弦变换（Discrete Cosine Transform, DCT）量化（Quantization）编码阶段（Encoding Phase）. . .1. 离散余弦变换下面对正向离散余弦变换(FDCT)变换作几点说明。(1) 对每个单独的彩色图像分量，把整个分量图像分成88的图像块，并作为两维离散余

15、弦变换DCT的输入。通过DCT变换，把能量集中在少数几个系数上。. . .离散余弦变换阶段 707016) 12( cos 16) 12( cos),( )()(),(TxyjyixyxPjcicjiP(x, y)经DCT变换之后，T(0，0)是直流系数，其他为交流系数。在计算两维的DCT变换时，可把两维的DCT变换变成一维的DCT变换. . .图像和视频的压缩技术2.量化阶段量化是对经过FDCT变换后的频率系数进行量化。量化的目的是减小非“0”系数的幅度以及增加“0”值系数的数目。量化是图像质量下降的最主要原因Q=integer(T/U)其中：其中：DCTDCT变换系数变换系数T T ； U

16、 U是量化器步长，它是量化表的元素。是量化器步长，它是量化表的元素。. . .图像和视频的压缩技术量化器步长152 0 -48 0 -8 0 -7 01 3 5 7 9 11 13 15T=0 00 0 0 0 0 03 5 7 9 11 13 15 17-48 0 38 0 -3 0 2 05 7 9 11 13 15 17 19U=0 0 0 0 0 0 0 0-8 0 -3 0 13 0 -1 00 0 0 00 0 0 0-70 2 0 -1 0 7 00 0 0 00 0 0 07 9 11 13 15 17 19 219 11 13 15 17 19 21 2311 13 15 1

17、7 19 21 23 2513 15 17 19 21 23 25 2715 17 19 21 23 25 27 29. . .Q=图像和视频的压缩技术根据公式，量化后将得到152 0 -10 0 -1 0 -1 00 0 0 0 0 0 0 0-10 04 0 0 0 0 00 0-1 00 0-1 00 00 0 0 0 0 00 0 1 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0. . . 对于有损压缩算法，JPEG算法使用均匀量化器进行量化，量化步长是按照系数所在的位置和每种颜色分量的色调值来确定。 因为人眼对亮度信号比对色差信号更敏感，因此使用了两种

18、量化表：亮度量化表和色差量化表。. . .3.Z字形编码阶段。 量化后的系数要重新编排，目的是为了增加连续的“0”系数的个数，就是“0”的游程长度，方法是按照Z字形的式样编排。这样就把一个88的矩阵变成一个1 64的矢量。编码阶段1520-100-10-1000000000-10000000000000000-1000000000000000-1000000000000000. . .4.直流系数的编码阶段88图像块经过DCT变换之后得到的直流系数有两个特点：一是系数的数值比较大，二是相邻88图像块的直流系数值变化不大。 根据这个特点，JPEG算法使用了差分脉冲编码调制(DPCM)技术，对相邻

19、图像块之间的直流系数的差值(Delta)进行编码， DeltaDC(0, 0)k - DC(0, 0)k-1 . . .5. 交流系数的编码阶段量化交流系数的特点是164矢量中包含有许多“0”系数，并且许多“0”是连续的，因此使用非常简单和直观的游程长度编码(RLE)对它们进行编码。JPEG使用了1个字节的高4位来表示连续“0”的个数，而使用它的低4位来表示编码下一个非“0”系数所需要的位数，跟在它后面的是量化交流系数的数值。. . .6. 熵编码阶段使用熵编码还可以对DPCM编码后的直流系数和RLE编码后的交流A系数作进一步的压缩。在JPEG有损压缩算法中，使用霍夫曼编码器来减少熵。使用霍夫

20、曼编码器的理由是可以使用很简单的查表方法进行编码。压缩数据符号时，霍夫曼编码器对出现频度比较高的符号分配比较短的代码，而对出现频度较低的符号分配比较长的代码。这种可变长度的霍夫曼码表可以事先进行定义。. . . MPEG标准是面向运动图像压缩的一个系列标准。 多媒体运动图像和伴音的数据压缩编码标准，即MPEG标准，实际上包括四个部分，MPEG视频、MPEG音频和MPEG系统、 MPEG测试。 . . . MPEG标准简介 最初MPEG专家组的工作项目是3个，即在1.5Mbps， 10Mbps，40Mbps传输速率下对图像编码， 分别命名为MPEG-1，MPEG-2， MPEG-3。MPEG-3

21、后被取消. 为了满足不同的应用要求， MPEG又将陆续增加其他一些标准MPEG-4，MPEG-7，MPEG-21。 . . . MPEG算法编码过程和解码过程是一种非镜象对称算法(不对称)， 解码过程要比编码过程相对简单些。 MPEG-1和MPEG-2只规定了解码的方案， 重点将解码算法标准化。 最近几年，随着MPC性能的提高，软件解压功能也逐渐得到支持。. . .在MPEG中将图像分为3种类型： I图像：也叫I帧，就是静态图像，用JPEG帧内压缩的方法得到； P图像 用最近的前一个I图像(或P图像)预测编码得到(前向预测)，称为前向预测；而且可以作为下一个B帧或P帧的照图像 。 B图像 B图

22、像在预测时， 既可使用了前一个图像作参照， 也可使用下一个图像做参照或同时使用前后两个图像作为参照图像(双向预测)。 B图像压缩比最大，I图像压缩比最小。帧间编码技术 . . .运动视频流的组成 1、允许编码端自行选择I帧的使用频率和在视频流的位置，典型每秒使用2次。 2、允许编码端自行选择任何两帧参考图像（I，P）之间的B帧。插入两个B帧较为适宜。. . .运动图像的显示顺序与传输顺序不同 显示的顺序：显示的顺序：1 2 3 4 5 6 7 I B B P B B P 传输的顺序：传输的顺序：1 4 2 3 7 5 6 I P B B P B B MPEG编码器需对上述图像重新排序， 以便解

23、码器高效工作， 因为参照图像必须先于B图像恢复之前恢复。. . .压缩技术比较. . .音频压缩编码标准及应用范围G.711 1972年CCITT为电话质量和语音压缩制定。其速率为64kb/s，使用非线性量化技术，主要用于公共电话网中。G.722 1988年CCITT为调幅广播质量的音频信号压缩制定，它使用子带编码(SBC)方案，其滤波器组将输入信号分成高低两个子带信号，然后分别使用ADPCM进行编码。G.722能将224kb/s的调幅广播质量的音频信号压缩为64kb/s，主要用于视听多媒体和会议电视等。G.723 1996年ITU-T通过了“用于多媒体传输的5.3kb/s或6.3kb/s双速

24、率话音编码”标准。它采用多脉冲激励最大似然量化(MP-MLQ)算法，此标准可应用于视频电话及IP传输电话等方面。G.728使用基于低时延码本激励线性预测编码(LD-CELP)算法，其速率为16kb/s，主要用于公共电话网中。G.729 它使用8kb/s的共轭结构代数码激励线性预测(CS-ACELP)算法，此标准在无线移动网、数字多路复用系统和计算机通信系统中应用。. . .运动视频定量要求技术或标准 未压缩的 Mbps 压缩的 Mbps质量HDTV1920Xl08060 fps未压缩的压缩的演插室质量数字电视演插室质量数字电视未压缩的压缩的常规广播质量电视常规广播质量电视VCR 品质品质视频会

25、议视频会议MPEG 一 2ITU-R601MPEG-2MPEG-2MPEG-1H.2612000一166一一一一一25 一 303一62一41201. . .视频压缩编码标准及其应用范围目前，由国际标准化组织(ISO)和国际电联(ITU-T)正式公布的视频压缩编码标准中，有MPEG系列和H.26x系列建议。. . .H.261CCITT制定的国际上第一个视频压缩标准，主要用于电视电话和会议电视，以满足ISDN日益发展的需要。H.261视频压缩算法的核心是运动估值预测和DCT编码，其许多技术(包括视频数据格式、运动估算与补偿、DCT变换、量化和熵编码)都被后来的MPEG-1和MPEG-2所借鉴和

26、采用。. . .MPEG-1标准“运动图像和伴随声音的编码用于速率约在1.5Mb/s以下的数字存储媒体”。主要用于多媒体存储与再现，如VCD等。MPEG-1采用CIF视频格式，帧速率为25帧/秒或30帧/秒，码率为1.5Mb/s(其中视频约1.2Mb/s，音频约0.3Mb/s)。MPEG-1为了追求更高的压缩率，同时满足多媒体等应用所需的随机存取要求，将视频图象序列划分为I帧、P帧和B帧，根据不同的图象类型而不同对待。该标准草案于1991年11月完成，1992年11月正式通过。. . .MPEG-2标准基本算法也是运动补偿的预测和带有DCT的帧间内变长编码。继MPEG-1之后，MPEG制定的又

27、一视频压缩标准（ISO/IEC 13818)（其中视频部分即为H.262）。它能适用于更广的应用领域，主要包括数字存储媒体，广播电视和通信。制定MPEG-2标准的出发点是保持通用性，适用于广泛的应用领域、比特率、分辨率、质量和服务。MPEG-2适于高于2Mb/s的视频压缩，这包括了原打算为HDTV的发展而制定MPEG-3标准的内容。根据MPEG-2的标准CCIR 601格式(70257625帧)的信号可压缩到4Mb/s6Mb/s，而HDTV格式(128072060帧)的信号可压缩到20Mb/s左右。. . .H.263及H.263+H.263是ITU-T的关于低于64kb/s比特率的窄带通道视

28、频编码建议，其目的是能在现有的电话网上传输活动图象。由于H.263是面向低速信道的，所以必须在帧频和图象失真之间作出选择。H.263是在H.261建议的基础上发展起来的，其信源编码算法仍然是帧间预测/DCT混合编码，但H.263与H.261不同的是，它采用半象素的分辨率进行运动补偿，它处理的图象格式可以覆盖从sub-QCIF到16CIF，而且，H.263还提供了4种可协商选择的编码方法：无限制范围的运动矢量、基于语法的算法编码方法、先进预测和PB帧。. . .MPEG-4标准1994年，MPEG专家组正式开始制定MPEG-4标准，到1998年11月将发布MPEG-4 视频国际标准草案。它主要是

29、针对多媒体应用的，对可移动性的视频编码速率为564kb/s，而对影视应用最高速率可达2Mb/s。MPEG-4标准的突出特点是对音视频数据采用基于内容(Content-based)的操作、存取及传输。为了达到此目的，MPEG-4引入了“视频对象”(VO)的概念。这样可把视频流中的每一帧分割成任意形状的图象区域称为视频对象平面(VOP)，然后根据每一VOP的特点和需要，分别进行编码。要获得VOP，必须使用图象分割技术，如果将纹理信息与运动信息结合起来，则可产生较好的效果。. . .MPEG-4标准MPEG-4标准是一个开放、灵活、可扩展的结构形式，可随时加入新的、有效的算法模板，并可根据不同的应用

30、要求现场配置解码器。它具有如下一些新功能： 基于内容的交互性(Content-based interactivity) ：即可进行基于内容的多媒体数据访问和比特流编辑，并可混合自然和人工数据编码。 高压缩率 ：这不仅表现在可提高编码效率，在移动环境下可传输高质量图象，而且能对多个并发数据流进行编码，使其能有效地描述三维自然景物。 易错环境中的抗错性(Robustness) ：指可应用于各种有线、无线网中，特别是提供了在易错的移动环境下、低比特率应用中的对抗残留错误的能力。 基于内容的可扩缩性(Content-based scalability) ：即可给图象中的各个对象分配优先级，其中，比较重

31、要的对象用较高的空间和时间分辨率表示。基于内容的可扩缩性是MPEG-4的核心。. . .MPEG-7标准随着信息的增多，寻找到所需要的信息越来越困难。目前，基于文本(text-based)型式的搜索引擎已广泛使用，但基于视听内容的检索还很困难。MPEG-7正是为满足这方面的需求而制定的，主要用于基于内容的多媒体检索。MPEG-7又称为“多媒体内容描述接口”，它规定了一套可用于描述各种多媒体信息的描述符的标准。这些描述与多媒体信息的内容本身一起，将支持用户对其感兴趣的资源进行快速、有效的检索。MPEG-7标准建立在其它标准表示的基础上，但MPEG-7描述符不依赖于被描述内容的编码和存储方式。MP

32、EG-7只提供内容的描述，而不是内容本身。MPEG-7不包括特征提取(分析)和搜索引擎(应用)部分。其原因，一是为了促进各公司和研究所间的竞争，其二是为以后各种新技术的发展留下余地。. . .MPEG-7标准应用领域数字化图书馆(包括图象分类目录、音乐字典等)；多媒体目录服务(例如黄页)；广播式媒体选择(包括个人电子新闻服务、媒体著作等)；潜在的应用领域，如旅游信息、文化服务、地理信息系统等。MPEG-7已在2001年11月形成国际标准。目前，虽有许多公司和研究机构，如IBM、MIT已开始对其中的关键技术进行研究并已取得一些成果，但离实际应用还有相当距离。. . .MPEG21MPEG21致力于为多媒体传输和使用定义一个标准化的开放框架。这种框架将在开放的市场中为内容提供商和业务提供商创造同等的机会。同时，这将在一种互操作的模式下为用户提供更丰富的信息，用户将因此而受益。 MPEG21可以总结如下：一个多媒体框架，它可以在广阔的范围里，为不同的网络用户提供透明的和可不断扩展的多媒体资源。 . . .