영상처리 - 2-FFT

소개글

영상처리 - 2차원 Fourier Transform 에대 예제와 영상들을 통한 설명

목차

◆ Two-Dimensional Fast Fourier Transform
▷ 개요
◆ Low pass Filtering
○ 개요

본문내용

◆ Two-Dimensional Fast Fourier Transform
▷ 개요

DFT (Discrete Fourier Transform)
연속함수에서는 Fourier transform을 하면 되지만 discrete 에서는 DFT를 행한다.
waveform 이 interval T 로 sampled 되었다고 하면 , sample sequence 는 x(nT) = x(0), x(1), x(2), x(3), x(4), x(5) ∼ x[(N-1)T]라 할수 있다. 그래서 x(nT)의 DFT 는 frequency domain에서 X(k) = X(0),X(1),∼X[(N-1)] 같은 복소수 값의 sequence를 갖는다.
1차원 DFT는 다음과 같다.

( k = harmonic number of transform component )


그리고 중요한 DFT의 성질이 있는데 k번째의 요소와 k+N 번째 요소를 비교하면
X(k+N) = X(k)
따라서 위 식은 DFT 는 주기 N에 대하여 periodic 하게 나타난다는 것이다.

Computational complexity of the DFT
만약 8-point 에 대해서 DFT를 실행한다고 하면 총 8*8 번의 complex곱을 실시해야하고 8* 7 번의 덧셈을 해야 한다. 그래서 N point DFT 는 N^2 과 N(N-1) 번의 곱과 합을 계산해야한다.
만약 N=1024 개 라면 엄청난 계산시간이 필요하다. 따라서 이 작업을 개선하기 위해서 나온 algorithm이 FFT(Fast Fourier Transform) 이다.

참고 자료

없음