宣誓书 .................................................................................................................... 2
图形切割广泛用于计算机视觉中。为了加快优化过程并提高了大图的可伸缩性,Strandmark和Kahl引入了一种分裂方法,将图形分为多个子图中,以在共享和分布式内存模型中进行并行计算。然而,该平行算法(平行BK-Algorithm)在迭代次数上没有多项式结合,在某些情况下,由于其子问题的多个最佳解决方案,因此在某些情况下被认为是无代数的。为了补救这个非交流问题,在本文中,我们首先引入了一种合并方法,能够合并任何相邻的子图纸,这些子图几乎无法达成对其在平行BK-Algorithm中重叠区域的一致性。基于图形切割的伪树状表示形式,我们的合并方法被证明是有效地重用这些子图中的所有计算流动。通过分裂和合并,我们进一步提出了一种动态平行和分布式图切割算法,并保证在预定义的迭代次数中与全球最佳溶液收敛。本质上,本文提供了一个通用框架,以允许采用更复杂的分裂和合并策略来进一步提高性能。我们的动态平行算法通过广泛的实验结果验证。