Issue 
Wuhan Univ. J. Nat. Sci.
Volume 28, Number 1, February 2023



Page(s)  61  67  
DOI  https://doi.org/10.1051/wujns/2023281061  
Published online  17 March 2023 
Computer Science
CLC number: TP 751
An Image Denoising Model via the Reconciliation of the Sparsity and LowRankness of the Dictionary Domain Coefficients
^{1}
Key Laboratory of Multidisciplinary Management and Control of Complex Systems of Anhui Higher Education Institutes, Anhui University of Technology, Maanshan 243002, Anhui, China
^{2}
School of Mathematics and Physics, Anhui University of Technology, Maanshan 243032, Anhui , China
^{†} To whom correspondence should be addressed. Email: zt9877@163.com
Received:
28
August
2022
Sparse coding has achieved great success in various image restoration tasks. However, if the sparse representation coefficients of the structure (lowfrequency information) and texture (highfrequency information) components of the image are under the same penalty constraint, the restoration effect may not be ideal. In this paper, an image denoising model combining mixed norm and weighted nuclear norm as regularization terms is proposed. The proposed model simultaneously exploits the group sparsity of the high frequency and lowrankness of the low frequency in dictionarydomain. The mixed norm is used to constrain the high frequency part and the weighted nuclear norm is used to constrain the low frequency part. In order to make the proposed model easy to solve under the framework of alternative direction multiplier method (ADMM), iterative shrinkage threshold method and weighted nuclear norm minimization method are used to solve the two subproblems. The validity of the model is verified experimentally through comparison with some stateoftheart methods.
Key words: image denoising / mixed norm / sparse representation / principal component analysis (PCA) dictionary
Biography: YANG Yifan, male, Master candidate, research direction: image processing. Email: 154232892@qq.com
Fundation item: Supported by the National Natural Science Foundation of China (61701004) and Outstanding Young Talents Support Program of Anhui Province(GXYQ2021178)
© Wuhan University 2023
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
0 Introduction
As a fundamental and important image processing task, image denoising has a wide range of applications ^{[13]}. Traditional methods are based on local denoising, i.e., all pixels in the vicinity of the current pixel are used to estimate the current pixel. As a result, the estimated pixel can be heavily influenced by the pixels in its neighborhood. In recent years, image denoising methods based on nonlocal block matching have achieved great success ^{[4,5]}. Buades et al^{[6]} proposed the nonlocal mean (NLM) filter, which estimates each pixel by a nonlocal averaging of all the pixels in the image . The most wellknown hybrid method for image denoising is the blockmatching and 3D filtering (BM3D) reported in Ref.[7], which groups similar patches into 3D arrays and deals with these arrays by sparse collaborative filtering, achieving better visual results in several image processing tasks. Jia et al^{[8]} proposed a joint sparse and lowrank matrix approximation problem by solving the nuclear norm and norm related minimization problem .
Using nonlocal selfsimilarity, nuclear norm minimization (NNM) has a wide range of applications in matrix decomposition and low rank representation ^{[9]}. Cai et al^{[10]} proved that the NNM can be easily solved by a softthresholding operation on the singular values of observation matrix . Given a matrix , the aim of NNM is to find a lowrank matrix by solving the following problem:
where and · denote the Frobenius norm and nuclear norm, respectively, and is a tradeoff parameter between the fidelity term and the low rank regularization term induced by the nuclear norm. The solution of problem (1) can be obtained by
where is the singular value decomposition (SVD) of and is the soft thresholding operator on diagonal matrix with parameter .
In many applications, it is hard for single to shrink all singular values. Large will overpenalty the large singular values, and small preserves large singular values but prevents NNM from obtaining lowrank solutions. In recent year, Gu et al^{[11,12]} proposed a weighted nuclear norm minimization (WNNM) to balance the rank and thresholding, and achieved competitive results .
Inspired by the above approach, group sparse coding (GSC) has shown great potential in a variety of image processing tasks in recent years. Instead of using a single patch as the basic unit of sparse coding, image processing is accomplished using groups of similar patches. GSC has great potential for solving many image problems that takes full advantage of local sparsity and nonlocal selfsimilarity^{[1316]}. Specifically, an image is divided into overlapped patches of size . For each patch , similar matching patches are selected from a sized search window to form a set . Note that the knearest neighbor (KNN) algorithm ^{[17]} is commonly used to search for similarly matched patches. Then all patches in are stacked into a matrix , i.e.,. The matrix consisting of patches with similar structure is called a patch group, where denotes the th patch in the th patch group. Similar to GSC, given a dictionary , each patch group can be sparsely represented by solving the following norm minimization problem,
where represents the group sparse coefficient of each patch group . However, since norm minimization is an NPhard optimization problem, it is often relaxed to the convex norm minimization ^{[18]}. Unfortunately, for some practical image processing tasks, such as image restoration, norm minimization is just an estimation to the norm minimization and cannot obtain the desirable sparse solution. Various norm minimization methods, like the weighted norm minimization ^{[19]}, the norm minimization^{ [20]} and the weighted Schatten norm minimization ^{[21]}, are proposed to solve the norm minimization problem.
Inspired by GSC prior and low rank prior mentioned above, in this paper we will propose a denoising model in which mixed norm and nuclear norm are employed to regularize the coefficients of the high and low frequency of the image. The proposed denoising model can be efficiently solved by the ADMM algorithm ^{[22]}, which provides a closed solution for each subproblem of the model.
1 Preliminaries
1.1 Nuclear Norm and Mixed Norm
Here, we briefly introduce nuclear norm and mixed norm ^{[23]}.
Definition 1 The weighted nuclear norm of a matrix is defined as
where and means the ith singular value of . The diagonal matrix of and consisting of elements and , respectively.
Definition 2 The mixed (1,1) norm of a matrix is defined as
The mixed (2,1) norm of a matrix is defined as
1.2 Adaptive Dictionary Learning
In Ref.[24], an adaptive dictionary learning approach is designed. For each patch group , its adaptive dictionary can be learned from its observation . Specifically, SVD is applied to :
where is a diagonal matrix, and , are the columns of and , respectively. Then each dictionary atom of the adaptive dictionary for every patch group is defined as:
Thus, an adaptive dictionary has been learned, i.e.,
It can be seen that the designed dictionary learning approach only requires one SVD operation for each patch group.
2 Proposed Model
In existing group sparse models, sparse coding is conducted the same on different components of the image such as structure and texture. In fact, an image can be decomposed into the low frequency (structure) and high frequency (texture) components, and it is difficult for single regularization term to enforce sparsity on different components. So in this subsection, we aim to recover the sparse coefficients of high and low frequency components simultaneously by solving the following problem:
where has the same meaning as that of group sparse model (2). are regularization parameters which control the balance between the fidelity term and the regularization terms. and represent the high frequency coefficient and the low frequency coefficient corresponding to the texture and structure components of the image, respectively.
The corresponding augmented Lagrange function of Eq. (11) is defined by
where is a positive parameter. In the following we use the ADMM algorithm to solve these proposed problem. Eq. (10) is decomposed into the following subproblems.
1) subproblem
For fixed , , the minimization problem for becomes
This is a quadratic problem and has a closedform solution:
2) subproblem
The subproblem of is a weighted nuclear norm minimization (WNNM) problem and is computed as follows
So, the solution of subproblem can be obtained by the following equation
where is a singular value decomposition of , and is the softthresholding operator with weight vector :
3) subproblem
The subproblem of is given explicitly by the twodimensional shrinkage
where and represents pointwise product.
4) update
We update by
Based on the above discussion, we summarize the complete algorithm of the proposed model (9) for image decomposition and denoising in Algorithm 1.
For simplicity, we terminate the Algorithm 1 with the relative change of in all experiments, i.e.,
The recovered high and low frequency components of the image can be obtained by reconstructing the PCA dictionary from , and then aggregating all the estimated patch groups , .
Algorithm 1 

Initialization: Input . Iteration: 1. While to MaxIter or Eq. (16) is satisfied. 2. Iterative regularization 3. For each patch in do 4. Find nonlocal similar patches from group . 5. Compute by Eq. (11). 6. Compute by Eq. (12). 7. Compute by Eq. (14). 8. Compute by Eq. (15). 9. Get the estimation: . 10. End for 11. 12. Aggregate to form the denoised image . 13. End while. 14. Output: The final denoised image . 
3 Experiments
In this section, we present various numerical results to illustrate the performance of the proposed model for image decomposition and denoising. Figure 1 shows the test images used in this paper.
Fig. 1 Test images 
3.1 Image Decomposition Results
For image decomposition, the goal of the proposed model is to separate the high frequency information from the low frequency information in the image. Generally speaking, the structure and contours in an image belong to the low frequency components, while small details, textures and noise in an image belong to the high frequency components.We use the image Starfish shown in Fig. 2(a) to give a clear insight into the behavior of the proposed decomposition model. Figure 2(b) and 2(c) show the "cartoon + texture" decomposition result on noiseless Starfish image. For noisy Starfish image in Fig. 2(d), the proposed model also produces reasonable highlow frequency decomposition. The Starfish image is decomposed into simple cartoon component (low frequency) and noisy component (high frequency).
Fig. 2 Decomposition result on Starfish. Tifby the proposed method (a)(c):decomposition result on noiseless image; (d)(f): decomposition result on noisy image 
3.2 Image Denoising Results and Comparison with Other Methods
For image denoising, we compare the proposed method with other advanced methods including nonlocal means (NLM ^{[6]}), BM3D ^{[7]} and EPLL ^{[25] }in terms of objective and perceptual metrics. Both NLM and BM3D are based on the prior of nonlocal self similarity, and EPLL is a patchprior based denoising method which ensures denoising performance in ensemble approximation by local patch denoising. In the proposed method, the size of patch is set to for . The parameters are set to (7,10,40), (7,9,80) and (6,8,180) for noise level , and , respectively. In Fig. 3, we show the visual comparison of the denoising results with noise level obtained by different methods. From visual comparison, we can see that the images restored by NLM and BM3D seem oversmooth and EPLL produces some bad artifacts. Images restored by our algorithm has better denoising performance and less staircase artifacts compared with the other three methods.
Fig. 3 Visual comparison results with noise level by different denoising methods 
The peak signaltonoise (PSNR) ratio is employed to measure the quality of the recovered images which is defined as:
where u is the restored image, f is the true image, m and n denote the size of the image. However, the PSNR only considers the global statistics of image pixel values with neglect of the local visual factor of human eyes, which make it is impossible to access local image quality. To this end, an objective image quality evaluation index conforming to the characteristics of human visual system, structural similarity (SSIM)^{[26]}, was proposed. The advantage of SSIM is that it assesses the reconstructed image from the perspective of luminance, contrast and structure. Thus, we select the PSNR and SSIM as quality evaluation criteria to quantitatively assess the reconstruction performance.
The PSNR and SSIM results of all methods are shown in Table 1. The proposed method has an average PSNR gain of up to 1.5dB, 0.31dB and 0.46dB compared with NLM, BM3D and EPLL, respectively. Overall, the proposed method achieves better numerical results.
Results with different methods for PSNR and SSIM
4 Conclusion
This paper proposed a new group sparse denoising model, in which the weighted nuclear norm and l_{2,1} mixed norm are employed as regularization terms to simultaneously enforce the priors on low and high frequency of the image. The proposed model can be solved efficiently based on the ADMM framework. Experimental results have demonstrated that the proposed method achieves comparable performance to some stateoftheart methods.
References
 Elad M, Aharon M. Image denoising via sparse and redundant representations over learned dictionaries[J]. IEEE Transactions on Image Processing, 2006, 15(12):37363745. [NASA ADS] [CrossRef] [MathSciNet] [PubMed] [Google Scholar]
 Guo Q , Zhang C M, Zhang Y F, et al. An efficient SVDbased method for image denoising[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2016, 26(5):868880. [CrossRef] [Google Scholar]
 Foi A , Katkovnik V , Egiazarian K . Pointwise shapeadaptive DCT for highquality denoising and deblocking of grayscale and color images[J]. IEEE Transactions on Image Processing, 2007, 16(5): 13951411. [NASA ADS] [CrossRef] [MathSciNet] [PubMed] [Google Scholar]
 Katkovnik V, Ponomarenko M, Egiazarian K. Complex domain nonlocal blockmatching denoising based on highorder singular value decomposition (HOSVD)[C] // 2017 25th European Signal Processing Conference (EUSIPCO). Washington D C: IEEE, 2017: 718722. [Google Scholar]
 Dong W S, Shi G M, Ma Y, et al. Image restoration via simultaneous sparse coding: where structured sparsity meets Gaussian scale mixture[J]. International Journal of Computer Vision, 2015, 114(23):217232. [CrossRef] [MathSciNet] [Google Scholar]
 Buades A, Coll B, Morel J. A nonlocal algorithm for image denoising[C] // 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05). Washington D C: IEEE, 2005, 2: 6065. [Google Scholar]
 Dabov K, Foi A, Katkovnik V, et al. Image denoising by sparse 3D transformdomain collaborative filtering[J]. IEEE Transactions on Image Processing, 2007, 16(8): 20802095. [CrossRef] [Google Scholar]
 Jia X X, Feng X, Wang W, et al. Bayesian inference for adaptive low rank and sparse matrix estimation[J]. Neurocomputing, 2018, 291(24):7183. [Google Scholar]
 Fazel S M. Matrix Rank Minimization with Applications [D].Palo Alto: Stanford University, 2002. [Google Scholar]
 Cai J F, Candès E J, Shen Z. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization , 2010, 20(4): 19561982. [CrossRef] [MathSciNet] [Google Scholar]
 Gu S H, Zhang L, Zuo W, et al. Weighted nuclear norm minimization and its applications to low level vision[J]. International Journal of Computer Vision, 2017, 121(2): 183208. [CrossRef] [Google Scholar]
 Gu S H, Zhang L, Zuo W, et al. Weighted nuclear norm minimization with application to image denoising[C]// 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Washington D C: IEEE, 2014: 28622869. [Google Scholar]
 Zhang J, Zhao D, Gao W. Groupbased sparse representation for image restoration[J]. IEEE Transactions on Image Processing, 2014, 23(8):3336. [NASA ADS] [CrossRef] [MathSciNet] [PubMed] [Google Scholar]
 Wang Q, Zhang X G, Wu Y, et al. Nonconvex weighted l_{p }minimization based group sparse representation framework for image denoising[J]. IEEE Signal Processing Letters, 2017, 24(11): 16861690. [NASA ADS] [CrossRef] [Google Scholar]
 Mairal J, Bach F, Ponce J, et al. Nonlocal sparse models for image restoration[C]// 2009 IEEE 12th International Conference on Computer Vision. Washington D C: IEEE, 2009: 22722279. [Google Scholar]
 Li S T, Yin H T, Fang L Y. Groupsparse representation with dictionary learning for medical image denoising and fusion[J]. IEEE Transactions on Biomedical Engineering, 2012, 59(12):34503459. [NASA ADS] [CrossRef] [PubMed] [Google Scholar]
 Keller J M, Gray M R, Givens J A. A fuzzy knearest neighbor algorithm[J]. IEEE Transactions on Systems Man & Cybernetics, 1985, 15(4):580585. [CrossRef] [Google Scholar]
 Donoho D L . For most large underdetermined systems of linear equations the minimal 1norm solution is also the sparsest solution[J]. Communications on Pure and Applied Mathematics, 2006, 59(6): 797829. [CrossRef] [MathSciNet] [Google Scholar]
 Candès E J, Wakin M B, Boyd S P. Enhancing sparsity by reweighted l_{1} minimization[J]. Journal of Fourier Analysis & Applications, 2008, 14(56): 877905. [CrossRef] [MathSciNet] [Google Scholar]
 Xu Z B, Chang X Y, Xu F M, et al. L1/2 Regularization: A thresholding representation theory and a fast solver[J]. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(7):10131027. [CrossRef] [PubMed] [Google Scholar]
 Xie Y, Gu S H, Liu Y, et al. Weighted schatten pnorm minimization for image denoising and background subtraction[J]. IEEE Transactions on Image Processing, 2016, 25(10):48424857. [NASA ADS] [CrossRef] [MathSciNet] [Google Scholar]
 Chartrand R, Wohlberg B. A nonconvex ADMM algorithm for group sparsity with sparse groups[C]// 2013 IEEE International Conference on Acoustics, Speech and Signal Processing. Washington D C: IEEE, 2013: 60096013. [Google Scholar]
 Fu H Y, Ng M K, Nikolova M, et al. Efficient minimization methods of mixed l_{2}l_{1} and l_{1}l_{1} norms for image restoration[J]. SIAM Journal on Scientific Computing, 2006, 27(6):18811902. [CrossRef] [MathSciNet] [Google Scholar]
 Zha Z Y, Yuan X, Wen B H, et al. A benchmark for sparse coding: When group sparsity meets rank minimization[J]. IEEE Transactions on Image Processing, 2020, 29:50945109. [NASA ADS] [CrossRef] [MathSciNet] [Google Scholar]
 Zoran D , Weiss Y. From learning models of natural image patches to whole image restoration [C]// IEEE International Conference on Computer Vision. Washington D C: IEEE, 2011: 479486. [Google Scholar]
 Wang Z, Bovik A C, Sheikh H R, et al. Image quality assessment: From error visibility to structural similarity[J]. IEEE Transactions on Image Processing, 2004, 13: 600612. [NASA ADS] [CrossRef] [PubMed] [Google Scholar]
All Tables
All Figures
Fig. 1 Test images  
In the text 
Fig. 2 Decomposition result on Starfish. Tifby the proposed method (a)(c):decomposition result on noiseless image; (d)(f): decomposition result on noisy image 

In the text 
Fig. 3 Visual comparison results with noise level by different denoising methods  
In the text 
Current usage metrics show cumulative count of Article Views (fulltext article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 4896 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.