This is an old revision of the document!
Combinatorial Optimization in Computer Vision
WS 2011/12, TU München
Lecture
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.
Exercises
Location: 02.09.023
Time and Date: Wednesday 14.15-15.45h every other week
Organization: Dr. Ulrich Schlickewei
Schedule for the first weeks
In the first weeks some lectures have to be shifted because of public holidays, conferences and other constraints. The schedule is as follows:
Tue 18.10.: Lecture 1
Wed 19.10.: Lecture 2
Tue 25.10.: No lecture (has been shifted to Wed 19.10.)
Wed 26.10.: No tutorial
Tue 1.11.: No lecture (All Saints)
Wed 2.11.: No tutorial
Tue 8.11.: Lecture 3
Wed 9.11.: No tutorial
Tue 15.11.: No lecture (Student Assembly, lecture is shifted to Wed 16.11.)
Wed 16.11.: Lecture 4
From thereon regularly lectures on Tuesdays and tutorials on Wednesdays.
Summary
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
Prerequisites
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.
Slides
Additional material can be downloaded from here.