# American Institute of Mathematical Sciences

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. [2] L. Ambrosio and S. Masnou, On a variational problem arising in image reconstruction,, In, (2004), 17. [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). [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. [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. [6] C. Brito and K. Chen, Fast numerical algorithms for Euler's elastica inpainting model,, Int. J. Modern Math., 5 (2010), 157. [7] C. Brito and K. Chen, Multigrid algorithm for high order denoising,, SIAM J. Imaging Sci., 3 (2010), 363. doi: 10.1137/080737903. [8] A. Chambolle and P. Lions, Image recovery via total variation minimization and related problems,, Numer. Math., 76 (1997), 167. doi: 10.1007/s002110050258. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [23] S. Masnou, Disocclusion: A variational approach using level lines,, IEEE Trans. Image Process., 11 (2002), 68. doi: 10.1109/83.982815. [24] S. Masnou and J. M. Morel, Level lines based disocclusion,, In, (1998), 259. doi: 10.1109/ICIP.1998.999016. [25] Y. Meyer, "Oscillating Patterns in Image Processing and Nonlinear Evolution Equations,", The fifteenth Dean Jacqueline B. Lewis memorial lectures. University Lecture Series, (2001). [26] D. Mumford, Elastica and computer vision,, Algebraic Geometry and its Applications, (1994), 491. [27] M. Nitzberg and D. Mumford, The 2.1D sketch,, In, (1990), 138. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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.

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. [2] L. Ambrosio and S. Masnou, On a variational problem arising in image reconstruction,, In, (2004), 17. [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). [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. [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. [6] C. Brito and K. Chen, Fast numerical algorithms for Euler's elastica inpainting model,, Int. J. Modern Math., 5 (2010), 157. [7] C. Brito and K. Chen, Multigrid algorithm for high order denoising,, SIAM J. Imaging Sci., 3 (2010), 363. doi: 10.1137/080737903. [8] A. Chambolle and P. Lions, Image recovery via total variation minimization and related problems,, Numer. Math., 76 (1997), 167. doi: 10.1007/s002110050258. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [23] S. Masnou, Disocclusion: A variational approach using level lines,, IEEE Trans. Image Process., 11 (2002), 68. doi: 10.1109/83.982815. [24] S. Masnou and J. M. Morel, Level lines based disocclusion,, In, (1998), 259. doi: 10.1109/ICIP.1998.999016. [25] Y. Meyer, "Oscillating Patterns in Image Processing and Nonlinear Evolution Equations,", The fifteenth Dean Jacqueline B. Lewis memorial lectures. University Lecture Series, (2001). [26] D. Mumford, Elastica and computer vision,, Algebraic Geometry and its Applications, (1994), 491. [27] M. Nitzberg and D. Mumford, The 2.1D sketch,, In, (1990), 138. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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.
 [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] 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 [8] 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 [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] 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 [17] 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 [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

2017 Impact Factor: 1.465