Augmented Lagrangian method for a mean curvature based image denoising model

Previous Article
IPI Home
This Issue
Next Article
Reconstruction of penetrable grating profiles

November 2013, 7(4): 1409-1432. doi: 10.3934/ipi.2013.7.1409

Augmented Lagrangian method for a mean curvature based image denoising model

Wei Zhu ^1, , Xue-Cheng Tai ^2, and Tony Chan ^3,

1.	Department of Mathematics, University of Alabama, Box 870350, Tuscaloosa, AL 35487
2.	Department of Mathematics, University of Bergen, Bergen 5007, Norway
3.	Office of the President, Hong Kong University of Science and Technology (HKUST), Clear Water Bay, Kowlon, Hong Kong, China

Received October 2011 Revised October 2012 Published November 2013

Abstract
Related Papers

High order derivative information has been widely used in developing variational models in image processing to accomplish more advanced tasks. However, it is a nontrivial issue to construct efficient numerical algorithms to deal with the minimization of these variational models due to the associated high order Euler-Lagrange equations. In this paper, we propose an efficient numerical method for a mean curvature based image denoising model using the augmented Lagrangian method. A special technique is introduced to handle the mean curvature model for the augmented Lagrangian scheme. We detail the procedures of finding the related saddle-points of the functional. We present numerical experiments to illustrate the effectiveness and efficiency of the proposed numerical method, and show a few important features of the image denoising model such as keeping corners and image contrast. Moreover, a comparison with the gradient descent method further demonstrates the efficiency of the proposed augmented Lagrangian method.

Keywords: mean curvature, Augmented lagrangian method, image denoising..

Mathematics Subject Classification: Primary: 68U10, 65K10; Secondary: 49M0.

Citation: Wei Zhu, Xue-Cheng Tai, Tony Chan. Augmented Lagrangian method for a mean curvature based image denoising model. Inverse Problems and Imaging, 2013, 7 (4) : 1409-1432. doi: 10.3934/ipi.2013.7.1409

References:

[1]	L. Ambrosio and S. Masnou, A direct variational approach to a problem arising in image reconstruction, Interfaces Free Bound., 5 (2003), 63-81. doi: 10.4171/IFB/72.
[2]	L. Ambrosio and S. Masnou, On a variational problem arising in image reconstruction, Free Boundary Problems (Trento, 2002), Internat. Ser. Numer. Math., 147, Birkhäuser, Basel, (2004), 17-26.
[3]	L. Alvarez, F. Guichard, P. L. Lions and J. M. Morel, Axioms and fundamental equations of image-processing, Archive for Rational Mechanics and Analysis, 123 (1993), 199-257. doi: 10.1007/BF00375127.
[4]	G. Aubert and L. Vese, A variational method in image recovery, SIAM J. Numer. Anal. 34 (1987), 1948-1979. doi: 10.1137/S003614299529230X.
[5]	A. L. Bertozzi and J. B. Greer, Low curvature image simplifiers: Global regularity of smooth solutions and Laplacian limiting schemes, Comm. Pure Appl. Math., 57 (2004), 764-790. doi: 10.1002/cpa.20019.
[6]	T. Chan and S. Esedoglu, Aspects of total variation regularized $L^1$ function approximation, SIAM J. Appl. Math., 65 (2005), 1817-1837. doi: 10.1137/040604297.
[7]	T. Chen, W. Yin, X. S. Zhou, D. Comaniciu and T. Huang, Total variation models for variable lighting face recognition, IEEE. Trans. Pattern Anal. Mach. Intell., 28 (2006), 1519-1524. doi: 10.1109/TPAMI.2006.195.
[8]	A. Chambolle and P. L. Lions, Image recovery via total variation minimization and related problems, Numer. Math., 76 (1997), 167-188. doi: 10.1007/s002110050258.
[9]	T. Chan, S. H. Kang and J. H. Shen, Euler's elastica and curvature-based inpainting, SIAM J. Appl. Math., 63 (2002), 564-592. doi: 10.1137/S0036139901390088.
[10]	T. Chan, A. Marquina and P. Mulet, High-order total variation-based image restoration, SIAM J. Sci. Comput., 22 (2000), 503-516. doi: 10.1137/S1064827598344169.
[11]	M. P. do Carmo, Differential geometry of curves and surfaces, Translated From the Portuguese. Prentice-Hall, Inc., Englewood Cliffs, N.J., 1976. viii+503 pp.
[12]	M. Elsey and S. Esedoglu, Analogue of the total variation denoising model in the context of geometry processing, SIAM J. Multiscale Modeling and Simulation, 7 (2009), 1549-1573. doi: 10.1137/080736612.
[13]	S. Esedo$\overlineg$lu and J. Shen, Digital inpainting based on the Mumford-Shah-Euler image model, European J. Appl. Math., 13 (2002), 353-370. doi: 10.1017/S0956792502004904.
[14]	T. Goldstein and S. Osher, The split bregman method for L1 regularized problems, SIAM J. on Imaging Sciences, 2 (2009), 323-343. doi: 10.1137/080725891.
[15]	J. B. Greer and A. L. Bertozzi, Traveling wave solutions of fourth order PDEs for image processing, SIAM J. Math. Anal., 36 (2004), 38-68. doi: 10.1137/S0036141003427373.
[16]	J. B. Greer, A. L. Bertozzi and G. Sapiro, Fourth order partial differential equations on general geometries, J. Comp. Phys., 216 (2006), 216-246. doi: 10.1016/j.jcp.2005.11.031.
[17]	R. Kimmel, R. Malladi and N. Sochen, Image processing via the Beltrami Operator, Proceedings of Asian Conference on Computer Vision, LNCS 1351 (1998), 574-581, Hong Kong. doi: 10.1007/3-540-63930-6_169.
[18]	R. Kimmel, R. Malladi, and N. Sochen, Images as embedded maps and minimal surfaces: Movies, color, texture and volumetric medical images, International Journal of Computer Vision, 39 (2000), 111-129.
[19]	P. L. Lions and B. Mercier, Splitting algorithms for the sume of two nonlinear opertors, SIAM J. Numer. Anal., 16 (1979), 964-979. doi: 10.1137/0716071.
[20]	M. Lysaker, A. Lundervold and X. C. Tai, Noise removal using fourth-order partial differential equation with applications to medical magnetic resonance images in space and time, IEEE. Trans. Image Process., 12 (2003), 1579-1590. doi: 10.1109/TIP.2003.819229.
[21]	M. Lysaker, S. Osher and X. C. Tai, Noise removal using smoothed normals and surface fitting, IEEE. Trans. Image Process., 13 (2004), 1345-1357. doi: 10.1109/TIP.2004.834662.
[22]	S. Masnou, Disocclusion: A variational approach using level lines, IEEE Trans. Image Process., 11 (2002), 68-76. doi: 10.1109/83.982815.
[23]	S. Masnou and J. M. Morel, Level lines based disocclusion, Proc. IEEE Int. Conf. on Image Processing, Chicago, IL, (1998), 259-263. doi: 10.1109/ICIP.1998.999016.
[24]	Y. Meyer, Oscillating patterns in image processing and nonlinear evolution equations, University Lecture Series, Amer. Math. Soc., 22 (2002).
[25]	D. Mumford and J. Shah, Optimal approximation by piecewise smooth functions and associated variational problems, Comm. Pure Appl. Math., 42 (1989), 577-685. doi: 10.1002/cpa.3160420503.
[26]	J. M. Morel and S. Solimini, Variational methods in image segmentation, Birkhauser, Boston, (1995). doi: 10.1007/978-1-4684-0567-5.
[27]	M. Nitzberg, D. Mumford and T. Shiota, Filtering, segmentation, and depth, Lecture Notes in Computer Science, 662 (1993), Springer Verlag, Berlin. doi: 10.1007/3-540-56484-5.
[28]	S. Osher, A. Sole and L. Vese, Image decomposition and restoration using total variation minimization and the $H^{-1}$ norm, SIAM Multiscale Model., (2003), 349-370. doi: 10.1137/S1540345902416247.
[29]	P. Perona and J. Malik, Scale-space and edge-detection using anisotropic diffusion, IEEE Trans. on Pattern Analysis and Machine Intelligence, 12 (1990), 629-639. doi: 10.1109/34.56205.
[30]	L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithm, Physica D, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F.
[31]	N. Sochen, R. Kimmel and R. Malladi, A geometrical framework for low level vision, IEEE Trans. on Image Process., 7 (1998), 310-318. doi: 10.1109/83.661181.
[32]	X. C. Tai, J. Hahn and G. J. Chung, A fast algorithm for Euler's Elastica model using augmented Lagrangian method, SIAM J. Imaging Sciences, 4 (2011), 313-344. doi: 10.1137/100803730.
[33]	T. Tasdizen, R. Whitaker, P. Burchard and S. Osher, Geometric surface processing via normal maps, ACM Transactions on Graphics, 22 (2003), 1012-1033. doi: 10.1145/944020.944024.
[34]	L. Vese and S. Osher, Modeling textures with total variation minimization and oscillatory patterns im image processing, SINUM., 40 (2003), 2085-2104. doi: 10.1137/S0036142901396715.
[35]	C. Wu and X. C. Tai, Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, Vectorial TV, and high order models, SIAM J. Imaging Sciences, 3 (2010), 300-339. doi: 10.1137/090767558.
[36]	W. Yin, T. Chen, X. S. Zhou and A. Chakraborty, Background correction for cDNA microarray image using the TV+L1 model, Bioinformatics, 21 (2005), 2410-2416. doi: 10.1093/bioinformatics/bti341.
[37]	W. Zhu and T. Chan, A variational model for capturing illusory contours using curvature, J. Math. Imaging Vision, 27 (2007), 29-40. doi: 10.1007/s10851-006-9695-8.
[38]	W. Zhu and T. Chan, Image denoising using mean curvature of image surface, SIAM J. Imaging Sciences, 5 (2012), 1-32. doi: 10.1137/110822268.
[39]	W. Zhu, T. Chan and S. Esedoglu, Segmentation with depth: A level set approach, SIAM J. Sci. Comput., 28 (2006), 1957-1973. doi: 10.1137/050622213.

show all references

References:

[1]	L. Ambrosio and S. Masnou, A direct variational approach to a problem arising in image reconstruction, Interfaces Free Bound., 5 (2003), 63-81. doi: 10.4171/IFB/72.
[2]	L. Ambrosio and S. Masnou, On a variational problem arising in image reconstruction, Free Boundary Problems (Trento, 2002), Internat. Ser. Numer. Math., 147, Birkhäuser, Basel, (2004), 17-26.
[3]	L. Alvarez, F. Guichard, P. L. Lions and J. M. Morel, Axioms and fundamental equations of image-processing, Archive for Rational Mechanics and Analysis, 123 (1993), 199-257. doi: 10.1007/BF00375127.
[4]	G. Aubert and L. Vese, A variational method in image recovery, SIAM J. Numer. Anal. 34 (1987), 1948-1979. doi: 10.1137/S003614299529230X.
[5]	A. L. Bertozzi and J. B. Greer, Low curvature image simplifiers: Global regularity of smooth solutions and Laplacian limiting schemes, Comm. Pure Appl. Math., 57 (2004), 764-790. doi: 10.1002/cpa.20019.
[6]	T. Chan and S. Esedoglu, Aspects of total variation regularized $L^1$ function approximation, SIAM J. Appl. Math., 65 (2005), 1817-1837. doi: 10.1137/040604297.
[7]	T. Chen, W. Yin, X. S. Zhou, D. Comaniciu and T. Huang, Total variation models for variable lighting face recognition, IEEE. Trans. Pattern Anal. Mach. Intell., 28 (2006), 1519-1524. doi: 10.1109/TPAMI.2006.195.
[8]	A. Chambolle and P. L. Lions, Image recovery via total variation minimization and related problems, Numer. Math., 76 (1997), 167-188. doi: 10.1007/s002110050258.
[9]	T. Chan, S. H. Kang and J. H. Shen, Euler's elastica and curvature-based inpainting, SIAM J. Appl. Math., 63 (2002), 564-592. doi: 10.1137/S0036139901390088.
[10]	T. Chan, A. Marquina and P. Mulet, High-order total variation-based image restoration, SIAM J. Sci. Comput., 22 (2000), 503-516. doi: 10.1137/S1064827598344169.
[11]	M. P. do Carmo, Differential geometry of curves and surfaces, Translated From the Portuguese. Prentice-Hall, Inc., Englewood Cliffs, N.J., 1976. viii+503 pp.
[12]	M. Elsey and S. Esedoglu, Analogue of the total variation denoising model in the context of geometry processing, SIAM J. Multiscale Modeling and Simulation, 7 (2009), 1549-1573. doi: 10.1137/080736612.
[13]	S. Esedo$\overlineg$lu and J. Shen, Digital inpainting based on the Mumford-Shah-Euler image model, European J. Appl. Math., 13 (2002), 353-370. doi: 10.1017/S0956792502004904.
[14]	T. Goldstein and S. Osher, The split bregman method for L1 regularized problems, SIAM J. on Imaging Sciences, 2 (2009), 323-343. doi: 10.1137/080725891.
[15]	J. B. Greer and A. L. Bertozzi, Traveling wave solutions of fourth order PDEs for image processing, SIAM J. Math. Anal., 36 (2004), 38-68. doi: 10.1137/S0036141003427373.
[16]	J. B. Greer, A. L. Bertozzi and G. Sapiro, Fourth order partial differential equations on general geometries, J. Comp. Phys., 216 (2006), 216-246. doi: 10.1016/j.jcp.2005.11.031.
[17]	R. Kimmel, R. Malladi and N. Sochen, Image processing via the Beltrami Operator, Proceedings of Asian Conference on Computer Vision, LNCS 1351 (1998), 574-581, Hong Kong. doi: 10.1007/3-540-63930-6_169.
[18]	R. Kimmel, R. Malladi, and N. Sochen, Images as embedded maps and minimal surfaces: Movies, color, texture and volumetric medical images, International Journal of Computer Vision, 39 (2000), 111-129.
[19]	P. L. Lions and B. Mercier, Splitting algorithms for the sume of two nonlinear opertors, SIAM J. Numer. Anal., 16 (1979), 964-979. doi: 10.1137/0716071.
[20]	M. Lysaker, A. Lundervold and X. C. Tai, Noise removal using fourth-order partial differential equation with applications to medical magnetic resonance images in space and time, IEEE. Trans. Image Process., 12 (2003), 1579-1590. doi: 10.1109/TIP.2003.819229.
[21]	M. Lysaker, S. Osher and X. C. Tai, Noise removal using smoothed normals and surface fitting, IEEE. Trans. Image Process., 13 (2004), 1345-1357. doi: 10.1109/TIP.2004.834662.
[22]	S. Masnou, Disocclusion: A variational approach using level lines, IEEE Trans. Image Process., 11 (2002), 68-76. doi: 10.1109/83.982815.
[23]	S. Masnou and J. M. Morel, Level lines based disocclusion, Proc. IEEE Int. Conf. on Image Processing, Chicago, IL, (1998), 259-263. doi: 10.1109/ICIP.1998.999016.
[24]	Y. Meyer, Oscillating patterns in image processing and nonlinear evolution equations, University Lecture Series, Amer. Math. Soc., 22 (2002).
[25]	D. Mumford and J. Shah, Optimal approximation by piecewise smooth functions and associated variational problems, Comm. Pure Appl. Math., 42 (1989), 577-685. doi: 10.1002/cpa.3160420503.
[26]	J. M. Morel and S. Solimini, Variational methods in image segmentation, Birkhauser, Boston, (1995). doi: 10.1007/978-1-4684-0567-5.
[27]	M. Nitzberg, D. Mumford and T. Shiota, Filtering, segmentation, and depth, Lecture Notes in Computer Science, 662 (1993), Springer Verlag, Berlin. doi: 10.1007/3-540-56484-5.
[28]	S. Osher, A. Sole and L. Vese, Image decomposition and restoration using total variation minimization and the $H^{-1}$ norm, SIAM Multiscale Model., (2003), 349-370. doi: 10.1137/S1540345902416247.
[29]	P. Perona and J. Malik, Scale-space and edge-detection using anisotropic diffusion, IEEE Trans. on Pattern Analysis and Machine Intelligence, 12 (1990), 629-639. doi: 10.1109/34.56205.
[30]	L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithm, Physica D, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F.
[31]	N. Sochen, R. Kimmel and R. Malladi, A geometrical framework for low level vision, IEEE Trans. on Image Process., 7 (1998), 310-318. doi: 10.1109/83.661181.
[32]	X. C. Tai, J. Hahn and G. J. Chung, A fast algorithm for Euler's Elastica model using augmented Lagrangian method, SIAM J. Imaging Sciences, 4 (2011), 313-344. doi: 10.1137/100803730.
[33]	T. Tasdizen, R. Whitaker, P. Burchard and S. Osher, Geometric surface processing via normal maps, ACM Transactions on Graphics, 22 (2003), 1012-1033. doi: 10.1145/944020.944024.
[34]	L. Vese and S. Osher, Modeling textures with total variation minimization and oscillatory patterns im image processing, SINUM., 40 (2003), 2085-2104. doi: 10.1137/S0036142901396715.
[35]	C. Wu and X. C. Tai, Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, Vectorial TV, and high order models, SIAM J. Imaging Sciences, 3 (2010), 300-339. doi: 10.1137/090767558.
[36]	W. Yin, T. Chen, X. S. Zhou and A. Chakraborty, Background correction for cDNA microarray image using the TV+L1 model, Bioinformatics, 21 (2005), 2410-2416. doi: 10.1093/bioinformatics/bti341.
[37]	W. Zhu and T. Chan, A variational model for capturing illusory contours using curvature, J. Math. Imaging Vision, 27 (2007), 29-40. doi: 10.1007/s10851-006-9695-8.
[38]	W. Zhu and T. Chan, Image denoising using mean curvature of image surface, SIAM J. Imaging Sciences, 5 (2012), 1-32. doi: 10.1137/110822268.
[39]	W. Zhu, T. Chan and S. Esedoglu, Segmentation with depth: A level set approach, SIAM J. Sci. Comput., 28 (2006), 1957-1973. doi: 10.1137/050622213.

[1]	Wei Zhu. A numerical study of a mean curvature denoising model using a novel augmented Lagrangian method. Inverse Problems and Imaging, 2017, 11 (6) : 975-996. doi: 10.3934/ipi.2017045
[2]	Li Jin, Hongying Huang. Differential equation method based on approximate augmented Lagrangian for nonlinear programming. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2267-2281. doi: 10.3934/jimo.2019053
[3]	Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial and Management Optimization, 2020, 16 (1) : 1-9. doi: 10.3934/jimo.2018136
[4]	Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems and Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237
[5]	Lei Guo, Gao-Xi Li, Xinmin Yang. Global convergence of augmented Lagrangian method applied to mathematical program with switching constraints. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022114
[6]	Hongpeng Sun. An efficient augmented Lagrangian method with semismooth Newton solver for total generalized variation. Inverse Problems and Imaging, , () : -. doi: 10.3934/ipi.2022047
[7]	Fatemeh Bazikar, Saeed Ketabchi, Hossein Moosaei. Smooth augmented Lagrangian method for twin bounded support vector machine. Numerical Algebra, Control and Optimization, 2022, 12 (4) : 659-678. doi: 10.3934/naco.2021027
[8]	Xi-Hong Yan. A new convergence proof of augmented Lagrangian-based method with full Jacobian decomposition for structured variational inequalities. Numerical Algebra, Control and Optimization, 2016, 6 (1) : 45-54. doi: 10.3934/naco.2016.6.45
[9]	Anis Theljani, Ke Chen. An augmented lagrangian method for solving a new variational model based on gradients similarity measures and high order regulariation for multimodality registration. Inverse Problems and Imaging, 2019, 13 (2) : 309-335. doi: 10.3934/ipi.2019016
[10]	Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial and Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319
[11]	Qingsong Duan, Mengwei Xu, Yue Lu, Liwei Zhang. A smoothing augmented Lagrangian method for nonconvex, nonsmooth constrained programs and its applications to bilevel problems. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1241-1261. doi: 10.3934/jimo.2018094
[12]	Egil Bae, Xue-Cheng Tai, Wei Zhu. Augmented Lagrangian method for an Euler's elastica based segmentation model that promotes convex contours. Inverse Problems and Imaging, 2017, 11 (1) : 1-23. doi: 10.3934/ipi.2017001
[13]	Xihong Yan. An augmented Lagrangian-based parallel splitting method for a one-leader-two-follower game. Journal of Industrial and Management Optimization, 2016, 12 (3) : 879-890. doi: 10.3934/jimo.2016.12.879
[14]	Andy M. Yip, Wei Zhu. A fast modified Newton's method for curvature based denoising of 1D signals. Inverse Problems and Imaging, 2013, 7 (3) : 1075-1097. doi: 10.3934/ipi.2013.7.1075
[15]	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
[16]	Weina Wang, Chunlin Wu, Jiansong Deng. Piecewise constant signal and image denoising using a selective averaging method with multiple neighbors. Inverse Problems and Imaging, 2019, 13 (5) : 903-930. doi: 10.3934/ipi.2019041
[17]	Chiara Corsato, Franco Obersnel, Pierpaolo Omari, Sabrina Rivetti. On the lower and upper solution method for the prescribed mean curvature equation in Minkowski space. Conference Publications, 2013, 2013 (special) : 159-169. doi: 10.3934/proc.2013.2013.159
[18]	Weihong Guo, Jing Qin. A geometry guided image denoising scheme. Inverse Problems and Imaging, 2013, 7 (2) : 499-521. doi: 10.3934/ipi.2013.7.499
[19]	Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial and Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157
[20]	Qian Liu, Xinmin Yang, Heung Wing Joseph Lee. On saddle points of a class of augmented lagrangian functions. Journal of Industrial and Management Optimization, 2007, 3 (4) : 693-700. doi: 10.3934/jimo.2007.3.693

2021 Impact Factor: 1.483

Tools

Metrics

Other articles
by authors

on AIMS
Wei Zhu Xue-Cheng Tai Tony Chan
on Google Scholar
Wei Zhu Xue-Cheng Tai Tony Chan

[Back to Top]