单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2024/11/20,四川大学多媒体课件3,一、信息理论,概述,信息理论之父,为什么压缩,?,如何压缩,?,无损压缩,Lossless compression,有损压缩,Lossy compression,图象,Image,视频,Video,声音,Audio,未来,?,信息理论之父,Claude Shannon,Born:30 April 1916 in Gaylord,Michigan,USA,Died:24 Feb 2001 in Medford,Massachusetts,USA,信息理论之父,Claude Shannon(,续,),The founding father of electronic communications age,American mathematical engineer,In 19361940,MIT:,Masters thesis,A symbolic analysis of relay and,switching,circuits,Doctoral thesis:on theoretical genetics,In 1948:,A mathematical theory of communication,landmark,climax,(An important feature of Shannons theory:concept of,entropy,),二、,为什么压缩,?,任务：存储和传送多媒体信息,.,Example:,(1),Text:Word document,chp09.doc:,12.3 MB,chp09.zip:,907 KB,(WinZip 8.0),chp09.rar:,767 KB,(WinRAR 2.7,Finland),为什么压缩,?,(,续,),(2)Digital camera(image),Card with 64 MB,picture:,1280 pixels/line,960 lines/picture,3 B/pixel,3.6864 MB/picture,Total(without compression):64 MB/(3.6864 MB/picture),17 pictures,Total(with compression),：,198 pictures,Compression ratio:198/52,11.647,picture:,640,480,3,：,0.9216 MB/picture,Total(without compression):,69 pictures,Total(with compression),：,663 pictures,Compression ratio:663/69,9.5472,为什么压缩,?,(,续,),(3)Audio:e.g.,CD-Audio,：,44 100 samples/s 16 B/samples 2(left,right)=,1.4112 Mb,/s!MP3:,-,Near CD:,96,kb/s,Compression ratio:,15:1,-,CD:,112 128,kb/s,Compression ratio:,10 12:1,为什么压缩,?,(,续,),(4)Video,e.g.,DVD-Video:,(,假设子采样为,4:2:2),Y(,亮度,):720576258 83 Mb/s(PAL)720480308 83 Mb/s(NTSC),Cr(,红色差,),Cb(,蓝色差,):2360576258 83 Mb/s(PAL)2360480308 83 Mb/s(NTSC),Total:,166 Mb/s,!,Average bit rate:,4.1 Mb/s,Compression ratio:,40:1,为什么压缩,?,(,续,),解决办法,:,更高带宽,减少传输位数来传送未压缩信息内容？,其他,?,文件编码（,coding,）,减少存储空间和传输时间,普遍使用的文本、图象、声音、视频（,text,images,sound,，,video,）,文件转换成,bit,数较少的文件,这种压缩文件（,compressed files,）,以后可以扩展成为原来形式，显示或执行,为什么压缩,?,(,续,),压缩算法,更适合某种类型文件的压缩算法，如：,JPEG,GIF,图象,MPEG,视频,通用压缩算法（不考虑数据表达的类型），如：,zip and pkzip for DOS,stuffit for Macintosh operating systems,andcompress(using gzip)for UNIX operating systems.,为什么压缩,?,(,续,),三、如何压缩,?,数据（,Data,）,:,数据冗余（,Data Redundancy,）,声音（,Audio,）,:,人听觉系统能力数据冗余,视频（,Video,）,:,人视觉系统能力数据冗余,压缩类型,无损压缩,Lossless(entropy coding),不丢失信息,(,即,信号解压,decompression,后完全复原,),产生可变长位（,variable bit-rate,）,不保证实际上减少数据长度,有损压缩,Lossy,丢失某些信息,(,即,解压,decompression,后信号不能完全复原,),产生任意固定位,constant bit-rate,数据源,Data Sources,数据源有,N,个符号组成,每个符号用,log,2,N,位表示,声音,speech:16 bits/sample:,N,=2,16,=65,536 symbols,彩色图象,color image:38 bits/sample:,N,=2,2 4,=1.677721610,6,symbols,88,的 图象块,:864 bits/block:,N,=2,512,=10,77,symbols,四、,无损压缩,Lossless Compression,编码：把每个符号“翻译”成一个二进制码（,binary codeword,）每个,二进制码可以不同长度，目标是平均码长最小。,减少平均码长的基本思路：出现次数多的符号翻译成较短二进制码；出现次数少的符号翻译成较长二进制码,more frequently symbols,shorter codewords,less frequently symbols,longer,codewords,熵,：符号,i,在信息源中出现的概率,l(i),：,符号,i,的二进制码长度,平均码长,L=,i,N,=1,p(i)l(i),熵,熵的定义,(,Entropy,):,熵是信息源平均信息量，是信息源的特性,当所有符号概率相等时，,熵的最大值为,log,2,N,；,当符号概率相差大时，,熵的值较小。,冗余量：,i,N,=1,p(i)l(i)-H,最优码：冗余量最小的编码,编码符号的平均二进制码长度 信息源的熵（,entropy H,）,(,熵是最小平均码长,),熵,0.25,0.25,0.25,0.25,1,0,0,0,熵,假定：,某些符号出现概率比其他符号大,例：,N,=8 symbols:a,b,c,d,e,f,g,h,3 bits per symbol(,N,=2,3,=8),P(a)=0.01 P(b)=0.02,P(c)=0.05 P(d)=0.09,P(e)=0.18 P(f)=0.2,P(g)=0.2 P(h)=0.25,Huffman coding,Huffman coding,平均代码长度,(,编码前,):,熵,:,平均代码长度,(Huffman coding):,Shannon-Fano,coding,符号,出现的次数,分配的代码,需要的位数,A,15(0.375),1.4150,00,30,B,7(0.175),2.5145,01,14,C,7(0.175),2.5145,10,14,D,6(0.150),2.7369,110,18,E,5(0.125),3.0000,111,15,Shannon-Fano,coding,Shannon-Fano,算法步骤：,Step1,：将源符号及其概率按,非增,次序排列；,Step2,：将符号分成,概率和,最接近的两组（各,1/2,），第,1,组以,0,开始编码，第,2,组以,1,开始编码；,Step3,：每组重复,Step2,，在已有编码后按规则追加,0/1,，直到每个组只有一个符号时，算法终止。,优点：,简单；不保证最优；,H+1,平均码长,H,Shannon-Fano,coding&,Huffman,coding,例,1,S-F,Huffman,a1,0.35,00,1,a2,0.17,01,011,a3,0.17,10,010,a4,0.16,110,001,a5,0.15,111,000,平均码长,2.31,2.30,Huffman coding,静态,Huffman,编码,算法步骤：,Step1,：以每个源符号的概率为权，组成,N,个只有根节点的二叉树的集合；,Step2,：将,2,个权值最小的二叉树,w,i,和,w,j,合并成一个根为,w,i+,w,j,的二叉树，其左、右子树分别为,w,i,和,w,j,，将,w,i+,w,j,插入到集合中，并将,w,i,和,w,j,从集合中删除；,Step3,：重复,Step2,，直到集合只有一个权值；,Step4,：从根到每一叶子节点（源符号）路径上（左,0,右,1,）的字符串即为该符号的编码。,评价：,最优码（最小冗余）,Shannon-Fano,coding&,Huffman,coding,例,2,：“,aa bbb cccc ddddd eeeeee fffffffgggggggg”,Shannon-Fano,coding&,Huffman,coding,例,2,：“,aa bbb cccc ddddd eeeeee fffffffgggggggg”,H=2.894(116),S-F(117),Huffman(117),g,8/40,00,00,f,7/40,010,110,e,6/40,011,111,d,5/40,100,010,space,5/40,101,101,c,4/40,110,011,b,3/40,1110,1000,a,2/40,1111,1001,数据压缩的模型建立,建立模型（,modeling,）：,给消息源中每一符号指定概率,建立模型的方式,:,静态的,(static),：对所有信息源使用同一模型；,半自适应的,：对每一信息源使用一种模型（压缩之前扫描一遍信息源或其样本）；,自适应的（,adaptive,）,：最初按照某一假定模型，在压缩,/,解压进行中，同步更改模型（即增、减所压缩,/,解压符号的概率）,数据压缩的模型建立,数据压缩：,a-b,数据压缩的方法,:,静态的,：采用,“,静态的,”,和,“,半自适应的,”,的,modeling,方式建立模型，,a,的任何出现都被转换成同一,b,；,自适应的,：,采用“自适应的”的,modeling,方式建立模型，,a,的不同出现可能被转换成不同,b,；,adaptive Huffman coding,基本思想：,以自适应的,modeling,，对迄今出现的信息进行概率估算，以,Huffman,编码树实现编码。,具体做法：,编码,/,译码双方维护随压缩,/,解压进行不断更改的,Huffman,编码树，使之一直保持是迄今压缩,/,解压的源信息,整个源信息的前缀部分,构成的,Huffman,编码树。,adaptive Huffman coding,算法,FGK,：,（,Faller1973,Gallager1978,Knuth1985,）,基本准则,“sibling”,性质：,一个有,p,个节点的二分树是一,Huffm