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