刘学谦，张 涛，王 赞

(天津大学 电子信息工程学院，天津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算法中还设定了提前终止搜索和跳转搜索步骤的阈值，这就大大减少搜索的点数，节省了搜索时间。……