CN101547359A - 一种基于运动复杂度的快速运动估计自适应选择方法 - Google Patents

Abstract

一种基于运动复杂度的快速运动估计自适应选择方法，首先，根据视频序列的时间连续性，以前一帧图像的运动复杂度为依据，进行运动复杂度的帧级判断；然后，根据帧级判断的结果，对需要继续进行判断的图像帧，根据视频序列的空间相关性，进行宏块级运动复杂度的判断；最后，根据帧级和宏块级对运动复杂度的判断，为当前宏块选择运动估计方法进行运动估计。本发明在分析了菱形搜索方法和分级运动估计方法优缺点的基础上，利用已有方法的互补性，通过对视频序列进行帧级和宏块级运动复杂度的计算，并结合自适应阈值和提前终止条件的判断，选择出较为合适的搜索方法。实验结果表明本发明可以在保证图像质量的前提下，达到加快运动估计的目的。

Description

一种基于运动复杂度的快速运动估计自适应选择方法

技术领域

本发明涉及一种基于运动复杂度的快速运动估计自适应选择方法

背景技术

运动估计是视频处理系统的一个重要组成部分，是通过对图像序列的分析，得到图像全局运动量或局部运动量的一种重要方法。作为视频编码的一个重要环节，运动估计不仅决定着整个编码过程的速度，还直接影响图像质量。因此，一个好的运动估计方法应该是在不损害编码质量的前提下，尽可能地提高编码效率，实现缩短整个编码时间的目的。

正是由于运动估计在视频编码中的广泛应用，近年来出现了各种快速运动估计方法。总体来说，这些方法可以分为两大类，一类是通过某一种固定的搜索过程得到运动向量，这类方法的共同特点是不考虑视频内容。虽然实现过程简单，但是不能够结合视频内容本身的信息，会出现浪费搜索时间的情况。另一类是基于多种搜索模式下的选择方法，这类方法会根据视频内容的运动情况，在几种备选方法中选择出一种最合适的搜索方法。这类方法考虑到了各种运动估计方法的互补性，可以更有效地提高编码效率，因此有着更广泛的适应性。本发明属于第二类方法。

传统的快速运动估计方法是对不同的视频采用同一种搜索过程，这种方法会在某些情况下获得不错的效果，但是对于运动复杂度变化较为剧烈的视频，会延长整个搜索过程，从而增加视频编码的时间。

发明内容

本发明的目的在于提供一种利用对运动复杂度的判断进行搜索过程选择，在同等编码质量下获得更高的编码效率的基于运动复杂度的快速运动估计自适应选择方法。

为达到上述目的，本发明采用的技术方案是：

1)首先，根据视频序列的时间连续性，以前一帧图像的运动复杂度为依据，进行运动复杂度的帧级判断；

2)然后，根据帧级判断的结果，对需要继续进行判断的图像帧，根据视频序列的空间相关性，进行宏块级运动复杂度的判断；

3)最后，根据帧级和宏块级对运动复杂度的判断，为当前宏块选择运动估计方法进行运动估计。

本发明帧级判断包括以下步骤：

1)计算上一帧图像中宏块与最佳匹配宏块的绝对误差之和，即单帧宏块预测误差mb_SAD：

$\mathrm{mb}\_\mathrm{SAD}=\underset{i=1}{\overset{N}{\mathrm{\Σ}}}{\mathrm{SAD}}_i$

其中SAD_i是第i个宏块与其最佳匹配宏块的绝对误差和(SAD，Sum of AbsoluteDifferences)，N是该帧图像中的宏块总数；

2)计算上一帧图像的纹理复杂度，使用尺寸为3×3的Sobel算子计算图像像素I(i，j)位于(i，j)位置处的像素的灰度值的水平梯度Grad_H(i，j)和垂直梯度Grad_V(i，j)，得到该像素对应的梯度信息值：

gradient(i，j)＝|Grad_H(i，j)|+|Grad_V(i，j)|

整帧图像纹理复杂度的梯度信息gradient由下式得到：

$\mathrm{grad}\mathrm{ient}=\underset{(i,j)\∈I}{\mathrm{\Σ}}\mathrm{grad}\mathrm{ient}(i,j)$

其中i、j分别代表像素对应位置的横、纵坐标，I代表一帧图像像素的集合；

3)进行帧级判断，对单帧宏块预测误差和该帧图像纹理复杂度进行比较，如果纹理复杂度大于或等于单帧宏块预测误差，则认为宏块的预测误差主要来源于图像本身的纹理信息，图像运动较为简单，采用菱形搜索方法；反之则认为图像运动较为复杂，可能需要使用分级运动估计方法，即：

当gradient≥mb_SAD时：flag_HME＝0，进行菱形搜索方法搜索；

当gradient<mb_SAD时：flag_HME＝1，则根据判断的图像帧，根据视频序列的空间相关性，进行宏块级运动复杂度的判断。

本发明宏块级判断包括以下步骤：

1)当前宏块的运动向量预测(MVP，Motion vector prediction)集：该集合由空间相邻宏块(上、下、左上、右上)的运动向量、前一帧相同位置对应的宏块的运动向量以及预测值为零的运动向量(0，0)构成；

2)计算宏块所在区域的运动复杂性：该复杂性用当前宏块的运动向量预测集中预测值的差异性diff_MVP来表示：

$\mathrm{diff}\_\mathrm{MVP}=\underset{i=1}{\overset{\mathrm{MVPnum}}{\mathrm{\&Sigma;}}}(|{\mathrm{Px}}_i-\mathrm{px}|+|{\mathrm{Py}}_i-\mathrm{py}|)$

其中：MVPnum是当前宏块的运动向量预测集中可用的预测值个数，(px，py)是当前宏块的运动向量预测集中最小匹配误差对应的运动向量预测值，(Px_i，Py_i)是当前宏块的运动向量预测集中除去(px，py)以外的预测值；

3)获得宏块级判断的自适应阈值value_dis：该阈值是编码过程中采用菱形搜索方法的宏块的diff_MVP均值；

4)结合前两步得到的运动复杂性和自适应阈值进行宏块级判断：

当diff_MVP>value_dis时，宏块所在区域为复杂运动，使用分级运动估计方法；

当diff_MVP≤value_dis时，宏块所在区域为简单运动，使用菱形搜索方法。

本发明是一种基于视频内容的多模式选择方法。在对各种运动估计方法分析的基础上，结合当前视频内容的运动情况，选择出最为合适的搜索方法。该方法首先对几种经典的运动估计方法进行对比，利用不同方法对不同运动复杂度的视频图像在搜索性能方面的互补性，通过对视频图像内容的运动复杂度进行判断，选择出一种合适的方法进行运动估计。从而减少了不必要的搜索过程，并在保证图像质量的同时提高了运动估计效率。

附图说明

图1是本发明使用的菱形搜索方法的搜索模板；

图2是本发明使用的菱形搜索方法的搜索过程；

图3是本发明使用的分级运动估计方法的两级图像金字塔；

图4是本发明使用的分级运动估计方法的搜索过程；

图5(a)、5(b)是菱形搜索方法DS和分级运动估计方法HME方法在匹配点数和运动估计时间方面的性能对比结果；

图6是本发明提出的基于运动复杂度的快速运动估计自适应选择方法流程；

图7(a)，7(b)，7(c)是对三段测试序列采用DS、HME和帧级自适应(FLA)方法基于平均匹配点数的对比结果。

具体实施方式

下面结合附图对本发明作进一步详细说明。

传统的运动估计方法对不同的视频采用同一种搜索过程，虽然可以获得不错的搜索效果，但由于未考虑视频图像本身的运动复杂度信息，对于运动剧烈程度变化较大的视频序列，其整个搜索过程并非最优，编码效率仍有提升的空间。

本发明提出的方法主要基于对现有的两种典型运动估计方法——菱形搜索方法(DS，Diamond Search)和分级运动估计方法(HME，Hierarchical Motion Estimation)的分析，利用它们之间在搜索性能方面的互补性，同时结合视频图像内容的运动复杂度，为当前宏块选择一个合适的搜索方法，进而从整体上缩短运动估计的时间，提高编码效率。

DS是一种基于搜索模式的快速块匹配方法，它的搜索策略近似于圆形，具有很好的全方向性。该方法从起始点开始按照LDSP(Large Diamond-Shaped Pattern)模板以菱形的形状逐步向外扩展，如果计算的最佳点在中心，则以该点为中心继续按照SDSP(Small Diamond-Shaped Pattern)模板进行细搜索。相应的LDSP、SDSP模板以及搜索过程如图1、图2所示。

HMe属于多分辨率下的块匹配方法，如图3所示，在本发明中该方法采用均值法构造了一个两级图像金字塔，自底部向上，图像分辨率逐渐减小，上层中的一个像素对应下层4*4的图像区域，且上层像素值为下层对应区域的均值。HME的搜索过程属于多级搜索模式，如图4所示，它以低分辨率图像得到的运动向量作为高分辨率图像运动估计的初始值，从整体上缩短运动估计时间。图3、图4中a为Level1中宏块的尺寸，K*a为Level 0中宏块的尺寸，K为两级宏块尺寸的比例因子；

为了比较DS和HME两种方法在搜索性能上的优劣。记mbnum是一帧中宏块的个数，(px_i，py_i)和(x_i，y_i)分别是一帧中第i个宏块搜索的初始位置和得到的最佳位置。定义一帧图像搜索的复杂度为：

[式1]

$\mathrm{complexity}=\underset{i=1}{\overset{\mathrm{mbnum}}{\mathrm{\&Sigma;}}}\left(\right|{\mathrm{px}}_i-x_i|+|{\mathrm{py}}_i-y_i\left|\right)$

对六段运动复杂度不同的视频分别进行10次测试，对每一个complexity值，统计对应的参与宏块匹配计算的像素点数(即匹配点数，因为HME方法中低分辨率图像对一点搜索匹配的计算量和高分辨率图像不同，为了做到标准统一，所以采用了匹配点数)和运动估计时间。随着搜索复杂度的增大，DS和HME两种方法在搜索策略上的差异可以通过图5的一组对比曲线反映。

由以上的分析可以看到，两种方法具有互补性，DS方法简单，适合于运动平缓的视频序列，但是对于运动变化较大的视频序列，比较耗时。相反，HME方法由于采用了由粗到细的定位过程，可以对大的运动向量进行有效估计，但是需要额外地构建塔形结构，这对于背景块和运动向量较小的块来说是没有必要的。为了克服上述技术的限制，本发明提出了一种对运动复杂度进行判断的快速运动估计选择方法。

如图6所示，本发明主要分为两个步骤：1、对视频图像运动复杂度进行帧级判断。2、对帧级判断为可能进行分级运动估计的图像帧继续进行运动复杂度的宏块级判断。根据运动复杂度的判断结果为当前宏块选择合适的方法进行运动估计。

本发明的第一步是对视频图像的运动复杂度进行帧级判断。根据视频序列的时间连续性，将前一帧图像的运动复杂性作为当前帧判断的依据。运动估计中，宏块的预测误差，也就是残差，主要来自两个方面：图像本身的纹理以及运动复杂度。图像纹理越复杂，或者运动越复杂，都会导致宏块预测误差的增大。定义单帧宏块预测误差为该帧图像中宏块与最佳匹配宏块的绝对误差之和。即：

[式2]

$\mathrm{mb}\_\mathrm{SAD}=\underset{i=1}{\overset{N}{\mathrm{\&Sigma;}}}{\mathrm{SAD}}_i$

其中SAD_i是第i个宏块与其最佳匹配宏块的绝对误差和(SAD：Sum of AbsoluteDifferences)，N是该帧图像中的宏块总数。

图像的纹理复杂度可以用图像的梯度信息来描述，本发明使用下式尺寸为3×3的Sobel算子

[式3]

$S_H=\frac{1}{8}\&CenterDot;\left[\begin{array}{ccc}-1& -2& -1\\ 0& 0& 0\\ 1& 2& 1\end{array}\right]$ $S_V=\frac{1}{8}\&CenterDot;\left[\begin{array}{ccc}1& 0& -1\\ 2& 0& -2\\ 1& 0& -1\end{array}\right]$

来计算计算图像像素I(i，j)位于(i，j)位置处的像素的灰度值的水平梯度Grad_H(i，j)和垂直梯度Grad_V(i，j)，得到该像素对应的梯度信息值：

[式4]

gradient(i，j)＝|Grad_H(i，j)|+|Grad_V(i，j)|

则描述整帧图像纹理复杂度的梯度信息gradient可由下式得到：

[式5]

$\mathrm{grad}\mathrm{ient}=\underset{(i,j)\&Element;I}{\mathrm{\&Sigma;}}\mathrm{grad}\mathrm{ient}(i,j)$

其中i、j分别代表像素对应位置的横、纵坐标，I代表一帧图像像素的集合；对单帧宏块预测误差与该帧图像纹理复杂度进行比较，如果纹理复杂度大于或等于单帧宏块预测误差，则认为宏块的预测误差主要来源于图像本身的纹理信息，图像运动较为简单，采用DS方法；反之则认为图像运动较为复杂，可能需要使用HME方法；即：

当gradient≥mb_SAD时：flag_HME＝0，进行DS搜索；

当gradient<mb_SAD时：flag_HME＝1构建图像金字塔，即根据判断的图像帧，根据视频序列的空间相关性，进行宏块级运动复杂度的判断；

本发明的第二步是对确定可以采用HME的图像帧进行宏块级运动复杂度判断。根据视频序列的空间相关性，当前宏块的运动向量预测(MVP：Motion vectorprediction)集可以由空间相邻宏块(上、下、左上、右上)的运动向量、前一帧相同位置对应的宏块的运动向量以及运动向量(0，0)构成。宏块所在区域的运动复杂性用MVP集中预测值的差异性来判断，该差异性用diff_MVP表示：

[式6]

$\mathrm{diff}\_\mathrm{MVP}=\underset{i=1}{\overset{\mathrm{MVPnum}}{\mathrm{\&Sigma;}}}\left(\right|{\mathrm{Px}}_i-\mathrm{Px}|+|{\mathrm{Py}}_i-\mathrm{py}\left|\right)$

其中：MVPnum是MVP集中可用的预测值个数，(px，py)是MVP集中最小匹配误差对应的运动向量预测值，(Px_i，Py_i)是MVP集中除去(px，py)以外的预测值。差异性越大说明该宏块的运动越复杂。为了有效判断宏块所在区域的运动复杂度，本发明使用编码过程中已采用DS方法的宏块的diff_MVP均值(value_dis)作为阈值，即：

当diff_MVP>value_dis时，宏块所在区域为复杂运动，使用HME方法。

当diff_MVP≤value_dis时，宏块所在区域为简单运动，使用DS方法。对一个视频序列进行编码时，value_dis的初始值置为零，value_dis的值随着编码的帧数增长，逐渐趋于稳定。

经过以上整像素的运动搜索后，对得到运动向量继续进行半像素和四分之一像素的搜索，从而得到最终的运动向量。如果当前宏块不是帧中的最后一个宏块，则继续进行宏块级判断，否则对下一帧进行帧级判断。

为了验证本发明的有效性，在jm86源代码上进行了以下实验，其中编码为IPPP格式，以前一帧图像作为参考，最大搜索范围16，采用16*16宏块模式运动估计。用来进行测试的是标准序列football.cif(90帧)以及另两段截自足球比赛的视频Football2.cif(100帧)、Football3.cif(100帧)。这三段视频序列中存在准静止与剧烈运动两种状态的交替，可以有效地检验新方法的自适应选择性能。对视频序列分别采用DS、HME、帧级自适应(FLA：Frame-Level Adaptive)和两级自适应方法(TLA：Two-Level Adaptive)进行测试，为了得到运动估计的时间均值，每段视频测试10次。

为了验证帧级自适应方法对运动复杂度的判断性能，对测试序列只进行帧级判断，即对于flag_HME＝1的帧中宏块全部采用HME方法进行搜索，测试结果如图7所示。图中自适应方法对于flag_HME＝0时的平均匹配点数略低于DS方法，这主要是因为传统的DS方法要适用于所有的运动情况，为了保证图像质量，搜索的初始位置并不唯一，增加了一些额外的搜索过程。而自适应方法已经对运动情况预先做了判断，所以对原来的DS搜索策略进行了简化，采用了初始位置唯一的DS搜索过程。从图中的判断结果可以看出帧级自适应阈值可以有效的跟随图像复杂度变化对搜索模式做出正确的判断。

对DS、HME和两级自适应方法在平均匹配点数和图像质量方面进行对比，结果如表1、表2所示。由表1中数据可以看出，两级自适应方法较DS、HME方法在平均匹配点数方面有明显的改善，并且可以达到缩短编码时间的目的。需要提及的是，在编程实现的时候，新方法并没有优化诸如内存、缓冲之类的相关因素。因此搜索点数的减少比运行时间的减少更能说明方法的性能提高。

表1 DS、HME和两级自适应(TLA)方法比较

(a)平均匹配点数

(b)运动估计时间

表2给出了三种方法的图像质量比较结果，可以看出两级自适应方法能够达到与DS、HME方法基本相同的图像质量。

表2 DS、HME和两级自适应(TLA)基于图像质量的比较

表3给出了两级自适应方法和帧级自适应方法的结果对比，可以看出宏块级判断是对帧级判断的有效补充，可以进一步减少搜索点数，加快搜索过程。

表3 两级判断对帧级判断的性能提升

(a)平均匹配点数

(b)运动估计时间

如上所述，本发明提供了一种通过对运动复杂度判断来进行搜索过程选择的方法，以及在此思想指导下提出的一种基于运动复杂度的快速运动估计自适应选择方法。该方法可以较好地结合DS、HME方法各自的优势，通过对视频序列进行帧级和宏块级运动复杂度的判断，选择出适合当前宏块的快速运动估计方法。在运动比较简单的情况下，其搜索性能基本与DS方法相同，而在运动复杂度较大的情况下，其性能与HME方法接近，从而在保证图像质量的前提下，有效地缩短编码时间。值得一提的是，运动复杂度的判断阈值是视频本身相关的、自适应的，无需人工交互。

Claims (3)

1、一种基于运动复杂度的快速运动估计自适应选择方法，包括以下步骤：

1)首先，根据视频序列的时间连续性，以前一帧图像的运动复杂度为依据，进行运动复杂度的帧级判断；

2)然后，根据帧级判断的结果，对需要继续进行判断的图像帧，根据视频序列的空间相关性，进行宏块级运动复杂度的判断；

3)最后，根据帧级和宏块级对运动复杂度的判断，为当前宏块选择运动估计方法进行运动估计。

2、如权利要求1所述的基于运动复杂度的快速运动估计自适应选择方法，其特征在于：

所说的帧级判断包括以下步骤：

1)计算上一帧图像中宏块与最佳匹配宏块的绝对误差之和，即单帧宏块预测误差mb_SAD：

$\mathrm{mb}\_\mathrm{SAD}=\underset{i=1}{\overset{N}{\mathrm{\&Sigma;}}}S{\mathrm{AD}}_i$

其中SA_i是第i个宏块与其最佳匹配宏块的绝对误差和(SAD，Sum of AbsoluteDifferences)，N是该帧图像中的宏块总数；

2)计算上一帧图像的纹理复杂度，使用尺寸为3×3的Sobel算子计算图像像素I(i，j)位于(i，j)位置处的像素的灰度值的水平梯度Grad_H(i，j)和垂直梯度Grad_V(i，j)，得到该像素对应的梯度信息值：

gradient(i，j)＝|Grad_H(i，j)|+|Grad_V(i，j)|

整帧图像纹理复杂度的梯度信息gradient由下式得到：

$\mathrm{grad}\mathrm{ient}=\underset{(i,j)\&Element;I}{\text{\&Sigma;}}\mathrm{grad}\mathrm{ient}(i,j)$

其中i、j分别代表像素对应位置的横、纵坐标，I代表一帧图像像素的集合；

3)进行帧级判断，对单帧宏块预测误差和该帧图像纹理复杂度进行比较，如果纹理复杂度大于或等于单帧宏块预测误差，则认为宏块的预测误差主要来源于图像本身的纹理信息，图像运动较为简单，采用菱形搜索方法；反之则认为图像运动较为复杂，可能需要使用分级运动估计方法，即：

当gradient≥mb_SAD时：flag_HME＝0，进行菱形搜索方法搜索；

当gradient<mb_SAD时：flag_HME＝1，则根据判断的图像帧，根据视频序列的空间相关性，进行宏块级运动复杂度的判断。

3、如权利要求1所述的基于运动复杂度的快速运动估计自适应选择方法，其特征在于：

宏块级判断包括以下步骤：

1)当前宏块的运动向量预测(MVP，Motion vector prediction)集：该集合由空间相邻宏块(上、下、左上、右上)的运动向量、前一帧相同位置对应的宏块的运动向量以及预测值为零的运动向量(0，0)构成；

2)计算宏块所在区域的运动复杂性：该复杂性用当前宏块的运动向量预测集中预测值的差异性diff_MVP来表示：

$\mathrm{diff}\_\mathrm{MVP}=\underset{i=1}{\overset{\mathrm{MVPnum}}{\mathrm{\&Sigma;}}}\left(\right|{\mathrm{Px}}_i-\mathrm{px}|+|{\mathrm{Py}}_i-\mathrm{py}\left|\right)$

其中：MVPnum是当前宏块的运动向量预测集中可用的预测值个数，(px，py)是当前宏块的运动向量预测集中最小匹配误差对应的运动向量预测值，(Px_i，Py_i)是当前宏块的运动向量预测集中除去(px，py)以外的预测值；

3)获得宏块级判断的自适应阈值value_dis：该阈值是编码过程中采用菱形搜索方法的宏块的diff_MVP均值；

4)结合前两步得到的运动复杂性和自适应阈值进行宏块级判断：

当diff_MVP>value_dis时，宏块所在区域为复杂运动，使用分级运动估计方法；

当diff_MVP≤value_dis时，宏块所在区域为简单运动，使用菱形搜索方法。

Images