基于三维递归搜索的多级运动估计视频帧率上转换算法

贾 茜 肖进胜 易本顺 甘良才

(武汉大学电子信息学院 武汉 430072)

1 引言

尽管目前视频传输中的编解码技术已经可以获得很高的压缩比，然而为了适应一些网络带宽的限制，通常将视频信号的时空分辨率降低使数据量更少，在时域中可以通过编码端跳帧来实现。这样，在解码端的低帧率视频必然会引起运动不连续、图像质量的退化，尤其是在快速运动和复杂场景中更为明显。为此，可以在解码端采用视频插帧，即帧率上转换技术来恢复原始帧率以提高视频图像的主观视觉效果，该技术也可用于不同帧率视频格式之间的转换。由于简单的帧重复、帧平均会产生运动抖动和模糊，因此在实际中帧率上转换通常采用的方法是基于块匹配的运动补偿内插(Motion-Compensated Interpolation, MCI)，该方法所获得的内插帧质量取决于运动矢量估计的精度。已存在的 MCI算法按照运动矢量的来源不同可以分为两类：第1类方法基于压缩域，直接对解码端得到的码流中的运动矢量和残差信号进行分析和处理[1,2]。由于省去了重新运动估计的步骤，计算量显著降低，然而该类算法对压缩标准有依赖。第2类方法基于像素域，对解码后的图像序列相邻帧重新进行运动矢量估计，得到面向插帧应用的运动矢量[3-11]，再进行分析和处理。本文主要讨论第2类算法。

在MCI中需要解决以下3个问题：(1)估计的运动矢量必须正确地反映真实的运动才能准确地重构插值帧。大多数的MCI算法利用块匹配算法做运动估计，基于块匹配的各种模板搜索快速算法大幅度地减小了计算量。然而，与视频压缩不同的是，MCI中的运动估计不是为了最小化残差信号的能量，而是为了找到代表真实运动的矢量场，使重构的内插帧获得符合主观视觉的图像信息。目前，已存在众多运动估计的快速搜索算法，利用运动矢量场的相关性预测当前块的运动，自适应地选择不同搜索模板和搜索策略，可以在一定程度上进一步提高搜索速度和精确度，典型算法如：预测运动矢量自适应搜索技术[3](Predictive Motion Vector Field Adaptive Search Technique, PMVFAST)。由于传统的块匹配搜索算法得到的运动矢量最优解常与真实的运动不符，为了提高运动矢量场的时空一致性，获得代表真实运动的运动矢量，文献[4]提出了3维递归搜索(3-D Recursive Search, 3-D RS)算法，该算法追求的是平滑的运动矢量场，而且其收敛快速，复杂度低，所以在面向帧率上转换应用的运动估计中受到重视。(2)传统的块匹配算法是前后两帧“单向”搜索，使得中间内插帧的一个像素可能有多个运动轨迹通过，或者没有运动轨迹通过，而分别产生“重叠”和“空洞”问题。而双向运动估计[5,6]是以内插帧中的块作为定位基准，在前后帧中对称地搜索匹配块，这样在插值补偿中间帧时就不会存在单向运动估计方法所带来的像素“重叠”和“空洞”。(3)块匹配方法是基于块内所有的像素点具有一致运动状态的假设，当一个块包含多个不同运动时，会使内插帧出现“块效应”。国内外研究者提出了许多方法来提高运动估计精度，或者改进运动补偿策略，以减小块效应，例如：文献[2]将中值滤波作为矢量后处理步骤，在运动补偿时采用类似于 H.264和 MPEG4中所用到的重叠块运动补偿技术(Overlapped Block Motion Compensation, OBMC)来减小块效应；由于传统的中值滤波算法计算量较大，文献[3]提出了一种简化的中值滤波方法；文献[6]通过K-均值聚类对运动对象进行分割，再采用可变尺寸块运动补偿(Variable-Size Block Motion Compensation, VS-BMC)和自适应的OBMC以克服传统OBMC带来的图像过平滑，获得了较好的内插效果，但是该算法在运动估计和对象分割时需要反复迭代，计算较为复杂。

本文力求用低复杂度的算法获得好的内插图像质量，提出了一种基于 3-D RS的多级运动估计帧率上转换算法。该算法将3-D RS与双向运动估计算法相结合，在相邻的前后两帧中计算初始运动矢量；然后按照块的尺寸对初始运动矢量“由粗到细”逐级精确修正，并利用简化的中值滤波器对矢量场进一步平滑；再通过时域线性插值补偿产生中间帧。该算法在不产生“重叠”与“空洞”的同时，提高了双向运动估计准确性和运动矢量一致性，有效减小了块效应，并且复杂度低、易于实现，可应用于高清视频的实时处理。

2 基于3-D RS的多级运动估计帧率上转换算法

在视频编解码领域已有很多成熟的块匹配算法。但是，如前所述，在视频插帧应用中要求运动信息能够反映物体的真实运动，仅靠匹配误差确定的运动矢量有可能与真实的运动截然不同，使运动补偿的内插帧产生与主观视觉不符的图像信息。由于视频对象的运动具有连续性，因此运动矢量间也存在时空相关性。由此，出现了递归搜索的方法，它是利用运动场时空相关性预测的搜索算法，不仅能获得更为平滑的运动矢量场，同时也减少了计算开销。

2.1 双向3维递归搜索的运动估计

3维递归搜索包括空间递归和时间递归，即认为当前块与当前帧中的空间相邻块以及前一帧中时间相邻块在运动上具有相关性，当前块的运动矢量可由时空相关矢量“传播”得来。应当注意的是，当前块的运动矢量与其时间、空间相邻块运动矢量相近，但并非完全相同，如果所有的候选矢量都来自相邻块运动矢量的原始值，则不符合实际情况。因此，给原始运动矢量加上一个更新矢量，得到的候选运动矢量将更接近实际、更准确。传统的 3-D RS算法中运动估计误差准则[4]由式(1)计算：

其中F(x,t)是t帧中像素点x的亮度，T是帧数间隔，B(X)代表参考帧中的块，X为块的位置，C为候选矢量，U(X,t)为更新矢量，α为常数。式(1)即首先计算相邻两帧中块内像素的绝对差和(Sum of Absolute Differences, SAD)，再加上一个依赖更新矢量大小的惩罚值，误差最小的运动矢量即为估计值。

在搜索匹配块时，如果按照单向运动估计获得的运动矢量线性补偿插值可能会有像素“重叠”和“空洞”问题，如图 1(a)所示。而双向运动估计是以内插帧中待插块的坐标为基准，在相邻的前后两帧中对称地搜索匹配块，如图1(b)所示，从而巧妙地解决了该问题。

由于原始的3-D RS利用SAD作为匹配准则，这与其他单向运动估计的经典搜索算法一致，为了同时利用 3-D RS和双向运动估计各自的优点，将它们进行结合时需要对匹配准则进行修改，故本文用双向运动估计中的匹配准则“双向绝对差和”SBAD(Sum of Bilateral Absolute Differences)来代替原来的SAD。

图1 单向运动估计与双向运动估计示意图

其中Bi,j代表内插帧中的块，s为内插帧中的像素点，v为运动矢量，fn-1和fn+1是与内插帧相邻的前后两帧。为了减小搜索时的计算量，可以减少候选矢量的个数[7]，在本文运动估计算法中，对于第n帧中位置为X=[X,Y]T的块，其时空相关预测中候选运动矢量d(·,·)的集合CS表示如下：

其中Vx,Vy是水平和垂直方向的单位向量；d(·,n)表示空间相关预测矢量；d( ·,n-1)表示时间相关预测矢量；k交替地取-1和1;US为更新矢量，从以下集合中依次选取：

由于实际中水平方向上的大运动比垂直方向的大运动发生概率更高，所以更新矢量中水平分量变化要比垂直分量大[5]。这样，候选的预测矢量共有6个，如图 2所示，包括：内插帧中Bi,j的左边、上边块和左上块(或右上块)；前一个内插帧中的Bi,j块，以及其右边和下边块。

图2 3-D RS时空预测候选矢量

式(1)中加上的惩罚值主要是用以区分不同类型候选矢量的优先权。为简化计算，本文在算法中对空间预测、时间预测、更新矢量预测的匹配误差加上的惩罚值分别由小到大设置为 3个不同的常数，也可以区分不同类型候选矢量的优先权，即：若在搜索的过程中出现了相等SBAD的候选矢量，则优先次序为空间预测、时间预测、更新矢量预测。这样，运动矢量最优估计值为

其中Penalty对于空间预测、时间预测、更新矢量预测分别取常数0,2,4。为了提高好的运动估计结果的传播，改变扫描顺序可能会有所帮助。有两种可行的机制：第1种是在“先左后下”扫描一遍之后，再反向扫描一遍；第 2种是“曲径”(meandering)扫描，即“从左至右”的扫描完一行之后，下一行“从右至左”的扫描；也可以同时采用这两种机制[8]。本文算法中用的是第1种方法，即第1次“先左后下”扫描，第2次再“先右后上”的反向扫描，如果搜索到更好的匹配则更新矢量估计值。需要指出的是，式(3)列举的只是“先左后下”的扫描顺序所代表的预测矢量，第2遍“先右后上”的扫描时，由于循序扫描并不是所有的空间预测矢量都能立即获得，空间预测矢量要选取那些已估计的块，可以通过将空间预测与时间预测块位置互换来获得。

2.2 多级运动矢量处理

当一个块包含多个不同运动对象时，无法得到正确描述运动的估计矢量。这时可以采用多级块匹配和多分辨率块匹配[8]，它们都是基于“由粗到细”的搜索思想，上一层的运动矢量可以传播到下一层，而下一层的估计值是对上一层估计结果的进一步细化。如图 3(a)所示，多级法在每一级上图像大小相同，而块的尺寸不同。当某些块不能得到好的匹配时将其块拆分成小块进行搜索，每一级可以使用不同的块匹配搜索算法，如3-D RS、钻石搜索(DS)、六边形搜索(HS)等。而多分辨率法如图3(b)所示，是在多尺度图像上进行搜索，块的大小保持不变，但每个层次上的图像分辨率不同。低分辨率层可以对高分辨率层下采样得到，或者构建图像金字塔。

图3 多级块匹配与多分辨率块匹配

(1)多级块匹配运动估计 本文运动估计算法采用多级法，以16×16块作为初始搜索，通过三级运动估计逐步得到4×4块的运动矢量。设块匹配预测误差门限阈值为threshold_SAD，处理步骤如下：

(a)首先用 16×16块匹配搜索，对大于threshold_SAD块进行标记；

(b)将16×16块拆分为8×8块继承上一级运动估计的结果，对上一步中标记的块重新搜索，更新估计值；对大于threshold_SAD/4的块再次标记；

(c)将8×8块拆分4×4块继承上一级运动估计的结果；对上一步中标记的块再次重新搜索，更新估计值；对大于threshold_SAD/16的块运动矢量由其周围的块运动矢量中值滤波的结果直接分配。

在本文设计的三级运动估计中，前两级是用上一节介绍的基于3-D RS的双向运动估计算法，第3级是HS算法。

由于传统的矢量中值滤波计算量较大，本文采用一种简化的中值滤波器[3]对运动估计得到的矢量进行处理。该算法是通过对邻域内初始的运动矢量的水平、垂直分量分别进行排序，并按大小赋予权值，找出总权值最小的一对矢量作为窗口内矢量的中值。该算法实际上是简化了矢量中值的甄选过程。在实验中，我们发现执行该算法过程中当总权值最小的矢量对不唯一时，可能甄选出的中值矢量并不是最佳的，最终使最后插值帧出现了“块效应”，如图 4(a)所示。因此，本文算法中在甄选中值矢量时对水平、垂直赋予 2组不同大小的权值：{4,3,2,1,0,1,2,3,4}和{20,15,10,5,0,5,10,15,20}，保证选出的最佳矢量对的唯一性。赋值的依据是先判断运动矢量水平分量和垂直分量的大小，较大者赋予第2组权值。甄选出的中值矢量'mv是否要替换原始窗口中心的mv，是通过两者之间的差异以及窗口的尺寸来决定的：

图4 Bowing序列第64帧内插结果

本文在三级运动估计的每一级完成之后进行上述的运动矢量中值滤波处理，“由粗到精”地逐步修正运动矢量，最终得到4×4的块运动矢量。最后利用式(7)的线性插值运动补偿重构中间帧。

3 实验结果与分析

实验数据选取了8个4:2:0的YUV格式的标准测试序列来验证本文算法的有效性，包括7个CIF序列：Football, Bowing, Susan, Carphone, News,Silent和Forman，以及1个HD序列Sunflower。其中，Football有大量快速运动，Bowing 和Silent背景静止，前景人物有复杂运动；Susan前景有大面积运动；Carphone与Forman类似，前景运动比较复杂，背景有微小晃动，而 Forman序列后半部分还存在背景的全局运动；News图像中间部分有复杂运动；Sunflower存在局部和全局同时运动。

实验中对每个序列时域下采样，跳过偶数帧后，采用本文提出的帧率上转换算法对相邻帧进行内插，重构出跳过的帧，恢复原始帧率。插帧客观质量通过内插帧与原始帧的PSNR值来衡量。为了评价本文算法的性能，对比了其他3种算法：方法 1是全搜索(Full Search, FS)双向运动估计结合传统的中值滤波方法；方法2是PMVFAST自适应双向运动估计算法[3]；方法3是抛物线运动模型自适应运动矢量选择算法[12]。在方法1中，双向运动估计的块大小为16×16，全搜索半径设置为8，对应到单向运动估计的搜索范围为±16。以上算法对不同测试序列的内插帧平均PSNR值如表1所示。

表1 各算法对测试序列内插帧平均PSNR(dB)

由表1可见，本文提出的算法对于大部分序列内插帧PSNR值，超过或者接近参考算法中的最优者。对于Carphone和Forman序列，本文算法PSNR值略低于全搜索而高于其他算法；对于 News序列方法3的PSNR值最高，本文算法次之；对于HD序列Sunflower, PMVFAST算法略优于本文算法与全搜索。

图5是内插帧主观质量的对比。由图5可以看出，本文算法得到的Carphone序列第72个内插帧，人的嘴巴、鼻子、头发部分更为清晰。

在计算复杂度方面，由于本文采取 3-D RS为核心的搜索算法，根据式(3)和式(4)，对于一个块的运动估计正向、反向两次扫描需搜索28个位置。据实验统计，第1级16×16块对于图像大部分区域已经能够取得比较好的匹配结果，拆分小块进行后面两级搜索只是少数块，所以即使算法中进行了三级运动估计，其计算开销也并无大幅增加。方法2的PMVFAST算法是以当前块空间相关的3个块的矢量作为预测矢量，根据预置的SAD阈值和计算出的矢量距离选择合适的模板再进行搜索。PMVFAST在搜索中为了减小计算量加入了提前终止策略，预先不能确定计算量。方法3的抛物线运动模型和自适应运动矢量选择使在已知初始运动矢量，利用抛物线对运动轨迹建模，修正时间不连续的运动矢量，得到正确的“双向运动矢量对”。由于该方法讨论的是已知初始的运动矢量之后的进一步处理，并未讨论初始运动矢量如何得到，所以在本文算法处理速度对比实验中方法3没有参与比较。

图5 Carphone序列第72帧内插帧主观质量对比

为了评估本文算法的效率，在 Intel Core i5-2500K (CPU@3.30 GHz), 3 GB内存的PC平台上分别运行方法 1、方法 2和本文算法，对于不同测试序列的平均处理时间如表2所示。在处理HD序列时，为了减小计算量，在实验中先对HD序列每一帧进行空间图像下采样。由表2可见，相对于CIF序列，HD序列由于其数据量更大，本文算法在处理速度方面的优势更加明显，计算时间明显少于其他两种算法，对于HD序列有足够的处理能力。

表2 各算法对测试序列插帧的平均处理时间(ms)

4 结论

本文提出了一种基于3-D RS多级运动估计的帧率上转换算法，采用了多级时空相关预测的双向运动估计和运动矢量校正。由于3-D RS搜索点少，且矢量校正部分采用了简化的中值滤波器，所以该方法计算量小，易于实现。文中先介绍了该方法原理和处理流程，然后通过实验对比了其他3种方法来评价本文算法的性能，验证了算法的有效性。实验结果表明，本文算法获得的内插帧客观指标和主观效果均令人满意，在保证内插帧质量的同时，算法复杂度低，大幅度提高了处理速度，对于高清序列插帧速度可以达到15 fps以上，适用于高清甚至更高分辨率的视频帧率上转换的实时处理。

[1]Huang A M and Nguyen T Q. A multistage motion vector processing method for motion-compensated frame interpolation[J].IEEE Transactions on Image Processing,2008, 17(5): 694-707.

[2]Zhai J, Yu K, Li J,et al.. A low complexity motion compensated frame interpolation method[C]. International Symposium on Circuits and Systems, Kobe, Japan, 2005, (5):4927-4930.

[3]李莉, 侯正信. 一种自适应帧频提升算法研究[J]. 计算机应用研究, 2009, 26(4): 1575-1577.

Li Li and Hou Zheng-xin. Research on adaptive algorithm for frame rate up conversion[J].Application Research of Computers, 2009, 26(4): 1575-1577.

[4]Haan G D, Biezen P W, Huijgen H,et al.. True-motion estimation with 3-D recursive search block matching [J].IEEE Transactions on Circuits and Systems for Video Technology, 1993, 3(5): 368-379.

[5]Choi B T, Lee S H, and Ko S J. New frame rate up-conversion using bi-directional motion estimation[J].IEEE Transactions on Consumer Electronics, 2000, 46(3): 603-609.

[6]Chio B D, Han J W,et al.. Motion-compensated frame interpolation using bilateral motion estimation and adaptive overlapped block motion compensation[J].IEEE Transactions on Circuits and Systems for Video Technology,2007, 17(4): 407-415.

[7]侯正信, 李娜, 张丽晓, 等. 帧率提升中的三维递归搜索块匹配改进算法[J]. 计算机工程与应用, 2011, 17(33): 169-171.

Hou Zheng-xin, Li Na, Zhang Li-xiao,et al.. Improved 3-D recursive search block matching algorithm in frame rate up conversion[J].Computer Engineering and Applications, 2011,17(33): 169-171.

[8]Heinrich A, Bartel C,et al.. Optimization of hierarchical 3DRS motion estimators for picture rate conversion[J].IEEE Journal of Selected Topics in Signal Processing, 2011, 5(2):263-264.

[9]Wang D, Zhang L, and Vincent A. Motion-compensated frame rate up-conversion part I: fast multi-frame motion estimation[J].IEEE Transactions on Broadcasting, 2010,56(2): 133-141.

[10]李淼, 李迅波, 魏海龙. 基于运动矢量场预测的自适应多模板块运动估计算法[J]. 电子测量技术, 2010, 33(10): 36-39.

Li Miao, Li Xun-bo, and Wei Hai-long. Multi-pattern block motion estimation search algorithm based on predictive motion vector field[J].Electronic Measurement Technology,2010, 33(10): 36-39.

[11]张少娴, 俞琼. 基于时空相关性预测的运动估计的优化[J]. 计算机技术与发展, 2010, 20(1): 104-107.

Zhang Shao-xian and Yu Qiong. An optimization method for spatiotemporal predictive motion estimation[J].Computer Technology and Development, 2010, 20(1): 104-107.

[12]Choi K S and Hwang M C. Motion-compensated frame interpolation using a parabolic motion model and adaptive motion vector selection[J].ETRI Journal, 2011, 33(2):295-298.