基于块运动模型的块匹配算法简单、高效且易于硬件实现，已被很多国际视频编码标准采纳，并得到广泛的应用^[1][2]。其主要思想是把编码帧分成若干个大小相同的图像块，对每个图像块，根据块匹配算法在预测帧中寻找最佳的匹配块，然后对其残差进行编码。编码残差系数所用的比特数和编码运动矢量所用的比特数越少，则整体的编码效率就越高。
　　本文在块运动模型的基础上，分析了当前使用的块匹配准则的优缺点，提出一种改进的块匹配准则——约束条件求和绝对差匹配准则(RCSAD)。
1 块匹配准则
　　在现有搜索算法中，最常用的匹配准则有如下几种：
　　(1)归一化互相关函数准则NCCF

　　由以上公式可知，前两种准则得到的运动位移矢量要比按平均绝对帧差准则及求和绝对差值准则得到的结果更加准确,但是函数的计算量很大，从硬件使用的角度来说，目前寻找匹配块一般使用SAD准则。

2 SAD准则存在的问题
　　这里涉及一个基本假设，即SAD最小值能否准确地反映真实运动和图像细节。举一简单例子说明SAD块匹配准则的不足。图1是一个4×4待匹配像素块A和两个参考匹配像素块XY。采用SAD匹配准则进行最简单可靠的全搜索法，对搜索范围内的每一点都计算MAD值。
　　像素块A与像素块X、Y之间的SAD值：
　　SAD(A，X)=80 SAD(A，Y)=70
　　显然，SAD(A，X)>SAD(A，Y)，按SAD匹配准则，Y像素块应为最佳匹配块。但从主观质量评价看，最佳匹配块不是Y而是X。实际上，像素块A和X都是图像的平坦区域，它们对应像素值之差均在5以内，人眼主观感觉不出它们之间的明显差别，而像素块Y却存在一条明显的黑色竖线，与A的主观感觉相差甚大。
　　从上述简单例子可以看到，SAD准则只是简单地将像素块之间的差异进行累加，并以此效果作为匹配程度的判断准则，而未考虑两匹配像素块中各像素之间的差值大小程度，忽视了像素块内的细节特征，因而造成了主、客观评价的差异，带来了运动估值的不精确。

3 约束条件求和绝对差匹配准则
3.1 SAD块匹配准则的优化
　　块匹配算法搜索区域几何关系如图2所示。子块" title="子块">子块CB为当前帧中待匹配的子块，SR为该子块在前一相邻帧中的搜索区间。假设子块RB为搜索区SR中的任一子块，如果用abs(i，j)来表示子块RB中相对坐标为(i，j)的像素点与它在CB中对应像素点的差值的绝对值(以下简称预测残差)，即：
　　abs(i，j)=RB(i，j)-CB(i，j) (0≤i≤M-1，0≤j≤N-1)
　　假设图像为256灰度值，用n_L(x)表示在以上两子块内对应像素的预测残值为x的数量(x∈[0，255]，x为整数)。则在两子块完全匹配的情况下， n_L-x的分布有以下结果：
　　n_L(x)=M×N，x=0
　　n_L(x)=0，x=(1，…，255)          (5)
　　一般地，块RB是搜索区SR中的任意一个待匹配块，则有：
　　n_L(x)=p[abs(i，j)=x]×(M×N)
　　abs(i，j)∈[0，255]
　　i∈[0，M-1]，j∈[0，N-1]
　　式中n_L(x)=p[abs(i，j)=x]为预测残差值为x的概率密度函数。可用预测残差的分布图来描述n_L-x分布，其预测残差分布图如图3所示。图中，曲线1已经归一化。由图3可知：
　　
　　从统计的观点来看，2个块越匹配，其分布曲线的峰值越趋向于0点(即分布曲线的中心点越趋于x轴的原点)，上述分布曲线越趋于呈现正脉冲特性(即标准方差越小)。
　　理论上，当子块RB与子块CB完全匹配时(即两子块的像素一一对应)，则其n_L-x的分布图退化为位于原点的幅度为MN的一条竖线，即此时分布图描述的是式(5)的情况。
　　类似于在分布函数中取方差的方法，如果在横轴x方向上对分布曲线3取门限T(T为整数，如假设某最佳匹配块使预测残差分布的均值为μ₀，方差为σ₀，可令T= μ₀+2σ₀ ，或视情况而定)，且令：
　　
　　则式(6)的物理意义为子块RB和子块CB中对应像素之差的绝对值比T小的所有数目。由统计特性可知，在相同的门限T下，如果某待匹配的子块越趋近于预测子块CB，则其对应的Q值越大。反之，在一确定的T值下，Q越大，则块RB与块CB越匹配。基于以上的结论，提出如下的算法：如图2所示，在搜索区SR中寻找预测块CB的匹配块，如果采用FS算法，并先选定一合适的门限T，设有一组二维数组Q_{(2W+1)×(2W+1)}变量，在每次块运算时，对数组中的每个变量Q(i，j)(i∈[-W，W]，j∈[-W，W])有：
　　当 CB(i，j)-RB(x+i，y+j)≤T
　　x∈[0，M-1]，y∈[0，N-1]时，Q(i，j)=Q(i，j)+1               (7)
　　这样，在FS搜索完毕后，可得到相应的(2W+1)²个Q(i，j)值。之后，在数组变量中寻找其最大值：
　　
　　则Q(I，J)与对应的子块为所要寻找的最佳匹配块，(I，J)即为运动矢量。

3.2 最佳匹配判决方法
　　在运动估值块匹配搜索过程中，最早被提出的搜索算法是全搜索法FS^[3]，虽然它的搜索精度很高，但巨大的时间开销和计算量是实时视频编码系统不能接受的，从而出现了很多快速搜索算法，如二维对数法、三步法、菱形搜索" title="菱形搜索">菱形搜索法等^[4～7]。
　　在搜索过程中，无论使用哪种搜索算法进行搜索匹配，往往存在一些像素点求得的匹配值是相等的。在这种情况下，如何确定此时哪一点对应最佳运动矢量或下一步搜索的中心点，成为一个比较棘手的问题。菱形搜索示意图如图4 所示。在使用菱形搜索法时，若搜索点A和B的SAD值相等，如何进行下一步的搜索。如果使用MSD或其他准则进行二次判别，会大大增加算法的复杂性和一致性，也失去了SAD准则本来的意义。该问题得不到解决，SAD准则运动估值算法的稳定性就得不到保证。

　　对此，提出了如下的约束判别方法：
　　假设子块CB为当前帧中待匹配的子块，运动矢量为(i_k，j_k)；块RB为与CB相邻的子块，运动矢量为(i_k′，j_k′)。根据上节中得到的SAD优化准则求出CB在参考帧上对i、j位移块的匹配像素数Q(i，j)，若有位移值I、J使
　　
　　当且仅当有惟一的I、J使上式成立时，位移矢量i_k=I，j_k=J。
　　若有{i_u，j_u}，u=1，2，…，U₀同时满足(9)式，根据相邻空间块对应的运动矢量存在高度的空间相关性，特别是属于统一对象的块运动保持一致的可能性更大，计算
　　
　　选取与△d(i_min，j_min)对应的位移矢量(i_min，j_min)为最佳运动矢量。即在SAD优化准则意义下，若多个不同位移的像素点有相同最小风险时，选择与相邻块相对位移最小的像素点为当前块的最佳匹配点。显而易见，这一判决准则不仅显著提高了判决的惟一性，而且由于在相同风险下选择最小相对位移使得相邻图像区域的运动矢量场的一致性得到进一步提高。
　　将这种基于SAD优化准则下的最佳匹配判决方法称为约束条件求和绝对差匹配准则RCSAD(Restrictive Conditional SAD)。
4 实验结果
　　为比较RCSAD与SAD、MSE准则下块匹配算法的性能，分别运用三种准则对标准测试序列Miss America (QCIF格式)进行运动位移矢量估值实验。对每个16×16的子块进行运动矢量估值，预测误差进行二维离散余弦变换(DCT)，并将DCT 系数量化，对量化后的系数采用变字长码编码。
　　图5给出了三种匹配准则下，测试序列Miss America各图像帧N_k(k=1，2，…45)的预测峰值信噪比PSNR曲线。可以看出，约束条件求和绝对差准则的性能(视频序列的图像质量)优于均方误差准则，比求和绝对差准则有了很大提高。