一种十字六边形运动估计搜索方法

技术领域

本发明涉及一种视频压缩中的处理方法，特别涉及一种视频压缩中快速块匹配运动估计中的搜索方法。

背景技术

由于视频序列图像在时间轴上具有较强的相关性，运动估计(ME)及运动补偿(MC)技术可以有效的减少时间相关性，因此该技术被广泛应用于各种视频压缩编码方案中。运动估计用来估计物体的位移，得到运动矢量；运动补偿根据得到的运动矢量，对前一帧中由于运动而产生的位移进行调整，从而得到尽可能接近本帧的预测帧。由此可见，运动估计算法越完善，估计出的运动矢量越准确，运动补偿的性能就越好，从而使预测误差越小，编码后需要传输的信息量也将随之大大减少，整个系统的码率压缩比得到很大的提高，因此运动估计和补偿技术己经成为视频序列图像编码系统中减少时间冗余、提高压缩比的重要技术。

现有的运动估计算法有多种，其中块匹配法以其算法简单有效、易于硬件实现的特点，被当今所有的视频编码标准所采用。块匹配的基本思想就是将当前帧分成若干个大小相同的块，对每一个块(当前块)分别在参考帧中的一定区域(称为搜索窗)内，按照一定的匹配准则搜索与之最接近的块(称为预测块)，预测块与当前块之间的位移称为运动矢量，它们的像素间的差值称为残差块，预测块与当前块之间通过匹配准则函数得到的值称为块失真度(BDM)。这样当前帧中的每一块都可用一个残差块和一对运动矢量来表示。图1为块匹配运动估计的示意图。

块匹配运动估计可以从三个方面进行研究：块形状与大小、块匹配准则、搜索策略。目前，块形状与大小以及块匹配准则由于相对比较简单，已经有了比较一致的选择。而搜索策略最为复杂，它决定了一个块匹配运动估计方法的好坏，因此一直是快速运动估计研究的主要方向。目前的H.26X和MPEG-1，MPEG-2，MPEG-4等标准采用的都是基于块运动估计与运动补偿的帧间压缩方案，其压缩比和基于帧内压缩的标准(如JPEG)相比有较大的提高。如在H.261的编码过程中，在采用著名的三步快速搜索法的情况下，运动估计仍要占用整个编码过程的63％的计算量；而在H.263编码器中，运动估计占用了42％的计算量。因此，运动估计是视频压缩的瓶颈。由于上述原因，高效快速的运动估计算法一直是视频压缩领域的研究热点。尤其是从1997年10月召开的MPEG会议上开始征集运动估计快速算法以来，在视频编码中运动估计算法的研究领域中竞争日益激烈。

为此，很多运动估计的快速算法从降低匹配函数复杂度和降低搜索点数等方面进行了改进，早期的运动估计改进算法主要有三步搜索法(TSS)，后来为了进一步提高计算速度和预测矢量精度，利用运动矢量的中心偏移分布特性来设计搜索模式，相继又提出了新三步法(NTSS)、四步法(FSS)、菱形搜速法(DS)、十字菱形搜索法(CDS)和六边形搜索法(HEXBS)等算法。在所有的搜索算法中，全搜索算法虽然精度最高，但是巨大的计算复杂度使其不宜实时应用。三步法通过限制搜索位置的数目来减小计算复杂度，不利于估计小的运动且容易陷入局部最小。新三步法，四步法，菱形搜索法、十字菱形搜索法和六边形搜索法提高了匹配速度，减小了陷入局部最小的可能性，但是搜索点数依然较多，可以进一步优化。

发明内容

本发明要解决的技术问题是：为克服现有技术的不足，本发明提供一种十字六边形运动估计搜索方法，在不影响图像质量的同时能够大大降低了计算复杂度，缩短了计算时间。

本发明解决其技术问题所采用的技术方案是：一种十字六边形运动估计搜索方法，其特征在于包括以下步骤：

第一步：(小十字模式)在小十字模式的5个搜索点中，应用改进的部分块失真准则，找出最小块失真(MBD)所在点，如果最小块失真MBD点在小十字模式的中心，则一步搜索停止，得到最终要求的运动矢量MV(0，0)；否则，进入第二步；

第二步：(小十字模式)以第一步所搜索的最小块失真MBD点为中心构造新的小十字模式，搜寻3个新的搜索点，应用改进的部分块失真准则，找出新的最小块失真MBD点，如果该点在小十字模式的中心，则二步搜索停止，得到最终要求的运动矢量MV(±1，0)或(0，±1)；否则，进入第三步；

第三步：(大十字模式)搜索大十字模式3个还没有搜索到的点，应用改进的部分块失真准则，找出新的最小块失真MBD点，以作为下一步搜索的中心；

第四步：(大六边形模式)以第三步中的最小块失真MBD点为中心，构造大六边形搜索模式，应用改进的部分块失真准则，找出新的最小块失真MBD点，如果该点在大六边形的中心，进入第五步；否则，继续第四步；

第五步：(小六边形模式)以第四步中的最小块失真MBD点为中心，构造小六边形搜索模式，应用改进的部分块失真准则，找出新的最小块失真MBD点，该点所对应的向量即为最终要求的运动矢量。

采用改进的部分块失真准则搜索所述的最小块失真MBD点，改进的部分块失真准则具体如下：

在块匹配算法BMA中，改进的部分块失真准则只使用块其中的一部分像素就可以对失真度有较好的度量。

定义块的大小为16×16时，第n帧左上角坐标为(m，n)的块与第n-1帧左上角坐标为(m+p，n+q)的块间的失真度量SAD值由下式给出：

$\mathrm{SAD}(m,n;p,q)=\underset{i=0}{\overset{15}{\Sigma }}\underset{j=0}{\overset{15}{\Sigma }}|f_n(m+i,n+j)-f_{n-1}(m+p+i,n+q+j)|$

其中，f_n(m+i，n+j)表示第n帧坐标为(m+i，n+j)像素点的像素值。

将失真度量SAD(m，n；p，q)分成16个部分失真度量sad_k(m，n；p，q)(k＝1，2，...，16)。第k个部分失真度量的定义如下式所示：

${\mathrm{sad}}_k(m,n;p,q)=\underset{i=0}{\overset{3}{\Sigma }}\underset{j=0}{\overset{3}{\Sigma }}|f_n(m+4i+s_k,n+4j+t_k)-f_{n-1}(m+p+4i+s_k,n+q+4j+t_k)|$

其中s_k，t_k分别为第k个部分失真度量所用左上角像素点相对于块左上角的水平和垂直偏移。部分失真度量sad_k(m，n；p，q)(k＝1，2，...，16)的计算顺序如图5方框内序号所示。

第k次累加部分失真度量的定义如下式所示：

${\mathrm{SAD}}_k(m,n;p,q)=\underset{i=1}{\overset{k}{\Sigma }}{\mathrm{sad}}_i(m,n;p,q)$

如果第k次累加部分失真度量满足

16×SAD_k(m，n；p，q)>k×min(SAD)

其中min(SAD)是搜索过程中当前得到的最小失真，k为自己设定的整数，取值范围为：3≤k≤16，则认为该点不可能为匹配点；否则，继续计算第k+1次累加部分失真度量SAD_k+1(m，n；p，q)，再进行比较。

本发明与现有技术相比所具有的优点在于：本发明的搜索方法在六边形搜索之前加上十字搜索，并对传统的六边形搜索做出了改进，使其进一步符合视频序列间运动矢量的运动规律，减少了寻找最优匹配块的搜索点，从而缩短了搜索时间；本发明还采用了中途停止，即一步停止和二步停止，对静止和半静止块的搜索速度有显著的提高；本发明同时对最优匹配准则进行了优化，在不影响判别失真度情况下，大大降低了计算复杂度，缩短了计算时间。实验测试表明：本发明的搜索方法对各种测试视频序列都有较好的适应性，尤其是对背景变化不太大的序列，搜索点数明显降低，搜索时间有较大的减少，而搜索质量(运动估计和补偿后的图像的峰值信噪比PSNR)降低很少甚至没有变化。

附图说明

图1.块匹配模型；

图2.十字六边形搜索中的搜索模式：图2(a)表示十字模式，其中表示大十字模式，●表示小十字模式；图2(b)表示传统六边形模式，其中表示传统大六边形模式，表示小六边形模式；图2(c)表示本发明六边形模式，其中表示本发明大六边形模式，表示小六边形模式；

图3.本发明的十字六边形运动估计搜索方法流程图；

图4.本发明的十字六边形运动估计搜索方法搜索示例：图4(a)表示一步停止；图4(b)表示二步停止；图4(c)表示搜索大十字模式没有搜索到的3个点；图4(d)表示大六边形搜索；图4(e)表示小六边形搜索得到最终运动矢量MV；

图5.改进的部分失真准则所用到的搜索点；其中16个数字表示部分失真度量的计算顺序，16个黑点为1个部分失真度量所用到的像素；

图6.news.cif视频中第19帧、20帧的原始图像、运动矢量图以及运动估计和补偿图像：图6(a)表示参考帧第19帧；图6(b)表示原始帧第20帧；图6(c)表示运动矢量图；图6(d)表示本发明十字六边形运动估计搜索方法对第20帧的运动估计和补偿图像；

图7.对news.cif视频前70帧逐帧进行运动估计：图7(a)表示每帧搜索点数；图7(b)表示运动估计和补偿后每帧图像的峰值信噪比。