| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Local or Global Minima: Flexible Dual-Front Active Contours
January 2007 (vol. 29 no. 1)
pp. 1-14
Most variational active contour models are designed to find local minima of data-dependent energy functionals with the hope that reasonable initial placement of the active contour will drive it toward a "desirable” local minimum as opposed to an undesirable configuration due to noise or complex image structure. As such, there has been much research into the design of complex region-based energy functionals that are less likely to yield undesirable local minima when compared to simpler edge-based energy functionals whose sensitivity to noise and texture is significantly worse. Unfortunately, most of these more "robust” region-based energy functionals are applicable to a much narrower class of imagery compared to typical edge-based energies due to stronger global assumptions about the underlying image data. Devising new implementation algorithms for active contours that attempt to capture more global minimizers of already proposed image-based energies would allow us to choose an energy that makes sense for a particular class of energy without concern over its sensitivity to local minima. Such implementations have been proposed for capturing global minima. However, sometimes the completely-global minimum is just as undesirable as a minimum that is too local. In this paper, we propose a novel, fast, and flexible dual front implementation of active contours, motivated by minimal path techniques and utilizing fast sweeping algorithms, which is easily manipulated to yield minima with variable "degrees” of localness and globalness. By simply adjusting the size of active regions, the ability to gracefully move from capturing minima that are more local (according to the initial placement of the active contour/surface) to minima that are more global allows this model to more easily obtain "desirable” minimizers (which often are neither the most local nor the most global). Experiments on various 2D and 3D images and comparisons with some active contour models and region-growing methods are also given to illustrate the properties of this model and its performance in a variety of segmentation applications.
[1] 1 X. Munoz et al., “Strategies for Image Segmentation Combining Region and Boundary Information,” Pattern Recognition Letters, vol. 24, no. 1, pp. 375-392, 2003.[2] M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: Active Contour Models,” Int'l J. Computer Vision, vol. 1, no. 4, pp. 321-332, 1988.[3] V. Caselles et al., “A Geometric Model for Active Contours in Image Processing,” Numerical Math., vol. 66, no. 1, pp. 1-31, 1993.[4] R. Malladi, J. Sethian, and B. Vemuri, “Shape Modeling with Front Propagation: A Level Set Approach,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 1, pp. 158-175, Jan. 1995.[5] S. Osher and J. Sethian, “Fronts Propagating with Curvature Dependent Speed: Algorithms Based on the Hamilton-Jacobi Formulation,” J. Computational Physics, vol. 79, no. 1, pp. 12-49, 1988.[6] V. Caselles, R. Kimmel, and G. Sapiro, “Geodesic Active Contours,” Int'l J. Computer Vision, vol. 22, no. 1, pp. 61-79, 1997.[7] A. Yezzi, S. Kichenassamy, A. Kumar, P. Olver, and A. Tannenbaum, “A Geometric Snake Model for Segmentation of Medical Imagery,” IEEE Trans. Medical Imaging, vol. 16, no. 2, pp.199-209, 1997.[8] H. Tek and B. Kimia, “Image Segmentation by Reaction Diffusion Bubbles,” Proc. Int'l Conf. Computer Vision, pp. 156-162, 1995.[9] L. Cohen and I. Cohen, “Finite-Element Methods for Active Contour Models and Balloons for 2D and 3D Images,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 15, no. 11, pp. 1131-1147, Nov. 1993.[10] L. Cohen and R. Kimmel, “Global Minimum for Active Contour Models: A Minimal Path Approach,” Proc. IEEE Int'l Conf. Computer Vision and Pattern Recognition, pp. 666-673, 1996.[11] L. Cohen and R. Kimmel, “Global Minimum for Active Contour Models: A Minimal Path Approach,” Int'l J. Computer Vision, vol. 24, no. 1, pp. 57-78, 1997.[12] L. Cohen, “Multiple Contour Finding and Perceptual Grouping Using Minimal Paths,” J. Math. Imaging and Vision, vol. 14, no. 3, pp. 225-236, 2001.[13] T. Deschamps and L. Cohen, “Fast Extraction of Minimal Paths in 3D Images and Applications to Virtual Endoscopy,” Medical Image Analysis, vol. 5, no. 4, pp. 281-299, 2001.[14] R. Ardon and L. Cohen, “Fast Constrained Surface Extraction by Minimal Paths,” Proc. Int'l Conf. Computer Vision-Workshop Variational, Geometric, and Level Set Methods, pp. 233-244, 2003.[15] S. Gunn and M. Nixon, “A Model Based Dual Active Contour,” Proc. British Machine Vision Conf., pp. 305-314, 1994.[16] S. Gunn and M. Nixon, “A Robust Snake Implementation: A Dual Active Contour,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 1, pp. 63-68, Jan. 1997.[17] G. Giraldi, L. Goncalves, and A. Oliveira, “Dual Topologically Adaptable Snakes,” Proc. Int'l Conf. Computer Vision, Pattern Recognition, and Image Processing, pp. 103-107, Feb. 2000.[18] G. Georgoulas, G. Nikolakopoulos, Y. Koutroulis, A. Tzes, and P. Groumpos, “An Intelligent Visual-Based System for Object Inspection and Welding, Relying on Active Contour Models-Algorithms,” Proc. Second Hellenic Conf. Artificial Intelligence, pp.399-410, Apr. 2002.[19] G. Aboutanos, J. Nikanne, N. Watkins, and B. Dawant, “Model Creation and Deformation for the Automatic Segmentation of the Brain in MR Images,” IEEE Trans. Biomedical Eng., vol. 46, no. 11, pp. 1346-1356, 1999.[20] C. Erdem, A. Tekalp, and B. Sankur, “Video Object Tracking with Feedback of Performance Measures,” IEEE Trans. Circuits and Systems for Video Technology, vol. 13, no. 4, pp. 310-324, 2003.[21] M. Dawood, X. Jiang, and K. Schafers, “Reliable Dual-Band Based Contour Detection: A Double Dynamic Programming Based Approach,” Lecture Notes in Computer Science, vol. 3212, pp. 544-551, 2004.[22] N. Xu, R. Bansal, and N. Ahuja, “Object Segmentation Using Graph Cuts Based Active Contours,” Proc. IEEE Int'l Conf. Computer Vision and Pattern Recognition, vol. 2, pp. 46-53, 2003.[23] A. Chakraborty, L. Staib, and J. Duncan, “Deformable Boundary Finding in Medical Images by Integrating Gradient and Region Information,” IEEE Trans. Medical Imaging, vol. 15, no. 6, pp. 859-870, 1996.[24] T. Chan and L. Vese, “Active Contours without Edges,” IEEE Trans. Image Processing, vol. 10, no. 2, pp. 266-277, 2001.[25] N. Paragios and R. Deriche, “Geodesic Active Regions: A New Framework to Deal with Frame Partition Problems in Computer Vision,” J. Visual Comm. and Image Presentation, vol. 13, no. 1, pp.249-268, 2002.[26] C. Samson et al., “A Level Set Method for Image Classification,” Proc. Int'l Conf. Scale-Space Theories in Computer Vision, pp. 306-317, 1999.[27] A. Yezzi, A. Tsai, and A. Willsky, “A Statistical Approach to Image Segmentation for Bimodal and Trimodal Imagery,” Proc. Int'l Conf. Computer Vision, vol. 2, pp. 1-5, 1999.[28] A. Tsai, A. Yezzi, and A. Willsky, “Curve Evolution Implementation of the Mumford-Shah Functional for Image Segmentation, Denoising, Interpolation, and Magnification,” IEEE Trans. Image Processing, vol. 10, no. 8, pp. 1169-1186, 2001.[29] A. Yezzi, A. Tsai, and A. Willsky, “A Fully Global Approach to Image Segmentation via Coupled Curve Evolution Equations,” J.Visual Comm. Image Representation, vol. 13, no. 1, pp. 195-216, 2002.[30] S. Jehan-Besson, M. Barlaud, and G. Aubert, “${\rm DREAM}^{2}$ s: Deformable Regions Driven by an Eulerian Accurate Minimization Method for Image and Video Segmentation,” Int'l J. Computer Vision, vol. 53, no. 1, pp. 45-70, 2003.[31] S. Zhu and A. Yuille, “Region Competition: Unifying Snakes, Region Growing, and Bayes/MDL for Multiband Image Segmentation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 9, pp. 884-900, Sept. 1996.[32] D. Adalsteinsson and J. Sethian, “A Fast Level Set Method for Propagating Interfaces,” J. Computational Physics, vol. 118, no. 2, pp. 269-277, 1995.[33] J. Helmsen, E. Puckett, P. Colella, and M. Dorr, “Two New Methods for Simulating Photolithography Development in 3D,” Proc. SPIE, vol. 2726, pp. 253-261, 1996.[34] J. Tsitsiklis, “Efficient Algorithms for Globally Optimal Trajectories,” IEEE Trans. Automatic Control, vol. 40, no. 9, pp. 1528-1538, 1995.[35] J. Sethian, “A Fast Marching Level Set Method for Monotonically Advancing Fronts,” Proc. Nat'l Academy of Science of USA, vol. 93, no. 4, pp. 1591-1595, 1996.[36] C. Bajaj, Z. Yu, and M. Auer, “Volumetric Feature Extraction and Visualization of Tomographic Molecular Imaging,” J. Structural Biology, vol. 144, no. 1-2, pp. 132-143, 2003.[37] M. Boué and P. Dupuis, “Markov Chain Approximations for Deterministic Control Problems with Affine Dynamics and Quadratic Cost in the Control,” SIAM J. Numerical Analysis, vol. 36, no. 3, pp. 667-695, 1999.[38] H. Zhao, “Fast Sweeping Method for Eikonal Equations,” Math. Computation, vol. 74, pp. 603-627, 2004.[39] E. Rouy and A. Tourin, “A Viscosity Solutions Approach to Shape-from-Shading,” SIAM J. Numerical Analysis, vol. 29, no. 3, pp. 867-884, 1992.[40] P. Dupuis and J. Oliensis, “An Optimal Control Formulation and Related Numerical Methods for a Problem in Shape Reconstruction,” Annals of Applied Probability, vol. 4, no. 2, pp. 287-346, 1994.[41] H. Li, A. Elmoataz, J. Fadili, and S. Ruan, “Dual Front Evolution Model and Its Application in Medical Imaging,” Proc. Int'l Conf. Medical Image Computing and Computer-Assisted Intervention, pp.103-110, Sept. 2004.[42] H. Li, A. Yezzi, and L. Cohen, “Fast 3D Brain Segmentation Using Dual-Front Active Contours with Optional User-Interaction,” Proc. Int'l Conf. Computer Vision Workshop-Computer Vision for Biomedical Image Applications, pp. 335-345, Oct.21 2005.[43] L. Yatziv, A. Bartesaghi, and G. Sapiro, “O(N) Implementation of the Fast Marching Algorithm,” J. Computational Physics, vol. 212, no. 2, pp. 393-399, 2006.[44] P. Danielsson, “Euclidean Distance Mapping,” Computer Graphics and Image Processing, vol. 14, pp. 227-248, 1980.[45] Y. Tsai, “Rapid and Accurate Computation of the Distance Function Using Grids,” J. Computational Physics, vol. 178, no. 1, pp. 175-195, 2002.[46] Y. Tsai, L. Cheng, S. Osher, and H. Zhao, “Fast Sweeping Algorithms for a Class of Hamilton-Jacobi Equations,” SIAM J. Numerical Analysis, vol. 41, no. 2, pp. 673-694, 2003.[47] C. Kao, S. Osher, and J. Qian, “Lax-Friedrichs Sweeping Scheme for Static Hamilton-Jacobi Equations,” J. Computational Physics, vol. 196, no. 1, pp. 367-391, 2004.[48] F. Gibou and R. Fedkiw, “A Fast Hybrid $k$ -Means Level Set Algorithm for Segmentation,” Proc. Fourth Ann. Hawaii Int'l Conf. Statistics and Math., pp. 281-291, Jan. 2005.[49] P. Perona and J. Malik, “Scale-Space and Edge Detection Using Anisotropic Diffusion,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12, no. 7, pp. 629-639, July 1990.[50] R. Malladi and J. Sethian, “A Unified Approach to Noise Removal, Image Enhancement, and Shape Recovery,” IEEE Trans. Image Processing, vol. 5, no. 11, pp. 1554-1568, 1996.[51] T. Deschamps, “Curve and Shape Extraction with Minimal Path and Level-Sets Techniques: Applications to 3D Medical Imaging,” PhD dissertation, Universite de Paris-Dauphine, Dec. 2001.[52] L. Vincent and P. Soille, “Watersheds in Digital Spaces: An Efficient Algorithm Based on Immersion Simulation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 6, pp. 583-598, June 1991.[53] E. Sifakis and G. Tziritas, “Moving Object Localization Using a Multi-Label Fast Marching Algorithm,” Signal Processing: Image Comm., vol. 16, no. 10, pp. 963-976, 2001.[54] D. Mumford and J. Shah, “Optimal Approximation by Piecewise Smooth Functions and Associated Variational Problems,” Comm. Pure Applied Math., vol. 42, pp. 577-685, 1989.[55] R. Ronfard, “Region-Based Strategies for Active Contour Models,” Int'l J. Computer Vision, vol. 3, no. 2, pp. 229-251, 1994.[56] C. Davatzikos and R. Bryan, “Using a Deformable Surface Model to Obtain a Shape Representation of the Cortex,” IEEE Trans. Medical Imaging, vol. 15, no. 6, pp. 785-795, 1996.[57] P. Teo, G. Sapiro, and B. Wandell, “Creating Connected Representations of Cortical Gray Matter for Functional MRI Visualization,” IEEE Trans. Medical Imaging, vol. 16, no. 6, pp.852-863, 1997.[58] D. MacDonald, D. Avis, and A. Evans, “Proximity Constraints in Deformable Models for Cortical Surface Identification,” Proc. Int'l Conf. Medical Image Computing and Computer-Assisted Intervention, pp. 650-659, 1998.[59] C. Xu, D. Pham, J. Prince, M. Etemad, and D. Yu, “Reconstruction of the Central Layer of the Human Cerebral Cortex from MR Images,” Proc. Int'l Conf. Medical Image Computing and Computer-Assisted Intervention, pp. 481-488, 1998.[60] C. Xu and J. Prince, “Snakes, Shapes, and Gradient Vector Flow,” IEEE Trans. Image Processing, vol. 7, no. 3, pp. 359-369, 1998.[61] X. Zeng, L. Staib, R. Schultz, and J. Duncan, “Segmentation and Measurement of the Cortex from 3D MR Images Using Coupled Surfaces Propagation,” IEEE Trans. Medical Imaging, vol. 18, no. 10, pp. 100-111, 1999.[62] R. Goldenberg, R. Kimmel, E. Rivlin, and M. Rudzsky, “Cortex Segmentation: A Fast Variational Geometric Approach,” IEEE Trans. Medical Imaging, vol. 21, no. 2, pp. 1544-1551, 2002.[63] R. Goldenberg, R. Kimmel, E. Rivlin, and M. Rudzsky, “Fast Geodesic Active Contours,” IEEE Trans. Image Processing, vol. 10, no. 10, pp. 1467-1475, 2001.[64] C. Cocosco, V. Kollokian, R. Kwan, and A. Evans, “Brainweb: Online Interface to a 3D MRI Simulated Brain Database,” NeuroImage, vol. 5, no. 4,part 2/4, S425, http://www.bic.mni.mcgill.cabrainweb/, 1997.
Index Terms:
Active contours, curve evolution, dual front evolution, morphological dilation, local minima, global minima, minimal path technique, level set methods, fast sweeping methods, image segmentation.
Citation:
Hua Li, Anthony Yezzi, "Local or Global Minima: Flexible Dual-Front Active Contours," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 1, pp. 1-14, Jan. 2007, doi:10.1109/TPAMI.2007.16
