Discrete optimization provides a very general and flexible modeling paradigm that is ubiquitous in computer vision and image analysis. As a result, related optimization methods form an indispensable computational tool for a wide variety of computer vision tasks nowadays (including both low-level and high-level tasks). The aim of this course is to introduce students to the relevant concepts and techniques of discrete optimization and to familiarize them with how these methods can be applied to computer vision and machine learning. We will cover state of the art algorithms used for energy minimization, marginal computation and parameter estimation of rich, expressive models that are employed in computer vision, focusing not only on the accuracy but also on the efficiency of the resulting methods.

Place & time

Classes will take place on Fridays from 9:30am to 12:45pm at Ecole Centrale de Paris (Amphitheater 7 at the Olivier Building).


Each programming assignment can be done by groups of 2 students.

Assignment 1 [supp. material]

Sample exam questions

Sample problems


Introduction, basic concepts, dynamic programming, message-passing methods [slides]

Generalizing belief propagation, message-passing for higher-order models, accelerating message-passing [slides]

Graph-cuts, binary energy minimization [slides]

Multi-label energy minimization via graph-cuts [slides]

Reparameterization and message-passing [slides]

Convex relaxations [slides]

Linear programming relaxations [slides]

Tree-reweighted message passing [slides]

Dual decomposition [slides]

Rounding-based moves [slides]

Sum-product belief propagation [slides]

Minimizing free energy [slides]