Method for segmenting an image using constrained graph partitioning of watershed adjacency graphs

A computer implemented method for segmenting at least a pair of regions of a digital image, said method performed by the computer comprising:

• obtaining data of the image;
• computing watersheds of the digital image using a rain simulation algorithm;
• performing a region growing procedure on the computed watersheds to produce a tessellation of the computed watersheds into smaller portions;
• transforming the smaller portions to an adjacency graph comprising a plurality of nodes and a plurality of node interconnecting edges, wherein each node corresponding to one of the smaller portions;
• assigning a weight to each node-interconnecting edge;
• identifying the nodes corresponding to at least a pair of smaller portions in the adjacency graph;
• marking each of a plurality of the identified nodes with one of at least a first and a second foreground labels prior to segmenting the adjacency graph;
• applying a competing wavefront process wherein each calculated competing wavefronts emanates from a first node to interconnected nodes at a rate related to the edge weights associated with the interconnected nodes and an unmarked node is marked according to the label of a marked node that is closest to the unmarked node.

A computer implemented method for segmenting at least a pair of regions of a digital image, said method performed by the computer comprising:

• obtaining data of the image;
• computing watersheds of the image from image data using a rain simulation algorithm;
• performing a region growing procedure on the plurality of watersheds to produce a tessellation of the plurality of watersheds into smaller portions;
• transforming the smaller portions to an adjacency graph comprising a plurality of nodes and a plurality of node-interconnecting edges, wherein each node corresponding to one of the smaller portions;
• assigning a weight to each node-interconnecting edge;
• identifying the nodes corresponding to at least a pair of smaller portions in the adjacency graph and marking each of a plurality of the identified nodes with one of at least a first and a second foreground labels prior to segmenting the adjacency graph;
• applying a segmentation process to the adjacency graph using the assigned weights and the identified nodes, wherein the segmentation process is a competing wavefronts process.