运动估计算法比较-块匹配-全搜索-四步法-三步法

大作业运动估计算法比较一、实验内容简要介绍各种运动估计算法，并比较不同运动估计算法的性能，主要考虑各算法的运算速度和精度。二、实验背景视频原始图像中存在着大量的信息冗余，如时间冗余、空间冗余、信息熵冗余、谱间冗余、几何结构冗余、视觉冗余和知识冗余等等。运动估计是视频压缩编码中的核心技术之一，采用运动估计和运动补偿技术可以消除视频信号的时间冗余以提高编码效率。如何提高运动估计的效率，使运动估计算法的搜索过程更健壮、更快速、更高效成为目前研究的热点。运动估计的基本思想是尽可能准确地获得序列图像帧间的运动位移，即运动矢量。因为运动估计越准确，预测补偿的图像质量越高，补偿的残差就越小，补偿编码所需位数越少，需要传输的比特率就越小。利用得到的运动矢量在帧间进行运动补偿。补偿残差经过变换、量化、编码后与运动矢量一起经过熵编码，然后以比特流形式发送出去。运动估计算法多种多样，大体上可以把它们分成四类：块匹配法、递归估计法、贝叶斯估计法和光流法。其中块匹配运动估计算法因其具有算法简单、便于VLSI实现等优点得到广泛应用。所以本文将重点介绍块匹配运动估计算法，并对各种块匹配算法在计算速度和估计精度上进行简单比较。三、实验原理（一）、像素递归技术像素递归技术是基于递归思想。在连续帧中像素数据的变化是因为物体的移位引起的，郑么如果沿着梯度方向在某个像素周圈的若干像素作迭代运算，运算会最后收敛于一个固定的运动估计矢量，从而预测该像素的位移。（二）、块匹配运动估计块匹配运动估计是把图像帧划分为若干互不重叠的块，并以块为单位寻找目标帧中每块在参考帧（上一帧或者其它帧）中最优匹配的块的相对位置，假设图像中每块的大小为M×N，dxmax为参考块水平方向可搜索最大位移而dymax为参考块垂直方向可搜索最大位移那么基于块匹配的运动估计就是在参考帧（或者其它上一帧）的(M+2dxmax)×(N+2dymax)候选区搜索窗口中找到和目标帧的当前大小为M×N的块的最匹配的块则参考块的运动矢量可用如下的数学公式描述：R表示相关性评价函数，f(m,n)表示目标或当前帧图像的灰度值。满足R为最大时的X、Y为运动矢量，用MV表示。块匹配估计准则是判断块相似程度的依据，因此匹配准则的好坏直接影响了运动估计的精度；另一方面，匹配运算复杂度、数据读取复杂度和内存管理复杂度在很大程度上取决于所采用的块匹配准则。我们这里用到的块匹配准则是：平均绝对误差函数(MeanofAbsoluteError,MAE)有些文献中MAD演变为绝对差和：在上述匹配准则中，由于SAD只采用了加法和绝对值计算，便于计算和硬件实现而且它的匹配精度与MAD相差不大。此外搜索精度还与块的大小、搜索窗的大小、搜索步长有关。块匹配的方法主要有：三步法(TSS)和二维对数法(TDL)、新三步法(NTSS)、四步法(FSS)、基于菱形的搜索算法(DS)和基于六边形的搜索算法(HEXBS)等。其中全搜索算法是简单也是效果最好的一种匹配算法，通过的全搜索匹配得到的结果是全局最优的，但由于计算量很大，我们在编解码中往往不采用这种方法，而只把他作为与其他算法的一种比较。为了兼顾估算精度和运算速度，人们提出了一系列的快速算法。快速算法通过限制搜索位置的数目来减小计算复杂度，但不利于估计小的运动且搜索容易陷入局部最优。下面我们将详细介绍各种基于块的匹配算法。快速算法基于一下假设：认为误差函数在整个搜索区域内有唯一极小值点，并假设误差函数曲面值随偏离最小值点距离是单调递增的。另外运动矢量还满足中心偏执性。即块的运动矢量基本上都是在一个中心位置集中了绝大部分运动矢量，而且随着运动矢量的位置远离中心其数逐渐减少。通过对常用视频序列的运动矢量分布作了更为详细的统计分析发现，运动矢量以不同的比例集中分布在中心附近的特定区域内。如下图：有大约81.80％的运动矢量分布在中心附近范围2的正方形区域内(25个点)，大约77.52％的运动矢量分布在中心附近范围2的菱形区域内(13个点)，更有大约74．76%的矢量集中分布在中心附近范围2的十字形区域内(9个点)。（1）、全搜索运动估计(FS)全搜索法（FullSearchMethod,FS）也称为穷尽搜索法，是对（M＋2dx）×（N＋2dy）搜索范围内所有可能的候选位置计算MAD(i,j)值，从中找出最小MAD，其对应偏移量即为所求运动矢量。此算法虽计算量大，但最简单、可靠，找到的必为全局最优点。FS算法描述如下：从原点出发，按顺时针螺旋方向由近及远，在逐个像素处计算MAD值，直到遍历搜索范围内听有的点，然后在计算的所有点的MAD中找到最小值，该点所在位置即对应最佳运动矢量。但是正因为它是穷尽搜索因此会产生巨大的计算量如[7,7]的搜索区间每个宏块16*16需计算225个MAD值，这就直接制约了编码的实时实现。快速算法本质上是一种穷尽搜索法其计算量仍是相当巨大的。全搜索算法是简单也是效果最好的一种匹配算法，通过的全搜索匹配得到的结果是全局最优的，但由于计算量很大，我们在编解码中往往不采用这种方法，而只把他作为与其他算法的一种比较。（2）、快速匹配算法运动矢量的中心偏执性1、三步法：三步法是应用得相当广泛的一种次优的运动估计搜索算法它的搜索区间一般为[-7，7]即在候选区中与编码块相同坐标位置处为原点，将参考块在其上下左右距离为7的范围内按照一定规律移动移到一个位置就做匹配计算它总共进行了三步搜索在下一次搜索时步长减半以前一步搜索得到的最优点为中心。下图为三步法的搜索示意图。算法的中心思想是，采用一种由粗到细的搜索模式，从原点开始，按一定步长取周围8个点构成每次搜索的点群，然后进行匹配计算，利用上一步搜索得到的最小块误差MBD点作为当前搜索的中心位置，每做一步，搜索的步长减1。步搜索算法搜索窗选取(-7，+7)，最多只需要做25个位置的匹配计算，相对于全搜索来比，大大减少了匹配运算的复杂度，而且数据读取比较规则。2、新三步法：TSS假定运动矢量分布特点是在搜索窗口中均匀分布,但事实证明运动矢量是偏置中心的，RenxiangLi等人在TSS的基础上提出了一种增强运动矢量中心偏置搜索和减小补偿误差的新三步法。NTSS是对TSS的一个改进，对运动量比较小的视频序列如可视电话序列有比较好的性能。对于绝大多数的视频序列，运动矢量的分布都是在中心位置上的概率最大，随着与中心位置的距离的增大，概率会急剧地下降，这也就是前面所说的运动矢量的中心偏移特性。运动量比较小的视频序列的这一特性会更加明显。NTSS算法在最好的情况下只需要做17个点的匹配，在最坏的情况下需要做33个点的匹配，由于运动矢量中心偏置在现实视频序列中是普遍存在的，在通常情况下，NTSS算法需要做33点匹配的概率比三步法(TSS)搜索示意图新三步法(NTSS)搜索示意图较小，因此，在低速率视频应用中，如视频电话或视频会议中，NTSS算法的优点可以得到较好的发挥。3、四步法：四步法FourStepSearch4SS由PoLai-manMaWing-chung等人提出。FSS也是基于视频序列图像的运动矢量的中心偏置特征，以原点为中心，在5*5大小的正方形中构造9个检测点的搜索模型。每一步将搜索模型的中心移向MBD点处，且后两步搜索模式取决于MBD点的位置。与NTSS一样，当运动较小时，FSS也会很快结束搜索过程，只需要2到3步即可。新三步搜索法考虑了块矢量中心偏置的特性，在初步搜索时对中心周围的位置同时做了匹配运算。在物体做小范围运动时，这种改进很见效，可以大大减少运算量。然而，在物体做大范围运动时，这种改进却带来了额外的运算量，因为新三步算法最多需要做33次运算，而三步算法最多只需要做25次运算。四步搜索法考虑到了块的中心匹配的特性，同时兼顾了物体的大范围运动。这种改进在物体既有小范围运动又有大范围运动时可以得到较好的性能。实验的结果表明4SS算法比TSS算法有更好的性能，与NTSS算法有相似的性能。但在物体大范图运动时，4SS算法有更强的鲁棒性。4、菱形搜索法：菱形搜索(DS)算法于2000年被提出，经过多次改进，已成为目前快速块匹配运动估计算法中性能最好的算法之一。搜索模板的形状和大小不但影响整个算法的运行速度，而且也影响它的性能。块匹配的误差实际上是在搜索范围内建立了误差表面函数，全局最小点即对应着最佳运动矢量。由于这个误差表面通常并不是单调的，所以搜索窗口太小，就容易陷入局部最优，例如BBGDS算法，其搜索窗口仅为3四步法(TSS)搜索算法菱形(DS)搜索法×3；而搜索窗口太大，又容易产生错误的搜索路径，像TSS算法的第一步。另外，统计数据表明，视频图像进行运动估计时，最优点通常在零矢量周围。当物体相对静止，运动矢量较小时，DS算法进行的运算要明显少于上述其他算法，我们以4SS算法为例，假设当运动矢量范围为l时，4SS算法需要搜索17各位置，而DS算法最少需要搜索13个位置，最多只需要搜索16个位置。矢量范围加大时，DS算法需要进行搜索的位置数明显要少于4SS算法。实验的结果表明DS算法在性能相当情况下比4SS算法的速度快31%。5、基于块的梯度下降搜索算法：基于块的梯度下降搜索法(BBGDS)是1996年由Lurng-KuoLi和EphraimFeig提出的。该算法采用了一个非常偏向于中心位置的搜索模式—步长为1的9点搜索，如图2-7所示。它不限制搜索的步数，当某一步的最小BDM点位于中心位置或该步已到达搜索窗口的边缘时，则停止搜索。与FSS的某些搜索步骤一样，BBGDS的每个后续搜索步骤都是增加3个或5个搜索点。这个算法非常适合于小运动量的场合。在每一步搜索过程中，BBGDS算法使用了中心匹配块而不是匹配块，降低了陷入局部最优的可能性。利用梯度下降的方向来指导搜索方向，对该方向进行重点搜索，从而减少和避免了不必要的搜索，大大降低了算法的复杂度。基于块的梯度下降搜索算法四、实验步骤具体实验步骤如下：读入视频两帧图像，分别采用上述各种运动估计方法计算运动矢量补偿出预测图像，分析比较各种算法性能。五、实验结果分析我们取视频的第1和第3帧进行各种运动补偿。实验参数如下：块大小16x16；搜索范围dmax=7；搜索精度：1像素；视频大小720*400。（一）、全搜索运动估计运动估计结果：参考帧当前帧预测图像补偿误差Matlab运行时间是：3.963858。重构图像PSNR值：38.0220（二）、三步法运动估计运动估计结果：预测图像补偿误差Matlab运行时间是：0.909280。重构图像PSNR值：35.4990。（三）、新三步法运动估计运动估计结果：预测图像补偿误差Matlab运行时间是：0.900035。重构图像PSNR值：37.2834。（四）、四步法运动估计运动估计结果：预测图像补偿误差Matlab运行时间是：0.948070。重构图像PSNR值：37.4156。（五）、菱形法运动估计运动估计结果：预测图像补偿误差Matlab运行时间是：1.178112。重构图像PSNR值：37.7799。（六）、基于块的梯度下降搜索算法运动估计结果：预测图像补偿误差Matlab运行时间是：0.853036。重构图像PSNR值：37.6766。结果分析：通过实验我们得到各种各种匹配算法的Matlab执行时间、重构图像和重构图像的PSNR值。Matlab执行时间反映了算法的执行效率；图像重构PSNR反映了图像恢复的质量，反映了算法的估算精度。各种各种匹配算法的Matlab执行时间、重构图像的PSNR值如下表：匹配算法Matlab运行时间重构图像PSNR值FS3.96385838.0220TSS0.90928035.4990NTSS0.90003537.2834TSS0.94807037.4156DS1.17811237.7799BBGDS0.85303637.6766从表中分析和恢复出来的图像，显然全搜素匹配是恢复效果最好的，块匹配运动估计算法中搜索精度最高的是全搜索法，这显然跟全搜索算法对搜索范围内的每一个象素点进行匹配运算以得到一个最优的运