August  2013, 7(3): 1075-1097. doi: 10.3934/ipi.2013.7.1075

A fast modified Newton's method for curvature based denoising of 1D signals

1. 

Department of Mathematics, National University of Singapore, 10, Lower Kent Ridge Road, 119076

2. 

Department of Mathematics, University of Alabama, Box 870350, Tuscaloosa, AL 35487, United States

Received  June 2012 Revised  December 2012 Published  September 2013

We propose a novel fast numerical method for denoising of 1D signals based on curvature minimization. Motivated by the primal-dual formulation for total variation minimization introduced by Chan, Golub, and Mulet, the proposed method makes use of some auxiliary variables to reformulate the stiff terms presented in the Euler-Lagrange equation which is a fourth-order differential equation. A direct application of Newton's method to the resulting system of equations often fails to converge. We propose a modified Newton's iteration which exhibits local superlinear convergence and global convergence in practical settings. The method is much faster than other existing methods for the model. Unlike all other existing methods, it also does not require tuning any additional parameter besides the model parameter. Numerical experiments are presented to demonstrate the effectiveness of the proposed method.
Citation: 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
References:
[1]

L. Ambrosio and S. Masnou, A direct variational approach to a problem arising in image reconstruction,, Interfaces and Free Boundaries, 5 (2003), 63. doi: 10.4171/IFB/72. Google Scholar

[2]

L. Ambrosio and S. Masnou, On a variational problem arising in image reconstruction,, In, (2004), 17. Google Scholar

[3]

G. Aubert and P. Kornprobst, "Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations,", Second edition. With a foreword by Olivier Faugeras. Applied Mathematical Sciences, (2006). Google Scholar

[4]

E. Bae, J. Shi, and X. C. Tai, Graph cuts for curvature based image denoising,, IEEE Trans. Image Process, 20 (2011), 1199. doi: 10.1109/TIP.2010.2090533. Google Scholar

[5]

P. Blomgren, P. Mulet, T. Chan and C. Wong, Total variation image restoration: Numerical methods and extensions,, In, (1997), 384. doi: 10.1109/ICIP.1997.632128. Google Scholar

[6]

C. Brito and K. Chen, Fast numerical algorithms for Euler's elastica inpainting model,, Int. J. Modern Math., 5 (2010), 157. Google Scholar

[7]

C. Brito and K. Chen, Multigrid algorithm for high order denoising,, SIAM J. Imaging Sci., 3 (2010), 363. doi: 10.1137/080737903. Google Scholar

[8]

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

[9]

T. Chan, G. Golub and P. Mulet, A nonlinear primal-dual method for total variation-based image restoration,, SIAM J. Sci. Comp., 20 (1999), 1964. doi: 10.1137/S1064827596299767. Google Scholar

[10]

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

[11]

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

[12]

T. F. Chan and J. Shen, "Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods,", Society for Industrial and Applied Mathematics (SIAM), (2005). doi: 10.1137/1.9780898717877. Google Scholar

[13]

T. F. Chan, S. Esedo$\barg$lu and F. Park, A fourth order dual method for staircase reduction in texture extraction and image restoration problems,, In, (2010), 4137. doi: 10.1109/ICIP.2010.5653199. Google Scholar

[14]

T. F. Chan, S. Esedo$\barg$lu, F. E. Park and A. M. Yip, Recent developments in total variation image restoration,, In Nikos Paragios, (2005), 17. doi: 10.1007/0-387-28831-7_2. Google Scholar

[15]

M. Elsey and S. Esedo$\barg$lu, Analogue of the total variation denoising model in the context of geometry processing,, SIAM J. Imaging Sci., 7 (2009), 1549. doi: 10.1137/080736612. Google Scholar

[16]

S. Esedo$\barg$lu and R. March, Segmentation with depth but without detecting junctions,, Special issue on imaging science (Boston, 18 (2003), 7. doi: 10.1023/A:1021837026373. Google Scholar

[17]

S. Esedo$\barg$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

[18]

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

[19]

K. Ito and K. Kunisch, An active set strategy based on the augmented Lagrangian formulation for image restoration,, RAIRO Math. Mod. and Num. Analysis, 33 (1999), 1. doi: 10.1051/m2an:1999102. Google Scholar

[20]

T. S. Lau and A. M. Yip, A fast method to segment images with additive intesity value,, SIAM J. Imaging Sci., 5 (2012), 993. doi: 10.1137/120863617. Google Scholar

[21]

Y. N. Law, H. K. Lee, C. Liu and A. M. Yip, A variational model for segmentation of overlapping objects with additive intensity value,, IEEE Trans. Image Process., 20 (2011), 1495. doi: 10.1109/TIP.2010.2095868. Google Scholar

[22]

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

[23]

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

[24]

S. Masnou and J. M. Morel, Level lines based disocclusion,, In, (1998), 259. doi: 10.1109/ICIP.1998.999016. Google Scholar

[25]

Y. Meyer, "Oscillating Patterns in Image Processing and Nonlinear Evolution Equations,", The fifteenth Dean Jacqueline B. Lewis memorial lectures. University Lecture Series, (2001). Google Scholar

[26]

D. Mumford, Elastica and computer vision,, Algebraic Geometry and its Applications, (1994), 491. Google Scholar

[27]

M. Nitzberg and D. Mumford, The 2.1D sketch,, In, (1990), 138. Google Scholar

[28]

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

[29]

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

[30]

P. Smereka, Semi-implicit level set methods for curvature and surface diffusion motion,, J. Sci. Comput., 19 (2003), 439. doi: 10.1023/A:1025324613450. Google Scholar

[31]

D. M. Strong, P. Blomgren and T. F. Chan, Spatially adaptive local feature-driven total variation minimizing image restoration,, In, 3167 (1997), 222. doi: 10.1117/12.279642. 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 Sci., 4 (2011), 313. doi: 10.1137/100803730. Google Scholar

[33]

C. Wu and X. C. Tai, Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and higher order models,, SIAM J. Imaging Sci., 3 (2010), 300. doi: 10.1137/090767558. Google Scholar

[34]

Y. L. You and M. Kaveh, Fourth-order partial differential equations for noise removal,, IEEE Trans. Image Process., 9 (2000), 1723. doi: 10.1109/83.869184. Google Scholar

[35]

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

[36]

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

[37]

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

[38]

W. Zhu, X. C. Tai and T. F. Chan, Augmented Lagrangian method for a mean curvature based image denoising model,, UCLA CAM Report, (2012), 12. Google Scholar

show all references

References:
[1]

L. Ambrosio and S. Masnou, A direct variational approach to a problem arising in image reconstruction,, Interfaces and Free Boundaries, 5 (2003), 63. doi: 10.4171/IFB/72. Google Scholar

[2]

L. Ambrosio and S. Masnou, On a variational problem arising in image reconstruction,, In, (2004), 17. Google Scholar

[3]

G. Aubert and P. Kornprobst, "Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations,", Second edition. With a foreword by Olivier Faugeras. Applied Mathematical Sciences, (2006). Google Scholar

[4]

E. Bae, J. Shi, and X. C. Tai, Graph cuts for curvature based image denoising,, IEEE Trans. Image Process, 20 (2011), 1199. doi: 10.1109/TIP.2010.2090533. Google Scholar

[5]

P. Blomgren, P. Mulet, T. Chan and C. Wong, Total variation image restoration: Numerical methods and extensions,, In, (1997), 384. doi: 10.1109/ICIP.1997.632128. Google Scholar

[6]

C. Brito and K. Chen, Fast numerical algorithms for Euler's elastica inpainting model,, Int. J. Modern Math., 5 (2010), 157. Google Scholar

[7]

C. Brito and K. Chen, Multigrid algorithm for high order denoising,, SIAM J. Imaging Sci., 3 (2010), 363. doi: 10.1137/080737903. Google Scholar

[8]

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

[9]

T. Chan, G. Golub and P. Mulet, A nonlinear primal-dual method for total variation-based image restoration,, SIAM J. Sci. Comp., 20 (1999), 1964. doi: 10.1137/S1064827596299767. Google Scholar

[10]

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

[11]

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

[12]

T. F. Chan and J. Shen, "Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods,", Society for Industrial and Applied Mathematics (SIAM), (2005). doi: 10.1137/1.9780898717877. Google Scholar

[13]

T. F. Chan, S. Esedo$\barg$lu and F. Park, A fourth order dual method for staircase reduction in texture extraction and image restoration problems,, In, (2010), 4137. doi: 10.1109/ICIP.2010.5653199. Google Scholar

[14]

T. F. Chan, S. Esedo$\barg$lu, F. E. Park and A. M. Yip, Recent developments in total variation image restoration,, In Nikos Paragios, (2005), 17. doi: 10.1007/0-387-28831-7_2. Google Scholar

[15]

M. Elsey and S. Esedo$\barg$lu, Analogue of the total variation denoising model in the context of geometry processing,, SIAM J. Imaging Sci., 7 (2009), 1549. doi: 10.1137/080736612. Google Scholar

[16]

S. Esedo$\barg$lu and R. March, Segmentation with depth but without detecting junctions,, Special issue on imaging science (Boston, 18 (2003), 7. doi: 10.1023/A:1021837026373. Google Scholar

[17]

S. Esedo$\barg$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

[18]

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

[19]

K. Ito and K. Kunisch, An active set strategy based on the augmented Lagrangian formulation for image restoration,, RAIRO Math. Mod. and Num. Analysis, 33 (1999), 1. doi: 10.1051/m2an:1999102. Google Scholar

[20]

T. S. Lau and A. M. Yip, A fast method to segment images with additive intesity value,, SIAM J. Imaging Sci., 5 (2012), 993. doi: 10.1137/120863617. Google Scholar

[21]

Y. N. Law, H. K. Lee, C. Liu and A. M. Yip, A variational model for segmentation of overlapping objects with additive intensity value,, IEEE Trans. Image Process., 20 (2011), 1495. doi: 10.1109/TIP.2010.2095868. Google Scholar

[22]

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

[23]

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

[24]

S. Masnou and J. M. Morel, Level lines based disocclusion,, In, (1998), 259. doi: 10.1109/ICIP.1998.999016. Google Scholar

[25]

Y. Meyer, "Oscillating Patterns in Image Processing and Nonlinear Evolution Equations,", The fifteenth Dean Jacqueline B. Lewis memorial lectures. University Lecture Series, (2001). Google Scholar

[26]

D. Mumford, Elastica and computer vision,, Algebraic Geometry and its Applications, (1994), 491. Google Scholar

[27]

M. Nitzberg and D. Mumford, The 2.1D sketch,, In, (1990), 138. Google Scholar

[28]

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

[29]

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

[30]

P. Smereka, Semi-implicit level set methods for curvature and surface diffusion motion,, J. Sci. Comput., 19 (2003), 439. doi: 10.1023/A:1025324613450. Google Scholar

[31]

D. M. Strong, P. Blomgren and T. F. Chan, Spatially adaptive local feature-driven total variation minimizing image restoration,, In, 3167 (1997), 222. doi: 10.1117/12.279642. 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 Sci., 4 (2011), 313. doi: 10.1137/100803730. Google Scholar

[33]

C. Wu and X. C. Tai, Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and higher order models,, SIAM J. Imaging Sci., 3 (2010), 300. doi: 10.1137/090767558. Google Scholar

[34]

Y. L. You and M. Kaveh, Fourth-order partial differential equations for noise removal,, IEEE Trans. Image Process., 9 (2000), 1723. doi: 10.1109/83.869184. Google Scholar

[35]

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

[36]

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

[37]

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

[38]

W. Zhu, X. C. Tai and T. F. Chan, Augmented Lagrangian method for a mean curvature based image denoising model,, UCLA CAM Report, (2012), 12. Google Scholar

[1]

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

[2]

Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial & Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037

[3]

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

[4]

Liyan Ma, Lionel Moisan, Jian Yu, Tieyong Zeng. A stable method solving the total variation dictionary model with $L^\infty$ constraints. Inverse Problems & Imaging, 2014, 8 (2) : 507-535. doi: 10.3934/ipi.2014.8.507

[5]

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

[6]

Johnathan M. Bardsley. An efficient computational method for total variation-penalized Poisson likelihood estimation. Inverse Problems & Imaging, 2008, 2 (2) : 167-185. doi: 10.3934/ipi.2008.2.167

[7]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733

[8]

Yunho Kim, Paul M. Thompson, Luminita A. Vese. HARDI data denoising using vectorial total variation and logarithmic barrier. Inverse Problems & Imaging, 2010, 4 (2) : 273-310. doi: 10.3934/ipi.2010.4.273

[9]

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

[10]

R. Baier, M. Dellnitz, M. Hessel-von Molo, S. Sertl, I. G. Kevrekidis. The computation of convex invariant sets via Newton's method. Journal of Computational Dynamics, 2014, 1 (1) : 39-69. doi: 10.3934/jcd.2014.1.39

[11]

Liqun Qi, Zheng yan, Hongxia Yin. Semismooth reformulation and Newton's method for the security region problem of power systems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 143-153. doi: 10.3934/jimo.2008.4.143

[12]

Zhengmeng Jin, Chen Zhou, Michael K. Ng. A coupled total variation model with curvature driven for image colorization. Inverse Problems & Imaging, 2016, 10 (4) : 1037-1055. doi: 10.3934/ipi.2016031

[13]

Nils Dabrock, Yves van Gennip. A note on "Anisotropic total variation regularized $L^1$-approximation and denoising/deblurring of 2D bar codes". Inverse Problems & Imaging, 2018, 12 (2) : 525-526. doi: 10.3934/ipi.2018022

[14]

Rustum Choksi, Yves van Gennip, Adam Oberman. Anisotropic total variation regularized $L^1$ approximation and denoising/deblurring of 2D bar codes. Inverse Problems & Imaging, 2011, 5 (3) : 591-617. doi: 10.3934/ipi.2011.5.591

[15]

Florian Krügel. Some properties of minimizers of a variational problem involving the total variation functional. Communications on Pure & Applied Analysis, 2015, 14 (1) : 341-360. doi: 10.3934/cpaa.2015.14.341

[16]

Matteo Cozzi. On the variation of the fractional mean curvature under the effect of $C^{1, \alpha}$ perturbations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (12) : 5769-5786. doi: 10.3934/dcds.2015.35.5769

[17]

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

[18]

Matthias Gerdts, Martin Kunkel. A nonsmooth Newton's method for discretized optimal control problems with state and control constraints. Journal of Industrial & Management Optimization, 2008, 4 (2) : 247-270. doi: 10.3934/jimo.2008.4.247

[19]

Henryk Leszczyński, Monika Wrzosek. Newton's method for nonlinear stochastic wave equations driven by one-dimensional Brownian motion. Mathematical Biosciences & Engineering, 2017, 14 (1) : 237-248. doi: 10.3934/mbe.2017015

[20]

T. Tachim Medjo. On the Newton method in robust control of fluid flow. Discrete & Continuous Dynamical Systems - A, 2003, 9 (5) : 1201-1222. doi: 10.3934/dcds.2003.9.1201

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]