# US 12,223,691 B2 · Max-flow/min-cut solution algorithm for early terminating push-relabel algorithm

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,223,691 B2
- Document ID: US12223691B2
- Status: Granted
- Kind: B2
- Application number: 17/798,898
- Filed: 2021-09-22
- Published: 2024-04-04
- Granted: 2025-02-11
- Earliest claimed: 2021-04-20
- Assignees: Shanghaitech University
- Applicants: Shanghaitech University
- Inventors: Xinzhe Liu; Guangyao Yan; Yajun Ha
- Web page: https://patentgrep.com/patent/US12223691B2

## CPC

- G06V 10/26: Segmentation of patterns in the image field; Cutting or merging of image elements to establish the pattern region, e.g. clustering-based techniques; Detection of occlusion
- G06V 10/7635: {based on graphs, e.g. graph cuts or spectral clustering}
- G06T 7/11: Region-based segmentation
- G06T 7/162: involving graph-based methods
- G06V 10/267: {by performing operations on regions, e.g. growing, shrinking or watersheds}
- G06V 10/764: using classification, e.g. of video objects
- G06V 10/96: Management of image or video recognition tasks
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A max-flow/min-cut solution algorithm for early terminating a push-relabel algorithm is provided. The max-flow/min-cut solution algorithm is used for an application that does not require an exact maximum flow, and includes: defining an early termination condition of the push-relabel algorithm by a separation condition and a stable condition; determining that the separation condition is satisfied if there is no source node s, s∈S, in the set T at any time in an operation process of the push-relabel algorithm; determining that the stable condition is satisfied if there is no active node in the set T; and terminating the push-relabel algorithm if both the separation condition and the stability condition are satisfied. The early termination technique is proposed to greatly reduce redundant computations and ensure that the algorithm terminates correctly in all cases.

## Claims

### Claim 1

A computer vision method, implemented by a processor, employing a max-flow/min-cut solution algorithm for early terminating a push-relabel algorithm, used for an application that does not require an exact maximum flow, comprising:
defining, by the processor, an early termination condition of the push-relabel algorithm by a separation condition and a stable condition;
mapping, by the processor, image pixels onto a plurality of nodes;
assuming, by the processor, that all nodes v of the plurality of nodes reachable to a sink node t of the plurality of nodes in a residual graph constitute a set T and other nodes of the plurality of nodes constitute a set S;
determining, by the processor, that the separation condition is satisfied when there is no source node s, s∈S, in the set T at any time in an operation process of the push-relabel algorithm;
determining, by the processor, that the stable condition is satisfied when there is no active node in the set T; and
terminating, by the processor, the push-relabel algorithm when the separation condition and the stability condition are satisfied to reduce computations implemented by the processor to perform the computer vision method on the image pixels;
wherein the separation condition is defined as an absence of an augmenting path from a source node to the sink node in the residual graph; and
the stable condition is defined as an absence of an augmenting path from any active node to the sink node in the residual graph.

### Claim 2 (depends on 1)

The according to claim 1, comprising: applying the max-flow/min-cut solution algorithm in an application, wherein the application requires only a maximum flow value, or a minimum cut rather than a complete maximum flow with all detail.