武汉理工大学《通信工程应用技术综合训练与实习》报告
3 全搜索算法和三步搜索算法
上述介绍的几种运动估计算法中，基于块的运动估计硬件复杂度较少，易在超大规模集成电路中实现，被认为是最通用的方法
3.1 全搜索算法
全搜索法（Full Search, FS）也称为穷尽搜索法，是对（M＋2dx）×（N＋2dy）搜索范围内所有可能的候选位置计算MAD值，从中找出最小MAD，其对应偏移量即为所求运动矢量。此算法虽计算量大，但最简单、可靠，找到的必为全局最优点。
FS 算法描述如下：从原点出发，按顺时针螺旋方向由近及远，在逐个像素处计算MAD 值，直到遍历搜索范围内所有的点，然后在计算的所有点的MAD 中找到最小值，该点所在位置即对应最佳运动矢量。
FS 算法是最简单、最原始的块匹配算法，由于可靠，且能够得到全局最优的结果，通常是其它算法性能比较的标准，但因为对于搜索窗中的每一的候选运动矢量都需要计算一次它的平均绝对差值，所以它的计算量的确很大，这就限制了在需要实时压缩场合的应用，所以有必要进一步研究其它的快速算法。
由于块运动估计的全搜索算法具有很高的计算复杂度，因此在已有的文献中，人们提出了许多快速运动估计算法。这些算法可大致归为多步搜索算法和穷尽搜索算法这两类。对于多步搜索算法，只选择搜索窗中所有运动矢量的一个子集，这样就可以减少对MAD的计算次数。对于穷尽搜索算法，先计算MAD的一个下界，然后尽可能地利用此下界来避免计算MAD。
3.2 三步搜索算法
三步搜索算法、新三步搜索算法、四步搜素算法、基于块的梯度下降搜索算法、二维对数搜索算法、菱形搜索算法、交叉搜索算法、共轭方向搜索算法、正交搜索算法、分层块匹配算法、简易搜索算法是属于此类的快速算法。在这些搜
7
武汉理工大学《通信工程应用技术综合训练与实习》报告
索算法中，运动估计的过程都将包括几个步骤。每一个步骤都将选择一些搜索点，并计算这些搜索点的MAD/SAD值。本文着重介绍三步搜索算法(TSS)。
图3.1 三步搜服哦算法
三步法是应用得相当广泛的一种次优的运动估计搜索算法。此搜索算法如图2-2 所示，可分为下面三步：
第一步搜索9 个位置点，如图中方块所标示的9个点。对每一个位置点计算MAD，找出最小MAD值的点。
将搜索中心移动到第一步中具有最小MAD值的点上。搜索步长减少为第一步搜索步长的一半，进行第二步的搜索匹配，如图中圆形标示的点。对每个位置点计算MAD值，找出最小MAD值的点。
然后继续将搜索中心移动到第二步中具有最小MAD值的点上。搜索步长减少为第二步搜索步长的一半，来进行第三步的搜索匹配，如图中三角块标示的点。对每个位置点计算MAD值，找出最小MAD值的点。得到最佳的运动矢量MV（■→▲）。
由于第二步和第三步的9 个搜索点中均有一个点是在上一步中已经计算过MAD 值，所以第二步与第三步均只要计算8 个点而已，所以TSS 算法的计算次数是9＋8＋8＝25 次，同直接匹配需要225 次比较，计算量大大减少。
8
武汉理工大学《通信工程应用技术综合训练与实习》报告
4 运动估计算法的设计
对于全搜索法和三步法的仿真，本文将采用MATLAB （R2009a）软件进行仿真。
4.1 全搜索算法设计
将图像的k+1帧分为不重叠，紧靠的N*N大小的块，然后依次对每一块进行处理。在处理某一块时，以该块的中心点为中心点，在源帧k中的窗口内的每个像素进行一次匹配，计算所有的MAD（公式2.2），然后找出最小的MAD的点，就是与之相匹配的点。
图4.1 全搜索算法程序流程图
4.2 三步搜索算法设计
9
武汉理工大学《通信工程应用技术综合训练与实习》报告
三步法是一种较好的搜索算法，快速而且高效，它是在对数法的基础上对其进行了改进，提出在每一步搜索后搜索步长均减半的算法。它基本保持了FS（全搜索算法）的性能，但比FS少了大量的计算量。TSS在会议电视和可视电话中应用较多， 它通过三步搜索，逐步较小搜索步长。
对于搜索步长m>0,我们定义
T（m）=M(m) ∪{(-m,-m)，（-m,m）,(m,m),(m,-m)} 这里M（m）定义为：
M（m）={(0,0)，（m,0）,(-m,0),(0,-m)}
这种搜索样式将会被重复利用直到搜索步长为1。
三步搜索法采用T(M)这个搜索样式。三步搜索法的初始搜索步长为搜索窗的1/4。接着，在三步搜索法中的每一步的搜索步长均减半，直到搜索步长为1。初始的搜索中心是在搜索窗的中心。除初始步骤外，在每一步所选择的搜索中心为前一步中具有最小MAD值的位置。
(1)初始化
对每一个（i,j）￠N(W),MAD(i,j)=∞,这里N(W)={(i,j)|-m<=i,j<=m} q=l=0 n=└W/2┘ (2)(n)←T(n)
(3)寻找（i,j）∈（n）以使MAD(i+q,j+l)为最小。 (4）q←q+i,l←l+j,n←└n/2┘
如果n=1跳到（5），否则跳到（2）。
(5）寻找（i,j）∈T（1）以使MAD(i+q,j+l)为最小。 (6）q←q+i,l←l+j,(q,l)为三步搜索算法的最优运动矢量。
10
武汉理工大学《通信工程应用技术综合训练与实习》报告
5仿真结果
5.1 全搜索法结果
为测试算法的可靠性，并考虑到视频图像的连贯性和仿真的简便性，采用两张gif动画分解图像进行仿真。图像尺寸为256*256。块尺寸为16*16；最大搜索步长为7像素。仿真结果如图5.1和5.2：
第一帧图像第二帧图像第二帧与第一帧差值匹配块间差值恢复后的重建帧图像重建帧与第一帧差值
图5.1 全搜索算法仿真图
通过仿真，得到重建帧（即恢复后的第二帧图像）与原第一帧的差值，同原帧间差值几乎相同，肉眼来看，重建帧和原第二帧是基本一样的。这也体现了全搜索算法全局最优的特点。匹配块间差值则是找到第一帧中与第二帧中各块相干度最大的对应快后各对应块基于第一帧块的差值，从图中看出几乎都在0附近，这事可用快运动估计压缩视频信息的依据，也是构成视频的各帧的固有特点。
图5.2为第二帧图像相对第一帧图像的块运动矢量。箭头表示参考块从第一
11