Image inpainting using non-convex low rank decomposition and multidirectional search. (English) Zbl 07702344
Summary: Low-rank (LR) and nonlocal self-similarity (NSS) are two important priors for image inpainting as a typical inverse problem. Nuclear norm minimization (NNM) is a widely used convex relaxation for relevant rank minimization problems. However, NNM regularizes each singular value equally and ignores the significance of bigger singular values. In this paper, we propose a non-convex low-rank decomposition (NC-LRD) model that is based on robust principal component analysis (RPCA) with a weighted \(L_1\) norm. Utilizing NSS prior for image inpainting we search similar patches by using a newly designed multidirectional search (MS) method, and apply the NC-LRD model to complete each corrupted patch matrix (low-rank decomposition with multidirectional search, MS-LRD). We focus on the spatial distribution of similar patches by restricting matched \(N\) patches to locate at \(N\) different directions relative to a target patch, while previous state-of-the-art methods do not consider the spatial distribution in similarity criterion. The MS method solves the problem that many patch-based inpainting algorithms fail to complete missing lines. Experimental results on line missing demonstrate that the proposed NC-LRD method has lower reconstruction error in matrix completion, and it converges faster than several state-of-the-art matrix completion algorithms. At the same time, the effectiveness and superiority of MS-LRD over other competitive inpainting algorithms are also verified.
MSC:
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
| 90C26 | Nonconvex programming, global optimization |
| 90C90 | Applications of mathematical programming |
Keywords:
low rank decomposition; image inpainting; inverse problem; multidirectional search; matrix completionSoftware:
PatchMatchReferences:
| [1] | Guillemot, C.; Le Meur, O., Image inpainting: overview and recent advances, IEEE Signal Process. Mag., 31, 1, 127-144 (2014) |
| [2] | Cao, J.; Li, Y.; Zhang, Q.; Cui, H., Restoration of an ancient temple mural by a local search algorithm of an adaptive sample block, Heritage Sci., 7, 1, 39 (2019) |
| [3] | Chan, T. F.; Shen, J., Nontexture inpainting by curvature-driven diffusions, J. Vis. Commun. Image Represent., 12, 4, 436-449 (2001) |
| [4] | Shen, J.; Chan, T. F., Mathematical models for local nontexture inpaintings, SIAM J. Appl. Math., 62, 3, 1019-1043 (2002) · Zbl 1050.68157 |
| [5] | https://www.sciencedirect.com/science/article/pii/S0096300314007164 · Zbl 1334.35419 |
| [6] | Hohm, K.; Storath, M.; Weinmann, A., An algorithmic framework for mumford-shah regularization of inverse problems in imaging, Inverse Probl., 31, 11, 115011 (2015) · Zbl 1329.35351 |
| [7] | Wali, S.; Zhang, H.; Chang, H.; Wu, C., A new adaptive boosting total generalized variation (tgv) technique for image denoising and inpainting, J. Vis. Commun. Image Represent., 59, 39-51 (2019) |
| [8] | Criminisi, A.; Pérez, P.; Toyama, K., Region filling and object removal by exemplar-based image inpainting, IEEE Trans. Image Process., 13, 9, 1200-1212 (2004) |
| [9] | Zhang, J.; Zhao, D.; Gao, W., Group-based sparse representation for image restoration, IEEE Trans. Image Process., 23, 8, 3336-3351 (2014) · Zbl 1374.94445 |
| [10] | Gu, S.; Xie, Q.; Meng, D.; Zuo, W.; Feng, X.; Zhang, L., Weighted nuclear norm minimization and its applications to low level vision, Int. J. Comput. Vis., 121, 2, 183-208 (2017) · Zbl 1458.68231 |
| [11] | https://www.sciencedirect.com/science/article/pii/S009630031730440X · Zbl 1426.94019 |
| [12] | Yeh, R. A.; Chen, C.; Yian Lim, T.; Schwing, A. G.; Hasegawa-Johnson, M.; Do, M. N., Semantic image inpainting with deep generative models, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 5485-5493 (2017) |
| [13] | Yu, J.; Lin, Z.; Yang, J.; Shen, X.; Lu, X.; Huang, T. S., Generative image inpainting with contextual attention, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 5505-5514 (2018) |
| [14] | Candès, E. J.; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 6, 717 (2009) · Zbl 1219.90124 |
| [15] | Cai, J.-F.; Candès, E. J.; Shen, Z., A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20, 4, 1956-1982 (2010) · Zbl 1201.90155 |
| [16] | Lu, C.; Tang, J.; Yan, S.; Lin, Z., Nonconvex nonsmooth low rank minimization via iteratively reweighted nuclear norm, IEEE Trans. Image Process., 25, 2, 829-839 (2016) · Zbl 1408.94866 |
| [17] | Nie, F.; Hu, Z.; Li, X., Matrix completion based on non-convex low-rank approximation, IEEE Trans. Image Process., 28, 5, 2378-2388 (2019) · Zbl 1411.94008 |
| [18] | Buades, A.; Coll, B.; Morel, J.-M., Nonlocal image and movie denoising, Int. J. Comput. Vis., 76, 2, 123-139 (2008) |
| [19] | Guo, Q.; Gao, S.; Zhang, X.; Yin, Y.; Zhang, C., Patch-based image inpainting via two-stage low rank approximation, IEEE Trans. Vis. Comput. Graph., 24, 6, 2023-2036 (2017) |
| [20] | Pathak, D.; Krahenbuhl, P.; Donahue, J.; Darrell, T.; Efros, A. A., Context encoders: feature learning by inpainting, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2536-2544 (2016) |
| [21] | Wright, J.; Ganesh, A.; Rao, S.; Peng, Y.; Ma, Y., Robust principal component analysis: exact recovery of corrupted low-rank matrices via convex optimization, Advances in Neural Information Processing Systems, 2080-2088 (2009) |
| [22] | Wen, F.; Ying, R.; Liu, P.; Qiu, R. C., Robust pca using generalized nonconvex regularization, IEEE Trans. Circuits Syst. Video Technol., 30, 6, 1497-1510 (2020) |
| [23] | Fan, J.; Li, R., Variable selection via nonconcave penalized likelihood and its oracle properties, J. Am. Stat. Assoc., 96, 456, 1348-1360 (2001) · Zbl 1073.62547 |
| [24] | Bertalmio, M.; Sapiro, G.; Caselles, V.; Ballester, C., Image inpainting, Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, 417-424 (2000) |
| [25] | Chan, T. F.; Kang, S.; Shen, J., Euler’S elastica and curvature based inpaintings, SIAM J. Appl. Math., 63, 2, 564-592 (2001) · Zbl 1028.68185 |
| [26] | Tschumperlé, D., Fast anisotropic smoothing of multi-valued images using curvature-preserving pde’s, Int. J. Comput. Vis., 68, 1, 65-82 (2006) · Zbl 1481.94031 |
| [27] | Barnes, C.; Shechtman, E.; Finkelstein, A.; Goldman, D. B., Patchmatch: a randomized correspondence algorithm for structural image editing, ACM Trans. Graph., 28, 3 (2009) |
| [28] | Mairal, J.; Elad, M.; Sapiro, G., Sparse representation for color image restoration, IEEE Trans. Image Process., 17, 1, 53-69 (2007) |
| [29] | Shen, B.; Hu, W.; Zhang, Y.; Zhang, Y. J., Image inpainting via sparse representation, 2009 IEEE International Conference on Acoustics, Speech and Signal Processing, 697-700 (2009) |
| [30] | Dong, W.; Shi, G.; Li, X., Nonlocal image restoration with bilateral variance estimation: a low-rank approach, IEEE Trans. Image Process., 22, 2, 700-711 (2012) · Zbl 1373.94102 |
| [31] | Hu, Y.; Zhang, D.; Ye, J.; Li, X.; He, X., Fast and accurate matrix completion via truncated nuclear norm regularization, IEEE Trans. Pattern Anal. Mach. Intell., 35, 9, 2117-2130 (2013) |
| [32] | Huang, Y.; Liao, G.; Xiang, Y.; Zhang, L.; Li, J.; Nehorai, A., Low-rank approximation via generalized reweighted iterative nuclear and frobenius norms, IEEE Trans. Image Process., 29, 2244-2257 (2019) · Zbl 1518.94009 |
| [33] | Zhang, H.; Qian, J.; Zhang, B.; Yang, J.; Gong, C.; Wei, Y., Low-rank matrix recovery via modified schatten-\(p\) norm minimization with convergence guarantees, IEEE Trans. Image Process., 29, 3132-3142 (2019) · Zbl 07586091 |
| [34] | Zha, Z.; Yuan, X.; Wen, B.; Zhang, J.; Zhou, J.; Zhu, C., Image restoration using joint patch-group-based sparse representation, IEEE Trans. Image Process., 29, 7735-7750 (2020) · Zbl 07586433 |
| [35] | Chen, L.; Jiang, X.; Liu, X.; Zhou, Z., Robust low-rank tensor recovery via nonconvex singular value minimization, IEEE Trans. Image Process., 29, 9044-9059 (2020) · Zbl 07586530 |
| [36] | Hsu, D.; Kakade, S. M.; Zhang, T., Robust matrix decomposition with sparse corruptions, IEEE Trans. Inf. Theory, 57, 11, 7221-7234 (2011) · Zbl 1365.15018 |
| [37] | Candès, E. J.; Li, X.; Ma, Y.; Wright, J., Robust principal component analysis?, J. ACM, 58, 3, 1-37 (2011) · Zbl 1327.62369 |
| [38] | Lin, Z.; Chen, M.; Ma, Y., The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices, arXiv preprint arXiv:1009.5055 (2010) |
| [39] | Mirsky, L., A trace inequality of john von neumann, Monatshefte Für Mathematik, 79, 4, 303-306 (1975) · Zbl 0316.15009 |
| [40] | https://www.sciencedirect.com/science/article/pii/S0096300319301316. · Zbl 1429.65096 |
| [41] | Lu, C.; Tang, J.; Yan, S.; Lin, Z., Generalized nonconvex nonsmooth low-rank minimization, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2014) |
| [42] | Xue, S.; Qiu, W.; Liu, F.; Jin, X., Double weighted truncated nuclear norm regularization for low-rank matrix completion, arXiv preprint arXiv:1901.01711 (2019) |
| [43] | Zhang, D.; Hu, Y.; Ye, J.; Li, X.; He, X., Matrix completion by truncated nuclear norm regularization, 2012 IEEE Conference on Computer Vision and Pattern Recognition, 2192-2199 (2012) |
| [44] | https://www.sciencedirect.com/science/article/pii/S0925231220303532. |
| [45] | Dabov, K.; Foi, A.; Katkovnik, V.; Egiazarian, K., Image denoising by sparse 3-d transform-domain collaborative filtering, IEEE Trans. Image Process., 16, 8, 2080-2095 (2007) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
