  Graph-cuts are widely used in computer vision. In order to speed up the
optimization process and improve the scalability for large graphs, Strandmark
and Kahl introduced a splitting method to split a graph into multiple subgraphs
for parallel computation in both shared and distributed memory models. However,
this parallel algorithm (parallel BK-algorithm) does not have a polynomial
bound on the number of iterations and is found non-convergent in some cases due
to the possible multiple optimal solutions of its sub-problems.
  To remedy this non-convergence problem, in this work we first introduce a
merging method capable of merging any number of those adjacent sub-graphs which
could hardly reach an agreement on their overlapped region in the parallel BK
algorithm. Based on the pseudo-boolean representations of graph cuts,our
merging method is shown able to effectively reuse all the computed flows in
these sub-graphs. Through both the splitting and merging, we further propose a
dynamic parallel and distributed graph-cuts algorithm with guaranteed
convergence to the globally optimal solutions within a predefined number of
iterations. In essence, this work provides a general framework to allow more
sophisticated splitting and merging strategies to be employed to further boost
performance. Our dynamic parallel algorithm is validated with extensive
experimental results.
