Patent ID: 7444019

Claim:
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 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.