Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the Application of the Spectral Projected Gradient Method in Image Segmentation

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

We investigate the application of the nonmonotone spectral projected gradient (SPG) method to a region-based variational model for image segmentation. We consider a “discretize-then-optimize” approach and solve the resulting nonlinear optimization problem by an alternating minimization procedure that exploits the SPG2 algorithm by Birgin et al. (SIAM J Optim 10(4):1196–1211, 2000). We provide a convergence analysis and perform numerical experiments on several images, showing the effectiveness of this procedure.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Aujol, J.F., Chambolle, A.: Dual norms and image decomposition models. Int. J. Comput. Vis. 63(1), 85–104 (2005)

    Article  MathSciNet  Google Scholar 

  2. Barzilai, J., Borwein, J.: Two-point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bertsekas, D.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999)

    MATH  Google Scholar 

  4. Birgin, E., Martínez, J., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10(4), 1196–1211 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  5. Birgin, E., Martínez, J., Raydan, M.: Algorithm 813: SPG—software for convex-constrained optimization. ACM Trans. Math. Softw. 27(3), 340–349 (2001)

    Article  MATH  Google Scholar 

  6. Birgin, E., Martínez, J., Raydan, M.: Spectral projected gradient methods: review and perspectives. J. Stat. Softw. 60(3) (2014)

  7. Bonettini, S.: Inexact block coordinate descent methods with application to non-negative matrix factorization. IMA J. Numer. Anal. 31(4), 1431–1452 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  8. Bonettini, S., Zanella, R., Zanni, L.: A scaled gradient projection method for constrained image deblurring. Inverse Probl. 25(1), 015002 (2009)

    Article  MathSciNet  Google Scholar 

  9. Bresson, X., Esedo\(\bar{\rm {g}}\)lu, S., Vandergheynst, P., Thiran, J.P., Osher, S.: Fast global minimization of the active contour/snake model. J. Math. Imaging Vis. 28(2), 151–167 (2007)

  10. Brown, E., Chan, T., Bresson, X.: Completely convex formulation of the Chan-Vese image segmentation model. Int. J. Comput. Vis. 98(1), 103–121 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  11. Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20(1–2), 89–97 (2004)

    MathSciNet  Google Scholar 

  12. Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120–145 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  13. Chan, T., Vese, L.: Active contours without edges. IEEE Trans. Image Process. 10(2), 266–277 (2001)

    Article  MATH  Google Scholar 

  14. Chan, T., Esedo\(\bar{\rm {g}}\)lu, S., Nikolova, M.: Algorithms for finding global minimizers of image segmentation and denoising models. SIAM J. Appl. Math. 66(5), 1632–1648 (2006)

  15. Chan, T., Sandberg, B., Moelich, M.: Some recent developments in variational image segmentation. In: Tai, X.C., Lie, K.A., Chan, T., Osher, F. (eds.) Image Processing Based on Partial Differential Equations, Mathematics and Visualization Series, pp. 175–201. Springer, Heidelberg (2005)

    Google Scholar 

  16. Dai, Y.H., Fletcher, R.: Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numerische Mathematik 100(1), 21–47 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  17. Dai, Y.H., Yuan, Y.: Analysis of monotone gradient methods. J. Ind Manag. Optim. 1(2), 181–192 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  18. De Asmundis, R., di Serafino, D., Riccio, F., Toraldo, G.: On spectral properties of steepest descent methods. IMA J. Numer. Anal. 33(4), 1416–1435 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  19. De Asmundis, R., di Serafino, D., Hager, W., Toraldo, G., Zhang, H.: An efficient gradient method using the Yuan steplength. Comput. Optim. Appl. 59(3), 541–563 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  20. Esser, E.: Applications of Lagrangian–based alternating direction methods and connections to split Bregman. CAM Technical Report 09-31, UCLA, Los Angeles. ftp://ftp.math.ucla.edu/pub/camreport/cam09-31.pdf (2009)

  21. Figueiredo, M., Nowak, R., Wright, S.: Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE J. Sel. Top. Signal Process. 1(4), 586–598 (2007)

    Article  Google Scholar 

  22. Fletcher, R.: A limited memory steepest descent method. Math. Program. Ser. A 135(1–2), 413–436 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  23. Goldstein, T., Osher, S.: The split Bregman method for l1-regularized problems. SIAM J. Imaging Sci. 2(2), 323–343 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  24. Goldstein, T., Bresson, X., Osher, S.: Geometric applications of the split Bregman method: segmentation and surface reconstruction. J. Sci. Comput. 45(1–3), 272–293 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  25. Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton’s method. SIAM J. Num. Anal. 23(4), 707–716 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  26. Jung, M., Kang, M., Kang, M.: Variational image segmentation models involving non-smooth data-fidelity terms. J. Sci. Comput. 59(2), 277–308 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  27. Mumford, D., Shah, J.: Optimal approximations by piecewise smooth functions and associated variational problems. Commun. Pure Appl. Math. 45(2), 577–685 (1989)

    Article  MathSciNet  Google Scholar 

  28. Papadakis, N., Yildizoǧlu, R., Aujol, J.F., Caselles, V.: High-dimension multilabel problems: convex or nonconvex relaxation? SIAM J. Imaging Sci. 6(4), 2603–2639 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  29. Setzer, S.: Operator splittings, Bregman methods and frame shrinkage in image processing. Int. J. Comput. Vis. 92(3), 265–280 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  30. Wang, Y., Yang, J., Yin, W., Zhang, Y.: A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imaging Sci. 1(3), 248–272 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  31. Yildizoǧlu, R., Aujol, J.F., Papadakis, N.: Active contours without level sets. In: ICIP 2012—IEEE International Conference on Image Processing (Orlando, FL, Sept. 30–Oct. 3, 2012), pp. 2549–2552. IEEE (2012)

  32. Yu, G., Qi, L., Dai, Y.H.: On nonmonotone Chambolle gradient projection algorithms for total variation image restoration. J. Math. Imaging Vis. 35(2), 143–154 (2005)

    Article  MathSciNet  Google Scholar 

  33. Zhu, M., Wright, S., Chan, T.: Duality-based algorithms for total-variation-regularized image restoration. Comput. Optim. Appl. 47(3), 377–400 (2010)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

We wish to thank Giovanni Pisante for useful discussions concerning variational models for image segmentation. We are also grateful to the anonymous referees for their useful comments, which helped us to improve the quality of this work. This work was partially supported by INdAM-GNCS (2014 Project First-order optimization methods for image restoration and analysis; 2015 Project Numerical Methods for Non-convex/Nonsmooth Optimization and Applications) and by MIUR (FIRB 2010 Project No. RBFR106S1Z002).

Author information

Authors and Affiliations

  1. Institute for High-Performance Computing and Networking (ICAR), CNR, via P. Castellino 111, 80131, Naples, Italy

    Laura Antonelli

  2. Department of Mathematics and Physics, Second University of Naples, viale A. Lincoln 5, 81100, Caserta, Italy

    Valentina De Simone & Daniela di Serafino

Authors
  1. Laura Antonelli
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Valentina De Simone
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Daniela di Serafino
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniela di Serafino.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Antonelli, L., De Simone, V. & di Serafino, D. On the Application of the Spectral Projected Gradient Method in Image Segmentation. J Math Imaging Vis 54, 106–116 (2016). https://doi.org/10.1007/s10851-015-0591-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-015-0591-y

Keywords

Mathematics Subject Classification

Search

Navigation