Re-Implementing 3Blue1Brown's Fourier Series Drawing
Dec. 15, 2021, 18:11:15
While learning Fourier Transform, I searched for additional resources online and found a very great video by 3Blue1Brown on this topic. His explanations, aided by the animated graphs, were very intuitive and easy to follow.
In one of his three-video-sequel on Fourier Transform, he explained how Fourier Series can be used to approximate any "piecewise continuous functions". He also showed how to use circles of different sizes and which are rotating at different frequencies to approximate any 2D drawings, assuming the drawing is continuous.
This is so cool! I want to implement a similar program as a proof of me understanding how Fourier Transform works (at least the basics).
Fourier Transform Basics
Fourier transform is a transformation that decomposes a time or space dependent function into spatial or temporal dependent functions. Fourier Transform is often used in signal processing (ie. voice signal) and lossy image compression (ie. JPEG image format).
The classic Fourier Transform takes the integral of continuous functions. In the computing world where everything is discrete, there is an equivalent Discrete Fourier Transform where the integral is replaced with a summation:
$$X_k=\sum_{n=0}^{N-1}x_n\cdot e^{-\frac{2\pi i}{N}kn}$$
Both $x_n$ and $X_k$'s are complex numbers. The inverse discrete fourier transform is:
$$x_n=\frac{1}{N}\sum_{k=0}^{N-1}X_k\cdot e^{\frac{2\pi i}{N}kn}$$
Theory Behind Using Circles
Given a sequence of discrete data $\{x_0,...,x_{n-1}\}$, we can perform Fourier Transform on those data and get an equal amount of $X_k$'s. If we then perform the Inverse Fourier Transform on those $X_k$'s, we will get back the same input sequence $\{x_0,...,x_{n-1}\}$.
Let's treat the input sequence as the values of some function over some unit time. That is, $x_0$ happens at $t=0$, $x_1$ happens at $t=1$, etc. If we already have the sequence of $X_k$'s, then to get back $x_0$ at $t=0$, we perform Inverse Fourier Transform with $n=0$ as such:
$$x_0=\frac{1}{N}\sum_{k=0}^{N-1}X_k\cdot e^{\frac{2\pi i}{N}k\cdot 0} = \frac{1}{N}\sum_{k=0}^{N-1}X_k$$
This is quite easy - we just get the average of all $X_k$'s. Similarly to compute $x_1$, we have:
$$x_1=\frac{1}{N}\sum_{k=0}^{N-1}X_k\cdot e^{\frac{2\pi i}{N}k\cdot 1} = \frac{1}{N}\sum_{k=0}^{N-1}X_k\cdot e^{\frac{2\pi i}{N}k}$$
With $t\ne 0$, the computation gets more complicated but the equation doesn't change much. All we need to do is letting $n=t$.
But where do circles come into play?
If we look at the summation in the previous step, every term is of the form $X_k\cdot e^{\frac{2\pi i}{N}kn}$.
The first part of the product is a fixed number which we get from the initial Fourier Transform.
The second part changes with different values of $n$ and it defines a rotation operation at a certain frequency that is different for each $k$. This rotation naturally forms a circle in the complex plane as time $n$ progresses.
Combined together, we now see $X_k$ controls the length of a vector whose rotating frequency is controlled by $k$. The data value we want to compute at a certain time $t$ is just the sum of all vectors that are rotating at different frequencies after time $t$ has passed.
Implementation
Here are the logical steps I take:
- Implement complex numbers calculations w/ data structure
- Implement Fourier Transform and Inverse Fourier Transform
- Implement time controls and animations
Full code can be found here. The Joseph Fourier data is obtained from a similar SVG graph as in the video, which is made by Twitter user "Stuart@Biocinematics" (link to Tweet).
Or try to draw something here:
Thanks to my roommate, who as a math major, helped me greatly in understanding some of the core math concepts about Fourier Series.
Useful Links/References:
Fourier Transform - Wikipedia
Discrete Fourier Transform - Wikipedia
"But what is a Fourier series? From heat flow to drawing with circles | DE4" - 3Blue1Brown YouTube
"But what is the Fourier Transform? A visual introduction." - 3Blue1Brown YouTube