基于中心点预测的分数像素运动估计改进算法

熊承义,董朝南

(中南民族大学电子信息工程学院,武汉430074)

H.264是当前最具影响力的多媒体数据压缩编码国际标准之一.与之前编码标准相比,H.264引入了许多新的压缩技术,如多参考帧预测、可变块运动补偿及分数像素运动估计等.较之M PEG-2标准而言,H.264能够在保证视频图像质量的前提下降低50%的比特率[1],但其算法的运算复杂度同时也大幅提高,尤其是运动估计部分占用80%的计算量[2].运动估计分为整数像素运动估计和分数像素运动估计.随着整数像素运动估计快速算法的发展,整数像素搜索点数大大减少,使得分数像素运动估计的计算量占整个运动估计的比重不断加大.因此,减少分数像素运动估计的运算量对于H.264标准尤为重要.

随着对分数像素运动估计的不断研究,人们提出了一些分数像素快速搜索算法.Chen等人[3]提出利用最佳整数点及其周围相邻8个整数点拟合分数像素误差曲面模型,直接预测最佳分数像素点,但一般情况下整数像素搜索过程最后采用小菱形模型,只搜索最佳整数点及其上下左右4个点.W ang等人[4]提出通过邻近像素值的预测,将分数像素点进行分组从而减少搜索点.Shen等人[5]提出利用整数像素点线性拟合分数像素点,并建立提前退出分数像素搜索的模型以减少运算量.Du等人[6]提出的PPHPS算法首先利用整数像素搜索的结果拟合误差曲面,通过误差曲面预测最佳分数像素点的位置,从而省略部分分数像素点的搜索.Chen等人[7]提出的CBFPS算法采用小菱形模型直接对1/4像素点进行搜索以减少运算量,但该方法只应用于分块小于8×8的情况,对于较大的宏块仍采用全搜索法.针对当前分数像素搜索方法存在的不足,本文通过分析分数像素搜索范围误差曲面的特点并结合CBFPS算法,提出一种分数像素运动估计的改进算法.该算法首先利用整数像素搜索的结果建立抛物线模型从而跳过不必要的分数像素搜索,对于8×8及以下分块采用CBFPS算法,当分块较大时,分析搜索中心点及其相邻4个较近分数点的像素值,由分析的结果决定其它分数像素点是否搜索或部分搜索,从而减少分数像素搜索点数.该算法在保证搜索准确率的条件下显著提高了计算速度.

1 H.264中分数像素搜索

在视频编码过程中,运动矢量位移的精度越高,帧间误差越小,传输码率越低,压缩比越高.H.264在整数像素精度搜索完成后,进一步对亮度成分采用1/4像素精度,色度成分1/8像素精度进行阶层式全搜索.搜索过程中采用拉格朗日函数作为运动搜索的代价判断准则.拉格朗日函数如下:

式中:rmv为运动矢量;D(rmv)为当前rmv的块匹配误差;R(rmv)为对当前rmv编码所需的比特数;λ为拉格

图1 分数像素全搜索过程Fig.1 Illustration o f fu ll fractionalp ixel search

2 分数像素运动估计分析

由于搜索范围较大,视频内容较复杂,整数像素运动估计匹配误差曲面一般不是单峰值的,因此在整数像素搜索过程中容易陷入局部最小点.而在分朗日因子.该函数综合考虑了运动矢量rmv的匹配误差和编码开销.

全搜索过程如下:假设A点为整数像素搜索后得到的最优点,然后以该点为中心搜索其周围的8个1/2像素点,比较各点对应的拉格朗日函数值,并找出具有最小函数值的1/2像素位置,假设为F点;完成1/2像素精度搜索之后,以最优1/2像素点F为中心搜索其周围8个1/4像素点,同理找出具有最小拉格朗日函数值的1/4像素点,整个搜索过程共计16个分数像素点,如图1所示.分数像素位置的亮度和色度并不存在于参考图像中,需利用邻近已编码点进行内插而得.因此,搜索的点数越多,运动估计的计算量就越大[8].

为提高编码效率,H.264支持16×16、16×8、8×16、8×8、8×4、4×8 及4×4 等7 种不同大小分块的预测,该7种分块分别称为模式1到模式7.当分块模式为模式1到模式3时,采用全搜索算法,其它模式采用CBFPS算法,如图2所示.该算法首先比较(0,0)和frac-p red-m v的拉格朗日函数值,值较小的作为分数像素搜索起始点,其中frac-p redm v由公式(2)得出.然后以起始点为中心进行小菱形方式搜索,直到搜索中心为最小值为止.式中,p red-m v为当前块左、上及左上(或右上)方向块运动矢量的中值;m v为当前块整数像素的运动矢量.数像素搜索过程中,分数像素位置的亮度和色度值是利用邻近已编码点进行内插得到,所以与整数像素相比,分数像素运动矢量之间的相关性大大增强.通过实验表明,分数像素运动估计时,尤其是在搜索点接近全局中心点时,其误差曲面大都是单峰值的[4].

图2 CBFPS搜索过程Fig.2 Illustration o f CBFPS algo rithm

在全搜索法中,对最佳整数像素周围的所有分数像素点进行搜索.基于搜索中心点周围为单峰值误差曲面的假定,且周围候选的分数像素点成为最优点的概率不等,则使用快速分数像素搜索算法将取得较好的效果.通过统计分析,在各种内容的图像中,超过90%的最优搜索点都在搜索中心[4].但是仍不能忽视分数像素的搜索,因为微小分数像素精度运动矢量的偏差,都可能带来比特率的明显增大.

由图1可知,B,C,D,E,F,G,H,I为整数像素点A周围的8个1/2像素点.本文将其分为两组,其中B,C,D,E4个点与A点的距离相同,分为第1组;F,G,H,I4个点与A点的距离相同,分为第2组.显然,第1组与A点的距离比第2组更小.由上节分析可知,搜索点周围局部的误差曲面为单峰值,并且分数像素位置的亮度和色度像素值由邻近已编码点进行内插而得.因此,与第2组相比,第1组的搜索点与A点的相关性更强.

文献[4]指出在各类内容的图像中,超过90%的最优搜索点都在搜索中心.在进行分数像素搜索的初始阶段能否通过相关性较强的邻近4个1/2像素点而预测最优搜索点是否在搜索中心?此处采用全搜索法对new s-qcif.yuv等6个视频序列进行统计分析.实验中比较B,C,D,E4个点的拉格朗日函数值,若A点为其最小点,而1/2像素搜索完成后的最佳点为F,G,H,I中的某一点,则说明仅通过第1组4个1/2像素点预测A点为最佳点不可靠,计数值N1加1,否则说明预测准确,计数值N2加1,实验中1/2像素搜索总次数用N0表示,统计结果如表1所示.

表1 预测中心的准确度统计结果Tab.1 Statistical resu ltsof accu racy fo r the p redicted center

由表1可知,邻近1/2像素点对最优点是否在搜索中心预测的平均准确率为98.84%.因此,通过计算与最佳整数像素点较近的第1组1/2像素点预测实际的运动矢量是否为搜索中心可信.

由前文分析可知,距离搜索中心较近的点与其相关性较强,因此可以通过第1组1/2像素点运动矢量的变化趋势来预测实际最佳点的位置,从而舍弃部分第2组中1/2像素点的搜索.此处同样对new s-qcif.yuv等6个视频序列进行统计分析.实验中采用全搜索法,计算与最佳整数像素点较近的第1组1/2像素点和较远的第2组1/2像素点的拉格朗日函数值.如果以下4种情况之一发生:a.第1组中最匹配的1/2像素点为图1中的B点,而全搜索后最佳的1/2像素点为图1中的H点或I点;b.第1组中最匹配的1/2像素点为图1中的C点,而全搜索后最佳的1/2像素点为图1中的F点或G点;c.第1组中最匹配的1/2像素点为图1中的D点,而全搜索后最佳的1/2像素点为图1中的G点或I点;d.第1组中最匹配的1/2像素点为图1中的E点,而全搜索后最佳的1/2像素点为图1中的F点或H点,则说明实际的运动矢量变化趋势与第1组中的运动矢量变化趋势方向不同,这样利用第1组1/2像素点预测实际最佳点的位置不准确,此时计数值N1加1,否则说明预测准确,计数值N2加1.实验中1/2像素搜索总次数用表示N0,统计结果如表2所示.

表2 运动矢量相关性分析Tab.2 Co rrelation analysis o fm o tion vecto r

由表2可知,邻近整数像素点的运动矢量趋势与实际的运动矢量趋势相同率达到99.80%.因此,通过计算与最佳整数像素点较近的4个第1组1/2像素点的运动矢量预测实际的运动矢量可信.

3 分数像素运动估计改进算法

3.1 分数像素运动估计跳过条件

H.264标准编码时首先进行整数像素运动估计,然后以最佳整数点为中心进行分数像素精度搜索.当分数像素搜索之后最佳点仍为整数点时,分数像素搜索过程可以直接跳过.整数像素运动估计最后一般利用小菱形模型搜索,因此整数最佳点及其上下左右4个点的拉格朗日函数值都已知.如图1中A,H1,H2,V1,V2点的坐标分别为(0,0),(-1,0),(1,0),(0,-1)和(0,1),其函数值已知,表示为F(A),F(H1),F(H2),F(V1),F(V2).考虑一维情况下(水平方向为例),F(A),F(H1),F(H2)3点可构造一抛物线模型,表达式如下:

式中x0表示F取得最小值时的像素位置,a,x0,b3个未知参数可通过F(A),F(H1),F(H2)的值得出,经推导可得:

当x0在(-1/8,1/8)区间时,F(A)小于F(1/4)和F(-1/4),如图3(a)所示.此时预测在水平方向上最佳整数点的函数值小于其周围的分数像素位置函数值,可跳过分数像素搜索;当x0不在(-1/8,1/8)时,最佳整数点的函数值大于其周围的分数像素位置函数值,如图3(b)所示,则分数像素搜索是必要的.由此可将跳过分数像素搜索的条件归纳为｜x0｜＜1/8,为避免分母部分可能为0的情况,将其转化为:

在垂直方向上同理得:

由此得出跳过分数像素搜索的条件为(5)和(6)式同时成立.

图3 分数像素运动估计误差曲面抛物线模型F ig.3 Parabo licm odel of error surface of fractiona l p ix elM E

3.2 改进的运动估计算法

通过以上分析,本文提出一种改进的分数像素运动估计算法.算法首先利用上节的结论,分析公式(5)和公式(6)是否成立,若成立则直接跳过分数像素运动估计,不成立则进行分数像素运动估计.然后判断分块模式是否为模式4到模式7,若是则采用CB FPS算法,不是则计算与最佳整数像素点邻近4个1/2像素点的拉格朗日函数值,通过对1/2像素点函数值的比较预测实际运动矢量的变化趋势并进行分数像素搜索.以1/2像素精度搜索为例,详细过程如下.

计算整数像素点A及第1组中4个1/2像素点B,C,D,E的拉格朗日函数值,得到函数值最小的1/2像素点,共分为5种情况:

(1)若A点拉格朗日函数值最小,则A点为最佳1/2像素点,搜索结束;

(2)若B点拉格朗日函数值最小,则又分为3种情况:

①D,E两点的函数值相同,则继续搜索F,G两点,得到函数值最小的1/2像素点;

②D,E两点中D点的函数值较小,则只继续搜索F点,得到函数值最小的1/2像素点;

③D,E两点中E点的函数值较小,则只继续搜索G点,得到函数值最小的1/2像素点.

(3)若C点拉格朗日函数值最小,则又分为3种情况:

①D,E两点的函数值相同,则继续搜索H,I两点,得到函数值最小的1/2像素点;

②D,E两点中D点的函数值较小,则只继续搜索H点,得到函数值最小的1/2像素点;

③D,E两点中E点的函数值较小,则只继续搜索I点,得到函数值最小的1/2像素点.

(4)若D点拉格朗日函数值最小,则又分为3种情况:

①B,C两点的函数值相同,则继续搜索F,H两点,得到函数值最小的1/2像素点;

②B,C两点中B点的函数值较小,则只继续搜索F点,得到函数值最小的1/2像素点;

③B,C两点中C点的函数值较小,则只继续搜索H点,得到函数值最小的1/2像素点.

(5)若E点拉格朗日函数值最小,则又分为3种情况:

①B,C两点的函数值相同,则继续搜索G,I两点,得到函数值最小的1/2像素点;

②B,C两点中B点的函数值较小,则只继续搜索G点,得到函数值最小的1/2像素点;

③B,C两点中C点的函数值较小,则只继续搜索I点,得到函数值最小的1/2像素点.

1/4像素精度搜索方法与1/2像素精度搜索方法同理,以1/2像素搜索的最佳点为中心搜索其周围的1/4像素点,并同样分5种情况最终搜索出1/4像素精度的最佳点.在该算法中,1/4像素精度搜索一般只需计算4个分数像素点,极少的分块搜索需计算5个点或6个点.与全搜索法相比,在保证编码质量的情况下搜索的点数明显减少.

4 实验结果及分析

本文采用QC IF格式序列,实验平台为JM 12.2版,帧率30H z,编码帧数为100.第1帧为I帧,其余部分为P帧,参考帧为5帧,熵编码采用CABAC,量化因子QP=28,整数像素部分的运动估计方法为UM HexagonS,实验结果如表3所示.

表3 分数像素搜索算法实验结果Tab.3 Sim u lation resu ltso f fractionalp ixel search algo rithm

由表3可知,本文提出的算法与全搜索法相比,图像的PSNR近似不变,B itrate平均上升4.48%,分数像素平均搜索点数为4.91,比全搜索法的16个点下降69.32%.而CBFPS算法和PPHPS算法的PSNR分别下降0.18dB和0.02dB,B itrate上升0.18%和3.25%,分数像素平均搜索点数下降52.71%和31.25%.从实验结果可以看出,本文算法在大幅提高计算速度的同时较好的保持了编码图像的PSNR和B itrate.

5 结束语

通过分析分数像素运动估计的过程,利用分数像素点之间相关性强及搜索中心点周围局部范围为单峰值误差曲面的特点,提出了一种改进的分数像素运动估计算法.该算法在保证图像质量和增加较少码率的条件下,能有效减少搜索点数,从而使搜索速度显著提高,便于硬件实现,能较好地满足实际应用中实时性的要求.

[1] W iegand T,Su llivan G J,B jon tegaard G,et al.O verview o f the H.264/AVC video coding standard[J]. IEEE T ransactions on C ircuit and System fo r V ideo Techno logy,2003,13(7):560-576.

[2] Chang Jingfu,Jin Jang leou.A quad ratic p red iction based fractional-p ixel m o tion estim ation algo rithm fo r H.264[J].Jou rnalo f V isualComm un ication and Im age Rep resen tation,2006,17(5):1 074-1 089.

[3] Chen Gang,Jia Zhenhong,Chen H e.A fast quarterp ixelm o tion estim ation algo rithm fo r H.264/AVC[J].Op toelectronics L etters,2008,4(1):66-68.

[4] W ang Yu jen,Cheng Chaochung,Chang T iansheuan.A fast fractional pelm o tion estim ation algo rithm fo r H.264/M PEG-4 AVC [J]. IEEE In ternational Sym posium on C ircuits and System s,2006(1):3 974-3 977.

[5] Shen L iquan,Zhang Zhaoyang,L iu Zh i,et al.A n adap tive and fast fractional p ixel search algo rithm in H.264[J].Signal Processing,2007,87(11):2629-2639.

[6] Chen Du,H e Yun,Zheng Jun li.PPHPS-a parabo lic p red iction-based fast half-p ixel search algo rithm fo r very low bit-rate m oving-p ictu re coding[J]. IEEE T ransactions on C ircuits and System s fo r V ideo Techno logy,2003,13(6):514-518.

[7] Chen Zh ibo,Xu Jianfeng,H e Yun,et al. Fast in teger-pel and fractional-pelm o tion estim ation fo r H.264/AVC[J].Jou rnal o f V isual Comm unication and Im age Rep resen tation,2006,17(2):264-290.

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