Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

A variant of the level set method and applications to image segmentation


Authors: Johan Lie, Marius Lysaker and Xue-Cheng Tai
Journal: Math. Comp. 75 (2006), 1155-1174
MSC (2000): Primary 35G25, 65K10
DOI: https://doi.org/10.1090/S0025-5718-06-01835-7
Published electronically: February 22, 2006
MathSciNet review: 2219023
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we propose a variant of the level set formulation for identifying curves separating regions into different phases. In classical level set approaches, the sign of $ n$ level set functions are utilized to identify up to $ 2^n$ phases. The novelty in our approach is to introduce a piecewise constant level set function and use each constant value to represent a unique phase. If $ 2^n$ phases should be identified, the level set function must approach $ 2^n$ predetermined constants. We just need one level set function to represent $ 2^n$ unique phases, and this gains in storage capacity. Further, the reinitializing procedure requested in classical level set methods is superfluous using our approach. The minimization functional for our approach is locally convex and differentiable and thus avoids some of the problems with the nondifferentiability of the Delta and Heaviside functions. Numerical examples are given, and we also compare our method with related approaches.


References [Enhancements On Off] (What's this?)

  • 1. Martin Burger, A framework for the construction of level set methods for shape optimization and reconstruction, Interfaces Free Bound. 5 (2003), no. 3, 301–329. MR 1998617, https://doi.org/10.4171/IFB/81
  • 2. Martin Burger, Benjamin Hackl, and Wolfgang Ring, Incorporating topological derivatives into level set methods, J. Comput. Phys. 194 (2004), no. 1, 344–362. MR 2033389, https://doi.org/10.1016/j.jcp.2003.09.033
  • 3. T. CHAN AND L. A. VESE, Active contours without edges, IEEE Image Proc., 10 (2001), pp. 266-277.
  • 4. Tony F. Chan and Xue-Cheng Tai, Identification of discontinuous coefficients in elliptic problems using total variation regularization, SIAM J. Sci. Comput. 25 (2003), no. 3, 881–904. MR 2046116, https://doi.org/10.1137/S1064827599326020
  • 5. Tony F. Chan and Xue-Cheng Tai, Level set and total variation regularization for elliptic inverse problems with discontinuous coefficients, J. Comput. Phys. 193 (2004), no. 1, 40–66. MR 2022688, https://doi.org/10.1016/j.jcp.2003.08.003
  • 6. T. F. CHAN AND L. A. VESE, Image segmentation using level sets and the piecewise constant Mumford-Shah model, Tech. Rep. CAM00-14, UCLA Dep. Math.
  • 7. S. CHEN, B. MERRIMAN, M. KANG, R. E. CAFILSCH, C. RATSCH, L.-T. CHENG, M. GYURE, R. P. FEDKIW, AND S. OSHER, Level set method for thin film epitaxial growth, Tech. Rep. CAM00-03, UCLA Math. Dep., 2000.
  • 8. S. ESEDOGLU AND Y.-H. R. TSAI, Threshold dynamics for the piecewise constant Mumford-Shah functional, Tech. Rep. CAM04-63, UCLA Dep. Math, 2004.
  • 9. L. C. EVENS AND R. F. GARIEPY, Measure therory and fine properties of functions, 1992.
  • 10. F. GIBOU AND R. FEDKIW, A fast hybrid k-means level set algorithm for segmentation, tech. rep., Stanford, 2002
    (in review).
  • 11. E. HODNELAND, Segmentation of digital images, cand. scient thesis, Dep. Math., University of Bergen, 2003.
    Available online at http://www.mi.uib.no/ $ \tilde{\;}$tai/.
  • 12. M. KASS, A. WITKIN, AND D. TERZOPOULOS, Snakes, active contour models, Int. J. of Comp. Vision, 1 (1988), pp. 321-331.
  • 13. K. Kunisch and X.-C. Tai, Sequential and parallel splitting methods for bilinear control problems in Hilbert spaces, SIAM J. Numer. Anal. 34 (1997), no. 1, 91–118. MR 1445731, https://doi.org/10.1137/S0036142993255253
  • 14. J. LIE, M. LYSAKER, AND X.-C. TAI, A binary level set model and some applications to image processing, Tech. Rep. CAM04-31, UCLA Dep. Math., 2004.
  • 15. Barry Merriman, James K. Bence, and Stanley J. Osher, Motion of multiple functions: a level set approach, J. Comput. Phys. 112 (1994), no. 2, 334–363. MR 1277282, https://doi.org/10.1006/jcph.1994.1105
  • 16. Barry Merriman, Russel Caflisch, Stanley Osher, Christian Ratsch, Susan Chen, Myungjoo Kang, and Mark Gyure, Island dynamics and level set methods for continuum modeling of epitaxial growth, Applied and industrial mathematics, Venice–2, 1998, Kluwer Acad. Publ., Dordrecht, 2000, pp. 145–171. MR 1755326
  • 17. David Mumford and Jayant Shah, Optimal approximations by piecewise smooth functions and associated variational problems, Comm. Pure Appl. Math. 42 (1989), no. 5, 577–685. MR 997568, https://doi.org/10.1002/cpa.3160420503
  • 18. Stanley Osher and James A. Sethian, Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys. 79 (1988), no. 1, 12–49. MR 965860, https://doi.org/10.1016/0021-9991(88)90002-2
  • 19. C. SAMSON, L. BLANC-FRAUD, G. AUBERT, AND J. ZERUBIA, A level set model for image classification, IJCV, 40 (2000), pp. 187-197.
  • 20. -, A variational model for image classification and restoration, TPAMI, 22 (2000), pp. 460-472.
  • 21. C. J. SETCHELL, Applications of computer vision to road-traffic monitoring, Ph.D. thesis, Department of Computer Science, University of Bristol, 1997.
    Available online at http://www.cs.bris.ac.uk/Tools/Reports/Abstracts/1997-setchell.html.
  • 22. B. SONG AND T. CHAN, A fast algorithm for level set based optimization, Tech. Rep. CAM02-68, UCLA Dept. Math., 2002.
  • 23. SPM, http://afni.nimh.nih.gov/afni/.
  • 24. M. SUSSMAN, P. SMEREKA, AND S. OSHER, A level set approach for computing solutions to incompressible two phase flow, J. Comput. Phys, 114 (1994), pp. 146-159.
  • 25. L. A. VESE AND T. F. CHAN, A multiphase level set framework for image segmentation using the Mumford and Shah model, International Journal of Computer Vision, 50 (2002), pp. 271-293.
  • 26. Joachim Weickert and Gerald Kühne, Fast methods for implicit active contour models, Geometric level set methods in imaging, vision, and graphics, Springer, New York, 2003, pp. 43–57. MR 2070064, https://doi.org/10.1007/0-387-21810-6_3
  • 27. Hong-Kai Zhao, T. Chan, B. Merriman, and S. Osher, A variational level set approach to multiphase motion, J. Comput. Phys. 127 (1996), no. 1, 179–195. MR 1408069, https://doi.org/10.1006/jcph.1996.0167

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 35G25, 65K10

Retrieve articles in all journals with MSC (2000): 35G25, 65K10


Additional Information

Johan Lie
Affiliation: Department of Mathematics, University of Bergen, Bergen, Norway
Email: johanl@mi.uib.no

Marius Lysaker
Affiliation: Department of Mathematics, University of Bergen, Bergen, Norway
Address at time of publication: Simula Research Lab, Norway
Email: mariul@simula.no

Xue-Cheng Tai
Affiliation: Department of Mathematics, University of Bergen, Bergen, Norway
Email: tai@mi.uib.no

DOI: https://doi.org/10.1090/S0025-5718-06-01835-7
Keywords: Level set, energy minimization, partial differential equations, segmentation.
Received by editor(s): March 12, 2004
Received by editor(s) in revised form: December 9, 2004
Published electronically: February 22, 2006
Additional Notes: This work was supported by the Norwegian Research Council
Article copyright: © Copyright 2006 American Mathematical Society