多媒体技术基础3版2章节数据无损压缩

《多媒体技术基础3版2章节数据无损压缩》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、多媒体技术基础(第3版)第2章数据无损压缩林福宗清华大学计算机科学与技术系linfz@mail.tsinghua.edu.cn2008年9月第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算法参考文献和站点7/20/20212第2章数据无损压缩2.0数据无损压缩概述数据可被压缩的依据

2、数据本身存在冗余听觉系统的敏感度有限视觉系统的敏感度有限三种多媒体数据类型文字(text)数据——无损压缩根据数据本身的冗余(Basedondataredundancy)声音(audio)数据——有损压缩根据数据本身的冗余(Basedondataredundancy)根据人的听觉系统特性(Basedonhumanhearingsystem)图像(image)/视像(video)数据——有损压缩根据数据本身的冗余(Basedondataredundancy)根据人的视觉系统特性(Basedonhumanvisualsystem)7/20/20213第2章数据无损压

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

4、iccoding)行程长度编码(run-lengthcoding)词典编码(dictionarycoding)……7/20/20214第2章数据无损压缩2.0数据无损压缩概述(续2)TheFatherofInformationTheory——ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USAhttp://www.bell-labs.com/news/2001/february/26/1.html信息论之父介绍7/20

5、/20215第2章数据无损压缩2.0数据无损压缩概述(续3)ClaudeShannon——Thefoundingfatherofelectroniccommunicationsage；AmericanmathematicalengineerIn1936~1940,MIT:Master'sthesis,AsymbolicanalysisofrelayandswitchingcircuitsDoctoralthesis:ontheoreticalgeneticsIn1948:Amathematicaltheoryofcommunication,landmark,cl

6、imax(AnimportantfeatureofShannon'stheory:conceptofentropy)7/20/20216第2章数据无损压缩2.1数据的冗余冗余概念人为冗余在信息处理系统中，使用两台计算机做同样的工作是提高系统可靠性的一种措施在数据存储和传输中，为了检测和恢复在数据存储或数据传输过程中出现的错误，根据使用的算法的要求，在数据存储或数据传输之前把额外的数据添加到用户数据中，这个额外的数据就是冗余数据视听冗余由于人的视觉系统和听觉系统的局限性，在图像数据和声音数据中，有些数据确实是多余的，使用算法将其去掉后并不会丢失实质性的信息或含义，

7、对理解数据表达的信息几乎没有影响数据冗余不考虑数据来源时，单纯数据集中也可能存在多余的数据，去掉这些多余数据并不会丢失任何信息，这种冗余称为数据冗余，而且还可定量表达7/20/20217第2章数据无损压缩2.1数据的冗余(续1)决策量(decisioncontent)在有限数目的互斥事件集合中，决策量是事件数的对数值在数学上表示为H0=log(n)其中，n是事件数决策量的单位由对数的底数决定Sh(Shannon):用于以2为底的对数Nat(naturalunit):用于以e为底的对数Hart(hartley)：用于以10为底的对数7/20/20218第2章数据无

8、损压缩2.1数据的冗余(