Drawing Llamas with Circles — Dekau.dev

Fourier Analysis: Drawing Llamas with Circles¶ The Fourier transform is a method of transforming an input signal from the time domain to the frequency domain. It has a huge range of applications, for instance audio engineers can pick out individual undesired frequencies in a song with the Fourier transform and then get back the sound without that frequency using the inverse Fourier transform.  We can make use of the Fourier transform in digital image processing for filtering images, like gaussian blurs and compressing images using the JPEG format. Lastly, as this article will go into: drawing! What am I talking about by drawing? Well, the idea is that we can take a path that represents something such as a fish, the pi symbol, or just about anything else we can draw by putting pencil lead down on a piece of paper and sketching a picture without lifting the pencil until completion. Using this path we can connect a bunch of vectors rotating in circles at different frequencies tip to tail and the last vector’s tip will draw out our original sketch, or at least something very closely resembling it. Here are a few examples of what I am talking about: Fig. 1 Drawing a line with circles¶ So you can draw a straight line using a shape that is about as far opposite from a straight line as possible. By modifying the circles you can change the shape that is drawn. For example, by decreasing the radius of the outer circle and increasing the speed it spins at, we can draw a square. Fig. 2 A square¶ So what happens, then, if we add a third circle? It will allow our curves to get more sophisticated. Using a third circle we can draw a curve that looks like a fish. Fig. 3 A fish.¶ For a more extreme example of what is possible using only circles connected to other circles, here’s a llama being drawn using \(1024\) circles each with different frequencies, radii, and start angles. In general (most) every closed curve can be drawn using circles, called epicycles. Fig. 4 A llama?!¶ In general, the more circles that we add, the more complicated the drawings we can produce. Also, the more circles we add for the same drawing, the better it will resemble the original “input” drawing. In order to understand what creates that animation, we will need to go into some of the underlying math and intuition behind the Fourier transform (and series). As mentioned previously, there are three conditions we can modify on a circle to draw different curves. They are: the rate at which it rotates (frequency), how big the circle is (radius), and the angle it starts at (phase). All three of these conditions can be represented using a single complex number. Here’s an example you can mess around with to visualize the effect adding circles has on the final drawing. Fourier Transform¶ But first, I should probably give a quick overview of what the Fourier transform is. It is a transformation from the time domain to the frequency domain. What does this mean? If we have a function, \(\sin(2\pi\times 3t)\), then the Fourier transformation of that \(\sin(2\pi\times 3t)\) function would just be a single spike at the frequency \(\pm 3\text{hz}\). Fig. 5 The graph of \(\sin(2\pi\times 3t)\)¶ Fig. 6 The magnitude of \(\sin(2\pi\times 3t)\) in the frequency domain.¶ As expected, there are spikes at the frequency \(3\text{hz}\) and \(-3\text{hz}\). Essentially what we are doing is finding what frequencies are present in whatever we want and then combining those sine waves into an approximation of the original thing we wanted. Over the next few sections I’ll attempt to show how the Fourier transform works. Complex Numbers¶ This section will be a quick refresher on what a complex number is, and can be skipped if you are already familiar with them. A complex number consists of two parts, the “real” part, and the “imaginary” part. This takes numbers we are already familiar with and essentially adds another axis to represent them with. A complex number is written as \(3+4i\), where \(3\) is the real part and \(4i\) is the imaginary part. These two separate pieces are added together to form a complex number. Another useful property of complex numbers here is that they can be easily thought of as two-dimensional vector where the real portion is \(x\) and the imaginary part is \(y\) in a standard point, \((x, y)\), in the two-dimensional Euclidean space. This representation is very convenient here due to the connection between trigonometry and complex exponentials. The formula that provides the link between the two is known as Euler’s Identity. This will be covered further in a later section in the article. Linear Algebra¶ Linear Algebra is an important concept in understanding how we draw pictures using vectors rotating in circles. Namely, how we can represent vectors in terms of other vectors. In the standard 2D \((x, y)\) Euclidean space, we can represent all vectors in terms of the \(\textbf{x}\) and \(\textbf{y}\) unit vectors. These are typically called \(\hat{\textbf{i}}\) and \(\hat{\textbf{j}}\) (pronounced “i-hat” and “j-hat”) with \(\hat{\textbf{i}} = (1, 0)\) (the \(x\)-axis) and \(\hat{\textbf{j}} = (0, 1)\) (the \(y\)-axis). To do this we have two operations we can use: multiplication by a scalar and addition. For example, the vector \(\vec{a} = (5,-8)\) can be expressed as (1)¶\[\begin{split}\begin{equation}\begin{aligned}\vec{a} &= 5\cdot \hat{\textbf{i}} - 8\cdot \hat{\textbf{j}} \\ &= 5\cdot (1, 0) + -8\cdot (0, 1)\\ &=(5, 0) + (0, -8)\\ &= (5, -8)\end{aligned}\end{equation}\end{split}\] This multiplication by a scalar and addition of vectors to produce another vector is known as the linear combination of a set of vectors. In this instance, that set of vectors is the unit vectors \(\hat{\textbf{i}}\) and \(\hat{\textbf{j}}\). Fig. 7 Two vectors, \(\vec{u}\) and \(\vec{v}\) with an angle of \(90^{\circ}\) between them and both length \(1\)¶ But \(\hat{\textbf{i}}\) and \(\hat{\textbf{j}}\) aren’t the only vectors that can be used to represent other vectors, however. In fact, any two vectors can be scaled and added together to form any other vector as long as they are not a multiple of the other themselves. For example \((1,-1)\) and \((-2, 2)\) would not be valid since \((-2,2) = -2 \times (1,-1)\). In the above picture, we have vectors \(\vec{u} = (\tfrac{1}{\sqrt{2}},\tfrac{1}{\sqrt{2}})\) and \(\vec{v} = (-\tfrac{1}{\sqrt{2}}, \tfrac{1}{\sqrt{2}})\) which have length 1 and are orthogonal (a \(90^{\circ}\) angle between them). Neither of these vectors can be scaled to equal the other, which means they are linearly independent and therefore they can be basis vectors of the entire 2D space. The dot product (or sometimes called “inner product”) is how we determine what number to scale vectors by to represent them in terms of the chosen vectors. In order to represent the vector \(\vec{\textbf{w}} = (0.7, 1.2)\) from the above diagram in terms of the vectors \(\vec{u}\) and \(\vec{v}\), we need to figure out what numbers to multiply them in order to form the linear combination \(\vec{w} = c_1\cdot \vec{u}+c_2\cdot \vec{v}\). Specifically, the numbers that we need from the dot product are the constant multipliers \(c_1\) and \(c_2\). Another way of thinking about this concept is that the dot product answers the question “how much of \(\vec{u}\) is in \(\vec{w}\)?” This intuition will be important later on when we go into the math behind the Fourier transform. Anyways, we can figure out what \(c_1\) is by taking the dot product of \(\vec{w}\) with \(\vec{u}\), also note that the order does not matter (e.g., \(\langle\vec{u},\vec{w}\rangle = \langle\vec{w},\vec{u}\rangle\)). (2)¶\[\begin{split} \begin{equation}\begin{aligned} c_1 &= \langle\vec{u},\vec{w}\rangle\\ &=({u}_x\times {w}_x)+({u}_y\times {w}_y)\\ &= (\tfrac{1}{\sqrt{2}}\times 0.7)+(\tfrac{1}{\sqrt{2}}\times 1.2)\\ &= 1.3435 \end{aligned}\end{equation} \end{split}\] So we need to scale \(\vec{u}\) by a factor of \(1.3435\) which means it will get stretched by a factor of \(1.3435\) times its original size. Our \(\vec{u}\) component of \(\vec{w}\) (\(c_1\)) therefore is \(1.3435\). (3)¶\[\begin{split} \begin{equation}\begin{aligned} c_2 &= \langle\vec{v},\vec{w}\rangle\\ &=({v}_x\times {w}_x)+({v}_y\times {w}_y)\\ &=(-\tfrac{1}{\sqrt{2}}\times 0.7)+(\tfrac{1}{\sqrt{2}}\times 1.2)\\ &= 0.353553 \end{aligned}\end{equation} \end{split}\] Similarly, we need to scale \(\vec{v}\) by a factor of \(0.353553\) which means it will get shrunk (or compressed) by a factor of \(0.353553\) times its original size. Our \(\vec{v}\) component of \(\vec{w}\) (\(c_2\)) therefore is \(0.353553\). We wind up with our linear combination being (4)¶\[\begin{split} \begin{equation}\begin{aligned} \vec{w} &= 1.3435\cdot \vec{u}+0.353553\cdot \vec{v}\\ &= (0.95, 0.95)+(-0.25, 0.25)\\ &= (0.7, 1.2)\end{aligned}\end{equation} \end{split}\] Which is indeed equal to our original vector, \(\vec{w}\). Fig. 8 The linear combination of \(\vec{u}\) and \(\vec{v}\) to produce \(\vec{w}\)¶ The dot product of any two vectors is defined as (5)¶\[\begin{split} \begin{equation}\begin{aligned} \langle\vec{v_1},\vec{v_2}\rangle &= {v_1}_x\times {v_2}_x + {v_1}_y\times {v_2}_y\\ &= \|\vec{v_1}\|\times \|\vec{v_2}\| \times \cos(\theta) \end{aligned}\end{equation} \end{split}\] Where \(\theta\) is the angle between \(v_1\) and \(v_2\) and \(\|\vec{v}\|\) is the magnitude of the vector. The magnitude is also known as the norm and is defined as \(\|\vec{v}\| = \sqrt{{v}_x^2 + {v}_y^2}\). That equation probably looks familiar, and that would be because it’s just the Pythagorean theorem we’ve all learned at some point in a K-12 math class. Fig. 9 Pythagorean Triangle¶ The dot product also has some important properties that make it useful in our case. First, the dot product of any vector with itself is the magnitude of the vector squared (\(\vec{v_1}\cdot \vec{v_1} = \|\vec{v_1}\|^2\)). For instance, (6)¶\[