使用优化函数执行基于图形的预测的方法和装置

摘要

本发明提供一种用于使用图形信号执行基于图形的预测的方法，包括以下步骤：获得上下文信号；基于图形参数集来产生图形信号；基于图形信号来获得基于图形的变换矩阵，其中基于图形的变换矩阵包括本征矢量；通过使用经由优化函数计算的最佳变换矢量来获得预测矢量；以及使用预测矢量来产生预测信号，其中优化函数具有作为变量的上下文信号、图形拉普拉斯矩阵的本征值和本征矢量。

权利要求

1.一种用于使用图形信号执行基于图形的预测的方法，包括：获得上下文信号；

基于图形参数集产生图形信号；

基于所述图形信号获得基于图形的变换矩阵，其中所述基于图形的变换矩阵包括本征矢量；

使用经由优化函数计算的最佳变换矢量获得预测矢量；以及使用所述预测矢量产生预测信号，

其中，所述优化函数具有作为变量的所述本征矢量、所述上下文信号和图形拉普拉斯矩阵的本征值，其中，所述优化函数基于拉格朗日乘子被表示为无约束优化函数，并且所述无约束优化函数由M维矢量表示，其中，所述最佳变换矢量是最小化所述无约束优化函数的变换矢量。

2.根据权利要求1所述的方法，其中，基于所述最佳变换矢量和所述本征矢量的线性组合获得所述预测矢量，以及其中，基于所述图形拉普拉斯矩阵的本征值的分布，使用代价函数来确定所述变换矢量，其中，所述代价函数是所述变换矢量的凸函数，以及所述凸函数包括变换矢量分量的加权的P范数。

3.根据权利要求1所述的方法，进一步包括：基于所述图形信号计算所述图形拉普拉斯矩阵，其中，经由所述图形拉普拉斯矩阵的频谱分解获得所述基于图形的变换矩阵。

4.根据权利要求1所述的方法，

进一步包括：编码预测误差；以及

发送编码的预测误差。

5.一种用于基于图形的预测解码视频信号的方法，包括：接收包括图形参数集和残留信号的视频信号；

基于所述图形参数集获得包括本征矢量的基于图形的变换矩阵；

使用经由优化函数计算的最佳变换矢量获得预测矢量；

使用所述预测矢量产生预测信号；以及

通过累加所述预测信号和所述残留信号来重建所述视频信号，其中，所述优化函数具有作为变量的所述本征矢量、上下文信号和图形拉普拉斯矩阵的本征值，其中，所述优化函数基于拉格朗日乘子被表示为无约束优化函数，并且所述无约束优化函数由M维矢量表示，其中，所述最佳变换矢量是最小化所述无约束优化函数的变换矢量。

6.根据权利要求5所述的方法，其中，基于所述最佳变换矢量和所述本征矢量的线性组合获得所述预测矢量，以及其中，基于所述图形拉普拉斯矩阵的本征值的分布，使用代价函数确定所述最佳变换矢量，其中，所述代价函数是所述变换矢量的凸函数，以及所述凸函数包括变换矢量分量的加权的P范数。

7.根据权利要求5所述的方法，其中，经由所述图形拉普拉斯矩阵的频谱分解获得所述基于图形的变换矩阵。

8.一种用于使用图形信号来执行基于图形的预测的装置，包括：基于图形的变换单元，所述基于图形的变换单元用于基于图形参数集产生图形信号，以及基于所述图形信号获得包括本征矢量的基于图形的变换矩阵；以及预测单元，所述预测单元用于获得上下文信号，使用经由优化函数计算的最佳变换矢量获得预测矢量，以及使用所述预测矢量产生预测信号，其中，所述优化函数具有作为变量的本征矢量、上下文信号和图形拉普拉斯矩阵的本征值，其中，所述优化函数基于拉格朗日乘子被表示为无约束优化函数，并且所述无约束优化函数由M维矢量表示，其中，所述最佳变换矢量是最小化所述无约束优化函数的变换矢量。

9.根据权利要求8所述的装置，其中，基于所述最佳变换矢量和所述本征矢量的线性组合获得所述预测矢量，以及其中，基于所述图形拉普拉斯矩阵的本征值的分布，使用代价函数确定所述最佳变换矢量，其中，所述代价函数是所述变换矢量的凸函数，以及所述凸函数包括变换矢量分量的加权的P范数。

10.根据权利要求8所述的装置，其中，所述基于图形的变换单元基于所述图形信号计算所述图形拉普拉斯矩阵，其中，经由所述图形拉普拉斯矩阵的频谱分解获得所述基于图形的变换矩阵。

11.根据权利要求8所述的装置，进一步包括熵编码单元，所述熵编码单元用于编码预测误差和发送编码的预测误差。

12.一种用于基于图形的预测解码视频信号的装置，包括：熵解码单元，所述熵解码单元用于接收包括图形参数集和残留信号的视频信号；

逆变换单元，所述逆变换单元用于基于所述图形参数集获得包括本征矢量的基于图形的变换矩阵；

预测单元，所述预测单元用于使用经由优化函数计算的最佳变换矢量来获得预测矢量，以及使用所述预测矢量产生预测信号；以及重建单元，所述重建单元用于通过累加所述预测信号和所述残留信号重建所述视频信号，其中，所述优化函数具有作为变量的所述本征矢量、上下文信号和图形拉普拉斯矩阵的本征值，其中，所述优化函数基于拉格朗日乘子被表示为无约束优化函数，并且所述无约束优化函数由M维矢量表示，其中，所述最佳变换矢量是最小化所述无约束优化函数的变换矢量。

13.根据权利要求12所述的装置，其中，基于所述最佳变换矢量和所述本征矢量的线性组合获得所述预测矢量，以及其中，基于图形拉普拉斯矩阵的本征值的分布，使用代价函数确定所述最佳变换矢量，其中，所述代价函数是所述变换矢量的凸函数，以及所述凸函数包括变换矢量分量的加权的P范数。

14.根据权利要求12所述的装置，其中，经由所述图形拉普拉斯矩阵的频谱分解来获得所述基于图形的变换矩阵。

说明书

使用优化函数执行基于图形的预测的方法和装置

技术领域

[0001] 本发明涉及基于图形的信号处理方法和装置，并且更具体地，涉及用于处理供使用优化函数执行基于图形的预测的信号的方法和装置。

背景技术

[0002] 大多数传统离散时间信号处理技术已经直接地从处理和过滤模拟信号演进，并且因此，已经通过几个通用假设，类似采样和处理仅仅有规律组织的数据来约束。视频压缩的领域基本上以相同的假设为基础，但是，仅仅概括为多维信号。

[0003] 图形是在各种应用领域中用于描述数据的几何结构的有用类型的数据表示。基于图形表示的信号处理可以使用每个信号采样表示顶点的图形来概括类似采样、滤波、傅里叶变换等等的概念，并且信号关系由具有正权重的图形边缘来表示。这从其获取过程中断开信号，使得类似采样速率和序列的属性可以通过图形的属性来替换。事实上，传统的表示现在变为由一些特定图形模型定义的简单特殊情形。

发明内容

[0004] 技术问题

[0005] 所有视频编译标准包括作为基本元素之一的信号预测，并且压缩效率强烈地受到预测方法的精度和可靠性的影响。存在用于基于信号的统计模型的信号预测的许多理论工具。但是，当将该工具应用于诸如音频、图像和视频的复合信号时，存在许多实际的问题。例如，预测可靠的模型参数是非常难的。这是因为模型参数可以相对于不同的源，甚至相同的源显著地变化。重点是预测的使用在压缩中是基础，其是与其他应用重要的区别。但是，存在实际上用于压缩信号的许多的预测方法是基于试验性统计数值的问题。

[0006] 此外，已经提出用于信号处理和压缩的新图形模型。与由常规统计数字提供的模型相比较，新图形模型启用诸如边缘和中断的本地信号属性的一部分以更简单和更加恰当的方式来建模。例如，图形的拉普拉斯矩阵的频谱分辨率被以适合于用于图形模型的信号的傅里叶分析的形式提供。

[0007] 因此，本发明将提供当提供用于建模在变量之间的统计关系的图形时，用于找到具有低复杂度的更好的预测器的方法。

[0008] 技术解决方案

[0009] 本发明提供用于使用优化函数来执行基于图形的预测的方法。

[0010] 此外，本发明提供用于基于图形拉普拉斯的本征值的分布和本征矢量的线性组合来定义基于代价函数(cost function)的优化预测算法的方法。

[0011] 此外，本发明提供用于使用凸优化公式找到预测值的方法和用于利用图形特征的方法。

[0012] 有益效果

[0013] 本发明应用于其的基于图形的信号建模可以是强大的工具。特别地，本发明提供用于使用优化函数来执行基于图形的预测的优化预测算法，并且因此，预测值可以以低复杂度获得。此外，预测性能可以被改善。

[0014] 此外，本发明可应用于任意图形信号以及常规结构的图形信号，并且因此，可以避免用于编码图形信号需要的比特速率过度的开销。

[0015] 此外，本发明自适应地利用用于视频序列的其他部分信号的统计特征，从而改善压缩效率。

附图说明

[0016] 图1图示执行视频信号编码的编码器的示意性框图。

[0017] 图2图示在本发明应用于其的实施例中执行视频信号解码的解码器的示意性框图。

[0018] 图3表示按照本发明应用于其的实施例的在视频帧内用于以8×8块建模统计关系图形的示例。

[0019] 图4是本发明应用于其的实施例，并且图示由用于顶点的信号矢量和边缘加权值定义的任意图形。

[0020] 图5图示作为本发明应用于其的实施例的处理基于图形的信号的编码器的示意性框图。

[0021] 图6图示作为本发明应用于其的实施例的处理基于图形的信号的解码器的示意性框图。

[0022] 图7图示作为本发明应用于其的实施例的基于图形的变换单元的内部框图。

[0023] 图8是作为本发明应用于其的实施例的用于描述基于图形信号获得最佳预测矢量过程的流程图。

[0024] 图9是作为本发明应用于其的实施例的用于描述使用基于图形的预测解码视频信号过程的流程图。

具体实施方式

[0025] 本发明提供一种用于使用图形信号执行基于图形的预测的方法，包括：获得上下文信号；基于图形参数集来产生图形信号；基于图形信号来获得基于图形的变换矩阵，其中基于图形的变换矩阵包括本征矢量；使用经由优化函数计算的最佳变换矢量获得预测矢量；以及使用预测矢量来产生预测信号，这里优化函数具有作为变量的本征矢量、上下文信号和图形拉普拉斯矩阵的本征值。

[0026] 此外，在本发明中，基于变换矢量和本征矢量的线性组合获得预测矢量，以及基于图形拉普拉斯矩阵的本征值的分布，使用代价函数来确定变换矢量。

[0027] 此外，本发明进一步包括基于图形信号计算图形拉普拉斯矩阵，以及经由图形拉普拉斯矩阵的频谱分解来获得基于图形的变换矩阵。

[0028] 此外，在本发明中，优化函数基于拉格朗日乘子被表示为无约束优化函数，并且无约束优化函数由新的M维矢量表示。

[0029] 此外，本发明进一步包括编码预测误差；以及发送编码的预测误差。

[0030] 此外，本发明提供用于基于基于图形的预测解码视频信号的方法，包括：接收包括图形参数集和残留信号的视频信号；基于图形参数集来获得包括本征矢量的基于图形的变换矩阵；使用经由优化函数计算的最佳变换矢量来获得预测矢量；使用预测矢量来产生预测信号；以及通过累加预测信号和残留信号来重建视频信号，这里优化函数具有作为变量的本征矢量、上下文信号和图形拉普拉斯矩阵的本征值。

[0031] 此外，本发明提供用于使用图形信号执行基于图形的预测的装置，包括：基于图形的变换单元，该基于图形的变换单元用于基于图形参数集来产生图形信号，并且基于图形信号来获得包括本征矢量的基于图形的变换矩阵；以及预测单元，该预测单元用于获得上下文信号，使用经由优化函数计算的最佳变换矢量来获得预测矢量，以及使用预测矢量来产生预测信号，这里优化函数具有作为变量的本征矢量、上下文信号和图形拉普拉斯矩阵的本征值。

[0032] 此外，在本发明中，基于图形的变换单元基于图形信号来计算图形拉普拉斯矩阵，其中经由图形拉普拉斯矩阵的频谱分解获得基于图形的变换矩阵。

[0033] 此外，本发明进一步包括用于编码预测误差和发送编码的预测误差的熵编码单元。

[0034] 此外，本发明提供用于基于基于图形的预测解码视频信号的装置，包括：熵解码单元，该熵解码单元用于接收包括图形参数集和残留信号的视频信号；逆变换单元，该逆变换单元用于基于图形参数集来获得包括本征矢量的基于图形的变换矩阵；预测单元，该预测单元用于使用经由优化函数计算的最佳变换矢量来获得预测矢量，以及使用预测矢量来产生预测信号；以及重建单元，该重建单元用于通过累加预测信号和残留信号来重建视频信号，这里优化函数具有作为变量的本征矢量、上下文信号、图形拉普拉斯矩阵的本征值。

[0035] 用于发明的模式

[0036] 在下文中，参考伴随的附图来描述按照本发明的实施例示范性元件和操作，但是应当注意，参考附图描述的本发明的元件和操作被仅仅作为实施例提供，并且本发明的技术精神和核心配置和操作不受限于此。

[0037] 此外，在本说明书中使用的术语是现在广泛地使用的公用术语，但是，在特殊情形下，使用由本申请人随机地选择的术语。在这样的情况下，相应的术语的含义在相应部分的详细说明中清楚地描述。因此，应当注意，本发明不应该认为是仅仅基于在本说明书相应的描述中使用的术语的名称，并且本发明应该通过检查甚至相应的术语的含义解释。

[0038] 此外，在本说明书中提出的实施例涉及视频信号处理，但是，本发明不应该被认为是仅仅基于视频信号处理，并且将可应用于处理常规的基于图形的信号的方法。

[0039] 此外，在本说明书中使用的术语是选择以描述本发明的公用术语，但是，如果存在具有类似含义的这样的术语，可以以用于更加适宜的分析的其他术语替换。例如，信号、数据、采样、图片、帧和块可以在每个编译过程中适当地替换和解释。

[0040] 实际上，没有用于非常复杂和类似视频的各种信号的精确的统计模型。因此，本说明书以形成统计模型的概率分布f(x/y)或者f(x，y)是已经知道的假设为基础。

[0041] 视频信号的统计属性取决于视频类型或者在每个帧中显著地变化。因此，甚至在利用简单统计模型或者自动获悉的情况下，本发明在可靠地测量连续地变化的模型参数方面具有困难。此外，当模型太简单，或者参数不能反映信号的真实属性时，预测可能是不精确的。实际上，当模型复杂度增加时，预测精度变得降低。

[0042] 因此，本发明需要更加强大的方法以改善预测性能。

[0043] 关于应用于压缩的该预测的另一个重要的问题是不同于常规的统计方法，编码器可以访问要编码的所有数据。由于编码器可以发送能够改善解码器的预测的边信息(side information)，所以其可能导致非常显著的变化。例如，编码器可以编码使用的模型类型和用于该参数的边信息。

[0044] 通常地，对于视频编译方法使用的预测方法通常取决于边信息的编码，并且对于统计模型使用非常平常的假设，例如，像素复制、简单内插等等。此外，代替使用常规的统计分布，几何模型用于表示诸如边缘的视频属性。

[0045] 例如，视频编译标准对于帧内预测仅仅利用简单内插(interpolation)，其是选择的像素分布模型，或者按照33个方向的集合，在预先确定的像素值之中被选择。并且，帧间预测假定在帧之间的运动模型，并且对于次要像素运动利用内插。

[0046] 在这样的方法中的主要问题是几何模型是非常有限的，并且当前的视频编译标准充分地利用诸如直线边缘和运动变化的特征。

[0047] 同时，图形信号处理是新的方法，其概括已经用于处理信号的大多数基本技术。该图形信号处理基于几何特征概括实验技术，其能够实现在预测过程期间图像属性强大的结合。该图形信号处理可以与统计分析结合，但是，不需要导出完美的统计模型。

[0048] 很明显，用于选择适当的图形边缘加权值的方法是在所有类型的图形信号处理中的基本部分。但是，由于其不直接地与本发明相关，所以这些将不会在本说明书中详细描述。在下文中，将描述优化预测方法，其解决如上所述的统计模式、几何模型和图形模型的问题。

[0049] 图1图示执行视频信号编码的编码器的示意性框图。

[0050] 参考图1，编码器100可以包括图像分割单元110、变换单元120、量化单元130、逆量化单元140、逆变换单元150、滤波单元160、解码的图片缓存器(DPB)170、间预测单元(inter-prediction unit)180、内预测单元(intra-prediction unit)185和熵编码单元190。

[0051] 图像分割单元110将输入给编码器100的输入图像(或者图片帧)分割为一个或多个处理单元。例如，处理单元可以是编译树单元(CTU)、编译单元(CU)、预测单元(PU)或者变换单元(TU)。

[0052] 但是，这些术语仅仅为了本发明描述的方便起见使用，但是，本发明不局限于相应的术语的定义。此外，在本发明中，为了描述的便利，编译单元的术语用作在编码或者解码视频信号的过程中使用的单元，但是，本发明不受限于此，并且可以按照本发明的内容适当地解释。

[0053] 编码器100可以通过在输入图像信号中减去从间预测单元180和内预测单元185输出的预测信号来产生残留信号，并且产生的残留信号被发送给变换单元120。

[0054] 变换单元120可以通过将变换技术应用于残留信号来产生变换系数。该变换过程可以应用于具有与正方形相同大小的像素块，或者也可以应用于可变大小的块。

[0055] 作为本发明的一个实施例，该变换单元120可以使用图形参数来获得图形信号。

[0056] 作为本发明的另一个实施例，变换单元120可以使用顶点参数集和边缘参数集的至少一个来获得图形信号。

[0057] 作为本发明的另一个实施例，变换单元120可以基于优化函数来获得优化的基于图形的变换核心。在这种情况下，优化函数可以使用拉格朗日乘子被表示为无约束优化函数，并且无约束优化函数可以由新的M维矢量表示。

[0058] 作为本发明的另一个实施例，变换单元120可以使用经由优化函数计算的最佳变换矢量来获得预测矢量，并且该预测矢量可以用于产生预测信号。在这种情况下，可以基于在矩阵的本征矢量之间的线性组合和基于本征矢量分布的代价函数来获得该预测矢量。

[0059] 量化单元130可以量化变换系数，并且将其发送给编码单元190。熵编码单元190可以执行量化信号的熵编译，并且将其作为比特流输出。

[0060] 从量化单元130输出的量化信号可以用于产生预测信号。例如，量化信号可以经由在环路中的逆量化单元140和逆变换单元150，通过应用逆量化和逆变换来重建残留信号。通过将重建的残留信号增加给从间预测单元180或者内预测单元185输出的预测信号，可以产生重建的信号。

[0061] 同时，在压缩过程中，邻近块通过不同的量化参数来量化，并且因此，可能存在块边缘示出的伪影。该现象被称作块伪影(artifact)，其是用于评估图像质量的主要因素之一。为了降低该伪影，可以执行滤波处理。经由该滤波处理，块伪影可以被去除，并且同时，用于当前的图片的误差被降低，从而改善图像质量。

[0062] 滤波单元160将滤波应用于重建的信号，并且将滤波的信号输出给回放设备，或者将滤波的信号发送给DPB 170。发送给DPB 170的滤波的信号可以在间预测单元180中用作参考图片。因而，图片质量和编码效率这两者可以以间预测模式使用滤波的图片作为参考图片来改善。

[0063] DPB 170可以存储滤波的图片，以便在间预测单元180中作为参考图片使用滤波的图片。

[0064] 间预测单元180参考重建的图片来执行时间预测和/或空间预测，以便去除时间冗余和/或空间冗余。在这种情况下，用于执行预测的参考图片可以包括块伪影或者环形伪影，因为当参考图片被事先编码或者解码时，其是已经以块为单位量化或者逆量化信号。

[0065] 因此，为了解决这样的信号的中断或者由于信号的量化的性能恶化，间预测单元180可以使用低通滤波器以子像素为单位在像素之间内插信号。在这种情况下，子像素指的是通过将内插滤波应用于子像素产生的虚拟像素，并且整体像素指的是存在于重建的图片之中的实际像素。内插方法可以包括线性内插、双线性内插和维纳(wiener)滤波器。

[0066] 内插滤波可以应用于重建的图片以便改善预测的精度。例如，间预测单元180可以通过将内插滤波器应用于整个像素来产生内插像素，并且将包括内插的像素的内插块作为预测块使用来执行预测。

[0067] 内预测单元185可以参考邻近将要编码的块的采样预测当前块。内预测单元185可以执行以下的处理以便执行内预测。首先，可以准备产生预测信号需要的参考采样。此外，预测信号可以使用准备的参考采样来产生。此后，预测模式被编译。在这种情况下，参考采样可以经由参考采样填充和/或参考采样滤波来准备。参考采样可以包括量化误差，因为其经历预测和重建处理。因此，为了降低这样的误差，可以对在内预测中使用的每个预测模式来执行参考采样滤波处理。

[0068] 经由间预测单元180或者内预测单元185产生的预测信号可以用于产生重建的信号，或者可用于产生残留信号。

[0069] 图2图示在本发明应用于其的实施例中执行视频信号解码的解码器的示意性框图。

[0070] 参考图2，解码器200可以包括熵解码单元210、逆量化单元220、逆变换单元230、滤波单元240、DPB 250、间预测单元260和内预测单元265。

[0071] 经由解码器200输出的重建的视频信号可以在回放装置上播放。

[0072] 解码器200可以接收由图1示出的编码器100输出的信号。接收的信号可以经由熵解码单元210来经历熵解码。在这种情况下，该输出信号可以包括图形参数集和预测矢量信息。可以基于在图形拉普拉斯矩阵的本征矢量之间的线性组合和基于本征矢量分布的代价函数来确定该预测矢量信息。

[0073] 作为另一个示例，可以基于图形拉普拉斯矩阵的本征值和具有作为变量的本征矢量的优化函数来确定预测矢量信息。在这种情况下，优化函数可以使用拉格朗日乘子被表示为无约束优化函数，并且无约束优化函数可以由新的M维矢量表示。

[0074] 解码器200可以基于预测矢量信息来产生预测信号。这个过程可以在间预测单元260中执行，但是，本发明不受限于此。

[0075] 逆量化单元220使用有关量化级大小的信息从熵解码的信号中获得变换系数。获得的变换系数可以是在以上图1示出的变换单元120中描述的各种实施例应用的变换系数。

[0076] 逆变换单元230通过逆变换该变换系数来获得残留信号。

[0077] 通过将获得的残留信号增加给由间预测单元260或者内预测单元265输出的预测信号来产生重建的信号。

[0078] 滤波单元240将滤波应用于重建的信号，并且将其输出给显示装置或者DPB 250。发送给DPB 250的滤波的信号可以在间预测单元260中用作参考图片。

[0079] 在本说明书中，对于编码器100的滤波单元160、间预测单元180和内预测单元185描述的实施例可以分别地同等地应用于解码器的滤波单元240、间预测单元260和内预测单元265。

[0080] 图3表示按照本发明应用于其的实施例的用于在视频帧内以8×8块建模统计关系图形的示例。

[0081] 图3示出定义为图像像素的正方形块的图形的示例。

[0082] 参考图3，本发明提供可以用于处理在图像或者视频中8×8像素块的图形类型的二个示例。每个像素与图形顶点有关，并且像素值变为图形顶点值。

[0083] 图形边缘可以指的是连接图形顶点的线。该图形边缘被用于以表示其强度的正权重来表示在该信号中统计相关的某个形式。例如，每个顶点可以连接到每个其他顶点，并且零权重被分配给连接顶点(其是无关或者微弱地相关的)的边缘。但是，为了简化表示，具有零权重的边缘可以被完全地去除。

[0084] 在本发明的另一个实施例中，连接图形顶点的边缘可以按照信号特征来预置。例如，顶点可以被安排在用于音频信号的1-D阵列、用于图像的2-D阵列和用于视频帧的3-D阵列。在这种情况下，时间轴可以用作第三维。例如，在图3(a)的图形中，图形边缘可以被定义为将每个顶点连接到其最近的邻居中的四个。但是，在块边缘上图形边缘可以被不同地定义。此外，在图3(b)的图形中，它们被连接到八个最近的邻近。

[0085] 同时，本发明可以应用于任何图形配置。

[0086] 图形信号G的拉普拉斯矩阵如以下的等式1表示。

[0087] [等式1]

[0088] L＝D-A

[0089] 在此处，D表示度矩阵(degree matrix)。例如，度矩阵可以指的是包括每个顶点度数信息的对角矩阵。A表示相邻矩阵，其通过加权值表示与邻近像素的互连(边缘)。

[0090] 定义图形G和矩阵的方法在本说明书中没有详细描述。在本说明书中，仅假设图形由使用通过图形类型定义的信号特征的几个技术定义。因此，按照本发明，当通过使用矩阵D和A执行信号建模来产生图形时，可以经由如由以下的等式2表示的本征分解过程来产生变换核心U。

[0091] [等式2]

[0092] L＝UΛUT

[0093] 在此处，A表示图形拉普拉斯矩阵的本征值，并且U表示可以是基于图形的变换矩阵的本征矢量。L表示图形拉普拉斯矩阵。

[0094] 基于图形的变换矩阵U的列可以包括图形拉普拉斯矩阵L的本征矢量。对应于对角矩阵的图形拉普拉斯矩阵L的本征值可以由以下的等式3表示。

[0095] [等式3]

[0096] Λ＝diag(λ)

[0097] 通常地，本征矢量没有定义为特定的形状。但是，按照本发明的目的，由于图形拉普拉斯矩阵L是对称的，所有本征矢量是实值，并且分解的至少一个可能存在。在图形信号G中，信号矢量g的基于图形的傅里叶变换可以定义为以下的等式4。

[0098] [等式4]

[0099] h＝UTg＝Tg

[0100] 在此处，h表示变换矢量，UT表示基于图形的变换矩阵U的转置矩阵，并且g表示图形信号G的矢量。

[0101] 基于如上所述对于图形信号的基本定义，本发明的实施例将在下面详细描述。

[0102] 图4是本发明应用于其的实施例，并且图示由用于顶点的信号矢量和边缘加权值定义的任意图形。

[0103] 在本发明的一个实施例中，提供了用于由任意图形G定义的信号的方法。例如，图形信号可以由每个图形顶点定义，并且可以由G维矢量g表示。可以由在每个图形边缘上非负加权值来定义图形特征。

[0104] 图4图示任意图形，其具有由在顶点中定义的信号矢量和非负边缘加权值定义的图形特征。在这里，顶点值可以被划分为两组，并且两组可以指的是要预测的信号x和上下文信号y。在以上的图4中，x1、x2、…、x6表示要预测的信号，并且y1、y2、…、y5表示上下文信号。例如，如以下的图5所示，要预测的信号x可以指的是原始信号，并且上下文信号y可以指的是按照环路重建的信号。

[0105] 如参考图4描述的，假设在图形模型中，在本发明将从上下文信号y预测信号x，x和y可以形成信号g。

[0106] 按照矢量标记，本发明可以分解如在等式5中表示的图形信号g。

[0107] [等式5]

[0108]

[0109] 在此处，g表示图形信号，x表示要预测的信号，并且y表示上下文信号。

[0110] 同时，基于图形的变换矩阵T可以由以下的等式6表示。

[0111] [等式6]

[0112] T＝[A M]

[0113] 在这里，T表示基于图形的变换矩阵。A和M分别地表示矩阵。

[0114] 并且，以上的等式4可以基于以上的等式5和等式6改写为以下的等式7。

[0115] [等式7]

[0116]

[0117] 在此处，h具有G(＝M+N)的维度。

[0118] 同时，由于TT＝T-1，以上的等式7可以改写为等式8。

[0119] [等式8]

[0120]

[0121] 在这种情况下，满足等式9的条件。

[0122] [等式9]

[0123] ATA＝I.

[0124] MTM＝I.

[0125] ATM＝0

[0126] 在此处，I和0表示对应于每个矩阵积的维度的单位矩阵和零矩阵。

[0127] 基于该定义，本发明的一个实施例将在下面更详细描述。

[0128] 图5图示作为本发明应用于其的实施例的处理基于图形的信号的编码器的示意性框图。

[0129] 参考图5，本发明应用于其的编码器500包括基于图形的变换单元510、量化单元520、逆量化单元530、逆变换单元540、缓存器550、预测单元560和熵编码单元570。

[0130] 编码器500接收视频信号，并且通过从视频信号中减去从预测单元560输出的预测信号来产生预测误差。产生的预测误差被发送给基于图形的变换单元510，并且基于图形的变换单元510将变换方案应用于预测误差，从而产生变换系数。在这种情况下，基于图形的变换单元510可以计算基于图形的变换矩阵，并且可以使用其执行变换。此外，基于图形的变换单元510可以执行在本说明书中描述的实施例。

[0131] 作为本发明的另一个实施例，基于图形的变换单元510可以基于优化函数来获得优化的基于图形的变换核心。在这种情况下，优化函数可以使用拉格朗日乘子被表示为无约束优化函数，并且无约束优化函数可以由新的M维矢量表示。

[0132] 此外，基于图形的变换单元510可以使用经由优化函数计算的最佳变换矢量获得预测矢量，并且该预测矢量可以用于产生预测信号。在这种情况下，可以基于在图形拉普拉斯矩阵的本征值之间的线性组合和基于本征值分布的代价函数来获得预测矢量。

[0133] 该获得的预测矢量可以被发送给逆变换单元540，并且可以被逆变换，并且该逆变换的预测矢量可以被发送给预测单元560，并且用于产生预测信号。此外，该预测矢量可以被发送给熵编码单元570和被编码。

[0134] 基于图形的变换单元510的实施例可以通过被包括在图1示出的变换单元120中执行，或者可以作为单独的功能块执行。并且，所描述的是本发明应用于其的预测方法也在基于图形的变换单元510中执行，但是，本发明不受限于此。例如，本发明应用于其的预测方法可以作为单独的功能块执行，或者由间预测单元180/预测单元560执行。

[0135] 在下文中，将更详细描述本发明应用于其的预测方法的实施例。

[0136] 基于图形的预测

[0137] 为了定义图形的傅里叶变换，本发明可以由对应于G(W)的度矩阵来表示。在这里，度矩阵是包括每个顶点度数信息的对角矩阵，并且可以如以下的等式10定义。例如，度数可以指的是连接到顶点的侧面的数目。

[0138] [等式10]

[0139]

[0140] 图形拉普拉斯矩阵L＝D-W，并且因此，图形拉普拉斯矩阵Li,j如以下的等式11表示。

[0141] [等式11]

[0142]

[0143] 在这种情况下，当矩阵T是图形傅里叶变换时，矩阵T如以下的等式12表示。

[0144] [等式12]

[0145] T(W)＝UT

[0146] 在此处，U表示对角化L的本征矩阵，并且L如以下的等式13表示。

[0147] [等式13]

[0148] L＝UΛU-1＝UΛUT

[0149] 并且，正交矩阵满足以下的等式14。

[0150] [等式14]

[0151] UT＝U-1

[0152] 基于以上的定义，本征矩阵U的列包括L的本征矢量，并且L的本征值可以如以下的等式15表示。

[0153] [等式15]

[0154] Λ＝diag(λ)，

[0155] 通常地，本征矢量没有定义为特定的形状。但是，按照本发明的一个目的，由于L是对称的，应该认为所有本征矢量是实值，并且分解的至少一个可能存在。这可以应用于满足等式14的任何矩阵。

[0156] 随机信号的预测是经典统计的问题。作为常规的方案，在本发明中，矢量函数可以如等式16定义。

[0157] [等式16]

[0158]

[0159] 在此处，当给出N维的矢量y时，p(y)表示M维随机矢量的预测值。

[0160] 假设条件概率分布f(x/y)是已知的，按照本发明，最佳预测函数p*(y)可以经由如等式17表示的优化函数找到。

[0161] [等式17]

[0162]

[0163] 在此处，当给出N维矢量y时，p*(y)表示最佳预测函数，x表示原始信号，并且p(y)表示M维随机矢量的预测值。并且，Ex|y{·}表示条件期望算符。

[0164] 并且，等式18表示测量预测误差的函数。

[0165] [等式18]

[0166]

[0167] 例如，当D测量欧几里德(Euclidean)距离时，本发明具有如等式19表示的最小均方误差问题。

[0168] [公式19]

[0169]

[0170] 在此处，当给出N维矢量y时，p*(y)表示最佳预测函数，x表示原始信号，并且p(y)表示M维随机矢量的预测值。

[0171] 在这种情况下，最佳预测器可以被表示为下面的等式20。

[0172] [等式20]

[0173] P*(y)＝E{x|y}

[0174] 在诸如应用线性预测的特殊情形的情形下，本发明可以由等式21表示。

[0175] [等式21]

[0176] p(y)＝Py

[0177] 在此处，P表示MxN矩阵，并且y表示N维矢量。

[0178] 用于均方误差测量的最佳线性预测器矩阵可以如以下的等式22来计算。

[0179] [等式22]

[0180] P＝E{xyT}(E{yyT})-1

[0181] 此外，为了描述本发明应用于其的预测算法，所需要的是进一步假设目标函数的定义。

[0182] [等式23]

[0183]

[0184] 在等式23中，Ω(h，λ)使用图形拉普拉斯本征值λ的矢量，以便测量如何“不可能”是变换h。最小化该函数的变换矢量h对应于更多的概率信号。

[0185] 本发明不采用统计模型的实际理论，但是，基于经验观测值，与更大本征值相对应的高频分量典型地具有更小的幅值。

[0186] 按照该定义，本发明提供用于分解基于图形的预测的方法。也就是说，为了从x预测y，可以使用图形信号G。这沿用以下的过程。

[0187] 第一，可以确定图形信号G的边缘加权值，并且可以计算图形拉普拉斯矩阵L。

[0188] 第二，为了确定具有变换矩阵T和本征值λ的矢量，可以执行图形拉普拉斯矩阵L的频谱分解。

[0189] 第三，基于频谱分解的结果，最佳变换矢量h*(y)可以如由等式24表示的那样来获得。

[0190] [等式24]

[0191]

[0192] 第四，基于使用以上的等式24的等式25，可以获得预测矢量p(y)。

[0193] [等式25]

[0194] p(y)＝MTh*(y)

[0195] 作为本发明的另一个实施例，其也可用于预先确定图形加权值集合。因此，对于所有预测矢量，相对于拉普拉斯计算和变换矩阵计算的第一步骤和第二步骤可以不必重复。

[0196] 基于图形的变换优化

[0197] 在本发明的基于图形的预测算法中，为了找到对以下的等式26的优化问题更加有效率的解决方案，可以使用几个特殊特征。

[0198] [等式26]

[0199]

[0200] s.t.ATh＝y

[0201] 在这里，Ω(h，λ)表示用于测量如何不可能是变换h的目标函数，并且λ矢量表示图形拉普拉斯本征值。并且，“s.t.”是“受制于”的缩写，并且表示其遵循用于优化函数的约束公式。在Ω(h，λ)是连续的并且可区分的情形下，本发明可以使用由矢量s表示的一组拉格朗日乘数，并且可以解由以下的等式27定义的公式系统。

[0202] [等式27]

[0203]

[0204] ATh＝y

[0205] 但是，由于矩阵A和M产生正交子空间，本发明可以定义M维矢量z，并且可以使用以下的等式28来获得等式29。

[0206] [等式28]

[0207] h＝Ay+Mz

[0208] [等式29]

[0209] ATh＝ATAy+ATMz＝y，

[0210] 并且，通过解决以下的等式30的无约束优化问题，可以获得等式31。

[0211] [等式30]

[0212]

[0213] [等式31]

[0214] h*(y)＝Ay+Mz*(y)

[0215] 经由基于图形的变换优化过程，可以获得优化的变换矢量。

[0216] 二次目标函数的定义

[0217] 按照本发明，如由以下的等式32表示的目标函数可以定义为二次函数。

[0218] [等式32]

[0219] Ω(h，λ)＝hTW(λ)h

[0220] 在此处，W是基于λ的半正矩阵。例如，W可以简要地如在等式33中表示的那样被定义。

[0221] [等式33]

[0222] W(λ)＝diag(λ)

[0223] 为了简化该表示，本发明基于λ隐含地考虑矩阵W的相关性，并且可以分析以下的等式34的解答。

[0224] [等式34]

[0225]

[0226] s.t.ATh＝y

[0227] 拉格朗日乘子可以用于找到最佳解。在二次目标函数的情况下，在以上的等式27中定义的所有数学表示是线性的，并且本发明可以具有如在以下的等式35中表示的矩阵形状。

[0228] [等式35]

[0229]

[0230] 当W不是单个形式时，W可以表示为以下的等式36和等式37。

[0231] [等式36]

[0232] h＝W-1As.

[0233] [等式37]

[0234] s＝(ATW-1A)-1y.

[0235] 通过相对于h解该等式，本发明可以获得以下的等式38，并且预测值如在等式39中表示。

[0236] [等式38]

[0237] h*＝W-1A(ATW-1A)-1y

[0238] [等式39]

[0239] p(y)＝MTh*＝MTW-1A(ATW-1A)-1y

[0240] 作为本发明的另一个实施例，W是单个的情形可以描述如下。与用于二次目标函数相对应的等式30的版本如在等式40中那样被表示。

[0241] [等式40]

[0242]

[0243] 最佳解可以被定义为以下的等式41和等式42，并且因此，获得等式43。

[0244] [等式41]

[0245] z*＝-(MTWM)-1MTWAy

[0246] [等式42]

[0247] h*＝Ay-M(MTWM)-1MTWAy.

[0248] [等式43]

[0249] p(y)＝MTh*＝-(MTWM)-1MTWAy

[0250] 作为本发明应用于其的另一个实施例，提供选择用于选择最佳变换矢量的目标函数的另一方法。例如，二次函数可以是如在以下的等式44中表示的凸函数的特殊情形。

[0251] [等式44]

[0252]

[0253] 在此处，ωk(λk)是非零的加权值，并且αk≥1定义用于大的变换值的不利结果的相对增加。这样的参数可以被选择，使得概率的系数不具有小的值。

[0254] 同时，量化单元520量化经由该过程产生的变换系数，并且将量化的系数发送给熵编码单元570。

[0255] 熵编码单元570对于量化信号执行熵编译，并且输出熵编译的信号。

[0256] 从量化单元520输出的量化信号可以用于产生预测信号。例如，在编码器500的环路中的逆量化单元530和逆变换单元540可以对量化信号执行逆量化和逆变换，使得量化信号被以预测误差重建。可以通过将重建的预测误差增加给由预测单元560输出的预测信号来产生重建的信号。

[0257] 缓存器550存储用于未来参考的重建的信号。

[0258] 预测单元560可以使用在缓存器550中存储的信号来产生预测信号。在这种情况下，本发明涉及有效率地使用在锚定图像内的区域来预测在目标图像内的区域。在此处，锚定图像可以指的是参考图像、参考图片或者参考帧。效率可以通过评估均方差来确定，该均方差量化速率失真成本或者在预测误差内的失真。

[0259] 本发明提出用于区别在图形内的顶点和边缘以及编码或者解码残留信号的方法。例如，按照本发明的实施例，各种实施例可以经由基于图形的变换单元510来执行。基于图形的变换单元510可以被包括在编码器500或者解码器700中。

[0260] 图6图示作为本发明应用于其的实施例的处理基于图形的信号的解码器的示意性框图。

[0261] 在图6中示出的解码器600接收从编码器500输出的信号。在这种情况下，该输出信号可以包括图形参数集和残留信号。基于该图形参数集，可以获得基于图形的变换矩阵，并且基于图形的变换矩阵可以包括本征矢量。并且，可以使用最佳变换矢量来获得预测矢量，并且最佳变换矢量可以经由优化函数来计算。在这种情况下，可以基于变换矢量和本征矢量的线性组合来获得预测矢量，并且可以基于图形拉普拉斯函数的本征值的分布，使用代价函数来确定变换矢量。

[0262] 同时，优化函数可以使用拉格朗日乘子被表示为无约束优化函数，并且无约束优化函数可以由新的M维矢量表示。

[0263] 解码器600可以基于预测矢量信息来产生预测信号。这个过程可以在预测单元650中执行，但是本发明不受限于此。

[0264] 熵解码单元610执行用于接收信号的熵解码。逆量化单元620基于量化步长的信息从熵解码的信号中获得变换系数。

[0265] 逆变换单元630通过对变换系数执行逆变换来获得预测误差。在这种情况下，逆变换可以指的是对从编码器500中获得的基于图形的变换的逆变换。

[0266] 通过将获得的预测误差增加给从预测单元650输出的预测信号来产生重建的信号，其在重建单元(未示出)中执行。

[0267] 缓存器640存储用于预测单元650的未来参考的重建的信号。

[0268] 预测单元650基于被事先重建的在缓存器640中存储的信号和本发明应用于其的预测矢量来产生预测信号。

[0269] 在本发明中，基于图形参数获得的基于图形的变换可以在编码器500或者解码器600中被使用。

[0270] 图7图示作为本发明应用于其的实施例的基于图形的变换单元的内部框图。

[0271] 参考图7，基于图形的变换单元510可以包括图形参数提取单元511、图形信号产生单元512、基于图形的变换计算单元513、变换执行单元514、变换优化单元515和基于图形的预测单元516。但是，本发明不受限于此。在基于图形的变换单元510中的功能单元的每个可以作为单独的功能单元操作，或者可以通过包括在其他功能单元中操作。

[0272] 图形参数提取单元511可以在与残留信号的目标单元相对应的图形内提取图形参数。例如，该图形参数可以包括顶点参数和边缘参数中的至少一个。顶点参数可以包括顶点位置和顶点编号中的至少一个，并且边缘参数可以包括边缘加权值和边缘加权值编号中的至少一个。此外，图形参数可以被定义为预先确定的数字的集合。

[0273] 图形信号产生单元512可以基于从图形参数提取单元511提取的图形参数来产生图形信号。在这种情况下，可以从图形信号来计算图形拉普拉斯矩阵。

[0274] 基于图形的变换计算单元513可以基于图形参数或者图形参数集来获得基于图形的变换矩阵。在这种情况下，基于图形的变换矩阵可以包括本征矢量。

[0275] 此外，基于图形的变换计算单元513可以基于图形参数或者图形参数集来计算图形拉普拉斯矩阵。在这种情况下，可以经由图形拉普拉斯矩阵的频谱分解来获得基于图形的变换矩阵。

[0276] 变换执行单元514可以使用基于图形的变换矩阵来执行变换。

[0277] 变换优化单元515可以经由优化函数来计算最佳变换矢量。在此处，优化函数可以使用拉格朗日乘子被表示为无约束优化函数，并且无约束优化函数可以由新的M维矢量表示。例如，以上的等式24或者等式34可以用于优化函数，并且可以使用以上的等式18、等式25或者等式36来获得最佳变换矢量。

[0278] 基于图形的预测单元516可以使用计算的最佳变换矢量来获得预测矢量。可以基于变换矢量和本征矢量的线性组合来获得预测矢量，并且可以基于图形拉普拉斯矩阵的本征值的分布，使用成本矩阵来确定变换矢量。例如，预测矢量可以使用以上的等式19或者等式37来获得。

[0279] 此外，该预测矢量可以被编码和发送给解码器，或者从解码器导出。作为传输方法，矢量值或者矢量差值可以被发送，但是，本发明不受限于此。

[0280] 图8是作为本发明应用于其的实施例的用于描述基于图形信号来获得最佳预测矢量过程的流程图。

[0281] 编码器可以从接收的视频信号来产生预测信号，并且可以通过从视频信号减去预测信号来产生残留信号。对残留信号执行变换，并且在这种情况下，通过应用基于图形的信号处理技术，可以执行基于图形的变换或者基于图形的预测。在下文中，将基于图形信号来描述用于执行基于图形的预测的方法。

[0282] 首先，编码器可以确定图形参数集，其对应于视频信号的目标单元(步骤S810)。例如，图形信号G的顶点参数和边缘加权值中的至少一个可以确定。

[0283] 并且，编码器可以基于图形参数集来产生图形信号，并且可以基于该图形信号来计算图形拉普拉斯矩阵L(步骤S820)。

[0284] 编码器可以执行图形拉普拉斯矩阵L的频谱分解，以便确定变换矩阵T和具有本征值λ的矢量，并且可以基于频谱分解的结果来获得基于图形的变换矩阵(步骤S830)。在这种情况下，基于图形的变换矩阵可以包括本征矢量。

[0285] 编码器可以经由优化函数来获得最佳变换矢量(步骤S840)。在这种情况下，以上的等式24或者等式34可以被用于优化函数，并且最佳变换矢量可以使用以上的等式18、等式25和等式36来获得。在此处，优化函数可以具有作为变量的图形拉普拉斯矩阵的本征矢量、本征值和上下文信号。并且，优化函数可以基于拉格朗日乘子被表示为无约束优化函数，并且无约束优化函数可以由新的M维矢量表示。

[0286] 并且，编码器可以使用最佳变换矢量来计算预测矢量(步骤S850)。在这里，可以基于变换矢量和本征矢量的线性组合来获得预测矢量，并且可以基于图形拉普拉斯矩阵的本征值的分布，使用成本矩阵来确定变换矢量。例如，以上的等式19或者等式37可以作为预测函数被使用。

[0287] 同时，计算的预测矢量可以用于产生预测信号。或者，作为另一个示例，该预测矢量可以被编码，并且发送给解码器，或者在解码器中导出。

[0288] 图9是作为本发明应用于其的实施例的用于描述使用基于图形的预测解码视频信号过程的流程图。

[0289] 本发明应用于其的解码器可以接收包括图形参数集和残留信号的视频信号(步骤S910)。

[0290] 并且，基于该图形参数集，可以获得基于图形的变换矩阵(步骤S920)。使用获得的基于图形的变换矩阵，可以重建该残留信号(步骤S930)。

[0291] 同时，解码器可以经由优化函数来计算最佳变换矢量(步骤S940)。在这种情况下，优化函数可以具有作为变量的图形拉普拉斯矩阵的本征矢量、本征值和上下文信号。并且，优化函数可以基于拉格朗日乘子被表示为无约束优化函数，并且无约束优化函数可以由新的M维矢量表示。

[0292] 编码器可以使用最佳变换矢量来获得预测矢量(步骤S950)。这个过程可以在解码器的预测单元或者逆变换单元中执行。可以基于变换矢量和本征矢量的线性组合来获得预测矢量，并且可以基于图形拉普拉斯矩阵的本征值的分布，使用成本矩阵来确定变换矢量。

[0293] 并且，解码器可以基于预测矢量来产生预测信号(步骤S960)。

[0294] 解码器可以通过累加产生的预测信号和残留信号来重建视频信号(步骤S970)。

[0295] 因而，本发明提供用于使用优化函数来执行基于图形的预测的优化预测算法，并且因此，预测值可以以低复杂度获得。此外，预测性能可以被改善。

[0296] 如上所述，在本发明中解释的实施例可以在处理器、微处理器、控制器或者芯片上实现和执行。例如，在图1、2、5、6和7中解释的功能单元可以在计算机、处理器、微处理器、控制器或者芯片上实现和执行。

[0297] 如上所述，本发明应用于其的解码器和编码器可以被包括在多媒体广播传输/接收装置、移动通信终端、家庭影院视频装置、数字影院视频装置、监视照相机、视频聊天装置、诸如视频通信的实时通信装置、移动流装置、存储介质、摄录一体机、VoD服务提供装置、因特网流服务提供装置、三维(3D)视频装置、电话会议视频装置和医学视频装置中，并且可用于编译视频信号和数据信号。

[0298] 此外，本发明应用于其的解码/编码方法可以以由计算机执行，并且可以存储在计算机可读的记录介质中的程序的形式来生成。具有按照本发明的数据结构的多媒体数据也可以被存储在计算机可读的记录介质中。计算机可读的记录介质包括由计算机系统可读的数据存储在其中的所有类型的存储设备。计算机可读的记录介质例如可以包括BD、USB、ROM、RAM、CD-ROM、磁带、软盘和光数据存储设备。此外，计算机可读的记录介质包括以载波(例如，经由因特网传输)的形式实现的介质。此外，由编码方法产生的比特流可以被存储在计算机可读的记录介质中，或者可以经有线/无线通信网络发送。

[0299] 工业实用性

[0300] 为了说明性的目的已经公开了本发明示范性实施例，并且本领域技术人员可以在附加权利要求中公开的本发明的技术精神和范围内改进、变化、替换或者增加各种其他实施例。