APP下载

运动估计UMHexagonS算法的分析与优化

2013-10-08袁友伟汪世瑜徐伟雷

关键词:六边形算子矢量

李 勇,袁友伟,汪世瑜,徐伟雷

(杭州电子科技大学计算机学院,浙江杭州310018)

0 引言

运动估计是视频编码和视频处理中广泛使用的一种技术,由于它占据了60%左右的编码时间而严重降低了编码标准H.264的实时性应用。若能找到一种更加有效的方法来化简运动估计过程,在减少编码计算量方面就非常有效,因此,很多人都对快速运动估计算法进行研究[1]。块匹配算法是运动估计技术的主流算法,其基本思想是将每帧图像分成若干块,再为每一块找一个最优匹配的运动矢量,从而提高编码的效率。早期研究的快速匹配算法有交叉法[2]、六边形算法[3]等,但上述这些单一搜索模板的匹配算法非常容易陷入局部最优,不能很好地保证视频质量。于是便产生了一种新的快匹配算法—非对称十字型多层次六边形格点搜索算法(Unsymmetrical-Cross Multi-Hexagon Search,UMHexagonS)。相比全局搜索算法,UMHexagonS算法在计算量上节约了90%以上,不仅减少了出现局部最小点的可能性,还在预测的有效性及鲁棒性两方面有了提高。本文延续了H.264块匹配运动估计中UMHexagonS算法的优化[4],在此基础上做了新的研究,分别引入了基于矢量分布的搜索模板及螺旋式匹配误差法两个优化策略,实验结果表明,运动估计时间的平均减少程度由原来的11.750%提高到现在的16.240%。

1 UMHexagonS算法

UMHexagonS算法的主要原理是利用多个层次多种形状的模板进行块的匹配,并且利用了时空相关性来对运动矢量场[5]进行预测。算法搜索的具体步骤如图1所示。

图1 UMHexagonS算法的搜索过程

(1)初始搜索点的搜索。从初始搜索矢量集S中寻找一个运动矢量作为初始搜索点,该点对应的成本函数值为最小,即最优匹配点,并将该点作为下一步搜索的起始点。

(2)非对称十字型交叉的搜索。自然界有种规律,那就是物体运动在水平方向较垂直方向更剧烈。因此,本文使用非对称十字型来搜索。

(3)不均匀的多层次六边形格点的搜索。首先围绕上一步获得的最优匹配点进行5×5的小矩形窗搜索,接着多层次六边形格点搜素,确定最优匹配点,并以此作为下一起始搜索点。

(4)扩展的六边形搜索。以起始搜索点为中心,首先作六边形搜索,然后再进行菱形搜索,当最优匹配点位于菱形的中心点时,获得的运动矢量就是所求的最佳运动矢量。

2 UMHexagonS算法的具体优化

2.1 基于矢量分布的搜索模板的引入

UMHexagonS算法步骤3中采用了5×5的正方形模板搜索,是属于大范围的非精细搜索。文献[6]在16×16的搜索窗口中得到了最优匹配点的平均分布规律表,结合5×5的搜索模板,本文给出了5×5搜索模板的最优匹配点的分布图,并把25个搜索点分成6类:A为64.934%、B为13.026%、C为1.810%、D为4.286%、E为0.277%、F为1.266%(类后面的百分数为最优匹配点概率)。最优匹配点的分布规律图如图2所示。观察表明,由A、B、C、D、F这5类所构成的运动矢量与总和只差0.277%,为84.322%。由此可以得出,参数R为2的正方形搜索模板的25个搜索点数过多。对搜索点所占的百分比进行分析后,本文引进了3种模板来优化正方形搜索模板,如图3所示。

图2 5×5搜索模板运动矢量分布及柱状图

图3 3种优化模板

图3中,3种模板搜索点的个数分别为21、13、5,搜索点个数的减少可以减少搜索时间,从而提高运动估计效率,但是由于是视频,因此需要保证视频图像的质量,到底使用哪一种优化模板需要通过实验来进行验证。为了对各种优化后的模板进行验证,本文分别选用了Mobile和Container两种序列进行实验测试,实验的结果如表1所示。

表1 3种优化后模板的数据比对

表1的结果表明,3种优化模板信噪比和比特率相差无几,但在运动估计耗时、编码耗时上都所减少,因此只有5个搜索点的钻石搜索模板是确实可行的。

2.2 基于阈值比较的螺旋子集匹配误差法的引入

在UMHexagonS的搜索过程中,算法的其他各个步骤最终都要经过多次的基于绝对误差值和(Sum of Absolute Difference,SAD)的计算,这两种计算都很耗时。此外,在UMHexagonS算法中进行误差匹配的计算是线式搜索,不能很好地反映两个块的匹配程度,影响了编码效率。针对这一不足,本文引进了螺旋子集匹配误差法。螺旋子集匹配误差法的基本思想是:由s_x[m]和s_y[m]构成了一个可由m索引的点,随着m值的增长,这个点将沿着原点作运动,而该运动轨迹类似于螺旋状。螺旋子集匹配法原理图如图4所示,图中的数字0,1,2,…,25即为m,数字所在的位置即为点的位置。

图5为本文提出的螺旋子集匹配误差法的搜索算子与原UMHexagonS算法中匹配误差的搜索算子。图5表明,本文引进的螺旋式搜索算子有两个优点:(1)减少了搜索点数;(2)体现了当前块和参考块的匹配度。改进后的搜索算子对于一般的视频图像序列来说,统计的效率都有明显地提高;而对运动较剧烈的序列来说,峰值信噪比(Peak Signal to Noise Ratio,PSNR)可能会下降,但编码率却有很大提升。

图4 螺旋子集匹配法

图5 匹配误差中原SAD算子和螺旋搜索算子

3 实验结果和分析

本文选用具代表性的3个QCIF测试序列(Y∶U∶V=4∶2∶0):Mobile_qcif、Silent_qcif分别代表了运动复杂到缓慢的实际视频场景,而Highway_qcif代表的是高速运动的序列,JM中配置文件的参数设置为:FramesToBeEncoded=100,FrameRate=30.0,SearchRange=16,NumberReferenceFrames=5,QP=28,其余参数为默认值。将上述的两处优化点同时集成到原UMHexagonS算法中测试。测试的数据结果见表2。

从统计结果可以看出,与原算法相比较,优化后的算法在编码耗时上平均节省了10.683%,在运动估计耗时上平均节省了16.240%,而PSNR基本不变,保持了原有的视频质量。因此,优化后的算法具有视频质量不变、编码耗时降低、改善视频压缩实效性等特点。

表2 UMHexagonS原算法与加入两处优化点后算法的测试结果

4 结束语

本文针对H.264中使用的运动估计算法UMHexagonS进行了深入的研究,并针对其自身存在的不足之处,提出了两个优化点。优化后的算法在视频图像质量基本不变的情况下,通过减少搜索点的个数,实现了编码时间和运动估计时间的下降,从而提高了编码效率。未来将对H.264视频编码的帧内模式选择、帧间预测、熵编码以及码率控制等技术进行研究与优化。

[1]毛小明,鲍可进.一种基于H.264/AVC的高性能快速运动估计算法[J].计算机应用研究,2012,29(4):1 598-1 600.

[2]Ghanbari M.The cross-search algorithm for motion estimation[J].IEEE Transactions on Communications,1990,38(7):950-953.

[3]Zhu C,Lin X,Chau L,etal.Enhanced Hexagonal Search for Fast Block Motion Estimation[J].IEEE Trans on Circuits and Systems for Video Technology,2004,14(10):1 210 -1 214.

[4]叶文龙,袁友伟,汪世瑜,等.H.264块匹配运动估计中UMHexagonS算法的优化[J].计算机工程与应用,2011,47(25):133-136.

[5]Chen Z,Zhou P,He Y,etal.Fast Motion Estimation for JVT[C].Pattaya Thailand:JVT - G016.7th Meeting,2001:7-14.

[6]Tsai T H,Pan Y N.A novel 3-D predict hexagon search algorithm for fast block motion estimation on H.264 video coding[J].Circuits and Systems for Video Technology,2006,16(12):1 542 -1 549.

猜你喜欢

六边形算子矢量
与由分数阶Laplace算子生成的热半群相关的微分变换算子的有界性
知识快餐店 到处都是六边形
矢量三角形法的应用
拟微分算子在Hp(ω)上的有界性
各向异性次Laplace算子和拟p-次Laplace算子的Picone恒等式及其应用
一类Markov模算子半群与相应的算子值Dirichlet型刻画
创意六边形无限翻
怎样剪拼
怎样剪拼
基于矢量最优估计的稳健测向方法