Wavelets in Computer Graphics
Multiresolution techniques and the use of hierarchy have a long
history in computer graphics. Most recently these approaches have
received a significant boost and increased interest through the
introduction of the mathematical framework of wavelets. With
their roots in signal processing and harmonic analysis, wavelets have
lead to a number of efficient and easy to implement algorithms.
Wavelets have already had a major impact in several areas of computer
graphics:
- Image Compression and Processing: some of the most
powerful compression techniques for still and moving images
are based on wavelet transforms;
- Global Illumination: wavelet radiosity and radiance
algorithms are asymptotically faster than other finite element
techniques;
- Hierarchical Modeling: using multiresolution
representations for curves and surfaces accelerates and
simplifies many common editing tasks;
- Animation: the large constrained optimization tasks which
arise in physically based modeling and animation subject to
goal constraints can be solved faster and more robustly with
wavelets;
- Volume Rendering and Processing: wavelets can greatly
facilitate dealing with huge data sets since they can be used
for compression as well as feature detection and enhancement;
- Multiresolution Painting: using multiresolution analysis
one can build efficient ``infinite'' resolution paint systems;
- Image Query: using a small number of the largest wavelet
coefficients of an image results in a perceptually useful
signature for fast search and retrieval.
Some of the very recent and most exciting generalizations and
extensions of classical wavelet constructions have been developed by
researchers in the context of graphics applications.
Following the success of the wavelets courses at SIGGRAPH 94 and 95
and based on the experiences of the organizers and lecturers, there
will be another wavelets course at SIGGRAPH 96. Since new wavelet
constructions now exist, which are easy to implement and do not
require any heavy mathematical machinery to describe, the course will
be accessible to those who do not have any prior knowledge of wavelets
or a strong background in mathematical Fourier theory.
Course Materials
The course notes themselves come in a number of postscript files
- Building Your own Wavelets at Home,
Wim Sweldens and Peter Schröder,
chapter 1: First Generation Wavelets, chapter 2:
Second Generation Wavelets
- Multiresolution Curves, Adam
Finkelstein and David H. Salesin, chapter 3
- Multiresolution Painting and
Compositing, Deborah F. Berman, Jason T. Bartell, David
H. Salesin, chapter 4 (Color figure (big)
)
- Fast Multiresolution Image Querying
Charles E. Jacobs, Adam Finkelstein, David H. Salesin, chapter 5
- Multiresolution Surfaces for
Compression, Display and Editing, Tony D. DeRose, chapter 6
- Wavelet Radiosity: Wavelet Methods for
Integral Equations, Peter Schröder, chapter 7
- Variational Geometric Modeling with
Wavelets, Steven J. Gortler and Michael F. Cohen, chapter 8
(references for chapter 8 are at the end of chapter 9)
- Hierarchical Spacetime Control of Linked
Figures, Michael F. Cohen, Zicheng Liu and Steven
J. Gortler, chapter 9
The slides for the first (basic) part of the course are also available
The images from the slides were all generated with
LIFTPACK,
a software package for computing wavelet transform using lifting.
Format
The course will run for a whole day and consist of introductory
lectures covering wavelet basics as well as advanced lectures
describing some state of the art applications in computer graphics.
Syllabus
Morning: Introductory Material - Peter Schröder and Wim Sweldens:
- The basic idea behind wavelets: exploiting coherence
- Multiresolution analysis: looking at the world at different
resolutions
- A simple example: the Haar transform
- Building wavelets: the lifting scheme
- The fast wavelet transform
- Applications: image compression, image processing
(blurring, sharpening, denoising, edge finding)
- Classical wavelet construction: filter banks, quadrature mirror filters
- How to custom design wavelets: boundaries, irregular samples,
weighted approximation, surfaces
- Mathematical background: Function spaces, bases, and projections.
Afternoon: Applications - David Salesin, Tony DeRose, Peter
Schröder, Wim Sweldens, Michael Cohen
- David Salesin: Multiresolution curve editing, paint
systems, and image query;
- Tony DeRose: Multiresolution surfaces for compression,
display, and editing;
- Peter Schröder: Fast wavelet based solvers for
radiosity and radiance;
- Wim Sweldens: Functions defined on surfaces: efficient
representation and computation;
- Michael Cohen: Variational surface modeling for
interactive design; hierarchical space-time constraints for
animation;
- All: Wrap up: where to find resources? research
directions, future outlook.
Contact Info
| Organizers |
|---|
| Peter Schröder |
Wim Sweldens |
|---|
Assistant Professor of Computer Science
Computer Science Department 256-80
California Institute of Technology
Pasadena, CA 91125
vox: 818.395.4269
fax: 818.792.4257
net: ps@cs.caltech.edu
|
Member of Technical Staff
Lucent Technologies, Bell Laboratories
Room 2C-175
700 Mountain Avenue
Murray Hill, NJ 07974
vox: 908.582.3288
fax: 908.582.2379
net: wim@lucent.com
|
| Speakers |
|---|
| Michael Cohen |
Tony DeRose |
David Salesin |
|---|
Researcher
Microsoft Research
One Microsoft Way
Redmond, WA 98052
vox: 206.703.0134
fax: 206.936.7329
net: mcohen@microsoft.com
|
Member of Tools Group
Pixar Animation Studios
1001 West Cutting Blvd.
Richmond, CA 94804
vox: 510.236.4000
fax: 510.236.0388
net: derose@pixar.com
|
Assistant Professor
Dept. of CS and Engr.
University of Washington
Seattle, WA 98195
vox: 206.685.1227
fax: 206.543.2969
net: salesin@cs.washington.edu
|
Speaker Biographies
Peter Schröder
is an assistant professor of computer science at the California
Institute of Technology, Pasadena. He received a BS in mathematics
from the Technical
University of Berlin in 1987 and his Master degree
from the MIT Media Lab in
1990. After working for Thinking Machines
Corporation on massively parllel graphics algorithms he studied
computer graphics under Pat Hanrahan at Princeton Unviversity and
received his PhD in 1994 for research on wavelet based algorithms for
illumination computations. Most recently he was a postdoctoral
research fellow at the University of
South Carolina under the direction of Björn Jawerth.
He has worked extensively in the area of wavelet based methods for
many graphics related problems, and made fundamental contributions in
this area. His work on the subject has appeared at SIGGRAPH as well as
in WIRED magazine and he has lectured widely in Europe and the US on
the subject including previous SIGGRAPH courses.
Wim
Sweldens is a researcher at the Mathematics Center of Lucent Technologies, Bell
Laboratories. (Lucent
Technologies is the former systems and technology part of AT&T.) He received his PhD in May 1994
from the Katholieke Universiteit
Leuven, Belgium, for his work on wavelet constructions and
applications in numerical analysis. Until May 1995 he was a
postdoctoral research fellow at the University of South Carolina where
he worked with Peter Schröder and Björn Jawerth.
In his
PhD dissertation he introduced the notion of ``Second Generation
Wavelets,'' a generalization of classical wavelets which allows
wavelet transforms for irregularly sampled data and data defined on
complex geometries. Later he discovered the ``Lifting Scheme,'' a very
general and easy to implement construction of Second Generation
Wavelets, which can also be used to introduce wavelets without the use
of Fourier analysis. More recently, his work has been concerned with
the application of wavelets to computer graphics. He has lectured
widely on wavelets and their applications throughout Europe and the
United States as well as in two previous SIGGRAPH courses. He is the
founder and current editor of the Wavelet Digest, a
newsletter on the Internet concerned with wavelets.
Michael F. Cohen is curently a member of the research staff at
Microsoft. He came to
Microsoft from Princeton
University where he was an Assistant Professor of Computer
Science. Michael received his PhD in 1992 from the University of Utah. He also holds
undergraduate degrees in Art from Beloit College and in Civil
Engineering from Rutgers
University. He began his career in computer graphics at Cornell University where he
received an MS in 1985. Dr. Cohen also served on the Architecture
faculty at Cornell University
and was an adjunct faculty member at the University of Utah. His recent work
has focused on spacetime control for linked figure animation and
variational modeling methods. He is perhaps better known for his work
on the radiosity method for realistic image synthesis as discussed in
his recent book ``Radiosity and Image Synthesis'' (co-authored by John
R. Wallace). His current interests range from linked figure
animation, to image capture and synthesis, to intelligent camera
control, and image based rendering. Michael has published widely and
presented his work
internationally in these and other areas.
Tony DeRose is currently a member of the Tools Group at Pixar Animation Studios. He received
a BS in Physics in 1981 from the University of California,
Davis; in 1985 he received a Ph.D. in Computer Science from the University of California,
Berkeley. He received a Presidential Young Investigator award from the
National Science Foundation in 1989. In 1995 he was selected as a finalist
in the software category of the Discover
Awards.
From September 1986 to December 1995 Dr. DeRose was a Professor of
Computer Science and Engineering at the University of Washington.
From September 1991 to August 1992 he was on sabbatical leave at the
Xerox Palo Alto Research
Center and at Apple
Computer. He has served on various technical program committees
including SIGGRAPH, and from 1988 through 1994 was an associate editor
of ACM Transactions on Graphics.
His research has focused on mathematical methods for surface modeling,
data fitting, and more recently, in the use of multiresolution
techniques. Recent projects include surface reconstruction from
laser range data and multiresolution/wavelet methods for
high-performance computer graphics.
David Salesin teaches Computer Science and Engineering at the University of Washington,
Seattle, where he has recently been promoted to Associate Professor.
He received his ScB from Brown University in 1983, his PhD
from Stanford University in
1991, and joined the faculty at the
University of Washington
in the fall of that year. From 1983-86, he worked at Lucasfilm, where
he contributed computer animation for the Academy Award-winning short
film, ``Tin Toy,'' and the feature-length film Young Sherlock
Holmes. He spent the 1991-92 year on leave as a Visiting
Assistant Professor in the
Program of Computer Graphics at Cornell University. In 1993, he
received an NSF Young Investigator award. In 1995, he received an ONR
Young Investigator Award and was named an Alfred P. Sloan Research
Fellow and an NSF Presidential Faculty Fellow.
Professor Salesin's research interests are in computer graphics, and
include photorealistic image synthesis and computer-generated
illustration in particular. He has had a major impact on the use
of wavelets in computer graphics and is co-author (with Eric Stollnitz
and Tony DeRose) of the forthcoming book ``Wavelets for Computer
Graphics'' (Morgan-Kaufman).
Summary Statement
The course is designed to introduce practitioners in the field of
computer graphics to the many applications of wavelets:
multiresolution curve and surface modeling, image compression and
processing, radiosity and radiance computations, solution of PDEs, and
constrained optimization problems. It covers both wavelet fundamentals
and application driven algorithms, which can be put to immediate use
by the participants. Applications and algorithmic implementation
details will be emphasized.
Course Level
Intermediate The course is self contained and
participants are not expected to have prior knowledge of
wavelets. Familiarity with basic questions of computer graphics
research is assumed.
Course Objectives
The course aims to give participants a working knowledge of wavelets
and their fundamental algorithms. It will provide enough basics to
serve as a starting point for independent evaluation of the presented,
as well as future techniques. In the first half the focus is on the
basic techniques: one dimensional and higher dimensional forward and
inverse transforms; different wavelets and their various tradeoffs;
general and simple construction tools for a large class of wavelets,
applicable in many different settings, including arbitrary curves,
surfaces and volumes; fundamental processing algorithms such as
smoothing, denoising, compression, and non-linear approximation.
Intuitive examples will be used throughout to motivate and introduce
all techniques. The aim is to make it possible for participants to
immediately implement the discussed algorithms. In the second half of
the course participants will learn about the algorithmic details of
the major applications of wavelets in graphics. Again the focus will
be on ``making things work'' for real world applications. This is
necessarily done at a somewhat higher level, but with the basics from
the first half the participants will be able to envision every step
along the way to a successful implementation. In general we will
emphasize algorithmic ``know how'' and its efficient realization in
real world applications over mathematical analysis. For the latter
interested readers will find extensive notes and pointers to the
literature in the course materials. After the course participants will
be able to confidently evaluate the suitability of wavelets for
various application contexts, and rapidly implement custom designed
wavelets wherever applicable.
Course Prerequisites
Basic college level linear algebra and calculus will be assumed.
Familiarity with fundamental computer graphics algorithms and
techniques is helpful to motivate and put into perspective, many of
the taught techniques.
Intended Audience
The course is aimed at practitioners - students, researchers,
implementors - in the field of computer graphics who want to come up
to speed rapidly on this important new set of tools, as well as
people already familiar with wavelets who want to find out about
the current state of the art.
Course Notes Description
The course notes will follow the basic syllabus outline given
above. The first half will be co-written by the organizers, to
guarantee a comprehensive and continuous treatment of all the basic
foundations. The structure of the presentation will be hierarchical:
examples will be interspersed throughout to motivate and explain basic
ideas. Sections with deeper material, suitable for skipping on a first
pass, will be so marked. With these foundations
in place the second half will consist of topic treatments from the
latest research of some of the major contributors to this area of
graphics. In second part the emphasis will be on the application of the
fundamental techniques taught in the first part to the construction of
``industrial strength'' applications.
Special Notes Requirements
The CDROM will contain ready to run code for the basic techniques
presented in the course.
Copyright © 1996 Peter Schröder and Wim Sweldens