基于运动矢量空间相关性的H.264分像素运动估计

曾接贤，郑大芳，符 祥

南昌航空大学 软件学院，南昌 330063

基于运动矢量空间相关性的H.264分像素运动估计

曾接贤，郑大芳，符 祥

南昌航空大学 软件学院，南昌 330063

1 引言

运动估计是视频压缩编码中的关键技术之一，它可消除视频信号的时间冗余，它的效率直接影响到编码速度，压缩率和视频解码后的图像质量。H.264中由于采用分层设计、多帧参论、多模式运动估计、1/4像素精度运动估计等技术，提高了预测精度，降低了匹配误差，从而获得比其他标准更好的压缩性能。但是，它的计算复杂度却大幅度增加。因此，研究高效快速的运动估计算法具有重要意义。

典型的运动估计包括整像素运动估计和分像素运动估计。整像素运动估计由于其搜索点数多而备受关注，许多快速运动估计算法致力于整像素运动估计计算复杂度降低的研究。随着整像素运动估计快速算法的发展，整像素搜索点数[1]可以减少到10个以下，这使得分像素运动估计的计算量高于或相当于整像素运动估计的计算量。因此，分像素运动估计快速算法的发展对于整个运动估计的计算量的减少变得尤为重要。目前分像素运动估计快速算法主要有三类：一类是基于运动补偿预测误差模型的算法，如H.264/AVC中快速1/4像素运动估计算法[2]和具有低计算复杂度的基于模型的1/4像素运动估计[3]等，这类算法根据最优整像素点的一个整像素运动领域的数学模型建立误差模型，避免了运算量很大的分像素内插运算和分像素搜索过程，但算法的匹配精度较低。另一类是采用提前终止搜索策略的算法，如改进的面向H.264/AVC的快速运动估计策略[4]，这类算法通过阈值判定，提前结束分像素搜索，但存在阈值选取或计算问题——阈值过大，搜索准确度就会降低，阈值过小，搜索速度很难有明显提高。还有一类是基于图像平坦区域预测的算法，这类算法避免了前两类算法的缺陷，如针对H.264的基于平坦区域预测的分像素运动估计[5]。该算法采用中值预测运动矢量和模式1的运动矢量，通过预测整像素匹配宏块，从而跳过部分宏块的分像素搜索过程，达到提高搜索速度的目的，但对于未预测为整像素匹配宏块的宏块，其中可能含有整像素运动块，对这部分整像素运动块进行分像素搜索就是浪费。

针对文献[5]的不足，本文提出了一种基于运动矢量空间相关性的H.264分像素运动估计算法，简称MVSCBS算法。该算法充分利用运动矢量空间相关性来预测整像素运动块，并对整像素运动块只进行整像素搜索，不进行分像素搜索。实验结果表明，本文算法结合全分像素搜索算法使用，基本保持了搜索精度的同时，可比文献[5]中的算法减少10%左右的分像素搜索点。

2 H.264中的分像素搜索算法

H.264中采纳了两种分像素搜索算法：分像素全搜索（FFPS）和基于中心的快速分像素搜索（CBFPS）[6]。

2.1 分像素全搜索

分像素全搜索算法如图1所示。该算法首先计算最佳整像素位置周围的8个1/2像素位置（如图1所示中的空心方框“□”处），找到最佳1/2像素位置（如图1所示中的实心方框“■”处）；然后计算最佳1/2像素位置周围的8个1/4像素位置（如图1所示中的空心三角“△”处），找到最佳1/4像素位置（如图1所示中的实心三角“▲”处），作为分像素搜索的最佳运动矢量。由于分像素搜索在计算匹配误差值时增加了Hadamard变换，所以最佳整像素位置的匹配误差值在分像素运动估计时要重新计算。分像素全搜索算法总共需要搜索17个点，其中包括8个1/2像素位置，8个1/4像素位置和1个最优整像素位置。

图1 分像素全搜索

2.2 基于中心的快速分像素搜索

基于中心的快速分像素搜索算法如图2所示。该算法首先根据式（1）计算(pred_x，pred_y)，比较该点处的匹配误差值和最佳整像素位置的匹配误差值的大小，选匹配误差值较小的位置作为搜索起始点；然后再循环使用小菱形模板进行搜索，直到最小匹配误差点为搜索模板的中心时停止；最后选取最小匹配误差点为最终的分像素匹配点。

其中，fracpredmv=(pred_x，pred_y)，predmv是相邻块运动矢量的中值，mv为当前块的整像素运动矢量，%是求模操作，在1/4像素的情况下，β=4。

图2 基于中心的快速分像素搜索

3 MVSCBS算法

3.1 MVSCBS算法的切入点

H.264的运动估计采用七种模式，并选取匹配误差最小的模式作为帧间预测模式。每种模式的运动估计都是首先进行整像素运动估计，然后以最优整像素位置为中心，在一个整像素运动领域内进行分像素精确搜索。但是当分像素搜索之后最佳点仍为整数位置时，分像素搜索过程就是浪费。表1显示了在五个图像测试序列中的最终运动矢量分别为整像素运动矢量和分像素运动矢量的比例。从表1可以看出，18.33%以上的运动块的最终运动矢量都是整像素运动矢量。特别是对于运动程度比较低的测试序列，70%以上的运动块的最终运动矢量在整像素位置，如claire序列的整像素运动矢量比例占74.25%。设经过分像素搜索之后最佳点仍为整像素位置的运动块为整像素运动块（Integer Pixel Motion Block，IPMB）。可以提前预测这些IPMB，从而跳过IPMB的分像素搜索过程，这就是MVSCBS算法的切入点。通过跳过这些IPMB的分像素搜索，可以减少运动估计时间，从而提高编码效率。

表1 整像素和分像素运动矢量比例 （%）

3.2 MVSCBS算法描述

在整像素运动估计中，许多快速搜索算法都利用运动矢量的空间相关性来预测运动块的初始搜索点，如文献[6-7]中的算法，减少了大量的搜索点数，提高了整像素运动估计效率。因此，本文对运动矢量的空间相关性在分像素运动估计中的影响进行了统计性研究。本文根据运动块的运动矢量空间相关性来预测IPMB，即分别利用运动块的左邻块运动矢量（左）、上邻块运动矢量（上）、右上邻块运动矢量（右上）、中值预测运动矢量（中值）和上层块模式运动矢量（上层）作为当前块的预测运动矢量，如果预测运动矢量在整像素位置，则预测当前块为IPMB。表2和表3分别列出了用各种单个预测运动矢量来预测IPMB的预测精度和预测比例。表4和表5分别列出了用各种多个预测运动矢量来预测IPMB的预测精度和预测比例。其中预测精度表示在被预测的IPMB中，真正的IPMB所占的比例；预测比例则表示在所有的IPMB中，能提前预测为IPMB的运动块所占的比例。

表2 IPMB预测方法的预测精度 （%）

表3 IPMB预测方法的预测比例 （%）

表4 IPMB合并预测方法的预测精度 （%）

表5 IPMB合并预测方法的预测比例 （%）

预测精度越高，匹配误差就越小，因此图像的编码质量变化也越小；预测比例越高，能够预测出的IPMB越多，跳过分像素搜索的运动块就越多，因此分像素运动估计的计算量就越小。从表2和表3综合来看，虽然单个预测运动矢量预测IPMB的方法的预测比例较高，在小运动程度的测试序列中，达到90%以上，但是预测精度不够高，大部分都在90%以下。从表4和表5综合来看，对于同一测试序列，将左邻块运动矢量、上邻块运动矢量、右上邻块运动矢量和上层块模式运动矢量都作为预测运动矢量来预测IPMB的方法的预测精度是最高的，但是预测比例偏低，特别是对于运动程度比较大的测试序列，如foreman测试序列，预测比例只有29.81%，这样分像素运动估计计算量的减少就不明显。因此，本文从预测精度和预测比例两方面来综合考虑，选用了一种折中的方法，即将中值预测运动矢量和上层块模式运动矢量作为预测运动矢量来预测IPMB的方法。

为了判断预测运动矢量是否落在整像素位置，本文给出如下判断准则：当is_IntPos_x和is_IntPos_y都为0时，当前预测运动矢量被判定为落在整像素位置。is_IntPos_x和is_IntPos_y计算如下：

其中，(fracmν_x,fracmν_y)是分像素预测运动矢量，(mν_x,mν_y)是当前块的最优整像素运动矢量。

如果中值预测运动矢量和上层块模式运动矢量这两个预测运动矢量都落在整像素位置，则预测当前块为IPMB。对于被判定为IPMB的运动块，本文算法对其只进行整像素搜素，不进行分像素搜索，但是重新计算最优整像素位置的匹配误差值；对于未判定为IPMB的运动块，本文算法对其进行常规的整像素和分像素搜索。

表4和表5中的数据显示了本文方法比文献[5]方法的预测精度和预测比例都要高。文献[5]根据中值预测运动矢量和模式1的运动矢量，预测整像素匹配宏块，但对于未预测为整像素匹配宏块的宏块，其中可能含有IPMB，本文方法能预测出其中大部分的IPMB，因此预测比例更高，并且本文方法对所有的运动块都进行IPMB预测判决，所以预测精度更高。

4 实验结果及分析

本文实验是基于H.264/AVC参考模型和JM10.1平台进行的。实验硬件环境：Pentium®Dual-Core CPU 2.6 GHz，2 GB RAM。编码环境如下：搜索范围是[-16，16]，5帧作为参考帧，序列类型是IPPP，YUV的格式是4∶2∶0，帧率是30 frame/s。实验选取5个运动程度不同的QCIF格式的图像测试序列：akiyo，mother-daughter，news，foreman，claire，对这些序列中的前100帧进行视频编码。本文主要研究分像素运动估计算法，因此整像素运动估计算法采用JM10.1中的UMHexagonS[3]。分像素运动估计算法分别使用FFPS、CBFPS和本文提出的MVSCBS算法结合，分别称之为F&M，C&M。为了验证算法的有效性，与文献[5]提到的F&F，C&F算法进行了对比实验，并测试了峰值信噪比（PSNR），码率（Bitrate）和总分像素搜索点数（Τotal Fractional Pixel Searching Points，ΤFPSP）。分别计算了F&M，C&M算法相对于FFPS和CBFPS的峰值信噪比改变△PSNR，码率改变率△Bitrate和总分像素搜索点数改变率△TFPSP。表6反映了算法在量化参数为28时的性能。图3至图6显示了△PSNR和△Bitrate在量化参数从20到40之间的波动情况。

从表6可以看出，MVSCBS算法和FFPS结合使用，与FFPS算法相比，可以降低12.26%至69.26%的分像素搜索点，而峰值信噪比平均下降不超过0.012 dB，最高下降不超过0.03 dB；码率平均上升不超过0.118%，最高上升不超过0.57%，即F&M算法在保证搜索精度的同时，降低了分像素搜索工作量。若MVSCBS算法和CBFPS结合使用，与CBFPS算法相比，可以降低11.13%至55.44%的分像素搜索点，峰值信噪比平均下降不超过0.004 dB，最高下降不超过0.03 dB；码率平均上升不超过0.17%，最高上升不超过1.63%，即C&M算法保证了搜索精度的同时，也降低了分像素搜索工作量。

从表6还可以看出，相对于FFPS来说，F&M的峰值信噪比平均下降不超过0.012 dB，F&F的峰值信噪比平均下降不超过0.008 dB，F&M的码率平均上升不超过0.118%，F&F的码率平均上升不超过0.122%，即表明F&M和F&F有着相同的搜素精度，但F&M比F&F减少了大约10%的分像素搜索点；相对于CBFP来说，C&M的峰值信噪比平均下降不超过0.004 dB，C&F的峰值信噪比平均下降不超过0.008 dB，C&M的码率平均上升不超过0.170%，C&F的码率平均上升不超过0.198%，即表明C&M和C&F有着相同的搜素精度，但C&M比C&F减少了大约10%的分像素搜索点。

从图3可以看出，F&M算法相对于FFPS算法，△PSNR的波动范围为－0.07 dB到0.05 dB。从图4可以看出，F&M算法相对于FFPS算法，△Bitrate的波动范围为－0.94%到1.87%。从图5可以看出，C&M算法相对于CBFPS算法，△PSNR的波动范围为－0.07 dB到0.06 dB。从图6可以看出，C&M算法相对于CBFPS算法，△Bitrate的波动范围为－1.75%到1.99%。这说明本文提出的MVSCBS算法具有较高的搜素精度。

表6 算法性能

图3 F&M算法对PSNR的影响

图5 C&M算法对PSNR的影响

图4 F&M算法对Bitrate的影响

图6 C&M算法对Bitrate的影响

5 结论

为了减少分像素运动估计的计算量，本文提出了一种基于运动矢量空间相关性的分像素运动估计方法。它充分利用了运动矢量的空间相关性来避免IPMB的分像素搜索过程。本文算法将中值预测运动矢量和上层块模式运动矢量都作为预测运动矢量，并根据预测运动矢量是否落在整像素位置的方法来预测IPMB。对于被判定为IPMB的运动块，本文算法对其只进行整像素搜索，不进行分像素搜索，从而提高了搜索速度。实验结果表明，本文算法结合全分像素搜索算法使用，在基本保持搜索精度不变的同时，可比文献[5]中的算法减少10%左右的分像素搜索点。本文算法可与其他快速分像素搜索算法结合使用，以获得更好的编码性能。

[1]He Wenwei，Zhang Yuling.Improved hexagon-based searching algorithm for fast motion estimation[C]//IEEE Wireless Communications，Networking and Mobile Computing（WiCOM）. Shenzhen，China：IEEE Press，2010：1-3.

[2]陈刚，贾振红，陈荷.H.264/AVC中快速1/4像素运动估计算法[J].光电子·激光，2008，19（7）：960-962.

[3]Suh J W，Cho J，Jeong J.Model-based quarter-pixel motion estimation with low computational complexity[J].Electronics Letters，2009，45（12）：618-620.

[4]Xu Xiaozhong，He Yun.Improvements on fast motion estimation strategy for H.264/AVC[J].IEEE Τransactions on Circuits and Systems for Video Τechnology，2008，18（3）：285-293.

[5]方健，郑伟，李炳博，等.针对H.264的基于平坦区域预测的分像素运动估计[J].中国图象图形学报，2008，13（12）：2286-2290.

[6]Chen Z B，Zhou P，He Y.Fast integer pel and fractional pel motion estimation for JVΤ（JVΤ-F017）[C]//Proceedings of 6th Joint Video Τeam Meeting，Awaji，Japan，2002：5-13.

[7]Wu Xiaomin，Xu Weizhang，Zhu Nanhao，et al.A fast motion estimation algorithm for H.264[C]//Proceedings of International Conference on Signal Acquisition and Processing（ICSAP）.Bangalore，India：IEEE Press，2010：112-116.

ZENG Jiexian,ZHENG Dafang,FU Xiang

School of Software,Nanchang Hangkong University,Nanchang 330063,China

With the development of fast integer pixel motion estimation algorithms,the proportion of the computational cost of fractional pixel motion estimation in that of the whole motion estimation has become more and more significant.Τo reduce the complexity of fractional pixel motion estimation,a novel method of H.264 fractional pixel motion estimation based on the spatial correlation of motion vector is proposed.It predicts Integer Pixel Motion Block（IPMB）using the spatial correlation of motion vector.It skips the fractional pixel search process for IPMB.Experimental results show that combined with the full fractional pixel search algorithm,the proposed algorithm can reduce 60%of fractional pixel search points while maintaining the search accuracy basically compared with the pure full fractional pixel search algorithm.Τhe proposed algorithm can be combined with other fractional pixel search algorithm to get better coding performance.

H.264;motion vector;spatial correlation;motion estimation;Integer Pixel Motion Block（IPMB）

随着整像素运动估计快速算法的发展，分像素运动估计的计算量在运动估计中所占比重越发明显。为了减少分像素运动估计的计算量，提出了一种利用运动矢量空间相关性来预测整像素运动块，对整像素运动块进行分像素搜索过程跳过的分像素运动估计方法。实验结果表明，该算法与全分像素搜索算法结合使用，在基本保持搜索精度不变的情况下，比单纯的全分像素搜索算法减少60%左右的分像素搜索点。该算法可与其他快速分像素搜索算法结合使用，以获得更好的编码性能。

H.264；运动矢量；空间相关性；运动估计；整像素运动块

A

ΤN919.81

10.3778/j.issn.1002-8331.1111-0334

ZENG Jiexian,ZHENG Dafang,FU Xiang.H.264 fractional pixel motion estimation based on spatial correlation of motion vector.Computer Engineering and Applications,2013,49（15）：175-178.

国家自然科学基金（No.61165011）；江西省科技支撑计划项目（No.20112BBG70092）；航天科技创新基金。

曾接贤（1958—），男，教授，主要研究领域为图像处理与模式识别，计算机视觉；郑大芳（1988—），女，硕士，主要研究领域为图像处理与模式识别；符祥（1980—），男，博士，讲师，主要研究领域为数字图像处理和计算机视觉。E-mail：zengjx58@163.com

2011-11-18

2011-12-20

1002-8331（2013）15-0175-04

CNKI出版日期：2012-04-25 http://www.cnki.net/kcms/detail/11.2127.ΤP.20120425.1720.043.html