武汉理工大学《通信工程应用技术综合训练与实习》报告
帧到第二帧之间的运动位移。获得运动矢量的过程就是运动估计。图中部并没有大规模的箭头，边缘则有较整齐的矢量排列，反应了视频序列运动特性是边缘局部运动。事实也如此，视频序列中人物主题改动不大，只有桨的位置、船头吊饰部分以及背景边缘有变化移动。且箭头方向与各区域变动方向一致。全搜索算法的精确度很高，肉眼很难分辨出重建帧与原始帧的差别。
运动矢量181614121086420024681012141618
图5.2 全搜索法运动矢量图
5.2 三步法结果
为对比FS算法性能，这里还是采用上述图片进行仿真。块大小同样设置为16*16；最大搜索步长为7像素。仿真结果如图5.3和5.4：
结果显示重建帧与原第二帧帧极为相似，体现了TSS算法也具有很高的精确度。
对比FS仿真结果得到的运动矢量，图3-7大部分箭头指向都相同或相似，只有小部分不一样。这也是算法搜索步骤的不同带来的结果。
12
武汉理工大学《通信工程应用技术综合训练与实习》报告
第一帧图像第二帧图像第二帧与第一帧差值匹配块间差值恢复后的重建帧图像重建帧与第一帧差值
图5.3 三步法仿真图
运动矢量181614121086420024681012141618
图5.4 三步法运动矢量图
13
武汉理工大学《通信工程应用技术综合训练与实习》报告
5.3 性能比较
两算法时间和峰值信噪比计算结果如图5.5：
图5.5 时间和峰值信噪比对比结果
5.3.1计算复杂度
为了对比各算法的优劣性，对于每一个加法、减法或左右移动运算，我们都用一个计算单位来表示其计算复杂度。对于每一个比较运算或取绝对值运算，我们用两个计算单位来表示其计算复杂度。这个假设对于通常所使用的CPU来说是合理的。我们用x表示运动估计所使用的具体算法，用nMAD(x)表示平均每一图像块需要计算MAD的次数，用c(x)表示为完成运动估计过程，块运动估计算法x所需的平均每像素的计算复杂度。
在块运动估计算法中，当前帧被分为固定大小M*N的宏块。现有的视频压缩标准中，M*N被设置为16*16并采用MAD作为匹配准则。
在FS或多步搜索算法的情况下，
和Min(l)分别表示当前运功估计矢量
和已计算的MAD的最小值。在这些算法的每一个搜索点上，将计算一次MAD（
）并将它与Min(l)对比。这里MAD（
）由式（2.2）给出。从式（2.2））需要16*16=256次减法、256
）的每像素的计算
中，可以看出每计算一次对宏块的MAD（
次取绝对值和256次加法运算。所以，计算一次MAD（复杂度为
C(MAD)=(256+256*2+256)/256 (5-1)
这里除以256是因为每个宏块有256个像素。MAD（较运算计算复杂度为
c(c1)=2/256 (5-2)
所以FS的计算复杂度为
c(FS)=( c(MAD)+ c(c1))* nMAD(FS) (5-3)
）与Min(l)的比
14
武汉理工大学《通信工程应用技术综合训练与实习》报告
对于FS
nMAD(FS)=S*S (5-4)
这里（S*S）为搜索窗的大小。c(FS)又可以表示为
c(FS)=( c(MAD)+ c(c1))* S*S (5-5) 由式5-1、5-2、5-3、5-4可得
c(FS)=1025*S*S/256 (5-6) 一个多步搜索算法X的计算复杂度为
c(x)=( c(MAD)+ c(c1))* nMAD(x) (5-7) 特别地
c(Tss)=1025* nMAD(Tss)/256 (5-8)
通常在视频压缩标准中，搜索窗大小为（31*31）， 对于FS
c(FS)=1025*S*S/256=1025*31*31/256=3847.75 (5-9)
对于Tss，（31*31）的搜索窗，搜索点数固定为33个。有
c(Tss)=1025* nMAD(Tss)/256=1025*33/256=132.13 (5-10) 对比c(FS)和c(Tss)，显而易见，三步搜索算法的计算复杂度大约只有全搜索算法的1/30。大大地提高了运动估计效率。这点在仿真系统运行时间可以看出：全搜索算法的运行时间是三步搜索算法时间的8倍。
5.3.2 峰值信噪比
峰值信噪比PSNR是“Peak Signal to Noise Ratio”的缩写，是一个表示信号最大可能功率和影响它的表示精度的破坏性噪声功率的比值的工程术语。系统的失
真度是用峰值信噪比（PSNR）来表示的。其定义为：
PSNR=10*错误！未找到引用源。(255*255/MSE) (5-11)
这里，Peak 就是指8 bits 表示法的最大值255。MSE 指 Mean Square Error（均方误差）。MSE可以表示为： MSE=错误！未找到引用源。 错误！未找到引用源。[s(n1,n2,k)-s(n1+d1,n2+d2,k+1)]
错误！未找到引用源。 (5-12)
其中，B代表M*N块，s()为块中某像素的亮度值。 PSNR 的单位为dB。所以PSNR值越大，就代表失真越少。
PSNR 是最普遍，最广泛使用的评鉴画质的客观量测法，不过许多实验结果
15
武汉理工大学《通信工程应用技术综合训练与实习》报告
都显示，PSNR 的分数无法和人眼看到的视觉品质完全一致，有可能 PSNR 较高者看起来反而比 PSNR 较低者差。这是因为人眼的视觉对于误差的敏感度并不是绝对的，其感知结果会受到许多因素的影响而产生变化（例如：人眼对空间频率较低的对比差异敏感度较高，人眼对亮度对比差异的敏感度较色度高，人眼对一个区域的感知结果会受到其周围邻近区域的影响）。
从PSNR信噪比对比结果和恢复出来的图像，显然全搜素匹配是恢复效果最好的，块匹配运动估计算法中搜索精度最高的是全搜索法，这显然跟全搜索算法对搜索范围内的每一个像素点进行匹配运算以得到一个最优的运动矢量有关，它是全局最优的。但它的计算复杂度太高，MATLAB运行时间最长，不适合实时应用。
在本次仿真中三步法和快速搜索算法的差异不大，这与所选的地图像有关。图像象素电枢越多运动越复杂差异就会越大。事实上三步算法的重构图像PSNR值不如全搜索大，重构的图像用肉眼却分不出差别。因此二者中三步算法是较优的算法。
16