算术编码在图像信号压缩中的应用

—234— 算术编码在图像信号压缩中的应用邓关宝，杨士元，汪 锐(清华大学自动化系，北京 100084)摘 要：阐述了算术编码的有限精度描述及其推导过程，并对几种不同的算术编码模型进行了测试分析，提出了一种采用算术编码对特定格式的图形文件进行压缩的算法，并论证了该算法实现的优势。

关键词：算术编码；上溢；下溢；有限精度；静态模型；自适应模型；数据压缩Arithmetic Coding and Its Application in Image CompressionDENG Guanbao, YANG Shiyuan, WANG Rui(Department of Automation, Tsinghua University, Beijing 100084)【Abstract 】This paper presents the fundamentals and the deduction of the arithmetic coding using fixed precision registers. And the analyses and testing of the common probability models are given. In the end it presents an effective way of compressing for a given formatted photograph. 【Key words 】Arithmetic coding; Overflow; Underflow; Fixed precision; Static model; Adaptive model; Data compression计 算 机 工 程Computer Engineering 第32卷 第6期Vol.32 № 6 2006年3月March 2006·多媒体技术及应用·文章编号：1000—3428(2006)06—0234—03文献标识码：A中图分类号：TP37算术编码的基本算法是将信源信号映射为编码串，解码是对编码串进行逆向映射而得到原来的信源信号。

获得信源字符对象的概率模型的方式通常有两种：静态概率模型和自适应概率模型。

静态概率模型给每一个字符指定足够位数的概率分布表来加以识别；自适应的模型不需要为解码附加概率分布表，它在读取数据时动态更新概率模型分布数据，但是其执行时间长，数据结构复杂一些。

算术编码在图像数据压缩的一些标准(如JPEG 、JBIG)中扮演着重要角色。

1 算术编码基本算法设X ＝123....n x x x x ,其中对于任意i x 属于一个有限字符表集合A 。

为简便起见，将A 采用整数来表示(每个字符和它的查询标码唯一相对应)；(1,2,3,...,)1A N N =>，；每个字符的发生概率用()P i 0>来表示，其中1i N <<；用()Q i 表示到第i 个字符的积累概率，其定义为(1)()()Q i Q i P i +=+，1i N <<，且(0)0Q =。

算术编码算法1(0)0,(0)1F M ==；(1)()()*();(1)()*();i i F i F i M i Q X M i M i P X +=+⎧⎫⎨⎬+=⎩⎭[),F F M +为其编码空间。

译码算法(0)0,(0)1F M ==；[),F F M +为其编码空间。

对编码后的数据作n 次循环：由A 到D(假设：S 为经过编码后的比特字符串)A ：找到最大的整数j 满足：()()*()F i M i Q j S +≤；B ：令i X j =；C ：(1)()()*()F i F i M i Q j +=+；D ：(1)()*()M i M i P j +=。

2 整形算术编码算法上述算术编码在实现时有一个致命的缺点：随着信源的不断增大，小数点后的数值会随之增加，这样就要求描述区间的小数精度随之不断地提高。

整型算术编码算法的实现使算术编码的实用性得以大大增强。

文献[1]提出了采用有限精度寄存器实现无穷精度的算法。

定义 ()/i P i p D ；()/i Q i q D ，其中：0Ni i p D ==∑；(/i F i f D ）；()/i M i m D 。

将上述的定义带入算法1，得到递推式：11*/*/i i i xi i i xi f f m q D m m p D ++=+⎧⎫⎨⎬=⎩⎭从上述递推式中可以看出：f 的迭代为单调增，m 的迭代为单调减。

采用有限寄存器表征时，f 将可能发生上溢而m 可能发生下溢。

2.1 量度空间的存在性在整数范围内量度空间存在要求：1111i i i f m f ++++−≥ (0)i >= (1)恒成立。

即区间[)111,i i i f f m ++++中至少存在一个用于编码的标识值。

将式(1)进行化简得到：对任意i 值必须成立 11i m +>= (2) 在11*/*/i i i xi i i xi f f m q D m m p D ++=+⎧⎫⎨⎬=⎩⎭中，max ()xi q D =。

若概率参量p q 和分别采用k 个比特来描述，编码参量m 和f 分别采用b 个比特来描述，当满足2k b k b p ≤−⎛⎞⎜⎟+≤⎝⎠时， 可以使1*/i i i xi f f m q D +=+中1*2p i xi m q −<。

取2max 21b D −=−，作者简介：邓关宝(1980—)，男，硕士生，主研方向：远程图像传输；杨士元，教授、博导；汪 锐，博士生收稿日期：2005-03-19 E-mail ：dgb02@—235—当采用C 语言实现时选用长整形数据描述，通常31p =，而1416k b ==，。

若对任意i m D ≥成立，又由1xi p ≥(xi p 的初始化值为1)，可使11i m +≥ 恒成立，即1*/1i i xi m m p D +=≥，从而得到m 的约束条件：2[21,21)b b−−− (3)2.2 精度扩展要求在量度空间存在情况下，精度扩展要求量度空间[),i i i f f m +中存在一个标识区间的值来满足扩展的要求。

当每次从高位数据区取走编好的一位比特数据时(当每次输出若要不止一位比特数据时，可参考文献[4])，要求区间值高位的数据相同。

在这种情况下，当前量度空间同下一次递归的量度空间区间值有相同的高位，可以将相同的高位数据移出存放，将剩余的低位数据进行左移的方式来提高数据的精度。

当量度空间[),i i i f f m +存在时，显然必可以选取i f 作为标识字符编码的值。

当以此时i f 作为区间标识时，要求1i f +和i f 有相同的高位数据。

m f 、采用b 位寄存器来表征，对于任意x 其高位值记作：H(x)，L(x)为除去高位后的生成值定义算子：1()2()b L x x H x −=−。

可将上述要求描述为H(1i f +)=H(i f )，即(/)()i i xi i H f m q D H f +∗=。

显然该条件可以被放宽为()()i i i H f m H f +=。

当m 属于b-1b[2,2-1)时，H(m)=1必有：H(f)H(f+m)≠。

因而m 可以被进一步约束，由式(3)变为下面的式(4)：2122b b m −−≤< (4) 当需要满足条件：21222022b b b b m f −−−≤<≤<−，且2b m f +<时，有如下3种扩展计量空间的方式，分别对应于3种数学变换如图1所示(图1中的a)、b)、c)对应于区间跨度范围，例如a)情况下表示区间的起点位于0.0～0.25之间，终点位于0.25～0.5之间)。

(L~全长)a)采用变换E1 扩展计量空间 b) 采用变换E3 扩展计量空间 c) E2扩展计量空间图1 3种扩充计量空间的放大变换E1变换为212a a E b b ⎛⎞⎛⎞=⎜⎟⎜⎟⎝⎠⎝⎠，当其高位具有共有数据‘0’时，将比特数据‘0’输出后数据左移来扩展其计量空间如图2所示。

同样对E2定义为21221a a E b b −⎛⎞⎛⎞=⎜⎟⎜⎟−⎝⎠⎝⎠，其高位数据为‘1’，可将比特数据‘1’输出后左移剩余数据来扩展计量空间。

E3定义为21/2321/2a a E b b −⎛⎞⎛⎞=⎜⎟⎜⎟−⎝⎠⎝⎠，E3满足条件：22b f −>；2122b b m −−≤<。

在进行编码时，计量空间是单调缩小的，E3变换无法预知其结果会落在上半区间还是下半区间。

但是一旦得知下一个进行的是E1或E2变换，就可以知道在E3变换中保存的数据内容。

因而E3变换和E1、E2变换一样，所不同的是它没有直接地将数据输出存储，而是需要一个参量(该参量在算法3中为bit_outs ，初始化为0)来计数E3被使用的次数。

图2 3种扩充计量空间变换的示意图例如，E3变换后紧跟E1变换表明：区间将落在21[2,2)b b −−区间内，其等价于E1后紧跟一次E2变换。

即1*32*1E E E E =，更宽泛地有： 1*(3)(2)*1n n E E E E =和2*(3)(1)*2n n E E E E = 成立！基于上述分析可以得到：算术编码的算法2 编码算法：(1)初始化f m ，的值：12;0b m f −==； (2)对编码后的数据作n 次循环：由1)～3) 1)计算：1*/i i i xi f f m q D +=+； 2)计算：1*/i i xi m m p D +=； 3)更新m 和f 的值； 更新m 和f 的值步骤如下： 当22b m −≤ 时，重复1)～4)的操作： 1)如果12b f m −+≤， __(0)bit plus follow ；/*将实行E1变换*/2)如果12b f −≥，__(1);bit plus follow 12b f f −←− ； /*将实行E2变换*/3)其它剩余情况_;bit outs ++ 22b f f −←− ；/*将实行E3变换*/ 4)22f f m m ←←；；其中：__(x)bit plus follow 函数如下： { output(x);当(bit_outs >0)时 }{ output(1-x); bit_outs - -; }对应的解码算法(1)初始化m ，f 和value 的值(中间变量value 值的更新：进行左移一位＋read_one_bit 表示更新一位被压缩数据)：021b f m ==−；；value ：用读入被压缩的刚刚开始的前b 个字符来初始化。

—236—(2)进行1)～4)的循环操作直到字符串结束： 1)更新1:*()/i i i f f f m q j D +=+； 2)更新1:*()/i i m m m p j D +=； 3)调整f m 、和s 的值；4)解码输出返回一个查询标识参量： ((1)*1)/value f D m −+−。