2020년 9월 20일 일요일

이산 푸리에 변환(DFT: Discrete Fourier Transform)

[경고] 아래 글을 읽지 않고 "이산 푸리에 변환"을 보면 바보로 느껴질 수 있습니다.


이산 푸리에 변환(discrete Fourier transform, DFT)푸리에 변환(Fourier transform)을 컴퓨터 상에서 구현할 때 사용하는 중요 개념이다. 이산(離散, discrete) 푸리에 변환은 명칭에도 있듯이 연속적이지 않고 이산적으로 변하는 함수에 대한 푸리에 변환이다. 컴퓨터는 원론적으로 연속 함수(continuous function)를 다룰 수 없기 때문에, 수치 해석에서는 컴퓨터에 저장하기 쉬운 이산화(離散, discretization)를 적극적으로 채택한다. 

[그림 1] 이산 푸리에 변환의 적용 예시(출처: wikipedia.org)

연속적으로 변하는 함수 $f(t)$를 이산적으로 바꾸려면, 연속 함수에 [그림 2]와 같은 표본화(sampling)를 적용한다. 표본화하는 주기를 $\Delta t$, 표본 개수를 $M$이라 하면, $f(t)$를 이산화한 전체 표본화 시간은 $T$ = $M \Delta t$가 된다. 하지만 표본화 시간인 $0 \le t < M\Delta t$에서는 함수 $f(t)$의 값을 알지만, 나머지 시간에서는 함수값을 알 수 없게 된다. 이때는 $f(t)$를 과감하게 주기 $T$를 가진 주기 함수(periodic function)라 가정한다. 그래서 표본화된 함수 $f_\text{sa}(t)$는 주기가 $T$이면서 $t$ = $m \Delta t$[$m$ = $0, \pm 1, \pm 2, \cdots$]에서만 값이 이산적으로 존재하는 주기 함수가 된다.

[그림 2] 연속 함수의 표본화 예시(출처: wikipedia.org)

DFT 관계식을 유도하기 위해, 먼저 복소 푸리에 급수(complex Fourier series)푸리에 변환(Fourier transform) 공식을 고려한다.

                  (1)

                  (2)

여기서 $\omega_0$ = $2 \pi/T$이다. 푸리에 변환은 $F(\omega)$ = $\lim_{T_\text{tot} \to \infty} \widetilde{F}_m T_\text{tot}$로 정의한다. 여기서 $T_\text{tot}$는 $f(t)$가 존재하는 전체 시간이다. 함수 $f(t)$가 전체 표본화 시간 $T$를 주기로 반복되고 이상적인 표본화는 디랙 델타 함수(Dirac delta function)라고 가정하면, 푸리에 변환보다는 식 (1)에 있는 푸리에 급수가 표본화된 함수 $f_\text{sa}(t)$의 해석에 더 적절하다. 그러면 $f_\text{sa}(t)$에 대해, 푸리에 변환에서 유추한 새로운 DFT의 푸리에 계수 $F_k$를 다음처럼 얻을 수 있다.

                  (3)

여기서 표본화 계수 $f_m$ = $f(m \Delta t)$이다. 식 (3)에 $k$ = $k + M$을 대입하면, $F_k$ = $F_{k+M}$이 항상 성립한다. 이 결과는 $F_k$가 주기 $M$을 가지고 반복되는 계수임을 뜻한다. 푸리에 계수 $F_k$를 식 (1)에 대입해서 $F_k$의 무한 합으로 $f_\text{sa}(t)$를 다음과 같이 표현한다.

                  (4)

여기서 $f_\text{sa}(t)$의 정의역을 $0 \le t < T$로 제한한다. 식 (3)의 첫째식과 식 (4)의 마지막식을 비교해서 다음 결과를 유도한다.

                  (5)

따라서 이산 푸리에 변환쌍(DFT pair)을 다음처럼 표현할 수 있다.

                  (6)

식 (6)을 한 차원 더 확장해서 2차원 이산 푸리에 변환쌍을 정의할 수도 있다.

                  (7)

식 (6)의 첫째식을 둘째식에 대입하거나 둘째식을 첫째식에 대입하면, 다음 항등식이 유도된다.

                  (8)

여기서 $\delta_{ml}$은 크로네커 델타(Kronecker delta)이다. 식 (8)의 최종식은 등비 급수(geometric series)를 적용해서 간단히 얻을 수도 있다.

                  (9)

[그림 3] 여러 가지 이산 코사인 변환(출처: wikipedia.org)

이산 코사인 변환(discrete cosine transform, DCT)은 DFT의 현실적인 변형이다. DFT는 푸리에 변환을 실제 수치 해석에 적용할 때 매우 유용하다. 하지만 DFT의 계수 $F_k$는 복소수라서 다루기 불편하다. 만약 DFT 대신 DCT를 쓰면, 변환 결과는 실수가 되기 때문에 아주 편해진다. 현실적인 신호 처리에 필수적인 DCT는 아메드Nasir Ahmed(1940–)가 1972년아메드 32세, 박정희 정부 시절에 제안했다. [그림 3]에 있는 여러 DCT 중에서 가장 쉬운 형태인 DCT-I을 보자. [그림 3]처럼 모든 DCT는 우함수(even function) 특성을 쓰기 때문에, DFT 기준으로 보면 $f_m$ = $f_{-m}$이 항상 성립한다. 또한 표본화된 함수는 계속 반복되므로, DCT는 주기적인 특성이 나타난다. 예를 들어 DCT-I의 주기는 $2M-2$이다. 하지만 DCT를 적용하는 함수가 반드시 우함수이어야 할까? 아니다. 함수 $f(t)$는 우함수일 필요는 없고, 어떠한 $f(t)$이든지 [그림 3]과 같이 대칭적으로 함수값을 배정하여 우함수를 강제적으로 만들 수 있다. 즉 [그림 3]에서 빨간색은 직접 측정해서 대상의 정보를 가진 실제 표본이고, 검정색은 각 DCT 방법에 맞도록 실제 표본으로 생성한 부차적인 계산 표본이다. [그림 3]의 DCT-I처럼 $0 \le m < M$에서 표본화한 함수값[그림 3에서 빨간색]을 $x_m$ = $f(m \Delta t)$라 한다. 그러면 표본화한 범위를 넘는 $M \le m < 2M-2$에 대해, 우함수 특성인 $f_m$을 다음처럼 표현할 수 있다.

                  (10)

여기서 $f_m$은 $m$ = $M-1$ 기준으로도 우함수이다. 의도적으로 주기 $2M-2$를 가진 우함수로 만든 DFT의 표본화 계수 $f_m$을 식 (6)에 대입해 본다.

                  (11)

여기서 $F_k$의 주기도 $2M-2$이다. DCT-I의 푸리에 계수를 $X_k = F_k /2$로 정의해 정리하면, DCT-I의 변환식을 얻을 수 있다.

                  (12)

DCT-I의 표본화 계수 $x_m$이 실수라서 $X_k$도 당연히 실수가 된다. 또한 식 (12)에 의해 $X_k$는 우함수이면서 $k$ = $M-1$ 기준으로도 우함수가 된다. 즉 $X_k$ = $X_{-k}$ = $X_{2M-2-k}$[$k$ = $0, 1, \cdots, M-1$]가 성립한다. 그러면 $k$의 범위를 $0 \le k < M$로 제한해도 문제는 없다. 이 특성을 식 (6)에 대입해서 $x_m$을 위한 DCT-I의 역변환식도 얻는다.

                  (13)

여기서 $0 \le m < M$. 식 (12)와 (13)에서 새로운 DCT-I 공식을 얻었지만, DCT의 표현식이 간결해 보이지는 않는다. 그래서 DFT의 표본화 계수 $f_m$을 다음처럼 다시 정의해서 DCT-I과는 다른 공식 전개를 해본다.

                  (14)

여기서 $f_m$의 주기는 $4M$이다. 식 (11)과 비슷하게 식 (14)를 식 (6)에 대입한다.

                  (15)

여기서 $F_k$의 주기도 $4M$이다. DFT의 푸리에 계수를 바꾸어 $X_k = F_k /2$로 정의하면, 식 (15)에 의해 [그림 3]에 있는 DCT-II의 푸리에 계수를 얻는다.

                  (16)

여기서 $0 \le k < M$. 식 (12)와 비교하면 식 (16)은 매우 깔끔한 DCT-II의 표현식이다. 그래서 보통 DCT라고 하면 DCT-II를 의미한다. DCT-II 푸리에 계수 $X_k$의 주기 특성을 알기 위해 $X_{2M \pm k}$를 식 (16)에 대입하면, [그림 3]에 있는 DCT-III와 비슷하게 $X_{2M \pm k}$ = $-X_k$를 얻을 수 있다. 푸리에 계수 $X_k$의 주기는 분명 $4M$이지만, $X_k$와 $X_{2M \pm k}$는 서로 기함수 관계이기도 하다. 그러면 식 (16)에서 $k$의 범위를 $0 \le k < M$로 제한해도 문제없다. 이를 이용해 DCT-II의 역변환식을 구해보자.

                  (17)

여기서 $X_{2M}$ = $-X_0$. 기함수 관계 $X_{2M \pm k}$ = $-X_k$를 다시 식 (17)에 적용해서 간결하게 정리한다.

                  (18)

여기서 $0 \le m < M$, $X_M$ = $0$이다. 노이만 수(Neumann number) $\varepsilon_k$를 이용해 식 (18)을 더 간단하게 표현한다.

                  (19)

여기서 $\varepsilon_m$ = $2 - \delta_{m0}$, $\delta_{ml}$은 크로네커 델타(Kronecker delta)이다. 식 (12)와 (19)에서 유추해서 [그림 3]에 있는 DCT-III의 변환식도 정의할 수 있다.

                  (20)

여기서 $0 \le k < M$. DCT-II와 DCT-III은 비율 상수가 약간 다르지만 서로 역변환 관계를 가진다. 식 (7)에 있는 2차원 DFT와 비슷하게 2차원 이산 코사인 변환쌍을 정의할 수 있다. 예를 들어, DCT-II의 변환쌍은 다음과 같다.

                  (21)

                  (22)

[그림 3]에 4가지 종류의 DCT를 소개했지만, DCT의 표본화 계수 $x_m$에 기반을 둔 DFT의 표본화 계수 $f_m$을 다양하게 정의해서 다채로운 우리만의 DCT를 정의할 수도 있다. DCT를 어떻게 정의하든지 우함수 혹은 기함수의 대칭을 사용하므로, 표본화된 함수의 주기는 원래 경우보다 배 이상 늘어난다. 주기 $T$가 늘어나면, $\omega_0$ = $2 \pi/T$의 관계에 의해 주파수 영역의 계수 간격이 줄어든다. 따라서 DFT보다는 DCT의 푸리에 계수가 저주파에 더 많이 모이므로, 고주파 성분을 자르는 손실 있는 영상 압축 등에 DCT를 많이 사용한다.

[다음 읽을거리]

댓글 6개 :

  1. 식 16에서 M이 샘플의 개수인가요? 원래 신호의 샘플의 개수가 N개 이면 M=N이 되는건가요?
    아니면.. 원래 신호를 대칭으로 만들어서 M이 2N-1이 되어야 하나요? ㅠㅠ

    답글삭제
    답글
    1. 1. 네, 맞습니다. 실제 얻은 표본의 개수입니다. [그림 3]에서는 빨간색으로 표시되어 있어요.

      2. 본문에도 있듯이, M개의 실제 표본으로 DCT에 맞는 계산 표본을 적절히 만들어요. [그림 3]에 있는 검정색이 계산 표본입니다.

      삭제
    2. 답글 감사합니다 거북이님! 한가지 더 궁금한게 있는데요. 식 15를 이용하여 F(k) 를 구하면 F(0)은 DC 값을 의미하는건 알겠는데..
      F(1), F(2), ... F(M-1)은 무엇을 의미하나요? 그림 그려서 보면.. 각 파수에 대한 계수가 아닌거 같아서요..

      삭제
    3. 식 (14)와 같은 표본화된 신호 $f_m$에 대한 DFT입니다. 이걸 깔끔한 DCT-II 공식으로 바꾸는 방법을 설명하고 있어요.

      삭제
  2. 감사합니다 천천히 읽어보겠습니다

    답글삭제

욕설이나 스팸글은 삭제될 수 있습니다. [전파거북이]는 선플운동의 아름다운 인터넷을 지지합니다.