使用可变块尺寸的分层运动估算装置和方法

摘要

本发明公开了一种装置和一种与之相伴的方法,用于使用结合N标度叠放的M元金字塔分解以在确定基于块的运动估算的运动矢量时降低计算的复杂性。

说明书

本发明一般涉及一种用于编码图象序列的系统，并且特别涉及一种装置和一种与之相伴的方法，它采用“多标度块叠放(multi-scale block tiling)”以在确定基于块的运动估算的运动矢量时降低计算复杂性并且提高运动估算的精确度。

诸如视频图象序列的图象序列通常包括一系列的图象帧或画面。包括移动对象的视频的重放通常要求每秒三十个图象帧的帧速，其中每帧可包含多于一兆字节的信息。因此，传输或存储这种图象序列需要大量的传输带宽或存储容量。为了减少必需的传输带宽或存储容量，可对帧序列进行压缩，这样就不必存储或传送该序列内的冗余信息。电视、视频会议以及CD-ROM存档就是得益于有效视频序列编码的应用实例。

通常在编码一个图象序列时，从一帧到下一帧的景物中的对象运动的信息在编码处理中起着重要的作用。因为大多数图象序列的连续帧之间存在高冗余度，所以通过使用已知的运动估算／补偿技术可实现大量的数据压缩。简而言之，编码器仅仅编码相对于已编码区变化的区域的差值。换句话说，运动估算是一个处理过程，用于确定相对于一个或多个参考帧的当前帧中的一个区域(例如，一个块或宏块)的运动方向和大小(运动矢量)。而运动补偿是一个使用该运动矢量产生当前帧的预测(预测的图象)的处理。当前帧和预测帧的不同产生一个剩余信号(误差信号)，它包括的信息远远少于当前帧本身。因此，通过仅仅编码和发送剩余信号和相应的运动矢量可节省大量的编码比特。

为了进行说明，在一个包含运动的序列中，可通过使用前一帧和表示当前帧与前一帧之间的不同的剩余信号来重建当前帧。发射机或编码器把前一个帧、剩余信号和相应的运动矢量发送到接收机。在接收机侧，通过把前一个帧与剩余信号和运动信息组合起来可重建当前帧。因而只需发送和接收一个(1)帧和具有其相关运动矢量的不同信息，而不必发送和接收两(2)个完全的帧。

然而，编码器设计者必须在两者之间折衷，即或者是努力提高运动估算的精确度以使剩余信号最小(即减少编码比特)，或者是在运动估算处理时接受较低级别的精确度以最小化总计算。换句话说，通过帧序列确定运动矢量需要在帧间进行充分地搜索以确定运动信息。越充分地搜索将产生越精确的运动矢量组，但同时则需要更长的计算周期。

例如，很多系统确定运动信息是采用了一种所谓的基于块的方法。在一种简单的基于块的方法中，当前帧被分成了若干个像素块(以下称作“当前块”)。对于每一个这些当前块来说，要在前一帧的所选搜索区中搜索与当前块“最佳”匹配的一个像素块。通常，通过重复比较所选当前块和前个帧的所选搜索区中的类似大小的像素块可完成这个搜索。一旦找到一个匹配的块，则相对于当前帧的当前块位置的前一帧的搜索区中的匹配块的位置定义一个运动矢量。这种方法，即把每个当前块与全部的所选搜索区相比较的方法称作全搜索法或穷举搜索法。通过穷举搜索法确定运动矢量的计算量大，特别是在搜索区特别大的情况下。因此，这些系统在处理帧时往往较慢并且造价昂贵。

因而，在本技术领域中需要一种在确定基于块的运动估算的运动矢量时降低计算复杂性的装置和一种与之相伴的方法。

本发明的一个实施例是一种装置和方法，它采用“多标度块叠放”(N-标度叠放)以在确定基于块的运动估算的运动矢量时降低计算复杂性并且提高运动估算法的精确度。具体来说，本发明把图象序列中的每个帧分解成一个M元金字塔(pyramid)。接着N-标度叠放与M元金字塔一起使用以完成分层运动估算。N-标度叠放是一个通过使用“N”个不同“叠放块”尺寸执行该帧的当前块运动估算的处理。例如，如果设定N为三，则每个帧中的每个块产生三个(3)运动矢量，即通过使用三个不同的块尺寸或标度(scale)，该块“被叠放”。因此，使用N-标度叠放的分层运动估算允许编码器在所考虑帧的较大结构的运动和较小特征的运动之间进行鉴别。

通过结合附图研究下面的详细描述可以容易地理解本发明的宗旨，其中附图为：

图1所示为本发明的编码器框图，该编码器用于在确定基于块的运动估算的运动矢量时降低计算的复杂性；

图2所示为一种用于在确定基于块的运动估算的运动矢量时降低计算复杂性的方法的流程图；

图3所示为通用平均金字塔的框图；

图4所示为产生M元金字塔的量化处理的框图；

图5所示为一个已经被分解且分类为多个块的输入帧。

图6所示为本发明的一种编码系统；

图7所示为使用3-标度叠放的像素块的框图；

图8所示为根据本发明的装置的第二实施例的框图；

图9所示为小波树的示意图；

图10所示为用于产生图象的M元金字塔的方法流程图；

图11所示为用于对使用N-标度叠放的M元金字塔执行运动估算的方法的流程图。

图1示出了本发明的装置100的框图，该装置用于在确定基于块的运动估算的运动矢量时降低计算的复杂性。下面使用一种编码器对本发明的最佳实施例进行描述，但是应当理解的是，通常可在图象处理系统中采用本发明。而且，可在符合各种编码标准的编码器中采用本发明。这些标准包括运动图象专家组标准(例如MPEG-1(11172-*)和MPEG-2(13818-*)，H．261和H．263，但这些标准并不局限于此。

装置100是一个编码器或者是一种更复杂的基于块的运动补偿编码系统的一部分。装置100包括运动估算模块140、运动补偿模块150、任选的分割模块151、预处理模块120、速率控制模块130、变换模块(例如DCT模块)160、量化模块170、编码器(例如可变长编码模块)180、缓冲器190、逆向量化模块175、逆变换模块(例如逆DCT模块)165、减法器115和加法器155。尽管编码器100包括多个模块，但本领域的普通技术人员将认识到，由各种模块执行的功能并不需要分散于图1所示的各个独立模块中。例如，包括运动补偿模块150、逆向量化模块175和逆向DCT模块165的模块组通常称作“嵌入式解码器”。

图1示出了路径110上的输入图象(图象序列)，它根据MPEG标准数字化并且被看作是一个亮度和两个色差信号(Y，C_r，C_b)。这些信号被进一步分成多个层，这样每个画面(帧)可由多个宏块表示。每个宏块包括四个(4)亮度块、一个C_r块和一个C_b块，其中一个块被定义为八(8)乘以八(8)的样本阵列。画面分成块单元提高了识别两个连续画面间的变化的能力，并且通过消除低幅变换系数(下面将进行讨论)提高了图象的压缩。

下述公开使用了MPEG标准术语；但是应当理解的是，本发明中的术语宏块和块用于描述用作编码基础的任意大小和形状的像素块。广义上来说，“宏块”可小到一个单个像素，或者大到全部的视频帧。

在最佳实施例中，数字化的输入图象信号在预处理模块120中经过了一个或多个处理步骤。更具体来说，预处理模块120包括一个金字塔发生器122和一个块分类器124。M元金字塔发生器122采用平均滤波器123a和量化器123b以滤波并且量化每个帧为多个不同的分辩率，即一个M元的分辩率的金字塔，其中每个帧的不同分辩率相关于下面描述的分层形式。接着，通过使用分辩率的金字塔，块分类器124能够把区域(块)快速分类为高活动区或低活动区。下面将详细描述由预处理模块120执行的功能。

运动估算模块140也接收路径110的输入图象以用于估算运动矢量。运动矢量是一个二维矢量，它由运动补偿所使用以提供一个从当前画面一个块的坐标位置到参考帧的坐标的位移。由于仅仅编码和发送当前帧中的变化减少了信道传输的信息量，所以运动矢量的使用大大增强了图象的压缩。在最佳实施例中，运动估算模块140还接收来自预处理模块120的信息以加强运动估算处理的实施。

来自运动估算模块140的运动矢量由运动补偿模块150接收以用于提高采样值预测的效率。运动补偿涉及到一个预测，它使用运动矢量以把位移提供到包含以前解码的取样值的过去和／或未来的参考帧中，并且用于形成预测误差。换句话说，运动补偿模块150使用先前解码的帧和运动矢量来在路径152上构建当前帧的估算(运动补偿预测或预测图象)。这个运动补偿预测通过减法器115而从当前宏块中的路径110上的输入图象中减去，从而在路径153上形成一个误差信号(e)或预测剩余信号。

预测剩余信号传送到诸如DCT模块160的变换模块。该DCT模块随即把前向离散余弦变换应用到预测剩余信号的每个块以产生一组八(8)乘八(8)的DCT系数的块。离散余弦变换是一个可逆的离散正交变换，其中DCT系数表示一组余弦基本函数的幅度。

产生的8×8的DCT系数的块由量化(Q)模块170接收，在其中DCT系数被量化。通过使用DCT系数除以适当地进行四舍五入形成整数值的一组量化值或标度，量化处理降低了表示DCT系数的精确度。通过使用根据基本函数的可见度(称作可见加权量化)的标准可为每个DCT系数单独设置量化值。通过使用这个值量化DCT系数，很多DCT系数变为零，由此提高了图象的压缩效率。

接着，由此产生的8×8的量化DCT系数的块经信号连接171由诸如可变长编码模块180的编码器接收，其中二维的量化系数的块以“z形(zig-zag)”的顺序被搜索，从而将其转换成一维的量化DCT系数串。可变长编码(VLC)模块180随即把量化DCT系数串和诸如宏块类型和运动矢量的宏块边信息编码。因此，VLC模块180执行把输入图象转换成有效数据流的最后步骤。

该数据流由诸如“先进先出”(FIFO)缓冲器190的缓冲器接收。使用不同图象类型和可变长编码的结果是总比特率可变。换句话说，用于编码每个帧的比特数可以不同。所以在涉及固定速率信道的应用中，FIFO缓冲器用于把编码器输出与信道匹配以用于平整比特率。因此，路径195上的来自FIFO缓冲器190的输出信号是输入图象110的压缩表示，其中它被发送到一个存储介质或一个电信信道。

速率控制模块130用于监视并调节输入到FIFO缓冲器190的数据流的比特率，以防止数据流传输后在解码器侧(在接收机或目标存储装置之内，未示出)发生溢出或下溢。假设固定速率的信道以固定速率把比特传送到解码器(未示出)内的输入缓冲器中。该解码器以帧速所确定的正常间隔即刻把下一个画面的全部比特从其输入缓冲器中移出。如果输入缓冲器中的比特太少，即还没有接收到下一个画面的全部比特，则输入缓冲器下溢引起下溢误差。类似地，如果输入缓冲器中的比特太多，即画面开始之间的比特超出了输入缓冲器的容量，则输入缓冲器溢出引起溢出误差。因此，速率控制模块130的任务就是监控缓冲器190的状态以控制由编码器产生的比特数，从而防止溢出和下溢情况的发生。一种速率控制方法可通过调节量化标度来控制编码比特数。

而且，来自量化模块170的8×8的量化DCT系数块经信号连接172由逆向量化模块175和逆向DCT模块165接收。简而言之，在这个阶段，编码器通过解码数据重新产生图象序列的I-帧和P-帧，这样它们可用作随后进行的编码的参考帧。

图2所示为用于在确定基于块的运动估算的运动矢量时降低计算复杂性的方法200的流程图。换句话说，方法200通过快速定义可能出现匹配的初始搜索区可加强基于块的运动估算法。

更具体地说，方法200开始于步骤205并且前进到步骤210，在该步骤为图象序列中的每个图象帧产生一个M元金字塔(或M元平均金字塔)。对于产生M元金字塔的详细描述将在下面通过参考图3、4和10提供。

更具体来说，图10所示为用于产生图象的M元金字塔的方法1000的流程图。该方法开始于步骤1005并且前进到步骤1010，在该步骤初始图象被分解为平均金字塔的图象。

图3所示为通用平均金字塔300的框图，其中该平均金字塔包括多个级别(level)310、320和330。最低一级310是一个来自图象序列的初始图象帧，该图象序列具有多个以“×”表示的像素311。一般地，这些像素由像素值表示，这些像素值所具有的范围由分配来表示像素值的比特数进行限定。例如，如果分配八(8)比特，则像素值可采用256个可能的值中的一个。

在一个平均金字塔中，通过在两个方向由两个因素中的一个低通滤波和下取样，从而通过较低一级中的四个(4)像素值(子)产生较高一级的一个单个像素值(父)，由此而产生了接着的较高一级。这在图3中已经示出，其中每组的四个像素312a-d用于产生级别320中的单个的一个像素321。接着，四个像素值的组322a用于产生级别330中的一个像素值331，如此类推。应当理解的是，本发明并不局限于具有三个级别的平均金字塔。级数通常由图象大小和所选以用于产生接着的较低分辩率的图象的下采样因数限制。因此，可为特定的应用选择平均金字塔中的级数。

在一个平均金字塔中，父像素值通过平均其四个子像素值而获得，因而命名为平均金字塔。但是，也可使用其它的测量或度量法产生其它类型的金字塔，例如，可根据四个子像素值的中间值的度量法。另一方面，子像素周围的较大区域可用于加权平均以获得一般的低通金字塔。

现在返回到图10，方法1000随后在步骤1020通过所述平均金字塔产生M元金字塔。换句话说，在一个“M元金字塔”中，像素值被量化，这样每个量化的像素值只能采用“M”个可能的像素值。例如，如果M等于二(2)，则每个量化的像素值可采用值0或1，即如在“二元金字塔”中所产生的。

图4所示为产生三元金字塔的量化处理的框图，其中M等于三(3)。更具体地说，根据子和父像素之间的不同，八比特像素值255(410a)量化为两比特像素值10(420a)。换句话说，就是计算父像素值430a和其子像素值410a-d中的每一个之间的差值，其中四个(4)差值中的每一个随即被量化为三个可能的值10、00和01。因此，像素值128(410b和410c)量化为像素值00(420b和420c)并且像素值0(410d)量化为像素值01(420d)。这些表示级适用于将用于运动估算的基于逐位(bit wise)XOR的成本函数。它们也用于特征检测和块分类。M元金字塔降低了像素值的精确度，从而允许快速检测图象内的“特征”。特征定义为高活动区或强度区，例如，对象的边缘。值得注意的是，级别410和430是平均金字塔的级，而级420是M元金字塔(其中M=3)的级。这两个金字塔如图4所示还可以具有其它的级，但该M元金字塔应当比该平均金字塔少一个级。换句话说，我们需要两个平均金字塔级410和430产生一个M元金字塔级420。

而且，表示像素值的比特数的显著降低减少了运动估算处理中的总计算。例如，由于一个像素值可采用的值较少，所以可加速运动估算处理中执行的块匹配操作，从而简化了总的块匹配处理。

尽管M可以是任意值，但已经发现诸如二元金字塔的“较低级”的M元金字塔的分解与诸如三元金字塔的“较高级”的M元金字塔相比对噪声较敏感。换句话说，由于在二元金字塔中的量化像素值仅能采用两个可能值中的一个，所以噪声可能会导致误差，其中一个像素值可能会被错误地看作是具有值1而非0，或者相反。但是，“较高级”的金字塔需要更多的计算。因此，尽管可以看出最好采用M大于2的M元金字塔分解，但特定M元金字塔分解的选择常常由特定应用的要求所决定。一旦产生M元金字塔，则方法1000在步骤1030结束并且返回到图2的步骤220。

应当理解的是，步骤210的重要特性是为图象序列中的每个输入图象产生一个M元金字塔。因此，尽管该最佳实施例产生一个M元平均金字塔，但本发明也可采用其它类型的金字塔，如M元中值金字塔和M元低通金字塔等等。

另一方面，M元平均金字塔分解的发明概念能够以方程式的形式表达。设定(i，j)表示图象帧上的像素位置并且设I(i，j)表示位置(i，j)的强度。并且设l指示金字塔内的级别，其中0≤l≤L，其中L是该金字塔中的最高一级。因此，该平均金字塔X^l(i，j)，1≤l≤L可如下构建： $>>>X>l>>>(>i>,>j>)>>=>>1>4>>>>\Sigma >>m>=>0>>l>>>\Sigma >>n>=>0>>l>>>X>>l>->1>>>>(>2>i>+>m>,>2>j>+>n>)>>.>.>.>.>.>.>.>.>.>.>(>1>)>>>$

其中X⁰(i，j)=I(i，j)。

现在返回到图2，通过这些平均金字塔，诸如一个块的特征的信息可在下面的步骤220中提取。在一个实施例中，该块是一个宏块的8×8的子块，但应当理解的是，本发明并不局限于这个块尺寸。特别是，诸如边缘的特征可通过块中的强度变化而被提取。这个变化是通过计算0≤l≤L-1的1级的平均值和1+1级的平均值之间的差值来表示的。但是，为了获得健壮特征，并且为了便于进行快速的运动估算，这些差值被量化以产生M元金字塔。该M元金字塔的每一级都将表示该图象的一种模式，这可用于识别诸如边缘和零交叉的图象特征，并且用于执行运动估算。

例如，图象的二元金字塔B^l(i，j)可如下创建：

其中l表示二元金字塔内的级别。尽管方程(1a)示出了定义二元金字塔的两个值(“0”和“1”)的特定条件(量化器步骤)，但也可根据特定应用使用其它条件或量化器步骤定义二元金字塔的两个值(“0”和“1”)。

另一方面，可创建图象的三元金字塔Y^l(i，j)。例如，以Y^l(i，j)表示M元(M=3)金字塔中的模式值： $>>>B>1>>>(>i>,>j>)>>=>Quant>[>>X>l>>>(>i>,>j>)>>->>X>>l>+>1>>>>(>INT>>(>>i>2>>)>>,>INT>>(>>j>2>>)>>)>>]>,>0>\le >l>\le >L>->1>.>.>.>.>.>.>.>.>.>.>(>2>)>>>$

以λ表示Quant[·]的自变量。例如，研究具有阈值T的三元金字塔的情况，并且如下定义Y^l(i，j)：

如果适当地选择特定应用的量化阈值T(例如，在最佳实施例中T选为5)，那么定义有利于噪声健壮性(noise-robustness)。换句话说，可定义一个“死区”，例如|λ|＜T，其中因噪声引起的像素值的轻微变化可被有效地消除。因此在零周围具有一个死区的任何M元金字塔(M＞2)将把噪声敏感问题降至最小。

在较平坦的区域(低活动区)中，Y^l(i，j)将包括大量的零(0)，而在包含边缘的区域中，Y^l(i，j)将包括若干个一(1)。一旦输入图象分解为M元金字塔，输入图象中的块就可被分类以用于通过使用M元金字塔Y^l(i，j)进行特征提取。换句话说，M元金字塔Y^l可用于快速检测输入图象中的特征，而不必进行大量的总计算。所检测特征可用于强化下述的运动估算处理或者是其它的图象处理步骤，例如通过使用分割模块151进行的图象内的区域(例如对象)分割。分割是一个重要的图象处理步骤，其中图象中的重要区域可被识别以接受专门的处理。例如在视频会议应用期间的一个人的脸可能需要专门的图象处理，如接受更多的编码比特的分配。另一方面，可采用分割来识别大的对象，其中可对这些大对象执行整体的运动估算。

应当理解的是，前面的讨论使用了三元金字塔作为实例，并且示出了一种可能的方法，其中可分配量化阈值或级别以用于特征识别和分类。通常，M≥2的M元金字塔可与根据特定应用要求和／或图象序列内容的量化阈值的专门分配一起使用。

现在返回到图2，在产生M元金字塔之后，方法200前进到步骤220，在该步骤，考虑到M元金字塔，帧中的块被分为高活动类和低活动类。在最佳实施例中，该“分类块尺寸”是一个具有由128比特表示的64个M元像素值的8×8块。如果25个或更多的像素值是非零则把该8×8的块分类为高活动块，由此设置“活动性阈值”为25。否则把该8×8块分类为低活动块。另外也可执行其它较大块的分类，例如，把宏块分类为高活动宏块或低活动宏块。在最佳实施例中，包括至少一个分类为高活动子块的宏块使得该宏块也被分类为高活动块。应当理解的是，可根据特定应用调节“分类块尺寸”和“活动性阈值”，而且它们并不局限于在最佳实施例中所选择的那些值。

现在返回到图2，在块分类后，方法200前进到步骤230，在该步骤，块分类用于强化运动估算的处理。通常，在具有显著图象特征的区域进行运动估算比在因孔径(aperture)问题而具有较少变化的较“平坦区域”(例如，相邻块的图象内容非常相似的均匀区域)进行运动估算更可靠。因此，上述的分类方法通常用于增加运动估算的可靠性。然而应当理解的是，没有必要在运动估算应用中的使用M元金字塔之前把一个块按其内容进行预分类。换句话说，应当理解的是，可直接采用本发明的M元金字塔(图2中以虚线示出)以提高各类或不同体系结构的运动估算法的性能。

更具体来说，通常是以对块进行光栅扫描的顺序对块执行运动估算。在运动估算处理期间，总计算或成本(cost)通常平均分布到所有的块上。在本发明中，在“边缘”块(高活动块)中的运动估算通过使用根据Y^l(i，j)和／或X^l(i，j)的成本函数(costfunction)首先执行。这种方法允许图象特征的强调，并且在存在敏感噪声、量化噪声和照度变化时提供健壮可靠的运动估算。成本函数的一个实例是可涉及到对金字塔中的M元级别执行逐位XOR操作，它可作为对某种体系结构的快速方法使用。该成本函数用于确定“最佳匹配”。让我们把在时间t的M元估值的块(当前帧)看作为Y^l(i，j，t)，而在时间t-1的M元估值的块(前一帧)看作为Y^l(m，n，t-1)。则该成本函数可表示如下：

其中表示逐位XOR操作。这种成本函数与用于初始8比特像素强度值的标准“绝对差”成本函数相比节省了大量的计算。这个处理程序对M元金字塔分层执行。

换句话说，运动估算方法开始于高活动块。图5所示为已经被分解且分类为多个块510的输入帧500。在最佳实施例中，两个块510a被分类为高活动块。因此，首先对这两个块执行运动估算。事实上，这两个块的计算成本可能会提高，这是因为这些高活动块(高置信“边缘”块)最有可能提供非常高精确度的运动矢量。因此，在这两个块中执行的运动估算比在图象帧500中的其它块执行的运动估算要更加充分，例如，这些高活动块可被分解以获得更加精确的运动矢量，在这两个块中可执行“半个像素”的运动估算或者采用更精确的搜索方案。

接着，在完成高活动块的运动估算之后，运动估算将传播到图象中的低活动块(“低置信”块)。但是，这种传播是根据通过分类所得的区域或对象的分割而巧妙地进行的。这种传播是通过把边缘块的运动作为相邻块的运动的起始并且通过使用较小的搜索范围来精制(refine)这个起始部分而执行的。换句话说，运动估算处理传播(例如以一个螺旋形的顺序)到块510b，其中初始搜索区由高活动块的运动矢量产生。接着，这个传播方案扩展到“平坦的”块，例如块510c，如此等等，它们并不与“边缘”块相邻，并且由于精制搜索范围较小，所以有利于快速计算。而且，运动估算将更加平整并且更易于进行编码，它主要的优点是在非常低的比特率(VLBR)应用中，运动信息形成比特流的大部分。而且，可期望这种更平整的运动估算在时间内插应用中更好地执行。

最后，当使用半像素精制提高运动估算的精确度时，此分类方法还节省计算。仅对“边缘”块执行半像素精制，而不对图象的较平坦的区域执行半像素精制。

本发明的另一个实施例涉及使用M元金字塔的N标度叠放以实现运动估算。更具体地来说，在这另一个实施例中，4-级二元金字塔如下创建： $>>>X>l>>>(>i>,>j>)>>=>INT>\{>>1>4>>>\Sigma >>m>=>0>>l>>>\Sigma >>n>=>0>>l>>>X>>l>->1>>>>(>2>i>+>m>,>2>j>+>n>)>>\}>.>.>.>.>.>.>.>.>.>.>>>(>5>)>>>$

1≤l≤3

其中X¹(i，j)表示第1级的位置(i，j)的灰度级并且X₀(i，j)表示初始图象。

其次，4-级二元金字塔图象如下创建：

其中0≤l≤2

B³(i，j)=X³(i，j)    (7)

值得注意的是，本发明的N-标度叠放实施例采用的是具有方程式(7)所表示的金字塔的最高一级的改进的二元金字塔。但是，本发明的N-标度叠放实施例也可结合上述的M元金字塔(例如方程式1、1a或2)一起实施，或者结合在此处作为参考的在98年6月29日同时提交的附属专利应用领域的题为“用于执行可标度分层运动估算的装置和方法”(代理人审察SAR12545；序列号09／106，706)中所公开的其它的改进M元金字塔一起实施。

图11示出了用于对使用N-标度叠放的M元金字塔执行运动估算的方法1100的流程图。具体来说，方法1100开始于步骤1105并且前进到步骤1110，在该步骤从金字塔的最高一级对二元金字塔(为了说明设M=2)执行N-标度叠放。通常，执行运动估算是为了估算当前块(例如一个16×16个像素的宏块)的运动或位移，其中全部帧被分成多个不重叠的当前块。但是，如图7所示，N-标度叠放是一个使用“N”个不同的“叠放块”执行该帧的当前块的运动估算处理。

图7所示为执行3-标度叠放的像素块710的框图。更具体来说，块710是一个帧内的多个8×8块中的一个。在最佳实施例中，运动估算的执行是使用了三个(N=3)不同的块尺寸，例如8×8块尺寸710、8×4块尺寸720和4×8块尺寸730。因此，在每个帧内为每个8×8的块产生三个(3)运动矢量，即该块是使用三个不同块尺寸或标度“叠放”的。

在本发明的一个最佳实施中，3-标度叠放(N=3)在最高一级(M元金字塔的最低分辩率)开始执行，由此为每个块产生三个运动矢量。

在步骤1120，方法1100查询下一级是否是M元金字塔的最低一级。如果查询的回答是否定的，则方法1100前进到步骤1130，在该步骤，三个运动矢量传送到较低一级，即每个标度的一个运动矢量传送到M元金字塔的较低一级。接着，方法1100返回到步骤1110以对接着的较低一级执行处理，在该级别，根据来自较高一级的接收运动矢量执行精制(refinement)以产生传送到较低级别的另外三个运动矢量，其中运动矢量在每一级都被精制，依此类推。

但是，如果在步骤1120的查询回答是肯定的话，则方法1100前进到步骤1140，在该步骤，只从级别1中选择一个运动矢量传送到级别0(M元金字塔的最低一级(最高分辨率))。从级别1传送到级别0的运动矢量的选择是根据把该块的运动补偿预测误差最小化的运动矢量进行的。应当注意的是，全分辩率的目标块尺寸是16×16。接着，在步骤1150，使用由步骤1140传送的运动矢量确定每个16×16块的一个最终运动矢量，并且方法1100在步骤1160结束。

结合M元金字塔执行N-标度叠放的特征在于包括在布尔域(当M=2时)中执行运动估算的能力。这个特征减少了帧缓冲器和运动估算器140之间的数据传送时间。而且，使用3-标度叠放执行运动估算允许编码器在所考虑的情况下在帧内的较大结构的运动和较小特征的运动之间进行识别。例如，如果选择一个与诸如4×8或8×4的块而非8×8的块的小叠放块相关的当前块的运动矢量，那么我们可以推断在当前块中可能存在“特征”或子块的运动。因此，我们可以建立一个直方图以根据一个帧的当前块最终所选的运动矢量来测量不同叠放标度的分布。可分析该直方图以推导出一个结构(structure)内的大结构或较小特征的运动，如此等等。

应当理解的是，尽管最佳实施例采用了三个标度，但不同块尺寸可以采用“N”个标度数。而且，可以改进本发明以使每个块的任意数的运动矢量可逐级传送。

上述使用3-标度叠放的分层运动估算法能够以方程式的形式表示。换句话说，设定F_m表示图象帧序列中的第m个图象帧，其中每个帧分解为未重叠的尺寸是“s”的块。由此产生的分割或叠放在分辩率1时以F¹_m(x)表示。在分辩率为1的图象帧m中的坐标为x=[x₁，x₂］^J的像素强度值表示为。对于一个给定的s=[s₁，s₂]^J来说，在图象位置x左上角的像素块称作B^l_m(x，s)=｛F^l_m(q)∈F^l_m|×≤q＜x+s｝。来自帧m的块B¹_m(x，s)的像素与来自帧m-1的块B¹_m-1(x，s)的对应像素之间的绝对差的求和(SAD)可表示如下： $>>>B>m>l>>>(>x>,>s>)>>->>B>>m>->1>>l>>>(>x>,>s>)>>=>>\Sigma >>0>\le >d>\le >s>>>|>>F>m>l>>>(>x>+>d>)>>->>F>>m>->1>>l>>>(>x>+>d>)>>|>.>.>.>.>.>.>.>.>.>.>(>8>)>>>来自帧m的块B1$_m(x，s)的像素与来自帧m-1的块B¹_m-1(x，s)的对应像素之间的XOR布尔运算()的求和可表示如下： $>>>B>m>l>>>(>x>,>s>)>>\otimes >>B>>m>->1>>l>>>(>x>,>s>)>>=>>\Sigma >>0>\le >d>\le >s>>>\phi >>>(>>F>m>l>>>(>x>+>d>)>>\otimes >>F>>m>->1>>l>>>(>x>+>d>)>>)>>.>.>.>.>.>.>.>.>.>.>(>9>)>>>$

设F^0．5为在具有基数(cardinality)为k的全分辩率图象上定义的一个叠放。对于较低分辩率的图象来说，3-标度叠放被看作是 $>>\{>>F>>l>,>s>>>>\}>>l>=>1>>3>>,>\{>>F>>l>,>s>1>>>>\}>>l>=>1>>3>>,>>>以及$ >>\{>>F>>l>,>s>2>>>>\}>>l>=>1>>3>>>>。值得注意的是s1=[s$$₁／2，s₂]^J并且s2=[s₁，s₂／2]^J，但也可使用其它的块尺寸。

首先，在四个级别的金字塔(0-3级)中的级别3的运动矢量场V_s³，V_s1³和V_s2³可表示如下： $>>>v>s>3>>=>arg>>min>>v>\in >\Omega >>>>B>m>3>>>(>x>,>s>)>>->>B>>m>->1>>3>>>(>x>+>v>,>s>)>>.>.>.>.>.>.>.>.>.>.>(>11>)>>>$ >>>v>>s>1>>3>>=>arg>>min>>v>\in >\Omega >>>>B>m>3>>>(>y>,>s>1>)>>->>B>>m>->1>>3>>>(>y>+>v>,>s>1>)>>.>.>.>.>.>.>.>.>.>.>(>12>)>>>$ >>>v>>s>2>>3>>=>arg>>min>>v>\in >\Omega >>>>B>m>3>>>(>z>,>s>2>)>>->>B>>m>->1>>3>>>(>z>+>v>,>s>2>)>>.>.>.>.>.>.>.>.>.>.>(>13>)>>>$$$

其中Ω³=｛v：-d³≤v≤d³｝

其中-d³和d³分别为-M／8和M／8，M是在搜索窗中的像素数。接着，对于从较低分辩率l+1到较高分辩率l(l=2和l=1)的级别2和级别1来说，运动矢量场根据下面的方程式进行传播： $>>>u>s>l>>=>2>>v>s>>l>+>1>>>>.>.>.>.>.>.>.>.>.>.>(>14>)>>>$ >>>u>>s>1>>l>>=>2>>v>>s>1>>>l>+>1>>>.>.>.>.>.>.>.>.>.>.>(>15>)>>>$ >>>u>>s>2>>l>>=>2>>v>>s>2>>>l>+>1>>>.>.>.>.>.>.>.>.>.>.>(>16>)>>>$$$

换句话说，在对运动矢量场执行精制处理之前，来自较低分辩率的运动矢量场被加倍。

接着，如下定义分辩率为l的运动矢量场： $>>>v>s>l>>=>arg>>min>>v>\in >\Omega >>>>B>m>l>>>(>x>+>>u>s>l>>,>s>)>>\otimes >>B>>m>+>1>>l>>>(>x>+>>u>s>l>>+>v>,>s>)>>.>.>.>.>.>.>.>.>.>.>(>17>)>>>$ >>>v>>s>1>>l>>=>arg>>min>>v>\in >\Omega >>>>B>m>l>>>(>y>+>>u>>s>1>>l>>,>s>1>)>>\otimes >>B>>m>->1>>l>>>(>y>+>>u>>s>1>>l>>+>v>,>s>1>)>>.>.>.>.>.>.>.>.>.>.>(>18>)>>>$ >>>v>>s>2>>l>>=>arg>>min>>v>\in >\Omega >>>>B>m>l>>>(>z>+>>u>>s>2>>l>>,>s>2>)>>\otimes >>B>>m>->1>>l>>>(>z>+>>u>>s>2>>l>>+>v>,>s>2>)>>.>.>.>.>.>.>.>.>.>.>(>19>)>>>其中\Omega $$$₁={v：-d¹≤v≤d¹}；并且其中-d¹和d¹分别为-3和3。

最后，对于级别0来说： $>>>v>l>>=>\psi >>(>>v>s>l>>,>>v>>s>1>>l>>,>>v>>s>2>>l>>)>>.>.>.>.>.>.>.>.>.>.>(>20>)>>>$ >>\psi >>(>>v>s>l>>,>>v>>s>1>>l>>,>>v>>s>2>>l>>)>>=>arg>>min>>v>\in >\{>>v>s>l>>,>>v>>s>1>>l>>,>>v>>s>2>>l>>\}>>>>B>m>l>>>(>x>,>s>)>>\otimes >>B>>m>->1>>l>>>(>x>+>v>,>s>)>>.>.>.>.>.>.>.>.>.>.>(>21>)>>> u0=2v1 (22)$ >>>v>0>>=>arg>>min>>v>\in >>\Omega >0>>>>>B>m>0>>>(>x>+>>u>0>>,>s>)>>\otimes >>B>>m>->1>>0>>>(>x>+>>u>0>>+>v>,>s>)>>.>.>.>.>.>.>.>.>.>.>(>23>)>>>$$$

其中

Ω₀={v: -d⁰≤v≤d⁰}

其中-d⁰和d⁰分别为-3和3。

本发明使用的3-标度叠放的二元金字塔的分层运动估算提供了一种计算低廉的有效运动估算法。为了便于说明，设定视频图象的宽度和高度分别是W和H。搜索窗具有±M个像素。传统的全搜索块匹配法需要一个单个的像素匹配进行1减，1加和1绝对值的运算。因此，其计算的复杂性(每帧的运算)约为：

C_FULL≈W×H×4×M²×3=12WH M²       (24)

对于本发明来说，可使用同样的全搜索法。在0级的块尺寸是16×16。在级别1、级别2和级别3使用相同的块尺寸8×8。在级别0、级别1和级别2的有效搜索范围设定为±3。在级别3的有效搜索范围设定为±M／8。

在级别3，计算的复杂性约为： $>>>C>0>>=>>WH>64>>\times >>>M>2>>64>>\times >4>\times >3>=>>>3>WH>>M>2>>>1024>>.>.>.>.>.>.>.>.>.>.>(>25>)>>>$

在级别2和级别1，每个8×8块可由四个16-比特矢量表示。通过使用一个16-比特异-或阵列和一个具有65536个入口的双端口检查表(LUT)可执行16-比特的XOR布尔运算器。因而，该8×8的块需要4／64的累加(accumulation)以用于基本匹配。同样，8×4的块需要2／32的累加以用于基本匹配。因此，在级别2和级别1的计算复杂性约为： $>>>C>>2>,>1>>>=>>WH>64>>\times >>(>>4>64>>+>>2>32>>\times >2>)>>\times >49>+>>WH>4>>\times >>(>>4>64>>+>>2>32>>\times >2>)>>\times >49>=>>>147>WH>>256>>+>>>147>WH>>64>>.>.>.>.>.>.>.>.>.>.>(>26>)>>>$

在级别0，16×16的块需要16／256的累加以用于基本匹配。其计算复杂性约为： $>>>C>0>>\approx >WH>\times >>32>256>>\times >49>=>>>49>WH>>16>>.>.>.>.>.>.>.>.>.>.>(>27>)>>>因此，本发明的计算复杂性C$_HMEBP约为： $>>>C>HMEBP>>=>>C>3>>+>>C>>2>.>1>>>+>>C>0>>=>>>3>WH>>M>2>>>1024>>+>>>1519>WH>>256>>.>.>.>.>.>.>.>.>.>.>(>28>)>>>最后，C$_HMEBP和C_FULL之间的比率为： $>>>>C>HMEBP>>>C>FULL>>>=>>>>>3>WH>>M>2>>>1024>>+>>>1519>WH>>256>>>>12>WH>>M>2>>>>=>>1>4096>>+>>1519>>3072>>M>2>>>>.>.>.>.>.>.>.>.>.>.>(>29>)>>>$

因此，方程式(29)显示出与传统的全搜索方法相比较，本发明具有较小的计算复杂度。

值得注意的是，尽管本发明始终对M元金字塔的所有级采用了N-标度叠放，但本发明并不局限于此。事实上，可在M元金字塔的每个级之内调节N-标度叠放。换句话说，我们可以对每一级中不同组的块采用不同的N-标度叠放。例如，如果一个块特别重要，那么我们可以一个8×8的块采用5-标度叠放(例如一个8×8叠放块、两个4×8叠放块和8×4叠放块)。相反地，如果一个块在M元金字塔的同相级别中不是特别地重要，那么我们可以一个8×8的块采用1-标度叠放(例如，一个8×8的叠放块)，从而降低计算的周期数。因此，上面的块分类(高活动块和低活动块)方法可用于指示将在M元金字塔的每一级中的每个块所采用的N-标度的级别。事实上，可使用任何结合本发明的其它块分类方法。

另一方面，上述的使用可变长叠放块尺寸的分层运动矢量估算法可使用图3所示的平均金字塔执行。换句话说就是直接对平均金字塔而非M元金字塔执行运动估算。

为了便于说明，在平均金字塔的最高一级，使用了两个不同的块尺寸执行运动估算以用于在所考虑的当前帧的较大特征的运动和较小特征的运动之间进行识别。更具体地来说，一个4-级平均金字塔根据上面的方程式(5)构建，其中X¹(i，j)表示第1级的位置(i，j)的灰度级，并且X⁰(i，j)表示初始图象。

分层运动估算是从平均金字塔的粗糙(coarse)级别到更精制(finer)的级别执行的。假设16×16的目标块为全分辩率，分层运动估算开始于级别3，其中搜索两个块尺寸，例如4×4的块和8×8的块(也可使用其它的叠放块数和／或叠放块尺寸)。

接着在级别2和级别1，每一个候选的运动矢量在两个不同的标度被精制(refined)，并且来自每个标度的最佳运动矢量传播到下一级以用于进一步的精制。最后，在级别0，根据最小化运动补偿预测误差而选择一个运动矢量以用于每个块的精制。这种使用平均金字塔和可变叠放块尺寸的分层运动估算的计算费用少于传统的分层运动估算法，但大于上面的使用M元金字塔和可变叠放块尺寸分层运动估算。

图8所示为结合本发明的基于小波的编码器800。该编码器包括一个块运动补偿器(BMC)和运动矢量编码器804、减法器802、离散小波变换(DWT)编码器806、比特率控制器810、DWT解码器812和输出缓冲器814。

通常如上所述，输入信号是一个视频图象(一个定义视频序列中的帧的二维像素(半像素)阵列)。为了通过低比特率的信道精确地传送图象，必须显著地降低视频帧序列中的时间和空间冗余。这通常是通过仅编码和传送连续帧间的差值来实现的。该编码器具有三个功能：第一，通过使用BMC和其编码器804，它产生表示帧间发生的运动的多个运动矢量；第二，它通过使用结合运动矢量的先前帧的重建模式预测当前帧；以及第三，该预测帧从当前帧中减去以产生一个与运动矢量一起编码和发送到接收机的剩余的帧。

离散小波变换执行小波分层副频带分解以产生传统的输入图象的小波树表示。为了实现这种图象分解，可通过使用两次子取样(subsampling)而把该图象分解为高水平-高垂直(HH)、高水平-低垂直(HL)、低水平-高垂直(LH)、以及低水平-低垂直(LL)的副频带。随后，LL副频带被进一步子取样两次以产生一组HH、HL、LH和LL副频带。这种子取样是递归执行的，用以产生一个诸如图9所示的副频带阵列，其中使用了三个子取样。在实际应用中最好采用六个子取样。副频带间的父-子相依性以箭头示出，箭头从父节点的副频带指向子节点的副频带。最低的副频带是左上角的LL1，而且最高的副频带是右下角的HH3。在这个实例中，所有的子节点具有一个父节点。副频带的分解在IEEE Trans．On Signal Processing，Vol．41，No．12，pp3445-62，December 1993的J．M．Shapiro的“使用小波系数的零树的嵌入式图象编码”中进行了详细描述。

图8的DWT编码器以“宽优先”或“深优先”的模式编码小波树的系数。宽优先模式以逐比特平面的模式经过小波树，即量化所有的父节点，然后是所有的子节点，然后是所有的孙节点，依此类推。相反地，深优先模式从低-低载频(LL₁)的根部经子节点穿过每个树(从顶部向下)，或者经低-低副频带穿过子节点(从底部向上)。由速率控制器810进行的适当量化级的选择如上所述，用于控制一个序列的每个帧内的每个宏块的比特率。因此，本发明可适用于使用不同变换的各类编码器。

图6示出了本发明的编码系统600。该编码系统包括一个通用计算机610和各种输入／输出设备620。该通用计算机包括一个中央处理器(CPU)612、一个存储器614和一个编码器616，以用于接收和编码图象序列。

在最佳实施例中，编码器616就是上述的编码器100和800。编码器616可以是一个通过通信信道与CPU612连接的物理装置。另一方面，编码器616也可由软件应用程序表示(可者是一个软和硬件的组合，例如专用集成电路(ASIC))，它通过诸如磁盘或光盘的存储装置装入并且常驻于计算机的存储器612中。因此，本发明的编码器100可存储到计算机的可读介质上。

计算机610可与多种输入和输出设备620连接，例如，键盘、鼠标、摄像机、camcorder、视频监视器、任意数量的成像装置或存储装置，包括但又不限于下面的装置，磁带驱动器、软盘驱动器、硬盘驱动器、致密盘驱动器。输入设备用于向计算机提供输入以用于产生编码的视频比特流或者用于接收来自存储装置或成像装置的视频图象序列。最后，所示通信信道630用于把编码的信号由编码系统传送到解码系统(未示出)。

尽管在此已经详细的示出并描述了结合本发明宗旨的各种实施例，但本领域的普通技术人员可以轻易地设计许多仍然结合本发明宗旨的其它变化的实施例。