
ICCV
2009 Tutorial on MAP
Inference in Discrete Models 
 
Speakers
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 lowlevel vision such as image
segmentation, optical flow and stereo reconstruction, to highlevel 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 halfday tutorial at ECCV 2008 on MAP
estimation in Computer Vision (see link). The fullday
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 higherorder functions;
introducing various convex relaxation techniques; new movemaking 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.3010.00
Introduction (Andrew Blake) –
Part1 10.0011.00
Discrete Models in Computer Vision (Carsten Rother) – Part2 15min Coffee
break 11.1512.30
Message Passing: DP, TRW, LP relaxation (Pawan Kumar) – Part3 12.3013.00
Quadratic pseudoboolean optimization (Pushmeet Kohli) – Part4 1 hour Lunch
break
15:0015.30
Speed and Efficiency (Pushmeet Kohli) –
Part4 15min Coffee
break 15:4516.15
Comparison of Methods (Carsten Rother) –
Part5 16:1516.45
Dualdecomposition (Carsten Rother) –
Part5 164517.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 postdoctoral 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 runnerup 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
postdoctoral 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 OptoElectronics 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 JanOlof Eklundh. His
thesis was nominated for the Best Nordic Thesis Award 20032004, 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.  