（微电子学与固体电子学专业论文）jpegmjpeg中huffman编解码的ip设计.pdf

摘要 摘要 j p e g 静态图像压缩算法因其对连续色调、多级灰度的静止图象具有优良的压 缩特性，已成为目前多媒体通信中的图像压缩标准之一，开始广泛地应用于各个 方面。多媒体技术中，图像的数据压缩和解压缩实现是目前国内和国际研究的热 点问题之一。同时，随着v l s i 设计技术的飞速发展，越来越多的图像和视频应用 被实现成v l s i 芯片系统。 h u f f m a n 编码做为一种优秀的、成熟的编码方法，目前已经被广泛使用于静止 图像和运动视频的压缩方法中，本文着重研究了静态图像的j p e g 编码和解码流程 及关键技术一h u 胁a n 编解码，依据j p e g 标准推荐的h u f f m a n 表及生成的方法，将 h u f f m a n 表按码字长度分别建立，提出了一种基于j p e g 图像解码的并行h u f f m a n 解 码器模块的v l s i 设计思想，采用模块化方式，并对整体设计进行了进一步的划分 成6 个模块，对每一个小模块的具体要实现的功能作了详细的说明，并且用v e r i l o g 硬件语言对其进行时序仿真验证，最后对整体设计验证，结果证明，对码字长度 较短的码字，平均每两个时钟周期，可以解出一个码字，对于码字长度较大的， 平均每三到四个时钟周期，可以解出一个码字，效率要明显高于串行的解码方法。 同时，这种设计方法简单可行，易于实现。 关键字：j p e g 标准h u f f m a nv e r i l o gh d l 仿真 a b s t r a c t i i i a b s t r a c t j p e gi so n eo ft h ec o m p r e s s i o ns t a n d a r di nm u l t i m e d i ac o m m u n i c a t i o n a n dh a sb e e n w i d e l yu s e di nm a n yf i e l d sf o ri t se x c e l l e n tc h a r a c t e r i s t i c so fg o o dc o m p r e s s i o no f c o n t i n u o u st o n es t i l li m a g e i nm u l t i - m e d i at e c h n o l o g y ，t h ed i g i t a lc o m p r e s s i o na n d d e c o m p r e s s i o no ng r a p h sa r eo n eo ft h ef o c u s e si nd o m e s t i ca n di n t e r n a t i o n a lr e s e a r c h f i e l d m e a n t i m e ，w i t ht h er a p i dd e v e l o p m e n to fv l s it e c h n o l o g y ，m o r ea n dm o r ei m a g e a n dv i d e oa p p l i c a t i o n sa r ei m p l e m e n t e di n t ov l s i c h i p h u f f m a ne n c o d i n gi sc o n s i d e r e dt ob eav e r ye x c e l l e n ta l g o r i t h ma n dw i d e l yu s e di n s t i l li m a g ea n dm o t i o nv i d e oc o m p r e s s i o n t h i sp a p e rm a i n l ys t u d i e sj p e ge n c o d i n g a n dd e c o d i n gt e c h n o l o g y t h ea u t h o rp r o p o s e sa p a r a l l e lh u f f m a nv l s id e s i g nm e t h o d b a s e do nr e c o m m e n d e dh u f f m a nt a b l e ss u p p o r t e db yj p e gs t a n d a r d t h ed e s i g ni s d i v i d e di n t os i xs m a l lm o d u l e sa n de x p l m n e ds e p a r a t e l y t h ed e s i g ni sd e s c r i b e di n h a r d w a r el a n g u a g ev e r i l o ga n ds i m u l a t e d t h er e s u l t sp r o v e st h a ti ne v e r yt w oc l o c k p e r i o d s ，as h o r tc o d ew o r dc a nb ed e c o d e da n di ne v e r yt h r e et of o u rc l o c kp e r i o d sa l o n g e rc o d ew o r dc a nb ed e c o d e d s oi ti so b v i o u s l yt h a tt h ee f f i c i e n c yo ft h i sd e s i g ni s b e r e rt h a nt h es e r i a lo n e m e a n w h i l e ，t h i sd e s i g ni ss i m p l ea n d e a s yt or e a l i z e k e y w o r d ：j p e gs t a n d a r d h u f f m a n v e r i l o gh d ls i m u l a t i o n 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担切相关责任。 本人签名：暂邑金匝 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文( 与学位论文相关) 工作成果时署名单位仍然为 西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学 校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保 存论文。( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： 手一葛生 塑釜 第一章绪论 第一章绪论弟一旱珀下匕 1 1 引言 2 0 世纪9 0 年代，随着多媒体技术地迅速发展，静止图像开始广泛地应用于各 个方面。从互联网上的网页图像，到数码相机中的数码照片，都离不开静止图象 的应用。静止图象的广泛应用给人们提供了巨大的方便，但是，大数据量的图像 信息会给存储器的存储容量，通信干线信道的带宽，以及计算机的处理速度增加 极大的压力。例如一幅5 1 2 x 5 1 2 、各分量为8 b i t s 的中低分辨率彩色图像，数据量 为7 6 8 k b ，一张1 4 m b 容量的软盘只能存放近两幅这样的图像，运动图像的数据量 更大，在典型高清晰度电视( h d t v ) 标准中，原始数据速率约7 2 0 1 2 8 0 2 4 6 0 约等于1 2 4 g b i t s ，而按照目前的数字传输能力通过6 m h z 的带宽，只能达到2 0 m b i t s 的传输速率，这显然需要高效的压缩技术才能实现。面对如此大量的数据，单纯 靠增加存储器容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题 是不现实的，这时就要考虑压缩，数据压缩己经成为了非常必要的技术。图像压 缩技术的发展趋势是：算法更复杂，压缩率更高，j p e g 的压缩率在1 ：2 0 左右， j p e g 2 0 0 0 的压缩率将为1 ：2 0 0 或更高。 1 2 理论基础 数据压缩技术是建立在信息理论的基础上，是信息论1 3 1 中的重要分枝。信息 论之父s h a n n o n 在1 9 4 8 年发表的论文“am a t h e m a t i c a lt h e o r yo f c o m m u n i c a t i o n 中指出任何信息都存在冗余，冗余大小与信息中每个符号( 数字、字母或单词) 的出 现概率或者说不确定性有关。s h a n n o n 借鉴了热力学的概念，把信息中排除了冗余 后的平均信息量称为“信息熵”，并给出了计算信息熵的数学表达式。s h a n n o n 第 一次用数学语言阐明了概率与信息冗余度的关系，奠定了所有数据压缩算法的理 论基础。从本质上讲，数据压缩的目的就是要消除信息中的冗余，以尽可能少的 数据表示信源发出的信号，减少容纳给定消息集合的信号空f m ( 且p 被压缩的对象) 。 信息熵及相关的定理恰恰用数学手段精确地描述了信息冗余的程度。利用信息熵 公式，我们可以计算出信息编码的极限： 在一定的概率模型下，无损压缩的编码长度不可能小于信息熵公式给出的结果。 数据压缩的研究己经有几十年的历史，期间提出了很多中压缩算法。在分类 j p e g m j p e g 中h u f f m a n 编解码的i p 设计 上，人们通常将这些算法按照编码的失真程度分为两种类型：有损压缩编码和无 损压缩编码。使用无损压缩算法的压缩后，原始数据可以由压缩数据完全恢复出 来。常用的无损压缩算法有h u f f r n a n 编码、l z w 编码和算术编码等。使用有损压 缩算法压缩后，原始数据不能由压缩数据完全恢复出来。常用的有损压缩算法有 预测编码、量化编码、变换编码等。 h u f f m a n 在19 5 2 年的论文“am e t h o df o rt h ec o n s t r u c t i o no fm i n i m u m r e d u n d a n c yc o d e s ”中提出了第一个实用的压缩编码方法h u f f m a n 编码。h u f f m a n 编码效率高，运算速度快，实现方式灵活方便，从2 0 世纪6 0 年代至今，h u f f r n a n 编码在数据压缩领域得到了广泛的应用。u n i x 系统上的c o m p a c t 、c p m 和 d o s 系统中的s q 都是以h u f f m a n 编码为核心算法设计和实现的。今天，在许多 知名的压缩工具和压缩算法( 如w i n r a r 和j p e g ) 里，都有使用h u f f m a n 编码。 1 3j p e g 发展现状 j p e g 全称为j o i n tp h o t o g r a p h i ce x p e r t sg r o u p ，它是一个在国际标准组织( i s o ) 下从事静念图像压缩标准制定的委员会，并于1 9 9 1 年制定出了第一套国标静态图 像压缩标准：i s o i e c1 0 9 1 8 - j p e g t l l 。由于j p e g 优良的品质，使得它在短短的几 年内就获得极大的成功，目前网站上百分之八十的图像都是采用j p e g 的压缩标 准。然而，随著多媒体应用领域的激增，人们对多媒体图像资料提出了更高的要 求。因此，联合摄影专家组于2 0 0 0 年8 月制定了新一代静态图像压缩技术 j p e g 2 0 0 0 t7 1 。与传统j p e g 最大的不同，在于它放弃了j p e g 所采用的以离散余 弦变换( d i s c r e t ec o s i n et r a n s f o r m ) 为主的分块编码方式，而采用以小波变换 ( w a v e l e tt r a n s f o r m ) 为主的多解析编码方式。并将j p e g 的四种模式( j i l 顷序模式、渐 进模式、无损模式和分层模式) 集成在一个标准之中。作为j p e g 标准的一个更新 换代标准，j p e g 2 0 0 0 能够提供更好的图像质量、更低的比特率，满足一些特殊特 性的要求( 渐进传输和感兴趣区域编码等) 。但在一些低复杂度的应用中，j p e g 2 0 0 0 不可能代替j p e g ，因为j p e g 2 0 0 0 的算法复杂度不能满足这些领域的要求。在大 多数的场合下，采用j p e g 就可以满足要求了。j p e g 应用的领域包括互联网、彩 色传真、打印、扫描、数字摄像、遥感、移动通信、医疗图像和电子商务等等。j p e g 在数码相机、p d a 、手机等手持设备和嵌入式设备中的使用正方兴未艾。 1 4 本文的主要工作 j p e g 图像编码是目前非常流行的一种压缩方法，本文介绍了j p e g 图像的编解 第一章绪论 码原理、编解码的主要流程和h u f f m a n 编码原理，仔细分析研究了j p e g 标准图像的 编码格式和j p e g d 、组推荐的四个h u f f m a n 码表，提出了一种可行的应用于j p e g 图 像解码的h u f f r n a n 压缩方法的v l s i 设计思想，并对设计的方法进行了仿真验证，证 实了该设计方法的可行性。整个设计采用模块化设计，简洁高效，易于实现。 1 5 本文的章节安排 论文第一章绪论介绍了论文选题的意义、主要研究内容及论文各章节安排。 论文第二章介绍j p e g 图像的编解码原理。对j p e g 图像编解码流程中的各个模 块中使用的方法，都做了详细的讲述。尤其是对其中的主要模块h u f f m a n 编码的 基本原理做了详细的说明。证明了为什么h u f f m a n 编码是目前最优的变长编码，如 何生成h u f f m a n 树以及j p e g 图像编解码中h u f f m a n 表示如何建立的。 论文第三章j p e g 图像h u f f m a n 解码器的v l s i 设计，介绍了本文的主要工作， 应用于j p e g 图像解码的h u f f m a n 解码器的总体方案设计以及具体模块的设计方案 和仿真。这一部分是根据j p e g 标准的码流格式，对j p e g d , 组推荐的码表进行研究 分析，提出来的一种并行的设计思想，文中对每个模块的设计思想都有详尽细致 的解释，并用v e r i l o g 硬件描述语言编写代码，进行了时序仿真。证明了这种设计 思想的可行性。 论文第四章总结。 第二章j p e g 图像标准及h u f f m a n 编解码原理 第二章j p e g 图像标准及h u f f m a n 编解码原理 j p e g 标准是静态图像编码中最常用的，是在牺牲较少细节的情况下用典型的 4 ：1 到2 0 ：1 的压缩比来存档静态图像的，一张3 0 4 0 2 0 1 6 2 4 b 的图像，在j p e g 中只有1 m b 左右大小，相对于b m p 等格式而言，品质相差无己而压缩率却高得 多，无论是传送还是保存都更加方便。j p e g 编码中使用的h u f f m a n 算法目前来说 是一种最优的无损熵编码，应用极其广泛。本章就对j p e g 标准基本系统和h u f f m a n 算法做详细的介绍。 2 1j - p e g 编解码流程 基线( b a s e l i n e ) 系统使用有损的、连续的d c t 序列、h u f f m a n 编码，b a s e l i n e 这个词把基于d c t 的顺序编码限制在一个特定的编码顺序里，要求： 1 图像的每一个颜色分量使用8 位精度； 2 仅使用h u f f m a n 编码； 3 每次扫描最多使用2 组d c 和a ch u f f m a n 表； 具体的流程如图2 1 所示： 8 x 8 原始 图像数据 8 x 8 恢复 图像数据 d c t 变换卜叫量化器卜- 叫熵编码器 量化表il 熵编码表 y c 疋b r g b _ 一逆d c t 变换h _ 一逆量化器卜一熵解码器 图2 1j p e g 编解码过程幽 编解码算法的主要计算步骤如下： ( 1 ) 色空间变换( c o l o rt r a n s f o r m ) 。 ( 2 ) 离散余弦变换( d c t & i d c t ) 。 ( 3 ) 量化与反量化( q u a n t i z a t i o n & i n v e r s eq u a n t i z a t i o n ) 。 ( 4 ) z 字形扫描( z i 配a gs c a n ) 。 存 储 盟 - 二，c 6 j p e g m j p e g 中h u f f m m 编解码的i p 设计 ( 5 ) 使用差分脉冲编码调锘l j ( d i f f e r e n c ep u l s ec o d em o d u l a t i o n ，简称d p c m ) 对直流 系数( d c ) 进行编码。 ( 6 ) 使用行程长度编f - 马( r u n - l e n g t he n c o d i n g ，简称a l e ) 对交流系数( a c ) 进行编码。 ( 7 ) 熵编码( e n t r o p yc o d i n g ) 。 2 1 1 色空间模型【1 9 j 匮h c r 裂1 6 9 - 0 瓢3 3 1 0 5 斟0 0 圈g + 1 2 。8 c b 05 0 0 - 04 1 9 - 00 8 1b 1 2 8 p ， ll = i o i + i( 2 1 ) i iiil - r - 1 1 4 0 3 0 f - 】， l b 1 0 1 7 7 0 儿c b j 2 1 2d c t & i d c t 选择不同的正交基向量，可以得到不同的正交变换。在均方误差准则下，当 信号的统计特性符合一阶平稳马尔柯夫过程，而且相关系数接近1 时，d c t 变换 仅次于k l t 变换，称为准最佳变换，变换后的能量集中程度较高。即使信号的统 计特性偏离这一模型，d c t 的性能下降也不显著。加上其基向量是固定的，并具 有快速算法等原因，它在图像数据压缩中得到了最广泛地应用。 j p e g 标准中规定将图像分成8 8 大小的像素块后再进行变换，相邻元素间 存在很强的相关性，而d c t 变换的目的就是消除这种相关性，经过正变换所得到 第二章j p e g 图像标准及h u f f m a n 编解码原理 7 的结果就为d c t 系数，f ( 0 ，0 ) 称为直流系数( d c ) ，d c 值表示了变换前块中全 部像素值的平均数，其他的6 3 个系数称为交流系数( a c ) 。d c t 变换后系数存 在这样的特点：随着与d c 系数距离的增加，a c 系数的值越来越小。 因为d c t 变换是在实数域运算，而且还具有可分离性，不牵扯复数运算，算 法简单，而且还可以采用降阶处理，所以d c t 算法是目前使用最广的一种算法， 目前有很多种实用的方法，例如c h e n 算法、w a n g 算法、h a q u e 算法等，这些算法 都在不同程度上降低了二维d c t 的算法难度。 图2 2 是d c t 变换前后的系数的对比，由图可以看出，变换前的6 4 个系数经 过d c t 变换后，绝大多数系数都变为零，编码时，只需要对几个系数编码即可， 这样就大大的降低了要编码的数据量，实现压缩。 5 79986677 2oo。7oo o 0 891 0 1 08891 0 80 oooo0 o 7886557 9 000 ooo 0 o 9 1 01 09 8891 1 入 o o 60oo0 0 81 0111 11 0991 0 v oo0 oo00 o 681 01 19888o00 000o 0 1 0 1 2 1 31 21 11 0l11 28oo 0oooo 1 01 1l19881 0 1 2o00oooo o d c t 变换前的系数d c t 变换后的系数 图2 2d c t 系数变换前后的对比图 d c t 变换是将图像从空间域变换到频率域。在系数块即频域中，低频分量都 集中在左上角，高频分量分布在右下角( d c t 变换可看作是空间域的低通滤波) 。 由于该低频分量包含了图像的主要信息，相比之下，高频就不那么重要了，基于 d c t 变换的j p e g 图像压缩标准就是通过轻视或忽略高频分量来减少信息量的。 通过逐渐减少低频系数进行编码后的恢复图像与原图像的对比。 d c t 是目前比较好的图像变换，具有很多优点。首先d c t 是正交变换，它可 以将n n 图像的空间表达式转换到频率域，只需要用少量的数据点表示图像； 其次d c t 产生的系数可以被量化，因此能获得好的块压缩；再者，d c t 算法的性 能好，有快速算法，类似采用快速傅立叶变换( f f t ) 。因此，d c t 在硬件和软 件中都容易实现，同时，d c t 算法是对称的，d c t 在精度较大的运算范围内是可 逆的，即基本上是无损的，因此，逆d c t 算法可以直接用来解压缩图像。 2 1 3 量化反量化 为了达到压缩数据的目的，对d c t 系数需作量化处理。量化处理是一个多到 8 j p e g m j p e g 中h u f f m a n 编解码的i p 设计 一的映射，这是造成d c t 编解码信息损失的根源。在j p e g 标准中采用线性均匀 量化器。量化定义为，对6 4 个d c t 变换系数f ( u ，) 除以量化步长q ( u ，v ) 后四舍 五入取整，即 c ( u ，1 ，) c ( u ，v ) f ( 材，v ) + 1 q ( “，v ) f ( “，v ) 一1 q ( “，v ) q ( u ，v )f ( u ，v ) 0 ( 2 - 3 ) q ( u ，v )f ( u ，) 0 量化表的值个数也是6 4 ，与6 4 个变换系数一一对应。每一个元素值为1 至2 5 5 之 问的任意整数，其值规定了对应位置变换系数的量化器步长。在接收端要进行反 量化，反量化的计算公式为： f ( u ，v ) = c ( u ，1 ，) q ( u ，v ) ( 2 - 4 ) 若把量化阶距q ( u ，v ) 记为，则式中绝对值小于a 2 的d c t 系数都被量化为o ， 能有效地抑制弱小信号及背景噪声，有利于熵编码压缩。 不同频率的余弦函数对视觉的影响不一样，可根据不同频率的视觉阂值来选 择量化表中的元素值的大小，量化处理是在一定的主观保真度的前提下，丢掉那 些对视觉影响不大的信息。根据心理视觉加权函数得到亮度量化表和色度量化表。 d c t 变换系数f ( u ，v ) 除以量化表中对应位置的量化步长，其幅值下降，动态范围 变窄，高频系数的零值数目增加。表2 1 是j p e g 推荐使用的量化表【l 】。 表2 1j p e g 推荐使用的亮度和色度量化表 亮度量化表 1 6 l l 1 01 6 2 44 05 16 l 1 2 1 21 41 92 65 8 6 05 5 1 41 3 1 6 2 44 05 76 95 6 1 41 72 22 9 5 l 8 78 06 2 1 82 2 3 7 5 66 81 0 91 0 37 7 2 43 5 5 5 6 48 11 0 411 39 2 4 96 4 7 8 8 710 312 112 01 0 1 7 29 29 59 811 21 0 0 10 39 9 色度量化表 1 71 82 44 79 99 99 99 9 1 8 2 1 2 6 6 69 99 9 9 9 9 9 2 42 65 69 99 99 99 99 9 4 76 69 9 9 9 9 99 98 09 9 9 99 9 9 9 9 99 99 99 99 9 9 99 9 9 99 99 9 9 99 99 9 9 99 99 99 99 99 99 99 9 9 99 9 9 99 9 9 99 99 99 9 对j p e g 而言，6 4 个变换系数经量化后，d c 系数是6 4 个图像采样的平均值。 8 8 数掘块经过d c t 变换之后得到的d c 直流系数有两个特点：一是系数的数值 比较大，二是相邻8 8 图像块的d c 系数值变化不大。 j p e g 编码失真主要来源于d c t 系数的量化噪声，适当地选取量化表对图像质 第二章j p e g 图像标准及h u f f m a n 编解码原理 9 量的影响很大，因此，量化表的选取还要考虑人的视觉对各频率分量的心理阈值。 2 1 4z i g z a g 扫描 经过d c t 变换、量化后，二个8 8 的数组变换成另一个8 x 8 的数组。但是 内存里所有数据都是线性存放的，如果按行的顺序存放这6 4 个变换系数，每行的 结尾的点和下行开始的点就没有什么关系，所以j p e g 规定按如图2 3 的次序整理 6 4 个数据，就是所谓的z 字形扫描。这样可以使得相同或相邻频率的系数在一维 序列中保持相邻的位置，即8 8 的系数矩阵可以按频率由低到高的顺序排列成一 个长度为6 4 的d c t 系数向量。 ol5 6 1 4152 72 8 2 47 1 3 1 62 6 2 9 4 2 381 2l72 53 04 14 3 9 1 1 1 82 4 3 14 04 4 5 3 l o19 2 3 3 23 94 55 25 4 2 02 23 33 8 4 65 1 5 56 0 2 l3 43 74 75 05 65 96 1 3 53 64 84 95 75 86 26 3 7厂。7厂。7厂。7 么么_ 么_ 。 么_ 图2 3 z i g z a g 扫描示意图 量化a c 系数的特点是1x 6 4 矢量中包含有许多“0 ”系数，并且许多“0 是 连续的，经“z ”字形路径扫描，可使值为零的a c 系数尽可能的集中，便于使用 游程编码的方法。 2 1 5 差分编码与游程编码 经过量化，下一步的操作就是对量化后的数据进行编码，j p e g 基本系统使用 的编码方式为差分脉冲编码调制、游程编码矛d h u f f m a n 编码。 差分脉冲编码调制是在p c m 的基础上加以改进。它不对原始取样值编码，而 是用第二次取样值与第一次取样值的差，即增量来进行编码。由于相邻信号之间 的幅度差别不会很大，原始信号本身的大小也无关紧要，所以，要达到与p c m 同 样的量化精度，量化比特就可以少用几位。 游程编码是一种非常简单的编码方法，它将数据流中连续出现的数据( 称为游 1 0 j p e g m j p e g 中h u f f m a | l 编解码的i p 设计 程) 用该数据以及它连续出现的个数来表示。例如： 假设有一段数据流是这样的 o a o a o a o a o d o d o d o f o f o f o f o f o f o f 经过游程编码后，该数据流可以表示为： 0 4 0 a 0 3o d 0 7 0 f 很显然，这种编码方法实现了数据的压缩。由于这种方法编码和解码的算法都非 常简单，因此得到了广泛的应用。 在j p e g 编码中，对直流系数的编码就是采用的差分脉冲编码调制。因为相邻 的8 8 数据块之间有很强的相关性，所以相邻块的d c 系数值很接近，对相邻图像 块之间量化d c 系数的差值( d e l t a ) 进行编码： d e l t a = d c ( o ，o ) t d c ( o ，o ) ( 2 - 5 ) 这样可以用较少的比特数表示。解码时，只要将该点的d c 系数值加上前一个d c 系数的值就可以了。 在j p e g 编码中，6 3 个a c 系数的游程编码和码字，可用两个字节表示。因此使 用非常简单和直观的游程长度编码( r l e ) 对它们进行编码。j p e g 使用了1 个字节的 高4 位来表示连续“0 ”的个数，而使用它的 f l 毳4 位来表示编码下一个非“0 ”系数 所需要的位数，跟在它后面的是量化a c 系数的数值。 2 2h u f f m a n 编解码原理 数据压缩可分为两种类型，一种叫做无损压缩，另一种叫有损压缩。无损压 缩是指使用压缩后的数据进行重构，或者叫做还原、解压缩，重构后的数据与原 来的数据完全相同。无损压缩是对信源熵冗余信息的压缩。h u f f m a n 编码就是其中 的一种无损熵编码。 2 2 1 熵的概念及其与数据压缩的关系 熵作为信息量的一种度量，可以看作是信源概率分布的泛函数。因为熵可以 反应信源的冗余信息，所以它也能反应出数据压缩的可能性，在信息论中，用概 率的负对数来定义不肯定性，即事件a 的不肯定性可定义为： f ( p ) = - l 0 9 2p( 2 - 6 ) 其中p 为事件a 所发生的概率，f 表示不确定性，单位是比特( b i t ) 由于对一个信源 来说，它可能发送各种不同的事情，因此对上述的不肯定性做统计平均，就得到 第二章j p e g 图像标准及h u f f m a n 编解码原理 11 平均信息量的概念。假设信源s 发出事件q ，a 2 ，的概率分别是五，只，则它 的平均信息量h ( s ) 定义为： 一 日o ) = 一p ，l 0 9 2 b ( 2 7 ) f = l 其中b = 1 ，p j o ；因为这里的h ( j ) 与热力学中熵的表达式相似，故平均信息 f 量习惯上称为信源的熵。 熵就是信源发出的事情的不肯定性的数学期望，可以理解成事件随机性的度 量。当信源中的各种事件服从等概率分布时，平均信息量即达到最大值。但是事 实上信源的熵总是低于它的最大熵l o g ，n 。信源的熵与其最大熵的差值定义为信源 的冗余度，使熵达到或逼近最大熵的过程，就是统计编码。也可以说统计编码是 改变信源原有概率分布，使之达到或接近等概率分布，h u f f m a n 编码是一种统计编 码。 2 2 2h u f f m a n 编码的最优性【2 0 】 统计编码从码字长度上分为变长码和定长码。信号经过去除相关性后，其冗 余度还存在于概率分布的非均匀性中，若用变长码字表示信源发送的各个事件， 可以使码字中的符号达到或接近信源的最大熵，这就是变长码的基本思想。变长 码编码是一种很重要的统计编码方法，而h u f f m a n 编码是迄今为止最优的一种变长 码。 h u f f m a n 编码是根据变长码的理论。在变长编码中，输出码字的字长是不相等 的。基本原理是对出现频率较高的信息赋予较短的字长，对于出现频率较低的信 息赋予较长的字长。h u f f m a n 编码和标准变长码法的区别在于码表的确立上， h u f f m a n 编码的码表是由原文件数据中符号的出现频率确定的，这个码表唯一适用 于该原文件，对该文件来说是最优的，而标准码表是适用于一类文件，不是最优 的。h u f f m a n 编码被称为最优变长码。因为至今各种变长码中以h u f f m a n 码的平均 码字长度为最小。 在信息论中五条定理保证了h u f f m a n 码的这种最优性： 定理一：设有一类非续长码，它所对应的概率分布为，鼻，罡，己如果码c 在这一 类非续长码中为最优，那么对应的全部可译码来说，码c 也为最优。 定理二：某码树的终端节点集合是完全的，其充要条件为： m ，z m = 1 ( 2 8 ) 一 、 1 2 j p e g m j p e g 中h u f f m m 编解码的i p 设计 其中m 为节点次数。 定理三：具有m 个终端节点的完全码树存在的充要条件为，存在某个非负整数y ， 且使 m = y ( n 1 ) + 聆 ( 2 - 9 ) 成立。 定理四：设a - - o ，1 ) ，对于满足式丑最的信源x 来说，则一定存在这样 的最优码，即码字儿一。与以具有相同的长度，且此一1 的最后一个字符为o ，虬的最 后一个字符为1 。 定理四暗示- j h u f f m a n 编码的构码过程。根据定理四，以一。与具有相同的长 度，只是末位不同，因此可以将4 ，一。与4 两事件合并为一个事件，用彳川表示， 概率为两事件概率之和，4 一，与4 ，两事件合并后在么州后添o 或1 就可以分别得到 4 一。与4 ，这样使得事件个数减少了1 个。 定理五：假设对于x 有满足非续长性的最优码c ，那么按上述方法得到的对应于 x 的非续长码也是最优的。 以上五条定理是保证h u f f m a n 码是最优变长码的理论依据。为具体h u f f m a n 编 码器和解码器的实现提供了依据。 2 2 3h u f f m a n 树的生成 设计h u f f m a n 码表的过程，实际上是建立一棵码树的过程，首先将信源按概率 大小顺序排列。然后，在分配码字长度时，将出现概率最小的两个符合的概率相 加，合成一个概率；把这个合成的概率看成一个新组合符号的概率，重复上面的 做法，直到最后只剩下两个符号的概率为止。完成以上概率相加顺序排列后，再 反过来逐步向前进行编码。每一步有2 个分支，各赋予一个二进制码，如对概率大 的赋编码为0 ，概率小的赋为1 。具体步骤归纳如下： ( 1 ) 概率统计( 如对一幅图像做灰度信号统计) ，得到n 个不同概率的信号符号。 ( 2 ) 将n 个信源信息符号按概率大小排序。 ( 3 ) 将n 个概率中最后2 个小概率相加，这时概率个数减为n 1 个。 ( 4 ) 将剩下的n 1 个概率，按大小重新排序。 ( 5 ) 重复4 ，直到剩下两个概率序列为止。 ( 6 )以二进制码元( o ，1 ) 赋值，构成h u f m a n 树。 举个例子：假设一个文件中出现了8 种符号s 0 、s 1 、s 2 、s 3 、s 4 、s 5 、s 6 、 s 7 ，那么每种符号要编码，至少需要3 比特。假设编码成0 0 0 、0 0 1 、0 1 0 、0 11 、 1 0 0 、1 0 1 、1 1 0 、1 11 ( 称做码字) 。那么符号序列s o s l s 7 s o s l $ 6 s 2 s 2 s 3 s 4 s 5 s o s o s l 第二章j p e g 图像标准及h u f f m a n 编解码原理 1 3 编码后变成0 0 0 0 0 1111 00 0 0 0 111 0 0 1 0 0 1 0 0 111 0 0 1 0 1 0 0 0 0 0 0 0 0 1 ，共用了4 2 比特。 研究发现s o 、s 1 、s 2 这三个符号出现的频率比较大，其它符号出现的频率比较小， 如果采用一种编码方案使得s 0 、s l 、s 2 的码字短，其它符号的码字长，这样就能 够减少占用的比特数。例如，可以采用这样的编码方案：s 0 到s 7 的码字分别为 0 1 ，1 1 ，1 0 1 ，0 0 0 0 ，0 0 0 1 ，0 0 1 0 ，0 0 11 ，1 0 0 ，那么上述符号序列变成0 11 11 0 0 0 1l1 0 0 11 1 o “0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 11 1 ，共用了3 9 比特，尽管有些码字如s 3 、s 4 、s 5 、s 6 变 长了( 由3 位变成4 位) ，但使用频繁的几个码字如s o 、s 1 变短了，所以实现了压 缩。编码必须保证不能出现一个码字和另一个的前几位相同的情况，比如说，如 果s 0 的码字为0 1 ，s 2 的码字为0 1 1 ，那么当序列中出现0 1 1 时，不知道是s o 的 码字后面跟了个l ，还是完整的一个s 2 的码字。h u f f m a n 编码能够保证这一点。 依据前面给出的h u f f m a n 编码的步骤，对应如下步骤生成码字： ( 1 ) 首先统计出每个符号出现的频率，上例s 0 到s 7 的出现频率分别为4 1 4 、3 1 4 、 2 1 4 ，1 1 4 ，1 1 4 ，1 1 4 ，1 1 4 ，1 1 4 。 ( 2 ) 从左到右把上述频率按从小到大的顺序排列。 ( 3 ) 每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节 点，这两个叶子节点不再参与比较，新的根节点参与比较。 ( 4 ) 重复( 3 ) ，直到最后得到和为1 的根节点。 ( 5 ) 将形成的二叉树的左节点标0 ，右节点标l 。把从最上面的根节点到最下面的 叶子节点途中遇到的0 、l 序列串起来，就得到了各个符号的编码。 4 1 4 ( 4 k ， o o 1o 1 1 1 4o1 1 4 0 1 1 4o1 1 4o1 1 4 0 2 1 4o3 1 4o4 1 4 0 s 3s 4s 5s 6s 7s 2s 1s 0 0 0 0 00 0 0 10 0 1 00 0 1 11 0 01 0 l 1 1 o l 图2 4h u f f m a n 编码树的生成示意图 2 1 4 j p e g m j p e g 中h u f f m a n 编解码的i p 设计 上面的例子用h u f f m a n 编码的过程如图2 4 所示，其中圆圈中的数字是新节点 产生的顺序。 产生h u f f m a n 编码需要对原始数据扫描两遍。第一遍扫描要精确地统计出原 始数据中，每个值出现的频率，第二遍是建立h u f f m a n 树并进行编码。由于需要 建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但简单有 效，因而得到广泛的应用。 2 3j p e g 中h u f f m a n 表的建立 熵编码可分成两步进行；首先把d c 和a c 系数转换成一个中间格式的符号序 列，第二步是给这些符号赋以变长码字。对d c t 系数进行h u f f m a n 编码分为直流分 量和交流分量两种编码方式。 h u f f m a n 编码过程用于8 位采样精度，编码器在一扫描行内最多可以使用两个 d c 和两个a ch u f f m a n 表。 ( 1 ) d c 系数的h u f f m a n 编码 d c 码表由一组h u f f m a n 代码( 最大长度为1 6 位) 和附加位组成，附加位可对差分 值d i f f 的可能值进行编码。生成用于差分值分类的h u f f m a n 代码时，要保证没有一 个代码完全由值为1 的位组成。 表2 2 用于d c 差分量的编码分类 分类( s p )差分值( d i f fv a l u e ) o0 1 1 ，1 2 - 3 , - 2 ，2 ，3 3 - 7 ，一4 ，4 ，7 4 - 1 5 ，- 8 ，8 ，1 5 5 - 3 l ，- 1 6 ，1 6 ，3 1 6 - 6 4 , - , - 3 2 ，3 2 ，6 3 7 1 2 7 ，- 6 4 ，6 4 ，1 2 7 8 2 5 5 ，一1 2 8 ，1 2 8 ，2 5 5 9 - 5 11 ，- 2 5 6 ，2 5 6 ，5 11 1 0 1 0 2 3 ，- 5 1 2 ，5 1 2 ，1 0 2 3 1 1 2 0 4 7 ，- 1 0 2 4 ，1 0 2 4 ，2 0 4 7 d c 的补码差分量被分成1 2 组不同的编码分类( s p ) ，并且为1 2 个差分量分类中 的每一个创建h u f f m a n 代码。对于每一分类( 除y s p = o ) 外，要把一额外位附加到 代码字上，以便唯一地识别在那个分类中实际发生哪一个差分值。额外位的位长 由s p 给定，额外位被附加到前缀型h u f f m a n 代码的l s b 上( 最高有效位优先) 。当d i f f 是正值时，d i f f 的s p 低序位被附加；当d i f f 是负值时，d i f f 一1 的s p 低序位被附 第二章j p e g 图像标准及h u f f m a n 编解码原理 1 5 加。注意，对于负的差分值，附加位序列的m s b 为0 ；对于正的差分值，附加位序 列的m s b 为1 。 表2 3亮度、色度的d c 系数差分h u f f m a n 表 亮度d c 系数差分h u f f m a n 表色度d c 系数差分h u f f m a n 表 分类 码长 码字 o20 0 l30 1 0 23o l l 331 0 0 431 0 l 531 1 0 6 4 11 1 0 751 1 1 1 0 861 11 11 0 97l l l l l l o 1 081 1 1 1 1 1 l o 1 l91 1 1 1 1 1 1 1 0 分类 码长 码字 020 0 l20 1 221 0 331 1 0 441 11 0 551 11 1 0 661 1 1 1 1 0 771 1 1 1 1 1 0 881 1 1 1 1 1 1 0 991 1 1 1 1 1 1 1 0 1 0l o1 1 1 1 1 1 1 1 1 0 l1111 1 1 1 1 1 1 1 1 1 0 根据d i f f 值，查找表2 2 ，可以得n s p ，再根据s p 查找表2 3 ，就可以得到差分 值的h u f f m a n 代码，即d c 编码= 哈夫曼识别码(