论文部分内容阅读
摘 要：块匹配运动估计算法是实时视频编解码技术的研究重点。为降低视频编码中运动估计的计算复杂度，考虑到现实序列运动矢量的分布存在方向性，文章提出了基于块匹配的自适应快速运动估计算法。该算法在运动估计的初始阶段，利用相邻宏块间的空间相关性来预测初始搜索点的位置，使搜索起点更接近理想的最优匹配点；在搜索过程中引入具有方向特征的非对称十字形搜索模型，加快了搜索速度。实验结果表明该算法具有很好的性能。
关键词：运动估计；非对称十字形算法；中心偏置；块匹配
0 引言
降低帧间的冗余是视频数据压缩的关键，而实现这一步的重要环节是运动估计和运动补偿。运动估计的目的在于降低视频数据的时间冗余。块匹配算法(BMA)是成功应用于视频压缩的运动估计方法之一，它已成为视频编码与标准(如ITU-T H.261、H.263、MPEG-1、2、4)中不可缺少的部分。目前，能够很好地降低帧间冗余的算法是全搜索块匹配算法，但是该算法由于巨大的计算量而很难满足实时应用要求。后来出现了许多快速块匹配算法，如：二维对数法(TDL)、三步搜索法(3SS)、新三步搜索法(N3SS)、四步法(4SS)、基于块的梯度下降搜索法(BBGDS)、菱形搜索法(DS)以及六边形搜索算法(HEXBS)等，这些算法或是搜索步长过长或是模型单一，易使搜索陷入局部最小。
最近出现了一种“非对称十字形搜索(UDCS)”算法，该算法考虑图像序列的中心偏置特性，在搜索的初始阶段采用大、小十字搜索模型。在搜索过程中，该算法还采用非对称的水平或垂直十字模型以适应现实序列具有对象或场景运动的方向性的特点。由于很好地考虑了中心偏置特性和运动方向性的特点，UDCS在保持图像质量的前提下大大降低了运动估算的复杂度。本文将该算法的主要思想引入到预测法中，提出了“自适应的非对称十字形搜索(A-UDCS)”算法。
1 自适应搜索算法
由于运动矢量的概率分布具有中心偏置特性，因此在各种非预测的基于块的快速运动估计算法中，都是以搜索窗的中心为搜索起点的。然而，“运动矢量概率分布的中心偏置特性”是一个统计结果，它特别适合小运动量的图像序列，而对于大运动量的图像序列，其中心偏置特性就比较差。也就是说，有些序列的运动矢量并不一定集中在搜索窗的中心范围内。图1(a)是Garden序列的运动矢量(以搜索窗中心为参考中心)概率分布情况。从图中可以看出，Garden的运动矢量大量集中在(1，0)点(占42.4％)，主要分布在(1，0)点、(2，0)点和(3，0)点(共占77.1％)。运动矢量的概率分布相对(0，0)点整体偏移，搜索窗中心的菱形区域内的运动矢量的分布概率为68.2％，其中心偏置特性比较差。
为了使搜索起点更接近最优匹配点，出现了先预测、再搜索的方法。只要选择合适的搜索模型和终止准则进行搜索，使用该方法最终可以获得具有足够精度的运动矢量。预测法能显著减少搜索点的数目，降低计算量。图1(b)是Garden序列的运动矢量(以预测的搜索起点为参考中心)概率分布情况，其运动矢量绝大部分在(0，0)点(占66.2％)、(1，0)点(占10％)及(－1,0)点(占5，3％)，以预测的搜索起点为中心的菱形区域的运动矢量的分布概率为90，7％。由此可见，以预测的搜索起点为参考中心的运动矢量分布的“中心偏置特性”(这里称之为“预测点偏置特性”)要远好于以搜索窗中心为参考中心的中心偏置特性。显然，小运动量图像序列的预测点偏置特性也好于中心偏置特性，因此，在预测的基础上进行搜索将比在没有预测的情况下进行的搜索能更快地获得最优匹配点。
2 自适应的非对称十字形搜索算法(A－UDCS)
2．1 搜索起始点和搜索方向的预测
运动对象和场景的整体性和视频运动的连续性决定了视频图像序列在时域和空域里必然存在相关性，因此，在空域预测中可以作以下两个假设：①相邻宏块包含相同的视频对象或场景；②相邻的宏块具有相同或相似的运动特征。根据这两个假设，当前块的运动矢量可利用与其相邻块的运动矢量来预测。实验证明，当前宏块与其左、上、上右三个相邻宏块的运动关系最为密切，且使用左、上、上右三个相邻宏块的运动矢量的中值来作为当前宏块的运动矢量的预测值可获得较佳效果。也就是说，若当前块相邻的左、上、上右三宏块的运动矢量为MVleft、MVabove和MVabove-right，则预测运动矢量MVainent可用(1)式表达：
MVcurrent=median(MVleft，MVabove，MVabove-right) (1)
在预测到起始搜索点之后，进一步确定最小BDM点成为关键。由于现实运动序列的运动矢量在整体上呈十字形分布，即其水平运动和垂直运动几率大，并且具有极强的沿中心水平和垂直轴偏置分布的方向性，因此，可以将宏块的运动分为水平运动和垂直运动两个方向。如果在搜索前知道宏块的运动方向并在搜索过程中使用带方向性的搜索模型，将会提高搜索效率。图2(a)是一个水平臂比垂直臂长的搜索模型，称为水平十字搜索模型(HCSP)，它在水平方向上的移动速度快于垂直方向。将其用于对具有水平运动特征的宏块的运动估计，既可以加快水平方向上的搜索速度，还可以减少对不必要的点(垂直方向上的点)的匹配，从而减少匹配点的数目。因此，HCSP更适合对具有水平运动特征的运动矢量的搜索。同理，图2(b)是垂直十字搜索模型(VCSP)，它更适合搜索在垂直方向上的运动矢量。
为了在搜索的初始阶段选择正确的搜索模型，需要先预测宏块的运动方向。根据当前宏块与相邻宏块间的密切相关性可知，当前宏块运动方向的预测可由已预测的运动矢量获得。设预测运动矢量的坐标为MVcunrent=(VxVy)，其与水平直线的夹角为θ(0≤θ＜π/2)，其值可用公式(2)表达。
如果θ小于π/4，则认为当前宏块的运动方向为垂直方向；如果θ大于或等于π/4，那么当前宏块在水平方向上运动，属于水平运动。
2．2 自适应搜索过程
A-UDCS采用三个搜索模型(如图2)：小十字搜索模型(SCSP)、水平十字搜索模型(HCSP)和垂直十字搜索模型(VCSP)。在本算法中，首先预测出自适应搜索的搜索起点和宏块的运动方向，然后根据预测的方向选择适当的搜索模型，在搜索过程中根据次最优点的轨迹纠正预测方向并调整搜索模型直到获得最优匹配点。A-UDCS的具体搜索步骤如下：
(1)在搜索的初始阶段，通过预测获得自适应搜索的搜索 起点和宏块的运动方向。根据运动方向(即θ的值)选择初始搜索模型进行块匹配。如果为垂直方向，应选择VCSP；如果为水平方向，则选择HCSP。进入下一步。
(2)通过匹配获得最小BDM点，如果该点在中心，则进入第三步；如果该点不在中心，则以最小BDM点为中心，以连续两个最小BDM点的相对位置关系来重新选择搜索模型：如果两个最小BDM点在水平方向上，选择HCSP；如果两个最小BDM点在垂直方向上，则选择VCSP，并重复本步骤。
(3)以最小BDM点为中心，选择SCSP进行块匹配，并将得到的最小BDM点视为最优匹配点，自适应搜索结束。搜索过程如图3所示。
3 实验结果
实验使用了多个图像序列来验证所提出的算法的性能，包括American(CIF)、Foreman(CIF)、Garden(SIF)及Football(SIF)各100帧。在测试过程中，以平均绝对差和(sAD)作为BDM标准，宏块大小为16×16，搜索窗口为w＝±7。
表1给出了在不同图像序列下各种算法的平均搜索点数和各算法相对全搜索算法的搜索速度比。从表中可以看出，A-UDCS比UDCS算法搜索点数少1.032至4.446点，平均少搜索2.94点，相对UDCS算法速度提高26.99％；而A-UDCS比DS算法平均少搜索9.144点，相对DS算法速度提高53.48％。各算法平均搜索点数总体表现为：A-UDCS
4 结束语
与UDCS相比，A-UDCS利用预测法使算法在搜索的初始阶段就已接近最优匹配点，减少了进一步搜索点的数目。它与传统算法的不同点在于，考虑到了现实序列运动矢量分布的方向性，在搜索过程中根据运动特征选择适当的搜索模型增强了局部搜索的方向性，避免了搜索的盲目性。经测试，A-UDCS比UDCS显示出更为优良的性能。与DS比较，A-UDCS在降低计算代价的同时，保证了PSNR值(图像质量)基本不发生明显的变化，而对运动规律强的序列，A-UDCS表现更好。
关键词：运动估计；非对称十字形算法；中心偏置；块匹配
0 引言
降低帧间的冗余是视频数据压缩的关键，而实现这一步的重要环节是运动估计和运动补偿。运动估计的目的在于降低视频数据的时间冗余。块匹配算法(BMA)是成功应用于视频压缩的运动估计方法之一，它已成为视频编码与标准(如ITU-T H.261、H.263、MPEG-1、2、4)中不可缺少的部分。目前，能够很好地降低帧间冗余的算法是全搜索块匹配算法，但是该算法由于巨大的计算量而很难满足实时应用要求。后来出现了许多快速块匹配算法，如：二维对数法(TDL)、三步搜索法(3SS)、新三步搜索法(N3SS)、四步法(4SS)、基于块的梯度下降搜索法(BBGDS)、菱形搜索法(DS)以及六边形搜索算法(HEXBS)等，这些算法或是搜索步长过长或是模型单一，易使搜索陷入局部最小。
最近出现了一种“非对称十字形搜索(UDCS)”算法，该算法考虑图像序列的中心偏置特性，在搜索的初始阶段采用大、小十字搜索模型。在搜索过程中，该算法还采用非对称的水平或垂直十字模型以适应现实序列具有对象或场景运动的方向性的特点。由于很好地考虑了中心偏置特性和运动方向性的特点，UDCS在保持图像质量的前提下大大降低了运动估算的复杂度。本文将该算法的主要思想引入到预测法中，提出了“自适应的非对称十字形搜索(A-UDCS)”算法。
1 自适应搜索算法
由于运动矢量的概率分布具有中心偏置特性，因此在各种非预测的基于块的快速运动估计算法中，都是以搜索窗的中心为搜索起点的。然而，“运动矢量概率分布的中心偏置特性”是一个统计结果，它特别适合小运动量的图像序列，而对于大运动量的图像序列，其中心偏置特性就比较差。也就是说，有些序列的运动矢量并不一定集中在搜索窗的中心范围内。图1(a)是Garden序列的运动矢量(以搜索窗中心为参考中心)概率分布情况。从图中可以看出，Garden的运动矢量大量集中在(1，0)点(占42.4％)，主要分布在(1，0)点、(2，0)点和(3，0)点(共占77.1％)。运动矢量的概率分布相对(0，0)点整体偏移，搜索窗中心的菱形区域内的运动矢量的分布概率为68.2％，其中心偏置特性比较差。
为了使搜索起点更接近最优匹配点，出现了先预测、再搜索的方法。只要选择合适的搜索模型和终止准则进行搜索，使用该方法最终可以获得具有足够精度的运动矢量。预测法能显著减少搜索点的数目，降低计算量。图1(b)是Garden序列的运动矢量(以预测的搜索起点为参考中心)概率分布情况，其运动矢量绝大部分在(0，0)点(占66.2％)、(1，0)点(占10％)及(－1,0)点(占5，3％)，以预测的搜索起点为中心的菱形区域的运动矢量的分布概率为90，7％。由此可见，以预测的搜索起点为参考中心的运动矢量分布的“中心偏置特性”(这里称之为“预测点偏置特性”)要远好于以搜索窗中心为参考中心的中心偏置特性。显然，小运动量图像序列的预测点偏置特性也好于中心偏置特性，因此，在预测的基础上进行搜索将比在没有预测的情况下进行的搜索能更快地获得最优匹配点。
2 自适应的非对称十字形搜索算法(A－UDCS)
2．1 搜索起始点和搜索方向的预测
运动对象和场景的整体性和视频运动的连续性决定了视频图像序列在时域和空域里必然存在相关性，因此，在空域预测中可以作以下两个假设：①相邻宏块包含相同的视频对象或场景；②相邻的宏块具有相同或相似的运动特征。根据这两个假设，当前块的运动矢量可利用与其相邻块的运动矢量来预测。实验证明，当前宏块与其左、上、上右三个相邻宏块的运动关系最为密切，且使用左、上、上右三个相邻宏块的运动矢量的中值来作为当前宏块的运动矢量的预测值可获得较佳效果。也就是说，若当前块相邻的左、上、上右三宏块的运动矢量为MVleft、MVabove和MVabove-right，则预测运动矢量MVainent可用(1)式表达：
MVcurrent=median(MVleft，MVabove，MVabove-right) (1)
在预测到起始搜索点之后，进一步确定最小BDM点成为关键。由于现实运动序列的运动矢量在整体上呈十字形分布，即其水平运动和垂直运动几率大，并且具有极强的沿中心水平和垂直轴偏置分布的方向性，因此，可以将宏块的运动分为水平运动和垂直运动两个方向。如果在搜索前知道宏块的运动方向并在搜索过程中使用带方向性的搜索模型，将会提高搜索效率。图2(a)是一个水平臂比垂直臂长的搜索模型，称为水平十字搜索模型(HCSP)，它在水平方向上的移动速度快于垂直方向。将其用于对具有水平运动特征的宏块的运动估计，既可以加快水平方向上的搜索速度，还可以减少对不必要的点(垂直方向上的点)的匹配，从而减少匹配点的数目。因此，HCSP更适合对具有水平运动特征的运动矢量的搜索。同理，图2(b)是垂直十字搜索模型(VCSP)，它更适合搜索在垂直方向上的运动矢量。
为了在搜索的初始阶段选择正确的搜索模型，需要先预测宏块的运动方向。根据当前宏块与相邻宏块间的密切相关性可知，当前宏块运动方向的预测可由已预测的运动矢量获得。设预测运动矢量的坐标为MVcunrent=(VxVy)，其与水平直线的夹角为θ(0≤θ＜π/2)，其值可用公式(2)表达。
如果θ小于π/4，则认为当前宏块的运动方向为垂直方向；如果θ大于或等于π/4，那么当前宏块在水平方向上运动，属于水平运动。
2．2 自适应搜索过程
A-UDCS采用三个搜索模型(如图2)：小十字搜索模型(SCSP)、水平十字搜索模型(HCSP)和垂直十字搜索模型(VCSP)。在本算法中，首先预测出自适应搜索的搜索起点和宏块的运动方向，然后根据预测的方向选择适当的搜索模型，在搜索过程中根据次最优点的轨迹纠正预测方向并调整搜索模型直到获得最优匹配点。A-UDCS的具体搜索步骤如下：
(1)在搜索的初始阶段，通过预测获得自适应搜索的搜索 起点和宏块的运动方向。根据运动方向(即θ的值)选择初始搜索模型进行块匹配。如果为垂直方向，应选择VCSP；如果为水平方向，则选择HCSP。进入下一步。
(2)通过匹配获得最小BDM点，如果该点在中心，则进入第三步；如果该点不在中心，则以最小BDM点为中心，以连续两个最小BDM点的相对位置关系来重新选择搜索模型：如果两个最小BDM点在水平方向上，选择HCSP；如果两个最小BDM点在垂直方向上，则选择VCSP，并重复本步骤。
(3)以最小BDM点为中心，选择SCSP进行块匹配，并将得到的最小BDM点视为最优匹配点，自适应搜索结束。搜索过程如图3所示。
3 实验结果
实验使用了多个图像序列来验证所提出的算法的性能，包括American(CIF)、Foreman(CIF)、Garden(SIF)及Football(SIF)各100帧。在测试过程中，以平均绝对差和(sAD)作为BDM标准，宏块大小为16×16，搜索窗口为w＝±7。
表1给出了在不同图像序列下各种算法的平均搜索点数和各算法相对全搜索算法的搜索速度比。从表中可以看出，A-UDCS比UDCS算法搜索点数少1.032至4.446点，平均少搜索2.94点，相对UDCS算法速度提高26.99％；而A-UDCS比DS算法平均少搜索9.144点，相对DS算法速度提高53.48％。各算法平均搜索点数总体表现为：A-UDCS
4 结束语
与UDCS相比，A-UDCS利用预测法使算法在搜索的初始阶段就已接近最优匹配点，减少了进一步搜索点的数目。它与传统算法的不同点在于，考虑到了现实序列运动矢量分布的方向性，在搜索过程中根据运动特征选择适当的搜索模型增强了局部搜索的方向性，避免了搜索的盲目性。经测试，A-UDCS比UDCS显示出更为优良的性能。与DS比较，A-UDCS在降低计算代价的同时，保证了PSNR值(图像质量)基本不发生明显的变化，而对运动规律强的序列，A-UDCS表现更好。