Coding Challenge #130.1: Drawing with Fourier Transform and Epicycles

Coding Challenge #130.1: Drawing with Fourier Transform and Epicycles

November 24, 2019 100 By Bernardo Ryan


(bell dings) – Hello, welcome to a coding challenge. I actually just finished
this coding challenge, and I’m coming back to
re-record a little intro to it. And what I made in this coding challenge is a drawing machine. Maybe let’s call this a Fourier
transform drawing machine. There’s a few more things
we want to do with it. There’s going to be some followup videos. But this very, very long
video, if you can stand to watch it, has, as part
of it, at the end, this. This is the end result. I am using an algorithm
called Fourier Transform to take an arbitrary signal,
in this case, a sequence of X’s and a sequence of Y’s, the
path of the Coding Train logo, thank you to Tom Fevrier. I will link to Tom Fevrier’s
Twitter, who provided the path for this
particular logo, to trace the path of the logo through
this sort of sequence of rotating circles, sometimes
referred to as epicycles. Okay, so what’s going on here? So, first thing I should
mention is this is a continuation of my coding
challenge Fourier Series. And so, what I did in that
particular coding challenge, which was inspired by a Smarter
Everyday video on the same topic, was create the Fourier
series for a square wave. I don’t know why I just had to write that. But in this video, I’m going
to do something different, which is I’m going to use the
Fourier transform algorithm. And these are different concepts. I somewhat conflated these
in my previous video. The idea of the Fourier transform. Now, where I know this
algorithm from, where I learned about this algorithm first in
like, learning about coding and creative coding and new
media and sound and video is with the terminology FFT, and actually, if you go into the p5
sound library, you’ll see there is a class or
function called p5.FFT. I don’t remember exactly what it’s called, but something like that. The F here stands for fast,
Fast Fourier Transform. The algorithm I’m going to implement, by the way, is discrete Fourier transform. Why is this FFT thing,
where is it typically used? Well, it’s typically used in,
it’s in signal processing, but a familiar place
where you might find that is in audio signal processing. So let’s say you have
some arbitrary sound wave that maybe looks like
this, and it has a really high-pitched, awful,
screeching sound in it. How would you filter that out? Well, if you could take
this sound wave pattern and break it into a bunch
of smaller sound waves, a bunch of sound waves that have varying amplitudes and frequencies,
then you could take, you could sort of remove the one that has the high-pitched sound in it and then add them all back together
and get a new sound wave. So the idea of a Fourier
transform, I think I said this in the Fourier Series, but
it’s unsmoothie-ing a smoothie. If we could take a smoothie
that’s made with blueberry, mango, and strawberries,
and like, separate it out and then put it back together
without the strawberries, this is essentially what
happens in signal processing. But in this video, what I’m going to do is instead of the signal being
an audio, it’s going to be a series of X values or
a series of Y values, and eventually, there
actually a way to do that with the X, Y values
together that I will get to. So, I am not going to go
too deep into the math in this particular video. I’m not going to derive the
Fourier Transform algorithm. I’m not going to talk about
Fast Fourier Transform. I’m just going to use a very
crude, discrete Fourier Transform implementation just to
get the thing working. If you want to know more
about the math, though, let me reference a few
really key references. The 3blue1brown video, But
what is the Fourier Transform? will give you an infinitely
better understanding of what the Fourier Transform algorithm is and what it does, and even how
it works, way better than my trying to ramble through
that over on the whiteboard. I would also highly recommend
this GoldPlatedGoof video, Fourier Analysis for the
Rest of Us, which goes through the details of the
math in a much deeper way, and then there’s this wonderful
video from Mathologer, Epicycles, complex Fourier
series and Homer Simpson’s orbit, which will give you the
full story of everything that I’m trying to do. But hopefully, what’s useful
to you that’s different in my video than from these
is I’m just going to sit here and attempt to code the thing. And I know that it’s going to
work, because I already did it, and here is the result. So enjoy. This is a very long video. I hope that if you watch
it, you get the code, you make your own variation of
it, please share it with me. You can go to thecodingtrain.com,
to the particular coding challenge page, and
then there’s instructions on how to submit a user
community variation thingy there. Okay, goodbye, enjoy, or not, or whatever. I am ready to start coding, finally. Now, this is where I left off
before in my Fourier Series coding challenge, and
the difference now is what I want to do is be able
to have an arbitrary signal and then compute what
all of these amplitudes and frequencies and phases should be. So, the way that I’m going to do that is, so let’s think about this. This is really a bunch of Y
values that I’m calculating. So let’s make an array
called something like Y, and this is going to be the
signal, this is my signal. This could be audio, it
could be Y positions, any arbitrary digital
signal/array of numbers. Then what I want to do is I want to have like, the Fourier transform
of that particular signal. So I want to say, fourierY
=fourierTransform, or maybe like dft, discrete Fourier
Transform, of the Y value. So this is the idea. The first thing that I
need to do is compute the discrete Fourier transform
of an arbitrary signal. Now I need some kind of signal. So I think what I’m going to absurdly do is hardcode the signal. Let’s actually make it the square wave, and then we’ll know if it kind of worked. So what is the square wave? Square wave would be
something like 100, 100, 100, – 100, -100, -100, and then
like, do that a few times. So this is going to be
my arbitrary signal, which I’m just hardcoding the square wave. And we’ll do some interesting
things that we might, maybe I’ll try a Perlin noise signal or just a sine wave signal. We’ll try different things, random numbers, and see what that does. So then, this actual code here
can largely stay the same, ’cause in theory, the difference is now, instead of following the
specific Fourier Series for the square wave, I just need to take the results of my discrete
Fourier transform. So this would be a loop that’s going to go through the length of
that transform, how many different wave patterns are
there that I’m adding together, and then this ultimately, I’m
going to have to figure out. So let’s comment this out right now, and there’s a little bit
of an issue where I have this x and y as like,
local variables here. But let’s, I think this will be okay. So let’s refresh this,
and DFT is not fine. Okay, step one, let’s write the discrete Fourier Transform algorithm. So, I’m going to start by
making a function called dft. It’s going to have some
array of values, and now, I need to, at the end, I
need to return something. (laughs) The idea is that I will return the discrete Fourier
transform of those values. So, a couple things. One is I highly recommend,
if you want to pause this video right now and
read this particular article on the Algorithm Archive by James Schloss or the
LeIOS YouTube channel. This is a really nice article
about Fourier transforms and the discrete Fourier
Transform algorithm, and this particular algorithm for FFT. But what I’m going to do
is I’m just going to follow exactly what’s here on the Wikipedia page. So, my signal is x sub n, lowercase xn. So what I need to do is basically, and the transform is capital X sub k. So I need to write a
function that computes this exact equation and
returns it as an array, and this is exactly what I’m going to do. This is exciting. Now, one thing I should mention is that in order to work with Fourier transforms, I need to understand something
called a complex number. Now, if I recall correctly,
the last time a complex number came up on this YouTube
channel was probably in my Mandelbrot set coding
challenge, where I visualized the famous Mandelbrot fractal,
and I referenced something called an imaginary number,
and I was way too informal and loosey goosey and jokey about how I talked about imaginary numbers being this pretend thing
that doesn’t exist, which is absolutely incorrect. The reason why the term imaginary is used is because there is no
real number solution to the square root of negative
one, but the square root of negative one is referred
to in mathematics as i. I is a complex number. A complex number is a
number with both a real, a, plus an imaginary component. So it’s two real values, a real value and another real value
kind of multiplied by i, the square root of negative one. So, this is the idea of a
complex number, and by the way, another way for me to
refer to a complex number is by its position on the complex plane. So if this were the real axis, and this were the imaginary
axis, this would be a, and this would be b, and this
is a vector representation, whoa, of this particular complex number. So, why do I bring this up? The reason why I bring this up
is that the Fourier Transform algorithm, even if I start
with an array of real numbers, single numbers, I’m going to
apply the Fourier Transform and get out a complex number. What I’m going to return
from that function is both a’s and b’s, otherwise
known as the real component, which is often written in code as re, and the imaginary component,
which is often written as im. So this is one bit that I
really need to understand before working with this formula. So now is this moment, this
moment that happens to you in life, where you see
one of these formulas on a Wikipedia page or in a math textbook, and you’re a creative coder making some kind of visualization thing,
and you just want to stop. But together, you and me,
we’re not going to stop. We’re going to figure out
how to translate all this notation and symbols and
stuff into JavaScript code. Now, again, it’ll be super
interesting to go down the rabbit hole of deriving all these
formulas and the background for how Fourier transform works,
but I’m not going to do that. If you look in the video description, there are several excellent
videos and resources linked to that will give
you that background. But I do want to mention one
thing, which is quite important, which is that this particular
formula in the top here for the discrete Fourier
transform uses this symbol e, Euler’s number, or the
base of natural law. This is a very famous number
in mathematics, much like pi, but there’s also a very well known formula called Euler’s formula,
which looks like this: e to the i, which, complex
number i, x, equals cosine of x plus i times sine of x. Really interesting,
kind of looks like polar to Cartesian coordinate transformation. All this stuff is interrelated, right? But so, that is where,
if I come back to here, this is where we get the
second line here, using Euler’s formula from the
particular formula that’s up top. But this is the one that
I want to implement, and I have written the
formula out right over here so we can unpack it a little bit. What are the components
we need to understand? Now, really, if this were a math lesson about Fourier Transform,
we wouldn’t be using summation; we would be using integration. But because we’re working on a computer, and I need to write a loop,
and I don’t have infinity as a tool that I can just use, I need to, instead of doing integration,
do summation, and that’s why also this is called
discrete Fourier transform, ’cause I’m doing it over this
sort of like, discrete space. Okay, so this means summation. So this should give you
clue that I can just do like a for loop, going from
zero all the way up to n. And by the way, n is
going to be the length, the number of values I have in my signal, so the length of that original array. Oh, and then the other thing
that’s really important is that basically what I
get to do is separate out. This is the real component, and this is the imaginary component. So even though this is all
written as one formula, I’m going to sum up
all the real components and all the imaginary components together. And by the way, as Simon, who
has been watching this live, pointed out to me, there
are only complex numbers. The term imaginary, it’s
really too bad that it’s called imaginary, ’cause it’s very misleading. But a real number is just a complex number with the imaginary component as zero. Okay, so, I should be able to start writing the
code for this now, right? This is my signal. It’s a little confusing
that this is called X, ’cause I called it Y, but this
is just the values, the vals. This n is vals.length
in my code, and then, k, we’re going to have to work out what k is. I know what cosine is, two
pi, and all these things. So we’re going to work out what k is. Oh, boy, I’m so silly. What is k? This should actually, this is, this is, I completely forgot to
write what is quite possibly the most important part of this formula (instructor laughs)
over here, which is capital X, big X, sub k equals. So, this is what I’m trying to calculate. I’m trying to create
an array of k elements. At each element k, I’m going to sum up n from zero to the end. So there’s a little bit of
a nested loop going on here. I want to loop through
every k, which is going from zero all the way up
to n, and then also sum up. So k is going to stay constant
within each one of these, and k is actually really the
frequency, we’ll see that, the frequency of the particular
wave pattern in that slot. Okay, all right, so let me
write the code for this. The first thing that I want to
do is create an empty array. This is where I’m going to
store all of the results. Then I need to write a loop,
which is let k=0; k