一种新的基于H.264/AVC的快速块运动估计算法

摘要：为了解决目前快速块运动估计搜索算法容易使系统陷入局部最优陷阱这一问题，本文提出了一种新的基于H.264/AVC的快速块运动估计算法。简要介绍了运动估计算法和部分失真消除算法，给出了基于空间相关性的搜索范围修正方法，并提出了基于PDE算法的最大局部匹配误差算法。通过实验数据测试表明，该算法在缩小搜索点数，提高编码效率上具有较大的优势。

关键词：最大局部匹配误差；空间相关性；部分失真消除；运动估计

中图分类号：TP301.6 文献标识码：A文章编号：1007-9599 (2011)06-0000-02

A New Fast Block Motion Estimation Algorithm Based H.264/AVC

Chen Gaobing,Yang Libo

(School of Electronics and Information Engineering,Changchun University of Science and Technology,Changchun130022,China)

Abstract:In order to solve this problem which the algorithm of fast motion estimation easily cause the system trapped into local optimization, this paper presents a new algorithm of fast block motion estimation based on H.264/AVC.The motion estimation algorithm and partial distortion eliminate algorithm have been briefly introduced,spatial correlation-

based search range adjustment has been give given,and puts forward the maximum partial matching error-based fast PDE algorithm.The experiment shows that this algorithm has many advantages in reducing search points and enhancing the coding efficiency.

Keywords:Maximum partial matching error;Spatial correlation;Partial distortion elimination;Motion estimation

H.264是由ISO/IEC与ITU-T组成的联合视频组(JVT)制定的新一代视频压缩编解码标准。国际电信联盟将该系统命名为H.264/AVC，国际标准化组织和国际电工委员会将其称为14496-10/MPEG-4AVC。

在目前流行的MPEG-2、MPEG-4、H.261、H.263视频编码标准以及新一代的H.264/AVC标准中，基于运动估计（Motion Estimation，ME）的块处理技术已经在消除视频数据冗余方面得到广泛应用。最常见的也是最直接的一种方法是开展全搜索（FS），所有可能的候选在搜索窗内被穷举。然而，这种方法存在计算量较大和复杂度高的问题。在保证很高的编码效率同时，为了减小这种计算代价，近几年出现了许多有效的运动估计算法，如三步搜索法（TSS）、新三步搜索法（NTSS）、四步搜索法（4SS）和基于梯度下降块搜索法（BBGDS）、钻石搜索法（DS）以及六边形搜索法（HEXBS）等等。

上面提到的快速算法在相对小的搜索范围内，能够较好体现与全搜索相当的性能。然而，对于有快速运动块和要求在一个大的搜索范围内保持较高的编码效率的大尺寸视频序列而言，它们极易陷入局部最优问题的陷阱中。为此，本文提出一种具有较好鲁棒性的快速块运动估计算法，拟解决上述这一问题，同时给出了该算法的性能评估。

一、运动估计

（一）运动估计（ME）算法

设初始块大小为 ，在图像中寻求最佳匹配块的位置为 ，在给定搜索范围为R的另一图像中的运动矢量为 ，采用对应块像素差的绝对值总和（SAD）作为匹配判决准则：

(1)

其中 为在R内的最佳运动矢量。则SAD可表示为：

(2)

其中 和 分别表示当前和参考帧。它只计算搜索范围内的各像素块与当前运动块（MB）的绝对差之和，运算量小，不包括乘法，易于硬件实现。

（二）部分失真消除（PDE）算法

为搜索一个匹配块，采用螺旋扫描，初始化匹配误差是候选块在被给定搜索范围中心（ ）的SAD，即 ，这个值有作为一个最小SAD的可能性最高。部分像素的SAD累积到第K个块单元可表示为：

(3)

其中 是按照螺旋扫描路径的重排位置， 是在第K个块单元的局部误差。因此，采用PDE算法进行ME处理可表示为：

(4)

其中n为在块中所有单元总数。

二、快速块运动估计算法提出

（一）基于空间相关性的搜索范围修正

在保证相同质量前提下，本文首先提出基于空间相关性的相邻块匹配算法的搜索范围修正，来缩小ME的搜索窗尺寸。对于当前块，采用聚集在 的超过三个相邻运动矢量的平均算子，初始运动矢量 最先被估计，为：

(5)

则使用 的动态搜索范围D可表示为：

(6)

其中 为权重函数，定义为：

其中 对 取整，R为距离搜索范围 中心的最大距离， 是一个阈值，基于相邻块匹配错误进行线性搜索范围调节。

（二）基于快速PDE算法的最大局部匹配误差方法

结合式（1）和（2），最佳运动矢量在局部匹配误差下的 和 分别表示为：

(7)

(8)

其中 是块中的一组计算单元。 作为一个给定候选块是否被限制的约束条件。

在当前和参考系上，初始块和候选块被分别定位在p和 处。根据式（3），将各个部分的SAD 累积到第K个块单元的累积SAD为：

(9)

可以看到，为了获得可靠的评估，本文提出的估计算法依赖于SAD 的可靠性，一个用于比较的计算单元必须能够代表整个块并反映其中的内容。在块内的一个计算单元的匹配误差不能波动太大，应尽可能的分散到整个块去。因此，本文将一个块分为16个子块，每个子块重新排列为新块，重排方式如图1所示的 子块。

由部分SAD重排累加的 为：(10)

其中 ，M为 ， 和 为每个重排块的起始位置， 。

由此，在 的各个局部SAD可表示为：

(11)

三、算法测试

根据本文提出的算法思想，下面对算法测试执行过程做以下说明：

Step1：首先估计一个初始化运动矢量，按照式（6）获得修正搜索范围D，然后运用式（10）计算原始和候选块在 的总的 ，并设SAD的最小值为 。运用式（8）计算最大局部SAD值 。进入step2，为下一个候选块在螺旋扫描轨迹 上设置K值。

Step2：比较块的累积局部绝对误差和 和 ，若 大，则当前候选块被跳过，算法重复执行本步，K减1，直到K=0。否则，执行step3。

Step3：比较由式（11）得到的 和step1的 。若 大，则当前候选块被跳过，算法回到step2执行，K减1，直到K=0。否则，当前候选块被跳过，算法回到step2执行，K加1。不过，若当K增至 时， 和 分别用式（10）和（8）得到的 和进行更新。当执行完修正搜索范围D后，回到step1准备执行新一轮的预测。

在H.264系统中融入FS、UMHexagonS、S-UMHexagonS和本文算法，分别简测试了akyio，football、foreman、mobile、news等5个内容和运动强弱各不相同的CIF序列。每隔30帧插入一个I帧，其它均为P帧，帧率为25fps；序列长度为60帧，目标码率为512Kbps，测试数据如表1所示。

注：PSNR-峰值信噪比；Pts-搜索点数

从上表可以看出，各个算法的PSNR基本接近，它们的质量相当。然而，对于衡量算法运算复杂度的Pts指标来说，相差就比较大。综合来看，本文提出的算法在搜索点数上是最低的，即便在剧烈运动的football序列上，本文算法也呈现出了较大的速度提升。

参考文献：

[1]T.Wiegand,G.J.Sullivan，G.Bjntegaard et al. Overview of the H.264/AVC video coding standard. IEEE Transactions on Circuits and Systems for Video Technology,2003,13(7):560-576

[2]T.Koga,K.Iinuma,A.Hirano et al.Motion-compensated interframe coding for video conferencing.in:NTC'81.IEEE 1981 National Telecommunications Conference. Innovative Telecommunications-Key to the Future. New Orleans,LA,USA:IEEE,1981.G5.3.1-G5.3.5

[3]Li Reoxiang,Zeng Bing,M.L.Liou. A new three-step search algorithm for block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology,1994,4(4):438-442

[4]Po Lai-Man，Ma Wing-Chung. A novel four-step search algorithm for fast block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology,1996,6(3):313-317

[5]Zhu Shan，Ma Kai-Kuang. A new diamond search algorithm for fast block matching motion estimation. IEEE Transactions on Image Processing,2000,9(2):287-290

[6]阴法明,赵晓铃.用于运动估计的基于梯度下降搜索扩展算法[J].计算机工程与应用,2010,46(33):139-141

[7]杨红生,杨光.针对样品视频的H.264/SVC的快速运动估计算法[J].吉林大学学报(工学版),2010,40(6):1710-1714

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文