173
Views
1
CrossRef citations to date
0
Altmetric
Original Articles

On an effective multigrid solver for solving a class of variational problems with application to image segmentation

, , &
Pages 2015-2035 | Received 01 Oct 2018, Accepted 25 Sep 2019, Published online: 10 Oct 2019

References

  • L. Adams and Z. Li, The immersed interface/multigrid methods for interface problems, SIAM J. Sci. Comput. 24(2) (2002), pp. 463–479.
  • U.M. Ascher, E. Haber, and H. Huang, On effective methods for implicit piecewise smooth surface recovery, SIAM J. Sci. Comput. 28(1) (2006), pp. 339–358.
  • N. Badshah and K Chen, Multigrid method for the Chan-Vese model in variational segmentation, Commun. Comput. Phys. 4(2) (2008), pp. 294–316.
  • N. Badshah and K. Chen, On two multigrid algorithms for modeling variational multiphase image segmentation, IEEE Trans. Image Process. 18(5) (2009), pp. 1097–1106.
  • N. Badshah and K. Chen, Image selective segmentation under geometrical constraints using an active contour approach, Commun. Comput. Phys. 7(4) (2010), pp. 759–778.
  • N. Badshah, K. Chen, H. Ali, and G. Murtaza, A coefficient of variation based image selective segmentation model using active contours, East Asian J. Appl. Math. 2 (2012), pp. 150–169.
  • R.E. Bank and D.J. Rose, Analysis of a multilevel iterative method for nonlinear finite element equations, Math. Comput. 39(160) (1982), pp. 453–465.
  • K.J. Brabazon, M.E. Hubbard, and P.K. Jimack, Nonlinear multigrid methods for second order differential operators with nonlinear diffusion coefficient, Comput. Math. Appl. 68(12, Part A) (2014), pp. 1619–1634.
  • D. Braess and W. Hackbusch, A new convergence proof for the multigrid method including the v-cycle, SIAM J. Numer. Anal. 20(5) (1983), pp. 967–975.
  • J.H. Bramble, J.E. Pasciak, J.P. Wang, and J. Xu, Convergence estimates for multigrid algorithms without regularity assumptions, Math. Comput. 57(195) (1991), pp. 23–45.
  • J.H. Bramble, J.E. Pasciak, J.P. Wang, and J. Xu, Convergence estimates for product iterative methods with applications to domain decomposition, Math. Comput.57(195) (1991), pp. 1–21.
  • A. Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comput. 31(138) (1977), pp. 333–390.
  • A. Brandt, Multi-level adaptive techniques for singular-perturbation problems. NASA-TM-80966, ICASE report 78-18, 1978.
  • A. Brandt, Rigorous quantitative analysis of multigrid, I. Constant coefficients two-level cycle with ℓ2-norm, SIAM J. Numer. Anal. 31(6) (1994), pp. 1695–1730.
  • X. Bresson, S. Esedoglu, P. Vandergheynst, J.-P. Thiran, and S. Osher, Fast global minimization of the active contour/snake model, J. Math. Imaging Vis.28(2) (2007), pp. 151–167.
  • W.L. Briggs, V. E. Henson, S.F. McCormick, A Multigrid Tutorial Vol. 72, SIAM, Philadelphia, USA, 2000.
  • C. Brito-Loeza and K. Chen, Multigrid algorithm for high order denoising, SIAM J. Imaging Sci. 3(3) (2010), pp. 363–389.
  • E.S. Brown, T.F. Chan, X. Bresson, A convex relaxation method for a class of vector-valued minimization problems with applications to mumford-shah segmentation. UcCLA Cam Rep., USA 10(43) (2010), pp. 1–34. ftp://ftp.math.ucla.edu/pub/camreport/cam10-43.pdf.
  • V. Caselles, R. Kimmel, and G. Sapiro, Geodesic active contours, Int. J. Comput. Vis. 22(1) (1997), pp. 61–79.
  • F. Catté, P.-L. Lions, J.-M. Morel, and T. Coll, Image selective smoothing and edge detection by nonlinear diffusion, SIAM J. Numer. Anal. 29(1) (1992), pp. 182–193.
  • T.F. Chan and K. Chen, On a nonlinear multigrid algorithm with primal relaxation for the image total variation minimisation, Numer. Algorithms 41(4) (2006), pp. 387–411.
  • T.F. Chan and L.A. Vese, Active contours without edges, IEEE Trans. Image Process. 10(2) (2001), pp. 266–277.
  • T.F. Chan, S. Esedoglu, and M. Nikolova, Algorithms for finding global minimizers of image segmentation and denoising models, SIAM J. Appl. Math. 66(5) (2006), pp. 1632–1648.
  • K. Chen, Matrix Preconditioning Techniques and Applications, Cambridge University Press, Cambridge, UK, 2005.
  • D. Cremers, F.R. Schmidt, F. Barthel, Shape priors in variational image segmentation: Convexity, Lipschitz continuity and globally optimal solutions. IEEE conference on Computer Vision and Pattern Recognition. CVPR 2008, IEEE, Anchorage, Alaska, USA, 2008, pp. 1–6.
  • P. D'Ambra and G. Tartaglione, Solution of ambrosio-tortorelli model for image segmentation by generalized relaxation method, Commun. Nonlinear Sci. Numer. Simul. 20 (2014), pp. 819–831.
  • C.K. Filelis-Papadopoulos and G.A. Gravvanis, On the multigrid method based on finite difference approximate inverses, Comput. Model Eng. Sci. 90 (2013), pp. 233–253.
  • C. Frohn-Schauf, S. Henn, and K. Witsch, Nonlinear multigrid methods for total variation image denoising, Comput. Vis. Sci. 7(3–4) (2004), pp. 199–206.
  • B. Goldluecke, D. Cremers, Convex relaxation for multilabel problems with product label spaces. European Conference on Computer Vision, Springer, Crete, Greece, 2010, pp. 225–238.
  • T. Goldstein and S. Osher, The split bregman method for l1-regularized problems, SIAM J. Imaging Sci. 2(2) (2009), pp. 323–343.
  • D.G. Gordeziani and G.V. Meladze, Simulation of the third boundary value problem for multidimensional parabolic equations in an arbitrary domain by one-dimensional equations, USSR Comput. Math. Math. Phys. 14 (1974), pp. 249–253.
  • C. Gout, C. Le Guyader, and L. Vese, Image segmentation under interpolation conditions. Preprint CAM-IPAM, 2003, p. 44.
  • G.A. Gravvanis and C.K. Filelis-Papadopoulos, On the multigrid cycle strategy with approximate inverse smoothing, Eng. Comput. 31 (2014), pp. 110–122.
  • W. Hackbusch, Multi-grid Methods and Applications, Springer Science & Business Media, Berlin Heidelberg, Germany, 2013.
  • W. Hackbusch and A. Reusken, Analysis of a damped nonlinear multilevel method, Numer. Math.55(2) (1989), pp. 225–246.
  • W. Hackbusch, A. Reusken, On global multigrid convergence for nonlinear problems. in Robust Multi-grid Methods, Proceedings of 4th GAMM-Seminar, Kiel 1988, W. Hackbusch, ed., Springer Vieweg Teubner Verlag, 1989, pp. 105–113.
  • V.E. Henson, Multigrid methods nonlinear problems: An overview, Comput. Imaging 5016 (2003), pp. 36–48.
  • P. Jaccard, The distribution of the flora in the alpine zone. 1, New Phytologist 11(2) (1912), pp. 37–50.
  • A.K. Jumaat and K. Chen, An optimization-based multilevel algorithm for variational image segmentation models, Electron. Trans. Numer. Anal. 46 (2017), pp. 474–504.
  • T. Kim, J.E. Pasciak, and P.S. Vassilevski, Mesh-independent convergence of the modified inexact newton method for a second order non-linear problem, Numer. Linear Algebra Appl. 13(1) (2006), pp. 23–47.
  • M. Klodt, F. Steinbrücker, D. Cremers, Moment constraints in convex optimization for segmentation and tracking. Adv. Topics Comput. Vis., Advances in Computer Vision and Pattern Recognition (2013), pp. 1–29.
  • C. Le Guyader and C. Gout, Geodesic active contour under geometrical conditions: Theory and 3D applications, Numer. Algorithms 48(1–3) (2008), pp. 105–133.
  • R.J. Leveque and Z. Li, The immersed interface method for elliptic equations with discontinuous coefficients and singular sources, SIAM J. Numer. Anal. 31(4) (1994), pp. 1019–1044.
  • C. Liu, M.K.-P. Ng, T. Zeng, Weighted variational model for selective image segmentation with application to medical images. Pattern Recognit. 76 (2018), pp. 367–379.
  • T. Lu, P. Neittaanmäki, and X-C. Tai, A parallel splitting up method and its application to navier-stokes equations, Appl. Math. Lett. 4(2) (1991), pp. 25–29.
  • S.P. MacLachlan and C.W. Oosterlee, Local fourier analysis for multigrid with overlapping smoothers applied to systems of pdes, Numer. Linear Algebra Appl. 18(4) (2011), pp. 751–774.
  • A. Napov and Y. Notay, Smoothing factor, order of prolongation and actual multigrid convergence, Numer. Math. 118(3) (2011), pp. 457–483.
  • T.N.A. Nguyen, J. Cai, J. Zhang, and J. Zheng, Robust interactive image segmentation using convex active contours, IEEE Trans. Image Process 21(8) (2012), pp. 3734–43.
  • P. Ochs, T. Brox, Object segmentation in video: A hierarchical variational approach for turning point trajectories into dense regions. International Conference on Computer Vision, Barcelona, 2011, pp. 1583–1590. doi:10.1109/ICCV.2011.6126418.
  • S. Osher and J. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys. 79(1) (1988), pp. 12–49.
  • P. Perona and J. Malik, Scale-space and edge detection using anisotropic diffusion, IEEE Trans. Pattern Anal. Mach. Intell. 12(7) (1990), pp. 629–639.
  • L. Rada and K. Chen, A new variational model with dual level set functions for selective segmentation, Commun. Comput. Phys. 12(1) (2012), pp. 261–283.
  • L. Rada and K. Chen, Improved selective segmentation model using one level-set, J. Algorithms Comput. Technol. 7(4) (2013), pp. 509–540.
  • A. Reusken, Convergence of the multigrid full approximation scheme for a class of elliptic mildly nonlinear boundary value problems, Numer. Math. 52(3) (1987), pp. 251–277.
  • A. Reusken, Convergence of the multilevel full approximation scheme including thev-cycle, Numer. Math. 53(6) (1988), pp. 663–686.
  • M. Roberts, Selective image segmentation models and fast multigrid methods. PhD thesis, University of Liverpool, 2019.
  • M. Roberts and J. Spencer, Chan-Vese reformulation for selective image segmentation, J. Math. Imaging Vis. (2019), To appear.
  • M. Roberts, K. Chen, K.L. Irion, Multigrid algorithm based on hybrid smoothers for variational and selective segmentation models. Int. J. Comput. Math. 96(8) (2019), pp. 1623–1647. doi:10.1080/00207160.2018.1494827.
  • M. Roberts, K. Chen, and K.L. Irion, A convex geodesic selective model for image segmentation, J. Math. Imaging Vis. 61(4) (2019), pp. 482–503.
  • V.V. Shaidurov, Multigrid Methods for Finite Elements, Springer Science & Business Media, Dordrecht, Netherlands, 2013.
  • J. Spencer and K. Chen, A convex and selective variational model for image segmentation, Commun. Math. Sci. 13(6) (2015), pp. 1453–1472.
  • C. Tai, X. Zhang, and Z. Shen, Wavelet frame based multiphase image segmentation, SIAM. J. Imaging Sci. 6(4) (2013), pp. 2521–2546.
  • U. Trottenberg, C.W. Oosterlee, A. Schüller, Multigrid, Academic Press, London, UK, 2001.
  • L.A. Vese and T.F. Chan, A multiphase level set framework for image segmentation using the MS model, Int. J. Comput. Vis. 50(3) (2002), pp. 271–293.
  • J. Weickert, B.M. Ter Haar Romeny, and M.A. Viergever, Efficient and reliable schemes for nonlinear diffusion filtering, IEEE Trans. Image Process. 7(3) (1998), pp. 398–410.
  • R. Wienands, W. Joppich, Practical Fourier Analysis for Multigrid Methods, CRC press, Boca Raton, Florida, USA, 2004.
  • D. Xie, New nonlinear multigrid analysis. NASA Conference Publication 3339, Proceedings of Copper Mountain Conference on Multigrid Methods, N. D. Melson, T. A. Manteuffel, S. F. McCormick and C. C. Douglas, eds., Copper Mountain, Colorado, USA, 1996, pp. 793–808. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.4442&rep=rep1&type=pdf.
  • J. Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34(4) (1992), pp. 581–613.
  • J. Zhang, K. Chen, and D.A. Gould, A fast algorithm for automatic segmentation and extraction of a single object by active surfaces, Int. J. Comput. Math.92(6) (2015), pp. 1251–1274.
  • W. Zhu, X.-C. Tai, and T.F. Chan, Image segmentation using euler's elastica as the regularization, J. Sci. Comput. 57 (2013), pp. 414–438.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.