Advanced

Parallel and Distributed Graph Cuts by Dual Decomposition

Strandmark, Petter LU and Kahl, Fredrik LU (2010) IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), 2010 In IEEE Conference on Computer Vision and Pattern Recognition p.2085-2092
Abstract
Graph cuts methods are at the core of many state-of-the-art 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... (More)
Graph cuts methods are at the core of many state-of-the-art 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 speed-up, an extensive empirical evaluation on several applications with many different data sets consistently shows good performance. An open source C++ implementation of the dual decomposition method is also made publicly available. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
mpi, supercomputer, parallel, graph cuts
in
IEEE Conference on Computer Vision and Pattern Recognition
pages
8 pages
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
conference name
IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), 2010
external identifiers
  • wos:000287417502018
  • scopus:77956008810
ISSN
1063-6919
ISBN
978-1-4244-6984-0
DOI
10.1109/CVPR.2010.5539886
language
English
LU publication?
yes
id
8d6fa8fb-cf7b-4e3f-b1f7-885f9e1f7c94 (old id 1567612)
alternative location
http://www.maths.lth.se/vision/publdb/reports/pdf/strandmark-kahl-cvpr-2010.pdf
date added to LUP
2010-03-26 12:52:08
date last changed
2018-05-29 11:48:49
@inproceedings{8d6fa8fb-cf7b-4e3f-b1f7-885f9e1f7c94,
  abstract     = {Graph cuts methods are at the core of many state-of-the-art 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.<br/><br>
<br/><br>
We demonstrate that our approach both allows <br/><br>
 (i) faster processing on multi-core computers and <br/><br>
 (ii) the capability to handle larger problems by splitting the graph across multiple computers on a distributed network. <br/><br>
Even though our approach does not give a theoretical guarantee of speed-up, an extensive empirical evaluation on several applications with many different data sets consistently shows good performance. An open source C++ implementation of the dual decomposition method is also made publicly available.},
  author       = {Strandmark, Petter and Kahl, Fredrik},
  booktitle    = {IEEE Conference on Computer Vision and Pattern Recognition},
  isbn         = {978-1-4244-6984-0},
  issn         = {1063-6919},
  keyword      = {mpi,supercomputer,parallel,graph cuts},
  language     = {eng},
  pages        = {2085--2092},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  title        = {Parallel and Distributed Graph Cuts by Dual Decomposition},
  url          = {http://dx.doi.org/10.1109/CVPR.2010.5539886},
  year         = {2010},
}