运动估计算法研究
2.1.1 运动估计算法研究现状
通过运动估计可以除去帧间冗余度，使得传输的比特数大为减少，因此，运动估计是视频压缩处理系统中的一个重要组成部分。作为帧间预测算法的核心和关键，运动估计技术受到人们的广泛关注，出现了多种研究方案，主要有光流方程法、像素递归和块匹配(Block Matching Algorithm)三种。综合考虑计算复杂度和编码效率等因素，块匹配(BMA)出于简单实用，已经成为运动估计算法的主流。块匹配算法是假设矩阵区域中的像素经过相同平移运动，来估算相邻帧相对应矩阵区域位移矢量D。它依赖于位移矢量D进行补偿。由于块匹配算法运算简单，易于实时实现。
因此这种技术已广泛用于视频压缩的一些国际标准，如H.261、H.263、MPEG-1、
MPEG-2和MPEG-4等。
目前，块匹配算法中搜索精度最高的是全搜索算法(Full Search,FS )，他对搜索范围内的每一个像素点进行匹配算法以得到一个最优的运动矢量。但它的计算复杂度最高，不适合实时应用，为此人们提出了许多快速运动估计算法。早期的三步法 (Three Step Seach,TSS)，二维对数法(Two-Dimensional Logarithmic, TDL)等主要通过限制搜索位置的数目来减少计算量。新三步法(NTSS )，新四步法(NFSS) ,基于块的梯度下降法(BBGDS)等利用运动矢量具有中心偏差，提高了匹配速度，减少了陷入局部极小的可能性。预测搜索法(PSA )、自适应跟踪法(AMTS)等利用相邻块的运动相关性选择一个反映当前运动块趋势的预测点作为初始搜索点，以提高搜索的速度和预测的准确性。1999年10月，菱形(DS)被MPEG-4国际标准采纳并收入验证模型CVM)。虽然菱形法获得了非常大的成功，但其性能上仍然存在缺陷：其一，对于运动大的序列，菱形法在搜索最佳点所在的区域时，广度搜索和梯度下降搜索同时进行，即同等地对待搜索区域的各部门，这就造成较大地冗余，影响了算法的搜索速度；其二，对于保持静止地图像序列，即运动矢量为零的情况，菱形法要经历由大的模板(LDSP)到小模板(SDSP)地变化过程，要对13个搜索点进行搜索，而理想情况仅仅需要5个搜索点，即对小运动序列和DS算法还有待改进。
2.1.2 运动估计的基本原理
运动图像多数情况下只是其中很少的一部分图像在运动，同一场景相邻的两幅图像之间在内容上的差异不会太大，或者说后面一帧的内容与前面一帧的重复部分很多。对于相关的视频图像，发送端不一定必须把每帧图像所有的像素都传送给接收端，而仅仅要将物体(或摄像机)的运动信息告诉接收端，接收端就可以根据运动信息和前一帧图像的内容来更新当前帧，这比全部传送每帧图像的具体细节所需的数据量要小的多。
要这样做，首先要解决的问题是如何从序列图像中提取有关物体运动的信息，这个过程称为运动估计(Motion Estimation, ME)，其表达方式是运动矢量(Motion Vector, MV)，运动估计的研究的主要内容就是如何加速、有效的获得有足够精度的运动矢量；而把前一帧相应的运动部分信息根据运动矢量补偿过来的过程称为运动补偿(Motion Compensation, MC)。
按照一般的想法，运动估值应当首先将图像中静止背景和运动物体区分开来，然后对运动物体的实际位移进行估值。但块匹配方法却不是这样，它的思想是将图像划分为许多互不重叠的子块(例如16 16)，并认为子块内所有像素的位移量都相同。这意味着每个子块被视为运动物体。假设在视频序列中，t时刻对应于第k帧图像，t- 时刻对应于第k-1帧图像。对于k帧中的一个子块，在k-1帧中寻找与其最相似的子块，这个过程称为寻找匹配块，并认为该匹配块在k-1帧中所处的位置就是k帧子块位移前的位置，这种位置的变化用运动矢量D来表示。将图像分割成M N的小块，并假设块内像素作相同的运动，且只作平移运动。虽然实际上块内各点运动不一定相同，也不定只有平移运动，但当M N较小时，上述假设可近似成立，这样做的目的只是为了简化运算。块匹配法对当前帧图像的每一块，在上一帧的一定范围内搜索最优匹配，并认为本块就是从上一帧最优匹配块位置处平移过来的。设可能的最大偏移矢量为 ，则搜索范围为 。 图2-1显示了待匹配块与搜索区的几何位置关系。
图2-1 待匹配块与搜索区的几何位置关系
视频压缩的时候，只需保存运动矢量和残差数据就可以完全恢复出当前块。利用搜索到的运动矢量在参考帧上进行运动补偿，补偿残差(difference)经DCT变化、量化、行程编码后与运动矢量共同经熵编码，然后以比特流形式传出去。显然，残差块的值越小，越有利于压缩。因此，运动估计的主要目标就是使预测块和当前块之间的即残差值尽量小。
这里，搜索范围(搜索窗尺寸)的选取对搜索结果有很大影响：搜索范围越大，得到更小残差块的可能性越大，但这会带来更大的时间开销。通常选择的搜索范围有±7,±16，±32等等。由于块匹配时需要在前后帧间逐像素比较，如果采用全搜索算法(即穷尽参考帧搜索区域所有可能的点进行比较，从中找到全局最优点)，计算量非常大。如对格式为CIF(352×288)的图像，若块大小为16×16,当搜索范围为116时，每个块的搜索点数为1089，每帧图像的搜索点数则达到431244；当搜索范围为±128时，每帧图像的搜索点数将达到26155404。因此为了减少块匹配算法的运算量，对快速块匹配搜索算法的研究是非常必要的。
快速块匹配算法一般是基于如下假设：当前块与预测块的残差值随搜索块偏离最佳匹配点单调增加。事实上，残差值的分布并不完全符合这个假定，因此搜索过程有可能陷入局部最优。在快速块匹配算法中得到广泛运用的还有视频序列运动矢量的中心偏置分布特性，即：运动矢量在空间上是非均匀分布的，中心区域的分布远大于边缘区域。这是因为，很多情况下的运动都是静态或半静态。利用这一个特性，在搜索过程中实行非均匀搜索，可以使算法的性能有较大提高。事实上，除了三步搜索法外其他著名的快速算法都利用了这一个特性。
2.1.3运动估计的特性研究
运动估计算法的效率主要体现在图像质量、压缩码率和搜索速度(复杂度)三个方面.运动估计越准确，预测补偿的图像质量越高，补偿的残差就越小，补偿编码所需位数越少，比特率越小：运动估计速度越快，越有利于实时应用。提高图像质量，加快估计速度，减小比特率是运动估计算法研究的目标。通常通过研究初始搜索点的选择、块的模式选择、匹配准则、运动搜索策略来提高算法效率。
2.1.3.1 搜索起点和初始方向
通常匹配块算法的初始点都是从原点开始的，但是对于运动变化较大的图像序列，确定一个初始点，大大节省了搜索时间。另外如果不考虑初始方向，在寻找匹配块的搜索过程中，最终的搜索结果可能由于误差并非最佳匹配块，只是局部最优块.所以这类算法的研究重点就是确定当前搜索的初始点和初始方向。例如利用相邻块的相关性采用自适应预测法确定当前块的运动趋势，利用图像灰度进行预测等等。
(1)运动的相关性
由于运动物体的整体性和视频运动的连续性，因此视频的运动必然具有时间和空间上的相关性。一方面由于摄像机的运动造成了整个画面的运动，这种全局的运动((global motion)造成了该帧图像不同部分运动具有相似性，此外由于块划分的小型化，使得同一帧图像的同一物体可能覆盖多个块，这也使得这些块的运动具有相似性.像这样的同一帧图像的不同部分运动的相似性，就称为运动的空间相关性。另一方面由于运动在时间上的连续性，因此前后相邻帧(或相邻几帧)图像运动具有相关性，这称为运动的时间相关性。
(2)利用运动的相关性对搜索起点预测
早期的三步搜索法、四步搜索法都没有应用相邻块运动矢量预测值的方法。因为运动矢量具有空间和时间上的相关性，周围的块对当前块的搜索起点可以提供很好的预测值。搜索起点预测的基本思想是：利用运动的相关性，以空间位置上的相邻块(左边或上边已编码的块，如图2-2中的A, B,C, C′或时间上的相邻块(前一帧图像相同位置块)的运动预测当前块的初始运动矢量，然后以此为起点作进一步的搜索。

图2-2 周围块运动矢量的预测
在实际应用中，由于视频序列的运动差异性，当前块可能和其相邻块中的某一块或某几块具有运动相关性。另外，某些相邻块由于和其它相邻块具有高度相关性，其预测作用通常可以适当地被其它相邻块中的一块或几块所取代。如：所得到的相邻宏块A、B、C的运动矢量MVA、MVB、MVO和MVmedian作为宏块E的候选预测点，最后对当前宏块E进行运动估计。
2.1.3.2搜索算法的研究
这类研究主要是解决匹配运动估值的矛盾：计算复杂度和图像质量。快速算法通常都是限制搜索位置来减少计算量，牺牲了运动估计精度。经典的快速搜索算法减少了搜索时的匹配点，提高搜索速度，但是却可能陷入局部最优，得不到最佳结果。
搜索模式是运动估计计算法最关键也是最复杂的部分。从搜索方问上看有梯度式、螺旋式，从搜索路线上看有矩形、交叉线性、圆形和菱形，将它们与不同的搜索步长相结合，可得到不同的搜索模式：为深证搜索过程及时停止，需要选择合适的中止准则。
    搜索模式体现了搜索算法的基本特征，它从根本上决定了搜索算法的效率；搜索中止准则是保证搜索过程结束的条件。一般来说，梯度式搜索能够自动中止搜索，螺旋式搜索准则需要指定搜索的中止条件，好的搜索中止准则能进一步提高搜索算法的效率，而目前采用最多的搜索策略是采用菱形搜索法。
2.1.3.3块的模式选择
   块匹配法是基于如下假设：同一匹配块的像素运动是一致的。显然这个假设具有一定的片面性，但选择合适的块形状与大小可在一定程度上消除这种片面性.一般说来，块形状选用正方形是比较自然的选择，这样既便于图像的划分，又有利于块匹配准则函数的计算。但这并非总是最佳选择，因此有的算法采用了其他形状，如三角形，针对视频对象的边缘形状特征，将宏块按不同形状的模板进行了分割。
    关于块的大小，如果块越小，得到的残差值越小，但是这会引入较多的运动矢量，可能降低编码的效率。在H.261, MPEG-1和MPEG-2中，运动矢量是以16×16宏块为单位的，由于块尺寸相对较大，可能包含图像中不同的运动部分，造成预测精度的下降；H.263和MPEG-4标准在宏块运动矢量的基础上加入了以8×8块的运动矢量，预测精度得到了一定的提高。而在H.264编码标准中，在标准的参考代码中，有10个模式可供选择，即SKIP、16×16、16×8、8×16、8×8、8×4、 4×8、4×4、intra4×4和intral6 ×16。其中SKIP模式是指直接拷贝前一帧中对应的某一宏块的运动矢量；intra4×4和intral6×16是帧内预测模式；而其它的模式分别代表不同的块类型，一个宏块可以采用上述10种模式中的任意一种模式或是多种模式的组合。
    H.264在进行运动估计时，首选对当前块采用的所有的模式进行运动估计，然后用率失真优化(RDO)比较在每种模式下码率的大小，码率小的模式将作为最终的模式。该过程是一个全搜索的过程，它盲目地搜索了所有候选模式，从而造成了极大的计算复杂度。虽然通过这种方法能够得到最优的效果，但是在很多硬件设备中不能支持这种庞大的计算能力要求。因此，在尽可能小的质量损失前提下，过滤一些候选的模式，是对H.264进行优化的关键。同时，当确定模式后，再进行运动估计，如分级块匹配法采用的是块大小可变的方案。其基本思想就是从最低分辨率级开始，在每一层依次进行运动估计。较低分辨率用于确定相对较大块的，接着把低分辨率级位移矢量的估计值传递到下一个高分辨率级，较高分辨率级用于精确调整位移矢量的估计。
 在H.264以前的编码标准中，块的形状大多选择16  16的模式或8 8的模式.但是在H.264中，引入了10种候选模式。虽然这种多模式方法能够在一定程度上提高块的匹配效率，但是判断所有模式的算法却极大地增加了计算的复杂度。因此有必要通过各种方法和统计结果来排除一些候选模式，达到降低复杂度的目的。
2.1.3.4匹配准则
运动估计的准确性依赖于在块匹配过程中所用的匹配准则。其中最主要的是两个相匹配的像素块之间的误差度量(Block Distortion Measure，缩写为BDM)，共有三种基于块的误差度量。这里假设物体的帧间运动局限在查找窗口(2w 2w)之内。下面给出这些BDM的定义以及相应的匹配准则。其中，m和n是计算BDM的象素块的尺度(分别对应于宽度和高度)，U(k , l)是上一帧中的物体块，  (k+p，l+q)是当前帧中的匹配块，(p，q)的就是物体的帧间运动矢量(位移向量)。
① 归一化互相关函数(CCF)
           (2-1)
匹配准则：查找区域中最小的 所对应的像素块代表最佳的匹配块， 和 分别表示运动矢量的水平分量和垂直分量。
② 均方误差(MSE)
                (2-2)
③ 绝对平方误差(MAE)
               (2-3)
匹配准则：查找区域中最小的MAE(p,q)  )，所对应的象素块代表最佳的匹配块， 分别表示运动矢量的水平分量和垂直分量。这里，最优匹配相应于找NCCF的最大点。
求和绝对误差SAD (Sum of Absolute Diference)准则出现后，迅速取代MAE且被各种运动估计算法采用，因为它与MAE的匹配效果等价，却去掉了不必要的除法，计算量大大降低：
                  (2-4)
这是因为，对采用相同形状大小的块来说，Nz都是相同的，除以它已没有必要：另一方面，在计算SAD的过程中，当发现块的部分SAD已经大于当前最小SAD时，可以中途退出，从而使计算量大大减少。
上述匹配准则中，除SAD准则外，基本都是基于完全计算块失真度的方法。为减少匹配运算复杂度，也有人对于基于部分计算块失真度的运动估计方法进行了尝试，比如先根据部分BDM选出一组候选匹配，然后这些候选点进行完全BDM的计算，从而确定最优匹配点。
2.2 H.264中运动估计的新特点
H.264的编解码框架与以前提出的标准，如H.261, H.263及MPEG-1/2/4并无显著变化，也是基于混合编码的方案：以运动矢量代表图像序列各帧的运动内容，使用前面已解码帧对其进行运动估计和补偿或使用帧内预测技术，所得的图像残差值要经过变换、量化、熵编码等部分的处理。所以，新标准的性能提升在于各个部分的技术方案的改进及新算法的应用。
新标准在提高图像传输的容错性方面做了大量工作，重新定义了适于图像的结构划分。在编码时，图像帧各部分被划分到多个Slice结构中去，每个Slice都可以被独立解码，不受其它部分的影响。Slice由图像最基本的结构一宏块组成，每个宏块包含一个16×16的亮度块和两个8×8的色度块。
在技术上，H.264标准中有多个闪光之处，如多模式的帧内和帧间预测编码，高精度亚像素运动估计，多参考帧运动补偿技术等。
2.2.1可变尺寸块运动估计
H.264/AVC采用了一种可变块尺寸的运动预测模式，亮度块尺寸的范围从16×16 变化到4×4，其中包含很多可选模式, 形成了一种树形结构的运动预测。同时还为P帧和B 帧提供了特殊的SKIP 模式和DIRECT 模式( 跳过模式, 直接用参考帧相应块代替当前块, 无需残差编码) 和可选的帧内4×4 模式、帧内16×16 模式，总共11 种模式。然而，可选的帧间预测模式增加了，必然会使得运算复杂度增加，因此有必要采用一种高效的决策方法来选取块尺寸组合方式，使得编码效率和编码质量俱佳。
H.264标准中采用不同大小的块模式进行帧间预测，其中，一个16×16 的亮度宏块可以划分为16×16、16×8、8×16 和8×8 四种模式，每个划分区域都是一个宏块分区；如果选择8×8 模式，那么宏块中的8×8分区还可以再细分为8×8、8×4、4×8 和4×4 四种模式称为宏块子分区，这些块尺寸模式可以形象地表示成树形结构。
图2-3 H.264标准中采用的不同大小的块