摘要：在视频压缩技术中，运动估计是视频处理系统的一个重要组成部分，同时也是最耗时的一部分。本文提出了一种结合冗余小波变换的运动估计算法，有效地减少了运动估计的运行时间，并在TI公司的TMS320DM642芯片上验证了该算法的实时性。
关键词：冗余小波；运动估计；视频压缩；DSP

Motion Estimation Based on Redundant Wavelet Transform and Its DSP Implementation

Abstract: In the technology of video compressing, motion estimation is the important part of the video compressing system and the most time-consuming part. This article brings forward a new motion estimation algorithm based on redundant wavelet transformation and effectively cuts down the time of the motion estimation. We use the TMS320DM642 to test and verify our algorithm.  
Key words: redundant wavelet; motion estimation; video compression; DSP

1  引　言
   在视频压缩算法中，运动估计是非常重要的一部分，运动估计也是视频压缩过程中耗时最长的一部分，约占整个压缩过程运行时间的50%左右[1]，所以在保证估计的准确度基础上减少运动估计运行时间成为视频压缩的研究热点之一。目前运动估计通常采用的搜索算法有：全搜索算法，二维对数算法，“钻石”搜索算法。全搜索算法一定能够找到最优的匹配块，但是计算复杂度很高，硬件实现全搜索算法非常困难。二维对数算法和“钻石”搜索算法能够有效减少计算的复杂度，但是搜索到的结果可能是局部最优点，而不是全局最优点。这些算法都是在时域进行，而在变换域进行运动估计则引起了人们的关注。对此文献[2]提出了冗余小波变换域运动估计方法，利用小波变换的空间方向性，提高搜索精度，但是运算复杂度大，精度不稳定，不利于硬件实现。文献[3]也提出了一种基于二维小波变换域的运动估计算法，同传统的时域运动估计相比，可以节省大量的搜索匹配时间，但小波变换不具有平移不变性，在小波变换域内无法确定相邻帧之间的平移运动，因而会造成大量的误配预测，从而降低运动补偿的效果。
   通过以上分析，我们提出了一种通过冗余小波变换获得运动特征点和潜在运动区域并在时域进行运动估计的变换域、时域相结合的运动估计算法，在保证匹配的准确性同时有效的减少了搜索匹配时间，并在TI公司的TMS320DM642芯片开发板上验证其实时性。
2  冗余小波变换运动估计方法
   冗余小波变换近似于连续小波变换，是除去了下采样的传统离散小波变换DWT。本文冗余小波变换所采用的基函数为Haar基函数，其尺度函数与小波函数的定义分别为：

   L为小波变换级数。对图像进行二维冗余小波变换可以先对图像的行进行一维变换，然后再对列进行一维变换。

2.1冗余小波变换产生运动特征点
   由于冗余小波变换没有下采样，不同尺度的时间抽样率固定，离散小波变换固有的平移变化在这里也消除了，冗余小波变换的结果各子带的大小与输入信号的大小相同。本算法采用相邻尺度子带系数相乘后求和的方法得到模板[2]，计算所有像素点的模板值，如果大于预设的阈值，即确定该点为特征点。这样整个图像的运动特征点就确定下来。
模板公式如下：

2.2潜在运动区域的提取

   结合了冗余小波变换的各子带系数高度相关、方向选择性、各子带与输入信号大小相等以及平移不变的性质，在冗余小波变换域提取潜在运动区域模板。模板由多子带组成包括近似子带（LL）、低-高子带（LH）、高-低子带（HL）、高-高子带（HH）：

2.3时域运动估计

   通过提取潜在运动区域，可以对前面获得的运动特征点进行进一步筛选：即不在潜在运动区域的运动特征点的运动矢量直接设为0，不进行运动估计，只对落在潜在运动区域的运动特征点进行运动估计。运动估计算法类似于传统的宏块匹配法，即在当前帧以特征点为中心取得16*16的宏块，然后在参考帧以该点位置为中心的64*64（对于图像边缘的特征点的搜索，会随着到边界的的距离而调整搜索窗）的范围内搜索匹配宏块，位移差即该顶点的运动矢量。本文采用的最佳匹配准则为绝对帧间差平均准则(SAD) ^[4],其数学表达式为:

3  运动估计方法的DSP实现
   本文采用TI公司的TMS320DM642芯片实现该运动估计算法。TMS320DM642是TI公司最新推出的一款针对多媒体处理领域的DSP芯片，芯片内核采用先进的超长指令字（VLIW）结构，每个时钟周期最高可提供8条32位指令，具有高度的并行性和快速的运行能力。有500MHz/600MHz/720MHz三种时钟频率，如果选用600MHz时钟频率，其最大处理能力可达到4800×106条指令/s。TMS320DM642芯片在C64系列的基础上增加了很多外围设备和接口。

3.1算法实现及流程图：
   首先主机通过PCI初始化DSP并对其加载程序。DSP开始运行主程序程序, 摄像头采集的视频为PAL制, 通过A/D转换芯片SAA7115转化成数字信号,得到的数字图像大小为720*576个像素，4:2:0 格式的YCbCr信号。经过DM642芯片编码处理后，重建图像则通过D/A转换芯片SAA7105转化成模拟信号输出到显示器。程序设计主要采用了TI公司推荐使用的TMS320DM642 Video Port Mini-Driver即视频端口微型驱动函数。视频设备硬件驱动一般分为上下两层，底层为IOM驱动，上层为FVID模式。FVID实际上是DSP/BIOS GIO驱动的简单封装。FVID为视频图像的输入和输出提供了标准的APIs接口。使用FVID提供的函数可以有效地减少便写代码的工作量，并且只需要少量修改便可以很方便地将写好的程序移植到不同的DSP芯片上去，提高了程序适用的灵活性。算法的程序流程图如图1所示，其中输入为原始的视频序列，经过DCT变换，量化以及运动估计和补偿，最后通过VLC变长编码得到最终的视频压缩编码结果。

图1 算法程序流程图

Fig.1 the flow of the algorithm

3.2程序优化处理

由于图像处理的数据量大,数据处理相关性高,并且具有严格的帧、场时间限制,因此如何针对图像处理的特点对DSP 进行优化编程,充分发挥其性能就成为提高整个系统性能的关键。我们从如下几个方面进行考虑^[5~8]:

(1)存储空间的考虑:DSP存储空间的配置十分重要。因为DSP对不同的存储单元的访问速度是有区别的，对片内寄存器的访问速度最快，对片内RAM的访问速度比片外RAM的访问速度快。因此合理地配置和使用存储空间，对系统整体效率影响很大。应该尽可能地把访问比较频繁的常数表和代码段装入片内RAM，如果过大，则把其中一部分装入片外存储器。

(2)使用库函数:TI公司对TMS320DM642的用户提供了功能强大的IMAGE LIB库支持。在这个库中，包含许多常用函数，可以完成DCT/IDCT变换、小波变换、DCT量化等功能。

这些函数都是优化过的，完全能够实现软件流水，效率很高。

(3)高速缓存优化:最大化高速缓存的效率是实现总体视频编码性能目标的关键因素之一。高效的高速缓存可减少由于存储器活动而造成的CPU停止响应，从而提高处理器的吞吐量。

(4)汇编级的优化:对于程序中特别影响速度的地方，如运动估计、运动补偿等部分可以改为线性汇编程序。线性汇编是C6000系列DSP所特有的类汇编工具,只需按照C代码的自然顺序,写出线性汇编语句，不必考虑功能单元的分配,以及指令的并行性。因此，它比编写纯汇编语句耗时要少,又具有较高的执行效率。DM642强大的汇编优化器通过对输入的线性汇编代码分配寄存器和循环优化，能够将汇编程序转化为利用流水线方式的高速并行汇编程序。

4  实验结果及讨论
   为了说明本文所述方法的效果，我们先在PC机上分选用fish﹑workman和tennis三个视频序列，图像大小都为352*288，帧数都为10帧。使用本文提出算法的对三个视频序列进行运动估计并编码，最后解码输出，软件环境为VC++6.0，结果如下：

   由此可见，使用本文所提出的运动估计算法进行视频压缩后，解码可以良好地恢复图像。同时我们还使用MPEG_4SVP压缩标准对fish序列﹑workman序列和tennis序列进行压缩，软件环境为VC++6.0,并比较运行时间,结果见表1。

对于算法的DSP实现，我们在DM642 EVM开发板上实现该算法，从摄像头端获取图像，到DSP芯片算法处理，最后显示器端重建回放，每秒可以处理25帧左右，基本达到了实时性。

   对于冗余小波变换带来的额外时间消耗，我们将小波变换的级数限制在3级以内，但算法的性能也因此受到了限制。本文提出的算法跟目前成熟的运动估计算法如钻石搜索算法﹑三步法相比，当相邻帧变化缓慢时（如可视电话帧）具有一定的优势，而当相邻帧运动变化大而多时，则该方法不具有明显的优势甚至要差一些。原因不仅在于小波变换所带来的时间消耗，而且潜在运动区域将增大，限制搜索域的作用也会减小，此时PMA基本上接近宏块运动估计搜索域，所以算法性能有所下降。另外该算法对数据量的压缩比与目前成熟的压缩算法(如h264)的压缩比还有一定的差距，这些方面的改进都是日后研究的重点。

5  结　论
   本文提出了一种新型的基于冗余小波变换的运动估计算法，与传统的宏块匹配法相比,减少了运算量,通过理论研究和实验分析，运动潜在区PMA与宏块搜索方法结合提高了两者的效率。我们在DM642DSP芯片上验证了其实时性，该算法可以减少搜索时间，并良好地恢复原始图像。所以冗余小波变换应用在视频图像运动估计和补偿上，有很大的发展前景，有待于进一步的深入研究。

参考文献：

[1] 李群迎，张晓林，刘荣科，姚 远. 基于TMS320C64x DSPs的MPEG-4实时编码器设计与实现. 电子技术应用，2005年07期
[2] Suxia Cui, Yong Wang, and James E.Mesh-Based Motion Estimation And Compensation In The Wavelet Domain Using A Redundant Transform.Fowler. IEEE ICIP 2002
[3] Zhang Y-Q and Zafar S.Motion-compensated wavelet transform coding for color video compression. IEEE Transactions on Circuit and SyStems for Video Technology, 1992,2(3): 285~296
[4] 靳济芳.VisualC++小波变换技术与工程实践.北京：人民邮电出版社
[5] 宋胜利，曾峦.基于DM642 EVM的MPEG_4编码器实现.国外电子测量技术，2005年06期
[6] 郭栋，王志良，李正熙，张永忠.基于DSP的实时图像处理系统.微计算机信息，2005年03期
[7] 郭卓锋，丁艳.基于DSP的实时图像处理系统的设计.光学技术，2004年01期
[8] 尹黎明，王玲.运动估计算法及其DSP优化.咸宁学院学报，2005年03期