Parallel and distributed graph cuts by dual decomposition
Authors:
- 1 June 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636919,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 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.Keywords
This publication has 16 references indexed in Scilit:
- Local layeringACM Transactions on Graphics, 2009
- Dynamic dual decomposition for distributed control2009
- A Scalable graph-cut algorithm for N-D grids2008
- Global Optimization for Shape Fitting2007
- MRF Optimization via Dual Decomposition: Message-Passing Revisited2007
- Efficiently solving dynamic Markov random fields using graph cuts2005
- An experimental comparison of min-cut/max- flow algorithms for energy minimization in visionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Markov random fields with efficient approximations2002
- A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics2002
- Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of ResourcesOperations Research, 1963