Elsevier

Neurocomputing

Volume 311, 15 October 2018, Pages 209-224
Neurocomputing

Non-convex weighted ℓp nuclear norm based ADMM framework for image restoration

https://doi.org/10.1016/j.neucom.2018.05.073Get rights and content

Abstract

Inspired by the fact that the matrix formed by nonlocal similar patches in a natural image is of low rank, the nuclear norm minimization (NNM) has been widely used in various image processing studies. Nonetheless, nuclear norm based convex surrogate of the rank function usually over-shrinks the rank components since it treats different components equally, and thus may produce a result far from the optimum. To alleviate the aforementioned limitations of the nuclear norm, in this paper we propose a new method for image restoration via the non-convex weighted ℓp nuclear norm minimization (NCW-NNM), which is able to accurately impose the image structural sparsity and self-similarity simultaneously. To make the proposed model tractable and robust, the alternating direction method of multiplier (ADMM) framework is adopted to solve the associated non-convex minimization problem. Experimental results on various image restoration problems, including image deblurring, image inpainting and image compressive sensing (CS) recovery, demonstrate that the proposed method outperforms many current state-of-the-art methods.

Introduction

Image restoration (IR) aims to reconstruct a high quality image X from its degraded observation Y, which can be generally expressed as Y=HX+η,where H is a non-invertible linear degradation operator and η is the vector of some independent white Gaussian noise. With different settings of matrix H, various IR problems can be derived from Eq. (1), such as image denoising [1], [2], [3], [4], [5] when H is an identity matrix, image deblurring [6], [7], [8], [9] when H is a blur operator, image inpainting [10], [11], [12], [13] when H is a mask and image compressive sensing (CS) recovery when H is a random projection matrix [14], [15], [16], [17], [18], [19]. In this work, we focus on the latter three problems.

IR is a typical ill-posed problem, and in order to deal with this issue, image prior knowledge is usually exploited for regularizing the solution. This leads to the following minimization problem, X^=argminX12YHX22+λR(X),where the first term is the data fidelity term and the second term depends on the employed image priors, and λ is the regularization parameter. Due to the ill-posed nature of IR, the image prior knowledge plays a critical role in the performance of IR algorithms. In other words, how to design an effective regularization model to represent the image priors is vital for IR tasks.

The classical regularization models, such as Tikhonov regularization [20] and total variation (TV) regularization [21], [22], exploited the image local structure and high effectiveness to preserve image edges. Nonetheless, they tended to over-smooth the image and some image details are usually lost. As an emerging machine learning technique, sparse representation based modeling has been proved to be a promising model for image restoration [23], [24], [25], [26]. It assumes that image (or image patches) can be precisely represented as a sparse linear combination of basic elements. These elements, called atoms, compose a dictionary [23], [24], [27], [28], [29]. The dictionary is usually learned from a natural image dataset [23], [24]. The well known dictionary learning (DL) based methods, such as KSVD [23], [24], ODL [27] and tasked driven DL [28], have been proposed and applied to image restoration and other image processing tasks.

Image patches that have similar pattern can be spatially far from each other and thus can be collected across the whole image. This so-called nonlocal self-similarity (NSS) prior is the most outstanding priors for image restoration. The seminal work of nonlocal means (NLM) [1] exploited the NSS prior to perform a series of weighted filtering for image denoising. Due to its effectiveness, a large number of related approaches have been proposed [3], [8], [18], [30], [31], [32], [33]. For instance, BM3D [32] exploited the nonlocal similarity of 2D image patches and the 3D transform domain collaborative filtering. Marial et al. [3] considered the idea of NSS by simultaneous sparse coding (SSC). Dong et al. [30] proposed the nonlocally centralized sparse representation (NCSR) model for image restoration, which obtained the estimation of the sparse coding coefficients of the original image by the principle of NLM [1], and then starting from these estimates, NCSR, centralized the sparse coding coefficients of the observed image to improve the restoration performance. Zhang et al. [33] proposed a group-based sparse representation framework for image restoration.

Recently, image priors based on NSS [1], [4], [7], [8], [25], [30], [31], [32], [33], [34], [35], [36], [37] and low-rank matrix approximation (LRMA) [38], [39], [40], [41], [42], [43], [44], [45], [46] have achieved a great success in IR [47], [48], [49]. A flurry of IR has been proposed, such as image alignment [47], image/video denoising [4], [37], [48], [50], image deblurring [7], [51], [52] and image inpainting [10], [53]. However, these methods usually suffer from a common drawback that the nuclear norm is usually adopted as a convex surrogate of the rank of a matrix. Despite a good theoretical guarantee by the singular value thresholding (SVT) model [38], the nuclear norm minimization (NNM) [38], [39], [42] tends to over-shrink the rank components since it treats the different rank components equally, and thus it cannot estimate the matrix rank accurately enough. To enforce the low rank regularization efficiently, inspired by the success of ℓp (0 < p < 1) sparse optimization [54], [55], [56], Schatten p-norm is proposed [57], [58], [59], which is defined as the ℓp-norm (0 < p < 1) of the singular values. Compared with traditional nuclear norm, Schatten p-norm not only achieves a more accurate recovery result of the signal, but also requires only a weaker restricted isometry property based on theory [58]. Nonetheless, similar to the standard nuclear norm, most of the Schatten p-norm based models treat all singular values equally, which may be infeasible in executing many practical problems, such as image inverse problems [60]. In the meantime, to further improve the flexibility of NNM, Gu et al. [4] proposed the weighted nuclear norm minimization (WNNM) model. Actually, the weighted nuclear norm is essentially the reweighted ℓ1-norm of the singular values. Compared with NNM, WNNM assigns different weights to different singular values such that the matrix rank approximation becomes more reasonable.

Inspired by the success of ℓp (0 < p < 1) norm [54], [55], [56] and the reweighted ℓ1 sparse optimization [61], to obtain the rank approximation more accurately, we propose a novel model for image restoration (IR) via the non-convex weighted ℓp (0 < p < 1) nuclear norm minimization (NCW-NNM), which is expected to be more accurate than traditional nuclear norm. Moreover, to solve the associated non-convex minimization problem, we develop an efficient alternating direction multiplier method (ADMM). Experimental results on three typical IR tasks, including image deblurring, image inpainting and image compressive sensing (CS) recovery, show that the proposed method outperforms many current state-of-the-art methods both quantitatively and qualitatively.

The remainder of this paper is organized as follows. Section 2 introduces the proposed non-convex weighted ℓp nuclear norm prior model for image restoration. Section 3 presents the implementation details of the proposed non-convex model under the ADMM optimization framework. Section 4 reports the experimental results. Finally, Section 5 concludes this paper.

Section snippets

Non-convex weighted ℓp nuclear norm prior model for image restoration

Generally speaking, the low rank property of the data matrix formed by nonlocal similar patches in IR, is usually characterized by the nuclear norm. However, nuclear norm based convex surrogate of the rank function usually over-shrinks the rank components and thus may produce a result far from the optimum. To boost the accuracy of the rank approximation in IR, we propose an efficient IR method via the non-convex weighted ℓp nuclear norm minimization (NCW-NNM).

In this section, we will elaborate

Non-convex weighted ℓp nuclear norm based ADMM framework for image restoration

In this section, the proposed scheme is used to solve the IR tasks, including image deblurring, image inpainting and image CS recovery. It can be seen that solving the objective function of Eq. (6) is very difficult, since it is a large scale non-convex optimization problem. To make the proposed scheme tractable and robust, in this paper, we adopt the alternating direction method of multipliers (ADMM) [62] to solve Eq. (6).

The ADMM algorithm is a powerful tool for various large scale

Experimental results

In this section, we conduct a variety of experiments on three IR tasks, including image deblurring, image inpainting and image CS recovery, to evaluate the effectiveness of the proposed NCW-NNM method. To prove the advantage of the proposed NCW-NNM method, which can improve the accuracy of the matrix rank approximation. We compare it with traditional rank minimization method, i.e., the nuclear norm minimization (NNM) method. All the experimental images are shown in Fig. 1. To evaluate the

Conclusion

Image priors based on nonlocal self-similarity and low-rank matrix approximation have achieved a great success in image restoration. However, since the singular values have clear meanings and should be treated differently, traditional nuclear norm minimization regularized each of them equally, which often restricted its capability and flexility. To rectify the shortcoming of the nuclear norm, this paper proposed a new method for image restoration via non-convex weighted ℓp nuclear norm

Acknowledgment

The authors would like to thank Associate Editor for his efforts in coordinating the review of the manuscript, and thank three anonymous reviewers for their constructive suggestions to improve the manuscript. This work was supported by the NSFC (61571220, 61462052, 61502226 and 61601362).

Zhiyuan Zha received the B.S. degrees in computer science from the JiangSu University, Zhenjiang, China, in 2010, and the M.S. degree in computer science from the Kunming University of Science and Technology, Kunming, China, in 2015. He is currently pursuing the Ph.D. degree with the Department of Electronic Science and Engineering, Nanjing University, Nanjing, China. His current research interests include inverse problems in image processing, sparse signal representation, Low rank matrix

References (80)

  • LiuL. et al.

    Exact minimum rank approximation via schatten p-norm minimization

    J. Comput. Appl. Math.

    (2014)
  • ZhaoC. et al.

    Nonconvex lp nuclear norm based admm framework for compressed sensing

    Proceedings of the Data Compression Conference (DCC), 2016

    (2016)
  • A. Buades et al.

    A non-local algorithm for image denoising

    Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition

    (2005)
  • J. Mairal et al.

    Non-local sparse models for image restoration

    Proceedings of the IEEE Twelfth International Conference on Computer Vision

    (2009)
  • GuS. et al.

    Weighted nuclear norm minimization with application to image denoising

    Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition

    (2014)
  • ChenC.L.P. et al.

    Weighted couple sparse representation with classified regularization for impulse noise removal

    IEEE Trans. Image Process.

    (2015)
  • HuangC. et al.

    Robust image restoration via adaptive low-rank approximation and joint kernel regression

    IEEE Trans. Image Process.

    (2014)
  • ZhangJ. et al.

    Image restoration using joint statistical modeling in a space-transform domain

    IEEE Trans. Circuits Syst. Video Technol.

    (2014)
  • JinK.H. et al.

    Annihilating filter-based low-rank Hankel matrix approach for image inpainting

    IEEE Trans. Image Process.

    (2015)
  • ZhouM. et al.

    Nonparametric Bayesian dictionary learning for analysis of noisy and incomplete images

    IEEE Trans. Image Process.

    (2012)
  • ZhangJ. et al.

    Image compressive sensing recovery via collaborative sparsity

    IEEE J. Emerg. Sel. Top. Circuits Syst.

    (2012)
  • YuanX. et al.

    Parallel lensless compressive imaging via deep convolutional neural networks

    Opt. Express

    (2018)
  • ZhaZ. et al.

    Compressed sensing image reconstruction via adaptive sparse nonlocal regularization

    Vis. Comput.

    (2016)
  • YuanX. et al.

    Slope: shrinkage of local overlapping patches estimator for lensless compressive imaging

    IEEE Sens. J.

    (2016)
  • H.W. Engl et al.

    Convergence rates for tikhonov regularisation of non-linear ill-posed problems

    Inverse Prob.

    (1989)
  • A. Chambolle

    An algorithm for total variation minimization and applications

    J. Math. Imaging Vis.

    (2004)
  • M. Aharon et al.

    k-svd: an algorithm for designing over complete dictionaries for sparse representation

    IEEE Trans. Signal Process.

    (2006)
  • M. Elad et al.

    Image denoising via sparse and redundant representations over learned dictionaries

    IEEE Trans. Image process.

    (2006)
  • DongW. et al.

    Image deblurring and super-resolution by adaptive sparse domain selection and adaptive regularization

    IEEE Trans. Image Process.

    (2011)
  • J. Mairal et al.

    Online dictionary learning for sparse coding

    Proceedings of the Twenty-Sixth Annual International Conference on Machine Learning

    (2009)
  • J. Mairal et al.

    Task-driven dictionary learning

    IEEE Trans. Pattern Anal. Mach. Intell.

    (2012)
  • DengC. et al.

    Weakly supervised multi-graph learning for robust image reranking

    IEEE Trans. Multimed.

    (2014)
  • DongW. et al.

    Nonlocally centralized sparse representation for image restoration

    IEEE Trans. Image Process.

    (2013)
  • ZhangX. et al.

    Bregmanized nonlocal regularization for deconvolution and sparse reconstruction

    SIAM J. Imaging Sci.

    (2010)
  • K. Dabov et al.

    Image denoising by sparse 3-d transform-domain collaborative filtering

    IEEE Trans. Image Process.

    (2007)
  • ZhangJ. et al.

    Group-based sparse representation for image restoration

    IEEE Trans. Image Process.

    (2014)
  • WenB. et al.

    Joint adaptive sparsity and low-rankness on the fly: an online tensor reconstruction scheme for video denoising

    Proceedings of the IEEE International Conference on Computer Vision (ICCV)

    (2017)
  • WenB. et al.

    When sparsity meets low-rankness: transform learning with non-local low-rank constraint for image restoration

    Proceedings of the 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

    (2017)
  • ZhaZ. et al.

    Image denoising via group sparsity residual constraint

    Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

    (2017)
  • WenB. et al.

    Structured overcomplete sparsifying transform learning with convergence guarantees and applications

    Int. J. Comput. Vis.

    (2015)
  • Cited by (61)

    • A matrix rank minimization-based regularization method for image restoration

      2022, Digital Signal Processing: A Review Journal
      Citation Excerpt :

      They include the famous methods, such as Tikhonov and total variational (TV)-based methods [3,4], nonlocal methods [5,6], sparse representation and dictionary learning methods [7,8], block-matching 3D filtering (BM3D) methods [9,10], etc. In recent years, by exploiting image nonlocal low-rank priors, the low-rank minimization (LRM) methods have been extensively applied for this problem and shown impressive image recovery effects [11–26]. In fact, the image nonlocal low-rank priors are exploited by the image nonlocal self-similarities [5,6], which assume the similar patches to a reference patch can be found in a noisy image, and by grouping and stacking these patches into column vectors to form a patch matching matrix, the corresponding matrix in the original clean image should be a low-rank matrix and has sparse singular values.

    View all citing articles on Scopus

    Zhiyuan Zha received the B.S. degrees in computer science from the JiangSu University, Zhenjiang, China, in 2010, and the M.S. degree in computer science from the Kunming University of Science and Technology, Kunming, China, in 2015. He is currently pursuing the Ph.D. degree with the Department of Electronic Science and Engineering, Nanjing University, Nanjing, China. His current research interests include inverse problems in image processing, sparse signal representation, Low rank matrix factorization and machine learning. He was a recipient of the best paper award at the IEEE International Conference on Multimedia & Expo (ICME) in 2017.

    Xinggan Zhang received the B.S. degree in electrical engineering from Nanjing University of Aeronautics and Astronautics, Nanjing, PR China, in1982, and the S.M. and Ph.D.degree from the same University in 1988 and 2001, respectively. In 1992, he joined the Department of Electronic Engineering at the NUAA, where he was an associate professor. In1999, he joined the Department of Electronic Science and Engineering at Nanjing University, where he is currently a professor. His research interests include target recognition and image processing.

    Yu Wu received the B.S. degrees with the Department of Electronic Science and Engineering, Nanjing University, Nanjing, China in 2015. She is currently pursuing the M.S. degree with the department of Electronic Scirnce and Engineering, California Institute of Technology, CA, USA. She current research interests include inverse problems in image processing, sparse signal representation, dictionary learning and machine learning.

    Qiong Wang received the B.S. and the Ph.D. degrees in Electronic Science and Engineering from PLA University of Science and Technology, China, in 2004 and 2011, respectively. Since 2014, she has been Lecturer at Nanjing University, China. Her current research interests include target automatic recognition and radar target detection.

    Xi Liu received the B.S. degree in computer science from the Changchun University of Science and Technology, Changchun, China, in 2003, and the M.S. degree in computer science from the Kunming University of Science and Technology, Kunming, China, in 2007. He is a Ph.D. candidate at the School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an, China. He is currently a Researcher with the Center of Machine Vision Research, Department of Computer Science and Engineering, University of Oulu, Finland. His current research interests include object detection and tracking, human gesture analysis, and behavior understanding.

    Lan Tang received the B.S and M.S. degrees in communication engineering from the Jilin University, Jilin, China, in 2002 and 2005, respectively, and the Ph.D. degree in information science and engineering from Southeast University, China, in 2009. She joined the school of electronic science and engineering, Nanjing University in 2009, and has been an associate professor since 2012. Her current research interests are wireless energy transfer, cooperative communication and optimization in wireless communications.

    Xin Yuan is currently a video analysis and coding lead researcher at Bell Labs, Murray Hill, NJ, USA. Prior to this, he had been a Post-Doctoral Associate with the Department of Electrical and Computer Engineering, Duke University from 2012 to 2015, where he was working on compressive sensing and machine learning. Before joining Duke, Dr. Yuan obtained his B.Eng. and M.Eng. from Xidian University in 2007 and 2009, respectively, and his Ph.D. from the Hong Kong Polytechnic University in 2012.

    Fully documented templates are available in the elsarticle package on CTAN.

    View full text