School of Mathematical Sciences/Institute of Computational Science, University of Electronic Science and Technology of China, Chengdu, Sichuan 611731, China uestc.edu.cn
School of Mathematical Sciences/Institute of Computational Science, University of Electronic Science and Technology of China, Chengdu, Sichuan 611731, China uestc.edu.cn
School of Mathematical Sciences/Institute of Computational Science, University of Electronic Science and Technology of China, Chengdu, Sichuan 611731, China uestc.edu.cn
School of Mathematical Sciences/Institute of Computational Science, University of Electronic Science and Technology of China, Chengdu, Sichuan 611731, China uestc.edu.cn
School of Mathematical Sciences/Institute of Computational Science, University of Electronic Science and Technology of China, Chengdu, Sichuan 611731, China uestc.edu.cn
School of Mathematical Sciences/Institute of Computational Science, University of Electronic Science and Technology of China, Chengdu, Sichuan 611731, China uestc.edu.cn
School of Mathematical Sciences/Institute of Computational Science, University of Electronic Science and Technology of China, Chengdu, Sichuan 611731, China uestc.edu.cn
School of Mathematical Sciences/Institute of Computational Science, University of Electronic Science and Technology of China, Chengdu, Sichuan 611731, China uestc.edu.cn
A combined total variation and high-order total variation model is proposed to restore blurred images corrupted by impulse noise or mixed Gaussian plus impulse noise. We attack the proposed scheme with an alternating direction method of multipliers (ADMM). Numerical experiments demonstrate the efficiency of the proposed method and the performance of the proposed method is competitive with the existing state-of-the-art methods.
1. Introduction
Image restoration is one of the most fundamental tasks in image processing and plays an important role in various areas of applied sciences [1]. In the literature of image restoration, there exist a lot of good methods dealing with images which are contaminated by single kind of noise, such as additive Gaussian noise or impulse noise. However, in many practical situations, the observed images are usually corrupted by mixed noise, for example, Gaussian plus impulse noise and Gaussian plus Poisson noise. In this work, we focus on Gaussian plus impulse noise. This kind of mixed noise is commonly caused by malfunctioning arrays in camera sensors or transmission errors [2]. We aim to find the unknown true image from the observed image defined by
()
where Nimp denote the process of image degradation with impulse noise, is a blurring matrix which is assumed to be known, and is an additive zero-mean Gaussian white noise of variance σ2. For simplicity and without loss of generality, we assume that the underlying images have square domains. Based on the noise values, impulse noise can be classified as salt-and-pepper noise and random-valued noise. Suppose that [dmin , dmax ] is the dynamic range of f and fj,k ((j, k) ∈ Ω = {1,2, …, n}×{1,2, …, n}) is the gray value of an image f at location (j, k) [3]. The operator g = Nimp(f) is defined as follows.
(i) Salt-and-pepper noise: the gray level of g at pixel location (j, k) is
()
where s is the noise ratio which defines the level of the salt-and-pepper noise.
(ii) Random-valued noise: the gray level of g at pixel location (j, k) is
()
where dj,k are uniformly distributed random numbers in [dmin , dmax ] and r is the noise ratio which defines the level of the random-valued noise.
It is obvious that it is more difficult to remove the random-valued impulse noise than salt-and-pepper noise since the random-valued impulse noise can be arbitrary number in [dmin , dmax ]. As is well known, recovering f form g is an ill-conditioned problem. A general approach to compute a meaningful approximation is the regularization method. Recently, variational models have attracted a lot of interest in cleaning mixed noise [3–9]. The key idea of these methods is based on a two-approach: detect the location of the impulse corrupted pixels then proceed with the filtering phase. For example, Cai et al. [4] proposed a two-phase approach for (1). In the first phase, they identify the location of the impulse noise and remove them from the data set through median filter. In the second phase, they minimize a functional of the form
()
where 𝒰 is the set of data samples that are likely to be uncorrupted with impulse noise and Φ(x) is the Mumford-Shah regularization term [10]:
()
where Γ is the edge set. Due to nonconvexity of Mumford-Shah regularizer, there exist numerous local minimums of (4). It is difficult to handle the Mumford-Shah functional. To overcome this difficulty, the Γ-convergence functional for Φ is used in [4]. The reconstruction performance is competitive; however the choice of p = 1 or p = 2 in (4) is depending on noise level and the computational performance is poor. In [5], Cai et al. accelerate the method in [4] and the computational time is much less than that in [4], although it is still highly depending on noise level. Recently, Li et al. [9] considered a functional with a content-dependent fidelity term and then proposed an iterative framelet-based approximation deblurring algorithm IFASDA. The advantage of IFASDA is that this algorithm is parameter free, which makes the proposed method more practical. We note that the total variation (TV) is not used in [4, 9]; however, the TV regularization is very popular [11] as its superiority of preserving sharp edges or object boundaries in the recovered images. The modified total variation minimization scheme is proposed in [3] to restore the images and an alternating minimization algorithm is employed to solve the proposed problem. In [8], a cost functional consisting of TV regularization term and l2 and l1 data fidelity terms is proposed to remove mixed Gaussian plus impulsive noise. Their numerical experiments showed that their method was very efficient and the reconstruction performance was quite competitive. However, as we know the TV norm transforms the smooth area to piecewise constants, the so-called staircase effect. In order to overcome this spurious effect, many high-order PDEs have been proposed [12–14] to solve this problem. Motivated by this, we propose a new model combining total variation and high-order total variation to restore the blurred images corrupted by Gaussian plus impulse noise. Our numerical experiments show the effectiveness of the proposed approach.
The outline of this paper is as follows. In Section 2, we briefly introduce the work of Huang et al. in [3] and the alternating direction method of multipliers (ADMM). In Section 3, we present the proposed algorithm. To demonstrate the effectiveness of the proposed method, we will show some numerical results on several test images in Section 4. Finally, some conclusion remarks are drawn in Section 5.
2. Brief Review of Related Methods
2.1. Review of Current Methods
In [3], Huang et al. proposed the following modified total variation minimization scheme to restore the blurred images corrupted by Gaussian plus impulse noise:
()
where 𝒰 is the set of data samples that are likely to be uncorrupted by impulse noise, p = 1 (or 2), α1 and α2 are two positive regularization parameters, and is the discrete total variation (TV) regularization term. The discrete TV of f is defined by . The discrete gradient operator is defined by with
()
for j, k = 1, …, n. Here fj,k refers to the ((k − 1)n + j)th entry of the vector f (it is the (j, k)th pixel location of the image). In [3], the median-type filter was used to identify the location of the possible noisy pixels in the first phase; then problem (6) was solved by alternating minimization method with respect to f and u. As reported in [3], they used the L1 norm in the experiment, and the restoration results by using L2 norm were about the same as those by using the L1 norm for impulse plus Gaussian noise condition.
2.2. The Alternating Direction Method of Multipliers (ADMM)
In this section, we present the alternating direction method of multipliers (ADMM) [15–17] which belongs to the family of augmented Lagrangian methods. Consider the following linearly constrained separable convex minimization problem of the form:
()
where and are closed proper convex functions, and are closed convex sets, and are given matrices, and b ∈ ℝl is a given vector. Specifically, the iterative scheme of ADMM for solving (8) is as follows.
Algorithm ADMM
(1)
Setk = 0 and choose β > 0, , and d0
(2)
repeat
(3)
,
(4)
,
(5)
,
(6)
k ← k + 1,
(7)
until stopping criterion is satisfied.
As reported in [18], the penalty parameter β can be substituted by a symmetric positive definite (spd) matrix Q and the extension of ADMM is still convergent. This leads to the following extension of algorithm ADMM.
Extension of Algorithm ADMM
(1)
Setk = 0 and choose β > 0, , and d0,
(2)
repeat
(3)
,
(4)
,
(5)
,
(6)
k ← k + 1,
(7)
until stopping criterion is satisfied.
3. The Proposed Approach
Throughout this paper, we will assume that the set of outlier (pixels corrupted with impulse noise) is known. Actually, we can use the adaptive median filter (AMF) [19] to detect salt-and-pepper noise and the adaptive center-weighted median filter (ACWMF) [20] for random-valued impulse noise case. Using the set 𝒰 represents the data samples that are likely to be uncorrupted by impulse noise; then we proposed the following objective function;
()
where Λ = diag (I[f∈𝒰]), I[·] is the indicator function, p = 1 (or 2), and [12]. For simplicity we introduce the notation . Then we will discuss the details of the algorithm to solve the model (9). For convenience we introduce three new variables and rewrite (9) in the constrained optimization problem as follows:
()
We apply the extension of ADMM algorithm to the constrained problem (10), which we call mixed noise image deblurring by extension of ADMM (MNID-ADMM). In the following algorithm, we can simply choose positive matrix Q as diag (β1I, β2I, β3I), where I is the identity matrix. If we set Q = βI, it is known as ADMM algorithm.
Algorithm of MNID-ADMM
(1)
Setk = 0, , and choose α1 > 0, α2 > 0 and positive matrix H,
(2)
repeat
(3)
,
(4)
,
(5)
,
(6)
,
(7)
,
,
,
(8)
k ← k + 1,
(9)
until stopping criterion is satisfied.
Cai et al. [4] considered to use lp (p = 1 or p = 2) as the data-fidelity term and discussed how to choose l1 or l2 norm. It is known that l1 data-fidelity term is more suitable than l2 data-fidelity when applying to remove impulse noise [21, 22]. From an experimental point of view, we find that it is faster to use l2 norm than l1 norm. Considering this, we use l2 data-fidelity term when the images are corrupted by mixed Gaussian plus impulse noise and we use l1 data-fidelity term when the images are corrupted by impulse noise only. Then, we will discuss the details of solving the v1, v2, v3, and f subproblems, respectively. For v1 subproblem, when p = 1, it is easy to solve the v1 subproblem through shrinkage and the minimizer v1 is given by
()
When p = 2, the minimizer v1 is given by . There are numerous algorithms to solve the v2 subproblem [11, 23–25]; here, we consider adopting Chambolle’s algorithm [25]. The minimizer v3 is given by
()
where . In order to get fk+1, we need to solve the following problem:
()
In image restoration, H is usually a matrix of special structure. For example, H is a block-circulant with circulant block (BCCB) matrix when periodic boundary conditions are applied to the image boundary. The matrix H can be diagonalized by the discrete fast Fourier transform (FFT) matrix. There are some fast algorithms to solve the problem (13) for different boundary conditions. In this paper, we use periodic boundary conditions. Then the solution of subproblem (13) can be exactly and efficiently calculated via fast Fourier transform.
4. Numerical Results
In this section, numerical experiments are presented to demonstrate the performance of our proposed MNID-ADMM for test images “Lena,” “Einstein,” “Cameraman,” and “Boat.” All test images are 256 × 256 gray level images. The results are compared with those obtained by the two-phase method denoted by “Cai-TP” [4] and the fast restoration method proposed in [3]. The splitting-and-penalty method is employed to solve the modified total variation scheme in [3]. As we know, the ADMM approach is more efficient and stable than the splitting-and-penalty method [26, 27]. For a fair comparison, we solve the total variation scheme (just set α2 = 0 in (9)) by ADMM rather than the splitting-and-penalty method used in [3]. For simplicity, we call this method “HADMM” hereafter. In order to measure the quality of the restored images by different methods, we introduce the mean squared error (MSE), and the peak signal-to-noise ratio (PSNR):
()
where f, g, n2 and MAXf are the original image, the blurred image, the number of pixels of image, and the maximum possible pixel value of the image, respectively. The higher PSNR, the better quality of the restoration. All the experiments are performed using MATLAB 7.10.0 on a computer equipped with an Intel(R) Pentium(R) 2.80 GHz processor, with 4.00 GB of RAM, and running Windows 7. The stop criterion of all methods is set to be . In order to reduce the computational time in the search for good regularization parameters, we set β1 = β2 for impulse noise only situation. It is reasonable to set α1 + α2 = 1; for further details, see [12]. Moreover, we find that we can get good restoration result by just setting β1 = β2 = β3 for impulse plus Gaussian noise situation. An out-of-focus kernel with radius 3 is used to blur the original images in the following examples. The parameters were hand tuned to give the best PSNR improvement. Similarly as in [4], we also use the same parameters for different images for the same convolution kernel and noise level.
Example 1. We restore images contaminated by impulse noise only. In this example, we consider the images corrupted by salt-and-pepper noise with level of 70% and random-valued noise with level of 55% separately. The four original images and the blurred images are shown in Figure 1. The comparisons of MNID-ADMM, Cai-TP, and HADMM methods are shown in Figures 2 and 3 and Table 1. From the restoration results, we get that the MNID-ADMM method performs better than Cai-TP both in restoration quality and computation times and we get a little higher PSNR than HADMM method for various images.
Table 1.
The PSNR (dB) and computing time (seconds) for the restoration results by MNID-ADMM, Cai-TP, and HADMM for blurred images contaminated by impulse noise only. The blurring kernel is the out-of-focus kernel of radius 3.
Top: the original images. Middle: Blurred and noisy images by using an out-of-focus kernel with radius 3 and corrupted by salt-and-pepper noise with noise level s = 70%. Bottom: blurred and noisy images by using an out-of-focus kernel with radius 3 and corrupted by random-valued noise with noise level r = 55%.
Images blurred with out-of-focus kernel of radius 3 and then corrupted by salt-and-pepper noise with noise level s = 70%. Top: the restored images by MNID-ADMM and the parameters we used are [α1 = 0.01, α2 = 0.005, β1 = β2 = 0.01, β3 = 5e − 6]. Middle: the restored images by Cai-TP. Bottom: the restored images by HADMM.
Images blurred with out-of-focus kernel of radius 3 and then corrupted by random-valued noise with noise level r = 55%. Top: the restored images by MNID-ADMM and the parameters we used are [α1 = 0.002, α2 = 0.005, β1 = β2 = 0.02, β3 = 5e − 6]. Middle: the restored images by Cai-TP. Bottom: the restored images by HADMM.
Example 2. We restore “Lena” contaminated by Gaussian noise of variance σ2 = 25 plus impulse noise with different level. The blurred and restored images by MNID-ADMM are shown in Figure 4 and the results are shown in Table 2. These results show that our proposed method can restore corrupted image with various noise level efficiently and the restore quality is quite well.
Table 2.
The PSNR (dB) and computing time (seconds) for the restoration results by MNID-ADMM, Cai-TP, and HADMM for blurred Lena contaminated by Gaussian noise (σ = 5) plus impulse noise. The blurring kernel is the out-of-focus kernel of radius 3.
Top: Lena image blurred with out-of-focus kernel of radius 3 and then corrupted by Gaussian noise with σ = 5 and salt-and-pepper noise with s = 30%, 50%, 70%, and 90%, respectively. The second line: results restored by MNID-ADMM (α1 = 0.9, β1 = β2 = β3 = 0.05). The third line: Lena image blurred with out-of-focus kernel of radius 3 and then corrupted by Gaussian noise with σ = 5 and random-valued noise with r = 25%, 40%, 55%, and 70%, respectively. Bottom: results restored by MNID-ADMM (α1 = 0.9, β1 = β2 = β3 = 0.05).
Example 3. We restore different images contaminated by Gaussian noise of variance σ2 = 25 plus impulse noise with different level. The blurred and restored images by MNID-ADMM are shown in Figures 5 and 6, and the results are shown in Tables 3 and 4. From the experiments results, we conclude that the proposed method can restore different images with various noise level quite well with the same parameters.
Table 3.
The PSNR (dB) and computing time (seconds) for the restoration results by MNID-ADMM, Cai-TP, and HADMM for blurred images contaminated by Gaussian noise (σ = 5) plus salt-and-pepper noise. The blurring kernel is the out-of-focus kernel of radius 3.
Type
Image
Level
MNID-ADMM
Cai-TP
HADMM
PSNR
Time
PSNR
Time
PSNR
Time
Gaussian + salt and pepper
Einstein
27.4
12.4
26.8
29.6
27.2
4.1
Cameraman
50%
25.1
12.5
24.6
24.6
25.1
3.4
Boat
25.7
12.9
25.4
18.4
25.5
3.4
Gaussian + salt and pepper
Einstein
26.6
13.8
26.1
29.8
26.2
4.7
Cameraman
70%
24.5
13.8
24.0
22.6
24.4
4.1
Boat
25.1
13.4
24.9
19.2
25.0
4.3
Table 4.
The PSNR (dB) and computing time (seconds) for the restoration results by MNID-ADMM, Cai-TP, and HADMM method for blurred images contaminated by random-valued noise plus Gaussian noise (σ = 5). The blurring kernel is the out-of-focus kernel of radius 3.
Top: images blurred with out-of-focus kernel of radius 3 and then corrupted by Gaussian noise with σ = 5 and salt-and-pepper noise with s = 50%. The second line: results restored by MNID-ADMM (α1 = 0.9, β1 = β2 = β3 = 0.05). The third line: Images blurred with out-of-focus kernel of radius 3, and then corrupted by Gaussian noise with σ = 5 and salt-and-pepper noise with s = 70%. Bottom: results restored by MNID-ADMM (α1 = 0.9, β1 = β2 = β3 = 0.05).
Top: images blurred with out-of-focus kernel of radius 3 and then corrupted by Gaussian noise with σ = 5 and random-valued noise with r = 55%. The second line: results restored by MNID-ADMM (α1 = 0.9, β1 = β2 = β3 = 0.05). The third line: images blurred with out-of-focus kernel of radius 3, and then corrupted by Gaussian noise with σ = 5 and random-valued noise with r = 70%. Bottom: results restored by MNID-ADMM (α1 = 0.9, β1 = β2 = β3 = 0.05).
5. Conclusion
In this paper, a high-order total variation scheme is proposed to restore blurred images corrupted by Gaussian plus impulse noise. The alternating direction method of multipliers (ADMM) is employed to solve the proposed problem. Numerical examples demonstrate that the proposed model efficiently removes the mixed Gaussian plus impulse noise meanwhile avoids staircase effect. The proposed method can be extended to solve blind convolution problems. One of the difficulties in this paper is how to choose appropriate parameters and an adaptive parameter chosen method may be used in this method. These are future works.
Acknowledgments
This research is supported by 973 Program (2013CB329404), NSFC (61170311), and Sichuan Province Science and Technology Research Project (2012GZX0080).
3Huang Y. M.,
Ng M. K., and
Wen Y. W., Fast image restoration methods for impulse and Gaussian noises removal, IEEE Signal Processing Letters. (2009) 16, 457–460.
4Cai J.-F.,
Chan R. H., and
Nikolova M., Two-phase approach for deblurring images corrupted by impulse plus Gaussian noise, Inverse Problems and Imaging. (2008) 2, no. 2, 187–204, https://doi.org/10.3934/ipi.2008.2.187, MR2395140, ZBL1154.94306.
5Cai J.-F.,
Chan R. H., and
Nikolova M., Fast two-phase image deblurring under impulse noise, Journal of Mathematical Imaging and Vision. (2010) 36, no. 1, 46–53, https://doi.org/10.1007/s10851-009-0169-7, MR2579308.
7Xiao Y.,
Zeng T. Y.,
Yu J., and
Ng M. K., Restoration of images corrupted by
mixed Gaussian-impulse noise via l1 − l0 minimization, Pattern Recognition. (2011) 44, 1708–1720.
8Rodríguez P.,
Rojas R., and
Wohlberg B., Mixed Gaissian-impulse noise restoration
via total variation, Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Process, 2012, 1077–1080.
9Li Y.-R.,
Shen L.,
Dai D.-Q., and
Suter B. W., Framelet algorithms for de-blurring images corrupted by impulse plus Gaussian noise, IEEE Transactions on Image Processing. (2011) 20, no. 7, 1822–1837, https://doi.org/10.1109/TIP.2010.2103950, MR2840120.
10Esedoglu S. and
Shen J., Digital inpainting based on the Mumford-Shah-Euler image model, European Journal of Applied Mathematics. (2002) 13, no. 4, 353–370, https://doi.org/10.1017/S0956792502004904, MR1925256, ZBL1017.94505.
12Lysaker M.,
Lundervold A., and
Tai X. C., Noise removal using fourth-order partial
differential equation with applications to medical magetic resonace images in space
and time, IEEE Transactions on Image Processing. (2003) 12, 1579–1590.
14Lysaker M. and
Tai X. C., Iterative image restoration combining total variation minimization and a second-order functional, International Journal of Computer Vision. (2006) 66, 5–18.
15Eckstein J. and
Bertsekas D. P., On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming. (1992) 55, no. 3, 293–318, https://doi.org/10.1007/BF01581204, MR1168183, ZBL0765.90073.
16Gabay D. and
Mercier B., A dual algorithm for the solution of nonlinear variational
problems via finite-element approximations, Computers & Mathematics with Applications. (1976) 2, 17–40.
17He B.,
Tao M., and
Yuan X., Alternating direction method with Gaussian back substitution for separable convex programming, SIAM Journal on Optimization. (2012) 22, no. 2, 313–340, https://doi.org/10.1137/110822347, MR2968856.
18Kontogiorgis S. and
Meyer R. R., A variable-penalty alternating directions method for convex optimization, Mathematical Programming. (1998) 83, no. 1, 29–53, https://doi.org/10.1016/S0025-5610(97)00103-2, MR1643963, ZBL0920.90118.
20Ko S. J. and
Lee Y. H., Center weighted median filters and their applications to
image enhancement, IEEE Transactions on Image Process. (1991) 42, 984–993.
21Nikolova M., Minimizers of cost-functions involving nonsmooth data-fidelity terms. Application to the processing of outliers, SIAM Journal on Numerical Analysis. (2002) 40, no. 3, 965–994, https://doi.org/10.1137/S0036142901389165, MR1949401, ZBL1018.49025.
22Nikolova M., A variational approach to remove outliers and impulse noise, Journal of Mathematical Imaging and Vision. (2004) 20, no. 1-2, 99–120, https://doi.org/10.1023/B:JMIV.0000011920.58935.9c, MR2049784.
23Goldstein T. and
Osher S., The split Bregman method for L1-regularized problems, SIAM Journal on Imaging Sciences. (2009) 2, no. 2, 323–343, https://doi.org/10.1137/080725891, MR2496060.
24Wang Y.,
Yang J.,
Yin W., and
Zhang Y., A new alternating minimization algorithm for total variation image reconstruction, SIAM Journal on Imaging Sciences. (2008) 1, no. 3, 248–272, https://doi.org/10.1137/080724265, MR2486032, ZBL1187.68665.
25Chambolle A., An algorithm for total variation minimization and applications, Journal of Mathematical Imaging and Vision. (2004) 20, no. 1-2, 89–97, https://doi.org/10.1023/B:JMIV.0000011320.81911.38, MR2049783.
26Bioucas-Dias J. M. and
Figueiredo M. A. T., Multiplicative noise removal using variable splitting and constrained optimization, IEEE Transactions on Image Processing. (2010) 19, no. 7, 1720–1730, https://doi.org/10.1109/TIP.2010.2045029, MR2790463.
27Huang Y.-M.,
Ng M. K., and
Wen Y.-W., A new total variation method for multiplicative noise removal, SIAM Journal on Imaging Sciences. (2009) 2, no. 1, 20–40, https://doi.org/10.1137/080712593, MR2486520.
Please check your email for instructions on resetting your password.
If you do not receive an email within 10 minutes, your email address may not be registered,
and you may need to create a new Wiley Online Library account.
Request Username
Can't sign in? Forgot your username?
Enter your email address below and we will send you your username
If the address matches an existing account you will receive an email with instructions to retrieve your username
The full text of this article hosted at iucr.org is unavailable due to technical difficulties.
