푸리에 변환 & JPEG 압축

Fourier Transform & JPEG Encoding

by. 20118 이도이

F T

Fourier Transform

F T

Fourier Transform

$$X(\xi) = \int^{\infty}_{-\infty}{x(t)e^{-2\pi i \xi t}}dt$$

$$e^{i\theta} = \cos\theta + i\sin\theta$$ $$\downarrow$$

\[X(\xi) = \displaystyle{\int^{\infty}_{-\infty}}\] \[{x(t)\Bigl(\cos-2\pi \xi t+i \sin-2\pi \xi t\Bigr)}\] \[dt\]

\[{x(t)\Bigl(\cos-2\pi \xi t+i \sin-2\pi \xi t\Bigr)}\]

\[X(\xi) = \displaystyle{\int^{\infty}_{-\infty}}\] \[{x(t)\Bigl(\cos-2\pi \xi t+i \sin-2\pi \xi t\Bigr)}\] \[dt\]

F F T

Fast Fourier Transform

D F T

Discrete Fourier Transform

F F T

Fast Fourier Transform

$\displaystyle{X(\xi) = \int^{\infty}_{-\infty}{x(t)e^{-2\pi i \xi t}}dt}$ $$\downarrow$$

$\displaystyle{X_k =\sum^{N-1}_{n=0}{x_ne^{-2\pi kn/N}}}\quad k = 0, ... , N-1 .$

JPEG Encoding

Joint Photographic Experts Group

Color space transform

Downsampling & Blocksplitting

D C T

Discrete Cosine Transform

$\displaystyle{X_k =\sum^{N-1}_{n=0}{x_n\Bigl(\cos\Bigl(\frac{-2\pi kn}{N}\Bigr) + i\sin\Bigl(\frac{-2\pi kn}{N}\Bigr)\Bigr)}}$
$k = 0, ... , N-1$ $$ \downarrow \\ $$ $$ X_k = \sum^{N-1}_{n=0}{x_n \cos\left[\frac{(2n+1)k\pi}{2N}\right]},\quad k=0,...N-1 $$

\[G_{u,v} = \displaystyle{\frac14\alpha(u)\alpha(v)\sum^7_{x=0}\sum^7_{y=0}g_{x,y}\cos\left[\frac{(2x+1)u\pi}{2\times8}\right]\cos\left[\frac{(2y+1)v\pi}{2\times8}\right]}\]

$u$: 수평 DCT, $0\leq u<8,\,u\in\mathbb{Z}$< /li>
$v$: 수직 DCT, $0\leq v<8,\,v\in\mathbb{Z}$< /li>
$\alpha(i)=\begin{cases} \frac{1}{\sqrt{2}}, \quad &(i=0)\\ 1, \quad &(i>1)\end{cases}$: 정규화를 위한 상수
$g_{x,y}$: $(x,y)$에서 픽셀 값
$G_{u,v}$: $(u,v)$에서 DCT 계수 값

$$ G=\left[\begin{array}{rrrrrrrr} -489&-31.16&22.39&24.78&9.25&4.69&35.1&-7.61\\ -134.08&109.79&-39.62&10.48&-9.89&-32.28&21.12&5.68\\ -134.97&-253.81&-79.67&118.39&-19.68&40.1&-8.07&11.38\\ -65.01&-2.69&269.96&-18.72&39.46&13.22&25.15&-10.85\\ 96.25&221.86&4.16&-130.05&41&2.72&-31.76&-30.57\\ -20.32&22.37&-23&-54.62&27.23&-16.83&-3.01&10.17\\ -42.32&-17.35&-26.57&23.94&65.52&22.06&13.67&34.94\\ -31.23&-14.17&20.34&-5.07&25.08&-80.53&31.89&13.76 \end{array}\right]\quad $$

Quantization

$$ Q=\left[\begin{array}{rrrrrrrr} 16& 11& 10& 16& 24& 40& 51& 61 \\ 12& 12& 14& 19& 26& 58& 60& 55 \\ 14& 13& 16& 24& 40& 57& 69& 56 \\ 14& 17& 22& 29& 51& 87& 80& 62 \\ 18& 22& 37& 56& 68& 109& 103& 77 \\ 24& 35& 55& 64& 81& 104& 113& 92 \\ 49& 64& 78& 87& 103& 121& 120& 101 \\ 72& 92& 95& 98& 112& 100& 103& 99\\ \end{array}\right] $$

$$ B_{j,k} = \Bigl\lfloor \frac{G_{j,k}}{Q_{j,k}}\Bigr\rceil\quad 0\leq j<7, 0\leq k<7 $$

$$ B=\left[\begin{array}{rrrrrrrr} 1&-1&-3&1&1&-1&0&1\\ -1&1&0&0&0&0&0&0\\ -1&0&2&-1&0&0&0&0\\ 0&0&-1&0&0&0&0&0\\ -1&0&1&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0 \end{array}\right] $$

Entropy Encoding

$$ \begin{array}{rrrrrrrr} &-31 \\ &-3 & -11 \\ &-10 & 9 & 2 \\ &2 & -3& -20& -5 \\ &5 & 0 & -5& 1 & 0 \\ &0 & 0 & 5 & 12 & 10 & -1\\ &-1& 1 & 0 & -1 & 0 & -1 & 1 \\ &0 & 0 & 1 & 1 & -2 & 0 & ~~0 & ~0 \\ &0 & 0 & -1& 1 & 0 & 0 & 0 \\ &0 & 0 & 0 & 0 & 0 & 0 \\ &0 & 1 & 0 & 0 & 0 \\ &0 & 0 & 0 & 0 \\ &-1 & 0 & 0 \\ &0 & 0 \\ &0 \end{array} $$

Summary

Fast Fourier Transform

$\displaystyle{X(\xi) = \int^{\infty}_{-\infty}{x(t)e^{-2\pi i \xi t}}dt}$ $$\downarrow$$

$\displaystyle{X_k =\sum^{N-1}_{n=0}{x_ne^{-2\pi kn/N}}}\quad k = 0, ... , N-1 .$

Discrete Cosine Transform

\[G_{u,v} = \displaystyle{\frac14\alpha(u)\alpha(v)\sum^7_{x=0}\sum^7_{y=0}g_{x,y}\cos\left[\frac{(2x+1)u\pi}{2\times8}\right]\cos\left[\frac{(2y+1)v\pi}{2\times8}\right]}\]

Quantization

Result

PNG

JPEG

마치며...

https://ywppt.kro.kr/docs/jpeg.html
https://ywppt.kro.kr/ppt/jpeg
https://ywbird.github.io/jpeg-dct-web