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.