Patent ID: 11934459
Assignee: SHANGHAITECH UNIVERSITY
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 0:
1. A ripple push method for a graph cut implemented in an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), or a graphic processing unit (GPU), the method, comprising the following steps:
step 1: obtaining, by the ASIC, FPGA, or GPU, an excess flow ef(v) of a current node v;
step 2: traversing, by the ASIC, FPGA, or GPU, four edges connecting the current node v in four directions of top, bottom, left and right; determining whether each of the four edges is a pushable edge; if a current edge ev,u connecting the current node v to a neighboring node u is a pushable edge, recording a capacity value c(ev,u) of the current edge ev,u; otherwise, recording the capacity value of the current edge ev,u as 0;
step 3: calculating, by the ASIC, FPGA, or GPU, according to different weight functions, a maximum push value of each of the four edges by efw=ef(v)*W, wherein W denotes a weight function;
step 4: traversing, by the ASIC, FPGA, or GPU, the four edges described in step 2; recording a pushable flow of each of the four edges, and pushing out a calculated flow; simultaneously updating the capacity value of the current edge, the excess flow of the current node v, an excess flow of the neighboring node connected to the current node v through the current edge and a received flow of the neighboring node; and updating an edge connecting the neighboring node to the current node v; and
for the current edge ev,u connecting the current node v to the neighboring node u:
expressing the pushable flow of the current edge ev,u as f(ev,u)=min (efw,c(ev,u)); pushing the calculated flow out; simultaneously updating the capacity value c(ev,u)=c(ev,u)−f(ev,u) of the current edge ev,u, the excess flow ef(v)=ef(v)−f(ev,u) of the current node v, the excess flow ef(u)=ef(u)+f(ev,u) of the neighboring node u and the received flow f(ev,u) of the neighboring node u; and updating the capacity value of the edge eu,v connecting the neighboring node u to the current node v to c(eu,v)=c(eu,v)+f(ev,u); and
step 5: determining, by the ASIC, FPGA, or GPU, whether a current weight function W is a constant 1; if yes, ending the operation; otherwise returning to step 3; and repeating n times, setting the weight function W to 1, and returning to step 3.