一种改进的三维递归搜索帧率上转换算法

姜肇海，胡园园，司丹丹，干宗良

(南京邮电大学江苏省图像处理与图像通信重点实验室，江苏南京210003)

一种改进的三维递归搜索帧率上转换算法

姜肇海，胡园园，司丹丹，干宗良

(南京邮电大学江苏省图像处理与图像通信重点实验室，江苏南京210003)

提出了一种改进的三维递归搜索(3－Dimension Recursive Search，3DRS)帧率上转换算法。相较于3DRS算法，在3个方面提出改进:首先，调整候选运动矢量的选择，充分利用运动失量的空间相关性;其次，增加一次逆序运动估计，加速运动失量收敛;最后，提出一种新的匹配准则以进一步提高运动估计的准确性。实验结果表明，该算法有效提高了运动估计的准确性，所得结果在主客观均取得较好的效果。

三维递归搜索;运动估计;帧率上转换

帧率上转换(Frame Rate Up－Conversion，FRUC)也称为帧频提升，主要是通过在相邻两帧图像中间估计内插帧，实现视频帧率的提高。帧率上转换算法最早起源于20世纪80年代，用于解决帧率为24/25 Hz的电影片源转换为50/60 Hz以在普通电视中播放的问题。在视频通信中，帧率上转换技术可以有效提高系统的图像传输质量。例如，当通信网络波动，或者带宽受限时，发送端可以通过减低帧频来降低传输速率，在接收端可以通过帧率上转换来估计丢弃的图像帧，这样可以有效解决低帧率视频导致的视觉上的停滞感和跳跃感。

目前帧率上转换中广泛采用考虑视频中物体运动信息的运动补偿内插算法，即运动补偿帧插方法(Motion Compensation Frame Interpolation，MCFI)，它可以有效减轻非运动补偿内插算法引起的视频模糊和抖动等现象［1］。运动补偿内插算法主要包括2步:运动估计和运动补偿。由于运动估计的准确性直接影响内插帧的效果，因此很多算法都致力于得到更加真实的运动矢量场。Haan等［2］提出了一种三维递归搜索(3－Dimension Recursive Search，3DRS)块匹配运动估计算法。该算法主要基于连续视频序列中帧与帧之间不存在运动突变和同一物体内部运动场保持一致的观点，利用当前宏块的时间和空间相邻块运动矢量估计当前块的运动矢量。Wang等［3］在此基础上提出了仅利用3个时空候选矢量的运动估计算法，它降低了运动估计所需的复杂度。虽然这两种算法得到的运动矢量场有很好的平滑性，但由于更新矢量范围的限制，它们都不能保证运动矢量快速收敛，而且存在错误矢量传递的现象。

本文针对3DRS算法在帧率上转换中存在的问题，对其进行了改进。首先，通过调整候选矢量选取，舍弃可能引入错误运动矢量的时间预测矢量，充分利用空间相邻块的运动矢量。其次，利用一次逆序运动估计加速运动矢量收敛。最后，提出一种新的匹配准则，匹配误差的计算考虑到噪声的影响，同时通过引入高频信息，增加了对图像边缘运动估计的准确性。实验结果表明，本文算法处理效果较好。

1 3DRS算法

3DRS算法假设图像中物体尺寸比匹配块尺寸大，且物体具有惯性。这两个假设保证了图像中某块的最佳位移矢量可以从其时空相邻块的运动矢量中找到，从而没有必要搜索所有可能的位移矢量，相比于要搜索整个区域的普通块匹配算法而言，大大减少了计算复杂度。

取当前帧图像的前一帧为参考帧，则当前块和时空候选块的相对位置如图1所示。

假设当前块为B(X)，其中X=(Xx，Xy)，代表当前块左上角像素点的位置。图像块尺寸为M×N，则

图1 当前块与空间、时间候选块的相对位置

当前帧中块SD和参考帧中块TD的运动矢量构成时空预测集CSa(X，n)

Sb和Tb的运动矢量构成时空预测集CSb(X，n)

CSa(X，n)和CSb(X，n)构成当前块B(X)运动矢量候选集

使匹配误差SAD最小的候选矢量即为当前块的运动矢量

式中:fn(x)，fn″(x－D)分别代表当前帧和参考帧在x，x－D处的灰度值。

2 改进的3DRS算法

2.1 候选矢量的改变

3DRS算法仅利用2个空间相邻块和2个时间候选块的运动矢量进行运动估计，提高了运动矢量场的平滑性，在帧率上转换中得到了广泛应用［4－5］。但当当前块运动相对于匹配块尺寸来说较小且当前块所属运动物体相对于匹配块并不太大时，时间候选矢量由于距离当前块较远，因此它的运动和当前块的相关性可能并不大。此外，对于场景切换的情况，时间候选矢量预测效果也不好。为了解决上述问题，本文算法改变候选失量的选择。如图2所示，舍弃时间候选矢量，同时增加空间候选矢量个数，取当前块左方以及上方一共4个相邻块的运动矢量及其各自的更新值构成候选矢量集，充分利用了运动的空间相关性。

图2 改进的3DRS运动矢量候选块相对位置

2.2 增加逆序运动估计

由于3DRS算法中运动矢量更新值较小，因此一旦候选块与当前块的运动相差较大，将会导致不能正确得到当前块的运动矢量。虽然可以通过迭代解决这一问题，但由于3DRS算法采用固定的扫描顺序、候选块，对于存在剧烈运动的块需要迭代多次才能收敛到正确的值，而且迭代过程中可能由于某次找到的错误运动矢量导致之后迭代得到的运动矢量错误收敛。由于3DRS算法是递归搜索，位于当前块之后的块经过多次递归可能已经得到正确的运动矢量。因此，本算法通过一次候选块取相反位置的逆序估计修正之前可能错误的运动矢量。即从图像右下角，按照从右向左、从下向上的方向重新进行一次运动估计，同时构成候选失量的候选块也取相反位置，如图3所示，即选择当前块右方的1个相邻块以及下方的3个相邻块作为候选块。

2.3 匹配误差的更新

3DRS算法利用式(6)的SAD作为匹配准则寻找最佳匹配块，由于图像不可避免地含有噪声，因此SAD最小并不一定对应真实的运动矢量。为了尽可能找到真实的运动矢量，本文算法对匹配准则做出调整。匹配误差计算中忽略人眼不敏感的灰度值在3以下的匹配误差，同时给予两像素间匹配误差大于25的点较大权值，这样就减轻了噪声对运动矢量准确度的影响。此外，由于图像边缘对内插图像质量的影响较大，本文算法通过对原始图像进行高通滤波提取出图像的边缘信息，在匹配误差计算中引入高频项，提高了图像边缘处运动估计的可靠度。调整后的匹配准则为

图3 逆向估计候选块相对位置

式中:ffn，ffn″分别代表当前帧和参考帧的高频信息。

3 实验结果

实验选取了4组帧率为30 Hz的标准CIF(352×288)格式序列:Bus，City，Foreman，Paris。这些序列包含不同的运动，例如Bus包含复杂纹理，Foreman前景运动丰富而背景有微小晃动。在所有实验中，匹配块尺寸都设为8×8。为了验证本文算法效果，跳过测试序列的偶数帧，然后分别利用本文算法、文献［2］的3DRS算法、文献［8］的TF算法和文献［9］的HD算法重构偶数帧，对下采样后的测试序列进行帧率上转换，并对处理结果进行比较。

表1、表2分别给出了各测试序列利用不同算法得到的前50内插帧的平均PSNR、FSIM值。从表中可以看出，对各测试序列，采用本文算法得到的内插帧的平均PSNR、FSIM值相对于另外3种算法，均有不同程度的提高。

图4给出了Foreman序列中原始图像及利用各种帧率上转换算法得到的相应内插图像。其中图4a是原始的中间帧，图4b、图4c、图4d、图4e分别是利用3DRS算法、TF算法、HD算法以及本文算法仿真得到的内插图像。从图中可以看出，3DRS、HD得到的内插图像都有明显的块效应，这是由于错误的运动估计引起的，TF算法得到的内插图像由于过度平滑，在嘴部和帽子的顶部都存在一定的模糊。本文算法得到的内插图像比其他3种算法得到的结果更加清晰，这是由于本文算法利用一次逆序估计，修正了之前错误的运动矢量。

表1 不同序列各种算法下的PSNR

表2 不同序列各种算法下的FSIM

图4 不同算法内插出的Foreman序列

图5是利用不同算法得到的City内插帧，可以看出，本文算法得到的内插图像不仅在纹理较多的区域处得到准确的运动矢量，而且在底部建筑物存在对称图案的区域同样得到比较好的效果，这是由于本文算法的匹配准则中引入了图像的高频信息，而且考虑了人眼对噪声的敏感程度。

图5 不同算法内插出的City序列

4 小结

针对3DRS算法在帧率上转换中存在的问题，本文提出了一种改进算法。首先通过调整候选矢量的选择，排除了可能引入错误运动矢量的时间候选矢量，同时通过4个空间候选块，充分利用了运动矢量的空间相关性。其次，增加了一次逆序运动估计，加速运动矢量正确收敛。此外，本文提出了一种新的匹配准则，匹配准则考虑了噪声对运动估计的影响，同时通过引入图像高频成分提高了运动估计在边缘处的准确性。文章对具有不同特点的视频序列进行处理，并与其他算法在主、客观两个方面进行对比。实验结果表明，本文算法得到的内插图像边缘更加清晰，有效地减小了运动模糊以及块效应，同时PSNR， FSIM也均有不同程度的提高。

［1］YANG Y，TUNG Y，WU J.Quality enhancement of frame rate up-converted video by adaptive frame skip and reliable motion extraction［J］. IEEE Trans.Circuits and Systems for Video Technology，2007，17(22): 1700-1713.

［2］HAAN G，BIEZEN P，HUIJGEN H，et al.True-motion estimation with 3-d recursive search blockmatching［J］.IEEE Trans.Circuits and Systems for Video Technology，1993，3(5):368-379.

［3］WANG J，WANG D，ZHANGW.Temporal compensatedmotion estimation with simple block-based prediction［J］.IEEE Trans.Broadcasting，2003，49(2):241-248.

［4］JEON B，LEE G，LEE S，et al.Coarse-to-fine frame interpolation for frame rate up-conversion using pyramid structure［J］.IEEE Trans.Consumer Electronics，2003，49(3)499-508.

［5］LEE G，JEON B，PARK R，et al.Hierarchicalmotion compensated frame rate up-conversion based on the gaussian/laplacian pyramid［C］//Proc. IEEE International Conference on Consumer Electronics.［S.l.］:IEEE Press，2003:350-351.

［6］WANG C，ZHANG L，HE Y，etal.Frame rate up-conversion using trilateral filtering［J］.IEEE Trans.Circuits and Systems for Video Technology，2010，20(6):886-893.

［7］HAN R，MEN A.Frame rate up-conversion for high-definition video applications［J］.IEEE Trans.Consumer Electronics，2013，59(1):229-236.

［8］KANG S，YOO S，KIM Y.Frame rate up-conversion using trilateral filtering［J］.IEEE Trans.Circuits and Systems for Video Technology，2010，20(6):886-893.

［9］HAN R，MEN A.Frame rate up-conversion for high-definition video applications［J］.IEEE Trans.Consumer Electronics，2013，59(1): 229-236.

Frame Rate Up－conversion Algorithm Based on Im proved 3D Recursive Search

JIANG Zhaohai，HU Yuanyuan，SIDandan，GAN Zongliang
(Jiangsu Provincial Key Lab.of Image Processing and Image Communication，Nanjing University of Posts and Telecommunications，Nanjing 210003，China)

A frame rate up－conversion algorithm based on improved 3D Recursive Search(3DRS)is presented.Compared with 3DRS algorithm，improvements from the following three aspectsare proposed:firstly，adjust the selection ofmotion vector candidates tomake fulluse ofmotion vector’s spatial correlation;then，add a reversemotion estimation to acceleratemotion vector’s convergence;finally，a new matching criterion is put forward so as to further improve the accuracy ofmotion estimation.Experimental results show that the algorithm in this paper effectively improves the accuracy ofmotion estimation and the results achieve better effects both subjectively and objectively.

3DRS;motion estimation;frame rate up－conversion

TN949.198

A

�� 雯

2013－08－10

【本文献信息】姜肇海，胡园园，司丹丹，等.一种改进的三维递归搜索帧率上转换算法［J］.电视技术，2014，38(13).