M. Pawan Kumar
 
 

HOME

RESEARCH

PUBLICATIONS

GROUP

TALKS

TEACHING

CV

 

 

 

 

 

 

This course has been replaced by a new MVA course.

SLIDES

Lecture 1: Probabilistic Models.
PPT   PDF

Lecture 2: Belief Propagation.
PPT   PDF

Lecture 3: Algorithms based on Minimum Cut.
PPT   PDF

Lecture 4, Part 1: Convex Relaxations.
PPT   PDF

Lecture 4, Part 2: LP Relaxation and its Dual.
PPT   PDF

Lecture 5: Tree Reweighted Message Passing, Dual Decomposition.
PPT   PDF

Lecture 6, Part 1: Dual Decomposition.
PPT   PDF

Lecture 6, Part 2: Belief Propagation for Computing Marginals.
PPT   PDF

Lecture 7: Free energy approximations.
PPT   PDF

EXTERNAL LINKS

The following paper provides speed-ups for special cases of belief propagation.
Distance Transforms of Sampled Functions
by Pedro Felzenszwalb and Dan Huttenlocher.

More speed-ups for special cases of belief propagation.
Efficient Belief Propagation for Early Vision
by Pedro Felzenszwalb and Dan Huttenlocher.

The following paper provides the graph construction for an energy function defined using 2 labels for each random variable.
What Energy Functions Can Be Minimized via Graph Cuts?
by Vladimir Kolmogorov and Ramin Zabih.

The following paper describes a minimum cut based interactive image segmentation system.
Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images
by Yuri Boykov and Marie-Pierre Jolly.

The following paper describes the expansion algorithm.
Fast Approximate Energy Minimization via Graph Cuts
by Yuri Boykov, Olga Veksler and Ramin Zabih.

The following thesis contains the derivation of the multiplicative bound for the expansion algorithm (section 4.3.4).
Efficient Graph-based Energy Minimization Methods in Computer Vision
by Olga Veksler.

The following paper provides a comparison of different convex relaxations.
An Analysis of Convex Relaxations for MAP Estimation of Discrete MRFs
by M. Pawan Kumar, Vladimir Kolmogorov and Phil Torr.

The following paper provides the tree-based dual of the LP relaxation and the original TRW algorithm.
MAP estimation via agreement on (hyper)trees: Message-passing and linear-programming approaches.
by Martin Wainwright, Tommi Jaakkola and Alan Willsky.

The following paper describes the sequential TRW algorithm. It also provides a brief description of belief propagation as reparameterization (subsection 2.2).
Convergent Tree-reweighted Message Passing for Energy Minimization
by Vladimir Kolmogorov.

The following paper describes the dual decomposition algorithm.
MRF Optimization via Dual Decomposition: Message-Passing Revisited
by Nikos Komodakis, Nikos Paragios and Georgios Tziritas.

The following paper describes the free energy approximations.
Understanding Belief Propagation and its Generalizations
by Jonathan Yedidia, William Freeman and Yair Weiss.

The following paper provides the messages for generalized belief propagation.
Generalized Belief Propagation
by Jonathan Yedidia, William Freeman and Yair Weiss.

RESOURCES

Energy minimization benchmark for smoothness-based priors.

Tutorial on (sum-product tree-reweighted) message passing algorithms.
Graphical Models and Message-Passing Algorithms
by Martin Wainwright.

Tutorial on LP relaxation.
Linear Programming Relaxations for Graphical Models
by Tommi Jaakkola and Amir Globerson.

Online course.
Probabilistic Graphical Models
by Daphne Koller.