Parallel and Distributed Graph Cuts
Author
Summary, in English
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.
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.
Department/s
Publishing year
2010
Language
English
Full text
Document type
Conference paper
Topic
- Computer Vision and Robotics (Autonomous Systems)
- Mathematics
Conference name
Swedish Symposium on Image Analysis (SSBA) 2010
Conference date
2010-03-11 - 2010-03-12
Conference place
Uppsala, Sweden
Status
Unpublished
Research group
- Mathematical Imaging Group