はじめに
画像圧縮の際に出てくるフーリエ変換まわりの知識をまとめました。
フーリエ級数展開
フーリエ級数展開：以下の制約を満たす関数は、振幅・周波数が異なる三角関数の足し算で近似可能。
周期$2\pi$の周期関数$f(x)$は、以下のように近似可能。
f(x) = \frac{a_0}{2} + \sum_{k=1}^{\infty}(a_k\cos(kx) + b_k\sin(kx)) \tag{1}\\
\Bigr(\frac{a_0}{2}: 定数項,\quad a_k,b_k:フーリエ係数（各周波数成分をどれだけ含むか）\Bigr)
なお、
$$
a_k = \frac{1}{\pi} \int_{-\pi}^{\pi} f(x)\cos(kx)dx \qquad(k=0,1,2,...) \tag{2}
$$
$$
b_k = \frac{1}{\pi} \int_{-\pi}^{\pi} f(x)\sin(kx)dx \qquad(k=1,2,...) \tag{3}
$$
フーリエ級数展開の制約
- 周期関数のみ
- 区分的になめらか（有限個の点を除いて連続かつ微分可能）
ただし、上記の制約を満たさない場合は、
- 周期関数のみ ⇒ 周期関数とみなして近似
- 区分的に滑らか（有限個の点を除いて連続かつ微分可能）⇒ 滑らかでない点でギプスの現象（波形の先端が尖る現象）が発生
フーリエ変換
フーリエ変換：フーリエ係数を求める過程を拡張して、「ある関数の周波数ごとの特性を表す関数」に変換。
フーリエ変換の式は、周波数 $\omega$ に対してどのような値（特性）を取るかを返す関数を$F(\omega)$とすると
F(\omega) = \int_{-\infty}^{\infty} f(t)e^{-j\omega t}dt \tag{4}
フーリエ変換の簡単な導出
フーリエ級数展開を用いたフーリエ変換の導出過程
1. フーリエ級数展開の複素表現
フーリエ級数展開の式は、(1)~(3)式のようにsinとcosの両方を含み、式が煩雑なので、オイラーの公式（$e^{j\theta} = \cos{\theta} + j\sin{\theta}$）を用いてまとめると
f(x) = \sum_{k=0,\pm1}^{\pm\infty}c_ke^{jkx} ,
\qquad c_k = \frac{1}{\pi}\int_{-\pi}^{\pi}f(x)e^{-jkx}dx \tag{5}\\
\Bigr(c_k: フーリエ係数\Bigr)
2. 任意の周期への拡張
今までのフーリエ級数展開は周期を$2\pi$と仮定したが、拡張するために周期を$2\pi$から$T$へと変換する。
上式において、$T = 2\pi$とすると
$$
f(x) = \sum_{k=0,\pm1}^{\pm\infty}c_ke^{jkx} \tag{6}
$$
$$
c_k = \frac{1}{T}\int_{-T/2}^{T/2}f(x)e^{-j\frac{2\pi}{T}kx}dx \tag{7}
$$
3. 無限周期への拡張
(7)式を(6)式に代入すると
$$
f(x) = \sum_{k=0,\pm1}^{\pm\infty}\Bigr(\frac{1}{T}\int_{-T/2}^{T/2}f(x)e^{-j\frac{2\pi}{T}kx}dx\Bigr)e^{jkx} \tag{8}
$$
$T\rightarrow \infty$とすると、総和$\sum$は$2\pi /T \rightarrow \omega$を積分変数とする積分になって
$$
f(x) = \frac{1}{2\pi}\int_{-\infty}^{\infty} e^{j\omega x} \Bigr(\int_{-\infty}^{\infty} f(t)e^{-j\omega t}dt \Bigr)d\omega
\tag{9}
$$
4. フーリエ変換と逆フーリエ変換
(9)式において、フーリエ係数（各周波数成分をどれだけ含むか）にあたるフーリエ変換の式は
フーリエ変換： F(\omega)=\int_{-\infty}^{\infty} f(t)e^{-j\omega t}dt\\
空間領域（数直線上の表現）から周波数領域（周波数による表現）へ変換
また、逆フーリエ変換の式は
逆フーリエ変換： f(x)=\int_{-\infty}^{\infty} F(\omega)e^{j\omega x}d\omega\\
周波数領域から元の空間領域へ戻す変換
フーリエ級数展開とフーリエ変換の違い
- フーリエ変換では、フーリエ係数のような数値ではなく、関数として扱えるようにしている。
- フーリエ変換は、周期関数を仮定しなくてもよい。
離散フーリエ変換
離散フーリエ変換（DFT: Descrete Fourier Transform）：任意のデータ（配列）の周波数の分布を算出可能（フーリエ変換は関数に含む周波数の分布を算出可能）
コンピュータで処理を行うためには**離散的なデータ点(配列)**で処理する必要があるため、離散フーリエ変換を利用。
定義
N点からなる離散的なデータ点$x_n(n=0,1,...,N-1)$に対する離散フーリエ変換は
$$
X_k = \sum_{n=0}^{N-1} x_n e^{-j \frac{2\pi kn}{N}} \qquad
(k=0,1,...,N-1)
$$
- 離散データは微分・積分を厳密に計算できないので総和$\sum$を利用
- 有限個のデータ点なので、無限の総和を計算できない ⇒ 周期Nの周期性を仮定
- $x_n$に含まれる周波数は0~N-1までを仮定
二次元離散フーリエ変換
二次元離散フーリエ変換：離散フーリエ変換を二次元に拡張したもの。
$$
X_{u,v} = \sum_{h=0}^{H-1} \sum_{w=0}^{W-1} x_{h,w} e^{-2 \pi j \bigr(\frac{uh}{H}+\frac{vw}{W}\bigr)}
$$
- 入力は二次元のデータ点（二次元配列）
- 入力に、二次元の様々な周波数の三角関数をどれだけ含むかが分かる
- $X_{u,v}$は、縦方向に$u/2$本のピーク、横方向に$v/2$本のピークがある。
画像のフーリエ変換
フーリエ変換は2次元信号の画像にも適用可能。
しかし、
フーリエ変換の式は∞を含み、数学では∞という考えが通用するが、コンピュータは有限界の計算にする必要がある。
そこで⇒「離散的フーリエ変換」
- 離散的フーリエ変換（DFT: Descrete Fourier Transform）：コンピュータでも計算できるように制約を受けたフーリエ変換。三角関数と積和計算のみ。
ただ、DFTも計算量膨大。
そこで、
⇒「高速フーリエ変換」というアルゴリズムを考案。
- 高速フーリエ変換（FFT: Fast Fourier Transform）：DFTを高速に解くアルゴリズムで、結果はDFTと同じ。データ数は2のべき乗個の場合のみに限定。ディジタル画像のフーリエ変換は、ほぼFFT。
画像は2次元信号で、水平・垂直方向の周波数を持つ。そのため、画像に2次元FFT処理を行うときは、水平方向にFFTした後、垂直方向にFFTを行う。
画像圧縮
-
画像圧縮：二次元離散フーリエ変換により画像に含む2次元の周波数成分を調べ、周波数の偏りを利用して圧縮する。
-
画像の周波数の偏り：画像は低周波成分が多く、高周波成分が少ない。すなわち、高周波成分を削っても、画像に大きな変化はない。⇒ これを利用して圧縮。
JPEG圧縮
手順
1. 画像を8x8のブロックに分割（以降の処理はブロックごと）
2. 各ブロックを離散コサイン変換（= 離散フーリエ変換の基底関数を変えたもの）
3. 離散コサイン変換の結果の浮動小数点を量子化して整数化
（量子化後の値）= [X_{u,v} / (p_{u,v}/2)] \\
\Bigr(X_{u,v}:離散コサイン変換後の値,\quad p_{u,v}:量子化幅 \Bigr)
量子化幅
- 周波数ごとに量子化幅が違う
- ブロック左上（低周波成分）にいくにつれて量子化幅が小さい ⇒ 画像の多くを占める低周波成分を残す
- ブロック右下（高周波成分）にいくにつれて量子化幅が大きい ⇒ 画像にとって重要度の低い高周波成分をなくす
4. ジグザグスキャン
量子化後のブロック内の値は、左上（低周波成分）ほど絶対値が大きくなり、右下（高周波成分）のほとんどが0になる。
そして、ブロック内を左上からジグザグにスキャンし、残りの要素が全て0となる点までいったらやめる。
この結果、ブロック内の値の総数に対して、スキャンされたデータ列の総数は取り除かれた高周波成分（量子化後0となった部分）の分だけ圧縮されたことになる。
⇒ その後、ラングレンス符号化やハフマン符号化を行う。
関連語句
-
空間領域：距離の空間
-
空間周波数領域：信号がどのような周波数成分を持つかを表す空間。単位長さ中に存在する明暗の縞模様の波の数（波の周波数の逆数）。電波や音波の周波数は時間軸だが、空間周波数は空間軸。
-
周波数スペクトル：元の波形を構成する周波数成分。
-
空間周波数スペクトル：周波数が空間周波数の時の空間周波数成分。
-
振幅スペクトル：（空間）周波数-振幅図。
-
位相スペクトル：（空間）周波数-位相図。