公开(公告)号：US12223691B2

公开(公告)日：2025-02-11

申请号：US17798898

申请日：2021-09-22

Applicant: SHANGHAITECH UNIVERSITY

Inventor： Xinzhe Liu ,  Guangyao Yan ,  Yajun Ha

IPC: G06V10/762 ,  G06V10/764 ,  G06V10/96

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.

公开(公告)号：US11934459B2

公开(公告)日：2024-03-19

申请号：US17799278

申请日：2021-09-22

Applicant: SHANGHAITECH UNIVERSITY

Inventor： Guangyao Yan ,  Xinzhe Liu ,  Yajun Ha ,  Hui Wang

IPC: G06T7/162 ,  G06F16/901 ,  G06T7/13

CPC classification number: G06F16/9024 ,  G06T7/13 ,  G06T7/162 ,  G06T2207/20072

Abstract: A ripple push method for a graph cut includes: obtaining an excess flow ef(v) of a current node v; traversing four edges connecting the current node v in top, bottom, left and right directions, and determining whether each of the four edges is a pushable edge; calculating, according to different weight functions, a maximum push value of each of the four edges by efw=ef(v)*W, where W denotes a weight function; and traversing the four edges, recording a pushable flow of each of the four edges, and pushing out a calculated flow. The ripple push method explores different push weight functions, and significantly improves the actual parallelism of the push-relabel algorithm.