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

ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　基于运动矢量空间相关性的Ｈ．２６４分像素运动估计　曾接贤，郑大芳，符祥　ＺＥＮＧ　Ｊｉｅｘｉａｎ，ＺＨＥＮＧ　Ｄａｆａｎｇ，ＦＵ　Ｘｉａｎｇ　

南昌航空大学软件学院，南昌３３００６３　Ｓｃｈｏｏｌ　ｏｆ　Ｓｏｆｔｗａｒｅ，Ｎａｎｃｈａｎｇ　Ｈａｎｇｋｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｃｈａｎｇ　３３００６３，Ｃｈｉｎａ　

ＺＥＮＧ　Ｊｉｅｘｉａｎ，ＺＨＥＮＧ　Ｄａｆａｎｇ，ＦＵ　Ｘｉａｎｇ．Ｈ．２６４　ｆｒａｃｔｉｏｎａｌ　ｐｉｘｅｌ　ｍｏｔｉｏｎ　ｅｓｔｉｍａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｓｐａｔｉａｌ　ｃｏｒｒｅｌａｔｉｏｎ　ｏｆ　ｍｏ—　ｔｉｏｎ　ｖｅｃｔｏｒ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１３，４９（１５）：１７５—１７８．　

Ａｂｓｔｒａｃｔ：Ｗｉｔｈ　ｔｈｅ　ｄｅｖｅｌｏｐｍｅｎｔ　ｏｆ　ｆａｓｔ　ｉｎｔｅｇｅｒ　ｐｉｘｅｌ　ｍｏｔｉｏｎ　ｅｓｔｉｍａｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ，ｔｈｅ　ｐｒｏｐｏｒｔｉｏｎ　ｏｆ　ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｓｔ　ｏｆ　ｆｒａｃｔｉｏｎａｌ　ｐｉｘｅｌ　ｍｏｔｉｏｎ　ｅｓｔｉｍａｔｉｏｎ　ｉｎ　ｔｈａｔ　ｏｆ　ｔｈｅ　ｗｈｏｌｅ　ｍｏｔｉｏｎ　ｅｓｔｉｍａｔｉｏｎ　ｈａｓ　ｂｅｃｏｍｅ　ｍｏｒｅ　ａｎｄ　ｍｏｒｅ　ｓｉｇｎｉｆｉｃａｎｔ．Ｔｏ　ｒｅｄｕｃｅ　ｔｈｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ｆｒａｃｔｉｏｎａ１　ｐｉｘｅｌ　ｍｏｔｉｏｎ　ｅｓｔｉｍａｔｉｏｎ．ａ　ｎｏｖｅｌ　ｍｅｔｈｏｄ　ｏｆ　Ｈ．２６４　ｆｒａｃｔｉｏｎａｌ　ｐｉｘｅｌ　ｍｏｔｉｏｎ　ｅｓｔｉｍａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｓｐａｔｉａｌ　ｃｏｒｒｅｌａｔｉｏｎ　ｏｆ　ｍｏｔｉｏｎ　ｖｅｃｔｏｒ　ｉｓ　ｐｒｏｐｏｓｅｄ．Ｉｔ　ｐｒｅｄｉｃｔｓ　Ｉｎｔｅｇｅｒ　Ｐｉｘｅｌ　Ｍｏｔｉｏｎ　Ｂｌｏｃｋ（ＩＰＭＢ）ｕｓｉｎｇ　ｔｈｅ　ｓｐａｔｉａｌ　ｃｏｒｒｅｌａｔｉｏｎ　ｏｆ　ｍｏｔｉｏｎ　ｖｅｃｔｏｒ．Ｉｔ　ｓｋｉｐｓ　ｔｈｅ　ｆｒａｃｔｉｏｎａｌ　ｐｉｘｅｌ　ｓｅａｒｃｈ　ｐｒｏｃｅｓｓ　ｆｏｒ　ＩＰＭＢ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｃｏｍｂｉｎｅｄ　ｗｉｔｈ　ｔｈｅ　ｆｕｌｌ　ｆｒａｃｔｉｏｎａｌ　ｐｉｘｅｌ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ，ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｒｅｄｕｃｅ　６０％ｏｆ　ｆｒａｃｔｉｏｎａｌ　ｐｉｘｅｌ　ｓｅａｒｃｈ　ｐｏｉｎｔｓ　ｗｈｉｌｅ　ｍａｉｎｔａｉｎｉｎｇ　ｔｈｅ　ｓｅａｒｃｈ　ａｃｃｕ－　ｒａｃｙ　ｂａｓｉｃａｌｌｙ　ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｔｈｅ　ｐｕｒｅ　ｆｕｌｌ　ｆｒａｃｔｉｏｎａｌ　ｐｉｘｅｌ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ．Ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｂｅ　ｃｏｍｂｉｎｅｄ　ｗｉｔｈ　ｏｔｈｅｒ　ｆｒａｃｔｉｏｎａｌ　ｐｉｘｅｌ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｇｅｔ　ｂｅｔｔｅｒ　ｃｏｄｉｎｇ　ｐｅｒｆｏｒｍａｎｃｅ．　Ｋｅｙ　ｗｏｒｄｓ：Ｈ．２６４；ｍｏｔｉｏｎ　ｖｅｃｔｏｒ；ｓｐａｔｉａｌ　ｃｏｒｒｅｌａｔｉｏｎ；ｍｏｔｉｏｎ　ｅｓｔｉｍａｔｉｏｎ；Ｉｎｔｅｇｅｒ　Ｐｉｘｅｌ　Ｍｏｔｉｏｎ　Ｂｌｏｃｋ（ＩＰＭＢ）　

摘　要：随着整像素运动估计快速算法的发展，分像素运动估计的计算量在运动估计中所占比重越发明显。为了减少分　像素运动估计的计算量，提出了一种利用运动矢量空间相关性来预测整像素运动块，对整像素运动块进行分像素搜索过　程跳过的分像素运动估计方法。实验结果表明，该算法与全分像素搜索算法结合使用，在基本保持搜索精度不变的情况　下，比单纯的全分像素搜索算法减少６０％左右的分像素搜索点。该算法可与其他快速分像素搜索算法结合使用，以获得　更好的编码性能。　关键词：Ｈ．２６４；运动矢量；空间相关性；运动估计；整像素运动块　文献标志码：Ａ　中图分类号：ＴＮ９１９．８１　ｄｏｉ：１０．３７７８／ｊ．ｉｓｓｎ．１００２．８３３１．１１１１．０３３４　

ｌ　引言　运动估计是视频压缩编码中的关键技术之一，它可消　除视频信号的时间冗佘，它的效率直接影响到编码速度，　压缩率和视频解码后的图像质量。Ｈ．２６４中由于采用分层　设计、多帧参论、多模式运动估计、１／４像素精度运动估计等　技术，提高了预测精度，降低了匹配误差，从而获得比其他　标准更好的压缩性能。但是，它的计算复杂度却大幅度增　加。因此，研究高效快速的运动估计算法具有重要意义。　典型的运动估计包括整像素运动估计和分像素运动　估计。整像素运动估计由于其搜索点数多而备受关注，许　多快速运动估计算法致力于整像素运动估计计算复杂度　降低的研究。随着整像素运动估计快速算法的发展，整像　素搜索点数ｕ　可以减少到１０个以下，这使得分像素运动估　计的计算量高于或相当于整像素运动估计的计算量。因　此，分像素运动估计快速算法的发展对于整个运动估计的　计算量的减少变得尤为重要。目前分像素运动估计快速　算法主要有三类：一类是基于运动补偿预测误差模型的算　法，如Ｈ．２６４／ＡＶＣ中快速１／４像素运动估计算法　和具有低　计算复杂度的基于模型的１／４像素运动估计　等，这类算法　根据最优整像素点的一个整像素运动领域的数学模型建　立误差模型，避免了运算量很大的分像素内插运算和分像　素搜索过程，但算法的匹配精度较低。另一类是采用提前　终止搜索策略的算法，如改进的面向Ｈ．２６４／ＡＶＣ的快速运　动估计策略　，这类算法通过阈值判定，提前结束分像素搜　索，但存在阈值选取或计算问题——阈值过大，搜索准确　度就会降低，阈值过小，搜索速度很难有明显提高。还有　

基金项目：国家自然科学基金（Ｎｏ．６１１６５０１１）；江西省科技支撑计划项目（Ｎｏ．２０１１２ＢＢＧ７００９２）；航天科技创新基金。　作者简介：曾接贤（１９５８一），男，教授，主要研究领域为图像处理与模式识别，计算机视觉；郑大芳（１９８８一），女，硕士，主要研究领域为图像　处理与模式识别；符祥（１９８０一），男，博士，讲师，主要研究领域为数字图像处理和计算机视觉。Ｅ—ｍａｉｌ：ｚｅｎｇｊｘ５８＠１６３．ｃｏｍ　收稿日期：２０１１－１１－１８　修回日期：２０１１—１２—２０　文章编号：１００２—８３３１（２０１３）１５－０１７５—０４　ＣＮＫＩ出版日期：２０１２－０４—２５　ｈｔｔｐ：／／ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉｌ／１１．２１２７．ＴＰ．２０１２０４２５．１７２０．０４３．ｈｔｍｌ　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　一类是基于图像平坦区域预测的算法，这类算法避免了前　两类算法的缺陷，如针对Ｈ．２６４的基于平坦区域预测的分　像素运动估计　。该算法采用中值预测运动矢量和模式１　的运动矢量，通过预测整像素匹配宏块，从而跳过部分宏　块的分像素搜索过程，达到提高搜索速度的目的，但对于　未预测为整像素匹配宏块的宏块，其中可能含有整像素运　动块，对这部分整像素运动块进行分像素搜索就是浪费。　针对文献［５】的不足，本文提出了一种基于运动矢量空　间相关性的Ｈ．２６４分像素运动估计算法，简称ＭＶＳＣＢＳ算　法。该算法充分利用运动矢量空间相关性来预测整像素　运动块，并对整像素运动块只进行整像素搜索，不进行分　像素搜索。实验结果表明，本文算法结合全分像素搜索算　法使用，基本保持了搜索精度的同时，可比文献【５】中的算　法减少１　Ｏ％左右的分像素搜索点。　

２　Ｈ．２６４中的分像素搜索算法　Ｈ．２６４中采纳了两种分像素搜索算法：分像素全搜索　（ＦＦＰＳ）和基于中心的快速分像素搜索（ＣＢＦＰＳ）　。　２．１分像素全搜索　分像素全搜索算法如图１所示。该算法首先计算最佳　整像素位置周围的８个１／２像素位置（如图１所示中的空心　方框“口”处），找到最佳１／２像素位置（如图１所示中的实心　方框“・”处）；然后计算最佳１／２像素位置周围的８个１／４像　素位置（如图１所示中的空心三角“△”处），找到最佳１／４像　素位置（如图１所示中的实心三角“▲”处），作为分像素搜　索的最佳运动矢量。由于分像素搜索在计算匹配误差值　时增加了Ｈａｄａｍａｒｄ变换，所以最佳整像素位置的匹配误差　值在分像素运动估计时要重新计算。分像素全搜索算法　总共需要搜索１７个点，其中包括８个１／２像素位置，８个１／４　像素位置和１个最优整像素位置。　

—　—一　—＿＿｛　—　｝　叫　ｈ　——一　

１　ｊ——　——一　一　—　

—　一　—　｝一　——｛　

０整像素位置　●最佳整像素位置　口１／２像素位置　－最佳１／２像素位置　△１／４像素位置　▲最佳１／４像素位置　

图１分像素全搜索　２．２基于中心的快速分像素搜索　基于中心的快速分像素搜索算法如图２所示。该算法　首先根据式（１）计算（ｐｒｅｄ　Ｘ，ｐｒｅｄ），比较该点处的匹配Ｙ　

误差值和最佳整像素位置的匹配误差值的大小，选匹配误　差值较小的位置作为搜索起始点；然后再循环使用小菱形　模板进行搜索，直到最小匹配误差点为搜索模板的中心时　停止；最后选取最小匹配误差点为最终的分像素匹配点。　ｆｒａｃ，　＝（ｐｒｅｄ　一ｍｖ）％ｆｌ　（１）　其中，ｆｒａＣｐｒｅｄ＝（ｐｒｅｄｘ，ｐｒｅｄｊ），ｐｒｅｄ　是相邻块运动　

矢量的中值，ｍｐ为当前块的整像素运动矢量，％是求模　操作，在１／４像素的情况下，　＝４。　

索＿＋　、范围　

——１　ｊ—一　、　

｝—　一　搜索范围　

ｌ　

０整像素位置　●最佳整像素位置　★（ｐｒｅｄ＿ｘ，ｐｒｅｄｊ）　△１／４像素位置　▲１／４像素匹酉己位置　

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

３　ＭＶＳＣＢＳ算法　３．１　ＭＶＳＣＢＳ算法的切入点　Ｈ．２６４的运动估计采用七种模式，并选取匹配误差最　小的模式作为帧间预测模式。每种模式的运动估计都是　首先进行整像素运动估计，然后以最优整像素位置为中　心，在一个整像素运动领域内进行分像素精确搜索。但是　当分像素搜索之后最佳点仍为整数位置时，分像素搜索过　程就是浪费。表１显示了在五个图像测试序列中的最终运　动矢量分别为整像素运动矢量和分像素运动矢量的比　例。从表１可以看出，１８．３３％以上的运动块的最终运动矢　量都是整像素运动矢量。特别是对于运动程度比较低的　测试序列，７０％以上的运动块的最终运动矢量在整像素位　置，如ｃｌａｉｒｅ序列的整像素运动矢量比例占７４．２５％。设经　过分像素搜索之后最佳点仍为整像素位置的运动块为整　像素运动块（Ｉｎｔｅｇｅｒ　Ｐｉｘｅｌ　Ｍｏｔｉｏｎ　Ｂｌｏｃｋ，ＩＰＭＢ）。可以提　前预测这些ＩＰＭＢ，从而跳过ＩＰＭＢ的分像素搜索过程，这　就是ＭＶＳＣＢＳ算法的切入点。通过跳过这些ＩＰＭＢ的分　像素搜索，可以减少运动估计时间，从而提高编码效率。