Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-30T21:18:39.287Z Has data issue: false hasContentIssue false
  • English
  • Français

A Fast Augmented Lagrangian Method for Euler’s Elastica Models

Published online by Cambridge University Press:  28 May 2015

Yuping Duan ,
Yu Wang  and
Jooyoung Hahn
Yuping Duan*
Affiliation:
Institute for Infocomm Research, Singapore
Yu Wang*
Affiliation:
Computer Science Department, Technion, Haifa 32000, Israel
Jooyoung Hahn*
Affiliation:
Institute for Mathematics and Scientific Computing, University of Graz, Austria
*
Corresponding author.Email address:[email protected]
Corresponding author.Email address:[email protected]
Corresponding author.Email address:[email protected]
Get access

Abstract

In this paper, a fast algorithm for Euler’s elastica functional is proposed, in which the Euler’s elastica functional is reformulated as a constrained minimization problem. Combining the augmented Lagrangian method and operator splitting techniques, the resulting saddle-point problem is solved by a serial of subproblems. To tackle the nonlinear constraints arising in the model, a novel fixed-point-based approach is proposed so that all the subproblems either is a linear problem or has a closed-form solution. We show the good performance of our approach in terms of speed and reliability using numerous numerical examples on synthetic, real-world and medical images for image denoising, image inpainting and image zooming problems.

Keywords

68U1065N2174S20Euler’s elasticaaugmented Lagrangian methodimage denoisingimage inpaintingimage zooming
Type
Research Article
Information
Numerical Mathematics: Theory, Methods and Applications , Volume 6 , Issue 1 , February 2013 , pp. 47 - 71
Copyright
Copyright © Global Science Press Limited 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Ambrosio, L. and Masnou, S., A direct variational approach to a problem arising in image reconstruction, Interfaces and Free Boundaries, 5(1) (2003), pp. 63–82.Google Scholar
[2] Ambrosio, L. and Masnou, S., On a variational problem arising in image reconstruction, Free Boundary Problems, 147(1) (2005), pp. 17–26.Google Scholar
[3] Bae, E., Shi, J. and Tai, X. C., Graph cuts for curvature based image denoising, IEEE Trans. Image Proc., 20(5) (2011), pp. 1199–1210.Google Scholar
[4] Ballester, C., Bertalmio, M., Caselles, V., Sapiro, G. and Verdera, J., Filling-in by joint interpolation of vector fields and gray levels, IEEE Trans. Image Proc., 10(8) (2002), pp. 1200–1211.Google Scholar
[5] Ballester, C., Caselles, V. and Verdera, J., Disocclusion by joint interpolation of vector fields and gray levels, Multiscale Model. Sim., 2(1) (2004), pp. 80–123.Google Scholar
[6] Bresson, X. and Chan, T. F., Fast dual minimization of the vectorial total variation norm and applications to color image processing, Inverse Problems Imaging, 2(4) (2008), pp. 455–484.CrossRefGoogle Scholar
[7] Brito-Loeza, C. and Chen, K., Fast numerical algorithms for eulers elastica inpainting model, Int. J. Modern Math., 5 (2010), pp. 157–182.Google Scholar
[8] Brito, C.-LOEZA and Chen, K., Multigrid algorithm for high order denoising, SIAM J. Imaging Sci., 3(3) (2010), pp. 363–389.Google Scholar
[9] Chambolle, A., An algorithm for total variation minimization and applications, J. Math. Imaging Vision, 20(1) (2004), pp. 89–97.Google Scholar
[10] Chambolle, A. and Lions, P. L., Image recovery via total variation minimization and related problems, Numer. Math., 76(2) (1997), pp. 167–188.CrossRefGoogle Scholar
[11] Chan, T., Golub, G. and Mulet, P., A nonlinear primal-dual method for total variation-based image restoration, SIAM J. Sci. Comput., 20(6) (1999), pp. 1964–1977.CrossRefGoogle Scholar
[12] Chan, T., Marquina, A. and Mulet, P., High-order total variation-based image restoration, SIAM J. Sci. Comput., 22(2) (2000), pp. 503–516.Google Scholar
[13] Chan, T. F., Kang, S. H. and Shen, J., Total variation denoising and enhancement of color images based on the CB and HSV color models, J. Visual Commun. Image Representation, 12(4) (2001), pp. 422–435.Google Scholar
[14] Chan, T. F., Kang, S. H. and Shen, J., Euler’s elastica and curvature-based inpainting, SIAM J. Appl. Math., 63(2) (2002), pp. 564–592.Google Scholar
[15] Droske, M. and Bertozzi, A., Higher-order feature-preserving geometric regularization, SIAM J. Imaging Sci., 3(1) (2010), pp. 21–51.Google Scholar
[16] Esedoglu, S. and March, R., Segmentation with depth but without detecting junctions, J. Math. Imaging Vision, 18(1) (2003), pp. 7–15.Google Scholar
[17] Esedoglu, S., Ruuth, S. and Tsai, R., Threshold dynamics for shape reconstruction and disocclusion, in IEEE Int. Conference Image Processing, 2 (2005), pp. 502–505.Google Scholar
[18] Gao, R., Song, J. P. and Tai, X. C., Image zooming algorithm based on partial differential equations technique, Int. J. Numer. Anal. Modeling, 6(2) (2009), pp. 284–292.Google Scholar
[19] Hahn, J., Chung, G. J., Wang, Y. and Tai, X. C., Fast algorithms for p-elastica energy with the application to image inpainting and curve reconstruction, in SSVM’11: Proceedings of the Second International Conference on Scale Space and Variational Methods in Computer Vision, pp. 169–182. Springer, 2011.Google Scholar
[20] Hahn, J., Wu, C. and Tai, X. C., Augmented lagrangian method for generalized TV-stokes model, J. Sci. Computing, 50(2) (2012), pp. 235–264.Google Scholar
[21] Komodakis, N. and Paragios, N., Beyond pairwise energies: efficient optimization for higherorder MRFs, in IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 2985–2992, 2009.Google Scholar
[22] Lai, R. and Chan, T. F., A framework for intrinsic image processing on surfaces, Comput. Vision Image Understanding, 115(12) (2011), pp. 1647–1661.Google Scholar
[23] Lehmann, T. M., Gonner, C. and Spitzer, K., Survey: interpolation methods in medical image processing, IEEE Trans. Medical Imaging, 18(11) (1999), pp. 1049–1075.Google Scholar
[24] Lysaker, M., Lundervold, A. and Tai, X. C., Noise removal using fourth-order partial differential equation with applications to medical magnetic resonance images in space and time, IEEE Trans. Image Processing, 12(12) (2003), pp. 1579–1590.Google Scholar
[25] Maeland, E., On the comparison of interpolation methods, IEEE Trans. Medical Imaging, 7(3) (1988), pp. 213–217.CrossRefGoogle ScholarPubMed
[26] Masnou, S. and Morel, J. M., Level lines based disocclusion, in IEEE Int. Conference Image Processing, pp. 259–263, 1998.Google Scholar
[27] Masnou, S. and Morel, J. M., Level lines based disocclusion, in Int. Conference Image Processing, pp. 259–263, 1998.Google Scholar
[28] Mumford, D. and Center for Intelligent Control Systems (US), Elastica and computer vision. Center for Intelligent Control Systems, Massachusetts Institute of Technology, 1991.Google Scholar
[29] Nitzberg, M., Mumford, D. and Shiota, T., Filtering, segmentation and depth, Lecture Notes Computer Sci., 1993.Google Scholar
[30] Rockafellar, R. T., Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Operations Research, 1(2) (1976), pp. 97–116.Google Scholar
[31] Rudin, L. I., Osher, S. and Fatemi, E., Nonlinear total variation based noise removal algorithms, Phys. D Nonlinear Phenomena, 60(1-4) (1992), pp. 259–268.Google Scholar
[32] Schönlieb, C. and Bertozzi, A., Unconditionally stable schemes for higher order inpainting, Commun. Math. Sci., 9(2) (2011), pp. 413–457.Google Scholar
[33] Tai, X. C., Hahn, J. and Chung, G. J., A fast algorithm for Euler’s elastica model using augmented lagrangian method, SIAM J. Imaging Sci., 4(1) (2011), pp. 313–344.Google Scholar
[34] Tai, X. C. and Wu, C., Augmented Lagrangian method, dual methods and split Bregman iteration for ROF model, in SSVM’09: Proceedings of the Second International Conference on Scale Space and Variational Methods in Computer Vision, pages 502–513. Springer, 2009.CrossRefGoogle Scholar
[35] Unser, M., Aldroubi, A. and Eden, M., Enlargement or reduction of digital images with minimum loss of information, IEEE Trans. Image Processing, 4(3) (1995), pp. 247–258.CrossRefGoogle ScholarPubMed
[36] Wu, C. and Tai, X. C., Augmented Lagrangian method, dual methods, and split bregman iteration for rof, vectorial TV, and high order models, SIAM J. Imaging Sci., 3(3) (2010), pp. 300–339.Google Scholar
[37] Wu, C., Zhang, J., Duan, Y. and Tai, X. C., Augmented lagrangian method for total variation based image restoration and segmentation over triangulated surfaces, J. Sci. Computing, 50(1) (2012), pp. 145–166.Google Scholar
[38] Wu, C., Zhang, J. and Tai, X. C., Augmented Lagrangian method for total variation restoration with non-quadratic fidelity, Inverse Problems Imaging, 5(1) (2011), pp. 237–261.Google Scholar