A message passing algorithm for the minimum cost multicut problem Conference Paper


Author(s): Swoboda, Paul; Andres, Bjoern
Title: A message passing algorithm for the minimum cost multicut problem
Affiliation IST Austria
Abstract: We propose a dual decomposition and linear program relaxation of the NP-hard minimum cost multicut problem. Unlike other polyhedral relaxations of the multicut polytope, it is amenable to efficient optimization by message passing. Like other polyhedral relaxations, it can be tightened efficiently by cutting planes. We define an algorithm that alternates between message passing and efficient separation of cycle- and odd-wheel inequalities. This algorithm is more efficient than state-of-the-art algorithms based on linear programming, including algorithms written in the framework of leading commercial software, as we show in experiments with large instances of the problem from applications in computer vision, biomedical image analysis and data mining.
Conference Title: CVPR: Computer Vision and Pattern Recognition
Conference Dates: July 22 - 25, 2017
Conference Location: Honolulu, Hawaii, USA
Publisher: IEEE  
Date Published: 2017-07-01
Start Page: 1617
End Page: 1626
URL:
DOI: 10.1109/CVPR.2017.530
Notes: The authors would like to thank Vladimir Kolmogorov for helpful discussions and gratefully acknowledge Fred Hamprecht’s and Thorsten Beier’s help in comparing OpenGM’s multicut solvers. This work is partially funded by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160. We thank anonymous reviewers for pointing out the references [37,11]
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work