[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Sparse representation based image deblurring model under random-valued impulse noise

  • Published:
Multidimensional Systems and Signal Processing Aims and scope Submit manuscript

Abstract

In this article, we introduce a new patch-based model for restoring images simultaneously corrupted by blur and random-valued impulse noise. The model involves a \(l_0\)-norm data-fidelity term, a sparse representation prior over learned dictionaries, and the total variation (TV) regularization. Unlike previous works Cai et al. (Inverse Probl Imaging 2(2):187–204, 2008), Ma et al. (SIAM J Imaging Sci 6(4):2258–2284, 2013), one-phase approach is utilized for random-valued impulse noise. As in Yuan and Ghanem (IEEE conference on computer vision and pattern recognition (CVPR), pp 5369–5377, 2015), the \(l_0\) data-fitting term plays an influential role for removing random-valued impulse noise. Moreover, the sparse representation prior enables to preserve textures and details efficiently, whereas TV regularization locally smoothes images while keeping sharp edges. To handle nonconvex and nondifferentiable terms, we adopt a variable splitting scheme, and then the penalty method and alternating minimization algorithm are employed. This results in an efficient iterative algorithm for solving our model. Numerical results are reported to show the effectiveness of the proposed model compared with the state-of-the-art methods.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Aharon, M., Elad, M., & Bruckstein, A. (2006). K-svd: An algorithm for designing of overcomplete dictionaries for sparse representation. IEEE Transactions on Signal Processing, 54(11), 4311–4322.

    MATH  Google Scholar 

  • Bai, M., Zhang, X., & Shao, Q. (2016). Adaptive correction procedure for TVL1 image deblurring under impulse noise. Inverse Problems, 32(8), 85004–85026.

    MathSciNet  MATH  Google Scholar 

  • Bar, L., Sochen, N., & Kiryati, N. (2006). Image deblurring in the presence of salt-and-pepper noise. International Journal of Computer Vision, 70(3), 279–298.

    MATH  Google Scholar 

  • Blomgren, P., & Chan, T. F. (1998). Color TV: Total variation methods for restoration of vector-valued images. IEEE Transactions on Image Processing, 7(3), 304–309.

    Google Scholar 

  • Brownrigg, D. (1984). The weighted median filter. Communications of the ACM, 27, 807–818.

    Google Scholar 

  • Buades, A., Coll, B., & Morel, J. M. (2005). A review of image denoising algorithms with a new one. Multiscale Modeling and Simulation, 4(2), 490–530.

    MathSciNet  MATH  Google Scholar 

  • Cai, J. F., Chan, R., & Nikolova, M. (2008). Two-phase approach for deblurring images corrupted by impulse plus Gaussian noise. Inverse Problems and Imaging, 2(2), 187–204.

    MathSciNet  MATH  Google Scholar 

  • Cai, J. F., Chan, R. H., & Nikolova, M. (2010). Fast two-phase image deblurring under impulse noise. Journal of Mathematical Imaging and Vision, 36(46), 46–53.

    MathSciNet  Google Scholar 

  • Chan T.-F., & Zhou, H.-M. (2001). Adaptive eno-wavelet transforms for discontinuous functions. In 12th international conference on domain decomposition methods (pp. 93–100).

  • Chan, T., Esedoglu, S., Park, F., & Yip, A. (2006). Total variation image restoration: Overview and recent developments. In N. Paragios, Y. Chen, & O. D. Faugeras (Eds.), Handbook of mathematical models in computer vision (pp. 17–31). New York: Springer

  • Chan, R. H., & Chen, K. (2010). A multilevel algorithm for simultaneously denoising and deblurring images. SIAM Journal on Scientific Computing, 32(2), 1043–1063.

    MathSciNet  MATH  Google Scholar 

  • Chan, R. H., Dong, Y., & Hintermüller, M. (2010). An efficient two-phase L1-TV method for restoring blurred images with impulse noise. IEEE Transactions on Image Processing, 19(7), 1731–1739.

    MathSciNet  MATH  Google Scholar 

  • Chen, T., & Wu, H. (2001). Space variant median filters for the restoration of the impulse noise corrupted images. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 48(8), 784–789.

    MATH  Google Scholar 

  • Chen, T., & Wu, H. R. (2001). Adaptive impulse detection using center-weighted median filters. IEEE Signal Processing Letters, 8(1), 1–3.

    Google Scholar 

  • Courant, R. (1943). Variational methods for the solution of problems of equilibrium and vibrations. Bulletin of the American Mathematical Society, 49, 1–23.

    MathSciNet  MATH  Google Scholar 

  • Csiszár, I., & Tusná, G. (1984). Information geometry and alternating minimization procedures. Statistics and Decisions, 1, 205–237.

    MathSciNet  Google Scholar 

  • Daubechies, I., Defriese, M., & Mol, C. (2004). An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Communications on Pure and Applied Mathematics, 57(11), 1413–1457.

    MathSciNet  MATH  Google Scholar 

  • Delon, J., & Desolneux, A. (2013). A patch-based approach for removing impulse or mixed Gaussian-impulse noise. SIAM Imaging Science, 6(2), 1140–1174.

    MathSciNet  MATH  Google Scholar 

  • Dong, Y., Hintermüller, M., & Neri, M. (2009). An efficient primal-dual method for L1TV image restoration. SIAM Journal on Imaging Sciences, 2(4), 1168–1189.

    MathSciNet  MATH  Google Scholar 

  • Dong, B., Ji, H., Li, J., Shen, Z., & Xu, Y. (2012). Wavelet frame based blind image inpainting. Applied and Computational Harmonic Analysis, 32(2), 268–279.

    MathSciNet  MATH  Google Scholar 

  • Dong, W., Zhang, L., Shi, G., & Wu, X. (2011). Image deblurring and super-resolution by adaptive sparse domain selection and adaptive regularization. IEEE Transactions on Image Processing, 20(7), 1838–1857.

    MathSciNet  MATH  Google Scholar 

  • Donoho, D., & Johnstone, I. (1994). Ideal spatial adaptation by wavelet shrinkage. Biometrika, 81(3), 425–455.

    MathSciNet  MATH  Google Scholar 

  • Elad, M., & Aharon, M. (2006). Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image Processing, 15(12), 3736–3745.

    MathSciNet  Google Scholar 

  • Figueiredo, M., Bioucas-Dias, J., & Nowak, R. (2007). Majorization-minimization algorithms for wavelet-based image restoration. IEEE Transactions on Image Processing, 16(12), 2980–2991.

    MathSciNet  Google Scholar 

  • Fletcher, R. (1983). Penalty functions. In: Mathematical Programming The State of the Art (pp. 87–114). Springer.

  • Gilboa, G., & Osher, S. (2008). Nonlocal operators with applications to image processing. SIAM Journal on Multiscale Modeling and Simulation, 7(3), 1005–1028.

    MathSciNet  MATH  Google Scholar 

  • Guo, X., Li, F., & Ng, M. K. (2009). A fast L1-TV algorithm for image restoration. SIAM Journal on Scientific Computing, 31(3), 2322–2341.

    MathSciNet  MATH  Google Scholar 

  • Huang, Y. M., Moisan, L., Ng, M. K., & Zeng, T. (2012). Multiplicative noise removal via a learned dictionary. IEEE Transactions on Image Processing, 21(11), 4534–4543.

    MathSciNet  MATH  Google Scholar 

  • Hu, H., Li, B., & Liu, Q. (2016). Removing mixture of Gaussian and impulse noise by patch-based weighted means. Journal of Scientific Computing, 67(1), 103–129.

    MathSciNet  MATH  Google Scholar 

  • Hwang, H., & Haddad, R. (1995). Adaptive median filters: New algorithms and results. IEEE Transactions on Image Processing, 4(4), 499–502.

    Google Scholar 

  • Kaleem, M., Guergachi, A., & Krishnan, S. (2013). Empiricalmode decomposition based sparse dictionary learning with application to signal classification. In: Digital signal processing and signal processing education meeting (DSP/SPE, IEEE) (pp. 18–23).

  • Ko, S., & Lee, Y. (1991). Center weighted median filters and their applications to image enhancement. IEEE Transactions on Circuits and Systems, 38(9), 984–993.

    Google Scholar 

  • Li, Y. R., Shen, L., Dai, D. Q., & Suter, B. W. (2011). Framelet algorithms for de-blurring images corrupted by impulse plus Gaussian noise. IEEE Transactions on Image Processing, 20(7), 1822–1837.

    MathSciNet  MATH  Google Scholar 

  • Liu, J., Huang, T. Z., Lv, X. G., & Huang, J. (2015). Restoration of blurred color images with impulse noise. Computers and Mathematics with Applications, 70(6), 1255–1265.

    MathSciNet  Google Scholar 

  • Li, S., Wang, G., & Zhao, X. (2016). Multiplicative noise removal via adaptive learned dictionaries and TV regularization. Digital Signal Processing, 50, 218–228.

    Google Scholar 

  • Lou, Y., Bertozzi, A., & Soatto, S. (2011). Direct sparse deblurring. Journal of Mathematical Imaging and Vision, 39(1), 1–12.

    MathSciNet  MATH  Google Scholar 

  • Ma, L., Moisan, L., Yu, J., & Zeng, T. (2013). A dictionary learning approach for poisson image deblurring. IEEE Transactions on Medical Imaging, 32(7), 1277–1289.

    Google Scholar 

  • Ma, L., Yu, J., & Zeng, T. (2013). Sparse representation prior and total variation based image deblurring under impulse noise. SIAM Journal on Imaging Sciences, 6(4), 2258–2284.

    MathSciNet  MATH  Google Scholar 

  • Nikolova, M. (2002). Minimizers of cost-functions involving nonsmooth data-fidelity terms. application to the processing of outliers. SIAM Journal on Numerical Analysis, 40, 965–994.

    MathSciNet  MATH  Google Scholar 

  • Nikolova, M. (2004). A variational approach to remove outliers and impulse noise. Journal of Mathematical Imaging and Vision, 20(1–2), 99–120.

    MathSciNet  MATH  Google Scholar 

  • Nocedal, J., & W, S. J. (2006). Numerical optimization. New York: Springer.

    MATH  Google Scholar 

  • Pati, Y.C., Rezaiifar, R., & Krishnaprasad, P. (1993). Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In 1993 Conference record of the twenty-seventh asilomar conference on signals, systems and computers 1993 (pp. 40–44).

  • Pok, G., Liu, J., & Nair, A. (2003). Selective removal of impulse noise based on homogeneity level information. IEEE Transactions on Image Processing, 12(1), 85–92.

    Google Scholar 

  • Pratt, W. (1975). Median filtering. Technical report, Image Processing Institute, University of Southern California, Los Angeles.

  • Protter, M., & Elad, M. (2009). Image sequence denoising via sparse and redundant representations. IEEE Transactions on Image Processing, 18(1), 27–35.

    MathSciNet  MATH  Google Scholar 

  • Rudin, L., Osher, S., & Fatemi, E. (1992). Nonlinear total variation based noise removal algorithms. Physica D: Nonlinear Phenomena, 60(1–4), 259–268.

    MathSciNet  MATH  Google Scholar 

  • Shi, Y., Fang, H., & Wang, G. (2014). Poissonian image deconvolution via sparse and redundant representations and framelet regularization. Mathematical Problems in Engineering, 2014, 917040.

  • Wang, Z., Bovik, A. C., Sheikh, H. R., & Simoncelli, E. P. (2004). Image quality assessment: From error visibility to structural similarity. IEEE Transactions on Image Processing, 13(4), 600–612.

    Google Scholar 

  • Wang, S., Liu, Q., Xia, Y., Dong, P., Luo, J., Huang, Q., et al. (2013). Dictionary learning based impulse noise removal via L1–L1 minimization. Signal Processing, 93(9), 2696–2708.

    Google Scholar 

  • Wang, S. S., & Wu, C. H. (2009). A new impulse detection and filtering method for removal of wide range impulse noises. Pattern Recognition, 42(9), 2194–2202.

    MATH  Google Scholar 

  • Wang, Y., Yang, J., Yin, W., & Zhang, Y. (2008). A new alternating minimization algorithm for total variation image reconstruction. SIAM Journal on Imaging Sciences, 1(3), 248–272.

    MathSciNet  MATH  Google Scholar 

  • Wu, C., Zhang, J., & Tai, X. C. (2011). Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems and Imaging, 5(1), 237–261.

    MathSciNet  MATH  Google Scholar 

  • Xiao, Y., & Zeng, T. (2010). Poisson noise removal via learned dictionary. In Proceedings IEEE International Conference on Image Processing (pp. 1177–1180).

  • Xiao, Y., Zeng, T., Yu, J., & Ng, M. K. (2011). Restoration of images corrupted by mixed Gaussian-impulse noise via l1–l0 minimization. Pattern Recognition, 44(8), 1708–1720.

    MATH  Google Scholar 

  • Xiong, B., & Yin, Z. (2012). A universal denoising framework with a new impulse detector and nonlocal means. IEEE Transactions on Image Processing, 21(4), 1663–1675.

    MathSciNet  MATH  Google Scholar 

  • Xu, Y., & Yin, W. (2013). A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM Journal on Imaging Sciences, 6(3), 1758–1789.

    MathSciNet  MATH  Google Scholar 

  • Yan, M. (2013). Restoration of images corrupted by impulse noise and mixed Gaussian impulse noise using blind inpainting. SIAM Journal on Imaging Sciences, 6(3), 1227–1245.

    MathSciNet  MATH  Google Scholar 

  • Yang, J., Zhang, Y., & Yin, W. (2009). An efficient TVL1 algorithm for deblurring multichannel images corrupted by impulsive noise. SIAM Journal on Scientific Computing, 31(4), 2842–2865.

    MathSciNet  MATH  Google Scholar 

  • Yang, J., Zhao, Y. Q., Chan, J. W., et al. (2016). Coupled sparse denoising and unmixing with low rank constraint for hyper-spectral imag. IEEE Transactions on Geoscience and Remote Sensing, 54(3), 1818–1833.

    Google Scholar 

  • Yuan, G., & Ghanem, B. (2015). \(l_0\)TV: A new method for image restoration in the presence of impulse noise. In IEEE conference on computer vision and pattern recognition (CVPR) (pp. 5369–5377).

  • Zeng, T., Li, X., & Ng, M. (2010). Alternating minimization method for total variation based wavelet shrinkage model. Communications in Computational Physics, 8(5), 976–994.

    MathSciNet  MATH  Google Scholar 

  • Zeng, T., Li, X., & Ng, M. (2010). Alternating minimization method for total variation based wavelet shrinkage model. Computer Physics Communications, 8(5), 976–994.

    MathSciNet  MATH  Google Scholar 

  • Zhang, H., Yang, J., Zhang, Y., & Huang, T. (2011). Sparse representation based blind image deblurring. In Proceedings IEEE international conference on multimedia and expo (ICME) (pp. 1–6 ).

  • Zhao, Y. Q., & Yang, J. (2015). Hyperspectral image denoising via sparse representation and low-rank constraint. IEEE Transactions on Geoscience and Remote Sensing, 53(1), 296–308.

    Google Scholar 

Download references

Acknowledgements

Myeongmin Kang was supported by the NRF (2016R1C1B1009808). Myungjoo Kang was supported by the NRF (2015R1A5A1009350, 2017R1A2A1A17069644), and IITP-MSIT (B0717-16-0107). Miyoun Jung was supported by Hankuk University of Foreign Studies Research Fund and the NRF (2017R1A2B1005363).

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences, Seoul National University, Seoul, Korea

    Myeongmin Kang & Myungjoo Kang

  2. Department of Mathematics, Hankuk University of Foreign Studies, Yongin, Korea

    Miyoun Jung

Authors
  1. Myeongmin Kang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Myungjoo Kang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Miyoun Jung
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Miyoun Jung.

Appendix

Appendix

Proof of Lemma 1

Define \(\varPhi _1\) and \(\varPhi _2\) as the objective functions in problems (10) and (11), respectively:

$$\begin{aligned} \varPhi _1(u,D,\{\alpha _s\})= & {} \lambda \Vert f-Au\Vert _0 + \sum _{s\in \mathcal {B}} \mu _s \Vert \alpha _s\Vert _0 + \sum _{s\in \mathcal {B}} \Vert D\alpha _s - R_s u\Vert _2^2+ \eta \Vert \nabla u\Vert _1,\\ \varPhi _2(u,v,D,\{\alpha _s\})= & {} \lambda \langle \mathbf {1}, \mathbf {1}-v \rangle + \sum _{s\in \mathcal {B}} \mu _s \Vert \alpha _s\Vert _0 + \sum _{s\in \mathcal {B}} \Vert D\alpha _s - R_s u\Vert _2^2 + \eta \Vert \nabla u\Vert _1. \end{aligned}$$

Assuming that \((u^*,D^*, \{\alpha _s^{*}\})\) is a global solution of problem (10), suppose that \((u^*, \mathbf {1}-sign(|Au^*-f|), D^*, \{\alpha _s^*\})\) is not a global solution of problem (11). Then, there exists \((u_1^*,v_1^*,D_1^*, \{\alpha _s^{1,*}\})\) satisfying that

$$\begin{aligned}&\varPhi _2(u_1^*,v_1^*,D_1^*, \{\alpha _s^{1,*}\}) < \varPhi _2(u^*, \mathbf {1}-sign(|Au^*-f|), D^*, \{\alpha _s^*\}),\\&v_1^* \odot |f-Au_1^*|=\mathbf { 0} \quad \text {and} \quad \mathbf {0}\le v_1^* \le \mathbf {1}. \nonumber \end{aligned}$$
(16)

Let \(v_2^* = \mathbf {1}-sign(|f-Au_1^*|)\). Then we have

$$\begin{aligned} \varPhi _1(u_1^*,D_1^*,\{\alpha _s^{1,*}\})= & {} \varPhi _2(u_1^*,v_2^*,D_1^*, \{\alpha _s^{1,*}\}) \\\le & {} \varPhi _2(u_1^*,v_1^*,D_1^*, \{\alpha _s^{1,*}\}) \\< & {} \varPhi _2(u^*,\mathbf {1}-sign(|Au^*-f|),D^*, \{\alpha _s^{*}\}) \\= & {} \varPhi _1(u^*,D^*, \{\alpha _s^{*}\}), \end{aligned}$$

where the first and last equalities are due to the definition of \(\varPhi _i\) (\(i=1,2\)) and \(l_0\) norm, and the second and third inequalities are obtained from Lemma 2 (given below this proof) and (16), respectively. This contradicts to the assumption that \((u^*,D^*, \{\alpha _s^{*}\})\) is a global solution of (10).

Conversely, assuming that \((u^*,v^*,D^*, \{\alpha _s^{*}\})\) is a global solution of problem (11), suppose that \((u^*,D^*, \{\alpha _s^{*}\})\) is not a global solution of problem (10). Then, we can have a tuple \((u_1^*,D_1^*,\{\alpha _s^{1,*}\})\) such that

$$\begin{aligned} \varPhi _1(u_1^*,D_1^*, \{\alpha _s^{1,*}\}) < \varPhi _1(u^*, D^*, \{\alpha _s^*\}). \end{aligned}$$
(17)

With setting \(v_1^* = \mathbf {1}-sign(|f-Au_1^*|)\) and \(v_2^* = \mathbf {1}-sign(|f-Au^*|)\), we have that \(\Vert Au^*_1-f\Vert _0 = \langle \mathbf {1},\mathbf {1}-v_1^* \rangle \) and \(\Vert Au^*-f\Vert _0 = \langle \mathbf {1},\mathbf {1}-v_2^* \rangle \). These yield that

$$\begin{aligned} \varPhi _2(u^*_1,v^*_1, D^*_1, \{\alpha _s^{1,*}\})= & {} \varPhi _1(u_1^*, D_1^*, \{\alpha _s^{1,*}\})\\< & {} \varPhi _1(u^*, D^*, \{\alpha _s^*\})\\= & {} \varPhi _2(u^*, v_2^*,D^*, \{\alpha _s^*\})\\\le & {} \varPhi _2(u^*, v^*,D^*, \{\alpha _s^*\}), \end{aligned}$$

where the second and last inequalities are obtained from (17) and Lemma 2, respectively. This is also a contradiction to the assumption that \((u^*,v^*,D^*, \{\alpha _s^{*}\})\) is a global solution of (11). \(\square \)

Lemma 2

For fixed u, assume that \(v_1\) satisfies the constraints:

$$\begin{aligned} v \odot |f-Au|=\mathbf { 0} \quad \text {and} \quad \mathbf {0}\le v \le \mathbf {1}, \end{aligned}$$
(18)

and let \(v_2 = \mathbf {1}-sign(|Au-f|)\). Then, it holds that

$$\begin{aligned} \Vert Au-f\Vert _0 = \langle \mathbf {1}, \mathbf {1}-v_2\rangle \le \langle \mathbf {1}, \mathbf {1}- v_1\rangle . \end{aligned}$$

Proof of Lemma 2

By the definition of \(v_2\), it trivially holds that \(\Vert Au-f\Vert _0 = \langle \mathbf {1}, \mathbf {1}- v_2\rangle \). For any v satisfying (18), \(v_s = 0\) with \(s\in \varTheta =\{ s\,:\, |(Au-f)_s| \ne 0\}\). Clearly, \(v_2\) satisfies (18), so \((v_1)_s=(v_2)_s =0 \) for all \(s\in \varTheta \). Thus we obtain

$$\begin{aligned} \langle \mathbf {1}, \mathbf {1}-v_2\rangle = |\varTheta | \le |\varTheta | + \sum _{s\in {\varTheta }^{c}} (1-(v_1)_s) = \langle \mathbf {1}, \mathbf {1}- v_1\rangle . \end{aligned}$$

This completes the proof of the Lemma 2. \(\square \)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kang, M., Kang, M. & Jung, M. Sparse representation based image deblurring model under random-valued impulse noise. Multidim Syst Sign Process 30, 1063–1092 (2019). https://doi.org/10.1007/s11045-018-0587-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11045-018-0587-z

Keywords

Search

Navigation