JPEG2000小波提升在DSP上的缓存管理

武汉大学电子信息学院(430079) 辛庆勋 金伟正 顾益芳
 
　　摘　要：提出一种采用高效的内存管理实现的基于块的小波提升方案。该方法通过减少缓存失败增强缓存性能。实验结果表明该方法比现有的快速方法要快两倍多
　　关键词：内存管理 小波提升 缓存失败

　　JPEG2000压缩标准与JPEG相比有更高的压缩效率,尽管如此,它在执行时间上还存在一些问题。为缩短执行时间,必须对小波变换编码进行优化。小波提升方案与传统的卷积滤波相比需要更小的内存和计算量。可是,提升方案在执行垂直小波滤波时仍存在严重的缓存失败问题。
　　Meerwald 曾经提出过行扩展和聚合的方法,Chatterjee 和 Brooks也提出了条采集和递归数据设计来改善提升方案的缓存处理。尽管这些方法可以降低缓存失败率,却不能完全消除缓存失败问题。缓存失败问题在一个内存有限的嵌入式系统中变得较为突出,尤其是在DSP中更为严重。为解决这一问题,笔者提出了一种新的方法与DSP相匹配。
1 主要方法
　　图1是该方法的内存结构图。它由一个有两个64字节块联合的16KB数据缓冲存储器L1、直接映射到SRAM上的数据存储器L2、直接映射到DRAM上的外部存储器和一个DMA控制器组成。

图1 提升算法的输入图像内存处理图

　　通常,为执行提升方案,图像的行先在水平方向滤波,然后经水平滤波的图像再进行垂直滤波。提出的新方法采用一个改进的按块执行的提升方案,块大小与L1缓存中的块大小相同。图1描述了该方法。在小波提升变换开始前,在输入图像内存中块1的数据已通过DMA传输到L2,然后L2中块1的第一行被取到L1缓存中在水平方向提升。以相同方式对块1下面的行进行处理。注意在块1的最后一行滤波后,L1缓存中包含输入图像内存中块1的数据;其次,块1的垂直方向的滤波在L1缓存中完成。这样,垂直提升就不需要取数据,因为L1缓存包含块1的数据。因此,块1在水平和垂直方向的滤波只在CPU需要下一水平行时才可能有缓存失败。这就是笔者提出的方法有显著性能的原因所在。
　　块1完全滤波后,块2被取到L1缓存的1路中;然后,块2的滤波完成后,块3被从L2取到L1的0路中。同时,0路中滤波过的块1 一行一行移到L2。图2描述了滤波过的块1的移动,每个子带分别称为LL、 LH、HL和HH,已经由小波提升算法形成。每个子带中的数据从L2通过DMA传送到输出图像内存中的恰当位置。
　　L2与外部存储器之间的数据传递是独立于L1与L2间的数据传递进行的。这意味着通过DMA的块复制不影响CPU的运转。因此,通过小波提升序列的重新排序和控制DMA,在没有额外CPU负载的情况下增大了缓存成功率。
　　该方法完全去除了缓存失败的问题, 但还存在一个问题,因为小波滤波在边界需要一些邻近块的系数才能获得正确的滤波结果。而这一方法中,垂直提升处理与这一问题不相关,因为垂直的两个邻近块总是同时装载于L1缓存中。但对于水平提升处理,笔者用下面的方法来解决:区1和区3都取到滤波器区域1,如图3所示。对于滤波器区2,区2和区3都是必需的。然而,当达到改进性能时,重叠处理的开销是可忽略的。

图2 提升算法的输出图像内存处理图

图3 重叠块结构

2 仿真结果
　　为检验所提出方法的效率,在TMS320C6416 DSP上用Jasper1.700.2版进行了仿真。所有数据都对灰度图像的第一级分解并且所有图像的宽度2倍放大。
　　表1显示了用本文方法产生的缓存失败数目。其中,在水平滤波上产生的缓存失败是由块重叠引起的。然而,在垂直滤波中,算法完全去除了缓存失败,因此,算法减少了98%的缓存失败率。

图像尺寸	提升方向	缓存失败数
		本文方法	其它方法
256×256	水平	1280	1024
	垂直	0	65536
512×512	水平	4680	4096
	垂直	0	262114

　　表2显示了用现有两种方法与提出方法的DWT处理时间比较,对于所有的图像大小,在水平滤波上都没有改进,但是所有三种方法在垂直滤波中是有效的。在垂直滤波中,行扩展、聚合及两种方法的联合处理时间减少分别为78%、88%和90%;条采集、递归数据设计与两种方法结合的处理时间减少分别为73%、66%和82%。笔者提出的方法在垂直滤波中减少处理时间为98%。注意,水平滤波的速度与垂直滤波基本相同。这意味着笔者提出的算法在垂直滤波中消除了最多的缓存失败。

不同方法		DWT执行时间
		水平ms	垂直ms	总计ms	速度

一般小波提升		2.65	117.63	120.28	1
Meerwald 方法	行扩展	2.85	24.66	27.15	4.38
	聚 合	2.95	14.14	17.09	7.04
	综 合	2.88	10.88	13.76	8.74
Chatterjeek 方法	条采集	2.71	32.27	33.98	3.54
	数据设计	2.87	41.12	43.99	2.76
	综 合	2.77	20.26	23.03	5.22
本文方法		3.81	3.22	7.03	17.18

一般小波提升		12.74	659.35	672.09	1
Meerwald 方法	行扩展	12.98	143.77	156.75	4.28
	聚 合	12.85	77.15	89.10	7.54
	综 合	13.02	61.27	74.29	9.04
Chatterjeek 方法	条采集	12.89	175.90	188.79	3.56
	数据设计	12.95	225.71	238.66	2.84
	综 合	12.87	115.40	128.27	5.24
本文方法		17.94	17.35	35.29	19.04

　　笔者已经验证了JPEG 2000的小波提升算法的性能及其在存储系统中的执行。实验结果表明提出的方法与现有的快速方法相比要快2～3.5倍。
参考文献
1 Rabbani, M., Joshi, R. An overview of the JPEG 2000 still image compression standard,
  Signal Process. Image Com-mun, 2002;17(1):3～48
2 Taubman,D.S.,Marcellin,M.W. JPEG2000: Image com-pression fundamentals, Standards and
  practice. Kluwer Aca-demic Publishers,2002
3 Daubechies, I., Sweldens, W. Factoring wavelet trans-forms into lifting schemes, J.Fourier
  Anal.Appl,1998;4:247～269
4 Meerwald,P. Norcen,R.,Uhl,A.Cache issues woth JPEG2000 wavelet lifting, Proc. SPIE,
  Electron. Imaging, Vis.Commun. Image Process, 2002;4671:626～634
5 Chatterjee,S., Brooks,C.D.Cache-efficient wavelet lifting in JPEG2000. IEEE Int.Conf. on
  Multimedia and Expo, 2002;(1)797～800
6 张旭东,卢国栋,冯健.图像编码基础和小波压缩技术-原理、算法和标准.北京:清华大学出版社,2004