基于H.264的运动估计搜索算法的改进-AET-电子技术应用

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

电子技术应用第02期

林永，杨印根，杨柳，许大姐

江西师范大学计算机信息工程学院，江西南昌330022

摘要： 针对UMHexagonS算法的运算量大、耗时长、复杂度较高等问题，提出了改进方案，采用混合时空域起点预测，提高起始点的预测精度；为搜索模块设定阈值，提前终止搜索；在整个搜索过程中，提出了一种搜索模块象限区域分割法，有效地减少了搜索点数。实验结果表明，改进后的算法在保证信噪比和控制误码率的情况下，比原算法减少了14%~38%的运动估计时间。

关键词： 软件运动估计 UMHexagonS 混合时空域区域分割

中图分类号: TP391.41
文献标识码: A
文章编号： 0258-7998(2012)02-0134-04

Improvement of motion estimation search algorithm based on H.264

Lin Yong, Yang Yin′gen, Yang Liu, Xu Dajie

College of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, China

Abstract： As UMHexagonS algorithm has the disadvantages of big computation, time consuming and high complexity, this paper proposes some schemes of improvement, which mainly includes three aspects. Firstly, use spatio-temporal initial point prediction to improve the forecast accuracy of the initial point; Secondly, set threshold for the search module to terminate search; Thirdly, put forward a search module quadrant regional segmentation method in the whole search process, effectively reducing the searching points. Through the experimental results show that the improved algorithm can in guarantee SNR and bit-error rates than the original algorithm, reduce 14%~38% of the motion estimation time.

Key words : motion estimation;UMHexagonS;spatio-temporal;quadrant segmentation;threshold

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]进行起始点的预测，针对不同的宏块模式采用不同的预测方式，可使起始点的预测精度更高。

2.2 搜索模块象限区域分割法
　   由上述UMHexagonS搜索过程得知，该搜索算法在搜索过程中，搜索的候选点数较多，可以通过一些改进的方法减少搜索点数。本文采用了搜索模块象限区域分割法，根据参考文献[6]中得知预测运动矢量和最佳运动矢量落入某同一象限的平均概率在95%以上，准确度很高。因此，利用混合时空域起点预测方法，可找到起始点的运动矢量方向，由于起点运动矢量方向和最佳运动矢量方向所落入的象限范围基本一致，所以在后面的搜索阶段只需要在一个约定的象限区域内进行搜索，其他3/4的区域都不用搜索，这样可以大大减少搜索点数和节省搜索时间。
   如图2所示,整个宏块可划分为4个象限区域，分别是A1、A2、A3、A4,如果将当前宏块运动估计的起始点的最佳预测运动矢量记为MVpred(pred_x,pred_y)，则通过该运动向量计算得出：
     (1)
     由式(1)可判断得出预测运动矢量方向落入在哪个象限内：
     If: sinθ>0 && cosθ>0   MV_pred∈A1
     If: sinθ>0 && cosθ<0   MV_pred∈A2
     If: sinθ<0 && cosθ<0   MVp_red∈A3
     If: sinθ<0 && cosθ>0   MV_pred∈A4
　   由图2给出的4种不同的运动矢量所属象限的划分,以及式(1)和式(2)的判断，得知对原UMHexagonS算法的非对称十字型模板搜索、螺旋模板搜索、大六边形模板搜索，六边形模板搜索和菱形模板搜索进行象限区域划分，如图3所示。

图3 改进后的搜索模块

   以16×16搜索范围为例,只搜索一个象限区域，从图3(a)可以看出，原搜索算法需要搜索24个候选点，优化改进后，搜索点数只有原搜索算法的一半，将该改进后的搜索方法记为P1。图3(b)中，原搜索算法需要搜索25个候选点，改进模板后只需要搜索9个点，将该改进后的搜索方法记为P2。图3(c)中，原搜索算法需要搜索64个候选点，改进后只需要搜索20个点，将该改进后的搜索方法记为P3。图3(d)中，原搜索算法需要搜索6个候选点，改进后只需要搜索2个点，将该改进后的搜索方法记为P4。图3(e)原搜索算法需要搜索4个候选点，改进后只需要搜索2个点，将该改进后的搜索方法记为P5。优化及改进后的各种搜索模块平均节省了一半以上的搜索点数，因此，采用搜索模板象限区域分割法可以大大减少搜索点数。
2.3 搜索提前终止策略
   提前终止搜索策略的方法是设定阈值，在保证率失真的情况下，设定合理的阈值T可以较好地节省搜索时间。在H.264标准中采用块匹配准则方式计算搜索点的最小绝对差值和(SAD)，如果SAD值小于或等于设定的阈值T，则提前结束搜索。由于宏块支持7种分块模式，各种块模式的平均SAD值各有不同，为了减少计算量，可以根据不同块模式的需要，设定7个不同的阈值。
2.4 算法改进的具体流程
　   (1)首先，进行混合时空域起始搜索点的预测，判断该起始点SAD值，如果小于阈值T，则转入步骤(7)，否则，转入步骤(2)。
　   (2)通过式(1)和式(2)计算后得到预测运动矢量方向落入所属的象限区域，并采用P1的方法进行搜索，判断各候选点SAD值，如果小于阈值T，则转入步骤(7)，否则，转入步骤(3)。
　   (3)以步骤(2)最小候选点为中心，在预测的象限区域内采用P2的方法进行搜索，判断各候选点SAD值，如果小于阈值T，则转入步骤(7)，否则，转入步骤(4)。
　   (4)在预测的象限区域内采用P3的方法进行搜索，判断各候选点SAD值，如果小于阈值T，则转入步骤(7)，否则，转入步骤(5)。
   (5)以步骤(4)最小候选点为中心，在预测的象限区域内采用P4的方法进行反复搜索，判断各候选点SAD值，如果小于阈值T，则转入步骤(7)，否则，转入步骤(6)。
　   (6)在预测的象限区域内采用P5的方法进行反复搜索。
　   (7)找到最佳匹配点，结束搜索。
　   算法改进后具体流程如图4所示。

图4 UMHexagonS算法改进流程图

3 仿真实验结果与分析
3.1 仿真实验平台与配置
　　为了测试改进后的算法，本文在VC++6.0的平台上，将H.264标准测试JM10.2[7]集成到平台上进行了算法改进后的测试。实验所用PC机的硬件配置如下：Windows XP，CPU 2.80 GHz，内存为2 GB。选用的测试序列集为5个176×144的QCIF格式序列，所有序列都为Yuv4:2:0。采用baseline编码，编码器主要参数配置为FramesToBeEncoded=100，FrameRate=30.0，UseHadamard=1，SearchRange=16，NumberReferenceFrames=5,其他参数为默认值。
3.2 实验结果与分析
算法改进前、后仿真实验数据对照如表1所示。
算法改进前、后实验数据对比及变化如表2所示。

   从表2的实验数据中可以发现，改进后的算法与原算法相比，PSNR值的变化不超过0.01dB，误码率的增加率最大不超过1.2%，然而运动估计时间却减少了14%~38%。其中，对于运动比较缓慢的序列news和akiyo而言，搜索速度提高了14.24%和18.19%，对于中度运动foreman序列，提高了28.86%，对于剧烈运动的序列coastguard和mobile而言，提高了38.88%和38.67%。从而可以看出，改进后的算法相对于原算法，搜索速度随运动序列剧烈强度的增加而提高。因此，本文算法在保证编码性能的基础上，可以大幅地减少原算法的运动估计时间，整体上提高编码效率。
   本文通过对运动估计UMHexagonS进行了分析和研究，针对该算法提出了一些改进，通过混合时空域高精度的起始点预测，引入预测运动矢量方向性判别搜索区域从而降低搜索点数，设定阈值提前终止搜索。从实验结果可以发现，本文算法在PSNR和码率与原算法相近的情况下，运动估计时间得到大幅降低。因此，本文的改进算法与原算法相比，具有明显的优势。
参考文献
[1] WIEGAND T, SULIVAN G J, LUTHRA A. Draft ITU-Trecommendation H.264 and final draft international standard 14496-10 AVC[R]. JVT of ISO/IEC JTC1/SC29/WG11 and ITU-T SG16/Q.6,Doc.JVT G050r1, Geneva, Switzerland,May 2003.
[2] Yang Peng,He Yuwen, Yang Shiqiang. An unsymmetrical-cross multi-resolution motion search aigorithm for Mpeg4-Avcm. 264 coding[R]. IEEE International Conference on Multimedia and Expo(ICME),2004:531-534.
[3] Yang Peng, Wu Hua, Yang Shiqiang. Fast motion estimation algorithm for H.264[J]. Journal of Tsinghua University (Science and Technology),2005,45(4):527-531.
[4] 李会宗,陈雷霆,卢光辉,等.基于起点预测的不连续十字形快速搜索算法[J].计算机应用究，2008，25(10):
     2929-2931.
[5] Zhou Wei, Duan Zhemin,Hu Hongqi.Fast motion estimation algorithm for H.264/AVC based on centered prediction[J].Journal of Systems Engineering and Electronics.2010,21(6):1103-1110.
[6] 李桂菊,刘刚,梁静秋.H.264快速运动估计算法的改进[J].光学精密工程.2010,18(11):2489-2496.
[7] JVT Reference Software of H.264.http://iphome.hhi.de/suehring/tml/.

原创声明：此内容为AET网站原创，未经授权禁止转载。

相关内容