CN101977325B - 一种新型块匹配运动估计方法 - Google Patents

Abstract

本发明涉及一种新型块匹配运动估计方法，该方法包括以下步骤：获取视频图像中与当前宏块相邻的上、下、左、右四个宏块的运动矢量；根据所述运动矢量确定搜索中心；根据所述运动矢量的平均值调整搜索范围；在上述搜索范围内进行运动搜索，并利用改进后的最小绝对误差准则进行匹配或提前终止判定。本发明在运动特征不变的情况下，可以选择六边形、八边形、十二边形、十六边形、圆形等近似圆形的模板来实现，同样可以达到符合运动特征本身、降低算法复杂度和提高效率的目的。在运动特征变化的情况下，可以按照运动物体本身形状、运动规律和运动特性来改变模板的形状，选择三角形、五边形、椭圆形等模板来实现，可以达到同样的效果。

Description

一种新型块匹配运动估计方法

技术领域

本发明涉及一种视频图像编码技术，特别涉及一种基于H.264编码的新型块匹配运动估计方法。

背景技术

H.264是由ITU-T和ISO两个组织的专家为实现视频的更高压缩比，更好的图像质量和良好的网络适应性而提出的视频编码标准。事实证明，H.264编码具有比其他视频压缩标准更节省码流，并且比MPEG一4算法简单的特点。

H.264视频编码标准的性能很大程度上取决于运动估计，而影响运动估计的主要因素是匹配准则和搜索算法。而搜索中心和搜索范围的确定能够大大提高搜索的效率。因此，很多针对块匹配的快速搜索算法被相继提出来。块匹配运动估计的基本原理是将当前帧分割成互不重叠的小块(如大小为16×16像素等)，然后在参考帧中进行运动搜索，寻找最佳匹配位置作为预测，编码时只编码运动矢量与块残差信息，以消除帧间冗余度，降低码率。

运动估计算法中常用的匹配准则有四种：即最小绝对差准则(MAD)、最小均方误差准则(MSE)、归一化互相关函数准则(NCCF)和求和绝对误差准则(SAD)。在H.264编码标准中，由于SAD匹配准则没有乘除运算，且简单、方便，所以作为最佳匹配准则来判别最佳匹配块，其计算公式如下式所示：

$\mathrm{SAD}=\underset{i=1}{\overset{N}{\mathrm{\Σ}}}\underset{j=1}{\overset{M}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|$

其中N、M是搜索块的横坐标和纵坐标，S是当前进行编码的原始块，R是参考帧的数据。

虽然SAD匹配准则相比其它匹配准则而言，具有上述优点而被广泛应用。但是由于生产实践的变化，其不能满足数字视频的实时性要求的弊端，已严重影响其在生产实践中的应用效率。

理论上其存在弊端的原因在于其方法论错误。匹配准则SAD的模板都是方形的，真实物体的轮廓很少是方形的。物体的运动是平滑的近似圆形的运动，是没有棱角的运动。因而SAD匹配准则的模板一律用方形模板的做法不符合运动本身及事物是多样性的统一规律，是不科学的。

实践上在块匹配的运动估计算法中，由于SAD模板上述固有的缺陷导致其不能在有效的时间内找到最佳的匹配块，且需反复调用SAD模块，进而使运动估计运算复杂度增高，耗时增多，效率低下，已不能满足日益发展的生产实践的需要。

发明内容

本发明要解决的技术问题是提供一种用于H.264编码的新型块匹配运动估计方法，其具有高度的灵活性，可减少运动估计的范围和时间；同时也解决了现有通用匹配准则SAD模板形状的不科学性问题。

为解决上述技术问题，所述的新型块匹配运动估计方法，其特征在于，包括以下步骤：

(1)获取视频图像中与当前宏块相邻的上、下、左、右四个宏块的运动矢量，若其中某个宏块不存在，则相应的运动矢量赋值为0；

(2)根据所述运动矢量确定搜索中心；

(3)根据所述运动矢量的平均值调整搜索范围；

(4)在步骤(3)中所述的搜索范围内进行运动搜索，根据不同的运动特征选择相应的最小绝对误差准则进行匹配或提前终止判定。

其中，所述最小绝对误差准则可以为BSAD误差准则，BSAD误差准则定义式如下式所示：

$\mathrm{BSAD}=\underset{i=1}{\overset{N/4}{\mathrm{\Σ}}}\underset{j=M/4-i+2}{\overset{3M/4+i-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4+1}{\overset{3N/4}{\mathrm{\Σ}}}\underset{j=1}{\overset{M}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=3N/4+1}{\overset{N}{\mathrm{\Σ}}}\underset{j=i-3N/4+1}{\overset{M-i+3N/4}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|$

其中，所述最小绝对误差准则可以为SSAD误差准则，SSAD误差准则定义式如下式所示：

$\mathrm{SSAD}=\underset{i=1}{\overset{N/8}{\mathrm{\Σ}}}|S(i,M/2)-R(i,M/2)|+\underset{i=N/8+1}{\overset{N/4}{\mathrm{\Σ}}}\underset{j=M/2-1}{\overset{M/2+1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4+1}{\overset{3N/8}{\mathrm{\Σ}}}\underset{j=M/2-2}{\overset{M/2+2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{i=3N/8+1}{\overset{N/2}{\mathrm{\Σ}}}\underset{j=M/2-3}{\overset{M/2+3}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/2+1}{\overset{5N/8}{\mathrm{\Σ}}}\underset{j=M/2-4}{\overset{M/2+4}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=5N/8+1}{\overset{3N/4}{\mathrm{\Σ}}}\underset{j=M/2-5}{\overset{M/2+5}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|$

$+\underset{i=3N/4+1}{\overset{7N/8}{\mathrm{\Σ}}}\underset{j=M/2-6}{\overset{M/2+6}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=7N/8+1}{\overset{N}{\mathrm{\Σ}}}\underset{j=M/2-7}{\overset{M/2+7}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|.$

其中，所述最小绝对误差准则可以为WSAD误差准则，WSAD误差准则定义式如下式所示：

$\mathrm{WSAD}=\underset{i=1}{\overset{N/2}{\mathrm{\Σ}}}\underset{j=M/2-i+1}{\overset{M/2+i-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/2+1}{\overset{3N/4-1}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=3N/4}{\overset{3N/4+2}{\mathrm{\Σ}}}\underset{j=3}{\overset{M-3}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{i=3N/4+3}{\overset{N}{\mathrm{\Σ}}}\underset{j=4}{\overset{M-4}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|.$

其中，所述最小绝对误差准则可以为LSAD误差准则，LSAD误差准则定义式如下式所示：

$\mathrm{LSAD}=\underset{i=1}{\overset{N/4}{\mathrm{\Σ}}}\underset{j=M/2-2(i-1)}{\overset{M/2+2(i-1)}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4+1}{\overset{3N/4}{\mathrm{\Σ}}}\underset{j=1}{\overset{M}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=3N/4+1}{\overset{N}{\mathrm{\Σ}}}\underset{j=2(i-3N/4)}{\overset{M-2(i-3N/4)}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|.$

其中，所述最小绝对误差准则可以为SESAD误差准则，SESAD误差准则定义式如下式所示：

$\mathrm{SESAD}=|S(1,M/2)-R(1,M/2)|+\underset{i=2}{\overset{N/4}{\mathrm{\Σ}}}\underset{j=M/2-i-1}{\overset{M/2+i+2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4+1}{\overset{N/2-1}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{j=1}{\overset{M}{\mathrm{\Σ}}}|S(N/2,j)-R(N/2,j)|+\underset{j=N/2+1}{\overset{3N/4}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=3N/4+1}{\overset{3N/4+3}{\mathrm{\Σ}}}\underset{j=i-3N/4+2}{\overset{M-(i-3N/4+1)}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$|S(N,M/2)-R(N,M/2)|.$

其中，所述最小绝对误差准则可以为SLSAD误差准则，SLSAD误差准则定义式如下式所示：

$\mathrm{SLSAD}=|S(1,M/2)-R(1,M/2)|+\underset{j=M/2-3}{\overset{M/2+3}{\mathrm{\Σ}}}|S(2,j)-R(2,j)|+\underset{i=3}{\overset{N/4}{\mathrm{\Σ}}}\underset{j=M/2-5}{\overset{M/2+5}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{i=N/4+1}{\overset{N/2-1}{\mathrm{\Σ}}}\underset{j=M/2-6}{\overset{M/2+6}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{j=1}{\overset{M-1}{\mathrm{\Σ}}}|S(N/2,j)-R(N/2,j)|+\underset{i=N/2+1}{\overset{3N/4-1}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{i=3N/4}{\overset{3N/4+1}{\mathrm{\Σ}}}\underset{j=3}{\overset{M-3}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{j=2}{\overset{M-5}{\mathrm{\Σ}}}|S(3N/4+2,j)-R(3N/4+2,j)|+\underset{i=3N/4+3}{\overset{N}{\mathrm{\Σ}}}\underset{j=M/2-(N-i)}{\overset{M/2+(N-i)}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|.$

其中，所述最小绝对误差准则为YSAD误差准则，YSAD误差准则定义式如下式所示：

$\mathrm{YSAD}=\underset{i=1}{\overset{N/4-1}{\mathrm{\Σ}}}\underset{j=M/2-2i+1}{\overset{M/2+2i-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4}{\overset{N/4+2}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4+3}{\overset{N/2+1}{\mathrm{\Σ}}}\underset{j=1}{\overset{M-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{i=N/2+2}{\overset{3N/4}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=3N/4+1}{\overset{N-1}{\mathrm{\Σ}}}\underset{j=M/2-2(N-i)+1}{\overset{M/2+2(N-i)-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|.$

式中：N是搜索块的垂直方向的像素点数；M是搜索块的水平方向的像素点数；S代表当前块的某像素的亮度或色度值；R代表对应的预测块的对应像素的亮度或色度值；i代表当前块内某像素的水平坐标；j代表当前块内某像素的垂直坐标。

与现有技术相比，本发明具有如下优点：

(1)、本发明的块匹配准则明显提高了运算效率，解决了现有通用匹配准则SAD的效率低下，不能满足数字视频的实时性迫切要求的问题。在运动特征不变的情况下，可以选择六边形、八边形、十二边形、十六边形、圆形等近似圆形的模板来实现，同样可以达到符合运动特征本身、降低算法复杂度和提高效率的目的。在运动特征变化的情况下，可以按照运动物体本身形状、运动规律和运动特性来改变模板的形状，选择三角形、五边形、椭圆形等模板来实现，可以达到同样的效果。

(2)、本发明的运动估计方法，利用了视频图像中当前宏块与相邻宏块间的很强的空间相关性，特别是运动矢量间的强相关性，同时利用大部分相邻宏块的运动矢量代表了当前宏块基本的运动方向的特点，自适应地确定搜索中心，动态调整搜索范围，能在基本不损失信噪比的前提下，大大提高搜索准确度，降低运算复杂度。

(3)、本发明的块匹配准则改变了现有通用匹配准则SAD模板形状的不科学性的现状，从而提高了运算精度。

(4)、本发明的块匹配准则降低了运算复杂度，解决了现有通用匹配准则SAD运算复杂度高，软件技术应用到硬件时受限的问题。

附图说明

图1为本发明新型块匹配运动估计方法的BSAD匹配准则的模板示意图。

图2为本发明新型块匹配运动估计方法的SSAD匹配准则的模板示意图。

图3为本发明新型块匹配运动估计方法的WSAD匹配准则的模板示意图。

图4为本发明新型块匹配运动估计方法的LSAD匹配准则的模板示意图。

图5为本发明新型块匹配运动估计方法的SESAD匹配准则的模板示意图。

图6为本发明新型块匹配运动估计方法的SLSAD匹配准则的模板示意图。

图7为本发明新型块匹配运动估计方法的YSAD匹配准则的模板示意图。

具体实施方式

下面结合附图对本发明作进一步说明：

本发明的方法主要依据是：视频图像运动的连续性以及图像中运动物体的整体性，从而导致了同一帧图像中相邻宏块的运动矢量具有高时空相关性，可以根据已编码块的运动矢量来预测当前块的运动矢量。通过相邻块的运动矢量预测搜索中心，使中心进一步逼近全局最优点，在全局最优点附近的小范围内，找到全局最优点的概率将大大提高，从而可以大大提高编码效率。

本发明的运动估计方法主要包含以下步骤：获取与当前宏块相邻的四个宏块的运动矢量信息。编码以宏块为单位，一个宏块包含1个16×16的亮度块和2个8×8色度块。编码时，按照从左到右，从上到下的顺序一个宏块接着一个宏块进行。假设A，B，C，D为与当前宏块的相邻的左边、右边、上边和下边的四个宏块，获取这四个宏块相对应的x方向和y方向运动矢量，分别为mvx和mvy。若当前宏块四个相邻宏块中某个宏块不存在，则相应的mvx和mvy设为0。从而得到与当前宏块的左边、上边、左上和右上四个宏块相对应的4组值mvx和mvy。

根据上述四个宏块的运动矢量确定搜索中心的x坐标和y坐标，以searchcenter x和search center y表示。自适应搜索中心的确定是根据图像相邻宏块之间的空间相关性，当前宏块与相邻宏块的运动矢量(motion vector)代表了图像整体的运动方向这一原理进行预测的。

具体可分以下几种情况处理：

(1)四个宏块的mvx或mvy，若0的个数大于2，则search center x＝0，searchcenter y＝0；

(2)若四个宏块的mvx或mvy符号均相同，取上述四个块运动矢量的平均值作为搜索中心坐标；

(3)若四个宏块的运动矢量中，有3个宏块的mvx(或mvy)符号相同，取这三个符号相同的mvx(或mvy)的中间值(即数值大小在三个数中排在中间的那个数)作为搜索中心坐标；

(4)若四个宏块的运动矢量中，X轴运动矢量mvx或Y轴运动矢量mvy符号为2正2负，则搜索中心坐标为(0，0)。

搜索范围(search center x，search center y)的确定。

为适应不同运动程度的视频图像序列、提高运动估计的性能，采用自适应搜索窗。扩大的搜索窗对于大运动序列，无疑可以进一步提高运动估计的精度，但对于较小运动序列，却是不必要的浪费。显然，如果能够根据序列本身的运动特性，自适应地确定一个搜索范围，使绝大部分最佳匹配点都落于该范围内，则可在保证PSNR方面性能的同时，降低运算量，提高效率。

根据运动区域的特征，特别是对同一物体，由于构成它的宏块具有高度相关的运动矢量，因此如果利用相邻宏块的运动矢量来预测当前宏块的初始运动矢量，那么找到初始搜索中心位置后，就可以使最终得到的运动矢量更接近于全局最优值，甚至优于用全搜索算法找到的运动矢量。

在上步骤中所述的搜索范围内进行运动搜索，并利用最小绝对误差准则进行匹配或提前终止判定。

其中，如图1所示，所述最小绝对误差准则可以为BSAD误差准则，为八边形匹配模块，BSAD误差准则定义式如下式所示：

$\mathrm{BSAD}=\underset{i=1}{\overset{N/4}{\mathrm{\Σ}}}\underset{j=M/4-i+2}{\overset{3M/4+i-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4+1}{\overset{3N/4}{\mathrm{\Σ}}}\underset{j=1}{\overset{M}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=3N/4+1}{\overset{N}{\mathrm{\Σ}}}\underset{j=i-3N/4+1}{\overset{M-i+3N/4}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|$

其中，如图2所示，所述最小绝对误差准则可以为SSAD误差准则，为三边形匹配模块，SSAD误差准则定义式如下式所示：

$\mathrm{SSAD}=\underset{i=1}{\overset{N/8}{\mathrm{\Σ}}}|S(i,M/2)-R(i,M/2)|+\underset{i=N/8+1}{\overset{N/4}{\mathrm{\Σ}}}\underset{j=M/2-1}{\overset{M/2+1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4+1}{\overset{3N/8}{\mathrm{\Σ}}}\underset{j=M/2-2}{\overset{M/2+2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{i=3N/8+1}{\overset{N/2}{\mathrm{\Σ}}}\underset{j=M/2-3}{\overset{M/2+3}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/2+1}{\overset{5N/8}{\mathrm{\Σ}}}\underset{j=M/2-4}{\overset{M/2+4}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=5N/8+1}{\overset{3N/4}{\mathrm{\Σ}}}\underset{j=M/2-5}{\overset{M/2+5}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|$

$+\underset{i=3N/4+1}{\overset{7N/8}{\mathrm{\Σ}}}\underset{j=M/2-6}{\overset{M/2+6}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=7N/8+1}{\overset{N}{\mathrm{\Σ}}}\underset{j=M/2-7}{\overset{M/2+7}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|.$

其中，如图3所示，所述最小绝对误差准则可以为WSAD误差准则，为五边形匹配模块，WSAD误差准则定义式如下式所示：

$\mathrm{WSAD}=\underset{i=1}{\overset{N/2}{\mathrm{\Σ}}}\underset{j=M/2-i+1}{\overset{M/2+i-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/2+1}{\overset{3N/4-1}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=3N/4}{\overset{3N/4+2}{\mathrm{\Σ}}}\underset{j=3}{\overset{M-3}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{i=3N/4+3}{\overset{N}{\mathrm{\Σ}}}\underset{j=4}{\overset{M-4}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|.$

其中，如图4所示，所述最小绝对误差准则可以为LSAD误差准则，为六边形匹配模块，LSAD误差准则定义式如下式所示：

$\mathrm{LSAD}=\underset{i=1}{\overset{N/4}{\mathrm{\Σ}}}\underset{j=M/2-2(i-1)}{\overset{M/2+2(i-1)}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4+1}{\overset{3N/4}{\mathrm{\Σ}}}\underset{j=1}{\overset{M}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=3N/4+1}{\overset{N}{\mathrm{\Σ}}}\underset{j=2(i-3N/4)}{\overset{M-2(i-3N/4)}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|.$

其中，如图5所示，所述最小绝对误差准则可以为SESAD误差准则，为十二边形匹配模块，SESAD误差准则定义式如下式所示：

$\mathrm{SESAD}=|S(1,M/2)-R(1,M/2)|+\underset{i=2}{\overset{N/4}{\mathrm{\Σ}}}\underset{j=M/2-i-1}{\overset{M/2+i+2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4+1}{\overset{N/2-1}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{j=1}{\overset{M}{\mathrm{\Σ}}}|S(N/2,j)-R(N/2,j)|+\underset{j=N/2+1}{\overset{3N/4}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=3N/4+1}{\overset{3N/4+3}{\mathrm{\Σ}}}\underset{j=i-3N/4+2}{\overset{M-(i-3N/4+1)}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$|S(N,M/2)-R(N,M/2)|.$

其中，如图6所示，所述最小绝对误差准则可以为SLSAD误差准则，为十六边形匹配模块，SLSAD误差准则定义式如下式所示：

$\mathrm{SLSAD}=|S(1,M/2)-R(1,M/2)|+\underset{j=M/2-3}{\overset{M/2+3}{\mathrm{\Σ}}}|S(2,j)-R(2,j)|+\underset{i=3}{\overset{N/4}{\mathrm{\Σ}}}\underset{j=M/2-5}{\overset{M/2+5}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{i=N/4+1}{\overset{N/2-1}{\mathrm{\Σ}}}\underset{j=M/2-6}{\overset{M/2+6}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{j=1}{\overset{M-1}{\mathrm{\Σ}}}|S(N/2,j)-R(N/2,j)|+\underset{i=N/2+1}{\overset{3N/4-1}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{i=3N/4}{\overset{3N/4+1}{\mathrm{\Σ}}}\underset{j=3}{\overset{M-3}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{j=2}{\overset{M-5}{\mathrm{\Σ}}}|S(3N/4+2,j)-R(3N/4+2,j)|+\underset{i=3N/4+3}{\overset{N}{\mathrm{\Σ}}}\underset{j=M/2-(N-i)}{\overset{M/2+(N-i)}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|.$

其中，如图7所示，所述最小绝对误差准则为YSAD误差准则，为圆形匹配模块，YSAD误差准则定义式如下式所示：

$\mathrm{YSAD}=\underset{i=1}{\overset{N/4-1}{\mathrm{\Σ}}}\underset{j=M/2-2i+1}{\overset{M/2+2i-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4}{\overset{N/4+2}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4+3}{\overset{N/2+1}{\mathrm{\Σ}}}\underset{j=1}{\overset{M-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{i=N/2+2}{\overset{3N/4}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=3N/4+1}{\overset{N-1}{\mathrm{\Σ}}}\underset{j=M/2-2(N-i)+1}{\overset{M/2+2(N-i)-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|.$

式中：N是搜索块的垂直方向的像素点数；M是搜索块的水平方向的像素点数；S代表当前块的某像素的亮度或色度值；R代表对应的预测块的对应像素的亮度或色度值；i代表当前块内某像素的水平坐标；j代表当前块内某像素的垂直坐标。

综上所述，本发明能广泛的应用到生产实践中，如H.264编解码标准中的运动估计算法，以及其它基于块匹配的运动估计算法和模式识别，都能带来较多有益效果，具有很强的实用性。

改变匹配准则的模板形状这一思路和改进的模板：八边形、六边形、十二边形、十六边形、圆形、三角形、五边形等等。在运动特征不变的情况下，可以选择六边形、八边形、十二边形、十六边形、圆形等近似圆形的模板来实现，同样可以达到符合运动特征本身、降低算法复杂度和提高效率的目的。在运动特征变化的情况下，可以按照运动物体本身形状、运动规律和运动特性来改变模板的形状，选择三角形、五边形、椭圆形等模板来实现，可以达到同样的效果。

根据不同的匹配准则，SAD值不同，这个SAD值也决定了编码所能接受的搜索精度与编码图像质量：即：给定一个值T(可根据该码流的场景复杂度和运动快慢确定)，当SAD≤T则认为该块的时空相关性高；SAD＞T则认为该块的时空相关性较弱。因此，按照这一方式，对于当前块与相邻块的时空相关性高的搜索，通过SAD≤T判定有效之后直接结束本次搜索；而对于时空相关性比较弱的情况，以少量的计算复杂度为代价，提高该块的搜索精度。

以上显示和描述了本发明的基本原理和主要特征及其优点。本行业的技术人士应该了解，本发明不受上述实施条例的限制，上述实施条例和说明书中描述的只是用于说明本发明的原理，在不脱离本发明原理和范围的前提下，本发明还可有各种变化和改进，这些变化和改进都属于要求保护的本发明范围内。

本发明要求保护范围同所附的权利要求书及其它等效物界定。

Claims (1)

1.一种新型块匹配运动估计方法，其特征在于，包括以下步骤：

(1)获取视频图像中与当前宏块相邻的上、下、左、右四个宏块的运动矢量，若其中某个宏块不存在，则相应的运动矢量赋值为0；

(2)根据所述运动矢量确定搜索中心；

(3)根据所述运动矢量的平均值调整搜索范围；

(4)在步骤(3)中所述的搜索范围内进行运动搜索，根据不同的运动特征选择相应的最小绝对误差准则进行匹配或提前终止判定；

在运动特征不变的情况下，选择最小绝对误差准则BSAD误差准则、LSAD误差准则、SESAD误差准则、SLSAD误差准则或者YSAD误差准则，其中：

BSAD误差准则定义式如下式所示：

$\mathrm{BSAD}=\underset{i=1}{\overset{N/4}{\mathrm{\Σ}}}\underset{j=M/4-i+2}{\overset{3M/4+i-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4+1}{\overset{3N/4}{\mathrm{\Σ}}}\underset{j=1}{\overset{M}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=3N/4+1}{\overset{N}{\mathrm{\Σ}}}\underset{j=i-3N/4+1}{\overset{M-i+3N/4}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|$

LSAD误差准则定义式如下式所示：

$\mathrm{LSAD}=$

$\underset{i=1}{\overset{N/4}{\mathrm{\Σ}}}\underset{j=M/2-2(i-1)}{\overset{M/2+2(i-1)}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4+1}{\overset{3N/4}{\mathrm{\Σ}}}\underset{j=1}{\overset{M}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=3N/4+1}{\overset{N}{\mathrm{\Σ}}}\underset{j=2(i-3N/4)}{\overset{M-2(i-3N/4)}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|$

SESAD误差准则定义式如下式所示：

$\mathrm{SESAD}=|S(1,M/2)-R(1,M/2)|+\underset{i=2}{\overset{N/4}{\mathrm{\Σ}}}\underset{j=M/2-i-1}{\overset{M/2+i+2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4+1}{\overset{N/2-1}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{j=1}{\overset{M}{\mathrm{\Σ}}}|S(N/2,j)-R(N/2,j)|+\underset{j=N/2+1}{\overset{3N/4}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=3N/4+1}{\overset{3N/4+3}{\mathrm{\Σ}}}\underset{j=i-3N/4+2}{\overset{M-(i-3N/4+1)}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$|S(N,M/2)-R(N,M/2)|$

SLSAD误差准则定义式如下式所示：

$\mathrm{SLSAD}=|S(1,M/2)-R(1,M/2)|+\underset{j=M/2-3}{\overset{M/2+3}{\mathrm{\Σ}}}|S(2,j)-R(2,j)|+\underset{i=3}{\overset{N/4}{\mathrm{\Σ}}}\underset{j=M/2-5}{\overset{M/2+5}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{i=N/4+1}{\overset{N/2-1}{\mathrm{\Σ}}}\underset{j=M/2-6}{\overset{M/2+6}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{j=1}{\overset{M-1}{\mathrm{\Σ}}}|S(N/2,j)-R(N/2,j)|+\underset{i=N/2+1}{\overset{3N/4-1}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{i=3N/4}{\overset{3N/4+1}{\mathrm{\Σ}}}\underset{j=3}{\overset{M-3}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{j=2}{\overset{M-5}{\mathrm{\Σ}}}|S(3N/4+2,j)-R(3N/4+2,j)|+\underset{i=3N/4+3}{\overset{N}{\mathrm{\Σ}}}\underset{j=M/2-(N-i)}{\overset{M/2+(N-i)}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|$

YSAD误差准则定义式如下式所示：

$\mathrm{YSAD}=\underset{i=1}{\overset{N/4-1}{\mathrm{\Σ}}}\underset{j=M/2-2i+1}{\overset{M/2+2i-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4}{\overset{N/4+2}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4+3}{\overset{N/2+1}{\mathrm{\Σ}}}\underset{j=1}{\overset{M-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{i=N/2+2}{\overset{3N/4}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=3N/4+1}{\overset{N-1}{\mathrm{\Σ}}}\underset{j=M/2-2(N-i)+1}{\overset{M/2+2(N-i)-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|;$

在运动特征变化的情况下，按照运动物体本身形状、运动规律和运动特性选择最小绝对误差准则SSAD误差准则或者WSAD误差准则，其中：

SSAD误差准则定义式如下式所示：

$\mathrm{SSAD}=\underset{i=1}{\overset{N/8}{\mathrm{\Σ}}}|S(i,M/2)-R(i,M/2)|+\underset{i=N/8+1}{\overset{N/4}{\mathrm{\Σ}}}\underset{j=M/2-1}{\overset{M/2+1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/4+1}{\overset{3N/8}{\mathrm{\Σ}}}\underset{j=M/2-2}{\overset{M/2+2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{i=3N/8+1}{\overset{N/2}{\mathrm{\Σ}}}\underset{j=M/2-3}{\overset{M/2+3}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/2+1}{\overset{5N/8}{\mathrm{\Σ}}}\underset{j=M/2-4}{\overset{M/2+4}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=5N/8+1}{\overset{3N/4}{\mathrm{\Σ}}}\underset{j=M/2-5}{\overset{M/2+5}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|$

$+\underset{i=3N/4+1}{\overset{7N/8}{\mathrm{\Σ}}}\underset{j=M/2-6}{\overset{M/2+6}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=7N/8+1}{\overset{N}{\mathrm{\Σ}}}\underset{j=M/2-7}{\overset{M/2+7}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|$

WSAD误差准则定义式如下式所示：

$\mathrm{WSAD}=\underset{i=1}{\overset{N/2}{\mathrm{\Σ}}}\underset{j=M/2-i+1}{\overset{M/2+i-1}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=N/2+1}{\overset{3N/4-1}{\mathrm{\Σ}}}\underset{j=2}{\overset{M-2}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+\underset{i=3N/4}{\overset{3N/4+2}{\mathrm{\Σ}}}\underset{j=3}{\overset{M-3}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|+$

$\underset{i=3N/4+3}{\overset{N}{\mathrm{\Σ}}}\underset{j=4}{\overset{M-4}{\mathrm{\Σ}}}|S(i,j)-R(i,j)|;$

式中：N是搜索块的垂直方向的像素点数；M是搜索块的水平方向的像素点数；S代表当前块的某像素的亮度或色度值；R代表对应的预测块的对应像素的亮度或色度值；i代表当前块内某像素的水平坐标；j代表当前块内某像素的垂直坐标。

Images