| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Globally Optimal Regions and Boundaries as Minimum Ratio Weight Cycles
October 2001 (vol. 23 no. 10)
pp. 1075-1088
—We describe a new form of energy functional for the modeling and identification of regions in images. The energy is defined on the space of boundaries in the image domain and can incorporate very general combinations of modeling information both from the boundary (intensity gradients, etc.) and from the interior of the region (texture, homogeneity, etc.). We describe two polynomial-time digraph algorithms for finding the global minima of this energy. One of the algorithms is completely general, minimizing the functional for any choice of modeling information. It runs in a few seconds on a 256x256 image. The other algorithm applies to a subclass of functionals, but has the advantage of being extremely parallelizable. Neither algorithm requires initialization.
[1] 1075 K. Ahuja, T.L. Magnati, and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.[2] A. Amini, S. Tehrani, and T. Weymouth, “Using Dynamical Programming for Minimizing the Energy of Active Contours in the Presence of Hard Constraints,” Proc. Int'l Conf. Computer Vision, pp. 95-99, 1988.[3] A. Blake and A. Zisserman, Visual Reconstruction. MIT Press, 1987.[4] I.J. Cox, S.B. Rao, and Y. Zhong, “Ratio Regions: A Technique for Image Segmentation,” Proc. Int'l Conf. Pattern Recognition, vol. 2, pp. 557-564, 1996.[5] G.B. Dantzig, W.O. Blatner, and M.R. Rao, “Finding a Cycle in a Graph with Minimum Cost to Time Ratio with Application to a Ship Routing Problem,” Proc. Int'l Symp. Theory of Graphs, pp. 77-84, 1966.[6] J. Elder and S.W. Zucker, “The Effect of Contour Closure on the Rapid Discrimination of Two-Dimensional Shapes,” Vision Resolution, vol. 33, pp. 981-991, 1993.[7] J. Elder and S.W. Zucker, “A Measure of Closure,” Vision Resolution, vol. 34, no. 24, pp. 3361-3369, 1994.[8] J. Elder and S. Zucker, “Computing Contour Closure,” Proc. European Conf. Computer Vision, pp. 399-412, 1996.[9] D. Geiger, A. Gupta, L.A. Costa, and J. Vlontzos, Dynamical Programming for Detecting, Tracking and Matching Deformable Contours IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 3, pp. 294-302, Mar. 1995.[10] G. Guy and G. Medioni, “Inferring Global Perceptual Contours from Local Features,” Proc. Int'l J. Computer Vision, vol. 20, no. 1-2, 1996.[11] H. Ishikawa and I.H. Jermyn, “Region Extraction from Multiple Images,” Proc. Eighth IEEE Int'l Conf. Computer Vision, 2001.[12] I. Jermyn and H. Ishikawa, “Globally Optimal Regions and Boundaries as Minimum Ratio Cycles,” IEEE Trans. Pattern Analysis and Machine Intelligence, 2001.[13] G. Kaniza, “Contours without Gradients or Cognitive Contours,” Italian J. Psychology, vol. 1, pp. 93-112, 1971.[14] G. Kaniza, Organization in Vision: Essays on Gestalt Perception. New York: Praeger, 1979.[15] R. Karp, “A Characterization of the Minimum Cycle Mean in a Digraph,” Discrete Math., vol. 23, pp. 309-311, 1978.[16] M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: Active Contour Models,” Proc. Int'l J. Computer Vision, vol. 1, no. 4, pp. 321-331, 1988.[17] P. Klein, S. Rao, M. Rauch, and S. Subramanian, “Faster Shortest-Path Algorithms for Planar Graphs,” J. Computer and System Science, vol. 55, no. 1, pp. 3-23, 1997.[18] I. Kovács and B. Julesz, “A Closed Curve Is Much More than an Incomplete One: Effect of Closure in Figure-Ground Segmentation,” Proc. Nat'l Academy Science, vol. 90, pp. 7495-7497, 1993.[19] E.L. Lawler, “Optimal Cycles in Doubly Weighted Linear Graphs,” Proc. Int'l Symp. Theory of Graphs, pp. 209-213, 1966.[20] T. Leung and J. Malik, “Contour Continuity in Region Based Image Segmentation,” Proc. European Conf. Computer Vision, 1998.[21] S. Mahamud, K. Thornber, and L. Williams, “Segmentation of Salient Closed Contours From Real Images,” Proc. Int'l Conf. Computer Vision, 1999.[22] N. Meggido, “Combinatorial Optimization with Rational Objective Functions,” Math. Operations Research, vol. 4, pp. 414-424, 1979.[23] U. Montanari, “On the Optimal Detection of Curves in Noisy Pictures,” Comm. ACM, vol. 15, no. 5, pp. 335-345, 1971.[24] D. Mumford, “Elastica and Computer Vision,” Algebraic Geometry and Its Applications, C.L. Bajaj, ed., pp. 491-506, New York: Springer-Verlag, 1994.[25] P. Parent and S.W. Zucker, “Trace Inference, Curvature Consistency and Curve Detection,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, no. 8, pp. 823-839, 1989.[26] A.E. Seiffert and P. Cavanagh, “Position Displacement, not Velocity, Is the Cue to Motion Detection of Second-Order Patterns,” Vision Research, vol. 38, pp. 3569-3582, 1988.[27] A. Shashua and S. Ullman, “Structural Saliency: The Detection of Globally Salient Structures Using a Locally Connected Network,” Proc. Second Int'l Conf. Computer Vision, 1988.[28] J. Shi and J. Malik, Normalized Cuts and Image Segmentation IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888-905, Aug. 2000.[29] G. Sperling, “Three Stages and Two Systems of Visual Processing,” Spatial Vision, vol. 4, no. 2, pp. 183-207, 1989.[30] K.K. Thornber and L.R. Williams, “Analytic Solution of Stochastic Completion Fields,” Biological Cybernetics, vol. 75, pp. 141-151, 1996.[31] L.R. Williams and D.W. Jacobs, “Stochastic Completion Fields: A Neural Model of Illusory Contour Shape and Salience,” Neural Computation, vol. 9, pp. 837-858, 1997.[32] S.C. 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, pp. 884-900, 1996.
Citation:
I.H. Jermyn, H. Ishikawa, "Globally Optimal Regions and Boundaries as Minimum Ratio Weight Cycles," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, no. 10, pp. 1075-1088, Oct. 2001, doi:10.1109/34.954599
