[高等教育]第六章多媒体数据压缩编码技术第二节

高中信息技术（选修2）多媒体技术应用广东教育出版社3.2.6 数据压缩技术,数据压缩原理分类具体压缩方法,高中信息技术（选修2）多媒体技术应用教育科学出版社第二章 图形、图像2.1.4 图形、图像文件的压缩,数据压缩基本原理,第六章 多媒体数据压缩编码技术,学习内容,一、多媒体数据压缩编码概述 （压缩必要性、可能性、分类）二、多媒体数据压缩经典理论 理解压缩的理论极限 掌握典型的压缩方法,第二节 多媒体数据压缩经典理论,数据压缩是在保持一个可以接受的逼真度损失的情况下采用尽可能少的比特数来表示信源。,问题1：数据压缩的理论极限,1、信息量2、熵,两个基本概念：,1、信息量,如何衡量信息的多少呢 ？,信息（香农） ：是事物的运动状态和存在方式不确定性的描述,要从1256中猜一个数 ，只允许提问“是否大于？”，问如何猜出这个数？,这个过程由下列公式表示： log22568,1、信息量,玩个猜数游戏吧！,假设这个数是12，需要提问几次？,有何启示？（游戏与信息量的关系）,1、信息量,信息量：为了从N个相等的可能事件中挑选出一个事件所需的信息度量和含量，所提问“是或否”的次数.也就是说，在N个事件中辨识特定的一个事件要询间“是或否”多少次。,对于256个数的询问只要进行8次，即可确定一个具体的数。,设从N个数中选定任意一个数x的概率为p（x），假定选定任意一个数的概率都相等，即p（x）=1/N，则信息量为：,1、信息量,2、熵,数据压缩起源于 40 年代由 Claude Shannon 首创的信息论，信息论中用“熵”( Entropy )来表示一条信息中真正需要编码的信息量。,2、熵,用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码，假设符号 xi 在整条信息中重复出现的概率为 P(xi ) ，则该符号的熵也即表示该符号所需的位数为：E xi = - log2( P xi ),对于一条信息来说，熵表明了集合X中随机事件的平均不确定性，或者说平均信息量。,2、熵,熵的计算 例1：字符串：aabbaccbaa,P(a)=0.5 P(b)=0.3 P(c)=0.2,Ha = -log2(0.5) = 1Hb = -log2(0.3) = 1.737Hc = -log2(0.2) = 2.322,整条信息的熵即表达整个字符串需要的平均位数为：H= Ha * P(a) + Hb * P(b) + Hc * P(c) = 1.4855 位,概率：,熵：,2、熵,如果用计算机中常用的 ASCII 编码，表示字符串aabbaccbaa，需要多少 位呢？,80位,2、熵,整条信息共需要 14.855位 进行编码,极限,熵的计算（例2）,有一幅40个象素组成的灰度图像，灰度共有5级，分别用符号A、B、C、D和E表示,如果用3个位表示5个等级的灰度值，也就是每个象素用3位表示，编码这幅图像总共需要120位。,H(S) = (15/40) (40/15) + (7/40) (40/7) + + (5/40) (40/5) =2.19640个象素需用87.84位。,问题2：典型的压缩方法,多媒体数据压缩编码,无失真编码,有失真编码,统计编码,预测编码,变换编码,分析合成编码,量化编码小波变换编码分行图像子带编码,K-L变换DCT变换,DPCM编码ADPCM编码,香农-范农编码霍夫曼编码算术编码行程编码LZW编码,问题2：典型的压缩方法,统计编码：是给已知统计信息的符号分配代码的数据无损压缩方法。目的：使得平均码长到达熵极限原则：根据符号集中各个符号出现的频繁程度来编码， 出现次数越多的符号，分配的代码就越少； 出现次数越少的符号，分配的代码就越多。,问题2：典型的压缩方法,1、前缀编码（基础）2、Huffman编码3、Shannon-Fano 编码4、算术编码5、行程编码（图像压缩部分讲）,一、前缀编码,对 a 用 3 个二进制位就可以表示，而对 b 用 4 个二进制位就可以表示。,在解码时，面对一连串的二进制流，怎么知道哪三个位是 a，哪四个位是 b 呢？,必须设计出一种编码方式，使得解码程序可以方便地分离每个字符的编码部分。,“前缀编码”的技术,任何一个字符的编码，都不是另一个字符编码的前缀。,0,1,10,11,110,111,一、前缀编码,任何一个字符的编码，都不是另一个字符编码的前缀。,011011110111,一、前缀编码,例：,符号 编码 A 0 B 10 C 110 D 1110 E 11110 ？以下二进制流中包含的真正的信息内容是什么1110010101110110111100010,一、前缀编码,D,A,B,B,D,C,E,A,A,B,二、Huffman编码,例：对下面这串出现了五种字符的信息( 40 个字符长 ):cabcedeacacdeddaaabaababaaabbacdebaceada 五种字符的出现次数分别：a - 16，b - 7，c - 6，d - 6，e - 5。,二、Huffman编码,Huffman 编码过程：,将各个符号及其出现频率(由高到低）分别作为不同的小二叉树（目前每棵树只有根节点）。a(16) b(7) c(6) d(6) e(5),二、Huffman编码,2) 在 1 中得到的树林里找出频率值最小的两棵树，将他们分别作为左、右子树连成一棵大一些的二叉树，该二叉树的频率值为两棵子树频率值之和。对上面的例子，我们得到一个新的树林：,a(16) b(7) c(6),二、Huffman编码,3) 对上面得到的树林重复 2 的做法，直到所有符号都连入树中为止。这一步完成后，我们有这样的二叉树：,a(16),二、Huffman编码,编码:a:0 b:100 c:101d:110 e:111,此信息的编码表： a:0 b:100 c:101 d:110 e:111,将例子中的信息编码为：Cabcedeacacdeddaaabaababaaabbacdebaceada( 101 0 100 101 111 110 111 0 101 . ）,码长共（ 88 ） 位,用 ASCII 码表示上述信息需要 8 * 40 = 320 位,二、Huffman编码,上面的例子中，每个字符的熵为：Ha = - log2(16 / 40) = 1.322Hb = - log2( 7 / 40) = 2.515Hc = - log2( 6 / 40) = 2.737 Hd = - log2( 6 / 40) = 2.737He = - log2( 5 / 40) = 3.000,二、Huffman编码,表示该条信息最少需要：H = Ha * 16 + Hb * 7 + Hc * 6 + Hd * 6 + He * 5 = 86.601 位,86.601 88 320,1、Huffman编码通常采用两次扫描的办法，第一次扫描得到统计结果，第二次扫描进行编码。2、译码时间较长 ,使得压缩与还原相当费时。3、编码长度不统一,硬件实现有难度。4、为解决误码率高的问题, Huffman编码采用双字长编码,概率高的字长短,概率低的字长长。,特点：,二、Huffman编码,5、对不同信号源的编码效率不同,当信号源的符号概率为的负幂次方时，达到的编码效率；若信号源符号的概率相等，则编码效率最低。,特点（续）：,二、Huffman编码,6、Huffman编码表是编码的重要依据,为了节省编码时间，通常把Huffman编码表存储在发送端和接收端。否则，在进行编码时还要传送编码表，在很大程度上延长了编码时间。,三、Shannon-Fano编码,例：对下面这串出现了五种字符的信息( 40 个字符长 )：cabcedeacacdeddaaabaababaaabbacdebaceada,五种字符的出现次数分别：,a - 16，b - 7，c - 6，d - 6，e - 5,三、Shannon-Fano编码,1) 将给定符号按照其频率从大到小排序。,Shannon-Fano 编码过程：,2) 将序列分成上下两部分，使得上部频率总和尽可能接近下部频率总和。,a - 16 b - 7 c - 6 d - 6 e - 5,a 16 b 7c - 6 d 6 e - 5,三、Shannon-Fano编码,3) 我们把第（2）步中划分出的上部作为二叉树的左子树，记 0，下部作为二叉树的右子树，记 1。,4) 分别对左右子树重复 2 3 两步，直到所有的符号都成为二叉树的树叶为止。现在我们有如下的二叉树：,三、Shannon-Fano编码,于是我们得到了此信息的编码表： a - 00 b 01 c 10 d - 110 e - 111,将例子中的信息编码为：Cabcedeacacdeddaaabaababaaabbacdebaceada( 10 00 01 10 111 110 111 00 10 00 10 . ),码长共 91 位,用 ASCII 码表示上述信息需要 8 * 40 = 320 位,无论是 Shannon-Fano 还是 Huffman，都只能用近似的整数位来表示单个符号，而不是理想的小数位。,三、Shannon-Fano编码,Huffman 编码：假设某个字符的出现概率为 80%该字符事实上只需要（ -log2(0.8) = 0.322 ）位编码，但 Huffman 编码一定会为其分配（ 1位 ）的编码。整个信息的 80% 在压缩后都几乎相当于理想长度的（ 3 ）倍左右Huffman 编码使用整数个二进制位对符号进行编码，这种方法在许多情况下无法得到最优的压缩效果。,四、算术编码,基本思想： 算术编码不是将单个信源符号映射成一个码字，而是把真个信源表示为实数线上的0到1之间的一个区间，其长度等于该序列的概率； 再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。 消息序列中的每个元素都要用来缩短这个区间。消息序列中元素越多，所得到的区间就越小，区间越小，表示这一区间所需的二进制位数就越多。 采用算术编码每个符号的平均编码长度可以为小数。,四、算术编码,算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于 0 和 1 之间的二进制小数。,四、算术编码,例如：算术编码对某条信息的输出为 1010001111，那么它表示小数 0.1010001111，也即十进制数 0.64。,在没有开始压缩进程之前，假设对 a b c 三者在信息中的出现概率一无所知（采用自适应方式），暂时认为三者的出现概率相等，也就是都为 1/3。,四、算术编码,假设某条信息中可能出现的字符有 a b c 三种，要压缩保存的信息为 bccb。,算术压缩编码例子：,四、算术编码,将 0 - 1 区间按照概率的比例分配给三个字符，即 a 从 0.0000 到 0.3333，b 从 0.3333 到 0.6667，c 从 0.6667 到 1.0000。,0.000 - 0.3333 -0.6667 -1.0000,a b c,（1）,概率分布图一,输入第一个字符 b，b 对应的区间 0.3333 - 0.6667。这时由于多了字符 b，三个字符的概率分布变成：Pa = 1/4，Pb = 2/4，Pc = 1/4。按照新的概率分布比例划分 0.3333 - 0.6667 这一区间。,四、算术编码,0.3333 - 0.4167 - 0.5834-0.6667,a b c,（2）,概率分布图二,输入第二个字符 c，上一步中得到的 c 的区间 0.5834 - 0.6667。新添了 c 以后，三个字符的概率分布变成 Pa = 1/5，Pb = 2/5，Pc = 2/5。用这个概率分布划分区间 0.5834 - 0.6667。,四、算术编码,0.5834 -0.6001-0.6334 -0.6667,a b c,（3）,概率分布图三,输入第三个字符 c，上一步中得到的 c 的区间 0.6334 - 0.6667 。新添了 c 以后，三个字符的概率分布变成Pa = 1/6，Pb = 2/6，Pc = 3/6。用这个概率分布划分区间 0.6334 - 0.6667：,四、算术编码,0.6334 -0.6390-0.6501 - 0.6667,a b c,（4）,概率分布图四,输入最后一个字符 b，因为是最后一个字符，不用再做进一步的划分了，上一步中得到的 b 的区间为 0.6390 - 0.6501，在这个区间内随便选择一个容易变成二进制的数，例如 0.64，将它变成二进制 0.1010001111，去掉前面没有太多意义的 0 和小数点，输出 1010001111，这就是信息被压缩后的结果。,四、算术编码,（5）,压缩过程结束,解压缩之前我们仍然假定三个字符的概率相等，并得出以下概率分布图一。,四、算术编码,解压缩过程：,0.000 - 0.3333 -0.6667 -1.0000,a b c,概率分布图一,解压缩时面对的是二进制流 1010001111。,四、算术编码,先在前面加上 0 和小数点把它变成小数 0.1010001111，也就是十进制 0.64。,0.64 在概率分布图一中落入字符 b 的区间内，我们立即输出字符 b。,（1）,结果：b,三个字符新的概率分布为： Pa = 1/4，Pb = 2/4，Pc = 1/4。类似压缩时的方法，按照新的概率分布划分字符 b 的区间。在新的划分即概率分布图二中，0.64 落入了字符 c 的区间，我们可以输出字符 c。,四、算术编码,0.3333 - 0.4167 - 0.5834-0.6667,a b c,概率分布图二,（2）,结果：b c,三个字符新的概率分布为： Pa = 1/5，Pb = 2/5，Pc = 2/5。按照新的概率分布划分字符 c 的区间。在新的划分即概率分布图三中，0.64 落入了字符 c 的区间，我们可以输出字符 c。