JPEG2000的MQ模块在DSP环境下的优化实现

张浩宇，徐建军，张　南

（国防科学技术大学 计算机学院，长沙　410072）

JPEG2000的MQ模块在DSP环境下的优化实现

张浩宇，徐建军，张南

（国防科学技术大学 计算机学院，长沙410072）

随着航空技术和专用CCD/CMOS成像技术的飞速发展，星载系统中图像的大小和清晰度都成倍的提高，由此带来的数据量和带宽要求也呈指数级增长，如何在星载高性能的计算平台下有效压缩图像成为了星载系统面临的最主要挑战之一。经典的JPEG2000图像压缩算法，其模块并不适应高性能DSP中编译器进行流水线排布的要求，导致运行效率无法达到要求。本文面向JPEG2000图像压缩算法，提出一种在DSP环境下，JPEG2000算法中MQ编码器的优化算法。优化算法使用了多种线性汇编语言流水线排布的通用优化技术对MQ编码器进行DSP环境适应性优化，并根据MQ编码器算法特点，进行了编码流程简化和二次重归一化过程中冗余分支的消除。图像压缩试验表明，该算法提高了MQ编码器的吞吐率，提升了JPEG2000的压缩效率。

数字信号处理器；JPEG2000；算术编码器；线性汇编

本文著录格式：张浩宇，徐建军，张南. JPEG2000的MQ模块在DSP环境下的优化实现[J]. 软件，2016，37（9）：130-135

1　引言

在航天侦测领域，随着图像处理技术的进步和应用需求的发展，海量的探测数据和有限的空地数传带宽之间的矛盾亟待解决。高性能DSP[1]的出现使得高速在轨图像压缩成为可能，依靠多个功能部件并发执行指令和软件流水排布技术，高性能 DSP显著提升了程序代码尤其是其中循环代码的执行效率。但是其编译器在进行软件流水线排布时有着诸如循环中的代码不能过长，一般不能超过250条线性汇编指令；循环中不能有函数调用；循环中不能有跳转指令；循环中的条件判读不能过多，一般不能超过6个；循环不能有嵌套；程序执行时不能有中断产生等限制[1]，这就对程序代码的编写提出了严格的要求。

JPEG2000是新一代的图像压缩算法，具有压缩速度快，信噪比高，同时支持有损和无损压缩，可同时生成多种分辨率等优点。JPEG2000的压缩过程如图1所示，其中的嵌入式块编码过程（EBCOT）把经过离散小波变化（DWT）得到的小波系数分成互相不重叠且大小相同的编码块，然后将编码块按比特位高低分成多个位平面，然后从最高有效位平面到最低有效位平面，对于每个位平面进行基于上下文的算术编码（MQ编码）。

图1　JPEG2000编码流程

图2是MQ编码器的一个简要工作流程。它的输入是当前的数据位D和当前位的上下文（如前文表述概念）决定的类型CX组成的一个决定对，而输出是单个的压缩码字，也就是压缩数据CD。压缩数据CD也叫做一个“MQ码段”，只是被压缩的码流中的一部分。当数据位D和类型CX组成的数据对（CX，D）从位平面编码器到达时，压缩数据位CD增量的产生。

MQ编码器使用了状态变量来实现算术编码，这些变量包括A，C，temp，t和L。A和C是分别用来表示概率区间长度和下限，他们一起表示出当前的概率子区间。temp为一临时的字节缓冲器，用来保存输出的编码。t用作一个计数器，当这个计数器减少到零时，部分产生的编码位应被移出C寄存器，并移入临时字节缓冲器temp中。L代表到当前为止所产生的编码字节数。

图2　MQ编码器流程

由于不同码流引起的输出序列是不同且唯一的，所以MQ编码器对于不同的码流概率估计值也不可能是固定的，必须能够实现随着码流数据变化而随时调整。MQ编码器通过使用概率值表和上下文状态表能够实现随码流变化自适应的功能。

其中概率估计表是一个可以对原始数据快速适应的概率估计模型。概率估计表包括47个索引值。每个索引都对应着不同的状态，每个状态有28位，其中6位是当前符号是大概率符号（MPS）时下一个索引（NMPS）；6位是当前符号是小概率符号（LPS）时下一个索引（NLPS）；一位是交换位（SWITCH）来确定本轮是否发生大概率符号的交换，只有当前符号是小概率符号的时候才有可能用到；15位是小概率符号的概率值（Qe），它体现了序号值Index和对类型CX的LPS最不可能符号的估计概率之间的关系。大概率符号（MPS）就是在之前的码流中出现的次数多的符号，它就是0或者1，随着码流输入不断变化。

上下文概率映射表包括19个不同的状态，每个状态包括索引值（index）和大概率符号值（MPS）。Index是一个范围从0到46的6比特量，对应于概率估计表中的一项，用于标识对当前类型的符号集合做的概率估计。

MQ编码器大体可以分为两个主要阶段[2]，第一阶段是编码阶段，根据输入的上下文判断当前的编码符号的类型是大概率符号（MPS）还是小概率符号（LPS），并根据该类型当前保存的索引取出当前该类型符号的概率估计值（Qe），并根据Qe值按照输入D进行新概率计算，更新A、C寄存器和该类型的索引。第二阶段是重归一化阶段，主要进行码流的输出和概率的重归一化。

针对MQ编码器的性能问题，不少学者提出了优化方案，刘奇卫[3]等人设计了4级流水线的2符号并发编码结构，王振道[4]等人设计实现了一种部分并行的优化算法，但这些优化都是针对算法本身的改进，没有针对DSP应用平台，仍无法改变其不适应DSP环境的问题。本文基于TI的C6000系列DSP，消除了JPEG2000在DSP环境下对流水线排布影响较大的上下文机制，将MQ编码器模块进行适应性改造，大幅提高了程序的运行速度。

2　改写过程中的线性汇编优化

首先对于MQ编码器使用线性汇编语言进行改写，但仅仅对原模块进行简单的线性汇编改造，并没有体现出本文选择DSP处理器的初衷。为了充分发挥DSP并行优势，提高程序性能，使用了以下方法：

（1）使用DSP环境下的指令条件执行机制来取代原有跳转指令。根据不同的DSP型号，在DSP中一般会提供5-6个条件寄存器，储存在该寄存器中的变量可用于作为其它指令的条件：即当条件寄存器内变量非0时，使用它作为条件的指令就会被执行，否则则不执行，具体改造示例如图3所示：

图3　使用条件执行机制消除跳转

（2）循环展开。由于编译器进行流水排布时只对最内层循环进行排布，因此在程序改造中通过条件执行机制将嵌套循环的外层循环每次迭代后的参数变化改为条件执行语句，从而展开这一层循环，扩大流水排布范围，达到进一步改善流水排布效果的目的。具体改造示例如图4所示：

图4　使用条件执行机制展开循环

（3）通过数据预取与打包减少流水空闲。流水线排布的成功与否主要受到程序 的结构影响，而排布成功之后的流水线的执行时间则主要受制于访存指令多少。访存指令需要多个周期执行，且往往与其后的指令有较高的相关性，很多时候会导致流水线因等待数据而停滞。对此，本文主要采用一次存取多个数据和提前读取数据的方法减少访存指令的数量及其造成的流水线空白期。C6000系列一次可以存取64位数据，而一般程序中处理的数据以16位和32位为主，这样通过64位的存取操作指令和数据处理指令我们可以一次读取多个数据从而减少存取指令的数量。同时，我们将循环中的读取指令提前，即在进入循环前预取第一次循环所要用到的数据，以后每次循环都在做本次循环的数据处理的同时预取下次循环即将用到的数据，减少因等待数据而造成的流水线停滞。

3　MQ编码器模块优化

针对DSP独特的体系结构，为了提高MQ模块在DSP环境下的效率，不仅仅需要在汇编语言级别进行适应性优化，而且需要对MQ编码器的流程进行优化改造，使之在目标平台上具有更高的效率。

3.1编码流程简化

MQ的编码阶段的算法流程如图5所示，算法有五条执行路径，在原有算法的运行情况下DSP的汇编优化器难以排布并行流水线，效率会大大降低。而如果基于前述的DSP并行流水排布规则进行优化，为了消除分支指令，相当于将5条路径全部展开串行执行，将导致循环单次迭代长度过长且相关性较高，即使排布出流水也极大的影响流水线排布效果。因此，需要对算法的执行流程进行优化。

将图中的左路分支合并入右路后MQ编码器的重归一化流程如图6所示，其中，当t=0时的字节输出过程在一次重归一化过程中最多执行2次，输出字节时有两种情况主要是因为MQ编码器当0xFF字节被输出到字节缓冲器时，会将一多余的冗余位插入到变化的码字中，保证来自之前编码中对C寄存器的算术操作所产生的进位不会传播到已经被发送到字节缓冲中的字节。在发生第一次字节输出时，由于C寄存器的值来源于编码阶段，在发生C=C+D的操作时可能会产生进位，故8位的temp寄存器的值在与进位相加时出现了3种可能会大于等于0xFF的情况，这就使得不仅需要对输出进行独立，使temp=0x100时输出0xFF，还需要在寄存器向temp中移入值时考虑进位的存在，导致这一分支比较复杂。但是在第二次字节输出发生时，寄存器C和t的值都来源于上一次字节输出后的更新，这种情况下，上一次字节输出后的处理保证了这一次t=0时C一定不会产生进位，故不需要考虑特殊的输出，也不需要考虑保留进位，其过程可简化成如，从而减少冗余分支，提高性能。

图5　MQ编码器编码流程

图6　优化后的MQ编码流程

图7　重归一化阶段算法流程图

3.2二次重归一化的冗余分支消除

首先将图7中的左路分支合并入右路后MQ编码器的重归一化流程。其中，当t=0时的字节输出过程在一次重归一化过程中最多执行2次，输出字节时有两种情况主要是因为MQ编码器当0xFF字节被输出到字节缓冲器时，会将一多余的冗余位插入到变化的码字中，保证来自之前编码中对C寄存器的算术操作所产生的进位不会传播到已经被发送到字节缓冲中的字节。

在发生第一次字节输出时，由于C寄存器的值来源于编码阶段，在发生C=C+D的操作时可能会产生进位，故8位的temp寄存器的值在与进位相加时出现了3种可能会大于等于0xFF的情况，这就使得不仅需要对输出进行独立，使temp=0x100时输出0xFF，还需要在寄存器向temp中移入值时考虑进位的存在，导致这一分支比较复杂。

但在第二次字节输出发生时，寄存器C和t的值都来源于上一次字节输出后的更新，这种情况下，上一次字节输出后的处理保证了这一次t=0时C一定不会产生进位，故不需要考虑特殊的输出，也不需要考虑保留进位，其过程可简化成如图8，从而减少冗余分支，提高性能。

图8　优化后输出过程

4　试验及测试结果

选用不同分辨率下的图像压缩的标准测试样本中Lena的黑白二值图片作为测试集合。对于使用原始MQ编码器模块的JPEG2000程序及使用优化后版本的JPEG2000程序分别进行压缩测试并利用Profiler获取其总执行时间及MQ模块执行时间。各程序版本编译选项为-opt-level=3。测试结果如下表所示。测试结果表明，本文提出的MQ模块优化改造有效提高了MQ模块及压缩程序的执行效率。

图9　图像测试集

表1　压缩测试结果

5　结束语

本文提出了一种星载DSP环境下JPEG2000的算术编码模块的优化方案，该方案采用循环展开等方法解决原程序无法排布软件流水的问题，另外通过算法执行路径和垂直提升算法进行优化改造，从而大大提高了MQ模块的单次执行效率以及JPEG2000压缩算法的整体压缩效率。另外，该方法在实际使用中还有若干问题有待解决，如MQ编码器软件流水排布效率问题以及JPEG2000中其他模块的优化问题等，都有待于进一步研究。

[1] Texas Instruments Incorporated. TMS320C6000系列DSP编程工具与指南[M]. 田黎育, 何佩琨. 出版地: 北京清华大学出版社, 2006. 9: 235-240.

[2] Skodras A, Christopoulos C, Ebrahimi T. The Jpeg 2000 Still Image Compression Standard[J]. IEEE Signal Processing Magazine, 2010, 18(5): 36-58.

[3] 刘奇卫. 基于JPEG2000二进制算术编码器的研究与设计[D]. 浙江大学, 2006.

[4] 王镇道, 章兢等. 一种JPEG2000算术编码器的优化算法与实现[J]. 湖南大学学报(自然科学版), 2007, 34(4).

Optimization and Implementation of MQ Encoder of JPEG2000 in DSP

ZHANG Hao-yu, XU Jian-jun, ZHANG Nan
(Academy of Computer Science and Technology, National University of Defense Technology, Changsha 410072)

With the rapid development of aviation technology and a dedicated CCD/CMOS imaging technology, space borne system image size and clarity are increased exponentially, which lead to the exponential growing of the magnitude of data and bandwidth requirements. Therefore, how to compress images effectively in space borne systems have become a hot topic and a serious challenge. The classic JPEG2000 image compression algorithm is not designed to run on DSP, so the perfermance decline rapidly. This paper present a optimized MQ-encoder in DSP based on JPEG2000 compression algorithm. The optimizations used in the paper include serval common optimized techonologies in order to let the compiler construct pipeline properly. Furthermore, based on the characters of MQ encoder, we simplify the encoding flow and cut some paths in the secondary normalization. According to the experiment results, the optimized MQ-encode algorithm applying our method achieves higher throughput compared to the classical algorithm.

DSP; JPEG2000; MQ; Arithmetic-Encoder

TP391.41

A

10.3969/j.issn.1003-6970.2016.09.031