四川大学多媒体课件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-