运动矢量搜索方法和装置，其程序和记录有程序的记录介质

摘要

本发明提供一种在进行运动补偿预测的视频图像编码中使用的运动矢量搜索方法，其中，对与编码对象块相关的预先搜索到的运动矢量进行输入，对上述编码对象块的运动矢量的产生码量成为最小的开销成本最小的运动矢量进行计算，根据上述输入的运动矢量和上述计算出的开销成本最小的运动矢量限定搜索区域，通过仅对所述限定的搜索区域进行搜索，从而搜索运动矢量。也可以根据已完成编码的附近块的运动矢量计算编码对象块的预测矢量，将该计算出的预测矢量作为开销成本最小的运动矢量。

说明书

技术领域

本发明涉及在进行运动补偿预测的视频图像编码中使用的运动矢量搜索方法及其装置，和用于实现该运动矢量搜索方法的运动矢量搜索程序及记录有该程序的计算机能够读取的记录介质。

本发明基于2007年3月14日提出的日本专利申请特愿2007-064286号主张优先权，在此引用其内容。

背景技术

在进行运动补偿预测的视频图像编码方式中，需要对运动矢量进行搜索。在运动矢量的搜索中，在预测误差功率最小的位置编码效率并不一定最大。这是因为，实际的编码信息除了传送预测误差信号外，还传送运动矢量等信息。

因此，进行将运动矢量的产生码量作为开销成本(overhead cost)加以考虑的运动矢量搜索。在H.264的参照软件中，在选择预测模式时，使用

Cost＝D+λ·R

这样的成本函数(例如，参照非专利文献1)。

此处，D表示预测误差功率，R表示正交变换系数以外的产生码量，λ是由量化步长(quantization step size)决定的常数。

利用这样的方法，能够对考虑了运动矢量的产生码量的最小成本的运动矢量进行搜索。

运动矢量的产生码量根据视频图像编码方式而不同。

例如，在MPEG-2中，原则上将左邻的块的运动矢量作为预测矢量对差分进行编码(例如，参照非专利文献2)。

此外，在H.264中，将附近的3个块的运动矢量的中值(median)作为预测矢量进行编码(例如，参照非专利文献3)。

这样，在运动矢量的成本不同的视频图像编码方式间挪用运动矢量的情况下，利用前级的视频图像编码方式搜索到的运动矢量在后级的视频图像编码方式中不一定成本最小。

作为在后级利用前级的运动矢量(以下，称为原运动矢量)的例子，能够考虑如图8A和8B所示，进行“挪用其它的运动搜索方法的视频图像编码处理”，或如图9A和9B所示，进行“再编码处理”。

前者是挪用其它的视频图像编码方式的运动搜索部分等构成编码装置的情况，后者是针对已完成编码的位流(bit stream)，为了变更视频图像编码方式、比特率等而进行再编码的情况。

特别是，在进行再编码时，再利用包含在原来的位流中的运动矢量，能够削减再编码时的运动搜索所耗费的运算成本。例如，在下述的专利文献1所记载的发明中，以原运动矢量为搜索开始点，进行再搜索。

因为在任一个例子中，均仅直接利用原运动矢量，不能保证在后级的编码部为最小成本，所以与在宽范围内进行再搜索的情况相比编码效率降低。

特别是，在进行再编码时，搜索原运动矢量的视频图像信号是原信号，与此相对，在后级输入原来的位流的解码信号，因此视频图像信号不同。因此，编码效率降低的可能性高。

因此，通常进行在后级侧的运算成本容许的范围内仅对原运动矢量的周边进行再搜索的方法。利用该方法，因为能够限定搜索范围，部分地进行再搜索，所以能够抑制编码效率的降低。

图10是表示该再搜索的流程图。

此处，因为将运动矢量的产生码量作为开销成本加以考虑，所以在再搜索前计算预测矢量，但是对于运动矢量的再搜索，与预测矢量无关地仅对原运动矢量的周边进行再搜索。

利用这样的方法，能够抑制后级的再搜索的运算成本，并且能够抑制编码效率的下降。

非专利文献1：国际互联网<URL：http://inhome.hhi.de/suehring/tml/download/>

非专利文献2：ISO/IEC-13818-2，“Information technology-Genericcoding of moving pictures and associated audio information：Video”，pp.77-85，May，1996

非专利文献3：ITU-T H.264 ITU-T Rec.H.264，“Advanced videocoding for generic audiovisual services”，pp.146-149，March，2005

专利文献1：日本专利申请特开2000-244921号公报

但是，在搜索原运动矢量时使用的成本函数与后级的视频图像编码方式的成本函数不同的情况下，并不一定在原运动矢量附近存在最佳的运动矢量。

图11表示其一个例子。在该例子中，表示与在后级的再搜索范围内(原运动矢量附近的再搜索范围内)成为最小成本的运动矢量相比，在该再搜索范围外还存在成本更小的运动矢量。

这是由于在进行前级的运动搜索时，未考虑后级的预测矢量而引起的。此外，在进行再编码时，因为输入视频图像也不同，所以存在该偏差扩大的可能性。

这样，在搜索原运动矢量的前级和对运动矢量进行再搜索的后级，在进行搜索时的成本函数、视频图像信号不同的情况下，存在编码效率下降的可能性。为了解决该问题，必须扩大再搜索范围，但是在此情况下，存在后级的运算成本增加的问题。

发明内容

本发明是鉴于上述问题而完成的，其目的在于提供一种新的运动矢量搜索技术，在利用以前级的视频图像编码方式求得的原运动矢量，以后级的视频图像编码方式搜索运动矢量的情况下，能够抑制编码效率的下降，并且能够削减运算成本。

为了达到该目的，本发明的运动矢量搜索装置构成为在进行运动补偿预测的视频图像编码中被使用时，具备：(1)输入单元，对与编码对象块相关的预先搜索到的运动矢量进行输入；(2)计算单元，对编码对象块的运动矢量的产生码量成为最小的开销成本最小的运动矢量进行计算；(3)限定单元，基于输入单元所输入的运动矢量、和计算单元所计算出的开销成本最小的运动矢量，限定搜索区域；和(4)搜索单元，通过仅对限定单元所限定的搜索区域进行搜索而搜索运动矢量。

通过以上的各处理单元工作而实现的本发明的运动矢量搜索方法利用计算机程序也能够实现，该计算机程序记录在适当的计算机能够读取的记录介质中并被提供，或通过网络被提供，在实施本发明时被安装，通过在CPU等控制单元上工作而实现本发明。

在这样构成的本发明的运动矢量搜索装置中，在搜索运动矢量时，对以前级的视频图像编码方式搜索到的运动矢量(上述的原运动矢量)进行输入。

接着，对编码对象块的运动矢量的产生码量成成为最小的开销成本最小的运动矢量进行计算。

例如，根据已完成编码的附近块的运动矢量计算编码对象块的预测矢量，将该计算出的预测矢量作为开销成本最小的运动矢量。

接着，确定被输入的运动矢量和计算出的开销成本最小的运动矢量夹着的区域，将该确定后的区域作为搜索区域进行限定。

例如，对将连接输入的运动矢量和计算出的开销成本最小的运动矢量的直线作为直径的圆内的区域进行确定，将该确定后的区域作为搜索区域进行限定。

或者，对连接输入的运动矢量和计算出的开销成本最小的运动矢量的直线上的区域进行确定，将该确定后的区域作为搜索区域进行限定。

或者，将连接输入的运动矢量和计算出的开销成本最小的运动矢量的直线作为长方形的一边，将具有预先设定的长度、且在该直线的中点位置交叉正交的直线作为长方形的另一边，确定该长方形内的区域，将该确定后的区域作为搜索区域进行限定。

或者，将输入的运动矢量和计算出的开销成本最小的运动矢量作为焦点，确定与各焦点的距离之和为预先设定的固定值的椭圆内的区域，将该确定后的区域作为搜索区域进行限定。

接着，典型的是，从限定后的搜索区域抽出搜索点，通过仅对该抽出的搜索点进行再搜索而搜索运动矢量。

发明的效果

这样，在本发明中，在利用以前级的视频图像编码方式求得的原运动矢量，以后级的视频图像编码方式搜索运动矢量的情况下，考虑由于存在进行搜索时的成本函数、视频图像信号不同的情况，而使得最佳的运动矢量不一定存在于原运动矢量附近，不是仅对原运动矢量的周边进行再搜索，而是以包括原运动矢量和在后级的开销成本最小点的方式限定搜索区域。

从而，因为根据本发明，能够抑制编码效率的下降，并且还能够抑制搜索点数，所以能够削减运算成本。

附图说明

图1是基于本发明的工作的流程图。

图2A是本发明限定的再搜索范围的说明图。

图2B同样是本发明限定的再搜索范围的说明图。

图2C同样是本发明限定的再搜索范围的说明图。

图2D同样是本发明限定的再搜索范围的说明图。

图3是本发明的视频图像编码装置的装置结构例。

图4是该视频图像编码装置的内部结构例。

图5是图形参数存储部的数据构造的说明图。

图6是同视频图像编码装置执行的流程图的一例。

图7同样是同视频图像编码装置执行的流程图的一例。

图8A是在后级利用前级的运动矢量的视频图像编码处理的一例的说明图。

图8B同样是上述一例的说明图。

图9A是在后级利用前级的运动矢量的视频图像编码处理的另一例的说明图。

图9B同样是上述另一例的说明图。

图10是现有技术的流程图。

图11是现有技术的问题的说明图。

符号的说明

1  视频图像编码装置

10  运动搜索部

20  再搜索范围限定部

200  预测矢量输入部

201  原运动矢量输入部

202  图形种类信息输入部

203  再搜索范围设定部

204  图形参数存储部

具体实施方式

接着，根据实施方式对本发明进行说明。

在利用以前级的视频图像编码方式求得的原运动矢量，以后级的视频图像编码方式搜索运动矢量的情况下的现有技术的问题，起因于仅在原运动矢量的附近搜索运动矢量。

另一方面，关于运动矢量信息，根据附近的已完成编码的块的运动矢量计算编码对象块的预测矢量，对该运动矢量和该预测矢量的差分进行编码，在差分为0时运动矢量的码量变得最小。即，此情况下的预测矢量成为使开销成本最小的运动矢量。

由此，如果能够以有限的搜索点数对原运动矢量附近和预测矢量附近进行搜索，则能够解决现有技术的问题，从而能够抑制编码效率的下降，并能够削减运算成本。

因此，在本发明中采用如下结构，即，使用原运动矢量、和作为使后级的视频图像编码方式下的运动矢量的产生码量(开销成本)为最小的点的预测矢量这2点，限定后级的视频图像编码方式下的再搜索范围(再搜索区域)。

图1表示作为本发明的工作的1例的流程图。

如该流程图所示，首先，最初在步骤S101输入原运动矢量。即，输入利用前级的视频图像编码方式求得的原运动矢量。

接着，在步骤S102，根据附近的已完成编码的块的运动矢量计算编码对象块的预测矢量。

此处，预测矢量的计算方法根据视频图像编码方式而不同。此外，已完成编码的块不具有帧内编码模式等运动矢量的情况下的处理，也按照各视频图像编码方式的预测矢量的生成方法决定。

接着，在步骤S103，根据原运动矢量和预测矢量限定再搜索范围。

接着，在步骤S104，从已限定的再搜索范围抽出表示该搜索范围的图形中包括的搜索点。

例如，如果再搜索范围是圆形，则抽出包括在该圆中的所有的搜索点，将其作为再搜索范围。如果使包括在该再搜索范围中的搜索点数与现有方法的再搜索点数一致，则后级的运动搜索部的运算成本变为同等。如果将搜索点数削减得比现有方法少，则实现运算成本的削减。

接着，在步骤S105，通过对抽出的再搜索点进行再搜索而决定运动矢量。

接着，对根据原运动矢量和预测矢量进行的再搜索范围的限定方法进行说明。

在限定(设定)再搜索范围时，优选以包括作为使开销成本为最小的运动矢量的预测矢量的方式进行设定。

图2A～2D表示再搜索范围的设定例。在该例中，将圆形、椭圆形、长方形、线段作为再搜索范围。以下，对再搜索范围的限定方法进行说明。

[1]圆形

例如，如图2A所示，描绘将连接原运动矢量和预测矢量的线段作为直径的圆。将包括在该圆的内侧的搜索点作为再搜索范围。

[2]椭圆形

例如，如图2B所示，描绘将原运动矢量和预测矢量作为焦点的椭圆。与各焦点的距离的和作为常数被预先设定。将包括在该椭圆的内侧的搜索点作为再搜索范围。

[3]长方形

例如，如图2C所示，描绘将原运动矢量和预测矢量的距离作为长边的长方形。短边的长度作为常数被预先设定。将包括在该长方形的内侧的搜索点作为再搜索范围。

[4]线段

例如，如图2D所示，描绘连接原运动矢量和预测矢量的线段。将该线段上的搜索点作为再搜索范围。

这些再搜索范围的限定方法是一个例子。这样，再搜索范围主要根据原运动矢量和预测矢量进行限定。

此外，在具有多个运动补偿块大小的视频图像编码方式中，因为根据块大小，运动矢量的条数变化，所以存在最大块大小总成为最小开销成本的可能性。在此情况下，按每个块大小，计算出开销成本最小的运动矢量即可。

例如，在存在16×16大小和8×8大小的2种块大小的情况下，以各个大小求取开销成本最小的运动矢量，限定再搜索范围。

利用这种方法，根据本发明，在利用以前级的视频图像编码方式求得的原运动矢量，以后级的视频图像编码方式搜索运动矢量的情况下，不增加再搜索点数就能够对预测矢量附近进行搜索，由此，能够抑制编码效率的下降，并且能够削减运算成本。

实施例

以下，根据具体的实施例对本发明进行说明。

图3是表示应用本发明的视频图像编码装置的装置结构例的图。

如该图所示，本视频图像编码装置1用于进行如下处理，即生成视频图像信号的预测信号，求取视频图像信号与其预测信号的差分值，通过对其进行量化并编码而生成编码位流并加以输出这样的处理，且该视频图像编码装置1具有根据附近的已完成编码的块的运动矢量计算编码对象块的预测矢量的功能，该视频图像编码装置1具备：进行运动矢量的搜索的运动搜索部10，还具备：再搜索范围限定部20，该再搜索范围限定部20输入以前级的视频图像编码方式求得的原运动矢量和运动搜索部10计算出的预测矢量，对运动搜索部10指示运动矢量的再搜索范围(再搜索区域)。

图4表示为了实现本实施例的运动矢量搜索处理，视频图像编码装置1具备的再搜索范围限定部20所采用的结构的一例。

如该图所示，在搜索范围限定部20具备：预测矢量输入部200、原运动矢量输入部201、图形种类信息输入部202、再搜索范围设定部203、和图形参数存储部204。

预测矢量输入部200对运动搜索部10计算出的预测矢量进行输入。

原运动矢量输入部201输入以前级的视频图像编码方式求得的原运动矢量。

图形种类信息输入部202输入是预先设定的圆形、还是椭圆形、还是长方形、还是线段这样的再搜索范围的图形类别的信息。

再搜索范围设定部203根据预测矢量输入部200输入的预测矢量、原运动矢量输入部201输入的原运动矢量、和图形种类信息输入部202输入的图形种类信息，设定运动矢量的再搜索范围，并通知给运动搜索部10。

图形参数存储部204具有图5所示那样的数据结构，对再搜索范围设定部203设定再搜索范围时所需的图形参数的信息进行存储。

例如，如利用图2B所说明的那样，关于椭圆的图形类别，因为设定再搜索范围需要关于与2个焦点的距离之和的设定值，所以存储该设定值的信息。

此外，如利用图2C所说明的那样，关于长方形的图形类别，因为设定再搜索范围需要关于另一边的长度的设定值，所以存储该设定值的信息。

在本实施例中，将利用其它视频图像编码方式进行编码而得到的位流的再编码作为前提，被输入的原运动矢量利用从原来的位流取出的运动矢量。

此外，预测矢量根据附近的3个块的运动矢量进行计算。

此外，假定原来的位流在后级的编码处理之前已完成解码，还保存有运动矢量。

图6表示如图4那样构成的视频图像编码装置1执行的流程图的一例。

接着，根据该流程图，对视频图像编码装置1执行的运动矢量搜索处理进行详细的说明。

在视频图像编码装置1中，如图6的流程图所示，首先，最开始在步骤S201输入预先设定的再搜索范围的图形种类信息。

接着，在步骤S202，在图形参数存储部204中存储有输入的图形种类信息所指的参数的情况下将其读出。

此外，在图形种类信息相对于整个视频图像序列已被设定的情况下，关于步骤S201、202的处理，相对于该视频图像序列仅执行一次即可。

接着，在步骤S203，通过从原来的位流取出运动矢量，输入针对编码对象块求得的原运动矢量。

接着，在步骤S204，根据附近的已完成编码的块的运动矢量计算编码对象块的预测矢量。

例如，在将编码对象块的附近的3个块(A、B、C)的运动矢量(<MVA>、<MVB>、<MVC>)的中央值作为预测矢量进行计算的情况下，按照

PMV_x＝Median(MVA_x，MVB_x，MVC_x)

PMV_y＝Median(MVA_y，MVB_y，MVC_y)

这样的数学式，计算预测矢量<PMV>。此处，“<......>”是表示矢量的符号。

接着，在步骤S205，根据输入的图形种类信息、输入的原运动矢量、计算出的预测矢量、和从图形参数存储部204读出的参数，以图2A～2D所示的那样的形状限定运动矢量的再搜索范围，从该限定的再搜索范围抽出搜索点，对运动矢量进行搜索。

接着，根据图7所示的流程图，以作为再搜索范围的图形类别指定线段的情况为具体例，对在图6的流程图的步骤S205执行的处理进行详细的说明。

此处，在该流程图中，假定：搜索点设定为整数像素精度，从原运动矢量起在水平或垂直方向上1像素1像素地在线段上进行搜索，将预测矢量的位置作为终点。

即，在作为再搜索范围的图形类别指定线段的情况下，当进入步骤S205的处理时，如图7的流程图所示的那样，首先，最开始在步骤S301进行利用原运动矢量进行初始化的处理，设定输入的原运动矢量<MVO>作为初始运动矢量，并且代入原运动矢量<MVO>的成本作为最小成本。

接着，在步骤S302，计算连接原运动矢量<MVO>和预测矢量<PMV>的线段y＝αx+β。

即，根据

α＝(PMV_y-MVO_y)/(PMV_x-MVO_x)

β＝MVO_y-α·MVO_x

这样的数学式计算线段的倾斜度α和截距β。其中，除去PMV_x＝MVO_x的情况。

接着，在步骤S303，如果计算出的倾斜度的绝对值|α|为1以上，则使垂直成分一个一个地变化，如果不满1，则使水平成分一个一个变化。然后，通过根据变化后的水平或垂直成分，使用线段的数学式计算另一方的成分，从而计算设定在线段y＝αx+β上的搜索位置。其中，在PMV_x＝MVO_x的情况下仅使垂直成分变化。

接着，在步骤S304，计算在搜索位置的成本，在接着的步骤S305与当前时刻的最小成本进行比较。

根据该比较处理，在判断计算出的成本不足当前时刻的最小成本时，进入步骤S306，根据本次的成本和运动矢量，替换最小成本和运动矢量。

接着，在步骤S307，确认搜索位置是否与预测矢量一致，在确认不一致的情况下，返回至步骤S303的处理；在确认一致的情况下，结束处理。

此处，在图7的流程图中，虽然将原运动矢量作为起点，将预测矢量作为终点，但是搜索的顺序是任意的。例如，在搜索范围的两端和中央位置的3点进行成本的比较，也能够削减搜索点数。

在使用该方法的情况下，例如，首先，对原运动矢量、预测矢量和两矢量的中点这3个位置进行比较，抽出成本低的2点。但是，在两端成为低成本的点的情况下，抽出最低成本的点和中点的2点。接着，求取该2点间的中点，同样地以3点进行比较。反复进行该处理，直至变得不能计算出中点。

此外，也能够从成本小的位置开始搜索。

在图7的流程图中，假定作为再搜索范围的图形类别指定线段的情况，对在图6的流程图的步骤S205执行的处理进行了说明，但是在作为再搜索范围的图形类别指定线段以外的图形的情况下，也执行同样的处理。

即，从以图2A～2C所示的形状限定的再搜索范围之中依次选择搜索位置，计算其成本，在判断不足当前时刻的最小成本时，通过根据此次的成本和运动矢量反复替换最小成本和运动矢量，搜索成为成本最小的运动矢量。

这样，在本发明中，在进行再编码时，根据原来的位流的运动矢量和预测矢量，能够限定在后级的运动搜索的搜索范围。

虽然根据图示的实施例对本发明进行了说明，但是本发明不限于此。例如，在实施例中，公开了通过具备图形种类信息输入部202，使得能够从外部指定再搜索范围的图形类别这样的结构，但是也可以采用如下结构，即，不具备图形种类信息输入部202，将再搜索范围的图形类别决定为预先规定的图形类别。

此外，在实施例中，令原来的位流已完成解码，但是也能够进行逐次解码处理。此外，在实施例中，虽然进行再编码处理，但是如果能够输入原运动矢量和视频图像信号，则因为能够进行在后级的编码处理，所以也能够进行将前级作为运动搜索部的视频图像信号的编码处理。

产业上的可利用性

根据本发明，因为能够抑制编码效率的下降，并且还能够抑制搜索点数，所以能够削减运算成本。