Image analysis – Image segmentation
Patent
1996-08-23
2000-06-20
Au, Ameolia
Image analysis
Image segmentation
382199, G06K 934
Patent
active
060786884
ABSTRACT:
Segmentation of an image into separate regions is useful in many computer vision problems. The separate regions may be represented by their enclosing contours. A planar graph is constructed for each image. The optimal contour is determined by the assignment of edge costs and face weights of the graph. An algorithm is provided such that given a planar graph G = (V,E) where V is a set of nodes, E is a set of edges and each edge e is provided with a non-negative cost c(e) and each face f of the planar graph is provided with a non-negative weight w(f), and given a single node v in G and single face F adjacent to v which is viewed as the exterior face, then find a directed path P in G that starts and finishes at v and minimizes ##EQU1## where cost(P) is defined as the length of the path under c, and weight (P) is the weight of the faces that are separated from F by P. The contour that minimizes .zeta. is the optimal contour.
REFERENCES:
patent: 4233662 (1980-11-01), LeMay
patent: 4843630 (1989-06-01), Catros et al.
patent: 4910786 (1990-03-01), Eichel
patent: 5054100 (1991-10-01), Tai
patent: 5260871 (1993-11-01), Goldberg
patent: 5274565 (1993-12-01), Reuben
patent: 5341142 (1994-08-01), Reis et al.
patent: 5532934 (1996-07-01), Rostoker
patent: 5544284 (1996-08-01), Allebach et al.
patent: 5634113 (1997-05-01), Rusterholz
Michael Kass, et al. "Snakes: Active Contour Models", International Journal Computer Vision, 321-331 (1988).
Laurent D. Cohen "Note On Active Contour Models and Balloons", CVGIP: Image Understanding, vol. 53 No. 2, Mar., pp.211-218 (1991).
Amini, et al. "Using Dynamic Programming for Minimizing the Energy of Active Contours in the Presence of Hard Constraints", IEEE (1988).
Ugo Montanari "On the Optimal Detection of Curves in Noisy Pictures", Communications of the ACM, May 1971, vol. 14, No. 5.
Geiger, et al. "Dynamic Programming for Detecting , Tracking, and Matching Deformable Contours", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, No. 3, Mar. 1995.
Chakraborty, et al. "Deformable Boundary Finding Influenced by Region Homogenity", IEEE (1994).
Remi Ronfard "Region-Based Strategies for Active Contour Models", International Journal of Computer Vision, 13:2, 229-251 (1994).
Yvan G. Leclerc "Constructing Simple Stable Descriptions for Image Partitioning" International Journal of Computer Vision, 3, 73-102 (1989).
Zhu, et al. "Region Competition: Unifying Snakes, Region Growing, Energy/Bayes/MDL for Multi-band Image Segmentation", Fifth Int. Conf. On Comp. Vision, IEEE (1995).
Wu, et al. "An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 15, No.11, Nov. 1993.
Satish B. Rao "Faster Algorithms for Finding Small Edge Cuts in Planar Graphs", Proc. of the 24.sup.th Annual ACM Symposium on Theory of Computing, pp 29-240 (May 1992).
Rao, Faster Algorithms for Finding Small Edge Cuts in Planar Graphs, May 1992, pp. 229-240.
Geiger et al., Dymanic Programming for Detecting, Tracking , and Matching Deformable Contours, Mar. 1995, pp. 294-302.
Amini et al., Using Dynamic Programming for Minimizing the Energy of Active Contours in the Presence of Hard Constraints, 1988, pp. 95-199.
Kass et al., Snakes: Active Contour Models, 1988, pp. 321-331.
Wu et al., An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation, Nov. 1993, pp. 1101-1113.
Montanari, On the Optimal Detection of Curves in Noisy Pictures, May 1971, pp. 335-345.
Cox Ingemar J.
Rao Satish B.
Au Ameolia
Feig Philip J.
Johnson Timothy M.
NEC Research Institute Inc.
LandOfFree
Method for image segmentation by minimizing the ratio between th does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for image segmentation by minimizing the ratio between th, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for image segmentation by minimizing the ratio between th will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1860567