Image analysis – Image segmentation
Reexamination Certificate
2007-03-14
2010-11-30
Ge, Yuzhen (Department: 2624)
Image analysis
Image segmentation
Reexamination Certificate
active
07844113
ABSTRACT:
A region-based push-relabel formulation is disclosed that removes the requirement that the entire graph should fit into the computer memory and yields an implementation that can reduce the required size and redundancy of accesses to the data memory, thus improving speed performance, while allowing for an efficient parallel processing implementation. The algorithm assigns all vertices that are not part of the sources or sinks with a value of 1. Sinks are assigned with zeros and sources are assigned a label equal to the number of their vertices. The preflow is then pushed from the sources to their neighbors, if any. When the preflow has all reached the boundaries, an adjacent region of the neighboring set is selected and preflow is pushed within this region. When the values of the preflow have been exhausted, region relabeling is done to update the label values. This is repeated within the region until all preflow has exited to the boundary of this region. The operation is then repeated for the neighboring regions that now contain the preflow. Regions which have no preflow may be skipped, thereby realizing a savings in processing resources.
REFERENCES:
patent: 6973212 (2005-12-01), Boykov et al.
patent: 7444019 (2008-10-01), Boykov et al.
patent: 7536050 (2009-05-01), Boykov et al.
patent: 2006/0029275 (2006-02-01), Li et al.
TopCoder Algorithm Tutorials “Maximum Flow” article, obtained at http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow, part 1 of 2, 11 pages, Jan. 18, 2007.
TopCoder Algorithm Tutorials “Maximum Flow” article, obtained at http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2, part 2 of 2, 15 pages, Jan. 18, 2007.
Cherkassky and Goldberg “On Implementing Push-Relabel Method for the Maximum Flow Problem” publication, 18 pages, Sep. 1994.
Boykov Yuri
Delong Andrew
Yu Daphne
Ge Yuzhen
Paschburg Donald B.
Siemens Medical Solutions USA , Inc.
The University of Western Ontario
LandOfFree
Region based push-relabel algorithm for efficient... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Region based push-relabel algorithm for efficient..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Region based push-relabel algorithm for efficient... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4232511