Direkt zum Inhalt springen
Computer Vision Group
Faculty of Informatics
Technical University of Munich

Technical University of Munich

Home Teaching Winter Semester 2015/16 IN2245 - Combinatorial Optimization in Computer Vision (4+2h | 8 ECTS)

IN2245 - Combinatorial Optimization in Computer Vision (4+2h | 8 ECTS)

WS 2015/16, TU München


Location: Room 02.09.023
Time and Date: Tuesday 10ct - 12, Wednesday 14ct - 16
Lecturers: Dr. Frank R. Schmidt and Dr. Csaba Domokos
Start: October, 20

The lectures are held in English.


Location: Room 02.09.023
Time and Date: Tuesday 14ct - 16
Organization: Thomas Windheuser and Thomas Möllenhoff
Start: October, 27


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
Lecture Material

Course material (slides and exercise sheets) can be accessed here.

The password will be presented in the first lecture.

Rechte Seite

Informatik IX

Computer Vision Group

Boltzmannstrasse 3
85748 Garching