IEEE Trans Image Process. 2016 Dec;25(12):5511-5525. doi: 10.1109/TIP.2016.2609819. Epub 2016 Sep 15.
Graph cuts are widely used in computer vision. 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 (the parallel BK-algorithm) does not have a polynomial bound on the number of iterations and is found to be non-convergent in some cases due to the possible multiple optimal solutions of its sub-problems. To remedy this non-convergence problem, in this paper, we first introduce a merging method capable of merging any number of those adjacent sub-graphs that can hardly reach agreement on their overlapping regions in the parallel BK-algorithm. Based on the pseudo-boolean representations of graph cuts, our merging method is shown to be effectively reused all the computed flows in these sub-graphs. Through both 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 paper 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.
图割在计算机视觉中被广泛应用。为了加速优化过程并提高大规模图的可扩展性，Strandmark 和 Kahl 提出了一种分割方法，将图分割成多个子图，以便在共享内存和分布式内存模型中进行并行计算。然而，这种并行算法（并行 BK 算法）在迭代次数上没有多项式界，并且由于其子问题的多个最优解，在某些情况下被发现是不收敛的。为了解决这个不收敛问题，在本文中，我们首先引入了一种合并方法，能够合并并行 BK 算法中难以就重叠区域达成一致的任意数量的相邻子图。基于图割的伪布尔表示，我们的合并方法被证明能够有效地重用这些子图中计算出的所有流。通过分割和合并，我们进一步提出了一种具有保证收敛性的动态并行和分布式图割算法，能够在预定义的迭代次数内达到全局最优解。本质上，本文提供了一个通用框架，允许采用更复杂的分割和合并策略来进一步提高性能。我们的动态并行算法通过广泛的实验结果得到了验证。
