一种基于UMHexagonS运动估计的优化算法

刘学谦，张 涛，王 赞

(天津大学 电子信息工程学院，天津300072)

责任编辑:时 雯

由JVT制定的最新视频编码标准H.264/AVC[1]，因其采用了很多新技术、新方法，特别是帧间预测中的可变化尺寸块运动估计、1/4像素精度的运动估计、多参考帧的使用，所以其比以往的视频标准有更高的编码质量，同时也有更高的复杂性。运动估计所需要的时间占整个编码器编码时间的60%～80%[2]。为了提高编码速度，研究运动估计快速算法，也非常必要。

近年来，各国学者提出多种运动估计的快速算法，在保证编码质量基本不变的前提下，提高运动估计的效率。比如，三步法(TSS)[3]、四步法(FSS)[4]、六边形搜索法(HEXBS)[5]、钻石搜索法(DS)[6]、改进的预测式区域搜索算法(EPZS)[7]、非对称十字型多层次六边形格点搜索(UMHexagonS)算法[2]。

本文基于UMHexagonS算法，根据运动情况，使用动态搜索窗口以及自适应的搜索模板，在图像质量和码率没有太大变化的情况下，降低了算法的复杂度，大大减少了运动估计的时间。

1 UMHexagonS算法描述

UMHexagonS搜索算法主要包括4个步骤[2]:

1)非对称的十字形搜索;

2)5×5小矩形搜索;

3)非均匀多层次六边形搜索;

4)扩展的六边形搜索。

算法流程如图1所示。

图1 UMHexagonS搜索算法的步骤

在开始搜索之前，起始搜索点要根据当前块的运动情况，在原点预测值、中值预测值(MVpred_MP)、上层预测值(MVpred_UP)、相邻参考帧预测值(MVpred_NRP)和时域对应块预测值(MVpred_CP)这5种预测模式中来进行选择。搜索范围的大小通过配置文件的search_range参数设置:search_range=16/32/48/64。在搜索的同时，UMHexagonS算法中还设定了提前终止搜索和跳转搜索步骤的阈值，这就大大减少搜索的点数，节省了搜索时间。

2 UMHexagonS算法的优化

2.1 动态的搜索范围

最新的编码标准中，分块模式不再是单一的16×16。比如H.264/AVC标准有7种分块模式，最大块为16×16，最小块4×4。虽然已经引入了动态搜索范围[8]，但是并没有考虑到不同模式，比如会对4×4的块增加额外的搜索。因此为了进一步优化搜索范围，可以利用MVpred_MP和MVpred_UP来针对非16×16(该模式没有MVpred_UP)模式，再计算一个新的搜索范围[9]，取新的搜索范围与以前搜索范围中的最小值作为最后的搜索范围。动态搜索窗口的计算方法如图2所示。

图2 动态搜索窗口计算方法

A是从配置文件获得的search_range;B是计算得出的新的动态搜索范围(new_search_range)，由C和D构成;C是固定的搜索范围。D是动态范围。其中，MVpred_UPX，MVpred_UPY和MVpred_MPX，MVpred_MPY分 别 是MVpred_UP，MVpred_MP的X和Y分量。C，D两个搜索范围的计算公式定义如下

2.2 搜索模板的改进

2.2.1 十字模板的优化

原始的十字搜索模板要搜索24个点，虽然是不对称的模板，但在某些情况下垂直方向上发现最优点的可能性要比水平方向大，如果使用同一个模板，不利于更快找到最优点。可以根据当前的预测运动矢量MVpred的X方向与Y方向的不同，选择以下不同的模板，如图3所示。

模板是不对称的小十字模板，一个步长是2，一个步长是1。如果abs(MVpred_x)＜abs(MVpred_y)选用模板2;否则选用模板1。搜索方式是:以当前点为中心，搜索周围四个点，直到最优点为中心点，停止搜索。实验结果显示，采用这种方法，平均每次搜索不到5个点。

图3 不对称小十字模板

2.2.2 5×5小矩形搜索的改进

由于运动矢量的最优点在13点的菱形和25点的小矩形出现的概率分布是80.7%和82.6%[10]，所以本文采用了13点菱形来替代25点的小矩形，如图4所示。

图4 13点菱形和25点小矩形

2.3 多层次多角度自适应模板

UMHexagonS中的非均匀多层次六边形搜索，为了有效避免陷入局部最优，每次需要检测4×16个点。此步骤可以结合运动矢量分布的空间方向性[11]，并结合MVpred_MP来简化搜索模板的层数。具体方法如下:

1)当Num_Big_Hexagon≥4时

如果Mv_Big_Hexagon≥12，则修改Num_Big_Hexagon=4;

如果8≤Mv_Big_Hexagon＜12，则修改Num_Big_Hexagon=3;

其他情况，则修改Num_Big_Hexagon=2。

2)当3≤Num_Big_Hexagon＜4时

如果Mv_Big_Hexagon≥8，则修改Num_Big_Hexagon=3;

如果6≤Mv_Big_Hexagon＜8，则修改Num_Big_Hexagon=2;

其他情况，则修改Num_Big_Hexagon=1。

3)当2≤Num_Big_Hexagon＜3时

如果Mv_Big_Hexagon≥6，则修改Num_Big_Hexagon=2;

其他情况，则修改Num_Big_Hexagon=1。

4)当Num_Big_Hexagon≤1时

Num_Big_Hexagon=1。

其中，Mv_Big_Hexagon是MVpred_MP中X方向和Y方向的最大值;Num_Big_Hexagon为最后的搜索层次数，1即为图5的单层，2即为在单层的基础上，再向外扩展一层，搜索点坐标为单层的2倍，3层、4层以此类推;Num_Big_Hexagon=new_search_range/4。

经过以上几步搜索后，可以利用当前获得的最佳运动矢量与上一帧对应位置块的运动矢量的偏离方向，确定自适应模板的搜索方向，既减少了搜索点数，又能准确地避免陷入局部最优。搜索方向的角度在第一/三象限，使用12，13，14，15，0，4，5，6，7，8十点构成的模板;角度在第二/四象限，使用0，1，2，3，4，8，9，10，11，12十点构成的模板;X轴方向，即X轴方向不为0，Y轴方向为0使用2，4，6，10，12，14六点构成的模板;Y轴方向，使用1，5，0，1，7，8，9六点构成的模板。模板的示意图如图5所示。

图5 非均匀多层次六边形搜索的单层模板

3 实验结果和分析

3.1 测试平台和配置

本文采用H.264/AVC的JM11.0平台进行测试。实验所用计算机的硬件配置为:Intel(R)Core(TM)i5-2310@2.90 GHz，4 Gbyte内存，操作系统为Windows XP SP3。为了更好地评价本文算法，实验选取几组不同运动类型的、不同分辨率的标准测试序列，设定不同的搜索范围，序列格式为YUV 420，编码档次为Baseline Profile。实验所用到的编码参数及测试序列如表1所示。

3.2 测试结果和分析

对于运动估计搜索算法的复杂度，可以由搜索点的个数来评价。对于16×16大小的块在搜索范围为16时，UMHexagonS算法的搜索点个数至少为N1=step1+step2+step3+step4=25+24+64+10=123点，而本文改进算法的搜索点个数至少为N2=step1+step2+step3+step4=5+12+6+10=34点。由上可知，本文的改进算法能有效地降低搜索点个数，相应地也极大地减少了运动估计时间，编码时间也会减少，所以从理论上可以证明本文算法的有效性。

表1 实验用到的测试序列

测试中将本文改进的算法与原有的UMHexagonS算法进行了对比，实验数据如表2和表3所示，其中同一分辨率下的序列平均值就是统计表1中同一分辨率的序列测试结果的平均值作为最终测试结果。

表2 图像运动缓慢的序列实验结果

表3 不同分辨率不同搜索范围的实验结果

实验主要是将本文算法和UMHexagonS算法在不同搜索范围下的PSNR、码率、编码时间、运动估计时间等方面进行了比较。从实验结果来看，本文算法的PSNR与UMHexagonS算法比几乎相同，下降时的幅度也都在0.02 dB以内;本文算法的码率与UMHexagonS算法比，幅度变化不大;从表2可以看出，本文算法在简化运动估计方面有很大的优势，特别是对图像运动剧烈的序列，效果尤为明显。一般情况下，本文算法在PSNR和码率变化不大的同时，QCIF分辨率搜索范围设置为32，平均可节省32.64%的运动估计时间;由表3可知，随着搜索范围的扩大，本文算法在运动估计时间上优势就越明显，有时都能节省47.05%。

4 小结

视频编码系统在有效提高编码质量的同时，也提高了其复杂性。本文对运动估计的UMHexagonS算法进行了研究和分析，对不同搜索模式下的动态搜索范围进行了改进，用自适应不对称小十字模板替代原有的十字模板，用小菱形替代原有的小矩形搜索，又提出多层次多角度的自适应六边形模板，并对小菱形搜索进行了简化，这在一定程度上减少了搜索点数。从实验结果可以看出，本文提出的新算法，在保证图像质量和码率基本不变的前提下，编码时间和运动估计时间都有不同程度的减少，特别是对运动较剧烈的序列有更好的效果，并且搜索范围越大，本文算法在运动估计时间上的优势就越明显。

[1]WIEGAND T，SULLIVAN G，LUTHRA A.Overview of the H.264/AVC video coding standard[J].IEEE Trans.Circuits and System for Video Technology，2003，13(7):560-576.

[2]CHEN Zhibo，XU Jianfeng，HE Yun，et al.Fast integer-pel and fractionalpel motion estimation for H.264/AVC[J].Journal of Visual Communication and Image Representation，2006，17(2):264-290.

[3]KOGA T，IINUMA K，HIRANO A，et al.Motion compensated interframe coding for video conferencing[EB/OL].[2013-05-02].http://citeseer.uark.edu:8080/citeseerx/showciting;jsessionid=228570CE9CB7B FDA1E15A138A877B06C?cid=20547.

[4]PO L，MA W.A novel four-step search algorithm for fast block motion estimation[J].IEEE Trans.Circuits and Systems for Video Technology，1996，6(3):313-317.

[5]ZHU C，LIN X，CHAU L.Hexagon-based search patten for fast block motion estimation[J].IEEE Trans.Circuits and Systems for Video Technology，2002，12(5):349-355.

[6]ZHU Shan，MA Kaikuang.A new diamond search algorithm for fast block matching motion estimation[J].IEEE Trans.Image Processing，1997，9(2):292-296.

[7]TOURAPIS A，AU O，LIOU M.New results on zonal based motion estimation algorithms-advanced predictive diamond zonal search[C]//Proc.ISCAS 2001.Sydney，NSW:IEEE Press，2001:183-186.

[8]XU Xiaozhong，HE Yun.Modification of dynamic search range for JVT[S].2005.

[9]CHEN Z，SONG Y，IKENAGA T，et al.A dynamic search range algorithm for variable block size motion estimation in H.264/AVC[C]//Proc.6th International Conference on Information，Communications &Signal Processing.Singapore:IEEE Press，2007:1-4.

[10]LIU Haihua，XIE Changsheng，LEI Yi.An unsymmetrical dual cross search algorithm for fast block-matching motion estimation[C]//Proc.ICTAI 2005.Hong Kong:IEEE Press，2005:613-620.

[11]TOURAPIS A，AU O，LIOU M.Predictive motion vector field adaptive search technique(PMVFAST)enhancing block based motion estimation[C]//Proc.VCIP 2001.San Josc，CA:IEEE Press，2001:24-26.