Skip to main content
SpringerLink
Log in

Globally Optimal Geodesic Active Contours

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

Abstract

An approach to optimal object segmentation in the geodesic active contour framework is presented with application to automated image segmentation. The new segmentation scheme seeks the geodesic active contour of globally minimal energy under the sole restriction that it contains a specified internal point pint. This internal point selects the object of interest and may be used as the only input parameter to yield a highly automated segmentation scheme. The image to be segmented is represented as a Riemannian space S with an associated metric induced by the image. The metric is an isotropic and decreasing function of the local image gradient at each point in the image, encoding the local homogeneity of image features. Optimal segmentations are then the closed geodesics which partition the object from the background with minimal similarity across the partitioning. An efficient algorithm is presented for the computation of globally optimal segmentations and applied to cell microscopy, x-ray, magnetic resonance and cDNA microarray images.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. D. Adalsteinsson and J.A. Sethian, “A fast level set method for propagating interfaces,” Journal of Computational Physics, Vol. 118, No. 2, pp. 269–277, 1995.

    Google Scholar 

  2. C.C. Adams, The Knot Book, W. H. Freeman and Company, 1994.

  3. R. Adams and L. Bischof, “Seeded region growing,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 16, pp. 641–647, 1994.

    Google Scholar 

  4. B. Appleton and H. Talbot, “Globally optimal surfaces by continuous maximal flows,” in C. Sun, H. Talbot, S. Ourselin, and T. Adriaansen (Ed.), Digital Image Computing: Techniques and Applications, Proc. VIIth APRS conference, Vol. 2, pp. 987–996. CSIRO publishing: Sydney, 2003.

  5. B. Appleton and C. Sun, “Circular shortest paths by branch and bound,” Pattern Recognition, Vol. 36, No. 11, pp. 2513–2520, 2003.

    Google Scholar 

  6. P. Bamford, Performance evaluation in image segmentation.http://www.cssip.uq.edu.au/staff/bamford/SegmentationEvaluation/index.htm.

  7. P. Bamford and B. Lovell, “Unsupervised cell nucleus segmentation with active contours,” Signal Processing (Special Issue: Deformable Models and Techniques for Image and Signal Processing), Vol. 71, No. 2, pp. 203–213, 1998.

    Google Scholar 

  8. M. Buckley, “Spot image analysis software,” http://experimental.act.cmis.csiro.au/Spot/index.php.

  9. V. Caselles, F. Catte, T. Coll, and F. Dibos, “A geometric model for active contours in image processing,” Numerische Mathematik, Vol. 66, pp. 1–31, 1992.

    Google Scholar 

  10. V. Caselles, R. Kimmel, and G. Sapiro, “Geodesic active contours,” IJCV, Vol. 22, No. 1, pp. 61–79, 1997.

    Google Scholar 

  11. V. Caselles, R. Kimmel, G. Sapiro, and C. Sbert, “Minimal surfaces based object segmentation,” IEEE Trans. on PAMI, Vol. 1, No. 9, pp. 394–398, 1997.

    Google Scholar 

  12. T. Chan and L. Vese, “An active contour model without edges,” in Scale-Space Theories in Computer Vision, 1999, pp. 141– 151.

  13. Y. Chen, T. Huang, and Y. Rui, “Optimal radial contour tracking by dynamic programming,” in Proc. of IEEE ICIP, Thessaloniki, Greece, October 2001.

    Google Scholar 

  14. L.D. Cohen, “On active contour models and balloons,” Computer Vision, Graphics, and Image Processing. Image Understanding, Vol. 53, No. 2, pp. 211–218, 1991.

    Google Scholar 

  15. L.D. Cohen and I. Cohen, “Finite-element methods for active contour models and balloons for 2-D and 3-D images,” IEEE Transaction on Pattern Analysis and Machine Intelligence, Vol. 15, pp. 1131–1147, 1993.

    Google Scholar 

  16. L.D. Cohen, “Multiple contour finding and perceptual grouping using minimal paths,” Journal of Mathematical Imaging and Vision, Vol. 14, No. 3, pp. 225–236, 2001.

    Google Scholar 

  17. L.D. Cohen and Ron Kimmel, “Global minimum for active contour models: A minimal path approach,” International Journal of Computer Vision, Vol. 24 No. 1, pp. 57–78, 1997.

    Google Scholar 

  18. J. Denzler and H. Niemann, “Active rays: Polar-transformed active contours for real–time contour tracking,” Journal on Real-Time Imaging, Vol. 5, No. 3, pp. 202–213, 1999.

    Google Scholar 

  19. E. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, Vol. 1, pp. 269–271, 1959.

    Google Scholar 

  20. R. Goldenberg, R. Kimmel, E. Rivlin, and M. Rudzsky, “Fast geodesic active contours,” IEEE Trans. On Image Processing, Vol. 10, No. 10, pp. 1467–1475, 2001.

    Google Scholar 

  21. M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: Active contour models,” International Journal of Computer Vision, Vol. 1, No. 4, pp. 321–331, 1998.

    Google Scholar 

  22. R. Kimmel, “Numerical geometry of images: Theory, algorithms and applications,” Technion, Israel Institute of Technology, Haifa 32000, Oct. 2000.

  23. R. Kimmel and A.M. Bruckstein, “Regularized laplacian zero crossings as optimal edge integrators,” International Journal of Computer Vision, Vol. 53, No. 3, pp. 225–243, 2003.

    Google Scholar 

  24. E. Kreyszig, Advanced Engineering Mathematics, 7th edn., W. Anderson, 1993.

  25. R. Malladi, J.A. Sethian, and B.C. Vemuri, “Shape modeling with front propagation: A level set approach,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 17, No. 2, pp. 158–175, 1995.

    Google Scholar 

  26. S. Osher and J.A Sethian, “Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations,” Journal of Computational Physics, Vol. 79, pp. 12–49, 1988.

    Google Scholar 

  27. J. Sethian, “A fast marching level set method for monotonically advancing fronts,” Proceedings of the National Academy of Sciences, Vol.93, No. 4, pp. 1591–1595, 1996.

    Google Scholar 

  28. J.A. Sethian, Level Set Methods and Fast Marching Methods–-Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science, Cambridge University Press, 1999.

  29. C. Sun and S. Pallottino, “Circular shortest path on regular grids,” in Asian Conference on Computer Vision, Melbourne, Australia, 2002, pp. 852–857.

  30. C. Sun and S. Pallottino, “Circular shortest path in images,” Pattern Recognition, Vol. 36, No. 3, pp. 709–719, 2003.

    Google Scholar 

  31. J. Weickert, B.M. ter Haar Romeny, and M.A. Viergever, “Efficient and reliable schemes for nonlinear diffusion filtering,” IEEE Transactions on Image Processing, Vol. 7, No. 3, pp. 398–410, 1998.

    Google Scholar 

  32. C. Xu and J.L. Prince, “Gradient vector flow: A new external force for snakes,” in Proc. IEEE Conf. on Comp. Vis. Pat. Rec. (CVPR), Comp. Soc. Press: Los Alamitos, 1997, pp. 66– 71.

    Google Scholar 

  33. C. Xu and J.L. Prince, “Snakes, shapes and gradient vector flow,”IEEE Transaction on Image Processing, Vol. 7, No. 3, pp. 359–369, 1998.

    Google Scholar 

  34. W. Zhang and R. Korf, “An average-case analysis of branch-and-bound with applications: Summary of results,” in Proc. 10th National Conf. on Artificial Intelligence, AAAI-92, San Jose, CA, 1992, pp. 545–550.

Download references

Author information

Authors and Affiliations

  1. Intelligent Real-Time Imaging and Sensing Group, ITEE, The University of Queensland, Brisbane, QLD, 4072, Australia

    Ben Appleton

  2. CSIRO Mathematical and Information Sciences, Locked Bag 17, North Ryde, NSW, 1670, Australia

    Hugues Talbot

Authors
  1. Ben Appleton
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hugues Talbot
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ben Appleton.

Additional information

Ben Appleton received degrees in engineering and in science from the University of Queensland in 2001 and was awarded a university medal. In 2002 he began a Ph.D at the University of Queensland in the field of image analysis. He is supported by an Australian Postgraduate Award and the Commonwealth Scientific and Industrial Research Organisation (CSIRO), Mathematical and Information Sciences. He has been a teaching assistant in image analysis at the University of Queensland since 2001. He has also contributed 10 research papers to international journals and conferences and was recently awarded the prize for Best Student Paper at Digital Image Computing: Techniques and Applications. His research interests include image segmentation, stereo vision and algorithms.

Hugues Talbot received the engineering degree from École Centrale de Paris in 1989, the D.E.A. (Masters) from University Paris VI in 1990 and the Ph.D from École des Mines de Paris in 1993, under the guidance of Dominique Jeulin and Jean Serra. He has been affiliated with the Commonwealth Scientific and Industrial Research Organisation (CSIRO), Mathematical and Information Sciences since 1994. He has worked on numerous applied projects in relation with industry, he has contributed more than 30 research papers in international journals and conferences and he has co-edited two sets of international conference proceedings on image analysis. He now also teaches image processing at the University of Sydney, and his research interest include image segmentation, linear structure analysis, texture analysis and algorithms.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Appleton, B., Talbot, H. Globally Optimal Geodesic Active Contours. J Math Imaging Vis 23, 67–86 (2005). https://doi.org/10.1007/s10851-005-4968-1

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-005-4968-1

Keywords

Search

Navigation