フーリエ変換でラマを描く
フーリエ変換は任意の閉曲線を回転する円の集まりに分解できる。1024 個の円でラマを描き、SVG のサンプリングから DFT、アニメーションまでを TypeScript で実装する。
日本語
コピー

目次
フーリエ解析:円でリャマを描く¶
フーリエ変換は、入力信号を時間領域から周波数領域へ変換する手法だ。応用範囲はきわめて広い。たとえば音響エンジニアはフーリエ変換で楽曲から不要な周波数を取り出し、逆フーリエ変換でその周波数を除いた音を得る。デジタル画像処理では、フーリエ変換を使って画像フィルタリングができる。ガウスぼかしや JPEG 圧縮がその例だ。そして最後に、これから本記事で展開するように——お絵かきである。 お絵かきとは何のことか。考え方はこうだ。何か——魚、π 記号、あるいは描けるものであればほぼ何でも——を表す一本の経路を取る。紙に鉛筆を下ろし、途中で持ち上げずに一筆で描き切る。この経路があれば、異なる周波数で円の周りを回転するベクトルを何本も端から端へつなげられ、最後のベクトルの先端が最初のスケッチを、少なくともそれにかなり近いものをなぞる。 いくつか例を挙げよう:
図 1 円で直線を描く¶
直線とはできるだけかけ離れた図形で、直線が描けるのだ。これらの円を変えれば描かれる形も変わる。たとえば外側の円の半径を小さくし、回転速度を上げると正方形が描ける。

図 2 正方形¶
では三つ目の円を加えたらどうなるか。曲線はさらに細かくなる。三つの円があれば、魚に見える曲線が描ける。

図 3 魚。¶
つなげた円だけでどこまで極端なことができるか。ここにリャマがいる。描画に 個の円を使い、それぞれが異なる周波数、半径、開始角度を持つ。一般に、(ほぼ)すべての閉曲線は円で描ける。これらの円をエピサイクルと呼ぶ。

図 4 リャマ?!¶
一般に、円を増やすほど描ける図形は複雑になる。同じ絵に対しては、円を増やすほど元の「入力」図形に近づく。このアニメーションがどう成り立っているかを理解するには、フーリエ変換(およびフーリエ級数)の背後にある数学と直観を掘り下げる必要がある。前述のとおり、円で異なる曲線を描くには三つの条件を調整できる。回転する速さ(周波数)、円の大きさ(半径)、そして開始角度(位相)だ。この三つはすべて一つの複素数で表せる。
次の例は自分で動かして、円を増やすことが最終的な図形に与える影響を体感してみてほしい。
フーリエ変換¶
だがその前に、まずフーリエ変換とは何かを簡単に説明しておくべきだろう。時間領域から周波数領域への変換だ。どういうことか。関数 があるとして、この をフーリエ変換すると、周波数 のところに鋭いピークが現れる。
図 5 のグラフ¶
図 6 の周波数領域における振幅。¶
案の定、周波数 と にピークがある。要するに、扱いたい対象にどんな周波数が含まれるかを見つけ出し、それらの正弦波を組み合わせて元の対象の近似を作る、ということだ。以降の節で、フーリエ変換がどう働くかを見ていく。
複素数¶
この節は複素数とは何かの簡単な復習なので、すでに知っていれば飛ばしてよい。複素数は「実」部と「虚」部の二つからなる。すでに慣れ親しんだ数を取り、本質的にもう一本軸を足して表したものだ。 複素数は と書き、 が実部、 が虚部である。この二つを足し合わせて一つの複素数になる。 ここで複素数には便利な性質がある。二次元ベクトルとして扱いやすく、実部が 、虚部が で、二次元ユークリッド空間の標準的な点 に対応する。三角関数と複素指数関数の結びつきのおかげで、この表現はここでは非常に都合がよい。両者を結ぶ式をオイラーの等式と呼ぶ。本記事の後の節でさらに詳しく扱う。
線形代数¶
線形代数は、ベクトルを円の上で回転させて図形を描く仕組み、具体的にはあるベクトルを他のベクトルで表す仕組みを理解するうえで重要な概念だ。標準的な二次元 ユークリッド空間では、すべてのベクトルは と の単位ベクトルで表せる。この二つはふつう と (「i-hat」「j-hat」と読む)と書き、( 軸)、( 軸)である。これには二つの演算が使える。スカラー倍と加法だ。たとえばベクトル は次のように表せる。
(1)¶
このように、スカラー倍とベクトルの和を組み合わせて別のベクトルを作る操作を、ベクトルの線形結合と呼ぶ。この例では、そのベクトルの組は単位ベクトル と である。
図 7 2つのベクトル と 。なす角は 、長さはどちらも ¶
ただし、ほかのベクトルを表すのに使えるベクトルは と だけではない。実は、互いに倍数の関係にない2つのベクトルであれば、それぞれを拡大縮小して足し合わせることで任意のベクトルを作れる。たとえば と は使えない。 だからだ。上の図では、ベクトル と は長さが 1 で、互いに直交している(なす角が )。この2つはどちらも拡大縮小してもう一方にはなれないので線形独立であり、2次元空間全体の基底ベクトルとして使える。
内積(「ドット積」とも呼ぶ)は、選んだベクトルを使ってあるベクトルを表すとき、各ベクトルを何倍すればよいかを求めるために使う。 ベクトル (上の図を参照)を と の線形結合 として表すには、この2つのベクトルそれぞれに掛ける数を求めればよい。具体的には、内積が与えてくれるのはこの2つの係数 と そのものだ。別の言い方をすれば、内積は「 の中に がどれだけ含まれているか」という問いに答える。この直感は、Fourier 変換の背後にある数学を扱うときに重要になる。ともあれ、 と の内積を取れば が求まり、順序は関係ない(たとえば )。
(2)¶
つまり を 倍、すなわち元の長さの 倍に引き伸ばす。したがって のうち に属する成分()は である。
(3)¶
同様に、 を 倍、つまり元のサイズの 倍に縮める。よって のうち の成分()は である。
最終的に得られる線形結合は
(4)¶
これは確かに最初のベクトル に等しい。
図 8 と の線形結合で を得る¶
任意の2つのベクトルの内積は次のように定義される。
(5)¶
ここで は と のなす角、 はベクトルの大きさである。大きさはノルムとも呼ばれ、 と定義される。この式には見覚えがあるはずだ。小中学校の数学で習った三平方の定理そのものである。
図 9 直角三角形¶
内積には、ちょうど我々の役に立つ重要な性質がいくつかある。まず、任意のベクトルと自身の内積はそのベクトルの大きさの2乗に等しい()。例えば、
(6)¶
次に、互いに直交する(直角に交わる)2つのベクトルの内積は になる。 だからである。したがって、 が直交するとき、
(7)¶
先ほどの「 の中に がいくつあるか」という直感的な理解に照らせば、この結果が になるのは妥当である。この2つのベクトルは直交しているからだ。
連続関数の内積¶
前節では2つのベクトルの内積を扱ったが、この定義は連続関数に拡張できる。鍵となる違いは和の取り方にある。前述のとおり、2次元の内積の式は
(8)¶
である。より正確には、2つのベクトルの対応する項を足し合わせている。このときベクトルの長さは有限(ここでは )なので、和は離散的である。この式は任意の次元について次のようにも書ける。
(9)¶
ここで は次元である。このシグマ記号による和は離散区間上で取られる。例えば3次元空間なら、和の区間は である。ただし、この和が使えるのは のベクトルに限る。長さ の複素ベクトル の式もよく似ているが、2番目のベクトルの複素共役を取る点が異なる。
(10)¶
ここで複素共役を取ることで、この式は「2番目の引数について反線形」になる。つまり である。ただしスカラー倍について線形ではなく、スカラーの共役を外に出す必要がある。 となる。一方、1番目の引数については線形である。つまり、内積の1番目の引数からスカラー倍をくくり出すとき、そのスカラーの共役を取る必要はない。一般に、複素共役を取る側の引数について反線形、もう一方の引数について線形である。
連続区間上で和を取る必要があり、しかもその区間はいくらでも小さくできる。まさに積分の出番だ。
(11)¶
唯一の条件は、関数 と が区間 上で二乗可積分であること、つまり絶対値の二乗の積分が 上で有限であることだ。
(12)¶
注意 は二乗可積分関数の集合、 は区間 上の二乗可積分関数の集合である。
2D 空間の内積の定義に寄せて、見た目を似せるなら、この積分をリーマン和(シグマ記号)で書ける。
(13)¶
ここで が にあたり、各ステップで掛ける無限小量だ。関数 と の引数は、積分の上端 に、現在の和のステップ数と極限で近づく値を掛けたもので、これにより と の引数は常に積分区間内に収まる。ステップ数が小さいうち( など)は は に非常に近く、引数も に非常に近い。 が に近づくと は に近づき、 に近づく。
複素指数で正弦と余弦を表す¶
複素指数を使うと正弦と余弦を都合よく扱える。三角法と複素平面の間には意外な関係があり、それを表す公式がオイラーの等式だ。以下がその式で、複素数の節で約束したとおりである。
(14)¶
ここで は円をどれだけ進むかを表す。たとえば は円を ラジアン進み、 に落ち着く。また は円を ラジアン進み、 に落ち着く。これがオイラーのもう一つの有名な等式だ。
(15)¶

図 10 と三角関数の関係¶
なぜこうなるのか。 を虚数乗すると、なぜ単位円を回るのか。答えは物理にある。時刻 における位置 が
(16)¶
なら、その点の速度は の一階微分だ。
(17)¶
これで十分だ。速度は位置と同じ形をしていて、実数が虚数に変わっただけである。 を掛けることは反時計回りに 回転させることに等しい。たとえば なら、 は元の が虚軸上に移ったものだ。しかし がもともと虚数ならどうか。このとき ( はある実数)である。さらに を掛けると となる。 の定義より は なので、。これは実数の符号を反転させただけ、つまり の回転だ。 を掛けることが の回転に等しいのだから、速度関数は常に現在位置の方向と直交する。こうして描かれる曲線は円であり、 が円を描くのはそのためである。
補足
(18)¶
と は直交関数であり、これによって と がフーリエ変換の基底を成す。

図 11 は と が直交関数であることを示している。¶
本質的にここで行っているのは、2 次元複素空間 から、関数 を基底 とする無限次元空間への基底変換である。つまり、複素数を生成する関数から、無限次元の複素ベクトルを生成する新しい関数へと写像している。オイラーの公式を使って基底を に変換すれば、これは 上の無限次元基底としても表せる。線形演算であり、ある関数空間から別の関数空間への写像であることから、これを線形作用素と呼ぶ。
方形波の近似¶
図 12 方形波。¶
方形波は信号処理における「hello world」のようなものだ。方形波は 上の周期波として定義され、半周期が「オン」すなわち 、残りの半周期が「オフ」すなわち となる。
(19)¶
ここで 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 ## リャマを描く¶ 描きたいものを十分になめらかな閉曲線として表せるなら、前節で示したのと同じ原理でほとんど何でも描ける。リャマを表す関数を得る方法は 2 通りある。ベクターグラフィックスプログラムでリャマを描いて SVG として書き出し、その SVG をそのまま使う方法だ。SVG はもともと数学的に定義された曲線(直線、ベジェ曲線など)でできている。もう一つは、その SVG を等間隔にサンプリングして点列を得て、その点列に離散フーリエ変換(DFT)を適用してフーリエ係数を求める方法である。本記事では後者を採る。こちらのほうが直接的だからだ。 ``` const numSamples = 400; let pts = []; function entry() { const svgUrl = './images/llama.svg'; const response = await fetch(svgUrl); const text = await response.text(); pts = await sampleSvgPoints(text, numSamples); } entry(); // Might not sample exactly numPts number of sample points, but it will be // close. Not a concern using the O(N^2) DFT. Using FFT, that can be // concerning since the ideal number of point samples is an exponent of 2. async function sampleSvgPoints(xml: string, numPts: number): Promise { 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 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} ParseError: Expected & or \\ or \cr or \end at position 121: …\text{if}\; x #̲# リャマを描く¶ 描きたい…ここで は変換対象のサンプリング点リストに含まれる点の総数である。今回の場面では、 は要するにインデックスで配列の要素を取り出すことにあたる。たとえば がサンプリング点のリストなら、Javascript では p[k] となる。DFT とフーリエ級数は実は同じもので、違いは、等間隔の有限個のサンプリング点について和を取るか、刻み幅を に近づける極限、言い換えれば和の項数を に近づける極限を取るかにある。DFT はまた、時間領域の 個の等間隔な複素サンプリング点を周波数領域の表現に変換する方法でもあり、つまり各整数倍の正弦周波数の強度を求める。これはまさに、 次元基底 に基底変換を直接適用することであり、数節前の Complex Exponentials as Sines and Cosines の節で説明したとおりである。
DFT は 2 重ループでかなり簡単に実装できる。外側のループで各係数 を計算し、内側のループで数値積分の和を取り、 で割って各周波数 の平均強度を求める。この方法は非常に遅いが、点の数がそれほど多くないうちは使える。計算量は 、最悪の場合で である。より効率的なアルゴリズムを使えばはるかに良くできる。たとえば Radix-2 高速フーリエ変換(FFT)なら平均計算量は だが、この記事はすでに長すぎるので、それはまた別の機会の話題にとっておく。
import * as M from 'mathjs';
export type DFTData = M.Complex & {
freq: number;
radius: number;
phase: number;
};
export async function dft(cps: M.Complex[]): Promise {
const X = [];
const N = cps.length;
for (let i = 0; i
DFT implementation in TypeScript.
係数が手に入ったので、曲線をパラメータ化して描画できるようにする。
function parameterize(cn: M.Complex[]) {
return async (t: number): Promise =>
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;
}
この係数でラマを近似したとき、正弦項を増やすほどラマに近づいていくはずだ。次のアニメーションで確認できる。ここでいう「モード」は使う正の周波数の個数を指し、 の周波数と対応する負の周波数も併せて使っている。

Fig. 14 modes of a llama approximation.¶
このアニメーションを見ると、作業の大部分は低い周波数で済んでいることが分かる。すぐにラマらしい形になるからだ。高周波を足していくにつれて、細かい部分が少しずつ補われる。
In order to recreate the image at the beginning of the article, with the circles moving around in organized chaos drawing the outline of the llama, we need some code to go through and draw each frequency’s circle. To do that we need the radius and phase which we have included in the DFTData type in the first code block. To do the actual graphics representation, we’ll be using the p5.js library. Note that the code depends on variables defined in the above code blocks. I’ll also provide the full source at the end.
function draw() {
for (let i = 0; i M.pi * 2)
points.pop();
}
time += ((2 * M.pi) / pts.length);
}
これで記事冒頭のアニメーションが描ける。

Fourier アニメーションの完全なソースコードはこちら:
adekau/fourier — フーリエ変換で描く。
](https://github.com/adekau/fourier)
Index Notes on Classical & Intuistionistic Logic