Organizers:

Nikos Komodakis, Philip Torr, Vladimir Kolmogorov, Yuri Boykov

Abstract

A wide variety of tasks in computer vision and pattern recognition involve assigning a label (from a discrete set of labels) to each element in a given set of objects. Such labeling problems can be very elegantly expressed in the language of Discrete Markov Random Fields (MRFs), and it is exactly for this reason that MRF optimization is considered to be a task of fundamental importance, which has attracted a significant amount of research over the last years.

The goal of this course will be to provide an overview for some of the recent developments in the field of MRF optimization. To this end, state-of-the-art optimization algorithms for discrete MRFs will be reviewed, while, in addition, the underlying ideas and principles behind these methods will be explained.

Course outline

Part I: [slides] (speaker: Yuri Boykov)
• Introduction to MRFs
• Graph cuts and energy minimization
• Alpha-expansion

Part II: [slides] (speaker: Nikos Komodakis)
• Convex relaxations and discrete optimization
• Linear Programming relaxations
• The Primal-Dual Schema in Linear Programming
• The Primal-Dual Schema for MRF optimization

Part III: [slides] (speaker: Vladimir Kolmogorov)
• Message-passing algorithms for energy minimization
• Belief propagation
• Tree-reweighted message-passing techniques
  (TRW-E, TRW-T and TRW-S algorithms)

Part IV: [slides] (speaker: Philip Torr)
• Alternative relaxations for MRF optimization
  (SDP relaxations, SOCP relaxations)
• Dynamic graph-cuts and reparameterization
• Putting higher order priors into MRFs