Patent ID: 7844113

Claim:
A method of computing maximum flow of a graph, used in image segmentation, the graph comprising a plurality of vertices and at least one source vertex and at least one target vertex, and a plurality of edges therebetween, each of the plurality of edges being constrained by a maximum amount of flow that can be transported thereover, the graph being further characterized by a flow comprising a plurality of preflow, the method comprising: dividing the graph into a plurality of regions, each of the plurality of regions including a subset of the plurality of vertices, including a regional source vertex and a regional target vertex, and an associated subset of the plurality of edges; identifying each region of the plurality of regions having at least a portion of the plurality of preflow and, for each identified region and for all of the portion of the plurality of preflow and for all of the subset of the plurality of vertices of the identified region, processing the identified region by: transporting the portion of the plurality of preflow between neighboring vertices of the subset of the plurality of vertices of the identified region via an edge of the subset of the plurality of edges of the identified region; determining a degree to which the edge is saturated and determining, based on the degree of saturation of the edge, a direction in which subsequent preflow should be transported between the neighboring vertices via the edge; and terminating the transporting and determining when all of the portion of the plurality of preflow of the identified region has reached the regional target vertex of the identified region, retreated to the regional source vertex of the identified region, or a combination thereof; and wherein the method further comprises: skipping each region of the plurality of regions which have none of the plurality of preflow; and computing, using one or more processors, the maximum flow once all of the plurality of regions have been identified or skipped.