Mathematical Optimization
in Graphics and Vision

Course Organizer:

Luiz Velho (IMPA)

Course Speakers:

Paulo Cezar Pinto Carvalho (IMPA)

Luiz Velho (IMPA)


Mathematical optimization has a fundamental importance for the solution of many problems in computer graphics and vision. This fact is apparent from a quick look at the SIGGRAPH proceedings, where a significant percentage of the papers employ in one way or another mathematical optimization techniques.

The course will provide a careful conceptual analysis of the problems in computer graphics and will discuss the mathematical models used to solve them.This will motivate the audience to understand the importance of optimization techniques in graphics and vision.

The course will give an overview of combinatorial, continuous and variational optimization methods, focusing on graphical applications. Different optimization algorithms will be described and illustrated using problems from computer graphics and vision. Global optimization approaches will also be discussed in the course. Examples of the use of optimization techniques in different areas of computer graphics will be presented, including: geometric modeling, image processing, animation, computer vision and visualization.

Course Syllabus

A. Computer graphics and optimization

This module is divided into two parts. The first part will give a conceptual overview of computer graphics, focusing on problems and describing the mathematical models used to solve them. This is a short introduction to motivate the study of optimization techniques. The subject will be taught in such a way to make it clear the necessity of using optimization techniques in the solution of a large family of problems.

The second part will introduce the subject of optimization and provide a classification of the optimization problems into different categories: continuous, variational and combinatorial methods. Several examples in computer graphics will be given to illustrate each category of problems.
(Speaker: Luiz Velho)

B. Continuous and variational optimization

This module will discuss the optimization of functions $f:S \rightarrow \bf R$ , where $S$ is a subset of the Euclidean space $\bf R^n$. Optimality conditions will be discussed for optimization with and without restrictions. Different algorithms will be described such as: Newton methods, linear programming, conjugate gradient, sequential quadratic programming. Applications to camera calibration, color correction, animation and visualization will be given. The problem of variational optimization will be properly posed, with special emphasis to variational modeling using plane curves.
(Speaker: Paulo Cezar Pinto Carvalho)

C. Combinatorial optimization

The problem of combinatorial optimization is posed and different strategies to devise good algorithms are discussed. Special emphasis will be given to Dynamic programming and Integer programming. Algorithms of Dijkstra and Branch-and-bound will be discussed. Examples will be given to image and color quantization, level of detail computation, interactive visualization, minimum paths in maps and surface reconstruction from sections.
(Speaker: Luiz Velho)

D. Global optimization

The difficulties of global optimization are clearly pointed and some strategies to find solutions is discussed, including simullated annealing and genetic algorithms. The role of interval and affine arithmetic in the solution of problems is also discussed. Applications to geometric modeling, and animation will be given.
(Speaker: Paulo Cezar Pinto Carvalho)

Course History

A tutorial version of this course was presented at SIGGRAPH 2002. The course was extremely well received by the atendees. However, we had many requests to propose a full day course on this topic for SIGGRAPH 2003. The full day version of the course has been substantially expanded including a more detailed description of the optimization techniques, as well as, examples of applications in graphics and vision.

In addition to the SIGGRAPH 2002 tutorial, the course speakers have taught courses on this topic in Brazil for three times. First, as regular course for undergraduate students at IMPA, second as a 5 hour tutorial course at the Brazilian Mathematical Colloquium in July of 1999, and third as a 3 days short course at the Brazilian Congress of Applied Mathematics in October of 2000.

Course Notes Description

Course notes in PDF

Course Slides