# Discrete Cosine Tranform
想必大家一定對於 Discrete Fourier Transform (DFT) 已經不陌生了，再看一次 DFT 的數學式：

$$X[k]=\sum_{n=0}^{N-1} x[n]e^{-j\frac{2{\pi}kn}{N}}$$

但大家應該可能會發現到如果是把 $N$ 點的實數 (real number) 資料拿去做 $N$ 點的 DFT，結果會是 $N$ 點的複數 (complex number)，而在計算機裡面儲存一個複數需要兩個變數的空間，所以實際上 DFT 的結果需要 $2N$ 個變數來儲存結果：

$$X[k]=X_{Re}[k]+jX_{Im}[k]$$

其中 $X_{Re}[k]$ 為 $X[k]$ 的實部，而 $X_{Im}[k]$ 為 $X[k]$ 的需部。這樣的結果是不是覺得有點奇怪呢？為什麼 $N$ 點的資料經過轉換會變成 $2N$ 點的資料呢？

其實原因很簡單，就是因為在 DFT 數學式裡面和時域訊號相乘的 complex exponential ($e^{-j\frac{2\pi kn}{2N}}$)本身就是一個複數。
## 把 DFT 視為 linear transform
我們可以把 DFT 寫成 matrix form，如下：
$$X=Ax$$
其中
$$X=(X[0],\ X[1], ..., X[N-1])=\left[
\begin{matrix}
X[0] \\
X[1] \\
. \\
. \\
. \\
X[N-1]
\end{matrix}
\right]$$

$$A=\left[
\begin{matrix}
A_0^T\\
A_1^T\\
. \\
. \\
. \\
A_{N-1}^T
\end{matrix}
\right]=\left[
\begin{matrix}
e^{-j\frac{2{\pi}\cdot 0\cdot 0}{N}} & e^{-j\frac{2{\pi}\cdot 0\cdot 1}{N}} & ... & e^{-j\frac{2{\pi}\cdot 0\cdot (N-1)}{N}}\\
e^{-j\frac{2{\pi}\cdot 1\cdot 0}{N}} & e^{-j\frac{2{\pi}\cdot 1\cdot 1}{N}} & ... & e^{-j\frac{2{\pi}\cdot 1\cdot (N-1)}{N}}\\
e^{-j\frac{2{\pi}\cdot 2\cdot 0}{N}} & e^{-j\frac{2{\pi}\cdot 2\cdot 1}{N}} & ... & e^{-j\frac{2{\pi}\cdot 2\cdot (N-1)}{N}}\\
. \\
. \\
e^{-j\frac{2{\pi}\cdot (N-1)\cdot 0}{N}} & e^{-j\frac{2{\pi}\cdot (N-1)\cdot 1}{N}} & ... & e^{-j\frac{2{\pi}\cdot (N-1)\cdot (N-1)}{N}}\\
\end{matrix}
\right]$$

$$A_k=\left[
\begin{matrix}
e^{-j\frac{2{\pi}\cdot k\cdot 0}{N}}\\
e^{-j\frac{2{\pi}\cdot k\cdot 1}{N}}\\
e^{-j\frac{2{\pi}\cdot k\cdot 2}{N}}\\
. \\
. \\
e^{-j\frac{2{\pi}\cdot k\cdot (N-2)}{N}}\\
e^{-j\frac{2{\pi}\cdot k\cdot (N-1)}{N}}
\end{matrix}
\right]
$$

$$e^{-j{\frac{2\pi kn}{N}}}=\cos(\frac{2{\pi}kn}{N})-j\sin(\frac{2{\pi}kn}{N})$$

$$x=(x[0],\ x[1], ..., x[N-1])=\left[
\begin{matrix}
x[0] \\
x[1] \\
. \\
. \\
. \\
x[N-1]
\end{matrix}
\right]$$

$$X[k]=x\cdot A_k$$

$$x=\frac{1}{N}A^*X$$

$$A^*=(\bar{A})^T=\bar{(A^T)}$$

$$A=\left[
\begin{matrix}
1+j & 2-3j \\
4-9j & 3+2j
\end{matrix}
\right]$$

$$\bar{A}=\left[
\begin{matrix}
1-j & 2+3j \\
4+9j & 3-2j
\end{matrix}
\right]$$
$\bar{A}$ 為 $A$ 的 Complex conjugate

## 想辦法讓 DFT 的計算僅考量和 cos 或 sin 的投影

$X[k]=\sum_{n=0}^{N-1} x[n]e^{-j\frac{2{\pi}kn}{N}}$

$k = 0\ \ \ \ \ \ \ \ \ X[0]=\sum_{n=0}^{N-1}x[n]$

$k = 1\ \ \ \ \ \ \ \ \ X[k]=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2{\pi}kn}{N}}$

$e^{-j{\frac{2\pi kn}{N}}}=cos(\frac{2{\pi}kn}{N})-jsin(\frac{2{\pi}kn}{N})$

如果要讓 DFT 的結果僅有 real number，直覺想到的是如果只讓 $x[n]$ 在 $cos(\frac{2{\pi}kn}{N})$ 有投影量，而在 $sin(\frac{2{\pi}kn}{N})$ 沒有投影量，而 $cos(\frac{2{\pi}kn}{N})$ 是 even function，$sin(\frac{2{\pi}kn}{N})$ 為 odd function，所以只有讓 $x[n]$ 也是一個 even function，一種方法是產生一個新的 sequence：

$\hat{x}[n]=x[n]+x[2N-n-1]$ for $n=0,1,...2N-1$

這個 $\hat{x}[n]$ 的長度為 $2N$，且此序列為偶對稱 (even symmetric) 於 $n=(2N-1)/2$，因此我們要找尋長度為 $2N$ 且奇對稱 (odd symmetric) 於 $n=(2N-1)/2$ 的 sinusoidal functions，這些 functions 是 $sin(\frac{2{\pi}k(n+\frac{1}{2})}{2N})$，$\hat{x}[n]$ 和 $sin(\frac{2{\pi}k(n+\frac{1}{2})}{2N})$ 做內積結果為 0。$cos(\frac{2{\pi}k(n+{\frac{1}{2}})}{2N})$ 為長度 $2N$ 且偶對稱 (even symmetric) 於 $n=(2N-1)/2$ 的 sinusoidal functions，所以 $\hat{x}[n]$ 和 $cos(\frac{2{\pi}k(n+\frac{1}{2})}{2N})$ 做內積結果不為 0，且計算乘法時可以省略一半的計算量。

$\hat{X}[k]=\sum_{n=0}^{2N-1}\hat{x}[n]e^{-j\frac{2{\pi}kn}{2N}}$

$\hat{x}[n]=\frac{1}{2N}\sum_{k=0}^{2N-1}\hat{X}[k]e^{j\frac{2{\pi}kn}{2N}}$

$\begin{split}
\dot{X}[k] &=\sum_{n=0}^{2N-1}\hat{x}[n]e^{-\frac{2\pi k(n+0.5)}{2N}}\\
&=\sum_{n=0}^{2N-1}\hat{x}[n]e^{-\frac{2\pi kn}{2N}}e^{-\frac{2\pi k(0.5)}{2N}}\\
&=\hat{X}[k]e^{-\frac{2\pi k(0.5)}{2N}}
\end{split}$

其中 $\hat{X}[k]$ 為 $\hat{x}[n]$ 的 DFT，都是處理長度為 $2N$ 的資料。

## DCT 的推導起手式

$\begin{split}
\dot{X}[k]&=\sum_{n=0}^{2N-1}\hat{x}[n]e^{-j\frac{2{\pi}k(n+\frac{1}{2})}{2N}}\\
&=\sum_{n=0}^{N-1}\hat{x}[n]e^{-j\frac{2{\pi}k(n+\frac{1}{2})}{2N}}+
\sum_{n=N}^{2N-1}\hat{x}[n]e^{-j\frac{2{\pi}k(n+\frac{1}{2})}{2N}}\\
&=\sum_{n=0}^{N-1}\hat{x}[n]e^{-j\frac{2{\pi}k(n+\frac{1}{2})}{2N}}+
\sum_{n=0}^{N-1}\hat{x}[2N-n-1]e^{-j\frac{2{\pi}k(2N-n-1+\frac{1}{2})}{2N}}\\
&=\sum_{n=0}^{N-1}\hat{x}[n]e^{-j\frac{2{\pi}k(n+\frac{1}{2})}{2N}}+
\sum_{n=0}^{N-1}\hat{x}[n]e^{-j\frac{2{\pi}k*2N}{2N}}e^{j\frac{2{\pi}k(n+\frac{1}{2})}{2N}}\\
&=\sum_{n=0}^{N-1}\hat{x}[n](e^{-j\frac{2{\pi}k(n+\frac{1}{2})}{2N}}+e^{j\frac{2{\pi}k(n+\frac{1}{2})}{2N}})\\
&=2\sum_{n=0}^{N-1}\hat{x}[n]cos(\frac{2{\pi}k(n+\frac{1}{2})}{2N})
\end{split}$

for $k=1\sim2N-1$

## Inverse DCT 的推導
### 起手式
$\begin{split}
\hat{x}[n]&=\frac{1}{2N}\sum_{k=0}^{2N-1}\hat{X}[k]e^{j\frac{2{\pi}kn}{2N}}\\
&=\frac{1}{2N}\sum_{n=0}^{2N-1}\dot{X}[k]e^{j\frac{2{\pi}k\cdot \frac{1}{2}}{2N}}e^{j\frac{2{\pi}kn}{2N}}
\end{split}$
### 特性
$\hat{X}[0]=\sum_{n=0}^{2N-1}\hat{x}[n]$
$\begin{split}
\hat{X}[N]&=\sum_{n=0}^{2N-1}\hat{x}[n]e^{-j\frac{2{\pi}(N)n}{2N}}\\
&=\sum_{n=0}^{2N-1}\hat{x}[n]e^{-j{\pi}n}\\
&=\hat{x}[0]-\hat{x}[1]+\hat{x}[2]...\ \ \hat{x}[N-1]\\
&\ \ -\hat{x}[2N-1]+\hat{x}[2N-2]...\hat{x}[N]\\
&=0
\end{split}$ (recall$\ \ \ \ \ \hat{x}[n]=\hat{x}[2N-n-1]$)

### 依據特性整理

$\begin{split}
\hat{x}[n]&=\frac{1}{2N}\sum_{k=0}^{2N-1}\hat{X}[k]e^{j\frac{2{\pi}kn}{2N}}\\
&=\frac{1}{2N}[\hat{X}[0]+\sum_{k=1}^{2N-1}\hat{X}[k]e^{j\frac{2{\pi}kn}{2N}}]\\
&=\frac{1}{2N}[\hat{X}[0]+\sum_{k=1}^{N-1}\hat{X}[k]e^{j\frac{2{\pi}kn}{2N}}+\sum_{k=N+1}^{2N-1}\hat{X}[k]e^{j\frac{2{\pi}kn}{2N}}]\\
&=\frac{1}{2N}[\hat{X}[0]+\sum_{k=1}^{N-1}\hat{X}[k]e^{j\frac{2{\pi}kn}{2N}}+\sum_{k=1}^{N-1}\hat{X}[2N-k]e^{j\frac{2{\pi}(2N-k)n}{2N}}]\\
&=\frac{1}{2N}[\hat{X}[0]+\sum_{k=1}^{N-1}\hat{X}[k]e^{j\frac{2{\pi}kn}{2N}}+\sum_{k=1}^{N-1}\hat{X}[2N-k]e^{j\frac{2{\pi}2Nn}{2N}}e^{j\frac{2{\pi}kn}{2N}}]\\
&=\frac{1}{2N}[\hat{X}[0]+\sum_{k=1}^{N-1}\hat{X}[k]e^{j\frac{2{\pi}kn}{2N}}+\sum_{k=1}^{N-1}\hat{X}[2N-k]e^{j\frac{2{\pi}kn}{2N}}]\\
&=\frac{1}{2N}[\hat{X}[0]+\sum_{k=1}^{N-1}\dot{X}[k]e^{j\frac{2{\pi}k\frac{1}{2}}{2N}}e^{j\frac{2{\pi}kn}{2N}}+\sum_{k=1}^{N-1}\dot{X}[2N-k]e^{j\frac{2{\pi}(2N-k)\frac{1}{2}}{2N}}e^{-j\frac{2{\pi}kn}{2N}}]\\
\end{split}$

$\hat{X}[k]=(\hat{X}[2N-k])^*$

$\dot{X}[k]=\hat{X}[k]e^{-j\frac{2{\pi}k\frac{1}{2}}{2N}}$

$\begin{split}
|\dot{X}[k]|&=|\hat{X}[k]e^{-j\frac{-2{\pi}k\frac{1}{2}}{2N}}|=|\hat{X}[k]|
\end{split}$

$\dot{X}[0]=\hat{X}[0]e^{-j\frac{2{\pi}\cdot 0 \cdot\frac{1}{2}}{2N}}=\hat{X}[0]$

$\dot{X}[k]=(\dot{X}[2N-k])^*$

$\begin{split}
\hat{x}[n]&=\frac{1}{2N}[\hat{X}[0]+\sum_{k=1}^{N-1}\dot{X}[k]e^{j\frac{2{\pi}k\frac{1}{2}}{2N}}e^{j\frac{2{\pi}kn}{2N}}+\sum_{k=1}^{N-1}\dot{X}[2N-k]e^{j2{\pi}(2N-k)\frac{1}{2}}e^{-j\frac{2{\pi}kn}{2N}}]\\
&=\frac{1}{2N}[\hat{X}[0]+\sum_{k=1}^{N-1}\dot{X}[k]e^{j\frac{2{\pi}k(n+\frac{1}{2})}{2N}}+\sum_{k=1}^{N-1}\dot{X}^*[k]e^{j2{\pi}N}e^{-j2{\pi}k\frac{1}{2}}e^{-j\frac{2{\pi}kn}{2N}}]\\
&=\frac{1}{2N}[\hat{X}[0]+\sum_{k=1}^{N-1}\dot{X}[k]e^{j\frac{2{\pi}k(n+\frac{1}{2})}{2N}}+\sum_{k=1}^{N-1}\dot{X}^*[k]e^{-j\frac{2{\pi}k(n+\frac{1}{2})}{2N}}]\\
&=\frac{1}{2N}[\dot{X}[0]+2\sum_{k=1}^{N-1}\dot{X}[k]cos(\frac{2{\pi}k(n+\frac{1}{2})}{2N})]\\
\end{split}$

$$ \left\{
\begin{aligned}
\dot{X}[k]=2\sum_{n=0}^{N-1}\hat{x}[n]cos(\frac{2{\pi}k(n+\frac{1}{2})}{2N}), k=0,1,2,...N-1,N,N+1,...,2N-1\\
\hat{x}[n]=\frac{1}{2N}[\hat{X}[0]+2\sum_{k=1}^{N-1}\dot{X}[k]cos(\frac{2{\pi}k(n+\frac{1}{2})}{2N})], n=0,1,2,...,N-1,N,N+1,...,2N-1
\end{aligned}
\right.
$$

## 重新定義變數以及係數

$$ \left\{
\begin{aligned}
X^{c}[k]&=2\sum_{n=0}^{N-1}x[n]cos(\frac{{\pi}k(2n+1)}{2N})\\
x[n]&=\frac{1}{2N}[2(\frac{1}{2}X^{c}[0])+2\sum_{k=1}^{N-1}X^{c}[k]cos(\frac{{\pi}k(2n+1)}{2N})]
\end{aligned}
\right.
$$

以上數學式的 $X^c[0]$ 前面的係數和其他 $X^c[k]$ 前面的係數不一樣很討厭，我們想辦法讓 DCT 和 IDCT 裡面各項係數的值類似或對稱，就需要外加一個輔助係數 ($\beta [k]$) 來幫忙

$$ \left\{
\begin{aligned}
\frac{1}{\sqrt[]{2N}}X^{c}[k]&=\frac{1}{\sqrt[]{2N}}\cdot 2\sum_{n=0}^{N-1}x[n]cos(\frac{{\pi}k(2n+1)}{2N})=\sqrt{\frac{2}{N}}\sum_{n=0}^{N-1}x[n]cos(\frac{{\pi}k(2n+1)}{2N})\\
x[n]&=\frac{1}{2N}[2(\frac{1}{2}\frac{1}{\sqrt[]{2N}}X^{c}[0]\cdot \sqrt[]{2N})+2\sum_{k=1}^{N-1}\frac{1}{\sqrt[]{2N}}X^{c}[k]\cdot \sqrt[]{2N}cos(\frac{{\pi}k(2n+1)}{2N})]\\
&=\sqrt{\frac{2}{N}}[(\frac{1}{2}\frac{1}{\sqrt[]{2N}}X^{c}[0])+\sum_{k=1}^{N-1}\frac{1}{\sqrt[]{2N}}X^{c}[k]cos(\frac{{\pi}k(2n+1)}{2N})]
\end{aligned}
\right.
$$

$$ X^{c_2}[k]=\left\{
\begin{aligned}
\frac{1}{\sqrt[]{4N}}X^c[k]\ \ \ &,k=0\\
\frac{1}{\sqrt[]{2N}}X^c[k]\ \ \ &,k=1,2,3,...N-1\\
\end{aligned}
\right.
$$

$$ X^{c_2}[k]=\left\{
\begin{aligned}
\sqrt{\frac{2}{N}}\sum_{n=0}^{N-1}(\frac{1}{\sqrt[]{2}})x[n]cos(\frac{{\pi}k(2n+1)}{2N})\ \ \ &,k=0\\
\sqrt{\frac{2}{N}}\sum_{n=0}^{N-1}(1)x[n]cos(\frac{{\pi}k(2n+1)}{2N})\ \ \ &,k=1,2,3,...N-1\\
\end{aligned}
\right.
$$

$$x[n]=\sqrt{\frac{2}{N}}[(\frac{1}{\sqrt[]{2}}X^{c2}[0])+\sum_{k=1}^{N-1}X^{c2}[k]cos(\frac{{\pi}k(2n+1)}{2N})]$$

## 最後結果

$$ \left\{
\begin{aligned}
X^{c2}[k]&=\sqrt[]{\frac{2}{N}}\sum_{n=0}^{N-1}\beta[k]x[n]cos(\frac{{\pi}k(2n+1)}{2N})\\
x[n]&=\sqrt[]{\frac{2}{N}}\sum_{k=0}^{N-1}\beta[k]X^{c2}[k]cos(\frac{{\pi}k(2n+1)}{2N})
\end{aligned}
\right.
$$

其中 $\beta[k]$ 定義為：
$$ \beta[k]=\left\{
\begin{aligned}
\frac{1}{\sqrt[]{2}}\ \ \ &,k=0\\
1\ \ \ &,k=1,2,3,...N-1\\
\end{aligned}
\right.
$$

## 2D Discrete Consine Transform

$$ \left\{
\begin{aligned}
F[u,v]&=\sqrt[]{\frac{4}{HW}}\sum_{r=0}^{H-1}\sum_{c=0}^{W-1}\beta[u]\beta[v]f[r,c]cos(\frac{{\pi}u(2r+1)}{2H})cos(\frac{{\pi}v(2c+1)}{2W})\\
f[r,c]&=\sqrt[]{\frac{4}{HW}}\sum_{u=0}^{H-1}\sum_{v=0}^{W-1}\beta[u]\beta[v]F[u,v]cos(\frac{{\pi}u(2r+1)}{2H})cos(\frac{{\pi}v(2c+1)}{2W})
\end{aligned}
\right.
$$

其中 $\beta[k]$ 定義為：
$$ \beta[k]=\left\{
\begin{aligned}
\frac{1}{\sqrt[]{2}}\ \ \ &,k=0\\
1\ \ \ &,k=1,2,3,...N-1\\
\end{aligned}
\right.
$$