在运动补偿时间滤波可伸缩视频编码器的环境中用于可变尺寸块的重叠块运动补偿

摘要

一种用于处理视频帧的方法、计算机程序产品、和计算机系统。当前帧被划分为包括至少两个不同尺寸的块的M块。M至少是9。当前帧中的每一块被分类为运动块或I块。根据预定扫描顺序对所述M块中的每一块执行重叠块运动补偿(OBMC)。对其执行OBMC的块被表示为自身块(270)。相对于其相邻块(271、272、273、274)对自身块(270)执行OBMC。相邻块包括自身块的最近相邻块。对自身块执行OBMC的步骤包括生成用于该自身块及其相邻块中的每一个的加权窗口。

说明书

相关申请

本发明要求于2003年10月17日提交的题为“用于MCTF型可伸缩视频编码器的重叠块运动补偿(OBMC)”的美国临时申请号60/512,120的优先权，其通过引用而全部并入本申请中。本发明还是于2004年6月9日提交的题为“用于处理用于运动补偿时间滤波的I块(I-BLOCK)的方法”的待审美国专利申请号10/864,833的部分继续申请，其要求于2003年6月10日提交的美国临时申请号60/477,183的优先权。

技术领域

本发明一般涉及一种用于处理视频帧的方法、计算机程序产品、和计算机系统，并更具体地，涉及一种用于在运动补偿时间滤波(MCTF)可伸缩视频编码器的环境中执行可变尺寸块的重叠块运动补偿(OBMC)的方法、系统、计算机程序产品、和计算机系统。

背景技术

当前在可伸缩视频编码器的环境中使用的可变尺寸块匹配(VSBM)运动趋向于在块边界处创建差运动匹配，从而导致低编码效率。由此，需要一种由可伸缩视频编码器的环境中的VSBM提供的块边界处的运动匹配，其比现有技术中当前存在的运动匹配具有更高精度。

发明内容

本发明提供了一种用于处理视频帧的方法，所述方法包括步骤：

提供被划分为多个块的当前帧，所述多个块包括至少两个不同尺寸的块；和

对每一块执行重叠块运动补偿(OBMC)，对其执行所述OBMC的所述块被表示为自身块，所述执行OBMC的步骤包括相对于该自身块的相邻块而对该自身块执行OBMC，所述相邻块由该自身块的最近相邻块组成，所述相邻块包括第一相邻块，所述对自身块执行OBMC的步骤包括生成用于该自身块及其相邻块中的每一个的加权窗口。

本发明提供了一种计算机程序产品，包括其中嵌入有计算机可读程序代码的计算机可用介质，所述计算机可读程序代码包括适配为实现处理视频帧的方法的算法，所述方法包括步骤：

提供被划分为多个块的当前帧，所述多个块包括至少两个不同尺寸的块；和

对每一块执行重叠块运动补偿(OBMC)，对其执行所述OBMC的所述块被表示为自身块，所述执行OBMC的步骤包括相对于该自身块的相邻块而对该自身块执行OBMC，所述相邻块由该自身块的最近相邻块组成，所述相邻块包括第一相邻块，所述对自身块执行OBMC的步骤包括生成用于该自身块及其相邻块中的每一个的加权窗口。

本发明提供了一种计算机系统，包括处理器和耦接到该处理器的计算机可读存储单元，所述存储单元包括当由处理器执行时实现用于处理视频帧的方法的指令，所述方法包括以下计算机实现的步骤：

提供被划分为多个块的当前帧，所述多个块包括至少两个不同尺寸的块；和

对每一块执行重叠块运动补偿(OBMC)，对其执行所述OBMC的所述块被表示为自身块，所述执行OBMC的步骤包括相对于该自身块的相邻块而对该自身块执行OBMC，所述相邻块由该自身块的最近相邻块组成，所述相邻块包括第一相邻块，所述对自身块执行OBMC的步骤包括生成用于该自身块及其相邻块中的每一个的加权窗口。

本发明有利地提供了在可伸缩视频编码器的环境中由可变尺寸块匹配(VSBM)提供的块边界处的运动匹配，其比现有技术中当前存在的运动匹配具有更高精度。

附图说明

图1描绘了根据本发明实施例的包括运动补偿时间滤波(MCTF)处理器的视频编码系统。

图2描绘了根据本发明实施例的由图1的MCTF处理器实现的MCTF处理。

图3是描绘了根据本发明实施例的利用由图2的MCTF处理生成的时间高帧中的I块的流程图。

图4描绘了根据本发明实施例的连续帧的各像素之间的连接。

图5描绘了根据本发明实施例的包括I块和P块(P-BLOCK)的帧。

图6图示了根据本发明实施例的用于I块的空间内插的表示法。

图7A-7C图示了根据本发明实施例的在仅一个相邻块可用的情况下的I块的空间内插。

图8图示了根据本发明实施例的帧中的I块的可变块尺寸。

图9A-9F图示了根据本发明实施例的I块的定向空间内插。

图10图示了根据本发明实施例的I块的混合空间内插。

图11描绘了根据本发明实施例的已被配置为多个可变尺寸块的当前帧。

图12描绘了根据本发明实施例的图11的当前帧及其参考帧、以及将当前帧中的各块与参考帧中的对应块链接起来的运动矢量。

图13A是根据本发明实施例的用于在图2中的MCTF时间高帧中利用可变块尺寸OBMC的流程图。

图13B是描述根据本发明实施例的图13A的可变块尺寸OBMC处理步骤的流程图。

图14是根据本发明实施例的与图13A-13B的流程图关联的帧处理的方框图。

图15描绘了根据本发明实施例的要由MCTF变换为高时间帧和低时间帧的两个连续输入帧。

图16描绘了根据本发明实施例的OBMC所使用的自身块和关联的最近相邻块。

图17A图示了根据本发明实施例的其中自身块为运动块的4×4加权窗口。

图17B图示了根据本发明实施例的其中自身块为I块的4×4加权窗口。

图18A图示了根据本发明实施例的其中自身块为运动块的8×8加权窗口。

图18B图示了根据本发明实施例的其中自身块为I块的8×8加权窗口。

图19示出了根据本发明实施例的图11的帧，从而描绘了部分所选最近相邻块，其中所述所选最近相邻块大于它们关联的自身块。

图20示出了根据本发明实施例的描绘大于关联的最近相邻块的自身块的部分的图11的帧。

图21A-21C描绘了根据本发明实施例的结合其中最近相邻块为运动块的收缩(shrinking)方案的由OBMC使用的用于自身块和关联较小最近相邻块的加权窗。

图22A-22C描绘了根据本发明实施例的结合其中最近相邻块为I块的反射(reflecting)方案的由OBMC使用的用于自身块和关联较小最近相邻块的加权窗。

图23是根据本发明实施例的用于计算用于可变块尺寸OBMC的加权窗的流程图。

图24是根据本发明实施例的利用根据图13A、13B和23的流程图描述的方法所计算的概率加权窗口、而计算根据可变块尺寸OBMC处理的当前帧的自身块的连续改进的运动矢量的流程图。

图25图示了根据本发明实施例的用于在运动MCTF可伸缩视频编码器的环境中处理用于MCTF的I块和/或对于可变尺寸块执行重叠块运动补偿(OBMC)的计算机系统。

具体实施方式

本发明的详细描述被划分为以下几个部分：导言、定义、运动补偿时间滤波(MCTF)、检测和处理I块、OBMC处理、收缩方案、反射方案、OBMC加权窗口算法、OBMC迭代、基于上升的MCTF的修改、和计算机系统。

导言

视频压缩方案通过将输入视频信号的各帧编码为代表由输入视频的各帧组成的图像的近似值的压缩信息，而在发送之前从输入视频信号中去除冗余信息。在将压缩信息发送到其目的地之后，通过从压缩信息中解码图像的近似值而重构视频信号。由于时间冗余度，所以像素值不是独立的，而是与跨越输入视频信号的连续帧的其相邻像素值相关的。

在运动画面专家组(MPEG)混合编码中，可以通过运动补偿预测(MCP)而去除时间冗余度。视频信号典型地被划分为一连串画面组(GOP)，其中每个GOP以帧内编码帧(I)开始，后面跟随前向预测编码帧(P)和双向预测帧(B)的配置。P帧和B帧都是帧间。P帧中的目标宏块可以通过一个或多个过去参考帧来预测(前向预测)。双向预测，也称为运动补偿(MC)内插，是MPEG视频的重要特征。用双向预测编码的B帧使用两个参考帧，一个在过去，一个在未来。B帧中的目标宏块可以通过多个过去参考帧(前向预测)或多个未来参考帧(后向预测)来预测，或者通过这两个预测的平均值(内插)来预测。P帧或B帧中的目标宏块也可被帧内编码为以下定义的I块或P块。

前向或后向预测考虑到当前输入帧和一个或多个参考帧中的像素处的亮度和/或色度值，而分别基于前面的或后面的参考帧的内容对当前输入帧(即画面)中的数据进行编码。由此，用于预测编码的参考帧是前面的参考帧或后面的参考帧。对于当前输入帧中的像素(例如16×16阵列的像素)的给定输入块，预测编码利用运动补偿的预测(MCP)而在预定搜索范围内连续偏移参考帧中的各块，从而确定在与输入块具有至少给定最小相关度的参考帧内是否发现16×16阵列的像素。如果确定存在给定最小相关度，则以具有水平和垂直分量的运动矢量(MV)的形式获得参考帧中所发现的16×16像素阵列和输入块之间的位移的量和方向。输入块的像素值(例如仅亮度值或亮度和色度值两者)和在参考帧内发现的16×16阵列的像素内的对应像素之间的相应差值是被运动补偿的预测误差值，有时称为预测余量或简单余量。如前所述，根据前面参考帧进行的预测被称为前向预测，而根据后面参考帧进行的预测被称为后向预测。如果在搜索范围内没有发现参考帧内的相关16×16块，则输入块可以在输入帧内被帧内编码，并被称为I块。利用双向预测，可分别基于前面和后面参考帧内的16×16块像素而预测输入块的值。注意前面关于16×16像素块的讨论仅是图示性的，并且本发明的范围包括任意像素阵列尺寸的像素块。利用可变尺寸块匹配(VSBM)，例如块尺寸至少是4×4。

当前输入帧内的不连接的块被分类为I块或P块。I块被定义为当前输入帧内的输入块，该输入块与用于相对于该帧进行前向或后向预测的参考帧内的像素的对应块不具有足够相关性(即具有给定最小相关度)。由于缺少足够相关性，所以I块在给定帧内被完全编码，而与参考帧无关。P块通过以下步骤被编码：在假设参考帧在给定帧前面的前提下根据参考帧进行前向预测；在假设参考帧在给定帧后面的前提下根据参考帧进行后向预测；或利用前面和后面的参考帧两者进行双向预测。

I块的例子是不具有前一帧内的对应像素的当前输入帧内的一块新暴露(uncovered)的像素。I块的其它例子包括匹配不太好的运动块，例如特别是，当前输入帧中的一块部分覆盖(covered)或部分封闭(occluded)的像素，其中所述块与参考帧中的像素的对应块不具有足够相关性。本发明提供了一种确定和编码I块的方法。

本发明针对运动的质量，因为运动补偿时间滤波(MCTF)对所述质量相当敏感。常规使用的MPEG视频标准中的基于块的运动不具有足够高的质量，来避免由MCTF和结果可伸缩视频编码器输出的较低帧频视频中的伪影的建立。当前，即使VSBM也不足以可靠避免伪影。相反，本发明提供了一种确定和编码用于MCTF的更平滑和连贯的运动的方法。

定义

以下定义在这里应用于本发明的描述：

“视频编码系统”是对视频数据进行编码的系统。

“视频编码器”是通过去除冗余和导入受控失真而减少存储视频削波(clip)所需比特数目的算法。

“子带/小波编码器”是在减少冗余的处理中使用子带/小波变换的视频编码器。

“时间相关性”是在相邻或邻近帧中的像素之间的相关性。

“空间相关性”是同一帧中的像素之间的相关性。

“运动估计”是位于另一帧的匹配块中的运动或位移矢量的估计。

“运动补偿”(MC)实际上是将当前帧中的块和不同帧中的匹配块对准的处理。

“运动补偿时间滤波”(MCTF)是以下面结合图2所要描述的方式沿时间轴(即运动轨迹)对块或像素阵列进行滤波的处理。

“时间低帧”是一对(或更大集合)帧中包括公用的空间低频的帧。

“时间高帧”是一对(或更大集合)帧中包括构成MC差值的空间高频的帧。

“时间冗余”表明相邻或邻近帧中的像素之间的从属性(dependency)。

“块匹配”是为一块像素指定一个运动的方法。“可变尺寸块匹配”(VSBM)是利用可变尺寸块以更好地表示运动的块匹配运动估计。块尺寸可以特别从4×4变化到64×64。

“分层VSBM”(HVSBM)是使用一层空间分辨率(从最低到最高(全)分辨率)来执行VSBM的运动估计方法。

“重叠块运动补偿”(OBMC)是增强基于块的运动、以使得基于得到的运动的预测更平滑并降低或消除相邻块之间的运动矢量不连续性的效果的方法。

“全局运动矢量”是用于整个帧的运动矢量，其中有关块尺寸等于帧尺寸。

“不相连区域”是不具有参考帧中的对应区或运动太复杂使得运动估计器不能正确跟踪的区的图像帧中的区域。

“运动补偿预测”(MCP)是数据缩减技术，其中使用运动矢量来扭曲(warp)先前发送的帧，然后将其用作当前帧的预测，并对于该帧仅量化和发送所得到的预测误差。

“移位帧差”(DFD)是根据运动补偿后的预测得到的误差。

“混合编码器”是例如MPEG2的视频编码器，其利用反馈环内部的MC预测来在时间上压缩数据，并然后利用空间变换编码器来对得到的预测误差进行编码。

运动补偿时间滤波(MCTF)

可伸缩视频编码是运动画面专家组(MPEG)中的探索活动，其是国际标准化组织(ISO)的一个小组委员会。MPEG的目的在于设计用于发送和存储组合的音频和视频信号的国际标准。其中的关键元素在于由于这些视听信号的较大未压缩尺寸而对其进行压缩。可伸缩视频编码器提供包含整个范围的比特率、较低分辨率、和较低帧频、以及输入到可伸缩编码器的全帧频和全分辨率的嵌入式比特流。利用所述嵌入，较低比特率结果被嵌入到每个较高比特率的流中。

图1描绘了根据本发明实施例的视频编码系统50。输入视频51由MCTF处理器52接收，并包括例如16个输入帧的画面组(GOP)。每一帧具有多个像素，并且每一像素具有用于亮度和色度的像素特性的像素值。对于MCTF处理器52处理的每一块数据，MCTF处理器52需要运动矢量形式的运动信息。因此，输入视频51数据从MCTF处理器52发出到运动估计56块，该块确定运动矢量并将所确定的运动矢量向回发出到MCTF处理器52，以执行运动补偿时间滤波。另外，运动信息在运动现场编码处理器57中被编码，并然后被发送到分组器(Packetizer)55。

MCTF处理器52产生从输入视频51的输入帧得出的具有变换的像素值的包括一个时间低帧和多个时间高帧的输出帧，这将在下面结合图2进行描述。所产生的输出帧通过利用子带小波编码器进行空间分析而由空间分析53处理，称为离散小波变换。通过使用MCTF处理器52，视频编码系统50不经受由具有反馈环的混合编码器展示的漂移问题。

空间分析53将产生的输出帧(即一个时间低帧和多个时间高帧)分解为一个低频带和具有增加尺度(scales)的越来越高频率的多个频带。由此，空间分析53执行空间像素变换，从而以与MCTF处理器52在时间域执行的像素变换类似的方式导出空间子带。空间分析53的输出是未压缩的浮点数据，并且许多子带可以包括最接近零的值(near zero values)。

空间分析53所产生的空间中的这些空间子带被发出到EZBC(嵌入式零块编码器)54，其是利用时间相关性的一系列子带/小波编码器之一，但是被完全嵌入在质量/比特率、空间分辨率、和帧频中。EZBC 54算法通过对每一空间分辨率和时间高子带进行单独编码，而提供基本可伸缩性的性质。EZBC54包括对子带系数进行量化并向它们分配比特的压缩块。所述量化步骤将空间分析53的浮点输出变换为二进制比特表示，随后通过对二进制比特表示舍位而丢弃相对无效比特，从而所述舍位只产生可以忽略的失真。EZBC 54是自适应算术编码器，其将固定比特串变换为可变长度串，由此实现进一步压缩。由此，EZBC 54既是量化器，又是称作条件自适应算术编码器的可变长度编码器。尽管量化器丢弃了一些比特，但是可变长度编码器无损失地压缩来自量化器的输出。EZBC 54产生的比特流被交织并被发出到分组器55。EZBC编码器可由另一合适的嵌入或分层编码器替代，例如JPEG 2000和其它。

分组器55组合EZBC 54所产生的流中的各比特和运动现场编码处理器57所发送的(稍后解码所需要的)运动矢量中的各比特，并将所述比特的组合分割为期望尺寸的分组(例如500千字节或更小的因特网分组)。分组器55接着通过通信信道将这些分组发出到目的地(例如用于存储编码的视频信息的存储区)。

图2描绘了根据本发明实施例的由图1的MCTF处理器52实现的用于16帧的示例GOP尺寸的MCTF处理。图2示出了连续滤波的MCTF处理中的5级，即其中分别具有16、8、4、2和1帧的第5、4、3、2和1级。由此，每一级N包括2^N-1帧，其中N＝1、2、3、4、5。第5级包括图1的输入视频51的16个输入帧，即按照从左到右增加时间的方向排序的输入帧F1、F2、…、F16。对成对的帧执行MC时间滤波，以产生具有下一较低时间尺度或帧频的时间低(t-L)和高(t-H)子带帧。在图2中，实线表示时间低帧，而虚线表示时间高帧。在每一时间尺度上，曲线表示对应运动矢量。

在图2中执行4次MC时间滤波，以生成5个时间尺度或帧频，即原始帧频和4个较低的帧频。生成的帧频分别是第5、4、3、2和1级的全速率(fullrate)、1/2全速率、1/4全速率、1/8全速率、和1/16全速率。由此，如果输入帧频是每秒32帧(fps)，则最低的帧频是第一级的2fps。在图2中，最低帧频表示为(1)，而下一较高帧频表示为(2)，依此类推。

在从第5级到第4级的运动估计和关联的时间滤波中，图1的运动估计56执行：从F1到F2、F3到F4、F5到F6、F7到F8、F9到F10、F11到F12、F13到F14、和F15到F16的运动估计，并分别确定关联的运动矢量M1、M2、M3、M4、M5、M6、M7、和M8。图1的MCTF处理器52执行：对帧F1和F2的时间滤波以生成时间低帧L1和时间高帧H1；对帧F3和F4的时间滤波以生成时间低帧L2和时间高帧H2；对帧F5和F6的时间滤波以生成时间低帧L3和时间高帧H3；对帧F7和F8的时间滤波以生成时间低帧L4和时间高帧H4；对帧F9和F10的时间滤波以生成时间低帧L5和时间高帧H5；对帧F11和F12的时间滤波以生成时间低帧L6和时间高帧H6；对帧F13和F14的时间滤波以生成时间低帧L7和时间高帧H7；以及对帧F15和F16的时间滤波以生成时间低帧L8和时间高帧H8。一般来说，被时间滤波为时间低和时间高帧的帧被称为“子帧(child frames)”。例如，F1和F2帧是L1和H1帧的子帧。一般来说，特别是在将Haar滤波器用于时间滤波的情况下，如果子帧中的对应像素值为V_A和V_B，则时间低和时间高帧中的对应像素值分别与V_A+V_B和V_A-V_B成比例。由此，时间低帧中的像素值与子帧中的对应像素值的平均值成比例。相反，时间高帧中的像素值与子帧中对应像素值之间的差值成比例。由此，如果子帧中的像素值彼此接近，则时间高帧中的像素一般具有低能量(即大量接近零的值)，并因此是可高度压缩的。

在从第4级到第3级的运动估计和关联的时间滤波中，图1的运动估计56还执行：从L1到L2、L3到L4、L5到L6、和L7到L8的运动估计，并分别确定关联的运动矢量M9、M10、M11、和M12。图1的MCTF处理器52还执行：对帧L1和L2的时间滤波以生成时间低帧L9和时间高帧H9；对帧L3和L4的时间滤波以生成时间低帧L10和时间高帧H10；对帧L5和L6的时间滤波以生成时间低帧L11和时间高帧H11；以及对帧L7和L8的时间滤波以生成时间低帧L12和时间高帧H12。

在从第3级到第2级的运动估计和关联的时间滤波中，图1的运动估计56还执行从L9到L10和从L11到L12的运动估计，并分别确定关联的运动矢量M13和M14。图1的MCTF处理器11还执行：对帧L9和L10的时间滤波以生成时间低帧L13和时间高帧H13；以及对帧L11和L12的时间滤波以生成时间低帧L14和时间高帧H14。

在从第2级到第1级的运动估计和关联的时间滤波中，图1的运动估计56还执行从L13到L14的运动估计，并确定关联的运动矢量M15。图1的MCTF处理器52还执行：对帧L13和L14的时间滤波以生成时间低帧L15和时间高帧H15。

作为图2的MCTF的结果，在这5级示例中的16帧(包括时间低帧L15和时间高帧H1、H2、…、H15)作为MCTF处理器52的输出而被发送到图1的空间分析12。由于时间高帧H1、H2、…、H15可包括大量接近零的值，所以如前所述，时间高帧H1、H2、…、H15可修改为被高度压缩。

给定帧L15、H1、H2、…、H15，可通过依次颠倒产生帧L15、H1、H2、…、H15的处理，而重新生成第2、3、4和5级中的帧。例如，第1级的帧L15和H15可被算术组合，以重新生成第2级的帧L13和L14。类似地，第2级的帧L13和H13可被算术组合，以重新生成第3级的帧L9和L10，而第2级的帧L14和H14可被算术组合，以重新生成第3级的帧L11和L12。该处理可依次继续进行，直到重新生成第1级的帧F1、F2、…、F16为止。由于图1的EZBC 54执行的压缩有损耗，所以第2-5级中重新生成的帧将近似地但不精确地与时间滤波前的第2-5级中的原始帧相同。

检测和处理I块

因为如前结合图2所述MCTF分解被类似地应用到多对帧，所以注意力再次集中到图2的一级中的有代表性的一对连续帧(例如第4级的帧L1和L2)。这对连续帧中的代表性的两帧被表示为帧A和B，其中从帧A到帧B执行前向估计，使得帧A在时间上比帧B早。帧B中新暴露的像素在帧A中不具有对应的像素。类似地，帧A中封闭的像素在帧B中不具有对应的像素。本发明利用I块来局部处理由帧B中新暴露的像素引起的较差匹配的运动块。对于根据本发明标识的I块，如下所述，省略了MC时间滤波，并使用空间内插来确定I块中的像素值。得到的用于I块的空间内插误差块(也称为内插的I块的残留误差块)随后被重叠在(即插入到)关联MCTF时间高帧中的对应块上。

本发明公开了一种压缩视频的方法，其涉及利用成对输入帧(例如具有输入帧A和B的代表对)中的运动补偿块的时间空间或时空变换。这些块具有各种尺寸，并被选择来匹配局部运动矢量场，从而存在该场具有高空间梯度的小块和空间梯度小的更平坦区域内的大块。所述基于块的运动场用于控制时间空间变换，使得其沿着合适的运动轨迹进行滤波。该变换的输出被压缩，用于发送或存储。

因为由于运动而在帧中引起的覆盖或暴露区域(例如在静止的背景目标前移动的球)，所以一些块可能不与下一帧(时间方向)中的相邻块相连。这些区域(即I块)不应参与MC时间滤波，因为MC时间滤波将导致低帧频视频中的伪影。这些I块需要与时间高帧中的其它块(即P块)一起被压缩。P块可用于经由空间内插而空间预测不相连的I块。这些I块由此适于与非混合的MCTF一起工作。

图3是描绘根据本发明实施例的用于利用MCTF时间高帧中的I块的步骤31-38的流程图。

步骤31在MCTF滤波级利用两个连续帧A和B，其中从帧A到帧B执行前向估计。作为示例，帧A和B可代表图2的第5级中的帧F1和F2、或图2的第4级中的帧L1和L2。

步骤32和33分别确定根据本发明实施例的图4所示的帧A和B中的像素的连接状态。帧A和B中的每一像素可被分类为具有如下“连接”或“不连接”的连接状态。图4示出了帧A中的像素A1、A2、…、A12以及帧B中的像素B1、B2、…、B12。像素A1、A2、A3和A4在帧A的第1块中。像素A5、A6、A7和A8在帧A的第2块中。像素A9、A10、A11和A12在帧A的第3块中。像素B1、B2、B3和B4在帧B的第1块中。像素B5、B6、B7和B8在帧B的第2块中。像素B9、B10、B11和B12在帧B的第3块中。相对于从帧A到帧B的前向运动估计，帧A中的像素用作帧B中的像素的参考。注意：帧A和B中的块都是4×4像素块，而图4仅示出了每个4列块中的一列。在图4中，由来自帧B中的像素P_B的箭头指向的帧A中的像素P_A被用作像素P_B的参考。例如，帧A中的像素A1被用作帧B中的像素B1的参考。

在步骤32，帧A中的像素如果未被帧B中的任何像素用作参考，则被标记为未连接。因此，像素A7和A8未连接。帧A中的像素如果被用作帧B中的像素的参考，则被连接。因此，像素A1-A6和A9-A12被连接。然而，像素A3和A4需要特殊对待，因为像素A3和A4各自被帧B中多于一个像素用作参考。例如，像素A3被帧B的像素B3和B5用作参考，并且本发明使用基于最小均方移位帧差(DFD)(下面将定义)计算的算法，来将像素A1保留为像素B3或像素B5(而非像素B3和B5两者)的参考。注意，像素A3在帧A的第1块中，而像素B3在帧B的第1块中，该算法计算帧A的第1块和帧B的第1块之间的作为均方DFD的DFD11。注意，像素A3在帧A的第1块中，而像素B5在帧B的第2块中，该算法计算帧A的第1块和帧B的第2块之间的作为均方DFD的DFD12。如果DFD11小于DFD12，则像素A3被保留作为像素B3的参考，而像素A3被撤销作为像素B5的参考。如果DFD12小于DFD11，则像素A3被保留作为像素B5的参考并被撤销作为像素B3的参考。如果DFD11等于DFD12，则可使用任何同分决赛(tie-breaker)。同分决赛的第一示例是“扫描顺序”，这意味着像素A3保留作为以下像素的参考，该像素是首先被确定为使用像素A3作为参考的像素B3和B5中的任一个。同分决赛的第二示例是从0和1之间的均匀分布中拾取随机数R，并保留像素A3：作为像素B3的参考(如果R小于0.5)；或者作为像素B5的参考(如果R不小于0.5)。在图4的例子中，DFD11小于DFD12，使得像素A3被保留作为像素B3的参考并撤销作为像素B5的参考。类似地，像素B4和B6各自使用像素A4作为参考，并且可使用先前描述的基于DFD的算法来保留像素A4作为像素B4或像素B6(而不是像素B4和B6两者)的参考。在图4的例子中，基于前述基于DFD的算法，像素A4被保留作为像素B4的参考而撤销作为像素B6的参考。

在步骤33，在已应用了基于DFD的算法来解决帧A中的像素被帧B中的多于一个像素用作参考的情况之后，如果没有使用帧A中的参考像素，则帧B中的像素被标记为未连接。例如，如前所述，在应用了基于DFD的算法之后，像素A3和A4被分别撤销作为像素B5和B6的参考。因此，像素B5和B6未连接。否则，帧B中的像素被连接。因此，像素B1-B4和B7-B12被连接。注意，如果已执行了前述基于DFD的算法(即当确定了帧A中的像素的连接状态时)，则图4中从像素B5指向像素A3的箭头和从像素B6指向像素A4的箭头不相关，因为像素A3和A4已分别被撤销作为像素B5和B6的参考。尽管图4示出了在步骤32之后执行步骤33，但是可替换地，可以在步骤32之前执行步骤33。可以在执行步骤32和33之前、期间、或之后的任一时间，执行前述基于DFD的算法，该算法用于解决帧A中的像素被帧B中的多于一个像素用作参考的情况。例如，如果在步骤33之前执行步骤32，则可以在步骤32之前、步骤32和33之间、或步骤33之后执行前述基于DFD的算法。作为另一个例子，如果在步骤32之前执行步骤33，则可以在步骤33之前、步骤33和32之间、或步骤32之后执行前述基于DFD的算法。

作为执行步骤32和33的结果而实际需要的是帧B中的每个像素相对于帧A中的各像素的连接状态(即连接或未连接)。由此，可替换地，可省略步骤32，因为帧B中的每个像素的连接状态需要知道用于帧B中的每个像素的帧A中的参考像素，而不需要知道帧A中的每个像素的连接状态。

如下定义帧A中的块与帧B中的块之间的均方DFD。假设n表示所述块中的每一块的像素数目。假设V_A1、V_A2、…、V_An表示帧A中的块中的像素的值(例如亮度或色度)。假设V_B1、V_B2、…、V_Bn表示帧B中的块中的对应像素的值。帧A中的块与帧B中的块之间的均方DFD是：

均方DFD＝[(V_A1-V_B1)²+(V_A2-V_B2)²+…+(+V_An-V_Bn)ⁿ]/n    (1)

前述基于DFD的算法可应用到具有与子像素之间的连接相关的子像素精度的运动矢量，如高性能视频编码器中利用的那样。子像素是相邻像素之间的位置。内插的子像素用于计算DFD。由此，不需要MCTF算法中的其它改变，仅需要在参考像素不是整数时，使用空间内插的规定形式。作为例子，可为了该目的而利用可分离的9抽头FIR内插滤波器。

在执行了图4的步骤32和33之后，帧A和B中的所有像素已被分类为“未连接”或“连接”。由于前述基于DFD的算法消除了从帧B中的两个或多个像素到帧A中的参考像素的多重连接，所以帧A中的每个“连接”像素正好被连接到帧B中的一个像素，反之亦然。

根据本发明的实施例，步骤34将帧B中的块分类为“单方连接”或“未连接”。如果一帧的块中的像素的小部分F未连接，则该块是“未连接的”块；否则，该块是“单方连接的”块。所述小部分F具有反映图像质量和处理时间之间的折衷的值，因为I块需要额外的处理时间。所述小部分F尤其可具有至少0.50(例如，在0.50到0.60、0.50到0.75、0.60到0.80、0.50到1.00、0.30到1.00、0.50到小于1.00等的范围内)的值。通过检查帧B的单方连接的块中的像素所连接到的帧A中的参考像素，可对于帧B中的每一单方连接块而确定帧A中的匹配块(称为帧A的单方连接块)。得到的帧A和B中的单方连接块形成单方连接块的匹配对的集合，其中每一匹配对包括帧B中的单方连接块和帧A中的匹配单方连接块。假设单方连接块的匹配对被分别表示为帧A和帧B中的第一和第二单方连接块。

根据本发明的实施例，如果满足以下重新分类标准，则步骤35将单方连接块的匹配对中的第一和第二单方连接块重新分类为未连接。假设V₁和V₂分别表示第一和第二单方连接块的像素方差。块的像素方差是块的像素值与块的平均像素值之间的均方偏差。假设V_MIN表示V₁和V₂中的最小值。然后，如果第一和第二块之间的均方DFD超出fV_MIN，则第一和第二单方连接块被重新分类为未连接块，其中f是在0到1的范围内的实数。例如，f可以尤其在0.4到0.6、0.5到0.7、0.4到0.75、0.5到0.9、0.4到1.00等的范围内。在执行了步骤35之后，完成将帧B中的每一块分类为“未连接”或“单方连接”的动作。

根据本发明的实施例，步骤36将帧B中的每一未连接块归类(categorizes)为P块或I块。I块将随后将其初始像素值替换为从I块外部的相邻像素导出的空间内插值，下面将进行描述。I块像素的初始像素值和空间内插像素值之间的差值是内插I块像素的残留误差。I块中的所有像素处的残留误差块被称为I块的残留误差块，或与I块相关联。

为了确定未连接块是I块还是P块，形成内插I块，计算其残留误差块，并还计算残留误差块中的残留误差和(S_RES)的绝对值。S_RES被称为未连接块的“残留内插误差”。残留误差是残留误差块的各像素处的误差。另外，对未连接块执行前向和后向运动。计算前向和后向运动补偿后的预测误差的绝对DFD之和。确定前向和后向运动补偿后的预测误差的绝对DFD之和的最小值(S_MC-MIN)。S_MC-MIN被称为未连接块的“最小运动补偿误差”。如果S_RES小于S_MC-MIN，则未连接块被分类为I块。如果S_RES不小于S_MC-MIN，则未连接块被分类为P块。

根据本发明的实施例，在步骤37，步骤36所确定的I块经过可用相邻像素的空间内插处理，并生成与该内插I块关联的残留误差块。帧中的各块可以具有固定尺寸或可变尺寸。图5-7和9在下文描述了根据本发明实施例的用于固定块尺寸情况的内插实施例，而图8用于在下文描述根据本发明实施例的可变块尺寸情况。

在步骤38，与内插I块关联的残留误差块被重叠在与所分析的一对帧A和B关联的相关时间高帧上(即位于其中)，用于在执行图2的空间分析53之后由EZBC 54随后进行相关时间高帧的压缩。图7C(下文描述)示出了该残留误差块包含很多接近零的值并由此可适于被有效压缩。

图5示出了包括I块、P块、和单方连接块的帧。I块包括第1-3块，而P块和单方连接块包括含有第4-10块的剩余块。每一I块具有4个可能相邻块：上相邻、下相邻、左相邻、和右相邻。在这里使用的内插算法中，帧中的各块根据扫描顺序进行处理，并且仅“可用”块(即其中建立有像素值的先前处理的I块、其中具有原始数据的P块、和/或单方连接块)可用于空间内插。例如，对于第1块使用图5中的从左到右并然后从上到下的扫描顺序，仅相邻的第4-5块可用于第1块的空间内插，因为第2块和第3块不可用。然而，对于第2块，存在4个相邻块可用于在第1块的内插之后进行第2块空间内插，即第1和6-8块。类似地，存在4个相邻块可用于在第1块的内插之后进行第3块空间内插，即第1和8-10块。

遵循光栅扫描规则(例如前述从左到右并然后从上到下的扫描规则)而执行空间内插。基于可用相邻块的数目和它们的位置，存在不同的内插函数。图6图示了以下表示法：“u”表示上相邻像素，“lw”表示下相邻像素，“lf”表示左相邻像素，“r”表示右相邻像素，而“in”表示I块中的内插像素值。内插可以是线性或非线性的，并且可使用许多不同的内插方案。

图7A-7C(统称为图7)图示了其中仅一个相邻块可用的情况。图7A中的4×4像素的I块40由行线段41-44定义，并且假设仅可用相邻像素在块40之上的上相邻块中的行线段45中。图7A中为I块40示出的示例像素值是空间内插之前的初始值。行线段45中的像素值用于空间内插。对于该情况，表1中的C语言代码可用于实现该空间内插。

表1

for(i＝0；i＜4；i++)  for(j＝0；j＜4；j++)    in[i*4+j]＝u[j]；

图7B示出了运行表1的C语言代码所得到的I块40中的结果内插值。图7C示出了通过从图7A的初始像素值减去图7B的内插像素值而确定的残留误差块。图7C描绘的残留误差块重叠在(即位于)与所分析的一对帧A和B关联的相关时间高帧中，用于由图2的EZBC 54进行随后的相关时间高帧的压缩。尽管图7A-7C描述了仅上相邻像素可用于内插的实施例，但是可以从上述“上”相邻情况中、或者通过正确的坐标旋转而类似地导出仅左、右、或下相邻像素可用于内插的情况。

表2和3图示了其中两个相邻块可用的内插算法。表2详细说明了根据图6的表示法使用上和左位置中的可用相邻像素计算4×4I块中的内插像素值in[0]…in[15](见图6)的公式。表3详细说明了根据图6的表示法使用上和下位置中的相邻像素计算4×4I块中的内插像素值in[0]…in[15]的C语言代码。

表2

in[0]＝(lf[0]+u[0])/2；in[1]＝u[1]；           in[2]＝u[2]；            in[3]＝u[3]；in[4]＝lf[1]；         in[5]＝(in[4]+in[1])/2；in[6]＝in[2]；           in[7]＝in[3]；in[8]＝lf[2]；         in[9]＝in[8]；          in[10]＝(in[9]+in[6])/2；in[11]＝in[7]；in[12]＝lf[3]；        in[13]＝in[12]；        in[14]＝in[13]；         in[15]＝(in[11]+in[14])/2

表3

  or(i＝0；i＜4；i++)  {    in[i]＝u[i]；    in[12+i]＝lw[i]；    in[4+i]＝in[8+i]＝(u[i]+lw[i])/2；  }

可以从上面分别结合表2和3所述的“上和左”或“上和下”相邻情况、或通过正确的坐标旋转而类似地导出其中两个相邻块可用的其它实施例。

表4图示了其中三个相邻块可用的内插算法。表4详细说明了根据图6的表示法使用上、左、和右位置的相邻像素来计算4×4I块中的内插像素值in[0]…in[15](见图6)的C语言代码。

表4

  in[0]＝(lf[0]+u[0])/2；in[1]＝u[1]；           in[2]＝u[2]；  in[3]＝(u[3]+r[0])/2；  in[4]＝lf[1]；         in[5]＝(in[4]+in[1])/2；in[7]＝r[1]；  in[6]＝(in[2]+in[7])/2；  in[8]＝lf[2]；         in[9]＝in[8]；          in[11]＝r[2]； in[10]＝in[11]；  in[12]＝lf[3]；        in[13]＝in[12]；        in[15]＝r[3]； in[14]＝in[15]；

可以从上面结合表4所述的“上、左、和右”相邻情况、或通过正确的坐标旋转而类似地导出其中三个相邻块可用的其它实施例。

表5图示了其中四个相邻块可用的内插算法。表5详细说明了根据图6的表示法使用上、下、左、和右位置的相邻像素来计算4×4I块中的内插像素值in[0]…in[15](见图6)的C语言代码。

表5

  in[0]＝(lf[0]+u[0])/2；  in[1]＝u[1]；            in[2]＝u[2]；  in[3]＝(u[3]+r[0])/2；  in[4]＝lf[1]；           in[5]＝(in[4]+in[1])/2； in[7]＝r[1]；  in[6]＝(in[2]+in[7])/2；  in[12]＝(lf[3]+lw[0])/2；in[13]＝lw[1]；          in[14]＝lw[2]；in[15]＝(lw[3]+r[3])/2；  in[8]＝lf[2]；           in[9]＝(in[8]+in[13])/2；in[11]＝r[2]； in[10]＝(in[14]+in[11])/2；

图8图示了可变块尺寸的情况，其由匹配从4×4到64×64的范围内的块尺寸的5级分层可变尺寸块而引起。例如，在图8中，示出了I块11和12。块11具有8×8的像素尺寸，而块12具有4×4的像素尺寸。如果按照前述从左到右并然后从上到下的扫描顺序对块11和12进行处理(即在内插块12之前，内插块11)，则块12不可用于块11的内插。为了简化内插，块11可被看作用于内插目的的4个单独的4×4I块，从而空间内插可被实现为固定块内插。

图9A-9F(统称为图9)图示了根据本发明实施例的用于确定I块的像素值的定向空间内插方案。图9A-9F描绘了在帧60的一部分中的4×4I块61。这部分帧60包括像素P11…P99。I块61包括像素P22、P23、P24、P25、P32、P33、P34、P35、P42、P43、P44、P45、P52、P53、P54、和P55。在图9A-9F中，不在I块61中的所有像素是I块61中的像素的相邻像素。I块61中的像素的内插沿着与X轴成θ固定角的平行线而进行，例如如图9A所示的一条平行线，即线66。图9B-9F中的每个图代表具有不同值的θ的实施例。为了出于图示的目的而估计θ的值，简要假设每个像素是正方形。由此，对于对角穿过像素P25、P34、P43、和P52的顶点的图9A所示线66，θ＝45度。当然，如果像素具有矩形而非正方形的形状，则θ将与图9A的线62的45度不同。注意，θ和θ+180度代表平行线的相同集合。沿着每一这样的线的内插利用该线上最近可用相邻像素的像素值，其中可用相邻像素是先前已建立了其像素值的相邻像素。定向内插方案假设至少一个相邻像素总是可用于平行线中的每一条这样的线。

图9B图示了相对于平行线63、64、…、69具有θ＝45度的定向内插。线63、64、…、69被称为“定向线”。由于线63穿过像素P22，所以线63用于基于内插使用以下像素而确定像素P22的值：如果相邻像素P13和P31都可用，则使用P13和P31；如果P13可用而P31不可用，则仅使用相邻像素P13；或者如果P31可用而P13不可用，则仅使用相邻像素P31。由于线64穿过像素P23和P32，所以线64用于基于内插使用以下像素而确定像素P23和P32的值：如果相邻像素P14和P41都可用，则使用P14和P41；如果P14可用而P41不可用，则仅使用相邻像素P14；或者如果P31可用而P13不可用，则仅使用相邻像素P31。类似地，沿着线65、66、67、68、和69的内插分别用于确定(P24，P33，P42)、(P25，P34，P43，P52)、(P35，P44，P53)、(P45，P54)、和(P55)处的像素值。

线67-69表示最近相邻像素的替代可能性。例如，线68在I块61的对边处具有相邻像素(P36，P27，和P18)以及(P63，P72，和P81)。在选择相邻像素(P36，P27，和P18)中的哪个相邻像素来使用的过程中，如果像素P36可用，则定向内插将使用像素P36，因为像素P36是相邻像素(P36，P27，和P18)中的最近相邻像素。如果像素P36不可用、而像素P27可用，则定向内插将使用像素P27，因为像素P27是相邻像素(P27和P18)中的最近相邻像素。如果像素P27不可用、而剩余的相邻像素P18可用，则定向内插将使用像素P18。如果像素P27不可用，则定向内插将不使用像素(P36，P27，和P18)中的任一个。类似地，定向内插将基于用于作出选择的最近可用相邻像素标准而选择相邻像素(P63，P72，和P81)中的一个像素。所以，作为应用该最近可用相邻像素标准的结果，用于确定像素P45和P54的值的沿着线68的定向内插将利用以下相邻像素组合中的一种：仅P63、仅P72、仅P81、P63和P36、P63和P27、P63和P18、P72和P36、P72和P27、P72和P18、P81和P36、P81和P27、P81和P18、仅P36、仅P27、和仅P18。

接下来图示沿着线68的用于线性内插的定向内插，来确定像素P45和P54的像素值(假设相邻像素P36和P63都可用)。沿着线68的点Q0、Q1、Q2、Q3和Q4如图9B所示。点Q0、Q1、Q2、Q3和Q4在线68中分别跨越像素P27、P36、P45、P54和P63的部分的中点。假设D12、D13和D14分别表示点Q1与点Q2、Q3、Q4之间的距离。假设F1214和F1314分别表示D12/D14和D13/D14。假设V36和V63分别表示像素P36和P63处的像素值。然后，像素P45和P54的像素值分别是(1-F1214)*V36+F1214*V63和(1-F1314)*V36+F1314*V63。

沿着线68的用于线性内插的定向内插提出了以下问题：如果相邻像素P36不可用而相邻像素P27可用，则如何进行内插。如果V27表示像素P27处的像素值，则只要V36出现在内插公式中，V27将替代V36。然而，本发明的范围包括用于处理沿着线68的距离的三种选项。

第一选项是在内插公式中保持参数F1214和F1314，尽管像素P36已被像素P27替换为最近可用相邻像素，但是使用点Q1作为测量距离的参考，该公式在概念上仍是等效的。对于第一选项，像素P45和P54处的像素值分别是(1-F1214)*V27+F1214*V63和(1-F1314)*V27+F1314*V63。

第二选项是利用与在相邻像素P27处开始线68的点Q0的距离。对于第二选项，D02、D03和D04分别表示点Q0和点Q2、Q3、Q4之间的距离。假设F0204和F0304分别表示D02/D04和D03/D04。然后，像素P45和P54处的像素值分别是(1-F0204)*V27+F0204*V63和(1-F0304)*V27+F0304*V63。

第三选项是使用第一和第二选项之间的折衷。不象第一和第二选项一样使用(F1214和F1314)或(F0204和F0304)，而使用参数(F1214，F0204)_AVE和(F1314，F0304)_AVE，其中(F1214，F0204)_AVE是F1214和F0204的加权或不加权的平均值，而(F1314，F0304)_AVE是F1314和F0304的加权或不加权的平均值。然后，像素P45和P54处的像素值分别是(1-(F1214，F0204)_AVE)*V27+(F1214，F0204)_AVE*V63和(F1314，F0304)_AVE*V27+(F1314，F0304)_AVE*V63。如果(F1214，F0204)_AVE和(F1314，F0304)_AVE是加权平均值，则权重可基于外在(extrinsic)因素，例如像素P36和P27沿着线68对I块61的图像质量的相对重要性的外在知识，而与像素P36和P27沿着线68距点Q2和Q3的距离无关。

图9C-9F与图9B类似，除了θ值不同。在图9C中，对于定向线71-74，θ＝90度。利用相邻像素P12、P62、P72、P82和P92的子集，通过沿着线71内插而确定像素P22、P32、P42和P52的值。利用相邻像素P13、P63、P73、P83和P93的子集，通过沿着线72内插而确定像素P23、P33、P43和P53的值。利用相邻像素P14、P64、P74、P84和P94的子集，通过沿着线73内插而确定像素P24、P34、P44和P54的值。利用相邻像素P15、P65、P75、P85和P95的子集，通过沿着线74内插而确定像素P25、P35、P45和P55的值。

在图9D中，对于定向线81-87，θ＝135度。利用相邻像素P41、P63、P74、P85和P96的子集，通过沿着线81内插而确定像素P52的值。利用相邻像素P31、P64、P75、P86和P97的子集，通过沿着线82内插而确定像素P42和P53的值。利用相邻像素P21、P65、P76、P87和P98的子集，通过沿着线83内插而确定像素P32、P43和P54的值。利用相邻像素P11、P66、P77、P88和P99的子集，通过沿着线84内插而确定像素P22、P33、P44和P55的值。利用相邻像素P12、P56、P67、P78和P89的子集，通过沿着线85内插而确定像素P23、P34和P45的值。利用相邻像素P13、P46、P57、P68和P79的子集，通过沿着线86内插而确定像素P24和P35的值。利用相邻像素P14、P36、P47、P58和P69的子集，通过沿着线87内插而确定像素P25的值。

在图9E中，对于定向线76-79，θ＝0度(或180度)。利用相邻像素P21、P26、P27、P28和P29的子集，通过沿着线76内插而确定像素P22、P23、P24和P25的值。利用相邻像素P31、P36、P37、P38和P39的子集，通过沿着线77内插而确定像素P32、P33、P34和P35的值。利用相邻像素P41、P46、P47、P48和P49的子集，通过沿着线78内插而确定像素P42、P43、P44和P45的值。利用相邻像素P51、P56、P57、P58和P59的子集，通过沿着线79内插而确定像素P52、P53、P54和P55的值。

在图9F中，对于定向线101-105，θ＝26.56度(即θ是2/4的反正切)。利用相邻像素P31和P14的子集，通过沿着线101内插而确定像素P22和P23的值。利用相邻像素P41和P16的子集，通过沿着线102内插而确定像素P32、P33、P24和P25的值。利用相邻像素P51、P26、P27、P18和P19的子集，通过沿着线103内插而确定像素P42、P43、P34和P35的值。利用相邻像素P61、P36、P37、P28和P29的子集，通过沿着线104内插而确定像素P52、P53、P44和P45的值。利用相邻像素P71、P46、P47、P38和P39的子集，通过沿着线105内插而确定像素P54和P55的值。

图9A-9F图示了定向空间内插，其特征在于通过沿着平行定向线的空间内插而确定I块中的所有像素值。相反，图7A-7C和表1-5图示了非定向空间内插，其特征在于通过空间内插中的最近可用相邻空间内插而确定I块中的所有像素值，在该最近可用相邻空间内插中，利用穿过I块的非定向线。用于I块的另一空间内插方法在于混合空间内插，其包括定向空间内插和非定向空间内插的组合。利用混合空间内插，至少一条定向线用于I块中的一些空间内插，而通过其中利用穿过I块的非定向线的最近可用相邻空间内插来确定I块中的一些像素值。当使用定向空间内插或混合空间内插时，选中的方向和混合掩模必须被编码并作为辅助(side)信息而发送。为此目的，本发明的一个实施例使用短固定霍夫曼代码。

图10图示了根据本发明实施例的混合空间内插。图10包括空间内插中使用的定向线121-124，用于确定(沿着线121)的像素P25、P34、P43和P52的值、(沿着线122)的像素P35、P44、和P53的值、(沿着线123)的像素P45和P54的值、和(沿着线124)的像素P55的值。然而，利用最近上相邻像素P12、P13、P14和最近左相邻像素P21、P31、P41，通过非定向空间内插，而确定像素P22、P23、P24、P32、P33和P42的值。

如前面结合图6-10和表1-5的空间内插例子所示，基于相对于给定帧中的每一I块的最近可用相邻像素的值，通过空间内插，而计算给定帧中的所述每一I块的像素值。如果给定帧中的特定I块外面的给定像素与I块足够接近而可能通过所述空间内插对I块中的像素值作出贡献，则所述给定像素被称为相对于I块的相邻像素。

前面结合图6-10和表1-5的讨论用于通过集中于线性内插的内插而确定I块中的像素值。不论如何，本发明的范围也包括根据任何非线性内插方案的非线性内插，其开发了对I块中的像素值作出贡献的各种相邻像素的相对价值(relative importance)。

OBMC处理

本发明公开了与视频帧的处理相关的实施例，其中所处理的每一帧被划分为包括至少两个不同尺寸的块的M块，并且其中M是至少9。

利用传统的块运动补偿，所处理的当前帧被划分为由像素组成的块，其中当前帧中的像素的每一这样的块B_CUR0根据参考帧中的相同尺寸的块B_REF0而预测。当前帧中的像素的块B_CUR0被称为“当前块”或“自身块”。当前帧中的自身块B_CUR0在空间上从参考帧中的块B_REF0位移运动矢量V₀。由此，当前帧中的自身块B_CUR0中的像素位置P₀(由矢量P_CUR0标识)处的像素值I_CUR0(P_CUR0)被预测为等于参考帧中的块B_REF0中的矢量(P_CUR0-V₀)所标识的像素位置处的像素值I_REF0(P_CUR0-V₀)。因变量“I”表示亮度和/或色度的像素值。传统块运动补偿的缺点涉及在块边界处引起的不连续性(成块伪影)。该不连续性可具有尖锐水平和垂直边缘的形式，其可被人眼高度可见，并也可在用于对残余帧变换编码的相关傅立叶变换中产生激振(ringing)效应(即高频子带中的大系数)。

利用重叠块运动补偿(OBMC)，可利用自身块B_CUR的最近相邻块来预测自身块B_CUR中的像素值。例如，最近相邻块可包括紧靠在自身块B_CUR右、下、左、上的4个最近相邻块，分别由运动矢量V1、V2、V3和V4表示为参考帧中的B_l、B_REF4。参考帧中的块B_REF1、B_REF2、B_REF3、和B_REF4最可能是参考帧中的块B_REF0的非最近相邻块。权重W(P_CUR0)与自身块B_CUR0中的像素位置P₀(由矢量P_CUR0标识)相关联。权重W(P₁)、W(P₂)、W(P₃)、和W(P₄)分别与最近相邻块B₁、B₂、B₃和B₄中的像素位置P₁、P₂、P₃和P₄相关联，使得像素位置P₁、P₂、P₃和P₄对应于像素位置P₀。利用OBMC，像素位置P₀处的像素值I_CUR0(P_CUR0)被预测为等于W(P_CUR0)*I_REF0(P_CUR0-V₀)+[W(P₁)*I(P₁-V₁)+W(P₂)*I(P₂-V₂)+W(P₃)*I(P₃-V₃)+W(P₄)*I(P₄-V₄)]。由此，在自身块B_CUR0中的矢量P_CUR0所标识的像素位置处的预测像素值通过考虑来自参考帧中的它们移位的位置处的最近相邻块的像素值贡献，而减轻了块边界处引起的不连续性。包括自身块B_CUR0中所有像素的W(P_CUR0)的权重阵列构成自身块B_CUR0的“加权窗口”。类似地，包括最近相邻块B₁、B₂、B₃、和B₄中所有像素的W(P₁)、W(P₂)、W(P₃)、和W(P₄)的权重阵列分别构成最近相邻块B₁、B₂、B₃、和B₄的加权窗口。在图17、18、21和22中呈现了根据本发明的加权窗口及其生成的例子，这将在下面进行讨论。

本发明公开了可变块尺寸OBMC。接下来，在图11和12中图示了当前帧中的块及其与参考帧中的块的关系。

图11描绘了根据本发明实施例的(例如通过四叉树算法)已被配置为可变尺寸块的当前帧240。如图所示，当前帧240包括22个块。图11中的每一块考虑到其最近相邻块而被处理为自身块。例如，将正处理的块241看作自身块。自身块244具有最近相邻块242-246。注意：自身块可具有等于、大于、或小于最近相邻块的尺寸。在图11中，自身块241的尺寸是：等于其最近相邻块242的尺寸、大于其最近相邻块245和246的尺寸、并小于其最近相邻块243和244的尺寸。

图12描绘了根据本发明实施例的图11的当前帧240、和参考帧260、以及分别链接当前帧240中的块241-246和参考帧260中的对应块261-266的矢量251-256。矢量251-256在参考帧260上的正轴投影分别是表示块241-246相对于块261-266的矢量位移的运动矢量。尽管为了简明起见，块261-266表现为在参考帧260中具有相同尺寸，但是实际上，块261-266分别与当前帧240中的它们的对应块241-246具有相同的尺寸。参考帧260代表一个或多个参考帧，每个这样的参考帧具有其自己的运动矢量以及与当前帧的各块相关联的块，因为可以根据单一参考帧或多个参考帧中的对应像素而对当前帧中的每一像素进行预测。

本发明公开了一种压缩视频的方法，其涉及在成对输入帧(例如前面结合图3讨论的具有输入帧A和B的代表对)中利用运动补偿后的块的时间空间或时空变换。这些块具有各种尺寸，并被选择用来匹配局部运动矢量场，从而存在该运动具有高空间梯度的小块、和该运动的空间梯度小的更平坦区域内的大块。不过，如同前面进行的解释，不同块的运动矢量在跨越块边界时是不连续的。结果，在根据另一帧预测一帧的过程中，创建了伪影。本发明的OBMC通过利用当前块的运动矢量及其最近相邻块的运动矢量、根据估计的加权组合进行预测，而着手解决该问题。本发明的OBMC还通过迭代调整该块运动矢量以达到改进的运动矢量而得以改进，这增加了得到的帧预测的精度并所以增加了编码效率。利用本发明，可以可选地省略该迭代。利用OBMC获得的MCTF的输出然后被压缩用于发送或存储。另外，运动矢量作为开销被发送到接收机，并可构成总比特率的大约10-15％。

图13A是根据本发明实施例的描绘了用于在图2的MCTF时间高帧中利用可变块尺寸OBMC的步骤211-214的流程图。在步骤211之前，当前帧已被配置为包括至少两个不同尺寸的块的M块，其中M至少是9。步骤211执行可变尺寸块匹配(VSBM)以获得本领域公知的用于运动块的初始矢量(例如见：Ostermann，and Zhang，“Video Processing and Communications”，Prentice-Hall，pp.182-187(2002))。步骤212将当前帧中的各块分类为I块或运动块。“运动块”被定义为非I块。前面已结合图3的步骤31-36描述了未连接块(即I块和P块)和单方连接块的检测和分类。图15在下面描述包括P块、缺省(DEFAULT)块、和反转(REVERSE)块的各种类别的运动块。步骤213执行可变块尺寸OBMC，以提供用于运动块和I块的重叠平滑。在步骤214，根据MCTF对步骤213中生成的运动场(即平滑的运动块和/或I块)进行处理。

图13B是描绘了根据本发明实施例的描述图13A的可变块尺寸OBMC处理步骤213的步骤221-223的流程图。对于当前帧中的给定自身块和关联最近相邻块，步骤221执行生成用于自身块及其关联最近相邻块的加权窗口的收缩方案，该方案考虑自身块是运动块还是I块，并考虑该最近相邻块是运动块还是I块。如果最近相邻块是I块，则步骤221的收缩方案调用执行反射方案的步骤222，其以说明最近相邻I块的内在无能(intrinsic inability)的方式影响加权窗口的生成，从而与参考帧通信。

按照预定扫描顺序所指明的次序，对于给定自身块的所有最近相邻块、并然后对于当前帧的所有自身块，执行收缩方案执行步骤221。执行步骤223，其中已利用了用于当前帧中的每一自身块的初始运动矢量。尽管自身块的所述初始运动矢量被用于生成加权窗口，但是所述初始运动矢量可能不是最佳加权窗口，因为当考虑所生成的加权窗口时，运动矢量的混集(perturbed set)可导致对于当前帧中像素值的更精确预测。因此，步骤223执行迭代处理，使得每次迭代都扰乱运动矢量，从而根据步骤222生成的加权窗口而改进当前帧中的像素值的精度。

图13B中的步骤221-223反映了图13A的可变块尺寸OBMC处理步骤213的简化描述。在图16-18和21-22的示意性加权窗口生成示例之后，图23将在下面呈现详细描述图13B的步骤221-222的可变块尺寸OBMC处理的实施例的流程图。另外，图24将在下面呈现详细描述图13B的步骤223的用于改进运动矢量的迭代处理的流程图。

图14是根据本发明实施例的与图13A-13B的流程图关联的帧处理的方框图。图14图示了以下依次排序的处理：分量(YUV)分层可变尺寸块匹配(HVS-M)运动估计231(对应于图13A的步骤211)；I块检测232(对应于图13A的步骤212)；可变块尺寸OBMC执行233(在图13A的步骤213中执行)；MTCF处理234(对应于图13A的步骤214)；和MC-EZBC编码器处理235。HVSBM运动估计231生成由算术编码器236处理的运动矢量。根据由EZBC编码器235生成的编码输出和由算术编码器236生成的编码输出而形成比特流237。

在图14中，MCTF处理234依次包括I块、P块、反转块、和缺省块的处理。反转块预测包括根据前一B帧而最佳预测的那些块的预测。缺省块的像素包括实际参与MC滤波的那些像素，既用于父帧H的“预测”步骤，又用于父帧L的“更新”步骤。

图15描绘了根据本发明实施例的要由MCTF变换为高时间帧H和低时间帧L的两个连续输入帧A和B。见图2(以及前面对其的讨论)，通过MCTF处理从帧A和B中导出H和L帧。然而，在图2中，对H和L帧的时间定位进行不同的选择。在图2中，L帧是输入帧A的时间基准，H帧是输入帧B的时间基准；而在图15中，H帧是输入帧A的时间基准，L帧是输入帧B的时间基准。实际上，已发现任一组时间基准都适用，并且任一组时间基准都存在于现代基于MCTF的可伸缩视频编码器中。上标“t”和“t-1”分别表示当前时间t和先前时间t-1。如前所述，如双箭头所示，缺省块参与(用于帧H的)预测和(用于帧L的)更新处理。如单箭头所示，P块、反转块和I块仅影响一帧，即H帧。没有示出对于这些块的更新。I块表示如前所述仅采用空间内插/预测的块。在I块检测之后，执行图14的可变尺寸OBMC执行233。

在OBMC框架中，本发明把对帧进行解码之前由解码器接收的任何数据看作有关最后采用的真预测方案的信息源。

图16描绘了根据本发明实施例的当前帧中的自身块和4个最近相邻块。图16中的自身块270的4个最近相邻块是右最近相邻块271、下最近相邻块272、左最近相邻块273、和上最近相邻块274。对于前述图17-18的示意性例子，假设自身块及其最近相邻块具有相同尺寸。根据前面的假设，使用的加权窗口是左右上下对称的。

图17A和17B(统称为“图17”)图示了根据本发明实施例的4×4加权窗口。在图17A中，自身块是运动块，而在图17B中，自身块是I块。图17A示出了用于自身块的加权窗口270A和分别用于右最近相邻块、下最近相邻块、左最近相邻块、和上最近相邻块的其关联最近相邻块加权窗口271A、272A、273A、和274A。图17B示出了用于自身块的加权窗口270B和分别用于右最近相邻块、下最近相邻块、左最近相邻块、和上最近相邻块的其关联最近相邻块加权窗口271B、272B、273B、和274B。

以下规定用于代表图17-18和21-22的例子中的加权窗口，为了图示目的而使用图17A。对于自身块加权窗口270A，图17A所示像素权重在与物理像素位置处的对应像素值相同的相对像素位置处。然而，对于最近相邻块，图17A所示像素权重被排序和显示为与物理像素位置处的对应像素值反射性地相对。例如，在图17A中，相对于自身块加权窗口270A及其上相邻块加权窗口274A，上相邻块加权窗口274A的最上行276A权重(1111)对应于自身块(按照物理像素位置)加权窗口270A的顶行277A中的像素。作为另一个例子，在图17A中，相对于自身块加权窗口270A及其右相邻块加权窗口271A，右相邻块加权窗口271A的最右列278A权重(1111)对应于自身块270A的最右列279A中的像素。

前述规定具有可见的优点：如果最近相邻块加权窗口叠加在自身块加权窗口270A上，则在最近相邻块加权窗口中的给定矩阵位置处的指明的权重和在自身块加权窗口中的直接在该矩阵位置下的权重被用作本发明的OBMC计算中的相同物理像素的权重。由此，当所有最近相邻块加权窗口叠加在自身块加权窗口270A上时，每一矩阵位置处的权重之和是4，或者对于N×N块一般是N。例如，在图17A中，当所有最近相邻块加权窗口叠加在自身块加权窗口270A上的左上角矩阵位置时，自身块加权窗口270A、右相邻块加权窗口271A、下相邻块加权窗口272A、左相邻块加权窗口273A、和上相邻块加权窗口274A的权重分别是2、1、0、0和1，它们的和是4。

对于作为概率加权窗口的加权窗口，该加权窗口中的权重之和将等于1，这将导致权重具有小于或等于1的分数或小数值。为了在数值上简化表示权重，图17-20中的示意性例子中使用的加权窗口被归一化，使得对于N×N加权窗口尺寸而言权重之和等于N(而不是等于1)，同时应该理解，当加权窗口中的权重用于计算像素值时，该加权窗口应被实现为概率加权窗口(或其等同)。

在图17A中，利用固定4×4块尺寸，自身块是运动块，并且使用两维(2-D)双线性(即直线)内插来确定自身块加权窗口270A以及最近相邻块加权窗口271A、272A、273A和274A的权重。2-D双线性内插像素值对应于沿着自身块的中心和相邻块的中心之间的直线的线性内插。由于2-D双线性内插是两维的，所以双线性内插的权重是沿两个彼此正交的方向的内插值的乘积。由2-D双线性内插导致的权重已被四舍五入为最接近的整数，约束条件是满足归一化条件(即与每一像素关联的权重之和等于N)。如果一个或多个自身块边界与帧边界相符，则自身块的至少一边将不具有最近相邻块，并且所得到的双线性加权窗口的权重将因此与当没有自身块边界与帧边界相符时存在的双线性加权窗口的权重不同。研究表明：2-D双线性内插加权窗口几乎与迭代最优加权窗口一样精确。然而，可使用其它形式的内插(例如四次幂内插、指数内插等)来代替用于图17A的加权窗口或这里讨论的任何其它实施例的加权窗口的双线性内插，使得双线性内插被公开为正使用中。

在图17B中，利用固定4×4块尺寸，自身块是I块。通过提取自身块加权窗口中的一部分权重并将所述一部分权重添加到最近相邻块加权窗口中的所选权重，而从图17A的加权窗口的权重中导出图17B的加权窗口中的权重，其约束条件是满足归一化条件。所述“一部分权重”调整在给出好可视误差性能的方面被实验性地确定，并不以任何方式被优化。其它“一部分权重”如果通过实验性和/或分析方法论而被验证或证实，则其可被利用。所述所选权重是接近块边界的权重。当自身块为I块时，图17A的权重的前述修改通过为相邻块提供相对较高的权重，而促进在自身块边界处的内插像素值的更强烈的平滑。图17B所使用的权重分布方法是“辐射方案”，其将权重分量从自身单元向外辐射到其相邻单元。

对于图17A和/或图17B，一旦已对于右最近相邻块确定了最近相邻块加权窗口，则用于左最近相邻块的最近相邻块加权窗口可通过开发图16所示的反射对称而确定、或可通过双线性内插而计算。类似地，一旦已对于下最近相邻块确定了最近相邻块加权窗口，则用于上最近相邻块的最近相邻块加权窗口可通过开发图16所示的反射对称而确定、或可通过双线性内插而计算。

图17的例子图示了实施例，其中自身块是I块，并且其中所产生的自身块的窗口包括第一像素权重和第二像素权重。第一像素权重小于如果自身块是运动块所应该具有的第一像素权重，第二像素权重等于如果自身块是运动块所应该具有的第二像素权重。例如，图17B的自身I块270B的所选矩阵位置处的第一像素权重“2”小于图17A的运动块270A的对应所选矩阵位置处的权重“3”，并且第二像素权重是作为图17B的自身I块270B和图17A的运动块270A中的相同权重(即相同权重幅度)的剩余像素权重。

因此，生成自身块的权重窗口的步骤可包括：生成自身块的第一权重窗口如同该自身块是运动块一样(例如图17A的生成运动块270A的步骤)；和通过降低第一加权窗口中的权重而从第一加权窗口生成用于自身块的加权窗口(例如通过降低图17A的运动块270A中的权重而生成图17B中的自身I块270B)。

此外，在通过图17的例子而图示的前述实施例中，自身块的每一相邻块的所生成的窗口可包括第三像素权重和第四像素权重，其中第三像素权重大于如果自身块是运动块所应该具有的第三像素权重，并且其中第四像素权重等于如果自身块是运动块所应该具有的第四像素权重。例如，所述第三权重通过右、下、左、和上相邻块权重中的所选部分而被图示，其在图17B中的幅度大于图17A中的幅度；并且所述第四权重通过右、下、左、和上相邻块权重中的剩余部分而被图示，其在图17B中的幅度等于图17A中的幅度。

图18A和18B(统称为“图18”)图示了根据本发明实施例的8×8加权窗口，其中关联的自身块分别是运动块和I块。图18A示出了用于自身块的加权窗口270C和分别用于右最近相邻块、下最近相邻块、左最近相邻块、和上最近相邻块的其关联最近相邻块加权窗口271C、272C、273C、和274C。图18D示出了用于自身块的加权窗口270D和分别用于右最近相邻块、下最近相邻块、左最近相邻块、和上最近相邻块的其关联最近相邻块加权窗口271D、272D、273D、和274D。生成图18的加权窗口的方法与前述用来生成图17的加权窗口的方法相同。

收缩方案

如前结合图11-12所述，自身块及其关联最近相邻块可全部具有相同尺寸，或者自身块的尺寸可以与其关联最近相邻块的至少一个的尺寸不同。本质上，对于与给定自身块关联的最近相邻块，存在三种实施例：

(a)空间最近相邻块的尺寸与自身块的尺寸相同(例如图14的自身块241及其相邻块242)，其是前面结合图17-18分析的“标准相同块尺寸”情况。由此，该实施例的加权窗口如前结合图17-18所述而生成。

(b)空间最近相邻块的尺寸大于自身块的尺寸(例如图11的自身块241及其相邻块243和244)，其通过利用与自身块具有相同尺寸的较大最近相邻块中的一部分来处理，其中所述部分与标准相同块尺寸情况(a)中的最近相邻块占据当前帧中相同的空间。为了图示的目的，图19描绘了根据本发明实施例的图11的帧240，其中示出了最近相邻块243和244的部分243A和243B。部分243A和244A和自身块241具有相同的尺寸，并占据适于标准相同块尺寸情况的帧240内的空间。对于此实施例，分别利用最近相邻块243和244的部分243A和244A作为相对于自身块241的有效最近相邻块。由此，相邻块243的部分243A是相邻块243的唯一一部分，该部分的加权窗口在对自身块241执行OBMC期间影响自身块241中的像素值的预测。类似地，相邻块244的部分244A是相邻块244的唯一一部分，该部分的加权窗口在对自身块241执行OBMC期间影响自身块241中的像素值的预测。实际上，本发明将块243和244“收缩”为相应部分243A和244A。自身块241和相邻块243(或244)各自是运动块，其中相邻块243(或244)的部分243A(或244A)的所产生的加权窗口可包括双线性内插的权重。如上结合图17-18所述对于标准相同块尺寸情况而生成用于该实施例的加权窗口。然而，与较大最近相邻块关联的运动矢量用于提供加权的相邻估计。例如，参考图12，运动矢量253将用于结合利用用于处理自身块241的较大相邻块243的部分243A(见图19)，来定位参考帧260中的块263。

(c)空间最近相邻块的尺寸小于自身块的尺寸(例如图11的自身块241及其相邻块245和246)，其使得必须选择自身块的一部分具有与较小最近相邻块相同的尺寸，并位于较小最近相邻块附近。为了图示的目的，图20描绘了根据本发明实施例的图11的帧240，其中示出了自身块241的部分1A和1B。部分1A和1B分别与最近相邻块245和246具有相同的尺寸(并位于其附近)。对于此实施例，分别利用自身块241的部分1A和1B作为相对于最近相邻块245和246的有效自身块部分。自身块241的部分1A是自身块241的唯一一部分，在该部分，在对自身块241的部分1A执行OBMC期间，相邻块245的加权窗口影响像素值的预测。类似地，自身块241的部分1B是自身块241的唯一一部分，在该部分，在对自身块241的部分1A执行OBMC期间，相邻块246的加权窗口影响像素值的预测。实际上，本发明“收缩”自身块241，从而仅利用部分1A和1B。对于空间最近相邻块尺寸小于自身块的尺寸的实施例，如下结合图21-22的收缩方案示例所述而生成加权窗口，其中自身块的每一所利用的部分包括受影响区域和未受影响区域，从而受影响区域受到较小最近相邻块的影响，而未受影响区域不受到较小最近相邻块的影响。对于某些应用，受影响区域可在水平方向上和垂直方向上都包括较小最近相邻块尺寸的一半。自身块的所利用部分的受影响区域的加权窗口和较小最近相邻块的加权窗口的对应部分的权重相同，如同从标准相同块尺寸情况导出一样。与自身块的所利用部分的未受影响区域对应的较小最近相邻块的加权窗口的一部分中的权重被“去除”并然后被设置为等于0。自身块的所利用部分的未受影响区域中的权重被增加了(相对于标准相同块尺寸情况)所述从较小最近相邻块的加权窗口的对应部分中去除的权重，这将在下面结合图22的例子进行图示。

由于自身块可具有与其较小最近相邻块不同的运动矢量，所以该收缩方案在运动不连续处降低了平滑性，因为该收缩方案降低了可与较小最近相邻块尺寸兼容的平滑范围。

对于每一自身块，对于每一这样的最近相邻块而重复分析其最近相邻块的相对块尺寸的步骤。根据预定扫描顺序而依次处理这些自身块。

图21A-21C(统称为图21)描绘了根据本发明实施例的结合收缩方案而由OBMC使用的用于自身块和关联较小最近相邻块的加权窗口，其中该最近相邻块是运动块。在图21A中，自身块280是8×8块，而其右相邻块281是4×4块。

图21B提供了分别与图21A的自身块280和右相邻块281相关联的自身块加权窗口280A及其右相邻块加权窗口281A。在图21B中，自身块加权窗口280A包括与右相邻块加权窗口281A结合在OBMC过程中利用的利用部分282A。利用部分282A是自身块加权窗口280A的“收缩”形式，并和右相邻块加权窗口281A具有相同的尺寸。

在图21B中，所示的数值权重不是最终权重，而是用于计算最终权重的标准初始权重。最终权重在图21C中示出。具体来说，图21B中的初始权重是与标准相同块尺寸情况相关的权重。由此，图21B的自身块加权窗口280A中的权重是出现在图18A的加权窗口270C中的相同双线性权重，而图21B的右相邻块加权窗口281A中的权重是出现在图18A的加权窗口271C的右上四分之一圆中的相同双线性权重。

在图21B中，利用部分282A包括受影响区域283A和未受影响区域284A。与受影响区域283A相关的自身块的像素在OBMC过程中受到右相邻块加权窗口281A的影响区域285A的影响。与未受影响区域284A相关的自身块的像素在OBMC过程中不受到右相邻块加权窗口281A的未影响区域286A的影响。

图21C的权重如下所示由图21B中的权重导出。图21C的影响区域285A和受影响区域283A中的权重与图21B所示相同。图21B的未影响区域286A中的权重被添加到图21B的未受影响区域284A中的对应权重上，以形成图21C的未受影响区域284A中的权重，并且图21C的未影响区域286A中的权重被设置为0。

图21中图示的前述收缩方案避免了在运动不连续处的过度平滑。由于大块可具有与其小最近相邻块不同的运动矢量，所以该收缩方案可降低在运动不连续处的过度平滑。该收缩方案可应用到矩形以及上述正方形块尺寸，并由此矩形块尺寸在本发明的范围内。然而，应注意，简单四叉树分解仅可用于生成正方形块阵列。矩形块阵列可通过水平和/或垂直分裂算法而实现(例如将8×8块分裂为两个8×4块或两个4×8块)。

对于前述图21所图示的收缩方案，最近相邻块是特征在于运动矢量的运动块。相反，作为I块的最近相邻块不具有关联运动矢量。然而，如果最近相邻I块不参与OBMC平滑预测，则所述最近相邻I块可利用最近相邻运动块(即缺省块、P块、或反转块)而创建一些块伪影。因此，本发明的反射方案在如上所述OBMC框架中合并了最近相邻I块。

反射方案

如果最近相邻块是I块，则使用反射方案。反射方案将最近相邻I块权重向回反射到自身块上。这实际上意味着使用自身块的运动矢量代替I块的丢失的运动矢量。

图22A-22C(统称为图22)描绘了根据本发明实施例的结合收缩方案由OBMC使用的自身块和关联较小最近相邻块的加权窗口，其中该最近相邻块是I块。在图22A中，自身块290是8×8块，而其右相邻块291是4×4块。

图22B提供了分别与图22A的自身块290和右相邻块291关联的自身块加权窗口290A及其右相邻块加权窗口291A。在图22B中，自身块加权窗口290A包括在OBMC过程中结合右相邻块加权窗口291A利用的利用部分292A。利用部分292A与右相邻块加权窗口291A具有相同的尺寸。

在图22B中，所示的数值权重不是最终权重，而是用于计算最终权重的标准初始权重。最终权重在图22C中示出。具体来说，图22B中的初始权重是与标准相同块尺寸情况相关的权重。由此，图22B的自身块加权窗口290A中的权重是出现在图18A的加权窗口270C中的相同双线性权重，而图22B的右相邻块加权窗口291A中的权重是出现在图18A的加权窗口271C的右上四分之一圆中的相同双线性权重。

图22C的权重如下从图22B的权重中导出。图22B的右相邻块加权窗口291A中的权重被添加到图22B的利用部分292A上，以形成图22C的利用部分292A中的权重，并且图21C的右相邻块加权窗口291A中的权重被设置为0。

本发明的发明人所得出的经验显示：如果最近相邻I块没有被包括在OBMC框架中，则可能存在I块和运动补偿块之间的可见块边界，这可以通过以下事实来解释，运动补偿块被帧内补偿，而I块被帧间内插/预测。在最近相邻I块如前所述被合并到OBMC框架中之后，大部分块边界被消除，并且观察到较小的峰值信号-噪声比(PSNR)增益。

OBMC加权窗口算法

基于关于OBMC的加权窗口的前述讨论，图23是描绘根据本发明实施例的用于计算可变块尺寸OBMC的加权窗口的算法的步骤311-319的流程图。图23的流程图包括上述图11B的流程图的步骤221-222的细节。图23的流程图根据预定扫描顺序依次处理当前帧中的全部自身块。

步骤311跳到到下一自身块，以处理要根据预定扫描顺序扫描的初始第一块。下一自身块相对于其相邻块而被处理，该相邻块包括该下一自身块的最近相邻块。自身块的相邻块(即下一自身块)包括第一相邻块。自身块和第一相邻块可以各自是运动块。自身块和第一相邻块可以各自是I块。自身块可以是运动块，第一相邻块可以是I块。自身块可以是I块，第一相邻块可以是运动块。

对于步骤311中建立的自身块，步骤312跳到下一相邻块，所述下一相邻块初始是步骤311中所建立的自身块周围的最近相邻块序列中的第一相邻块。

步骤313确定相邻块是运动块还是I块。

如果步骤313确定相邻块是运动块，则步骤314执行收缩方案，然后执行步骤316。收缩方案基于相邻块的尺寸等于、还是大于、还是小于上述自身块的尺寸，而生成用于自身块和相邻块的加权窗口。

如果步骤313确定相邻块是I块，则步骤315执行反射方案，然后执行步骤316。反射方案根据上述结合图22的过程，而生成用于自身块和相邻块的加权窗口。

步骤316确定是否存在要处理的自身块的多个相邻块。

如果步骤316确定存在要处理的自身块的多个相邻块，则算法返回到步骤312，以跳到要处理的下一相邻块。

如果步骤316确定不存在要处理的自身块的多个相邻块，则执行步骤317。

步骤317确定自身块是否是I块。如果步骤317确定自身块不是I块，则执行步骤319。如果步骤317确定自身块是I块，则步骤318执行上述结合图17B的辐射方案，以修改自身块及其相邻块的加权窗口，随后执行步骤319。

步骤319确定是否在帧中存在要处理的多个自身块。如果步骤319确定在帧中存在要处理的多个自身块，则算法返回到步骤311，以跳到要处理的下一自身块。如果步骤319确定在帧中不存在要处理的多个自身块，则算法结束。

OBMC的迭代

OBMC允许最近相邻块运动矢量影响自身块中的预测误差，并作出这样的去耦估计次优性(suboptimal)。此外，OBMC指定无因果关系的最近邻域(neighborhood)，使得不存在块扫描顺序，从而对于每一块来说，可在其之前扫描其所有最近相邻块。由此，本发明使用用于优化运动估计和空间内插/预测模式选择的迭代估计或搜索过程，这确保绝对平均失真(MAD)收敛到局部极小。

对于自身块b中的每一像素位置s(其是二维空间矢量)，像素位置s的残余误差r(s)被计算为：

$>>r>>(>s>)>>=>I>>(>s>)>>->>\Sigma >>>v>s>k>>>(>i>)>>\ne >>v>b>k>>>>>h>>lor>2>>>>(>i>)>ver>>I>~>>>(>s>->>v>s>k>>>(>i>)>>)>>->->->>(>2>)>>>s>$

其中指数i完成自身块b的最近相邻块的求和，并且k是迭代指数。在等式(2)中，h_lor2(i)是相邻块i的加权窗口系数(即权重)，其中h₁(i)用作当自身块b是运动块时的加权窗口，并且其中h₂(i)用作当自身块b是I块时的加权窗口。在等式(2)中，v_s(i)是在像素位置s处的相邻块i的运动矢量，并且I(s)是在像素位置s处的真像素值，并且表示相邻块像素的参考帧中的内插值(因为子像素精度而需要)。残余误差图像r(s)是当省略矢量v_b^k并固定所有最近相邻块的运动矢量时导致的运动补偿误差，该矢量v_b^k就是来自自身块b的运动矢量或该块的空间内插/预测。然后，本发明还根据以下等式而进一步优化用于运动块的或进一步优化I块所允许的空间内插模式中的空间内插模式

$>>ver>>v>^>>b>>=>>>arg>min>>v>>>\Sigma >>s>>(>j>)>>\in >>w>b>>>>|>r>>(>s>>(>j>)>>)>>->>h>1>>>(>j>)>>ver>>I>^>>>k>->1>>>>(>s>>(>j>)>>->>v>b>>)>>|>->->->>(>3>)>>>s>$

$>>ver>>m>^>>b>>=>>>arg>min>>m>>>\Sigma >>s>>(>j>)>>\in >>w>b>>>>|>r>>(>s>>(>j>)>>)>>->>h>2>>>(>j>)>>ver>>I>‾>>k>>>(>s>>(>j>)>>)>>|>->->->>(>4>)>>>s>$

其中是条件最佳运动矢量，而是用于块b的条件最佳空间内插/预测模式，是利用来自块b的运动矢量的运动补偿值，而是来自自身块b的最近相邻块的空间内插/预测值。

OBMC迭代受到设计参数α和β的控制：即预定总或最大迭代次数α和每次迭代时用于运动矢量的调整距离β。例如可选择α＝4。例如，可选择运动矢量摄动(perturbation)参数β＝2(对应于沿正交X和Y方向(例如分别为水平和垂直方向)的与一小部分像素单元成比例的运动矢量摄动：-4/8、-2/8、0、+2/8、+4/8)。由于X和Y摄动是独立的，所以β＝2代表在每次迭代中用于总共25个不同方向的运动矢量的沿每一X和Y方向的前面5个摄动。等式(3)和(4)确定25个运动矢量摄动中的哪一个是每一自身块的运动矢量的最佳选择。当每一自身块的最佳运动矢量按照给定迭代次数被这样确定时，所述最佳运动矢量在下一迭代中根据β而被摄动，以确定每一自身块的运动矢量的进一步改进的值。收敛速度很快，但其可根据视频片断而被切断，以降低计算复杂度，导致适当的次优性。

由于对于亮度和色度数据两者运行双向彩色HVSBM，所以可自然地得出以下结论：OBMC迭代可同时应用到YUV。U和V是在RGB数据中的一些变换之后的次采样的帧数据。由此，用于U和V的加权窗口也是用于Y的加权窗口的次采样版本。

基于前面的讨论，本发明的用于OBMC的迭代估计方案(“OBMC迭代”)连续计算当前帧的每一自身块的运动矢量的改进集合达到固定迭代次数(α)或者直到达到收敛标准为止。

图24是描绘了根据本发明实施例的、利用根据图13A、13B、和23的流程图描述的方法论计算的加权窗口、而连续计算根据可变块尺寸OBMC处理的当前帧的自身块的改进的运动矢量的算法的步骤321-326的流程图。所计算的加权窗口构成到OBMC迭代的输入，并在OBMC迭代期间不发生变化。

步骤321提供输入，即α、β、和加权窗口。

步骤322跳到下一迭代，以执行初始的第一迭代。

对于在步骤322建立的迭代，步骤323跳到下一自身块，以处理要根据预定扫描顺序扫描的初始的第一块。

步骤324结合等式(2)利用等式(3)或(4)而确定从基于β摄动的运动矢量中选择的自身块的最佳运动矢量。

步骤325确定在帧中是否存在要处理的多个自身块。如果步骤325确定在帧中存在要处理的多个自身块，则算法返回到步骤323，以跳到下一要处理的自身块。如果步骤325确定在帧中不存在要处理的多个自身块，则接下来执行步骤326。

步骤326确定是否存在要执行的多次迭代。

如果步骤326确定存在要执行的多次迭代，则算法返回到步骤322，以跳到下一迭代。

如果步骤326确定不存在要执行的多次迭代，则算法结束。可能不再存在要执行的多次迭代，因为执行的迭代次数等于α。也可能不再存在要执行的多次迭代，因为已满足了用于更新的运动矢量的预定收敛标准。例如，收敛标准可以尤其是从紧靠之前的迭代到当前迭代的运动矢量的均方分数改变(单独在每一自身块处，或者在所有自身块上求和)小于预定容差。在第一实施例中，在步骤326中仅使用α，以确定是否存在要执行的多次迭代。

在第二实施例中，在步骤326中仅使用收敛标准来确定是否存在要执行的多次迭代。在第三实施例中，在步骤326中使用α和收敛标准两者来确定是否存在要执行的多次迭代。

基于提升的MCTF的变形

本发明在缺省块的提升实现中使用OBMC，即象正常一样利用预测和更新步骤，以降低好运动区域中的噪声。在提升实现中用于OBMC的特定等式如下所示：

$>>H>[>m>,>n>]>=>>1>>2>\; >A>[>m>,>n>]>->>1>>2>\; >>\Sigma >k>>>h>k>>[>m>,>n>]ver>>B>~>>[>>m>f>>->>d>mk>>,>n>->>>b>0>>hk>>]>->->->>(>5>)>>>s>$

$>>L>[>m>->ver>>d>‾>>m>>,>n>->ver>>d>‾>>n>>]>=ver>>H>~>>[>m>->ver>>d>‾>>m>>+>>d>m>>,>n>->ver>>d>‾>>n>>+>>d>n>>]>+>>2>>B>[>m>->ver>>d>‾>>m>>,>n>->ver>>d>‾>>n>>]>->->->>(>6>)>>>s>$

OBMC将运动矢量场(d_m，d_n)视作随机处理。这意味着帧B中的像素B[m，n]具有运动矢量(d_mk，d_nk)以及来自前述其对应概率窗口的概率h_k[m，n]，并且由预测子像素的加权平均值进行补偿。在等式(5)-(6)中，(d_m，d_n)是(d_m，d_n)的最近整数。尽管低时间帧的形式似乎与没有OBMC的形式相同，但是实际上，OBMC不仅影响高时间帧，而且影响低时间帧。来自OBMC的低时间帧实际仍然是优选的，并更适于MCTF的更多级。

计算机系统

图25图示了根据本发明实施例的用于处理与MCTF一起使用的I块和/或用于在运动MCTF可伸缩视频编码器的环境下执行用于可变尺寸块的重叠块运动补偿(OBMC)的计算机系统90。计算机系统90包括处理器91、与该处理器91耦接的输入装置92、与该处理器91耦接的输出装置93、以及各自与该处理器91耦接的存储装置94和95。该输入装置92可以尤其是键盘、鼠标等。输出装置93可以尤其是打印机、绘图仪、计算机屏幕、磁带、内部硬盘或盘阵列、可去除硬盘、软盘、信息网络等。存储装置94和95可以尤其是硬盘、软盘、磁带、例如致密盘(CD)或数字视频盘(DVD)的光储存装置、动态随机存取存储器(DRAM)、只读存储器(ROM)等。存储装置95包括计算机代码97。计算机代码97包括用于处理与MCTF一起使用的I块和/或用于在运动MCTF可伸缩视频编码器的环境下执行用于可变尺寸块的重叠块运动补偿(OBMC)的一种或多种算法。处理器91执行计算机代码97。存储装置94包括输入数据96。输入数据96包括计算机代码97所需要的输入。输出装置93显示来自计算机代码97的输出。存储装置94和95中的任一个或两者(或图25中没有示出的一个或多个附加存储装置)可用作其中嵌入有计算机可读程序代码和/或其中存储有其它数据的计算机可用介质(或计算机可读介质或程序存储装置)，其中该计算机可读程序代码包括计算机代码97。一般来说，计算机系统90的计算机程序产品(或可替换地，制造物品)可包括所述计算机可用介质(或所述程序存储装置)。

尽管图25将计算机系统90示出为硬件和软件的具体配置，但是如本领域技术人员公知的那样，为了结合图25的具体计算机系统90的上述目的，可利用硬件和软件的任意配置。例如，存储装置94和95可以是单一存储装置中的各部分，而不是分离的存储装置。

尽管为了图示的目的而已在这里描述了本发明的实施例，但是许多变形和改变对于本领域技术人员来说将变得显而易见。因此，所附权利要求意欲包括所有这些变形和改变，只要它们落入本发明的真实精神和范围即可。