基于多特征匹配的双向运动估计帧率提升算法

薛春玲，李 然，朱秀昌

(1.黄河科技学院，河南 郑州 450063；2.南京邮电大学 江苏省图像处理与图像通信重点实验室，江苏 南京 210003)

基于多特征匹配的双向运动估计帧率提升算法

薛春玲1，李 然2，朱秀昌2

(1.黄河科技学院，河南 郑州 450063；2.南京邮电大学 江苏省图像处理与图像通信重点实验室，江苏 南京 210003)

视频帧纹理区域含有的大量周期重复模式常导致双向运动估计发生视频块的错匹配，从而导致帧率提升算法重建的内插视频质量衰退。为了克服该问题，提出提取视频帧的多个特征加入到块匹配中，以降低错匹配发生的可能性。由于视频天然具有彩色信息，因此色差分量首先被加入到块匹配中。另外，人眼对图像边缘较敏感，因此，由简单的Sobel算子计算出的梯度被使用去反应边缘特征并融入至块匹配。多特征匹配尽管可有效地提高运动估计精度，但也引入了较高的计算复杂度。为了减少计算复杂度，一个特殊模板被设计去将多特征合并到单平面上，那么，只需进行一次块匹配运算就可完成多特征的匹配，在节省计算复杂度的同时也提高了运动估计精度。仿真实验表明，该算法以较低的计算复杂度获得了良好的内插帧主客观质量。

图像处理；帧率提升算法；双向运动估计；多特征匹配

帧率提升(Frame Rate Up-conversion，FRUC)具有广泛的应用前景，例如，低比特率视频通信和液晶显示(LCD)运动去模糊等[1]。简单的帧率提升算法通过帧复制和帧平均实现，由于其忽略了帧间的运动信息，经常会导致物体的运动模糊和画面抖动。考虑帧间运动的运动补偿帧率提升(Motion-Compensated Frame Rate Up-conversion，MC-FRUC)可有效地提高内插帧质量，因此获得了广泛关注。

运动补偿帧率提升由运动估计(Motion Estimation，ME)和运动补偿内插(Motion Compensated Interpolation，MCI)两部分组成。运动估计首先计算出帧间的运动矢量场，接着运动补偿内插根据运动矢量场利用前后参考帧估计出内插帧[2]。由于经常出现有多个或无运动轨迹通过内插帧中的某些块，因此导致空洞和重叠现象，使内插帧质量衰退。为了解决上述问题，双向运动估计(Bidirectional Motion Estimation，BME)被提出利用运动对称性假设为内插帧各块分配唯一运动矢量，而解决了空洞和重叠问题[3]。但是由于视频帧的纹理区域常含有大量的周期重复模式，而双向运动估计中内插帧的缺失会造成在该区域内块的错匹配，因此，文献[4]通过计算相邻块间的重叠块运动增加运动矢量场密度，尽最大可能逼近真实运动矢量，文献[5]则通过在块匹配准则中增加可反映当前运动单向可靠度的正则化项来提高运动估计精度，上述方法尽管均能够提升内插帧质量，但却引入了较高的计算复杂度。

为了能够以较低计算复杂度克服纹理区域的错匹配问题，本文提出提取视频帧多个特征进行块匹配以提高双向运动估计精度。视频帧具有亮度分量Y、色差分量U和V，利用这些分量进行块匹配，可更准确地追踪物体运动轨迹。又由于人眼对物体边缘特征较敏感，通过提取视频帧的边缘图，并将与边缘特征相关的正则化项融入块匹配准则，可进一步地提高运动估计精度。然而，多特征共同进行匹配，势必会成倍地增加运算成本，为了避免高计算复杂度，本文算法设计特殊模板将多个特征合并到单平面上，那么，只需进行一次块匹配便可完成多特征匹配，从而以较低计算复杂度实现了高质量视频帧内插。

1 本文算法

传统的双向运动估计算法使用绝对差和(Sum of Absolute Differences，SAD)在既定的搜索范围内寻找最相似块。传统SAD仅使用了亮度分量，然而对于视频信号除了具有亮度分量外，仍包含色差分量，例如，4∶2∶0的YUV视频取样格式存在色差分量U和V，但它们的采样点个数在水平和垂直方向都是亮度Y的一半。由于相邻像素间的色差分量变化经常小于亮度分量，加之彩色亚采样导致彩色信息缺失，因此，在传统视频压缩领域中，基于SAD的运动估计被广泛使用。

对于帧率提升算法，高质量视频内插依赖于准确的运动矢量。忽略了彩色信息的SAD往往并不能有效地追踪物体运动，尤其是对于纹理细节丰富的视频序列。在视频的纹理区域，尽管存在大量的周期重复模式，但这些模式仅在亮度上具有较大相似性，而彩色特征往往具有很大差别。如图1所示(原图为彩色)，图1a中的方框为Flower视频序列第37帧的纹理区域，其内容是颜色各异的花朵与绿叶，由图1b可观察到通过颜色很容易区分纹理细节，而通过图1c显示的亮度图却不易区分纹理细节，尤其是观察不出黄花与绿叶的区别。

图1 视频纹理区域周期重复模式的彩色与亮度图视觉对比

因此，在SAD中加入彩色特征的匹配，可有效地避免SAD在纹理区域的错匹配。那么，融入彩色特征的SAD可按式(1)计算

(1)

式中：v是当前块Bt的候选运动矢量；p为在Bt内的像素位置；Yt-1(·)，Ut-1(·)和Vt-1(·)是前参考帧ft-1的亮度和色差分量；Yt+1(·)，Ut+1(·)和Vt+1(·)是后参考帧ft+1的亮度和色差分量。考虑到相邻帧像素间色差分量的差值常小于亮度分量的差值，因此，U和V分量的SAD值被乘以平衡因子W以使Y，U和V三分量的差值对式(1)具有均等的贡献。对于4∶2∶0的YUV视频，色差分量U和V的取样个数仅是Y分量的1/4，为了保证任一候选匹配块和当前块均有相同像素位置的色差分量，因此在计算式(1)之前首先使用双立方插值算法[6]放大U和V分量至Y分量的尺寸。

彩色特征虽然能够缓解纹理区域错匹配带来的不利影响，但其无法准确地描述物体的边缘特征。由于边缘包含了准确块匹配的显著信息，且在边缘区域的匹配误差与视觉理解是十分相似的，所以在SAD中加入与边缘特征相关的项也可有效地提升运动估计精度。梯度可反映图像边缘，且计算图像梯度的方法较多，但为了不引入过多的计算复杂度，简单的Sobel算子[7]被用来计算视频帧梯度，如图2所示，通过Sobel算子计算出的梯度图(图2b所示)可清晰地展现原始帧的边缘特征，因此其可被使用描述边缘特征，并按式(2)融入到基于SAD的块匹配准则

(2)

式中：ΔYt-1和ΔYt+1为由Sobel算子计算的前后参考帧ft-1和ft+1的梯度图。由于梯度匹配误差与亮度匹配误差具有一定差别，因此需要加入平衡因子α去权衡各项对式(2)的影响。

图2 Sobel算子提取的视频帧梯度图

使用式(2)进行块匹配，虽然可综合不同特征的匹配误差，但也引入了较高的计算复杂度。为了以较低的计算复杂度完成多个特征的匹配，本文算法将亮度特征、彩色特征和边缘特征通过特殊模板融合至单平面上，该特殊模板如图3所示。

图3 融合多特征的特殊模板

图3中Y代表亮度像素点，G代表梯度像素点，U和V代表色差像素点，由图3可看出，4种特征点均分了每个匹配块的所有像素，且均匀地分布在整个匹配块平面上，这相当于将当前块分成了同样尺寸的4层，每一层均是原始匹配块尺寸的1/4。由于视频具有层间相似性(图像金字塔)，即下采样获得的图像仍会保持与原始特征相似的特征[8]，所以通过该特殊模板融合而成的多特征块仍会近似保持原始匹配块的特征。那么，通过使用所提出的特殊模板，式(2)可被改进为

(3)

(4)

式中：BtY，BtU，BtV和BtG分别是当前块Bt的Y，U，V和G的像素点集合。通过使用式(3)进行块匹配运算，其计算复杂度与传统SAD相同，但却兼顾了多个特征的匹配，因此可在较低的计算复杂度下提高运动估计的精度。对于平衡因子W和α的选取，若干真实视频序列在不同的W和α取值下被测试，图4显示了内插帧的平均峰值信噪比随W和α变化的曲线，可看出当α固定为0.1时，最大的PSNR值出现在W= 8附近，当W固定为8时，最大的PSNR值出现在α= 0.1附近，因此，在本文中W和α分别取8和0.1。

图4 随W和α变化的PSNR曲线

上述改进的块匹配准则将被使用在双向运动估计中计算当前帧的运动矢量场，为了进一步的加快运动估计速度，三维递归搜索(3-D Recursive Search，3DRS)[9]被使用在双向运动估计中。得到当前帧的运动矢量场后，再使用重叠块运动补偿(Overlapped Block Motion Compensated，OBMC)[10]计算出最后的内插帧。

2 实验结果

实验数据选取了4个4∶2∶0的YUV格式的CIF标准测试序列来验证本文算法的有效性，它们包括：Foreman，Mobile，Flower和Football，其中Foreman前景背景分明且背景有轻微晃动，Mobile包含物体缩放和平移、旋转等复杂运动，Flower包含丰富的彩色纹理细节，Football含有大量快速运动。为了测试内插帧的主客观质量，每个测试序列的前50个偶帧被去除，并再次利用各种帧率提升算法从剩余51个奇帧中重建。插帧客观质量通过内插帧和原始帧的PSNR衡量。为了评比本文算法的性能，对比了其他3种算法：文献[4]提出的EBME算法(块大小为8×8，全搜索半径为4)；文献[5]提出的Dual ME算法(块大小为8×8，全搜索半径为16)；文献[9]提出的双向3DRS运动估计法(分块大小为8×8)。本文算法的分块尺寸为8×8，且其与Dual ME算法和双向3DRS算法均使用重叠尺寸为4的OBMC算法计算出最后的内插帧，对于EBME算法则使用文献[4]提出的补偿方法。

由表1可见，本文算法除Foreman序列外均超过了对比算法的最优者，尤其是对于包含复杂和快速运动的序列。对于Foreman序列，本文算法比双向3DRS算法略低0.08 dB，这是因为Foreman序列具有较清晰的边缘且纹理细节简单，这使得传统SAD就可保证高精度的运动估计。对于具有复杂和快速运动的Mobile和Football序列，本文算法分别超出对比算法中最优者2.00 dB和0.46 dB，这表明了本文算法可有效地追踪复杂快速运动。对于色彩丰富的Flower序列，本文算法也超出了双向3DRS算法0.39 dB，这表明本文算法可较好地区分彩色纹理细节。对于计算复杂度，表1也显示了在Intel Core i5 3.20 GHz， 8 Gbyte内存PC平台上的平均内插时间，可看出本文算法内插出一帧平均需要0.42 s， 其远低于EBME算法。对于Dual ME算法，本文算法平均缩短了0.27 s，且获得了4.49 dB的PSNR增益。由于本文算法与双向3DRS算法的不同仅在于：双向3DRS算法使用了传统SAD；而本文算法使用了基于多特征的SAD，那么，本文算法尽管在块匹配上与双向3DRS算法有相同的计算复杂度，但由于需要一定的计算量提取边缘特征和内插U，V分量，这造成了其平均内插时间高于双向3DRS算法0.14 s，但相比于双向3DRS算法，其可有效地改善内插帧质量，平均获得了0.86 dB的PSNR增益。

表1 不同序列下各算法的平均PSNR和平均内插时间

图5显示了不同算法重建Flower序列第90帧的主观视觉质量对比。首先可看到在路灯附近(左边方框圈定)，Dual ME算法和双向3DRS算法均出现了不同程度的模糊与变形，而本文算法能够更好地保护路灯的边缘特征，而对于路旁鲜花区域(右边方框圈定)，对比算法均无法保证清晰的纹理细节，产生了一定程度的模糊，尤其是对于双向3DRS算法，但本文算法很好地复原了纹理细节，获得了更好的主观视觉质量。

图6显示了不同算法重建Foreman序列第72帧的主观视觉质量对比。对于双眼和鼻子区域(方框圈定)，EBME算法和Dual ME算法均出现了不同程度的块效应。对于双向3DRS算法，其内插帧的左眼角纹理细节丢失，造成了一定的视觉质量衰退。本文算法能够有效地抑制块效应且可保护纹理细节，获得了良好的主观视觉质量。

图5 Flower序列在不同算法下的主观视觉效果(第90帧)

图6 Foreman序列在不同算法下的主观视觉效果(第72帧)

3 小结

本文提出了可融合多个特征的块匹配方法以在较低的计算复杂度前提下有效改善双向运动估计的错匹配问题。由于视频天然具有彩色信息，因此色差分量可作为一种特征融入到块匹配过程。人眼往往对图像边缘较敏感，边缘区域的匹配误差可有效地反映视觉差别，因此，本文利用简单的Sobel算子提取视频帧的梯度信息，将可反映边缘特征的梯度项加入块匹配过程。尽管多特征匹配的融入可有效提高运动估计精度，但也引入了较高的计算复杂度。为了减少多特征匹配引入的计算复杂度，本文设计了特殊模板将多个特征合并到单平面上，如此就可以只进行一次块匹配就完成多特征的匹配，实现了在低计算复杂度下运动估计精度的提高。仿真实验也表明了本文算法可在较短的时间内完成内插帧重建，且可有效地改善视频的主客观质量。

[1]HWANG J，CHOI Y，CHOE Y. Frame rate up-conversion technique using hardware-efficient motion estimator architecture for motion blur reduction for TFT-LCD[J]. IEICE Trans. Electronic，2011(5)：896-904.

[2]LIU H，XIN R，ZHAO D，et al. Multiple hypotheses bayesian frame rate up-conversion by adaptive fusion of motion-compensated interpolations[J]. IEEE Trans. Circuits System Video Technology，2012，22(8)：1188-1198.

[3]CHOI B，LEE S，KO S. New frame rate up-conversion using bi-directional motion estimation[J]. IEEE Trans. Consume Electronic，2000，46(3)：603-609.

[4]KANG S，CHO K，KIM Y. Motion compensated frame rate up-conversion using extended bilateral motion estimation[J]. IEEE Trans. Consume Electronic，2007，53(4)：1759-1767.

[5]KANG S，YOO S，KIM Y. Dual motion estimation for frame rate up-conversion[J]. IEEE Trans. Circuits System Video Technology，2010，20(12)：1909-1914.

[6]KEYS R. Cubic convolution interpolation for digital image processing[J]. IEEE Trans. Acoustical Speech Signal Processing，1981(6)：1153-1160.

[7]朱秀昌，刘峰，胡栋.数字图像处理与图像通信[M].北京：北京邮电大学出版社，2002.

[8]GONZALEZ R C，WOODS R E. Digital Image Processing[M]. 3rd ed. Upper Saddle River，NJ：Prentice Hall，2008.

[9]徐洪峰，孙为平，丁玉琴，等. 一种改进的三维递归搜索视频去隔行算法[J].计算机应用，2007，27(5)：1153-1155.

[10]ORCHARD M，SULLIVAN C. Overlapped block motion compensation：an estimation-theoretic approach[J]. IEEE Trans. Image Processing，1994，3(9)：693-699.

薛春玲(1983— )，女，讲师，主要研究方向为图像和视频编码；

李 然(1988— )，博士生，主要研究方向为图像处理与多媒体通信；

朱秀昌(1947— )，教授，博士生导师，长期从事图像通信方面的科研和教学工作。

责任编辑：时 雯

Multiple Features Matching Based Bidirectional Motion Estimation for Frame Rate Up-conversion

XUE Chunling1，LI Ran2，ZHU Xiuchang2

(1.HuangheScience&TechnologyCollege，Zhengzhou450063，China；2.JiangsuProvinceKeyLabonImageProcessing&ImageCommunication，NanjingUniversityofPostsandTelecommunications，
Nanjing210003，China)

It usually results in the quality degradation of the interpolated frame in frame rate up-conversion that lots of periodical repetitive patterns in the texture region of video frame lead to the mismatch of video blocks for bidirectional motion estimation. To overcome this problem，this paper proposes to extract multiple features of video frame and add them into the process of block-matching，and thus the probability of appearing mismatch is lowered. Since the video sequence naturally contains color information，the chrominance component is firstly mixed into the block-matching. Besides，human's eyes is obviously sensitive to image edges，and therefore the gradient component，which is computed by the simple Sobel operator，is used to reveal the edge feature and mixed into the block-matching. Although the multiple features matching can effectively improve the accuracy of motion estimation，it introduces also the higher computational complexity. To reduce the computational complexity of multiple features matching，a special template is designed to combine multiple features into a single panel，thereby completing multiple features matching by performing only a block-matching operation，which improve the accuracy of motion estimation while guaranteeing a low computational complexity. Experimental results show that the proposed algorithm can improve the both subjective and objective quality of the interpolated frame with a low computational complexity.

image processing；frame rate up-conversion；bidirectional motion estimation；multiple features matching

国家自然科学基金项目(61071091)；“通信工程”江苏省高校优势学科建设工程项目；江苏省研究生创新项目(CXZZ12_0466)；郑州市嵌入式系统应用技术重点实验室项目(121PYFZX177)；郑州市重点建设实验室项目(郑教高[2013]109号)

TN911.73

A

10.16280/j.videoe.2015.01.005

2014-02-20

【本文献信息】薛春玲，李然，朱秀昌.基于多特征匹配的双向运动估计帧率提升算法[J].电视技术,2015，39(1).