Location: Room 02.09.023
Time and Date: Tuesday, 10.15h - 11.45h
Lecturer: Dr. Ulrich Schlickewei
Start: Tuesday, 18.10.2011

The lectures will be held in English, if desired.

Location: 02.09.023
Time and Date: Wednesday 14.15-15.45h every other week
Organization: Dr. Ulrich Schlickewei

• Wednesday, November 30
• Wednesday, December 14

Many problems in Computer Vision but also in related fields such as Machine Learning can be cast as combinatorial optimization problems. Typically, such problems arise from Markov Random Field (MRF) models which provide a very elegant framework of formulating various types of labeling problems in imaging. Examples include image segmentation, optic flow estimation, depth estimation from stereo images or shape matching.

After quickly reviewing how MRFs lead to combinatorial optimization problems we will concentrate in this course on algorithmic strategies for solving these problems. Some “nice” problems can be solved in polynomial time while others are NP hard. We will see both, efficient algorithms for solving the “nice” problems and relaxation strategies for the “hard” problems.

Topics we plan to cover include:

• MAP inference for MRFs and combinatorial optimization problems
• Submodular boolean optimization, polynomial time algorithms (e.g. graph cuts)
• Integer Linear Programming, LP relaxation
• Dual Decomposition
• Quadratic Pseudo-Boolean Optimization and generalizations

The course is intended for Master students. The requirements for the class are knowledge in basic mathematics, in particular multivariate analysis and linear algebra. Some prior knowledge on optimization or linear programming is a plus but is not necessary.

Additional material can be downloaded from here.