四川大学多媒体课件二

数据压缩一、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/s

Compressionratio: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/s

Compressionratio:

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）每个个二进制制码可可以不不同长长度，，目标标是平平均码码长最最小。。减少平平均码码长的的基本本思路路：出出现次次数多多的符符号翻翻译成成较短短二进进制码码；出出现次次数少少的符符号翻翻译成成较长长二进进制码码morefrequentlysymbolsshortercodewordslessfrequentlysymbolslongercodewords熵：符号号i在信息息源中中出现现的概概率l(i)：符号i的二进进制码码长度度平均码码长L=∑∑iN=1p(i)l(i)熵熵的定定义(Entropy):熵是信信息源源平均均信息息量，，是信信息源源的特特性当所有有符号号概率率相等等时，，熵的最最大值值为log2N；当符号号概率率相差差大时时，熵的值值较小小。冗余量量：∑iN=1p(i)l(i)-H最优码码：冗冗余量量最小小的编编码编码符符号的的平均均二进进制码码长度度≥信信息息源的的熵（（entropyH）(熵是最最小平平均码码长)熵{0.25,0.25,0.25,0.25}{1,0,0,0}熵假定：：某些符符号出出现概概率比比其他他符号号大例：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):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.30Huff静态Huffman编码算法步步骤：：Step1：以每每个源源符号号的概概率为为权，，组成成N个只有有根节节点的的二叉叉树的的集合合；Step2：将2个权值值最小小的二二叉树树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编码树。adaptiveHuffmancoding算法FGK：（Faller[1973],Gallager[1978],Knut 基本准则——“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-节点点，，右右子子树树为为ai；然后后增增加加相相应应权权值值，，重重新新计计算算树树，，保保持持“sibling””性质质。。算术术编编码码（（ArithmeticCoding）例：：输输入入“AADB#”(结果果：：.0325或.0326或.0327)[0,.2)-[0,.04)-[.028,.036)-[.0296,.0328)-[.03248,.0328）符号概率累积概率间隔[msgleft,msgright)A.2.2[0,.2)B.4.6[.2,.6)C.1.7[.6,.7)D.2.9[.7,.9)#.11.0[0.9,1.0)算术术编编码码消息息用用0到1之间间的的实实数数进进行行编编码码。。[0，1）两个个基基本本的的参参数数：：符号号的的概概率率编码码间间隔隔数据据源源符符号号的的概概率率决决定定压压缩缩编编码码的的效效率率，，也也决决定定编编码码过过程程中中信信源源符符号号的的间间隔隔，，从从而而决决定定了了符符号号压压缩缩后后的的输输出出。。算术编码编码输出：可以是最后一一个间隔中的的任意数。结束：压缩方发送消消息的长度；；添加一个专门门的终止符；；算术编码几个问题：运算中出现溢溢出——比例缩放解决决。只产生一个码码字，译码器器在接受到表表示这个实数数的所有位之之前不能进行行译码。对错误很敏感感的编码方法法，如果有一一位发生错误误就会导致整整个消息译错错。延迟——前面位相同，，可以立即传传送。算术编码算术编码可以以是静态的或或者自适应的的。应用：在图像数据压压缩标准(如JPEG，JBIG)中扮演了重要要的角色。算术编码算法步骤：根据每个符号号概率确定其其编码间隔；；输入第一个字字符的间隔[msgleft,msgright);newleft=msgleftnewsize=msgright-msgleft对每个输入符符号，缩小间间隔范围：newleft=prevleft+msgleft*prevsizenewsize=prevsize*msgsize重复步骤3，直到最后字字符。取[[newleft,newleft+newsize)之间任意数,即为编码.9、静夜四无无邻，荒居居旧业贫。。。1月-231月-23Friday,January6,202310、雨中黄黄叶树，，灯下白白头人。。。00:41:1300:41:1300:411/6/202312:41:13AM11、以我我独沈沈久，，愧君君相见见频。。。1月-2300:41:1300:41Jan-2306-Jan-2312、故人江江海别，，几度隔隔山川。。。00:41:1300:41:1300:41Friday,January6,202313、乍见翻疑疑梦，相悲悲各问年。。。1月-231月-2300:41:1300:41:13January6,202314、他乡生白发发，旧国见青青山。。06一月202312:41:14上午午00:41:141月-2315、比不了得得就不比，，得不到的的就不要。。。。一月2312:41上午1月-2300:41January6,202316、行动出成成果，工作作出财富。。。2023/1/60:41:1400:41:1406January202317、做前前，能能够环环视四四周；；做时时，你你只能能或者者最好好沿着着以脚脚为起起点的的射线线向前前。。。12:41:14上上午午12:41上上午00:41:141月-239、没有失失败，只只有暂时时停止成成功！。。1月-231月-23Friday,January6,202310、很多事情努努力了未必有有结果，但是是不努力却什什么改变也没没有。。00:41:1400:41:1400:411/6/202312:41:14AM11、成功就是日日复一日那一一点点小小努努力的积累。。。1月-2300:41:1400:41Jan-2306-Jan-2312、世间间成事事，不不求其其绝对对圆满满，留留一份份不足足，可可得无无限完完美。。。00:41:1400:41:1400:41Friday,January6,202313、不不知知香香积积寺寺，，数数里里入入云云峰峰。。。。1月月-231月月-2300:41:1400:41:14January6,202314、意志志坚强强的人人能把把世界界放在在手中中像泥泥块一一样任任意揉揉捏。。06一一月月202312:41:14上上午午00:41:141月-2315、楚塞三三湘接，，荆门九九派通。。。。一月2312:41上上午1月-2300:41Janu