计算机研究与发展
JOURNAL OF COMPUTER RESEARCH
AND DEVELOPMENT
1999年 第36卷 第12期 Vol.36 No.12 1999



通用的高性能算术编码器
闫宇松　　　石青云
摘　要　文中基于成熟的QM算术编码器，提出了对称二叉树的编码方式STQM和最优二叉树的编码方式OTQM．STQM与OTQM均是大符号集熵编码器.它们不仅保持了QM编码器的超过96%的编码效率，也保持了它高速运算的特性.其中OTQM可以动态的调整码树结构，使得编码速度达到理论最优值.STQM由于可并行性和逻辑线路设计简单等特点，使之适合于做动态序列图像的基于专用硬件设计的熵编码模块.
关键词　QM编码器，STQM，OTQM，数据压缩，自适应模型
中图法分类号　TP391
UNIVERSAL HIGH PERFORMANCE ARITHMETIC ENCODER
YAN Yu-Song and SHI Qing-Yun
(National Laboratory of Machine Perception,
Peking University, Beijing 100871)
Abstract　In this paper, symmetry binary tree coder (STQM) and optimal binary tree coder (OTQM) are proposed based on the QM-coder. STQM and OTQM are multiplication-free arithmetic coders with high performance for multi-symbol alphabet, which not only keep the encoding efficiency of QM-coder, but also keep its high speed. OTQM can adjust its binary tree structure dynamically. This advantage enables the encoder to reach its maximum speed. STQM can be implemented by special hardware as a parallel coder, so that it is very useful for video coding. 
Key words　QM-coder，STQM，OTQM，data compression，adaptive model
1　引　　言
　　QM算术编码是一种成熟的压缩算法.它于90年代初被用于著名的静止图像压缩标准JPEG和JBIG中［1］.它被选用的原因是它具有超过96%的编码效率，因而能达到比霍夫曼编码更好的压缩水平.同时由于它将编码器所必须的乘法操作用查表和间隔寄存器的近似来替代，所以它又是一种无乘法运算的编码方法.对于编码符号的概率更新，QM编码器是利用状态机位置的转换来实现的，这种方法避免了CACM87［2］所必须的除法运算，同时保持了算术编码的自适应特性.所有这些都使QM编码器成为一种比较好的编码选择.但是由于QM编码器对状态机的更新机制，使它只能反映两个符号的概率变化，要想将其推广至多符号集合，必须引入二叉树结构.在JPEG标准中所采用的是类似于非对称二叉树结构，这种结构是由DCT变换后系数的特殊分布所决定的，因而不具有通用性.本文所提出的对称二叉树编码方法STQM和最优二叉树的编码方式OTQM，使得QM编码器具有通用、高速、高效率、自适应、结构简单、可并行、支持大字符集等诸多优点.
　　本文将在第2节对QM编码器做简单介绍．在第3节给出STQM编码器的构造方法，第4节对这种方法进行理论证明，第5节给出OTQM编码器的构造理论，第6节给出实验结果.
2　QM编码器简介
　　QM编码器起源于IBM公司的Q编码器，它是由Langdon,Rissanen等人的早期工作发展而来的．和其它的算术编码方法一样，QM编码器从原理上可清晰地分为二进制编码和统计模型两个部分．
　　QM编码器本质上是一种二进制编码方法，这意味着就单一上下文而言，它只能对0和1两个符号进行编码．在编码过程中，QM编码器利用重新归一化使间隔寄存器A保持在0.75～1.5之间，同时对编码寄存器C作相应运算产生输出码流．由于A满足：0.75＜A≤1.5，与1比较接近，因而可将需要用乘法精确计算的概率间隔细分A×Qe用Qe来直接近似，免去了乘法运算，提高了速度.
　　在统计模型部分，QM编码器最有特色的是状态机的概率估值技术．每一个输入符号流都有其对应的符号概率，QM编码器能够利用状态机对这种概率进行动态跟踪与估计．实际的算法中，状态机是用一个状态估值表来表示的，它包括状态的索引，概率的估值Qe以及状态的转移方向．初始编码时，符号流被置为一个初始状态．它所对应的概率估值Qe反映了符号的初始分布．随着编码过程的不断继续，符号流的概率分布也在不断的变化．每当编码器重新归一化时，符号流的状态都会按照状态估值表的状态转移方向改变到下一个状态．新状态所对应的Qe值正好是对当前符号概率的更新估计．状态估值表的特殊设计保证了这种估值的准确性，Pennebaker和Mitchell在文献［3］中对此做了详细的阐述.由于符号流的状态反映了符号的概率，因此每一个符号流只要维护一个状态索引值，就能确定当前是什么状态，进而得到概率的估计，完成算术编码．
　　QM编码器还是一种自适应算术编码．由于符号流状态的变化是随着符号的输入而自动调整的，因此QM编码器能够把握符号流的局部分布特性，无需对符号的整体概率做事先统计，具有很强的适应能力．同时状态转移方法还使它避免了一般自适应算术编码对概率估计所需要的除法运算，进一步提高了运算速度.
　　在算术编码中，我们通常为每一个符号流分配一个特定的上下文序号S．不同的上下文S对应着不同的符号流，也对应着不同的符号概率．如果编码器能够同时对不同的符号流采用各自的符号概率进行编码，那么这种编码就称为混合上下文编码，否则就称为单一上下文编码．QM编码器的状态机一共有113个状态，这一设计使它无论对单一上下文还是混合上下文都能保证概率估值的准确性.
　　使用QM编码器需要调用以下几个外部函数：
　　编码器：
　　　Initenc()　　　　　初始化编码器
　　　Code_0(S)　　　　　对上下文序号S编码0判决
　　　Code_1(S)　　　　　对上下文序号S编码1判决
　　　Flush()　　　　　　终止编码
　　解码器：
　　　Initdec()　　　　　初始化解码器
　　　Decode(S)　　　　　对上下文序号S解码二进制判决
　　编码时，首先调用Initenc()，它的作用是对编码器进行初始化．紧接着对上下文序号为S的二值符号流进行编码，如果输入符号为0，就调用Code_0(S)，如果输入符号为1，就调用Code_1(S).编码结束时，调用Flush()对编码寄存器置空.
　　解码时，使用Initdec()对解码器进行初始化.接着不断调用Decode(S)对上下文序号S进行解码，得到由0和1组成的二进制符号流.
　　在编解码过程中，上下文S的作用是标志不同的符号流．QM编码器允许混合上下文编码，也就是说它可以对几路符号流同时编码，而每一路符号流都用各自的状态索引值来估计概率．这一特点使得我们可以进行树型QM编码器的构造．事实上，下文我们所构造的编码树的每一个叉节点就对应着一个上下文，整个树型编码器就相当于一个混合上下文的QM编码器．
3　STQM编码器的构造
　　由于QM编码器原理上只对二值符号集进行编码，要想使其对大符号集进行编码，并且满足熵编码的性质，必须采用二叉树的结构.下面我们将讨论二叉树结构与QM编码器是如何结合的.
　　设输入符号串k的符号集为S，其中S={x0,x1,…,xN-1}，而xi,i=0,…,N-1表示k中可能出现的N种符号.我们定义N为符号集S的长度，记为|S|.对于二值符号集显然有|{x0,x1}|=2.如果N比较大，我们就称S为大符号集.
　　假设符号集S可以分成S0与S1两个部分，并且满足：S=S0∪S1且那么对于符号串k中的任何一个符号x，应有

(1)
其中p(x=xi|x∈S)为符号串k中符号xi的概率．反映在编码方法上就是：
　　(1)我们首先对x∈S0还是x∈S1进行编码;
　　(2)当x∈S0或x∈S1已知时，再针对符号子集S0或S1进行x=xi的编码．
　　对于(1)，单个符号x的归属显然是一种二值判定，可以用0或1来表示．将整个符号流k的每一个符号的归属都用0或1来表示，就得到一个二值判定符号流．我们可以使用QM编码器对该符号流进行二值编码．编码时，我们用一个上下文序号来表示这个二值判定符号流，并用一个状态值来反映符号流概率．显然，二值符号流的概率分布正是式(1)中的p(x∈S0|x∈S)与p(x∈S1|x∈S)，它可以在编码过程中用符号流状态所对应的概率估值来近似．
　　对于(2)，其实它等价于符号子集上的算术编码，编码所使用的概率是式(1)中的p(x=xi|x∈S0)或p(x=xi|x∈S1)．显然，这是一种多值编码，但我们可以继续将符号子集S0或S1分解成更小的子集，对每一次的分解我们都同(1)一样进行二值编码．由于符号子集每分解一次，长度都要减少，因此这一过程可以重复进行直到符号子集的长度等于1为止．
　　相应的解码方法可以实现为：
　　(1)先对x∈S0还是x∈S1进行解码；
　　(2)当x∈S0或x∈S1已知时，再针对解得的符号子集S0或S1进行x的解码．这一过程重复进行直到符号子集的长度等于1为止，这时子集所包含的唯一符号xi即为解码所求．
　　下面我们以长度为8的符号集为例，简述QM编码器的二叉树方法：
　　如图1所示，这是一个8个符号的二叉树结构．每一个叶节点代表一个从0到7的符号，而每一个叉节点代表一个符号集分割，或者称为二值判定．对叉节点我们使用QM编码器进行二值编码，即将二值判定中向左的分支用0来编码，向右的分支用1来编码．这样，对一个符号的算术编码就可以用二叉树上连续的几个叉节点的QM二值编码来表示．比如我们要对符号3进行编码，首先在根节点0…7处，符号集S0…7分解成两个符号子集S0…3和S4…7，由于3∈S0…3，而S0…3属于二值判定中向左的分支，所以在该节点处使用0来编码．同理，在叉节点0…3处，我们用1来编码右分支S2…3.最后，在叉节点2…3处，用1来编码右分支，这时达到叶节点，符号集S3只包含一个符号3，编码结束．解码时，我们首先在根节点处用QM解码器解出0，符号集由S0…7变为S0…3，接着，在叉节点0…3处，我们解出1，符号集变为S2…3，最后在叉节点2…3处解出1，使我们最终得到符号集S3，符号3是S3中的唯一符号，因此3即是解码所得.

图1　符号集长度为8的二叉树结构
　　容易看出，图1中每一个叉节点所对应的两个子节点具有相同数量的符号数.我们称这种节点树为对称型二叉树.显然，并不是所有的编码树都必须使用对称型二叉树，使用什么形式的二叉树应该具体问题具体分析.比如在JPEG标准中，它所构造的编解码树就是非对称的.这是由于经过DCT变换和量化以后，变换系数的振幅分布基本集中在0点附近，并且随着振幅的增大，概率迅速变小.由于小振幅系数相对较多，因此在编码树设计时，JPEG标准让数值较小的叶节点位于靠近根节点的地方，这样编码一个小振幅符号所经过的叉节点次数就非常低，从而加快了编码速度.正是由于这个原因，这种特殊的编码树被设计成非对称型的.但是对于一般问题，我们在编码之前，并不知道数据的分布情况.也就无法确定哪一个叶节点应在靠近根节点的位置上.针对这种情况，我们将通用编码器的二叉树设计成具有相对对称的结构，它的每一个节点上的符号集分解满足：

(2)
其中代表对数据取整.这种对称结构的编码器，即STQM，适用于任何形式的数据压缩，包括文档、图像、视频等.
　　下面是STQM的算法流程:
　　编码器：
　　(1)InitEnc()　　　　初始化编码器．
　　(2)FormTree(N)　　　按照符号集分解式(2)为输入符号流形成STQM编码树．N为符号集长度．不同的符号流应使用不同的编码树，并用编码树上下文TS对其标志．
　　(3)Code(TS,Symbol)对输入符号Symbol顺着编码树从根节点一直编到叶节点．在每一个分叉节点上使用QM编码器的二值编码函数Code_0(S)与Code_1(S)，其中S代表分叉节点的上下文．TS为Symbol所属符号流的编码树上下文．
　　(4)Flush()终止编码．
　　解码器：
　　(1)InitDec()初始化解码器．
　　(2)FormTree(N)形成STQM编码树．并用编码树上下文TS对其标志．
　　(3)Decode(TS)针对上下文TS所对应的编码树从根节点一直解码到叶节点．
　　显而易见STQM可以对混合上下文进行熵编码．不同的符号流通过编码树上下文TS加以区分．每一个符号流的字符集长度可以是任意大小．统计模式用对应的编码树来表示．至于STQM是否满足大符号集码流熵编码的性质，我们将在下一节中给予证明.
4　STQM编码器的理论证明
　　上一节中，我们利用符号集分割的方法，给出了树型QM编码器的构造.但是这种构造是否满足熵编码的原则？下面我们将给予证明.
　　设符号串k的符号集为S，对任一个符号xi∈S，它在k中的出现概率为p(x=xi|x∈S)．那么按照熵编码的原理，对于符号串k进行的变长编码，其最小平均码长是它的熵.并且这种最佳编码只有在xi所对应的码长为-log2p(x=xi|x∈S)才能达到．
　　然而树型QM编码器，对于每一个符号xi的编码是通过对几层二叉节点依次进行QM编码所获得的.因此，我们只有证明树型QM编码器在这几层节点上的编码码长之和仍旧是-log2p(x=xi|x∈S)，才能说明树型的QM编码器是真正的熵编码器.下面我们将对此给予证明.
　　由上节的式(1)，我们应当很容易得到：


(3)
　　式(3)左面的-log2p(x=xi|x∈S)就是熵编码在符号是xi、符号集为S时所应分配的码长．而式(3)的右面p(x∈S0|x∈S)与p(x∈S1|x∈S)所表示的正是符号集S分解成的两个子集S0与S1的概率，显然他们满足：p(x∈S1|x∈S)+p(x∈S0|x∈S)=1.因此，如果我们假设QM编码器是一个理想的算术编码器(实际上，任何算术编码器总会有一些冗余)，那么在这个节点上QM二值编码器为x∈S0与x∈S1两个事件所分配的码长分别为-log2p(x∈S0|x∈S)和-log2p(x∈S1|x∈S).而剩下的-log2p(x=xi|x∈S0)与-log2p(x=xi|x∈S1)可以按照同样的方法继续分解下去，最终写成所有后续节点的QM编码的码长和，直到叶节点为止.因而证明了树型的QM编码器是真正的大符号集熵编码器.
　　还是以图1为例，显然有


　　这表明对于符号3进行熵编码所需要的码长，正好等于树型QM编码器在S0…7，S0…3和S2…3三个节点所使用的码长之和，符合熵编码的要求.
5　OTQM编码器的构造理论
　　本节我们将研究最优树型编码器(OTQM)的构造原理和方法.从前面的讨论可知，JPEG的非对称二叉树结构是根据DCT变换而设计的一种速度最优的编码策略，但是它只适合于DCT系数的特殊分布特点，并不具有普适性.STQM对通常的编码数据都可以进行有效的编码，它的编码速度也是比较快的，但它并不能针对数据本身的分布情况达到最快.为了使不同分布的数据都能达到速度极限，我们必须使二叉树的结构可以在编码过程中动态地改变.这种可动态调整的树型结构不会降低压缩效率，能够达到最佳编码速度，对不同数据类型具有普适性.
　　首先从理论上研究OTQM的二叉树构造原理.为了分析编码时间，我们假设在每一个节点上，任何一次二值编码所用的时间都是固定的，并将其归一化为1.那么，任何一个符号的编码时间就可以由它在编码过程中所经历的树节点个数来确定.
　　对于符号集为{x0,x1,…,xN-1}的符号流，相应的概率分布为{p0,p1,…,pN-1}，各个符号编码时所经历的节点个数为n0,n1,…,nN-1，那么整个符号流的平均编码时间就可以表示为我们研究的目的是如何设计最优二叉树结构使T值最小.
　　容易证明以下定理：对于任意两组数据：{p0,p1,…,pN-1}与{q0,q1,…,qN-1}，其中0＜pi＜1，0＜qi＜1，它们分别满足∑pi=1和∑qi=1，那么必有

(4)
等号成立的条件为pi=qi,i=0,…,N-1.
　　对于我们将每个ni表示成-log2-ni(以下的对数都默认为以2为底)，由于二叉树的构造满足，因此通过式(4)可知：

(5)
并且等号成立的条件(也就是T取最小值的条件)为pi=2-ni,i=0,…,N-1.所以为了使编码时间最短，每一个符号所应经过的节点个数为ni=-logpi,i=0,…,N-1.这也就是最优编码树所应遵循的设计原则.下面我们从实际出发来设计OTQM的二叉树.
　　从理论上来说，ni=-logpi,i=0,…,N-1是每一个符号所应经过的最佳节点个数．但是节点的个数应该是一个整数，不可能是一个分数，因此我们只能设计一个近似于最优的编码方案．
　　首先需要对符号进行排序.在建立二叉树的时候，我们已经得到了符号集的概率分布{p0,p1,…,pN-1}，就可以按照每个符号的概率从大到小进行排序，经过排序后的符号集为{xs［0］,xs［1］,…,xs［N-1］}，相应的符号概率为{ps［0］,ps［1］,…,ps［N-1］}，并且满足
　　排序后我们应进行集分割.先搜索整数j，使得最小，其中0≤j＜N.然后将集合{xs［0］,xs［1］,…,xs［N-1］}分解为{xs［0］,xs［1］,…,xs［j］}和{xs［j+1］,xs［j+2］,…,xs［N-1］}两个子集合.不断的将子集合按照同样的方法分解，直到集合长度等于1为止.最后按照集合的分解过程建立二叉树，这个二叉树就是速度最优的OTQM编码树．
　　可以验证，当符号概率都是2的负整数幂的情况下，这种设计方法可以达到理论最优值.当符号概率不是2的负整数幂的时候，此方法是理论值的最佳近似.而且我们能够看到，针对于DCT符号流的统计特点，OTQM编码树的设计结果与JPEG编码树的设计保持一致.
　　在具体的编码过程中，由于树型QM编码器是自适应的编码方法，我们可以边编码边进行统计，并通过统计结果动态地调整最佳OTQM码树的结构，以适应数据的统计特点.对于非平稳数据，它还能够自适应地适应数据的局部统计特点，达到最佳效果.
　　当然OTQM编码中码树的动态调整也要耗费一定的时间，但是我们并不需要每编一个符号就调整一回码树，我们可以在编过相对较长的一段数据以后，再调整一次码树结构，比如，每处理2000个符号后进行一次码树重构，这种方法使得调整本身所用的时间可以忽略不计.另一方面，码树的调整在编码端和解码端应该保持同步，只有这样才能保证数据在解码端的正确解码．
　　对于专用硬件设计而言，动态调整的逻辑设计似乎比较复杂.我们感觉如果能够事先知道符号流的概率分布，并且数据相对平稳，可以将编码器设计成固定的OTQM码树.如果数据分布不平稳，符号概率不可知，是选用OTQM还是STQM应综合考虑.如果使用软件实现，OTQM编码是一种较好选择．
6　STQM编码器的实验结果
　　QM编码器之所以被使用是因为它只需要加减与移位运算，完全避免了费时的乘法与除法，因而比CACM87算术编码器具有更高的速度.同时，它的编码效率能够保持在96%以上，这也是一般的霍夫曼编码所难以达到的.
　　相应的，STQM编码器在每一个二叉点的编码上，只需要增加一个减法运算，同样避免了乘除法，因此在一定程度上保持了QM算术编码的高速特性，又由于它在每一个节点上进行的都是QM编码，因而整体的编码效率也能超过96%.
　　STQM编码器同样保持了QM编码器自适应统计的特点，这使得编码器可以随着数据不同部分的统计特点的变化而变化．这种自适应的特点往往使得QM编码器突破熵的限制，而熵是非自适应熵编码的编码极限．
　　下面的表1是本文的对称树型QM编码器的实验结果，与其相比较的是自适应CACM87编码器．实验数据取自一个长度为19475644字节的普通DOC文件．方法是对该文件的每个数据取余数，从而得到具有相应大小的字母表的实验数据文件．
表1　压缩结果

符号集尺寸符号串长度熵(bits)非自适应编码极限(bytes)STQM(bytes)CACM87(bytes)
3194756441.243019302607420948091975054
9194756442.176346529821730628213152563
16194756442.702360657877534839083820366
24194756442.708569659389034515923953770
32194756443.029870737608337353114338500


　　从表1的实验结果可以看到，STQM编码器的编码效率远远突破了非自适应算术编码的极限．这表明了该试验数据具有非平稳的特征．同时，STQM编码器的编码效率一般都超过了CACM87，表明了它具有比CACM87更好的自适应能力．
　　图2表明在小字符集的情况下，本文的对称树型编码器STQM比CACM87快很多．实际上，在字符集的大小为2的时候，STQM甚至比CACM87快1倍以上．而当字符集大小超过30的时候，STQM与CACM87的速度渐渐地接近．这主要是因为STQM编码所需要经过的节点数随着字符集尺寸的增加而加大，因而导致速度会渐渐地变慢．本程序是用C语言写成，实验结果在Pentium90上运行获得．如果排除文件输入与输出的影响，速度会进一步地提高．

图2　STQM与CACM87在Pentium90微机上的编码速度
　　值得提到的是文献［4］中的算术编码也是一种无乘法编码器，本文的STQM编码器在速度上比该文的方法略好一些．同时，本方法似乎也不太受字符集尺寸的影响，对系统的资源要求不高，适于高阶统计模型的应用．另外本文做比较用的CACM87的平均编码速度可以达到200Ksymbols/s，而文献［4］中的CACM87平均速度只有20Ksymbols/s，如此大的速度差距可能是由于程序优化不够造成的．
　　由于对称树型QM编码器只用到了整型的加减法与移位运算，因而给专用硬件设计带来了极大的方便．同时由于硬件的可并行性，使它可以成倍的提高速度，因此它也是一种基于硬件的视频信号熵编码的较好的选择．但同时也应看到，在专用硬件实现中，QM编码器需要维持一个表格存储器，该存储器也会占据一定的芯片面积，即总的成本孰优孰劣尚无定论．而在现代微处理器或DSP处理器中，乘法的速度似乎也并不比加法慢，这进一步拉近了CACM87和STQM的距离．因此如何选择，还应具体问题具体分析．
本课题得到国家自然科学基金重点项目(项目编号69735020)、航天领域863-2-4基金项目和“九七三”基金项目(项目编号G1998030606)的资助．
作者简介：闫宇松，男，1969年12月生，博士研究生，主要研究领域为模式识别与图像处理、计
　　　　　算机视觉．
　　　　　石青云，女，1936年8月生，教授，中科院院士，主要研究领域为模式识别与图像处
　　　　　理、计算机视觉．
作者单位：北京大学视觉与听觉信息处理国家重点实验室　北京　100871
参考文献
　1　William B Pennebaker, Joan L Mitchell. JPEG Still Image Data Compression Standard．NewYork: Van Nostrand Reinhold, 1993
　2　Cleary J G, Witten I H, Neal R M. Arithmetic coding for data compression. IBM Journal of Research and Development, Commun of the ACM, 1987, 30(6): 520～541
　3　Pennebaker W B,Mitchell J L.Probability estimation for the Q-coder.IBM Journal of Research and Development,1988,32(6):737～752
　4　薛晓辉， 高文. 小字母表的高性能算术编码. 计算机学报. 1997, 20(11): 974～981
　　(Xue Xiaohui,Gao Wen.High performance arithmetic coding for small alphabets.Chinese Journal of Computers,1997,20(11):974～981)
原稿收到日期：1999-03-01；修改稿收到日期：1999-04-28.
