具有利用快速搜索块匹配的运动估计器的视频编码器

摘要

一种相对至少一个特定参考图片来编码用于图像块的未压缩的视频信号数据的视频编码器(100)，该编码器包括快速搜索块运动估计器(180)，该运动估计器用于提供相应于所述至少一个特定参考图片的运动矢量，该运动估计器包括一个快速搜索块匹配部分，该快速搜索块匹配部分用于执行快速搜索块匹配，同时根据所述图像块像素的归一化相对于所述参考图片像素的归一化的比较来排除非最佳搜索点，所述快速搜索块匹配部分具有响应于所述至少一个特定参考图片的输出；和编码装置，用于编码未压缩的视频信号数据和运动估计器的输出之间的差异。

权利要求

1.一种相对至少一个参考图片来编码用于图像块的未压缩的视频信号数据的视频编码器(100)，该编码器包括快速搜索块匹配运动估计器(180)，该运动估计器用于提供相应于所述图像块和所述至少一个参考图片之间差异的运动矢量，该运动估计器包括一个快速搜索块匹配部分，该快速搜索块匹配部分基于逐次消元的快速搜索块匹配运动估计算法进行块匹配，同时根据所述图像块象素的归一化相对于所述参考图片象素的归一化的比较来排除非最佳搜索点，所述归一化是绝对差或均方误差，所述快速搜索块匹配部分具有响应于所述至少一个参考图片的输出；和编码装置，用于编码未压缩的视频信号数据和至少一个经运动补偿的参考图片之间的差异。

2.如在权利要求1中定义的视频编码器(100)，其中所述快速搜索块匹配部分包括数据重用部分和逐次消元部分中的至少一个。

3.如在权利要求1中定义的视频编码器(100)，其中所述快速搜索块匹配部分包括一个数据重用部分，该数据重用部分适于存储当前图片的归一化、并且当所述当前图片被用作参考图片用于编码另外的图像块时重用所存储的归一化。

4.如在权利要求1中定义的视频编码器(100)，其中所述快速搜索块匹配部分包括一个数据重用部分，该数据重用部分适合于存储最小块尺寸的归一化、并且对于更大的块尺寸重用所存储的归一化。

5.如在权利要求1中定义的视频编码器(100)，其中所述快速搜索块匹配部分包括绝对差计算器以及均方误差计算器中的至少一个以用于执行归一化。

6.如在权利要求1中定义的视频编码器(100)，还包括一个与所述快速搜索块匹配运动估计器(180)进行信号通信的参考图片贮存器(170)，用于提供所述至少一个参考图片和相应的参考图片索引。

7.如在权利要求6中定义的视频编码器(100)，还包括一个与所述参考图片贮存器(170)进行信号通信的可变长度编码器(140)，用于编码相应于该至少一个参考图片的参考图片索引。

8.如在权利要求1中定义的视频编码器(100)，还包括与所述 快速搜索块匹配运动估计器(180)进行信号通信的运动补偿器(190)，用于响应于所述快速搜索块运动估计器而提供经运动补偿的参考图片。

说明书

具有利用快速搜索块匹配的运动估计器的视频编码器

[0001] 对相关申请的交叉引用

[0002] 本申请要求2003年7月15日提交的、序列号为60/487,458的美国临时专利申请的利益，该临时申请的全部内容在此引入作为参考。

[0003] 发明领域

[0004] 本发明总地涉及视频编码器和译码器，并且具体地，是关于视频编码器和译码器中的运动估计算法。

[0005] 发明背景

[0006] 视频数据通常以比特流的形式被处理和传送。典型的视频压缩编码器和译码器(“编译码器”)通过形成对要编码图片的参考图片预测、并且编码当前图片和该预测间的差异，而获得它们的较大的压缩效率。预测与当前图片越相关，则压缩那个图片所需要的比特越少，由此提高了处理的效率。因此，期望形成最佳可能的参考图片预测。 [0007] 在包括运动图像专家组(“MPEG”)-1、MPEG-2和MPEG-4的许多视频压缩标准中，对先前参考图片和当前图片间的运动进行估计以形成先前参考图片的运动补偿版本。先前参考图片的运动补偿版本被用作对当前图片的预测，并且只编码当前图片和该预测间的差异。

[0008] 运动估计在当前的视频编码系统中发挥重要的作用，并且通常是编码器的在计算上最复杂的部分。当前的大多数视频编码标准采用了块匹配算法。逐块地估计运动量的全搜索策略是流行的运动估计方法。不幸的是，全搜索策略的复杂度非常高，尤其是对于采用多参考图片和多块类型的高级视频编码标准，诸如H.264。已经提出了几种快速搜索算法，诸如三步搜索、新三步搜索、钻石搜索、带状搜索、分级搜索、或者多分辨率(multi-resolution)搜索或者它们的组合。这些算法通过减少搜索点的数目来降低复杂度。不幸的是，它们在误差面(error surface)上趋于陷入局部最小。因此，它们的性能通常比全搜索策略要差。

[0009] 大多数当前的视频编码标准采用块运动估计来减小比特率。用于视频编码的块运动估计已经被很好地研究，但对于多参考图片和多块类型选择只有很少几种算法已经被提出，诸如在H.263++以及JVT/H.264/MPEG AVC中的算法。

[0010] 在H.264中，提供了各种模式用于运动补偿。每种运动补偿的宏块模式对应于一个固定尺寸的块。块可以被分割成16×16、16×8、8×16、以及8×8。8×8块可以进一步被再分割成8×4、4×8或4×4的块尺寸。因此，总计支持7种块类型。每个预测编码的m×n块的预测信号是通过位移相应的参考图片区域来得到的，其中所述参考图片区域由来自运动矢量预测器的、差分编码的平移运动矢量来指定。H.264也支持多图片运动补偿的预测。也就是，一个以上的先前编码的图片可被用作为参考以便构建预测编码块的预测信号。因此，对于运动估计，编码器必须决定应当选择哪种块类型以及哪个参考图片。这种多参考图片和多块类型选择使得运动搜索更加复杂。

[0011] 当前，已经提出了全搜索(“FS”)和几种快速搜索算法用于运动搜索，诸如象三步搜索、新三步搜索、钻石搜索、带状搜索以及分级搜索。其中，通常只有全搜索得到了最佳解决方案。因此，需要的是一种用于减小全搜索算法的复杂度同时得到最佳解决方案的方法。

[0012] 发明概述

[0013] 通过在视频编码器和译码器中利用快速搜索块匹配的运动估计的装置和方法，致力于解决现有技术的这些和其它不足和缺点。

[0014] 视频编码器被提供以编码用于图像块的视频信号数据和特定参考图片索引以预测该图像块，其中该编码器包括快速搜索块运动估计器用于提供相应于所述至少一个特定参考图片的运动矢量，该运动估计器包括一个快速搜索块匹配部分，用于执行快速搜索块匹配，同时根据该图像块象素的归一化相对于该参考图片象素的归一化的比较来排除非最佳搜索点，所述快速搜索块匹配部分具有响应于所述至少一个特定参考图片的输出。 [0015] 用于编码图像块的视频信号数据的相应的方法包括：接收基本上未压缩的图像块，与至少一个特定参考图片相对应地块匹配该图像块，同时根据该图像块象素的归一化相对于该参考图片象素的归一化的比较来排除非最佳搜索点，计算相应于该图像块和该至少一个特定参考图片之间差异的运动矢量，并且与所述运动矢量相对应地对该至少一个特定参考图片进行运动补偿。本发明的这些和其它特征、特性和优点将从以下示范实施例的描述中变得清晰，示范实施例要结合附图来理解。

[0016] 附图简述

[0017] 因此通过参考本发明的实施例可以得到：实现并且能够详细理解本发明的上述特性的方式、对以上简要概述的本发明的更具体的描述，其中所述实施例在所附图中图示。 [0018] 然而应当指出，附图仅仅图示了本发明的典型实施例并且因此不应被看作限制它的范围，因为本发明可以承认其它同样有效的实施例。

[0019] 图1示出了根据本发明原理的具有快速搜索块匹配运动估计的视频编码器的框图；

[0020] 图2示出了根据本发明原理的用于编码处理的流程图；

[0021] 图3示出了根据本发明原理的用于译码处理的流程图；以及

[0022] 图4示出了根据本发明原理的用于和快速搜索块匹配运动估计一起使用的视频译码器的框图。

[0023] 优选实施例详述

[0024] 本发明通过使用快速搜索块匹配来执行运动估计。本发明的实施例利用逐次消元法来丢弃非最佳搜索点，并且利用预先计算的数据来节省计算量而不牺牲全搜索方法的最优性。

[0025] 运动估计技术已经得到广泛研究。对于被编码图片的每个运动块，挑选一个代表该运动块距参考图片的位移的运动矢量。在搜索区域内以穷举搜索方法，测试在关于该运动块位置的偏移的预定范围内的每一位移。所述测试包括计算当前图片中运动块内的每个象素与参考图片中位移的运动块之间的绝对差(“SAD”)或均方误差(“MSE”)的和。选择具有最低SAD或MSE的偏移作为运动矢量。已经提出了这种技术上的多种变化，诸如象三步搜索和速率失真优化运动估计。

[0026] 以下的描述仅仅说明本发明的原理。因此应当理解，本领域的技术人员将能够设计出各种安排，它们尽管没有在这里明确地描述或示出，但却体现本发明的原理并且被包括在本发明原理的精神和范围之内。此外，这里陈述的所有例子和条件语言主要打算明确地仅仅用于示教目的，以帮助读者理解本发明的原理和发明人为促进该技术所贡献的概念，并且它们被解释为并不限于这样具体陈述的例子和条件。此外，在这里陈述本发明的原理、特征和实施例及其特定例子的所有表述打算包括其结构和功能上的等价物在内。另外，还打算使这样的等价物包括当前已知的等价物以及将来研发的等价物，即，被研发来执行同样的功能而不考 虑结构的任何元件。

[0027] 因此，例如，本领域的技术人员应当理解这里的框图代表体现本发明原理的说明性电路的概念上的视图。同样，应当理解任何流程图、程序框图、状态转移图、伪代码等等代表各种处理，这些处理可以基本地在计算机可读媒体中表示并且由计算机或处理器来执行，无论这样的计算机或处理器有没有被明确地示出。

[0028] 图中示出的各种元件的功能可以通过使用专用硬件以及能够与适当软件相联合地执行软件的硬件来提供。当由处理器提供时，所述功能可以由单个专用处理器、单个共享处理器、或者多个个体处理器来提供，其中所述个体处理器中的某些可被共享。此外，术语“处理器”或“控制器”的显式使用不应当被解释为专门地指能够执行软件的硬件，还可能隐含地包括，但不限于：数字信号处理器(“DSP”)硬件、用于存储软件的只读存储器(“ROM”)、随机存取存储器(“RAM”)以及非易失性贮存器。也可能包括常规的和/或定制的其它硬件。同样地，图中示出的任何开关只是概念性的。它们的功能可以通过程序逻辑的操作、通过专用逻辑、通过程序控制和专用逻辑的交互作用、或者甚至手工地来实现，随着对上下文的更具体理解，特定的技术可由实施者来选择。

[0029] 在本权利要求中，被表达为用于执行特定功能的装置的任何元件打算包括执行该功能的任何方式，包括例如：a)执行该功能的电路元件的组合，或b)任何形式的软件，因此包括与实施所述软件的适当电路相组合来执行该功能的固件、微码等等。由这样的权利要求定义的本发明具备这样一个事实：由所陈述的各种装置提供的功能性以权利要求所要求的方式被组合和集合。申请人因此把能够提供这些功能性的任何装置看作是在这里示出的这些装置的等价物。

[0030] 快速搜索块匹配运动估计算法可达到与全搜索块匹配相当的质量而同时降低了复杂度。目前公开的逐次消元算法实施例采用基于三角不等式的度量以便及早丢弃非最佳搜索点，并且重用预计算的数据以减少计算的次数。本算法可以被应用于软件和硬件实施例。它还可以被应用于其它启发式的快速搜索算法。

[0031] 如图1中所示，总体地由参考标号100来指示具有快速搜索块匹配运动估计的视频编码器。到编码器100的输入在信号通信中与求和接点110的非反相输入连接。求和接点110的输出在信号通信中与块变换器 120相连接。变换器120在信号通信中与量化器130相连接。量化器130的输出在信号通信中与可变长度编码器(“VLC”)140相连接，其中VLC140的输出是编码器100外部可得的输出。

[0032] 量化器130的输出在信号通信中还被连接到逆量化器150。逆量化器150在信号通信中与逆块变换器160相连接，逆块变换器160进而又在信号通信中与参考图片贮存器170相连接。参考图片贮存器170的第一输出在信号通信中与快速搜索块匹配运动估计器
180的第一输入相连接。到编码器100的输入在信号通信中还与快速搜索块匹配运动估计器180的第二输入相连接。

[0033] 尽管这里描述的本发明是运动估计块的概念性部分，但是应当理解，在替代实施例中独立的快速块搜索部分可向运动估计器部分馈送，所述部分之间的信令指示哪个操作点被测试或者不被测试。快速搜索块匹配运动估计器180的输出在信号通信中与运动补偿器190的第一输入相连接。参考图片贮存器170的第二输出在信号通信中与运动补偿器190的第二输入相连接。运动补偿器190的输出在信号通信中与求和接点110的反相输入相连接。

[0034] 转向图2，总体地由参考标号200来指示对于根据快速搜索块匹配运动估计来编码用于图像块的视频信号数据的示范处理。所述处理包括开始框210，它把控制传递给输入框212。输入框212接收基本未压缩的图像块数据，并且将控制传递给功能框214。功能框214执行快速搜索块匹配同时根据当前图片象素的归一化(例如SAD、MSE)相对于参考图片象素的相同归一化的比较来排除非最佳搜索点。功能框214将控制传递给功能框216，功能框216计算相应于该图像块和特定参考图片之间差异的运动矢量，并且将控制传递给功能框218。功能框218与该运动矢量相对应地对特定参考图片进行运动补偿，并且将控制传递给功能框222。

[0035] 功能框222从基本上未压缩的图像块中减去经运动补偿的参考图片，并且将控制传递给功能框224。功能框224进而又编码具有基本上未压缩的图像块和经运动补偿的参考图片之间的差异、连同特定参考图片的相应索引的信号，并且将控制传递给结束框226。 [0036] 现在转向图3，总体地由参考标号300来指示对于译码用于图像块的视频信号数据的示范处理。所述处理包括开始框310，它把控制传递 给输入框312。输入框312接收图像块压缩数据，并且将控制传递给输入框314。输入框314接收至少一个带有用于该图像块的数据的参考图片索引，每个参考图片索引对应于一个特定的参考图片。输入框314将控制传递给功能框318，功能框318检索相应于每个接收的参考图片索引的参考图片，并且将控制传递给功能框320。功能框320进而又对所检索的参考图片进行运动补偿，并且将控制传递给结束框326。

[0037] 如图4中所示，总体地由参考标号400来指示用于与快速搜索块匹配运动估计一起使用的视频译码器。视频译码器400包括可变长度译码器(“VLD”)410，它在信号通信中与逆量化器420相连接。逆量化器420在信号通信中与逆变换器430相连接。逆变换器430在信号通信中与加法器或求和接点440的第一输入端子相连接，其中求和接点440的输出提供视频译码器400的输出。求和接点440的输出在信号通信中与参考图片贮存器450相连接。参考图片贮存器450在信号通信中与运动补偿器460相连接，运动补偿器460在信号通信中与求和接点440的第二输入端子相连接。

[0038] 在操作中，全搜索可以首先将当前图片划分成无重叠的块，并且在参考图片中搜索它们中的每一块。通过测试搜索中心周围的搜索区域内的所有点来执行全搜索，并且找到具有最小成本函数的最终位置。尽管全搜索方法达到了最优的解决方案，但是它需要较高的计算成本。在视频编码方法中，如果搜索范围是S，参考图片的数目为RN(在H.26L中，RN可以高达15)，宏块(通常16×16)中的块类型的数目为BN(在H.26L中，BN可以高达2
7)，那么对于每个宏块，搜索点的总数目为(2S+1)*(2S+1)*BN*RN，或者多于4S*BN*RN个搜索点。

[0039] 结合本发明的实施例利用了两种技术来提高全搜索方法的计算速度。一种是数据重用，而另一种是逐次消元。对于数据重用，最小尺寸块类型(4×4)的绝对差(“SAD”)和的结果被存储以便由更大尺寸的块类型重用。因此，对于每个宏块，等价于搜索点的所需要2
的计算大约是4S*RN。

[0040] 一种称为三角不等式的数学不等式被用来在逐次消元算法(“SEA”)中加速全搜索。在块匹配中，例如，绝对差(“SAD”)的和或者方差(“SSD”)的和，可被用作搜索准则，以测定来自参考图片的运动补偿预测c[x，y]与当前图片中原始信号s[x，y]之间的失真。集合B包括所考虑的块的所 有采样位置。

[0041] 假设B被分割成子区域Bn，以使得：

[0042] 并且

[0043] 那么

[0044]

[0045] 把三角不等式应用于所有的Bn，推出：

[0046]

[0047]

[0048] 在以上的公式中，对于SAD有p＝1而对于SSD有p＝2。

[0049] 可以采用SAD或SSD作为视频编译码器中的失真量度。不失一般性地，SAD被用在以下示范讨论中并且等式(2)被明确地写成等式(3)。等式(3)可以通过去除某些绝对值算子而被简化，因为可以假设视频象素数据值总是正的。

[0050]

[0051] SEA被描述如下：

[0052] 假设Dmin是在块运动搜索中先前计算出的最小失真值；

[0053] 那么如果 (4)，则丢弃块c；

[0054] 否则，执行全搜索。

[0055] 计算 (等式(3)的右手侧)的开销可以被划分成两个部分。第一部分涉及到计算和范数(sum norm) 及 第二部分涉及到计算等式(3)中和范数的绝对差的和，它取决于子区域的尺寸。对于多块类型运动估计，对称分割是优选的。如果子
2
区域是4×4的，则对于一个宏块，开销等于大约S/4*BN*RN个搜索点。如果子区域是2×2
2
的，则开销是大约S*BN*RN。存储和范数所需要的存储器是大约(RN+1)*图片尺寸。SEA的效率依赖于下界能够有多严格。为了补偿开销的影响并且减少全搜索的点，Dmin的初始确定以及搜索顺序是重要的。

[0056] 在优选实施例中，对于SEA，应用数据重用来减小计算 (等式(3)的右手侧)的开销。 的计算可以被分割成两个部分。第一部分涉及到计算和范数及 第二部分涉及到计算等式(3)中和范数的绝对差的和。

[0057] 更详细地，为了计算 对经运动补偿的参考图片的和范数 以及当前图片的和范数 进行计算。 的计算可以被存储并且被重用于参考图片
中不同的候选运动矢量偏移。当视频序列中后面的图片被编码时，当前图片可以被用作后一图片的参考图片。这里，当前图片的和范数的计算结果可以被存储，并且在当前图片被用作参考图片来编码另一个相关的图片时重用作 。这样，在本发明的目前的实施例中计算和范数的开销被减小RN倍。

[0058] 此外，对于运动估计，用于 的和范数的绝对差的和在等式(3)中被计算以用于不同的块类型。对于最小块尺寸的和范数的绝对差的计算结果被存储并且被更大的块类型重用。因此，计算和范数的绝对差的开销可以被减小BN倍。

[0059] 现在提供一种被称为新SEA(“NSEA”)的新准则来在SEA中使用以丢弃除了(4)以外的非最佳点。在SEA中，由于三角不等式，仅有的被丢弃的点是那些在数学上不可能具有最低SAD的点，因此当使用全搜索方法时总是选择相同的运动矢量。在NSEA中，不再拥有这样的保证，并且作为结果的运动矢量可不同于全搜索方法，从而增加了被压缩序列的比特率。由于 与D(s，c)高度相关，因此比特率的增加可能是微小的。然而，对于NSEA，在搜索中要丢弃的点的数目可以被显著地减少，从而极大地降低了视频编码器复杂度。 [0060] NSEA被描述如下：

[0061] 假设Dmin是在块运动搜索中先前计算出的最小失真值；

[0062] 那么如果 (5)，则丢弃块c；

[0063] 否则，执行全搜索。

[0064] 在(5)中，因子α和β可以被动态地调整，因此可以选择更严格的下界，这可以进一步扔掉非最佳搜索点而不进行全搜索。在某些情况下， 速率约束的失真可以被利用来进一步提高编码效率，即，

[0065] J(s，c)＝D(s，c)+λmotionRmotion+λrefRref，(6)

[0066] 其中Rmotion和Rref分别是用于编码运动矢量和参考图片的比特，而λmotion和λref被用来平衡速率和失真以便可以达到全局最优。(6)中的速率约束的失真是速率失真最优化的一种方式，它能够极大地提高编码效率。

[0067] 这样(5)中的SEA算法因此被改变：

[0068] 假设Jmin是在块运动搜索中先前计算出的最小速率约束失真值； [0069] 那么如果J(s，c)≥Jmin＝αDmin+β+λmotionRmotion+λrefRref(7)，则丢弃块c； [0070] 否则，执行全搜索。

[0071] 该算法可以通过利用更好的初始Dmin/Jmin以及搜索顺序来进一步提高。这样的实施例的过程如下：

[0072] 对于每个预测的图片，

[0073] 计算等式(3)中的用于当前图片的和范数

[0074] 定义预测者集合P；

[0075] 在集合P中检查D(s，c)/J(s，c)，找到最小值作为初始Dmin/Jmin； [0076] 调整搜索中心及搜索范围以包括达到步骤3中的初始Dmin/Jmin的最佳预测者； [0077] 应用(5)/(7)中描述的NSEA算法，其中带有数据重用用于运动补偿编码； [0078] 计算并存储用于重建的图片的新的和范数为

[0079] 本发明不受限于所述示范快速搜索算法实施例。替代实施例可以直接应用于本领域已知的其它启发式的快速搜索算法。因为和范数的计算是代价较低的，并且结果可以被重用，因此 可以被用于其它应用。例如，在如H.264中的运动估计中，一种选择参考图片用于运动补偿而不损失太多质量的快速方法是优选的。由于 与D(s，c)之间高度相关，所以 可在这里被用作选择哪个参考图片来用于运动补偿的度量。此外，运动搜索的速度还依赖于搜索顺序。可以基于 的提高的质量来定义新的搜索顺序。因此，如果在某个点 则不 需要查看后续的搜索点。

[0080] 本发明实施例的计算上的节省可以被应用到其它应用上，诸如象扩展搜索范围或者为其它用途适配更好的算法。本发明的实施例可以直接与采用运动估计的许多不同的视频压缩标准一起使用，这些视频压缩标准诸如象H.261、H.263、H.264、MPEG-1、MPEG-2以及MPEG-4。

[0081] 本发明的这些和其它特性及优点可以被相关领域的普通技术人员基于这里的教导而容易地弄清。应当理解，本发明的教导可以以硬件、软件、固件、专用处理器或者其组合的各种形式来实现。

[0082] 根据一个示范实施例，本发明可以被实现为硬件和软件的组合。此外，软件优选地被实现为有形地具体化为在程序贮存器单元上的应用程序。该应用程序可以被上传到包括任何适当结构的机器上并且由其执行。优选地，该机器被实现在具有硬件的计算机平台上，所述硬件诸如是一个或多个中央处理器单元(“CPU”)、随机存取存储器(“RAM”)以及输入/输出(“I/O”)接口。该计算机平台也可以包括操作系统和微指令代码。在这里描述的各种处理和功能可以是能由CPU执行的微指令代码的一部分或者应用程序的一部分，或者它们的任意组合。此外，其它各种外围单元可以被连接到该计算机平台，诸如附加的数据贮存器单元和打印单元。

[0083] 还应当理解，由于在附图中描绘的某些组成系统元件和方法优选地以软件方式来实现，因此该系统元件或该处理功能块之间的实际连接可能不同，这取决于本发明被规划的方式。这里给出教导，相关领域的普通技术人员将能够设想本发明的这些和类似的实现或者配置。

[0084] 尽管这里参考附图描述了说明性的实施例，但是应当理解，本发明不限于这些精确的实施例，并且相关领域的普通技术人员可以在其中实行各种变化和修改而不脱离本发明的范围或精神。打算将所有这样的变化和修改包括在所附权利要求中提出的本发明的范围内。