基于距离加权搜寻顺序以估算移动向量的方法

摘要

本发明公开了一种基于距离加权搜寻顺序以估算移动向量的方法，是参考一第一画面所具有的一预定像块，并搜寻邻近的一第二画面中对应预定像块相匹配的像块以估算预定像块的移动向量，其特征在于：所述方法于第二画面中是依一预定原则选择一像块为一起始点，并以距离加权方式向外扩展搜寻与预定像块相匹配的像块以估算预定像块的移动向量，有鉴于移动向量常是以放射状分布的方式出现，依据距离加权顺序搜寻可节省不必要的搜寻时间。

说明书

技术领域

本发明是有关于一种视讯编码的动态估计的方法，特别是涉及一种以距离加权(Distance Weighted)顺序进行移动估算(Motion Estimation)的方法。

背景技术

如图1所示，目前在MPEG视讯编码影像的数据流(Data stream)中，其数据结构皆是由一个或一个以上的序列(Sequence)所构成，而在每个序列之中则包含了多数个图像群组(Group of Picture，GOP)，而所谓的图像群组指的是由许多画面(Frame)或称为图像(Picture)所构成的群组，画面依其属性可区分幅内编码画面(I Frame)、预测编码画面(P Frame)，以及双向编码画面(B Frame)影像三种型态。

上述每一种画面均可加以编码，一般是以幅内编码(I)画面作为起始影像压缩的切入点，借由移动向量(Motion Vector)的估算，预测编码(P)画面可以幅内编码(I)画面或预测编码(P)画面作为参考画面来进行预测，而双向编码(B)画面则是以幅内编码(I)画面与预测编码(P)画面二者或两预测编码(P)画面作为参考画面所产生的移动向量推估，如此将画面连续播放后，呈现在使用者面前即为动态的MPEG视讯影像。

而在MPEG的压缩标准中，除需进行移动向量的估算外，尚有所谓的移动补偿(Motion Compensation)，一般移动补偿最直接的作法，便是纪录每一画素的亮度及彩度，并以全找搜寻(Full Search)方式纪录两者变化，但是此举将耗费大量资源，因此，现行的做法是将每个画面细分为数个像条(Slice)，像条中又可再分为数个巨块(MacroBlock，MB)，而巨块可由四个亮度(Luminance)像块及数个彩度(Chrominance)像块所组成，最后将每一像块(Block)定义为MPEG的数据结构中的最小编码单位。

配合移动向量的估算以及移动补偿技术，目前画面便可借由具有的各像块以及从先前画面找出最佳匹配像块，以计算出的移动向量与差值资料将先前画面的像块加以调整而成为目前画面，依据移动向量可将像块转移至适当位置，差值数据则可提供亮度、彩度及饱和值的变化，由于无须纪录大部分的重复资料，因此可节省储存的数据量达到数据压缩的目的。

如图2所示，上述从先前画面找出最佳匹配像块的方式，以目前的一种三步搜寻(Three Step Search；TSS)判断方式为例，首先以一欲搜寻的搜寻区域21的中心定义为起始点210，而以其外部8点作为检查点，假设搜寻区域21的搜寻区域大小为4×4，且找到搜寻区域21右下方具有的检查点20为相似，则以检查点20为中心，再缩小搜寻区域22的搜寻区域大小为2×2，最后找到搜寻区域22右上方具有最相似的检查点220后，即可依此定义出移动向量值。

现有一种钻石搜寻(Diamond Shape Search；DSS)判断方式，则是以一菱形(Rhombus)的外框作为搜寻区域，其步骤说明如下：

步骤1：找寻一搜寻起始点及以起始点为中心的空心菱形外框共九点，若最相似点在菱形中心则进行步骤4，若最相似点在菱形外框则进行步骤2。

步骤2：以最相似点为中心点，重复以一菱形外框作为搜寻区域。

步骤3：若最相似点仍在中心点，则进行步骤4，若最相似点在菱形外框上，则重复步骤2。

步骤4：缩小搜寻区域的搜寻范围为小实心菱形，最后找到最相似点后，即结束搜寻。

如图3所示，说明步骤1中，发现最相似点在菱形中心1’，因此进行步骤4，缩小搜寻区域的搜寻范围为小实心菱形，最后找到最相似点2’后结束搜寻。

如图4所示，说明步骤1中，最相似点1”在菱形外框，因此进行步骤2，以最相似点1”为中心点，重复以一菱形外框作为搜寻区域，接着进行步骤3，因为最相似点2”在菱形外框上，故重复步骤2，重复以一菱形外框作为搜寻区域，发现最相似点仍在菱形中心2”，因此进行步骤4，缩小搜寻区域的搜寻范围为小实心菱形，最后找到最相似点4”后结束搜寻。

如图5、6所示，目前无论是三步搜寻或钻石搜寻等判断方式，其搜寻的顺序主要仍是采取扫描式(Raster Pattern)搜寻，或是螺旋式(Spiral Pattern)搜寻法。所谓扫描式搜寻，乃是在所定义的搜寻范围自左而右、自上而下的顺序逐列寻找最相似的检查点；而所谓螺旋式搜寻法，则是在所定义的搜寻范围由中心点出发，以螺旋状的顺序向外逐点搜寻。

发明内容

因此，本发明的一目的，即在提供一种节省搜寻所耗费的时间，并提高效率的基于距离加权搜寻顺序以估算移动向量的方法。

于是，本发明基于距离加权搜寻顺序以估算移动向量的方法是参考一第一画面所具有的一预定像块，并搜寻邻近的一第二画面中对应预定像块相匹配的像块以估算预定像块的移动向量，其特征在于：所述的方法是于第二画面中是依一预定原则选择的一像块为一起始点，并以距离加权方式向外逐渐扩展搜寻与预定像块相匹配的像块以估算预定像块的移动向量。

有鉴于移动向量常是以放射状分布的方式出现，依据本发明以距离加权顺序搜寻可避免前述扫描式搜寻或是螺旋式搜寻法需要逐点一一搜寻所耗费的搜寻时间。

附图说明

下面结合附图及实施例对本发明进行详细说明：

图1是一示意图，说明目前在MPEG视讯编码影像的数据数据结构；

图2是一示意图，说明现有的一种三步判断方式；

图3是一示意图，说明现有的一种钻石判断方式；

图4是一示意图，说明现有的一种钻石判断方式；

图5是一示意图，说明目前的一种扫描式搜寻法；

图6是一示意图，说明目前的一种螺旋式搜寻法；

图7是一电路方块图，说明使用本发明方法的系统是一用以执行MPEG视讯编码功能的视讯编码装置；

图8是一示意图，说明本发明基于距离加权搜寻顺序以估算移动向量的方法的移动向量估算方式；

图9是一示意图，说明本发明基于距离加权搜寻顺序以估算移动向量的方法的第一较佳实施例以距离加权顺序法则进行的搜寻顺序；

图10是一示意图，说明本发明基于距离加权搜寻顺序以估算移动向量的方法的第二较佳实施例以距离加权顺序法则进行的搜寻顺序。

具体实施方式

有关本发明的前述及其它技术内容、特点与功效，在以下配合参考图式的三个较佳实施例的详细说明中，将可清楚的呈现。在本发明被详细描述之前，要注意的是，在以下的说明内容中，类似的元件是以相同的编号来表示。

如图7所示，使用本发明方法的系统是一用以执行MPEG视讯压缩功能的视讯编码装置1，然而，其它实施例中，或可应用在执行类似的视讯压缩功能的处理系统。

视讯编码装置1具有一前处理单元(Preprocessor)10、一移动估算单元(MotionEstimation)11、一移动补偿单元12、一移动向量编码单元(Motion Vector EncodingUnit)13、一纹理编码模组(Texture Encoding Unit)14、一比特流组合单元(Bit-StreamComposer)15及一记忆体16。

欲将一原始的输入影像100输入至视讯编码装置1时，是由视讯编码装置1的一前处理单元10先将一给定画面中的每一个巨块资料定义出来，并暂存至记忆体16；接着由移动估算单元11对于输入影像100中画面所具有的巨块资料进行计算，例如运算前、后画面中对应的像块资料后，可求得全画面的各像块资料的移动向量资料102；接着将其输入至移动补偿单元12，由移动补偿单元12利用所述的移动向量撷取先前或后一画面中的影像巨块资料以得到一参考资料104；再将前处理单元10得到输入影像100具有的影像巨块资料减去移动补偿单元12得到的参考数据104后，便得到一差值数据103，由纹理编码模组14对差值数据103进行运算以获得压缩的纹理及重建的参考资料。

纹理编码模组14的一离散余弦转换单元141是是对每一像块的画素资料施以离散余弦转换(DCT)，接着以频域转换单元142把画素数据由时域转换为频域，接着由量化单元143施以量化(Quantize)步骤，使得许多经过离散余弦转换的DCT系数量化为零，并去除掉高频部分；并需再经反量化单元144、反离散余弦转换单元145进行反量化以及反离散余弦转换运算，如此再反馈至移动估算单元11。并可由移动向量编码单元13将各移动向量加以编码输出至比特流组合单元15具有的一可变长度编码器151。

同时，需以交流/直流预测单元146(AC/DC Prediction)依照同一画面中各像块(Block)重复的累赘信息去除，再由交错扫描单元147进行交错扫描(Zig-zag scan)来将量化后的DCT系数重新排列，将低频系数排列在前而高频系数排列在后，最后在经交错扫瞄过后的DCT系数进行动态长度编码(Run Length Encoding；RLE)，最后再由比特流组合单元15具有的另一可变长度编码器152对二者进行可变长度编码(VariableLength Coding；VLC)，由比特流组合单元15加以组合，便可完成MPEG压缩格式的输出。

配合图7、8所示，本发明基于距离加权搜寻顺序以估算移动向量的方法的三个较佳实施例，均是在视讯编码装置1中的移动估算单元11进行，然而，其它实施例中，本发明的概念也可用于目前常见的全找搜寻、钻石搜寻、三步搜寻、四步搜寻或其它任一种动态估计。

所述的方法是从一第一画面501(又称为目前画面；Current Frame)所具有的一预定像块51，并搜寻邻近的一第二画面502(又称为参考画面；Reference Frame)对应预定像块51所相匹配的像块52以估算预定像块51的移动向量53，所述的方法是以第二画面502中依一预定原则选择一像块为一起始点，以距离加权方式向外逐渐扩展搜寻相匹配的像块52以估算预定像块51的移动向量53。

本发明基于距离加权搜寻顺序以估算移动向量的方法对于加权距离的概念可以公式1来说明：

搜寻加权距离＝H(u，v)；    公式1

H是一预定的距离权重函数，u是与起始点相距的U轴坐标，v是与起始点相距的V轴坐标，U、V两坐标是构成平面的一组基底(Bases)，搜寻顺序是先自加权距离最小的各像块开始搜寻。

如图9所示，说明本发明基于距离加权搜寻顺序以估算移动向量的方法的第一较佳实施例，本实施例中，距离加权的计算是依据公式2来计算；x是与起始点相距的X轴坐标，y是与起始点相距的Y轴坐标，且搜寻顺序是先自加权寻距离最小的各像块开始搜寻。

加权搜寻距离＝(绝对值(x)+绝对值(y))    公式2

其搜寻顺序是以一搜寻区域201的中心点301为起始(Original)点，依计算所得的最小距离开始搜寻，例如先搜寻301周围的4点菱形区域，若搜寻不到，然后再以菱形向外环绕扩散至未搜寻区域，依此类推，直到搜寻到最近似的像块为止。

如图10所示，说明本发明基于距离加权搜寻顺序以估算移动向量的方法的第二较佳实施例，本实施例中，距离加权的计算是依据公式3来计算；x是与起始点相距的X轴坐标，y是与起始点相距的Y轴坐标，且搜寻顺序是先自加权搜寻距离最小的像块开始搜寻。

加权搜寻距离＝最小值(开平方根号(x²+y²))    公式3

第二较佳实施例的搜寻顺序与第一较佳实施例类似，是以一搜寻区域202的中心点302为起始(Original)点，依计算所得的最小距离开始搜寻，例如先搜寻302本身(1)，再搜寻最接近302周围的4点(2，3，4，5)，再逐渐往外搜寻302周围的4点(6，7，8，9)，若在上述9点均搜寻不到，再向外扩散至未搜寻区域的外部多点，仍是以最接近302周围的点开始搜寻，如先找(10，11，12，13)，接着找(14，15，16，17，18，19，20，21)，依此类推，直到搜寻到最近似的像块为止。

本发明的第三较佳实施例，是以查表对各种距离值进行转换，加权距离的计算是依据公式4所示：

搜寻加权距离＝F(u)+G(v)＝F(abs(x))+G(abs(y))    公式4

F(u)、G(v)可由一预定的距离权重函数表以查表的方式换算出，x是与起始点相距的x轴坐标，y是与起始点相距的y轴坐标，且搜寻顺序是先自加权距离最小的各像块开始搜寻。前述的距离权重函数表的范例如表1、表2所示，且公式中的F(·)＝G(·)。

          表1                                         表2

  u  F(u)  0  1  1  3  2  4  3  5  4  7  5  8  6  8  7  8  8  10  9  10  10  10  11  11  12  11  13  11  14  11  15  11  u  F(u)  0  1  1  4  2  7  3  8  4  10  5  10  6  11  7  11  8  11  9  11  10  11  11  11  12  11  13  12  14  12  15  12

必须说明的是，表1、2中的u、v值可递增其计数，即可再继续扩增u、v值与F(u)的对应值，而不以上述列表为限；此外，本实施例中的u、v值每次增加的单位除了可以一整数点的数值代入距离权重函数表的方式，也可以是以一非整数点，例如1/2、1/4或1/8等数值代入距离权重函数表，均属于本发明可应用的范畴。

归纳上述，本发明基于距离加权搜寻顺序以估算移动向量的方法的原理，乃是由于一般移动向量常是以放射状由内而外分布的方式出现，因此相较于以往采用的扫描式搜寻，或是螺旋式搜寻法，依据本发明以距离加权顺序搜寻将可快速找到相似像块，并且节省不必要的搜寻时间而使得移动向量的估算更为有效率。