基于方向自适应模板的UMHexagonS算法改进*

赵子武，邹雪妹，程 飞，魏小文

（上海大学 通信与信息工程学院，上海 200072）

责任编辑:孙 卓

1 引言

在视频压缩编码中，时域冗余主要通过运动估计和运动补偿来消除，它也是整个编码器比较耗时的部分。针对运动估计最先提出的全搜索算法[1]:在参考帧预先定义好的搜索区域中，将当前帧与搜索区域中所有的候选块进行比较，最小匹配误差的块为最优块。全搜索法（FS）能够获得非常高的搜索精度，但运算量十分巨大，之后的运动搜索算法都以在不影响精度的同时减少计算量为目标。 三步搜索法（TSS）、两维对数法（LOGS）、十字型搜索法（CS）、四步搜索法（FSS）、梯度下降法（BBGDS）[2]、钻石搜索法（DS）[3]和六边形搜索法（HEXBS）[4]等的搜索速度比全搜索有了提高，但它们没有充分考虑时间和空间上相邻块的信息，搜索时容易陷入局部最小值，从而导致匹配精度差。之后提出的运动估计算法主要集中于以下几个方面:充分考虑时间和空间上的相邻宏块信息，针对视频中静止宏块较多的情况提出自适应提前终止策略，改变搜索模板，根据初始预测运动矢量自适应修改搜索区域大小等。例如MPEG-4标准第7部分已经采用的MVFAST[5]和改进算法 PMVFAST[6]。

基于上述研究，H.264标准采用了UMHexagonS算法[7]，该算法能同时适应小运动和大运动情况下的运动估计，并能得到与全搜索基本一样的精度和率失真特性，同时最多能比全搜索节省90%的时间。因此，H.264/AVC标准采纳了该运动估计算法。文献[8]中UMHexagonS算法改变了搜索模板，一定程度上减少了运动估计时间。

2 UMHexagonS算法

非对称十字型多层次六边形格点搜索算法（UMH-exagonS）搜索步骤[1]如下:

1）初始搜索点预测。取对应费用函数最小的点为初始搜索点（预测搜索法包括针对空间相关性的中值预测、上层预测、前一帧对应块预测和邻近参考帧预测），然后判断是否提前截止。

2）非对称十字型搜索。由于一般物体水平方向运动要比垂直方向运动剧烈，所以将垂直方向设置为水平方向搜索范围的一半，判断是否提前终止搜索。

3）非均匀多层次六边形格点搜索分步进行5×5小矩形窗全搜索和扩展的多层次六边形格点搜索，同时也要判断是否提前终止搜索。

4）采用扩展多层次六边形格点搜索和小菱形搜索模式循环进行搜索，持续搜索到最小费用函数值的点位于菱形搜索窗口的中心点为止。

该算法充分考虑了空间和时间的相关性以及H.264采用的宏块划分技术中不同尺寸块的运动矢量相关性，进行初始点预测，针对运动幅度的大小采用自适应的六边形格点搜索和菱形搜索，具有很强的内容适应性，同时应用提前终止策略避免了不必要的运算，这些都取得了很好的效果。

3 改进UMHexagonS算法

要保证同样的编码效果，同时进一步减小UMHexagonS算法的运算量，笔者提出了改进方法，主要使初始运动矢量更准确，减少5×5全搜索点数，通过精确的运动矢量确定搜索方向并改用扩展的梯形格点进行搜索。

3.1 初始运动矢量改进

在原算法4种初始搜索点预测模式基础上提出第5种预测模式:当前块的左、上、右上块的运动矢量分别为 MV1，MV2，MV3，参考帧同位置块的运动矢量为 MV′1，MV′2，MV′3。

1）中值预测 。 PMV1=mediam（MV1，MV2，MV3），PMV2=mediam（MV′1，MV′2，MV′3），取两者中的最小SAD作为初始MV。

2）PMV=mediam（MV1，MV2，MV3，MV′1，MV′2，MV′3）。

3）Weighted 预测。PMV1=0.375（MV1+MV2）+0.25MV3，PMV2=0.375（MV′1+MV′2）+0.25MV′3，取两者中的最小SAD做为初始MV。

对上述3种方法进行实验测试证明第3种方法比较好，则本算法采用Weighted预测。

3.2 5×5全搜索改进

5×5模式因为采用了全搜索模式，所以需要计算25个搜索点，运算量相对较大。在文献[8]中，笔者对常用视频序列的运动矢量做了详细的统计分析，发现运动矢量大部分落于[-2，2]区域中，且以不同比例集中分布在中心附近的特定区域内。如图1所示，有大约81.8%的运动矢量分布在中心附近范围±2的正方形区域内（25个点），大约77.52%的运动矢量分布在中心附近范围±2的菱形区域内（13个点），大约74.76%的运动矢量集中分布在中心附近范围±2的十字形区域内（9个点），而且匹配点在中心点的概率最高，其次为中心点上、下、左、右4个点，而在周围右上、左上、右下、左下对角点概率相对较小。本算法参考以上研究结果，在基本保持搜索精度的情况下，通过采用六边形、八边形或大小菱形相结合等方法进行比较实验测试后共采用17个点（如图2中的小三角形）代替5×5全搜索（如图2中的小三角形和小圆点）模式25个点，减少了32%的运算量。

3.3 六边形格点搜索改进

首先根据3.1节中得到的最优初始运动矢量（MVx，MVy）计算 MvRatio=MVx/MVy，根据 MvRatio判断运动矢量所在的区域，采用可变搜索模板进行搜索从而减少搜索点。 比如（MVx，MVy）=（1，2），则 MvRatio=0.5，用不断扩大搜索模板搜索第 1，2 象限；（MVx，MVy）=（-2，1），则用不断扩大的搜索模板搜索第2，3象限。在进行搜索模板的选择时，对半六边形、三角形、梯形和矩形等模板进行实验测试，在考虑搜索精度和时间的情况下，最终选择梯形模板。非对称六边形要搜索16个点，而本算法的梯形只需搜索7个点，在保证搜索质量的同时能减少56.25%的运算量。图3为改进UMHexagonS算法的搜索步骤。

4 实验结果与分析

为了验证改进UMHexagonS算法的有效性，采用JVT参考软件JM8.6进行仿真实验。实验采用不同运动类型的标准视频序列bus_cif，mobile_cif，flower_cif，stefan_cif，foreman_cif，coastguard_cif等作为测试序列。表1是本实验采用的JM代码的编码控制参数。

表1 JM编码控制参数

本实验分别采用标准算法和改进算法对不同视频序列的前28帧进行编码。表2给出了两种方法的运动估计总耗时并进行比较，表3给出了两种算法的亮度平均峰值信噪比。从两表中可以看出，采用改进算法的PSNR基本不变，在保持图像质量的同时有效降低了运动估计时间，对运动很缓慢的序列效果提高不大，但对剧烈运动序列效果很明显。表4给出了两种算法的平均比特率的比较，可以看出改进算法经过视频编码后的比特数有极其微小的增加。综上所述，改进算法在降低运动估计时间的同时非常好地保持了原算法的率失真性能，码率基本不变，对图像质量没有影响。

表2 视频编码耗时和运动估计耗时

表3 视频亮度分量的平均峰值信噪比

表4 视频编码平均比特率

5 小结

笔者对运动估计经典算法和H.264采用的UMHexagonS算法进行了简单的分析，并提出了一种改进算法。该算法同时考虑了视频序列的时域和空域的相关性，使初始运动矢量预测更准确，减少5×5全搜索中的相对不重要搜索点和运算量，根据初始运动矢量的方向使用可变方向的梯形模型搜索，加快搜索速度。在不影响搜索精度，码率基本不变的情况下大幅减少运动估计的运算量，取得了很好的效果。

[1]毕厚杰.新一代视频压缩编码标准——H.264/AVC[M].北京:人民邮电出版社，2005.

[2]LIU L K，FEIG E.A block-based gradient descent search algorithm for block motion estimation in video coding[J].IEEE Trans.Circuits and Systems for Video Technology，1996，6（4）:419-422.

[3]ZHU S，MA K K.A new diamond search algorithm for fast blockmatching motion estimation[J].IEEE Trans.Image Processing，2000，9（2）:287-290.

[4]ZHU C， LIN X， CHAU L.Enhanced hexagonal search for fast block motion estimation[J].IEEE Trans.Circuits and Systems for Video Technology， 2004，14（10）:1210-1214.

[5]ISO/IEC JEC1/SC29/WG11 M5453，Report on performance of fast motion estimation using motion vector field adaptive search techni-que（MVFAST）[S].1999.

[6]TOURAPIS A M，AU O C，LIOU M L.Predictive motion vector field adaptive search technique-enhancing block based motion estimation[EB/OL].[2009-11-09].http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.9457&rep=rep1&type=pdf.

[7]CHEN Z B， XU J F， HE Y， et al.Fast integerpel and fractionalpel motion estimation for H.264/AVC[EB/OL].[2009-11-09].http://linkinghub.elsevier.com/retrieve/pii/S1047320305000787.

[8]段青青，宋瑞.一种H.264/AVC中的快速运动估计算法[J].计算机工程，2008，34（16）:244-246.