Dynamic Parallel and Distributed Graph Cuts

doi:10.1109/TIP.2016.2609819

	Dynamic Parallel and Distributed Graph Cuts
	Yu, Miao1,2 ; Shen, Shuhan1,3 ; Hu, Zhanyi1,3,4
发表期刊	IEEE TRANSACTIONS ON IMAGE PROCESSING
	2016-12-01
卷号	25 期号:12 页码:5511-5525
文章类型	Article
摘要	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.
关键词	Graph Cuts Parallel Computation Convergence Markov Random Field
WOS标题词	Science & Technology ; Technology
DOI	10.1109/TIP.2016.2609819
关键词[WOS]	MAXIMUM-FLOW PROBLEM ; MARKOV RANDOM-FIELDS ; ENERGY MINIMIZATION ; ALGORITHM
收录类别	SCI
语种	英语
项目资助者	National Natural Science Foundation of China(61333015 ; 61421004 ; 61473292)
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Artificial Intelligence ; Engineering, Electrical & Electronic
WOS记录号	WOS:000388205100001
引用统计	被引频次：6[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://ir.ia.ac.cn/handle/173211/13350
专题	多模态人工智能系统全国重点实验室_机器人视觉
作者单位	1.Chinese Acad Sci, Inst Automat, Natl Lab Pattern Recognit, Beijing 100190, Peoples R China 2.Zhongyuan Univ Technol, Zhengzhou 450007, Peoples R China 3.Univ Chinese Acad Sci, Beijing 100049, Peoples R China 4.Chinese Acad Sci, CAS Ctr Excellence Brain Sci & Intelligence Techn, Beijing 100190, Peoples R China
第一作者单位	模式识别国家重点实验室
推荐引用方式 GB/T 7714	Yu, Miao,Shen, Shuhan,Hu, Zhanyi. Dynamic Parallel and Distributed Graph Cuts[J]. IEEE TRANSACTIONS ON IMAGE PROCESSING,2016,25(12):5511-5525.
APA	Yu, Miao,Shen, Shuhan,&Hu, Zhanyi.(2016).Dynamic Parallel and Distributed Graph Cuts.IEEE TRANSACTIONS ON IMAGE PROCESSING,25(12),5511-5525.
MLA	Yu, Miao,et al."Dynamic Parallel and Distributed Graph Cuts".IEEE TRANSACTIONS ON IMAGE PROCESSING 25.12(2016):5511-5525.

条目包含的文件		下载所有文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
TIP2016.pdf（2857KB）	期刊论文	作者接受稿	开放获取	CC BY-NC-SA	浏览下载