디지털 영상 처리 - 단일 변수 함수의 이산 푸리에 변환(Discrete Fourier Transform)

 안녕하세요. 지난 포스팅의 디지털 영상 처리 - 샘플링 정리와 샘플링된 함수 복원에서는 디지털 영상에서의 핵심인 샘플링 정리의 원리, 대역 제한 함수인 이상적인 상황에서 언더-샘플링 시 발생하는 앨리어싱 현상, 그리고 컨볼루션 정리를 이용하여 주파수 공간에서 영상 공간으로 변환하였을 때 가지는 의미에 대해서 설명하였습니다. 지금까지는 푸리에 변환과 디지털 영상에 대한 관계성을 알아보았다면 오늘 포스팅에서는 디지털 영상 처리에서 활용되는 이산 푸리에 변환(Discrete Fourier Transform;DFT)를 유도해보도록 하겠습니다. 

 

1. 샘플링된 함수의 연속적 변환으로부터 DFT 유도

 기본적으로 저희가 DFT가 필요한 이유는 디지털 영상을 다루기 때문입니다. 디지털 영상은 이산 데이터의 일종이기 때문이죠. 일단 샘플링된 함수를 $\tilde{f}(t)$라고 했을 때 샘플링된 함수에 푸리에 변환을 적용한 $\tilde{F}(\mu)$는 푸리에 변환의 정의를 이용하면 아래의 관계식을 가집니다.

 

$$\tilde{F}(\mu) = \int_{-\infty}^{\infty} \tilde{f}(t)e^{-j2\pi\mu t} \; dt$$

 

 그리고 샘플링된 함수는 기존 함수 $f(t)$에 주기 $\Delta T$를 가지는 임펄스 열 $s_{\Delta T}(t)$을 곱한 것이므로 $\tilde{f}(t) = f(t)s_{\Delta T}(t) = f(t)\sum_{n=-\infty}^{\infty} f(t)\delta(t - n\Delta T)$입니다. 이 식을 그대로 위에 대입하면 아래와 같습니다. 

 

$$\tilde{F}(\mu) = \int_{-\infty}^{\infty} \tilde{f}(t)e^{-j2\pi\mu t} \; dt = \int_{-\infty}^{\infty} \sum_{n=-\infty}^{\infty} f(t)\delta(t - n\Delta T) e^{-j2\pi\mu t} \; dt$$

$$ = \sum_{n = -\infty}^{\infty} \int_{-\infty}^{\infty} f(t)\delta(t - n\Delta T)e^{-j2\pi\mu t} \; dt = \sum_{n = -\infty}^{\infty} f_{n}\delta(t - n\Delta T)e^{-j2\pi\mu n\Delta T}$$

 

 마지막 등호는 임펄스 함수의 선별 특성을 활용한 결과입니다. 결과를 보시면 $f_{n}$은 샘플링된 이산 함수입니다. 하지만 $\tilde{F}(\mu)$는 주기 $\frac{1}{\Delta T}$를 가지는 연속함수입니다. 따라서 $\tilde{F}(\mu)$를 결정짓는 것은 딱 한 주기이며 해당 주기만 뽑아내는 것이 DFT 유도 과정의 핵심입니다. 

 

 먼저 $\tilde{F}(\mu)$를 구간 $\mu = 0$부터 $\mu = \frac{1}{\Delta T}$까지 총 $M$개의 등간격의 샘플들을 얻고 싶다고 가정하겠습니다. 그러면 $\mu = \frac{m}{M\Delta T}$마다 샘플링을 하면 되겠죠? 이 식을 저희가 유도했던 $\tilde{F}(\mu) = \sum_{n = -\infty}^{\infty} f_{n}\delta(t - n\Delta T)e^{-j2\pi\mu n\Delta T}$에 대입한 $F_{m}$은 아래와 같습니다. 

 

$$F_{m} = \sum_{n = 0}^{M - 1}f_{n}e^{-j2\pi mn/M}$$

 

 해당 수식이 저희가 원하는 DFT입니다. 지금까지의 내용을 잠시 정리해보도록 하겠습니다. 저희가 $f(t)$의 $M$개의 샘플로 구성되는 집합 $\{f_{n}\}$이 주어지면 입력 샘플 집합에 대한 DFT에 해당되는 $M$개의 이산 복소수 집합 $\{F_{m}\}$이 나오게 됩니다. 이와 반대로 $\{F_{m}\}$이 주어지면 IDFT(Inverse Discrete Fourier Transform) $f_{n} = \frac{1}{M}\sum_{m = 0}^{M - 1}F_{m}e^{j2\pi mn /M}$을 사용하여 샘플 집합 $\{f_{n}\}$을 복원할 수 있습니다. 이때, $f_{n}, F_{m}$를 "DFT 쌍(DFT pair)"라고 합니다. 

 

 이제 표기를 앞으로 좀 더 간단하게 하기 위해 아래와 같이 쓰도록 하겠습니다.

 

1. DFT : $F(\mu) = \sum_{x = 0}^{M-1} f(x)e^{-j2\pi\mu x/M}$, $\mu = 0, 1, 2, \dots, M - 1$
2. IDFT : $f(t) = \frac{1}{M}\sum_{\mu = 0}^{M - 1}F(\mu) e^{j2\pi\mu x / M}$, $x = 0, 1, 2, \dots, M - 1$

 그리고 DFT와 IDFT를 보시면 주기 $M$으로 무한히 반복된다는 것을 알아채실겁니다. 따라서 $f(x + kM) = f(x)$, $F(\mu + kM) = F(\mu)$라고 적을 수 있겠죠. 

 

2. 샘플링과 주파수 간격 간의 관계

 이제 샘플링과 주파수 간격 간의 관계식을 보도록 하겠습니다. $f(x)$가 $\Delta T$ 간격으로 취해진 함수 $f(t)$의 $M$개의 샘플들로 구성되어있다고 가정하면 집합 $\{f(x)\}$, $x = 0, 1, \dots, M - 1$가 정의된 전체 구간은 $T = M\Delta T$입니다. 그리고 주파수 공간에서 대응되는 간격 $\Delta\mu = \frac{1}{M\Delta T} = \frac{1}{T}$입니다. 마지막으로 DFT의 $M$개의 성분들이 걸쳐있는 전체 주파수의 범위는 $\Omega = M\Delta\mu = \frac{1}{\Delta T}$입니다. 즉, DFT의 주파수 해상도는 샘플링되는 구간 $T$에 의존합니다. 그리고 DFT에 의해 만들어지는 주파수 공간의 간격은 샘플링 간격 $\Delta T$에 의존합니다.

 

마지막으로 DFT 예제를 확인해보고 마치도록 하겠습니다. 일단 아래와 같이 미리 샘플링된 함수 값의 집합 $\{f_{n}\}$가 있다고 가정하겠습니다. 

 현재 $\{f_{n}\} = \{1, 2, 4, 4\}$가 있다고 보시면 될 거 같습니다. 이제 DFT 공식 $F(\mu) = \sum_{x = 0}^{M - 1} f(x)e^{-j2\pi\mu x/M}$와 오일러 공식 $e^{j\theta} = \cos{\theta} + j\sin{\theta}$를 이용하여 샘플링된 함수의 푸리에 변환을 하면 됩니다. 

$$F(0) = \sum_{x = 0}^{3} f(x) = f(0) + f(1) + f(2) + f(3) = 1 + 2 + 4 + 4 = 11 + 0j$$

$$F(1) = \sum_{x = 0}^{3} f(x)e^{-j2\pi x/4} = 1e^{0} + 2e^{-j\pi/2} + 4e^{-j\pi} + 4e^{-j3\pi/2} = -3 + 2j$$

$$F(2) = \sum_{x = 0}^{3} f(x)e^{-j\pi x} = 1e^{0} + 2e^{-j2\pi} + 4e^{-j3\pi} + 4e^{-j4\pi} = -1 + 0j$$

$$F(3) = \sum_{x = 0}^{3} f(x)e^{-j3\pi x/4} = 1e^{0} + 2e^{-j3\pi/4} + 4e^{-j3\pi/2} + 4e^{-j3\pi} = -(3 + 2j)$$

 

변경점

21.04.07 : DFT 예제 추가