CN1578464A

CN1578464A - 在数字影像压缩中决定动态向量的方法

Info

Publication number: CN1578464A
Application number: CNA2004100015183A
Authority: CN
Inventors: 许俊民; 吕艾杰; 王岳宜
Original assignee: Primax Electronics Ltd
Current assignee: Primax Electronics Ltd
Priority date: 2003-07-14
Filing date: 2004-01-13
Publication date: 2005-02-09
Anticipated expiration: 2024-01-13
Also published as: CN1260977C; US7145950B2; US20050013364A1; TWI297576B; TW200503528A

Abstract

一现存数据块的像素信息会与一参考数据帧的像素信息作交联运算，其中参考数据帧可以三种向量表示：(a)第一动态向量表示近似于现存数据块的数据块，(b)第二动态向量表示在参考数据帧中，在空间上与现存数据块相符的数据块，以及(c)第三动态向量表示参考数据帧的预设区域。并从具有最低成本函数的第一、第二以及第三动态向量中，选取至少一项作为候补向量。现存数据块的像素信息与候补向量所标示的区域所近邻区域的像素信息作交联运算，以决定候补动态向量以及对应的成本函数。之后，选取具有最低成本函数的候补动态向量作为现存数据块的动态向量。

Description

在数字影像压缩中决定动态向量的方法

技术领域

本发明涉及一数字影像，特别是涉及一种使用动态估计的数字影像压缩技术。

背景技术

数字影像已经是目前信息传播中常用的方法，例如计算机视讯会议(Computer-based video conferencing)以及数字电视皆是应用此项技术的例子。当一个包含数以千计的像素的单一数字图像需要许多连续的图像帧以产生高阶影像时，就必需使用压缩系统以在压缩时能更有效率地节省处理时间以及储存空间。

一般来说，图像压缩受到像素区中的交联运算影响。举例来说，因为受到数据转换速度的限制而需要较高压缩比时，可能会牺牲影像的品质或者要增加额外用于压缩的硬件以及软件。若在运用低压缩比时，为维持影像品质就需要增加存储器的储存空间。为了从中取得平衡点，任何不会降低影像品质或不需要另外增加必要硬件的压缩技术一直都是大家都在追求的目标。

请参阅图1，图1为已知的数字影像(digital video)10显示图像12的现存数据帧14以及先前数据帧16的示意图。现存数据帧14是由影像存储或显示装置(如计算机监视器或数字电视机)的像素(pixel)20所组成。为达到影像压缩的目的，常使用动态估计，使像素20组成现存数据块18。常用的高阶动态估计压缩系统即为MPEG-1以及MPEG-2。

在动态估计期间，重复的数据会暂时最小化冗余影像帧，从而提供压缩。经过压缩的数据块18的像素信息会与先前数据帧16的像素信息相对照。特别是先前数据块16会先搜寻出一预测区(predictor region)22，而预测区22则包含大量的数据块18的像素数据。一旦发现适当的预测区，会以一动态向量加以确认标示，该动态向量即用来表示预测区22相对于数据块18的位置。换言之，数据块18内的数据包含有用来表示预测区22相对于数据块18位置的动态向量以及其它用来表示预测区22的像素变动的数据。因此，现存数据帧14的数据块18可以取代先前数据帧16。

有许多方法可通过搜寻先前数据帧或参考数据帧来寻找一适当的预测数据块。其中从较慢的像素搜寻法到快速的取样动态估计法等等。图2表示已知的快速动态估计方法。区域30表示被搜寻的参考数据帧的区域，其中格子点代表预设搜寻区域。搜寻区域的范围可大可小，从单一像素到一阵列(array)像素皆可，而且一般来说搜寻区域与被压缩的数据块大小相同，搜寻区域在空间上的大小与中央区域R1相符。根据三步骤方法的第一步骤所示，被压缩的数据块的像素信息(即现存数据块)会与搜寻区域R1-R9的像素信息相对照。之后便能决定每一区域R1-R9的像素信息经过交联运算后所得到的成本函数值(cost function)，而拥有最低成本函数值(图2的区域R4)的区域则会被选取。在步骤二中，将环绕在步骤一中具有最低成本函数值的区域R4的搜寻区域S2-S9与现存数据块的像素信息相对照，而且再一次地选取其中拥有最低成本函数值(本例的区域S7)的区域。最后，第三步骤将现存数据块与搜寻区域T2-T9相对照，其中拥有最低成本函数的区域(区域T2)与现存数据块最相符。第三步骤的结果就是压缩的现存数据块的预测区的位置，而且此结果可被参考数据帧的动态向量(区域T2向量(1，3))所确定。

一般来说，成本函数为绝对差(absolute differences)的总和(SAD)或者为平方差的总和(SSD)，两者皆可以以下两函数表示：

SAD (u, v) = Σ_{i = 1}^{N} Σ_{j = 1}^{M} | P_{curr} (i, j) - P_{ref} (i + u, j + v) |

SSD (u, v) = Σ_{i = 1}^{N} Σ_{j = 1}^{M} [P_{curr} (i, j) - P_{ref} (i + u, j + v)]^{2}

其中

P_curr为正被压缩的现存数据块的像素数据，如亮度；

P_ref为参考数据帧中的搜寻区域的像素数据(如图2的区域R1-R9、S2-S9以及T2-T9)；

i，j为搜寻区域以及现存数据块像素的水平指数(horizontal indices)以及垂直指数；

N，M为搜寻区域以及现存数据块的水平面积以及垂直面积；以及

u，v为与现存数据帧中的现存数据块的位置相关的参考数据帧的搜寻区域的水平偏移量(horizontal offsets)以及垂直偏移量(以区域R5为例，u＝-4而v＝0)。

尽管三步骤方法有上述的优点，但是却可能只得出局部区域的最小值(local minimum)。举图2的例子来说，虽然在第一步骤中，区域R4可与现存数据块得出最佳的交联运算结果，但是区域X1可能才具有最低的成本函数值，换言之，对搜寻区域30来说，实际的动态向量应该为X1。但是若以前述三步骤搜寻方法进行估计，在第一步骤期间，可先确定区域R4是具有最小成本函数值的候选者(candidate)，之后再依据区域R4去执行估计运算，最终会得出一不正确的动态向量如T2。这是因为一旦第一步骤选定了一区域，接下来的三步骤搜寻的结果会被限制在附近的区域，导致估计的错误。

发明内容

本发明的目的是提供一决定现存数据块的动态向量的方法，其中该现存数据块将相近于现存数据块的数据块的动态向量，一相异数据帧的相符数据块，以及预定搜寻模式，用来降低局部最小错误(local minimum error)的可能性。

本发明提供的一种方法将一现存数据块的像素信息与一参考数据帧的像素信息作交联运算，其中参考数据帧可以三种向量表示：(a)第一动态向量，表示近似于现存数据块的数据块，(b)第二动态向量，表示在参考数据帧中，在空间上与现存数据块相符的数据块，以及(c)第三动态向量，表示参考数据帧的预设区域。并从具有最低成本函数的第一、第二以及第三动态向量中，选取至少一项作为候补向量。现存数据块的像素信息与候补向量所标示的区域所近邻区域的像素信息作交联运算，以决定候补动态向量以及对应的成本函数。之后，选取具有最低成本函数的候补动态向量作为现存数据块的动态向量。

本发明在对应成本函数高于临界值(threshold level)的情况下，可摒弃第一以及第二动态向量。

本发明的优点在于该相近数据块的动态向量如同预定区域以及相符数据块的动态向量一样，可做为该现存数据块的候补，因此可提升决定动态向量的精确度。

本发明的优点为当对应成本函数高于临界值时，可抛弃相近数据块的动态向量以及相符数据块的动态向量，因此当该相近数据块的像素信息与该现存数据块的像素信息做缓慢地交联运算时，可增加决定动态向量过程的速度。

附图说明

图1为一数字影像数据帧的示意图；

图2为已知的三步骤动态向量搜寻方法的示意图；

图3为执行本发明方法的影像系统的方块图；

图4为本发明方法的示意图；

图5为本发明方法的第一实施例的流程图；和

图6为本发明方法的第二实施例的流程图。

附图符号说明

10 数字影像 12 图像

14、60 现存数据帧 16 先前数据帧

18、62 现存数据块 20 像素

22 预测区 30 搜寻区域

40 影像系统 42 影像来源

44 随机存取存储器 46 处理器

48 压缩演算系统 50 显示装置

64、66、68 相近数据块 70 参考数据帧

72 同位数据块

具体实施方式

一般情形(General)：

图3为一执行本发明的决定动态向量方法的影像系统40的方块图。影像系统40包含一随机存取存储器(random access memory，RAM)44以及一处理器46，用来执行压缩演算系统48。该压缩演算系统可储存在RAM44或者处理器的存储器。影像系统40通过RAM44的接口(图未示)从影像来源42如一数字影像摄影机，接收一未经处理的影像讯号。接下来处理器46会执行压缩演算系统48以处理储存在RAM44的未经处理的影像数据，而且通过一输出接口(图未示)输出已压缩影像数据到显示或储存装置50。在实际的应用中，录像或者是现场直播的节目，即影像来源42，可用数字播放的方式传送到一具有RAM44、处理器46以及显示装置50的数字电视机里。同样地，影像来源42也可能是利用计算机的数字摄影机，其中RAM44以及处理器46为该计算机的一部分，另外显示装置50也可能是一遥控监视器，能通过网络将已压缩影像传送到该监视器。

图4示出了本发明方法的较佳实施例的示意图，在图4中示出了一数字影像的现存数据帧60以及参考数据帧(参考图像)70。参考数据帧70为一典型的实时先前数据帧(immediately previous frame)。假设在一特定时间，现存数据帧60的数据块62的像素信息正在进行压缩程序。本发明将三组动态向量视为现存数据块的像素信息的压缩，其中该三组动态向量包括：附近(相近)数据块的动态向量、同一空间位置但不同数据帧的数据块的动态向量，以及由与现存数据块位置相关的预定位置所决定的动态向量。紧接着，这些候补动态向量的成本函数会依照预设规则加以对照，以决定接下来用于交联运算的两个最适动态向量。最后，在接下来的交联运算使用任何已知的方法后，会从候补动态向量中选取具有最低成本函数值的动态向量作为现存数据块的动态向量。

相近数据块(Proximate Blocks)：

请参阅图4，此时相近于现存数据块62的数据块64、66以及68会被选取。通过合理的设计程序可选取特定的相近数据块，因为这些选取的相近数据块会使得动态向量的选择较有效率。虽然最佳实施例仅选取三个相近数据决64、66以及68，但事实上可选取任意个相近数据块。接下来，相近数据块64、6 6以及68的个别动态向量A1、A2以及A3(如图4所示)与这些动态向量的平均向量A4相对照，也就是说，根据动态向量A1、A2、A3以及A4相对于数据块62在参考图像70在空间上的区域，其像素信息与现存数据块62的像素信息进行比较。举例来说，相近区域64的动态向量A1会被用来定位参考图像70对应于现存数据帧60中的现存数据块62的位置的区域。假设现存数据帧60中的现存数据块62的坐标为(64，48)，动态向量为(-3，-2)，则参考图像70中的区域(61，48)像素信息与现存数据块62的像素信息为交互关联(correlated)。此类像素信息对照关系可为一成本函数(costfunction)所对照，并可依任何先前所提到的方法如SAD或SSD加以执行。接下来，有最低成本函数值的动态向量A1、A2、A3以及A4，亦即有最佳交联关系者会被选取作为一可能动态向量或者点P1。很自然地，在其它实施例中，可以将两个以上的动态向量列入考虑。

可能动态向量(potential motion vector)P1的决定如图5流程图的步骤100以及图6流程图的步骤200所示。

同位数据块(Co-located Block)：

选取参考数据帧中相关位置与现存数据帧60中的现存数据块62相同的数据块72。此同位(或相符)数据块72的动态向量标名为可能动态向量P2。当然，假如同位数据块72在现存数据帧60之外，则同位数据块72不会在参考数据帧70之内。除此之外，同位数据块72应该已经有已决定的动态向量来避免冗长的计算。

可能动态向量P2的决定如图5流程图的步骤100以及图6流程图的步骤200所示。

预设区域(Predetermined Regions)：

选取预设点所标示的区域，如图2的区域R1-R9。为了方便在数据帧60上标示，这些点在图4中是以虚线圆圈R所标示，但实际上是表示参考数据帧70的区域。对应于这些点R的动态向量被用来定位参考图像70的区域，这些区域会与现存数据块作交联运算。具有最佳交联运算的两区域R的动态向量，(换言之具有最低成本函数值的动态向量)，可设定为可能动态向量P3以及P4。可能动态向量P3以及P4的选取与利用已知三步骤方法的第一步骤决定结果点的方法类似。然而，在较佳实施例中，多于或少于两个动态向量P3、P4都可被接受。

可能动态向量P3以及P4的决定如图5流程图的步骤100以及图6流程图的步骤200所示。

候补动态向量(Candidate Motion Vectors)：

在本发明中，一旦决定了可能动态向量P1、P2、P3以及P4后，紧接着会将可能动态向量减少为两个候补动态向量C1以及C2。以上可依适当决定规则(suitable decision rule)完成，而以下将说明其中的两项。

依照第一决定规则，从可能动态向量P1、P2、P3、P4之中选取两个具有最低成本函数值的可能动态向量作为候补动态向量C1、C2。当决定可能动态向量P1、P2、P3以及P4时，因为已经决定成本函数值，所以不需要重复计算。该第一决定标准如图5的步骤102所示。

依据第二决定规则，将该相近数据块以及同位数据块得出的可能动态向量P1、P2的成本函数值与一适当临界值(threshold value)作比较。假如成本函数值都高于适当临界值时，则会摒弃可能动态向量P1、P2。之后，未被摒弃的可能动态向量P1、P2和可能动态向量P3、P4的成本函数值会作比较，因为两个可能动态向量有最低成本函数值而且被选为候补动态向量C1以及C2的动态向量。第二决定标准如图6的步骤202以及204所示。当然，仅需要决定一候补动态向量即可，但为求保险，两个动态向量的选取可降低发生局部估计值的机会。

对于不同装置来说，用来决定的参数需求也会不同，但是凡是运用本发明选取规则的方法亦应属于本发明的范畴。

进一步的交联运算与选取(Further Correlation and Selection)：

在决定候补动态向量C1以及C2后，此候补动态向量可作为任何已知搜寻方法的起始向量。举例来说，依据先前所述的三步骤方法所剩下的两步骤所示，候补动态向量C1以及C2即可作为起始向量。在执行精确的搜寻方法之后，最终得出的动态向量(resulting motion vector)的成本函数值会被比较。由于该动态向量具有最低成本函数，因此会被选为现存数据块的动态向量的动态函数。此过程就分别如同图5的步骤104、106以及图6的步骤206、208所示。

摘要(Summary)：

在实际的应用中，图3的处理器46可用来执行上述决定现存数据块的动态向量的方法。上述处理器46所能执行的方法可储存为压缩演算系统48或者储存在RAM44中。本发明的方法可通过硬件以及软件实行，上述的每一项优点要看如何在特定应用上使用。

相较于已知技术，本发明将相近数据块的动态向量、同位数据块的动态向量以及预定搜寻区域的动态向量用来决定一现存数据块的最适动态向量。也就是说，本发明的方法将一动态向量搜寻区域尽可能的扩大到预设区域之外的位置。如此一来，则本发明可在数字影像压缩的过程中得以扩大搜寻范围，以减少得出不正确的局部估计值的发生机会。

以上所述仅为本发明的较佳实施例，凡依本发明权利要求所做的均等变化与修饰，皆应属本发明专利的涵盖范围。

Claims

1.一种用来决定一现存数据帧中的现存数据块的动态向量的方法，该方法可标示出一参考数据帧内的区域，并将该参考数据帧的像素信息与该现存数据块的像素信息作交联运算，而该现存数据帧以及参考数据帧为一数字影像的一连串数据帧的一部份，该方法包含：

将该现存数据块的像素信息与该参考数据帧的像素信息作交联运算，以决定一第一成本函数值，其中该参考数据帧的像素信息是由近似于该现存数据块的数据块的第一动态向量所标示；

将该现存数据块的像素信息与该参考数据帧的像素信息作交联运算，以决定一第二成本函数值，其中该参考数据帧的像素信息是由一第二动态向量所标示，该第二动态向量是一该参考数据帧的数据块，而且在空间上的位置与该现存数据块相符；

将该现存数据块的像素信息与至少一该参考数据帧的预定区域的像素信息作交联运算，以决定至少一第三动态向量以及对应第三成本函数值；

从该第一动态向量、该第二动态向量以及该第三动态向量之中选取至少一个具有最低成本函数值的动态向量作为一候补动态向量；

将该现存数据块的像素信息与从该参考数据帧相邻的区域像素信息作交联运算，以决定精确候补动态向量以及对应的精确成本函数值，其中该区域像素信息系由该候补动态向量所标示；以及

选取具有该最低精确成本函数值的精确候补动态向量作为该现存数据块的动态向量。

2.如权利要求1所述的方法，其中该像素信息交联运算的执行，是依据绝对差的总和或者平方差的总和。

3.如权利要求1所述的方法，其中多个近似数据块作交联运算，而且从拥有该最低成本函数的近似数据块之中选取该第一动态向量以及第一成本函数值。

4.如权利要求1所述的方法，其中多个近似数据块作交联运算，而且从拥有该最低成本函数的近似数据块选取该第一动态向量以及第一成本函数值，假如该对应的平均成本函数值为该最低成本函数值，则选取该多个近似数据块的平均动态向量作为该第一动态向量。

5.如权利要求1所述的方法，其中从具有最低成本函数的该第一动态向量、该第二动态向量以及该第三动态向量之中，选取两个动态向量作为候补动态向量。

6.如权利要求5所述的方法，其中对九个预设区域进行交联运算，以决定两个第三动态向量以及对应的第三成本函数值。

7.如权利要求6所述的方法，其中该九个预设区域与该现存数据块作交联运算后，选取两个具有该最低成本函数的区域作为第三动态向量。

8.如权利要求1所述的方法，其中当该第一以及第二成本函数分别低于一预设临界值时，仅将该第一以及第二动态向量作为该候补动态向量。

9.如权利要求1所述的方法，其中执行该精确候补动态向量以及对应的精确成本函数值的步骤重复执行两次。