The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Nov. 30, 2010
Filed:
Mar. 14, 2007
Andrew Delong, London, CA;
Yuri Boykov, London, CA;
Daphne Yu, Yardley, PA (US);
Siemens Medical Solutions USA, Inc., Malvern, PA (US);
The University of Western Ontario, London, Ontario, CA;
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.