Image analysis – Image segmentation
Reexamination Certificate
2005-12-06
2005-12-06
Bali, Vikkram (Department: 2623)
Image analysis
Image segmentation
C382S225000
Reexamination Certificate
active
06973212
ABSTRACT:
Disclosed is a method of segmenting one or more objects from one or more backgrounds in an image, the method comprising defining a plurality of image nodes, each said image node corresponding to one or more pixels of said image, connecting pairs of adjacent nodes with n-links, each said n-link weighted with an n-link cost, defining a source node, defining a sink node, defining one or more object seeds, said object seeds corresponding to image nodes within said objects, defining one or more background seeds, said background seeds corresponding to image nodes within said backgrounds, connecting said source node with each said object seed with a plurality of t-links, connecting said sink node with each said background seed with a plurality of t-links, wherein each said t-links is weighted with a t-link cost, and calculating a segmentation cut having the smallest total cost of all cuts separating said source from said sink, wherein said total cost of each said cut is defined as the sum of the costs of all said n-links and t-links that each said cut severs.
REFERENCES:
patent: 4905148 (1990-02-01), Crawford
patent: 6744923 (2004-06-01), Zabih et al.
patent: 2003/0206652 (2003-11-01), Nister
Snow et al. “Exact voxel occupancy with graph cuts.” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, vol. 1, Jun. 2000, pp. 345-352.
Bonneville et al. “Graph cut: application to Bayesian emission tomography reconstruction.” Proceedings of the International Conference on Image Analysis and Processing, Sep. 1999, pp. 1184-1189.
Amir A. Amini, Terry E. Weymouth, and Ramesh C. Jain. Using dynamic programming for solving variational problems in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(9):855-867, Sep. 1990.
Y. Boykov, O. Veksler, and R. Zabih. Markov random fields with efficient approximations. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 648-655, 1998.
Laurent D. Cohen. On active contour models and balloons. Computer Vision, Graphics, and Image Processing: Image Understanding, 53(2) :211-218, 1991.
Laurent D. Cohen and Isaac Cohen. Finite element methods for active contour models and balloons for 2-d and 3-d images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(II):1131-1147, Nov. 1993.
Irigemar J. Cox, Satish B. Rao, and Yu Zhong. “ratio regions”: a technique for image segmentation. In International Conference on Pattern Recognition, vol. II, pp. 557-564. 1996.
Marie-Pierre Dubuisson-Jolly, Cheng-Chung Liang, and Alok Gupta. Optimal polyline tracking for artery motion compensation in coronary angiography. In International Conference on Computer Vision, pp. 414-419, 1998.
L. Ford and D. Fulkerson. Flows in Networks. Princeton University Press, 1962.
Davi Geiger, Alok Gupta, Luiz A. Costa, and John Viontzos. Dynamic programming for detecting, tracking, and matching deformable contours. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(3):294-402, Mar. 1995.
A. Goldberg and R. Tarjan. A new approach to the maximum flow problem. Journal of the Association for Computing Machinery, 35(4):921-940, Oct. 1988.
D. Greig, B. Porteo:-ancl A. Seheult. Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society, Series B, 51(2):271-279, 1989.
Robert M. Haralick and Linda G. Shapiro. Computer and Robot Vision. Addison-Wesley Publishing Company, 1992.
H. Islilkawa and D. Geiger. Segmentation by grouping junctions. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 125-131, 1998.
Ian H. Jermyn and Hiroshi Ishikawa. Globally optimal regions and boundaries. In International Conference on Computer Vision, vol. II, pp. 904-910, 1999.
M. Kass, A. Witkin, and D. Terzolpoulos. Snakes: Active contour models. International Journal of Computer Vision, 2:321-331, 1988.
E. N. Mortensen and W. A. Barrett. Interactive segmentation with intelligent scissors, Graphical Models and Image Processing, 60:349-384, 1998.
Thomas O'Donnell, Marie-Pierre Dubuisson-Jolly; and Alok Gupta. A cooperative framework for segmentation using 2d active contours and 3d hybrid models as applied to branch cylindrical structures. In International Conference on Computer Vision, pp. 454-459, 1998.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 731-737, 1997.
D. J. Williams and M. Shah. A fast algorithm for active contours and curvature estimation. Computer Vision, Graphics, and Image Processing: Image Understanding, 55(I):14-26, 1992.
Zhenyu Wu and Richard Leahy. An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligenece, 15(II):1101-1113, Nov. 1993.
Alan Yuille and P. Hallinan. Deformable templates. In Andrew Blake and Alan Yuille, editors, Active Vision, pp. 20-38. MIT Press, 1992.
Song Chun Zhu and Alan Yuille. Region competition: Unifying snakes, region growing, and Bayes/MDL for multiband image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(9) :884-900, Sep. 1996.
Y. Boykov and V. Kolomogorov,An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision, 3rdInternational Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), Springer-Verlag (Sep. 2001).
Y. Boykov & M-P. Jolly,Interactive graph cuts for optical boundary®ion segmentation of objects in n-D images, Proceedings of the Interational Conference on Computer Vision, Vancouver, Canada, vol. 1, pp. 105-112 (2001).
Boykov Yuri
Jolly Marie-Pierre
Bali Vikkram
F. Chau & Associates LLC
LaRose Colin
Paschburg Donald B.
Siemens Corporate Research Inc.
LandOfFree
Graph cuts for binary segmentation of n-dimensional images... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Graph cuts for binary segmentation of n-dimensional images..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph cuts for binary segmentation of n-dimensional images... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3468138