Advanced

Parallel and Distributed Graph Cuts

Strandmark, Petter LU and Kahl, Fredrik LU (2010) Swedish Symposium on Image Analysis (SSBA) 2010
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 computers on a... (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 speedup, an extensive empirical evaluation on several applications with many different data sets consistently shows good performance. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to conference
publication status
unpublished
subject
conference name
Swedish Symposium on Image Analysis (SSBA) 2010
language
English
LU publication?
yes
id
8c2b9673-cb42-4b1e-9e9e-dda08046e12d (old id 1554158)
date added to LUP
2010-03-12 14:23:32
date last changed
2016-04-16 12:47:47
@misc{8c2b9673-cb42-4b1e-9e9e-dda08046e12d,
  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<br/><br>
with dual variables.<br/><br>
<br/><br>
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.},
  author       = {Strandmark, Petter and Kahl, Fredrik},
  language     = {eng},
  title        = {Parallel and Distributed Graph Cuts},
  year         = {2010},
}