基于双核范数鲁棒矩阵分解的遮挡图像恢复

史加荣，刘 晨

(西安建筑科技大学 理学院, 陕西 西安 710055)

在人工智能与大数据时代，推荐系统[1]、图像处理[2]和计算机视觉[3]等诸多应用领域的科学研究需要处理数据矩阵。大数据不仅具有大量、高速、多样、低价值密度、真实性5大特点，更重要的特点是高维度。数据维度过高，可用的数据信息有限，往往会造成数据采样不足的问题，而且易被噪声所污染，导致建立的模型难以发现数据中所隐含的规律。如何对这些高维度数据进行有效的建模，从而挖掘数据的潜在规律，进一步对未知的空间进行预测，是对研究者的一个重大挑战。

低秩矩阵分解[4-5]是解决上述问题的一类常用方法，系利用数据集的近似低秩结构来恢复低秩成分、移除噪声和补全缺失值。通常假设数据集存在于单个低维线性子空间中。矩阵分解方法主要包括传统的主成分分析(principal component analysis, PCA)[6]、奇异值分解(singular value decomposition, SVD)[7]和线性判别分析(linear discriminant analysis, LDA)[8]等。当数据集存在于多个低维线性子空间中时，主要的矩阵分解方法有二维PCA、二阶双向二维PCA、二维SVD、二维LDA和鲁棒广义低秩矩阵逼近(robust generalized low rank approximations of matrices, RGLRAM)等方法[9-10]。

传统的矩阵分解方法一般采用L2范数来度量逼近误差，但对数据中的异常值具有很高的敏感性。为了克服PCA对异常值的敏感性，文献[11]提出鲁棒主成分分析(robust principal component analysis, RPCA)，假设干净数据矩阵是低秩的，且误差矩阵是稀疏的，对于给定的数据矩阵，RPCA通过最小化核范数和L1范数的加权组合来恢复低秩成分与稀疏噪声。文献[12]讨论了RPCA目标函数的下界，随后部分学者提出了一系列基于RPCA的其他优化模型[13-14]。作为RPCA的一个重要扩展，低秩表示(low-rank representation, LRR)[15]中的低秩约束增强了矩阵行列之间的相关性，也提高了模型对噪声的鲁棒性。但与RPCA一样，LRR也假定误差项是稀疏的。

文献[16-17]提出了基于双核范数矩阵分解(double nuclear norm-based matrix decomposition, DNMD)方法，将每个数据矩阵分解为低秩干净数据和低秩误差数据之和，但没有考虑稀疏噪声的腐蚀。基于此，本研究提出一种基于双核范数的鲁棒矩阵分解(robust DNMD, RDNMD)方法，将每个数据矩阵分解为低秩干净数据、低秩误差数据和稀疏噪声之和，建立最小化矩阵双核范数与L1范数之和，并利用交替方向乘子法对模型进行求解。

1 相关知识

1.1 鲁棒主成分分析

在实际应用中可以将图像集表示为矩阵X∈Rmn×s,并将其分解为X=D+G，其中，D∈Rmn×s是需要恢复的低秩矩阵；G∈Rmn×s是未知的噪声矩阵。RPCA模型解决的问题是从被稀疏大噪声腐蚀的数据中精确地恢复出低秩矩阵。此问题可以描述为如下优化问题：

(1)

由于秩函数的非凸性和不连续性，上述秩最小化问题是NP难的，现有的算法无法有效求解秩最小化问题。文献[18]证明了秩函数的凸包络为核范数，可用于近似秩函数，可将问题(1)进行凸松弛。因此RPCA模型可以表示为：

(2)

求解RPCA模型的算法有迭代阈值法、加速近端梯度法、对偶法和增广拉格朗日乘子法等[19]。RPCA已经被应用于视频监控[2]、协同过滤[1]、人脸识别[16]等领域。RPCA模型还可以作为矩阵补全问题[20]的延伸，扩展到处理一小部分元素丢失的情况。

1.2 双核范数矩阵分解(DNMD)

(3)

将问题(3)进行凸松弛，即可得到双核范数矩阵分解模型：

(4)

2 双核范数鲁棒矩阵分解(RDNMD)

2.1 模型建立

RPCA模型未考虑低秩噪声，DNMD未考虑稀疏噪声。假设数据集同时受到低秩噪声和稀疏噪声的腐蚀，将图像集分解为Xi=Di+Ei+Gi，其中Gi∈Rm×n为噪声矩阵且服从均值为零的拉普拉斯分布，i=1,2,…,s。

记G=(vec(G1),…,vec(Gs))，建立双核范数鲁棒矩阵分解模型：

(5)

其中,λ≥0和τ≥0为正则化参数。

使用交替方向乘子法(ADMM)来求解优化问题(5)。为此，构造增广拉格朗日函数：

(6)

其中：‖·‖F为矩阵的Frobenius范数，μ>0为惩罚系数，〈·,·〉为内积算子，拉格朗日乘子矩阵Y=(vec(Y1),…,vec(Ys))，Yi∈Rm×n,i=1,2,…,s。

2.2 模型求解

借助优化问题(5)及函数(6)关于变量的可分性，ADMM采用交替优化的方法，即分别在固定其他变量的情况下得到感兴趣变量的最优解。下面给出主要的迭代过程。

当E,G,Y固定时，更新D:

(7)

因此D的更新公式为：

D:=D1/μ(X-E-G+Y/μ)，

(8)

其中，Dυ(·):Rm×n→Rm×n为奇异值阈值算子[21]。

Lμ关于Ei是可分离的。当D,G,Y固定时，更新Ei:

(9)

因此Ei的更新公式为：

Ei:=Dλ/μ(Xi-Di-Gi+(1/μ)Yi)。

(10)

当D,E,Y固定时，更新G:

(11)

因此G的更新公式为：

G:=Sτ/μ(X-D-E+Y/μ)，

(12)

其中，Sδ(·):Rm×n→Rm×n为绝对值阈值算子[11]。

当D,E,G固定时，更新Y:

Y:=Y+μ(X-D-E-G)。

(13)

更新μ：

μ:=min(ρμ,μmax),

(14)

其中：μmax是μ的最大值，ρ为大于1的常数。

算法1 求解RDNMD的ADMM算法

1.初始化:Y=0,E=0,G=0,μ=1/mean(svd(X))；

2.D:=D1/μ(X-E-G+Y/μ)；

3.Ei:=Dλ/μ(Xi-Di-Gi+(1/μ)Yi),i=1,2,…,s；

4.G:=Sτ/μ(X-D-E+Y/μ)；

5.Y:=Y+μ(X-D-E-G)；

6.μ:=min(ρμ,μmax)；

7.如果满足终止条件，终止算法；否则，转步骤2。

输出:D,E,G。

在算法1中，svd(X)表示矩阵X的所有奇异值，mean(·)表示均值算子。本实验中，取μmax=106,ρ=1.2,ε=10-10,Tmax=100，λ=0.125，τ=0.1。

2.3 算法分析

RDNMD求解算法的主要计算复杂度是由奇异值阈值算子产生的。给定一个m×n矩阵，不妨设m>n，对其进行奇异值分解的计算复杂度为O(mn2)。对于算法1,在更新D时，需要对mn×s维的矩阵进行奇异值分解，通常mn>s，于是计算复杂度为O(mns2)。在更新低秩误差图像Ei时,需要对m×n维的s个矩阵进行奇异值分解，计算复杂度为O(mn2s)。在更新稀疏误差矩阵G时,计算复杂度为O(mns)。在更新Y时,计算复杂度为O(mns)。因此，算法1在一次迭代过程中的总体计算复杂度为O(mns2+mn2s)。

3 数值实验与结果分析

3.1 数据描述与准备

在Extended Yale B人脸数据集[22]和Cuprite多光谱图像集[23]上进行实验。Extended Yale B人脸数据库共有38人,每人64幅照片。根据人脸与摄像机的方向角将每人的64幅照片分为5个子集。对于每个人，5个子集的人脸数目分别为7、12、12、14、19。每幅图像均被标准化为96×84的分辨率，提取了3人共192幅图像，部分图像见图1。Cuprite多光谱图像集选自NASA的AVIRIS数据集，共96个波段，每幅图像的大小为103×123，部分图像见图2。先对每个图像Di添加密度为p的椒盐噪声，再随机加入连续遮挡，遮挡大小为d×d。

图1 Extended Yale B数据集部分原始图像

图2 Cuprite多光谱图像集部分原始图像

连续遮挡的图像选自于哥伦比亚大学图像数据库COIL-20[24]。该数据集包含对20个物体从不同角度的拍摄图像，每隔5度拍摄一幅图像，每个物体72幅图像，总共1 440幅图像。

(15)

式(15)中相对误差RE越小，恢复性能越好。将RDNMD的实验结果与DNMD和RPCA的结果进行比较。采用MATLAB R2014a进行编程，所有实验在处理器为Intel®CoreTMi5-10210U CPU@1.60 GHz 2.11GHz的个人计算机上进行。

3.2 实验结果与分析

在Extended Yale B数据集上设计了两组实验来比较算法的性能。在第1组实验中，令d=20，p∈{0,0.1,0.2,0.3,0.4,0.5}，实验结果如图3所示，其中p=0表示观察到的图像中没有稀疏噪声，只有连续遮挡，此时提出的RDNMD就转化为DNMD。从图3可以看出：p=0时DNMD和RDNMD性能相当，均优于RPCA，而当p>0.1时，RDNMD得到的结果最好。

图3 3种模型在不同p下的相对误差Fig. 3 Relative errors of three models under different p

第2组实验中，固定稀疏噪声的密度p=0.2,考虑由于连续遮挡的变化导致相对误差的变化情况，取d∈{0,20,28,35,40,45,49,53,57}，实验结果如图4所示，其中d=0表明观察到的图像中没有低秩遮挡噪声，只有稀疏噪声，此时RDNMD转化为RPCA。从图4可以看出：d=0时，RPCA的恢复效果优于RDNMD和DNMD；1

图4 3种模型在不同连续遮挡d下的相对误差Fig. 4 Relative errors of three models under different continuous occlusion d

每人随机选取1幅图像进行可视化。令p=0.2,d=30，图5～7分别显示了RPCA、DNMD和RDNMD的实验结果，可以看出，RPCA和DNMD未能分离出低秩噪声和稀疏噪声，而RDNMD能较好地分离出低秩噪声和稀疏噪声；RDNMD将干净图像和噪声图像分离的最好。因此RDNMD具有最好的恢复性能。

图5 Extended Yale B在RPCA下的恢复结果Fig. 5 Recovered results of RPCA on Extended Yale B

在Cuprite多光谱图像集上进行实验，仅可视化地比较不同方法的恢复性能。取p=0.2,d=30，图8～10分别显示了RPCA、DNMD和RDNMD的部分实验结果。

由图8～10可以看出：RDNMD恢复出的低秩干净图像效果最好，DNMD次之，RPCA效果较差；RDNMD能较好地分离出低秩噪声和稀疏噪声，而DNMD和RPCA却不能有效地分离。此外，RPCA、DNMD和RDNMD的运行时间分别为15.98、22.69和26.36 s，即RDNMD需要的计算时间最长，RPCA的计算时间最短。

图6 Extended Yale B在DNMD下的恢复结果

图7 Extended Yale B在RDNMD下的恢复结果

图8 Cuprite在RPCA下的恢复结果

4 结论

本研究提出一种基于双核范数鲁棒矩阵分解方法,该方法假设低秩数据矩阵同时受到连续遮挡和稀疏噪声的腐蚀，使用低秩假设和稀疏假设来描述图像。所提出的方法不仅可以在一定程度上恢复干净的低秩数据，消除遮挡或前景引起的结构误差，而且通过L1范数消除稀疏误差。利用最小化矩阵双核范数与L1范数的加权组合建立优化模型，并使用交替方向乘子法进行求解。实验结果表明：本研究提出的方法对于同时受到连续遮挡和稀疏噪声腐蚀的矩阵更加鲁棒。

图9 Cuprite在DNMD下的恢复结果

图10 Cuprite在RDNMD下的恢复结果

对于RGB彩色图像集，可以先分别在每个通道上进行RDNMD,再按照RGB通道进行合成。当图像集很大时，矩阵分解的计算复杂度较大。为了加快矩阵分解的速度，减小对内存的需求，可以考虑采用随机梯度下降法[25]来求解RDNMD，这将是一个值得研究的问题。今后将进一步研究基于Schatten-q范数的矩阵分解和基于双核范数的概率矩阵分解，并将其应用于矩阵补全问题。