Fourier Transform (푸리에 변환)

 

EGG와 같은 신호를 공부할 때 한번쯤 보게 되는게 바로 Fourier Transform (푸리에 변환)이다. 

 

그런데 CVPR 2022의 Tutorial on Diffusion Model (링크)을 공부해서 블로그에 정리 (링크)하다가 궁금한 점이 생겼다.

 

Waveform 형태가 아니라 이미지 데이터에 푸리에 변환이 어떻게 가능한가 싶어서 시작한 포스트다.

 

우선 웨이브폼 신호에 대한 푸리에 변환 적용부터 알아본다.

 

 

Fourier Trasnform on Waveform

푸리에 변환의 핵심은 하나의 신호를 다양한 주파수의 주기 함수들의 합으로의 분해다.

 

EGG 같은 신호의 경우 푸리에 변환을 통해서 Time domain으로 표현된 데이터를 Frequency domain에서의 표현으로 변환하게 된다. 

 

시간 도메인에서 정의되는 원본 신호 함수를 $f(x)$라고 하자.

 

이를 주파수 도메인으로 변환하는 Fourier Transform 푸리에 변환의 결과는 아래와 같다.

 

$F(u) = \int_{- \infty}^{\infty} f(x) exp(-i2 \pi ux) dx$ ... (1)

 

이때 $i = \sqrt{-1}$인 허수다.

 

Euler's formula 오일러 공식은 복소지수함수를 삼각함수의 변환하는 식으로 아래 (2)다. 

 

$exp(i \theta) = e^{i\theta} = cos \theta + i \, sin \theta$ ... (2)

 

이때 (1)의 경우 $\theta$ 값이 $2 \pi u x$ 임을 파악하고 (2)를 정리하면 아래 (3)의 식이 된다.

 

$exp(i 2 \pi u x) = cos (2 \pi u x) + i \, sin (2 \pi u x)$ ... (3)

 

실수부인 $cos (2 \pi u x)$와 허수부인 $i \, sin (2 \pi u x)$ 모두 $1 / u$의 period 주기를 갖는다. 

 

주파수는 주기와 역수의 관계이므로 $u$다.

 

따라서, 정리하자면 $F(u)$는 특정 주파수 $u$에 대해서 여러가지 주기 함수들의 합으로 표현할 수 있다는 뜻이다. 

 

 

 

이때, 주파수 도메인의 함수 $F(u)$를 다시 시간 도메인으로 변경하는 작업을 Inverse Fourier Transform 푸리에 역변환이라고 한다. 그 식은 아래 (4)와 같다.

 

$f(x) = \int_{- \infty}^{\infty} F(u) exp(i2 \pi ux) du$ ... (4)

 

정리하자면 시간 도메인에서의 함수 $f(x)$는 주파수 $u$와 그 주기함수 $exp(i2 \pi ux)$, 이에 상응하는 가중치 $F(u)$의 weighted sum의 연속형 버젼이라고 볼 수 있다. 그리고 $u$에 대한 적분이므로 여러가지 주파수들의 합이다. 

 

 

 

 

Fourier Trasnform on Image

이미지 경우 푸리에 변환을 통해서 Spatial domain으로 표현된 데이터를 Frequency domain에서의 표현으로 변환하게 된다. 

 

2D 이미지 도메인에서의 원본 이미지 함수를 $f(x, y)$라 하자.

 

이에 대한 Fourier Transform 푸리에 변환의 결과는 아래와 같다.

 

$F(u, v) = \int_{- \infty}^{\infty}  \int_{- \infty}^{\infty} f(x, y) exp(-i2 \pi (ux + vy)) dx dy$ ... (5)

 

$u$ $x$에 대한 주파수 축이고, $v$는 $y$에 대한 주파수 축이다.

 

 

Inverse Fourier Transform 푸리에 역변환은 다음과 같다.

 

 

$f(x, y) = \int_{- \infty}^{\infty}  \int_{- \infty}^{\infty} F(u, v) exp(i2 \pi (ux + vy)) du dv$ ... (6)

 

 

이미지에서의 high frequency 고주파는 이미지가 급격하게 변하는 부분이고, low frequency 저주파는 이미지가 완만하게 변하는 부분이다. 예를 들어서 흑백 스트라이프 패턴은 고주파, 그라데이션은 저주파다. 

 

따라서 대체로 고주파는 이미지의 디테일, 저주파는 전체적인 윤곽이라고 이해할 수 있다. 

 

 

 

 

 

DFT, Discrete Fourier Trasnform

 

이산형 데이터에 대한 푸리에 변환이다. 디지털 신호는 이산형 신호이므로 DFT가 중요하다.

 

주파수 $k$에 대해서 DFT는 다음과 같이 쓸 수 있다.

 

$X_k = \sum_{n=0}^{N-1} x_n \cdot exp(- i 2 \pi k n / N)$

 

 

역변환은 다음과 같다.

 

$x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k \cdot exp(i 2 \pi k n / N)$

 

 

 

FFT, Fast Fourier Trasnform

 

DFT를 빠르게 계산하기 위한 방법으로 DFT의 계산 복잡도는 $O(n^2)$인데 이를 줄이고자 한다.

 

Cooley-Tukey FFT의 경우 $O(n \, logn)$ 이라고 한다. 

 

 

 

STFT, Short-Time Fourier Trasnform

Non-stationary (비정상) 신호에 있어서 강력한 분석 방법이 될 수 있는 FFT다.

 

이름 그대로 긴 시간의 정보를 더 짧은 구간으로, window 윈도우 사이즈 만큼 잘라서 FT를 적용한다.

 

그리고 이를 Spectrogram 스펙트로그램으로 표시한다.

 

Spectrogram은 Time 시간 축과 Frequency 주파수 축으로 이루어진 평면에서 Amplitude 진폭을 표기한다.

 

일종의 이미지처럼 만들어서 CNN과 같은 딥러닝을 적용한다.

 

여기에 음성신호의 경우 사람의 가청 주파수를 고려하여 주파수 (Hz)와 음높이 (Pitch) 사이의 관계를 비선형적으로 모델링한 Mel-Spectrogram 멜스펙트로그램을 사용한다. 

 

 

 

 

 

 

 

 

여담

 

푸리에 변환 자체에 대한 의미와 시각적인 설명은 3Blue1Brown 영상 (링크)에 잘 나와있으니 보면 도움이 될듯하다.

 

푸리에 변환이랑 STFT, 멜스펙트로그램 변환 예시 코드도 정리해서 올려야겠다. 

 

 

 

 

References:

https://en.wikipedia.org/wiki/Fourier_transform

https://mathworld.wolfram.com/FourierTransform.html

https://darkpgmr.tistory.com/171

https://angeloyeo.github.io/2019/07/07/CTFT.html

https://angeloyeo.github.io/2019/06/23/Fourier_Series.html

Mathematics for Physicists: Introductory Concepts and Methods, Altland, Alexander , Von Delft, Jan

https://en.wikipedia.org/wiki/Euler%27s_formula

https://greeksharifa.github.io/machine_learning/2021/08/14/GFT/

https://www.youtube.com/watch?v=Mc9PHZ3H36M

https://www.youtube.com/watch?v=eKSmEPAEr2U

https://www.mathworks.com/help/matlab/math/two-dimensional-fft.html

https://peterbbryan.medium.com/understanding-2d-fourier-space-59808b644a13

https://physics.stackexchange.com/questions/683831/what-is-meant-by-2d-fourier-transform-of-an-image

https://medium.com/@shashimalsenarath.17/frequency-in-images-computer-vision-d179b8c0f723

https://x.com/divamgupta/status/1619409474464415749

https://wikidocs.net/263938

https://en.wikipedia.org/wiki/Sparse_Fourier_transform

https://en.wikipedia.org/wiki/Discrete_Fourier_transform

https://en.wikipedia.org/wiki/Short-time_Fourier_transform

https://en.wikipedia.org/wiki/Fast_Fourier_transform

https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm

https://blog.naver.com/wjdalsdl1016/221109321310

https://en.wikipedia.org/wiki/Spectrogram

https://wikidocs.net/193588

https://medium.com/@hugmanskj/hands-on-%EC%86%8C%EB%A6%AC%EB%A5%BC-%EC%9D%B4%EB%AF%B8%EC%A7%80-%EC%A0%95%EB%B3%B4%EB%A1%9C-%EB%B3%80%ED%99%98%ED%95%98%EB%8A%94-%EB%8B%A4%EC%96%91%ED%95%9C-%EA%B8%B0%EC%88%A0%EB%93%A4-4b1b915e0ee5