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: [ppt slides] (Speaker: Yuri Boykov)
• Introduction to MRFs
• Graph cuts and energy minimization
• Alpha-expansion

Part II: [ppt slides] (Speaker: Nikos Komodakis)
• Convex relaxations and discrete optimization
• Linear Programming relaxations
• MRF optimization via the Primal-Dual Schema
• MRF optimization via Dual Decomposition

(15 minutes coffee break)

Part III: [ppt 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: [ppt slides] (Speaker: Philip Torr)
• Alternative relaxations for MRF optimization
  (SDP relaxations, SOCP relaxations)
• Dynamic graph-cuts and reparameterization
• Putting higher order priors into MRFs