确定一个数据样本与其它数据样本的内插值之间相似程度的制作方法
专利名称：确定一个数据样本与其它数据样本的内插值之间相似程度的制作方法
技术领域：
本发明涉及数据处理，其中对于每个内插值确定数据样本于另一个数据样本和其他数据样本之间内插值之间的相似程度。本发明可以应用于例如利用半像素运动估计的图象编码。
有可能以下列方式确定数据样本与另一个数据样本和其他数据样本之间内插值之间的相似程度。在第一步骤，计算内插值。例如，内插值可以是其他数据样本乘以第一加权系数和另一个数据样本乘以第二加权系数。在第二步骤，对于每个内插值数据样本和内插值之间的差值被计算。所公开的英国专利申请2311435似乎描述了按照该方法的半像素运动估计。
本发明的目的是实现减少成本。
按照本发明，数据样本和另一个数据样本与其他数据样本之间内插值之间的相似程度以下列方式确定。在主要步骤，计算共同部分。共同部分是K乘以数据样本和其他数据样本乘以第一加权系数之间的差值。在其他计算步骤，计算共同部分与各自其他数据样本之间的差值。每个差值对应数据样本与有关内插值之间的相似程度。
本发明考虑下列个方面。方法包括的运算操作数量越大，实现该方法的成本越高。例如，每个运算操作可以通过特定硬件项目实现。如果该方法包括相对多的运算操作，其实现将包括相对多的硬件项目。该方法也通过单一硬件项目实现一个被编程执行该方法的处理器。在许多应用中，该方法将在一定时间限制内执行。该处理器将需要相对快速，如果该方法包括相对多的运算操作。处理器越快，处理器将越昂贵。
现有技术需要下列运算操作。原则上，每个内插值包括至少两个乘法和一个加法。只有一个例外如果加权系数都是0.5，一次加法和一次除以二就可以了。这需要一个减法以计算有关数据样本和内插值之间的差值。假设有N个内插值，N是整数，这意味着需要2N次乘法、N次加法和N次减法。如果加权系数都是0.5，N次加法、N次除法和N次减法就足够了。
按照本发明的方法需要下列运算操作。原则上，基本运算步骤包括两个乘法和一个减法。有一个例外如果加权系数都是0.5，，一个乘法和一个加法就足够了。其他计算步骤包括对于每个内插值的一个减法。假设有N个不同内插值，这意味着需要两个乘法和N+1个减法。如果加权系数都是0.5，一个乘法和N+1个减法就足够了。因此，按照本发明的方法需要的运算操作比现有技术方法的更少。因此，本发明可以实现成本减少。
下面将参照附图更详细地描述本发明的这些和其它方面。
图1是表示上述本发明的基本特征的原理图；图2是表示包括一个运动估计器的MPEG编码器的方框图；图3是表示运动估计器运算方法的流程图；图4是图3所示运算方法细节的流程图。
下面的评述涉及参照标记。相同的条目在所有附图中被指定给相同字母参考。几个类似条目可以出现在单一附图中。在此情况下，数字或前缀被加到字母参照上以便区别类似参照。为方便可以省略该数字或前缀，或者在数值不重要情况下(不考虑数值)可以由通配符替代。这些应用于说明书和权利要求书中。
图1表示了上述本发明的基本特征。对于每个内插值[I]确定数据样本[X]和另一个数据样本[C]与其他数据样本[B]之间内插值之间的相似程度。该内插值[I]是其他数据样本[C]乘以第一加权系数[W1]与另一个数据样本[B]乘以第二加权系数[W2]的总和，公式表示为I＝C×W1+B×W2在主要计算步骤[PCS]，计算共同部分[Y]。共同部分[Y]是第二加权系数[W2]乘以数据样本[X]之间差值和其他数据样本[C]乘以第一加权系数[W1]的倒数。在公式中Y＝1/W2×{X-C×W1}在其他计算步骤[PCS]，计算共同部分[Y]和各自其他数据样本[B]之间的差值[ER]，公式表示为ER＝Y-B每个差值[ER]对应数据样本[X]与有关内插值[I]之间的相似程度。
图1所示的特征可以应用于例如利用半像素运动估计的图象编码。例如，按照由动画专家组(MPEG)定义的标准的图象编码可以利用半像素运动估计。半像素运动估计提供具有半像素精度的运动矢量。
图2表示了MPEG图象编码器。MPEG图象编码器接收图象系列[SOP]。相应地，它提供一个被编码图象数据流[CVS]。该图象编码器包括一个输入电路[INP]，一个运动估计器[MEST]，一个运动补偿器[MCOMP]，一个减法器[SUB]，一个离散余弦变换器和量化器[DCTQ]，一个反离散余弦变换器和量化器[IDCTQ]，一个加法器[ADD]，一个存储器[MEM]，一个变长编码器[VLC]和一个输出电路[OUT]。
MPEG图象编码器操作基本如下。输入电路[INP]实际上将要编码的图象分割成为像素块[MB]。一个像素块[MB]可以以下列方式编码。运动估计器[MEST]确定像素块的一个或几个运动矢量。运动补偿器[MCOMP]根据运动矢量[MV]和已经编码和存储在存储器[MEM]中的图象确定运动补偿像素块[MP]。减法器[SUB]从编码的像素块[MB]中减去运动补偿像素块[MP]。因此，获得误差像素块[MX]。
离散余弦变换器和量化器[DCTQ]对误差像素块[MX]应用一系列处理步骤。这些处理步骤包括一个离散余弦变换和一个量化。因此，获得被量化系数块[CF]。变长编码器[VLC]转换被量化系数块[CF]和运动矢量[MV]成为变长码字[CW]。输出电路[OUT]将一些其他数据加到这些变长码字上并且使各种类型数据形成按照MPEG标准的格式。因此，获得这些被编码图象数据流[OVS]。
已经被编码的像素块[MB]可以属于对于编码随后图象起基础作用的图象。在此情况下，被量化系数块[CF]被应用于反离散余弦变换器和量化器[IDCTQ]。该反离散余弦变换器和量化器[IDCTQ]将一系列处理步骤施加到被量化系数块[CF]，这些步骤功能上是由离散余弦变换器和量化器[DCTQ]所实施一系列步骤的相反运算。因此，将获得被编码误差像素块[MX｀]。加法器[ADD]将被编码误差像素块[MX｀]加到运动补偿像素块[MP]，以便获得被编码像素块[MX]。被编码像素块[MB｀]被存储在存储器[MEM]中，以便后面用于依靠运动估计和补偿对另一个图象编码。
图3表示了运动估计器[MEST]运算的方法。运动估计器[MEST]确定被编码像素块[MB]的运动矢量[MV]。
在步骤S1，运动估计器[MEST]执行具有全像素精度的标准运动估计。实际上，运动估计器[MEST]执行一个搜索，以在被存储在存储器[MEM]内的图象内发现与被编码像素块[MB]类似的像素块。或一个像素块将被称为类似块[MS]。该块在各自图象中可以具有不同位置。位置差值由全像素运动矢量[MV(fp)]指定。各自像素块之间的相似程度由绝对差值(SAD)的总和表示。SAD是各自图象内具有相同位置像素之间绝对差值的总和。
在步骤S2，运动估计器[MEST]对于被编码块[MB]中的每个像素执行下列计算。像素[X]被乘以二。与被编码块[MB]中有关像素具有相同位置的类似块中的像素[C]从该乘法结果[2X]中减去。减法的结果[2X-C]称为共同部分[Y]。因此，运动估计器[MEST]对于被编码块[MB]中的每个像素计算一个共同部分[Y]。因此获得共同部分块[MY]。
在步骤S3，运动估计器[MEST]对于全像素运动矢量[MV(pf)]的每8个可能半像素精度(+1/2，0)，(+1/2，+1/2)，(0，+1/2)，(-1/2，1/2)，(-1/2，0)，(-1/2，-1/2)，(0，-1/2)，(+1/2，-1/2)。逗号之前或之后的数字分别代表水平和垂直方向上的精度。各个SAD全部以相同方式根据共同部分块[MT]和具有相邻像素的类似块[MS]计算。该计算在后面将描述。
实际上，全像素运动矢量[MV(pf)]的半像素精度的SAD是如果下列三个步骤被应用于被编码块[MB]中每个像素[X]所获得的SAD。在第一步骤内插值[I]是由一方面具有与被编码块[MB]内像素[X]相同位置的类似块[MS]内像素[C]，和另一方面某个方向上相邻像素[B]组成。该方向由所讨论的半像素精度定义。例如，假设所讨论的半像素精度是(＝1/2，-1/2)。在此情况下，内插值[I]有关类似块[MS]中右上相邻像素[C]。在第二步骤，被编码块[MB]中像素[X]与内插值[I]之间的绝对差值被计算。在第三步骤，绝对差值被加到对于被编码块[MB]中其它像素已经计算出的绝对差值总和中。可是，按照本发明，用后面将描述的不同方式计算半像素精度的SAD。
在步骤S4，运动估计器[MEST]比较各种不同SAD有关全像素运动矢量[MV(pf)]的SAD和有关该运动矢量8个不同半像素精度的8个SAD。有关全像素运动矢量[MV(pf)]的SAD可能具有最低数值。在此情况下，运动估计器[MEST]将提供该运动矢量作为起运动补偿作用的运动矢量。可是，也可能有关某个半像素精度的SAD具有最低数值。在此情况下，运动估计器[MEST]将按照有关半像素精度调节全像素运动矢量[MV(pf)]。例如，假设半像素精度(+1/2，+1/2)提供最低SAD。在此情况下，全像素运动矢量[MV(pf)]将通过在水平和垂直方向上将正半像素单位加到全像素运动矢量上来调节。运动估计器[MEST]然后将提供被调节全像素运动矢量作为起运动补偿作用的运动矢量[MV]。
图4表示如何计算半像素精度的SAD。该计算在图3所示的方法步骤S3中执行。已经声明，半像素精度的SAD是根据在步骤S2已经确定的共同部分块[MY]、类似块[MS]和其相邻像素计算的。
半像素精度的SAD计算包括三个分步骤S3-1，S3-3和S3-3。运动估计器[MEST]对于共同部分块[MY]中的每个共同部分[Y]执行这些三个分步骤。
在分步骤S3-1，运动估计器[MEST]读取存储在存储器[MEM]内的像素[B]。被读取的像素[B]是类似块[MS]中相邻像素[C]，其位置对应有关共同部分[Y]的位置。在八个不同方向上有8个可能相邻像素(+1，0)，(+1，+1)，(0，+1)，(-1，-1)，(-1，0)，(-1，-1)，(0，-1)，(+1，-1)。读取对应半像素精度的该方向上相邻像素。例如，假设对于半像素精度(+1/2，0)进行SAD计算。在此情况下，在方向(+1，0)中读取相邻像素。为实现该例子，假设当前共同部分[Y]的位置是(5，5)。在此情况下，运动估计器[MEST]将读取类似块[MS]中具有位置(6，5)的像素[B]。
在分步骤S3-2运动估计器[MEST]确定共同部分[Y]与像素[B]之间的绝对差值[ABS(Y-B)]，它已经从存储器[MEM]中读取。绝对差值[ABS(Y-B)]等于比例系数乘以绝对差值，该差值是一方面用于计算共同部分[Y]的被编码块[MB]中像素[X]与另一方面存储器[MEM]内两个像素内插值之间的差值。内插值涉及类似块[MS]中像素[C]，其位置对应被编码块内像素[X]的位置，还涉及类似块中像素[C]在感兴趣方向上的相邻像素。比例系数是二。
在分步骤S3-3，运动估计器[MEST]将在最新分步骤S3-2中确定的绝对差值[ABS(Y-B)]加到累计绝对差值中[ACC(ABS(Y-B))]。累计绝对差值[ACC(ABS(Y-B))]是在最新分步骤S3-2以前的分步骤S3-2中已经确定的绝对差值的总和。不用说，在分别执行三个分步骤S3-1、S3-2和S3-3之前累计绝对差值[ACC(ABS(Y-B))]初始被设置为零，以便计算某个半像素精度的SAD。
当对于共同部分[Y]已经执行了三个分步骤S3-1，S3-2和S3-3时，累计绝对差值[ACC(ABS(Y-B))]被除以二。该除法的结果是有关半像素精度的SAD。
在分步骤S3-1，S3-2和S3-3中执行的运算也可以用于执行全像素运动估计。图1所示的方法步骤S1中进行全像素运动估计。因此，也可能利用相同硬件项目或软件执行步骤S1和S3，步骤S3包括分步骤S3-1，S3-2和S3-3。这种共同性进一步有助于成本效率。
图2所示的MPEG图象编码器是具有图1所示的特征的实施例的例子，其运算在图3和4中表示。图1中的加权系数W1，W2在MPEG图象编码器中都是0.5。图1所示的初步计算步骤以图3所示的步骤S2形成实现。由于加权系数都是0.5，共同部分[Y]被计算为Y＝2X-C。图1中的其他计算步骤[PCS]以图3所示步骤S3形式实现。
更具体地，MPEG图象编码器对于被编码像素块[MB]中的每个像素[X]应用图1所示的特征。在步骤S2，MPEG图象编码器为每个像素[X]执行初步步骤[PCS]。因此，在步骤S3，MPEG图象编码器执行与初步步骤[PCS]相伴的其他计算步骤[FCS]。一个像素[X]的其他计算步骤[FCS]涉及8个不同SAD计算。在每个SAD计算中，MPEG图象编码器计算已经为像素[X]确定的共同部分[Y]与类似块[MS]中位置对应被编码块[MB]中像素[X]位置的像素[C]的相邻像素之间的差值。
该附图和前面的说明表示而非限制本发明。很显然，存在落入附带权利要求书范围内的大量替代。为此，进行下列总结评论。
存在许多可以使用图1所示特征的数据处理应用。图2-4仅仅表示了涉及图象编码的一个可能应用。应当认为，图1所示的特征可以用于任何类型的数据处理，该数据处理需要考察一个数据样本与其他数据样本内插值之间的相似程度。
存在大量可以进行的不同类型内插。图2-4仅仅表示了加权系数都是0.5的一种可能实施例。其他可能的实施例是例如加权系数W1和W2分别是3/4和1/4。在此情况下，共同部分将服从Y＝4X-3C。这种实施例可以应用于例如执行四分之一像素运动估计。图4所示的方法可以应用于计算一个SAD。则累计绝对差值[ACC(ABS(Y-B))]应当被除以四。
存在按照本发明计算SAD的各种方式。图2-4仅仅表示了分开一个一个地计算SAD的一种可能实施例。另一个可能实施例是各种SAD被同时平行计算。例如，可以对每个共同部分[Y]顺序地执行下列步骤。在第一步骤，属于有关共同部分[Y]的各种相邻像素被读取。在第二步骤，利用每个相邻像素[B]确定绝对差值[ABS(Y-B)]。每个绝对差值涉及不同SAD计算。在第三步骤，绝对差值被加到涉及相同SAD计算的前面计算出绝对差值的总和中。这样，与步骤S3-3相比，存在各种平行的绝对差值累加，每个累加有关一个不同SAD。
存在大量通过硬件项目和软件或两者实现功能的方式。为此，附图是概略图，每个只代表本发明的一种可能实施例。这样，尽管附图表示了不同功能作为不同块，这不排除单一硬件项目或软件执行几个功能。这也不排除硬件项目和/或软件的组合体来执行功能。
例如，图2所示的MPEG图象编码器运动估计器[MEST]可以采用能够执行各种功能的处理器形式。被加栽到程序存储器内的一组指令使处理器执行图3和4所示的方法。另一组指令可以被加载到程序存储器，以便使处理器执行例如运动补偿。使处理器执行图3和4所示方法的该组指令可以被存储在数据载体上，例如磁盘。该数据载体不必形成图2所示的MPEG图象编码器的一部分。该组指令可以从数据载体上读取，以便被加载到处理器的程序存储器中，然后实现运动估计器[MEST]的任务。
权利要求中的参考标记不构成对权利要求的限制。动词“包括”不排除使用权利要求中所定义的任何其他元件和步骤。前缀在元件和步骤之前的不定冠词“一个”不排除使用多个这种元件和步骤。
权利要求
1.一种数据处理方法，其中对于每个内插值[I]确定一个数据样本[X]和另一个数据样本[C]与其他数据样本[B]之间内插值[I]之间的相似程度，该内插值[I]是其他数据样本[C]乘以第一加权系数[W1]和其他数据样本[B]乘以第二加权系数[W2]之和(I＝C×W1+B×W2)，特征在于该方法包括一个初步计算步骤[PCS]，其中计算一个共同部分[Y]，该共同部分[Y]是第二加权系数[W2]乘以数据样本[X]与其他数据样本[C]乘以第一加权系数[W1]之间差值的倒数(Y＝1/W2×{X-C×W1})；和一个进一步计算步骤[FCS]，其中计算共同部分[Y]与各自其他数据样本[B]之间的差值[ER]，(ER＝Y-B)，每个差值[ER]对应数据样本[X]和有关内插值[I]之间的相似程度。
2.一种数据处理设备，用于对于每个内插值[I]确定一个数据样本[X]和另一个数据样本[C]与其他数据样本[B]之间内插值[I]之间的相似程度，该内插值[I]是其他数据样本[C]乘以第一加权系数[W1]和其他数据样本[B]乘以第二加权系数[W2]之和(I＝C×W1+B×W2)，特征在于该数据处理设备被编程以执行下列步骤一个初步计算步骤[PCS]，其中计算一个共同部分[Y]，该共同部分[Y]是第二加权系数[W2]乘以数据样本[X]与其他数据样本[C]乘以第一加权系数[W1]之间差值的倒数(Y＝1/W2×{X-C×W1})；和一个进一步计算步骤[FCS]，其中计算共同部分[Y]与各自其他数据样本[B]之间的差值[ER]，(ER＝Y-B)，每个差值[ER]对应数据样本[X]和有关内插值[I]之间的相似程度。
3.一种用于数据处理器的计算机程序产品，该计算机程序产品包括一组指令，该指令当被加载到数据处理器的程序存储器内时，使该数据处理器对于每个内插值[I]确定一个数据样本[X]和另一个数据样本[C]与其他数据样本[B]之间内插值[I]之间的相似程度，该内插值[I]是其他数据样本[C]乘以第一加权系数[W1]和其他数据样本[B]乘以第二加权系数[W2]之和(I＝C×W1+B×W2)，按照下列步骤确定相似程度一个初步计算步骤[PCS]，其中计算一个其同部分[Y]，该共同部分[Y]是第二加权系数[W2]乘以数据样本[X]与其他数据样本[C]乘以第一加权系数[W1]之间差值的倒数(Y＝1/W2×{X-C×W1})；和一个进一步计算步骤[FCS]，其中计算共同部分[Y]与各自其他数据样本[B]之间的差值[ER]，(ER＝Y-B)，每个差值[ER]对应数据样本[X]和有关内插值[I]之间的相似程度。
4.一种图象编码方法，其中对于每个内插值[I]确定一个数据样本[X]和另一个数据样本[C]与其他数据样本[B]之间内插值[I]之间的相似程度，该内插值[I]是其他数据样本[C]乘以第一加权系数[W1]和其他数据样本[B]乘以第二加权系数[W2]之和(I＝C×W1+B×W2)，特征在于该方法包括一个初步计算步骤[PCS]，其中计算一个共同部分[Y]，该共同部分[Y]是第二加权系数[W2]乘以数据样本[X]与其他数据样本[C]乘以第一加权系数[W1]之间差值的倒数(Y＝1/W2×{X-C×W1})；和一个进一步计算步骤[FCS]，其中计算共同部分[Y]与各自其他数据样本[B]之间的差值[ER]，(ER＝Y-B)，每个差值[ER]对应数据样本[X]和有关内插值[I]之间的相似程度。
全文摘要
具有半像素运动估计的图象编码是数据处理的一种例子,其中对于每个内插值[I]确定一个数据样本[X]与另一个数据样本[C]和另外数据样本[B]之间内插值[I]的相似程度。内插值[I]是其它数据样本[C]乘以第一加权系数[W1]与其它数据样本[B]乘以第二加权系数[W2]的和,表达式为:I=CxW1+BxW2。下列方法允许利用相对少的运算操作执行该数据处理。在基本计算步骤中[PCS],计算共同部分[Y]。共同部分[Y]是第二加权系数[W2]乘以数据样本[X]于其它数据样本[C]之间差值再乘以第一加权系数的倒数,公式表示为:Y=1/W2x{X－CxW1}。在另一个计算步骤[PCS],计算共同部分[Y]与各自其它数据样本[B]之间的差值,公式表示为:ER=Y－B。每个差值[ER]对应数据样本[X]于有关的内插值[I]之间的相似程度。
文档编号H04N7/32GK1383671SQ01801625
公开日2002年12月4日 申请日期2001年4月2日 优先权日2000年4月11日
发明者J·戈贝尔特 申请人:皇家菲利浦电子有限公司
技术领域：
本发明涉及数据处理，其中对于每个内插值确定数据样本于另一个数据样本和其他数据样本之间内插值之间的相似程度。本发明可以应用于例如利用半像素运动估计的图象编码。
有可能以下列方式确定数据样本与另一个数据样本和其他数据样本之间内插值之间的相似程度。在第一步骤，计算内插值。例如，内插值可以是其他数据样本乘以第一加权系数和另一个数据样本乘以第二加权系数。在第二步骤，对于每个内插值数据样本和内插值之间的差值被计算。所公开的英国专利申请2311435似乎描述了按照该方法的半像素运动估计。
本发明的目的是实现减少成本。
按照本发明，数据样本和另一个数据样本与其他数据样本之间内插值之间的相似程度以下列方式确定。在主要步骤，计算共同部分。共同部分是K乘以数据样本和其他数据样本乘以第一加权系数之间的差值。在其他计算步骤，计算共同部分与各自其他数据样本之间的差值。每个差值对应数据样本与有关内插值之间的相似程度。
本发明考虑下列个方面。方法包括的运算操作数量越大，实现该方法的成本越高。例如，每个运算操作可以通过特定硬件项目实现。如果该方法包括相对多的运算操作，其实现将包括相对多的硬件项目。该方法也通过单一硬件项目实现一个被编程执行该方法的处理器。在许多应用中，该方法将在一定时间限制内执行。该处理器将需要相对快速，如果该方法包括相对多的运算操作。处理器越快，处理器将越昂贵。
现有技术需要下列运算操作。原则上，每个内插值包括至少两个乘法和一个加法。只有一个例外如果加权系数都是0.5，一次加法和一次除以二就可以了。这需要一个减法以计算有关数据样本和内插值之间的差值。假设有N个内插值，N是整数，这意味着需要2N次乘法、N次加法和N次减法。如果加权系数都是0.5，N次加法、N次除法和N次减法就足够了。
按照本发明的方法需要下列运算操作。原则上，基本运算步骤包括两个乘法和一个减法。有一个例外如果加权系数都是0.5，，一个乘法和一个加法就足够了。其他计算步骤包括对于每个内插值的一个减法。假设有N个不同内插值，这意味着需要两个乘法和N+1个减法。如果加权系数都是0.5，一个乘法和N+1个减法就足够了。因此，按照本发明的方法需要的运算操作比现有技术方法的更少。因此，本发明可以实现成本减少。
下面将参照附图更详细地描述本发明的这些和其它方面。
图1是表示上述本发明的基本特征的原理图；图2是表示包括一个运动估计器的MPEG编码器的方框图；图3是表示运动估计器运算方法的流程图；图4是图3所示运算方法细节的流程图。
下面的评述涉及参照标记。相同的条目在所有附图中被指定给相同字母参考。几个类似条目可以出现在单一附图中。在此情况下，数字或前缀被加到字母参照上以便区别类似参照。为方便可以省略该数字或前缀，或者在数值不重要情况下(不考虑数值)可以由通配符替代。这些应用于说明书和权利要求书中。
图1表示了上述本发明的基本特征。对于每个内插值[I]确定数据样本[X]和另一个数据样本[C]与其他数据样本[B]之间内插值之间的相似程度。该内插值[I]是其他数据样本[C]乘以第一加权系数[W1]与另一个数据样本[B]乘以第二加权系数[W2]的总和，公式表示为I＝C×W1+B×W2在主要计算步骤[PCS]，计算共同部分[Y]。共同部分[Y]是第二加权系数[W2]乘以数据样本[X]之间差值和其他数据样本[C]乘以第一加权系数[W1]的倒数。在公式中Y＝1/W2×{X-C×W1}在其他计算步骤[PCS]，计算共同部分[Y]和各自其他数据样本[B]之间的差值[ER]，公式表示为ER＝Y-B每个差值[ER]对应数据样本[X]与有关内插值[I]之间的相似程度。
图1所示的特征可以应用于例如利用半像素运动估计的图象编码。例如，按照由动画专家组(MPEG)定义的标准的图象编码可以利用半像素运动估计。半像素运动估计提供具有半像素精度的运动矢量。
图2表示了MPEG图象编码器。MPEG图象编码器接收图象系列[SOP]。相应地，它提供一个被编码图象数据流[CVS]。该图象编码器包括一个输入电路[INP]，一个运动估计器[MEST]，一个运动补偿器[MCOMP]，一个减法器[SUB]，一个离散余弦变换器和量化器[DCTQ]，一个反离散余弦变换器和量化器[IDCTQ]，一个加法器[ADD]，一个存储器[MEM]，一个变长编码器[VLC]和一个输出电路[OUT]。
MPEG图象编码器操作基本如下。输入电路[INP]实际上将要编码的图象分割成为像素块[MB]。一个像素块[MB]可以以下列方式编码。运动估计器[MEST]确定像素块的一个或几个运动矢量。运动补偿器[MCOMP]根据运动矢量[MV]和已经编码和存储在存储器[MEM]中的图象确定运动补偿像素块[MP]。减法器[SUB]从编码的像素块[MB]中减去运动补偿像素块[MP]。因此，获得误差像素块[MX]。
离散余弦变换器和量化器[DCTQ]对误差像素块[MX]应用一系列处理步骤。这些处理步骤包括一个离散余弦变换和一个量化。因此，获得被量化系数块[CF]。变长编码器[VLC]转换被量化系数块[CF]和运动矢量[MV]成为变长码字[CW]。输出电路[OUT]将一些其他数据加到这些变长码字上并且使各种类型数据形成按照MPEG标准的格式。因此，获得这些被编码图象数据流[OVS]。
已经被编码的像素块[MB]可以属于对于编码随后图象起基础作用的图象。在此情况下，被量化系数块[CF]被应用于反离散余弦变换器和量化器[IDCTQ]。该反离散余弦变换器和量化器[IDCTQ]将一系列处理步骤施加到被量化系数块[CF]，这些步骤功能上是由离散余弦变换器和量化器[DCTQ]所实施一系列步骤的相反运算。因此，将获得被编码误差像素块[MX｀]。加法器[ADD]将被编码误差像素块[MX｀]加到运动补偿像素块[MP]，以便获得被编码像素块[MX]。被编码像素块[MB｀]被存储在存储器[MEM]中，以便后面用于依靠运动估计和补偿对另一个图象编码。
图3表示了运动估计器[MEST]运算的方法。运动估计器[MEST]确定被编码像素块[MB]的运动矢量[MV]。
在步骤S1，运动估计器[MEST]执行具有全像素精度的标准运动估计。实际上，运动估计器[MEST]执行一个搜索，以在被存储在存储器[MEM]内的图象内发现与被编码像素块[MB]类似的像素块。或一个像素块将被称为类似块[MS]。该块在各自图象中可以具有不同位置。位置差值由全像素运动矢量[MV(fp)]指定。各自像素块之间的相似程度由绝对差值(SAD)的总和表示。SAD是各自图象内具有相同位置像素之间绝对差值的总和。
在步骤S2，运动估计器[MEST]对于被编码块[MB]中的每个像素执行下列计算。像素[X]被乘以二。与被编码块[MB]中有关像素具有相同位置的类似块中的像素[C]从该乘法结果[2X]中减去。减法的结果[2X-C]称为共同部分[Y]。因此，运动估计器[MEST]对于被编码块[MB]中的每个像素计算一个共同部分[Y]。因此获得共同部分块[MY]。
在步骤S3，运动估计器[MEST]对于全像素运动矢量[MV(pf)]的每8个可能半像素精度(+1/2，0)，(+1/2，+1/2)，(0，+1/2)，(-1/2，1/2)，(-1/2，0)，(-1/2，-1/2)，(0，-1/2)，(+1/2，-1/2)。逗号之前或之后的数字分别代表水平和垂直方向上的精度。各个SAD全部以相同方式根据共同部分块[MT]和具有相邻像素的类似块[MS]计算。该计算在后面将描述。
实际上，全像素运动矢量[MV(pf)]的半像素精度的SAD是如果下列三个步骤被应用于被编码块[MB]中每个像素[X]所获得的SAD。在第一步骤内插值[I]是由一方面具有与被编码块[MB]内像素[X]相同位置的类似块[MS]内像素[C]，和另一方面某个方向上相邻像素[B]组成。该方向由所讨论的半像素精度定义。例如，假设所讨论的半像素精度是(＝1/2，-1/2)。在此情况下，内插值[I]有关类似块[MS]中右上相邻像素[C]。在第二步骤，被编码块[MB]中像素[X]与内插值[I]之间的绝对差值被计算。在第三步骤，绝对差值被加到对于被编码块[MB]中其它像素已经计算出的绝对差值总和中。可是，按照本发明，用后面将描述的不同方式计算半像素精度的SAD。
在步骤S4，运动估计器[MEST]比较各种不同SAD有关全像素运动矢量[MV(pf)]的SAD和有关该运动矢量8个不同半像素精度的8个SAD。有关全像素运动矢量[MV(pf)]的SAD可能具有最低数值。在此情况下，运动估计器[MEST]将提供该运动矢量作为起运动补偿作用的运动矢量。可是，也可能有关某个半像素精度的SAD具有最低数值。在此情况下，运动估计器[MEST]将按照有关半像素精度调节全像素运动矢量[MV(pf)]。例如，假设半像素精度(+1/2，+1/2)提供最低SAD。在此情况下，全像素运动矢量[MV(pf)]将通过在水平和垂直方向上将正半像素单位加到全像素运动矢量上来调节。运动估计器[MEST]然后将提供被调节全像素运动矢量作为起运动补偿作用的运动矢量[MV]。
图4表示如何计算半像素精度的SAD。该计算在图3所示的方法步骤S3中执行。已经声明，半像素精度的SAD是根据在步骤S2已经确定的共同部分块[MY]、类似块[MS]和其相邻像素计算的。
半像素精度的SAD计算包括三个分步骤S3-1，S3-3和S3-3。运动估计器[MEST]对于共同部分块[MY]中的每个共同部分[Y]执行这些三个分步骤。
在分步骤S3-1，运动估计器[MEST]读取存储在存储器[MEM]内的像素[B]。被读取的像素[B]是类似块[MS]中相邻像素[C]，其位置对应有关共同部分[Y]的位置。在八个不同方向上有8个可能相邻像素(+1，0)，(+1，+1)，(0，+1)，(-1，-1)，(-1，0)，(-1，-1)，(0，-1)，(+1，-1)。读取对应半像素精度的该方向上相邻像素。例如，假设对于半像素精度(+1/2，0)进行SAD计算。在此情况下，在方向(+1，0)中读取相邻像素。为实现该例子，假设当前共同部分[Y]的位置是(5，5)。在此情况下，运动估计器[MEST]将读取类似块[MS]中具有位置(6，5)的像素[B]。
在分步骤S3-2运动估计器[MEST]确定共同部分[Y]与像素[B]之间的绝对差值[ABS(Y-B)]，它已经从存储器[MEM]中读取。绝对差值[ABS(Y-B)]等于比例系数乘以绝对差值，该差值是一方面用于计算共同部分[Y]的被编码块[MB]中像素[X]与另一方面存储器[MEM]内两个像素内插值之间的差值。内插值涉及类似块[MS]中像素[C]，其位置对应被编码块内像素[X]的位置，还涉及类似块中像素[C]在感兴趣方向上的相邻像素。比例系数是二。
在分步骤S3-3，运动估计器[MEST]将在最新分步骤S3-2中确定的绝对差值[ABS(Y-B)]加到累计绝对差值中[ACC(ABS(Y-B))]。累计绝对差值[ACC(ABS(Y-B))]是在最新分步骤S3-2以前的分步骤S3-2中已经确定的绝对差值的总和。不用说，在分别执行三个分步骤S3-1、S3-2和S3-3之前累计绝对差值[ACC(ABS(Y-B))]初始被设置为零，以便计算某个半像素精度的SAD。
当对于共同部分[Y]已经执行了三个分步骤S3-1，S3-2和S3-3时，累计绝对差值[ACC(ABS(Y-B))]被除以二。该除法的结果是有关半像素精度的SAD。
在分步骤S3-1，S3-2和S3-3中执行的运算也可以用于执行全像素运动估计。图1所示的方法步骤S1中进行全像素运动估计。因此，也可能利用相同硬件项目或软件执行步骤S1和S3，步骤S3包括分步骤S3-1，S3-2和S3-3。这种共同性进一步有助于成本效率。
图2所示的MPEG图象编码器是具有图1所示的特征的实施例的例子，其运算在图3和4中表示。图1中的加权系数W1，W2在MPEG图象编码器中都是0.5。图1所示的初步计算步骤以图3所示的步骤S2形成实现。由于加权系数都是0.5，共同部分[Y]被计算为Y＝2X-C。图1中的其他计算步骤[PCS]以图3所示步骤S3形式实现。
更具体地，MPEG图象编码器对于被编码像素块[MB]中的每个像素[X]应用图1所示的特征。在步骤S2，MPEG图象编码器为每个像素[X]执行初步步骤[PCS]。因此，在步骤S3，MPEG图象编码器执行与初步步骤[PCS]相伴的其他计算步骤[FCS]。一个像素[X]的其他计算步骤[FCS]涉及8个不同SAD计算。在每个SAD计算中，MPEG图象编码器计算已经为像素[X]确定的共同部分[Y]与类似块[MS]中位置对应被编码块[MB]中像素[X]位置的像素[C]的相邻像素之间的差值。
该附图和前面的说明表示而非限制本发明。很显然，存在落入附带权利要求书范围内的大量替代。为此，进行下列总结评论。
存在许多可以使用图1所示特征的数据处理应用。图2-4仅仅表示了涉及图象编码的一个可能应用。应当认为，图1所示的特征可以用于任何类型的数据处理，该数据处理需要考察一个数据样本与其他数据样本内插值之间的相似程度。
存在大量可以进行的不同类型内插。图2-4仅仅表示了加权系数都是0.5的一种可能实施例。其他可能的实施例是例如加权系数W1和W2分别是3/4和1/4。在此情况下，共同部分将服从Y＝4X-3C。这种实施例可以应用于例如执行四分之一像素运动估计。图4所示的方法可以应用于计算一个SAD。则累计绝对差值[ACC(ABS(Y-B))]应当被除以四。
存在按照本发明计算SAD的各种方式。图2-4仅仅表示了分开一个一个地计算SAD的一种可能实施例。另一个可能实施例是各种SAD被同时平行计算。例如，可以对每个共同部分[Y]顺序地执行下列步骤。在第一步骤，属于有关共同部分[Y]的各种相邻像素被读取。在第二步骤，利用每个相邻像素[B]确定绝对差值[ABS(Y-B)]。每个绝对差值涉及不同SAD计算。在第三步骤，绝对差值被加到涉及相同SAD计算的前面计算出绝对差值的总和中。这样，与步骤S3-3相比，存在各种平行的绝对差值累加，每个累加有关一个不同SAD。
存在大量通过硬件项目和软件或两者实现功能的方式。为此，附图是概略图，每个只代表本发明的一种可能实施例。这样，尽管附图表示了不同功能作为不同块，这不排除单一硬件项目或软件执行几个功能。这也不排除硬件项目和/或软件的组合体来执行功能。
例如，图2所示的MPEG图象编码器运动估计器[MEST]可以采用能够执行各种功能的处理器形式。被加栽到程序存储器内的一组指令使处理器执行图3和4所示的方法。另一组指令可以被加载到程序存储器，以便使处理器执行例如运动补偿。使处理器执行图3和4所示方法的该组指令可以被存储在数据载体上，例如磁盘。该数据载体不必形成图2所示的MPEG图象编码器的一部分。该组指令可以从数据载体上读取，以便被加载到处理器的程序存储器中，然后实现运动估计器[MEST]的任务。
权利要求中的参考标记不构成对权利要求的限制。动词“包括”不排除使用权利要求中所定义的任何其他元件和步骤。前缀在元件和步骤之前的不定冠词“一个”不排除使用多个这种元件和步骤。
权利要求
1.一种数据处理方法，其中对于每个内插值[I]确定一个数据样本[X]和另一个数据样本[C]与其他数据样本[B]之间内插值[I]之间的相似程度，该内插值[I]是其他数据样本[C]乘以第一加权系数[W1]和其他数据样本[B]乘以第二加权系数[W2]之和(I＝C×W1+B×W2)，特征在于该方法包括一个初步计算步骤[PCS]，其中计算一个共同部分[Y]，该共同部分[Y]是第二加权系数[W2]乘以数据样本[X]与其他数据样本[C]乘以第一加权系数[W1]之间差值的倒数(Y＝1/W2×{X-C×W1})；和一个进一步计算步骤[FCS]，其中计算共同部分[Y]与各自其他数据样本[B]之间的差值[ER]，(ER＝Y-B)，每个差值[ER]对应数据样本[X]和有关内插值[I]之间的相似程度。
2.一种数据处理设备，用于对于每个内插值[I]确定一个数据样本[X]和另一个数据样本[C]与其他数据样本[B]之间内插值[I]之间的相似程度，该内插值[I]是其他数据样本[C]乘以第一加权系数[W1]和其他数据样本[B]乘以第二加权系数[W2]之和(I＝C×W1+B×W2)，特征在于该数据处理设备被编程以执行下列步骤一个初步计算步骤[PCS]，其中计算一个共同部分[Y]，该共同部分[Y]是第二加权系数[W2]乘以数据样本[X]与其他数据样本[C]乘以第一加权系数[W1]之间差值的倒数(Y＝1/W2×{X-C×W1})；和一个进一步计算步骤[FCS]，其中计算共同部分[Y]与各自其他数据样本[B]之间的差值[ER]，(ER＝Y-B)，每个差值[ER]对应数据样本[X]和有关内插值[I]之间的相似程度。
3.一种用于数据处理器的计算机程序产品，该计算机程序产品包括一组指令，该指令当被加载到数据处理器的程序存储器内时，使该数据处理器对于每个内插值[I]确定一个数据样本[X]和另一个数据样本[C]与其他数据样本[B]之间内插值[I]之间的相似程度，该内插值[I]是其他数据样本[C]乘以第一加权系数[W1]和其他数据样本[B]乘以第二加权系数[W2]之和(I＝C×W1+B×W2)，按照下列步骤确定相似程度一个初步计算步骤[PCS]，其中计算一个其同部分[Y]，该共同部分[Y]是第二加权系数[W2]乘以数据样本[X]与其他数据样本[C]乘以第一加权系数[W1]之间差值的倒数(Y＝1/W2×{X-C×W1})；和一个进一步计算步骤[FCS]，其中计算共同部分[Y]与各自其他数据样本[B]之间的差值[ER]，(ER＝Y-B)，每个差值[ER]对应数据样本[X]和有关内插值[I]之间的相似程度。
4.一种图象编码方法，其中对于每个内插值[I]确定一个数据样本[X]和另一个数据样本[C]与其他数据样本[B]之间内插值[I]之间的相似程度，该内插值[I]是其他数据样本[C]乘以第一加权系数[W1]和其他数据样本[B]乘以第二加权系数[W2]之和(I＝C×W1+B×W2)，特征在于该方法包括一个初步计算步骤[PCS]，其中计算一个共同部分[Y]，该共同部分[Y]是第二加权系数[W2]乘以数据样本[X]与其他数据样本[C]乘以第一加权系数[W1]之间差值的倒数(Y＝1/W2×{X-C×W1})；和一个进一步计算步骤[FCS]，其中计算共同部分[Y]与各自其他数据样本[B]之间的差值[ER]，(ER＝Y-B)，每个差值[ER]对应数据样本[X]和有关内插值[I]之间的相似程度。
全文摘要
具有半像素运动估计的图象编码是数据处理的一种例子,其中对于每个内插值[I]确定一个数据样本[X]与另一个数据样本[C]和另外数据样本[B]之间内插值[I]的相似程度。内插值[I]是其它数据样本[C]乘以第一加权系数[W1]与其它数据样本[B]乘以第二加权系数[W2]的和,表达式为:I=CxW1+BxW2。下列方法允许利用相对少的运算操作执行该数据处理。在基本计算步骤中[PCS],计算共同部分[Y]。共同部分[Y]是第二加权系数[W2]乘以数据样本[X]于其它数据样本[C]之间差值再乘以第一加权系数的倒数,公式表示为:Y=1/W2x{X－CxW1}。在另一个计算步骤[PCS],计算共同部分[Y]与各自其它数据样本[B]之间的差值,公式表示为:ER=Y－B。每个差值[ER]对应数据样本[X]于有关的内插值[I]之间的相似程度。
文档编号H04N7/32GK1383671SQ01801625
公开日2002年12月4日 申请日期2001年4月2日 优先权日2000年4月11日
发明者J·戈贝尔特 申请人:皇家菲利浦电子有限公司
最新回复(0)