ICCV 2009 Tutorial on

MAP Inference in Discrete Models





New! Tutorial slides are now online!

Please download either all slides in pdf format or in ppt format . In total there are 6 parts. Note, you are welcome to use these slides for giving talks. If you plan to do, please let the respective author know.


Guest Speaker

Purpose of this course

Many problems in Computer Vision are formulated in form of a random filed of discrete variables. Examples range from low-level vision such as image segmentation, optical flow and stereo reconstruction, to high-level vision such as object recognition. The goal is typically to infer the most probable values of the random variables, known as Maximum a Posteriori (MAP) estimation. This has been widely studied in several areas of Computer Science (e.g. Computer Vision, Machine Learning, Theory), and the resulting algorithms have greatly helped in obtaining accurate and reliable solutions to many problems. These algorithms are extremely efficient and can find the globally (or strong locally) optimal solutions for an important class of models in polynomial time. Hence, they have led to a significant increase in the use of random field models in computer vision and information engineering in general.

This tutorial is aimed at researchers who wish to use and understand these algorithms for solving new problems in computer vision and information engineering. No prior knowledge of probabilistic models or discrete optimization will be assumed. The tutorial will answer the following questions:

(a)   How to formalize and solve some known vision problems using MAP inference of a random field?

(b)   What are the different genres of MAP inference algorithms?

(c)   How do they work?

(d)   Which algorithm is suitable for which problem?

(e)   What are the recent developments and open questions in this field?

Relationship to tutorial at ECCV 2008

Pawan Kumar and Pushmeet Kohli had given a half-day tutorial at ECCV 2008 on MAP estimation in Computer Vision (see link). The full-day tutorial at ICCV would cover the following topics that were not part of the tutorial at ECCV:

(a) Discussion of empirical studies of the performance of different inference methods for various classes of random fields.

(b) New material on recent advances: optimization of higher-order functions; introducing various convex relaxation techniques; new move-making methods.

(c) More example applications to motivate the need of different classes of functions and algorithms.


Researchers and students who had attended the previous version of our tutorial at ECCV would also find this tutorial useful and informative.


Final Syllabus

9.30-10.00 Introduction (Andrew Blake) – Part1

10.00-11.00 Discrete Models in Computer Vision (Carsten Rother) – Part2

15min Coffee break

11.15-12.30 Message Passing: DP, TRW, LP relaxation (Pawan Kumar) – Part3

12.30-13.00 Quadratic pseudo-boolean optimization (Pushmeet Kohli) – Part4

1 hour Lunch break

14:00-15.00 Transformation and move-making methods (Pushmeet Kohli) – Part4

15:00-15.30 Speed and Efficiency (Pushmeet Kohli) – Part4

15min Coffee break

15:45-16.15 Comparison of Methods (Carsten Rother) – Part5

16:15-16.45 Dual-decomposition (Carsten Rother) – Part5

16-45-17.30 Recent Advances in Convex Relaxations (Pawan Kumar) – Part6


About the Speakers


Pushmeet Kohli is a researcher in the Machine Learning and Perception group at Microsoft Research Cambridge, and a post-doctoral associate of Trinity Hall, University of Cambridge. He completed his PhD studies at Oxford Brookes University under the supervision of Prof. Philip Torr. His PhD thesis, titled "Minimizing Dynamic and Higher Order Energy Functions using Graph Cuts", was the winner of the British Machine Vision Association's Sullivan Doctoral Thesis Award, and was a runner-up for the British Computer Society's Distinguished Dissertation Award. Before joining Microsoft Research Cambridge, Pushmeet was a visiting researcher at Microsoft Research Bangalore. He previously worked in the Foundation of Software Engineering Group at MSR Redmond. Pushmeet has worked on a number of problems in Computer Vision, Machine Learning and Discrete Optimization. His papers have appeared in SIGGRAPH, PAMI, IJCV, ICCV, CVPR, ICML and ECCV.



Pawan Mudigonda is a post-doctoral researcher at Stanford University. Pawan obtained a Bachelors of Technology degree in Computer Science and Engineering from the International Institute of Information Technology, Hyderabad, India. He completed his PhD studies in 2008 at Oxford Brookes University under the supervision of Prof. Philip Torr and Prof. Andrew Zisserman. His work focuses on combinatorial and convex optimization based solutions for problems in Computer Vision and Machine Learning, and has appeared in several reputed conferences and journals such as ICCV, CVPR, NIPS, ICML and IJCV. Together with his collaborators, he won best paper awards at ICVGIP 2004, Rank Opto-Electronics Symposium 2007, and NIPS 2007.





Carsten Rother received his Diploma degree with distinction in 1999 at the University of Karlsruhe/Germany. He did his PhD at the Royal Institute of Technology Stockholm/Sweden, supervised by Stefan Carlsson and Jan-Olof Eklundh. His thesis was nominated for the Best Nordic Thesis Award 2003-2004, as one out of two candidates form Sweden. Since 2003 he is a researcher at Microsoft Research Cambridge/UK. He supervises several PhD students and gives frequently invited talks. His research interests are in the field of “Markov Random Fields for Computer Vision”, “Discrete Optimization”, and “Vision for Graphics”.  He has published more than 20 high impact papers (at least 10 citations) at international conferences and journals. He won the best paper honourable mention award at CVPR ’05. He serves on the program committee of major conferences (e.g. SIGGRAPH, ICCV, ECCV, CVPR, NIPS), and has been area chair for BMVC ‘08, and ‘09. He has organized workshops on “interactive computer vision” at ICCV ’07, and on “Color and Reflectance” at ICCV ’09.