四川大学计算机学院 多媒体技术 3

数据压缩一、InformationTheory二、WhyCompression?三、HowtoCompress?四、LosslessCompression五、LossyCompression六、JPEG七、JPEG2000八、MPEGstandards1.MPEGVideo2.ScalableMPEG-2Video3.MPEGAudio2002年10月28日一、信息理论概述信息理论之父为什么压缩?如何压缩?无损压缩Losslesscompression有损压缩Lossycompression图象Image视频Video声音Audio未来?2002年10月28日信息理论之父——ClaudeShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA/news/2001/february/26/1.html2002年10月28日信息理论之父——ClaudeShannon(续)ThefoundingfatherofelectroniccommunicationsageAmericanmathematicalengineerIn1936~1940,MIT:Master'sthesis,AsymbolicanalysisofrelayandswitchingcircuitsDoctoralthesis:ontheoreticalgeneticsIn1948:Amathematicaltheoryofcommunication,landmark,climax(AnimportantfeatureofShannon'stheory:conceptofentropy

)2002年10月28日二、为什么压缩?

任务：存储和传送多媒体信息.Example:(1)Text:Worddocumentchp09.doc: 12.3MBchp09.zip: 907KB

(WinZip8.0)chp09.rar: 767KB

(WinRAR2.7,Finland)2002年10月28日为什么压缩?(续)(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.54722002年10月28日为什么压缩?(续)(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

2002年10月28日为什么压缩?(续)(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:12002年10月28日为什么压缩?(续)解决办法:–更高带宽–减少传输位数来传送未压缩信息内容？其他?2002年10月28日——文件编码（coding）减少存储空间和传输时间普遍使用的文本、图象、声音、视频（text,images,sound,，video）文件转换成bit数较少的文件这种压缩文件（compressedfiles）以后可以扩展成为原来形式，显示或执行为什么压缩?(续)2002年10月28日压缩算法更适合某种类型文件的压缩算法，如：JPEG,GIF——图象MPEG——视频通用压缩算法（不考虑数据表达的类型），如：zipandpkzipforDOSstuffitforMacintosh®operatingsystemsandcompress(usinggzip)forUNIXoperatingsystems.为什么压缩?(续)2002年10月28日三、如何压缩?数据（Data）:

数据冗余（DataRedundancy）声音（Audio）:

人听觉系统能力

数据冗余视频（Video）:

人视觉系统能力

数据冗余2002年10月28日压缩类型无损压缩Lossless(entropycoding)

不丢失信息(即,信号解压decompression后完全复原)

产生可变长位（variablebit-rate）

不保证实际上减少数据长度有损压缩

Lossy

丢失某些信息(即,解压decompression后信号不能完全复原)

产生任意固定位constantbit-rate2002年10月28日数据源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=1077symbols2002年10月28日四、无损压缩LosslessCompression编码：把每个符号“翻译”成一个二进制码（binarycodeword）每个二进制码可以不同长度，目标是平均码长最小。减少平均码长的基本思路：出现次数多的符号翻译成较短二进制码；出现次数少的符号翻译成较长二进制码morefrequentlysymbols

shortercodewords

lessfrequentlysymbols

longer

codewords2002年10月28日熵：符号i在信息源中出现的概率l(i)：

符号i的二进制码长度平均码长L=∑iN=1p(i)l(i)2002年10月28日熵熵的定义

(Entropy):熵是信息源平均信息量，是信息源的特性当所有符号概率相等时，熵的最大值为log2N；当符号概率相差大时，熵的值较小。冗余量：

∑iN=1p(i)l(i)-H最优码：冗余量最小的编码编码符号的平均二进制码长度≥信息源的熵（entropyH）(熵是最小平均码长)2002年10月28日熵

{0.25,0.25,0.25,0.25}{1,0,0,0}2002年10月28日熵假定：某些符号出现概率比其他符号大例：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.252002年10月28日Huffmancoding2002年10月28日Huffmancoding平均代码长度

(编码前):熵:平均代码长度

(Huffmancoding):2002年10月28日Shannon-Fanocoding符号出现的次数分配的代码需要的位数A15(0.375)1.41500030B7(0.175)2.51450114C7(0.175)2.51451014D6(0.150)2.736911018E5(0.125)3.0000111152002年10月28日Shannon-FanocodingShannon-Fano

算法步骤：Step1：将源符号及其概率按非增次序排列；Step2：将符号分成概率和最接近的两组（各1/2），第1组以0开始编码，第2组以1开始编码；Step3：每组重复Step2，在已有编码后按规则追加0/1，直到每个组只有一个符号时，算法终止。优点：简单；不保证最优；

H+1≥平均码长≥H2002年10月28日Shannon-Fanocoding&Huffmancoding例1S-FHuffmana10.35001a20.1701011a30.1710010a40.16110001a50.15111000平均码长2.312.302002年10月28日Huffmancoding静态Huffman编码算法步骤：Step1：以每个源符号的概率为权，组成N个只有根节点的二叉树的集合；Step2：将2个权值最小的二叉树wi和wj,合并成一个根为wi+wj,的二叉树，其左、右子树分别为wi和wj,，将wi+wj插入到集合中，并将wi和wj从集合中删除；Step3：重复Step2，直到集合只有一个权值；Step4：从根到每一叶子节点（源符号）路径上（左0右1）的字符串即为该符号的编码。评价：最优码（最小冗余）2002年10月28日Shannon-Fanocoding&Huffmancoding例2：“aa

bbb

cccc

ddddd

eeeeee

fffffffgggggggg”2002年10月28日Shannon-Fanocoding&Huffmancoding

例2：“aa

bbb

cccc

ddddd

eeeeee

fffffffgggggggg”H=2.894(116)S-F(117)Huffman(117)g8/400000f7/40010110e6/40011111d5/40100010space5/40101101c4/40110011b3/4011101000a2/40111110012002年10月28日数据压缩的模型建立建立模型（modeling）：

给消息源中每一符号指定概率建立模型的方式:

静态的(static)：对所有信息源使用同一模型；半自适应的：对每一信息源使用一种模型（压缩之前扫描一遍信息源或其样本）；自适应的（adaptive）：最初按照某一假定模型，在压缩/解压进行中，同步更改模型（即增、减所压缩/解压符号的概率）2002年10月28日数据压缩的模型建立数据压缩：a->b数据压缩的方法:

静态的：采用“静态的”和“半自适应的”的modeling方式建立模型，a的任何出现都被转换成同一b；

自适应的：采用“自适应的”的modeling方式建立模型，a的不同出现可能被转换成不同b；2002年10月28日adaptiveHuffmancoding基本思想：以自适应的modeling，对迄今出现的信息进行概率估算，以Huffman编码树实现编码。具体做法：编码/译码双方维护随压缩/解压进行不断更改的Huffman编码树，使之一直保持是迄今压缩/解压的源信息——整个源信息的前缀部分——构成的Huffman编码树。2002年10月28日adaptiveHuffmancoding算法FGK： （Faller[1973],Gallager[1978],Knuth[1985]）

基本准则——“sibling”性质： 一个有p个节点的二分树是一Huffman树当且仅当：

1、p个叶节点有非负权值，每一内节点的权值为它的儿子的权值之和；

2、叶节点以权值的非增次序编号，节点2j-1和节点2j是兄弟（sibling），它们共同的父节点有较大的编号。 2002年10月28日adaptiveHuffmancoding算法FGK：

初始一个0-节点；

k种符号，k+1个节点（一个为0节点）；第i步：若ai(当前符号)为k中的一个，则传ai的编码;若ai为新出现符号，则将0-节点分裂：其左子树为0-节点，右子树为ai，并且增加相应权值，重新计算树，保持“sibling”性质。2002年10月28日adaptiveHuffmancoding算法FGK：

初始一个0-节点；

k种符号，构成k+1个节点（一个为0节点）的Huffman树；第i步： 若ai(当前符号)为k中的一个，则传ai的编码; 若ai为新出现符号，则传0-节点的编码以及ai

本身，并将0-节点分裂：其左子树为0-节点，右子树为ai；然后增加相应权值，重新计算树，保持“sibling”性质。2002年10月28日算术编码（ArithmeticCoding）例：输入“AADB#”(结果：.0325或.0326或.0327)[0,.2)-[0,.04)-[.028,.036)-[.0296,.0328)-[.03248,.03