编程实现全搜索块匹配算法、三部搜索法、二维对数搜索法.doc

编程实现全搜索块匹配算法、三部搜索法、二维对数搜索法一、实验内容简要介绍各种运动估计算法,并比较不同运动估计算法的性能,主要考虑各算法的运算速度和精度。二、实验背景视频原始图像中存在着大量的信息冗余,如时间冗余、空间冗余、信息熵冗余、谱间冗余、几何结构冗余、视觉冗余和知识冗余等等。运动估计是视频压缩编码中的核心技术之一,采用运动估计和运动补偿技术可以消除视频信号的时间冗余以提高编码效率。如何提高运动估计的效率,使运动估计算法的搜索过程更健壮、更快速、更高效成为目前研究的热点。运动估计的基本思想是尽可能准确地获得序列图像帧间的运动位移,即运动矢量。因为运动估计越准确,预测补偿的图像质量越高,补偿的残差就越小,补偿编码所需位数越少,需要传输的比特率就越小。利用得到的运动矢量在帧间进行运动补偿。补偿残差经过变换、量化、编码后与运动矢量一起经过熵编码,然后以比特流形式发送出去。运动估计算法多种多样,大体上可以把它们分成四类:块匹配法、递归估计法、贝叶斯估计法和光流法。其中块匹配运动估计算法因其具有算法简单、便于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)等。其中全搜索算法是简单也是效果最好的一种匹配算法,通过的全搜索匹配得到的结果是全局最优的,但由于计算量很大,我们在编解码中往往不采用这种方法,而只把他作为与其他算法的一种比较。为了兼顾估算精度和运算速度,人们提出了一系列的快速算法。快速算法通过限制搜索位置的数目来减小计算复杂度,但不利于估计小的运动且搜索容易陷入局部最优。下面我们将详细