chp2 数据无损压缩

2020-03-01 141浏览

1.多媒体技术基础 ( 第 3 版 ) 第 2 章数据无损压缩
2.第 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 算术编码 Tuesday, May 14, 2019 2.3 RLE 编码 2.4 词典编码 2.4.1 词典编码的思想 2.4.2 LZ77 算法 2.4.3 LZSS 算法 2.4.4 LZ78 算法 2.4.5 LZW 算法参考文献和站点第 2 章数据无损压缩 2 of 42
3.2.0 数据无损压缩概述  数据可被压缩的依据     数据本身存在冗余听觉系统的敏感度有限视觉系统的敏感度有限三种多媒体数据类型  文字 (text) 数据——无损压缩   声音 (audio) 数据——有损压缩    根据数据本身的冗余 (Based on data redundancy) 根据数据本身的冗余 (Based on data redundancy) 根据人的听觉系统特性 ( Based on human hearing system) 图像 (image)/ 视像 (video) 数据——有损压缩   根据数据本身的冗余 (Based on data redundancy) 根据人的视觉系统特性 (Based on human visual system) Tuesday, May 14, 2019 第 2 章数据无损压缩 3 of 42
4.2.0 数据无损压缩概述 ( 续 1)  数据无损压缩的理论 ——信息论 (information theory)     1948 年创创建的数学理创创创创创创的一个分支学科，研究信息的创创创创创创创创创创创创创创创、创创创和存创创该术语源于 Claude Shannon ( 香农 ) 发表的“ A Mathematical Theory of Communication” 论文题目，提议用二进制数据对信息进行编码最初只应用于通信工程领域，后来扩展到包括计算在内的其他多个领域，如信息的存储、信息的检索等。在通信方面，主要研究数据量、传输速率、信道容量、传输正确率等问题。数据无损压缩的方法      霍夫曼编 (Huffman 码 coding ) 算术编码 (arithmetic coding) 行程长度编码 (run-length coding) 词典编码 (dictionary coding) …… Tuesday, May 14, 2019 第 2 章数据无损压缩 4 of 42
5.2.0 数据无损压缩概述 ( 续 2)  信息论之父介绍  The Father of Information Theory —— Claude Elwood Shannon  Born:30 April 1916 in Gaylord, Michigan, USADied:24 Feb 2001 in Medford, Massachusetts, USAhttp://www.bell-labs.com/news/2001/february/26/1.htmlTuesday, May 14, 2019 第 2 章数据无损压缩 5 of 42
6.2.0 数据无损压缩概述 ( 续 3)  Claude Shannon ——The founding father of electronic communications age ； American mathematical engineer  In 1936~1940,MIT:   Master's thesis, A symbolic analysis of relay and switching circuits Doctoralthesis:on theoretical genetics In 1948: A mathematical theory of communication, landmark, climax (An important feature of Shannon'stheory:concept of entropy )  Tuesday, May 14, 2019 第 2 章数据无损压缩 6 of 42
7.2.1 数据的冗余  冗余概念  人为冗余    视听冗余   在信息处理系统中，使用两台计算机做同样的工作是提高系统可靠性的一种措施在数据存储和传输中，为了检测和恢复在数据存储或数据传输过程中出现的错误，根据使用的算法的要求，在数据存储或数据传输之前把额外的数据添加到用户数据中，这个额外的数据就是冗余数据由于人的视觉系统和听觉系统的局限性，在图像数据和声音数据中，有些数据确实是多余的，使用算法将其去掉后并不会丢失实质性的信息或含义，对理解数据表达的信息几乎没有影响数据冗余  不考虑数据来源时，单纯数据集中也可能存在多余的数据，去掉这些多余数据并不会丢失任何信息，这种冗余称为数据冗余，而且还可定量表达 Tuesday, May 14, 2019 第 2 章数据无损压缩 7 of 42
8.2.1 数据的冗余 ( 续 1)  决策量 (decision content)   在有限数目的互斥事件集合中，决策量是事件数的对数值在数学上表示为 H0=log(n)  其中， n 是事件数决策量的单位由对数的底数决定    Sh (Shannon): 用于以 2 为底的对数 Nat (natural unit): 用于以 e 为底的对数 Hart (hartley) ：用于以 10 为底的对数 Tuesday, May 14, 2019 第 2 章数据无损压缩 8 of 42
9.2.1 数据的冗余 ( 续 2)  信息量 (information content)   具有确定概率事件的信息的定量度量在数学上定义创 I ( x)  log 2 [1/ p( x)]   log 2 p( x) p( x) 其中，  是事件出现的概率举例：假设 X={a,b,c} 是由 3 个事件构成的集合， p(a)=0.5 ， p(b)=0.25 ， p(c)=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  一个等概率事件的集合，每个事件的信息量等于创创集合的决策量 Tuesday, May 14, 2019 第 2 章数据无损压缩 9 of 42
10.2.1 数据的冗余 ( 续 3)  熵 (entropy)   按照香农 (Shannon) 的理论，在有限的互斥和联合穷举事件的集合中，熵为事件的信息量的平均值，也称事件的平均信息量 (mean information content) 用数学表示为 Tuesday, May 14, 2019 第 2 章数据无损压缩 10 of 42
11.2.1 数据的冗余 ( 续 4)  数据的冗余量 Tuesday, May 14, 2019 第 2 章数据无损压缩 11 of 42
12.2.2 统计编码  统计编码   编码方法     给已知统计信息的符号分配代码的数据无损压缩方法香农 - 范诺编码霍夫曼编码算术编码编码特性   香农 - 范诺编码和霍夫曼编码的原理相同，都是根据符号集中各个符号出现的频繁程度来编码，出现次数越多的符号，给它分配的代码位数越少算术编码使用 0 和 1 之间的实数的间隔长度代表概率大小，概率越大间隔越长，编码效率可接近于熵 Tuesday, May 14, 2019 第 2 章数据无损压缩 12 of 42
13.2.2.1 统计编码 ——香农 - 范诺编码  香农 - 范诺编码 (Shannon–Fano coding)    熵的大小表示非冗余的不可压缩的信息量在计算熵时，如果对数的底数用 2 ，熵的单位就用 “香农 (Sh)” ，也称“位 (bit)” 。“位”是 1948 年 Shannon 首次使用的术语。例如最早阐述和实现“从上到下”的熵编码方法的人是 Shannon(1948 年 ) 和 Fano(1949 年 ) ，因此称为香农 - 范诺 (Shannon- Fano) 编码法 Tuesday, May 14, 2019 第 2 章数据无损压缩 13 of 42
14.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 符号在图像中出现的数目符号 A B C D E 出现的次数 15 7 7 6 5 出现的概率 15/4 0 7/40 7/4 0 6/40 5/40 Tuesday, May 14, 2019 第 2 章数据无损压缩 14 of 42
15.2.2.1 香农 - 范诺编码 ( 续 1) (1) 压缩比的理论值  按照常规的编码方法，表示 5 个符号最少需要 3 位，如用 000 表示 A ， 001 表示 B ，…， 100 表示 E ，其余 3 个代码 (101 ， 110 ， 111) 不用。这就意味每个像素用 3 位，编码这幅图像总共需要 120 位。按照香农理论，这幅图像的熵为 n H ( X )  �p( xi ) log 2 p( xi ) i 1   p( A) log 2 ( p( A))  p( B) log 2 ( p( B))  L  p( E ) log 2 ( p( E )) = (15/40) log 2 (40/15)+(7/40) log 2 (40/7)+ +(5/40) log 2 (40/5) �2.196  这个数值表明，每个符号不需要用 3 位构成的代码表示，而用 2.196 位就可以，因此 40 个像素只需用 87.84 位就可以，因此在理论上，这幅图像的的压缩比为 120:87.84≈1.37:1 ，实际上就是 3:2.196≈1.37 Tuesday, May 14, 2019 第 2 章数据无损压缩 15 of 42
16.2.2.1 香农 - 范诺编码 ( 续 2) (2) 符号编码  对每个符号进行编码时采用“从上到下”的方法。首先按照符号出现的频度或概率排序，如 A ， B ， C ， D 和 E ，见表 2-2 。然后使用递归方法分成两个部分，每一部分具有近似相同的次数，如图 2-1 所示 Tuesday, May 14, 2019 第 2 章数据无损压缩 16 of 42
17.2.2.1 香农 - 范诺编码 ( 续 3) 图 2-1 香农 - 范诺算法编码举例（ 3 ）压缩比的实际值  按照这种方法进行编码需要的总位数为 30+14+14+18+15 ＝ 91 ，实际的压缩比为 120:91≈1.32 : 1 Tuesday, May 14, 2019 第 2 章数据无损压缩 17 of 42
18.2.2.2 统计编码 ——霍夫曼编码  霍夫曼编码 (Huffman coding)    霍夫曼 (D.A. Huffman) 在 1952 年提出和描述的“从下到上”的熵编码方法根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素 ( 如字母 ) 出现的次数越多，其编码的位数就越少广泛用在 JPEG, MPEG, H.26X 等各种信息编码标准中 Tuesday, May 14, 2019 第 2 章数据无损压缩 18 of 42
19.2.2.2 霍夫曼编码— Case Study 1  霍夫曼编码举例 1  现有一个由 5 个不同符号组成的 30 个符号的字符串： BABACACADADABBCBABEBEDDABEEEBB  计算 (1) (2) (3) (4) 该字符串的霍夫曼码该字符串的熵该字符串的平均码长编码前后的压缩比 Tuesday, May 14, 2019 第 2 章数据无损压缩 19 of 42
20.2.2.2 霍夫曼编码— Case Study 1 ( 续 1) 符号出现的概率符号出现的次数log2(1/pi 分配的代码需要的位数） B 10 1.585 ? A 8 1.907 ? C 3 3.322 ? D 4 2.907 ? E 5 2.585 ? 合计 30 Tuesday, May 14, 2019 第 2 章数据无损压缩 20 of 42
21.2.2.2 霍夫曼编码 — Case Study 1 ( 续 2) (1) 计算该字符串的霍夫曼码步骤①：按照符号出现概率大小的顺序对符号进行排序步骤②：把概率最小的两个符号组成一个节点 P1 步骤③：重复步骤②，得到节点 P2 创 P3 创 P4 创……创 PN ，形成一棵树，其中的 PN 创创创创创步骤④：从根节点 PN 创创创创创创创创创创创创创创创创创 0( 上枝 ) 和 1( 下枝 ) ，至于哪个为 1 哪个为 0 则创创创创创创创创创创创创创创创 1 ，概率小的标成 0 步骤⑤：从根节点 PN 开始顺着树枝到每个叶子分别写出每个符号的代码 Tuesday, May 14, 2019 第 2 章数据无损压缩 21 of 42
22.2.2.2 霍夫曼编码 — Case Study 1 ( 续 3) 符号 B (10) A (8) E (5) D (4) C (3) 1 1 0 P3 (18) 0 1 0 Tuesday, May 14, 2019 1 0 P2 (12) P1 (7) 第 2 章数据无损压缩 P4 (30) 代码 B(11) A(10) E(00) D(011) C(010) 22 of 42
23.2.2.2 霍夫曼编码 — Case Study 1 ( 续 4) 5 个符号的代码符号出现的次数 log2(1/pi ）分配的代码需要的位数 B 10 1.585 11 20 A 8 1.907 10 16 C 3 3.322 010 9 D 4 2.907 011 12 E 5 2.585 00 10 合计 30 1.0 67 30 个字符组成的字符串需要 67 位 Tuesday, May 14, 2019 第 2 章数据无损压缩 23 of 42
24.2.2.2 霍夫曼编码 — Case Study 1 ( 续 5) (2) 计算该字符串的熵 H ( X )  �p( x ) I ( x )  �p( x ) log n n i i 1 其中， i i 1 X  {x1 ,L , xn } i 2 p( xi ) xi (i  1, 2,L , n) 的集合， n 并满足  是事件 �p( x )  1 i 1 i 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 – (8×lg8 ＋ 10×lg10 ＋ 3×lg3 ＋ 4 ×lg4 ＋ 5 lg5)] / (30×log22) = ( 44.3136 － 24.5592)/ 9.0308 ＝ 2.1874 (Sh) Tuesday, May 14, 2019 第 2 章数据无损压缩 24 of 42
25.2.2.2 霍夫曼编码 — Case Study 1 ( 续 6) (3) 计算该字符串的平均码长  平均码长： l  �l p (l ) N i 1 i i ＝ (2×8 ＋ 2×10 ＋ 3×3 ＋ 3×4 ＋ 2×5)/30 ＝ 2.233 位 / 符号平均码长： 67/30=2.233 位 (4) 计算编码前后的压缩比   编码前： 5 个符号需 3 位， 30 个字符，需要 90 位编码后：共 67 位压缩比 : 90/67=1.34:1 Tuesday, May 14, 2019 第 2 章数据无损压缩 25 of 42
26.2.2.2 霍夫曼编码 — Case Study 2  霍夫曼编码举例 2   编码前  N = 8symbols:{a,b,c,d,e,f,g,h},  3 bits per symbol (N =23=8)  P(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) 该字符串的霍夫曼码该字符串的熵该字符串的平均码长编码效率 Tuesday, May 14, 2019 第 2 章数据无损压缩 26 of 42
27.2.2.2 霍夫曼编码 — Case Study 2 ( 续 1) Tuesday, May 14, 2019 第 2 章数据无损压缩 27 of 42
28.2.2.2 霍夫曼编码 — Case Study 2 ( 续 2) Average length per symbol (before coding): L  �i 1 3P ( i )  3 bits/symbol 8 (2)Entropy:H  �i 1 P ( i )log 2 P ( i )  2.5821 bits/symbol 8 (3) Average length per symbol (with Huffman coding): L Huf  2.63 bits/symbol (4) Efficiency of thecode:H / L Huf  98% Tuesday, May 14, 2019 第 2 章数据无损压缩 28 of 42
29.2.2.2 霍夫曼编码 课堂练习：现有 5 个待编码的符号，它们的概率如下表所示，计算该符号集的：（ 1 ）熵；（ 2 ）霍夫曼码；（ 3 ）平均码长。平均码长为 2.2 Tuesday, May 14, 2019 第 2 章数据无损压缩 29 of 42
30.2.2.2 霍夫曼编码 — Case Study 2 ( 续 2)  霍夫曼编码特点：  霍夫曼码没有错误保护功能，可能出现“错误传播”现象  霍夫曼码是可变长度码  与香农 - 范诺编码类似，都是自含同步的代码，在编码之后的码流中无需添加标记符号  编码效率比香农 - 范诺码效率高 Tuesday, May 14, 2019 第 2 章数据无损压缩 30 of 42
31.2.2.3 统计编码 ——算术编码  算术编码 (arithmetic coding)    给已知统计信息的符号分配代码的数据无损压缩技术基本思想是用 0 和 1 之间的一个数值范围表示输入流中的一个字符，而不是给输入流中的每个字符分别指定一个码字实质上是为整个输入字符流分配一个“码字” ，因此它的编码效率可接近于熵 Tuesday, May 14, 2019 第 2 章数据无损压缩 31 of 42
32.2.2.3 算术编码举例  [ 例 2.3] （取自教材）假设信源符号为 {00, 01, 10, 11} ，它们的概率分别为 { 0.1, 0.4, 0.2, 0.3 }  对二进制消息序列 10 00 11 00 10 11 01 … 进行算术编码  Tuesday, May 14, 2019 第 2 章数据无损压缩 32 of 42
33.2.2.3 算术编码举例 ( 续 1)  初始化  根据信源符号的概率把间隔 [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-4 例 2.3 的信源符号概率和初始编码间隔 00 01 10 11 符号 0.1 0.4 0.2 0.3 概率初始编码间隔 [0, 0.1) Tuesday, May 14, 2019 [0.1, 0.5) 第 2 章数据无损压缩 [0.5, 0.7) [0.7, 1） 33 of 42
34.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 Tuesday, May 14, 2019 第 2 章数据无损压缩 34 of 42
35.2.2.3 算术编码举例 ( 续 3) 图 2-3 例 2.3 的算术编码过程 Tuesday, May 14, 2019 第 2 章数据无损压缩 35 of 42
36.2.2.3 算术编码举例 ( 续 4) Tuesday, May 14, 2019 第 2 章数据无损压缩 36 of 42
37.2.2.3 算术编码举例 ( 续 5) Tuesday, May 14, 2019 第 2 章数据无损压缩 37 of 42
38.2.3 RLE 编码  行程长度编码 (Run-Length Coding)    一种无损压缩数据编码技术，它利用重复的数据单元有相同的数值这一特点对数据进行压缩。对相同的数值只编码一次，同时计算出相同值重复出现的次数，称为行程程度。在 JPEG ， MPEG ， H.261 和 H.263 等压缩方法中， RLE 用来对图像数据变换和量化后的系数进行编码。例 : 假设有一幅灰度图像第 n 行的像素值如图 2-5 所示。用 RLE 编码方法得到的代码为： 80315084180 00000000 111 888       888 1111 00000000 8个0 3个1 50个8 4个1 8个0 图 2-5 RLE 编码概念 Tuesday, May 14, 2019 第 2 章数据无损压缩 38 of 42
39.2.3 RLE 编码 ( 续 ) Assumption:  Long sequences of identical symbols. Example, Tuesday, May 14, 2019 第 2 章数据无损压缩 39 of 42
40.2.4 词典编码  词典编码 (dictionary coding)    文本中的词用它在词典中表示位置的号码代替的一种无损数据压缩方法。采用静态词典编码技术时，编码器需要事先构造词典，解码器要事先知道词典。采用动态辞典编码技术时 , 编码器将从被压缩的文本中自动导出词典，解码器解码时边解码边构造解码词典两种类型的编码算法具体算法 LZ77 算法  LZSS 算法  LZ78 算法  LZW 算法 ( 当作课外阅读 )  Tuesday, May 14, 2019 第 2 章数据无损压缩 40 of 42
41.2.4 词典编码 ( 续 1)  第一类编码算法   用已经出现过的字符串替代重复的部分编码器的输出仅仅是指向早期出现过的字符串的“指针” 图 2-6 第一类词典编码概念 Tuesday, May 14, 2019 第 2 章数据无损压缩 41 of 42
42.2.4 词典编码 ( 续 2)  第二类编码算法   从输入的数据中创建一个“短语词典 (dictionary of the phrases)” 编码器输出词典中的短语“索引号”，而不是短语图 2-7 第二类词典编码概念 Tuesday, May 14, 2019 第 2 章数据无损压缩 42 of 42
43.第 2 章数据无损压缩参考文献和站点  1. 2. 3. 4. 5. 6. 7. 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.htmTimothy C.Bell, John G.Cleary, Ian H.Witten. 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. Dobb's Journal, October 1989 ，http://marknelson.us/1989/10/01/lzw-datacompression/R.Hunter and A.H.Robison. International Digital Facsimile Coding Standards. Proceedings of the IEEE, Vol.68, No.7 ， July, 1980 ， pp854 ～ 867 Tuesday, May 14, 2019 第 2 章数据无损压缩 43 of 42
44.END 第 2 章数据无损压缩