FFTs in Graphics and Vision

Course Description

In this course, we will study the Fourier Transform from the perspective of representation theory. We will begin by considering the standard transform defined by the commutative group of rotations in 2D and translations in two- and three-dimensions, and will proceed to the Fourier Transform of the non-commutative group of 3D rotations. Subjects covered will include correlation of images, shape matching, computation of invariances, and symmetry detection.


To facilitate discussion among students, a Piazza page has been set up. Please keep in mind that the instructor will only check the Piazza status infrequently, so if you have a question you would like him to address, please either email him directly or make sure Piazza notifies him of your post. (That said, you should feel very comfortable either contacting the instructor by email or having Piazza notify him.)

Source Code

The code you will be using is packed in the Assignments.zip archive. The archive contains Visual Studio 2017 solution files as well as Makefiles that should allow you to compile the code. For windows uers, the FFTW .lib and .dll files are already includes. For Linux users, you will need to download/install those so the compiler can find them. Also, the Makefile assumes that libjpeg is already installed on your system.


Date Subject Reading
Week 1 01/28/19 Introduction
01/30/19 Fast String Matching (and Math) Fast Pattern Matching in Strings
Week 2 02/04/19 More Math Review
02/06/19 Groups and Representations
Week 3 02/11/19 Moving Dot Products
02/13/19 The Fast Fourier Transform An Algorithm for the Machine Calculation of Complex Fourier Series
Week 4 02/18/19 Alignment, Invariance, and Pattern Matching
02/20/19 Rotational and Reflective Symmetry Detection
Week 5 02/25/19 Differential Equations
02/27/19 Snow Day
Week 6 03/04/19 Homogenous Polynomials and Irreducible Representations
03/06/19 The Laplace Operator
Week 7 03/11/19 Spherical Harmonics
03/13/19 Spherical Harmonics and Legendre Polynomials
03/18/19 Spring Break
Week 8 03/25/19 The Spherical Laplacian
03/27/19 Invariance of Shape Descriptors
Week 9 04/01/19 Class Cancelled
Week 10 04/08/19 Representing Rotations
04/10/19 Spherical Convolution and Axial Symmetry Detection
Week 11 04/15/19 Correlation of Spherical Functions
04/17/19 Rotational and Reflective Symmetry Detection
Week 12 04/22/19 Fast Alignment of Spherical Functions An Approximate and Efficient Method for Optimal Rotation Alignment of 3D Models
04/24/19 Characters and Representations
Week 13 04/29/19 Spectral Geometry Processing
05/01/19 Conclusion