SIGGRAPH 2003
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.
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)
This module will discuss the optimization of functions
, where 
is a subset
of the Euclidean space 
. 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)
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)
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)
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 in PDF
- Module 1:
- Module 2:
- Module 3:
- Module 4: