中文|CAS

logo
banner

Journals & Publications

Journals Publications Papers

Papers

Dynamic Parallel and Distributed Graph Cuts
Dec 16, 2016Author：
PrintText Size A A

Title: Dynamic Parallel and Distributed Graph Cuts
Authors: Yu, M; Shen, SH; Hu, ZY
Author Full Names: Yu, Miao; Shen, Shuhan; Hu, Zhanyi
Source: IEEE TRANSACTIONS ON IMAGE PROCESSING, 25 (12):5511-5525; 10.1109/TIP.2016.2609819 DEC 2016
Language: English
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.
ISSN: 1057-7149
eISSN: 1941-0042
IDS Number: EC5VJ
Unique ID: WOS:000388205100001
*Click Here to View Full Record