1、多媒体技术基础(第3版)第2章 数据无损压缩,林福宗清华大学 计算机科学与技术系2008年9月,2018年10月9日,第2章 数据无损压缩,2 of 42,第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算法参考文献和站点,2018年10月9日,第2章 数据无损压缩,3 of
2、 42,2.0 数据无损压缩概述,数据可被压缩的依据数据本身存在冗余听觉系统的敏感度有限视觉系统的敏感度有限三种多媒体数据类型文字 (text)数据无损压缩根据数据本身的冗余(Based on data redundancy)声音(audio)数据有损压缩根据数据本身的冗余(Based on data redundancy)根据人的听觉系统特性( Based on human hearing system) 图像(image)/视像(video) 数据有损压缩根据数据本身的冗余(Based on data redundancy)根据人的视觉系统特性(Based on human visual
3、system),2018年10月9日,第2章 数据无损压缩,4 of 42,2.0 数据无损压缩概述(续1),数据无损压缩的理论信息论(information theory) 1948年创建的数学理论的一个分支学科，研究信息的编码、传输和存储该术语源于Claude Shannon (香农)发表的“A Mathematical Theory of Communication”论文题目，提议用二进制数据对信息进行编码最初只应用于通信工程领域，后来扩展到包括计算在内的其他多个领域，如信息的存储、信息的检索等。在通信方面，主要研究数据量、传输速率、信道容量、传输正确率等问题。 数据无损压缩的方法霍夫曼
4、编码(Huffman coding )算术编码(arithmetic coding)行程长度编码(run-length coding)词典编码(dictionary coding),2018年10月9日,第2章 数据无损压缩,5 of 42,2.0 数据无损压缩概述(续2),The Father of Information TheoryClaude Elwood ShannonBorn: 30 April 1916 in Gaylord, Michigan, USADied: 24 Feb 2001 in Medford, Massachusetts, USA,http:/www.bell-
5、 数据无损压缩,6 of 42,2.0 数据无损压缩概述(续3),Claude Shannon The founding father of electronic communications age；American mathematical engineerIn 19361940, MIT: Masters thesis, A symbolic analysis of relay and switching circuitsDoctoral thesis: on theoretical geneticsIn 1948: A mathematical theory of communicat
6、ion, landmark, climax(An important feature of Shannons theory: concept of entropy ),2018年10月9日,第2章 数据无损压缩,7 of 42,2.1 数据的冗余,冗余概念人为冗余在信息处理系统中，使用两台计算机做同样的工作是提高系统可靠性的一种措施在数据存储和传输中，为了检测和恢复在数据存储或数据传输过程中出现的错误，根据使用的算法的要求，在数据存储或数据传输之前把额外的数据添加到用户数据中，这个额外的数据就是冗余数据视听冗余由于人的视觉系统和听觉系统的局限性，在图像数据和声音数据中，有些数据确实是多余的，使
7、用算法将其去掉后并不会丢失实质性的信息或含义，对理解数据表达的信息几乎没有影响数据冗余不考虑数据来源时，单纯数据集中也可能存在多余的数据，去掉这些多余数据并不会丢失任何信息，这种冗余称为数据冗余，而且还可定量表达,2018年10月9日,第2章 数据无损压缩,8 of 42,2.1 数据的冗余(续1),决策量(decision content)在有限数目的互斥事件集合中，决策量是事件数的对数值在数学上表示为 H0=log(n) 其中，n是事件数决策量的单位由对数的底数决定Sh (Shannon): 用于以2为底的对数Nat (natural unit): 用于以e为底的对数Hart (hartl
8、ey)：用于以10为底的对数,2018年10月9日,第2章 数据无损压缩,9 of 42,2.1 数据的冗余(续2),信息量(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一个等概率事件的集合，每个事件的信息量等于该集合的决策量,2
9、018年10月9日,第2章 数据无损压缩,10 of 42,2.1 数据的冗余(续3),熵(entropy)按照香农(Shannon)的理论，在有限的互斥和联合穷举事件的集合中，熵为事件的信息量的平均值，也称事件的平均信息量(mean information content) 用数学表示为,2018年10月9日,第2章 数据无损压缩,11 of 42,2.1 数据的冗余(续4),数据的冗余量,2018年10月9日,第2章 数据无损压缩,12 of 42,2.2 统计编码,统计编码给已知统计信息的符号分配代码的数据无损压缩方法编码方法香农-范诺编码霍夫曼编码算术编码编码特性香农-范诺编码和霍夫曼
10、编码的原理相同，都是根据符号集中各个符号出现的频繁程度来编码，出现次数越多的符号，给它分配的代码位数越少算术编码使用0和1之间的实数的间隔长度代表概率大小，概率越大间隔越长，编码效率可接近于熵,2018年10月9日,第2章 数据无损压缩,13 of 42,2.2.1 统计编码香农-范诺编码,香农-范诺编码(ShannonFano coding)在香农的源编码理论中，熵的大小表示非冗余的不可压缩的信息量在计算熵时，如果对数的底数用2，熵的单位就用“香农(Sh)”，也称“位(bit)” 。“位”是1948年Shannon首次使用的术语。例如,最早阐述和实现“从上到下”的熵编码方法的人是Shanno
11、n(1948年)和Fano(1949年)，因此称为香农-范诺(Shannon- Fano)编码法,2018年10月9日,第2章 数据无损压缩,14 of 42,2.2.1 香农-范诺编码,香农-范诺编码举例 有一幅40个像素组成的灰度图像，灰度共有5级，分别用符号A，B，C，D和E表示。40个像素中出现灰度A的像素数有15个，出现灰度B的像素数有7个，出现灰度C的像素数有7个，其余情况见表2-1(1) 计算该图像可能获得的压缩比的理论值(2) 对5个符号进行编码(3) 计算该图像可能获得的压缩比的实际值表2-1 符号在图像中出现的数目,2018年10月9日,第2章 数据无损压缩,15 of 4
12、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,2018年10月9日,第2章 数据无损压缩,16 of 42,2.2.1 香农-范诺编码(续2),(2
13、) 符号编码对每个符号进行编码时采用“从上到下”的方法。首先按照符号出现的频度或概率排序，如A，B，C，D和E，见表2-2。然后使用递归方法分成两个部分，每一部分具有近似相同的次数，如图2-1所示,2018年10月9日,第2章 数据无损压缩,17 of 42,2.2.1 香农-范诺编码(续3),（3）压缩比的实际值按照这种方法进行编码需要的总位数为30+14+14+18+1591，实际的压缩比为120:911.32 : 1,图2-1 香农-范诺算法编码举例,2018年10月9日,第2章 数据无损压缩,18 of 42,2.2.2 统计编码霍夫曼编码,霍夫曼编码(Huffman coding)霍
14、夫曼(D.A. Huffman)在1952年提出和描述的“从下到上”的熵编码方法根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少广泛用在JPEG, MPEG, H.26X等各种信息编码标准中,2018年10月9日,第2章 数据无损压缩,19 of 42,2.2.2 霍夫曼编码 Case Study 1,霍夫曼编码举例1现有一个由5个不同符号组成的30个符号的字符串：BABACACADADABBCBABEBEDDABEEEBB计算(1) 该字符串的霍夫曼码(2) 该字符串的熵(3) 该字符串的平均码长(4) 编码前后的压缩比
15、,2018年10月9日,第2章 数据无损压缩,20 of 42,2.2.2 霍夫曼编码 Case Study 1 (续1),符号出现的概率,2018年10月9日,第2章 数据无损压缩,21 of 42,2.2.2 霍夫曼编码 Case Study 1 (续2),(1) 计算该字符串的霍夫曼码步骤：按照符号出现概率大小的顺序对符号进行排序步骤：把概率最小的两个符号组成一个节点P1步骤：重复步骤，得到节点P2，P3，P4， PN，形成一棵树，其中的PN称为根节点步骤：从根节点PN开始到每个符号的树叶，从上到下 标上0(上枝)和1(下枝)，至于哪个为1哪个为0则 无关紧要，但通常把概率大的标成1，概
16、率小的 标成0步骤：从根节点PN开始顺着树枝到每个叶子分别写出 每个符号的代码,2018年10月9日,第2章 数据无损压缩,22 of 42,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),0,1,1,0,1,0,1,0,代码B(11)A(10)E(00)D(011)C(010),2018年10月9日,第2章 数据无损压缩,23 of 42,2.2.2 霍夫曼编码 Case Study 1 (续4),30个字符组成的字符串需要67位,5个符号的代码,2018年10
17、月9日,第2章 数据无损压缩,24 of 42,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),2018年10月9日,第2章 数据无损压缩,2
18、5 of 42,2.2.2 霍夫曼编码 Case Study 1 (续6),(3) 计算该字符串的平均码长平均码长： (28210333425)/30 2.233 位/符号,压缩比: 90/67=1.34:1,平均码长：67/30=2.233位,(4) 计算编码前后的压缩比编码前：5个符号需3位，30个字符，需要90位编码后：共67位,2018年10月9日,第2章 数据无损压缩,26 of 42,2.2.2 霍夫曼编码 Case Study 2,霍夫曼编码举例2编码前N = 8 symbols: a,b,c,d,e,f,g,h, 3 bits per symbol (N =23=8)P(a)
19、= 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) 编码效率,2018年10月9日,第2章 数据无损压缩,27 of 42,2.2.2 霍夫曼编码 Case Study 2 (续1),2018年10月9日,第2章 数据无损压缩,28 of 42,2.2.2 霍夫曼编码 Case Study 2 (续2),Average length per symbol (before coding):,(2) Ent
20、ropy:,(3) Average length per symbol (with Huffman coding):,(4) Efficiency of the code:,2018年10月9日,第2章 数据无损压缩,29 of 42,2.2.3 统计编码算术编码,算术编码(arithmetic coding)给已知统计信息的符号分配代码的数据无损压缩技术基本思想是用0和1之间的一个数值范围表示输入流中的一个字符，而不是给输入流中的每个字符分别指定一个码字实质上是为整个输入字符流分配一个“码字”，因此它的编码效率可接近于熵,2018年10月9日,第2章 数据无损压缩,30 of 42,2.2.
21、3 算术编码举例,例2.3（取自教材）假设信源符号为00, 01, 10, 11，它们的概率分别为 0.1, 0.4, 0.2, 0.3 对二进制消息序列10 00 11 00 10 11 01 进行算术编码,2018年10月9日,第2章 数据无损压缩,31 of 42,2.2.3 算术编码举例(续1),表2-4 例2.3的信源符号概率和初始编码间隔,初始化根据信源符号的概率把间隔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称为高边界或右边界,2
22、018年10月9日,第2章 数据无损压缩,32 of 42,2.2.3 算术编码举例(续2),确定符号的编码范围编码时输入第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)依此类推消息的编码输出可以是最后一个间隔中的任意数整个编码过程如图2-3所示编码和译码的全过程分别见表2-5和表2-6,2018年10月9日,第2章 数据无损压缩,33 of 42,2.
23、2.3 算术编码举例(续3),图2-3 例2.3的算术编码过程,2018年10月9日,第2章 数据无损压缩,34 of 42,2.2.3 算术编码举例(续4),2018年10月9日,第2章 数据无损压缩,35 of 42,2.2.3 算术编码举例(续5),2018年10月9日,第2章 数据无损压缩,36 of 42,2.3 RLE编码,行程长度编码(Run-Length Coding)一种无损压缩数据编码技术，它利用重复的数据单元有相同的数值这一特点对数据进行压缩。对相同的数值只编码一次，同时计算出相同值重复出现的次数。在JPEG，MPEG，H.261和H.263等压缩方法中，RLE用来对图像
24、数据变换和量化后的系数进行编码例: 假设有一幅灰度图像第n行的像素值如图2-5所示。用RLE编码方法得到的代码为：80315084180,图2-5 RLE编码概念,2018年10月9日,第2章 数据无损压缩,37 of 42,2.3 RLE编码(续),Assumption:Long sequences of identical symbols.Example,2018年10月9日,第2章 数据无损压缩,38 of 42,2.4 词典编码,词典编码(dictionary coding)文本中的词用它在词典中表示位置的号码代替的一种无损数据压缩方法。采用静态词典编码技术时，编码器需要事先构造词典，
25、解码器要事先知道词典。采用动态辞典编码技术时, 编码器将从被压缩的文本中自动导出词典，解码器解码时边解码边构造解码词典两种类型的编码算法具体算法LZ77算法LZSS算法LZ78算法LZW算法(当作课外阅读),2018年10月9日,第2章 数据无损压缩,39 of 42,2.4 词典编码(续1),第一类编码算法用已经出现过的字符串替代重复的部分 编码器的输出仅仅是指向早期出现过的字符串的“指针”,图2-6 第一类词典编码概念,2018年10月9日,第2章 数据无损压缩,40 of 42,2.4 词典编码(续2),第二类编码算法从输入的数据中创建一个“短语词典(dictionary of the
26、phrases)” 编码器输出词典中的短语“索引号”，而不是短语,图2-7 第二类词典编码概念,2018年10月9日,第2章 数据无损压缩,41 of 42,第2章 数据无损压缩,参考文献和站点David Salomon, Data Compression, ISBN 0-387-40697-2, Third Edition, Springer-Verlag, 2004Data Compression Reference Center，http:/compress.rasip.fer.hr/index_menu.htmTimothy C.Bell, John G.Cleary, Ian H.W
27、itten. Text Compression. Prentice-Hall, Inc.,1990Ziv, J. and Lempel, A. A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory, May 1977Terry A. Welch, A Technique for High-Performance Data Compression. Computer, June 1984Nelson, M.R. LZW Data Compression. Dr. Dobbs Journal, October 1989，http:/marknelson.us/1989/10/01/lzw-data-compression/ R.Hunter and A.H.Robison. International Digital Facsimile Coding Standards. Proceedings of the IEEE, Vol.68, No.7，July, 1980，pp854867,END,第2章 数据无损压缩,
