利用DSP实现图像的二维DCT变换及优化

liyf

  
         
    Implementation and Optimization of Two-dimensional DCT Based on DSP


摘  要：介绍了图像的二维DCT变换原理，分析了Loeffler的DCT变换算法。根据DSP处理器BF533的结构和指令特点，使用汇编语言对DCT算法程序进行优化，并且在 BF533实验平台上进行验证。实验结果表明，优化后的代码无论在空间还是在时间上运算效率都得到很大提高。
关键词：DCT;   DSP ; 代码优化


Abstract: The principle of two dimensional Discrete Cosine Transform(DCT) is introduced in this paper. The algorithm of Loeffler’s DCT is analyzed. The algorithm of DCT is performed in assembly according to the structure and characteristics of BF533. The codes mentioned above are run on ADSP-BF533 platform successfully. Experiment results show that optimized codes are more efficiency than before in whatever code store space and code execution time.
Keywords: DCT； DSP；Code optimization



1　引言
现今的图像编码标准，一般采用纹理编码方式对图像进行压缩。这种方式极大的利用了图像数据的空间相关性，使图像数据的压缩能够达到很高的比率。它主要是利用数学变换的方法，使用极少量的离散信号来表示大量的时域连续信号[1]。常用的数学变换有很多种，比如离散傅立叶变换DFT、沃尔什变换、哈尔变换、斜变换、离散余弦变换DCT、离散正弦变换DST 、K-L变换等。其中，K-L变换为理想状态下的最佳变换方法，但是，由于K-L变换没有快速的变换算法，而DCT、DFT和DST都具有与K-L变换近似的良好性质,尤其是当一阶马尔可夫过程相邻元素相关系数ρ逼近1时，DCT的近似性能远远优于其它两者,并且DCT变换有具体的快速算法。因此，图像压缩标准中，使用DCT变换来实现纹理编码。
由于DCT变换在各种编码标准中要被反复调用，因此，其代码执行效率对实时视频压缩起着至关重要的作用[2]。实际应用中，如何实现DCT变换的编码及如何用硬件电路实现这种编码变换是使用者关心的问题[3]。本文将利用DSP实现图像的二维DCT变换并对其实行优化。
2　DCT 变换
1974年Ahmed和Rao首先给出二维DCT 变换的数学表达式。该表达式适用于N点的DCT定义，但是，由于MPEG编码一般是把视频图像帧或图片分为场、片、宏块的结构，一帧图像一般包括1－2场，每场包括若干片，每片包括若干宏块，为了方便处理，把每个宏快分成8×8的子块，即DCT处理的基本单元是8×8的子块。因此，直接定义实用8点二维DCT变换：



500)this.style.width=500;" border=0>



因此，可以使用2次一维DCT变换来实现二维DCT变换。
在该定义被提出以后，很多优秀的算法也被提了出来。如Chen,Lee的快速DCT算法等，Loeffler 在1989年提出的实用快速DCT算法共使用11次乘法和29次加法，该算法比起Chen的算法快而且不会发生Lee算法中的上溢问题，并且该算法被证明已经达到了算法极限，是最优秀的算法[4]。该算法如图1，它把整个DCT过程分成了四级，第一级只有8次加法，第二级分为上下两块，上面是偶块，下面是奇块，偶块有4次加法，奇块有6次乘法和6次加法，第三级上面有5次加法3次乘法，下面有4次加法，第四级仅奇块有2次乘法和2次加法。由图1可见，奇数部分的第四级与第二级的计算构成了连续的乘法，这种运算实现的时间将增加实际的计算时间。故Loeffler 提出了无乘法串行的并行计算方法，该方法使用了12次乘法和32次加法，这在具有并行的MAC处理器的运算中，并不增加实际的计算时间[1]。本文即采用这种DCT算法实现图像的压缩与处理。
[1] [2]  下一页
         
          [/td]
        [/tr]
      
  
         
   

3　DSP及其视频指令
我们使用ADI的ADSP－BF533EZLITE评估板作为实验平台，该评估板使用最大内部时钟600M的BF533处理器。处理器内核包括二个40位的ALU,2个MAC,4个视频ALU 及一个桶形



500)this.style.width=500;" border=0>



移位寄存器。这种结构使并行的视频处理成为可能[5]。实验的软件环境是VisualDSP4.5，该环境集成了高性能C/C++编译器，并且具有比普通C/C++编译器更高效的代码优化功能。
    为了进一步提高代码效率，减少程序运行时间和代码空间,根据DSP硬件结构及其指令的特点,对代码进行汇编优化。本文主要注重以下三方面的优化。
（1）利用高度并行的算术运算单元和功能强大的地址运算单元的相结合的特点，使用高密度指令代码进行代码优化。
Blackfin的高度并行结构能在计算的同时进行数据的存储，如R5=R1+R5,R4=R1-R5 ||R1=W[P0+0x4](X);该指令使用两个加法器同时计算出两个32位的值R1＋R5和R1－R5并把该结果分别存入到R5和R4中，此时占用的是算术运算单元的两条内部总线一个指令周期时间，由于外部总线空闲，可以把外部Cache中的数据送入到R1中。索引寻址和变址寻址相结合的模式使一个指令周期内对不同块的SDRAM访问成为了可能，比如上面的指令可以加一条R4=[I2++]仍能正确执行，而且不增加指令执行时间，地址运算单元DAG还包括两个用于嵌套零开销循环的循环计数器以及支持传输过程中饱和的限幅的硬件。这些特性使得Blackfin指令操作的效率很高。
（2）利用有利于DCT变换的操作数位寻址指令来优化
Blackfin DSP指令集不仅支持一个周期最多3条指令的并发执行，而且具有大量的像素操作和向量操作指令可以减少算法时间复杂度。位反转指令对FFT、DCT、DFT等数学变换的操作数寻址提供了方便，在变换之前它把输入数组数据通过位变换的方式变换到易于处理的排列方式，减少了操作数寻址的时间。
（3）利用IEEE 1180 舍入指令来支持DCT变换
Blackfin的加法指令支持预比例加减法，这种指令执行的时间首先通过算术移位将两个操作数变大或者变小后再相加减，这在DCT变换中为了保证运算精度，一般会移位后相加减，这条指令大大加快了DCT变换的速度。
4　DSP实现与优化
无论是C语言还是汇编语言，程序流程均分为初始化、行变换、列变换和移位输出四个步骤。行、列变换具有相似性，如果对行变换的结果矩阵转置，则列变换程序跟行变换一样。对于汇编而言，初始化部分主要初始化FP指针以指向前一函数地址，初始化数据和指针寄存器以保存返回数据等。由于DCT行变和列变换过程相似，且列变换是在行变换操作的基础上进行的。则可利用多种索引寻址寄存器的灵活组合，把行变换结果直接以转置方式存储而不增加实际的存储时间，这样行列变换可使用同一代码循环两次实现，减小了实际代码大小。图3是一维 DCT变换的流程图。
由于DSP的小数乘法指令是先经过乘法运算后自动调整的，其运算时间比起整数运算要费时。因此，采用先倍乘CONST_SCALE，然后整数运算的方式来节省运算时间。运算的结果需要除以系数CONST_SCALE，这在程序运行时多带来了两次乘法，可以使用左右移位来实现。由于右移位同时会带来移位误差，因此在程序中使用了可选择舍入运算方式。
为了达到更好的精度，在行变换时倍乘后再相加。这可使用Blackfin带有预加/减比例的加法指令在一个指令周期内实现。
程序简化行列变换的代码如下:
B0 = R0;               
B3 = R1;               
B2 = R2; …
LSETUP (DCT_START, DCT_END) LC0 = P0;
DCT_START:…
LSETUP(ROW_START,ROW_END)LC1=P2;
ROW_START: …
ROW_END:…
B1 = B0;
B0 = B2;            
DCT_END:B2 = B1;
    程序初始时，R0指向输入矩阵，R2指向中间矩阵,内层循环是行变换过程，该过程结束时，中间矩阵存储着行变换结果的转置。通过B0和B2的指针交换，把中间矩阵当作输入进行行变换，这样，把原输入矩阵变成了输出矩阵，并且矩阵中各元素位置不变。            
比较式（1）和（3）发现，二维DCT 变换时结果为两次无理数sqrt(8)相乘，产生了有理项，因此，在程序里首先多乘一次sqrt(8)，然后在两次DCT 变换结束以后，使用右移3位以达到正常输出。




500)this.style.width=500;" border=0>


为了评估优化后的效果，在ADSP—BF533 EZLITE平台和VisualDSP4.5环境下，当BF533
工作在核心频率594MHZ时，对一源图像点阵灰度数据进行DCT处理。该灰度图像为一个8×8的数组A[6]，对A进行二维 DCT 调用，实际运行结果为：C语言代码为392 bytes，执行时间为3.806397 μs；汇编语言代码为248 bytes，执行时间为1.085859μs。显然，与以C语言为主的二维DCT编码相比，用汇编语言实现的二维DCT编码在代码大小、代码执行时间上均得到了很大改善。
5　结论
本文创新之处在于能根据ADSP-BF533的结构和指令特点及视频信号压缩的实时性要求，使用汇编语言对视频信号进行了二维DCT编码及优化。实验证明：在ADSP-BF533硬件平台和VisualDSP4.5环境下，当 CPU运行在594MHZ时，使用汇编语言实现的DCT变换比C语言实现的DCT变换执行时间减小71.4％，代码空间减小近30％。以标准CIF 测试序列为例，压缩一张352×288的图片能减少4.31ms，可见优化效果显著。

参考文献
[1] 魏本杰,刘明业,章晓莉.二维DCT算法及其优化的VLSI设计[J]，计算机工程，2006.2：16～18。
[2]张琛,赵昕等.基于TMS320DM642芯片的图像编码系统设计[J].微计算机信息,2005.4：113～114 。
[3]柯昱,高健,韦巍.二维DCT快速算法的DSP实现[J],机电工程,1999.5：83～85。
[4]Leoffler C , Ligtenberg A , Moschytz G S1 Practical fast 1D DCT algorithms with 11 multiplications [C]1 In : Proceedings ofIEEE International Conference Acoustics,Speech and Signal Processing( ICASSP) , Glasgow , 1989 . 2 ： 988～991。
[5]Analog Devices Inc.ADSP-BF53x/BF56x Blackfin Processor software Reference[M],2005.http://www.analog.com
[6]贺贵明,吴元保，蔡朝晖等.基于内容的视频编码与传输控制技术[M].武汉大学出版社2005.4：106-122。

作者简介：
曹玲芝(1965 - )，女，教授，博士生，主要从事信号处理、网络化测控系统等方面的研究工作。
张恒（1979-），男，硕士生，主要研究方向为信号处理。
联系方式：
地址：郑州市东风路5号郑州轻工业学院电气信息工程学院院长办公室
邮编：450002上一页  [1] [2]
         
          [/td]
        [/tr]