CN101815218B - 基于宏块特征的快速运动估计视频编码方法 - Google Patents

Abstract

本发明方法公开了一种基于宏块运动矢量特征分类的快速运动估计视频编码方法，涉及视频压缩编码领域。本发明包括以下步骤：首先从原始视频数据中提取当前编码宏块的亮度信息；针对整像素运动矢量搜索设计了简洁的运动估计搜索模板，合理分配搜索点；依据率失真准则对当前预测宏块的运动剧烈程度进行了分类，从当前预测宏块的运动特征着手，制定了相应的运动搜索优先停止策略，动态调整运动估计的搜索层数和搜索点数，自适应的选择相应的运动估计搜索准则。本发明方法与视频编码标准H.264中采用的运动估计搜索方法相比较，能有效地加速运动估计搜索过程，减少运动估计耗时，严格控制了码率增加，保证了较好的重构图像质量，实现了快速运动估计编码。

Description

基于宏块特征的快速运动估计视频编码方法

技术领域

本发明涉及视频压缩编码领域，设计和实现了一种基于宏块特征的视频快速运动估计编码压缩方法。

背景技术

H.264/AVC作为ITU和ISO联合制定的最新一代视频编码标准，具有更优的编码压缩性能和抗干扰性能，能够适应不同的网络环境，具有重要的研究价值和应用价值。然而H.264编码效率的提高是以编码器端极高的计算复杂度为代价的，导致了其难以实时应用的缺陷。

研究分析表明，H.264编码器端的计算复杂度的绝大部分来自于不同于以往编码标准的帧间预测编码：支持大小和形状可变的包含16×16，16×8，8×16，8×8，8×4，4×8，4×4七种可变大小块的帧间编码模式(见图1)、1/4像素运动矢量、多参考帧，利用拉格朗日率失真优化ROD(Rate Distortion Optimization)技术选择最优的运动估计和帧间编码模式选择等等。实验分析表明，采用多参考帧全部帧间编码模式的运动估计模块占整个编码器计算量的85％以上；仅采用单参考帧的运动估计模块占整个编码器计算量至少60％以上。因此，巨大的编码时间开销迫切要求降低运动估计模块的计算复杂度。

运动估计(Motion Estimation，ME)，是视频帧间编码中普遍采用的一项核心技术，它也是消除视频数据的时间冗余最基本和最重要的方法，运动估计的优劣直接影响到编码的效率和图像恢复质量，各种算法的研究也一直受到工业界和学术界的关注。

目前已经有很多种不同的运动估计和运动补偿方法，流行的算法主要有两种，一种是像素递归算法，另一种是块匹配算法。相比较像素递归法而言，块匹配法极大的简化了问题，虽然其精度降低了，但其具有位移跟踪能力强，易实现等优点，获得了广泛的应用。目前流行的视频编码标准(H.261/263/264，MPEG1/2/4等)普遍采用基于块匹配的运动估计算法。

块匹配运动估计算法的工作原理如图2所示。在运动估计中，视频帧被分割成大小相等的M×N块，假设块中所有像素都作相同的平移运动，下标t为时间。块在t和t-Δt间隔内的位移称作运动矢量MV(Motion vector)。运动估计是在参考帧F_t-Δt的给定窗口Ω中搜索当前编码块的匹配块，寻找最佳运动矢量的过程。在块匹配方法中，用相关函数相关函数R(x，y)来表示当前宏块与参考宏块之间的相关性函数，R(x，y)越大，表示当前块与预测块之间的相关性越强，二者越匹配。通常使用绝对误差和SAD(Sum of Absolute Difference)来衡量相关性函数的大小。

$\mathrm{SAD}(x,y)=\mathrm{MN}\×\mathrm{MAD}(x,y)=\underset{m=1}{\overset{M}{\mathrm{\Σ}}}\underset{n=1}{\overset{N}{\mathrm{\Σ}}}|f_k(m,n)-f_{k-1}(m+x,n+y)|$

f_k(m，n)表示当前帧宏块的亮度值，f_k-1(m+x，n+y)表示参考帧宏块的亮度值，M，N表示当前宏块的大小，R(x，y)表示当前宏块与参考宏块之间的相关性函数，在这种准则下，当前宏块与预测宏块的相关函数R(x，y)＝1/SAD(x，y)。

在运动估计中，匹配准则对运动估计的精度影响不大，为了进一步降低计算复杂度，

在现有的块匹配运动估计算法中，目前搜索精度最高的是全搜索算法(FS)，但计算复杂度太高，不利于实时应用。为此研究者们提出了各种各样的快速块匹配运动估计算法，如三步法、新三步法、四步法、菱形法、MVFAST和PMVFAST等算法。但是所有的改进算法，在搜索精度上比FS都有不同程度的下降，搜索速度仍难以很好的满足实际要求。因此，有必要寻找更加高效的块匹配运动估计算法。

一般的运动估计包括两个部分：整像素运动估计和由整像素搜索得到的最优点的小数运动估计。特别是快速的整像素运动估计已经得到许多的关注。这是因为传统的分数像素运动估计(比如1/2像素)在整个运动估计的计算量中只占了很少的比例。近期针对H.264/AVC压缩编码中整像素运动估计进行优化算法研究的主要成果有J.M.Zhang等人提出的UMHexagonS(Unsymmetrical-Cross Multi-Hexagon Search)，全称叫“非对称十字型多层次六边形格点搜索算法”，该方法与全搜索算法相比，能降低90％的运动估计计算复杂度，比特率与全搜索算法相比不相上下，平均峰值信噪比(peak signal-to-noise，PSNR)的下降小于0.05dB，同时能保持较好的率失真性能，是目前效果最好的快速搜索算法之一。H.264/AVC从参考软件JM7.6版本开始，采用了UMHexagonS算法，该算法结合了多种搜索算法，在很大程度上提高了预测的有效性和健壮性。包括四个步骤，每个步骤采用了不同的搜索模板(如图3)，基本步骤如下：

步骤1：起始搜索点的预测。

采用中值预测、上层预测、前一帧对应块运动矢量预测、邻近参考帧运动矢量预测等多种预测模式求预测运动矢量MV_pred，使最初的搜索起始点更加接近最佳预测点。

步骤2：非对称十字形搜索。

基于一般的假设，在大多数自然图像序列中，水平运动剧烈程度一般要比垂直方向大得多，因此可采用非对称十字搜索来优化算法。如图3的step2所示，非对称十字形搜索水平搜索范围是垂直搜索范围的2倍。相邻搜索点之间间距取两个像素单位。最佳匹配点将作为下一步搜索的初始搜索中心点。

步骤3：非均匀多层六边形格网搜索。

这一步搜索分为两个阶段完成。

第一阶段Step3-1：以步骤2中确定的最佳匹配点为中心，在其周围4×4的区域内进行5×5个整像素全搜索，如图3中的step3-1所示。

第二阶段Step3-2：以step3-1中确定的最佳匹配点作为起始点为中心，进行非均匀多层六边形格网格搜索，如图3中的step3-2所示。非均匀多层六边形格网搜索用于处理大幅度、不规则运动的情况，算法中统一进行4层非均匀的六边形网格搜索。考虑到实际情况中，自然图像序列水平方向运动幅度一般要大于垂直方向，算法中采用16点的非均匀六边形作为基本搜索模式，如图4所示。

步骤4：扩展对称六边形搜索。

Step4-1：先以步长为2个像素进行对称六边形六点搜索，比较中心点和6个对角点的率失真代价值，以率失真代价值最小的点作为下一次搜索的中心点，直到中心点变为率失真代价值最小的点。如图3的Step4-1所示。

Step4-2：再减小步长，以步长为1个像素进行菱形搜索，重复Step4-1的搜索过程，直到中心点的率失真代价值为最小点时中止。该点即为整像素搜索最佳匹配点。如图3的Step4-2所示。

如前所述，虽然UMHexagonS算法大幅提高了全搜索的运算速度，但该方法对七种帧间编码模式无一例外的采用遍历式的搜索策略，并没有考虑到当前预测宏块的运动特征，其搜索点数仍然较多，搜索策略存在冗余，在提高算法搜索速度方面还存在很大的上升空间。通过研究分析视频编码中整像素的运动估计特点和大量的实验统计数据结果，发现其搜索点数仍旧较多，算法存在冗余现象，搜索规则和搜索模板仍有提升空间，有必要进一步优化。H.264/AVC原有整像素搜索快速运动估计UMHexagonS算法的欠缺，主要表现在以下几方面：

(1)对所有被预测宏块采用统一固定的运动搜索估计方法，没有针对宏块特性进行分析。

(2)搜索半径固定，对于均匀的运动幅度较小的搜索区域，过大的搜索半径对提高运动估计性能作用不大，却花费了较多计算时间。

(3)搜索点数存在冗余现象，没有针对宏块自身特性，无一例外的对所有搜索点数进行遍历似的搜索计算，造成了编码耗时。

发明内容

为了有效减少运动估计过程中搜索点数，加快多参考帧中运动估计的计算速度以及保持、甚至提高运动搜索准确度，本发明从被预测宏块的运动特征着手，根据H.264/AVC标准帧间编码中运动估计的特点，针对整像素运动矢量搜索设计了高效、准确的运动估计搜索匹配模板，制定出相应的运动搜索优先停止策略，提出了一种基于H.264/AVC的运动矢量特征分类的快速运动估计方法，旨在能够以编码效率方面较小的牺牲赢得计算复杂度的大幅降低。实验结果表明本发明方法能够有效地加速运动估计搜索过程，减少计算量，同时可以保持原H.264标准算法中较低的编码码率和较好的重构视频图像质量，实现了计算复杂度和运动估计编码效率的双赢。

本发明具体技术方案为：基于宏块特征的快速运动估计视频编码方法，根据当前预测宏块的特征和帧间预测编码模式设计运动估计搜索模板和动态的快速搜索方法，依据当前被预测宏块的运动剧烈程度，结合帧间预测编码模式的选择结果，动态的调整搜索范围和自适应的选择相应的运动估计搜索准则，从而实现对帧间宏块的快速运动估计预测编码，其特征在于具体包括下述步骤：

步骤1：提取当前被预测宏块的亮度分量值：以当前被预测宏块的亮度信息为编码对象，从当前视频帧中提取被预测宏块的亮度分量信息；

步骤2：确定运动估计搜索模板，分配搜索点：包含四层搜索，随着搜索半径的增加，搜索范围的扩大，使每层的搜索点数逐步递增由内到外，每层上的搜索点数依次为8，8，12，16；

步骤3：确定高准确率的初始搜索点：采用拉格朗日率失真优化(RDO-Rate DistortionOptimization)函数，作为运动估计判决依据，选择率失真意义上最佳的匹配预测块和最优运动矢量，使得运动矢量和残差编码的比特分配最小；利用拉格朗日率失真准则选择最优运动矢量问题可描述为：

J_motion(mv，ref|λ_motin)＝SAD[s，r(ref，mv)]+λ_motin[R(mv-pred)+R(ref)]       (1)

(1)式中J_motion为当前预测的运动矢量的率失真代价值RDcost_motion；s为当前宏块像素值；mv是当前矢量，pred为预测矢量；ref为选择的参考帧；r(ref，mv)为参考宏块的像素值；R是运动矢量进行差分编码消耗的比特数，包括运动矢量与其预测值的差值的编码比特数和参考帧的编码比特数；λ_motion为拉格朗日乘子；SAD(Sum of absolute difference)为当前块与参考块像素之间的绝对误差和；

$\mathrm{SAD}[s,r(\mathrm{ref},\mathrm{mv})]=\underset{x=1}{\overset{B_1}{\mathrm{\Σ}}}\underset{y=1}{\overset{B_2}{\mathrm{\Σ}}}|s(x,y)-r(x-m_x,y-m_y)|---\left(2\right)$

公式(2)中B₁和B₂分别表示块的水平像素数和垂直像素数，根据不同的帧间预测模式，其取值可为16，8，4；s(x，y)为当前宏块像素值；r(x，y)为参考宏块的像素值，m_x和m_y分别表示水平和垂直方向的位移量；

利用拉格朗日率失真准则选择最优模式的问题可表述为：

J_mode(s，c，MODE|λ_mode)＝SSD(s，c，MODE|QP)+λ_mode×R(s，c，MODE|QP)  (3)

公式(3)中，MODE表示当前宏块的一种帧间编码模式；J_mode(s，c，MODE|λ_mode)表示MODE模式下的率失真代价值RDcost_mode；s为原始的视频信号；c为采用MODE模式编码后的重构视频信号；λ_mode为拉格朗日乘子；R(s，c，MODE|QP)是与模式和量化参数有关的包括宏块头信息、运动矢量和所有DCT块信息的总的二进制位数，它是通过对块进行实际的编码后获得的，所以其运算量较大；QP是编码量化步长；SSD(s，c，MODE)(Sum of SquareDifference)为原始信号与重构信号之间的平方差值和，即：

$\mathrm{SSD}(s,c,\mathrm{MODE}|\mathrm{QP})=\underset{i=1,j=1}{\overset{B_1,B_2}{\mathrm{\Σ}}}{\left(S_Y\right[x,y]-C_Y[x,y,\mathrm{MPDE}\left|\mathrm{QP}\right])}^2+$

$\underset{i=1,j=1}{\overset{B_1,B_2}{\mathrm{\Σ}}}{\left(S_U\right[x,y]-C_U[x,y,\mathrm{MPDE}\left|\mathrm{QP}\right])}^2+---\left(4\right)$

$\underset{i=1,j=1}{\overset{B_1,B_2}{\mathrm{\Σ}}}{\left(S_V\right[x,y]-C_V[x,y,\mathrm{MPDE}\left|\mathrm{QP}\right])}^2$

公式(4)式中：B₁和B₂分别表示块的水平像素数和垂直像素数，其取值可为16，8，4；S_Y[x，y]表示源宏块亮度信息的取值，C_Y[x，y，MODE|QP]表示重建宏块的亮度信息的取值；S_U，S_V和C_U，C_V分别表示相应的色差信息的取值；具体包括以下步骤：

步骤3.1：利用三种预测编码模式选取最佳的运动矢量(Motion Vector，MV)，即基于空间域的中值预测MV_{pred_space}；基于H.264标准采用的运动估计多尺寸宏块划分特点的上层预测MV_{pred_uplayer}；基于时间域的参考帧运动矢量预测MV_{pred_ref}；

(a)MV_{pred_space}：中值预测，利用空间相关性，取已求出的当前帧的左、上、右上临块的运动矢量的中间值；

(b)MV_{pred_uplayer}：上层预测，利用H.264运动估计多尺寸宏块划分特点，包含模式1：16×16，模式2：16×8，模式3：8×16，模式4：8×8，模式5：8×4，模式6：4×8，模式7：4×4的分级搜索顺序，取已求出的同位置、上一级up layer、大一倍块的运动矢量；

(c)MV_{pred_ref}：时间域预测，利用时间相关性，根据已求出的前一帧参考帧中的当前块的运动矢量MV_ref按比例进行预测

其中当前宏块所在帧的时间为t，预测宏块所在参考帧的时间为t’；

步骤3.2：相应的SAD值与预测的运动矢量MV具有很强的相关性；将MV_{pred_space}，MV_{pred_uplayer}，MV_{pred_ref}所指向点的率失真代价值分别记为pred_space_mincost，pred_uplayer_mincost，pred_ref_mincost，将具有最小率失真代价值的运动矢量指向点作为初始搜索点，该点将作为下一步非对称十字形搜索的初始搜索中心点；

步骤4：非对称十字形搜索：非对称十字搜索水平搜索范围设为W，垂直搜索范围为水平搜索范围的一半，即为W/2，相邻搜索点之间间距取两个像素单位，则水平方向的搜索点数为W/2；垂直方向的搜索点数为W/4；在非对称十字形搜索中共有W/2+W/4＝3W/4个候选搜索点；本步骤在这3W/4个候选搜索点中确定的最佳匹配点作为下一步非均匀多层六边形格网格搜索的初始搜索中心点；

步骤5：判断当前宏块运动剧烈程度：将当前预测宏块按剧烈程度分为三个档次，即运动剧烈程度较低、运动剧烈程度中等、运动剧烈程度较高；当前预测宏块运动剧烈程度的判断方法如下：

步骤5.1：根据公式(1)计算当前预测宏块的运动矢量的率失真代价值记为RDcost_motion，根据公式(3)计算当前预测宏块在mode模式下的率失真代值记为RDcost_mode，从中选取具有最小预测的率失真代价值，记为RD_mincost，即：RD_mincost＝min{Pred_space_mincost，Pred_uplayer_mincost，Pred_ref_mincost}；

步骤5.2：依据初始搜索点选择的运动矢量预测方式确定pred_mincost的值：

如果在步骤3中确定的初始搜索点采用时间域预测方式的运动矢量，则pred_mincost＝pred_ref_mincost；

如果在步骤3中确定的初始搜索点没有采用时间预测方式的运动矢量，再分为两类情况：

若当前运动估计预测宏块的帧间编码模式选择的是16×16大尺寸模式，则pred_mincost＝pred_space_mincost；

若当前运动估计预测宏块的帧间编码模式选择的不是16×16大尺寸模式，则pred_mincost＝pred_uplayer_mincost；

步骤5.3：计算运动剧烈程度调整因子γ，δ：

$\mathrm{\γ}=\frac{\mathrm{Bsize}\left[\mathrm{blocktype}\right]}{\mathrm{pred}\_\min \cos t^2}-{\mathrm{\α}}_{\mathrm{Radii}1}\left[\mathrm{blocktype}\right]$ (5)

$\mathrm{\δ}=\frac{\mathrm{Bsize}\left[\mathrm{blocktype}\right]}{\mathrm{pred}\_\min \cos t^2}-{\mathrm{\α}}_{\mathrm{Radii}2}\left[\mathrm{blocktype}\right]$

公式(5)中Bsize[blocktype]表示当前预测宏块的大小，其取值可为16，8，4；

矩阵α_Radii1[blocktype]依据7种帧间宏块划分模式，其取值定义为：

α_Radii1[1]＝-0.23；α_Radii1[2]＝-0.23；α_Radii1[3]＝-0.23；

α_Radii1[4]＝-0.25；α_Radii1[5]＝-0.27；α_Radii1[6]＝-0.27；α_Radii1[7]＝-0.28；

矩阵α_Radii2[blocktype]依据7种帧间宏块划分模式，的取值定义为：

α_Radii2[1]＝-2.39；α_Radii2[2]＝-2.40；α_Radii2[3]＝-2.40；

α_Radii2[4]＝-2.41；α_Radii2[5]＝-2.45；α_Radii2[6]＝-2.45；α_Radii2[7]＝-2.48；

步骤5.4：当前预测宏块运动剧烈程度的判断：

当RD_mincost＜(1+γ)×pred_mincost时，判定当前预测宏块的运动剧烈程度较低；

当(1+γ)×pred_mincost＜RD_mincost＜(1+δ)×pred_mincost时，判定当前预测宏块的运动剧烈程度中等；

当RD_mincost＞(1+δ)×pred_mincost时，判定当前预测宏块的运动剧烈程度较高；

步骤6：进行5×5像素全搜索：在步骤5已经判断出当前搜索内容剧烈程度之后，只在搜索内容剧烈程度较低时才以当前预测点为中心，在其周围的4×4区域进行5×5个搜索点数的全搜索；当运动剧烈程度为中等或者较剧烈时则放弃5×5全搜索，直接进入步骤7；

步骤7：非均匀多层六边形网格搜索：依据当前宏块的运动剧烈程度动态选择运动估计搜索层数：采用非均匀六边形搜索作为基本搜索模式，搜索层数最多为4层；运动剧烈程度较低时，只进行2层非均匀六边形网格搜索，每层的搜索点数为8；运动剧烈程度中等时，进行3层非均匀六边形网格搜索，由内到外的搜索点数依次为8，8，12；运动剧烈程度为较高时，才进行4层非均匀六边形网格搜索，由内到外的搜索点数依次为8，8，12，16；本步骤在非均匀六边形网格搜索中确定的最佳匹配点作为步骤8扩展对称六边形搜索的初始搜索中心点；

步骤8：扩展对称六边形搜索：以步骤7确定的最佳匹配点作为本步骤的初始搜索中心点；这里采用两个阶段搜索方式：

第一阶段：先以步长为2个像素进行对称六边形六点搜索，比较中心点和6个对角点的率失真代价值，依据率失真准则以率失真代价值最小点作为下一次搜索的中心点，直到中心点的率失真代价值变为最小点；

第二阶段：再减小步长，以步长为1个像素进行菱形四点搜索，重复第一阶段的搜索过程，依据率失真准则直到中心点的率失真代价值为最小点时终止搜索，该点即为最终确定的整像素搜索最佳匹配点；

步骤9：输出运动估计编码信息到Out.264文件中，并且记录运动估计时间(Total ME timefor sequence)、码率(Bit rate)、峰值信噪比信息(PSNR)，以评价编码算法质量。

本发明方法的快速运动估计搜索核心算法称为NUMHexagonS(New-UMHexagonS)，便于与UMHexagonS算法进行区分与比较。NUMHexagonS中主要包含以下技术：

一、设计更简洁的搜索模板

1.1设计原理一

UMHexagonS算法在步骤step3-2以当前预测起始点为中心，进行多层非均匀六边形格网格搜索时，始终是采用每层均有16个搜索点数的非均匀六边形搜索模板，如图3中的step3-2所示。这样固定每层分布的搜索点数的模板易造成搜索点数的分配不合理。试想，如果位于最内层的半径最小的第一层的非均匀六边形搜索模板上分配16个搜索点数没有浪费的话，那么随着搜索半径的增加，逐步向外扩展的第二层、第三层、第四层的非均匀六边形搜索模板上仍然分配16个搜索点数，必然出现搜索点数不够的现象；相反，如果位于最外层的半径最大的第四层的非均匀六边形搜索模板上分配16个搜索点数足够满足搜索要求的话，那么位于最内层的半径最小的第一层非均匀六边形搜索模板上仍然分配16个搜索点数必然存在搜索点数浪费的现象。一个更加优秀的搜索模板，应该是能够随着搜索半径的增加，即搜索范围的扩大，分布在每层非均匀六边形搜索模板上的搜索点数应随之递增，而不是采取固定搜索点数的搜索模板。

1.2实施技术

将每层固定16个搜索点数的非均匀六边形格点搜索改为可根据半径自动调整搜索点数的非均匀六边形格点搜索，如图5所示。因为原UMHexagonS算法本身具有起点预测准确的特点，因此最佳匹配点在当前预测点附近的可能性较大，为了保持原有算法的预测精度，在位于内层的第一层和第二层的非均匀六边形搜索模板上分配8个点搜索点，随着搜索半径的增加每层的搜索点数也会相应增加，第三层非均匀六边形分配12个搜索点，直到第四层非均匀六边形分配16个搜索点。大量实验证明本发明方法的搜索模板既能保证搜索的精度，又避免了不必要的搜索点数的浪费，节省了运动估计时间。

二、根据宏块特征自适应的选择搜索层数

2.1设计原理二

UMHexagonS算法一旦进入步骤step3-2进行非均匀多层六边形格网格搜索时，不论当前预测宏块的运动特别剧烈程度如何，都只能无一例外的完成全部4层的非均匀六边形搜索之后才能转到下一步搜索，如图3所示。原算法中4层的非均匀六边形搜索点数相当可观，共计4层×16个/层＝64个搜索点。尤其对具有高准确率的起点预测的UMHexagonS算法而言，开始就找到最佳点的概率较大，所以对于均匀的运动剧烈程度较低区域浪费在外层非均匀六边形网格搜索上的点数是不必要的。如果能够根据搜索内容剧烈程度来确定每次进行多层非均匀六边形搜索时的搜索层数将大大节约搜索点数，降低运动估计的计算复杂度，节省运动估计时间。

2.2实施技术

将层数为4的非均匀六边形网格搜索改为搜索层数随搜索内容剧烈程度自适应变化的非均匀六边形网格搜索，动态的选择搜索层数。首先，判断当前预测宏块的剧烈程度，将当前宏块的运动剧烈程度划分为三个档次，即：剧烈程度较低、剧烈程度中等、剧烈程度较高。依据运动剧烈程度确定需要进行的非均匀六边形网格搜索的搜索层数，如图5所示。

●当宏块的运动剧烈程度较低时，只进行第一层和第二层的两层非均匀六边形网格搜索，搜索点数为8+8＝16个；

●当宏块的运动剧烈程度中等时，进行搜索第一层到第三层的三层非均匀六边形网格搜索，搜索点数为8+8+12＝28个；

●当宏块的运动剧烈程度较高时，才进行搜索第一层到第四层的四层非均匀六边形网格搜索，搜索点数为8+8+12+16＝44个。

三、可选择的5×5像素全搜索技术

3.1设计原理三

UMHexagonS算法在步骤Step3-1，以当前预测起始点为中心，在其周围4×4的区域内进行5×5个整像素的全搜索，如图3Step3-1。Step3-1拥有25个搜索点数，计算量显然非常可观。原UMHexagonS算法之所以进行5×5全搜索是因为在进行了高准确率的起点预测之后，当前搜索点很可能就在最佳预测点附近，此时进行5×5全搜索极有可能在5×5范围内找到最佳预测匹配点。但是在搜索内容运动程度比较剧烈时，最佳匹配点在当前预测点附近的概率较低，此时再进行5×5全搜索显然不再适用于运动程度较剧烈的宏块，反而造成了不必要的搜索点数的极大浪费。如果能够根据当前搜索内容的运动剧烈程度自适应的选择是否进行5×5全搜索也将大大节约搜索点数。

3.2实施技术

在判断出当前搜索内容运动剧烈程度之后，只在搜索内容运动剧烈程度较低时才进行5×5全搜索，然后再进行多层次的非均匀六边形网格搜索；当运动剧烈程度为中等或者较剧烈时则放弃5×5全搜索，直接进行多层次的非均匀六边形网格搜索。

本发明的技术思路特征为：

1.本发明延用H.264/AVC标准算法中的率失真准则，选择具有最优意义的率失真代价值的运动矢量作为最优的运动估计预测矢量。利用本发明中提及的三种优化技术，在保证码率少许增加，运动估计精度和视频质量基本不变，维持原有码流结构的前提下，大幅度提高运动估计编码速度。

2.设计本发明方法的运动估计搜索模板，确定搜索模板每层当中的搜索点数，保证搜索点的合理分布。

3.设计运动估计搜索方案，分为六个步骤，即第一步：高准确率的初始搜索点预测；第二步：非对称十字形搜索；第三步：计算当前预测宏块的运动剧烈程度；第四步：根据当前预测宏块的运动剧烈程度，有选择的进行5×5像素全搜索；第五步：根据当前预测宏块的运动剧烈程度，进行非均匀多层六边形格网格搜索；第六步：扩展对称六边形搜索。

综上分析，通过以上三种技术，本发明方法，简化了搜索模板(如图6所示)，有效的设计了搜索点数的合理分布，节省了运动估计搜索点数，沿用了原标准方法起始点预测准确的优势，充分考虑了当前预测宏块的特征，不仅可以对运动程度较低的宏块直接采用仅有2层的非均匀六边形网格搜索，提前预判的方法实现快速预测；同时又对运动程度较高的宏块舍弃了5×5像素全搜索，保持原标准的4层非均匀六边形网格搜索的方法。这样充分考虑到所有的宏块运动特征，根据其运动剧烈程度，动态选择搜索策略，既能够保证了运动估计的准确度和编码后视频质量，严格控制码率的增长，又能够大幅提高运动估计编码速度，节省了运动估计编码时间。

本发明具有以下有益效果：

大量实验统计数据结果表明，本发明方法与目前H.264中最新采用的UMHexagonS方法相比，在保证运动估计准确度的前提下，严格控制了码率增加，保证了重建视频图像质量基本不变，保持了原有码流结构，有效地减少了搜索点数，大大减少了运动估计耗时，提高了帧间预测编码速度。实现了对帧间宏块的快速运动估计编码。

以下结合附图说明和具体实施方式对本发明作进一步详细说明。

附图说明

图1标准帧间算法预测方法中帧间宏块划分模式；

图2块匹配运动估计示意图；

图3十六个搜索点的非对称六边形搜索模板；

图4UMHexagonS非对称十字交叉多层六边形格网搜索算法示意图；

图5本发明分层次的非均匀六边形网格搜索模板；

图6本发明方法的运动估计搜索方法示意图；

图7本发明方法的技术方案流程图；

图8运动矢量中值预测示意图；

图9运动矢量上层预测示意图；

图10运动矢量时间域预测示意图；

具体实施方式

为了检验本发明提出方法的有效性，选择了具有不同特点的测试序列，如运动较为剧烈的序列Coastguard和Forman；运动较为平缓的序列Akiyo，Miss America和Mother andDaughter；具有较多细节平滑运动的序列Mobile。并且从能够代表视频编码方法优劣的三个性能，即运动估计编码时间、压缩码率和峰值信噪比，将本发明方法与H.264/AVC中采用的UMHexagonS运动估计编码方法进行了比较统计。在性能测试中，采用JVT公布的最新的编码校验模型JM12.2，实验条件配置如下：主机为P4 2.8CPU，512M内存，编码100帧，帧率30f/s码流结构为IPPP，即第一帧采用I帧编码，其余的采用P帧编码，量化系数QP设为28，熵编码为CAVLC，5个参考帧。

由于本方法是针对视频序列中的亮度分量来完成的，在实际使用中先读取一段YUV格式的视频序列，提取其亮度分量信息值，编码器调用本发明设计的帧间宏块快速运动估计编码模块来完成具体的视频压缩编码。

具体实施中，在计算机中完成以下步骤：

第一步：根据编码器配置文件encoder.cfg读入YUV格式的视频序列，按照配置文件中的参数配置编码器。如完成所需要视频序列编码的帧数FramesToBeEncoded；帧率FrameRate；原始视频文件的长宽尺寸SourceWidth，SourceHeight；输出文件名称OutputFile；量化步长QP值QPISlice，QPPSlice；运动估计搜索范围SearchRange；运动估计搜索模式类型SearchMode；允许的参考帧数NumberReferenceFrames；激活率失真代价函数RDOptimization；熵编码类型SymbolMode等参数配置；

第二步：从原始YUV格式的视频文件中读取出视频序列的亮度分量值，按顺序取出需要编码的宏块的亮度分量值；

第三步：确定初始搜索点：对当前预测宏块作中值预测MV_{pred_space}，上层预测MV_{pred_uplayer}和时间域预测MV_{pred_ref}。

中值预测MV_{pred_space}：利用均值预测器，用已求出的、位于当前预测宏块的左、上、右上邻块的运动矢量(MV)的中间值作为中值预测矢量MV_{pred_space}；

中值预测是一种常用的技术，它的理论依据在于块与块之间存在很大的空间相关性，因此当前预测宏块的最佳运动矢量可以由已知的周围邻块的运动矢量预测得到。如图8所示，E为当前预测宏块，其左边相邻宏块为A，上边相邻宏块为B，右上相邻宏块为C，中值预测的计算式如下：

MV_{pred_space}＝median(MV_A，MV_B，MV_C)           (9)

当块A在图片外或者GOB(片组)边界外的时候，MV_{pred_space}用(0，0)替代；当块C在图片外或者GOB(片组)边界外的时候，MV_{pred_space}用块D的运动向量替代，即MV_{pred_space} ^＝MV_D。

上层预测MV_{pred_uplayer}：利用H.264/AVC标准中帧间运动估计多尺寸宏块划分的特点，采用从模式1(16×16)，模式2(16×8)，模式3(8×16)，模式4(8×8)，模式5(8×4)，模式6(4×8)，直到模式7(4×4)的分级搜索顺序从取已求出的、同位置、上一级(up layer)、大一倍尺寸块的运动矢量，如图9所示；(例如，模式5(mode5)(8×4)或模式6(mode6)(4×8)是模式7(mode7)(4×4)的上层，模式4(mode4)(8×8)是模式5(mode5)(8×4)或模式6(mode6)(4×8)的上层)。

时间域预测MVp_{red_ref}：利用时间相关性，取已求出的、前一参考帧中当前块的运动矢量按比例进行预测。由于视频序列的连续性，当前预测宏块在不同的参考帧中的运动矢量也具有一定的相关性。如图10所示：假设当前预测宏块所在帧的时间为t，其前面参考帧所在的时间为t’，若在其前面参考帧中搜索当前块的最佳匹配块时，可以利用当前预测宏块在时间为t’+1的参考帧中的运动矢量来估测出当前预测宏块在时间为t’的参考帧中的运动矢量：

${\mathrm{MV}}_{\mathrm{pred}\_\mathrm{ref}}={\mathrm{MV}}_{\mathrm{ref}}\×\frac{t-t^{,}}{t-t^{,}-1}---\left(10\right)$

类似运动矢量MV，相应的SAD值也具有很强的相关性。将这三种运动矢量预测模式所指向点的率失真代价值分别记为Pred_space_mincost，Pred_uplayer_mincost，Pred_ref_mincost，将具有最小率失真代价值的运动矢量指向点作为初始搜索点，确定初始搜索起始点位置；本发明方法保持了原H.264标准采用的UMHexagonS运动估计算法具有高准确率的起始点预测的特点，使之更加接近最佳的运动估计匹配点位置；本步骤的最佳匹配点将作为下一步非对称十字形搜索的初始搜索中心点；

第四步：进行非对称十字形搜索；基于在大多数自然图像序列中，水平运动剧烈程度一般要比垂直方向大得多的特征。本实施过程中，取W＝32，即开一个大小为32×16的十字形搜索窗，相邻搜索点之间间距取两个像素单位，水平方向的搜索范围是32，搜索点数为16；垂直方向的搜索范围是16，搜索点数为8；在非对称十字形搜索中共有16+8＝24个候选搜索点；根据率失真准则，利用公式(3)对24个搜索点分别计算其运动矢量的率失真代价值，从中选取率失真代价值最小的点作为本步骤的最佳匹配点，将其作为下一步非均匀多层六边形网格搜索步骤中的初始搜索中心点；

第五步：判断当前宏块的剧烈程度：依据率失真代价准则将当前预测宏块按剧烈程度分为三个档次，即运动剧烈程度较低、运动剧烈程度中等、运动剧烈程度较高；当前预测宏块运动剧烈程度的判断方法如下：

根据公式(3)计算当前预测宏块的运动矢量的率失真代价值RDcost_motion，根据公式(5)计算当前预测宏块在mode模式下的率失真代值RDcost_motion，从中选取具有最小预测的率失真代价值，记为RD_mincost，利用公式(7)判断当前预测宏块的运动剧烈程度：

在公式(7)中定义的运动剧烈程度调整因子γ，δ，涉及到的矩阵变量α_Radii1，其附值如下：

AlphaRadii1[1]＝-0.23f；

AlphaRadii1[2]＝-0.23f；

AlphaRadii1[3]＝-0.23f；

AlphaRadii1[4]＝-0.25f；

AlphaRadii1[5]＝-0.27f；

AlphaRadii1[6]＝-0.27f；

AlphaRadii1[7]＝-0.28f；

涉及到的矩阵变量α_Radii2，其附值如下：

AlphaRadii2[1]＝-2.39f；

AlphaRadii2[2]＝-2.40f；

AlphaRadii2[3]＝-2.40f；

AlphaRadii2[4]＝-2.41f；

AlphaRadii2[5]＝-2.45f；

AlphaRadii2[6]＝-2.45f；

第六步：进行5×5像素全搜索：本发明方法在第五步中已经判断出当前搜索内容剧烈程度之后，只在搜索内容剧烈程度较低时才以当前预测点为中心，在其周围的4×4区域进行5×5个搜索点数的全搜索；当运动剧烈程度为中等或者较剧烈时则放弃5×5全搜索，直接进入第七步；

第七步：进行非均匀多层六边形网格搜索；依据当前宏块的运动剧烈程度动态选择运动估计搜索层数：在本发明中采用非均匀六边形搜索作为基本搜索模式，搜索层数最多为4层；根据第六步中判断出的当前预测宏块的运动剧烈程度，确定搜索层数：

以原算法中非对称六边形网格搜索的最内层，即第一层搜索点坐标为例，第一层上的16个搜索点在水平和垂直方向的坐标设置为：

static const int Big_Hexagon_x[16]＝{0，-2，-4，-4，-4，-4，-4，-2，0，2，4，4，4，4，4，2}；

static const int Big_Hexagon_y[16]＝{4，3，2，1，0，-1，-2，-3，-4，-3，-2，-1，0，1，2，3}；

若当前预测宏块的运动剧烈程度较低，则只进行最内2层非均匀六边形网格搜索，每层的搜索点数为8，共计16个搜索点，较原算法节省48个搜索点；

新多层次非对称六边形网格搜索模板，第一层上的8个搜索点水平和垂直方向坐标设置为：

static int Big_Hexagon_x1[8]＝{0，-4，-4，-4，0，4，4，4}；

static int Big_Hexagon_y1[8]＝{4，2，0，-2，-4，-2，0，2}；

第二层上的8个搜索点水平和垂直方向坐标设置为：

static int Big_Hexagon_x2[8]＝{0，-4，-4，-4，0，4，4，4}；

static int Big_Hexagon_y2[8]＝{4，2，0，-2，-4，-2，0，2}；

若当前预测宏块的运动剧烈程度中等，则进行由内到外的3层非均匀六边形网格搜索，由内到外的的搜索点数依次为8，8，12，共计28个搜索点；较原算法节省36个搜索点；

第三层上的12个搜索点水平和垂直方向坐标设置为：

static int Big_Hexagon_x3[12]＝{0，-4，-4，-4，-4，-4，0，4，4，4，4，4}；

static int Big_Hexagon_y3[12]＝{4，2，1，0，-1，-2，-4，-2，-1，0，1，2}；

若当前预测宏块的运动剧烈程度为较高，则进行4层非均匀六边形网格搜索，由内到外的的搜索点数依次为8，8，12，16，共计44个搜索点；较原算法节省20个搜索点；

第四层上的16个搜索点水平和垂直方向坐标设置为：

static int Big_Hexagon_x4[16]＝{0，-2，-4，-4，-4，-4，-4，-2，0，2，4，4，4，4，4，2}；

static int Big_Hexagon_y4[16]＝{4，3，2，1，0，-1，-2，-3，-4，-3，-2，-1，0，1，2，3}；

本步骤在非对称六边形网格搜索中确定的最佳匹配点作为下一步扩展对称六边形搜索的初始搜索中心点；

第八步：扩展对称六边形搜索，以上一步确定的最佳匹配点作为本步骤的初始搜索中心点；分为两个搜索阶段：

算一阶段：先以步长为2个像素点进行对称六边形六点搜索，比较中心点和6个对角点的率失真代价值，依据率失真准则以率失真代价值最小点作为下一次搜索的中心点，直到中心点的率失真代价值变为最小点；

第二阶段：再减小步长，以步长为1个像素点进行菱形模块的搜索，重复第一阶段的搜索过程，依据率失真准则直到中心点的率失真代价值为最小点时终止搜索；该点即为本发明方法确定的整像素搜索最佳匹配点；

菱形模块的搜索点水平和垂直方向的坐标设置为：

static int Diamond_x[4]＝{-1，0，1，0}；

static int Diamond_y[4]＝{0，1，0，-1}；

第九步：结束运动估计搜索，保存相关的运动估计编码信息到输出文件out.264中，并输出编码后的码流。

实验结果如表1。从表1中可以看出，本发明的方法与H.264/AVC标准采用的UMHexagonS运动估计编码方法相比较，峰值信噪比略有增加，平均增加0.007dB，视频质量没有损失；严格控制了码率，平均增加0.29％，保持了原标准算法高压缩比的优越性能；大大缩短了运动估计编码时间，平均节省运动估计编码时间18.46％。实验统计数据有效地验证了本发明的有效性。本发明方法具有良好的可移植性，可与其他快速视频编码方法(如帧间模式选择方法等)相结合，共同提高视频编码速度。

表1.本发明New-UMHexagonS算法与UMHexagonS算法运动估计编码性能比较

Claims (1)

1.基于宏块特征的快速运动估计视频编码方法，根据当前预测宏块的特征和帧间预测编码模式设计运动估计搜索模板和动态的快速搜索方法，依据当前被预测宏块的运动剧烈程度，结合帧间预测编码模式的选择结果，动态的调整搜索范围和自适应的选择相应的运动估计搜索准则，从而实现对帧间宏块的快速运动估计预测编码，其特征在于具体包括下述步骤：

步骤1：提取当前被预测宏块的亮度分量值：以当前被预测宏块的亮度信息为编码对象，从当前视频帧中提取被预测宏块的亮度分量信息；

步骤2：确定运动估计搜索模板，分配搜索点：包含四层搜索，随着搜索半径的增加，搜索范围的扩大，使每层的搜索点数逐步递增由内到外，每层上的搜索点数依次为8，8，12，16；

步骤3：确定高准确率的初始搜索点：采用拉格朗日率失真优化函数，作为运动估计判决依据，选择率失真意义上最佳的匹配预测块和最优运动矢量，使得运动矢量和残差编码的比特分配最小；利用拉格朗日率失真准则选择最优运动矢量问题可描述为：

J_motion(mv，ref|λ_motin)＝SAD[s，r(ref，mv)]+λ_motin[R(mv-pred)+R(ref)]  (1)

(1)式中J_motion为当前预测的运动矢量的率失真代价值RDcost_motion；s为当前宏块像素值；mv是当前矢量，pred为预测矢量；ref为选择的参考帧；r(ref，mv)为参考宏块的像素值；R是运动矢量进行差分编码消耗的比特数，包括运动矢量与其预测值的差值的编码比特数和参考帧的编码比特数；λ_motion为拉格朗日乘子；SAD为当前块与参考块像素之间的绝对误差和；

$\mathrm{SAD}[s,r(\mathrm{ref},\mathrm{mv})]=\underset{x=1}{\overset{B_1}{\mathrm{\Σ}}}\underset{y=1}{\overset{B_2}{\mathrm{\Σ}}}|s(x,y)-r(x-m_x,y-m_y)|---\left(2\right)$

公式(2)中B₁和B₂分别表示块的水平像素数和垂直像素数，根据不同的帧间预测模式，其取值可为16，8，4；s(x，y)为当前宏块像素值；r(x，y)为参考宏块的像素值，m_x和m_y分别表示水平和垂直方向的位移量；

利用拉格朗日率失真准则选择最优模式的问题可表述为：

J_mode(s，c，MODE|λ_mode)＝SSD(s，c，MODE|QP)+λ_mode×R(s，c，MODE|QP)  (3)

公式(3)中，MODE表示当前宏块的一种帧间编码模式；J_mode(s，c，MODE|λ_mode)表示MODE模式下的率失真代价值RDcost_mode；s为原始的视频信号；c为采用MODE模式编码后的重构视频信号；λ_mode为拉格朗日乘子；R(s，c，MODE|QP)是与模式和量化参数有关的包括宏块头信息、运动矢量和所有DCT块信息的总的二进制位数，它是通过对块进行实际的编码后获得的，所以其运算量较大；QP是编码量化步长；SSD(s，c，MODE)为原始信号与重构信号之间的平方差值和，即：

$\mathrm{SSD}(s,c,\mathrm{MODE}|\mathrm{QP})=\underset{i=1,j=1}{\overset{B_1,B_2}{\mathrm{\Σ}}}{\left(S_Y\right[x,y]-C_Y[x,y,\mathrm{MPDE}\left|\mathrm{QP}\right])}^2+$

$\underset{i=1,j=1}{\overset{B_1,B_2}{\mathrm{\Σ}}}{\left(S_U\right[x,y]-C_U[x,y,\mathrm{MPDE}\left|\mathrm{QP}\right])}^2+---\left(4\right)$

$\underset{i=1,j=1}{\overset{B_1,B_2}{\mathrm{\Σ}}}{\left(S_V\right[x,y]-C_V[x,y,\mathrm{MPDE}\left|\mathrm{QP}\right])}^2$

公式(4)式中：B₁和B₂分别表示块的水平像素数和垂直像素数，其取值可为16，8，4；S_Y[x，y]表示源宏块亮度信息的取值，C_Y[x，y，MODE|QP]表示重建宏块的亮度信息的取值；S_U，S_V和C_U，C_V分别表示相应的色差信息的取值；具体包括以下步骤：

步骤3.1：利用三种预测编码模式选取最佳的运动矢量Motion Vector，MV，即基于空间域的中值预测MV_{pred_space}；基于H.264标准采用的运动估计多尺寸宏块划分特点的上层预测MV_{pred_uplayer}；基于时间域的参考帧运动矢量预测MV_{pred_ref}；

(a)MV_{pred_space}：中值预测，利用空间相关性，取已求出的当前帧的左、上、右上临块的运动矢量的中间值；

(b)MV_{pred_uplayer}：上层预测，利用H.264运动估计多尺寸宏块划分特点，包含模式1：

16×16，模式2：16×8，模式3：8×16，模式4：8×8，模式5：8×4，模式6：4×8，模式7：4×4的分级搜索顺序，取已求出的同位置、上一级up layer、大一倍块的运动矢量；

(c)MV_{pred_ref}：时间域预测，利用时间相关性，根据已求出的前一帧参考帧中的当前块的运动矢量MV_ref按比例进行预测

其中当前宏块所在帧的时间为t，预测宏块所在参考帧的时间为t’；

步骤3.2：相应的SAD值与预测的运动矢量MV具有很强的相关性；将MV_{pred_space}，MV_{pred_uplayer}，MV_{pred_ref}所指向点的率失真代价值分别记为pred_space_mincost，pred_uplayer_mincost，pred_ref_mincost，将具有最小率失真代价值的运动矢量指向点作为初始搜索点，该点将作为下一步非对称十字形搜索的初始搜索中心点；

步骤4：非对称十字形搜索：非对称十字搜索水平搜索范围设为W，垂直搜索范围为水平搜索范围的一半，即为W/2，相邻搜索点之间间距取两个像素单位，则水平方向的搜索点数为W/2；垂直方向的搜索点数为W/4；在非对称十字形搜索中共有W/2+W/4＝3W/4个候选搜索点；本步骤在这3W/4个候选搜索点中确定的最佳匹配点作为下一步非均匀多层六边形格网格搜索的初始搜索中心点；

步骤5：判断当前宏块运动剧烈程度：将当前预测宏块按剧烈程度分为三个档次，即运动剧烈程度较低、运动剧烈程度中等、运动剧烈程度较高；当前预测宏块运动剧烈程度的判断方法如下：

步骤5.1：根据公式(1)计算当前预测宏块的运动矢量的率失真代价值记为RDcost_motion，根据公式(3)计算当前预测宏块在mode模式下的率失真代值记为RDcost_mode，从中选取具有最小预测的率失真代价值，记为RD_mincost，即：RD_mincost＝min{Pred_space_mincost，Pred_uplayer_mincost，Pred_ref mincost}；

步骤5.2：依据初始搜索点选择的运动矢量预测方式确定pred_mincost的值：

如果在步骤3中确定的初始搜索点采用时间域预测方式的运动矢量，则pred_mincost＝pred_ref_mincost；

如果在步骤3中确定的初始搜索点没有采用时间预测方式的运动矢量，再分为两类情况：

若当前运动估计预测宏块的帧间编码模式选择的是16×16大尺寸模式，则pred_mincost＝pred_space_mincost；

若当前运动估计预测宏块的帧间编码模式选择的不是16×16大尺寸模式，则pred_mincost＝pred_uplayer_mincost；

步骤5.3：计算运动剧烈程度调整因子γ，δ：

$\mathrm{\γ}=\frac{\mathrm{Bsize}\left[\mathrm{blocktype}\right]}{\mathrm{pred}\_\min \cos t^2}-{\mathrm{\α}}_{\mathrm{Radii}1}\left[\mathrm{blocktype}\right]$ (5)

$\mathrm{\δ}=\frac{\mathrm{Bsize}\left[\mathrm{blocktype}\right]}{\mathrm{pred}\_\min \cos t^2}-{\mathrm{\α}}_{\mathrm{Radii}2}\left[\mathrm{blocktype}\right]$

公式(5)中Bsize[blocktype]表示当前预测宏块的大小，其取值可为16，8，4；

矩阵α_Radii1[blocktype]依据7种帧间宏块划分模式，其取值定义为：

α_Radii1[1]＝-0.23；α_Radii1[2]＝-0.23；α_Radii1[3]＝-0.23；

α_Radii1[4]＝-0.25；α_Radii1[5]＝-0.27；α_Radii1[6]＝-0.27；α_Radii1[7]＝-0.28；

矩阵α_Radii2[blocktype]依据7种帧间宏块划分模式，的取值定义为：

α_Radii2[1]＝-2.39；α_Radii2[2]＝-2.40；α_Radii2[3]＝-2.40；

α_Radii2[4]＝-2.41；α_Radii2[5]＝-2.45；α_Radii2[6]＝-2.45；α_Radii2[7]＝-2.48；

步骤5.4：当前预测宏块运动剧烈程度的判断：

当RD_mincost＜(1+γ)×pred_mincost时，判定当前预测宏块的运动剧烈程度较低；

当(1+γ)×pred_mincost＜RD_mincost＜(1+δ)×pred_mincost时，判定当前预测宏块的运动剧烈程度中等；

当RD_mincost＞(1+δ)×pred_mincost时，判定当前预测宏块的运动剧烈程度较高；

步骤6：进行5×5像素全搜索：在步骤5已经判断出当前搜索内容剧烈程度之后，只在搜索内容剧烈程度较低时才以当前预测点为中心，在其周围的4×4区域进行5×5个搜索点数的全搜索；当运动剧烈程度为中等或者较剧烈时则放弃5×5全搜索，直接进入步骤7；

步骤7：非均匀多层六边形网格搜索：依据当前宏块的运动剧烈程度动态选择运动估计搜索层数：采用非均匀六边形搜索作为基本搜索模式，搜索层数最多为4层；运动剧烈程度较低时，只进行2层非均匀六边形网格搜索，每层的搜索点数为8；运动剧烈程度中等时，进行3层非均匀六边形网格搜索，由内到外的搜索点数依次为8，8，12；运动剧烈程度为较高时，才进行4层非均匀六边形网格搜索，由内到外的搜索点数依次为8，8，12，16；本步骤在非均匀六边形网格搜索中确定的最佳匹配点作为步骤8扩展对称六边形搜索的初始搜索中心点；

步骤8：扩展对称六边形搜索：以步骤7确定的最佳匹配点作为本步骤的初始搜索中心点；这里采用两个阶段搜索方式：

第一阶段：先以步长为2个像素进行对称六边形六点搜索，比较中心点和6个对角点的率失真代价值，依据率失真准则以率失真代价值最小点作为下一次搜索的中心点，直到中心点的率失真代价值变为最小点；

第二阶段：再减小步长，以步长为1个像素进行菱形四点搜索，重复第一阶段的搜索过程，依据率失真准则直到中心点的率失真代价值为最小点时终止搜索，该点即为最终确定的整像素搜索最佳匹配点；

步骤9：输出运动估计编码信息到Out.264文件中，并且记录运动估计时间、码率、峰值信噪比信息，以评价编码算法质量。

Images