ch02_数据无损压缩.ppt

《ch02_数据无损压缩.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、多媒体技术教程第2章数据无损压缩第2章数据无损压缩目录2.1数据的冗余2.1.1冗余概念2.1.2决策量2.1.3信息量2.1.4熵2.1.5数据冗余量2.2统计编码2.2.1香农-范诺编码2.2.2霍夫曼编码2.2.3算术编码2.3RLE编码2.4词典编码2.4.1词典编码的思想2.4.2LZ77算法2.4.3LZSS算法2.4.4LZ78算法2.4.5LZW算法参考文献和站点2第2章数据无损压缩2.0数据无损压缩概述数据可被压缩的依据数据本身存在冗余听觉系统的敏感度有限视觉系统的敏感度有限三种多媒体数据类型文

2、字(text)数据——无损压缩根据数据本身的冗余(Basedondataredundancy)声音(audio)数据——有损压缩根据数据本身的冗余(Basedondataredundancy)根据人的听觉系统特性(Basedonhumanhearingsystem)图像(image)/视像(video)数据——有损压缩根据数据本身的冗余(Basedondataredundancy)根据人的视觉系统特性(Basedonhumanvisualsystem)3第2章数据无损压缩2.0数据无损压缩概述(续1)数据无损压缩

3、的理论——信息论(informationtheory)1948年创建的数学理论的一个分支学科，研究信息的编码、传输和存储该术语源于ClaudeShannon(香农)发表的“AMathematicalTheoryofCommunication”论文题目，提议用二进制数据对信息进行编码最初只应用于通信工程领域，后来扩展到包括计算在内的其他多个领域，如信息的存储、信息的检索等。在通信方面，主要研究数据量、传输速率、信道容量、传输正确率等问题。数据无损压缩的方法霍夫曼编码(Huffmancoding)算术编码(arith

4、meticcoding)行程长度编码(run-lengthcoding)词典编码(dictionarycoding)……4第2章数据无损压缩2.0数据无损压缩概述(续2)TheFatherofInformationTheory——ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA信息论之父介绍5第2章数据无损压缩2.1数据的冗余冗余概念人为冗余在信息处理系统中，使用两

5、台计算机做同样的工作是提高系统可靠性的一种措施—此种冗余乃有意为之在数据存储和传输中，为了检测和恢复在数据存储或数据传输过程中出现的错误，根据使用的算法的要求，在数据存储或数据传输之前把额外的数据添加到用户数据中，这个额外的数据就是冗余数据—比如数字签名、水印等等视听冗余由于人的视觉系统和听觉系统的局限性，在图像数据和声音数据中，有些数据确实是多余的，使用算法将其去掉后并不会丢失实质性的信息或含义，对理解数据表达的信息几乎没有影响数据冗余不考虑数据来源时，单纯数据集中也可能存在多余的数据，去掉这些多余数据并不会丢

6、失任何信息，这种冗余称为数据冗余，而且还可定量表达6第2章数据无损压缩2.1数据的冗余(续1)决策量(decisioncontent)在有限数目的互斥事件集合中，决策量是事件数的对数值在数学上表示为H0=log(n)其中，n是事件数决策量的单位由对数的底数决定Sh(Shannon):用于以2为底的对数Nat(naturalunit):用于以e为底的对数Hart(hartley)：用于以10为底的对数7第2章数据无损压缩2.1数据的冗余(续2)信息量(informationcontent)具有确定概率事件的信息的定

7、量度量在数学上定义为其中，是事件出现的概率举例：假设X={a,b,c}是由3个事件构成的集合，p(a)=0.5，p(b)=0.25，p(b)=0.25分别是事件a,b和c出现的概率，这些事件的信息量分别为，I(a)=log2(1/0.50)=1shI(b)=log2(1/0.25)=2shI(c)=log2(1/0.25)=2sh一个等概率事件的集合，每个事件的信息量等于该集合的决策量8第2章数据无损压缩2.1数据的冗余(续3)熵(entropy)按照香农(Shannon)的理论，在有限的互斥和联合穷举事件的集合

8、中，熵为事件的信息量的平均值，也称事件的平均信息量(meaninformationcontent)用数学表示为9第2章数据无损压缩2.1数据的冗余(续4)数据的冗余量10第2章数据无损压缩2.2统计编码统计编码给已知统计信息的符号分配代码的数据无损压缩方法编码方法香农-范诺编码霍夫曼编码算术编码编码特性香农-范诺编码和霍夫曼编码的原理相同，都是根据符号集中各个符号出现的频