基于AVS的快速亚像素运动估计算法

宋雪桦，包 祥，吴问云

（江苏大学 计算机科学与通信工程学院，江苏 镇江212013）

0 引 言

在AVS、H.264等标准中，运动估计是其编码压缩的核心技术，采用多参考帧、高精度运动矢量等技术有效降低了视频帧间的时间冗余，很好提高了压缩效率，但是运动估计部分计算复杂度较高，通常约占全部编码时间的50%以上。运动估计分为整像素运动估计和亚像素运动估计，整像素运动估计快速算法目前已经较为成熟，整像素的搜索点数已经控制在个位数范围内，从而亚像素运动估计计算量占整个运动估计过程计算量的比重更大，因此也是研究的热点内容之一。

整像素的运动估计发展相对较久，也出现了很多快速搜索算法，主要包括：三步搜索算法（TSS），新三步搜索法（NTSS），四步搜索算法（FSS），菱形搜索算法（DS），基于块的梯度下降法（BBGDS），六边形搜索算法（HEX－BS），非对称十字形多层次六边形格点搜索算法（UMHexagonS）等［1］。在整像素快速搜索算法当中，由于UMHexagonS算法［2］相对于原快速全搜索算法，可节约90%以上的运算量，不会受到码率以及运动图像剧烈程度等因素太大影响，能够保持较好率失真性能，而且运算量较低，因此目前应用较广泛。亚像素快速搜索算法也经历了一段时间的发展，取得一些成果，目前比较典型的算法有：基于分像素的抛物线预测算法（PPFPS），该算法利用SAD函数在最优点周围呈现凸函数的特性，可以先得到最优1/2亚像素点，然后根据最优点和次优点判断最优1/4亚像素点，缩小了搜索范围［3］；基于运动补偿误差的数学模型快速算法，在得到最优整像素点基础上，利用其与周围的8个整像素点的运动补偿误差值求出模型系数，然后利用得到的模型估计分像素位置的绝对误差和（SAD）值，从而求出最优的分像素位置，计算量较大［4］；基于 MSE（均方误差）的小数像素运动估计快速算法，利用了二次曲线D（x）＝ax2＋bx＋c在一定范围内可以取得最小值的特性，从而判断出最优点，计算量大，且不适合在硬件实现［5］。这些算法在减少计算量的同时都增加了软硬件实现复杂度，不适合在AVS中推广开来。

本文提出一种简单亚像素快速搜索算法，通过最佳整像素点及其周围两个1/2像素点的匹配误差值来预测1/2像素点所在区域，并通过阈值判断是否提前结束亚像素点的搜索，避免一些冗余的搜索。并且该算法没有复杂的运算，在保证编码效果的同时很好的提高了效率。

1 亚像素运动估计算法和匹配准则

1.1 AVS中亚像素全搜索算法原理

由于自然物体运动的连续性，视频序列图像中帧间的位移并不是以整像素点为单位的，特别是背景较复杂的序列图像，为了进一步提高搜索精度，目前典型的运动搜索在整像素运动搜索的基础上都增加了亚像素运动搜索部分。AVS标准参考软件整像素运动估计部分采用了目前较成熟的UMHexagonS算法，在得到的最佳整像素点基础上，采用全搜索算法（HPFS）来对亚像素点进行搜索［6］。亚像素运动矢量全搜索算法如图1所示。首先搜索最优整像素点周围8个1/2像素点，然后搜索最优1/2像素点周围8个1/4像素点，共搜索16个点。显然HPFS算法性能是最佳的，但速度比较慢。

图1 HFPS算法

1.2 亚像素运动估计的匹配准则

在亚像素运动搜索过程中，根据已有的亚像素运动估计的匹配准则，计算亚数像素运动估计匹配误差值，选取最小匹配误差点为最优匹配点

2 亚像素运动估计快速算法

在搜索范围大，图像变化剧烈时，整像素运动估计匹配误差曲面不具有单峰性，因此利用单峰性特点进行搜索容易陷入局部最小，亚像素搜索则可以很好的利用这种特性，文献［7－8］统计显示平均约90%以上的亚像素搜索窗内的误差匹配曲面具有单峰曲面的特性，所以可以充分利用这个特性，单峰性的特点是搜索范围内亚像素的匹配值将随着它与搜索范围内全局最小点之间的距离减少而减少，因此没必要同时计算相对方向的亚像素点，因为最小值不可能同时出现在两个方向，只需要计算中心像素点一侧某几个亚像素点的匹配误差值，然后根据一定的准则，快速预测1/2亚像素搜索区域，并通过阈值判断是否提前终止1/4亚像素搜索，尽量减少搜索点数。

2.1 1/2像素的快速运动估计算法

亚像素运动矢量与整像素运动矢量及整像素最优点和次优点有很强的相关性，而且亚像素最优点总是在整像素最优点周围一个像素点距离的范围内［9］，本文所述的1/2像素快速运动估计算法是在UMHexagons快速算法搜索得到最匹配整像素点的基础上，利用最匹配整像素点及其周围2个1/2像素点，预测最匹配1/2像素所在区域，如图2所示。

图2 亚像素搜索

算法具体步骤如下：

步骤1 在搜索最优整像素点过程中，记录最优整像素点匹配函数值J（A），并计算出e和g两个亚像素点的匹配函数值J（e），J（g）；

步骤2 以得到的最优整像素点为中心，将其周围的亚像素点区域分为4个象限，如图2中所示。然后根据如下准则进行最佳1/2像素所在区域的预测：

如果J（e）≤J（A）并且J（g）≤J（A），则只预测Ⅳ象限内的1/2像素点，此时只需再计算f点的匹配函数值，然后选择3个亚像素点中最小者即为最优点；

如果J（e）≤J（A）并且J（g）＞J（A），则只预测Ⅱ象限内的1/2像素点，此时需再计算b，c点的匹配函数值，然后选择3个亚像素点中最小者即为最优点；

如果J（g）≤J（A）并且J（e）＞J（A），则只预测Ⅲ象限内的1/2像素点，此时需再计算d，h点的匹配函数值，然后选择3个亚像素点中最小者即为最优点；

如果J（e）＞J（A）并且J（g）＞J（A），则只预测Ⅰ象限内的1/2像素点，首先计算b，d两点的匹配函数值，如果J（b）＞J（A）并且J（d）＞J（A），则A点为最优点，否则再计算a点匹配函数值，选择3个亚像素点中最小者即为最优点；

步骤3 得到最佳1/2像素点后，则比较其匹配函数值是否小于阈值T。如果小于阈值T，不再进行1/4像素的运动矢量搜索，否则继续搜索。

根据运动的连续性，当前块和相邻块以及相邻帧同位置块有很强相关性，有分析表明，当前块和相邻块以及相邻帧同位置块的匹配误差有很强相关性［10－11］，采用其中的阈值T定义方法如下

式中：MinJ1、MinJ2、MinJ3、MinJ4——当前块的左边块、上边块、右上边块和参考帧中相同位置块在对应模式下的最小匹配误差值，b——当前搜索快像素个数。

2.2 1/4像素的快速运动估计算法

在3.1节搜索得到的最优1/2像素点的基础上预测需搜索的1/4像素点，在1/4像素运动估计搜索算法中，由于运动物体运动量很小，且大部分为水平运动或者垂直运动，故其运动矢量大都集中在X轴方向和Y轴方向上，即在最优1/2像素点或其上下左右4个点的概率比较大。本文利用以下方法来确定最佳1/4像素点：

（1）当最优1/2像素点为最优整像素点时，分别计算上下左右4个1/4像素点（2，4，5，7）的SAD值，并分别与中心整像素点比较，得到SAD值最小者，存在以下3种情况：

1）当水平和垂直方向最小者都为中心整像素点时，则该像素点就是最佳1/4像素点，停止搜索；

2）当水平和垂直方向最小者中只有一个是中心整像素点（如水平方向最小者是中心点，垂直方向最小者为2点），则不是中心整像素点的（2点）即为最佳1/4像素点，停止搜索；

3）当水平和垂直方向最小者都不是中心整像素点时，则比较两方向最小者和相应角上的1/4像素点（如水平方向最小者为4，垂直方向为2，则比较1，2，4），三者中最小者为最佳1/4像素点。

（2）当最优1/2像素点为中心整像素点周围8个1/2像素点，搜索方法同步骤1）；

根据以上分析可知，本文提出的亚像素快速搜索算法共需要搜索3～8个点，相比全搜索算法的16个点，节省了50%～81.25%的计算量。

3 实验结果与分析

实验选取的测试模型是AVS的RM52j。实验中选取news、foreman、silent、paris、coastguard和mobile几个标准测试序列。涵盖了各种特点的序列，具有普遍意义。编码器主要参数为：运动搜索半径为16，Hadamard变换开启，率失真优化开启，编码帧数为100f，帧率为30fps，I帧周期为15，量化参数QP取28、32、36、40几种情况，编码结构为IPPP…，视频序列格式为CIF。

对每个序列采用3种算法进行仿真，为了比较亚像素搜索算法性能，统一采用UMHexagons算法进行整像素运动估计。方法一采用亚像素全搜索算法（HPFS），方法二采用HPFS算法和中心偏倚的亚像素搜索算法混合算法，方法三采用本文的快速亚像素搜索算法。本文只给出了news，silent，coastguard，mobile几个序列在3种搜索算法，不同量化参数情况下，测试序列的PSNR－位率图，如图3～图6所示。

由以上图中可以看出，本文提出的改进的快速搜索算法与全搜索算法（HPFS）以及HPFS算法和中心偏倚的亚像素搜索算法（CBFPS）混合算法相比，改进算法在保证PSNR变化很小和牺牲一定码率的情况下，运动估计耗时得到较大的提高。

量化参数分别为QP＝28、32、36、40时，几种视频序 列 的 亮 度 信 噪 比（PSNR－Y）、运 动 估 计 时 间（MET）以及比特率（Bitrate）变化情况见表1。其中“＋”表示增加，“－”表示减少，Aver表示各个量化参数下的均值。

表1是本文提出的亚像素快速搜索算法与亚像素全搜索算法性能的比较，从表中可以看出：与亚像素全搜索算法相比，改进后的算法在运动估计耗时上显著降低，减少了25.36～34.51%；平均亮度信噪比 PSNR－Y 下降为0.027db～0.053db；平均比特率增加在2%以内。

4 结束语

本文在对AVS的亚像素运动矢量分布特性进行分析的基础上，提出一种改进的快速亚像素搜索算法。该算法充分利用了亚像素搜索窗内的误差匹配曲面普遍地具有单峰曲面的特性，并结合阈值判断提前结束搜索，很好的减少了搜索范围。测试结果表明：改进算法在保证PSNR变化很小和牺牲一定码率的情况下，运动估计耗时大幅度减少，减少了25.36～34.51%。同时该算法实现简单，具有使用灵活、效果明显等特点。

表1 本文提出算法与亚像素全搜索算法性能比较

［1］Kesrarat D，Patanavijit V.Investigation of performance trade off in motion estimation algorithms on sub－pixel displacement［C］.Bangkok，Thailand：Communications and Information Technologies，2010：1013－1018.

［2］Chen Zhibo，Zhou Peng，He Yun.Fast integer pel and fractional pel motion estimation for JVT［R］.Awaji Island，JP：JVT 6th Meeting，2002：5－13.

［3］Chen Zhibo，Du Cheng，Wang Jinghua，et al.PPFPS－aparaboloid prediction based fractional pixel search strategy for H.26L［C］.Beijing：Proc of IEEE International Symposium on Circuits and Systems，2002：9－12.

［4］Jeong J.Fast sub－pixel motion estimation having lower complexity［C］.Seoul，South Korea：Proc of IEEE International Conf on Consumer Electronics，2003：174－175.

［5］ WANG Wei－dong，YAO Qing－dong，LIU Peng.Fast algorithm of fractional pixel accuracy motion estimation［J］.Journal of China Institute of Communications，2003，24（4）：128－132（in Chinese）.［王维东，姚庆栋，刘鹏.小数像素运动估计快速算法［J］.通信学报，2003，24（4）：128－132.］

［6］ZHOU Cheng，TAN Yi－hua，TIAN Jin－wen，et al.A fast algorithm of sub－pixel motion estimation based on AVS［J］.Journal of Image and Graphics，2007，12（9）：1520－1523（in Chinese）.［周城，谭毅华，田金文，等.一种基于AVS的亚像素快速运动估计算法［J］.中国图象图形学报，2007，12（9）：1520－1523.］

［7］LIN Weiyao，Panusopone K，Baylon D M，et al.A fast subpixel motion estimation algorithm for H.264/AVC video coding［J］.IEEE Trans Circuits and Systems for Video Technology，2011，21（2）：237－242.

［8］HUANG Min－qi，HE Ming－hua，WEN Bin.A fast search algorithm for AVS encoding based on sub－pixel motion vectors［J］.Video Engineering，2011，35（1）：10－13（in Chinese）.［黄敏琪，何明华，文斌.基于亚像素运动矢量的AVS编码快速搜索算法［J］.电视技术，2011，35（1）：10－13.］

［9］WEI Jian－yun，PENG Yu－hua，LIU Wei.Fast Subpixel motion estimation algorithm for AVS［J］.Computer Engineering，2010，36（3）：229－231（in Chinese）.［魏建云，彭玉华，刘微.一种AVS亚像素运动估计快速算法［J］.计算机工程，2010，36（3）：229－231.］

［10］YANG Libo，YU Keman，LI Jiang.Prediction－based directional fractional pixel motion estimation for H.264video coding［C］.Hangzhou，China：IEEE International Conference on Acoustics，Speech and Signal Processing，2005：901－904.

［11］WANG Jian，ZHU Xiu－chang.The optimization scheme of subpixel motion estimation algorithm in H.264［J］.Journal of Nanjing Institute of Posts and Telecommunications，2005，25（4）：48－51（in Chinese）.［王建，朱秀昌.H.264中亚像素运动估计算法的优化［J］.南京邮电学院学报，2005，25（4）：48－51.］