LCD中几种运动估计块匹配算法比较

　　响应时间和保持型的驱动方式是影响液晶显示器件运动图像质量的两大主要因素，随着科学的发展和新技术的不断引进，液晶的响应时间已经可以下降到2ms 甚至更小，其对运动模糊的影响已经微乎其微, 减少运动模糊的重点转移到了减少保持时间上来。应用倍频技术(120Hz)以将保持时间降低为原来的一半，相应的运动模糊宽度也随之减小为原来的一半，如图1 所示。目前已经有采用240Hz 的倍频技术。在倍频技术的发展过程中，先后出现过简单倍场、插黑场、插灰场等技术，但效果都不理想。运动估计和运动补偿（ME/MC）技术的引进则有效改善了拖尾、残影，提高了运动图像质量。

图1 60 Hz 与120 Hz 技术的运动模糊比较

　　由于没有直接可用的120 Hz 视频信号，我们需要根据现有的60 Hz 视频信号，通过插帧的方法得到120 Hz 视频信号，如图2 所示。首先监测图像序列中物体运动的轨迹，从而得到代表物体运动方向的运动矢量，因此运动估计是运动插帧的前提和关键。

图2 运动插帧原理

　　运动估计的方法有很多，可以分为两大类：基于像素的直接估计法和基于图像特性的间接估计法。直接估计法又包括块匹配法(BMA)、频域相位相关法、像素递归算法(PRA)、MAP/MRF 型“倍叶斯”评价法。其中，直接估计法中的块匹配法算法原理简单，应用最为广泛。本文针对块匹配法算法方法进行分析研究。

1、块匹配方法

　　块匹配的基本思想是将目标图像分割成固定大小的块，然后在参考图像中寻找匹配最好的块。块匹配方法假设分割块中所有像素具有相同的运动趋势，这种假设有其局限性，但大大减少了匹配过程中的运算量。

1.1、块匹配原理

　　应用块匹配算法，首先要有搜索最佳匹配的标准，这里称之为价值函数：均方误差（MSE）、绝对误差和（SAD）、平均绝对误差（MAD）、方差和（SSE）、绝对变化误差和（SATD）都可以作为价值函数。其中常用的是均方误差（MSE）和平均绝对误差（MAD），如方程（1）和（2）。其中N 为块边长像素数（为方便搜索块一般划分为正方形），Cij 和Rij分别为当前宏块和参考宏块相应像素的灰度。

　　具体步骤首先要将当前和参考帧图像分块，选取的参考帧为当前帧的前一帧，一般宏块为16×16 像素大小，然后确定搜索范围大小，一般为以宏块为中心的30×30 像素区域，最后在参考图像相应搜索区域中寻找价值函数最小的宏块，运动矢量从参考宏块位置指向当前宏块位置，如图3所示。

图3 块匹配原理

1.2、几种块匹配方法

　　基于1.1节介绍的基本原理，块匹配方法根据搜索原理的不同又有不同的算法，主要有如下几种，如图3 所示。为方便说明，图中所有宏块由中心点代表。

　　全搜索法(ES)：从原点出发，按顺时针方向由近及远，逐个宏块计算价值函数值，直到遍历搜索范围内所有的点。比较所有点的价值函数，找到最小值。这是最简单、最原始的块匹配算法，可靠，且能够得到全局最优的结果，通常是其它算法性能比较的标准。但它的计算量的确很大，耗费大量的时间和资源，所以有必要进一步研究其它快速算法。

　　三步法(TSS)（图3（a））：第一步，从原点开始，选取最大搜索长度的一半为步长，在周围距离步长的8 个点处进行块匹配计算并比较。

　　第二步，将步长减半，中心点移到上一步的价值函数最小点，重新在周围距离步长的8 个点处进行块匹配计算并比较。第三步，在中心及周围8个点处找出价值函数最小点，若步长为1，该点价值函数最小，搜索结束，否则重复第二步。这种算法采用由粗到细的搜索模式，是最早的快速算法之一，减少了算法的复杂度和运算量。但是整个过程采用了统一的搜索模式，使得第一步的步长过大，容易引起误导，从而对小运动效率较低。

　　新三步法(NTSS)（图3（b））：对三步法的改进，先以步长为4 对周围的八个点搜索，再以步长为1 对另外八个点进行搜索。若初始点价值函数值最小，则搜索结束，如果价值函数值最低点是步长为1 的八个搜索点之一，则把初始点定为这一点再次搜索。如果价值函数值最低点为步长为4 的八个搜索点之一，则和三步法搜索方法相同。这种算法是对三步法的改进，可以进一步减少计算量。但是每次检查时，检查的次数比较多，误差出现的可能性也就比较大。

　　四步法(4SS)（图3（c））：第一步，以搜索区域原点为中心选定5×5的搜索窗，然后在9个检测点处进行匹配计算，如果价值函数最小点位于中心点，则跳到第四步；否则进行第二步。第二步，窗口保持为5×5，但搜索模式取决于上一步的价值函数最小点位置:a)上一步价值函数最小点位于窗的四个角上，则另外再搜索5 个检测点。b)上一步价值函数最小点位于窗的四边中点处，则只需再搜索3 个检测点，这一次价值函数最小点在窗口中心，则跳到第四步；否则进行第三步。第三步，搜索模式同第二步，但最终要进行第四步。第四步，将窗口缩小为3×3，这时检查出的价值函数最小点为整个区域的最小点。这种算法的计算复杂度比TSS 低，搜索幅度比较平滑，不至于出现方向上的误导，获得了较好的搜索效果。但是搜索速度并不一定快，对图像的依赖性比较强。

　　简单高效算法（SES）（图3（d））：这种方法将区域划分为四个区间，利用三点价值函数的比较，选择整个区域价值函数最小点所在的区域中点。如图，If MAD(A) ≥ MAD(B) and MAD(A) ≥ MAD(C) 选择 D，If MAD(A) ≥ MAD(B) and MAD(A) ≤ MAD(C) 选择 E,F，If MAD(A) ＜ MAD(B) and MAD(A) ＜ MAD(C) 选择 F,G,H，If MAD(A) ＜ MAD(B) and MAD(A) ≥ MAD(C) 选择 H,I。下一步重复同样的步骤，知道找到最佳匹配点。