随着数字电视和多媒体信息技术的发展，图像扫描格式的种类与日俱增，要求现今的图像显示系统具备多制式兼容及扫描格式转换能力。为使信号的传输频带降低，我国现行的电视信号为50Hz隔行PAL制式，有较明显的视觉缺陷，例如爬行及大面积闪烁。解决上述缺陷的方法就是去隔行，并提高系统的帧频^[1]。简单的帧复制或帧平均频率提升方法会导致运动图像的模糊或抖动，降低图像的动态分辨率，严重影响视频图像序列的主观质量。为了提高图像的显示质量，采用运动补偿的扫描频率转换方法逐渐为人们所青睐，文献[2～3]给出了两种实现方法。运动补偿频率提升的核心就是准确、高速的运动矢量计算。为此，本文提出了一种用于高速运动估计" title="运动估计">运动估计的改进三步搜索并用FPGA实现了该运动估计器的硬件原型。
1 运动估计/补偿帧频提升原理
1.1 改进的三步搜索
　　三步搜索(Three Step Search)具有计算简单、性能良好等特点，因而在视频系统中得到了广泛的应用^[4]。笔者根据具体的项目要求，在原有的TSS基础上做了相应的改进，提出了改进的三步搜索。
　　(1)原有的三步搜索一般都是步长折半搜索，也就是说，如果第一步的步长为4(像素)，那么第二步与第三步的步长分别为2和1。对帧频提升而言，每两帧之间的时间间隔非常小(约20ms), 说明两帧之间匹配块的运动矢量比较小。基于上述假设，将三步搜索中第一步的步长调整为3，其它两步的步长保持不变，可以直接计算出新三步搜索的搜索范围是±6。经过上述调整，运动估计器明显提升了中心点L₄(图1所示)附近小运动的估计效果，弥补了原三步法因为第一步步长过大而造成的运动估计精度下降。

　　(2)传统三步搜索的匹配块大小为16×16，显然不适合精细的运动补偿线性插补" title="插补">插补。但是，由于真实物体运动的一致性，过小的匹配块会产生较多不正确的运动矢量^[5]。于是，将匹配块的大小调整为8×8，以适应插补要求。
　　新三步搜索的过程如图1所示。每个8×8匹配块的中心点定为该块左上角的像素，搜索区(Searching Area)的大小为20×20(20＝8＋6＋6)。
　　第1步 搜索t帧搜索区内以L₀～L₈为中心的匹配块，用MAD(Mean Absolute Difference)函数计算块匹配误差BME(Block Matching Error)，得出与t＋1帧内当前块最匹配的块；
　　第2步 以第1步搜索得到的最小误差点为中心，即图中空心圆代表的位置，步长为2，搜索其周围的8个顶点，计算以这8个点为中心的匹配块的BME，得出与当前块最为匹配的块；
　　第3步 同第2步，步长变为1。
　　经过三步搜索后，运动估计器找到了当前块在前一帧内的匹配块以及用相对坐标表示的运动矢量，为后续的线性插补做准备。如图1所示，当前块的运动矢量为{5，5}。
1.2 帧频提升原理简介
　　运动估计器计算出当前块的运动矢量后，将运动矢量除以2，就可得到插值" title="插值">插值帧(t＋0.5)内与当前块相对应插值块的位置，或者说相对坐标。如果运动估计足够准确，则插值帧内所有的块都能找到与它对应的当前块，这样，可以将插值帧插补出来。将插值帧连同原始帧按顺序送显，可以实现50Hz～100Hz的帧频提升。插补的原理如图2所示，其中A代表前一帧内与当前块相匹配的块，A’代表A在当前帧内的映射块，I代表插补块，B代表当前块。以上只是简要说明插补的原理，在实际应用中，帧频一般不会很高，例如VGA格式的LCD显示器，其最佳扫描频率为75Hz。要想将逐行的50Hz数字电视信号在液晶屏上显示，只需将帧频提升到75Hz并调整分辨率即可。当然，使用的插补方法会与前述的略有不同，由于篇幅所限，本文就不再敷述。

2 运动估计器的硬件实现
　　标准数字PAL制式的分辨率为720×576^[6]，也就是说，每一帧图像内有6480个8×8的像素块。要想在一帧的间隔内(约20ms)将所有像素块的运动矢量(MV)计算出来，并将插值帧连同原始帧实时送显，就要求运动估计进行得非常快。为了满足矢量计算的高速性，本文提出的运动估计器采用了高度并行的处理结构。
2.1 系统结构
　　该系统主要分为三部分，即存储子系统、运算子系统以及数据组织子系统，如图3所示。

　　存储子系统主要由1块片外双口RAM和若干块片内RAM组成。片外RAM用于存储当前帧和上一帧的像素数据，一个端口用来接收输入视频流，另外一个端口用来向片内RAM缓冲区发送数据。片内RAM主要用于缓冲当前块和搜索区的数据，采用Xilinx VirtexⅡ2V1500的内置RAM充当，在编写代码时用RAMB4_S16_S16原语调用。片内RAM又分为当前块片内RAM以及搜索区(SA)片内RAM两大部分。地址产生及控制单元应该位于存储子系统内部，但是考虑到它的重要性，便将其单独表示。
　　运算子系统即运动估计单元，主要负责运动矢量的计算。它由三组处理单元(PE)、一组比较单元以及部分控制电路组成。
　　数据组织子系统主要包括帧到宏像素块转换模块(Frame To Macro Block)以及一些控制电路，它主要负责输入视频的序列缓冲，然后存入片外RAM以及将片外RAM的数据缓冲，写入片内RAM。
2.2 片内RAM的组织结构
　　用于存储当前块(8×8)的片内RAM由4块32位RAM组成，2块构成1页，共有2页。这样做的目的是为了在读取第n个当前块送入运动估计单元进行计算时，还能用另一页RAM载入第n＋1个当前块的数据。这种乒乓存储结构大大提高了运算速度，实现了时间的复用。图4表示了1页RAM的结构，其中地址线3根，可以计算出1页RAM的容量为：，刚好容纳1个当前块。

　　用于存储搜索区像素片内RAM的组成结构与当前块片内RAM基本相同，不同的是用到的RAM的块数为10块。RAM阵列提供了足够的数据带宽，使运动估计器能自由寻址搜索区内的一行20个像素数据。
2.3 运动估计单元
　　运动估计单元是整个运动估计器的核心，在文献[7～8]的基础上，提出了24个(三组)处理单元同时并行工作的高速结构。如图5所示，基于这种结构，运动估计单元每个时钟周期能计算出24个差值。

　　当数据组织子系统将当前帧的前8行数据存入片外RAM后，运动估计单元开始工作。系统与时钟的上升沿同步，T表示时钟周期。图6给出了运动估计单元的工作时序图；图7给出了处理单元PE的硬件结构。

　　0～7 T 依次读入匹配块L₀、L₁、L₂的第0行到第7行，送入并行PE阵列；
　　8～9 T 每一个PE计算出有效结果；
　　10～12 T 树状加法器阵列计算出匹配块L₀、L₁、L₂的匹配误差BME，并送入结果缓存。
　　13～20 T 依次读入匹配块L₃、L₄、L₅的第0行到第7行，送入并行PE阵列；
　　21～22 T 每一个PE计算出有效结果；
　　23～25 T 树状加法器阵列计算出匹配块L₃、L₄、L₅的匹配误差BME，并送入结果缓存。
　　26～38 T 运动估计单元计算出匹配块L₆、L₇、L₈的匹配误差；
　　39～41 T 比较阵列得出新三步搜索第一步的最佳匹配块。
　　第二步和第三步的情况与第一步类似：第83个时钟的上升沿比较阵列求得第二步的最佳匹配块，第125个时钟的上升沿比较阵列求得最终的最佳匹配块。
　　这样，每经过126个时钟周期，运动估计器找到一个当前块的最佳匹配块，并以运动矢量的方式将结果输出。取主频100MHz，处理大小为720×576的一帧图像所用的时间是=8.1648≈8.2ms＜帧间隔20ms的一半，为后续的插帧过程留下足够的处理时间。
3 实验结果
　　用Verilog硬件描述语言编写源代码，综合采用Xilinx ISE 6.3i；用ModelSim做后仿真，将运动矢量输出到记录文件中；用计算机处理输出的结果，插补出来的t＋0.5帧图像效果良好。输入采用football序列，软硬件的结果对比如图8、9所示。

　　本文提出了一种适用于帧频提升的三步搜索系统实现，并用FPGA对其硬件原型验证。实验结果表明采用高速并行结构的运动估计器具有速度快、精度高等优点，满足帧频提升系统的要求。
参考文献
1 C. Hentchel. Linear and nonlinear procedures for flicker reduction. [J]in IEEE Trans. Consumer Electron., 1987;CE-33(8)192～198
2 T. Reuter. Improved TV standards conversion with 3-dimen-sional motion compensating interpolation filter. [J]in Proc.Club de Rennes Young TV Researchers Conf.[C],Cambridge, MA, Oct. 1988
3 D. P. Siohan, B.Choquet.Field-rate conversion by motion estimation/compensation.[J]in Signal Processing of HDTV, L.Chiariglione,Ed.Amsterdam: Elsevier, 1988:319～328
4 H. M. Jong,L. G. Chen,T. D. Chiueh. Performance improvements and cost reductions of the 3-step block-matching algorithm.[J]in IEEE Trans.Circ. and Syst.for Video Technol
5 吴 勇.数字视频的时-空处理算法及其VLSI实现[J].西安交通大学博士学位论文，2002;0401
6 Roberto Castagno, Petri Haavisto, G. Ramponi.A method for motion adaptive frame rate up-conversion.[J]in IEEE Trans-actions on Circuits and Systems for Video Technology, Oct 1996;6(5)
7 H. M. Jong,L. G. Chen,T. D. Chiueh. Parallel architecture for 3-step hierarchical search block-matching algorithm. [J]in IEEE Trans. Circ. and Syst. for Video Technol.Aug.1994;4(4)
8 G. Gupta and C. Chakrabatri. Architectures for hierarchical and other block matching algorithms.[J]in IEEE Trans.Circ. and Syst. for Video Technol.Dec. 1995;5(6)