第2章数据无损压缩

1、2008-07-01 1 多媒体技术教程多媒体技术教程 第第2章章 数据无损压缩数据无损压缩 2 of 37 第第2章章 数据无损压缩目录数据无损压缩目录 n2.1 数据的冗余数据的冗余 2.1.1 冗余概念 2.1.2 决策量 2.1.3 信息量 2.1.4 熵 2.1.5 数据冗余量 n2.2 统计编码统计编码 2.2.1 香农-范诺编码 2.2.2 霍夫曼编码 2.2.3 算术编码 n2.3 RLE编码编码 n2.4 词典编码词典编码 2.4.1 词典编码的思想 2.4.2 LZ77算法 2.4.3 LZSS算法 2.4.4 LZ78算法 2.4.5 LZW算法 n参考文献和站点参考文献

2、和站点 3 of 37 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

3、 data redundancy) n根据人的视觉系统特性(Based on human visual system) 4 of 37 2.0 数据无损压缩概述数据无损压缩概述(续续1) n数据无损压缩的理论数据无损压缩的理论信息论信息论(information theory) 1948年创建的数学理论的一个分支学科，研究信息的编码、 传输和存储 该术语源于Claude Shannon (香农)发表的“A Mathematical Theory of Communication”论文题目，提议用二进制数据对信 息进行编码 最初只应用于通信工程领域，后来扩展到包括计算在内的其 他多个领域，如信息

4、的存储、信息的检索等。在通信方面， 主要研究数据量、传输速率、信道容量、传输正确率等问题。 n数据无损压缩的方法数据无损压缩的方法 霍夫曼编码(Huffman coding ) 算术编码(arithmetic coding) 行程长度编码(run-length coding) 词典编码(dictionary coding) 5 of 37 2.0 数据无损压缩概述数据无损压缩概述(续续2) nThe Father of Information Theory Claude Elwood Shannon Born: 30 April 1916 in Gaylord, Michigan, USA D

5、ied: 24 Feb 2001 in Medford, Massachusetts, USA http:/www.bell- n信息论之父介绍信息论之父介绍 6 of 37 2.1 数据的冗余数据的冗余 n冗余概念冗余概念 人为冗余 n在信息处理系统中，使用两台计算机做同样的工作是提高 系统可靠性的一种措施-冗余设备冗余设备 n在数据存储和传输中，为了检测和恢复在数据存储或数据 传输过程中出现的错误，根据使用的算法的要求，在数据 存储或数据传输之前把额外的数据添加到用户数据中，这 个额外的数据就是冗余数据冗余数据-检错码，纠错码检错码，纠错码 视听冗余 n由于人的视觉系统和听觉系统的局限性，

6、在图像数据和声 音数据中，有些数据确实是多余的，使用算法将其去掉后 并不会丢失实质性的信息或含义，对理解数据表达的信息 几乎没有影响 数据冗余 n不考虑数据来源时，单纯数据集中也可能存在多余的数据， 去掉这些多余数据并不会丢失任何信息，这种冗余称为数 据冗余，而且还可定量表达 7 of 37 2.1 数据的冗余数据的冗余(续续1) n决策量决策量(decision content) 在有限数目的互斥事件集合中，决策量是事 件数的对数值 在数学上表示为 H0=log(n) 其中，n是事件数 决策量的单位由对数的底数决定 nSh (Shannon): 用于以2为底的对数 nNat (natural

7、 unit): 用于以e为底的对数 nHart (hartley)：用于以10为底的对数 8 of 37 2.1 数据的冗余数据的冗余(续续2) n信息量信息量(information content) 具有确定概率事件的信息的定量度量 在数学上定义为 其中， 是事件出现的概率 一个等概率事件的集合，每个事件的信息量等 于该集合的决策量 22 ( )log 1/( )log( )I xp xp x ( )p x 9 of 37 举例：假设假设X=a,b,c是由是由3个事件构成的集合，个事件构成的集合，p(a)=0.5， p(b)=0.25，p(b)=0.25分别是事件分别是事件a, b和和c出

8、现的概率，这些事出现的概率，这些事 件的信息量分别为，件的信息量分别为， I(a)=log2(1/0.50)=1 sh I(b)=log2(1/0.25)=2 sh I(c)=log2(1/0.25)=2 sh p(a)=0.5是符号a 在I中出现的概率； log2(1/ p(a)表示包含在I 中的信息量，也就是编码 a所需要的位数。 例如例如: : 一幅用一幅用256256级灰度表示的图像，如果每一个象素级灰度表示的图像，如果每一个象素 点灰度的概率均为点灰度的概率均为P=1/256 1/256 ，编码每一个象素点就需，编码每一个象素点就需 要要8 8位。位。 10 of 37 2.1 数据

9、的冗余数据的冗余(续续3) n熵熵(entropy) 按照香农(Shannon)的理论，在有限的互斥和联合穷举事件的 集合中，熵为事件的信息量的平均值，也称事件的平均信息 量(mean information content) 用数学表示为 熵熵-最佳平均编码位数最佳平均编码位数 11 of 37 2.1 数据的冗余数据的冗余(续续4) n数据的冗余量数据的冗余量 12 of 37 2.2 统计编码统计编码 n统计编码统计编码 给已知统计信息的符号分配代码的数据无损压缩方法 n编码方法编码方法 香农-范诺编码 霍夫曼编码 算术编码 n编码特性编码特性 香农-范诺编码和霍夫曼编码的原理相同，都是

10、根据符 号集中各个符号出现的频繁程度来编码，出现次数越出现次数越 多的符号，给它分配的代码位数越少多的符号，给它分配的代码位数越少 算术编码使用0和1之间的实数的间隔长度代表概率大 小，概率越大间隔越长，编码效率可接近于熵 13 of 37 2.2.1 统计编码统计编码香农香农-范诺编码范诺编码 n香农香农-范诺编码范诺编码(ShannonFano coding) 在香农的源编码理论中，熵的大小表示非冗余的不 可压缩的信息量 在计算熵时，如果对数的底数用2，熵的单位就用 “香农(Sh)”，也称“位(bit)” 。“位”是1948年 Shannon首次使用的术语。例如 最早阐述和实现“从上到下”

11、的熵编码方法的人是 Shannon(1948年)和Fano(1949年)，因此称为香农-范 诺(Shannon- Fano)编码法 14 of 37 2.2.1 香农香农-范诺编码范诺编码 n香农香农-范诺编码举例范诺编码举例 有一幅40个像素组成的灰度图像，灰度共有5级，分别用符号 A，B，C，D和E表示。40个像素中出现灰度A的像素数有15 个，出现灰度B的像素数有7个，出现灰度C的像素数有7个， 其余情况见表2-1 n(1) 计算该图像可能获得的压缩比的理论值 n(2) 对5个符号进行编码 n(3) 计算该图像可能获得的压缩比的实际值 表表2-1 符号在图像中出现的数目符号在图像中出现的

12、数目 符号ABCDE 出现的次数157765 出现的概率15/407/407/406/405/40 15 of 37 符号符号ABCDE 出现的次数出现的次数157765 按照仙农理论，这幅图像的熵熵为 H(x) = (15/40)loglog2 2(40/15) + (7/40)loglog2 2(40/7) + + (5/40) loglog2 2(40/5) =2.196 这就是说每个符号用2.196位表示，40个象素需用87.84位。 因此在理论上，这幅图像的的压缩比为因此在理论上，这幅图像的的压缩比为 120:87.841.37:1， 实际上就是实际上就是 3:2.1961.37 按

13、照常规的编码方法，表示5个符号最少需要3位，这就意味每个像素 用3位，编码这幅图像总共需要120位。 16 of 37 2.2.1 香农香农-范诺编码范诺编码(续续2) (2) 符号编码符号编码 对每个符号进行编码时采用“从上到下从上到下”的方法。 首先按照符号出现的频度或概率排序，如A，B，C， D和E，见表2-2。然后使用递归方法分成两个部分， 每一部分具有近似相同的次数，如图所示 17 of 37 采用从上到下的方法进行编码。首先按照符号出现的频度或概率排序，例采用从上到下的方法进行编码。首先按照符号出现的频度或概率排序，例 如如A A、B B、C C、D D和和E E，然后使用递归方法

14、分成两个部分，每一部分具有近似，然后使用递归方法分成两个部分，每一部分具有近似 相同的次数相同的次数 符号符号 AB C D E 出现的次出现的次 数数 15 7 7 6 5 ABC DE 按照这种方法进行编码得到的总位数为 15*2+7*2+7*2+6*3+5*3=91实际的压缩比为120:911.32 : 1 01 01 01 0 1 A 00 B 01 C 10 D 110 E 111 18 of 37 2.2.2 统计编码统计编码霍夫曼编码霍夫曼编码 n霍夫曼编码霍夫曼编码(Huffman coding) 霍夫曼(D.A. Huffman)在1952年提出和描述的“从下 到上”的熵编码

15、方法 根据给定数据集中各元素所出现的频率来压缩数据的 一种统计压缩编码方法。这些元素(如字母)出现的次 数越多，其编码的位数就越少 广泛用在JPEG, MPEG, H.26X等各种信息编码标准中 19 of 37 即从下到上的编码方法，编码步骤：即从下到上的编码方法，编码步骤： ：初始化，根据符号概率的大小按由大到小顺序对符号进行排序。 ：把概率最小的两个符号组成一个节点P1 ：重复步骤，得到节点P2，P3，P4，PN，形成一棵树，其中 的PN称为根节点 ：从根节点PN开始到每个符号的树叶，从上到标上0(上枝)和1(下 枝)，至于哪个为1哪个为0则无关紧要，最后的结果只是分配的 代码不同，代码

16、的平均长度是相同的。 ：从根节点PN开始顺着树枝到每个叶子分别写出每个符号的代码 次数次数 概率概率 A 15 0.375 B70.175 C70.175 D60.150 E50.125 0.275 0.35 0.625 0 1 0 1 0 1 0 1 0 100 101 110 111 编码得到的总位数为1*15+3*(7+7+6+5)=90 20 of 37 2.2.2 霍夫曼编码 Case Study 1 n霍夫曼编码举例霍夫曼编码举例1 现有一个由5个不同符号组成的30个符号的字符串： BABACACADADABBCBABEBEDDABEEEBB 计算 (1) 该字符串的霍夫曼码 (2

17、) 该字符串的熵 (3) 该字符串的平均码长 (4) 编码前后的压缩比 21 of 37 2.2.2 霍夫曼编码 Case Study 1 (续续1) 符号 出现的 次数 概率log2(1/pi）分配的代码需要的位数 B100.331.585? A80.271.907? C30.13.322? D40.132.907? E50.172.585? 合计30 符号出现的概率符号出现的概率 22 of 37 2.2.2 霍夫曼编码霍夫曼编码 Case Study 1 (续续3) 符号符号 B (10) A (8) E (5) D (4) C (3)P1 (0.23) P2 (0.4) P3 (0.6

18、) P4 (1.0) 0 1 1 0 1 0 1 0 代码代码 B(11) A(10) E(00) D(011) C(010) 0.33 0.27 0.17 0.13 0.1 23 of 37 2.2.2 霍夫曼编码霍夫曼编码 Case Study 1 (续续4) 符号出现的次数log2(1/pi）分配的代码需要的位数 B101.5851120 A81.9071016 C33.3220109 D42.90701112 E52.5850010 合计301.067 30个字符组成的字符串需要个字符组成的字符串需要67位位 5个符号的代码 24 of 37 2.2.2 霍夫曼编码霍夫曼编码 Case

19、 Study 1 (续续5) 2 11 ()( ) ( )( )log( ) nn iiii ii H Xp x I xp xp x (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 4lg4 5 lg5) / (30log22) = ( 44.313624.5592)/ 9.0308 2.1874 (Sh) 符 号 出现的 次数 概率log2(1/pi

20、） B100.331.585 A80.271.907 C30.13.322 D40.132.907 E50.172.585 =0.33*1.585+0.27*1.907+0.1*3.322+0.13*2.907+0.17*2.585 =2.1876 25 of 37 2.2.2 霍夫曼编码霍夫曼编码 Case Study 1 (续续6) (3) 计算该字符串的平均码长计算该字符串的平均码长 平均码长： (28210333425)/30 2.233 位/符号 压缩比压缩比: 90/67=1.34:1 1 ( ) N ii i ll p l 平均码长：平均码长：67/30=2.233位位 (4)

21、计算编码前后的压缩比计算编码前后的压缩比 n编码前：5个符号需3位，30个字符，需要90 位 n编码后：共67位 26 of 37 2.2.3 统计编码统计编码算术编码算术编码 n算术编码算术编码(arithmetic coding) 给已知统计信息的符号分配代码的数据无损压缩技术 基本思想是用0和1之间的一个数值范围表示输入流中 的一个字符，而不是给输入流中的每个字符分别指定 一个码字 实质上是为整个输入字符流分配一个“码字”，因此 它的编码效率可接近于熵 27 of 37 2.2.3 算术编码举例算术编码举例 n例例2.3（取自教材）（取自教材） 假设信源符号为00, 01, 10, 11

22、，它们的概率分别为 0.1, 0.4, 0.2, 0.3 对二进制消息序列10 00 11 00 10 11 01 进行算术编码 (1)初始化初始化 根据信源符号的概率把间隔0, 1)分成如表2-4所示的4个子间 隔：0, 0.1), 0.1, 0.5), 0.5, 0.7), 0.7, 1)。其中x, y)的表示半开 放间隔 符号00011011 概率0.3 初始编码间隔0, 0.1)0.1, 0.5)0.5, 0.7)0.7, 1 28 of 37 算术编码中，消息用算术编码中，消息用0 0到到1 1之间的实数进行编码之间的实数进行编码 两个基本的参数：两个基本的参数：符

23、号的概率和它的和它的编码间隔。 信源符号信源符号 00011011 概率概率0.3 初始编码间隔初始编码间隔0, 0.1)0, 0.1)0.1, 0.5)0.1, 0.5)0.5, 0.7)0.5, 0.7)0.7, 1) 0.7, 1) 如果二进制消息序列的输入为：10 00 11 00 10 11 01。 编码时首先输入的符号是编码时首先输入的符号是1010, ,找到它的编码范围是找到它的编码范围是0.5, 0.7), 0.5, 0.7), d=0.2d=0.2 输入的符号输入的符号00,00,编码范围是编码范围是0, 0.1)0, 0.1) low=0.5+ low=0

24、.5+d d* *0 0=0.5+=0.5+0.20.2* *0 0=0.5=0.5 high=0.5+ high=0.5+d d* *0.10.1=0.5+=0.5+0.20.2* *0.10.1=0.52 =0.52 输出编码为输出编码为0.50.5，0.520.52） d=high-low=0.02d=high-low=0.02 3 3） 输入的符号输入的符号11,11,编码范围是编码范围是0.7, 1)0.7, 1) low=0.5+ low=0.5+0.020.02* *0.70.7=0.514=0.514 high=0.5+ high=0.5+0.020.02* *1 1=0.52

25、 =0.52 输出编码为输出编码为0.5140.514，0.520.52） d=0.006d=0.006 29 of 37 4) 输入的符号输入的符号00,00,编码范围是编码范围是0, 0.1)0, 0.1) low=0.514+ low=0.514+0.0060.006* *0 0=0.514=0.514 high=0.514+ high=0.514+0.0060.006* *0.10.1=0.5146 =0.5146 输出编码为输出编码为0.5140.514，0.51460.5146） d=0.0006d=0.0006 5) 输入的符号输入的符号10,10,编码范围是编码范围是0.5,

26、0.7)0.5, 0.7) low=0.514+ low=0.514+0.00060.0006* *0.50.5=0.5143=0.5143 high=0.514+ high=0.514+0.00060.0006* *0.70.7=0.51442 =0.51442 输出编码为输出编码为0.51430.5143，0.514420.51442） d=0.00012d=0.00012 依次类推依次类推 注意注意: :消息的编码输出可以是最后一个间隔中的任意数消息的编码输出可以是最后一个间隔中的任意数 30 of 37 31 of 37 32 of 37 在算术编码中需要注意的几个问题：在算术编码中需

27、要注意的几个问题： 运算中出现溢出是一个明显的问题， 算术编码器对整个消息只产生一个码字，在间隔0, 1)中的一个实数，因此译 码器在接受到表示这个实数的所有位之前不能进行译码。 如果有一位发生错误就会导致整个消息译错。 静态算术编码-信源符号的概率是固定的。 自适应算术编码中-信源符号的概率根据编码时符号出现的频繁程度动态地 进行修改，在编码期间估算信源符号概率的过程叫做建模。 33 of 37 2.3 RLE编码编码 n行程长度编码(Run-Length Coding) 一种无损压缩数据编码技术，它利用重复的数据单元有相同的数值这一 特点对数据进行压缩。对相同的数值只编码一次，同时计算出相同值重 复出现的次数行程长度行程长度。在JPEG