张 宸, 朱 娟, 王连明, 黄继鹏

(东北师范大学 物理学院, 吉林 长春 130024)

运动估计是视频压缩的核心技术, 视频压缩目前在手机电视、数字卫星广播、数字视频存储等方面得到了普遍应用.在视频压缩编码中, 视频图形序列中存在大量的时间和空间冗余,为了减少时间冗余, 在视频编码标准中采用了基于块匹配的运动估计和运动补偿技术[1]. 在运动估计过程中首先要进行匹配搜索,搜索的对象是宏块, 现有的搜索算法中全搜索算法是最佳块匹配的搜索方法, 但是全搜索的搜索时间很长. 由于运动估计在视频压缩中占了很大一部分, 为了更好更快地完成运动估计的过程,减少运动估计的计算量, 同时又能保证一定的视频质量, 有很多算法可以选择,其中具有代表性的有二维对数搜索法(two-dimensional logarithm)[2-3]、三步搜索法(three step search)、新三步搜索法(new three step search )[4]、四步搜索法(four-step search)[5], 菱形搜索法(diamond search)[6]、六边形搜索算法(hexagon search)[7]等.其中,三步搜素算法因其简单快捷的优点得到大量应用, 同时,人们针对不同的场合对三步搜索算法也做了一些改变. 例如, 2002年杨清永等人提出将传统的三步搜索算法中的前两步的搜索步长减半, 解决了传统三步搜索算法小运动估计效果差等问题[8].2003年文俊等人在分析运动向量场的空间和时间相关性后, 提出对传统三步搜索算法的改进[9]. 2016年张长帅等人提出基于模糊逻辑的三步搜索算法, 将三步搜索算法与模糊理论进行结合, 对三步搜索算法进一步优化[10].尽管近年来的优化算法层出不穷, 算法越来越完善, 但仍有可进步的空间.

以往的一些算法没有关注到运动矢量的中心偏置特性,也没有分析运动矢量分布的方向性,因此存在搜索精度低,搜索点数多等问题.本文提出将三步搜索算法与非对称十字形搜索结合,进行并行运算,减少搜索点,提高编码效率,使算法得到进一步完善.

1 视频压缩基本原理

1.1 运动估计

在H.264视频压缩标准中, 最小的划分单元是宏块, 所有的编码解码流程都是以宏块为单位进行运算的. 运动估计主要包括搜索和矢量运算两部分, 首先将一帧图像分成若干宏块, 这些宏块互相不重叠. 然后根据空间相关性可以在当前帧的前一帧或者前几帧找到与当前块最匹配的块, 这一过程就是搜索过程, 需要用到一些搜索方法, 在给定的搜索窗口里, 根据某些匹配原则进行搜索运算, 找到最佳匹配块. 最后,根据当前块的位移和最佳匹配块的位移得到相对位移, 相对位移也就是运动矢量(motion estimation, MV)[11]. 到此运动估计过程已经完成, 接下来就是对运动矢量进行编码. 简单地说, 运动估计就是研究如何又快又好地找到最佳匹配块的同时计算出MV.

1.2 块匹配原则

数字图像中的图片都是以矩阵的形式存在,每一帧图像都由许许多多的像素点构成,然而在人的视觉中,这些像素点则是一幅完整的图片.这种图像像素概念为块匹配技术带来了便利性.为了搜索出与当前块最匹配的块,比较常用的几种块匹配准则有MSE(mean square error)法、MAD(mean absolute difference/error)法、NCCF(normalized cross-correlation function)法等,由于SAD(sum of absolute differences)法的运算量相对较少,本文选择SAD算法进行匹配.

式中: (i,j)为运动矢量;f和fref分别为当前帧和参考帧的像素值;M,N为宏块的尺寸,各匹配准则值最小时的(i,j)为最佳运动矢量. MSE算法精度最高, 运算量最大, MAD算法和SAD算法精度相同, SAD算法运算量更小, 只涉及减法和求绝对值的运算. 一般选择SAD作为匹配准则.

2 三步搜索算法

2.1 传统的三步法

三步法(three step search, TSS)因其简单,在可视电话和会议电视等低速率视频编码中被广泛使用.传统的三步搜索算法的流程为:第一步,以当前块中心为搜索起点,在距离搜索起点为4的位置划分出一个8×8的搜索窗口,然后如图1所示,标识为1的9个点就是第一步搜索的点,根据匹配原则在9个点中找出最佳匹配块;第二步,将上一步的最佳匹配块的中心设为起点,然后在距离起点为2的位置划分一个4×4的搜索范围,图中标识为2的8个点就是第二步要搜索的点,此时的步长为2,搜索到最佳匹配块后进入第三步;第三步将上一步的最佳匹配块中心设为起点,然后在距离起点距离为1的位置划分出一个2×2的搜索范围,这时搜索步长为1,图中标识为3的点就是最后要搜索的8个点,根据匹配原则找到最佳匹配块并记下此点位移,最后根据此点位置与第一步的搜索中心位置求出相对位移,这个相对位移就是运动矢量.

图1 传统三步搜索算法Fig.1 Traditional TSS algorithm

2.2 非对称三步算法

经大量研究数据表明,运动矢量具有中心偏置特性.因为,无论视频运动剧烈或者缓慢,相邻的两帧图像之间的运动还是很小,所以,运动矢量大部分都是集中在搜索中心附近的.在对多种视频图像序列进行多次试验后,可以发现运动矢量大部分是按照“十”字形来分布的,为了验证这一分布特性,对图2中的m,n,p,q四点的运动矢量进行测试,测试结果如表1所示.

图2 像素位置示意图Fig.2 Pixel position map

由表1可知,绝大多数的像素运动矢量位于m,n,p,q点处,也就是说运动矢量概率以十字形分布,因此本文将十字搜索与三步搜索结合.

表1 像素运动矢量分布特征统计Table 1 Pixel motion vector distribution statistics %

运动矢量具有方向性,自然图像序列的水平运动要高于垂直运动.根据这两个特性提出了非对称十字搜索方法.再结合运动矢量的中心偏置特性,本文先搜索起点附近的较小区域.在三步搜索算法中,一共需要匹配9+8+8=25次,而在本文中,需要判断匹配点是否在水平方向上,所以匹配次数为9+8=17次,9+10=19次,或9+10+8=27次.这样数据的处理时间就大幅减少了,提高了搜索效率.

在传统的三步算法中,都是以中心点为标准进行正方形范围内的串行式搜索,这种搜索虽然比全搜索好很多,但是依然会产生很多的搜索点.又因为第一步的搜索范围太大,没有充分考虑到中心偏置特性,直接将最佳匹配点的位置扩远了.在大量的统计中可以看到在自然的图像序列中,图像的水平运动明显要比垂直方向的运动要剧烈[12],因此可以增加水平方向的搜索点,将传统的三步搜索算法与非对称十字搜索结合,进行并行搜索,如图3所示,改进的三步搜索算法主要步骤如下.

(1) 进行传统三步搜索,按步长为4进行8个点的搜索,同时并行非对称十字搜索,也就是在水平方向上增加步长为2的两个搜索点.所以第一步为图3中实心黑点.

(2) 在第(1)步的搜索点中选出最佳匹配点,计算位移进行判断.如果竖直方向位移为0,进行第(3)步;否则,进行第(4)步.

(3) 此时匹配点在水平方向上,接下来进行步长为1的搜索,需要搜索8个点.加上本身一共9个点,找出最佳匹配点.就是最后要找的匹配点.

(4) 此时匹配点在其他位置,然后按步长为2进行8个点搜索,同时并行非对称十字搜索,在水平方向上增加步长为1的两个搜索点,为图3中右下角空心圆部分.

(5) 同样对最佳匹配点进行判断.如果竖直方向位移为0,则匹配点为最后匹配点.否则进行第(6)步.

(6) 对这时的匹配点进行步长为1的8个点搜索,找出最后的匹配点.

图3 改进的三步搜索算法Fig.3 Improved TSS algorithm

3 实验结果

在Windows 7,MATLAB 2016软件平台中用标准运动序列stefan_cif、foreman_part_qcif、carphone_qcif等进行运动估计,来验证全搜索算法、传统三步搜索算法、改进的三步搜索算法的性能.以stefan_cif图像序列为例,其中图4图5为相邻的两帧图像,图6是两帧图像的帧间差值,图7是在全搜索、传统三步搜索、改进的三步搜索3种不同的搜索算法下的匹配差值.图8是3种搜索算法恢复图像的对比.从压缩算法解码后的效果看,3种压缩算法图像均不失真.

图4 第一帧图像Fig.4 The first frame

全搜索算法是所有算法中精度最高,但是耗时最长,最复杂的一种搜索算法,其核心思想是要遍历图像中的每一点,因此全搜索算法搜索点数最多.实验中,在算法部分增加了对搜索点数的计数功能,统计3种算法的搜索点数,得到表2.从表2中可以看出3组图像的全搜索算法的搜索点数明显大于后2种算法,通过计算可得,本文的搜索算法的搜索点数比全搜索算法平均减少了89%,比传统的三步搜索平均减少了6.5%.

图5 第二帧图像Fig.5 The second frame

图6 帧间差值Fig.6 Frame difference

图7 3种算法的匹配差值Fig.7 Matching difference of the three algorithms(a)—全搜索算法; (b)—传统三步搜索算法; (c)—本文算法.

图8 3种算法恢复后的第二帧图像Fig.8 Images of the second frame after the recovery of three algorithms(a)—全搜索算法; (b)—传统三步搜索算法; (c)—本文算法.

表2 搜索点数对比表Table 2 Search point comparison table

表3 算法时间对比表Table 3 Search time comparison table s

将3种算法的搜索时间进行了比较,如表3.从表3中可以看出本文的搜索算法的搜索时间比全搜索算法平均减少了67%,比传统的三步搜索平均减少了40%.

通过表2表3可以初步判定本文的算法在时间和搜索点数上是有优势的,但是,这种优势可能会导致匹配不到最佳块,因此重构出的图像质量会降低.为了对本文算法进行验证,在算法中引入一种评价图像的客观标准----峰值信噪比(PSNR).它是原图像与被处理图像之间的均方误差(式2)相对于某个数的对数值,单位是dB,见式3.其中,(i,j)为运动矢量,MSE为均方误差,m、n为图像尺寸.I和K分别为原图像和现图像像素点的灰度值.

(3)

由表4可以看出3种算法的信噪比相差不大,可以认为3种方法重构出的图像的图质量相当.但是由于本文算法在搜索点数和搜索时间上有优势,所以总体来看本文算法优于全搜索算法和传统的三步搜索算法.

表4 峰值信噪比对比表Table 4 PSNR comparison table dB

4 结 论

本文在传统的三步搜索算法上结合了非对称十字搜索,将传统的串行运算三步算法进行并行运算,同时采用经典的图像序列,将全搜索算法、传统的三步搜索算法、本文的搜索算法在各方面进行对比.在信噪比变化不大的情况下,本文的算法要比其他两种算法的搜索点数少,降低了搜索时间,从而提高了编码效率.