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.

[2]

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

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

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

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

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

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

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

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

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

[11]

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

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

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

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

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

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

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

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

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

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

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

[22]

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

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

[24]

Y. Meyer, Oscillating patterns in image processing and nonlinear evolution equations,, University Lecture Series, 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. doi: 10.1002/cpa.3160420503.

[26]

J. M. Morel and S. Solimini, Variational methods in image segmentation,, Birkhauser, (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). 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. doi: 10.4171/IFB/72.

[2]

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

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

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

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

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

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

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

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

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

[11]

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

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

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

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

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

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

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

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

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

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

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

[22]

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

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

[24]

Y. Meyer, Oscillating patterns in image processing and nonlinear evolution equations,, University Lecture Series, 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. doi: 10.1002/cpa.3160420503.

[26]

J. M. Morel and S. Solimini, Variational methods in image segmentation,, Birkhauser, (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). 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. doi: 10.1137/050622213.

[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]

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

[4]

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

[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]

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

[7]

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, 2017, 13 (5) : 1-21. doi: 10.3934/jimo.2018094

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

Qiang Liu, Zhichang Guo, Chunpeng Wang. Renormalized solutions to a reaction-diffusion system applied to image denoising. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1839-1858. doi: 10.3934/dcdsb.2016025

[18]

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

[19]

Jian Hao, Zhilin Li, Sharon R. Lubkin. An augmented immersed interface method for moving structures with mass. Discrete & Continuous Dynamical Systems - B, 2012, 17 (4) : 1175-1184. doi: 10.3934/dcdsb.2012.17.1175

[20]

Seung-Yeal Ha, Jeongho Kim, Jinyeong Park, Xiongtao Zhang. Uniform stability and mean-field limit for the augmented Kuramoto model. Networks & Heterogeneous Media, 2018, 13 (2) : 297-322. doi: 10.3934/nhm.2018013

2017 Impact Factor: 1.465

Metrics

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

Other articles
by authors

[Back to Top]