并行图切割马尔可夫随机场算法设计  

Parallel algorithm of graph cut in Markov random field

作　　者：王文涛[1] 陈聪[1] 李子茂[1] 

机构地区：[1]中南民族大学计算机科学学院,湖北武汉430074

出　　处：《武汉大学学报（工学版）》2010年第1期133-136,共4页Engineering Journal of Wuhan University

基　　金：国家自然科学基金项目(编号:60603008)

摘　　要：图切割(Graph-Cut)算法被广泛应用于马尔可夫随机场,使得原NP问题转变为多项式时间近似求解问题.讨论了Yuri Boykov的图切割算法的并行能力,设计并实现了其增长(Grow)和收养(Adopt)步骤的并行算法.在增长函数中使用分支界限法的广度优先搜索,并使用扩展终止线程函数,提升算法的执行效率,并在上述2个函数中调用OpenMP3.0新加入的任务(Task)功能,解决其不规则(Irregular)算法.对p个处理器,最坏情况的运行时间从原来的O(bd/2+a+nr)缩短到O(bd/2/p+a/p+nr/p).分别在单核与多核对多个能量函数的优化进行计算。Recently graph-cut becomes an increasingly useful tool for Markov random field to provide polynomial time complexity rather than the original NP hard problem.This paper explores parallelism of Yuri Boykov＇s graph cut algorithm and designs a parallel algorithm for Grow and Adopt function.The branch and bound method is used for Breadth First Search in Grow function and extending the cancel thread to improve the run times.The new feature ＂task＂ in OpenMP3.0 is used to solve the irregular problem.For p CPUs,the worst case reduces the running time from O（bd/2＋a＋nr） to O（bd/2/p＋a/p＋nr/p）.Parallel algorithms writing with OpenMP have been run on 1 and N kornels CPU.The experiment proves that this algorithm is precise and efficient.

关 键 词：并行 马尔可夫随机场 图切分 OPENMP 不规则问题 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]