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

Andy M. Yip; Wei Zhu

doi:10.3934/ipi.2013.7.1075

Article Contents

2013, Volume 7, Issue 3: 1075-1097. Doi: 10.3934/ipi.2013.7.1075

This issue Previous Article The Gaussian beam method for the wigner equation with discontinuous potentials Next Article Four color theorem and convex relaxation for image segmentation with any number of regions

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

Andy M. Yip^1, and
Wei Zhu^2,

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

Received: June 2012

Revised: December 2012

Published: August 2013

Abstract / Introduction Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 68U10, 49M15; Secondary: 94A12.

Citation:

Related Papers

Cited by

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-81.doi: 10.4171/IFB/72.
[2]	L. Ambrosio and S. Masnou, On a variational problem arising in image reconstruction, In "Proc. Free Boundary Problems," volume 147 of Internat. Series of Num. Math., Basel, 2004. Birkhauser, 17-26.
[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, 147. Springer, New York, 2006.
[4]	E. Bae, J. Shi, and X. C. Tai, Graph cuts for curvature based image denoising, IEEE Trans. Image Process, 20(2011), 1199-1210.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 "ICIP," pages 384-387, Santa Barbara, 1997.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-182.
[7]	C. Brito and K. Chen, Multigrid algorithm for high order denoising, SIAM J. Imaging Sci., 3 (2010), 363-389.doi: 10.1137/080737903.
[8]	A. Chambolle and P. Lions, Image recovery via total variation minimization and related problems, Numer. Math., 76 (1997), 167-188.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-1977.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-592.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-516.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), Philadelphia, PA, 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 "Proceedings of 2010 IEEE 17th Int. Conf. on Image Process," pages 4137-4140, Hong Kong, 2010.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, Yunmei Chen, and Olivier Faugeras, Editors, Handbook of Mathematical Models in Computer Vision, pages 17-31. Springer, Berlin, 2005.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-1573.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, MA, 2002). J. Math. Imaging and Vision, 18 (2003), 7-15.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-370.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-68.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-21.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-1021.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-1503.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-1590.doi: 10.1109/TIP.2003.819229.
[23]	S. Masnou, Disocclusion: A variational approach using level lines, IEEE Trans. Image Process., 11 (2002), 68-76.doi: 10.1109/83.982815.
[24]	S. Masnou and J. M. Morel, Level lines based disocclusion, In "Proc. IEEE Int. Conf. on Image Process.," pages 259-263, Chicago, IL, 1998.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, 22. AMS, Providence, Rhode Island, 2001.
[26]	D. Mumford, Elastica and computer vision, Algebraic Geometry and its Applications, 491-506, Springer, New York, (1994).
[27]	M. Nitzberg and D. Mumford, The 2.1D sketch, In "Proc. of the 3rd Intl. Conf. on Computer Vision," pages 138-144, 1990.
[28]	M. Nitzberg, D. Mumford and T. Shiota, "Filtering, Segmentation, and Depth," Lecture Notes in Computer Science, 662. Springer-Verlag, New York, 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-268.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-456.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 "Proceedings of The International Society of Photo-Optical Instrumentation Engineers: Statistical and Stochastic Methods in Image Processing II," 3167 (1997), 222-233.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-344.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-339.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-1730.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-40.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-1973.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-32.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, 12-02, 2012.