一种基于多线性增广拉格朗日乘子法的张量数据恢复方法

摘要

本发明公开了一种基于多线性增广拉格朗日乘子法的张量数据恢复方法，包括：根据受污染的高维数据的结构和多模式特性构建张量模型；根据张量模型构建包括低秩项和稀疏项且具有约束条件的第一目标函数；将第一目标函数转换成不包括松弛项且具有不同约束条件的第二目标函数，第二目标函数包括分别涉及低秩项和稀疏项的第一项和第二项；对第二目标函数进行优化然后利用多线性增广拉格朗日乘子法去约束得到第三目标函数；求解第三目标函数得到真实数据和污染数据。本发明通过对目标函数进行转换加之改变其约束条件并采用多线性增广拉格朗日乘子法去约束，提高了张量恢复精度并降低了计算复杂度。

权利要求

1.一种基于多线性增广拉格朗日乘子法的张量数据恢复方法，其特征在于，所述方法包括：根据受污染的高维数据的结构和多模式特性构建张量模型；

根据所述张量模型构建用于张量恢复的第一目标函数，其中，所述第一目标函数包括低秩项和稀疏项，所述低秩项和所述稀疏项分别表示所述高维数据中的真实数据和污染数据；

将所述第一目标函数转换成不包括松弛项的第二目标函数，其中，所述第二目标函数具有第二约束条件，并且其中，所述第二目标函数包括最小化所述低秩项沿所述各个模式展开所得矩阵的秩的第一项，所述第二目标函数还包括涉及所述稀疏项的第二项，所述第一项与所述第二项在所述第二目标函数中求加权和；

对所述第二目标函数进行优化，并且利用多线性增广拉格朗日乘子法对优化后的第二目标函数进行去约束得到第三目标函数；

求解所述第三目标函数，得到所述真实数据和所述污染数据。

2.根据权利要求1所述的一种基于多线性增广拉格朗日乘子法的张量数据恢复方法，其特征在于，所述第一目标函数具有第一约束条件，并且所述第一目标函数还包括最小化所述低秩项在所述多模式的各个模式中的秩的加权和的项。

3.根据权利要求2所述的一种基于多线性增广拉格朗日乘子法的张量数据恢复方法，其特征在于，所述第一目标函数为：其中， 表示待重建数据的张量，表示低秩部分的张量，表示稀疏部分的张量，λi为所述各个模式的权重参数，η为调整参数， 表示 在第i模式中的秩，||·||0表示

0范数， 为所述第一约束条件。

4.根据权利要求1所述的一种基于多线性增广拉格朗日乘子法的张量数据恢复方法，其特征在于，所述第二目标函数为：s.tL(n)+S(n)＝A(n)

其中，A(n)，L(n)和S(n)分别是 和S沿第n模式展开所得矩阵，rank(L(n))为L(n)的秩，λn为各个模式的调整参数，αn为所述各个模式的权重参数，s.t.L(n)+S(n)＝A(n)为所述第二约束条件。

5.根据权利要求1所述的一种基于多线性增广拉格朗日乘子法的张量数据恢复方法，其特征在于，所述稀疏项的第二项是所述稀疏项沿所述各个模式展开所得矩阵的0范数，所述优化包括：用所述低秩项沿所述各个模式展开所得矩阵的最小化迹范数来代替最小化所述低秩项沿所述各个模式展开所得矩阵的秩，并且用1范数代替所述0范数，得到替换后的目标函数；

在所述替换后的目标函数的基础上得到针对所述各个模式的第二目标函数。

6.根据权利要求5所述的一种基于多线性增广拉格朗日乘子法的张量数据恢复方法，其特征在于，所述替换后的函数为：s.t.L(n)+S(n)＝A(n)

其中，||·||*表示最小迹范数，||·||1表示1范数。

7.根据权利要求1所述的一种基于多线性增广拉格朗日乘子法的张量数据恢复方法，其特征在于，所述第二目标函数为：s.t.L(n)+S(n)＝A(n)。

8.根据权利要求1所述的一种基于多线性增广拉格朗日乘子法的张量数据恢复方法，其特征在于，所述第三目标函数为：

9.根据权利要求1所述的一种基于多线性增广拉格朗日乘子法的张量数据恢复方法，其特征在于，所述通过对所述第三目标函数求解得到所述真实数据和所述污染数据的步骤包括：利用交替方向乘子法对所述第三目标函数进行迭代求解，在达到预先的收敛条件的情况下得到所述真实数据和所述污染数据。

10.根据权利要求9所述的一种基于多线性增广拉格朗日乘子法的张量数据恢复方法，其特征在于，所述迭代求解中的每次迭代包括：分别计算所述低秩项的各个模式的展开矩阵，并且分别计算稀疏部分的各个模式的展开矩阵；

将计算得出的所述低秩项与所述稀疏项的展开矩阵沿所述各个模式重新构建成所述低秩项代表的张量和所述稀疏项代表的张量；

通过分别对所述低秩项代表的张量和所述稀疏项代表的张量进行加权平均得到所述真实数据和污染数据。

说明书

一种基于多线性增广拉格朗日乘子法的张量数据恢复方法

技术领域

[0001] 本发明属于图像恢复领域，具体涉及一种基于多线性增广拉格朗日乘子法的张量数据恢复方法。

背景技术

[0002] 在计算机视觉、智能交通系统以及脑信号处理等多个领域中，大部分数据都以天然的多模式结构存在，例如图像的三通道结构；另外，还有部分数据也能够整合成多模式结构，例如不同光照下的人脸图。在这些领域中，都存在着多模式数据的处理问题。张量是矩阵在高阶的推广，具有天然的高维结构，能够很好地表征数据的多模式特性。有鉴于此，近年来，针对多模式数据处理问题，通常通过张量来表征这些多模式数据。进一步，根据不同的应用需求，提取出这些数据中的低秩结构(例如图像压缩)或稀疏结构(例如前景检测)。

[0003] 张量恢复是张量结构数据处理中的一个重要组成部分，它能够分离张量的低秩部分与稀疏部分，其中，低秩部分代表去噪数据，而稀疏部分代表噪音污染。张量恢复的目标旨在去除数据中因各种原因导致的数据异常或数据噪音，最终提取出其低秩部分，使数据更加精准。张量恢复最常用的方法是基于张量分解的张量恢复方法，当数据噪音比较少且这些稀疏噪音服从独立同分布时，基于张量分解的张量恢复算法能取得比较好的效果。但当噪音污染较多时，该张量恢复方法则不能达到相应的效果。

[0004] 近年来，大量学者研究了基于二维张量(即矩阵)的低秩和稀疏分解方法。通过研究，证明了对于一个矩阵，当其具有低秩结构且受到稀疏结构的污染时，能够通过分离其低秩部分与稀疏部分对数据进行恢复。虽然现在对于二维张量的恢复有了较成熟的研究，但对于高维张量恢复方法的研究仍处于初始阶段，目前主要有Yin Li等提出的针对高维张量的低秩和稀疏张量分解(RSTD)方法(Li,Yin,et al."Optimum subspace learning and error correction for tensors."Computer Vision–ECCV 2010.Springer Berlin Heidelberg,2010.790-803)。由于矩阵存在确定的秩而张量的秩，因此认为当张量在各模式上的展开矩阵具有低秩结构时，该张量是低秩的。

[0005] 该方法的核心思想是假设原有张量数据具有低秩结构，而受到的干扰和污染是稀疏的，其目标函数如式(1)所示：

[0006]

[0007]

[0008] 其中 为受到污染的张量数据， 为满足低秩特性的原数据， 为稀疏噪声。λi和η为权重参数，ranki(.)表示秩，l0范数||·||0表示非零元素的个数。该目标函数通过最小化原数据的秩以及噪音的数量来保证原数据的低秩性和噪音的稀疏性。对该目标函数的求解是通过引入辅助元素Mi和Ni对求解问题进行松弛和简化，得到如下式子：

[0009]

[0010] 由于最小化张量的秩和l0范数是NP-hard问题，RSTD方法在求解时利用这两种求解函数的凸函数——迹范数||·||tr和l1范数||.||1分别进行替代求解。辅助元素Mi和Ni用来松弛张量各模式展开不独立的限制。对于松弛后的函数构建拉格朗日优化求解方程为：

[0011]

[0012] 得到拉格朗日求解函数之后，RSTD利用固定坐标下降法进行求解优化，即在迭代求解某一变量时，先将其他变量固定后进行求解。

发明内容

[0013] 为解决上述问题，本发明公开了一种基于多线性增广拉格朗日乘子法的张量数据恢复方法，通过对目标函数进行转换加之改变其约束条件并采用多线性增广拉格朗日乘子法去约束，提高了张量恢复精度并降低了计算复杂度。

[0014] 为达到上述目的，本发明的技术方案如下：

[0015] 一种基于多线性增广拉格朗日乘子法的张量数据恢复方法，包括：根据受污染的高维数据的结构和多模式特性构建张量模型；根据所述张量模型构建用于张量恢复的第一目标函数，其中，所述第一目标函数包括低秩项和稀疏项，所述低秩项和所述稀疏项分别表示所述高维数据中的真实数据和污染数据；将所述第一目标函数转换成不包括松弛项的第二目标函数，其中，所述第二目标函数具有第二约束条件，并且其中，所述第二目标函数包括最小化所述低秩项沿所述各个模式展开所得矩阵的秩的第一项，所述第二目标函数还包括涉及所述稀疏项的第二项，所述第一项与所述第二项在所述第二目标函数中求加权和；对所述第二目标函数进行优化，并且利用多线性增广拉格朗日乘子法对优化后的第二目标函数进行去约束得到第三目标函数；以及求解所述第三目标函数，得到所述真实数据和所述污染数据。

[0016] 优选地，所述第一目标函数具有第一约束条件，并且所述第一目标函数还包括最小化所述低秩项在所述多模式的各个模式中的秩的加权和的项。

[0017] 优选地，所述第一目标函数为：

[0018]

[0019]

[0020] 其中， 表示待重建数据的张量，表示低秩部分的张量，表示稀疏部分的张量，λi为所述各个模式的权重参数，η为调整参数， 表示 在第i模式中的秩，||·||0表示0范数， 为所述第一约束条件。

[0021] 优选地，所述第二目标函数为：

[0022]

[0023] s.t.L(n)+S(n)＝A(n)

[0024] 其中，A(n)，L(n)和S(n)分别是 和S沿第n模式展开所得矩阵，rank(L(n))为L(n)的秩，λn为各个模式的调整参数，αn为所述各个模式的权重参数，s.t.L(n)+S(n)＝A(n)为所述第二约束条件。

[0025] 优选地，所述第二项是所述稀疏项沿所述各个模式展开所得矩阵的0范数，所述优化包括：用所述低秩项沿所述各个模式展开所得矩阵的最小化迹范数来代替最小化所述低秩项沿所述各个模式展开所得矩阵的秩，并且用1范数代替所述0范数，得到替换后的目标函数；在所述替换后的目标函数的基础上得到针对所述各个模式的第二目标函数。

[0026] 优选地，所述替换后的函数为：

[0027]

[0028] s.t.L(n)+S(n)＝A(n)

[0029] 其中，||·||*表示最小迹范数，||·||1表示1范数。

[0030] 优选地，所述第二目标函数为：

[0031]

[0032] s.t.L(n)+S(n)＝A(n)。

[0033] 优选地，所述第三目标函数为：

[0034]

[0035] 优选地，所述通过对所述第三目标函数求解得到所述真实数据和所述污染数据的步骤包括：利用交替方向乘子法对所述第三目标函数进行迭代求解，在达到预先的收敛条件的情况下得到所述真实数据和所述污染数据。

[0036] 优选地，所述迭代求解中的每次迭代包括：分别计算所述低秩项的各个模式的展开矩阵，并且分别计算稀疏部分的各个模式的展开矩阵；将计算得出的所述低秩项与所述稀疏项的展开矩阵沿所述各个模式重新构建成所述低秩项代表的张量和所述稀疏项代表的张量；以及通过分别对所述低秩项代表的张量和所述稀疏项代表的张量进行加权平均得到所述真实数据和污染数据。

[0037] 本发明的有益效果是：

[0038] 本发明通过用张量沿各模式展开所得矩阵秩的加权和代替原张量的秩，增加约束条件并结合多线性增广拉格朗日乘子法，避免了目标函数中松弛项对张量恢复精度的影响，在高污染率时提高了张量恢复速度。

附图说明

[0039] 图1是根据本发明实施例的一种基于多线性增广拉格朗日乘子法的张量数据恢复方法的流程图；

[0040] 图2是门窗图片污染噪声去除的示意图；

[0041] 图3是MRI图像污染噪声去除的示意图。

具体实施方式

[0042] 下面结合附图和具体实施方式，进一步阐明本发明，应理解下述具体实施方式仅用于说明本发明而不用于限制本发明的范围。

[0043] 如图所示，本专利提出一种基于多线性增广拉格朗日乘子法的张量数据恢复，在原来的基础上，增加约束改变目标函数，并且在构建求解函数时，利用多线性增广拉格朗日乘子法(multi-linear augmented  Lagrange multipliers)和交替方向乘子法(alternating direction method of multipliers)构建了一种新的张量恢复增广拉格朗日乘子求解函数，充分考虑张量的原有多维结构，再利用优化方法求解构建的优化函数，恢复受污染数据。

[0044] 本发明所公开的张量恢复方法可用图1中的流程图来表示：

[0045] 在步骤101中，根据受污染的高维数据的结构和多模式特性构建张量模型。具体地，根据数据的结构和多模式特性构建合适张量模型 对于图片数据来说N＝3，其I1、I2和I3分别表示了图像的长、宽以及RGB通道。

[0046] 在步骤102中，根据所述张量模型构建用于张量恢复的第一目标函数，所述第一目标函数中包括低秩项和稀疏项，所述低秩项和所述稀疏项分别表示所述高维数据中的真实数据和污染数据。具体地，将张量恢复问题的原始目标函数/第一目标函数构建为：

[0047]

[0048]

[0049] 其中， 是低秩部分， 是由噪声等引起稀疏部分，λi为各个模式的权重参数，η为调整参数， 为在此式中体现的第一约束条件。

[0050] 在步骤103中，将所述第一目标函数转换成第二目标函数，其中，由于没有引入用于辅助的松弛项，第二目标函数仍不包括松弛项。

[0051] 具体地，第一目标函数向第二目标函数的转换，是将最小化张量各模式秩加权和的问题转变为最小化张量的各个模式秩再求和的问题，以便于后续求解。优选地，第二目标函数如式(5)所示：

[0052]

[0053] s.t.L(n)+S(n)＝A(n)   (5)

[0054] 其中，A(n)，L(n)和S(n)分别是 和S沿第n模式展开所得矩阵，αn为各个模式的权重。即把问题(4)转换成了各个模式展开所得低秩矩阵和稀疏矩阵和的加权。

[0055] 然后分别利用最小化迹范数和1范数来替代最小化张量的秩和0范数，则得到替换后的目标函数如下：

[0056]

[0057] s.t.L(n)+S(n)＝A(n)。   (6)

[0058] 此后，分别对每个模式展开的矩阵构建优化目标函数，用于后续优化，此时，问题(6)转换为问题(7)，式(7)为最终的第二目标函数：

[0059]

[0060] s.t.L(n)+S(n)＝A(n)   (7)

[0061] 其中，n＝1,2,….,N。该目标函数需要分别对n取不同值时进行优化。约束项的增加也使该模型更加符合实际问题，从而提高数据恢复的精度。

[0062] 在步骤104中，利用多线性增广拉格朗日乘子法对所述第二目标函数进行去约束求解，得到第三目标函数。具体地，利用增广拉格朗日乘子法将问题(7)进行去约束求解，得到第三目标函数，即式(8)。这样一来就避开了RSTD中的松弛项，更加符合实际问题，从而提高数据恢复的精度。

[0063]

[0064] 最后，在步骤105中，通过对所述第三目标函数求解得到所述真实数据和所述污染数据。具体地，对问题(8)通过交替方向乘子法进行优化，每次迭代的步骤如下：

[0065] 1)分别计算低秩部分的各模式展开矩阵L(n)，通过求解式(9)进行：

[0066]

[0067] 得到最优解为：

[0068]

[0069] 其中，UnΛVnT是A(n)-S(n)+μn-1Yn的奇异值分解。 是关于τ＞0的收缩算子，定义为：

[0070]

[0071] 2)分别计算稀疏部分的各模式展开矩阵S(n)，通过求解式(12)进行：

[0072]

[0073] 得到最优解为：

[0074]

[0075] 3)将所求得的低秩部分与稀疏部分的展开矩阵沿各模式重新构建成张量，并分别通过加权平均得到低秩部分和稀疏部分：

[0076]

[0077]

[0078] 此权重与问题(5)中的权重对应。

[0079] 每一步迭代结束后，将所得低秩部分与上一次的低秩部分进行对比，当两者之间的差异小于一定阈值时，说明算法收敛，所获得的低秩部分和稀疏部分分别对应于原始数据和噪音。

[0080] 此算法的伪代码如下所示：

[0081]

[0082] 在真实数据上进行实验，将张量恢复方法应用于图像恢复上以验证实际恢复效果，用于实验的图像数据需要具有良好的结构，例如门窗图像、CT/MRI data以及高光谱图像等。将原始图片数据作为对照组，通过随机在一定比例的原始数据上添加噪点作为受污染数据，将原始数据与恢复数据之间的差异作为恢复的精度标准。实验的污染率设置为0.1和0.3，具体精度衡量指标为均方根误差，即原始图像与恢复图像之间差异的F范数与原始图像的F范数之比，均方根误差越小说明精度越高。

[0083] 分别对RSTD张量恢复方法和本发明提出的张量恢复方法进行实验对比，从均方根误差和算法运行总时间两个指标分别验证方法的精度和速度。结果如表1所示，本发明方法在精度上取得了较好效果，虽然在低污染率下速度略慢于RSTD方法，但在高污染率时速度有了略微优势。

[0084] 图2和图3分别展示了在门窗图像上的污染恢复以及MRI图像数据上的污染恢复结果。在图2中，第一行图像污染率为0.1，第二行图像污染率为0.3。从左到右依次为:污染的数据、通过本发明方法对噪声恢复的结果、通过RSTD方法对噪声恢复的结果。在图3中，前三行表示通过本发明方法对污染数据的恢复结果，后三行表示RSTD方法对污染数据的恢复结果。从左到右依次为:污染率为10％的原始数据、污染率为30％的原始数据、对10％噪声污染数据恢复的结果、对30％噪声污染数据恢复的结果。

[0085] 可以看出，基于多线性增广拉格朗日乘子法的张量数据恢复的精度更高，图像的还原度更好。本发明所提方法的优势明显。

[0086] 表1本发明恢复算法与RSTD的对比

[0087]

[0088] 通过上文中对实施例和实验结果的描述，本领域技术人员应当能理解，本发明对用于张量恢复的目标函数进行了上述转换和优化并改变了其约束条件，避免了现有技术目标函数中涉及的松弛项，有效地提高了张量恢复精度。另外，即使涉及松弛项的现有技术也采用增广拉格朗日去约束，然而相对于对结果函数的求解来说，本发明的函数求解明显降低了计算复杂度。

[0089] 专业人员应该还可以进一步意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、计算机软件或者二者的结合来实现，为了清楚地说明硬件和软件的可互换性，在上述说明中已经按照功能一般性地描述了各示例的组成及步骤。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。
专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。

[0090] 结合本文中所公开的实施例描述的方法或算法的步骤可以用硬件、处理器执行的软件模块，或者二者的结合来实施。软件模块可以置于随机存储器(RAM)、内存、只读存储器(ROM)、电可编程ROM、电可擦除可编程ROM、寄存器、硬盘、可移动磁盘、CD-ROM、或技术领域内所公知的任意其它形式的存储介质中。

[0091] 以上的具体实施方式，对本发明的目的、技术方案和有益效果进行了进一步详细说明。所应理解的是，以上仅为本发明的具体实施方式而已，并不用于限定本发明的保护范围。凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。