Computer Science

Title: Two Topics in MAP-MRF Inference

Speaker: Vladimir Kolmogorov, University College London

Abstract:
Algorithms for MAP-MRF inference (computing maximum a posteriori configuration in a Markov Random Field) are of fundamental importance for many computer vision problems. I will talk about two such algorithms.

The first one, TRW-S, is a message passing technique for general MRFs with unary and pairwise terms, which is a variation of the tree-reweighted message algorithm by Wainwright et al.. Unlike Wainwright's techniques, TRW-S has certain convergence guarantees, and also performs better in practice.

Then I will consider the problem of computing correspondences between sparse image features related by an unknown non-rigid transformation and corrupted by clutter and occlusions. We formulate it as an instance of the graph matching optimisation problem, which is NP-hard in general. To tackle it, we use the dual decomposition approach with a particular choice of subproblems. Our method was able to find the global minimum within a minute in the majority of our examples. (These examples involved about 1000 potential correspondences.) This part of the talk is a joint work with L. Torresani and C. Rother.