一种用于图像压缩的算术编码器顺序重归一化方法

摘要

本发明提出了用于联合图像专家组(JPEG)2000图像压缩标准的一种用于图像压缩的算术编码器顺序重归一化方法。该方法添加独立的总移位步数预测规程来获得概率区间A的总移位步数，并分无字节输出、单字节输出和双字节输出三种情况逐次移位概率区间下边界C，从而在每读入一对上下文CX和码值D后可以一次性顺序完成参数计算，无需迭代循环计算。本发明的算术编码器重归一化过程方法可以无缝的替代原有部分，且无需改动算术编码算法的其他环节；逻辑分支间不存在交织判断；降低了运算量，有效提高了数据读入效率，利于硬件实现。

说明书

技术领域

本发明涉及一种用于图像压缩的算术编码器顺序重归一化方法，特别是应用 于联合图像专家组(JPEG)2000编码标准的算术编码算法的顺序算法结构。

背景技术

目前国际最新的JPEG2000标准(参考文献[1])具备帧内编码、压缩效果好、 支持感兴趣区域编码和渐进式传输等品质，因而在高端数字图像应用中得到了推 广。在编码过程中，首先采用离散小波(DWT)处理原始图像，之后采用位平 面编码器(BPC)处理小波系数子带生成上下文和码值(CX/D)，再送入算术编 码器(AC)进行压缩编码。随着各类高清数字图像的应用普及，对图像编码器 的实时处理能力提出了更高要求。因此也对AC的编码速率提出了更高的要求。

AC每读入一个CX/D，都要更新符号概率区间，并在必要时采用循环迭代计 算使其处于约定范围内，之后才可以读入新的数据。循环迭代计算涉及复杂的数 据控制和组合逻辑判断，不宜于电路实现，且约束了数据读入速率，进而影响了 系统的整体性能。简洁高效的编码算法，成为该领域研究热点之一。

该领域有代表性的研究成果有：多CX/D并行输入编码的方案(参考文献 [2]-[5])。多CX/D并行输入编码有利于发挥电路并行的优势，提高系统吞吐量。 但从已发表文献来看，并行编码方案的引入导致了编码关键路径较长，时钟频率 较低；且必须与位平面编码器输出接口紧耦合，对CX/D的读入进行有效控制。 参考文献[2]最早提出了主零点预测(LZP)的思想，即通过分析概率估值的主零 点分布规律，以查表形式求得重归一化规程(RP)期间所需的总移位次数。在 此基础上文献[6]和[7]着重对重归一化规程进行了研究，提出了可以避免循环迭 代计算的顺序算法结构。但是，文献[6]对算术编码算法的整体结构改动较大， 且判决条件分支过多，交叉进行，不适于硬件实现。而文献[7]仅仅考虑了无字 节输出和单字节输出的情况，直接影响了编码结果的正确性。文献[8]-[10]重点 研究了算术编码器的流水线方法实现。流水线算法提高了CX/D的读入速率；但 并没克服循环迭代操作的缺陷，依然无法有效缩短关键路径。

[1]JPEG2000 Part 1：Final Draft，document ISO/IEC JTCI/SC29/WGI N1855.doc， International Standard(ISO/IEC FDISF DIS15444-1)，Aug.2000.

[2]M.Dyer，D.Taubman，and S.Nooshabadi，“Improved throughput arithmetic coder for  JPEG2000，”In Proceeding IEEE International Conference on Image Processing 2004(ICIP 04)，IEEE Press，vol.4，pp.2817-2820，Oct.2004.

[3]Y.Z.Zhang，C.Xu and L.B.Chen，“A dual-symbol coding arithmetic coder architecture  design for high speed EBCOT coding engine in JPEG2000，”In Proceeding IEEE 6th International Conference on ASIC(ICASIC 05)，IEEE Press，vol.1，pp.261-164，Oct.2005.

[4]M.Dyer，D.Taubman，S.Nooshabadi and A.K.Gupta，“Concurrency techniques for arithmetic  coding in JPEG2000，”IEEE Transactions on Circuits and Systems，vol.53，no.6，pp. 1203-1213，June.2006.

[5]N.Noikaew and O.Chitsobhuk，“Dual Symbol Processing for MQ arithmetic coder in  JPEG2000，”IEEE Congress on Image and Signal Processing(CISP 08)，IEEE Press，vol.1， pp.521-524，Oct.2008.

[6]C.Y.Xiong，J.H.Hou，Z.R.Gao and X.He，“Efficient Fast Algorithm for MQ Arithmetic  Coder，”In Proceeding IEEE Conference on Multimedia and Expo(ICME 07)，IEEE Press， pp.759-762，July.2007.

[7]B.Min，S.Yoon，J.Ra and D.S.Park，“Enhanced Renormalization Algorithm in MQ-coder of JPEG2000，”International Symposium on Information Technology Convergence(ISITC 2007)，IEEE Press，Nov.2007，pp.213-216.

[8]C.J.Lian，K.F.Chen，H.H.Chen，and L.G.Chen，“Analysis and architecture design of  block-coding engine for EBCOT in JPEG 2000，”IEEE Transactions on Circuits Systems for  Video Technology，vol.13，no.3，pp.219-230，Mar.2003.

[9]K.Zhu，F.Wang，X.Zhou，and Q.Zhang，“An efficient accelerating architecture for Tier-1 coding in JPEG2000，”in Proceeding IEEE 7^th International Conference Solid-State  Integrated Circuits Technology，vol.3.Oct.18-21，2004，pp.1653-1656.

[10]Y.Li and M.Bayoumi，“A three-level parallel high-speed low-power architecture for EBCOT  of JPEG2000，”IEEE Transactions on Circuits Systems for Video Technology，vol.16，no.9， pp.1153-1163，Sep.2006.

发明内容

技术问题：本发明目的是设计一种用于图像压缩的算术编码器顺序重归一 化方法，该方法基于主零点预测思想，设计了总移位步数预测过程来预测概率区 间A的总移位步数；根据字节的输出次数，设计了一种顺序结构的重归一化过 程RP，使得整个AC算法在读入一个CX/D后，可以一次性的成所有更新计算， 无需任何循环。十分利于电路实现。

技术方案：JPEG2000图像压缩标准所采用的AC算法通过自适应调整符 号出现概率的方式进行编码，并采用了一系列优化技术以便于硬件实现。算法定 义符号概率区间A，并设定数值区间为0.75≤A＜1.5。区间边界定义为C。将接收 符号划分为小概率符号(LPS)，概率估值为Q_e；大概率符号(MPS)，对应概率 估值为(A-Q_e)。当接收到MPS时，根据公式(1)更新A和C；若接收到LPS， 则根据公式(2)进行相应更新。

$\left(\begin{array}{c}A=A-Q_e\\ C=C+Q_e\end{array}\right)---\left(1\right)$

$\left(\begin{array}{c}A=Q_e\\ C=C\end{array}\right)---\left(2\right)$

可以用概率估值表(PET)将符号概率估值及下一可能状态索引预存起来， 以查找表的方式完成A与C的更新。JPEG2000图像压缩标准中的算术编码器中， 概率估值表包含符号概率估值Q_e、概率估值索引Index、下一大概率符号索引 NMPS、下一小概率符号索引NLPS，大概率符号预设MPSS和大概率符号反转 条件Switch。Index用来检索当前符号的概率估值Q_e；NMPS表征在当前上下文 出现MPS时下一状态的概率估值索引；NLPS与之类似。考虑连续收到MPS时， 会通过公式(1)反复更新概率估值，从而导致MPS概率估值小于LPS概率估 值；若连续收到LPS时情况与之类似。为了避免上述情况发生，用MPSS表征 当前大概率符号，即当前码值若与MPSS相等，则视为MPS，反之为LPS。当 LPS概率估值大于MPS概率估值时，MPSS必须反转。Switch用来指示MPSS 是否需要反转。位平面编码器共输出19种上下文，每种上下文都有唯一对应的 Index和MPSS。算数编码器的总体流程是这样的：每收到一个上下文CX和码值 D时，从概率估值表中取出前述参数，分别计算A、C和移位计数器CT，并在 结束时更新Index和MPSS。如此循环，直到处理完所有的CX/D。

编码过程中，由于反复对概率区间A递归细分，精度会随之增长。为此，使 用16进制固定精度整数0x8000表征0.75。当A小于0.75时，通过循环移位使 其保持在[0.75，1.5)范围内。为保证A与C缩放一致，当A左移时，C也左移相应 次数。为防止C溢出，使用缓冲寄存器B来暂存C的高位数据，并采用了位填充 技术来防止进位传播。移位计数器CT用来指示是否需要将B中的字节发送到码 流中，同时从C中移出一个字节缓存到B中。以上计算都在重归一化过程RP中 完成。

本发明的算术编码器的顺序归一化过程方法，通过总移位步数预测过程获取 总移位步数TS，若不满足0.75≤A＜1.5，则调用顺序的重归一化过程RP，将概率 区间A一次性左移TS次，并分无字节输出、单字节输出和双字节输出三种情况 对概率区间下边界C逐次左移。

所述总移位步数预测过程为：概率区间A通过公式A＝Q_e更新时，执行归一 化过程RP，概率区间A的总移位次数TS等于符号概率估值Q_e的主零点个数； 符号概率估值Q_e的主零点个数通过下表查得，

当概率区间A选择A＝(A-Q_e)更新时，又分为两种情况：

1)若更新结果满足0.75≤A＜1.5，TS＝0，不执行RP；

2)若更新结果满足A＜0.75，执行RP；规定A最小值为0x8000，Q_e的最大 值为0x5601，则A更新后的最小值为0x29ff；将A与0x4000比较，若A≥0x4000， TS等于1；若A＜0x4000，TS等于2。

所述的重归一化过程将概率区间A一次性左移TS次，分无字节输出、单字 节输出和双字节输出三种情况对C逐次左移，通过两次比较TS与CT来逐步判 别属于无字节输出、单字节输出还是双字节输出，具体为：

1)无字节输出情况：第一次比较TS与CT，若TS小于CT就属于无字节输 出情况；对C一次性左移TS次，CT用CT＝(CT-TS)更新后，顺序重归一化过程 结束；

2)单字节输出情况：第一次比较TS与CT，若TS大于等于CT，则TS用 TS＝(TS-CT)更新，C左移CT次；调用字节输出子程序输出第一个字节，期间复 位CT；第二次比较TS与CT，若TS小于CT，属于单字节输出情况，将C左移 TS次后，CT用CT＝(CT-TS)更新后，顺序重归一化过程结束；

3)双字节输出情况：第二次比较TS与CT，若TS大于等于CT，属于双字 节输出情况，则TS用TS＝(TS-CT)更新，C左移CT次；调用字节输出子程序输 出第二个字节，期间复位CT；再将C左移TS次，CT用CT＝(CT-TS)更新后， 顺序重归一化过程结束

有益效果：本发明的关键在于新的用于图像压缩的算术编码器的顺序重归一 化方法顺序结构使得算术编码器可以在读入CX/D后可以一次性完成所有参数 的更新，无需迭代循环计算。添加了独立的总移位次数预测规程，可以无缝的替 代原有部分，而无需改动算术编码算法的其他部分；逻辑分支间不存在交织判断； 同时囊括了无字节输出、单字节输出和双字节输出三种情况，保证了编码结果的 正确。该算法结构适于硬件实现。

附图说明

下面结合附图和实施例对本发明做进一步说明。

图1JPEG2000图像压缩标准所采用的算术编码器总体算法流程，

图2带有循环移位判断的重归一化过程流程，

图3总移位步数预测过程，

图4顺序结构的重归一化过程。

具体实施方式

本发明设计了一种用于图像压缩的算术编码器的顺序重归一化方法，该方 法在算术编码器读取一对CX/D计算概率区间A和概率区间下边界C的同时， 通过总移位步数预测过程获取总移位步数TS；若不满足0.75≤A＜1.5，则调用重 归一化过程RP，将概率区间A一次性左移TS次，并分无字节输出、单字节输 出和双字节输出三种情况对概率区间下边界C逐次左移。无需任何循环。十分 利于电路实现。

具体实例如下：

1)收到一对新的CX/D后，根据CX求取Index，MPSS，然后用Index从表1 中求取查表移位步数LUT，概率估值Q_e，下一大概率符号索引NMPS、下一 小概率符号索引NLPS，大概率符号预设MPSS和大概率符号反转条件Switch。 之后通过A＝(A-Q_e)来更新A。

2)如果满足D＝MPSS且A≥0x8000，则A＝A，C＝C+Qe，Index＝Index， MPSS＝MPSS，TS＝0。本次更新结束，可以读入下一对CX/D。

3)如果满足D＝MPSS且A＜0x8000且A＜Q_e，则A＝Q_e，C＝C，Index＝NMPS， MPSS＝MPSS，TS＝LUT。之后执行重归一化过程RP；

4)如果满足D＝MPSS且0x4000≤A＜0x8000且A≥Q_e且，则A＝A，C＝C+Q_e， Index＝NMPS，MPSS＝MPSS，TS＝1。之后重执行归一化过程RP；

5)如果满足D＝MPSS且A＜0x4000且A≥Q_e且，则A＝A，C＝C+Q_e，Index＝NMPS， MPSS＝MPSS，TS＝2。之后执行归一化过程RP；

6)如果满足D不等于MPSS且A＜Q_e且Switch＝1且A≥0x4000，则A＝A， C＝C+Q_e，Index＝NLPS，MPSS＝1-MPSS，TS＝1。之后执行重归一化过程RP；

7)如果满足D不等于MPSS且A＜Q_e且Switch＝1且A＜0x4000，则A＝A， C＝C+Q_e，Index＝NLPS，MPSS＝1-MPSS，TS＝2。之后执行重归一化过程RP；

8)如果满足D不等于MPSS且A＜Q_e且Switch不等于1且A≥0x4000，则A＝A， C＝C+Q_e，Index＝NLPS，MPSS＝MPSS，TS＝1。之后执行重归一化过程RP；

9)如果满足D不等于MPSS且A＜Q_e且Switch不等于1且A＜0x4000，则A＝A， C＝C+Q_e，Index＝NLPS，MPSS＝1-MPSS，TS＝2。之后执行重归一化过程RP；

10)如果满足D不等于MPSS且A≥Q_e且Switch＝1，则A＝Q_e，C＝C， Index＝NLPS，MPSS＝1-MPSS，TS＝LUT。之后执行顺序重归一化过程；

11)如果满足D不等于MPSS且A≥Q_e且Switch不等于1，则A＝Q_e，C＝C， Index＝NLPS，MPSS＝MPSS，TS＝LUT。之后执行重归一化过程RP；

12)重归一化过程将概率区间A一次性左移TS次，然后分为以下三个阶段 分别判断处理：

●无字节输出情况：第一次比较TS与CT，若TS小于CT就属于无字 节输出情况；对C一次性左移TS次，CT用CT＝(CT-TS)更新后， 归一化过程结束；

●单字节输出情况：第一次比较TS与CT，若TS大于等于CT，则TS 用TS＝(TS-CT)更新，C左移CT次；调用字节输出子程序输出第一 个字节，期间复位CT；第二次比较TS与CT，若TS小于CT，属于 单字节输出情况，将C左移TS次后，CT用CT＝(CT-TS)更新后， 归一化过程结束；

●双字节输出情况：第二次比较TS与CT，若TS大于等于CT，属于 双字节输出情况，则TS用TS＝(TS-CT)更新，C左移CT次；调用 字节输出子程序输出第二个字节，期间复位CT；再将C左移TS次， CT用CT＝(CT-TS)更新后，归一化过程结束。