• Previous Article
    Solving inverse source problems by the Orthogonal Solution and Kernel Correction Algorithm (OSKCA) with applications in fluorescence tomography
  • IPI Home
  • This Issue
  • Next Article
    The "exterior approach" to solve the inverse obstacle problem for the Stokes system
February  2014, 8(1): 53-77. doi: 10.3934/ipi.2014.8.53

The Moreau envelope approach for the L1/TV image denoising model

1. 

Department of Mathematics, Syracuse University, Syracuse, NY 13244, United States, United States

2. 

Department of Mathematics, Syracuse University, Syracuse, NY 13244-1150

3. 

School of Mathematical Sciences, Ocean University of China, Qingdao 266100, China

Received  October 2012 Revised  August 2013 Published  March 2014

This paper presents the Moreau envelope viewpoint for the L1/TV image denoising model. The main algorithmic difficulty for the numerical treatment of the L1/TV model lies in the non-differentiability of both the fidelity and regularization terms of the model. To overcome this difficulty, we propose five modified L1/TV models by replacing one or two non-differentiable functions in the L1/TV model with their corresponding Moreau envelopes. We prove that several existing approaches for the L1/TV model essentially solve some of the modified models, but not the original L1/TV model. Algorithms for the L1/TV model and its five variants are proposed under a unified framework based on fixed-point equations (via the proximity operator) which characterize the solutions of the models. Depending upon whether we smooth the regularization term or not, two different types of proximity algorithms are presented. The convergence rates of both types of the algorithms are improved significantly by exploring either the strategy of the Gauss-Seidel iteration, or the FISTA, or both. We compare the performance of various modified L1/TV models for the problem of impulse noise removal, and make recommendations based on our numerical experiments for using these models in applications.
Citation: Feishe Chen, Lixin Shen, Yuesheng Xu, Xueying Zeng. The Moreau envelope approach for the L1/TV image denoising model. Inverse Problems & Imaging, 2014, 8 (1) : 53-77. doi: 10.3934/ipi.2014.8.53
References:
[1]

J. E. Aujol, G. Gilboa, T. Chan and S. Osher, Structure-texture image decomposition-modeling, algorithms, and parameter selection,, International Journal of Computer Vision, 67 (2006), 111.  doi: 10.1007/s11263-006-4331-z.  Google Scholar

[2]

H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Space,, Springer Press, (2011).  doi: 10.1007/978-1-4419-9467-7.  Google Scholar

[3]

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems,, SIAM Journal on Imaging Science, 2 (2009), 183.  doi: 10.1137/080716542.  Google Scholar

[4]

P. Bloomfield and W. Steiger, Least Absolute Deviations: Theory, Applications, and Algorithms,, Birkhäuser Boston, (1983).   Google Scholar

[5]

A. Bovik, Handbook of Image and Video Processing,, Academic Press, (2000).   Google Scholar

[6]

A. Chambolle, An algorithm for total variation minimization and applications,, Special issue on mathematics and image analysis, 20 (2004), 89.  doi: 10.1023/B:JMIV.0000011321.19549.88.  Google Scholar

[7]

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging,, Journal of Mathematical Imaging and Vision, 40 (2011), 120.  doi: 10.1007/s10851-010-0251-1.  Google Scholar

[8]

T. Chan and S. Esedoglu, Aspects of total variation regularized l1 function approximation,, SIAM Journal on Applied Mathematics, 65 (2005), 1817.  doi: 10.1137/040604297.  Google Scholar

[9]

R. Chartrand and V. Staneva, Total variation regularization of images corrupted by non-gaussian noise using a quasi-newton method,, IET Image Processing, 2 (2008), 295.  doi: 10.1049/iet-ipr:20080017.  Google Scholar

[10]

T. Chen, W. Yin, X. Zhou, D. Comaniciu and T. Huang, Total variation models for variable lighting face recognition,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 28 (2006), 1519.  doi: 10.1109/TPAMI.2006.195.  Google Scholar

[11]

C. Clason, B. Jin and K. Kunisch, A duality-based splitting method for l1-tv image restoration with automatic regularization parameter choice,, SIAM Journal on Scientific Computing, 32 (2010), 1484.  doi: 10.1137/090768217.  Google Scholar

[12]

P. Combettes and V. Wajs, Signal recovery by proximal forward-backward splitting,, Multiscale Model and Simulation, 4 (2005), 1168.  doi: 10.1137/050626090.  Google Scholar

[13]

Y. Dong, M. Hintermuller and M. Neri, An Efficient Primal-Dual Method for $l^1$-TV image Restoration,, SIAM Journal on Imaging Sciences, 2 (2009), 1168.  doi: 10.1137/090758490.  Google Scholar

[14]

T. Goldstein and S. Osher, The split bregman method for l1-regularized problems,, SIAM Journal on Imaging Science, 2 (2009), 323.  doi: 10.1137/080725891.  Google Scholar

[15]

Y. Gousseau and J.-M. Morel, Are natural images of bounded variation?,, SIAM Journal on Mathematical Analysis, 33 (2001), 634.  doi: 10.1137/S0036141000371150.  Google Scholar

[16]

X. Guo, F. Li and M. Ng, A fast $l^1$-TV algorithm for image restoration,, SIAM Journal of Scientific Computing, 31 (2009), 2322.  doi: 10.1137/080724435.  Google Scholar

[17]

B. He and X. Yuan, Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective,, SIAM Journal on Imaging Sciences, 5 (2012), 119.  doi: 10.1137/100814494.  Google Scholar

[18]

Q. Li, C. Micchelli, L. Shen and Y. Xu, A proximity algorithm accelerated by Gauss-Seidel iterations for L1/TV denoising models,, Inverse Problems, 28 (2012).  doi: 10.1088/0266-5611/28/9/095003.  Google Scholar

[19]

C. A. Micchelli, L. Shen and Y. Xu, Proximity algorithms for image models: Denosing,, Inverse Problems, 27 (2011).  doi: 10.1088/0266-5611/27/4/045009.  Google Scholar

[20]

C. A. Micchelli, L. Shen, Y. Xu and X. Zeng, Proximity algorithms for the $l_1$$/$$tv$ image denosing models,, Advances in Computational Mathematics, 38 (2013), 401.  doi: 10.1007/s10444-011-9243-y.  Google Scholar

[21]

J.-J. Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien,, C. R. Acad. Sci. Paris Sér. A Math., 255 (1962), 1897.   Google Scholar

[22]

M. Nikolova, A variational approach to remove outliers and impulse noise,, Journal of Mathematical Imaging and Vision, 20 (2004), 99.  doi: 10.1023/B:JMIV.0000011920.58935.9c.  Google Scholar

[23]

R. Rockafellar, Augmented lagrangians and applications of the proximal point algorithm in convex programming,, Mathematics of Operations Research, 8 (1976), 421.  doi: 10.1287/moor.1.2.97.  Google Scholar

[24]

R. T. Rockafellar and R. Wets, Variational Analysis,, Springer, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[25]

C. Wu, J. Zhang and X. Tai, Augmented lagrangian method for total variation restoration with non-quadratic fidelity,, Inverse Problems and Imaging, 5 (2011), 237.  doi: 10.3934/ipi.2011.5.237.  Google Scholar

[26]

J. Yang, Y. Zhang and W. Yin, An efficient TVL1 algorithm for deblurring multichannel images corrupted by impulsive noise,, SIAM Journal on Scientific Computing, 31 (2009), 2842.  doi: 10.1137/080732894.  Google Scholar

[27]

W. Yin, T. Chen, S. Zhou and A. Chakraborty, Background correction for cdna microarray images using the tv+l1 model,, Bioinformatics, 21 (2005), 2410.  doi: 10.1093/bioinformatics/bti341.  Google Scholar

[28]

W. Yin, D. Goldfard and S. Osher, The total variation l1 model for multiscale decomposition,, Multiscale Modelling and Simulation, 6 (2007), 190.  doi: 10.1137/060663027.  Google Scholar

[29]

C. Zach, T. Pock and H. Bischof, A duality based approach for realtime tv-l1 optical flow,, Pattern Recognition, 4713 (2007), 214.   Google Scholar

show all references

References:
[1]

J. E. Aujol, G. Gilboa, T. Chan and S. Osher, Structure-texture image decomposition-modeling, algorithms, and parameter selection,, International Journal of Computer Vision, 67 (2006), 111.  doi: 10.1007/s11263-006-4331-z.  Google Scholar

[2]

H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Space,, Springer Press, (2011).  doi: 10.1007/978-1-4419-9467-7.  Google Scholar

[3]

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems,, SIAM Journal on Imaging Science, 2 (2009), 183.  doi: 10.1137/080716542.  Google Scholar

[4]

P. Bloomfield and W. Steiger, Least Absolute Deviations: Theory, Applications, and Algorithms,, Birkhäuser Boston, (1983).   Google Scholar

[5]

A. Bovik, Handbook of Image and Video Processing,, Academic Press, (2000).   Google Scholar

[6]

A. Chambolle, An algorithm for total variation minimization and applications,, Special issue on mathematics and image analysis, 20 (2004), 89.  doi: 10.1023/B:JMIV.0000011321.19549.88.  Google Scholar

[7]

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging,, Journal of Mathematical Imaging and Vision, 40 (2011), 120.  doi: 10.1007/s10851-010-0251-1.  Google Scholar

[8]

T. Chan and S. Esedoglu, Aspects of total variation regularized l1 function approximation,, SIAM Journal on Applied Mathematics, 65 (2005), 1817.  doi: 10.1137/040604297.  Google Scholar

[9]

R. Chartrand and V. Staneva, Total variation regularization of images corrupted by non-gaussian noise using a quasi-newton method,, IET Image Processing, 2 (2008), 295.  doi: 10.1049/iet-ipr:20080017.  Google Scholar

[10]

T. Chen, W. Yin, X. Zhou, D. Comaniciu and T. Huang, Total variation models for variable lighting face recognition,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 28 (2006), 1519.  doi: 10.1109/TPAMI.2006.195.  Google Scholar

[11]

C. Clason, B. Jin and K. Kunisch, A duality-based splitting method for l1-tv image restoration with automatic regularization parameter choice,, SIAM Journal on Scientific Computing, 32 (2010), 1484.  doi: 10.1137/090768217.  Google Scholar

[12]

P. Combettes and V. Wajs, Signal recovery by proximal forward-backward splitting,, Multiscale Model and Simulation, 4 (2005), 1168.  doi: 10.1137/050626090.  Google Scholar

[13]

Y. Dong, M. Hintermuller and M. Neri, An Efficient Primal-Dual Method for $l^1$-TV image Restoration,, SIAM Journal on Imaging Sciences, 2 (2009), 1168.  doi: 10.1137/090758490.  Google Scholar

[14]

T. Goldstein and S. Osher, The split bregman method for l1-regularized problems,, SIAM Journal on Imaging Science, 2 (2009), 323.  doi: 10.1137/080725891.  Google Scholar

[15]

Y. Gousseau and J.-M. Morel, Are natural images of bounded variation?,, SIAM Journal on Mathematical Analysis, 33 (2001), 634.  doi: 10.1137/S0036141000371150.  Google Scholar

[16]

X. Guo, F. Li and M. Ng, A fast $l^1$-TV algorithm for image restoration,, SIAM Journal of Scientific Computing, 31 (2009), 2322.  doi: 10.1137/080724435.  Google Scholar

[17]

B. He and X. Yuan, Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective,, SIAM Journal on Imaging Sciences, 5 (2012), 119.  doi: 10.1137/100814494.  Google Scholar

[18]

Q. Li, C. Micchelli, L. Shen and Y. Xu, A proximity algorithm accelerated by Gauss-Seidel iterations for L1/TV denoising models,, Inverse Problems, 28 (2012).  doi: 10.1088/0266-5611/28/9/095003.  Google Scholar

[19]

C. A. Micchelli, L. Shen and Y. Xu, Proximity algorithms for image models: Denosing,, Inverse Problems, 27 (2011).  doi: 10.1088/0266-5611/27/4/045009.  Google Scholar

[20]

C. A. Micchelli, L. Shen, Y. Xu and X. Zeng, Proximity algorithms for the $l_1$$/$$tv$ image denosing models,, Advances in Computational Mathematics, 38 (2013), 401.  doi: 10.1007/s10444-011-9243-y.  Google Scholar

[21]

J.-J. Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien,, C. R. Acad. Sci. Paris Sér. A Math., 255 (1962), 1897.   Google Scholar

[22]

M. Nikolova, A variational approach to remove outliers and impulse noise,, Journal of Mathematical Imaging and Vision, 20 (2004), 99.  doi: 10.1023/B:JMIV.0000011920.58935.9c.  Google Scholar

[23]

R. Rockafellar, Augmented lagrangians and applications of the proximal point algorithm in convex programming,, Mathematics of Operations Research, 8 (1976), 421.  doi: 10.1287/moor.1.2.97.  Google Scholar

[24]

R. T. Rockafellar and R. Wets, Variational Analysis,, Springer, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[25]

C. Wu, J. Zhang and X. Tai, Augmented lagrangian method for total variation restoration with non-quadratic fidelity,, Inverse Problems and Imaging, 5 (2011), 237.  doi: 10.3934/ipi.2011.5.237.  Google Scholar

[26]

J. Yang, Y. Zhang and W. Yin, An efficient TVL1 algorithm for deblurring multichannel images corrupted by impulsive noise,, SIAM Journal on Scientific Computing, 31 (2009), 2842.  doi: 10.1137/080732894.  Google Scholar

[27]

W. Yin, T. Chen, S. Zhou and A. Chakraborty, Background correction for cdna microarray images using the tv+l1 model,, Bioinformatics, 21 (2005), 2410.  doi: 10.1093/bioinformatics/bti341.  Google Scholar

[28]

W. Yin, D. Goldfard and S. Osher, The total variation l1 model for multiscale decomposition,, Multiscale Modelling and Simulation, 6 (2007), 190.  doi: 10.1137/060663027.  Google Scholar

[29]

C. Zach, T. Pock and H. Bischof, A duality based approach for realtime tv-l1 optical flow,, Pattern Recognition, 4713 (2007), 214.   Google Scholar

[1]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463

[2]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321

[3]

Justin Holmer, Chang Liu. Blow-up for the 1D nonlinear Schrödinger equation with point nonlinearity II: Supercritical blow-up profiles. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020264

[4]

Zedong Yang, Guotao Wang, Ravi P. Agarwal, Haiyong Xu. Existence and nonexistence of entire positive radial solutions for a class of Schrödinger elliptic systems involving a nonlinear operator. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020436

[5]

Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363

[6]

Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117

[7]

Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071

[8]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[9]

Hoang The Tuan. On the asymptotic behavior of solutions to time-fractional elliptic equations driven by a multiplicative white noise. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020318

[10]

Serge Dumont, Olivier Goubet, Youcef Mammeri. Decay of solutions to one dimensional nonlinear Schrödinger equations with white noise dispersion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020456

[11]

Pengyu Chen. Non-autonomous stochastic evolution equations with nonlinear noise and nonlocal conditions governed by noncompact evolution families. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020383

[12]

Lin Shi, Xuemin Wang, Dingshi Li. Limiting behavior of non-autonomous stochastic reaction-diffusion equations with colored noise on unbounded thin domains. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5367-5386. doi: 10.3934/cpaa.2020242

[13]

Laurence Cherfils, Stefania Gatti, Alain Miranville, Rémy Guillevin. Analysis of a model for tumor growth and lactate exchanges in a glioma. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020457

[14]

Laurent Di Menza, Virginie Joanne-Fabre. An age group model for the study of a population of trees. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020464

[15]

Weiwei Liu, Jinliang Wang, Yuming Chen. Threshold dynamics of a delayed nonlocal reaction-diffusion cholera model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020316

[16]

Siyang Cai, Yongmei Cai, Xuerong Mao. A stochastic differential equation SIS epidemic model with regime switching. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020317

[17]

Yining Cao, Chuck Jia, Roger Temam, Joseph Tribbia. Mathematical analysis of a cloud resolving model including the ice microphysics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 131-167. doi: 10.3934/dcds.2020219

[18]

Zhouchao Wei, Wei Zhang, Irene Moroz, Nikolay V. Kuznetsov. Codimension one and two bifurcations in Cattaneo-Christov heat flux model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020344

[19]

Shuang Chen, Jinqiao Duan, Ji Li. Effective reduction of a three-dimensional circadian oscillator model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020349

[20]

Barbora Benešová, Miroslav Frost, Lukáš Kadeřávek, Tomáš Roubíček, Petr Sedlák. An experimentally-fitted thermodynamical constitutive model for polycrystalline shape memory alloys. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020459

2019 Impact Factor: 1.373

Metrics

  • PDF downloads (47)
  • HTML views (0)
  • Cited by (13)

Other articles
by authors

[Back to Top]