MQ算术编码器原理及实现
郭晴
北京邮电大学信息与通信工程学院，北京(100876)
E-mail:
摘 要：JPEG2000标准中， MQ算术编码是熵编码的主要部分。MQ算术编码器是一种基于上下文的自适应二进制算术编码器。它基于上下文以利于解除信源相关性，利用条件交换和概率估计状态机中的贝叶斯学习过程实现符号概率模型自适应过程，采用位填充技术解决编码中的进位问题，是一种高效率物理可实现的压缩编码算法。本文从算术编码的基本原理入手，详细分析JPEG2000标准提供的MQ编码器编码原理，以及编码流程。利用C语言编程实现JPEG2000标准要求的MQ算术编码器，并分析MQ算术编码器中上下文引入对压缩效率的影响。
关键词：JPEG2000 ；算术编码；MQ算数编码器
中图分类号：TN911.21
1. 引言
随着多媒体技术的不断运用发展，图像压缩要求更高的性能和新的特征。为了满足静止图像在特殊领域编码的需求，JPEG2000作为一个新的标准处于不断的发展中，这种新的标准更加注重图像的可伸缩表述[1]。
算术编码是一种变长信源编码技术,其卓越性能使其在多媒体领域得到了越来越广泛的应用 [2]。JPEG2000标准中，提高图像压缩性能的关键技术之一就是MQ算术编码。MQ算术编码器是一种基于上下文的自适应二进制算术编码器,它继承了IBM的ABIC（自适应双层图像压缩）中Q编码器无乘法的近似和位缓存的策略,增加了条件交换和概率估计状态机中的贝叶斯学习过程，是一种高效率物理可实现的压缩编码算法，非常具有研究价值。
2. 算术编码
2.1编码原理简述
算术编码是一种非分组码。编码时信源符号序列连续的进入编码器，通过编码器的运算得到连续的输出。通常算术编码是讲一条信源符号序列映射成一条码序列，这样的码序列有时也称为码字。算术编码的实质就是，将一条信源信息序列映射到[0,1)区间中的一个子区间，这种映射是一种一一对应关系，以保证唯一译码，然后取这个子区间内的一点所代表的数值作为码字。只要码长合适，就可以保证唯一可译。而当信源序列长度足够大时，每信源符号的平均码长接近信源的熵[2]。
虽然其编码效率很高，但仍然存在缺陷。首先，其运算需要精确的实数加法和乘法，这些运算在有限精度的计算机上实现是非常困难的。正是这个原因使得算术编码从提出到实际应用相差了近二十年之久。直到Rissanen和Pasco分别提出了一个先进后出算法和一个先进先出算法，并由此证明了算术编码可以用有限精度处理技术逼近。Rubin吸收了两个算法的精华，利用有限精度寄存器，讨论了一般算术编码的实现方法。在此基础上，Witten，Neal和Cleary做了进一步地精细化，并给出了一个完整的C语言程序。
算术编码的另一缺陷是编码速度太低，这是因为编码迭代过程中含有整数乘除运算，这些运算对于软件执行和硬件设计是十分不利的。
为此Langdon和Rissanen提出了一个用移位和加法实现二进制算术编码的方法，并成功地应用于黑白二值图象的压缩编码。二进制算术编码是一种步进式编码译码过程。它不需
要等到待编序列完全输入编码器，就可以在序列输入的同时输出编码码字。它同时也解决了算术编码的精度问题。
2.2二进制算术编码
如前所述，二进制算术编码是一种增长型编码译码过程，序列进入编码器的同时可以得到编码输出，而不需要等到所有序列完全进入编码器。
以消息“cacbad”为例说明编码过程。开始时，整个区间是一个半开半闭区间R0=[0,1)，由各个符号概率仍然分解为四个部分：[0.5, 0.62)，(0.62, 0.70)，[0.70, 0.86)，[0.86, 0.9)以代表a，b，c，d区间。计数器Count初始设为0。
第一个符号为c，所属区间R1=[0.5,0.9)完全属于[0.5,1)，为情况2因此编码输出1bit：1。同时根据情况2改变区间大小为R2=[0.0,0.8)。由于Count＝0，因此不用输出任何码字。
第二个符号为a，区间调整为R3=[0.0, 0.24)。由于整个区间属于前半部分，为情况1，因此输出1bit：0，同时区间调整为R4[0.0,0.48)。仍然属于前半部分。继续输出0，调整区间到R5=[0.0,0.96)。
第三个符号为c，区间调整至R6=[0.48,0.864)。不需要输出任何码字也不需要调整区间。 第四个符号是b。区间调整至R7=[0.5952,0.672)，属于情况2，输出1，调整区间R8＝
[0.1904,0.344)。情况1，输出0，调整区间为R9=[0.3808,0.688)。
此时区间属于情况3，因此我们对计数器加1：Count＝1，同时调整区间为R10=[0.2616,0.876)。
第五个符号是a，区间调整为R11=[0.2616,0.44592)，情况1，输出0，同时调整区间R12=[0.5232,0.89184)。此时计数器大于0，因此输出计数器值1bit：1。新的区间为情况1，因此输出1，调整至R13=[0.0464,0.78368)。
最后一个符号是d，区间调整至R14=[0.709952,0.78368)。情况2，输出1，调整为R15=[0.419904,0.56736)。此时我们结束编码，可以用此区间内任意值作为码字输出。不妨取0.5，则二进制表示为0.1000000b，可以添加任意多个0以满足位数要求。
因此作为唯一可译编码，编码过程中输出的码字与最后区间内任一数值结合，串起来即实际16bit编码：1001 0011 1100 0000。可以看到，前9bit为增长编码过程输出，最后7bit为从区间中选择与前9bit共同组成16bit编码。
详细编码过程如图1：
图1 “cacbad”二进制算术编码过程图
3. MQ算术编码器原理
3.1 MQ编码器结构
JPEG2000标准中的MQ编码器结构如图2所示，编码器输入由待编码位D和上下文矢量CX构成，他们是由EBCOT (嵌入式位平面失真率可优化编码)成对产生的。CX是位平面编码中根据邻域相关性归纳而来的概率统计模型，共有l9种。即对于不同的CX，符号概率不相同。
图2 MQ编码器结构图
3.2递归区间划分以及编码近似
递归概率区间分割的ELIAS编码是二进制算术编码的基础[3]。算术编码器首先按符号概率将符号分为大概率符号MPS和小概率符号LPS。区间划分时，LPS区间在MPS区间之前。如图2：
图3 MQ编码器编码区间示意图
当对MPS进行编码时，LPS子区间间隔就被加到编码串上。因而对每一位进行编码时，必须预先知道LPS子间隔的大小和MPS的代表符号。编码过程就是对输入的每一位进行判定，不断地改变编码串C的值，使它指向当前间隔底端。编码过程用二进制分数加法代替整数码字的串加，概率越大的二进制位可以用分数位进行编码，从而减少编码的位数，达到压缩的效果。
假设A为当前问隔，而Qe为LPS的估计概率。那么对间隔进行准确的划分，必须满足以下式子：
MPS子区间间隔=A-(Qe*A) (1)
LPS子区间间隔＝Qe*A (2)
为了避免硬件较难实现的乘法运算，在JPEG2000中用下面式子代替来避免乘法运算：
MPS子区间间隔=A-(Qe*A) (3)
LPS子区间间隔＝Qe*A (4)
编码时对运算进行简化，直接用小概率符号概率Qe代替LPS区间长度Qe*A，以消除乘法运算。当对MPS进行编码时，编码串的值加上Qe，而间隔减少为A-Qe 。而当对LPS进行编码时，编码串C不变，间隔减小为Qe。然后根据需要对A和C进行归一化，使A落在0．75～1．5的区间内(原始全概率区间为[0,1.5),0.75为中点值）[4]。其相应的整形表示为保持A大于0x8000。若小于这个值，则通过重整化过程，对寄存器C和A进行左移位处理。
由于区间分割采用这样的近似，可能在某些时候使LPS的概率比MPS的大。如当A值为0.75，而Q为0.5时，MPS的概率就为A-Qe =0.25。为避免这种倒置现象，当LPS的间隔比MPS大时，就对它们进行互换。
3.3自适应模型
前文描述的算术编码过程，均建立在已知各个符号概率的基础上。只有已知各符号概率才能根据其划分概率区间。而实际中各符号概率必须通过概率统计模型得到。模型提供了被编码符号的概率，编码算法利用相应概率实现对符号编码。JPEG2000中的算术编码采用基于上下文矢量的自适应模型。
一方面，符号概率的确定是一个自适应过程。利用概率转移有限状态机根据输入消息符号，实时调整符号概率。另一方面，其状态转移是基于上下文的过程。编码器输入不仅有消息序列D，还包括上下文CX。对于同一消息D，其上下文CX不同，则对应的符号概率并不一定相同。必须读取CX当前状态的符号概率来确定消息的符号概率，同时决定是否要转移到下一状态。符号概率的状态转移表由标准提供，共47种状态。
3.4位填充技术
在二进制算术编码中，由于编码过程采用增长传输技术，必须保证当前编码字节有进位时，不影响到编码器已经输出的字节。MQ算术编码器采用了位填充（bit-stuffing）技术解决进位问题[5]。
位填充技术的原理是在编码出现进位，造成缓存中上一待输出字节溢出时，将进位标志作为当前字节编码的一部分，而不加在上一码字上。
这种情况只会在上一码字为0xff时出现。同时为了便于译码，当上一字节为0xfe，且当前字节出现进位，使得上一字节变为0xff时，当前字节进位标志0仍然作为编码输出。这样在译码时，凡碰到码字为0xff，则对下一码字第一比特均按进位标志处理即可。
4. MQ算术编码器实现以及结果分析
4.1编码器流程
图4 MQ编码器总流程图
总流程如上图4。首先对编码器进行初始化INTENC，然后读入上下文CX和待编字D开始编码ENCODE。直到编码结束时，通过FLUSH过程清空寄存器完成编码。
ENCODE流程如下图5，编码时判断D为0还是为1。为0则进行0编码CODE0，为1则进行1编码CODE1。
图5 ENCODE流程图
CODE0编码时，判断0是否为大概率符号。若是则进行大概率符号编码CODEMPS，否则进行小概率符号编码。CODE1编码类似。流程如图6、7。
图6 CODE0流程图
图7 CODE1流程图
4.2结果及分析
首先考察不引入上下文CX时的压缩性能。只要在上下文生成时仅生成一种上下文CX(0),则信源相当于未引入上下文的单符号独立随机信源。0符号概率为70％时的压缩率。引入上下文后压缩率接近68%，性能有所提高。
由于测试的信源未经过JPEG2000前处理步骤，因此这个压缩率仅能提供一定参考。
5. 结论
本文给出了MQ算术编码器原理以及实现流程，利用简单的模型初步探讨了上下文CX在编码中的作用。要进行更深入的研究，必须对JPEG2000编码的其他模块做进一步的研究分析，理解CX在JPEG2000中的产生机制，将前面的模块与算术编码器结合起来，分析它们的性能。
参考文献
[1]
[2]
[3]
[4] 王芳, 汪伟. JPEG2000图像压缩标准及其应用 [J].光盘技术.第一期.2006,1:57-59. 田宝玉. 工程信息论 [M].北京邮电大学出版社.2004:108-116. 李文彬, 朱红. JPEG2000算术编码的研究及其FPGA设计 [J].遥测遥控. 26卷.2005, 5:38~40. JIN LI. Image Compression: The Mathematics of JPEG 2000 [J].Modern Signal Processing. Volume 46,
2003:185-221
[5] Tinku, Acharya, Ping-Sing, Tsai. JPEG2000 Standard for Image Compression: Concepts [J], Algorithms and
VLSI Architectures. JOHN WILEY & SONS, INC.2004:30~195.
The principle and realization of MQ arithmetic coding
GuoQing
Beijing University of Posts and Telecommunications (100876)
Abstract
MQ arithmetic coding is the most important part of entropy coding. MQ arithmetic coding is a context-based adaptive binary arithmetic encoder. It is based on the context in order to improve the coding efficiency. This paper explains the arithmetic coding theory, then further elaborated binary arithmetic coding theory and practical application of how to achieve finite precision arithmetic coder. Keywords: JPEG2000 arithmetic coding MQ-coder
MQ算术编码器原理及实现
郭晴
北京邮电大学信息与通信工程学院，北京(100876)
E-mail:
摘 要：JPEG2000标准中， MQ算术编码是熵编码的主要部分。MQ算术编码器是一种基于上下文的自适应二进制算术编码器。它基于上下文以利于解除信源相关性，利用条件交换和概率估计状态机中的贝叶斯学习过程实现符号概率模型自适应过程，采用位填充技术解决编码中的进位问题，是一种高效率物理可实现的压缩编码算法。本文从算术编码的基本原理入手，详细分析JPEG2000标准提供的MQ编码器编码原理，以及编码流程。利用C语言编程实现JPEG2000标准要求的MQ算术编码器，并分析MQ算术编码器中上下文引入对压缩效率的影响。
关键词：JPEG2000 ；算术编码；MQ算数编码器
中图分类号：TN911.21
1. 引言
随着多媒体技术的不断运用发展，图像压缩要求更高的性能和新的特征。为了满足静止图像在特殊领域编码的需求，JPEG2000作为一个新的标准处于不断的发展中，这种新的标准更加注重图像的可伸缩表述[1]。
算术编码是一种变长信源编码技术,其卓越性能使其在多媒体领域得到了越来越广泛的应用 [2]。JPEG2000标准中，提高图像压缩性能的关键技术之一就是MQ算术编码。MQ算术编码器是一种基于上下文的自适应二进制算术编码器,它继承了IBM的ABIC（自适应双层图像压缩）中Q编码器无乘法的近似和位缓存的策略,增加了条件交换和概率估计状态机中的贝叶斯学习过程，是一种高效率物理可实现的压缩编码算法，非常具有研究价值。
2. 算术编码
2.1编码原理简述
算术编码是一种非分组码。编码时信源符号序列连续的进入编码器，通过编码器的运算得到连续的输出。通常算术编码是讲一条信源符号序列映射成一条码序列，这样的码序列有时也称为码字。算术编码的实质就是，将一条信源信息序列映射到[0,1)区间中的一个子区间，这种映射是一种一一对应关系，以保证唯一译码，然后取这个子区间内的一点所代表的数值作为码字。只要码长合适，就可以保证唯一可译。而当信源序列长度足够大时，每信源符号的平均码长接近信源的熵[2]。
虽然其编码效率很高，但仍然存在缺陷。首先，其运算需要精确的实数加法和乘法，这些运算在有限精度的计算机上实现是非常困难的。正是这个原因使得算术编码从提出到实际应用相差了近二十年之久。直到Rissanen和Pasco分别提出了一个先进后出算法和一个先进先出算法，并由此证明了算术编码可以用有限精度处理技术逼近。Rubin吸收了两个算法的精华，利用有限精度寄存器，讨论了一般算术编码的实现方法。在此基础上，Witten，Neal和Cleary做了进一步地精细化，并给出了一个完整的C语言程序。
算术编码的另一缺陷是编码速度太低，这是因为编码迭代过程中含有整数乘除运算，这些运算对于软件执行和硬件设计是十分不利的。
为此Langdon和Rissanen提出了一个用移位和加法实现二进制算术编码的方法，并成功地应用于黑白二值图象的压缩编码。二进制算术编码是一种步进式编码译码过程。它不需
要等到待编序列完全输入编码器，就可以在序列输入的同时输出编码码字。它同时也解决了算术编码的精度问题。
2.2二进制算术编码
如前所述，二进制算术编码是一种增长型编码译码过程，序列进入编码器的同时可以得到编码输出，而不需要等到所有序列完全进入编码器。
以消息“cacbad”为例说明编码过程。开始时，整个区间是一个半开半闭区间R0=[0,1)，由各个符号概率仍然分解为四个部分：[0.5, 0.62)，(0.62, 0.70)，[0.70, 0.86)，[0.86, 0.9)以代表a，b，c，d区间。计数器Count初始设为0。
第一个符号为c，所属区间R1=[0.5,0.9)完全属于[0.5,1)，为情况2因此编码输出1bit：1。同时根据情况2改变区间大小为R2=[0.0,0.8)。由于Count＝0，因此不用输出任何码字。
第二个符号为a，区间调整为R3=[0.0, 0.24)。由于整个区间属于前半部分，为情况1，因此输出1bit：0，同时区间调整为R4[0.0,0.48)。仍然属于前半部分。继续输出0，调整区间到R5=[0.0,0.96)。
第三个符号为c，区间调整至R6=[0.48,0.864)。不需要输出任何码字也不需要调整区间。 第四个符号是b。区间调整至R7=[0.5952,0.672)，属于情况2，输出1，调整区间R8＝
[0.1904,0.344)。情况1，输出0，调整区间为R9=[0.3808,0.688)。
此时区间属于情况3，因此我们对计数器加1：Count＝1，同时调整区间为R10=[0.2616,0.876)。
第五个符号是a，区间调整为R11=[0.2616,0.44592)，情况1，输出0，同时调整区间R12=[0.5232,0.89184)。此时计数器大于0，因此输出计数器值1bit：1。新的区间为情况1，因此输出1，调整至R13=[0.0464,0.78368)。
最后一个符号是d，区间调整至R14=[0.709952,0.78368)。情况2，输出1，调整为R15=[0.419904,0.56736)。此时我们结束编码，可以用此区间内任意值作为码字输出。不妨取0.5，则二进制表示为0.1000000b，可以添加任意多个0以满足位数要求。
因此作为唯一可译编码，编码过程中输出的码字与最后区间内任一数值结合，串起来即实际16bit编码：1001 0011 1100 0000。可以看到，前9bit为增长编码过程输出，最后7bit为从区间中选择与前9bit共同组成16bit编码。
详细编码过程如图1：
图1 “cacbad”二进制算术编码过程图
3. MQ算术编码器原理
3.1 MQ编码器结构
JPEG2000标准中的MQ编码器结构如图2所示，编码器输入由待编码位D和上下文矢量CX构成，他们是由EBCOT (嵌入式位平面失真率可优化编码)成对产生的。CX是位平面编码中根据邻域相关性归纳而来的概率统计模型，共有l9种。即对于不同的CX，符号概率不相同。
图2 MQ编码器结构图
3.2递归区间划分以及编码近似
递归概率区间分割的ELIAS编码是二进制算术编码的基础[3]。算术编码器首先按符号概率将符号分为大概率符号MPS和小概率符号LPS。区间划分时，LPS区间在MPS区间之前。如图2：
图3 MQ编码器编码区间示意图
当对MPS进行编码时，LPS子区间间隔就被加到编码串上。因而对每一位进行编码时，必须预先知道LPS子间隔的大小和MPS的代表符号。编码过程就是对输入的每一位进行判定，不断地改变编码串C的值，使它指向当前间隔底端。编码过程用二进制分数加法代替整数码字的串加，概率越大的二进制位可以用分数位进行编码，从而减少编码的位数，达到压缩的效果。
假设A为当前问隔，而Qe为LPS的估计概率。那么对间隔进行准确的划分，必须满足以下式子：
MPS子区间间隔=A-(Qe*A) (1)
LPS子区间间隔＝Qe*A (2)
为了避免硬件较难实现的乘法运算，在JPEG2000中用下面式子代替来避免乘法运算：
MPS子区间间隔=A-(Qe*A) (3)
LPS子区间间隔＝Qe*A (4)
编码时对运算进行简化，直接用小概率符号概率Qe代替LPS区间长度Qe*A，以消除乘法运算。当对MPS进行编码时，编码串的值加上Qe，而间隔减少为A-Qe 。而当对LPS进行编码时，编码串C不变，间隔减小为Qe。然后根据需要对A和C进行归一化，使A落在0．75～1．5的区间内(原始全概率区间为[0,1.5),0.75为中点值）[4]。其相应的整形表示为保持A大于0x8000。若小于这个值，则通过重整化过程，对寄存器C和A进行左移位处理。
由于区间分割采用这样的近似，可能在某些时候使LPS的概率比MPS的大。如当A值为0.75，而Q为0.5时，MPS的概率就为A-Qe =0.25。为避免这种倒置现象，当LPS的间隔比MPS大时，就对它们进行互换。
3.3自适应模型
前文描述的算术编码过程，均建立在已知各个符号概率的基础上。只有已知各符号概率才能根据其划分概率区间。而实际中各符号概率必须通过概率统计模型得到。模型提供了被编码符号的概率，编码算法利用相应概率实现对符号编码。JPEG2000中的算术编码采用基于上下文矢量的自适应模型。
一方面，符号概率的确定是一个自适应过程。利用概率转移有限状态机根据输入消息符号，实时调整符号概率。另一方面，其状态转移是基于上下文的过程。编码器输入不仅有消息序列D，还包括上下文CX。对于同一消息D，其上下文CX不同，则对应的符号概率并不一定相同。必须读取CX当前状态的符号概率来确定消息的符号概率，同时决定是否要转移到下一状态。符号概率的状态转移表由标准提供，共47种状态。
3.4位填充技术
在二进制算术编码中，由于编码过程采用增长传输技术，必须保证当前编码字节有进位时，不影响到编码器已经输出的字节。MQ算术编码器采用了位填充（bit-stuffing）技术解决进位问题[5]。
位填充技术的原理是在编码出现进位，造成缓存中上一待输出字节溢出时，将进位标志作为当前字节编码的一部分，而不加在上一码字上。
这种情况只会在上一码字为0xff时出现。同时为了便于译码，当上一字节为0xfe，且当前字节出现进位，使得上一字节变为0xff时，当前字节进位标志0仍然作为编码输出。这样在译码时，凡碰到码字为0xff，则对下一码字第一比特均按进位标志处理即可。
4. MQ算术编码器实现以及结果分析
4.1编码器流程
图4 MQ编码器总流程图
总流程如上图4。首先对编码器进行初始化INTENC，然后读入上下文CX和待编字D开始编码ENCODE。直到编码结束时，通过FLUSH过程清空寄存器完成编码。
ENCODE流程如下图5，编码时判断D为0还是为1。为0则进行0编码CODE0，为1则进行1编码CODE1。
图5 ENCODE流程图
CODE0编码时，判断0是否为大概率符号。若是则进行大概率符号编码CODEMPS，否则进行小概率符号编码。CODE1编码类似。流程如图6、7。
图6 CODE0流程图
图7 CODE1流程图
4.2结果及分析
首先考察不引入上下文CX时的压缩性能。只要在上下文生成时仅生成一种上下文CX(0),则信源相当于未引入上下文的单符号独立随机信源。0符号概率为70％时的压缩率。引入上下文后压缩率接近68%，性能有所提高。
由于测试的信源未经过JPEG2000前处理步骤，因此这个压缩率仅能提供一定参考。
5. 结论
本文给出了MQ算术编码器原理以及实现流程，利用简单的模型初步探讨了上下文CX在编码中的作用。要进行更深入的研究，必须对JPEG2000编码的其他模块做进一步的研究分析，理解CX在JPEG2000中的产生机制，将前面的模块与算术编码器结合起来，分析它们的性能。
参考文献
[1]
[2]
[3]
[4] 王芳, 汪伟. JPEG2000图像压缩标准及其应用 [J].光盘技术.第一期.2006,1:57-59. 田宝玉. 工程信息论 [M].北京邮电大学出版社.2004:108-116. 李文彬, 朱红. JPEG2000算术编码的研究及其FPGA设计 [J].遥测遥控. 26卷.2005, 5:38~40. JIN LI. Image Compression: The Mathematics of JPEG 2000 [J].Modern Signal Processing. Volume 46,
2003:185-221
[5] Tinku, Acharya, Ping-Sing, Tsai. JPEG2000 Standard for Image Compression: Concepts [J], Algorithms and
VLSI Architectures. JOHN WILEY & SONS, INC.2004:30~195.
The principle and realization of MQ arithmetic coding
GuoQing
Beijing University of Posts and Telecommunications (100876)
Abstract
MQ arithmetic coding is the most important part of entropy coding. MQ arithmetic coding is a context-based adaptive binary arithmetic encoder. It is based on the context in order to improve the coding efficiency. This paper explains the arithmetic coding theory, then further elaborated binary arithmetic coding theory and practical application of how to achieve finite precision arithmetic coder. Keywords: JPEG2000 arithmetic coding MQ-coder