多媒体技术基础第3版第2章数据无损压缩.ppt
多媒体技术基础第3版第2章数据无损压缩 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第第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.3 RLE编码编码2.4 词典编码词典编码2.4.1 词典编码的思想2.4.2 LZ77算法2.4.3 LZSS算法2.4.4 LZ78算法2.4.5 LZW算法参考文献和站点参考文献和站点9/24/20222 of 42第2章 数据无损压缩2.0 数据无损压缩概述数据无损压缩概述n数据可被压缩的依据数据可被压缩的依据数据本身存在冗余听觉系统的敏感度有限视觉系统的敏感度有限n三种多媒体数据类型三种多媒体数据类型文字(text)数据无损压缩n根据数据本身的冗余(Based on data redundancy)声音(audio)数据有损压缩n根据数据本身的冗余(Based on data redundancy)n根据人的听觉系统特性(Based on human hearing system)图像(image)/视像(video)数据有损压缩n根据数据本身的冗余(Based on data redundancy)n根据人的视觉系统特性(Based on human visual system)9/24/20223 of 42第2章 数据无损压缩2.0 数据无损压缩概述数据无损压缩概述(续续1)n数据无损压缩的理论数据无损压缩的理论信息论信息论(information theory)1948年创建的数学理论的一个分支学科，研究信息的编码、传输和存储该术语源于Claude Shannon(香农)发表的“A Mathematical Theory of Communication”论文题目，提议用二进制数据对信息进行编码最初只应用于通信工程领域，后来扩展到包括计算在内的其他多个领域，如信息的存储、信息的检索等。在通信方面，主要研究数据量、传输速率、信道容量、传输正确率等问题。n数据无损压缩的方法数据无损压缩的方法霍夫曼编码(Huffman coding)算术编码(arithmetic coding)行程长度编码(run-length coding)词典编码(dictionary coding)9/24/20224 of 42第2章 数据无损压缩2.0 数据无损压缩概述数据无损压缩概述(续续2)nThe Father of Information TheoryClaude Elwood ShannonBorn:30 April 1916 in Gaylord,Michigan,USADied:24 Feb 2001 in Medford,Massachusetts,USAhttp:/www.bell- of 42第2章 数据无损压缩2.0 数据无损压缩概述数据无损压缩概述(续续3)nClaude Shannon The founding father of electronic communications age；American mathematical engineerIn 19361940,MIT:nMasters thesis,A symbolic analysis of relay and switching circuitsnDoctoral thesis:on theoretical geneticsIn 1948:nA mathematical theory of communication,landmark,climax(An important feature of Shannons theory:concept of entropy)9/24/20226 of 42第2章 数据无损压缩2.1 数据的冗余数据的冗余n冗余概念冗余概念人为冗余n在信息处理系统中，使用两台计算机做同样的工作是提高系统可靠性的一种措施n在数据存储和传输中，为了检测和恢复在数据存储或数据传输过程中出现的错误，根据使用的算法的要求，在数据存储或数据传输之前把额外的数据添加到用户数据中，这个额外的数据就是冗余数据视听冗余n由于人的视觉系统和听觉系统的局限性，在图像数据和声音数据中，有些数据确实是多余的，使用算法将其去掉后并不会丢失实质性的信息或含义，对理解数据表达的信息几乎没有影响数据冗余n不考虑数据来源时，单纯数据集中也可能存在多余的数据，去掉这些多余数据并不会丢失任何信息，这种冗余称为数据冗余，而且还可定量表达 9/24/20227 of 42第2章 数据无损压缩2.1 数据的冗余数据的冗余(续续1)n决策量决策量(decision content)在有限数目的互斥事件集合中，决策量是事件数的对数值在数学上表示为 H0=log(n)其中，n是事件数决策量的单位由对数的底数决定nSh(Shannon):用于以2为底的对数nNat(natural unit):用于以e为底的对数nHart(hartley)：用于以10为底的对数9/24/20228 of 42第2章 数据无损压缩2.1 数据的冗余数据的冗余(续续2)n信息量信息量(information content)具有确定概率事件的信息的定量度量在数学上定义为 其中，是事件出现的概率 举例：假设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)=1 sh I(b)=log2(1/0.25)=2 sh I(c)=log2(1/0.25)=2 sh一个等概率事件的集合，每个事件的信息量等于该集合的决策量9/24/20229 of 42第2章 数据无损压缩2.1 数据的冗余数据的冗余(续续3)n熵熵(entropy)按照香农(Shannon)的理论，在有限的互斥和联合穷举事件的集合中，熵为事件的信息量的平均值，也称事件的平均信息量(mean information content)用数学表示为9/24/202210 of 42第2章 数据无损压缩2.1 数据的冗余数据的冗余(续续4)n数据的冗余量数据的冗余量9/24/202211 of 42第2章 数据无损压缩2.2 统计编码统计编码n统计编码统计编码给已知统计信息的符号分配代码的数据无损压缩方法n编码方法编码方法香农-范诺编码霍夫曼编码算术编码n编码特性编码特性香农-范诺编码和霍夫曼编码的原理相同，都是根据符号集中各个符号出现的频繁程度来编码，出现次数越多的符号，给它分配的代码位数越少算术编码使用0和1之间的实数的间隔长度代表概率大小，概率越大间隔越长，编码效率可接近于熵9/24/202212 of 42第2章 数据无损压缩2.2.1 统计编码统计编码香农香农-范诺编码范诺编码n香农香农-范诺编码范诺编码(ShannonFano coding)在香农的源编码理论中，熵的大小表示非冗余的不可压缩的信息量在计算熵时，如果对数的底数用2，熵的单位就用“香农(Sh)”，也称“位(bit)”。“位”是1948年Shannon首次使用的术语。例如最早阐述和实现“从上到下”的熵编码方法的人是Shannon(1948年)和Fano(1949年)，因此称为香农-范诺(Shannon-Fano)编码法9/24/202213 of 42第2章 数据无损压缩2.2.1 香农香农-范诺编码范诺编码n香农香农-范诺编码举例范诺编码举例 有一幅40个像素组成的灰度图像，灰度共有5级，分别用符号A，B，C，D和E表示。40个像素中出现灰度A的像素数有15个，出现灰度B的像素数有7个，出现灰度C的像素数有7个，其余情况见表2-1n(1)计算该图像可能获得的压缩比的理论值n(2)对5个符号进行编码n(3)计算该图像可能获得的压缩比的实际值表表2-1 符号在图像中出现的数目符号在图像中出现的数目符号ABCDE出现的次数157765出现的概率15/407/407/406/405/409/24/202214 of 42第2章 数据无损压缩2.2.1 香农香农-范诺编码范诺编码(续续1)(1)压缩比的理论值压缩比的理论值按照常规的编码方法，表示5个符号最少需要3位，如用000表示A，001表示B，100表示E，其余3个代码(101，110，111)不用。这就意味每个像素用3位，编码这幅图像总共需要120位。按照香农理论，这幅图像的熵为这个数值表明，每个符号不需要用3位构成的代码表示，而用2.196位就可以，因此40个像素只需用87.84位就可以，因此在理论上，这幅图像的的压缩比为120:87.841.37:1，实际上就是3:2.1961.37 9/24/202215 of 42第2章 数据无损压缩2.2.1 香农香农-范诺编码范诺编码(续续2)(2)符号编码符号编码对每个符号进行编码时采用“从上到下”的方法。首先按照符号出现的频度或概率排序，如A，B，C，D和E，见表2-2。然后使用递归方法分成两个部分，每一部分具有近似相同的次数，如图2-1所示 9/24/202216 of 42第2章 数据无损压缩2.2.1 香农香农-范诺编码范诺编码(续续3)（3）压缩比的实际值）压缩比的实际值按照这种方法进行编码需要的总位数为30+14+14+18+1591，实际的压缩比为120:911.32:1 图2-1 香农-范诺算法编码举例 9/24/202217 of 42第2章 数据无损压缩2.2.2 统计编码统计编码霍夫曼编码霍夫曼编码n霍夫曼编码霍夫曼编码(Huffman coding)霍夫曼(D.A.Huffman)在1952年提出和描述的“从下到上”的熵编码方法根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少广泛用在JPEG,MPEG,H.26X等各种信息编码标准中9/24/202218 of 42第2章 数据无损压缩2.2.2 霍夫曼编码 Case Study 1n霍夫曼编码举例霍夫曼编码举例1现有一个由5个不同符号组成的30个符号的字符串：BABACACADADABBCBABEBEDDABEEEBB计算(1)该字符串的霍夫曼码(2)该字符串的熵(3)该字符串的平均码长(4)编码前后的压缩比9/24/202219 of 42第2章 数据无损压缩2.2.2 霍夫曼编码 Case Study 1(续续1)符号出现的次数 log2(1/pi）分配的代码需要的位数B101.585?A81.907?C33.322?D42.907?E52.585?合计30符号出现的概率符号出现的概率9/24/202220 of 42第2章 数据无损压缩2.2.2 霍夫曼编码霍夫曼编码 Case Study 1(续续2)(1)计算该字符串的霍夫曼码计算该字符串的霍夫曼码步骤：按照符号出现概率大小的顺序对符号进行排序步骤：把概率最小的两个符号组成一个节点P1步骤：重复步骤，得到节点P2，P3，P4，PN，形成一棵树，其中的PN称为根节点步骤：从根节点PN开始到每个符号的树叶，从上到下 标上0(上枝)和1(下枝)，至于哪个为1哪个为0则 无关紧要，但通常把概率大的标成1，概率小的 标成0步骤：从根节点PN开始顺着树枝到每个叶子分别写出 每个符号的代码9/24/202221 of 42第2章 数据无损压缩2.2.2 霍夫曼编码霍夫曼编码 Case Study 1(续续3)符号符号B(10)A(8)E(5)D(4)C(3)P1(7)P2(12)P3(18)P4(30)01101010代码代码B(11)A(10)E(00)D(011)C(010)9/24/202222 of 42第2章 数据无损压缩2.2.2 霍夫曼编码霍夫曼编码 Case Study 1(续续4)符号出现的次数log2(1/pi）分配的代码需要的位数B101.5851120A81.9071016C33.3220109D42.90701112E52.5850010合计301.06730个字符组成的字符串需要个字符组成的字符串需要67位位5个符号的代码9/24/202223 of 42第2章 数据无损压缩2.2.2 霍夫曼编码霍夫曼编码 Case Study 1(续续5)(2)计算该字符串的熵计算该字符串的熵 其中，是事件 的集合，并满足H(S)=(8/30)log2(30/8)+(10/30)log2(30/10)+(3/30)log2(30/3)+(4/30)log2(30/4)+(5/30)log2(30/5)=30lg30 (8lg8 10lg10 3lg3 4 lg4 5 lg5)/(30log22)=(44.313624.5592)/9.0308 2.1874 (Sh)9/24/202224 of 42第2章 数据无损压缩2.2.2 霍夫曼编码霍夫曼编码 Case Study 1(续续6)(3)计算该字符串的平均码长计算该字符串的平均码长平均码长：(28210333425)/30 2.233 位/符号 压缩比压缩比:90/67=1.34:1 平均码长：平均码长：67/30=2.233位位(4)计算编码前后的压缩比计算编码前后的压缩比n编码前：5个符号需3位，30个字符，需要90位n编码后：共67位9/24/202225 of 42第2章 数据无损压缩2.2.2 霍夫曼编码霍夫曼编码 Case Study 2n霍夫曼编码举例霍夫曼编码举例2编码前nN=8 symbols:a,b,c,d,e,f,g,h,n3 bits per symbol(N=23=8)nP(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计算(1)该字符串的霍夫曼码(2)该字符串的熵(3)该字符串的平均码长(4)编码效率9/24/202226 of 42第2章 数据无损压缩2.2.2 霍夫曼编码霍夫曼编码 Case Study 2(续续1)9/24/202227 of 42第2章 数据无损压缩2.2.2 霍夫曼编码霍夫曼编码 Case Study 2(续续2)Average length per symbol(before coding):(2)Entropy:(3)Average length per symbol(with Huffman coding):(4)Efficiency of the code:9/24/202228 of 42第2章 数据无损压缩2.2.3 统计编码统计编码算术编码算术编码n算术编码算术编码(arithmetic coding)给已知统计信息的符号分配代码的数据无损压缩技术基本思想是用0和1之间的一个数值范围表示输入流中的一个字符，而不是给输入流中的每个字符分别指定一个码字实质上是为整个输入字符流分配一个“码字”，因此它的编码效率可接近于熵 9/24/202229 of 42第2章 数据无损压缩2.2.3 算术编码举例算术编码举例n例例2.3（取自教材）（取自教材）假设信源符号为00,01,10,11，它们的概率分别为 0.1,0.4,0.2,0.3 对二进制消息序列10 00 11 00 10 11 01 进行算术编码9/24/202230 of 42第2章 数据无损压缩2.2.3 算术编码举例算术编码举例(续续1)符号00011011概率0.10.40.20.3初始编码间隔 0,0.1)0.1,0.5)0.5,0.7)0.7,1表表2-4 2-4 例例2.32.3的信源符号概率和初始编码间隔的信源符号概率和初始编码间隔 n初始化初始化根据信源符号的概率把间隔0,1)分成如表2-4所示的4个子间隔：0,0.1),0.1,0.5),0.5,0.7),0.7,1)。其中x,y)的表示半开放间隔，即包含x不包含y，x称为低边界或左边界，y称为高边界或右边界9/24/202231 of 42第2章 数据无损压缩2.2.3 算术编码举例算术编码举例(续续2)n确定符号的编码范围确定符号的编码范围编码时输入第1个符号是10，找到它的编码范围是0.5,0.7消息中第2个符号00的编码范围是0,0.1)，它的间隔就取0.5,0.7)的第一个十分之一作为新间隔0.5,0.52)编码第3个符号11时，取新间隔为0.514,0.52)编码第4个符号00时，取新间隔为0.514,0.5146)依此类推消息的编码输出可以是最后一个间隔中的任意数n整个编码过程如图整个编码过程如图2-3所示所示n编码和译码的全过程分别见表编码和译码的全过程分别见表2-5和表和表2-6 9/24/202232 of 42第2章 数据无损压缩2.2.3 算术编码举例算术编码举例(续续3)图2-3 例2.3的算术编码过程9/24/202233 of 42第2章 数据无损压缩2.2.3 算术编码举例算术编码举例(续续4)9/24/202234 of 42第2章 数据无损压缩2.2.3 算术编码举例算术编码举例(续续5)9/24/202235 of 42第2章 数据无损压缩2.3 RLE编码编码n行程长度编码(Run-Length Coding)一种无损压缩数据编码技术，它利用重复的数据单元有相同的数值这一特点对数据进行压缩。对相同的数值只编码一次，同时计算出相同值重复出现的次数。在JPEG，MPEG，H.261和H.263等压缩方法中，RLE用来对图像数据变换和量化后的系数进行编码例:假设有一幅灰度图像第n行的像素值如图2-5所示。用RLE编码方法得到的代码为：80315084180图2-5 RLE编码概念9/24/202236 of 42第2章 数据无损压缩2.3 RLE编码编码(续续)nAssumption:Long sequences of identical symbols.Example,9/24/202237 of 42第2章 数据无损压缩2.4 词典编码词典编码n词典编码词典编码(dictionary coding)文本中的词用它在词典中表示位置的号码代替的一种无损数据压缩方法。采用静态词典编码技术时，编码器需要事先构造词典，解码器要事先知道词典。采用动态辞典编码技术时,编码器将从被压缩的文本中自动导出词典，解码器解码时边解码边构造解码词典两种类型的编码算法n具体算法具体算法LZ77算法LZSS算法LZ78算法LZW算法(当作课外阅读)9/24/202238 of 42第2章 数据无损压缩2.4 词典编码词典编码(续续1)n第一类编码算法第一类编码算法用已经出现过的字符串替代重复的部分 编码器的输出仅仅是指向早期出现过的字符串的“指针”图2-6 第一类词典编码概念9/24/202239 of 42第2章 数据无损压缩2.4 词典编码词典编码(续续2)n第二类编码算法第二类编码算法从输入的数据中创建一个“短语词典(dictionary of the phrases)”编码器输出词典中的短语“索引号”，而不是短语图2-7 第二类词典编码概念9/24/202240 of 42第2章 数据无损压缩第第2章章 数据无损压缩数据无损压缩n参考文献和站点参考文献和站点1.David Salomon,Data Compression,ISBN 0-387-40697-2,Third Edition,Springer-Verlag,20042.Data Compression Reference Center，http:/compress.rasip.fer.hr/index_menu.htm3.Timothy C.Bell,John G.Cleary,Ian H.Witten.Text Compression.Prentice-Hall,Inc.,19904.Ziv,J.and Lempel,A.A Universal Algorithm for Sequential Data Compression.IEEE Transactions on Information Theory,May 19775.Terry A.Welch,A Technique for High-Performance Data Compression.Computer,June 19846.Nelson,M.R.LZW Data Compression.Dr.Dobbs Journal,October 1989，http:/marknelson.us/1989/10/01/lzw-data-compression/7.R.Hunter and A.H.Robison.International Digital Facsimile Coding Standards.Proceedings of the IEEE,Vol.68,No.7，July,1980，pp8548679/24/202241 of 42第2章 数据无损压缩ENDEND第第2章章 数据无损压缩数据无损压缩
