Non-convex weighted ℓp nuclear norm based ADMM framework for image restoration☆
Introduction
Image restoration (IR) aims to reconstruct a high quality image from its degraded observation which can be generally expressed as where is a non-invertible linear degradation operator and η is the vector of some independent white Gaussian noise. With different settings of matrix various IR problems can be derived from Eq. (1), such as image denoising [1], [2], [3], [4], [5] when is an identity matrix, image deblurring [6], [7], [8], [9] when is a blur operator, image inpainting [10], [11], [12], [13] when is a mask and image compressive sensing (CS) recovery when 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, 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)
- et al.
Image denoising and enhancement based on adaptive fractional calculus of small probability strategy
Neurocomputing
(2016) - et al.
Bayesian non-parametric gradient histogram estimation for texture-enhanced image deblurring
Neurocomputing
(2016) - et al.
Video-based non-uniform object motion blur estimation and deblurring
Neurocomputing
(2012) - et al.
Robust object removal with an exemplar-based image inpainting approach
Neurocomputing
(2014) - et al.
Inexact alternating direction method based on proximity projection operator for image inpainting in wavelet domain
Neurocomputing
(2016) - et al.
Image reconstruction algorithm from compressed sensing measurements by dictionary learning
Neurocomputing
(2015) - et al.
Image reconstruction with locally adaptive sparsity and nonlocal robust regularization
Signal Process. Image Commun.
(2012) - et al.
Nonlinear total variation based noise removal algorithms
Phys. D Nonlinear Phenom.
(1992) - et al.
Image compressive sensing recovery using adaptively learned sparsifying basis via l0 minimization
Signal Process.
(2014) - et al.
A comparison of typical ℓp minimization algorithms
Neurocomputing
(2013)
Exact minimum rank approximation via schatten p-norm minimization
J. Comput. Appl. Math.
Nonconvex lp nuclear norm based admm framework for compressed sensing
Proceedings of the Data Compression Conference (DCC), 2016
A non-local algorithm for image denoising
Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
Non-local sparse models for image restoration
Proceedings of the IEEE Twelfth International Conference on Computer Vision
Weighted nuclear norm minimization with application to image denoising
Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition
Weighted couple sparse representation with classified regularization for impulse noise removal
IEEE Trans. Image Process.
Robust image restoration via adaptive low-rank approximation and joint kernel regression
IEEE Trans. Image Process.
Image restoration using joint statistical modeling in a space-transform domain
IEEE Trans. Circuits Syst. Video Technol.
Annihilating filter-based low-rank Hankel matrix approach for image inpainting
IEEE Trans. Image Process.
Nonparametric Bayesian dictionary learning for analysis of noisy and incomplete images
IEEE Trans. Image Process.
Image compressive sensing recovery via collaborative sparsity
IEEE J. Emerg. Sel. Top. Circuits Syst.
Parallel lensless compressive imaging via deep convolutional neural networks
Opt. Express
Compressed sensing image reconstruction via adaptive sparse nonlocal regularization
Vis. Comput.
Slope: shrinkage of local overlapping patches estimator for lensless compressive imaging
IEEE Sens. J.
Convergence rates for tikhonov regularisation of non-linear ill-posed problems
Inverse Prob.
An algorithm for total variation minimization and applications
J. Math. Imaging Vis.
k-svd: an algorithm for designing over complete dictionaries for sparse representation
IEEE Trans. Signal Process.
Image denoising via sparse and redundant representations over learned dictionaries
IEEE Trans. Image process.
Image deblurring and super-resolution by adaptive sparse domain selection and adaptive regularization
IEEE Trans. Image Process.
Online dictionary learning for sparse coding
Proceedings of the Twenty-Sixth Annual International Conference on Machine Learning
Task-driven dictionary learning
IEEE Trans. Pattern Anal. Mach. Intell.
Weakly supervised multi-graph learning for robust image reranking
IEEE Trans. Multimed.
Nonlocally centralized sparse representation for image restoration
IEEE Trans. Image Process.
Bregmanized nonlocal regularization for deconvolution and sparse reconstruction
SIAM J. Imaging Sci.
Image denoising by sparse 3-d transform-domain collaborative filtering
IEEE Trans. Image Process.
Group-based sparse representation for image restoration
IEEE Trans. Image Process.
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)
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)
Image denoising via group sparsity residual constraint
Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
Structured overcomplete sparsifying transform learning with convergence guarantees and applications
Int. J. Comput. Vis.
Cited by (61)
Noise and distortion suppression for industrial confocal microscopy
2024, Optics CommunicationsImproved Image Compressive Sensing Recovery with Low-Rank Prior and Deep Image Prior
2023, Signal ProcessingA matrix rank minimization-based regularization method for image restoration
2022, Digital Signal Processing: A Review JournalCitation 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.
Remove the salt and pepper noise based on the high order total variation and the nuclear norm regularization
2022, Applied Mathematics and Computation
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.