多媒体数据压缩技术课件

,回到第一页,*,第四章 多媒体数据压缩技术,第,*,页,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,第四章 多媒体数据压缩技术,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第四章 数据压缩技术,Data Compression Technologies,本章主要介绍目前用得最多和技术最成熟的数据压缩编码技术。数据压缩可分成两种类型，一种叫做无损,(lossless),压缩，另一种叫做有损,(lossy),压缩。,无损压缩编码技术包括霍夫曼编码、算术编码、,RLE,编码和词典编码。,有损压缩技术如离散余弦变换、小波变换等。,2024/11/19,第,1,页,第四章 多媒体数据压缩技术,内容提纲,4.1,数据压缩技术概述,4.2,霍夫曼,(,Huffman,),编码算法,4.3,算术,(,Arithmetic,),编码算法,4.4,RLE,编码,(,Run Length Encoding,),算法,4.5,词典,(,Dictionary,),编码算法,参考文献与作业,2024/11/19,第,2,页,第四章 多媒体数据压缩技术,作业,运用,Huffman,算术编码，,LZ77,分别对下段文字进行编解码,：,(,Huffman,编码可设置码表,),Grid computing is becoming an important framework for enabling applications to utilize widely distributed collections of computational and data resources,however current grid software is still immature and rather difficult to use.The Globus Grid Toolkit is a set of low-level tools,protocols and services that has become a de facto standard for basic grid computing infrastructure.The Globus Resource Allocation and Management(GRAM)service provides for the management and remote execution of jobs defined using a standard Resource Specification Language(RSL).Currently,the GRAM has very limited functionality,which makes it more difficult to develop grid applications.One limitation is the lack of support for applications that require a special execution environment,such as Java applications that run within a Java Virtual Machine.Cumbersome workarounds are necessary to run such applications.The current GRAM addresses these problems in a rather ad hoc way for certain specific cases,however there is no general,well-defined mechanism for supporting arbitrary execution environments.Here we outline some of the problems with the current Globus GRAM specification and provide a proposal for how they might be addressed by defining some extensions to the standard RSL supported by the GRAM,as well as some modifications to the design of the GRAM that would enable it to support arbitrary execution environments.We give examples of how our proposed system can provide improved support for Java applications and cluster management systems,and describe our ongoing work in implementing prototypes of these proposed GRAM extensions.,2024/11/19,3,第四章 多媒体数据压缩技术,参考文献,题名：,多媒体数据压缩技术,丛编题名,：全国高技术重点图书,ISBN,号：,7-5053-2206-0,出版项,：北京 电子工业出版社,1994.4,著者：,高文,题名：,数据压缩技术及其应用,丛编题名：,计算机科学大众丛书,ISBN,号：,7-5053-3253-8,出版项：,北京 电子工业出版社,2019,著者：,袁玫,袁文,题名：,数据压缩技术原理与范例,ISBN,号：,7-03-004846-6,出版项：,北京 科学出版社,2019,著者：,(,美,)Mark Nelson,题名：,数据压缩技术及其应用,ISBN,号：,7-115-03835-X,出版项：,北京 人民邮电出版社,1989.6,著者：,(,美,),林奇,(Lynch,T.J.),2024/11/19,4,第四章 多媒体数据压缩技术,数据压技术缩概述,An Introduction to Data Compression,基本概念与定义,数据压缩技术的分类,常用的数据压缩方法,4.1,2024/11/19,第,5,页,第四章 多媒体数据压缩技术,数据压缩的必要性,数据通信,数据存储,24 Bit Bitmap(193k),JPEG(10k),2024/11/19,6,第四章 多媒体数据压缩技术,考虑的因素,不能失真,磁盘文件,。,允许失真,在不影响“质量”的情况下,ABCAACBBC,ABCAACBBC,#$%&*,压缩编码,数据还原,256 color(66k),24 bit(193k),2024/11/19,7,第四章 多媒体数据压缩技术,基本概念,无损压缩,(,Lossless Compression,),是指使用压缩后的数据进行重构,(,或者叫做还原，解压缩,),，重构后的数据与原来的数据完全相同。,有损压缩,(,Lossy Compression,),是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。,无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的,1/2,1/4,。一些常用的无损压缩算法有霍夫曼,(Huffman),算法和,LZW(Lenpel-Ziv&Welch),压缩算法。,有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。,2024/11/19,8,第四章 多媒体数据压缩技术,数据压缩技术的分类,多媒体数据压缩编码,PCM,量化,预测编码,基于频率,基于统计,(,熵编码,),基于重要性,基于模型,国际标准,DPCM,变换编码,(DCT),子带编码,小波变换,Huffman,Arithmetic,RLE,滤波,子采样,比特分配,基于内容,(,物体,),基于语义,物体截取,物体形状编码,运动估计,运动补偿,纹理编码,三维景物建模,模型限定,参数编码,JPEG,MPEG,H.261,MHEG,2024/11/19,9,第四章 多媒体数据压缩技术,统计编码中“熵”的基本概念,熵,(,Entropy,),熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。,某个事件的信息量用 表示，其中,p,i,为第,i,个事件的概率，,0,p,i,1,。,信源,s,的熵的,定义,：按照香农,(Shannon),的理论，信源,s,的熵定义为,其中：,p,i,为,s,i,在,s,中出现的概率，表示包含在,s,i,中的信息量，也就是编码所需要的位数，例如，一幅用,256,级灰度表示的图像，如果每一个象素点灰度的概率均为,p,i,=1/256,，编码每一个象素点就需要,8,位。,2024/11/19,10,第四章 多媒体数据压缩技术,常用的压缩方法,统计编码,图像,。,预测编码,音频,。,变换编码,图像,。,混合编码,标准,量化也是实现数据压缩的一种手段,2024/11/19,11,第四章 多媒体数据压缩技术,霍夫曼编码,Huffman Encoding System,霍夫曼,(Huffman),在,1952,年提出的一种编码方法，即从下到上的编码方法。该方法根据待编码信息的统计特征,(,熵,),，先按出现频率的大小从下到上构建编码树；然后按类似于前序,(,后序,),遍历的方法赋予树的每条边一个码值，“,0”,或“,1”,；最后探索根到叶结点，根到叶所经历边码的序列即为该字符的“码值”。,霍夫曼编码分为定长编码和变长编码两种。后者的应用比较广泛。此外，霍夫曼编码自含同步码，码串中不需要另加标记。,4.2,2024/11/19,第,12,页,第四章 多媒体数据压缩技术,编码算法,主要步骤,(,可变长编码,),统计各字符出现的频率,根据贪心策略构建编码树,按类似于前序遍历的方法递归地遍历编码树，对于连接左子树的边赋予边码为“,0”,，连接右树的边码为“,1”,。反过来亦可。,即算从“根”到“叶”的边码序列，得到某字符的编码。,0.1282,0.1538,0.1539,0.1795,0.3846,0.2820,0.3334,0.6154,1.0000,0,1,0,0,1,1,1,0,A,B,C,D,E,A:“,0,”,B:“,100,”,C:“,101,”,D:“,110,”,E:“,111,”,2024/11/19,13,第四章 多媒体数据压缩技术,编码方法,Huffman编码举例,符号,出现的次数,log,2,(1/p,i,),分配的代码,需要的位数,A,15(0.3846),1.38,0,15,B,7(0.1795),2.48,100,21,C,6(0.1538),2.70,101,18,D,6(0.1538),2.70,110,18,E,5(0.1282),2.96,111,15,从下到上按贪心策略进行选择来构建二进制编码树。,在进行编码树遍历时规定连接“左”子数的边码为“,0”,，右子树的码为“,1”,。反过来也可以。,从根到叶的边码序列为该叶节点的编码，如,C,的编码为“,101”,。,2024/11/19,14,第四章 多媒体数据压缩技术,霍夫曼编码小结,霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码,(,自含同步码，在编码之后的码串中都不须要另外添加标记符号,),。,例如，码串中的第,1,位为,0,，那末肯定是符号,A,，因为表示其他符号的代码没有一个是以,0,开