CN101170696A - 一种运动估计方法 - Google Patents

Abstract

本发明涉及一种视频处理过程中的运动估计方法，包括：步骤1，根据片内存储器的大小确定连续宏块的大小，把一帧中的所有宏块划分为若干连续的16×16宏块，每个连续宏块中的所有宏块都处于一帧中同一行上，并分配所需的片内缓冲区；步骤2，把当前帧和参考帧中对于连续宏块进行模式选择所需要的亮度、色度数据复制到片内缓冲区；步骤3步骤5是为了准确的得到预测的起始点；步骤6到步骤10是通过不连续十字形搜索方法获得最佳匹配点后找到最佳匹配块，结束本次运动估计。该方法充分利用了运动向量在水平和垂直方向的分布概率远大于其余方向的分布特性，并结合起点预测策略，提高了初始搜索点接近最佳匹配点的可能性，减少了搜索量。

Description

一种运动估计方法

技术领域

本发明涉及一种视频处理过程中的运动估计方法，特别涉及一种可以提高运动估计的速度与精度的运动估计方法。

背景技术

由于在视频序列中包含大量的信息，如果不对这些信息进行处理就存储或传递是很消耗资源的，因此对视频序列进行压缩处理就成为了一个热门话题。由于连续的运动图像序列的各邻近帧之间有时间冗余，就可以运用运动估计(Motion Estimation)对图像进行数据压缩。而运动估计是视频压缩中计算开销很大的一部分，因此人们提出了很多这方面的快速运动估计方法。

运动估计有很多种方法，块匹配就是其中的一种。块匹配运动估计(Block_matching，ME)理论简单且实现方便，现在大多数图像压缩标准如：ITU_TH.26L、MPEG_1\MPEG_2等都采用块匹配方法进行运动估计。这种方法的主要思想是把一帧图像分割成16×16的宏块，把宏块按情况进一步分割成更小的子块，然后用这些块与参考帧中搜索区域内的像素点相比较，得到和当前块最相似的块并与之作差，把差值进一步处理后进行编码，从而达到数据压缩的目的。

在块匹配运动估计中比较经典的方法有全局搜索方法(FS)、二维对数搜索方法、三步搜索方法、四步搜索方法、新三步搜索方法、十字搜索方法和菱形搜索方法等。同时也有很多组合几种搜索模型的方法如：十字形-菱形搜索方法、十字形-六边形搜索方法等。在这些搜索方法中，FS最直接明了且效果最优，它比较搜索窗口内的所有像素点，最后得出最佳参考块，但是FS计算量太大，不宜实际运用；二维对数搜索方法、三步搜索方法在减少计算量方面效果显著，但初始搜索步长太大，容易陷入局部最小而导致匹配精度很差；菱形搜索方法利用了运动矢量的中心偏置特性，在保证图像质量的同时，还使得计算量明显减少，提高了搜索速度，但这种方法依然存在不足，该方法虽然考虑了运动矢量的中心分布的特性，而忽略了运动矢量的另外一个特性，即：运动向量在水平和垂直方向的分布概率远大于其余方向。

发明内容

为了克服现有技术中对运动估算的速度和精度不高的不足，本发明提供了一种运动估计方法，该方法充分利用了运动向量在水平和垂直方向的分布概率远大于其余方向的分布特性，并结合起点预测策略，将提供一种新的快速运动估计方法，提高了初始搜索点接近最佳匹配点的可能性，减少了搜索量。

本发明所采用的技术方案是：一种运动估计方法，其特征在于，该方法包括步骤：步骤1，开始时根据片内存储器(ISRAM)的大小确定连续宏块的大小，把一帧中的所有宏块划分为若干连续的16×16宏块，每个连续宏块中的所有宏块都处于一帧中同一行上，并分配所需的片内缓冲区；步骤2，把当前帧和参考帧中对于连续宏块进行模式选择所需要的亮度、色度数据复制到片内缓冲区；步骤3，进行预测块的选择；步骤4，计算预测矢量；步骤5，预测得到起始点；步骤6，以预测出来的起始点为中心，开始不连续十字形搜索；步骤7，展开不连续十字形搜索法，计算象素点SAD(象素值绝对差和，Sum of AbsoluteDifference，简称SAD)值；步骤8，求出SAD值最小的点，作为最佳匹配点；步骤9，根据最佳匹配点找到最佳匹配块；步骤10，退出搜索，结束本次运动估计。

本发明的有益效果是：由于把一帧中的所有宏块划分为若干连续宏块，每个连续宏块中的所有宏块都处于一帧中同一行上，并把模式选择所需要的亮度、色度数据复制到片内缓冲区内，减少了数据的交换，使得数据访问的速度加快，加快了视频压缩的计算速度。充分利用了运动向量的分布特性，采用不连续十字形搜索，可以更快地查找到最佳匹配点，而且在不连续十字形搜索中，第一步搜索可以覆盖较大的面积，能够更好地避免运动估计中的局部最小情况出现等优点。

附图说明

图1示出了根据本发明实施例的一种运动估计方法的流程图；

图2示出了预测块选择的块分布图；

图3示出了不连续十字搜索方法的搜索模板第一步的结果；

图4示出了不连续十字搜索方法的搜索模板第二步的结果；

图5示出了不连续十字搜索方法的搜索模板第一步补充计算的结果；

图6示出了不连续十字搜索方法的搜索模板第二步与第三步的结果。

具体实施方式

下面结合附图和实施例为例对本发明进行进一步说明：

在本实施例中，选用美国德州仪器(TI)公司的TMS320DM64x系列多媒体处理芯片作为本实施例的硬件平台。德州仪器(TI)公司的TMS320DM64x系列多媒体处理芯片，适合于数字媒体应用，DM64x片上具有一级缓存(cache)和司配置RAM/Cache，以及64个32位通用寄存器，这些存储空间保证了大规模音视频处理程序高效快速地运行。一级缓存分为程序cache和数据cache两种，访问速度快。可配置RAM/Cache可以把它分割为片内存储器(ISRAM)和二级缓存，片内存储器(ISRAM)可以存放程序和数据，访问速度快。二级缓存也是一种高速cache，可提高程序和数据的访问速度。DM64x所应用的EDMA控制器具有64个独立DMA通道，其传输配置信息保存在RAM中，能够同时处理多个DMA传输任务。DMA传输只需要DSP核最小程度地介入，从而有效地提高了系统的处理速度。在本实施例中选用AVS标准进行运动估计计算。

如图1所示的流程图给出了本实施例的具体过程：

步骤1，初始时根据DSP有效的片内存储器(ISRAM)的大小确定可以把运动估计相关的数据放入片内存储器的宏块的大小，并分配所需的片内缓冲区(ISRAM)等。宏块个数是根据能用的片内存储器的大小和运动向量的取值范围决定：

一般地，设这些宏块的个数为L，运动向量的取值范围为-N~N，有效的片内存储器的大小为M₀字节，参考帧数为1帧，则

$L=\left[\frac{M_0-416-64N-{8N}^2}{928+64N}\right]$

根据计算出的宏块的大小L从而确定实际所需的片内缓冲区大小M(字节)，

M＝2×(16×L+2N)×(16+2N)+(L+1)×16×26

步骤2，把当前帧和参考帧中对于这些宏块进行运动估计所需要的亮度、色度数据通过DMA的方式复制到片内缓冲区。这些数据包含：当前帧的这些宏块中的亮度、色度数据；参考帧中对应位置的亮度、色度数据。

步骤3：根据本发明的块选择的原则，进行预测块的选择。

步骤4：计算预测矢量，根据公式：

Pred_mv＝w1*MVa+w2*MVb+w3*MVc+w4MVd+w5MVe，计算Pred_mv。

步骤5，预测得到起始点。

步骤6，以预测出来的起始点为中心，开始不连续十字形搜索。

步骤7，展开不连续十字形搜索方法，在搜索区域内计算水平和垂直方向9个像素点的SAD值，如图3所示。

步骤8，根据步骤7计算出来9个象素点的SAD值，求出SAD最小的点，分下面三种情况，分别执行下列步骤：

步骤8.1，搜索点在搜索区域内，

(a)若该点是中心点，则再计算该点周围上、下、左、右四个点的SAD值，如图4所示，求出SAD值最小的点；

(b)若该点是十字搜索模型中半径为2处的点，以该点为中心，计算周围矩形区域内的8个像素点的SAD值，如图5所示，求出SAD值最小的点；

(c)若该点是十字搜索模型中半径为4的点，以该点为中心，再扩展一个不连续十字形搜索区域，如图5所示。并将该点作为新的起始搜索点，跳转至步骤6继续执行。

步骤8.2，搜索点在搜索边界上，

若有搜索点落在搜索区域边界上面，就取本次搜索点中SAD值最小的点作为最佳匹配点。

步骤8.3，搜索点超出搜索区域，

当搜索范围超出搜索区域时，就取此次搜索模型的区域内可得点中的最小SAD值，并记录下该点作为最佳匹配点。

步骤9，根据最佳匹配点找到最佳匹配块。

步骤10，退出不连续十字形搜索，结束本次运动估计。

在步骤3到步骤5的目的是为了准确的得到预测的起始点，其具体原理是：

对十字搜索模型的初始中心点的位置进行预测，使不连续十字中心点搜索方法更接近最佳匹配点，进一步提高搜索效率。由于视频序列中对象的运动通常都是刚体运动，属于一个对象的几个块通常有相似的运动矢量。因此，可以利用时间域和空间域中邻近已编码块的运动矢量，来预测当前块的初始运动矢量，在此称为预测矢量(Pred_mv)。为了更好地预测出当前块的Pred_mv，我们需要挑选出参与预测的块和定义计算Pred_mv的规则。

本实施例对于块的挑选规则，借鉴常规预测运动矢量的方法：选择当前块空间域内的左边块、上边块和右上块，在时间域内选择与当前块对应位置的块，然后再取上述几个块的运动矢量的中值。然而常规方法存在以下不足：对矢量的处理过程固定化，不能很好地体现已编码块内的物体的运动趋势，使预测出的运动矢量精确度不高。

所以本实施例主要采用如下起点预测方法：

1)块的选择原则。

被选择参与预测的块如图2所示。其中：A、B和C属于当前块空间域内的左边、上边和右上块，D、E属于时间域内的块，并且D块的位置和当前块的位置对应，E块和D块相邻。本文的块选择原则比以往的策略多了一个E块，这样做的优点是可以更充分地利用临近块内对象的运动趋势信息，使得预测结果精确度更高。

2)计算Pred_mv的规则。

Pred_mv的计算规则使用加权计算的方式，具体方法如公式2所示：

Pred_mv＝w1*MVa+w2*MVb+w3*MVc+w4MVd+w5MVe

其中：wi是各个运动矢量的权值，权值的分配按五个运动矢量的绝对值的大小比例分配。MVa、MVb和MVc分别是块A、B、C的运动矢量，MVd和MVe分别是块D和E的运动矢量，若某块不可得，则设置该块运动矢量的值为零。

采用起点预测技术后，最明显的优点是可以使运动估计的起始搜索点更接近最佳匹配点，搜索方法只需执行较少的步骤就可以找到合适的匹配块，从而节减计算量，提高搜索速度。

在步骤6到步骤8的目的是通过不连续十字形搜索方法获得最佳匹配点，其具体原理是：

根据运动矢量的分布特性，本方案提出一种不连续十字形搜索方法。该方法充分利用运动矢量的分布特性，集中精力搜索中心区域、水平和垂直方向上的点，从而可以更快地查找到合适的点。本方法在搜索区域内计算水平和垂直方向9个像素点的SAD值，求出SAD最小的点，如图3示出了不连续十字搜索方法的搜索模板第一步的结果，接着：

步骤8.1，搜索点在搜索区域内，则包括以下步骤之一：

(a)若该点是中心点，如图4所示，则再计算该点周围上、下、左、右四个点的SAD值，求出SAD值最小的点，并结束搜索；

(b)若该点是十字搜索模型中半径为2处的点，如图5所示，则以该点为中心，计算周围矩形区域内的8个像素点的SAD值，求出SAD值最小的点，结束搜索；

(c)若该点是十字搜索模型中半径为4的点，如图5所示，则以该点为中心，再扩展一个不连续十字形搜索区域，重新执行不连续十字搜索方法；

步骤8.2，若有搜索点落在搜索区域边界上面，就取本次搜索点中SAD值最小的点作为最佳匹配点，并结束搜索；

步骤8.3，若搜索范围超出搜索区域时，就取此次搜索模型的区域内可得点中的SAD值最小的点作为最佳匹配点。

可以看出，本方案中不连续十字形搜索方法优先查找搜索区域内的中心点、水平和垂直方向的像素点，很好地利用了运动矢量的中心偏置特性和运动矢量落于水平、垂直方向的概率大于落在其它方向上的概率的特性。同时，考虑到搜索点在搜索边界上和搜索范围超出搜索区域时的情况，有效的补充计算了第一轮搜索所遗漏的点，增加了查找到最佳点的机会，保证了搜索精度，同时减少了计算量，使运动估计的速度得到了提高。

本实施例以德州仪器(TI)公司的TMS320DM64x系列多媒体处理芯片对AVS标准视频数据的运动估算来说明本发明的原理，本领域的普通技术人员将会意识到，其它任何视频压缩标准和任何硬件平台对本发明的技术方案的应用，尽管这里未明确描述和示出，都应包括在本发明的保护范围内。而且，这里所述的示例和公式和函数出于帮助读者理解本发明的原理，应被理解为并不局限于这样的特别陈述的示例和条件。

Claims (6)

1.一种运动估计方法，其特征在于，该方法包括步骤：

步骤1，开始时根据片内存储器的大小确定连续宏块的大小，把一帧中的所有宏块划分为若干连续的16×16宏块，每个连续宏块中的所有宏块都处于一帧中同一行上，并分配所需的片内缓冲区；

步骤2，把当前帧和参考帧中对于连续宏块进行模式选择所需要的亮度、色度数据复制到片内缓冲区；

步骤3，进行预测块的选择；

步骤4，计算预测矢量；

步骤5，预测得到起始点；

步骤6，以预测出来的起始点为中心，开始不连续十字形搜索；

步骤7，展开不连续十字形搜索法，计算象素点SAD值；

步骤8，求出SAD值最小的点，作为最佳匹配点；

步骤9，根据最佳匹配点找到最佳匹配块；

步骤10，退出搜索，结束本次运动估计。

2.根据权利要求1所述的运动估计方法，其特征在于，步骤3中被选择参与预测的块包括当前块空间域内的左边、上边和右上块(A、B、C)和时间域内与当前块的位置对应的块(D)及其相邻块(E)。

3.根据权利要求1所述的运动估计方法，其特征在于，步骤4包括计算步骤：

Pred_mv(预测矢量)＝w1*MVa+w2*MVb+w3*MVc+w4MVd+w5MVe。

4.根据权利要求1所述的运动估计方法，其特征在于，步骤8包括以下步骤之一：

步骤8.1，搜索点在搜索区域内，则包括以下步骤之一：

(a)若该点是中心点，则再计算该点周围上、下、左、右四个点的SAD值，求出SAD值最小的点；

(b)若该点是十字搜索模型中半径为2处的点，以该点为中心，计算周围矩形区域内的8个像素点的SAD值，求出SAD值最小的点；

(c)若该点是十字搜索模型中半径为4的点，以该点为中心，再扩展一个不连续十字形搜索区域，并将该点作为新的起始搜索点，跳转至步骤6继续执行；

步骤8.2，若有搜索点落在搜索区域边界上面，就取本次搜索点中SAD值最小的点作为最佳匹配点。

步骤8.3，当搜索范围超出搜索区域时，就取此次搜索模型的区域内可得点中的最小SAD值，并记录下该点作为最佳匹配点。

5.根据权利要求1-4任一项所述的运动估计方法，其特征在于，步骤1中的存储器为DSP的片内存储器。

6.根据权利要求1-4任一项所述的运动估计方法，其特征在于，步骤2中数据复制到片内缓冲区的方式为直接存储器访问(DMA)方式。

Images