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

A method of segmenting an image comprising the steps of:

• representing an image by a grid with a plurality of nodes, terminals, and edges, wherein said nodes correspond to voxels in the image, said terminals include a source and a sink, and wherein said edges include n-links and t-links, wherein each n-link connects a pair of nodes, and said t-links connect a node to a terminal, and wherein each t-link and n-link has an associated cost;
• 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 said node height table, said flow excess table, said t-link capacity table, and said n-link capacity table in parallel for all nodes until said flow excess table is zero for all nodes, wherein said nodes are segmented into a sink set and a source set based on the values of the node height table,
• wherein each n-link is associated with a reverse n-link among the n-links, and wherein said parallel updating further comprises the steps of:
• determining for all nodes in parallel an n-link push and a t-link push based on the n-link capacity table, the t-link capacity table and the flow excess table;
• updating the t-link capacity table from the t-link push in parallel for all nodes;
• updating the n-link capacity table from the n-link push in parallel for all nodes, wherein the step of determining an n-link push and updating the n-link capacity table and flow excess table is repeated for every n-link pair comprising an n-link and its reverse;
• updating the flow excess table from the n-link push and t-link push in parallel for all nodes;
• and
• updating the node height table based on the updated t-link capacity table and updated n-link capacity table, for all nodes in parallel.

A system for partitioning a grid using a graphics processing unit, said grid comprising a plurality of nodes, terminals, and edges, said terminals include a source and a sink, and wherein said edges include n-links and t-links, wherein each n-link connects a pair of nodes, and said t-links connect a node to a terminal, and wherein each t-link and n-link has an associated cost, said system comprising:

• a node height table;
• a flow excess table;
• a t-link capacity table;
• an n-link capacity table;
• a plurality of initialization procedures for initializing said node height table, said flow excess table, said t-link capacity table, and said n-link capacity table;
• and
• a plurality of pulse processing procedures for updating said node height table, said flow excess table, said t-link capacity table, and said n-link capacity table, wherein said pulse processing procedures are executed until a stopping criteria is satisfied, and wherein said plurality of initialization and said pulse processing procedures are fragment programs executable in parallel for each node in the grid by said graphics processing unit,
• wherein said pulse processing procedures further comprises
• a plurality of fragment programs for calculating a t-link push table from said t-link capacity table and flow excess table based on said node height table;
• a plurality of fragment programs for updating said t-link capacity table and flow excess table from said t-link push table;
• a plurality of fragment programs for calculating an n-link push table from said n-link capacity table and flow excess table based on said node height table;
• a plurality of fragment programs for updating said n-link capacity table and flow excess table from said n-link push table;
• and
• a plurality of fragment programs for updating said node height table from said n-link capacity table and said t-link capacity table,
• wherein said fragment programs are executable in parallel for each node in the grid by said graphics processing unit.

A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for segmenting an image, said method comprising the steps of:

• representing an image by a grid with a plurality of nodes, terminals, and edges, wherein said nodes correspond to voxels in the image, said terminals include a source and a sink, and wherein said edges include n-links and t-links, wherein each n-link connects a pair of nodes, and said t-links connect a node to a terminal, and wherein each t-link and n-link has an associated cost;
• 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 said node height table, said flow excess table, said t-link capacity table, and said n-link capacity table in parallel for all nodes until said flow excess table is zero for all nodes, wherein said nodes are segmented into a sink set and a source set based on the values of the node height table,
• wherein each n-link is associated with a reverse n-link among the n-links, and wherein said parallel updating further comprises the steps of:
• determining for all nodes in parallel a t-link push based on the t-link capacity table and the flow excess table, and using the t-link push to update the t-link capacity table and flow excess table in parallel for all nodes;
• determining for all nodes in parallel an n-link push based on the n-link capacity table and the flow excess table, and using the n-link push to update the n-link capacity table and flow excess table in parallel for all nodes, wherein the step of determining an n-link push and updating the n-link capacity table and flow excess table is repeated for every n-link pair comprising an n-link and its reverse;
• and
• updating the node height table based on the undated t-link capacity table and updated n-link capacity table, for all nodes in parallel.

A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for segmenting an image, said method comprising the steps of:

• representing an image by a grid with a plurality of nodes, terminals, and edges, wherein said nodes correspond to voxels in the image, said terminals include a source and a sink, and wherein said edges include n-links and t-links, wherein each n-link connects a pair of nodes, and said t-links connect a node to a terminal, and wherein each t-link and n-link has an associated cost;
• 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 said node height table, said flow excess table, said t-link capacity table, and said n-link capacity table in parallel for all nodes until said flow excess table is zero for all nodes, wherein said nodes are segmented into a sink set and a source set based on the values of the node height table,
• wherein each n-link is associated with a reverse n-link among the n-links, and wherein said parallel updating further comprises the steps of:
• determining for all nodes in parallel an n-link push and a t-link push based on the n-link capacity table, the t-link capacity table and the flow excess table;
• updating the t-link capacity table from the t-link push in parallel for all nodes;
• updating the n-link capacity table from the n-link push in parallel for all nodes, wherein the step of determining an n-link push and updating the n-link capacity table and flow excess table is repeated for every n-link pair comprising an n-link and its reverse;
• updating the flow excess table from the n-link push and t-link push in parallel for all nodes;
• and
• updating the node height table based on the updated t-link capacity table and updated n-link capacity table, for all nodes in parallel.