On Partial Optimality in Multi-label MRFs

author: Alexander Shekhovtsov, Institute for Computer Graphics and Vision, Graz University of Technology
published: Aug. 29, 2008,   recorded: July 2008,   views: 3645


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


We consider the problem of optimizing multi-label 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 programming problem 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. Our key contribution is a theoretical study of this new relaxation. We also show how this approach can be used in combination with recently developed optimization techniques based on roof-duality which have the desired property that a partial (or sometimes the complete) optimal solution of the binary MRF can be found. This property enables us to localize (restrict) the range of labels where the optimal label for any random variable of the multi-label MRF lies. In many cases these localizations lead to a partially optimal solution of the multi-label MRF. Further, running standard MRF solvers, e.g. TRW-S, on this restricted energy is much faster than running them on the original unrestricted energy. We demonstrate the use of our methods on challenging computer vision problems. Our experimental results show that methods derived from our study outperform competing methods for minimizing multi-label MRFs.

See Also:

Download slides icon Download slides: icml08_shekhovtsov_opo_01.pdf (583.8┬áKB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: