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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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.
C.C. Adams, The Knot Book, W. H. Freeman and Company, 1994.
R. Adams and L. Bischof, “Seeded region growing,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 16, pp. 641–647, 1994.
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.
B. Appleton and C. Sun, “Circular shortest paths by branch and bound,” Pattern Recognition, Vol. 36, No. 11, pp. 2513–2520, 2003.
P. Bamford, Performance evaluation in image segmentation.http://www.cssip.uq.edu.au/staff/bamford/SegmentationEvaluation/index.htm.
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.
M. Buckley, “Spot image analysis software,” http://experimental.act.cmis.csiro.au/Spot/index.php.
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.
V. Caselles, R. Kimmel, and G. Sapiro, “Geodesic active contours,” IJCV, Vol. 22, No. 1, pp. 61–79, 1997.
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.
T. Chan and L. Vese, “An active contour model without edges,” in Scale-Space Theories in Computer Vision, 1999, pp. 141– 151.
Y. Chen, T. Huang, and Y. Rui, “Optimal radial contour tracking by dynamic programming,” in Proc. of IEEE ICIP, Thessaloniki, Greece, October 2001.
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.
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.
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.
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.
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.
E. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, Vol. 1, pp. 269–271, 1959.
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.
M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: Active contour models,” International Journal of Computer Vision, Vol. 1, No. 4, pp. 321–331, 1998.
R. Kimmel, “Numerical geometry of images: Theory, algorithms and applications,” Technion, Israel Institute of Technology, Haifa 32000, Oct. 2000.
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.
E. Kreyszig, Advanced Engineering Mathematics, 7th edn., W. Anderson, 1993.
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.
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.
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.
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.
C. Sun and S. Pallottino, “Circular shortest path on regular grids,” in Asian Conference on Computer Vision, Melbourne, Australia, 2002, pp. 852–857.
C. Sun and S. Pallottino, “Circular shortest path in images,” Pattern Recognition, Vol. 36, No. 3, pp. 709–719, 2003.
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.
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.
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.
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.
Author information
Authors and Affiliations
Corresponding author
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
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
Issue Date:
DOI: https://doi.org/10.1007/s10851-005-4968-1