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

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

Feishe Chen ^1, , Lixin Shen ^1, , Yuesheng Xu ^2, and Xueying Zeng ^3,

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

Abstract
Related Papers

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.

Keywords: Moreau envelope, proximity operator., Impulse noise, L1/TV denoising model.

Mathematics Subject Classification: Primary: 94A08; Secondary: 49N45, 68U1.

Citation: Feishe Chen, Lixin Shen, Yuesheng Xu, Xueying Zeng. The Moreau envelope approach for the L1/TV image denoising model. Inverse Problems and 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-136. doi: 10.1007/s11263-006-4331-z.
[2]	H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Space, Springer Press, New York, 2011. doi: 10.1007/978-1-4419-9467-7.
[3]	A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Science, 2 (2009), 183-202. doi: 10.1137/080716542.
[4]	P. Bloomfield and W. Steiger, Least Absolute Deviations: Theory, Applications, and Algorithms, Birkhäuser Boston, Boston, 1983.
[5]	A. Bovik, Handbook of Image and Video Processing, Academic Press, San Diego, 2000.
[6]	A. Chambolle, An algorithm for total variation minimization and applications, Special issue on mathematics and image analysis, Journal of Mathematical Imaging and Vision, 20 (2004), 89-97. doi: 10.1023/B:JMIV.0000011321.19549.88.
[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-145. doi: 10.1007/s10851-010-0251-1.
[8]	T. Chan and S. Esedoglu, Aspects of total variation regularized l1 function approximation, SIAM Journal on Applied Mathematics, 65 (2005), 1817-1837. doi: 10.1137/040604297.
[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-303. doi: 10.1049/iet-ipr:20080017.
[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-1524. doi: 10.1109/TPAMI.2006.195.
[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-1505. doi: 10.1137/090768217.
[12]	P. Combettes and V. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model and Simulation, 4 (2005), 1168-1200. doi: 10.1137/050626090.
[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-1189. doi: 10.1137/090758490.
[14]	T. Goldstein and S. Osher, The split bregman method for l1-regularized problems, SIAM Journal on Imaging Science, 2 (2009), 323-343. doi: 10.1137/080725891.
[15]	Y. Gousseau and J.-M. Morel, Are natural images of bounded variation?, SIAM Journal on Mathematical Analysis, 33 (2001), 634-648. doi: 10.1137/S0036141000371150.
[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-2341. doi: 10.1137/080724435.
[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-149. doi: 10.1137/100814494.
[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), 20 pp. doi: 10.1088/0266-5611/28/9/095003.
[19]	C. A. Micchelli, L. Shen and Y. Xu, Proximity algorithms for image models: Denosing, Inverse Problems, 27 (2011), 30pp. doi: 10.1088/0266-5611/27/4/045009.
[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-426. doi: 10.1007/s10444-011-9243-y.
[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-2899.
[22]	M. Nikolova, A variational approach to remove outliers and impulse noise, Journal of Mathematical Imaging and Vision, 20 (2004), 99-120. doi: 10.1023/B:JMIV.0000011920.58935.9c.
[23]	R. Rockafellar, Augmented lagrangians and applications of the proximal point algorithm in convex programming, Mathematics of Operations Research, 8 (1976), 421-439. doi: 10.1287/moor.1.2.97.
[24]	R. T. Rockafellar and R. Wets, Variational Analysis, Springer, 1998. doi: 10.1007/978-3-642-02431-3.
[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-261. doi: 10.3934/ipi.2011.5.237.
[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-2865. doi: 10.1137/080732894.
[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-2416. doi: 10.1093/bioinformatics/bti341.
[28]	W. Yin, D. Goldfard and S. Osher, The total variation l1 model for multiscale decomposition, Multiscale Modelling and Simulation, 6 (2007), 190-211. doi: 10.1137/060663027.
[29]	C. Zach, T. Pock and H. Bischof, A duality based approach for realtime tv-l1 optical flow, Pattern Recognition, 4713 (2007), 214-223.

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-136. doi: 10.1007/s11263-006-4331-z.
[2]	H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Space, Springer Press, New York, 2011. doi: 10.1007/978-1-4419-9467-7.
[3]	A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Science, 2 (2009), 183-202. doi: 10.1137/080716542.
[4]	P. Bloomfield and W. Steiger, Least Absolute Deviations: Theory, Applications, and Algorithms, Birkhäuser Boston, Boston, 1983.
[5]	A. Bovik, Handbook of Image and Video Processing, Academic Press, San Diego, 2000.
[6]	A. Chambolle, An algorithm for total variation minimization and applications, Special issue on mathematics and image analysis, Journal of Mathematical Imaging and Vision, 20 (2004), 89-97. doi: 10.1023/B:JMIV.0000011321.19549.88.
[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-145. doi: 10.1007/s10851-010-0251-1.
[8]	T. Chan and S. Esedoglu, Aspects of total variation regularized l1 function approximation, SIAM Journal on Applied Mathematics, 65 (2005), 1817-1837. doi: 10.1137/040604297.
[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-303. doi: 10.1049/iet-ipr:20080017.
[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-1524. doi: 10.1109/TPAMI.2006.195.
[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-1505. doi: 10.1137/090768217.
[12]	P. Combettes and V. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model and Simulation, 4 (2005), 1168-1200. doi: 10.1137/050626090.
[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-1189. doi: 10.1137/090758490.
[14]	T. Goldstein and S. Osher, The split bregman method for l1-regularized problems, SIAM Journal on Imaging Science, 2 (2009), 323-343. doi: 10.1137/080725891.
[15]	Y. Gousseau and J.-M. Morel, Are natural images of bounded variation?, SIAM Journal on Mathematical Analysis, 33 (2001), 634-648. doi: 10.1137/S0036141000371150.
[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-2341. doi: 10.1137/080724435.
[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-149. doi: 10.1137/100814494.
[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), 20 pp. doi: 10.1088/0266-5611/28/9/095003.
[19]	C. A. Micchelli, L. Shen and Y. Xu, Proximity algorithms for image models: Denosing, Inverse Problems, 27 (2011), 30pp. doi: 10.1088/0266-5611/27/4/045009.
[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-426. doi: 10.1007/s10444-011-9243-y.
[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-2899.
[22]	M. Nikolova, A variational approach to remove outliers and impulse noise, Journal of Mathematical Imaging and Vision, 20 (2004), 99-120. doi: 10.1023/B:JMIV.0000011920.58935.9c.
[23]	R. Rockafellar, Augmented lagrangians and applications of the proximal point algorithm in convex programming, Mathematics of Operations Research, 8 (1976), 421-439. doi: 10.1287/moor.1.2.97.
[24]	R. T. Rockafellar and R. Wets, Variational Analysis, Springer, 1998. doi: 10.1007/978-3-642-02431-3.
[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-261. doi: 10.3934/ipi.2011.5.237.
[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-2865. doi: 10.1137/080732894.
[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-2416. doi: 10.1093/bioinformatics/bti341.
[28]	W. Yin, D. Goldfard and S. Osher, The total variation l1 model for multiscale decomposition, Multiscale Modelling and Simulation, 6 (2007), 190-211. doi: 10.1137/060663027.
[29]	C. Zach, T. Pock and H. Bischof, A duality based approach for realtime tv-l1 optical flow, Pattern Recognition, 4713 (2007), 214-223.

[1]	Yoon Mo Jung, Taeuk Jeong, Sangwoon Yun. Non-convex TV denoising corrupted by impulse noise. Inverse Problems and Imaging, 2017, 11 (4) : 689-702. doi: 10.3934/ipi.2017032
[2]	Lekbir Afraites, Aissam Hadri, Amine Laghrib, Mourad Nachaoui. A non-convex denoising model for impulse and Gaussian noise mixture removing using bi-level parameter identification. Inverse Problems and Imaging, , () : -. doi: 10.3934/ipi.2022001
[3]	Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1835-1861. doi: 10.3934/jimo.2021046
[4]	Michael Hintermüller, Monserrat Rincon-Camacho. An adaptive finite element method in $L^2$-TV-based image denoising. Inverse Problems and Imaging, 2014, 8 (3) : 685-711. doi: 10.3934/ipi.2014.8.685
[5]	Linghua Chen, Espen R. Jakobsen. L¹ semigroup generation for Fokker-Planck operators associated to general Lévy driven SDEs. Discrete and Continuous Dynamical Systems, 2018, 38 (11) : 5735-5763. doi: 10.3934/dcds.2018250
[6]	Duo Wang, Zheng-Fen Jin, Youlin Shang. A penalty decomposition method for nuclear norm minimization with l₁ norm fidelity term. Evolution Equations and Control Theory, 2019, 8 (4) : 695-708. doi: 10.3934/eect.2019034
[7]	Yingying Li, Stanley Osher. Coordinate descent optimization for l¹ minimization with application to compressed sensing; a greedy algorithm. Inverse Problems and Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487
[8]	Nils Dabrock, Yves van Gennip. A note on "Anisotropic total variation regularized $L^1$-approximation and denoising/deblurring of 2D bar codes". Inverse Problems and Imaging, 2018, 12 (2) : 525-526. doi: 10.3934/ipi.2018022
[9]	Rustum Choksi, Yves van Gennip, Adam Oberman. Anisotropic total variation regularized $L^1$ approximation and denoising/deblurring of 2D bar codes. Inverse Problems and Imaging, 2011, 5 (3) : 591-617. doi: 10.3934/ipi.2011.5.591
[10]	Badr-eddine Berrhazi, Mohamed El Fatini, Tomás Caraballo, Roger Pettersson. A stochastic SIRI epidemic model with Lévy noise. Discrete and Continuous Dynamical Systems - B, 2018, 23 (6) : 2415-2431. doi: 10.3934/dcdsb.2018057
[11]	Dmitrii Rachinskii. On geometric conditions for reduction of the Moreau sweeping process to the Prandtl-Ishlinskii operator. Discrete and Continuous Dynamical Systems - B, 2018, 23 (8) : 3361-3386. doi: 10.3934/dcdsb.2018246
[12]	C.M. Elliott, S. A. Smitheman. Analysis of the TV regularization and $H^{-1}$ fidelity model for decomposing animage into cartoon plus texture. Communications on Pure and Applied Analysis, 2007, 6 (4) : 917-936. doi: 10.3934/cpaa.2007.6.917
[13]	Juan Carlos De los Reyes, Carola-Bibiane Schönlieb. Image denoising: Learning the noise model via nonsmooth PDE-constrained optimization. Inverse Problems and Imaging, 2013, 7 (4) : 1183-1214. doi: 10.3934/ipi.2013.7.1183
[14]	Xiangjun Wang, Jianghui Wen, Jianping Li, Jinqiao Duan. Impact of $\alpha$-stable Lévy noise on the Stommel model for the thermohaline circulation. Discrete and Continuous Dynamical Systems - B, 2012, 17 (5) : 1575-1584. doi: 10.3934/dcdsb.2012.17.1575
[15]	Qiyu Jin, Li Bai, Ion Grama, Quansheng Liu, Jie Yang. Removing random-valued impulse noise with reliable weight. Inverse Problems and Imaging, 2020, 14 (2) : 171-203. doi: 10.3934/ipi.2020009
[16]	Hao Yang, Hang Qiu, Leiting Chen. An optimized direction statistics for detecting and removing random-valued impulse noise. Journal of Industrial and Management Optimization, 2018, 14 (2) : 597-611. doi: 10.3934/jimo.2017062
[17]	Jianbin Yang, Cong Wang. A wavelet frame approach for removal of mixed Gaussian and impulse noise on surfaces. Inverse Problems and Imaging, 2017, 11 (5) : 783-798. doi: 10.3934/ipi.2017037
[18]	Wenye Ma, Stanley Osher. A TV Bregman iterative model of Retinex theory. Inverse Problems and Imaging, 2012, 6 (4) : 697-708. doi: 10.3934/ipi.2012.6.697
[19]	Peter I. Kogut, Olha P. Kupenko. On optimal control problem for an ill-posed strongly nonlinear elliptic equation with $p$-Laplace operator and $L^1$-type of nonlinearity. Discrete and Continuous Dynamical Systems - B, 2019, 24 (3) : 1273-1295. doi: 10.3934/dcdsb.2019016
[20]	Martin Redmann, Melina A. Freitag. Balanced model order reduction for linear random dynamical systems driven by Lévy noise. Journal of Computational Dynamics, 2018, 5 (1&2) : 33-59. doi: 10.3934/jcd.2018002

2020 Impact Factor: 1.639

Tools

Metrics

Other articles
by authors

on AIMS
Feishe Chen Lixin Shen Yuesheng Xu Xueying Zeng
on Google Scholar
Feishe Chen Lixin Shen Yuesheng Xu Xueying Zeng

[Back to Top]