摘 要： 针对格式转换领域，提出一种全新的运动估计算法。该算法通过使用改进的三步搜索算法（TSS）进行运动估计，并引入零检测和矢量滤波器对运动矢量进行修正。硬件实现结构基于数字微分分析DDA算法，通过FPGA系统验证证明算法有效，设计可行。
　　关键词： 视频格式转换芯片；帧频提升；块匹配

　　在视频信号中，当场景中有快速运动物体存在时，必须事先估计场景中运动物体的位移量，即进行运动位移估值。得到运动位移的过程称为运动估计，通过运动估计可以去除帧间冗余度，使得视频传输的比特数大为减少。运动估计是视频编码中的核心技术，运动估计的好坏直接影响到编码的效率和图像恢复的质量。
　　目前在视频编码领域使用的运动估计算法有块匹配、像素递归法、相位相关法，其中块匹配运动估计算法(BMA)是消除视频数据时间冗余最基本且最重要的方法。由于其具有简单高效、额外开销小、易于硬件实现等优点而被包括H.26X、MPEG.1，MPEG.2和MPEG-4在内的绝大多数视频编码标准所采用^[1]。块匹配的基本思想就是将每一帧图像分成大小相同、互不重叠的子块(宏块)，然后在参考帧中固定大小的搜索窗口内找到最佳匹配块。按照一种块损失度量准则找到的最佳匹配块到当前块的位移，用运动矢量来描述。最佳匹配块与当前块之间的差值称为残差。预测得越准确，意味着残差中的数值越小，编码后的比特数也就越小。
　　如何快速而准确地在参考帧中搜索到最佳的匹配块是块匹配算法的核心。在本文研究的格式转换领域，运动估计注重物体的真实运动轨迹，不存在估算误差的反馈补偿，要求得到的运动矢量足够准确，能反映物体的真实运动。另外，由于格式转换应用的实时性，要求算法尽量简洁，以易于硬件实现。因此本文使用改进的三步搜索算法（ITSS）进行运动估计，并引入零检测和矢量滤波器对运动矢量进行修正。硬件实现结构基于数字微分分析DDA(Digital Differential Analyzer)算法，并用FPGA实现硬件原型。
1 基于块匹配的运动估计算法
　　在参考帧中寻找匹配块时，需要定义最佳匹配的搜索判据。最佳匹配的搜索判据有以下几种：相关函数CCF(Cross-Correlation Function)，均方误差MSE（Mean-Square Error)，平均绝对差MAD(Mean Absolute Difference)和绝对差之和SAD(Sum of Absolute Difference)。在实际应用中，由于SAD函数简单（不含乘除法），便于硬件实现，而且具有令人满意的性能，因此在本设计中也采用这种算法。公式为：
　　　

　　其中，(x，y)是指参考帧中当前块的中心点(每个8×8匹配块的中心点定为该块左上角的像素），f_n+1(x+i，y+j)是指参考帧中当前块的像素值，f_n-1(x+i+vx，y+j+vy)则是指前一帧搜索中候选匹配块的像素值。
　　根据上面最佳匹配的搜索判据，可得出参考帧中每一个块的运动矢量：
　　　　

　　其中，S表示运动估计的搜索范围。
　　有了判断最优匹配点的准则，剩下的问题就是确定寻找最优匹配点的收缩方法。在目前的块匹配算法中，全搜索法(FS)具有最高的搜索精度，但其运算量大、实时性差。研究者们提出了多种快速搜索算法，较有代表性的有三步搜索法(TSS)^[2]、四步搜索法(FSS)^[3]、梯度下降法(BBGDS)^[4]、菱形搜索法(DS)^[5]、自适应十字模板搜索算法(ARPS)^[6]等。其中三步搜索具有计算简单、性能良好等优点，因而在视频系统中得到了广泛的应用。本文在研究运动估计的特点以及三步搜索算法的基础上，提出了一种改进的三步搜索算法（ITSS）。
　　(1)传统三步搜索的匹配块大小为16×16，这显然不适用于精细的运动补偿线性插补。但是，由于真实物体运动的一致性，过小的匹配块会产生较多不正确的运动矢量。于是，将匹配块的大小调整为8×8 以适应插补要求。
　　(2)原有的三步搜索一般都是步长折半搜索，也就是说，如果第一步的补偿为4(像素)，则第二步与第三步的补偿分别为2和1。对视频系统中的帧频提升来说，每两帧之间的时间间隔非常小(约20ms)，说明两帧之间匹配块的运动矢量相对较小。基于这个假设，将三步搜索中三步步长调整为3、2和1，这样搜索范围为±6。经过调整，运动估计的运动估计精度得到了一定提高。
　　当用块匹配算法对小尺寸块进行运动矢量估计时，常易产生错误的运动矢量。例如，有时即使块处于静止区域，而得到的运动矢量却不为零。因此，本文引入了两种运动矢量修正技术来提高运动矢量的准确性。运动矢量修正技术是基于一个假设，即时-空域是平滑的。
　　(1)零检测(Zero Detection)
　　在计算得到一个块的运动矢量后，用S_ad(v_x，v_y)与S_ad(0，0)做比较。如果两者之差小于一个参数μ，则判定这个块是处于静止区域，并将所检测到的这个运动矢量修正为零矢量。参数μ的设定可根据实际情况进行修改，以提高算法的适应性。
　　(2)矢量滤波器（Vector Filter）
　　因为8×8的块在估算运动矢量时不是很可靠，所以，需要使用邻近块的运动矢量来对计算出的运动矢量进行一定的修正，以提高运动矢量的准确性。
　　以一个块的运动矢量为中心，加上邻近块的8个运动矢量，可以组成一个3×3的滤波器。根据这个滤波器，可以得到修正后的运动矢量：
　　
　　其中，W表示3×3的滤波器窗口。
　　通过上述计算，可以提高运动估计的搜索速度和搜索精度，有效降低出现局部最优点的可能。
2 运动估计器的电路实现
2.1 以改进DDA算法为基础的控制策略
　　在帧频提升算法中，需要根据输入输出频率确定插帧的位置以及相应的运动补偿加权系数。对于任意比例的帧频提升(提升前后的频率比为m/n的情况，n>m)来说，循环中的n-m个新帧必须均匀地插在原来的m个帧中，以此重组成n个帧，这就需要相应的算法来判断插帧的位置。对于此问题，采取的方法是直线DDA算法。
　　DDA算法是以输出频率为分母，输入频率为分子组成DDA因子c，如从50Hz到60Hz的帧频提升，c为50/60，此系数由系统在进行对输入格式的判定之后给出。每次累加c，当c>1时，则不进行帧频变换，直接进入尺寸缩放，并对所得的值减去1；当c<1，则需要进行帧频变换。
　　针对本项目要求,对上述一般的DDA算法进行了改进，当c<1时，每次得到的用作下一次累加的和均小于1；当c>1(需要帧频减低)时，其和可能大于1，此时，不累加c，并对和直接减去1，进行帧频减低，帧频减低算法为帧删除。由于以上算法系数为输入输出频率，因此此算法能够准确控制任意频率间的帧频变换。
2.2 运动估算器的实现
　　在帧频提升算法中，运动估计的实现是整个算法实现的核心。标准数字PAL制式的分辨率为720×576，也就是说，每一帧图像内有6 480个8×8的像素块。要想在一帧的时间间隔内（约20ms）将所有像素块的运动矢量（MV）计算出来，并且同时将插值帧连同原始帧实时送显，这就要求运动估计的速度必须很快。
　　运动估计器主要由三部分组成，即存储单元，运算单元和数据缓存单元，如图1。