Conference item icon

Conference item

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.
Publication status:
Published
Peer review status:
Peer reviewed

Actions

Access Document

Files:
Publisher copy:
10.1145/1390156.1390217

Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Engineering Science
Role:
Author
ORCID:
0009-0006-0259-5732


European Commission More from this funder


Publisher:
Association for Computing Machinery
Host title:
ICML '08: Proceedings of the 25th international conference on Machine learning
Pages:
480-487
Publication date:
2008-07-05
Event title:
25th Annual International Conference on Machine Learning (ICML 2008)
Event location:
Helsinki, Finland
Event website:
https://icml.cc/Conferences/2008/
Event start date:
2008-07-05
Event end date:
2008-07-09
DOI:
ISBN:
9781605582054


Language:
English
Keywords:
Pubs id:
971546
Local pid:
pubs:971546
Deposit date:
2024-05-21
ARK identifier:

Terms of use


Views and Downloads

Views and downloads will return soon






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP