基于自动秩估计的黎曼优化矩阵补全算法及其在图像补全中的应用

刘静; 刘涵; 黄开宇; 苏立玉

doi:10.11999/JEIT181076

基于自动秩估计的黎曼优化矩阵补全算法及其在图像补全中的应用

doi: 10.11999/JEIT181076

1.
西安交通大学电子与信息工程学院西安 710049
2.
西安交通大学智能网络与网络安全教育部重点实验室西安 710049

基金项目: 国家自然科学基金(61573276)

详细信息

作者简介:
刘静：女，1975年生，教授，博士生导师，从事压缩感知、图像融合、雷达信号处理方向的研究

刘涵：女，1991年生，硕士生，研究方向为压缩感知、图像处理、矩阵补全

黄开宇：男，1992年生，博士生，研究方向为压缩感知、信号处理、信号与图像处理

苏立玉：男，1996年生，硕士生，研究方向为压缩感知、图像处理、张量补全

通讯作者:
刘静　elelj20080730@gmail.com

中图分类号: TP391.41
计量
- 文章访问数: 3861
- HTML全文浏览量: 1979
- PDF下载量: 103
- 被引次数: 0
出版历程
- 收稿日期: 2018-11-23
- 修回日期: 2019-05-07
- 网络出版日期: 2019-05-20
- 刊出日期: 2019-11-01

Automatic Rank Estimation Based Riemannian Optimization Matrix Completion Algorithm and Application to Image Completion

1.
School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China
2.
Ministry of Education Key Laboratory for Intelligent Networks and Network Security, Xi’an Jiaotong University, Xi’an 710049, China

Funds: The National Natural Science Foundation of China (61573276)

摘要

摘要: 矩阵补全(MC)作为压缩感知(CS)的推广，已广泛应用于不同领域。近年来，基于黎曼优化的MC算法因重构精度高、计算速度快的特点，引起了广泛关注。针对基于黎曼优化的MC算法需假设原矩阵秩固定已知，且随机选择迭代起点的特点，该文提出一种基于自动秩估计的黎曼优化MC算法。该算法通过优化包含秩正则项的目标函数，迭代获取秩估计值和预重构矩阵。在估计所得秩对应的矩阵空间上以预重构矩阵为迭代起点，利用基于黎曼流形的共轭梯度法进行矩阵补全，从而提高重构精度。实验结果表明，与几种经典的图像补全方法相比，该文算法图像重构精度显著提高。
- 图像补全(IC) /
- 矩阵补全(MC) /
- 自动秩估计 /
- 黎曼优化 /
- 卷积神经网络
Abstract: As an extension of Compressed Sensing(CS), Matrix Completion(MC) is widely applied to different fields. Recently, the Riemannian optimization based MC algorithm attracts a lot of attention from researchers due to its high accuracy in reconstruction and computational efficiency. Considering that the Riemannian optimization based MC algorithm assumes a fixed rank of the original matrix, and selects a random initial point for iteration, a novel algorithm is proposed, namely automatic rank estimation based Riemannian optimization matrix completion algorithm. In the proposed algorithm, the estimate of rank is obtained minimizing the objective function that involving the rank regulation, in addition, the iterative starting point is optimized based on Riemannian manifold. The Riemannian manifold based conjugate gradient method is then used to complete the matrix, thereby improving the reconstruction precision. The experimental results demonstrate that the image completion performance is significantly improved using the proposed algorithm, compared with several classical image completion methods.
- Image Completion(IC) /
- Matrix Completion(MC) /
- Automatic rank estimation /
- Riemannian optimization /
- Convolutional Neural Network (CNN)

HTML全文

图 1 基于自动秩估计的黎曼优化矩阵补全算法的图像补全

下载: 全尺寸图片幻灯片

图 2 低秩矩阵构建示意图

下载: 全尺寸图片幻灯片

图 3 黎曼流形上的共轭梯度法

下载: 全尺寸图片幻灯片

图 4 30%采样率下各算法图像补全结果

下载: 全尺寸图片幻灯片

表 1 自动秩估计算法伪代码

算法1 自动秩估计算法
输入： ${\text{A}} = {{\text{A}}_p} \in {\mathbb {R}^{m \times n}}$ ，索引矩阵 ${\text{Ω}}$ ，正则项系数 $\mu$ , $\alpha$ ，初始秩 $\hat k$ ，最大迭代次数 $K$ ，容错度 ${\tau _2}$ 。
初始化：执行奇异值分解 ${\text{A}}{\rm{ = }}{\text{U}}{\text{W}}{{\text{V}}^{\rm{T}}}$ ，将 ${\text{U}}$ 的第 $r$ 列单位化记为 ${{\text{u}}_r}$ ，将 ${\text{V}}$ 的第 $r$ 行单位化记为 ${{\text{v}}_r}$ , ${\text{w}} = \left\{ {{w_r}} \right\}_{r = 1}^{\min \left( {m,n} \right)}$ 为 ${\text{W}}$ 中奇异值组成的　　　　　向量。令 ${\text{Z}} = {\text{0}}$ , ${{\text{P}}_{{\Omega ^c}}}\left( {\text{A}} \right) = {\text{0}}$ 。
输出： ${\text{Z}}$ , $k$ 。
(1) for $i = 1,2,·\!·\!·,K$ do：
(2) ${{\text{A}}_r} = {\text{A}}$ ；
(3) 更新 ${{\text{u}}_r}$ , ${{\text{v}}_r}$ , ${w_r}$ : for $r = 1,2, ·\!·\!· ,\hat k$ do：
若 ${w_r} \ne 0$ ，根据式(8)、式(9)和式(11)依次更新 ${{\text{u}}_r}$ , ${{\text{v}}_r}$ , ${w_r}$ ,
${{\text{A}}_r} = {{\text{A}}_r} - {w_r}{{\text{u}}_r}{\text{v}}_r^{\rm{T}}$ ，
end；
(4) 更新 ${\text{A}}$ ：更新 ${\text{Z}} = {\text{A}} - {{\text{A}}_r}$ ，令 ${ {\text{P} }_{ {\varOmega ^c} } }\left( {\text{A} } \right) = { {\text{P} }_{ {\varOmega ^c} } }\left( {\text{Z} } \right)$ ；
(5) 更新 $k$ ：for $k = 1,2, ·\!·\!· ,\min\left( {m,n} \right)$ do：
计算 $f\left( k \right) = {\rm{ } }\mu \left\| { { {\text{w} }_r} } \right\|_{r = 1}^k + 0.5\parallel {\text{A} } - \sum\limits_{r = 1}^k { {w_r}{ {\text{u} }_r}{ {\text{v} }_r}^{\rm{T} } } \parallel _{\rm F}^2 + \alpha k$ ，若 $f\left( k \right) < f\left( {k + 1} \right)$ ，则结束循环，
end；
(6) $\hat k = k$ ；
(7) 若 ${{\parallel {{\text{P}}_\Omega }\left( {{\text{A}} - {\text{Z}}} \right){\parallel _{\rm{F}}}} /{\parallel {{\text{P}}_\Omega }\left( {\text{A}} \right){\parallel _{\rm{F}}}}} < {\tau _2}$ 或 ${{\parallel {{\text{A}}^{i + 1}} - {{\text{A}}^i}{\parallel _{\rm{F}}}} / {\parallel {{\text{A}}^{i + 1}}{\parallel _{\rm{F}}}}} < {\tau _2}$ ，则结束循环；
(8) end。

下载: 导出CSV

表 2 基于自动秩估计的黎曼优化矩阵补全算法伪代码

算法2 基于自动秩估计的黎曼优化矩阵补全算法
输入： ${{\text{X}} _1}{\rm{ = }}Z \in {{\cal M}_k}$ ( ${\text{Z}}$ 和 $k$ 源于算法1)，容错度 ${\tau _1}$ ，切向量 ${{\text{η}} _0}{\rm{ = }}0$ 。
输出： ${{\text{X}}^ * }$ 。
(1) for $i = 1,2, ·\!·\!· ,K$ do：
(2) 梯度 ${\xi _i}: = {\rm{gradf}}\left( {{{\text{X}}_i}} \right)$ ；　　　　　　　　　　　　　% 计算黎曼梯度
(3) 若 $\parallel {\xi _i}\parallel \le {\tau _1}$ ，则停止迭代，令 ${{\text{X}}^ * }{\rm{ = }}{{\text{X}}_i}$ ，否则转(4)；% 终止条件
(4) 共轭方向 ${{\text{η}} _i}: = - {\xi _i} + {\beta _i}{{\cal T}_{{{\text{X}} _{i - 1}} \to {{\text{X}}_i}}}\left( {{{\text{η}}_{i - 1}}} \right)$ ；　　　　　　% 计算共轭方向
(5) 步长 ${t_i} = {{\rm{argmin}}_t}f\left( {{{\text{X}}_i} + t{{\text{η}} _i}} \right)$ ；　　　　　　　　　　% 计算步长
(6) 执行Armijo回溯以找到满足 $f\left( {{{\text{X}}_i}} \right) - f\left( {{R_{{{\text{X}}_i}}}\left( {0.{5^m}{t_i}{{\text{η}} _i}} \right)} \right) \ge - 0.0001 \times 0.{5^m}{t_i}\left\langle {{\xi _i},{{\text{η}} _i}} \right\rangle$ 且m≥0的最小整数，计算 ${X_{i + 1}}: = {R_{{{\text{X}}_i}}}\left( {0.{5^m}{t_i}{{\text{η}} _i}} \right)$ ；　　　　　　　　　　　　　　　　　　　　　　　　　　 % 收缩算子
(7) end。

下载: 导出CSV

表 3 基于各算法的补全后图像PSNR(dB)/SSIM指标评价

采样率(%)		图像补全算法
采样率(%)		本文算法	SVP	OptSpace	SVT	IALM
10	Barbara	25.1371/0.1018	27.1138/0.0749	28.4540/0.2703	26.4330/0.1817	27.9684/0.2217
10	House	25.0207/0.0737	27.0100/0.0845	28.8611/0.3805	26.0756/0.2122	27.3161/0.0319
20	Barbara	29.5855/0.6187	29.4788/0.3705	29.0277/0.3509	27.7929/0.3638	29.0097/0.3175
20	House	32.1346/0.7750	30.5881/0.4681	29.2989/0.4096	28.0950/0.4569	29.1008/0.0667
30	Barbara	31.8223/0.7775	30.5821/0.5530	29.7224/0.4138	29.0192/0.5193	29.6337/0.4010
30	House	34.3279/0.8434	32.6125/0.6858	29.8818/0.4437	30.2986/0.6472	29.9081/0.4560
40	Barbara	33.1805/0.8054	31.3704/0.6249	30.4532/0.4922	30.2063/0.6471	30.2152/0.4592
40	House	36.9926/0.9175	33.4685/0.7449	30.5393/0.4687	32.2618/0.7718	30.6276/0.4546
50	Barbara	34.3090/0.8545	32.3230/0.7045	31.1457/0.5349	31.6388/0.7607	31.0285/0.5060
50	House	37.9729/0.9342	34.4193/0.7909	31.8817/0.5854	34.2940/0.8575	31.3316/0.4965
60	Barbara	35.5808/0.8932	33.3609/0.7612	32.2731/0.5955	33.4085/0.8552	31.9375/0.5660
60	House	39.5723/0.9504	35.5242/0.8297	33.5629/0.7099	36.5579/0.9150	32.3391/0.4992
70	Barbara	37.1206/0.9277	34.6884/0.8124	33.4690/0.6453	35.7766/0.9191	33.0595/0.6449
70	House	41.0744/0.9622	36.8819/0.8690	34.4479/0.7395	39.3028/0.9524	33.4229/0.5724
80	Barbara	39.0801/0.9529	36.4704/0.8665	35.3219/0.7479	38.8081/0.9565	34.7671/0.6462
80	House	43.1665/0.9728	38.6710/0.9042	37.2815/0.8288	41.8076/0.9234	35.2485/0.6317
90	Barbara	42.3685/0.9699	39.3773/0.9213	38.4127/0.8653	40.6578/0.9357	38.0598/0.7796
90	House	46.1068/0.9810	41.9691/0.9442	40.3322/0.8943	42.0364/0.9707	38.1441/0.7449

下载: 导出CSV

参考文献(18)

臧芳. 一种利用低秩矩阵填充技术恢复气象数据的方法[J]. 计算机应用与软件, 2017, 34(9): 322–327. doi: 10.3969/j.issn.1000-386x.2017.09.063

ZANG Fang. Method of restoring meteorological data using low-rank matrix filling technique[J]. Computer Applications and Software, 2017, 34(9): 322–327. doi: 10.3969/j.issn.1000-386x.2017.09.063

杨国亮, 鲁海荣, 丰义琴, 等. 基于非局部矩阵填充的文物修复技术研究[J]. 计算机应用与软件, 2016, 33(11): 126–129. doi: 10.3969/j.issn.1000-386x.2016.11.030

YANG Guoliang, LU Hairong, FENG Yiqin, et al. On cultural relic images restoration technology based on non-local matrix completion[J]. Computer Applications and Software, 2016, 33(11): 126–129. doi: 10.3969/j.issn.1000-386x.2016.11.030

陈秋实, 杨强, 董英凝, 等. 基于矩阵填充的合成宽带高频雷达非网格目标分辨技术研究[J]. 电子与信息学报, 2017, 39(12): 2874–2880. doi: 10.11999/JEIT170449

CHEN Qiushi, YANG Qiang, DONG Yingning, et al. Off-the-grid targets resolution of synthetic bandwidth high frequency radar based on matrix completion[J]. Journal of Electronics &Information Technology, 2017, 39(12): 2874–2880. doi: 10.11999/JEIT170449

CAI T T and ZHANG Anru. Sparse representation of a polytope and recovery of sparse signals and low-rank matrices[J]. IEEE Transactions on Information Theory, 2014, 60(1): 122–132. doi: 10.1109/TIT.2013.2288639

CAI Jianfeng, CANDES E J, and SHEN Zuowei. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization, 2010, 20(4): 1956–1982. doi: 10.1137/080738970

LIN Zhouchen, CHEN Minming, and MA Yi. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[J]. arXiv preprint arXiv: 1009.5055, 2010.

VANDEREYCKEN B. Low-rank matrix completion by riemannian optimization[J]. SIAM Journal on Optimization, 2013, 23(2): 1214–1236. doi: 10.1137/110845768

MEKA R, JAIN P, and DHILLON I S. Guaranteed rank minimization via singular value projection[C]. Proceedings of the Neural Information Processing Systems Conference, Vancouver, Canada, 2010: 937–945.

KESHAVAN R H and OH S. A gradient descent algorithm on the grassman manifold for matrix completion[J]. arXiv preprint arXiv: 0910.5260, 2009.

SHI Qiquan, LU Haiping, and CHEUNG Y. Rank-one matrix completion with automatic rank estimation via L1-norm regularization[J]. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(10): 4744–4757. doi: 10.1109/TNNLS.2017.2766160

陈蕾, 陈松灿. 矩阵补全模型及其算法研究综述[J]. 软件学报, 2017, 28(6): 1547–1564. doi: 10.13328/j.cnki.jos.005260

CHEN Lei and CHEN Songcan. Survey on matrix completion models and algorithms[J]. Journal of Software, 2017, 28(6): 1547–1564. doi: 10.13328/j.cnki.jos.005260

CANDÈS E J and RECHT B. Exact matrix completion via convex optimization[J]. Foundations of Computational Mathematics, 2009, 9(6): 717–772. doi: 10.1007/s10208-009-9045-5

LI Wei, ZHAO Lei, LIN Zhijie, et al. Non-local image inpainting using low‐rank matrix completion[J]. Computer Graphics Forum, 2015, 34(6): 111–122. doi: 10.1111/cgf.12521

LIU Ping, LEWIS J, and RHEE T. Low-rank matrix completion to reconstruct incomplete rendering images[J]. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(8): 2353–2365. doi: 10.1109/TVCG.2017.2722414

DONG Bin, MAO Yu, OSHER S, et al. Fast linearized Bregman iteration for compressive sensing and sparse denoising[J]. Communications in Mathematical Sciences, 2010, 8(1): 93–111. doi: 10.4310/CMS.2010.v8.n1.a6

LIU Yuanyuan, SHANG Fanhua, WEI Fan, et al. Generalized higher-order orthogonal iteration for tensor decomposition and completion[C]. Proceedings of the 27th International Conference on Neural Information Processing Systems, Montreal, Canada, 2014: 1763–1771.

HORE A and ZIOU D. Image quality metrics: PSNR vs. SSIM[C]. Proceedings of the 20th International Conference on Pattern Recognition, Istanbul, Turkey, 2010: 2366–2369.

ÖZIÇ M Ü and ÖZŞEN S. A new model to determine asymmetry coefficients on MR images using PSNR and SSIM[C]. Proceedings of 2017 International Artificial Intelligence and Data Processing Symposium, Malatya, Turkey, 2017: 1–6.

施引文献

资源附件(0)

访问统计