基于H.264的运动估计搜索算法的改进

摘   要: 针对UMHexagonS算法的运算量大、耗时长、复杂度较高等问题，提出了改进方案，采用混合时空域起点预测，提高起始点的预测精度；为搜索模块设定阈值，提前终止搜索；在整个搜索过程中，提出了一种搜索模块象限区域分割法，有效地减少了搜索点数。实验结果表明，改进后的算法在保证信噪比和控制误码率的情况下，比原算法减少了14%~38%的运动估计时间。
     关键词: 运动估计; UMHexagonS; 混合时空域; 区域分割; 阈值  
       H.264是新一代视频压缩编码标准[1]，运动估计是视频压缩编码中的一个关键部分。在H.264整个编码过程中，运动估计在编码时间中占据了相当大的比例,因此，缩短运动估计时间是一个非常重要的环节。为了减少运动估计的时间，近年来国内外学者针对运动估计提出了很多经典的搜索算法,如全局搜索算法（FS）、三步搜索算法（TSS）、新三步搜索算法（NTSS）、四步搜索算法（FSS）、菱形搜索算法（DS）、六边形搜索算法（HS）、非对称十字型多层次六边形搜索算法(UMHexagonS)[2-3]。其中，UMHexagonS算法结合了其他算法的部分优点，在保证较好的率失真性能情况下，与FS算法比较，节省了90%以上的运算量。虽然如此，但对该算法的分析发现，UMHexagonS还存在一些不足，搜索点数较多，搜索范围较大，运算复杂度高，增长了编码时间，影响了编码效率。为了解决以上问题，本文提出了以下改进方案：
　　(1)设定阈值，在搜索过程中SAD值达到满意的情况下提前终止搜索。
　　(2)采用高精度的起始点预测，得到起始点的最佳预测运动矢量。
　　(3)采用搜索模块象限区域分割法，在原算法的基础上减少了一半以上的搜索点数。
1 UMHexagonS算法介绍
     (1)起始搜索点的预测：利用高精度的起始点预测，计算得出预测运动矢量MVpred。
　　(2)非对称十字型模板搜索，如图1(a)所示。
　　(3)螺旋模板搜索，以步骤(2)搜索的匹配点作为搜索中心，搜索坐标[-2,2]正方形区域内的25个候选点，类似于全局搜索，如图1(b)所示。
　　(4)大六边形多层次模板搜索，如图1(c)所示。
　　(5)以步骤(4)搜索的匹配点作为搜索中心，进行中小六边形模板搜索，如图1(d)所示。
　　(6)小菱形模板反复搜索，如图1(e)所示，搜索得到最佳的匹配点。
   
2 UMHexagonS算法的改进方案
2.1 起始搜索点的预测
　    起始搜索点的预测包括空间域预测方式和时间域两种预测方式。其中空间域预测方式包括运动矢量中值预测MP和上层块模式运动矢量预测UP;时间域预测方式包括前帧对应块运动矢量预测CP和时间域的邻近参考帧运动矢量预测NRP。根据运动矢量中心偏移特性[4]，原点也被设为一个候选点预测，称为原点预测ZP。在基于块匹配算法的运动估计中，宏块分为7种块模式，即16×16、16×8、8×16、8×8、8×4、4×8及4×4。由于同种预测方法针对不同的宏块，起始点的预测精度不一样，因此本文结合MP、UP、CP、NRP这四种方式采用了一种混合时空域预测方式[5]进行起始点的预测， 针对不同的宏块模式采用不同的预测方式， 可使起始点的预测精度更高。