视频编码系统、移动估算装置及移动估算的计算方法

技术领域

本发明与视频编码有关，特别地，有关于一种不需利用复杂的乘法运算即能迅速地估算出对应于不同候选搜寻位置的移动向量成本函数的视频编码系统、移动估算装置及其运作方法。

背景技术

在视频编码系统(video encoding system)中，移动估算(motion estimation)技术用以决定视频串流中的一张影像相对于其邻近影像的移动向量(motionvector)。在许多视频编码系统(例如与H.264或MPEG-4协议兼容的系统)中，通常会采用移动估算法来协助找出不同画面间的相依性，进而达到影像压缩或画面内容分析等应用。

一般而言，目前的影像处理技术主要透过区块比对的方法找出最适当的移动向量，来表示某一欲比对的区域(比对视窗)在两个不同画面之间的相对位移。请参阅图1(A)，图1(A)绘示先前技术中移动向量V的示意图。如图1(A)所示，移动向量V可以用来表示先前画面与目前画面之间，对应特定区块的水平及垂直位移的向量(如图一中的向量V)。在实际应用中，最常被使用的区块匹配差异(block-matching discrepancy)计算方法为计算绝对值差之和(Sum of Absolute Differences，SAD)。

在各种移动向量的估算方法中，移动向量成本函数(motion vector costfunction)算是一种较佳的估算方法，其公式如下：

移动向量成本函数＝A×(mvbits[cx-px]+mvbits[cy-py])

其中A为比例因子(scaling factor)；[cx，cy]为候选搜寻位置(searchcandidate)的移动向量；[px，py]为预估位置(predictor)的移动向量；mvbits[cx-px]为上述两移动向量的x方向分量差的位元估算值；mvbits[cy-py]则为上述两移动向量的y方向分量差的位元估算值。以mvbits[k]为例，其位元数与|k|之间的对应关系如图1(B)所示。

请参照图1(C)，图1(C)绘示了传统的移动向量成本函数产生器的电路架构。如图1(C)所示，移动向量成本函数产生器3包含第一减法单元30、第二减法单元31、第一移动向量位元估算单元32、第二移动向量位元估算单元33、加法单元34及乘法单元35。

首先，第一减法单元30根据候选搜寻位置的移动向量[cx，cy]与预估位置的移动向量[px，py]的x分量cx及px计算两者的差值[cx-px]；第二减法单元31根据候选搜寻位置的移动向量[cx，cy]与预估位置的移动向量[px，py]的y分量cy及py计算两者的差值[cy-py]。接着，第一移动向量位元估算单元32及第二移动向量位元估算单元33分别根据[cx-px]计算移动向量位元mvbits[cx-px]以及根据[cy-py]计算移动向量位元mvbits[cy-py]。之后，加法单元34将mvbits[cx-px]与mvbits[cy-py]相加而得到(mvbits[cx-px]+mvbits[cy-py])。最后，乘法单元35再将比例因子A与(mvbits[cx-px]+mvbits[cy-py])相乘而得到所求的移动向量成本函数。

然而，上述传统的移动向量成本函数产生器3的电路架构的最大缺点在于必须藉由较高阶的乘法单元35进行复杂的乘法运算，因而导致时间限制以及逻辑门数增加等问题。

因此，本发明的主要目的在于提供一种视频编码系统、移动估算装置及其运作方法，以解决上述问题。

发明内容

根据本发明的第一具体实施例，为一种移动估算装置。在此实施例中，该移动估算装置应用于一视频编码系统中。该移动估算装置包含第一计算模块及第二计算模块。当移动估算的计算沿着一搜寻路径自第一候选搜寻位置(x₁，y₁)移动至第二候选搜寻位置(x₂，y₂)时，该第一计算模块根据对应于该搜寻路径的一搜寻路径信息估算出第一移动向量成本差值。该第二计算模块根据一预设规则选择性地将一原始移动向量成本值加上或减去该第一移动向量成本差值，以得到对应于该第二候选搜寻位置(x₂，y₂)的一第一移动向量成本值。其中，x₁及x₂分别为该第一候选搜寻位置及该第二候选搜寻位置所对应的水平轴座标值；y₁及y₂分别为该第一候选搜寻位置及该第二候选搜寻位置所对应的垂直轴座标值。

根据本发明的第二具体实施例，为一种移动估算的计算方法。在此实施例中，该方法应用于一视频编码系统中。首先，当移动估算的计算沿着一搜寻路径自第一候选搜寻位置(x₁，y₁)移动至第二候选搜寻位置(x₂，y₂)时，该方法根据对应于该搜寻路径的一搜寻路径信息估算出第一移动向量成本差值。接着，该方法根据一预设规则选择性地将一原始移动向量成本值加上或减去该第一移动向量成本差值，以得到对应于该第二候选搜寻位置(x₂，y₂)的一第一移动向量成本值。其中，x₁及x₂分别为该第一候选搜寻位置及该第二候选搜寻位置所对应的水平轴座标值；y₁及y₂分别为该第一候选搜寻位置及该第二候选搜寻位置所对应的垂直轴座标值。

综上所述，由于本发明的移动估算装置并不需藉由复杂的乘法运算即可迅速且准确地估算出移动向量成本函数，故能够有效避免先前技术所遭遇到的时间限制、逻辑门数增加及移动估算效率不佳等问题，尤其是当该移动估算装置同时进行多个候选搜寻位置的移动估算时，其提升移动估算效率的效果更为显著。

关于本发明的优点与精神可以藉由以下的发明详述及附图得到进一步的了解。

附图说明

图1(A)绘示了先前技术中移动向量V的示意图；图1(B)绘示了mvbits[k]的位元数与|k|之间的对应关系；图1(C)绘示了传统的移动向量成本函数产生器的电路架构。

图2绘示了根据本发明的第一具体实施例的移动估算装置的功能方块图。

图3(A)绘示了信息提供模块与第一计算模块之间的信息传递情形；图3(B)绘示了第一计算模块的详细功能方块图；图3(C)绘示了信息提供模块与第二计算模块之间的信息传递情形；图3(D)绘示了第一计算模块、第二计算模块与第三计算模块之间的信息传递情形。

图4绘示了第二计算模块的详细功能方块图。

图5(A)～图5(C)绘示了不同型式的搜寻路径。

图6(A)及图6(B)绘示了透过蛇行型式的搜寻路径进行搜寻扫描的示意图；图6(C)绘示了分数(像素)移动估算的一范例。

图7绘示了根据本发明的第二具体实施例的移动估算装置运作方法的流程图。

主要元件符号说明

S10～S17：流程步骤

1：移动估算装置            10：信息提供模块

12：第一计算模块    14：第二计算模块

16：第三计算模块    18：储存模块

30：第一减法单元    31：第二减法单元

34：加法单元        35：乘法单元

3：移动向量成本函数产生器

32：第一移动向量位元估算单元

33：第二移动向量位元估算单元

140：第一多工器     141：x分量处理器

142：y分量处理器    143：第二多工器

122、144：加法器    145：移动向量位元估算单元

146：减法器         147：移动向量成本差值计算单元

V：移动向量         MVC₀：原始的移动向量成本值

A：比例因子         ΔMVC₁：第一移动向量成本差值

C：中央位置         H：1/2候选搜寻位置

Q：1/4候选搜寻位置

[px，py]：对应于预估位置的移动向量

[cx，cy]：候选搜寻位置的移动向量

[cx₀，cy₀]：对应于第一候选搜寻位置(x₁，y₁)的移动向量

[cx₁，cy₁]：对应于第二候选搜寻位置(x₂，y₂)的移动向量

MVC₁：对应于第二候选搜寻位置(x₂，y₂)的移动向量成本值

120：移动向量位元产生器  124：累加器

1200：第一减法器         1202：第二减法器

1204：第一移动向量位元估算单元

1206：第二移动向量位元估算单元

具体实施方式

本发明的主要目的在于提出一种不需藉由复杂的乘法运算即能迅速地估算出对应于不同候选搜寻位置的移动向量成本函数的视频编码系统、移动估算装置及其运作方法。

根据本发明的第一具体实施例，为一种移动估算装置。在此实施例中，该移动估算装置运用于一视频编码系统中。请参照图2，图2绘示了该移动估算装置的功能方块图。如图2所示，移动估算装置1包含信息提供模块10、第一计算模块12、第二计算模块14、第三计算模块16及储存模块18。其中，信息提供模块10耦接至第一计算模块12、第二计算模块14及储存模块18；第一计算模块12及第二计算模块14均耦接至第三计算模块16。

在此实施例中，当移动估算的计算尚未从第一候选搜寻位置(x₁，y₁)沿着一搜寻路径开始进行之前，第一计算模块12将会先计算对应于第一候选搜寻位置(x₁，y₁)的原始的移动向量成本值MVC₀。如图3(A)所示，假设对应于第一候选搜寻位置的移动向量表示为[cx₀，cy₀]且对应于预估位置的移动向量表示为[px，py]，信息提供模块10将会提供[cx₀，cy₀]、[px，py]及比例因子A等信息至第一计算模块12，使得第一计算模块12能够根据该些信息计算得到原始的移动向量成本值MVC₀。

值得注意的是，为了改善先前技术采用较高阶的乘法器进行复杂的乘法运算，导致时间限制以及逻辑门数增加等问题，第一计算模块12藉由仅包含多个加法单元的累加器计算出原始的移动向量成本值MVC₀，并未直接采用高阶的乘法器进行复杂的乘法运算，藉以有效地节省电路元件的成本。请参照图3(B)，图3(B)绘示了第一计算模块12的详细功能方块图。如图3(B)所示，第一计算模块12包含移动向量位元产生器120、加法器122及累加器124。其中，移动向量位元产生器120包含第一减法器1200、第二减法器1202、第一移动向量位元估算单元1204及第二移动向量位元估算单元1206；累加器124包含多个加法单元。

当第一减法器1200接收到cx₀及px时，第一减法器1200将其相减后传送至第一移动向量位元估算单元1204，第一移动向量位元估算单元1204再据以产生第一移动向量位元；当第二减法器1202接收到cy₀及py时，第二减法器1202将其相减后传送至第二移动向量位元估算单元1206，第二移动向量位元估算单元1206再据以产生第二移动向量位元。接着，当加法器122分别自第一移动向量位元估算单元1204及第二移动向量位元估算单元1206接收到第一移动向量位元及第二移动向量位元时，加法器122将第一移动向量位元与第二移动向量位元相加后传送至累加器124，累加器124透过其多个加法单元得到乘以例因子A的计算结果。

在此需说明的是，虽然第一计算模块12计算原始的移动向量成本值MVC₀时，仍需乘以比例因子A，然而，由于比例因子A仅为一常数，故第一计算模块12并不需透过高阶的乘法器进行复杂的乘法运算，仅需藉由累加器124所包含的多个加法单元即可实现乘以一常数的简单乘法运算，进而求得原始的移动向量成本值MVC₀。

当第一计算模块12计算出对应于第一候选搜寻位置(x₁，y₁)的原始的移动向量成本值MVC₀后，移动估算的计算即可开始沿着该搜寻路径依序分别对沿途经过的各个候选搜寻位置进行。当然，在移动估算的计算开始进行之前，该搜寻路径需先被决定，以利后续的移动估算。实际上，该搜寻路径可以是系统预设值或由使用者所设定。

假设移动估算的计算由第一候选搜寻位置(x₁，y₁)沿着该搜寻路径移动至第二候选搜寻位置(x₂，y₂)，且对应于第二候选搜寻位置(x₂，y₂)的移动向量表示为[cx₁，cy₁]，如图3(C)所示，信息提供模块10将会提供[cx₁，cy₁]、[px，py]以及对应于该搜寻路径的搜寻路径信息给第二计算模块14。藉此，第二计算模块14即可根据该些信息计算出第一移动向量成本差值ΔMVC₁。根据本发明，在进行搜寻扫描的过程中，由于移动估算的计算每一次移动的距离通常不会很大(例如一个像素)，且通常为水平方向或垂直方向的移动，因此，第二计算模块14计算第一移动向量成本差值ΔMVC₁的负荷量并不大，故可有效节省系统运算资源。

接着，如图3(D)所示，由于第一计算模块12已经计算出对应于第一候选搜寻位置(x₁，y₁)的原始的移动向量成本值MVC₀，并且第二计算模块14已经计算出第一移动向量成本差值ΔMVC₁，因此，第三计算模块16即可将MVC₀与ΔMVC₁相加得到对应于第二候选搜寻位置(x₂，y₂)的移动向量成本值MVC₁。值得注意的是，第三计算模块16根据一预设规则选择性地将MVC₀加上或减去ΔMVC₁以得到MVC₁，并且该预设规则由第三计算模块16根据该搜寻路径信息所估算出第一候选搜寻位置(x₁，y₁)与该第二候选搜寻位置(x₂，y₂)之间的座标值差异所决定，亦即该预设规则与两搜寻位置的x座标差(x₂-x₁)及y座标差(y₂-y₁)为正或负有关。

接下来，将就第二计算模块14如何根据[cx₁，cy₁]、[px，py]以及对应于该搜寻路径的搜寻路径信息计算第一移动向量成本差值ΔMVC₁进行更深入的探讨。请参照图4，图4绘示了第二计算模块14的详细功能方块图。如图4所示，第二计算模块14包含第一多工器140、x分量处理器141、y分量处理器142、第二多工器143、加法器144、移动向量位元估算单元145、减法器146及移动向量成本差值计算单元147。

在此实施例中，第一多工器140用以接收信息提供模块10所输入的对应于预估位置的移动向量[px，py]以及搜寻路径信息，并输出[px，py]至移动向量位元估算单元145。至于信息提供模块10所输入的对应于第二候选搜寻位置(x₂，y₂)的移动向量[cx₁，cy₁]，其x分量cx₁与y分量cy₁分别经过x分量处理器141及y分量处理器142的处理后，将会被传送至第二多工器143，而第二多工器143将会输出MV₁[cx₁，cy₁]至移动向量位元估算单元145。值得注意的是，第二多工器143与移动向量位元估算单元145之间设置有加法器144，用以根据搜寻路径信息于MV₁加入一位移量(displacement)，使其根据实际移动情形变成MV₁’。实际上，MV₁’可能是[cx₁’，cy₁]、[cx₁，cy₁’]或[cx₁’，cy₁’]，端视不同的搜寻路径中每一步移动的距离大小而定。举例而言，若搜寻路径为蛇行路径，则MV₁’应为[cx₁’，cy₁]或[cx₁，cy₁’]；若搜寻路径为钻石形状路径，则MV₁’可能出现[cx₁’，cy₁’]。

接着，移动向量位元估算单元145即分别根据不同的MV₁及MV₁’产生第一移动向量位元及第二移动向量位元。之后，减法器146再将第二移动向量位元减去第一移动向量位元以产生一移动向量位元差值。最后，移动向量成本差值计算单元147根据该移动向量位元差值计算得到所求的第一移动向量成本差值ΔMVC₁。

此外，关于上述搜寻路径的型式并无一定的限制，如图5(A)至图5(C)所示，搜寻路径的型式可以是蛇行路径(serpentine path)、螺旋状路径(spiralpath)及钻石形状路径(diamond path)，但不以此为限。实际上，这些具有不同型式的搜寻路径及其相对应的搜寻路径信息(例如搜寻路径沿途经过的所有搜寻位置及搜寻顺序等)可储存于储存模块18中，当第二计算模块14需要这些信息以进行运算时，信息提供模块10即会至储存模块18存取所需的信息以提供给第二计算模块14。

接下来，将以采用蛇行搜寻路径对一画面上的所有像素进行搜寻扫描的一实际例子作为说明。请参照图6(A)及图6(B)，图6(A)及图6(B)绘示了透过蛇行型式的搜寻路径进行搜寻扫描的示意图。如图6(A)所示，假设比对区域(比对视窗)为图中斜线部分且预估位置的座标为(0，0)，搜寻路径系由第一候选搜寻位置(-2，-2)开始依照(-2，-1)、(-2，0)、…、(-2，4)、(-1，4)、(-1，3)、…的顺序一直蛇行搜寻至(4，4)为止。

当移动估算的计算还未真正从(-2，-2)沿着搜寻路径开始进行之前，第一计算模块12将会先根据[cx₀，cy₀]、[px，py]及比例因子A计算对应于(-2，-2)的原始的移动向量成本值MVC₀。

在此例中，[cx₀，cy₀]＝[-2，-2]且[px，py]＝[0，0]。接着，当移动估算的计算沿着搜寻路径由(-2，-2)移动至(-2，-1)时，第二计算模块14即会根据[cx₁，cy₁]、[px，py]以及对应于该搜寻路径的搜寻路径信息计算出第一移动向量成本差值ΔMVC₁。在此例中，[cx₁，cy₁]＝[-2，-1]且[px，py]＝[0，0]，亦即仅有cy₁与cy₀不同，而cx₁则与cx₀相同，故第二计算模块14不必透过复杂的运算即可求出ΔMVC₁。之后，第三计算模块16即可根据预设规则选择性地将MVC₀加上或减去ΔMVC₁以得到MVC₁。在此例中，由于移动估算的计算自(-2，-2)移动至(-2，-1)时，y₁-y₀＝(-1)-(-2)＝1＞0，代表移动估算的计算于y方向上往正方向移动，故第三计算模块16将会将MVC₀加上ΔMVC₁以得到MVC₁。同理，移动估算的计算沿着搜寻路径由(-2，-1)移动至(-2，0)时的情形亦类似，在此不另行赘述。

如图6(B)所示，当移动估算的计算持续沿着搜寻路径欲由(-2，4)移动至(-1，4)时，情况会有所不同。假设于前一步骤所得到对应于(-2，4)的移动向量成本为MVC₆且其[cx₆，cy₆]＝[-2，4]，第二计算模块14即会根据[cx₇，cy₇]、[px，py]以及对应于该搜寻路径的搜寻路径信息计算出第七移动向量成本差值ΔMVC₇。于此例中，[cx₇，cy₇]＝[-1，4]且[px，py]＝[0，0]，亦即仅是cx₇与cx₆不同，而cy₇则与cy₆相同，故第二计算模块14不必透过复杂的运算即可求出ΔMVC₇。之后，第三计算模块16即可根据预设规则选择性地将MVC₆加上或减去ΔMVC₇以得到MVC₇。于此例中，由于移动估算的计算自(-2，4)移动至(-1，4)时，x₇-x₆＝(-1)-(-2)＝1＞0，代表移动估算的计算于x方向上往正方向移动，故第三计算模块16将会将MVC₆加上ΔMVC₇以得到MVC₇。

在实际应用中，根据本发明的移动估算装置除了可以应用于如同上述实施例的整数(像素)的移动估算(Integer Motion Estimation，IME)外，亦可应用于分数(像素)的移动估算(Factional Motion Estimation，FME)的情况。举例而言，如图6(C)所示，在分数(像素)的移动估算中，候选搜寻位置可分成中央位置C、1/2候选搜寻位置H及1/4候选搜寻位置Q。若移动估算装置位于中央位置C，则接下来移动估算的计算可透过一次移动移动至该些1/2候选搜寻位置H。至于该些1/4候选搜寻位置Q，移动估算的计算需透过两次移动才能从中央位置C移动至该些1/4候选搜寻位置Q，抑或是透过一次移动从该些1/2候选搜寻位置H移动至该些1/4候选搜寻位置Q。

根据本发明的第二具体实施例为一种移动估算的计算方法。在此实施例中，该方法应用于一视频编码系统中。请参照图7，图7绘示了该移动估算计算方法的流程图。如图7所示，首先，在步骤S10中，当移动估算的计算尚未开始进行之前，该方法将会先计算对应于第一候选搜寻位置(x₁，y₁)的原始的移动向量成本值MVC₀。实际上，MVC₀根据对应于第一候选搜寻位置的移动向量[cx₀，cy₀]、对应于预估位置的移动向量[px，py]以及比例因子A等信息计算而得。值得注意的是，为了改善先前技术采用较高阶的乘法器进行复杂的乘法运算，导致时间限制以及逻辑门数增加等问题，该方法仅需藉由累加器所包含的多个加法单元即可实现乘以一常数的简单乘法运算，进而求得原始的移动向量成本值MVC₀，并未直接采用复杂的乘法运算。

接着，在步骤S11中，移动估算的计算开始沿着一搜寻路径自第一候选搜寻位置(x₁，y₁)移动至第二候选搜寻位置(x₂，y₂)。然后，该方法执行步骤S12，根据对应于该搜寻路径的一搜寻路径信息估算出第一移动向量成本差值ΔMVC₁。实际上，第一移动向量成本差值ΔMVC₁根据搜寻路径信息、对应于第二候选搜寻位置(x₂，y₂)的移动向量[cx₁，cy₁]以及对应于预估位置的移动向量[px，py]所估算出来的。其中，x₁及x₂分别为该第一候选搜寻位置及该第二候选搜寻位置所对应的水平轴座标值；y₁及y₂分别为该第一候选搜寻位置及该第二候选搜寻位置所对应的垂直轴座标值。

实际上，该搜寻路径可以是一蛇行路径、一螺旋状路径或一钻石形状路径，并可为系统预设值或由使用者所设定，并无一定的限制。在此实施例中，假设该搜寻路径依序经过第一候选搜寻位置(x₁，y₁)、第二候选搜寻位置(x₂，y₂)及第三候选搜寻位置(x₃，y₃)，且该搜寻路径信息包含第一候选搜寻位置(x₁，y₁)、第二候选搜寻位置(x₂，y₂)及第三候选搜寻位置(x₃，y₃)的座标值。

接着，在步骤S13中，该方法根据一预设规则选择性地将原始的移动向量成本值MVC₀加上或减去第一移动向量成本差值ΔMVC₁，以得到对应于第二候选搜寻位置(x₂，y₂)的移动向量成本值MVC₁。于实际应用中，该预设规则和该第一候选搜寻位置(x₁，y₁)与该第二候选搜寻位置(x₂，y₂)之问的座标值差异有关，亦即该预设规则与两搜寻位置之x座标差(x₂-x₁)及y座标差(y₂-y₁)为正或负有关。

在计算出对应于第二候选搜寻位置(x₂，y₂)之移动向量成本值MVC₁后，该方法执行步骤S14，判断第二候选搜寻位置是否为搜寻路径的终点。若步骤S14的判断结果为是，代表移动估算的计算已移动至搜寻路径的终点，故整个移动估算的计算程序已完成；若步骤S14的判断结果为否，该方法执行步骤S15，移动估算的计算自第二候选搜寻位置(x₂，y₂)继续沿着该搜寻路径移动至第三候选搜寻位置(x₃，y₃)。

此时，该方法将会执行步骤S16，根据搜寻路径信息估算出一第二移动向量成本差值ΔMVC₂。其中，x₃及y₃分别为该第三候选搜寻位置所对应的水平轴座标值及垂直轴座标值。接着，在步骤S17中，该方法根据该预设规则选择性地将对应于第二候选搜寻位置(x₂，y₂)的移动向量成本值MVC₁加上或减去第二移动向量成本差值ΔMVC₂，以得到对应于第三候选搜寻位置(x₃，y₃)的第二移动向量成本值MVC₂。

接下来，该方法将会判断第三候选搜寻位置是否为搜寻路径的终点，若判断结果为否，代表搜寻路径尚未结束，该方法即会重复上述步骤，直至整个搜寻路径的移动估算的计算工作完成为止。藉此，透过该方法即能得到对应于搜寻路径中的每个候选搜寻位置的移动向量成本值，进而可据以判断出具有最低移动向量成本值的候选搜寻位置为何。

综上所述，由于本发明的移动估算装置并不需藉由高阶乘法器进行复杂的乘法运算，即可迅速且准确地估算出移动向量成本函数，故能够有效避免先前技术所遭遇到的时间限制、逻辑门数增加及移动估算效率不佳等问题。尤其是当移动估算装置同时进行多个候选搜寻位置的移动估算时，其提升移动估算效率的效果更为显著。此外，由于移动估算装置在搜寻扫描过程中每一次移动的距离通常不大且大多为水平或垂直方向的移动，因此，移动估算装置计算移动向量成本差值的负荷量并不大，故可有效节省系统运算资源。

藉由以上较佳具体实施例的详述，希望能更加清楚描述本发明的特征与精神，而并非以上述所揭示的较佳具体实施例来对本发明的范畴加以限制。相反地，其目的是希望能涵盖各种改变及具相等性的安排于本发明所欲申请的专利范围的范畴内。