디지털 영상 처리 - 2D DFT 특성 2

안녕하세요. 지난 포스팅의 디지털 영상 처리 - 2D DFT 특성 1에서는 2D DFT와 관련된 몇 가지 성질들에 대해서 알아보았습니다. 큰 줄기만 말씀드리면 공간 샘플 간격과 주파수 샘플 간격 사이의 관계, DFT의 이동 및 회전 특성, 그리고 제일 중요한 주기성에 대해서 알아보았습니다. 여기서 주기성은 일정 주기를 가지고 반복되는 특성을 의미합니다. 이러한 주기성을 활용해서 중앙으로 평행이동하는 과정도 알아보았습니다. 실제로 주파수 공간 필터링에서는 DFT를 적용한 이후 평행이동을 시키는 과정을 필수로 고려하고 있습니다. 오늘은 이러한 특성들에 이어서 나머지 중요한 특성들에 대해서 알아보도록 하겠습니다. 

 

1. 대칭성(Symmetric)

 기본적으로 임의의 실수 및 복소수 함수 $w(x, y)$는 우함수(even function)와 기함수(odd function)의 합으로 표현할 수 있습니다. 간단하게 설명드리면 1차원에서 우함수는 $y$축으로 대칭인 함수를 통틀어서 말합니다. 예를 들어 $y = x^{2}$ 과 같은 함수가 있겠네요. 그리고 기함수는 원점을 중심으로 대칭인 함수를 말합니다. 예를 들어 $y = x^{3}$이 가능합니다. 하여튼 임의의 함수는 기함수 + 우함수로 표현할 수 있습니다. 우함수를 $w_{e}(x, y) = \frac{w(x, y) + w(-x, -y)}{2}$, 기함수를 $w_{o}(x, y) = \frac{w(x, y) - w(-x, -y)}{2}$라고 하면 원래 함수 $w(x, y)$는 아래와 같이 표현할 수 있습니다. 

 

$$w(x, y) = w_{e}(x, y) + w_{o}(x, y)$$

 

 실제로 $w_{e}(x, y)$와 $w_{o}(x, y)$를 대입해보면 항등식이 됨을 앙ㄹ 수 있습니다. 또한 기함수와 우함수의 성질 중 하나인 대칭성(symmetric)과 반대칭성(antisymmetric)을 이용해서 $w_{e}(x, y) = w_{e}(-x, -y)$ 그리고 $w_{o}(x, y) = -w_{o}(-x, -y)$ 인 것도 알 수 있습니다. 여기서는 저희가 DFT와 IDFT를 다루고 있기 때문에 인덱스가 양수임을 보장해주어야합니다. 따라서 대칭성에 대해서 이야기 할 때는 샘플들의 시퀀스들의 중심점을 기준으로 설명하도록 하겠습니다. 시퀀스를 중심으로 왼쪽은 음수 인덱스, 오른쪽은 양수 인덱스라고 생각만 하시면 됩니다. 이 경우에는 우함수와 기함수의 정의를 다시 아래와 같이 쓸 수 있습니다. 

 

$$w_{e}(x, y) = w_{e}(M - x, N - y)$$

$$w_{o}(x, y) = -w_{o}(M - x, N - y)$$

 

 우함수와 기함수 사이에는 유용한 성질들이 많이 존재하고 있습니다. 특히 아래의 성질들을 이용할 것입니다.

 

1. 임의의 두 우함수의 곱은 우함수이다.
2. 임의의 두 기함수의 곱은 우함수이다.
3. 우함수와 기함수의 곱은 기함수이다.
4. 이산 함수가 기함수가 되기 위해서는 모든 샘플의 합이 0이여야만 한다.

 따라서 $w_{e}(x, y)w_{o}(x, y)$는 기함수이기 때문에 $\sum_{x = 0}^{M - 1}\sum_{y = 0}^{N - 1} w_{e}(x, y)w_{o}(x, y) = 0$이 됩니다. 또한 DFT와 IDFT는 복소수로 확장되는 개념이기 때문에 "공액 대칭(conjugate symmetric)"이라는 특성도 존재합니다. 이 특성은 크게 2가지로 나누어서 설명됩니다.

 

1. $f(x, y)$가 실수 함수라면 $F^{*}(\mu, \nu) = F(-\mu, -\nu)$이다.(공액 대칭)
2. $f(x, y)$가 허수 함수라면 $F^{*}(\mu, \nu) = -F(-\mu, -\nu)$이다.(공액 반대칭)

 여기서 $F^{*}$는 복소수의 공액을 의미합니다. 공액 대칭에 대한 성질을 간단하게 증명해보도록 하겠습니다. DFT의 정의와 성질을 이용하면 쉽게 보일 수 있는 성질입니다. 

 

$$F^{*}(\mu, \nu) = \left[\sum_{x = 0}^{M - 1}\sum_{y = 0}^{N - 1} f(x, y)e^{-j2\pi\left(\frac{\mu x}{M} + \frac{\nu y}{N}\right)}\right]^{*}$$

$$ = \sum_{x = 0}^{M - 1} \sum_{y = 0}^{N - 1} f^{*}(x, y)e^{j2\pi\left(\frac{\mu x}{M} + \frac{\nu y}{N}\right)}$$

$$ = \sum_{x = 0}^{M - 1} \sum_{y = 0}^{N - 1} f(x, y)e^{j2\pi\left(\frac{\mu x}{M} + \frac{\nu y}{N}\right)}$$

$$ = \sum_{x = 0}^{M - 1} \sum_{y = 0}^{N - 1} f(x, y)e^{-j2\pi\left(\frac{(-\mu) x}{M} + \frac{(-\nu) y}{N}\right)} = F(-\mu, -\nu)$$

 

 이번에는 공액 반대칭에 대한 성질을 증명해보도록 하겠습니다. 이번에도 유사한 접근법을 사용하면 됩니다.

 

$$F^{*}(\mu, \nu) = \left[\sum_{x = 0}^{M - 1}\sum_{y = 0}^{N - 1} f(x, y)e^{-j2\pi\left(\frac{\mu x}{M} + \frac{\nu y}{N}\right)}\right]^{*}$$

$$ = \sum_{x = 0}^{M - 1} \sum_{y = 0}^{N - 1} f^{*}(x, y)e^{j2\pi\left(\frac{\mu x}{M} + \frac{\nu y}{N}\right)}$$

$$ = \sum_{x = 0}^{M - 1} \sum_{y = 0}^{N - 1} -f(x, y)e^{j2\pi\left(\frac{\mu x}{M} + \frac{\nu y}{N}\right)}$$

$$ = -\left[\sum_{x = 0}^{M - 1} \sum_{y = 0}^{N - 1} f(x, y)e^{-j2\pi\left(\frac{(-\mu) x}{M} + \frac{(-\nu) y}{N}\right)}\right] = -F(-\mu, -\nu)$$

 

 이러한 대칭 성질들은 어마무시하게 많습니다. 이를 하나의 표로 정리하면 아래와 같습니다. 

 이 중에서 저희가 증명한 건 1)과 2) 밖에 없습니다만, 시간이 나면 종종 증명해서 추가해보도록 하겠습니다. 

 

2. 푸리에 스펙트럼과 위상각(Fourier Spectrum and Fourier Phase Angle)

 DFT는 일반적으로 복소수로 확장된 개념이기 때문에 복소평면을 고려하여 극좌표로 표현하면 더 많은 정보를 얻을 수 있습니다. 이번에 소개해드릴 정보가 바로 푸리에 스펙트럼과 위상각입니다. 일단 DFT를 극좌표로 쓰면 아래와 같습니다. 

 

$$F(\mu, \nu) = |F(\mu, \nu)|e^{j\phi(\mu, \nu)}$$

 

 여기서 $|F(\mu, \nu)|$와 $\phi(\mu, \nu)$를 각각 푸리에 스펙트럼, 그리고 푸리에 위상각이라고 부르고 그 정의는 각각 아래와 같습니다. 

 

$$|F(\mu, \nu)| = \left[R^{2}(\mu, \nu) + I^{2}(\mu, \nu)\right]^{\frac{1}{2}}$$

$$\phi(\mu, \nu) = \arctan{\left[\frac{I(\mu, \nu)}{R(\mu, \nu)}\right]}$$

 

 마지막으로 전력 스펙트럼은 $P(\mu, \nu) = R^{2}(\mu, \nu) + I^{2}(\mu, \nu) = |F(\mu, \nu)|^{2}$로 정의됩니다. 그리고 $R$은 DFT의 실수부, $I$는 DFT의 허수부를 의미합니다. 여기서 중요한 점은 각 점 $(\mu, \nu)$에 대한 계산이기 때문에 푸리에 스펙트럼, 위상각, 전력 스펙트럼은 모두 $M \times N$의 행렬이 됩니다($\mu = 0, 1, \dots, M - 1$, $\nu = 0, 1, \dots, N - 1$).

 

 여기서 저희가 방금 전에 정리해 대칭성을 활용해볼 수 있습니다. 디지털 영상은 기본적으로 실수값을 가집니다. 허수를 가질리가 없겠죠. 따라서 디지털 영상 $f(x, y)$가 실수 함수라고 생각하면 $\mathcal{F}\{f(x, y)\} = F(\mu, \nu)$는 공액 대칭을 가지게 됩니다. 이는 곧 푸리에 스펙트럼이 원점에 대해서 우대칭임을 보여주게 됩니다. 

 

$$|F(\mu, \nu)| = |F(-\mu, -\nu)|$$

 

 그에 반해 위상각은 원점에 대해서 기대칭임을 알 수 있습니다. 

 

$$\phi(\mu, \nu) = -\phi(-\mu, -\nu)$$

 

  잠깐 DFT의 정의를 이용하면 $F(0, 0) = \sum_{x = 0}^{M - 1} \sum_{y = 0}^{N - 1} f(x, y)$가 됩니다. 즉, 주파수가 0인 항은 $f(x, y)$의 평균값에 비례하고 있기 때문에 이를 정리하면 아래와 같이 쓸 수 있습니다. 

 

$$F(0, 0) = \sum_{x = 0}^{M - 1} \sum_{y = 0}^{N - 1} f(x, y) = MN \left(\frac{1}{MN} \sum_{x = 0}^{M - 1} \sum_{y = 0}^{N - 1} f(x, y)\right)$$

$$ = MN \bar{f}(x, y)$$

 

 따라서, $|F(0, 0)| = MN|\bar{f}(x, y)|$가 됩니다. 그런데 비례 상수 $MN$은 보통 큰 값입니다. 이는 $|F(0, 0)|$이 다른 항에 비해서 훨씬 큰 값임을 의미합니다. 그래서 이 항을 dc 항으로 따로 정의하도록 하겠습니다. 

 

3. 2D 컨볼루션 정리

 기본적으로 컨볼루션 연산은 적분을 통해 계산하지만 이산 함수의 경우에는 아래와 같이 단순 합으로 표현할 수 있습니다. 

 

$$f(x) * h(x) = \sum_{m = 0}^{M - 1} f(m)h(x - m)$$

 

 여기서 $m$이 연속 함수의 컨볼루션 연산에서 $\tau$를 맡고 있는 것이죠. 이때, 저희가 다루는 DFT나 IDFT는 모두 주기 함수이기 때문에 그 컨볼루션 결과 역시 주기 함수를 생성하게 됩니다. 이와 같이 주기 함수를 생성하는 컨볼루션 연산을 환형 컨볼루션(circular convolution)이라고 합니다. 

 

 이를 2D로 쉽게 확장할 수 있습니다. 

 

$$f(x, y)  * h(x, y) = \sum_{m = 0}^{M - 1} \sum_{n = 0}^{N - 1} f(m, n)h(x - m, y - n)$$

 

 여기서 $x = 0, 1, \dots, M - 1, y = 0, 1, \dots, N - 1$입니다. 또한 1D 컨볼루션 정리와 마찬가지로 영상 공간에서의 컨볼루션 연산은 주파수 공간에서의 단순곱, 그리고 주파수 공간에서의 컨볼루션은 영상 공간에서의 단순곱입니다. 이를 정리해보면 아래와 같습니다. 

 

$$f(x, y) * h(x, y) \Leftrightarrow F(\mu, \nu)H(\mu, \nu)$$

$$f(x, y)h(x, y) \Leftrightarrow F(\mu, \nu)*H(\mu, \nu)$$

 

 여기서 중요한 문제가 발생합니다. 방금도 말씀드렸다싶이 현재 저희가 다루고 있는 함수는 주기 함수이기 때문에 컨볼루션 연산에서 나오는 주기성 문제가 발생합니다. 이를 간단한 1D를 예제로 그림을 통해서 알아보도록 하겠습니다. 일단 주기성이 존재하지 않는 함수를 보도록 하겠습니다. 

 

$$f(x) *h(x) = \sum_{m = 0}^{399} f(x)h(x - m)$$

 

 궁극적으로 컨볼루션 연산이란 위의 $f(x)$로부터 기존의 필터 $h(m)$를 180도 반전시킨 $h(-m)$을 변위 $x$에 따라서 곱하면서 결과 $f(x)h(x - m)$를 얻는 것입니다. 그리고 그 결과는 가장 아래 그림과 같습니다. 애초에 $f(x)$와 $h(x)$에서 주기성을 제외하였기 때문에 컨볼루션 연산 결과 역시 주기성이 배제됩니다. 또한 컨볼루션 연산 결과의 정의역이 $[0, 799]$라는 점도 주목해주시길 바랍니다. 이번에는 주기성이 존재하는 $f(x)$와 $h(x)$에 컨볼루션 연산을 보도록 하겠습니다.

 일단 위의 그림과 같이 주기성이 존재하는 $f(x)$와 $h(m)$을 가지고 왔습니다. 

 

 이번에는 컨볼루션 연산을 위해서 180도 회전시킨 후 변위 $x$에 따라서 함수 $f(x)$와의 곱을 구하겠죠. 

 컨볼루션 과정은 동일합니다. 하지만 그 결과는 주기성을 가진 함수가 나오게 되었습니다. 하지만 위의 경우에는 주기가 너무 가까워서 "둘러겹침 오차(wraparound error)"라는 것을 발생시킵니다. 이는 간단하게 말해서 주기간에 서로 간섭을 일으키게 된 현상을 의미합니다. 해결 방법은 아주 간단합니다. 바로 $f(x)$와 $h(x)$에 "0-패딩(zero-padding)"을 적용해주면 됩니다. 두 함수에 모두 0으로 둘러싸서 $P$라는 같은 길이를 가지도록 만들어줍니다. 그렇다면 $P$는 어떻게 선택해야할까요? 이 부분은 이미 논문으로 나와있기 때문에 결과만 보시면될 거 같습니다. 저희가 $P \ge A + B - 1$를 만족하는 $P$를 선택한다면 둘러겹침 오차는 제거할 수 있습니다. 여기서 $A$와 $B$는 각각 함수 $f(x)$, $h(x)$의 길이를 의미합니다. 따라서 위의 예제의 경우에는 $A = B = 400$ 이므로 최소한 $P_{\text{min}} = 800 - 1 = 799$로 선택하면 됩니다. 즉, 각 함수의 양 쪽에 399개의 0을 추가하면 됩니다. 

 

 2D의 상황에서도 동일합니다. $f(x, y)$ 그리고 $h(x, y)$를 각각 $A \times B$ 그리고 $C \times D$의 크기를 갖는 다고 가정하겠습니다. 그러면 아래와 같이 0-패딩을 적용하면 됩니다.

 

$$f_{P} = \begin{cases} f(x, y) &0 \le x \le A - 1 \text{ and } 0 \le y \le B - 1 \\ 0 &A \le x \le P \text{ and } B \le y \le Q \end{cases}$$

$$h_{P} = \begin{cases} h(x, y) &0 \le x \le C - 1 \text{ and } 0 \le y \le D - 1 \\ 0 &C \le x \le P \text{ and } D \le y \le Q \end{cases}$$

 

 이때, 각 $P$와 $Q$는 아래의 조건을 만족하는 임의의 정수이기만 하면 됩니다. 

 

$$P \ge A + C - 1$$

$$Q \ge B + D - 1$$

 

 0-패딩을 적용하면 크기가 $P \times Q$를 얻을 수 있습니다. 만약 두 영상이 모두 같은 크기를 가진다면 $P \ge 2M - 1$, 그리고 $Q \le 2M - 1$을 만족해야합니다. 여기서 대개 DFT는 크기가 짝수인 배열에 더 빠르게 실행되는 경향이 있다고 합니다. 따라서 최소 짝수 정수 $P, Q$를 선택하여 사용하는 것이 제일 좋은 방법이 될거 같습니다. 

 

4. DFT 성질 종합

 아래는 지금까지 설명하지 않은 DFT들을 포함하여 알아두면 좋을 모든 성질들을 종합해놓았습니다. 나중에 필요하실 때 참고해보도록 하겠습니다.

 

[1]. digital image processing 4th edition rafael c. gonzalez

[2].Brigham, E. Oran. The fast Fourier transform and its applications. Prentice-Hall, Inc., 1988.