傅里叶分析：用圆圈绘制羊驼

# 用圆圈绘制羊驼 — Dekau.dev 来源：https://adekau.github.io/posts/2020/llamas.html ## 傅里叶分析：用圆圈绘制羊驼¶ (https://adekau.github.io/posts/2020/llamas.html#fourier-analysis-drawing-llamas-with-circles) 傅里叶变换是一种将输入信号从时域转换到频域的方法。它有*极广泛*的应用范围，例如，音频工程师可以使用傅里叶变换从一首歌曲中提取出不希望出现的单个频率，然后通过逆傅里叶变换得到去除了该频率的声音。我们可以在数字图像处理中使用傅里叶变换来过滤图像，比如高斯模糊和使用JPEG格式压缩图像。最后，正如本文将要探讨的：绘图！我说的*绘图*是什么意思？嗯，想法是这样的：我们可以取一条路径，这条路径代表像一条鱼、π符号，或者任何其他我们可以通过将铅笔放在纸上、不抬起笔直到完成素描就能画出来的东西。利用这条路径，我们可以将一系列以不同频率旋转的向量首尾相连（一个向量的终点连接下一个向量的起点），最后一个向量的终点将描绘出我们最初的素描，或者至少是与之非常相似的东西。以下是我所说的几个例子： ../../_images/line.gif 图1 用圆圈画一条线¶ (https://adekau.github.io/posts/2020/llamas.html#id1) 所以你可以用一个与直线形态截然相反的形状来画出一条直线。通过修改这些圆圈，你可以改变绘制出的形状。例如，通过减小外圆的半径并增加其旋转速度，我们可以画出一个正方形。 ../../_images/square.gif 图2 一个正方形¶ (https://adekau.github.io/posts/2020/llamas.html#id2) 那么，如果我们加入第三个圆圈会发生什么？它将允许我们的曲线变得更复杂。使用第三个圆圈，我们可以画出一条看起来像鱼的曲线。 ../../_images/fish.gif 图3 一条鱼。¶ (https://adekau.github.io/posts/2020/llamas.html#id3) 为了展示仅使用相互连接的圆圈所能达到的效果，这里有一个用\（1024）个不同频率、半径和起始角度的圆圈绘制羊驼的例子。一般来说，（大多数）所有闭合曲线都可以用圆圈（称为外摆线）来绘制。 ../../_images/llama.gif 图4 一只羊驼？\¶ 一般来说，我们添加的圆圈越多，能够绘制出的图形就越复杂。同时，对于同一幅画，我们添加的圆圈越多，它就越接近原始的“输入”图形。为了理解那个动画是如何产生的，我们需要深入探讨傅里叶变换（以及傅里叶级数）背后的一些数学原理和直觉。 如前所述，我们可以修改圆圈的三个条件来绘制不同的曲线。它们是：旋转的速率（频率）、圆圈的大小（半径）以及起始角度（相位）。所有这三个条件都可以用一个复数来表示。这里有一个你可以尝试的交互示例，用来可视化添加圆圈对最终绘图的影响。 ## 傅里叶变换¶ (https://adekau.github.io/posts/2020/llamas.html#fourier-transform) 但是首先，我大概应该快速概述一下什么是傅里叶变换。它是一种从时域到频域的变换。这意味着什么？如果我们有一个函数\(\sin(2\pi\times 3t)\)，那么这个\(\sin(2\pi\times 3t)\)函数的傅里叶变换将仅仅是在频率\(\pm 3\text{hz}\)处的一个尖峰。 ../../_images/sin2pi3t-2.svg 图5 \(\sin(2\pi\times 3t)\)的图像¶ (https://adekau.github.io/posts/2020/llamas.html#id5) ../../_images/fft_sin2pi3t-3.svg 图6 \(\sin(2\pi\times 3t)\)在频域中的幅度。¶ (https://adekau.github.io/posts/2020/llamas.html#id6) 正如预期的那样，在频率\(3\text{hz}\)和\(-3\text{hz}\)处有尖峰。本质上，我们所做的是找到我们想要的东西中存在的频率，然后将这些正弦波组合成我们想要的原始事物的近似。 在接下来的几节中，我将尝试展示傅里叶变换是如何工作的。 ## 复数¶ (https://adekau.github.io/posts/2020/llamas.html#complex-numbers) 本节将快速回顾一下什么是复数，如果你已经熟悉它们，可以跳过。复数由两部分组成：“实部”和“虚部”。这本质上是在我们已经熟悉的数上增加另一个轴来表示它们。复数写作\(3+4i\)，其中\(3\)是实部，\(4i\)是虚部。这两个部分相加形成一个复数。 复数在这里另一个有用的性质是，它们可以很容易地被视为二维向量，其中实部是标准点\((x, y)\)在二维欧几里得空间中的\(x\)坐标，虚部是\(y\)坐标。由于三角函数和复指数之间的联系，这种表示在这里非常方便。提供两者之间联系的公式被称为*欧拉恒等式*。这将在文章后面的部分进一步介绍。 ## 线性代数¶ (https://adekau.github.io/posts/2020/llamas.html#linear-algebra) 线性代数是理解我们如何使用在圆圈中旋转的向量来绘制图像的重要概念。具体来说，是我们如何用其他向量来表示向量。在标准的二维\((x, y)\)欧几里得空间中，我们可以用\(\textbf{x}\)和\(\textbf{y}\)单位向量来表示所有向量。这些通常被称为\(\hat{\textbf{i}}\)和\(\hat{\textbf{j}}\)（发音为“i-hat”和“j-hat”），其中\(\hat{\textbf{i}} = (1, 0)\)（\(x\)轴），\(\hat{\textbf{j}} = (0, 1)\)（\(y\)轴）。 为此，我们可以使用两种运算：标量乘法和向量加法。例如，向量\(\vec{a} = (5, -8)\)可以表示为： (1)¶ (https://adekau.github.io/posts/2020/llamas.html#equation-eq-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} \] 这种通过标量乘法和向量加法产生另一个向量的操作被称为一组向量的**线性组合**。在本例中，这组向量是单位向量\(\hat{\textbf{i}}\)和\(\hat{\textbf{j}}\)。 ../../_images/dotproduct-1.svg 图7 两个向量\(\vec{u}\)和\(\vec{v}\)，它们之间的夹角为\(90^{\circ}\)，长度均为\(1\)¶ (https://adekau.github.io/posts/2020/llamas.html#id7) 然而，\(\hat{\textbf{i}}\)和\(\hat{\textbf{j}}\)并不是唯一可以用来表示其他向量的向量。事实上，任何两个向量都可以通过缩放和相加来形成任何其他向量，只要它们彼此不是倍数关系。例如，\((1, -1)\)和\((-2, 2)\)就不行，因为\((-2,2) = -2 \times (1, -1)\)。 在上图中，我们有向量\(\vec{u} = (\tfrac{1}{\sqrt{2}}, \tfrac{1}{\sqrt{2}})\)和\(\vec{v} = (-\tfrac{1}{\sqrt{2}}, \tfrac{1}{\sqrt{2}})\)，它们长度为1且正交（它们之间有一个\(90^{\circ}\)角）。这两个向量中的任何一个都不能通过缩放等于另一个，这意味着它们是**线性无关的**，因此它们可以是整个二维空间的基向量。 **点积**（有时也称为“**内积**”）是确定将向量缩放多少以用所选向量来表示它们的方法。为了将上图中的向量\(\vec{\textbf{w}} = (0.7, 1.2)\)用向量\(\vec{u}\)和\(\vec{v}\)表示，我们需要找出将它们乘以什么数才能形成线性组合\(\vec{w} = c_1\cdot \vec{u} + c_2\cdot \vec{v}\)。具体来说，我们需要的常数乘子\(c_1\)和\(c_2\)来自点积。 思考这个概念的另一种方式是，点积回答了“\(\vec{w}\)中有多少\(\vec{u}\)？”这个问题。这种直觉在后面我们探讨傅里叶变换背后的数学时将会很重要。 无论如何，我们可以通过计算\(\vec{w}\)和\(\vec{u}\)的点积来找出\(c_1\)，另外请注意顺序并不重要（例如，\(\langle\vec{u},\vec{w}\rangle = \langle\vec{w},\vec{u}\rangle\)）。 (2)¶ (https://adekau.github.io/posts/2020/llamas.html#equation-eq-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} \] 所以我们需要将\(\vec{u}\)缩放\(1.3435\)倍，这意味着它将被拉伸为原始大小的\(1.3435\)倍。因此，\(\vec{w}\)的\(\vec{u}\)分量（\(c_1\)）是\(1.3435\)。 (3)¶ (https://adekau.github.io/posts/2020/llamas.html#equation-eq-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} \] 类似地，我们需要将\(\vec{v}\)缩放\(0.353553\)倍，这意味着它将被收缩（或压缩）为原始大小的\(0.353553\)倍。因此，\(\vec{w}\)的\(\vec{v}\)分量（\(c_2\)）是\(0.353553\)。 最终我们得到的线性组合是： (4)¶ (https://adekau.github.io/posts/2020/llamas.html#equation-eq-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} \] 这确实等于我们原始的向量\(\vec{w}\)。 ../../_images/dotproductW-1.svg 图8 \(\vec{u}\)和\(\vec{v}\)的线性组合产生\(\vec{w}\)¶ (https://adekau.github.io/posts/2020/llamas.html#id8) 任意两个向量的点积定义为： (5)¶ (https://adekau.github.io/posts/2020/llamas.html#equation-eq-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} \] 其中\(\theta\)是\(v_1\)和\(v_2\)之间的夹角，\(\|\vec{v}\|\)是向量的大小。大小也称为**范数**，定义为\(\|\vec{v}\| = \sqrt{\{v\}_x^2 + \{v\}_y^2}\)。这个方程看起来可能很熟悉，那是因为它就是我们都在K-12数学课上学过的毕达哥拉斯定理。 ../../_images/pythagthm-1.svg 图9 毕达哥拉斯三角形¶ (https://adekau.github.io/posts/2020/llamas.html#id9) 点积还有一些重要的性质，使它在我们的情况下很有用。首先，任何向量与自身的点积是该向量模的平方（\(\vec{v_1}\cdot \vec{v_1} = \|\vec{v_1}\|^2\)）。例如， (6)¶ (https://adekau.github.io/posts/2020/llamas.html#equation-eq-6) \[ \begin{equation} \langle[5, 7], [5, 7]\rangle = \sqrt{5^2 + 7^2}^2 = \sqrt{74}^2 = 74 \end{equation} \] 其次，相互垂直的向量（相交形成直角）的点积为\(0\)。这是因为\(\cos(\frac{\pi}{2}) = 0\)。因此，对于互相垂直的\(\vec{v_1}, \vec{v_2}\)，你得到的结果是： (7)¶ (https://adekau.github.io/posts/2020/llamas.html#equation-eq-7) \[ \begin{equation} \langle\vec{v_1},\vec{v_2}\rangle = \|\vec{v_1}\| \times \|\vec{v_2}\| \times 0 = 0 \end{equation} \] 根据我们之前的直觉“\(\vec{v_2}\)中有多少\(\vec{v_1}\)”，结果为\(0\)是合理的，因为这两个向量是正交的。 ## 连续函数的内积¶ (https://adekau.github.io/posts/2020/llamas.html#inner-products-of-continuous-functions) 上一节的点积是针对两个向量的，但这个定义可以扩展到也适用于连续函数。关键区别在于所执行的求和类型。如前所述，二维点积的公式是： (8)¶ (https://adekau.github.io/posts/2020/llamas.html#equation-eq-8) \[ \begin{equation} \langle\vec{a},\vec{b}\rangle = \{a\}_x \times \{b\}_x + \{a\}_y \times \{b\}_y \end{equation} \] 或者更准确地说，是两个向量同类项的求和，其中向量的长度是有限的（在这种情况下是\(2\)），所以求和是离散的。对于任何维度，这个方程的另一种写法是： (9)¶ (https://adekau.github.io/posts/2020/llamas.html#equation-eq-9) \[ \begin{equation} \langle\vec{a},\vec{b}\rangle = \sum_{n =1}^{N}\{a_n\times b_n\} \end{equation} \] 其中\(N\)是维度。这里的西格玛符号求和是在一个离散区间上的求和。例如，在三维空间中，求和是在区间\([1, 3]\)上进行的。然而，这种求和仅适用于\(\mathbb{R}^n\)中的向量。 对于长度为\(n\)的复向量\(\mathbb{C}^n\)，公式非常相似。我们只需要取第二个向量的共轭。 (10)¶ (https://adekau.github.io/posts/2020/llamas.html#equation-eq-10) \[ \begin{equation} \langle\vec{a},\vec{b}\rangle = \sum_{n = 1}^{N}\{a_n\times \overline{b_n}\} \end{equation} \] 需要注意的是，这里的复共轭使得这个公式“对第二个参数是反线性的”，也就是说\(\vec{a}\cdot(\vec{b}+\vec{c})=\vec{a}\cdot \vec{b} + \vec{a}\cdot \vec{c}\)。然而，在标量乘法中，它不是线性的，相反我们必须提取标量的共轭，\(\vec{a}\cdot(b\times \vec{c})=\overline{b}\times (\vec{a}\cdot \vec{c})\)。但它对第一个参数是线性的，这意味着当你从内积的第一个参数中提取一个标量倍数时，你不需要取该标量的共轭。一般来说，它对你取共轭的参数是反线性的，而对另一个参数是线性的。 我们需要一种可以在连续区间上执行的求和，其中求和区间可以无限小。这听起来像是积分的完美用例。 (11)¶ (https://adekau.github.io/posts/2020/llamas.html#equation-eq-11) \[ \begin{equation} \langle f(t),g(t)\rangle = \frac{1}{T}\int_0^T\{f(t)\overline{g(t)}dt\} \end{equation} \]