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

《多媒体技术基础3版2章节数据无损压缩.ppt》由会员分享，可在线阅读，更多相关《多媒体技术基础3版2章节数据无损压缩.ppt（42页珍藏版）》请在三一文库上搜索。

1、多媒体技术基础(第3版) 第2章 数据无损压缩 林福宗 清华大学 计算机科学与技术系 2008年9月 *2008-07-01 1 第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算法 参考文献和站点 Date22章 数据无损压缩 2.0 数据无

2、损压缩概述 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

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

4、夫曼编码(Huffman coding ) 算术编码(arithmetic coding) 行程长度编码(run-length coding) 词典编码(dictionary coding) Date42章 数据无损压缩 2.0 数据无损压缩概述(续2) nThe Father of Information Theory Claude Elwood Shannon Born: 30 April 1916 in Gaylord, Michigan, USA Died: 24 Feb 2001 in Medford, Massachusetts, USA http:/www.bell- n信息论之

5、父介绍 Date52章 数据无损压缩 2.0 数据无损压缩概述(续3) nClaude Shannon The founding father of electronic communications age；American mathematical engineer In 19361940, MIT: nMasters thesis, A symbolic analysis of relay and switching circuits nDoctoral thesis: on theoretical genetics In 1948: nA mathematical theory of

6、communication, landmark, climax (An important feature of Shannons theory: concept of entropy ) Date62章 数据无损压缩 2.1 数据的冗余 n冗余概念 人为冗余 n在信息处理系统中，使用两台计算机做同样的工作是提 高系统可靠性的一种措施 n在数据存储和传输中，为了检测和恢复在数据存储或数 据传输过程中出现的错误，根据使用的算法的要求，在 数据存储或数据传输之前把额外的数据添加到用户数据 中，这个额外的数据就是冗余数据 视听冗余 n由于人的视觉系统和听觉系统的局限性，在图像数据和 声音数据中，有些

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

8、 nHart (hartley)：用于以10为底的对数 Date82章 数据无损压缩 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、决策量 Date92章 数据无损压缩 2.1 数据的冗余(续3) n熵(entropy) 按照香农(Shannon)的理论，在有限的互斥和联合穷举事件 的集合中，熵为事件的信息量的平均值，也称事件的平均 信息量(mean information content) 用数学表示为 Date102章 数据无损压缩 2.1 数据的冗余(续4) n数据的冗余量 Date112章 数据无损压缩 2.2 统计编码 n统计编码 给已知统计信息的符号分配代码的数据无损压缩方 法 n编码方法 香农-范诺编码 霍夫曼编码 算术编码 n编码特性 香农-范诺编码和霍夫曼编码的原理相同，都是根据 符号集中各个符号出现的频

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

11、范诺(Shannon- Fano)编码法 Date132章 数据无损压缩 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 符号在图像中出现的数目 符号ABCDE 出现的次数157765 出现的概率15/407/407/406/405/40 Date142章 数据无损

12、压缩 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 Date152章 数据无损压缩 2.2.1 香农-范诺编码(续2) (2) 符号编码

13、 对每个符号进行编码时采用“从上到下”的方法。 首先按照符号出现的频度或概率排序，如A，B， C，D和E，见表2-2。然后使用递归方法分成两个 部分，每一部分具有近似相同的次数，如图2-1所 示 Date162章 数据无损压缩 2.2.1 香农-范诺编码(续3) （3）压缩比的实际值 按照这种方法进行编码需要的总位数为 30+14+14+18+1591，实际的压缩比为 120:911.32 : 1 图2-1 香农-范诺算法编码举 例 Date172章 数据无损压缩 2.2.2 统计编码霍夫曼编码 n霍夫曼编码(Huffman coding) 霍夫曼(D.A. Huffman)在1952年提出和

14、描述 的“从下到上”的熵编码方法 根据给定数据集中各元素所出现的频率来压 缩数据的一种统计压缩编码方法。这些元素 (如字母)出现的次数越多，其编码的位数就 越少 广泛用在JPEG, MPEG, H.26X等各种信息 编码标准中 Date182章 数据无损压缩 2.2.2 霍夫曼编码 Case Study 1 n霍夫曼编码举例1 现有一个由5个不同符号组成的30个符号的 字符串： BABACACADADABBCBABEBEDDABEEEBB 计算 (1) 该字符串的霍夫曼码 (2) 该字符串的熵 (3) 该字符串的平均码长 (4) 编码前后的压缩比 Date192章 数据无损压缩 2.2.2 霍

15、夫曼编码 Case Study 1 (续1) 符号出现的次数 log2(1/pi ） 分配的代码需要的位数 B101.585? A81.907? C33.322? D42.907? E52.585? 合计30 符号出现的概率 Date202章 数据无损压缩 2.2.2 霍夫曼编码 Case Study 1 (续2) (1) 计算该字符串的霍夫曼码 步骤：按照符号出现概率大小的顺序对符号进行排序 步骤：把概率最小的两个符号组成一个节点P1 步骤：重复步骤，得到节点P2，P3，P4， PN，形成一棵树，其中的PN称为根节点 步骤：从根节点PN开始到每个符号的树叶，从上到 下 标上0(上枝)和1(下

16、枝)，至于哪个为1哪个为0 则 无关紧要，但通常把概率大的标成1，概率小 的 标成0 步骤：从根节点PN开始顺着树枝到每个叶子分别写 出 每个符号的代码 Date212章 数据无损压缩 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 ) Date222章 数据无损压缩 2.2.2 霍夫曼编码 Case Study 1 (续4) 符号出现的次数log2(1

17、/pi）分配的代码需要的位数 B101.5851120 A81.9071016 C33.3220109 D42.90701112 E52.5850010 合计301.067 30个字符组成的字符串需要67位 5个符号的代码 Date232章 数据无损压缩 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 (

18、8lg8 10lg10 3lg3 4 lg4 5 lg5) / (30log22) = ( 44.313624.5592)/ 9.0308 2.1874 (Sh) Date242章 数据无损压缩 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位 Date252章 数据无损压缩 2.2.2 霍夫曼编码 Case Stu

19、dy 2 n霍夫曼编码举例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) 编码效率 Date262章 数据无损压缩 2.2.2 霍夫曼编码 Case Study 2 (续1) Date272章 数据无损压缩 2.2.2 霍夫曼编码 Case S

20、tudy 2 (续2) Average length per symbol (before coding): (2) Entropy: (3) Average length per symbol (with Huffman coding): (4) Efficiency of the code: Date282章 数据无损压缩 2.2.3 统计编码算术编码 n算术编码(arithmetic coding) 给已知统计信息的符号分配代码的数据无损 压缩技术 基本思想是用0和1之间的一个数值范围表示 输入流中的一个字符，而不是给输入流中的 每个字符分别指定一个码字 实质上是为整个输入字符流分配一个

21、“码字” ，因此它的编码效率可接近于熵 Date292章 数据无损压缩 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 进行算术编码 Date302章 数据无损压缩 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.3的信源符号概率和初始编码间隔 n初始化 根据信源符号的概率把间隔0, 1)分成如表 2-

22、4所示的4个子间隔：0, 0.1), 0.1, 0.5), 0.5, 0.7), 0.7, 1)。其中x, y)的表示半开放 间隔，即包含x不包含y，x称为低边界或左 边界，y称为高边界或右边界 Date312章 数据无损压缩 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) 依

23、此类推 消息的编码输出可以是最后一个间隔中的任意数 n整个编码过程如图2-3所示 n编码和译码的全过程分别见表2-5和表2-6 Date322章 数据无损压缩 2.2.3 算术编码举例(续3) 图2-3 例2.3的算术编码过程 Date332章 数据无损压缩 2.2.3 算术编码举例(续4) Date342章 数据无损压缩 2.2.3 算术编码举例(续5) Date352章 数据无损压缩 2.3 RLE编码 n行程长度编码(Run-Length Coding) 一种无损压缩数据编码技术，它利用重复的数据单 元有相同的数值这一特点对数据进行压缩。对相同 的数值只编码一次，同时计算出相同值重复出现

24、的 次数。在JPEG，MPEG，H.261和H.263等压缩方法中 ，RLE用来对图像数据变换和量化后的系数进行编 码 例: 假设有一幅灰度图像第n行的像素值如图2-5所 示。用RLE编码方法得到的代码为：80315084180 图2-5 RLE编码概念 Date362章 数据无损压缩 2.3 RLE编码(续) nAssumption: Long sequences of identical symbols. Example, Date372章 数据无损压缩 2.4 词典编码 n词典编码(dictionary coding) 文本中的词用它在词典中表示位置的号码代替的 一种无损数据压缩方法。采

25、用静态词典编码技术 时，编码器需要事先构造词典，解码器要事先知 道词典。采用动态辞典编码技术时, 编码器将从 被压缩的文本中自动导出词典，解码器解码时边 解码边构造解码词典 两种类型的编码算法 n具体算法 LZ77算法 LZSS算法 LZ78算法 LZW算法 (当作课外阅读) Date382章 数据无损压缩 2.4 词典编码(续1) n第一类编码算法 用已经出现过的字符串替代重复的部分 编码器的输出仅仅是指向早期出现过的字 符串的“指针” 图2-6 第一类词典编码概念 Date392章 数据无损压缩 2.4 词典编码(续2) n第二类编码算法 从输入的数据中创建一个“短语词典(dictiona

26、ry of the phrases)” 编码器输出词典中的短语“索引号”，而不是短语 图2-7 第二类词典编码概念 Date402章 数据无损压缩 第2章 数据无损压缩 n参考文献和站点 David Salomon, Data Compression, ISBN 0-387-40697-2, Third Edition, Springer-Verlag, 2004 Data Compression Reference Center， http:/compress.rasip.fer.hr/index_menu.htm Timothy C.Bell, John G.Cleary, Ian H.W

27、itten. Text Compression. Prentice-Hall, Inc.,1990 Ziv, J. and Lempel, A A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory, May 1977 Terry A. Welch, A Technique for High-Performance Data Compression. Computer, June 1984 Nelson, 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 Date412章 数据无损压缩 END 第2章 数据无损压缩 *2008-07-01 42