Back to Search
Start Over
Dynamic Parallel and Distributed Graph Cuts.
- Source :
- IEEE Transactions on Image Processing; Dec2016, Vol. 25 Issue 12, p5511-5525, 15p
- Publication Year :
- 2016
-
Abstract
- 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. [ABSTRACT FROM PUBLISHER]
- Subjects :
- GRAPH theory
GRAPH coloring
SIMULATED annealing
ALGORITHMS
MATHEMATICAL programming
Subjects
Details
- Language :
- English
- ISSN :
- 10577149
- Volume :
- 25
- Issue :
- 12
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Image Processing
- Publication Type :
- Academic Journal
- Accession number :
- 118673825
- Full Text :
- https://doi.org/10.1109/TIP.2016.2609819