中文摘要：

图切割（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.