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

Technical University of Munich

Home Teaching Winter Semester 2011/12 Combinatorial Optimization in Computer Vision

Combinatorial Optimization in Computer Vision

WS 2011/12, TU München


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

Dates for the next tutorials
  • Wednesday, January 11
  • Wednesday, January 25

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.

Rechte Seite

Informatik IX
Chair of Computer Vision & Artificial Intelligence

Boltzmannstrasse 3
85748 Garching