フーリエ変換と画像圧縮

# はじめに
画像圧縮の際に出てくるフーリエ変換まわりの知識をまとめました。

# フーリエ級数展開
フーリエ級数展開：以下の制約を満たす関数は、振幅・周波数が異なる三角関数の足し算で近似可能。

周期$2\pi$の周期関数$f(x)$は、以下のように近似可能。

```math
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}
$$

####フーリエ級数展開の制約
1. 周期関数のみ
2. 区分的になめらか（有限個の点を除いて連続かつ微分可能）

ただし、上記の制約を満たさない場合は、

1. 周期関数のみ ⇒ 周期関数とみなして近似
2. 区分的に滑らか（有限個の点を除いて連続かつ微分可能）⇒ 滑らかでない点でギプスの現象（波形の先端が尖る現象）が発生


# フーリエ変換
フーリエ変換：フーリエ係数を求める過程を拡張して、「ある関数の周波数ごとの特性を表す関数」に変換。

フーリエ変換の式は、周波数 $\omega$ に対してどのような値（特性）を取るかを返す関数を$F(\omega)$とすると

```math
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}$）を用いてまとめると

```math
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)式において、フーリエ係数（各周波数成分をどれだけ含むか）にあたるフーリエ変換の式は

```math
フーリエ変換： F(\omega)=\int_{-\infty}^{\infty} f(t)e^{-j\omega t}dt\\
空間領域（数直線上の表現）から周波数領域（周波数による表現）へ変換
```
また、逆フーリエ変換の式は

```math
逆フーリエ変換： 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. 離散コサイン変換の結果の浮動小数点を**量子化**して整数化

```math
（量子化後の値）= [X_{u,v} / (p_{u,v}/2)] \\
\Bigr(X_{u,v}:離散コサイン変換後の値,\quad p_{u,v}:量子化幅 \Bigr)
```
###### 量子化幅
* 周波数ごとに量子化幅が違う
* ブロック左上（低周波成分）にいくにつれて量子化幅が小さい ⇒ 画像の多くを占める低周波成分を残す
* ブロック右下（高周波成分）にいくにつれて量子化幅が大きい ⇒ 画像にとって重要度の低い高周波成分をなくす

###### 4. ジグザグスキャン
量子化後のブロック内の値は、左上（低周波成分）ほど絶対値が大きくなり、右下（高周波成分）のほとんどが0になる。
そして、ブロック内を左上からジグザグにスキャンし、残りの要素が全て0となる点までいったらやめる。
この結果、ブロック内の値の総数に対して、スキャンされたデータ列の総数は取り除かれた高周波成分（量子化後0となった部分）の分だけ圧縮されたことになる。

⇒ その後、ラングレンス符号化やハフマン符号化を行う。

# 関連語句
* 空間領域：距離の空間
* 空間周波数領域：信号がどのような周波数成分を持つかを表す空間。単位長さ中に存在する明暗の縞模様の波の数（波の周波数の逆数）。電波や音波の周波数は時間軸だが、空間周波数は空間軸。

* 周波数スペクトル：元の波形を構成する周波数成分。
* 空間周波数スペクトル：周波数が空間周波数の時の空間周波数成分。

* 振幅スペクトル：（空間）周波数-振幅図。
* 位相スペクトル：（空間）周波数-位相図。

# 参考
 * [周波数領域における画像処理](http://www.clg.niigata-u.ac.jp/~medimg/practice_medical_imaging/imgproc_scion/5fourier/index.htm)
 * [フーリエ変換と画像圧縮の仕組み](https://www.slideshare.net/ginrou799?utm_campaign=profiletracking&utm_medium=sssite&utm_source=ssslideview)