数据压缩霍夫曼编码算术编码

1、主要内容,图像压缩编码简介 Huffman编码 算术编码简介 算术编码原理 算术编码的发展及应用,一 图像压缩编码简介,霍夫曼编码,霍夫曼编码(Huffman coding) 根据给定数据集中霍夫曼(D.A. Huffman)在1952年提出和描述的“从下到上”的熵编码方法 各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少 广泛用在JPEG, MPEG, H.26X等各种信息编码标准中,熵(entropy) 按照香农(Shannon)的理论，在有限的互斥和联合穷举事件的集合中，熵为事件的信息量的平均值，也称事件的平均信息量(mean in

2、formation content) (依概率平均) 用数学表示为,熵是数据压缩的极限,霍夫曼编码,(1) 计算该字符串的霍夫曼码 步骤：按照符号出现概率大小的顺序对符号进行排序 步骤：把概率最小的两个符号组成一个节点P1 步骤：重复步骤，得到节点P2，P3，P4， PN，形成一棵树，其中的PN称为根节点 步骤：从根节点PN开始到每个符号的树叶，从上到下 标上0(上枝)和1(下枝)，至于哪个为1哪个为0则 无关紧要，但通常把概率大的标成1，概率小的 标成0.(标记) 步骤：从根节点PN开始顺着树枝到每个叶子分别写出 每个符号的代码.(反向编码),霍夫曼编码,霍夫曼编码举例1 现有一个由5个不同

3、符号组成的30个符号的字符串：BABACACADADABBCBABEBEDDABEEEBB 计算 (1) 该字符串的霍夫曼码 (2) 该字符串的熵 (3) 该字符串的平均码长 (4) 编码前后的压缩比,霍夫曼编码,符号出现的概率,霍夫曼编码,符号 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),霍夫曼编码,30个字符组成的字符串需要67位,5个符号的代码,霍夫曼编码,(2) 计算该字符串的熵 其中， 是事件 的集合，

4、并满足,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) = ( 44.313624.5592)/ 9.0308 2.1874 (Sh),理论上可获得的压缩比为： 3:2.1874=1.37,霍夫曼编码,(3) 计算该字符串的平均码长 平均码长： (28210333425)/30 2.233 位/符号,压缩比: 90/67=1.34:1,平均码长：67/30=2.233位,(4) 计算编码前后的压缩比 编码前：5个符号需3位，30个字符，需要9

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

6、个输入字符流分配一个“码字”，因此它的编码效率可接近于熵,算术编码 (1)基本思想：基于递归概率区间划分的二进制编码具体过程： 把信源符号序列Xi|i=1,2,n发生的概率用实数区间 0，1上的间隔（Xi的取值范围）来表示 按符号概率大小来分配符号间隔， 使0，1随迭代计算次数的增加而逐次变窄； 所求最后范围便是替代Xi符号串编码的取值范围 应用实例：待编码符号串为X1,X2,X3,X4,X5,算术编码处理过程的编码区间分配可用图解法表示： 以少代多思想：用最终求得的编码表示范围子区间的 任何值（如：0.10603），来替代被编码符号串X1X2X3X4X5,无论是否是二元信源，也不论数据的概率

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

8、了起压缩效率；,1987年, Witten等人发表了一个实用的算术编码程序(CACM87,后用于H.263); 同期IBM公司发表了著名的Q-编码器 (后用于JPEG和JPIG);,设一个信源，它有两个符号a和b，出现的概率分别是p和1p，设有一个基准区域0，1，对它进行划分，以便与信源输出序列相对应。,图A 符号序列与区域划分示意,算术编码的基本原理,aa,ba,0.8,1,0.96,bb,ab,aa,ba,0.64,bb,ab,例,设一个信源，它有两个符号a和b，出现的概率分别是0.8和0.2，有3个符号输出时，符号序列与区域划分的对应关系。,图B 3符号输出时的 符号序列与区域划分示意,

9、字符串 aabaa,对应的区域为 0.512，0.59392),该区域的二进制表示 0.1000001，0.1001100 ),二进制数0.1001 输出编码 1001,因此,对于这个信源：,相比Huffman编码，算术编码的编码效率有明显提高。对于长序列，理论上算术编码可以达到信源的熵。,编码效率,算术编码过程:,依据字符的发生概率对码区间的分割过程(即子区间宽度与正编码字符发生概率相乘的过程)。,算术解码过程:,只需知道最终编码区间中的某一个值就可以解码。,算术编码每次递推都要做乘法，而且必须在一个信源符号的处理周期内完成，有时难以实时，为此采用了查表等许多近似计算来代替乘法。,小结：,固定编码模式,概率统计与区间分配直接影响编码效率。,自适应模式,各符号的概率初始值都相同，但依据实际出现的符号而相应地改变。,两种编码模式：,算术编码的发展及应用,jpeg、mpeg-1和mpeg-2等国际标准采用的图像压缩编码方案都是传统的“DCT+运动补偿+算术编码”模式 JPEG2000、MQ算术编码器 嵌入位平面图像编码器EZW、SPIHT和SPECK中也采用这种通用算法编码器,算术码评述,能够自适应地估计条件概率, 从信源的统计特性 出发, 建立数据的概率模型。它不必预先定义信 源的概率模型, 尤其适用于不可能进行概率统计 的场合;,适用于信源符号概率比较接近的场合，在几种主 要