四川大学多媒体课件3

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

数据压缩一、InformationTheory二、WhyCompression?三、HowtoCompress?四、LosslessCompression五、LossyCompression六、JPEG七、JPEG2000八、MPEGstandards1.MPEGVideo2.ScalableMPEG-2Video3.MPEGAudio一、信息理论概述信息理论之父为什么压缩?如何压缩?无损压缩Losslesscompression有损压缩Lossycompression图象Image视频Video声音Audio未来?信息理论之父——ClaudeShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA信息理论之父——ClaudeShannon(续)ThefoundingfatherofelectroniccommunicationsageAmericanmathematicalengineerIn1936~1940,MIT:Master'sthesis,AsymbolicanalysisofrelayandswitchingcircuitsDoctoralthesis:ontheoreticalgeneticsIn1948:Amathematicaltheoryofcommunication,landmark,climax(AnimportantfeatureofShannon'stheory:conceptofentropy)二、为什么压缩?任务:存储和传送多媒体信息.Example:(1)Text:Worddocumentchp09.doc:12.3MBchp09.zip:907KB(WinZip8.0)chp09.rar:767KB(WinRAR2.7,Finland)为什么压缩?(续)(2)Digitalcamera(image),Cardwith64MBpicture:1280pixels/line×960lines/picture×3B/pixel=3.6864MB/pictureTotal(withoutcompression):64MB/(3.6864MB/picture)=17picturesTotal(withcompression):198picturesCompressionratio:198/52=11.647picture:640×480×3:0.9216MB/pictureTotal(withoutcompression):69picturesTotal(withcompression):663picturesCompressionratio:663/69=9.5472为什么压缩?(续)(3)Audio:e.g.CD-Audio:44100samples/s×16B/samples×2(left,right)=1.4112Mb/s!!!MP3:-NearCD:96kb/sCompressionratio:15:1-CD:112~128kb/sCompressionratio:10~12:1为什么压缩?(续)(4)Video,e.g.DVD-Video:(假设子采样为4:2:2)Y(亮度):720×576×25×8≈83Mb/s(PAL)720×480×30×8≈83Mb/s(NTSC)Cr(红色差),Cb(蓝色差):2×360×576×25×8≈83Mb/s(PAL)2×360×480×30×8≈83Mb/s(NTSC)Total:166Mb/s!!!Averagebitrate:4.1Mb/sCompressionratio:40:1为什么压缩?(续)解决办法:–更高带宽–减少传输位数来传送未压缩信息内容?其他?——文件编码(coding)减少存储空间和传输时间普遍使用的文本、图象、声音、视频(text,images,sound,,video)文件转换成bit数较少的文件这种压缩文件(compressedfiles)以后可以扩展成为原来形式,显示或执行为什么压缩?(续)压缩算法更适合某种类型文件的压缩算法,如:JPEG,GIF——图象MPEG——视频通用压缩算法(不考虑数据表达的类型),如:zipandpkzipforDOSstuffitforMacintosh®operatingsystemsandcompress(usinggzip)forUNIXoperatingsystems.为什么压缩?(续)三、如何压缩?数据(Data):数据冗余(DataRedundancy)声音(Audio):人听觉系统能力数据冗余视频(Video):人视觉系统能力数据冗余压缩类型无损压缩Lossless(entropycoding)不丢失信息(即,信号解压decompression后完全复原)产生可变长位(variablebit-rate)不保证实际上减少数据长度有损压缩Lossy丢失某些信息(即,解压decompression后信号不能完全复原)产生任意固定位constantbit-rate数据源DataSources数据源有N个符号组成每个符号用log2N位表示–声音speech:16bits/sample:N=216=65,536symbols–彩色图象colorimage:3×8bits/sample:N=224=1.6777216×106symbols–8×8的图象块:8×64bits/block:N=2512=1077symbols四、无损压缩LosslessCompression编码:把每个符号“翻译”成一个二进制码(binarycodeword)每个二进制码可以不同长度,目标是平均码长最小。减少平均码长的基本思路:出现次数多的符号翻译成较短二进制码;出现次数少的符号翻译成较长二进制码morefrequentlysymbolsshortercodewordslessfrequentlysymbolslongercodewords熵:符号i在信息源中出现的概率01Pi()11NiPi()Pi()l(i):符号i的二进制码长度平均码长L=∑iN=1p(i)l(i)熵熵的定义(Entropy):熵是信息源平均信息量,是信息源的特性当所有符号概率相等时,熵的最大值为log2N;当符号概率相差大时,熵的值较小。冗余量:∑iN=1p(i)l(i)-H最优码:冗余量最小的编码编码符号的平均二进制码长度≥信息源的熵(entropyH)(熵是最小平均码长)21()log()NiHPiPi熵{0.25,0.25,0.25,0.25}{1,0,0,0}2114244log()H0H熵假定:某些符号出现概率比其他符号大例:N=8symbols:{a,b,c,d,e,f,g,h},3bitspersymbol(N=23=8)P(a)=0.01P(b)=0.02P(c)=0.05P(d)=0.09P(e)=0.18P(f)=0.2P(g)=0.2P(h)=0.25HuffmancodingHuffmancoding平均代码长度(编码前):熵:平均代码长度(Huffmancoding):8133bits/symbol()iLPi82125821bits/symbol()log().iHPiPi263bits/symbol.HufLShannon-Fanocoding符号出现的次数分配的代码需要的位数A15(0.375)1.41500030B7(0.175)2.51450114C7(0.175)2.51451014D6(0.150)2.736911018E5(0.125)3.000011115Shannon-FanocodingShannon-Fano算法步骤:Step1:将源符号及其概率按非增次序排列;Step2:将符号分成概率和最接近的两组(各1/2),第1组以0开始编码,第2组以1开始编码;Step3:每组重复Step2,在已有编码后按规则追加0/1,直到每个组只有一个符号时,算法终止。优点:简单;不保证最优;H+1≥平均码长≥HShannon-Fanocoding&Huffmancoding例1S-FHuffmana10.35001a20.1701011a30.1710010a40.16110001a50.15111000平均码长2.312.30Huffmancoding静态Huffman编码算法步骤:Step1:以每个源符号的概率为权,组成N个只有根节点的二叉树的集合;Step2:将2个权值最小的二叉树wi和wj,合并成一个根为wi+wj,的二叉树,其左、右子树分别为wi和wj,,将wi+wj插入到集合中,并将wi和wj从集合中删除;Step3:重复Step2,直到集合只有一个权值;Step4:从根到每一叶子节点(源符号)路径上(左0右1)的字符串即为该符号的编码。评价:最优码(最小冗余)Shannon-Fanocoding&Huffmancoding例2:“aabbbccccdddddeeeeeefffffffgggggggg”Shannon-Fanocoding&Huffmancoding例2:“aabbbccccdddddeeeeeefffffffgggggggg”H=2.894(116)S-F(117)Huffman(117)g8/400000f7/40010110e6/40011111d5/40100010space5/40101101c4/40110011b3/4011101000a2/4011111001数据压缩的模型建立建立模型(modeling):给消息源中每一符号指定概率建立模型的方式:静态的(static):对所有信息源使用同一模型;半自适应的:对每一信息源使用一种模型(压缩之前扫描一遍信息源或其样本);自适应的(adaptive):最初按照某一假定模型,在压缩/解压进行中,同步更改模型(即增、减所压缩/解压符号的概率)数据压缩的模型建立数据压缩:a-b数据压缩的方法:静态的:采用“静态的”和“半自适应的”的modeling方式建立模型,a的任何出现都被转换成同一b;自适应的:采用“自适应的”的modeling方式建立模型,a的不同出现可能被转换成不同b;adaptiveHuffmancoding基本思想:以自适应的modeling,对迄今出现的信息进行概率估算,以Huffman编码树实现编码。具体做法:编码/译码双方维护随压缩/解压进行不断更改的Huffman编码树,使之一直保持是迄今压缩/解压的源信息——整个源信息的前缀部分——构成的Huffman编码树。adaptiveHuffmancoding算法FGK:(Faller[1973],Gallager[1978],Knuth[1985])基本准则——“sibling”性质:一个有p个节点的二分树是一Huffman树当且仅当:1、p个叶节点有非负权值,每一内节点的权值为它的儿子的权值之和;2、叶节点以权值的非增次序编号,节点2j-1和节点2j是兄弟(sibling),它们共同的父节点有较大的编号。adaptiveHuffmancoding算法FGK:初始一个0-节点;k种符号,k+1个节点(一个为0节点);第i步:若ai(当前符号)为k中的一个,则传ai的编码;若ai为新出现符号,则将0-节点分裂:其左子树为0-节点,右子树为ai,并且增加相应权值,重新计算树,保持“sibling”性质。adaptiveHuffmancoding算法FGK:初始一个0-节点;k种符号,构成k+1个节点(一个为0节点)的Huffman树;第i步:若ai(当前符号)为k中的一个,则传ai的编码;若ai为新出现符号,则传0-节点的编码以及ai本身,并将0-节点分裂:其左子树为0-

1 / 39
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功