Parallel and Distributed Graph Cuts by Dual Decomposition

author: Petter Strandmark, Centre for Mathematical Sciences, Lund University
published: July 19, 2010,   recorded: June 2010,   views: 5358


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


Graph cuts methods are at the core of many state-of-theart algorithms in computer vision due to their efficiency in computing globally optimal solutions. In this paper, we solve the maximum flow/minimum cut problem in parallel by splitting the graph into multiple parts and hence, further increase the computational efficacy of graph cuts. Optimality of the solution is guaranteed by dual decomposition, or more specifically, the solutions to the subproblems are constrained to be equal on the overlap with dual variables. We demonstrate that our approach both allows (i) faster processing on multi-core computers and (ii) the capability to handle larger problems by splitting the graph across multiple computers on a distributed network. Even though our approach does not give a theoretical guarantee of speedup, an extensive empirical evaluation on several applications with many different data sets consistently shows good performance. An open source implementation of the dual decomposition method is also made publicly available.

See Also:

Download slides icon Download slides: cvpr2010_strandmark_pdgc_01.ppt (6.8 MB)

Download article icon Download article: cvpr2010_strandmark_pdgc_01.pdf (2.3 MB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 ARJUN, January 4, 2011 at 11:23 a.m.:

its not a bad improve new innnovation natural science

Write your own review or comment:

make sure you have javascript enabled or clear this field: