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

Augmented Lagrangian method for a mean curvature based image denoising model

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

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.
Citation: Wei Zhu, Xue-Cheng Tai, Tony Chan. Augmented Lagrangian method for a mean curvature based image denoising model. Inverse Problems & 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. doi: 10.4171/IFB/72. Google Scholar

[2]

L. Ambrosio and S. Masnou, On a variational problem arising in image reconstruction,, Free Boundary Problems (Trento, 147 (2004), 17. Google Scholar

[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. doi: 10.1007/BF00375127. Google Scholar

[4]

G. Aubert and L. Vese, A variational method in image recovery,, SIAM J. Numer. Anal. 34 (1987), 34 (1987), 1948. doi: 10.1137/S003614299529230X. Google Scholar

[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. doi: 10.1002/cpa.20019. Google Scholar

[6]

T. Chan and S. Esedoglu, Aspects of total variation regularized $L^1$ function approximation,, SIAM J. Appl. Math., 65 (2005), 1817. doi: 10.1137/040604297. Google Scholar

[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. doi: 10.1109/TPAMI.2006.195. Google Scholar

[8]

A. Chambolle and P. L. Lions, Image recovery via total variation minimization and related problems,, Numer. Math., 76 (1997), 167. doi: 10.1007/s002110050258. Google Scholar

[9]

T. Chan, S. H. Kang and J. H. Shen, Euler's elastica and curvature-based inpainting,, SIAM J. Appl. Math., 63 (2002), 564. doi: 10.1137/S0036139901390088. Google Scholar

[10]

T. Chan, A. Marquina and P. Mulet, High-order total variation-based image restoration,, SIAM J. Sci. Comput., 22 (2000), 503. doi: 10.1137/S1064827598344169. Google Scholar

[11]

M. P. do Carmo, Differential geometry of curves and surfaces,, Translated From the Portuguese. Prentice-Hall, 1976 (). Google Scholar

[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. doi: 10.1137/080736612. Google Scholar

[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. doi: 10.1017/S0956792502004904. Google Scholar

[14]

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

[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. doi: 10.1137/S0036141003427373. Google Scholar

[16]

J. B. Greer, A. L. Bertozzi and G. Sapiro, Fourth order partial differential equations on general geometries,, J. Comp. Phys., 216 (2006), 216. doi: 10.1016/j.jcp.2005.11.031. Google Scholar

[17]

R. Kimmel, R. Malladi and N. Sochen, Image processing via the Beltrami Operator,, Proceedings of Asian Conference on Computer Vision, 1351 (1998), 574. doi: 10.1007/3-540-63930-6_169. Google Scholar

[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. Google Scholar

[19]

P. L. Lions and B. Mercier, Splitting algorithms for the sume of two nonlinear opertors,, SIAM J. Numer. Anal., 16 (1979), 964. doi: 10.1137/0716071. Google Scholar

[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. doi: 10.1109/TIP.2003.819229. Google Scholar

[21]

M. Lysaker, S. Osher and X. C. Tai, Noise removal using smoothed normals and surface fitting,, IEEE. Trans. Image Process., 13 (2004), 1345. doi: 10.1109/TIP.2004.834662. Google Scholar

[22]

S. Masnou, Disocclusion: A variational approach using level lines,, IEEE Trans. Image Process., 11 (2002), 68. doi: 10.1109/83.982815. Google Scholar

[23]

S. Masnou and J. M. Morel, Level lines based disocclusion,, Proc. IEEE Int. Conf. on Image Processing, (1998), 259. doi: 10.1109/ICIP.1998.999016. Google Scholar

[24]

Y. Meyer, Oscillating patterns in image processing and nonlinear evolution equations,, University Lecture Series, 22 (2002). Google Scholar

[25]

D. Mumford and J. Shah, Optimal approximation by piecewise smooth functions and associated variational problems,, Comm. Pure Appl. Math., 42 (1989), 577. doi: 10.1002/cpa.3160420503. Google Scholar

[26]

J. M. Morel and S. Solimini, Variational methods in image segmentation,, Birkhauser, (1995). doi: 10.1007/978-1-4684-0567-5. Google Scholar

[27]

M. Nitzberg, D. Mumford and T. Shiota, Filtering, segmentation, and depth,, Lecture Notes in Computer Science, 662 (1993). doi: 10.1007/3-540-56484-5. Google Scholar

[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. doi: 10.1137/S1540345902416247. Google Scholar

[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. doi: 10.1109/34.56205. Google Scholar

[30]

L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithm,, Physica D, 60 (1992), 259. doi: 10.1016/0167-2789(92)90242-F. Google Scholar

[31]

N. Sochen, R. Kimmel and R. Malladi, A geometrical framework for low level vision,, IEEE Trans. on Image Process., 7 (1998), 310. doi: 10.1109/83.661181. Google Scholar

[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. doi: 10.1137/100803730. Google Scholar

[33]

T. Tasdizen, R. Whitaker, P. Burchard and S. Osher, Geometric surface processing via normal maps,, ACM Transactions on Graphics, 22 (2003), 1012. doi: 10.1145/944020.944024. Google Scholar

[34]

L. Vese and S. Osher, Modeling textures with total variation minimization and oscillatory patterns im image processing,, SINUM., 40 (2003), 2085. doi: 10.1137/S0036142901396715. Google Scholar

[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. doi: 10.1137/090767558. Google Scholar

[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. doi: 10.1093/bioinformatics/bti341. Google Scholar

[37]

W. Zhu and T. Chan, A variational model for capturing illusory contours using curvature,, J. Math. Imaging Vision, 27 (2007), 29. doi: 10.1007/s10851-006-9695-8. Google Scholar

[38]

W. Zhu and T. Chan, Image denoising using mean curvature of image surface,, SIAM J. Imaging Sciences, 5 (2012), 1. doi: 10.1137/110822268. Google Scholar

[39]

W. Zhu, T. Chan and S. Esedoglu, Segmentation with depth: A level set approach,, SIAM J. Sci. Comput., 28 (2006), 1957. doi: 10.1137/050622213. Google Scholar

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. doi: 10.4171/IFB/72. Google Scholar

[2]

L. Ambrosio and S. Masnou, On a variational problem arising in image reconstruction,, Free Boundary Problems (Trento, 147 (2004), 17. Google Scholar

[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. doi: 10.1007/BF00375127. Google Scholar

[4]

G. Aubert and L. Vese, A variational method in image recovery,, SIAM J. Numer. Anal. 34 (1987), 34 (1987), 1948. doi: 10.1137/S003614299529230X. Google Scholar

[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. doi: 10.1002/cpa.20019. Google Scholar

[6]

T. Chan and S. Esedoglu, Aspects of total variation regularized $L^1$ function approximation,, SIAM J. Appl. Math., 65 (2005), 1817. doi: 10.1137/040604297. Google Scholar

[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. doi: 10.1109/TPAMI.2006.195. Google Scholar

[8]

A. Chambolle and P. L. Lions, Image recovery via total variation minimization and related problems,, Numer. Math., 76 (1997), 167. doi: 10.1007/s002110050258. Google Scholar

[9]

T. Chan, S. H. Kang and J. H. Shen, Euler's elastica and curvature-based inpainting,, SIAM J. Appl. Math., 63 (2002), 564. doi: 10.1137/S0036139901390088. Google Scholar

[10]

T. Chan, A. Marquina and P. Mulet, High-order total variation-based image restoration,, SIAM J. Sci. Comput., 22 (2000), 503. doi: 10.1137/S1064827598344169. Google Scholar

[11]

M. P. do Carmo, Differential geometry of curves and surfaces,, Translated From the Portuguese. Prentice-Hall, 1976 (). Google Scholar

[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. doi: 10.1137/080736612. Google Scholar

[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. doi: 10.1017/S0956792502004904. Google Scholar

[14]

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

[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. doi: 10.1137/S0036141003427373. Google Scholar

[16]

J. B. Greer, A. L. Bertozzi and G. Sapiro, Fourth order partial differential equations on general geometries,, J. Comp. Phys., 216 (2006), 216. doi: 10.1016/j.jcp.2005.11.031. Google Scholar

[17]

R. Kimmel, R. Malladi and N. Sochen, Image processing via the Beltrami Operator,, Proceedings of Asian Conference on Computer Vision, 1351 (1998), 574. doi: 10.1007/3-540-63930-6_169. Google Scholar

[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. Google Scholar

[19]

P. L. Lions and B. Mercier, Splitting algorithms for the sume of two nonlinear opertors,, SIAM J. Numer. Anal., 16 (1979), 964. doi: 10.1137/0716071. Google Scholar

[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. doi: 10.1109/TIP.2003.819229. Google Scholar

[21]

M. Lysaker, S. Osher and X. C. Tai, Noise removal using smoothed normals and surface fitting,, IEEE. Trans. Image Process., 13 (2004), 1345. doi: 10.1109/TIP.2004.834662. Google Scholar

[22]

S. Masnou, Disocclusion: A variational approach using level lines,, IEEE Trans. Image Process., 11 (2002), 68. doi: 10.1109/83.982815. Google Scholar

[23]

S. Masnou and J. M. Morel, Level lines based disocclusion,, Proc. IEEE Int. Conf. on Image Processing, (1998), 259. doi: 10.1109/ICIP.1998.999016. Google Scholar

[24]

Y. Meyer, Oscillating patterns in image processing and nonlinear evolution equations,, University Lecture Series, 22 (2002). Google Scholar

[25]

D. Mumford and J. Shah, Optimal approximation by piecewise smooth functions and associated variational problems,, Comm. Pure Appl. Math., 42 (1989), 577. doi: 10.1002/cpa.3160420503. Google Scholar

[26]

J. M. Morel and S. Solimini, Variational methods in image segmentation,, Birkhauser, (1995). doi: 10.1007/978-1-4684-0567-5. Google Scholar

[27]

M. Nitzberg, D. Mumford and T. Shiota, Filtering, segmentation, and depth,, Lecture Notes in Computer Science, 662 (1993). doi: 10.1007/3-540-56484-5. Google Scholar

[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. doi: 10.1137/S1540345902416247. Google Scholar

[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. doi: 10.1109/34.56205. Google Scholar

[30]

L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithm,, Physica D, 60 (1992), 259. doi: 10.1016/0167-2789(92)90242-F. Google Scholar

[31]

N. Sochen, R. Kimmel and R. Malladi, A geometrical framework for low level vision,, IEEE Trans. on Image Process., 7 (1998), 310. doi: 10.1109/83.661181. Google Scholar

[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. doi: 10.1137/100803730. Google Scholar

[33]

T. Tasdizen, R. Whitaker, P. Burchard and S. Osher, Geometric surface processing via normal maps,, ACM Transactions on Graphics, 22 (2003), 1012. doi: 10.1145/944020.944024. Google Scholar

[34]

L. Vese and S. Osher, Modeling textures with total variation minimization and oscillatory patterns im image processing,, SINUM., 40 (2003), 2085. doi: 10.1137/S0036142901396715. Google Scholar

[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. doi: 10.1137/090767558. Google Scholar

[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. doi: 10.1093/bioinformatics/bti341. Google Scholar

[37]

W. Zhu and T. Chan, A variational model for capturing illusory contours using curvature,, J. Math. Imaging Vision, 27 (2007), 29. doi: 10.1007/s10851-006-9695-8. Google Scholar

[38]

W. Zhu and T. Chan, Image denoising using mean curvature of image surface,, SIAM J. Imaging Sciences, 5 (2012), 1. doi: 10.1137/110822268. Google Scholar

[39]

W. Zhu, T. Chan and S. Esedoglu, Segmentation with depth: A level set approach,, SIAM J. Sci. Comput., 28 (2006), 1957. doi: 10.1137/050622213. Google Scholar

[1]

Wei Zhu. A numerical study of a mean curvature denoising model using a novel augmented Lagrangian method. Inverse Problems & Imaging, 2017, 11 (6) : 975-996. doi: 10.3934/ipi.2017045

[2]

Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems & Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237

[3]

Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-9. doi: 10.3934/jimo.2018136

[4]

Li Jin, Hongying Huang. Differential equation method based on approximate augmented Lagrangian for nonlinear programming. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2019053

[5]

Xi-Hong Yan. A new convergence proof of augmented Lagrangian-based method with full Jacobian decomposition for structured variational inequalities. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 45-54. doi: 10.3934/naco.2016.6.45

[6]

Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319

[7]

Egil Bae, Xue-Cheng Tai, Wei Zhu. Augmented Lagrangian method for an Euler's elastica based segmentation model that promotes convex contours. Inverse Problems & Imaging, 2017, 11 (1) : 1-23. doi: 10.3934/ipi.2017001

[8]

Xihong Yan. An augmented Lagrangian-based parallel splitting method for a one-leader-two-follower game. Journal of Industrial & Management Optimization, 2016, 12 (3) : 879-890. doi: 10.3934/jimo.2016.12.879

[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 & Imaging, 2019, 13 (2) : 309-335. doi: 10.3934/ipi.2019016

[10]

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 & Management Optimization, 2019, 15 (3) : 1241-1261. doi: 10.3934/jimo.2018094

[11]

Michael Hintermüller, Monserrat Rincon-Camacho. An adaptive finite element method in $L^2$-TV-based image denoising. Inverse Problems & Imaging, 2014, 8 (3) : 685-711. doi: 10.3934/ipi.2014.8.685

[12]

Andy M. Yip, Wei Zhu. A fast modified Newton's method for curvature based denoising of 1D signals. Inverse Problems & Imaging, 2013, 7 (3) : 1075-1097. doi: 10.3934/ipi.2013.7.1075

[13]

Weina Wang, Chunlin Wu, Jiansong Deng. Piecewise constant signal and image denoising using a selective averaging method with multiple neighbors. Inverse Problems & Imaging, 2019, 13 (5) : 903-930. doi: 10.3934/ipi.2019041

[14]

Weihong Guo, Jing Qin. A geometry guided image denoising scheme. Inverse Problems & Imaging, 2013, 7 (2) : 499-521. doi: 10.3934/ipi.2013.7.499

[15]

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

[16]

Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial & Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157

[17]

Qian Liu, Xinmin Yang, Heung Wing Joseph Lee. On saddle points of a class of augmented lagrangian functions. Journal of Industrial & Management Optimization, 2007, 3 (4) : 693-700. doi: 10.3934/jimo.2007.3.693

[18]

Y. Goto, K. Ishii, T. Ogawa. Method of the distance function to the Bence-Merriman-Osher algorithm for motion by mean curvature. Communications on Pure & Applied Analysis, 2005, 4 (2) : 311-339. doi: 10.3934/cpaa.2005.4.311

[19]

Chunrong Chen. A unified nonlinear augmented Lagrangian approach for nonconvex vector optimization. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 495-508. doi: 10.3934/naco.2011.1.495

[20]

Fangfang Dong, Yunmei Chen. A fractional-order derivative based variational framework for image denoising. Inverse Problems & Imaging, 2016, 10 (1) : 27-50. doi: 10.3934/ipi.2016.10.27

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (18)
  • HTML views (0)
  • Cited by (22)

Other articles
by authors

[Back to Top]