주파수 영역처리(푸리에 변환)

푸리에 변환의 종류는 여러가지가 있으나 대충 크게 나누어 보면 2가지를 들 수 있다.

1. DFT(Discrete Fourier Transform, 이산(불연속) 푸리에 변환)
: 연속적인 신호를 시간에 따라 Sampling을 한 형태의 신호로 생각하여 푸리에 변환식을 그대로 계산

2. FFT(Fast Fourier Transform)
: DFT는 연산시 시간이 너무 오래 걸리기 때문에 실제 계산에서 나타나는 항의 주기성과 대칭성을
  이용하여, 신호의 전부의 변환이 아닌, 필요한 신호만을 골라내어 최소화하며 고속으로 푸리에 변
  환을 연산한다.
  예를 들어 총 8개의 DFT 신호가 있다 가정하면, 4개를 먼저 골라낸 후, 다시 4개의 신호를 단순히
  연결함으로서 제외된 신호들의 예상치를 적용하게 되는 방법.
  실제로 변환 시간의 분제로 인해, 실제적으로 거의 대부분 FFT를 사용하고 있으며, 빠르기는
  DFT에 비해 최고 약 1000배의 시간차이를 보여준다고 한다.

푸리에 변환은 보통 아날로그 신호를 받아서 처리하는 기술의 하나로 사용 되기 때문에 항상
"실시간"으로 진행되어야 한다. 따라서, 속도가 느리면 안되므로, 속도를 보다 빠르게 개선하기 위해
보통 고속 푸리에 변환(FFT)을 사용한다.

주어진 신호의 개수 N이 이를 따른다고 가정 할 때,
N의 갯수는 짝수이며, 반으로 나눌 수 있고, 이는 N=2C로 표현할 수 있다.

이산 푸리에 변환(DFT)에 이를 대입하면

와 같다. 여기서 보면 N개의 점에 대해서, 각각 짝수 번째와 홀수 번째의 그룹으로 나누어
계산 할 수 있다는 걸 알 수 있다. 또한, 각 항에 대해 정리를 하면,

처럼 되며, 이를 다시 원래의 식에 대입하여 나온 식을 구성하고 있는 두 항목 각각은
짝수와 홀수그룹으로 정의 할 수 있다.

     -->  짝수 그룹


     -->  홀수 그룹


각 항은 주어진 N개의 점들 중 각각 짝수 번째, 홀수 번째에 해당하는 점들 N/2개를 이용하여
계산한 값이다. 이를 다시 위의 식에 대입하면

와 같은 식을 얻을 수 있다. 이를 이용하여 N개의 점이 주어진 경우 각각 짝수, 홀수 번째 점들의
두 그룹으로 나누어 계산을 한 후 S(0),...,S(C-1)=(N/2-1)까지의 값을 구할 수 있다.

그리고 나머지 S(C)=S(N/2), S(L+1),...,S(N-1)의 값은

로 구할 수 있다. 나머지 절반에 대한 점들의 계산에 기존의 계산결과를 그대로 이용할 수 있음을
알 수 있으며, 이를 통해 고속 연산이 가능하게 된다.
현재 경우에는 N개의 신호점들을 N/2개의 그룹으로 나눈 것이지만, 동일하게 N/2의 각 그룹을
다시 N/4의 짝수 그룹과 홀수 그룹으로 나눌 수 있으며, 이것을 최종적으로 2개의 신호점으로
이루어진 그룹까지 들어간 후에, 위의 식들을 이용하여 계산을 수행하게 된다.

위에서 말한 8개의 점을 예를 들면

S(0)   S(1)   S(2)   S(3)   S(4)   S(5)   S(6)   S(7)

이 점들은 S(0) S(2) S(4) S(6)의 홀수번째 그룹과
              S(1) S(3) S(5) S(7)의 짝수번째 그룹으로 나뉘며,

이는 각각의 그룹에 대해 다시

 S(0) S(4)   S(2) S(6)       S(1) S(5)   S(3) S(7)
짝수의홀수 짝수의짝수     홀수의홀수 홀수의짝수

각각의 번째 그룹으로 다시 나뉘며, 이산 푸리에 변환의 연산時
각 점에 대해 단순한 계산을 하면 8 by 8 = 64 이지만,
각 점에 대해 고속 푸리에 계산은 8 by 3 = 24 로서 40회의 계산을 줄일 수 있다.

이러한 푸리에 변환을 영상에 적용하고자 하면, 정지영상 자체를 놓고 볼 때는 행과 열을 갖는
2차원 데이터이므로, 2차원 함수에 대한 이산 푸리에 변환 S(x,y) 을 이용해야 한다.

푸리에 변환은 잡음제거, 엠프기술, 음성 및 그림 압축 등등 수많은 곳에서 사용되는 기술이다.
이것이 가능한 이유는 각 주파수 별로 신호를 쪼개서 나누는 것이 가능하기 때문이다.
푸리에 변환 기술을 이용해서 각 주파수 별로 신호를 나누면 필요한 데이터와
쓸모없는 데이터(Garbage)를 구분해 내기 쉬워지겠다.
가령 잡음의 경우는 일정한 Pattern으로 나타나는 경우가 많으므로, 해당하는 Pattern의
주파수만 0으로 Clipping 시켜버리면 잡음은 제거된다.
또한 각 주파수중 특정 일부 주파수만 키우면 특정 악기의 소리를 키울 수 있거나, 특정 Pattern을
강조 할 수 있겠다.
또한 각 주파수중 잡음과 같이 특정 일부 주파수를 아예 지워버리고 저장하면 데이터의 양이
줄어들게 되므로 압축에도 사용 할 수 있겠다. (Ex : JPG, MP3, MPEG)