On partial optimality in multi label MRFs Conference Paper

Author(s): Kohli, Pushmeet; Shekhovtsov, Alexander; Rother, Carsten; Kolmogorov, Vladimir; Torr, Philip H
Title: On partial optimality in multi label MRFs
Abstract: We consider the problem of optimizing multilabel MRFs, which is in general NP-hard and ubiquitous in low-level computer vision. One approach for its solution is to formulate it as an integer linear programming and relax the integrality constraints. The approach we consider in this paper is to first convert the multi-label MRF into an equivalent binary-label MRF and then to relax it. The resulting relaxation can be efficiently solved using a maximum flow algorithm. Its solution provides us with a partially optimal labelling of the binary variables. This partial labelling is then easily transferred to the multi-label problem. We study the theoretical properties of the new relaxation and compare it with the standard one. Specifically, we compare tightness, and characterize a subclass of problems where the two relaxations coincide. We propose several combined algorithms based on the technique and demonstrate their performance on challenging computer vision problems.
Keywords: NP-hard; Binary variables; Combined algorithms; Computer vision problems; Integer Linear programmings; Integrality constraints; Maximum flow algorithms; Multilabel; Optimality
Conference Title: ICML: International Conference on Machine Learning
Conference Dates: July 5-9, 2008
Conference Location: Helsinki, Finland
Publisher: Omnipress  
Location: New York, NY, USA
Date Published: 2008-01-01
Start Page: 480
End Page: 487
DOI: 10.1145/1390156.1390217
Open access: no
IST Austria Authors
Related IST Austria Work