Siemens Medical Solutions USA, Inc.

Siemens Corporate Research, Inc.

The University of Western Ontario

Yuri Boykov

Marie-Pierre Jolly

Daphne Yu

Gareth Funka-Lea

Gianluca Paladini

Romain Moreau-Gobard

Charles Henri Florin

Andrew Delong

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.

Region based push-relabel algorithm for efficient computation of maximum flow

A method and related system for automatically and efficiently isolating the heart in Computer Tomography (CT) or Magnetic Resonance Imaging cardiac scans is disclosed. The method involves segmenting a heart within a set of volumetric data. In accordance with one aspect of the present invention, the set of volumetric data is processed to determine the minimum value of an energy function having a first term, a second term and a third term. The heart is segmented based on the processing of the set of volumetric data.

CT/MRI heart isolation using a graph cut algorithm

An image editing system comprises an input device for inputting an image, a graphical user interface for selecting background and object seeds for the image, and an image processor for editing the image. The image processor has various editing routines, including a segmentation routine that builds a graph associated with the image and uses a graph cut algorithm to cut the graph into segments. The user marks certain pixels as 'object' or 'background' to provide hard constraints for segmentation. Additional soft constraints incorporate both boundary and regional information. Graph cuts are used to find the globally optimal segementation of the image. The obtained solution gives the best balance of boundary and region properties satisfying the constraints.

Using graph cuts for editing photographs

A method of segmenting an image includes representing an image by a grid with a plurality of nodes, terminals, and edges, the terminals including a source and a sink. The edges include n-links and t-links, where each n-link connects a pair of nodes, and the t-links connect a node to a terminal, and each t-link and n-link has an associated cost. The method includes initializing a node height table, a flow excess table, a t-link capacity table, and an n-link capacity table based on the t-link and n-link costs, and updating the node height table, the flow excess table, the t-link capacity table, the said n-link capacity table in parallel for all nodes until the flow excess table is zero for all nodes. The method steps are performed in parallel for all nodes on a graphics processing unit.

System and method for GPU acceleration of push-relabel algorithm on grinds

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.

Growing community of inventors

London, Canada

Yuri Boykov