基于DSP平台的JPEG2000 EBCOT-Tier2算法实现及优化

宋璐雯

（西安科技大学 电气与控制工程学院，陕西 西安 710054）

0 引言

JPEG2000图像压缩标准在高帧率的遥感图像传输中有重要应用[1-2]。目前JPEG2000的应用软件主要有 JasPer，JJ2000，Kakadu。硬件芯片有 ADI推出的ADV212，以及国内自主研发的编解码芯片[3]。

JPEG2000的可伸缩性嵌入式码流可以满足不同要求下的信息传递[4-6]。其中EBCOT-Tier2编码是JPEG2000嵌入式码流组织的最终体现。分析JasPer中的源代码，在JPEG2000的EBCOT-Tier1模块计算后得到位平面信息、编码通道总数、通道长度、RD斜率。根据硬件平台特点，将实现EBCOT-Tier2编码的功能函数依次归为：读取编码参数模块，主标头编码模块，初始化Tile模块，拼接块标头编码模块，读取码流信息和码流数据模块，读取Tile信息模块，码率控制模块，码流打包模块以及结束编码模块。

1 EBCOT-Tier2算法分析

EBCOT-Tier2最核心的是码率控制模块，其采用PCRD算法寻找最优截断点[7,8]。PCRD算法的实质是在满足累积码字长度不大于目标码率的前提下对EBCOT-Tier1编码后所有的码块通道进行截断，使得图像的失真度最小[9]。

1.1 RD 斜率

通常将码块i的第 ni个编码通道的率失真斜率定义为 RD斜率，它是码块通道被截断后，对图像带来的失真度的减小量与当前编码通道的长度增加量的比值。

1.2 码率控制

码率控制算法是在整个Tile的图像数据编码完成后，根据率失真信息判定最优分层截断点。用数学模型描述码率控制算法，即：目标码率定义为Rmax，各个码块的截断位置定义为 ni，图像失真度定义为D。

目标函数：

约束条件：引入拉格朗日乘子λ，将上述问题转化为在约束条件下求取公式（4）式的极小值。

可以将（4）式进一步转化为（5），（6）式：

目标函数：

约束条件：

对目标函数求取偏导数并结合 RD斜率公式进行化简，最后得到（7），（8）式：

根据最后化简的表达式，实际就将PCRD码率控制算法转化为，寻找一个最优 RD斜率截断阈值λ，对编码通道的 RD斜率大于λ的通道进行EBCOT-Tier2打包运算，使得最后的压缩码字长度最接近目标码率maxR 。

2 EBCOT-Tier2算法实现

2.1 码率控制算法

该模块是通过二分法寻找最优 RD截断点。通过比较法得到当前 tile的最大和最小 RD斜率，取二者均值作为第一次搜索的初值，对 RD斜率大于搜索值的所有通道进行标记。之后对标记的通道进行打包，依次进行0位平面tagtree编码，包含信息tagtree编码，计算被包含的通道数，长度增量指标，以及写入该码块的通道数据长度，如图1所示。

图1 码率控制流程Fig.1 Code rate control process

通过 out_cur_point（表示当前压缩文件对应的指针位置）在编码过程中的指针变换，以及累加当前写入码块的有效通道长度 datalen，来计算 length（表示当前截断阈值thresh对应的累积码字长度）的大小。将length与目标码率tilelen进行比较，判定该截断点是否最优。如果是最优截断点，则以该截断点的值再标记一次通道，以备最后打包使用。为了减少码率控制的时间，每次搜索只计算要写入最终压缩文件的数据长度。如果不是最优截断点，通过算法调整其值的大小并重新搜索，直至找到最优截断点。一般情况下，搜索7~8次就可以找到最优截断点。

2.2 tagtr ee编码

在EBCOT-Tier2算法实现中码块的包含信息和0位平面的计算需要建立 tagtree。tagtree的编码过程分为两个步骤[10][11]。在对码块建立了四叉数结构后，首先进行第一步父子节点的差值编码，编码规则是：在初始化时，最初表中的所有值都是 0，从level0开始编码，将上一级的编码值作为下一级编码的初值。编码一个0表示加1，编码一个1表示保持原值不变。在差值编码结束后，进行第二步tagtree的叶节点编码。沿着叶节点到父节点的方向进行搜索，若找到根节点或是第一个已经编码的节点，则停止搜索，并从该位置开始进行tagtree编码，即沿着搜索的反方向，依次排列组合差值编码的值，就得到tagtree叶节点的编码值。

由于在搜索和打包过程中，要频繁调用 tagtree编码条件判断函数，为了避免破坏DSP内部的流水线工作模式，在循环中应该尽量减少跳转指令，所以要对tagtree编码函数进行优化，其C语言的实现框图如图2所示。

图2 C 语言实现tagtree编码Fig.2 Achieve tagtree encoding by C language

3 EBCOT-Tier2算法优化[12-17]

3.1 DSP cache的优化设计

C64x DSP具有两级存储器结构，其采用哈佛结构，一级存储器L1P/L1D cache和L1P/L1D SRAM是固定大小，不可软件配置。二级存储器L2，是由程序和数据共享。L2共有1MB的空间大小，具有可配置cache大小的功能。

在对 EBCOT-Tier2打包程序不进行任何 cache优化时，即将 L2配置为 768KB SRAM，256KB cache，使用CACHE_CCFG_L2MODE_256KC语句设置。将EBCOT-Tier2的程序和数据都放在EMIFB CE0对应的片外存储空间，在cmd文件设置时，将所有段都放在0x60000000~0x63FFFFFF的空间范围内。对于输入256*256 lena_gray图像的码流信息和码流数据，压缩10倍，进行9/7小波变换，EBCOTTier2的编码打包时间是 0.008918s，即处理速度是112f/s。由于程序和数据都放在外部存储器，在每次访问数据信息时都要经历外部存储器—L2 cache—L1 cache的过程，所以代码的运行效率不高。

分析代码，在只对一幅图像进行处理时，程序占用59KB空间。码流信息，码流数据和压缩参数，这三组数据共占251KB空间。而此时L2有足够大的空间以存放这些程序和数据，所以将L2都设置成为 SRAM，CACHE_FSET（CCFG，L2MODE，CACHE_CCFG_L2MODE_0KC）。

此外，在 C64x DSP中 long型的数据位宽是40bits。如果程序中可以使用short型数据就避免使用int型数据，因为L1D的行大小是64B，采用short型就可以存放比int型多一倍的数据，这样可以提高L1D的使用效率，降低cache miss的发生以及miss所带来的stall数。

对EBCOT-Tier2编码打包程序进行上述优化，输入256*256的lena_gray图像的码流信息和码流数据，压缩10倍，进行9/7小波变换。统计cache的使用情况如下表1所示。

从上表数据可以看出，cache的命中率较高。这是因为没有信息存放在外部存储器，而是按照 L2 SRAM—L1 cache的顺序访问数据。其EBCOT-Tier2的运行时间是0.004566 s，处理速度是219 f/s。与上未优化的处理速度比较，代码的运行效率有明显提高。

3.2 码率控制算法优化

使用DSP的内部Timer0定时器对EBCOT-Tier2程序的每个子模块函数计时，发现码率控制函数是最耗费时间，它运行了2277128个CPU时钟。对码率控制函数进行具体分析，如下表2所示。

表1 Cache统计Tab.1 Cach e statistics

表2 码率控制函数运行时间统计Tab.2 The time statistics of code rate control

从上表可以明显看出，计算包头信息耗费了大量时间，而在包头信息计算中tagtree编码最耗费时间。这是因为在码率控制寻找最优截断点时，每刷新一次搜索值，都要进行一次相当于打包的计算量，要对所有标记的通道进行编码。

为提高搜索效率，首先考虑对EBCOT-Tier1输出的码流信息进行处理，列一个256项的统计表，将图像分成了256个质量层。然后从最高项依次向下累加，若累加的码字长度开始大于目标码率长度，则此时的 RD斜率值，定为最优截断点。当输入图像是256×256灰度lena图像，压缩10倍时，根据最初的二分法搜索，测得的最优RD截断值是149。在以该方法确定最优截断点时，发现搜索的复杂度降低了，但是搜索的次数增多，效率变慢，而且最后得到的最优 RD截断值要比原始的测量方法小2~3。由于该搜索方法，只依赖于 EBCOT-Tier1编码的压缩码流长度，而忽略了EBCOT-Tier2的所有编码信息。而在一般情况下，基于 JPEG2000标准的压缩文件的包头信息占压缩文件的5%~10%。

基于以上论述，从另一角度分析搜索过程。包头信息是由6部分构成的，SOP Marker标志位信息，零长度包标志，码块包含信息，0位平面包含信息，每个码块包含在包中的编码通道数以及每个码块对压缩码流贡献的字节长度编码。在搜索过程中，最耗费时间的模块是tagtree编码，即码块包含信息和0位平面包含信息。考虑在搜索的过程中，简化包头计算，即先不计算包头信息的两个tagtree编码，但是保留其他包头信息的计算。这样在搜索过程中，对标记的通道计算被该层包含的通道数，计算写入的长度增量以及计算写入的该码块被截断的通道数据长度，最后通过指针变换，计算出累积码字长度，并与目标码率进行对比，根据对比结果判定是否需要进行下一次二分法搜索，若确定此时的截断值为最优 RD斜率截断点，则码率控制函数不需要再以该 RD斜率值标记一次通道，这是因为在最后一次搜索中通道已经被标记过，所以不用再进行冗余计算。最后，根据每个码块的每个通道的标记信息就可以进行完整的打包运算得到.jpc压缩文件。

以输入256×256 lena灰度图像，进行9/7小波变换，压缩 10倍为例进行说明。发现改进算法的tagtree编码耗费时间明显降低，据统计耗费了119264个时钟周期。进行多次试验观察比较在不同压缩倍数下，改进算法与原始算法在确定最优截断点的差异，统计结果如下表3所示。

表3 RD 斜率最优截断点对比Tab.3 Comparison of RD slope optimal cut-off points

观察上表的统计结果，发现改进算法的最优截断点的值通常会比原始算法的值小 1。接着，通过测量PSNR值进一步定性分析改进算法的特性。分别测试由JasPer软件打包的PSNR的标准值和改进算法得到的PSNR值，如表4所示。

表4 PSNR 对比Tab.4 The comparison of PSNR

从以上数据可以分析得到，改进算法的 PSNR值比JasPer软件的标准值略大，但是二者PSNR值的差异一般最大不超过 0.2dB。再以对比改进算法与原始算法的EBCOT-Tier2运行效率来说明改进算法的性能提升，结果如表5所示。

表5 EBCOT-Tier2运行效率对比Tab.5 The comparison of EBCOT-Tier2 operating efficiency

从以上数据可以看出，改进算法的运行速度有显著的提高，速度基本上是原始算法的2倍左右。综合考虑压缩图像质量和打包速率这两大因素，认为简化包头计算的改进型码率控制算法可用于JPEG2000图像的实时编码打包。

4 结语

针对 C64x DSP的硬件平台，首先分析实现JPEG2000的 EBCOT-Tier2编码打包功能。接着根据DSP的两级cache特点进行代码优化。最后使用DSP的内部定时器找到码率控制模块中最耗时的计算模块，根据PCRD的算法特点，提出了一种简化包头信息计算的码率控制算法，通过验证仿真，该算法提高了EBCOT-Tier2的编码打包效率。

[1] 杨雪, 陈凡胜. 基于预测和JPEG2000的红外图像无损压缩方法[J]. 红外技术, 2016, 38(2): 144-148.

[2] Dong K K, Kim E Y, Yang K H, et al. A mobile tele-radiology imaging system with JPEG2000 for an emergency care.[J]. Journal of Digital Imaging, 2011, 24(4): 709-18.

[3] Liu L, Li D, Li Z, et al. A VLSI Architecture of EBCOT Encoder for JPEG2000[J]. Journal of Beijing University of Posts & Telecommunications, 2003, 2: 882-885 Vol.2.

[4] 孙水发, 张华熊, 仇佩亮. JPEG2000--新的静止图像压缩标准[J]. 计算机辅助设计与图形学学报, 2003, 15(11):1339-1346.

[5] Singh A, Nirala N K, Narula A, et al. JPEG2000: The upcoming still image compression standard[J]. Pattern Recognition Letters, 2001, 22(12): 1337-1345.

[6] 刘方敏, 吴永辉, 俞建新. JPEG2000图像压缩过程及原理概述[J]. 计算机辅助设计与图形学学报, 2002, 14(10): 905-911.

[7] 茅文深, 俞剑, 刘文松,等. JPEG2000码率控制截断预测算法及VLSI设计[J]. 计算机与数字工程, 2016, 44(1): 189-192.

[8] 庄怀宇, 吴成柯, 邓家先, 等. JPEG2000 T_2编码快速算法及硬件实现[J]. 系统工程与电子技术, 2004, 26(12):1939-1942.

[9] 李其虎, 任国强, 吴钦章,等. 一种率失真最优的JPEG2000码率自适应控制算法[J]. 测绘学报, 2011, 40(2): 204-208.

[10] 胡高军, 任广辉, 吴芝路. JPEG2000中Tag-tree编码分析及实现[J]. 电视技术, 2004(10): 13-15.

[11] 吴宗泽, 郑南宁, 黄宇, 等. 基于JPEG2000的TAGTREE编码算法分析及其FPGA实现[J]. 小型微型计算机系统, 2005,26(3): 478-481.

[12] 贺文静, 胡坚, 李子扬,等. 基于多DSP的遥感图像实时压缩系统设计[J]. 电子技术应用, 2015, 41(5): 46-49.

[13] 曾勇. JPEG2000新型码率控制算法及其DSP实现[J]. 电子科技, 2011, 24(7): 122-125.

[14] Tan K C B, Arslan T. Low power embedded extension algorithm for lifting-based discrete wavelet transform in JPEG2000[J]. Electronics Letters, 2002, 37(22): 1328-1330.

[15] Du W, Sun J, Ni Q. Fast and efficient rate control approach for JPEG2000[J]. IEEE Transactions on Consumer Electronics,2004, 50(4): 1218-1221.

[16] Son C H, Kim J W, Song S G, et al. Low complexity embedded compression algorithm for reduction of memory size and bandwidth requirements in the JPEG2000 encoder[J].IEEE Transactions on Consumer Electronics, 2010, 56(4):2421-2429.

[17] An J, Cai Z. Efficient Rate Control for Lossless Mode of JPEG2000[J]. IEEE Signal Processing Letters, 2008, 15: 409-412.