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

郭少校, 谭 兮, 宗 亮

(1. 湖南工业大学 电气与信息工程学院，湖南 株洲 412000；2. 湖南人文科技学院 通信与控制工程系，湖南 娄底 417000)

H.264/AVC[1]是由ITU-T和ISO/IEC联合提出的新一代视频编解码标准，其高效的编码性能和良好的网络亲和性，使其成为近年来视频编解码技术研究的热点之一。

由于视频序列中存在较大的冗余，消除这些冗余信息的一项重要技术就是运动估计与补偿。H.264/AVC采用基于块匹配(Block Matching Algorithm)的运动估计算法，在参考帧的搜索窗口内按照一定的匹配准则(如SAD)搜索最佳匹配块，该匹配块与当前块之间的位移为运动矢量，它们的差值为残差。运动估计与补偿越精确，最终得到的残差值越小，最终需要编码的比特数就越少。

在基于块匹配的运动估计算法中，全搜索算法(Full Search)的搜索精度最高，能够找到全局最优点，但是计算量太大，其运动估计部分占整个编码运算量的60%-80%，不适宜在实际中采用。为此，各国的学者们又提出了一些快速算法，这些快速算法的整体思想就是减少搜索点数，控制搜索步骤，如三步法[2](TSS)、四步法[3](FSS)、新三步法[4](NTSS)、菱形搜索法[5](DS)、六边形搜索法[6](HEXBS)等等，但是这些算法在某种程度上易陷入局部最优。非对称十字型多层次六边形格点搜索算法(UMHexagonS)[7]是一种优秀的快速运动估计算法，已被H.264/AVC标准所采纳。该算法在保持良好的率失真性能的前提下，相对于FS可节约70%左右的运算量。

本文对UMHexagonS算法做出了三点改进：在起始点预测之后进行一次零运动块判决；改进5*5螺旋搜索，减少搜索点数；根据运动矢量的方向性优化多层次六边形搜索。

一 UMHexagonS算法分析

UMHexagonS算法的重要特性就是它的精确的起始点预测以及提前终止判决(Early Termination)。它是一种混合的搜索方法，主要步骤如下：

(一) 起始搜索点预测

由于物体运动的连续性，运动矢量在空域(相邻块之间)和时域(相邻图像或参考帧之间)都表现出极强的相关性。UMHexagonS 采用4种有效的运动矢量预测模式：中值预测(Median Prediction) ，上层块预测(Uplayer Prediction)，相应位置块预测(Corresponding-block Prediction)，相邻参考图像预测(Neighboring Reference-picture Prediction)。

(二) 非对称十字型搜索

由于自然图像序列中，通常情况下物体做水平运动的比重要大于做垂直运动的比重，所以在水平方向取search_range个点，垂直方向上取search_range/2个点，如图1中下三角组成的十字模板所示。搜索所得的最小开销点，做为下一步的搜索中心。

图1 UMHexagon算法示意图

(三) 5*5方形全搜索

以上一步得到的最小开销点为中心，构造5*5的方形区域，如图1中黑色圆点所构成的区域，并做全搜索。

(四) 多层次六边形搜索

以上一步所得的最小开销点为中心，构造由16个点构成的六边形模板，由内到外依次扩展(1到search_range/4)，如图1中小方形点组成六边形所示。

(五) 扩展的六边形搜索和菱形搜索

执行六边形和菱形搜索，搜索模板如图1中由上三角组成的六边形以及由黑色的方形点组成的菱形所示。

二 基于UMHexagonS的优化方法

根据UMHexagonS算法的特点，本文在三个方面做出了优化，包括：提前引入零运动块判决；改进的5*5方形全搜索；优化的多层次六边形格点搜索。

(一)提前引入零运动块判决

本步骤改进的依据是现实中的大部分视频序列都具有静止或变化缓慢的背景。

在原UMHexagonS算法中，首先要根据块大小Bsize[blocktype]，预测绝对误差和Pred_SAD, AlphaSec[blocktype]和AlphaThird[blocktype]来计算调整因子β的值：

-AlphaSec[blocktype]

(3-1)

-AlphaThird[blocktype]

然后计算预测点的mcost和SAD值，并和最小开销min_mcost比较，取最小值，更新最佳预测位置；接着又做了一个菱形搜索，寻找最小开销点；然后根据其它条件做判断，最后由Early Termination判断是否要跳转到扩展的六边形搜索，或者小菱形搜索，或是非对称十字搜索和多层次六边形搜索。

由于求调整因子β需要进行浮点数运算，占用系统内存开销比较大；同时对于具有静止或变化缓慢的背景的视频序列，预测的起始点已经足够精确，而在经过如此繁琐的计算之后才进行判决，浪费了大量的计算时间。

针对这点不足，我们在计算β之前加入零运动块判决，取固定阈值[8]T=512，如果当前块和参考帧中预测块的SAD值小于512，则预测运动矢量即为整像素搜索的最终结果，同时返回最小开销。

(二)改进的5*5方形全搜索

原UMHexagonS算法在做完非对称十字形搜索之后，以其所得到的具有最小开销的点为中心，构造一个5*5的方形模板(如图1中黑色圆点组成的搜索区域所示)，执行螺旋形的全搜索，共需搜索24个点。

图2 改进后的搜索模板

(三)优化多层次六边形格点搜索

在多层次六边形格点搜索这一步骤，原算法依次搜索4个六边形的16个点，并未考虑实际视频序列中物体运动的方向性。本文把原六边形的16个点划分为4个区域，如图1中所示：

FIRSTQUARTER

SECONDQUARTER

THIRDQUARTER

FOURTHQUARTER。

每个区域5个点(部分点同时划分到两个区域)，根据预测运动矢量和参考帧中相同位置块的运动矢量，预测出物体的运动趋势，来判断搜索哪一区域的点。

由于多层次六边形搜索是在5*5方形搜索之后，假设5*5方形搜索得到的运动矢量为MVpred=(MVpred_x,MVpred_y)，参考帧中相应块的运动矢量为MVref=(MVref_x,MVref_y)，搜索流程如图3所示。

采用本文优化过的六边形格点搜索，在搜索每个六边形时，减少了原来2/3的搜索点数。由于预测出了物体的大致运动趋势，保证了搜索区域所得到的最小开销点是全局最优的，这样也就保持了良好的率失真性能，PSNR几乎没有下降。

图3 优化的多层次六边形搜索步骤

三 仿真及实验结果

本文采用H.264/AVC的标准测试代码JM86，编码配置参数如下： IntraPeriod=0， FrameSkip=1，NumberBFrames=1，FrameToBeEncoded=0，FrameRate=30,SearchRange=16，NumberReferenceFrames=10，编码序列IP…P。PC机配置如下：Inter(R) Core(TM) i3，2.53GHz，2G内存，Window7操作系统。对5个QCIF格式的标准序列进行测试：具有复杂运动的序列mobile、coastguard和foreman；简单头肩运动序列akiyo和salesman。

表1 原算法、FS以及优化算法的码率与运动估计时间比较

表2 原算法、FS以及优化算法的信噪比比较

表1是对改进算法前后码率、运动估计时间的比较。通过对比可以发现，改进后的算法在保持码率几乎不变的情况下，有效节省运动估计时间。对复杂运动序列，可节省运动估计时间达16%，对简单运动序列，可节省运动估计时间20%以上。表2是对改进算法前后的信噪比所做的比较。对比发现，改进后算法对视频序列的信噪比影响较小，有效保持了原有视频的质量。

综合以上结果，可发现本文优化后的算法在保证视频质量和码率稳定的前提下，可有效减少运动估计时间。

四 结论

本文通过对H.264/AVC中UMHexagon算法的分析与研究，从三个方面提出了改进或优化方法，通过实验对比可以发现，对各种不同运动情况的视频序列，改进后的算法均可在保持信噪比和码率几乎不变的情况下，有效减少运动估计时间，从而提高H.264/AVC编码器的性能。

注释：

①此处节省率是优化算法相对于FS的节省百分比。

②此处改善率是优化算法相对于原始算法改善百分比。

参考文献：

[1]Draft ITU-T recommendation and final draft of Video Specification (ITU-T Rec. h.264|ISO/IEC 14496-10 AVC)[S]. JVT-G050rl.doc, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, Geneva, Mar.2003.

[2]Zhibo Chen, Jianfeng Xu, Yun He, et al. Fast integer-pel and fractional-pel motion estimation for H.264/AVC [J]. Vis.Commun.Image R, 2006(17):264-290.

[3]KOGA T, IINUMA K, HIRANO A, et al. Motion-compensated inter frame coding for video conferencing[M]. IEEE 1981 National Telecommunications Conference, Innovative Telecommunications-Key to the Future, 1981:531-535.

[4]PO L M, MA W C. A novel four-step search algorithm for fast block motion estimation [J]. IEEE Trans on Circuits and System for Video Technology, 1996, 6(2):313-317.

[5]LI R X, ZENG B, LIOU M L. A new three-step search algorithm for block motion estimation [J]. IEEE Transactions on Circuits and Systems for Video Technology, 1994, 4(4):438-442.

[6]ZHU S, MA K K. A new diamond search algorithm for fast block matching motion estimation [J]. IEEE Trans-Image Processing, 2000, 9(2):287-290.

[7]ZHU C, LIN X, CHAU L, et al. Hexagon-based search pattern for fast block motion estimation [J]. IEEE Trans on Circuits and System for Video Technology, 2002, 9(11):349-355.

[8]YAO N, MA K K. Adaptive rood pattern search for fast block-matching motion estimation [J]. IEEE Trans on Circuits and System for Video Technology, 2002, 11(12):1442-1449.