Persönlicher Status und Werkzeuge

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

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

Dates for the next tutorials
  • Wednesday, January 11
  • Wednesday, January 25
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.

Last edited 31.01.2012 11:56 by schlicku