（电路与系统专业论文）基于JPEG2000二进制算术编码器的研究与设计[电路与系统专业优秀论文].pdf

摘要 摘要 随着计算机和数字通信技术的迅速发展，通信的带宽和容量受限，图像和视 频的编码和压缩成为研究的热点。算术编码作为种重要的熵编码方法，具有卓 越的编码性能，在任何情况下，它的平均码长都能逼近信源的熵。因此，算术编 码的研究越来越受到重视，并已被纳入许多图像和视频国际标准中。 j p e g 2 0 0 0 是联合图像专家组于2 0 0 0 年1 2 月通过的新一代静止图像压缩标 准。它不仅提供了超越j p e g 的压缩性能，更提供了系列丰富的功能，以满足 对图像编码技术日益增长的需求。它采用上下文自适应的二进制算术编码进行熵 编码运算，m q 编码器是该算术编码的具体实现形式。 本文详细深入的研究了算术编码的原理，探讨了无乘法器的二进制编码形 式、条件交换机制和自适应概率估计等重要概念。通过分析m q 编码中的关键运 算细节并优化算法，在给出一种一个时钟周期处理1 位符号的三级流水线m q 编 码器实现结构的基础上，为了达到更高吞吐率的要求，本文探讨了2 个符号的并 发编码，就设计中的难点进行分析，并提出相应的解决策略，最终实现了一种4 级流水线的2 个符号并发编码架构。 本文采用v e r i l o g 硬件描述语言对提出的结构进行寄存器传输级描述，并完 成了功能上的仿真验证，给出了仿真结果。性能比较分析结果显示，第一种结构 工作频率为2 0 0 m h z ，消耗7 4 8 6 逻辑门；本文绘出的2 个符号并发编码的结构， 工作频率达到1 4 3 m k ，消耗1 2 5 4 7 逻辑门，它能满足高吞吐率的要求，在1 秒 中内可处理约4 7 1 0 6 狄度图像象素，更好的匹配并行结构的位平面编码器。 关键字：二进制算术编码；j p e g 2 0 0 0 ；m q 编码器；v l s i a b s t r a t a b s t r a t w i t ht h er 印i dd e v e l o p m e mo fc o m p u t e ra 1 1 dd i g i t a lc o m m u n i c a t i o n ，i m a g e c o m p r e s s i o ni sb e c o m i n ga r e s e a r c hf o c u ss i n c et h eb a n d w j d t ha n dc a p a b i l i t yo f c o m m u n i c a t i o n si s1 i m i t e d a sa ni m p o n a i l te n t r o p yc o d i n gm e t l l o d ，a r i t l l l n e t i cc o d i n g h a s “c e l l e mp e r f o r m a n c e ；i t sa v e r a g ec o d el e n 垂h c a na l w a y s 印p r o a c ht l l e i n b r m a t i o ns 洲r c e se n t r o p y ，a n di t sr e l a t e dt e s e a r c hi sc o n c e m e di n c r e a s i n g l y m 汕m e t i cc o d i n gi sa d o p t e db ym a n yi n t e i m t i o n a ls t a t l d a r d sa se s s e n t i a le l e m e m j p e g 2 0 0 0i st h en e x tg e n e r a t i o nd i g i t a ls t i l li m a g ec o m p r e s s i o ns t a l l d a r d i n t r o d u c e db yj o i n tp h o t o g r a p h i ce x p e r t sg r o u pi nd e c e m b e r ，2 0 0 0 j p e 0 2 0 0 0 p r o v i d e sn o to n l ys u p e r i o rc o m p r e s s i o np e i f o m l a n c eo v e rj p e gb u ta l s oar i c hs e to f f e a f u r e s ，i na i l s w e rt ot h ee v e rg m w i n gr e q u i r e m e n t sf o ri m a g ec o d i n gt e c l l i l i q u e s m qe n c o d e rj sa d o p t e da si t se n t r o p ym e t h o d i n t h i st l l e s i s ，t h e o r yo fa r i t l l i n e t i cc o d i n gi sr e s e a r c h e dc a r e f h l l y ，a i l ds o m e i m p o r t a i l tc o n c e p ta b o u tb i n a r ya r i t h r n e t i cc o d i n gi sd i s c u s s e d ，s u c ha sm u h i e - 行e e ， c o n d i t i o ne x c h 锄g ea n da d a p t i v ep r o b a b i l i t ye s t i m a t i o n b yo p t i m i z i n ga l g o r i m m s a n da n a l y z i n gt h ed e t a i l so fm qe n c o d i n g ，at h r e ep i p e l i n e da r c h i t e c t u r eo fm q e n c o d e rw h i c hc a no p e r a t eo n es y m b o lp e rc l o c kc y c l ei si n t r o d u c e d i no r d e rt or e a c h l l i g h e rt l l r o u 曲p u t sr e q l 】i r e m e n t ，p a r a l l e le n c o d i n gt 、v os y m b 0 1 ss y n c h m n o u s l yi s d i s c u s s e d b y 锄a l ”j n gt h ed e s i 印sd i m c u l t i e sa i 】d 西v i n gc o h e s p o n d i n gs o l v i n g s t r a t e g y ，af b l l rp i p e l i n e ds t a g e sa r c h i t e c t l l r ei si m p l e m e n t e df i n a l l y 1 1 1 eg i v e n 踟h i t e c t 盯ei sd e s c r i b e d 晰t l lv e r i l o gh d li nr e g i s t e rt r a n s f e rl e v e l ( r t l ) ，a n ds i m u l a t e dt ov e r i f yt h ef 弧c t i o n a lc o r r e c t i o n b yc o m p a r e da n da i l a l y z e d t h ep e r f o m a l l c e s ，t h ef i r s ti m r o d u c e da r c l l i t e c t l l r ec a i lw o r ka t2 0 0 m h z ，c o n s 啪e d 7 4 8 6l o g i cg a t ec o u m s ；聃，h i l et 1 1 es e c o n d 西v e na r c h i t e c t u r ec a nw o r ka t1 4 3 m h z ， c o n s 啪e d1 2 5 4 7l o g i cg a t ec o u m s n es e c o n da r c h i t e c t u r ec a no p e r a t e4 7 l o o p i x e l s ，sf o r 笋a y s c a l ei m a g e ，w h j c hm e e t st b eh i g h e rn o u 曲p u t 。sd e m a n d st om a t c h t h ep a r a e lb j tp l a i l ee n c o d e rb e t t e l k e yw o r d s ：b i n a r ya r i t h m e t i cc o d i n g ；j p e g 2 0 0 0 ；m qe n c o d e r ；v l s i 第l 章绪论 随着多媒体技术和网络的发展，信息总量急剧增大，电脑硬盘存储容量的发 展给了我们最直观的体会。由于存储空间和带宽受限，数据难以赢接存储或者转 换，所以往往需要通过压缩，这就促成了数据压缩技术在近几十年来的巨大发展 和进步。近年来，多媒体技术发展迅猛，诸如数码相机、v c d 、d v d 、高清数 字电视、视频会议等都在影响并改变着我们的生活风格，已成为推动图像压缩技 术发展的重要市场动力；图像编码技术的研究及其v l s i 实现也因此成为非常活 跃的研究领域。 1 1 信息冗余和信息熵的概念 图像信息的压缩编码是依据图像信号固有的统计特性和人类的视觉特性进 行的。通常图像中含有大量的信息冗余，主要分为三类1 1 】： 1 1 空间冗余，由于相邻象素之间存在关联而产生。 2 1 频谱冗余，由不同彩色平面或频谱带的相关性造成。 3 ) 时间冗余，由图像序列不同帧的相关性而引起。 正是由于图像中含有大量的冗余，给图像压缩编码很大的研究空间。本质上， 编码与压缩就是对要处理的源数据按一定的规则进行变换和组合，从而达到以尽 可能少的比特数( 符号) 来表示尽可能多的数据信息。图像压缩的基本理论起源 于2 0 世纪4 0 年代s h a i l i l o n 划时代的论文【2 】该论文奠定了信息论的基础。从概 率统计学的角度来看，信息量定义为信源发出的所有信息中该信息出现概率的负 对数，信息熵表示平均信息量，如式( 1 1 ) 所表示： h ( x ) = 一 ( x ) l o g ： ( x ) ( 1 1 ) x e a x 其中，表示随机变量，与之相对应的是所有可能输出的集合，定义为符 号集以，随机变量的输出用x 表示。厶( x ) = p ( 工= z ) ，表示输出概率函数。 熵的一个重要价值在于它定义了一个关于编码性能的根本界限。这在 s h a n n o n 的“无噪声信源编码定理”中第一次得到阐述。这个定理的本质是：随 机过程的熵率提供了对它的每一个输出进行编码所花费的平均位数的下界，而且 绪论 当编码方案的复杂度允许无限制增长时，可以任意逼近这个下界1 3 j o 基于这个理 论框架，产生了很多种不同的熵编码方法。 1 2 熵编码技术 应用于数据压缩的编码技术很多，就方法而言主要有两类：基于统计和基于 字典。基于统计的方法就是上一小节中讲到的基于s h a n n o n 定理的可变长的熵编 码，主要包括香农一费诺编码、行程编码( r l c ) 、霍夫曼( h u m n a l l ) 编码、g 0 1 0 m b 编码、算术编码等。基于字典的方法通常是定长编码，有l z w 编码等。 不同的数据源相应于彳i 同的压缩编码方法。在图像压缩编码中，熵编码得到 了广泛的研究和使用。下面对几种常用的熵编码技术作概要的阐述。 1 2 1 行程编码 在一些待编码的信源序列中，某些符号经常连续出现，比如在二进制传真图 像中就会出现连续的o 或者连续的1 ，在经过变换编码和量化以后的图像系数， 也经常会出现连续的o 。在这样的情况下，就可以使用行程编码。在图像有失真 的压缩编码中，最为常用的行程编码方式是零行程，在这种情况下，可以用( 厶n 来表示，行程数三表示连续的0 的个数，y 表示o 串后紧跟的非零值。在实际应 用中，行程编码的上和矿可以分别用h u 茄m a n 编码或算术编码进一步压缩。 1 2 2h u m n a n 编码 h u 龋1 a l l 编码是一种形成前缀变长编码的方法。它根据信源中每个符号的出 现概率进行码字分配，出现概率较小的符号分配较长的码字，出现概率较大的符 号分配较短的码字。它先将信源中各符号按出现概率的大小排成一列，出现概率 最大的符号放在最顶部，出现概率最小的符号放在最底部。将最底端的两个概率 赋予0 和1 码，这样持续循环到最顶端，形成霍夫曼树。这样每个符号都是一个 树的端节点，可以得到一个符号前缀条件的码字，这就是h u m n a n 编码的方法。 h u f r m a l l 编码有其本身的合理性，但显然，它不是遵循s h 蛐o n 在信息论当 中所给出的最佳编码。因为h 硼f m 锄编码只注重频繁出现的那部分符号 4 】。 绪论 1 2 3 算术编码 算术编码的基本思想是用区域划分来表示信源输出序列，信源输出的任何一 种组合，与【0 ，1 ) 区间内的某一区域一一对应。用算术方法表示这一区域为一个 二进制小数。这个二进制小数是信源输出序列的种编码，且它是唯一可解码的。 算术编码的编码过程与信源的概率模型是分离的。在实际中使用概率估值表。详 细的算术编码原理将在后续章节中介绍。 1 3 算术编码的发展历程 算术编码的基本思想是以二进制小数表示一串符号。这一思想最先于1 9 4 8 年s h a n n o n 划时代的论文中提出【2 】即一个n 符号的消息可以通过先对符号的 概率进行排序，再按照该顺序发送符号的累计概率来传输。而后，p e t e re l i a s 发 现s h a n n o n 的方案可以不通过概率排序，而以递归的划分子区间的方式进行。 1 9 6 3 年，a b a m s o n 在其著作中提到了p e t e re l i a s 的这一结果既j e l i n e k 研究了 e 1 i a s 编码嘲。s h a i l i l o n 和e 1 i a s 编码存在无限精度运算的问题，即随着编码消息 长度的增加，递归运算需要的计算精度也随着增加。若使用有限精度系统进行编 码，则编码每个符号所需的时间随编码序列的增长线性增加。 1 9 7 2 年，s c h a l k w n k 从索引的角度提出了另一类似的编码系统【7 j o 它提供给 码串一个索引来编码字符，随着符号编码的增加，索引的大小也增加。它属于后 进先出的编码系统。c o v e r 对此进行了改进，提出了枚举编码( e n 啪e m t i v e e n c o d i n g ) 峨这类编码同样存在编码精度的问题。 m s s a i l e n 提出了以适当的近似来解决有限长精度问题的方案，改进了 s c h a l k w i j k c o v e r 的后进先出编码系统，提出了算术编码【9 】。而后，p a s c o 使用与 砌s s a n e n 本质上相同的方法约束s h a j l n o n e 1 i a s 编码，最终实现了先进先出的算 术编码【。 1 9 8 7 年，w i t t e n 等人发表了一个实用的算术编码程序，也就是c a c m 8 7 ( 后 来成为i t u - t 的h 2 6 3 视频压缩标准) 1 l 】，同期，i b m 公司对算术编码做了大 量的研究【1 2 ，1 3 ，1 “，并发表了著名的q 编码器，随后又提出q m 编码器( 用于j b i g 标准) 和m q 编码器( j p e g 2 0 0 0 标准【1 5 ，1 6 ，1 7 1 和j b i g 2 标准) 。m q 编码器在q 编码器的基础上，进一步改进了符号概率估计系统。 1 4 算术编码的优越性 算术编码与h u f b l l a i l 编码和行程编码不同，跳出了分组码的范畴：它从全序 列出发，采用递推形式的连续编码。它不是单个的信源符号映射成一个码字，而 是将整个输入符号序列映射为f 0 ，1 ) 区间内的一个子区间，其长度等于该序列的概 率；再在该小区间内选择个代表性的- 进制小数，作为实际的编码输出，从而 达到高效编码的日的。不论是否二元信源，也不论数据的概率分布怎样，其平均 码长都能逼近信源的熵。 通常，当信源符号概率比较接近时，建议使用算术编码，因为此时h u 髓1 a 1 1 编码的结果趋于定长码，效率不高。必须知道，霍夫曼编码只有当信源中各符号 出现的概率是1 2 的各次幂时，才能达到信源的熵，但这样的情况通常不满足。 其次，霍夫曼编码对于二元信源是无效的，然而算术编码可以很好的解决这 些问题，它可以获得更好的编码效率。 另外，因为信源符号概率的非平稳性，人们提出了自适应信源模型和自适应 编码方法。在自适应h u 瓶1 a n 编码中，信源模型和编译码树联系非常密切。也就 是说，如果信源模型的结构发生改变，编译码的算法结构也必须发生改变1 8 l 。 而算术编码可以将编码过程与概率估计建模分开，从而可以很好地进行动态自适 应的符号概率估计，其编码和解码端的符号概率模型由相同的初始状态开始，由 相同的状态机进行调整，而不需要像h u m n a n 编码那样要求由编码端发送码表至 解码端。 事实上，j p e g 成员测试过，对于许多实际图像，算术编码的压缩效率效果 优于h u f r m 柚编码约5 1 0 。在j p e g 的扩展系统中，己经用算术编码取代了 h 硼胁a n 编码。h p r i r 此等人采用多次查表操作实现了一个简单有效的多元快速 算术编码器，冗余码长只有0 0 6 3 4 比特；而根据t b e l l 等人对主要统计编码方 法( 包括各种h u f i m a l l 编码，l z 家族的主要算法和算术编码) 的比较，算术编码 具有最高的压缩效率2 0 1 。 绪论 1 5 算术编码的应用 由于其高压缩编码性能，算术编码的研究与应用越来越受到重视与关注，并 广泛应用于多种用途的数据压缩中，如图像压缩、视频压缩等。 早在j p e g 标准中，算术编码就已经是其熵编码部分的推荐算法，但是由于 当时软、硬件实现上的限制，一直没有广泛应用起来。直到后来推出的二值图像 压缩标准j b i g 2 以及最新的静止图像压缩标准j p e g 2 0 0 0 才开始将其作为首选推 荐算法。 另外，在h - 2 6 3 标准中，采用了基于语法的算术编码；在m p e g 一4 标准中， 采用基于邻近信息的算术编码来编码其形状信息：而最新的视频压缩标准h 2 6 4 中也采用内容自适应的算术编码( c o n t e x ta d a p t i v e b i n a r ya r j m m e t i cc o d i n g ， c a b a c ) 作为其熵编码算法之一。 1 6j p e g 2 0 0 0 图像标准 j p e g 2 0 0 0 是新的静止图像压缩标准，于2 0 0 0 年1 1 月起正式确定为国际标 准。与j p e g 不同，j p e g 2 0 0 0 基于小波变换，采用当前最新的嵌入式编码技术 和高效的算术编码，提供了卓越的压缩性能和一系列丰富的功能，不仅可应用于 传统的j p e g 市场，而且可以应用于视频医疗影像，无线通信，网络传输等新兴 领域。由于采用了先进的编码技术，与j p e g 相比，j p e g 2 0 0 0 有很多优越性， 主要体现在以下方面： 1 1 良好的低比特率压缩性能 2 1 有损和无损压缩编码之间的兼容 3 1 按照像素精度或者分辨率进行渐进式传输 4 1 码流的随机访问和处理 5 1 很强的抗误码特性 由于j p e g 2 0 0 0 的优良性能以及广阔的应用前景，其硬件电路结构的研究也 成为了一个热点。j p e g 2 0 0 0 硬件实现的各种相应的结构层出不穷，一些半导体 制造商也推出了一些a s i c 芯片，如c o n e x a n t 半导体公司的c s 6 2 1 0 【2 l 】和美国半 导体制造商a d ( a n a l o gd e v i c e ) 公司的a d v _ j p 2 0 0 0 1 2 2 】；它所采用的二进制算术编 绪论 码器m q 编码器的v l s i 实现也吸引了不少研究者陟3 钔。 1 7 本文研究内容及论文组织 综合上面，l 节的介绍，我们知道，算术编码具有卓越的编码压缩性能，且已 经被众多的图像和视频国际标准所采纳，j p e g 2 0 0 0 中的m q 编码器就是它们中 的典型；另v 一方面，必须看到，算术编码计算复杂度高，它包含大量比特级操作 以及复杂的控制，使得其吞吐率( t h r o u 曲p u t ) 成为设计实现的瓶颈。 因此，设计一款高吞吐率的二进制算术编码器具有很大的应用价值和研究意 义。本文将以j p e g 2 0 0 0 中的二进制算术编码器m q 编码器为研究对象，通过 对算术编码基本原理的掌握和分析，在m q 编码算法的基础上，提出高吞吐率 的v l s i 实现架构。并编写v e r i l o g 语言对其结构进行描述，最后，作出仿真验 证和性能比较分析。 接下来的内容组织如下： 第二章中介绍算术编码的基本原理，然后重点介绍二进制算术编码的若干技 术细节。 第三章，给出j p e g 2 0 0 0 所采用的m q 编码器的概况描述，阐述其算法实现 流程。 第四章，分析j p e g 2 0 0 0 中的二进制算术编码的硬件实现，通过对其基本组 件的研究，给出可实现的硬件架构，并探讨并发符号编码的可能性，在此基础上 实现2 符号同时编码的m q 编码器v l s i 架构。 第五章，介绍仿真验证的流程，对所给出的v l s i 实现进行仿真验证，得出 测试数据，并对其进行性能比较分析。 第六章，给出本文研究工作的总结，为下一步研究提出相关的研究内容和方 向。 算术编码原理 第2 章算术编码原理 如第一章所述，算术编码是种高压缩性能的熵编码方法。它从整个符号序 列出发，采用递推形式进行连续编码。这种思想来源于目i a s 编码。实际的算术 编码包括有限长精度、无乘法形式的近似、自适应概率估计等值得考虑的问题。 2 1 日i a s 编码 在s h a n n o n 发表信息论后不久，p e l i a s 设计了一种可变长编码算法，它是算 术编码的基础。 2 1 1 输出映射到区间 设 x 。) 为无记忆平稳随机过程，x 。表示随机变量的前n 个输出。该算法可 理解为将信源序列的每一个这样的长度为n 的前缀和实数轴上的一个区间相联 系：【q ，吒+ 吒) 【o ，1 ) 。算法递归实现如下5 1 e l i a s 编码算法 i n i t i a l i z e 吒= 0 ，嘞= 1 f o re a c h n = o 1 ， 1 = 厶( 矗) ，幸迭代更新。+ 勺+ i = c 。+ 以乓( 矗) 丰迭代更新c4 其中巧表示累计分布，墨( _ ) 皇厶( t ) 。 编码举例如下。设厶( 0 ) = 0 2 5 ，矗( 1 ) = o 7 5 ，编码信源序列为“0 1 1 0 ”， 图2 1 所示为区间h ，矗+ ) 的演变。 算术编码原理 4 i - a 3 l i 、j j 冬j 图2 1 无记忆二进制信源的e l i a s 编码示意图 2 1 2 区问映射到码字 因为每一个不同的矢量x 。相对应的区间【矗，“+ 吒) 的集合是不连续的，使 得，特定输出。可以用区间h ，+ ) 内的任意数字来唯一识别。由于区间长 度为，它一定包含至少一个形式为o ! ! 缝：垒的卅位的二进制小数，其中k k 是满足2k c 卅 几墨 m 一矿 7 一矿 ，ljij夏lfli丛1 i l 弋f i d 、k 盯藤豳濯豳匿曩圈n 吖lliil弋iijli小吖川邓j n嚼墨 ，；。，、。、代，il酬l 算术编码原理 因为；。+ 2 + 2 2 叱c m + ，假定解码器接收到与；。的前三。位位置 一致的任意一串二进制位，将这一串二进制位当作值为r 的二进制小数来处理， 则可以得到 c m r c m + 2 叫”+ 所以，r 【c 。，c 。+ d 。) 睢确定砩。这也说明，输出砩。可以用另外的任意 二避制位串的前l 。位准确表示。 当一个任意长度的信源记号序列到达时，e l i a s 编码就构造一个单一的码字。 它有一个非常重要的性质，即它是“可以增量解码的”，也就是说，给定任意的 r h ，气+ ) ，可以对每一个h = l ，2 ，掰，r k ，+ ) 可以一个接一个地对 前缀x 。进行解码，其优点是不需要延迟和用来保存巨大码字集合的存储器。而 且，增量构造容易适应非平稳信源的条件统计性质，它有助于自适应编码，其中 有关的条件概率由前面已经编码的信源过程的输出进行动态估计。 2 2 二进制算术编码 由于e l i a s 编码运算涉及到无限长的精度问题，使得其远离实际的应用。而 二进制算术编码则在它的基础上解决了这样的缺陷。 2 2 1 有限精度实现 在e 1 i a s 编码中，对区问k ，矗+ ) e o ，1 ) 的下界和壬度进行区间递归再分 割算法，其赋值更新遵循： “= 厶( ) ( 2 - 1 ) 。= 吒+ b ( )( 2 2 ) 雨在算术编码中，为了实现有限长度的精度要求，放弃了上面理想的更新关 系，而是假定；o o 执行，一1 次e m i t _ b i t ( 0 ) r = o e l s e ，= 一l m i l e ， 2 ”+ 一1 6 卜6 + 1 丁卜2 r c 卜2 c i fc 2 “+ i fr 寺，则值为负数。可以通过图2 - 2 的示意来理解。用爿：、磊矿 赢，。分别代表4 ，风死，。表示的二进制小数。当赢。= a 赢，。4e 唼，1 ) 时， 近似显然不合适。这是任何口 妄的选择都会产生的情况。可以采用的解决办法 是m p 三尸s 选择开关，即每当贰。 妻时，置换记号。和1 的角色。这里，此p 联m o s t p r o b a b l es y m b 0 1 ) 表示最可能的符号，三只双l e a s tp r o b a b l es y m b 0 1 ) 表示最不可能的 符号，并用q e 表示其出现的概率的估计。 2 一“4 瓴， i p 如妒铂。 图2 - 2 无乘法近似进行区间分割 文【3 】中就无乘法器的近似对编码效率的影响做了探讨，它指出，编码当记号 概率倾斜度很大时，是达到最大压缩率的地方，而编码效率的最大损失出现在 三p s 概率接近1 2 附近。并提出了口的优化值接近2 3 。在j p e g 2 0 0 0 标准的算术 编码中，僻取值为o 7 0 8 。 算术编码原理 2 2 3 条件交换 编码效率的最人损失出现在p s 概率接近i 2 时，条件交换机制可以减少这 种损失。参考图2 2 ，可以得到，当 圭4e 【丢，圭) 时，分配给m 雕的区间小 于分配给上p s 的区间。每当此时，条件交换就会交换a z 附和三p s 的作用，保证 舰s 总是分配到较大的区间。在条件交换的时候总是伴随着归一化。 2 2 4 自适应概率估计 最初的几个符号一般是用不合适的概率估计编码的，随着在任意一个给定环 境中有更多的符号被编码，概率估计就会稳定下来，编码变的更有效率。在实际 应用中，统计经常是非平稳的，因此往往将面向较近观测到的输出作概率估计。 自适应概率估计的方法是：保存在每一个环境中观测到的0 和l 符号数目的计数 值q 和c 1 ，每当c o 和c l 超过某个下限值c m 。使，计数值重归一化来实现概率估 讨。算法如下： i n i t i a l i z ec 0 = c l = 0 f o r e a c h ”= o ，l ， i f = l c l 卜q + 1 e l s e i fm i n c 0c i ) c 。o rm a ) 【 q g 吒。 c o 卜l 譬j ，q 卜l 导j 如卜者 严概率估值t 这样的比值技术概率估计器是一个有限状态机。具体到算术编码中，就是对 算术编码原理 上册和必船符号的数目t 和c _ 计数，0 q c 1 m 。o c 1 m 。，总共有 2 ( c m 。+ i ) ( 。+ 1 ) 个状态。因此，概率估计可以通过查表来实现。 通过重归一化，算术编码随机开启概率估计有限状态机中的状态转移门，使 得与概率估计相联系的复杂度大大降低。状态在任何符号的编码操作之后立即更 新，编码操作包含一次或多次调用“r e n o r m a l i z eo n c e ”子程序。新状态识别用 于后续所有符号的概率估计，直到后续重归一化引起再一次的状态转移为止。 详细的j p e g 2 0 0 0 二进制算术编码器状态转移表将在第三章中介绍。 2 2 5 其他发展形式 无乘法算术编码器变形可追溯到“偏移编码器”。无乘法操作以及重归一化 驱动的概率估计是类广泛的算术编码算法的最显著特征。这些算法包括q 编 码器、q m 编码器、m q 编码器等。 q 编码器和m q 编码器变形包含一个“位填充( b i t - s t u 艏n g ) ”机制。它限制进 位在编码器中的传递范围，以很小的编码效率损失为代价简化实现。这种机制在 后续章节得到详细的阐述。 2 3 本章小结 本章首先简要介绍了e l i a s 编码的编码算法，并举例图示其编码过程，阐述了 其优点以及不实用性。在此基础上，从算术编码的基本原理和算法出发，逐步探 讨了有关的编码要点，包括有限长精度实现、无乘法器的二进制编码形式、条件 交换机制和自适应的概率估计。 m o 编码_ 器 第3 章m q 编码器 如前述章节所提到，新一代静j 卜图像标准j p e g 2 0 0 0 采用基于e 下文的自适 应二进制算术编码进行熵编码。二进制算术编码器在j p e g 2 0 0 0 编码系统中的位 置如图3 一l 所示。该模块以位平面编码模块输出的数据位d 及其对应的概率索引 内容( 搿作为输入，对d 数据位序列进行熵编码，输出压缩数据( d 。 b i n a r ya r i t h m e t i cc o d i n gi n j p e g 2 0 0 0 图3 1 二进制算术编码器在j p e g 2 0 0 0 编码系统中的位置 j p e g 2 0 0 0 标准使用m q 编码器作为其基于内容的自适应算术编码器的实 现。m q 编码器对标准的二进制算法作了近似和改进，虽然牺牲了较小的压缩效 率，却大大提高了算法的运行效率，更利于有限长精度的软、硬件的具体实现。 本章将按如下顺序进行阐述：3 1 节对m q 编码器进行概述，3 2 节介绍m q 编码细节和要点，3 3 节介绍m o 编码流程。 3 1m q 编码器概述 j p e g 2 0 0 0 将量化后的小波系数经过位平面编码过程，为量化子带样本的每 一个编码块创建其嵌入式表示，并最终依赖于算术编码机制，将二进制数据判决 位d 映射到压缩数据位c d 。j p e g 2 0 0 0 中的算术编码的具体实现就是我们所要 讨论的m o 编码器。 在第二章，已经集中讨论过了算术编码的原理。本节将详细描述作为特定应 用的m q 编码方法。 m q 编码器可以理解为种“机器”，如图3 2 所示。它将二进制数据判决 位d 和相关的上下文内容c z 所组成的序列映射成单个的压缩码字，即压缩数据 m 0 编码器 位c d 。压缩数据位( 1 d 可能只是被压缩的较长码流中的一部分，也被成为个 “m q 码字段”。当数据判决位d 和其上下文内容c x 组成的数据对 c 蜀从位 平面编码器到达时，压缩数据位c d 增量产生，反映在图3 - 2 中。其算法可以用 下面的形式进行描述： 基i ；篡王r _ _ _ 丁王r i 嚣i 1 震羲j t 焉一r _ _ _ 丁下f 嚣i 1 l 翼，| 季 ；霎= ：二：蘧l | _ 譬| _ - “：+ 图3 2 m q 编码器 1 1 一组“内部”状态变量爿，c ，c r ，b 和工。其中爿和c 表示区问长度和 下限寄存器。工代表到当前为止所产生的编码字节数。b 为一临时的字节缓 冲器，c ，表示一个减计数器，当c 丁= o 处，部分产生的编码位应被移出c 寄 存器，并移入临时字节缓冲器口中。 2 ) 上下文环境状态“文件”，在j p e g 2 0 0 0 中定义了1 9 个上下文环境内容。对 每个可能的上下文内容c x 具有一对输入( 向拟，m 船) 。单个比特的 z 雎表 示编码环境中最可能符号，而伽妣是一个范围从0 到4 6 的6 比特量，它间 接标识编码环境的脱阳概率估计。 3 ) 一组概率映射规则，用于解释并操作与当前编码环境相关联的环境状态 ( 加加，m 陌) ，这些概率映射规则可以理解为4 个函数，函数q ( 如觑) 体现 了状态值如d 缸和上下文c r 的尸s 最不可能符号概率估计之间的关系。函 数m m 陌( 如d 打) 和e p s ( 如d h ) 标识如d h 的新值。根据当前编码是m 阽或 者三p s 而定。只有对上j p s 编码，才调用函数。帅f f c 矗( a z 盼) ，它表示 椰和尸s 符号是否交换。 m o 编码器是“面向字节”的，其压缩数据位c d 必须由整数字节组成。并 。器蕊畿、意一 码_ 势紫篷 孽囊一 醉繁誉 蒸鍪一 一 一 秽 一篱。挚。，蕊 曩j 旁一 蒺蹙鬻 m o 编码器 且只有当被压缩数据的个完整字节产生后才执行某种操作。在m q 编码器中 采用“位填充”方式来避免需要全进位分辨率f 2 。任何时候，当o x f f 字节被输 出到字节缓冲器时，就会出现位填充。它将一多余的冗余位插入到变化的码字中， 可保证来自对c 寄存器的算术操作所产生的进位不会传播到已经被发送到字节 缓冲中的字节。这样，整个编码效率的开销增加大概o 0 5 。同时m q 编码器位 填充的精确实现，使跟随在o x f f 后的字节处于范围o x o o 到o x 8 f 之问。 m q 编码器从无乘法器的q 编码算法改进而来，其明显的增强之处在于“有 条件交换机制”和概率状态机的“启动”部分。它与o m 编码器具有很大的相 似性，主要区别在于q m 编码器采用全进位分辫率结合字节填充进行错误恢复， 而m q 编码器则是采用位填充策略。 3 2 编码细节和要点 3 2 1 无乘法运算 用变量爿表示当前符号区问的大小，c 表示码流指针，缈表示三彤的符号 概率估计。2 ，2 2 节中已对无乘法的算术编码作了论述。本节中，具体到j p e g 2 0 0 0 中的m q 编码而言，通过将彳保持在o 7 5 s 爿1 5 的区划来近似爿q c 为( 垮， 并且用1 6 位整数o x 8 0 0 0 来表示十进制的o 7 5 。每当爿小于o x 8 0 0 0 时，通过左 移若干位使其值保持在 o 7 5 ，1 5 】的范围内，同时c 也左移相同的位数与爿对齐。 m q 编码器的编码过程简化为： p o t m p s 彳= 爿一4 x 9 p 爿一q p c = c + 爿 c + 9 p o r l p s 4 = 4 缈* 缈 c = c m o 编码器 3 2 2 基于状态迁移的概率估计 表3 1 为m o 编码器所使用的有限状态概率估计表，其中列出了对应于索引 值，彻p 的 、栅s 、，s 和s w f 幽值， 值用十六进制数和十迸制数分别 表示。其对应的转换公式如式( 3 1 ) 表示： q 。，：粤 ( 3 _ 1 ) 二x o x 8 0 0 0 3 新状态的索引值 砌r p s 和e 雕都可以从表中直接查出，概率估计过程中 z 嬲上p s 的状态交换只能在算术编码的概率区间重新归一化时发生。即在p s 或肘嬲编码过程中，当一的值小于o x 8 0 0 0 时，才会发生状态的改变。 表3 1 概率估计表 值 m d 缸n m p sn l p ss w i k h f h e x l ( b i n a r y ) ( d e c i m a ” o o x 5 6 0 1 o l0 l o 】1 0 0 0 0 0 0 0 0 10 5 0 39 3 7ll l l0 x 3 4 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 l0 - 3 0 47 】5260 2 o x l 8 0 l 0 0 0 1 l 0 0 0 0 0 0 0 0 0 0 1o 】4 06 5 0 39o 3o x 0 a c l 0 0 0 0 1 0 1 们1 0 0 0 0 0 l0 0 6 30 1 2 4 1 2 o 40 x 0 5 2 l 0 0 0 0 0 l o l o o i o o 0 0 1o 0 3 0 0 5 352 90 5o x 0 2 2 l 0 0 0 0 ( 0 1 0 0 0 】o o 0 0 10 0 1 24 7 4 3 8 3 3 0 60 x 5 6 0 1 0 1 0 l o n 0 0 0 0 0 0 0 0 l0 5 0 39 3 7761 70 x 5 4 0 l o l o l 0 1 0 0 0 0 0 l0 4 9 2 2 1 881 40 80 x 4 8 0 1 0 l0 ( j 1 0 0 0 0 0 0 0 0 0 0 1 04 2 1 9 0 49 1 4 0 9( 1 x 3 8 0 l o o l l1 0 0 0 0 0 0 0 0 lo - 3 2 8 1 5 31 01 40 1 0o x 3 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 呻0 10 2 8 1 2 7 7 1 1 1 7 o l l o x 2 4 0 1 0 0 i o o l 0 0 0 0 0 0 0 0 0 l0 2 1 0 9 6 4 1 2 1 8 o 1 2o x l c 0 1 0 0 0 11 1 0 0 0 0 0 0 0 0 0 10 1 6 4 0 8 8l32 00 1 30 x 1 6 0 l 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 l0 1 2 8 9 3l2 92 l0 1 40 x 5 6 0 l 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 io5 0 3 9 3 7l51 4l 1 50 x 5 4 0 l 0 1 0 l 们0 0 0 0 0 0 0 0 0 10 4 9 2 2 1 81 61 4o 】6o x 5 1 0 1 o l 们0 0 0 1 0 0 0 0 0 0 0 10 4 7 4 6 4 0 1 7 1 50 1 7o x 4 8 0 l 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 l 04 2 】9 0 41 81 60 1 80 ) ( 3 8 0 l 0 0 1 1 1 0 0 0 0 0 呻o 0 0 1 0 3 2 8j 5 3 1 91 70 m o 编码器 1 9o x 3 4 0 l 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 l0 3 0 4 7 1 52 01 80 2 0o x 3 0 0 l 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 l 0 2 8 1 2 7 72 l1 90 2 1 o x 2 8 0 10 0 1 0 1 0 0 0 0 0 0 0 0 0 0 10 2 3 4 4 0 l2 21 9o 2 20 x 2 4 0 l o 叫0 0 1 0 0 0 0 0 0 0 0 0 lo 2 1 0 9 6 42 32 00 2 30 x 2 2 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0