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]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[2]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[3]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[4]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[5]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

[6]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[7]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

[8]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120

[9]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167

[10]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[11]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[12]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[13]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321

[14]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

2019 Impact Factor: 1.373

Metrics

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

Other articles
by authors

[Back to Top]