HN 日本語サマリー

← 一覧へ戻る
科学・技術

フーリエ解析:円を使ってラマを描く

Fourier Analysis: Drawing Llamas with Circles (adekau.github.io)

79 pointsby cebert11 コメント

要約

この記事では、フーリエ解析を用いて複雑な図形を描画する手法について解説しています。時間領域の信号を周波数領域に変換するフーリエ変換の概念を応用し、複数の回転する円(エピサイクル)を組み合わせることで、線、四角形、魚、さらにはラマのような複雑な形状を描き出す方法を示しています。数学的な背景として、複素数と線形代数の概念にも触れ、フーリエ変換の仕組みを直感的に理解できるように説明しています。

全文翻訳

フーリエ解析:円を使ってラマを描く

フーリエ変換は、入力信号を時間領域から周波数領域に変換する手法です。オーディオエンジニアが楽曲中の不要な周波数を特定し、逆フーリエ変換でそれを取り除くといった、非常に幅広い応用があります。デジタル画像処理では、ガウシアンブラーのようなフィルタリングや、JPEG形式での画像圧縮にも利用できます。そして、この記事で詳しく解説するように、「描画」にも応用できます。

「描画」とはどういうことでしょうか?それは、鉛筆を紙から離さずに、魚、円周率の記号、あるいは描けるあらゆるものをスケッチするようなパス(経路)を考え、それを異なる周波数で回転する多数の円のベクトルを先端から繋げることで表現するという考え方です。最後のベクトルの先端が、元のスケッチ、あるいはそれに非常に近いものを描画します。

以下にその例をいくつか示します。

[画像: ../../_images/line.gif]

Fig. 1 円で直線を引く

このように、直線とは正反対とも言える形状を使って直線を描くことができます。円を調整することで、描画される形状を変更できます。例えば、外側の円の半径を小さくし、回転速度を速くすると、正方形を描くことができます。

[画像: ../../_images/square.gif]

Fig. 2 正方形

では、3つ目の円を追加するとどうなるでしょうか?曲線がより洗練されるようになります。3つ目の円を使うと、魚のような曲線を描くことができます。

[画像: ../../_images/fish.gif]

Fig. 3 魚。

円が他の円に繋がっていくことで可能になることの、より極端な例として、ここでは1024個の円(それぞれ異なる周波数、半径、初期角度を持つ)を使って描画されたラマを示します。一般的に、(ほとんどの)閉じた曲線は、エピサイクルと呼ばれる円を使って描画することができます。

[画像: ../../_images/llama.gif]

Fig. 4 ラマ?[画像: ¶]

一般的に、円の数を増やすほど、より複雑な描画が可能になります。また、同じ描画に対して円の数を増やすほど、元の「入力」スケッチに近づきます。このアニメーションがどのように生成されるかを理解するには、フーリエ変換(およびフーリエ級数)の背後にある数学と直感について掘り下げる必要があります。前述したように、異なる曲線を描くために円で変更できる条件は3つあります。それは、回転する速度(周波数)、円の大きさ(半径)、そして開始角度(位相)です。これら3つの条件は、単一の複素数で表現できます。

ここでは、円を追加することが最終的な描画にどのような影響を与えるかを視覚化できる、インタラクティブな例を示します。

フーリエ変換

まず、フーリエ変換が何であるかの簡単な概要を説明します。これは時間領域から周波数領域への変換です。これはどういう意味でしょうか?もし関数が (\sin(2\pi\times 3t)) である場合、その (\sin(2\pi\times 3t)) 関数のフーリエ変換は、周波数 (\pm 3\text{hz}) における単一のスパイクになります。

[画像: ../../_images/sin2pi3t-2.svg]

Fig. 5 (\sin(2\pi\times 3t)) のグラフ

[画像: ../../_images/fft_sin2pi3t-3.svg]

Fig. 6 周波数領域における (\sin(2\pi\times 3t)) の大きさ

予想通り、周波数 (3\text{hz}) と (-3\text{hz}) にスパイクがあります。本質的に、私たちは変換したい対象にどのような周波数が含まれているかを見つけ、それらのサイン波を組み合わせて元の対象の近似を作成しています。次のセクションでは、フーリエ変換がどのように機能するかを示していきます。

複素数

このセクションでは、複素数が何であるかの簡単な復習を行います。既に理解している場合はスキップできます。複素数は、「実部」と「虚部」の2つの部分から構成されます。これは、私たちが既に慣れ親しんでいる数に、表現するための別の軸を追加するようなものです。

複素数は (3+4i) のように記述され、ここで (3) が実部、(4i) が虚部です。これら2つの別々の部分は、加算されて複素数を形成します。

ここで複素数のもう一つの便利な性質は、実部を (x)、虚部を (y) とする標準的な点 ((x, y)) のような2次元ベクトルとして簡単に考えることができることです。この表現は、三角法と複素指数関数の関連性から、ここで非常に便利です。この2つを結びつける公式は、オイラーの等式として知られています。これは記事の後のセクションでさらに詳しく説明します。

線形代数

線形代数は、円で回転するベクトルを使って絵を描く方法を理解する上で重要な概念です。具体的には、ベクトルを他のベクトルの観点からどのように表現できるかということです。標準的な2D ((x, y)) ユークリッド空間では、すべてのベクトルを (\textbf{x}) および (\textbf{y}) の単位ベクトルで表現できます。これらは通常、(\hat{\textbf{i}}) と (\hat{\textbf{j}})(「iハット」と「jハット」と発音)と呼ばれ、(\hat{\textbf{i}} = (1, 0))(x軸)、(\hat{\textbf{j}} = (0, 1))(y軸)です。これを行うために、スカラー倍と加算という2つの操作を使用できます。例えば、ベクトル (\vec{a} = (5,-8)) は次のように表現できます。

(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}\n]

このスカラー倍とベクトルの加算によって別のベクトルを生成することは、ベクトルの集合の線形結合として知られています。この例では、ベクトルの集合は単位ベクトル (\hat{\textbf{i}}) と (\hat{\textbf{j}}) です。

[画像: ../../_images/dotproduct-1.svg]

Fig. 7 2つのベクトル、(\vec{u}) と (\vec{v}) で、それらの間の角度は (90^{\circ}) で、両方の長さは (1)

しかし、(\hat{\textbf{i}}) と (\hat{\textbf{j}}) だけが他のベクトルを表現するために使用できるベクトルではありません。実際、2つのベクトルが互いの倍数でない限り、任意の2つのベクトルをスケーリングして加算することで、他の任意のベクトルを形成できます。例えば、((1,-1)) と ((-2, 2)) は有効ではありません。なぜなら ((-2,2) = -2 \times (1,-1)) だからです。上の図では、長さが1で直交する(間に (90^{\circ}) の角度を持つ)ベクトル (\vec{u} = (\tfrac{1}{\sqrt{2}},\tfrac{1}{\sqrt{2}})) と (\vec{v} = (-\tfrac{1}{\sqrt{2}}, \tfrac{1}{\sqrt{2}})) があります。これらのどちらのベクトルも、もう一方の倍数にすることはできないため、線形独立であり、したがって2D空間全体の基底ベクトルとなり得ます。

内積(または「ドット積」とも呼ばれる)は、選択したベクトルに基づいてそれらを表現するために、どの数値をスケーリングするかを決定する方法です。上記の図のベクトル (\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}) はどれだけ含まれているか?」という問いに答えます。この直感は、後でフーリエ変換の数学に入る際に重要になります。いずれにせよ、(c_1) を求めるには、(\vec{w}) と (\vec{u}) の内積を取ります。順序は関係ないことにも注意してください(例:(\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}\n]

したがって、(\vec{u}) を (1.3435) の係数でスケーリングする必要があるため、元のサイズの (1.3435) 倍に引き伸ばされます。したがって、(\vec{w}) の (\vec{u}) 成分((c_1))は (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}\n]

同様に、(\vec{v}) を (0.353553) の係数でスケーリングする必要があるため、元のサイズの (0.353553) 倍に縮小(または圧縮)されます。したがって、(\vec{w}) の (\vec{v}) 成分((c_2))は (0.353553) になります。

線形結合は次のようになります。

(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}\n]

これは確かに元のベクトル (\vec{w}) と等しくなります。

[画像: ../../_images/dotproductW-1.svg]

Fig. 8 (\vec{w}) を生成するための (\vec{u}) と (\vec{v}) の線形結合

任意の2つのベクトルの内積は次のように定義されます。

(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}\n]

ここで (\theta) は (v_1) と (v_2) の間の角度、(|\vec{v}|) はベクトルの大きさ(ノルム)です。大きさはノルムとしても知られ、(|\vec{v}| = \sqrt{{v}_x^2 + {v}_y^2}) と定義されます。この式はおそらく見覚えがあるでしょう。それは、K-12の数学の授業で習ったピタゴラスの定理に他ならないからです。

[画像: ../../_images/pythagthm-1.svg]

Fig. 9 ピタゴラスの定理の三角形

内積には、このケースで役立ついくつかの重要な性質もあります。第一に、任意のベクトルとそれ自身の内積は、ベクトルの大きさの2乗です((\vec{v_1}\cdot \vec{v_1} = |\vec{v_1}|^2)。例えば、

(6)\
[ \begin{equation}\langle[5, 7],\ [5, 7]\rangle = \sqrt{5^2 + 7^2}^2 = \sqrt{74}^2 = 74\end{equation} \n]

第二に、互いに垂直な(交差する際に直角をなす)ベクトルの内積は (0) です。これは (\cos(\frac{\pi}{2}) = 0) であるためです。したがって、(\vec{v_1}, \vec{v_2}) が垂直である場合、

(7)\
[ \begin{equation}\langle\vec{v_1},\vec{v_2}\rangle = |\vec{v_1}|\times |\vec{v_2}|\times 0 = 0\end{equation} \n]

「(\vec{v_2}) の中に (\vec{v_1}) はどれだけ含まれているか」という以前の直感からすると、これらの2つのベクトルは直交しているため、内積が (0) になるのは理にかなっています。

連続関数の内積

前のセクションの内積は2つのベクトルの内積でしたが、この定義は連続関数にも有効なように拡張できます。主な違いは、実行される合計の種類にあります。前述したように、2D内積の公式は

(8)\
[ \begin{equation}\langle\vec{a},\vec{b}\rangle = {a}_x \times {b}_x + {a}_y \times {b}_y\end{equation} \n]

または、より正確には、有限の長さ(この場合は (2))のベクトルの対応する項の合計であり、合計は離散的です。任意の次元に対するこの方程式の別の書き方は次のとおりです。

(9)\
[ \begin{equation}\langle\vec{a},\vec{b}\rangle = \sum}_{n =1}^{N}{a_n\times b_n}\end{equation} \n]

ここで (N) は次元です。このシグマ記法による合計は、離散的な区間に対する合計です。例えば、3D空間では、合計は ([1, 3]) の区間で行われます。ただし、この合計は (\mathbb{R}^n) のベクトルにのみ有効です。長さ (n) の複素ベクトル (\mathbb{C}^n) の公式は非常に似ています。2番目のベクトルの共役を取るだけで済みます。

(10)\
[ \begin{equation}\langle\vec{a},\vec{b}\rangle = \sum}_{n = 1}^{N}{a_n\times \overline{b_n}}\end{equation} \n]

ここで複素共役を取ることで、この公式が「第2引数において反線形」になることに注意してください。つまり、(\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}))。ただし、第1引数においては線形であるため、内積の第1引数からスカラー倍を外に出す際にスカラーの共役を取る必要はありません。一般に、複素共役を取る引数においては反線形であり、もう一方の引数においては線形になります。

私たちが求めているのは、合計区間が無限に小さくなり得る連続的な区間に対して実行できる合計の種類です。これは積分に最適な用途のように思えます。

(11)\
[ \begin{equation}\langle f(t),g(t)\rangle = \frac{1}{T}\int_0^T{f(t)\overline{g(t)}dt}\end{equation} \n]

ここでの唯一の制約は、関数 (f(t)) と (g(t)) が区間 ([0,T]) 上で平方積分可能であること、つまり、関数の絶対値の2乗を積分した値が ([0, T]) 上で有限であることです。

(12)\
[ \begin{equation}f(t) \in L^2(0,T)\quad\text{if}\quad\int_0^T{|f(t)|^2dt}\quad\text{is finite.}\end{equation} \n]

注記

(L^2) は平方積分可能な関数の集合であり、(L^2(0, T)) は区間 ([0, T]) 上で平方積分可能な関数の集合です。

これをもう少し馴染みやすく、以前の2D空間での内積の定義に似た形にするために、この積分をリーマン和(シグマ記法)のように書くことができます。

(13)\
[ \begin{equation}\frac{1}{T}\int_0^T{f(t)g(t)dt} = \lim}{N\to\infty} \frac{1}{T}\sum}{k=0}^{N}{f(\frac{T\times k}{N})\times \overline{g(\frac{T\times k}{N})}\times\frac{T}{N}}\end{equation} \n]

ここで (\dfrac{T}{N}) は、この場合の (dt) に相当します。これは、各ステップが掛けられる無限に小さい部分です。関数 (f) と (g) は、積分区間内のパラメータとなる値を受け取ります。低いステップ((k = 0, 1, 2) など)では (\frac{T\times k}{N}) は (0) に非常に近く、したがって引数も (0) に近くなります。一方、(k) が (N) に近づくと、(\frac{T\times k}{N}) は (1) に近くなり、結果として (T) に近くなります。

複素指数関数をサインとコサインで表す

複素指数関数は、サインとコサインを簡単に扱うための便利な方法を提供します。三角法と複素平面の間には驚くべき関連性があります。その関連性を記述する公式は、オイラーの等式と呼ばれます。以下に、複素数セクションで約束したオイラーの等式の公式を示します。

(14)\
[ \begin{equation}e^{ix} = \cos(x) + i \times \sin(x)\end{equation} \n]

ここで (x) は円周上をどれだけ移動するかを表します。例えば、(e^{\frac{\pi}{4} i}) は円周上を (\frac{\pi}{4}) ラジアン移動し、(\frac{\sqrt{2}}{2} + \frac{\sqrt{2}}{2}i) に到達します。さらに、(e^{\pi i}) は円周上を (\pi) ラジアン移動し、(-1 + 0i) に到達します。これはオイラーのもう一つの有名な等式です。

(15)\
[ \begin{equation}e^{\pi i} = -1\end{equation} \n]

[画像: ../../_images/e-ix-1.gif]

Fig. 10 (e^{ix}) と三角法の相関

なぜこれが成り立つのでしょうか?虚数に (e) を累乗すると、単位円周上の回転がどのように引き起こされるのでしょうか?その答えは物理学にあります。時刻 (t) における位置 (p) が

(16)\
[ \begin{equation}p(t)=e^{it}\end{equation} \n]

である場合、その点の速度は (p(t)) の最初の導関数になります。

(17)\
[ \begin{equation}v(t)=\frac{dp}{dt}=i\times e^{it}\end{equation} \n]

これで十分です!速度は位置と同じですが、実数ではなく虚数です。(i) を掛けることは、反時計回りに (90^{\circ}) 回転することに似ています。例えば、(a\in\mathbb{R}) がある場合、(i\times a) は (a) が虚軸上にあった値になります。しかし、(a) が既に虚数であった場合はどうでしょうか?その場合、(a = i\times k)(ここで (k) は何らかの実数)となります。(a) を (i) で掛けることは (i\times a = i^2\times k) となります。(i) の定義から (i^2) は (-1) であることがわかるので、(i\times a = -k) となります。これは実数の否定に過ぎないので、(180^{\circ}) の回転です。(i) を掛けることが (90^{\circ}) 回転することに似ているので、速度関数は常に現在の位置の方向に対して垂直になります。これにより描画される曲線は円になり、それが (f(t)=e^{it}\enspace \text{where}\enspace t\in [[0, 2\pi]]) が円を描く理由です。

また、次のことも注目してください。

(18)\
[ \begin{equation}\frac{1}{2\pi}\int_0^{2\pi}{\cos(t)\sin(t),dt}=0\end{equation} \n]

(\cos{t}) と (\sin{t}) は直交関数であるため、(\cos) と (\sin) はフーリエ変換の基底となります。

[画像: ../../_images/cos-sin-orthogonal.png]

Fig. 11 (\cos) と (\sin) が直交関数であることを示す

したがって、本質的に行っていることは、2次元複素数空間 ((1,0), (0, 1)i) から、基底関数 ((...,e^{i\frac{-4\pi}{T}t}, e^{i\frac{-2\pi}{T}t}, 1, e^{i\frac{2\pi}{T}t}, e^{i\frac{4\pi}{T}t},...)) を持つ無限次元空間への基底変換です。これは、複素数を生成する関数から、無限次元複素ベクトルを生成する新しい関数へのマッピングを意味します。これは、オイラーの公式を使用して基底を ((...,\cos(\frac{-2\pi}{T}),\sin(\frac{-2\pi}{T}),1,\cos(\frac{2\pi}{T}), \sin(\frac{2\pi}{T}),...)) に変換することによっても、(\mathbb{R}) 上の無限次元基底として表すことができます。これは線形演算であるため、ある関数空間から別の関数空間へのマッピングであるため、線形演算子と呼びます。

方形波の近似

[画像: ../../_images/square_wave.svg]

Fig. 12 方形波

方形波は、信号処理の世界における「Hello, World!」のようなものです。方形波は、([-\pi, \pi]) の周期波であり、周期の半分が「オン」((1))で、半分が「オフ」((0))であると定義されます。

(19)\
[ \begin{equation}\text{square}(t)= \text{sgn}(\sin{(t)})\end{equation} \n]

ここで sgn は符号関数であり、次のように定義されます。

(20)\
[\begin{split} \begin{equation}\text{sgn}(x)=\begin{cases}1 &\text{if}; x>0 \ 0 &\text{if}; x=0 \ -1 &\text{if}; x<0 \end{cases}\end{equation} \end{split}\n]

したがって、方形波の (k) 番目のフーリエ係数を見つけるために、(方形波関数と (k) 番目の基底項の内積、上記の線形代数セクションで説明した2Dベクトルの基底変換と同じ)積分を行うことができます。

(21)\
[ \begin{equation}c_k=\int[-\pi\rbrack^{\pi}{\text{sgn}(\sin (t))e^{-i k t}dt}\end{equation} \n]

注記

(e^{-i \frac{2\pi}{T} k t}) の (\frac{2\pi}{T}) の項は、(T=2\pi) のため消滅します。

符号関数は不連続であるため、符号関数の各ケースに対して積分を新しい積分に分割する必要があります。

[画像: ../../_images/sin.svg]

Fig. 13 (-\pi) から (\pi) の区間におけるサイン波

([-\pi, 0]) の間では (\sin(t)) の符号は負であり、(0) では (0)、([0, \pi]) の間では正であることがわかります。したがって、分割された積分は次のようになります。

(22)\
[ \begin{equation}c_k=\frac{1}{2\pi}\int[-\pi\rbrack^{0}{-1\times e^{-i k t}dt}+\frac{1}{2\pi}\int_0^0{0\times e^{-i k t}dt}+\frac{1}{2\pi}\int_0^{\pi}{1\times e^{-i k t}dt}\end{equation} \n]

中央の項は区間が ([0, 0]) で被積分関数が (0) であるため消滅し、次のようになります。

(23)\
[ \begin{equation}c_k=\frac{1}{2\pi}\int[-\pi\rbrack^{0}{-e^{-i k t}dt}+\frac{1}{2\pi}\int_0^{\pi}{e^{-i k t}dt}\end{equation} \n]

最初の被積分関数から (-1) を外に出すことができるため、これはさらに単純化できます。

(24)\
[ \begin{equation}c_k=\frac{1}{2\pi}\left(\int_0^{\pi}{e^{-i k t}dt}-\int[-\pi\rbrack^{0}{e^{-i k t}dt}\right)\end{equation} \n]

この積分は比較的簡単に計算できます。次のことを思い出してください。

(25)\
[ \begin{equation}\int{e^{i x}dx}=-i e^{i x} + C\end{equation} \n]

ここでは定数項を無視して (-i e^{i x}) を使用します。(k) は定数であるため、割られます。結果は次のようになります。

(26)\
[\begin{split} \begin{equation} \begin{aligned} \frac{1}{2\pi}\left(\int_0^{\pi}{e^{-i k t}dt}-\int[-\pi\rbrack^{0}{e^{-i k t}dt}\right) &=\frac{1}{2\pi}\left(\frac{i e^{-i k t}}{k}\bigg\rvert[0\rbrack^{\pi} - \frac{i e^{-i k t}}{k}\bigg\rvert[-\pi\rbrack^{0} \right)\ &=\frac{1}{2\pi}\left\lbrack\left(\frac{ie^{-i k \pi}}{k}-\frac{i}{k}\right)-\left(\frac{i}{k}-\frac{ie^{i k \pi}}{k} \right) \right\rbrack \ &= \frac{1}{2\pi}\left(\frac{ie^{-i k \pi}-i}{k}-\frac{i+ie^{i k \pi}}{k}\right) \ &= \frac{1}{2k\pi}\left(ie^{-ik\pi}+ie^{ik\pi}-2i\right) \ &= \frac{i\left(e^{-ik\pi}+e^{ik\pi}-2\right)}{2k\pi} \end{aligned} \end{equation} \end{split}\n]

しかし、この公式には大きな問題があります。(k=0) の値が必要です。この公式で (k=0) とすると、(0) による除算となり、これは実行できません。そのため、(k=0) の場合と (k\not = 0) の場合で (c_k) を定義する必要があります。((26)) に (0) を代入すると (c_0) が得られます。

(27)\
[\begin{split} \begin{equation} \begin{aligned} c_0 &= \frac{1}{2\pi}\left(\int_0^{\pi}{e^{-i 0 t}dt}-\int[-\pi\rbrack^{0}{e^{-i 0 t}dt}\right)\ &= \frac{1}{2\pi}\left( \int_0^\pi{1dt} - \int[-\pi\rbrack^0{1dt} \right) \ &= \frac{1}{2\pi}\left( t\big\rvert[0\rbrack^\pi - t\big\rvert[-\pi\rbrack^0 \right)\ &= \frac{1}{2\pi}\left\lbrack (\pi-0)-(0+\pi) \right\rbrack \ &= \frac{1}{2\pi}(\pi - \pi) \ &= 0 \end{aligned} \end{equation} \end{split}\n]

これで両方のケースが定義されたので、区分関数として記述できます。

(28)\
[\begin{split} \begin{equation} c_k = \begin{cases} 0  &\text{if}; k=0 \ \cfrac{i\left(e^{-ik\pi}+e^{ik\pi}-2\right)}{2k\pi} &\text{if};k\not = 0 \end{cases} \end{equation} \end{split}\n]

これが (k) 番目の係数に対する最終的な方程式です。(k) にいくつかの値を代入して結果を見てみましょう。

(29)\
[\begin{split} \begin{equation}\begin{aligned} c_{-3}&=\frac{2i}{3\pi}\c_{-2}&=0\c_{-1}&=\frac{2i}{\pi}\c_0 &= 0\ c_1 &= -\frac{2i}{\pi}\c_2 &= 0\c_3&=-\frac{2i}{3\pi} \end{aligned}\end{equation} \end{split}\n]

正の対応する (c_k) と負の対応する (c_k) が同じ大きさで逆方向を持つことに注目してください。それでは、元の方形波関数を近似するグラフを作成できる方程式を得るために、各 (c_k) 係数に (e^{i k t}) を掛けたものを合計します。

(30)\
[\begin{split} \begin{equation} \begin{aligned} f(t) &=\sum}_{k=-3}^3{c_k \times e^{i k t}}\ &= \frac{2i}{3\pi}e^{-3it}+0+\frac{2i}{\pi}e^{-1it}+0-\frac{2i}{\pi}e^{1it}+0-\frac{2i}{3\pi}e^{3it}\ &= \frac{2i}{\pi}e^{-1it}-\frac{2i}{\pi}e^{1it}-\frac{2i}{3\pi}e^{3it}+\frac{2i}{3\pi}e^{-3it}\ &= \frac{2i}{\pi}\left(e^{-it}-e^{it}\right)+\frac{2i}{3\pi}\left(e^{-3it}-e^{3it}\right) \end{aligned} \end{equation} \end{split}\n]

この方程式は複雑に見えますが、次の恒等式を使用すると、さらに大幅に単純化できます。

(31)\
[\begin{split} \begin{equation} \begin{aligned} e^{-ikt}-e^{ikt} &= (\underbrace{\cos(-kt)}\limits_{\cos(-x) = \cos(x)}+i\underbrace{\sin(-kt)}\limits_{\sin(-x) = -\sin(x)})-(\cos(kt)+i\sin(kt)) \ &= (\cos(kt)-i\sin(kt))-(\cos(kt)+i\sin(kt))\ &= -2i\sin(kt) \end{aligned} \end{equation} \end{split}\n]

複素指数の差を虚数サイン成分に変換する上記の恒等式を使用すると、次の単純化が得られます。

(32)\
[\begin{split} \begin{equation} \begin{aligned} \frac{2i}{\pi}\left(e^{-it}-e^{it}\right)+\frac{2i}{3\pi}\left(e^{-3it}-e^{3it}\right) &= \underbrace{\frac{2i}{\pi}(-2i\sin(t))}\limits_{2i\times -2i = 4;\text{since};i^2=-1}+\frac{2i}{3\pi}(-2i\sin(3t))\ &= \frac{4}{\pi}\sin(t) + \frac{4}{3\pi}\sin(3t) \end{aligned} \end{equation} \end{split}\n]

これは、新しい方程式に虚数項が含まれなくなったため、はるかにすっきりします。これで、これをプロットして、元の方形波関数をどれだけうまく近似できるかを確認できます。

[画像: ../../_images/MathematicaSquareWaveApprox1-1.png]

まだ完全な方形波ではありませんが、アイデアとしては、上記と同じ方法で見つかったサイン波をさらに追加していくと、追加するサイン波の数が無限大に近づくにつれて方形波が得られるということです。これはフーリエ級数と呼ばれます。なぜなら、元の関数に収束するサイン波の無限和だからです。次の図を見ると、(7) 個の係数から (51) 個に増やすと、近似がはるかに良くなることがわかります。

[画像: ../../_images/MathematicaSquareWaveApprox2.png]

関数は (2) 個のサイン波から (13) 個になります。これらの追加の (9) 個のサイン波により、グラフは実際には方形波のように見え始めています。

上記のセクションで実証されたのと同じ原則を使用して、滑らかな閉曲線として表現できる限り、望むほとんどすべてのものを描画できます。ラマを表す関数を取得する方法については、2つの方法があります。ベクターグラフィックスプログラムでラマを描画し、SVGとしてエクスポートしてSVGを使用できます。SVGは数学的に定義された曲線(線、ベジェ曲線など)であるためです。または、そのSVGを取得し、均等に間隔を空けた点でサンプリングしてサンプル点のリストを取得し、それらのサンプル点に対して離散フーリエ変換(DFT)を実行してフーリエ係数を取得することもできます。この記事では、より直接的な方法である後者の方法を選択します。

const numSamples = 400;
let pts = [];

async function entry() {
    const svgUrl = './images/llama.svg';
    const response = await fetch(svgUrl);
    const text = await response.text();
    pts = await sampleSvgPoints(text, numSamples);
}

entry();

// 必ずしも numPts 個のサンプル点を正確にサンプリングするわけではありませんが、
// 近い値になります。O(N^2) DFT を使用しているため、これは問題になりません。
// FFT を使用する場合、理想的なサンプル点の数は2のべき乗であるため、懸念事項となる可能性があります。
async function sampleSvgPoints(xml: string, numPts: number): Promise<[number, number][]> {
    const parser = new DOMParser();
    const doc = parser.parseFromString(xml, 'application/xml');
    let samplePts = [];

    const paths = Array.from(doc.querySelectorAll('path'));
    const totalLength = paths.reduce((acc, v) => acc + v.getTotalLength(), 0);
    const step = (totalLength / numPts);
    paths.forEach(path => {
        const sample = [];
        const n = M.floor(path.getTotalLength());
        for (let i = 0; i < n; i += step)
            sample.push(toPt(path.getPointAtLength(i)));
        samplePts = samplePts.concat(sample);
    });
    while (samplePts.length > numPts)
        samplePts.pop();

    return samplePts;
}

function toPt(pt: SVGPoint): [number, number] {
    return [pt.x, pt.y];
}

SVGから点をサンプリングする
次に、サンプリングされた点に対して離散フーリエ変換(DFT)を実行し、方形波の場合と同様に、必要なフーリエ係数を見つけます。離散フーリエ変換の方程式は次のとおりです。

(33)\
[ \begin{equation}c_k=\frac{1}{N}\sum}_{j=0}^{N}{p(j)e^{-i\frac{2\pi}{N}kj}}\end{equation} \n]

ここで (N) は、変換したいサンプル点のリストの合計サンプル数です。この用途では、(p(k)) は配列をキーイングするだけです。例えば、(p) がサンプル点のリストである場合、JavaScriptでは単に p[k] になります。DFTは、厳密にはフーリエ級数と同じですが、ここでは (N) 個の均等に間隔を空けたサンプルを合計するのではなく、ステップ間の変化が (0) に近づく極限を取る、または同等に言えば、合計される項の数が (\infty) に近づくという考え方です。DFTはまた、時間領域の (N) 個の均等に間隔を空けたサンプル複素数を、周波数領域での表現に変換する方法です。つまり、各整数周波数の強さを決定します。これは、数セクション前の複素指数関数をサインとコサインで表すセクションで説明した、((...,e^{i\frac{-4\pi}{T}t}, e^{i\frac{-2\pi}{T}t}, 1, e^{i\frac{2\pi}{T}t}, e^{i\frac{4\pi}{T}t},...)) という (N)
次元基底への基底変換の直接的な応用です。

DFTは2つのループを使用して比較的簡単に実装できます。外側のループは各係数 (c_k) を計算し、内側のループは数値積分合計を実行して (N) で割ることで、各周波数 (k) の平均強度を取得します。このアプローチは非常に遅いですが、比較的少ない点数であれば機能します。これは (\mathcal{O}(kj)) となり、最悪の場合 (\mathcal{O}(N^2)) になります。Radix-2高速フーリエ変換(FFT)のような、平均 (\mathcal{O}(N\log(N))) のより効率的なアルゴリズムを使用すれば、はるかに高速化できますが、この記事は既に長くなっているので、これは将来の記事のトピックにできます。

import * as M from 'mathjs';

export type DFTData = M.Complex & { 
    freq: number;
    radius: number;
    phase: number;
};

export async function dft(cps: M.Complex[]): Promise<DFTData[]> {
    const X = [];
    const N = cps.length;
    for (let i = 0; i < N; i++) {
        let sum = M.complex('0');
        for (let n = 0; n < N; n++) {
            const xn = cps[n];
            const theta = -(2 * M.pi * i * n) / N;
            const c = M.complex(`${M.cos(theta)}+${M.sin(theta)}i`);
            sum = M.add(sum, M.multiply(xn, c)) as M.Complex;
        }
        const { re, im } = M.multiply(1 / N, sum) as M.Complex;
        X.push({
            re,
            im,
            freq: i,
            radius: M.sqrt((re * re) + (im * im)),
            phase: M.atan2(im, re)
        });
    }
    return X;
}

TypeScriptにおける (\mathcal{O}(N^2)) DFTの実装。

これで係数が得られたので、グラフを描画するためのパラメータ化を行うことができます。

function parameterize(cn: M.Complex[]) {
    return async (t: number): Promise<M.Complex> =>
        await sigma(k =>
            M.multiply(M.complex(cn[k - 1].re, cn[k - 1].im), 
                M.exp(M.multiply(M.i, (k - 1) * t))), [1, numSamples]) as M.Complex;
}

このラマ近似のパラメータ化からわかるように、サイン波の数が増えるにつれて、ラマをより正確に表現するようになります。これは次のアニメーションで見ることができます。「モード」とは使用される正の周波数の数を指し、(0) 周波数と対応する負の周波数も使用しています。したがって、円の数は (\text{# of modes}\times 2) になります。

[画像: ../../_images/modes.gif]

Fig. 14 ラマ近似の (1\to500) モード

このアニメーションから、低周波数でほとんどの作業が行われていることがわかります。なぜなら、すぐにラマらしくなるからです。より多くの高周波数を追加するにつれて、ラマの小さなディテールが埋め込まれ、近似が徐々に鮮明になっていきます。

記事の冒頭にある、円が整理された混沌の中でラマのアウトラインを描く画像を作成するには、各周波数の円を描画するためのコードが必要です。そのためには、最初のコードブロックに含めた (DFTData) 型に含めた半径と位相が必要です。実際のグラフィック表現には、p5.js ライブラリを使用します。コードは上記のコードブロックで定義された変数に依存することに注意してください。完全なソースコードも最後に提供します。

function draw() {
    for (let i = 0; i < complex.length; i++) {
        const cn = complex[i];
        const prevx = x;
        const prevy = y;
        const { freq, radius, phase } = cn;
        x += radius * M.cos(freq * time + phase);
        y += radius * M.sin(freq * time + phase);

        stroke(230, 85);
        noFill();
        ellipse(prevx, prevy, radius * 2);
        stroke(230, 142);
        line(prevx, prevy, x, y);
    }
    points.push(createVector(x, y));
    stroke(230);
    noFill();
    beginShape();
    for (let i =0 ; i < points.length; i++)
        vertex(points[i].x, points[i].y);
    endShape();
    if (time > M.pi * 2)
        points.pop();

    time += ((2 * M.pi) / pts.length);
}

これにより、記事の冒頭と同じアニメーションが描画されます。

[画像: ../../_images/llama.gif]

フーリエアニメーションの完全なソースコードはここで見つけることができます。

adekau/fourier

フーリエ変換による描画。GitHubでアカウントを作成してadekau/fourierの開発に貢献しましょう。

[画像] GitHub

[画像]