基于H.264快速运动估计算法研究

戴小新

（衡阳师范学院 计算机科学系，湖南 衡阳 421002）

H.264是由ITU－T和ISO／IEC组成的联合视频组提出的高度压缩数字视频编解码器标准。H.264最大的优势是具有很高的数据压缩比率，在同等图像质量的条件下，H.264的压缩比是MPEG－2的2倍以上，是MPEG－4的1.5～2倍。然而，其效率的提高是以增加计算复杂度为代价的，视频压缩编码的关键部分是运动估计，其时间开销占整个编码时间的60%以上。因此，以牺牲较少的图像质量为代价来降低运动估的计算复杂度就显得很有必要了。

运动估计快速搜索算法是以牺牲最佳匹配块的运动矢量准确度，来减少搜索计算的复杂度，做到搜索时间与搜索结果的最优平衡。研究者们提出了许多新的算法，比较早的主要有二维对数搜索（TDLS）法、三步搜索（TSS）法和变方向搜索（CDS）法，这些算法在处理小运动视频序列时效果比较好，而对大运动视频序列效果不理想，容易陷入局部最优陷阱；后来又提出了新三步搜索（NTSS）法、四步搜索（FSS）法、梯度下降搜索（BBGDS）法、菱形搜索（DS）法、混合非对称多层次六边形搜索（UMHexagonS）法和六边形搜索（HEXBS）法等算法［1］。其中UMHexagonS算法在一定程度上避免了这一问题，被H.264标准所采用，本文算法与该算法进行比较，作为评估本文算法水平的标准。

在运动估计过程中，如何利用提前终止策略来加速H.264的视频编码，一直是研究者们研究的问题。块匹配运动估计算法由于简单、高效、开销小、易于实现等优点而被大多数视频编码标准所采用，该算法匹配的准则有三种，即平均均方误差（MSE）、平均绝对差（MAD）和归一化函数（NCCF）［2］，为了降低计算复杂度，在运动估计过程中，通常用绝对误差和（SAD）来代替MAD，SAD的定义如下：

1 基于H.264快速运动估计

本文算法对当前宏块在原点的SAD值和预设阈值进行比较，确定候选尺寸块，通过部分像素和多参考帧技术搜索出整像素最佳运动矢量，并以其为搜索中心，通过基于部分像素的亚像素运动估计获得亚像素最佳运动矢量，最终确定运动估计的最佳尺寸块，本文提出的算法就从这三个方面进行改进的。

1.1 块尺寸预选

H.264支持七种尺寸块分割用于运动估计，本文把七种尺寸块分为大尺寸块和小尺寸块两类：16×16、16×8、8×16为大尺寸块，8×8、8×4、4×8、4×4为小尺寸块。在H.264中，宏块的SAD值确定了其运动特性，首先计算出宏块在原点的SAD值，如果SAD值小于预设阈值，则只搜索大尺寸块，否则，搜索所有尺寸块，确定宏块的最佳划分方式。

1.2 整像素匹配

为了减少宏块的运动估计时间，本文所提的算法仅抽取所有像素中具有代表性的一部分像素参与块匹配，按照计算精度不同，本算法设计了两种匹配模板：把当前宏块及其参考块分成4个子块或16个子块，并计算出SAD值，记作SAD（4）或SAD（16）。

步骤描述如下：

（1）计算出初始帧给定尺寸块在零运动矢量（ZMV）和预测运动矢量（PMV）的SAD值，把较小值记作SAD（a），预设的阈值记为T（i）。如果SAD（a）＜T（i），则确定SAD（a）所在点为最佳整像素匹配点，并停止搜索；否则，以SAD（a）所在点为搜索的中心，转至步骤（b）。

（2）以SAD（4）匹配模板和全搜索策略进行分辨率匹配，把具有最小SAD（4）值的点确定为初始匹配点。

（3）把初始匹配点与其八邻域点中具有最小SAD（16）值的点确定为初始帧的最佳匹配点。

（4）除初始帧外，其他帧的初始匹配点由其前一帧的最佳匹配点确定。

（5）以步骤（3）的方法确定当前帧的最佳匹配点。

（6）重复步骤（4）－（5），确定各帧的最佳匹配点。

（7）选择各帧中具有最小SAD（16）值的点作为整像素最佳匹配点。

1.3 亚像素匹配

在进行亚像素搜索时，先搜索位于最佳整像素匹配点相邻的1／2像素点（8个），确定1／2像素最佳点，然后再搜索其相邻的1／4像素点（8个），确定最佳1／4像素点，以其作为最终运动估计矢量，如图1所示，整像素点用黑点表示，1／2像素点用三角形表示，最佳整像素匹配点用O点表示。

图1 亚像素运动估计优化图

实验表明，最佳匹配点一般为SAD值较小的1／2像素点，为了减少计算量，我们只搜索其中概率较大的候选点，如图1，首先把V1、V2、H1、H2四个整像素点的SAD值记为SAD（V1）、SAD（V2）、SAD（H1）、SAD（H2），则本文的亚像素运动估计算法步骤描述如下：

（1）找出V1，V2，H1，H2中SAD值最小的点，并将其命名为A。

（2）从V1，V2，H1，H2中找出A的相邻点中SAD值较小的点，并将其命名为B。如A＝V1，则H1、H2为其相邻点。如果SAD（H2）＜SAD（H1），则B＝H2；反之亦然。

（3）以位于点A和点O中间、点A和点B中间的1／2像素点和O点作为1／2像素候选点。如果：A＝V1、B＝H2，则点5、6和O为候选点。搜索这3个候选点，确定1／2像素最佳匹配点。

（4）通过搜索1／2像素最佳匹配点和其相邻的8个1／4像素点确定1／4像素最佳匹配点。

1.4 算法描述

综上所述，本文的快速运动估计算法描述如下：

（1）计算当前宏块在搜索原点的SAD值，记为SAD（0），预设的阈值记为T（i），如果SAD（0）＜T（i），则跳过小尺寸块；否则搜索所有7种尺寸块。

（2）抽取块中的部分像素，通过多参考帧技术确定整像素最佳匹配点。

（3）以步骤（2）确定的整像素最佳匹配点为搜索中心，通过亚像素匹配确定亚像素最佳匹配点。

（4）重复步骤（2）－（3），对其他尺寸块进行搜索，选择开销最小的尺寸块为最佳运动矢量。

2 实验及结果分析

本算法在JM10.2代码中实现，通过UMHexagonS算法和本文算法与FS算法进行比较，来分析本算法的性能，选取CABAC编码模式在量化系数QP分别为24、28、32、36、40的条件下编码300帧进行测试，选取Akiyo、News、Foreman、Tempete、Mobile、和Stefan为测试序列，取5个参考帧数，格式为IPPP的GOP，搜索半径为16像素，其余编码参数使用默认值。

实验对算法得出的PSNR、码率、序列编码时间和运动估计时间进行了统计，并计算出UMHexagonS算法和本文算法参照FS算法的PSNR变化（△PSNR）、码率增加百分比（△B），编码时间增加百分比（△T），运动估计时间增加百（△MET），因篇幅所限，表1给出了QP＝32下的比较结果，表中正表示增加，负表示减少，（a）为UMHexagonS算法结果，（b）为本文算法结果。从表1可以看出，本文算法与FS算法比较，其运动估计耗时最多降低72.15%，平均降低69%；编码总时间平均降低58%；其PSNR仅减少0.033dB，对图像质量基本没有影响；码率增加最大不超过1.42%，平均仅增加0.657%，压缩比基本保持不变。与UMHexagonS算法比较，本文所提算法在保持了相近的PSNR和码率的情况下，运动估计耗时下降了13%。

表1 QP＝32时算法性能比较

3 结束语

针对H.264中运动估计计算复杂度过高的问题，提出在运动估计过程中使用宏块预测的提前终止策略来缩小搜索范围，并且通过部分像素匹配、多参考帧选取、亚像素匹配，及基于两种匹配模板进行搜索，实验表明，与FS算法和UMHexagonS算法比较，本文算法在保证编码质量的情况下，运动估计耗时平均下降了69%和13%，是一种效率较高的快速运动估计算法。

［1］毛小明，鲍可进.一种基于H.264／AVC的高性能快速运动估计算法［J］.计算机应用，2012（4）：1598－1600.

［2］余兆明，查日勇，黄磊，等.图像编码标准H.264技术［M］.北京：人民邮电出版社，2003.