一、概述

二基本概念

三 运动估计的方法

四 运动表示法(4.1 基于块的运动表示法 4.2 亚像素位置的内插 4.3运动矢量在时空域的预测方式)

五 运动估计准则分类

六 运动搜索算法(6.1 全局搜索算法 6.2 分数精度搜索算法 6.3 快速搜索算法 6.4 分级搜索范围（DSR）算法 6.5 混合搜索算法)

七 其他资料

一、概述

运动估计的英文名称是Motion Estimation. 是视频编码和视频处理(例如去交织)中广泛使用的一种技术.

运动估计的基本思想是将图像序列的每一帧分成许多互不重叠的宏块，并认为宏块内所有象素的位移量都相同，然后对每个宏块到参考帧某一给定特定搜索范围内根据一定的匹配准则找出与当前块最相似的块，即匹配块，匹配块与当前块的相对位移即为运动矢量。视频压缩的时候，只需保存运动矢量和残差数据就可以完全恢复出当前块。

二基本概念

在帧间预测编码中，由于活动图像邻近帧中的景物存在着一定的相关性。因此，可将活动图像分成若干块或宏块，并设法搜索出每个块或宏块在邻近帧图像中的位置，并得出两者之间的空间位置的相对偏移量，得到的相对偏移量就是通常所指的运动矢量，得到运动矢量的过程被称为运动估计。

运动矢量和经过运动匹配后得到的预测误差共同发送到解码端，在解码端按照运动矢量指明的位置，从已经解码的邻近参考帧图像中找到相应的块或宏块，和预测误差相加后就得到了块或宏块在当前帧中的位置。

通过运动估计可以去除帧间冗余度，使得视频传输的比特数大为减少，因此，运动估计是视频压缩处理系统中的一个重要组成部分。本节先从运动估计的一般方法入手，重点讨论了运动估计的三个关键问题：将运动场参数化、最优化匹配函数定义以及如何寻找到最优化匹配。

三 运动估计的方法

一般的运动估计方法如下： 设 t 时刻的帧图像为当前帧 f （x， y） ， t’时刻的帧图像为参考帧 f’(x，y)，参考帧在时间上可以超前或者滞后于当前帧，如图1所示，当 t’<t 时，称之为后向运动估计，

当 t’>t 时，称之为前向运动估计。当在参考帧 t’中搜索到当前帧 t 中的块的最佳匹配时，可以得到相

应的运动场 d（x; t, t + t △ ） ，即可得到当前帧的运动矢量。

H.264 编码标准和以往采用的视频压缩标准很大的不同在于，在运动估计过程中采用了多参考

帧预测来提高预测精度，多参考帧预测就是在编解码端建一个存储 M个重建帧的缓存，当前的待编

码块可以在缓存内的所有重建帧中寻找最优的匹配块进行运动补偿，以便更好地去除时间域的冗余

度。由于视频序列的连续性，当前块在不同的参考帧中的运动矢量也是有一定的相关性的。假定当

前块所在帧的时间为 t, 则对应前面的多个参考帧的时间分别为：t-1, t-2, ……。则当在帧 t-2 中搜索

当前块的最优匹配块时，可以利用当前块在帧 t-1 中的运动矢量 MVNR来估测出当前块在帧 t-2 的运

动矢量。

四 运动表示法

由于在成象的场景中一般有多个物体作不同的运动，如果直接按照不同类型的运动将图像分割成复杂的区域是比较困难的。最直接和不受约束的方法是在每个像素都指定运动矢量，这就是所谓基于像素表示法。这种表示法是对任何类型图像都是适用的，但是它需要估计大量的未知量，并且它的解时常在物理上是不正确，除非在估计过程中施加适当的物理约束。这在具体实现时是不可能的，通常采用基于块的物体运动表示法。

4.1 基于块的运动表示法

一般对于包含多个运动物体的景物，实际中普遍采用的方法是把一个图像帧分成多个块，使得在每个区域中的运动可以很好地用一个参数化模型表征，这被称为块匹配法，即将图像分成若干个n×n 块（典型值：16×16 宏块） ，为每一个块寻找一个运动矢量 MV，并进行运动补偿预测编码。 每一个帧间宏块或块都是根据先前已编码的数据预测出的，根据已编码的宏块、块预测的值和当前宏块、块作差值，结果被压缩传送给解码器，与解码器所需要的其他信息如（运动矢量、预测模型等）一起用来重复预测过程。 每个分割区域都有其对应的运动矢量，并必须对运动矢量以及块的选择方式进行编码和传输。在细节比较多的帧中如果选择较大的块尺寸，意味着用于表明运动矢量和分割区域类型的比特数会少些，但是运动压缩的冗余度要多一些；如果选择小一点的块尺寸，那么运动压缩后冗余度要少一些，但是所需比特数要比较多。因此必须要权衡块尺寸选择上对压缩效果的影响，一般对于细节比较少、比较平坦的区域选择块尺寸大一些，对于图像中细节比较多的区域选择块尺寸小一些。 宏块中的每个色度块 （Cb 和 Cr） 尺寸宽高都是亮度块的一半， 色度块的分割方法和亮度块同样，只是尺寸上宽高都是亮度块一半（如亮度块是 8×16 块尺寸大小，那么色度块就是 4×8，如果亮度块尺寸为 8×4，那么色度块便是 4×2 等等） 。每个色度块的运动矢量的水平和垂直坐标都是亮度块的一半。

4.2 亚像素位置的内插

帧间编码宏块中的每个块或亚宏块分割区域都是根据参考帧中的同尺寸的区域预测得到的，它

们之间的关系用运动矢量来表示。

由于自然物体运动的连续性，相邻两帧之间的块的运动矢量不是以整像素为基本单位的，可能

真正的运动位移量是以 1/4 像素或者甚至 1/8 像素等亚像素作为为单位的。

图 3.17 给出了一个视频序列当采用 1/2 像素精度、1/4 像素精度和 1/8 像素精度时编码效率的情

况，从图中可以看到 1/4像素精度相对于 1/2 像素精度的编码效率有很明显的提高，但是 1/8 像素精

度相对于 1/4像素精度的编码效率除了在高码率情况下并没有明显的提高， 而且 1/8像素的内插公式

更为复杂， 因此在 H.264的制定过程中 1/8 像素精度的运动矢量模型逐渐被取消而只采用了 1/4 像素

精度的运动矢量模型。

4.3运动矢量在时空域的预测方式

如果对每个块的运动矢量进行编码，那么将花费相当数目的比特数，特别是如果选择小尺寸的

块的时候。由于一个运动物体会覆盖多个分块，所以空间域相邻块的运动矢量具有很强的相关性，

因此，每个运动矢量可以根据邻近先前已编码的块进行预测，预测得到的运动矢量用 MVp 表示，当

前矢量和预测矢量之间的差值用 MVD 表示。同时由于物体运动的连续性，运动矢量在时间域也存

在一定相关性，因此也可以用邻近参考帧的运动矢量来预测。

1) 运动矢量空间域预测方式

运动矢量中值预测（Median Prediction）

利用与当前块 E 相邻的左边块 A，上边块 B 和右上方的块 C 的运动矢量，取其中值来作为当前

块的预测运动矢量。

设 E 为当前宏块、宏块分割或者亚宏块分割， A 在 E 的左侧，B 在 E 的上方、C 在 E 的右上

方，如果 E 的左侧多于一个块，那么选择最上方的块作为 A，在 E 的上方选择最左侧的块作为 B。

图 3.18 表示所有的块尺寸相同，图 3.19 表示邻近块尺寸不同时作为预测 E 的运动矢量的块的选择。

在预测 E 的过程中遵守以下准则：

1、 对于除了块尺寸为 16×8和 8×16 的块来说，MVp是块 A、B 和 C 的运动矢量的中值；

2、 对于 16×8 块来说， 上方的 16×8 块的MVp 根据B预测得到， 下方的 16×8 块的 MVp 根据 A

得到；

3、 对于 8×16 块来说， 左侧的 16×8 块的MVp 根据 A预测得到， 右侧的 16×8 块的 MVp 根据 C

得到；

4、 对于不用编码的可跳过去的宏块，16×16 矢量MVp 如第一种情况得到。

2) 运动矢量在时间域预测方式

a、前帧对应块运动矢量预测（Corresponding-block Prediction）

利用前一帧的与当前块相同坐标位置的块的运动矢量来作为当前块的预测运动矢量，如图 3.21

所示。

b、时间域的邻近参考帧运动运动矢量预测（Neighboring Reference-frame Prediction）

由于视频序列的连续性，当前块在不同的参考帧中的运动矢量也是有一定的的相干性的。如图

3.22 所示，假设当前块所在帧的时间为 t，则当在前面的参考帧 t’中搜索当前块的最优匹配块时，可

以利用当前块在参考帧 t’+1 中的运动矢量来估测出当前块在帧他 t’的运动矢量：

在上述运动矢量的四种预测方式中，经过实验证明，空间域的预测更为准确，其中上层块预测

的性能最优，因为其充分利用了不同预测块模式运动矢量之间的相关性。而中值预测性能随着预测

块尺寸的减小而增加，这是因为当前块尺寸越小，相关性越强。

五 运动估计准则分类

运动搜索的目的就是在搜索窗内寻找与当前块最匹配的数据块，这样就存在着如何判断两个块

是否匹配的问题，即如何定义一个匹配准则。而匹配准则的定义与运算复杂度和编码效率都是直接

相关的，通常有如下几类比较常用的匹配函数的定义：

设当前帧 f2，参考帧 f1，

（1）最小均方差函数（MSE）

MSE (MV) =Σ|f2（x，MV）-f1(x)|

2

(3.34)

（2）最小平均绝对值误差（MAD）等效于常用的绝对差值和（SAD）准则,性能很好,而且相对简单

的硬件需求，因而得到了最广泛的应用。

MAD (MV) =Σ|f2（x，MV）-f1(x)| (3.35)

（3）阈值差别计数（NTD）

NTD（MV）=ΣG（f2（x，MV）-f1(x)） (3.36)

其中：

当 | α－β | >T0 时，G（α，β）=1；

当 | α－β | <T0 时，G（α，β）=0 (3.37)

由于在用块匹配算法进行运动估计的过程中，利用匹配准则函数进行匹配误差的计算是最主要

的计算量，因此，我们可以从这方面进一步减少计算量。由于图象的帧内也具有相关性，在计算误

差匹配函数时，可以只让图象块中的部分像素参与运算，将块中的所有像素组成一个集合，那么参

与计算的这部分像素集合就是它的子集，这种误差匹配的方法被称为子集匹配法。实验结果表明，

在匹配误差无明显增加的情况下，采用子集匹配可以大大减少每帧图象的平均搜索时间。

六 运动搜索算法

匹配误差函数，可以用各种优化方法进行最小化，这就需要我们开发出高效的运动搜索算法，

主要的几种算法归纳如下：

6.1 全局搜索算法

为当前帧的一个给定块确定最优位移矢量的全局搜索算法方法是：在一个预先定义的搜索区域

内，把它与参考帧中所有的候选块进行比较，并且寻找具有最小匹配误差的一个。这两个块之间的

位移就是所估计的 MV，这样做带来的结果必然导致极大的计算量。

选择搜索区域一般是关于当前块对称的，左边和右边各有 Rx 个像素，上边和下边各有 Ry个像

素，如图 3.27 所示。

如果已知在水平和垂直方向运动的动态范围是相同的，那么 Rx=Ry=R。估计的精度是由搜索的

步长决定的，步长是相邻两个候选块在水平或者垂直方向上的距离。通常，沿着两个方向使用相同

的步长。在最简单的情况下，步长是一个像素，称为整数像素精度搜索，该种算法也称为无损搜索

算法。

6.2 分数精度搜索算法

由于在穷尽块匹配算法中搜索相应块的步长不一定是整数，一般来说，为了实现 1/K像素步长，

对参考帧必须进行 K倍内插。图 3.28 给出了 K=2 的例子，它被称为半像素精度搜索。根据实验证

明，与整像素精度搜索相比，半像素精度搜索在估计精度上有很大提高，特别是对于低清晰度视频。

但是，应用分数像素步长，搜索算法的复杂性大大增加，例如，使用半像素搜索，搜索点的总

数比整数像素精度搜索大四倍以上。

那么，如何确定适合运动估计的搜索步长，对于视频编码的帧间编码来说，即使得预测误差最

小化。预测误差和搜索精度之间的关系的统计分析如图 3.29 所示：

6.3 快速搜索算法

快速搜索算法和全局搜索算法相比，虽然只能得到次最佳的匹配结果，但在减少运算量方面效

果显著。

1） 二维对数搜索法

这种算法的基本思路是采用大菱形搜索模式和小菱形搜索模式，步骤如图 6.4.20 所示，从相应

于零位移的位置开始搜索，每一步试验菱形排列的五个搜索点。下一步，把中心移到前一步找到的

最佳匹配点并重复菱形搜索。当最佳匹配点是中心点或是在最大搜索区域的边界上时，就减小搜索

步长（菱形的半径） 。否则步长保持不变。当步长减小到一个像素时就到达了最后一步，并且在这最

后一步检验九个搜索点。初始搜索步长一般设为最大搜索区域的一半。

其后这类算法在搜索模式上又做了比较多的改进，在搜索模式上采用了矩形模式，还有六

边形模式、十字形模式等等。

2） 三步搜索法

如图 3.31 所示，这种搜索的步长从等于或者略大于最大搜索范围的一半开始。第一步，在起始

点和周围八个 “1”标出的点上计算匹配误差，如果最小匹配误差在起始点出现，则认为没有运动；

第二步，以第一步中匹配误差最小的点（图中起始点箭头指向的“1”）为中心，计算以“2”标出的 8

个点处的匹配误差。注意，在每一步中搜索步长搜都比上一步长减少一半，以得到更准确的估计；

在第三步以后就能得到最终的估计结果，这时从搜索点到中心点的距离为一个像素。

但是，上述一些快速算法更适合用于估计运动幅度比较大的场合，对于部分运动幅度小的场

合，它们容易落入局部最小值而导致匹配精度很差，已经有很多各种各样的视频流证明了这一点。

现在，针对这一缺点，国内外诸多专家学者也提出了相应的应对措施，特别是针对H.264编

码标准要求的一些快速算法的改进，并取得卓越的效果。例如[7]中提到的基于全局最小值具有自

适应性的快速算法，这种算法通过在每一搜索步骤选择多个搜索结果，基于这些搜索结果之间的

匹配误差的不同得到的最佳搜索点，因而可以很好地解决落入局部最小值的问题。

[8]中提到一种适用于H．264的基于自适应搜索范围的快速运动估计算法，经过实验证明对于

如salesman等中小运动序列，其速度可接近全局搜索算法的400倍，接近三步搜索算法的4倍；而对于

大运动序列，如table tennis，该算法则会自动调节搜索点数以适应复杂的运动。当从总体上考察速度

方面的性能时，可以看到，该算法平均速度是全局搜索算法的287．4倍，三步搜索的2．8倍。

6.4 分级搜索范围（DSR）算法

分级搜索算法的基本思想是从最低分辨率开始逐级精度的进行不断优化的运动搜索策略，如图

3.32 所示，首先取得两个原始图象帧的金子塔表示，从上到下分辨率逐级变细，从顶端开始，选择

一个尺寸比较大的数据块进行一个比较粗略的运动搜索过程，对在此基础上进行亚抽样（即通过降

低数据块尺寸（或提高抽样分辨率）和减少搜索范围的办法）进行到下一个较细的级来细化运动矢

量，而一个新的搜索过程可以在上一级搜索到的最优运动矢量周围进行。在亚抽样的过程中也有着

不同的抽样方式和抽样滤波器。这种方法的优点是运算量的下降比例比较大，而且搜索的比较全面。

缺点是由于亚抽样或者滤波器的采用而使内存的需求增加，另外如果场景细节过多可能会容易落入

局部最小点。

6.5 混合搜索算法

由于物体的运动千变万化，很难用一种简单的模型去描述，也很难用一种单一的算法来搜索最

佳运动矢量，因此实际上大多采用多种搜索算法相组合的办法，可以在很大程度上提高预测的有效

性和鲁棒性。

事实上，在运动估计时也并不是单一使用上述某一类搜索算法，而是根据各类算法的优点灵活

组合采纳。在运动幅度比较大的情况下可以采用自适应的菱形搜索法和六边形搜索法，这样可以大

大节省码率而图象质量并未有所下降。在运动图象非常复杂的情况下，采用全局搜索法在比特数相

对来说增加不多的情况下使得图象质量得到保证。 H.264 编码标准草案推荐使用 1/4分数像素精度搜

索。[6]中提到在整像素搜索时采用非对称十字型多层次六边形格点运动搜索算法，然后采用钻石搜

索模型来进行分数像素精度运动估计。

解码器要求传送的比特数最小化，而复杂的模型需要更多的比特数来传输运动矢量，而且易受

噪声影响。因此，在提高视频的编码效率的技术中，运动补偿精度的提高和比特数最小化是相互矛

盾的，这就需要我们在运动估计的准确性和表示运动所用的比特数之间作出折中的选择。它的效果

与选用的运动模型是密切相关的。

七 其他资料

三常见的运动估计匹配准则有三种：MAD、MSE和NCCF，由于MAD没有乘除操作，不需做乘法运算，实现简单方便，所以使用较多。通常使用求和绝对误差（SAD）代替MAD 。

运动估计和运动补偿是AVS 中去除时间冗余的主要方法，它采用多种宏块划分方式，1P4 像素插值、双向估计和多参考帧等技术大大提高了编码效率，但同时也给编解码器增加了一定的复杂度。

运动估计和运动补偿作为视频压缩编码系统的核心算法，占整个系统运算量的60%-80%。研究运动估计算法的DSP实现对整个H.264系统的嵌入式应用具有重要的指导意义。

运动估计算法

运动估计算法是视频压缩编码的核心算法之一。高质量的运动估计算法是高效视频编码的前提和基础。其中块匹配法（BMA, Block Match Algorithm）由于算法简单和易于硬件实现，被广泛应用于各视频编码标准中。块匹配法的基本思想是先将图像划分为许多子块，然后对当前帧中的每一块根据一定的匹配准则在相邻帧中找出当前块的匹配块，由此得到两者的相对位移，即当前块的运动矢量。在H.264标准的搜索算法中，图像序列的当前帧被划分成互不重叠16×16大小的子块，而每个子块又可划分成更小的子块，当前子块按一定的块匹配准则在参考帧中对应位置的一定搜索范围内寻找最佳匹配块，由此得到运动矢量和匹配误差。运动估计的估计精度和运算复杂度取决于搜索策略和块匹配准则。这里使用H.264推荐算法UMHexagonS（Unsymmetrical-cross Multi-Hexagon-grid Search）作为DSP实现的算法参考，与FS算法比较，它在保证可靠搜索精度的前提下大幅降低搜索复杂度。同时使用绝对差和（SAD, the Sum of Absolute Difference）标准作为匹配准则，它具有便于硬件实现的优点。