数据压缩霍夫曼编码算术编码精品文稿.ppt

《数据压缩霍夫曼编码算术编码精品文稿.ppt》由会员分享，可在线阅读，更多相关《数据压缩霍夫曼编码算术编码精品文稿.ppt（27页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据压缩霍夫曼编码算术编码第1页，本讲稿共27页主要内容图像压缩编码简介Huffman编码算术编码简介算术编码原理算术编码的发展及应用第2页，本讲稿共27页一 图像压缩编码简介第3页，本讲稿共27页 霍夫曼编码霍夫曼编码(Huffman coding)根据给定数据集中霍夫曼(D.A.Huffman)在1952年提出和描述的“从下到上从下到上”的熵编码方法各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次次数越多数越多，其编码的位数就越少位数就越少广泛用在JPEG,MPEG,H.26X等各种信息编码标准中第4页，本讲稿共27页熵(entropy)按照香农(Shanno

2、n)的理论，在有限的互斥和联合穷举事件的集合中，熵为事件的信息量的平均值，也称事件的平均信息量事件的平均信息量(mean information content)(依概率平均依概率平均)用数学表示为熵是数据压缩的极限第5页，本讲稿共27页霍夫曼编码(1)计算该字符串的霍夫曼码步骤：按照符号出现概率大小的顺序对符号进行排序排序步骤：把概率最小概率最小的两个符号组成两个符号组成一个节点P1步骤：重复重复步骤，得到节点P2，P3，P4，PN，形成一棵树，其中的PN称为根节点步骤：从根节点PN开始到每个符号的树叶，从上到下 标上0(上枝)和1(下枝)，至于哪个为1哪个为0则 无关紧要，但通常把概率大的

3、标成1，概率小的 标成0.(标记标记)步骤：从根节点PN开始顺着树枝到每个叶子分别写出 每个符号的代码.(反向编码反向编码)第6页，本讲稿共27页霍夫曼编码霍夫曼编码举例1现有一个由5个不同符号组成的30个符号的字符串：BABACACADADABBCBABEBEDDABEEEBB计算(1)该字符串的霍夫曼码(2)该字符串的熵(3)该字符串的平均码长(4)编码前后的压缩比第7页，本讲稿共27页霍夫曼编码符号出现的次数 log2(1/pi）分配的代码 需要的位数B101.585?A81.907?C33.322?D42.907?E52.585?合计30符号出现的概率符号出现的概率第8页，本讲稿共27

4、页霍夫曼编码符号B(10)A(8)E(5)D(4)C(3)P1(7)P2(12)P3(18)P4(30)01101010代码代码B(11)A(10)E(00)D(011)C(010)第9页，本讲稿共27页霍夫曼编码符号出现的次数log2(1/pi）分配的代码需要的位数B101.5851120A81.9071016C33.3220109D42.90701112E52.5850010合计306730个字符组成的字符串需要个字符组成的字符串需要67位位5个符号的代码第10页，本讲稿共27页霍夫曼编码(2)计算该字符串的熵计算该字符串的熵 其中，是事件 的集合，并满足H(S)=(8/30)log2(3

5、0/8)+(10/30)log2(30/10)+(3/30)log2(30/3)+(4/30)log2(30/4)+(5/30)log2(30/5)=(44.313624.5592)/9.0308 2.1874 (Sh)理论上可获得的压缩比为：理论上可获得的压缩比为：3:2.1874=1.37第11页，本讲稿共27页霍夫曼编码(3)计算该字符串的平均码长平均码长：(28210333425)/30 2.233 位/符号 压缩比压缩比:90/67=1.34:1 平均码长：平均码长：67/30=2.233位位(4)计算编码前后的压缩比计算编码前后的压缩比n编码前：5个符号需3位，30个字符，需要90

6、位n编码后：共67位第12页，本讲稿共27页算术编码简介算术编码(Arithmetic Coding)：和霍夫曼编码不同，算术编码跳出。分组编码的范畴,从全序列出发,采用递推形式的连续编码不是将单个信源符号映射成一个码字,而是将整个输入符号序列映射为实数轴上0,1)区间内的一个小区间,其长度等于该序列的概率,再在该小区间选择一个代表性的二进制小数,作为实际的编码输出。第13页，本讲稿共27页算术编码算术编码(arithmetic coding)给已知统计信息的符号分配代码的数据无损数据无损压缩技术基本思想是用0和1之间的一个数值范围数值范围表示输入流中的一个字符（串），字符（串），而不是给输入

7、流中的每个字符分别指定一个码字实质上是为整个输入字符流分配一个“码字”，因此它的编码效率可接近于熵接近于熵 第14页，本讲稿共27页 算术编码算术编码(1)(1)基本思想：基于递归概率区间划分的二进制编码具体过程：基本思想：基于递归概率区间划分的二进制编码具体过程：把信源符号序列把信源符号序列Xi|i=1,2,Xi|i=1,2,n,n发生的概率用实数区间发生的概率用实数区间 00，11上的间隔（上的间隔（XiXi的取值范围）来表示的取值范围）来表示 按符号概率大小来分配符号间隔，按符号概率大小来分配符号间隔，使使00，11随迭代计算次数的增加而逐次变窄；随迭代计算次数的增加而逐次变窄；所求最后

8、范围便是替代所求最后范围便是替代XiXi符号串编码的取值范围符号串编码的取值范围 应用实例：待编码符号串为应用实例：待编码符号串为X X1 1,X,X2 2,X,X3 3,X,X4 4,X,X5 5第15页，本讲稿共27页 算术编码处理过程的编码区间分配可用图解法表示：算术编码处理过程的编码区间分配可用图解法表示：以少代多思想：用最终求得的编码表示范围子区间的以少代多思想：用最终求得的编码表示范围子区间的 任何值（如：任何值（如：0.106030.10603），来替代被编码符号串），来替代被编码符号串X X1 1X X2 2X X3 3X X4 4X X5 5第16页，本讲稿共27页无论是否是

9、二元信源，也不论数据的概率分布如何，算术编码可以二进制小数表示，其平均码长可以接近无损压缩的熵极限。因此：第17页，本讲稿共27页算术编码的发展历史：1960年，P.Elias首先提出把这种依附Shannon编码概念推广到对符号序列直接编码上，推出了所谓的算术编码（Arithmetic Coding）；1948年，Shannon提出将信源依其概率降序排序,用符号序列累积概率的二进制表示对信源的编码;1976年,R.Pasco和J.Rissanen 分别用定长的寄存器实现了有限精度的算术编码;1979年,Rissanen 和G.G.Langdon将算术编码系统化，并于1981年将AC推广应用到二

10、值图像编码上,大大提高了起压缩效率；1987年,Witten等人发表了一个实用的算术编码程序(CACM87,后用于H.263);同期IBM公司发表了著名的Q-编码器(后用于JPEG和JPIG);第18页，本讲稿共27页设一个信源，它有两个符号a和b，出现的概率分别是p和1p，设有一个基准区域0，1，对它进行划分，以便与信源输出序列相对应。abp1aabap1p+p(1-p)bbabaabap2bbab图A 符号序列与区域划分示意算术编码的基本原理第19页，本讲稿共27页ab0.81aaba0.810.96bbabaaba0.64bbabaaabab0.810.960.64bbaaba0.512

11、0.7680.9920.928bbbbaaabbaab例设一个信源，它有两个符号a和b，出现的概率分别是0.8和0.2，有3个符号输出时，符号序列与区域划分的对应关系。图B 3符号输出时的 符号序列与区域划分示意第20页，本讲稿共27页字符串 aabaa对应的区域为0.512，0.59392)该区域的二进制表示0.1000001，0.1001100)二进制数0.1001输出编码 1001因此第21页，本讲稿共27页对于这个信源：H（X）=0.7219Huffman编码:算术编码:平均码长 R=0.8平均码长 R=1相比Huffman编码，算术编码的编码效率有明显提高。对于长序列，理论上算术编码

12、可以达到信源的熵。编码效率第22页，本讲稿共27页算术编码过程:依据字符的发生概率对码区间的分割过程(即子区间宽度与正编码字符发生概率相乘的过程)。算术解码过程:只需知道最终编码区间中的某一个值就可以解码。算术编码每次递推都要做乘法，而且必须在一个信源符号的处理周期内完成，有时难以实时，为此采用了查表等许多近似计算来代替乘法。小结：第23页，本讲稿共27页固定编码模式概率统计与区间分配直接影响编码效率。自适应模式各符号的概率初始值都相同，但依据实际出现的符号而相应地改变。两种编码模式：第24页，本讲稿共27页算术编码的发展及应用jpeg、mpeg-1和mpeg-2等国际标准采用的图像压缩编码方

13、案都是传统的“DCT+运动补偿+算术编码”模式JPEG2000、MQ算术编码器嵌入位平面图像编码器EZW、SPIHT和SPECK中也采用这种通用算法编码器第25页，本讲稿共27页 算术码评述 能够自适应地估计条件概率,从信源的统计特性 出发,建立数据的概率模型。它不必预先定义信 源的概率模型,尤其适用于不可能进行概率统计 的场合;适用于信源符号概率比较接近的场合，在几种主 要的统计编码中（Huffman，LZ家族以及算术编 码中），算术编码具有最高的压缩效率。优点：第26页，本讲稿共27页缺点：比霍夫曼编码复杂，特别是硬件实现；由于是变长码，也需要输入输出缓冲存储器，只适用于分段信息；误差扩散比分组码更严重，误码不会自动恢复，会一直延续下去，传输要求高质量的信道，或 采用检错反馈重发的方式。第27页，本讲稿共27页