基于非局部自相似性和低秩矩阵逼近的补全算法

doi:10.11772/j.issn.1001-9081.2020030419

计算机应用 ›› 2020, Vol. 40 ›› Issue (11): 3327-3331.DOI: 10.11772/j.issn.1001-9081.2020030419

• 虚拟现实与多媒体计算 • 上一篇下一篇

基于非局部自相似性和低秩矩阵逼近的补全算法

张丽, 孔旭, 孙忠贵

聊城大学数学科学学院, 山东聊城 252000

收稿日期:2020-04-06 修回日期:2020-06-01 出版日期:2020-11-10 发布日期:2020-06-10
通讯作者: 孔旭(1981-),男,山东曲阜人,副教授,博士,主要研究方向:应用数学、机器学习、图像处理;kongxu@lcu.edu.cn
作者简介:张丽(1995-),女,山东临沂人,硕士研究生,主要研究方向:应用数学、机器学习、图像处理;孙忠贵(1971-),男,山东阳谷人,副教授,博士,主要研究方向:机器学习、图像处理
基金资助:
国家自然科学基金资助项目（11801249）；山东省自然科学基金资助项目（ZR201713A034）；聊城大学创新实验基金资助项目（26322170128）。

Matrix completion algorithm based on nonlocal self-similarity and low-rank matrix approximation

ZHANG Li, KONG Xu, SUN Zhonggui

School of Mathematical Sciences, Liaocheng University, Liaocheng Shandong 252000, China

Received:2020-04-06 Revised:2020-06-01 Online:2020-11-10 Published:2020-06-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (11801249), the Natural Science Foundation of Shandong Province (ZR201713A034), the Innovative Experiment Foundation of Liaocheng University (26322170128).

摘要/Abstract

摘要： 针对传统矩阵补全算法在图像重建方面的不足，提出了一种基于非局部自相似性和低秩矩阵逼近（NL-LRMA）的补全算法。首先，通过相似性度量找到图像中局部块所对应的非局部相似块，并将相应灰度信息进行向量化，从而构建出非局部相似块矩阵；然后，针对所得相似矩阵的低秩性，对其进行低秩补全操作（LRMA）；最后，对补全结果进行重新组合，以达到恢复原始图像的目的。在灰度图像以及RGB图像上进行重建实验，结果表明：在经典数据集上，NL-LRMA算法要比原LRMA算法在平均峰值信噪比（PSNR）上高出4~7 dB；同时，新算法在视觉效果与PSNR值方面也明显优于迭代重加权核范数（IRNN）、加权核范数（WNNM）、LRMA等传统算法。总之，所提算法对传统算法在自然图像重建方面的不足进行了有效弥补，从而为图像重建提供了一种行之有效的解决方案。

关键词: 矩阵补全, 低秩矩阵逼近, 非局部自相似性, 图像恢复, 块匹配

Abstract: Aiming at the shortage of traditional matrix completion algorithm in image reconstruction, a completion algorithm based on NonLocal self-similarity and Low Rank Matrix Approximation (NL-LRMA) was proposed. Firstly, the nonlocal similar patches corresponding to the local patches in the image were found through similarity measurement, and the corresponding grayscale matrices were vectorized to construct the nonlocal similar patch matrix. Secondly, aiming at the low-rank property of the obtained similarity matrix, Low-Rank Matrix Approximation (LRMA) was carried out. Finally, the completion results were recombined to achieve the goal of restoring the original image. Reconstruction experiments were performed on grayscale and RGB images. The results show that the average Peak Signal-to-Noise Ratio (PSNR) of NL-LRMA algorithm is 4 dB to 7 dB higher than that of the original LRMA algorithm on a classic dataset; at the same time, NL-LRMA algorithm is better than IRNN (Iteratively Reweighted Nuclear Norm), WNNM (Weighted Nuclear Norm Minimization), LRMA (Low-Rank Matrix Approximation) and other traditional algorithms in the terms of visual effect and PSNR value. In short, NL-LRMA algorithm effectively make up for the shortcomings of traditional algorithms in natural image reconstruction, so as to provide an effective solution for image reconstruction.

Key words: matrix completion, low-rank matrix approximation, nonlocal self-similarity, image restoration, patch matching

中图分类号:

TP391.41

张丽, 孔旭, 孙忠贵. 基于非局部自相似性和低秩矩阵逼近的补全算法[J]. 计算机应用, 2020, 40(11): 3327-3331.

ZHANG Li, KONG Xu, SUN Zhonggui. Matrix completion algorithm based on nonlocal self-similarity and low-rank matrix approximation[J]. Journal of Computer Applications, 2020, 40(11): 3327-3331.

参考文献

[1] LI W,ZHAO L,LIN Z,et al. Non-local image inpainting using low-rank matrixcompletion[J]. Computer Graphics Forum,2015, 34(6):111-122.
[2] CABRAL R S,DE LA TORRE F,COSTEIRA J P,et al. Matrixcompletion for multi-label image classification[C]//Proceedings of the 24th International Conference on Neural Information Processing Systems. Red Hook,NY:Curran Associates Inc.,2011:190-198.
[3] BALZANO L,NOWAK R,RECHT B. Online identification and tracking of subspaces from highly incomplete information[C]//Proceedings of the 48th Annual Allerton Conference on Communication, Control, and Computing. Piscataway:IEEE, 2010:704-711.
[4] KESHAVAN R H,OH S. OptSpace:gradient descent algorithm on the grassman manifold for matrixcompletion[EB/OL].[2020-03-01]. https://arxiv.org/pdf/0910.5260.pdf.
[5] YI J,ZHANG L,JIN R,et al. Semi-supervised clustering by input pattern assisted pairwise similarity matrixcompletion[C]//Proceedings of the 30th International Conference on Machine Learning. New York:JMLR.org,2013:1400-1408.
[6] CAI J,CANDÈS E J,SHEN Z. A singular value thresholding algorithm for matrixcompletion[J]. SIAM Journal on Optimization, 2010,20(4):1956-1982.
[7] TOH K C,YUN S. An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems[J]. Pacific Journal of Optimization,2010,6(3):615-640.
[8] LIN Z,CHEN M,MA Y. The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices[EB/OL].[2019-10-18]. http://arxiv.org/pdf/1009.5055v3.pdf.
[9] HU Y, ZHANG D, YE J, et al. Fast and accurate matrixcompletion via truncated nuclear norm regularization[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2013, 35(9):2117-2130.
[10] LEE D,OH J,YU H,et al. OCAM:out-of-core coordinate descent algorithm for matrixcompletion[J]. Information Sciences,2020, 514:587-604.
[11] GUGLIELMI N, SCALONE C. An efficient method for nonnegative low-rankcompletion[J]. Advances in Computational Mathematics,2020,46(2):No. 31.
[12] GILL L E. OX-LINK:the Oxford medical record linkage system[EB/OL].[2019-10-20]. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.9641&rep=rep1&type=pdf.
[13] MARDANI M, MATEOS G, GIANNAKIS G B. Rank minimization for subspace tracking from incomplete data[C]//Proceedings of the 2013 IEEE International Conference on Acoustics,Speech and Signal Processing. Piscataway:IEEE, 2013:5681-5685.
[14] MUKHOPADHYAY S. Stochastic gradient descent for linear systems with sequential matrix entry accumulation[J]. Signal Processing,2020,171:No. 107494.
[15] AHMEDTL J,GAO B,WOO W L,et al. Ensemble joint sparse low rank matrix decomposition for thermography diagnosis system[J]. IEEE Transactions on Industrial Electronics,2020(Early Access):1-11.
[16] 陈蕾, 陈松灿. 矩阵补全模型及其算法研究综述[J]. 软件学报,2017,28(6):1547-1564.(CHEN L,CHEN S C. Survey on matrixcompletion models and algorithms[J]. Journal of Software, 2017,28(6):1547-1564.)
[17] 史加荣, 郑秀云, 周水生. 矩阵补全算法研究进展[J]. 计算机科学,2014,41(4):13-20.(SHI J R,ZHENG X Y,ZHOU S S. Research progress in matrixcompletion algorithms[J]. Computer Science,2014,41(4):13-20.)
[18] WANG J,WANG Y,XU Z,et al. Accelerated low rank matrix approximate algorithms for matrixcompletion[J]. Computers and Mathematics with Applications,2019,77(2):334-341.
[19] SUN Z,CHEN S. Analysis of non-local Euclidean medians and its improvement[J]. IEEE Signal Processing Letters,2013,20(4):303-306.
[20] SUN Z,CHEN S,QIAO L. A general non-local denoising model using multi-kernel-induced measures[J]. Pattern Recognition, 2014,47(4):1751-1763.
[21] SUN Z,HAN B,LI J,et al. Weighted guided image filtering with steering kernel[J]. IEEE Transactions on Image Processing, 2019,29:500-508.
[22] BUADES A,COLL B,MOREL J M. A non-local algorithm for image denoising[C]//Proceedings of the 2005 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway:IEEE, 2005:60-65.
[23] GU S, ZHANG L, ZUO W, et al. Weighted nuclear norm minimization with application to image denoising[C]//Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway:IEEE,2014:2862-2869.
[24] LIU D,WEN B,FAN Y,et al. Non-local recurrent network for image restoration[C]//Proceedings of the 32nd International Conference on Neural Information Processing Systems. Red Hook, NY:Curran Associates Inc.,2018:1680-1689.
[25] WANG S,ZHANG L,LIANG Y. Nonlocal spectral prior model for low-level vision[C]//Proceedings of the 2012 Asian Conference on Computer Vision, LNCS 7726. Berlin:Springer, 2012:231-244.
[26] 张雯雯, 韩裕生. 基于非局部自相似性的低秩稀疏图像去噪[J]. 计算机应用,2018,38(9):2696-2700,2746.(ZHANG W W,HAN Y S. Nonlocal self-similarity based low-rank sparse image denoising[J]. Journal of Computer Applications,2018,38(9):2696-2700,2746.)
[27] DABOV K,FOI A,KATKOVNIK V,et al. Image denoising by sparse 3-D transform-domain collaborative filtering[J]. IEEE Transactions on Image Processing,2007,16(8):2080-2095.
[28] LU C,TANG J,YAN S,et al. Nonconvex nonsmooth low rank minimization via iteratively reweighted nuclear norm[J]. IEEE Transactions on Image Processing,2016,25(2):829-839.
[29] GU S, XIE Q, MENG D, et al. Weighted nuclear norm minimization and its applications to low level vision[J]. International Journal of Computer Vision, 2017, 121(2):183-208.

基于非局部自相似性和低秩矩阵逼近的补全算法

Matrix completion algorithm based on nonlocal self-similarity and low-rank matrix approximation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	叶杨, 蔡琼, 杜晓标. 基于非局部通道注意力机制的单图像超分辨率方法[J]. 计算机应用, 2020, 40(12): 3618-3623.
[2]	李南云, 王旭光, 吴华强, 何青林. 基于灰度塔评分的匹配模型构建在无人机网络视频拼接中的应用[J]. 计算机应用, 2019, 39(5): 1480-1484.
[3]	向文, 张灵, 陈云华, 姬秋敏. 基于结构自相似性和形变块特征的单幅图像超分辨率算法[J]. 计算机应用, 2019, 39(1): 275-280.
[4]	张雯雯, 韩裕生. 基于非局部自相似性的低秩稀疏图像去噪[J]. 计算机应用, 2018, 38(9): 2696-2700.
[5]	孙莞格, 夏克文, 兰璞. 正则化的加权不完全鲁棒主成分分析方法及其在无线传感器网络节点轨迹拟合中的应用[J]. 计算机应用, 2018, 38(6): 1709-1714.
[6]	王园宇, 张一凡, 王云飞. 单幅粉尘图像的切片重构恢复方法[J]. 计算机应用, 2018, 38(4): 1117-1120.
[7]	向文, 张灵, 陈云华, 姬秋敏. 结合结构自相似性和卷积网络的单幅图像超分辨率[J]. 计算机应用, 2018, 38(3): 854-858.
[8]	刘宇, 金伟正, 范赐恩, 邹炼. 使用超像素分割与图割的网状遮挡物检测算法[J]. 计算机应用, 2018, 38(1): 238-245.
[9]	孙少超. 基于带权核范数最小化和混合高斯模型的去噪模型[J]. 计算机应用, 2017, 37(5): 1471-1474.
[10]	张新明, 康强, 程金凤, 涂强. 采用自适应四点窗中点滤波的高椒盐噪声滤除方法[J]. 计算机应用, 2017, 37(3): 832-838.
[11]	李创权, 路艳蒙, 李穆, 李明强, 李然, 曹蕾. 基于图像块匹配的肾小球基底膜自动分割[J]. 计算机应用, 2016, 36(11): 3201-3206.
[12]	康晓东王昊郭宏郭军. 基于曲线波和稀疏表达的卡通—纹理模型[J]. 计算机应用, 2012, 32(10): 2786-2789.
[13]	王强李月娥. 基于方向自适应采样搜索的快速运动估计算法[J]. 计算机应用, 2011, 31(10): 2721-2723.
[14]	闵涛赵苗苗成瑶. 图像恢复的正则化Gmres方法[J]. 计算机应用, 2011, 31(08): 2201-2203.
[15]	李丽娟阳琼. 粗糙自适应遗传算法在图像恢复中的应用[J]. 计算机应用, 2011, 31(05): 1230-1232.