IN2245 - Combinatorial Optimization in Computer Vision (4+2h | 8 ECTS)
WS 2015/16, TU München
By handing in reasonable solutions to 60% of the exercises you can obtain a bonus of 0.3 in the final exam. Note that you can neither improve a 1.0 nor a 5.0.
Location: Room 02.09.023
1st Date: March, 1 and March, 2
2nd Date: April 8
Please contact us per email if you want to reserve a specific time slot. For more details visit the internal page.
Many problems in Computer Vision can be cast as a combinatorial optimization problem. 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, human pose estimation, optical flow estimation or shape matching. 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. Theoretical topics we plan to cover include:
- MAP inference for MRFs and combinatorial optimization problems
- Submodular boolean optimization, polynomial time algorithms (e.g. graph cuts)
- Approximation approaches like alpha-expansion, belief propagation as well as submodular-supermodular procedure and fast trust region approaches.
Practical applications that we will cover are
- binary image segmentation (with and without prior information)
- multi-object segmentation
- stereo matching
- optical flow computation
The course is intended for Master students.
The requirements for the class are knowledge in basic mathematics, in particular multivariate analysis and linear algebra, and in basic computer science, in particular dynamic programming and basic data structures.
Since we will work with OpenGM, it is a plus if you make yourself familiar with it prior to the lecture.
- Schrijver, Combinatorial Optimization, ISBN 978-3-540-44389-6
- Boros, Hammer, Pseudo-Boolean Optimization, ScienceDirect
- Nowozin, Lampert, Structured Learning and Prediction in Computer Vision, ISBN 978-1-60198-456-2 Download
- Blake, Kohli, Rother, Markov Random Fields for Vision and Image Processing, ISBN 978-0-26201-577-6
Course material (slides and exercise sheets) can be accessed here.
The password will be presented in the first lecture.