Fourier transform (푸리에 변환)

2021, Feb 17    

• 참조 : Introduction to Computer Vision
• 참조 : https://youtu.be/TB1A2-Db67s
• 참조 : https://www.youtube.com/watch?v=spUNpyF58BY
• 참조 : https://www.youtube.com/playlist?list=PL5yujGYFVt0DhDXdKkFeou8zSV-KjOlAG (공돌이의 수학정리노트)
• 참조 : https://youtu.be/c8Q2lZvvnJo
• 참조 : https://www.youtube.com/playlist?list=PLEGnaIwMq6ozCqLEM_rEGxvZqqDi63omB

• 이번 글에서는 기본적인 푸리에 변환 (Fourier transform)에 대하여 다루어 보도록 하겠습니다.
• 보다 자세한 내용의 푸리에 변환은 아래 링크를 참조해 주시기 바랍니다. 이 글은 신호와 시스템 전반적인 내용을 다루며 그 중 푸리에 변환에 대한 자세한 내용을 확인하실 수 있습니다.
  • 링크 : https://gaussian37.github.io/vision/signal/

목차

• 푸리에 급수를 배우는 이유

• 푸리에 급수의 의미와 주파수 분석에서의 활용

• 연속 시간 푸리에 급수 유도

• 이산 시간 푸리에 급수 유도

• 연속 시간 푸리에 변환 유도

• 이산 시간 푸리에 변환 유도

• MATLAB 및 Python에서의 Fast Fourier Transform

• 푸리에 변환에서 음의 주파수

• 라플라스 변환과 푸리에 변환

푸리에 급수를 배우는 이유

푸리에 급수의 의미와 주파수 분석에서의 활용

• 아래 두가지 식은 푸리에 급수에 관련된 동일한 식을 다른 관점으로 표현한 식입니다.

• 위 식의 관점은 연속 신호(함수)는 무한 차원 벡터이고, 이것은 기저 벡터의 선형 결합으로 재구성할 수 있음입니다.

• 반면 위 식의 관점은 신호를 구성하는 각 기저 벡터는 얼마 만큼의 기여도를 가지고 있는지를 뜻하며 이는 주파수 분석에 활용 가능합니다.

• 푸리에 급수에 대하여 알아보기 이전에 벡터와 직교에 대하여 간략하게 알아보도록 하겠습니다.

• 벡터 \(\overrightarrow{i}, \overrightarrow{j}\)가 직교한다면 내적 \(\overrightarrow{i} \cdot \overrightarrow{j} = 0\)을 만족합니다.
• 두 벡터가 직교한다는 의미는 두 벡터의 내적이 0임을 뜻합니다. 벡터의 내적은 두 벡터가 얼마나 닮았는 지를 뜻하기 때문에 두 벡터의 내적이 0이되어 직교한다는 뜻은 두 백터가 전혀 닮지 않았다는 뜻이되고 바꿔 말하면 두 벡터가 서로 독립적이라는 말이 됩니다.

• \[\vec{a} \cdot \vec{b} = \vert \vec{a} \vert \vert \vec{b} \vert \cos{\theta}\]

• 이렇게 직교하는 벡터들을 이용하여 단위 벡터를 만들 수 있는데, 2차원에서 2개의 단위 벡터가 있으면 2차원 공간의 모든 벡터를 표현할 수 있습니다. 같은 개념으로 N차원 공간의 모든 벡터를 표현하기 위해서는 N개의 직교하는 벡터가 필요합니다.

• 앞으로 다룰 내용은 함수이기 때문에 벡터가 아닌 함수를 다루어야 합니다. 함수에서도 벡터의 직교와 같은 개념이 있을까요?
• 먼저 함수는 일반화된 벡터로 취급할 수 있습니다. N차원 벡터는 N개의 숫자 나열이듯이 실수 함수는 실수 값을 무한 개 나열한 것으로 본다면 실수 함수는 무한 차원 벡터라고 볼 수 있습니다. 따라서 앞으로는 실수 (혹은 복소수) 함수는 무한차원 벡터로 생각하도록 하곘습니다.
• 이러한 무한 차원의 벡터 공간을 표현하기 위해서 함수의 직교를 이용해야 합니다. 직교하는 함수를 무한 개 찾을 수 있다면 이 함수를 이용해서 어떤 실수 (혹은 복소수) 함수라도 그 구간 내의 함수를 표현할 수 있습니다.

• 함수의 내적은 위 식과 같이 나타낼 수 있습니다. 이는 벡터의 내적과 개념이 유사합니다.
• 벡터의 내적을 할 때 두 벡터 \((a, b), (c, d)\)를 내적하면 \(ac + bd\)가 됩니다. 이와 같이 함수의 내적을 할 때에도 두 함수를 특정 범위 내에서 함수값을 곱해주게 됩니다.
• 위 식을 보면 함수 \(f_{2}(x)\)에는 * 즉, 켤레복소수를 적용해 주도록 되어있습니다. 이는 함수값이 복소수(복소 벡터)일 때, 계산이 실수 공간에서 만족해야 하는 내적의 공리와 연관되어 있기 때문입니다. 따라서 계산을 실수화 하기 위함이라고 보시면 됩니다.

• \[z = a + jb\]
• \[\vert z \vert^{2} = a^{2} + b^{2} = (a + jb)(a - jb) = a^{2} + b^{2} = z \cdot \bar{z}\]

• 복소수의 크기(절대값)을 구할 때에도 켤레 복소수를 통하여 실수화 한 것과 동일한 방식입니다.

• 만약 두 함수가 직교한다는 것은 두 함수의 내적이 0임을 뜻합니다. 이는 벡터의 직교와 같은 의미입니다.

• 무한 차원의 공간을 표현하기 위해서는 무한 차원의 직교하는 함수들이 필요하다고 앞에서 언급하였습니다.
• 범위를 줄여서 (a, b) 구간을 표현하기 위해서는 이 범위에서 직교하는 함수들이 필요합니다. 이 때 사용 될 직교 함수들의 집합을 Orthogonal Set이라고 하며 그 표기법은 위 식과 같습니다. 위 식과 같이 직교하는 함수들의 집합을 통하여 (a, b) 구간 표현할 수 있습니다.
• 따라서 같은 구간에서 정의된 함수 \(f(x)\)는 이 직교 함수들의 대수 합으로 나타낼 수 있습니다.

• \[f(x) = c_{0}\phi_{0}(x) + c_{1}\phi_{1}(x) + c_{2}\phi_{2}(x) + \cdots + c_{n}\phi_{n}(x) + \cdots\]
• \[f(x) = \sum_{n=0}^{\infty}c_{n}\phi_{n}(x)\]

• 앞에서 살펴본 푸리에 급수의 식을 함수 직교와 연관하여 다시 살펴보도록 하겠습니다. 먼저 위 식에서 지수 함수부에 해당하는 식을 자세히 살펴보면

• \[\text{exp}(j \frac{2\pi k}{T} t)\]

• 이산 시간 푸리에 급수에서 위 지수부에 해당하는 식이 orthogonal set이 됩니다.
• 이 값은 오일러 공식 \(\text{exp}(j\theta) = \cos{\theta} + j\sin{\theta}\)을 이용하면 다음과 같이 변환되어 사용되어 집니다.
  • 오일러 공식 참조 : https://gaussian37.github.io/math-calculus-euler_formula/

• \[\text{exp}(j \frac{2\pi k}{T} t) = \cos{\frac{2\pi k}{T} t} + j\sin{\frac{2\pi k}{T} t}\]
• \[x(t) = \sum_{k=-\infty}^{\infty}a_{k}(\cos{\frac{2\pi k}{T} t} + j\sin{\frac{2\pi k}{T} t})\]

• 즉, 어떤 임의의 신호(함수값)은 cos, sin 함수의 합으로 표현할 수 있음을 알 수 있습니다.
• 이 식에서 가장 중요한 것은 지수부의 식 \(\text{exp}(j \frac{2\pi k}{T} t)\)가 Orthogonal set인 지 확인하는 것입니다. 따라서 다음 집합이 orthogonal set인 지 확인해 보겠습니다.

• \[\{\phi_{k}(t) \ \vert \ \phi_{k}(t) = \text{exp}(j \frac{2\pi k}{T}t), \ \ k = \text{integer on } [0, T] \}\]

• 위 집합의 임의의 두 원소인 함수 \(\phi_{\color{red}{k}(t) = \text{exp}(j \frac{2\pi \color{red}{k}}{T} t)\)와 \(\phi_{\color{blue}{p}}(t) = \text{exp}(j \frac{ 2\pi \color{blue}{p} }{T} t)\)가 있을 때, 두 함수의 내적을 해보겠습니다.

• \[\begin{align} \int_{0}^{T} \phi_{k}(t) \phi_{p}^{*}(t) dt &= \int_{0}^{T} \text{exp}(j \frac{2\pi k}{T} t) \text{exp}(-j \frac{2\pi p}{T} t)dt \\ &= \int_{0}^{T} \text{exp}(j \frac{2\pi (k-p)}{T} t)dt = \Biggl[ \frac{T}{j 2\pi (k-p)} \text{exp}(j \frac{2\pi (k-p)}{T} t) \Biggr]_{0}^{T} \\ &= \frac{T}{j 2\pi (k-p)} [ \text{exp}(j 2\pi(k-p)) - 1] \\ &= \frac{T}{j 2\pi (k-p)}[\cos{(2\pi(k-p))} + j\sin{(2\pi(k-0))}] = 0 \quad (\because \cos{(2n\pi)} = 0 \text{ and } \sin{(2n\pi)} = 1) \end{align}\]

• 따라서 서로 다른 \(k\)와 \(p\)에 대하여 두 함수가 내적이기 때문에 위 집합은 orthogonal set임을 확인할 수 있습니다.
• 처음 위 식을 설명할 때 다음과 같은 문구와 같이 설명하였었습니다.

• 위 식의 관점은 연속 신호(함수)는 무한 차원 벡터이고, 이것은 기저 벡터의 선형 결합으로 재구성할 수 있음입니다.
• 이 때, 기저 벡터는 삼각 함수이므로 \([0, T]\) 구간 사이에 정의된 어떤 주기 신호는 삼각 함수의 선형 결합으로 재구성 할 수 있음을 확인하였습니다.

• 다음으로 아래 식과 뜻에 대하여 알아보도록 하겠습니다.

• 반면 위 식의 관점은 신호를 구성하는 각 기저 벡터는 얼마 만큼의 기여도를 가지고 있는지를 뜻하며 이는 주파수 분석에 활용 가능합니다.

• 위 \(a_{k}\) 식에 대하여 생각해 보기 위해 주기 \(T = 1\)인 임의의 신호 \(x(t)\)에 대해서, \(k=1\)일 때, \(a_{k}\)의 의미를 살펴보겠습니다.

• \[a_{1} = \int_{0}^{1} x(t) \text{exp}(-j 2\pi t) dt = \int_{0}^{1} x(t) \times \{\cos{2\pi t - j \sin{2\pi t}} \} dt\]

• 위 식에서 cos 함수는 1Hz를 가지고 sin 함수는 3Hz를 가진다고 가정을 하여 식을 정하면 위 그래프와 같이 나타낼 수 있습니다.
• 왼쪽의 큰 그래프는 함수 \(x(t)\)를 뜻하며 수식에 해당하는 그래프를 그리면 위 그래프와 같습니다.
• 이 \(x(t)\) 함수와 \(\cos{2 * \pi * 1 * t}, \sin{2 * \pi * 1 * t}\)를 각각 내적 후 적분을 취하면 각각 0.5, 0이 됨을 계산할 수 있습니다.

• 상세 계산 과정 : 링크

• 상세 계산 과정 : 링크

• 앞에서 설명하였듯이 내적은 두 벡터 또는 함수가 얼마나 닮았는 지 나타냅니다. 위 식에 이 개념을 대입하면 \(x(t)\)의 삼각함수 성분 중 kernel의 성분을 얼만큼 내포하고 있는 지 뜻하게 됩니다. 여기서 kernel은 \(x(t)\)에 곱해지는 \(\cos{2 \pi t}, \sin{2 \pi t}\)에 해당합니다.

• 위 계산은 \(a_{1}\)의 경우에 해당합니다. 계산해야 하는 전체 영역은 음의 무한대에서 양의 무한대이기 때문에 전 과정을 계산을 해야 푸리에 급수를 나타낼 수 있습니다. 따라서 몇 가지 \(a_{k}\)를 좀 더 다루어 보도록 하겠습니다.

• 위 그래프는 \(a_{2}\)를 나타냅니다.

• 위 그래프는 \(a_{0}\)을 나타냅니다. cos, sin 함수가 상수로 수렴되기 때문에 계산이 쉽게 가능합니다.

• 이번에는 음의 방향으로 계산을 해보겠습니다. 위 그래프는 \(a_{-1}\)을 나타냅니다.

• 이와 같은 계산을 -3 ~ 3까지 적용하였을 때, 위 테이블과 같습니다.
• 위 테이블에서 \(a_{-3} = j * 0.4, a_{3} = -j * 0.4\)임을 확인할 수 있습니다. 여기서 \(j\)는 복소 평면의 Im 축을 나타내며 이와 관련된 자세한 내용은 아래 글을 통하여 복소 평면의 개념을 확인 하실 수 있습니다.
  • 링크 : https://gaussian37.github.io/math-calculus-phasor/
• 간단한 이해를 위하여 가로축은 실수축 Re로 생각하고 세로축은 허수축 Im로 생각하고 \(j\)가 붙은 숫자는 복소 평면에서 Im 축의 숫자로 이하해시면 됩니다.

• cos 함수의 자취는 위에서 바라보았을 때, 막대의 길이 자취와 같고 sin 함수의 자취는 오른쪽에서 바라보았을 때, 막대의 길이와 같습니다.
• 가로축인 실수축 Re는 실수부에 해당하고 세로축인 허수축 Im는 허수부에 해당합니다. 따라서 앞의 테이블의 \(j\)는 허수부에 해당하고

• 테이블의 \(a_{k}\)의 크기를 확인하기 위하여 \(a_{k}\)의 절대값을 취한 뒤 그래프로 나타나면 위 그래프와 같습니다.
• 여기서 주파수를 구해보겠습니다. 일반적으로 \(\cos{2 \pi \color{red}{f} t}\)에서 \(\color{red}{f}\)가 주파수를 뜻합니다.

• \[\text{exp}(-j \frac{2\pi k}{T} t) = \cos{\frac{2\pi \color{red}{k}}{\color{red}{T}} t } -j\sin{\frac{2\pi \color{red}{k}}{\color{red}{T}}t }\]

• 위 식과 같이 cos, sin 함수를 정의 할 수 있기 때문에 주파수는 \(k / T\)가 되고 \(T = 1\)로 가정을 하였기 때문에 주파수는 \(k / T = k\)가 되어 가로축이 주파수 Hz가 됨을 알 수 있습니다. 따라서 그래프를 조금 수정하면 다음과 같습니다.

• 따라서 위 그래프와 같이 \(a_{k}\)를 이용하여 가로축이 주파수인 주파수 분석을 할 수 있음을 의미합니다.
• 위 그래프를 해석하면 1, -1 Hz 성분은 0.5씩 존재하고 3, -3 Hz 성분은 0.4씩 존재한다는 것을 확인할 수 있습니다. 여기서 음의 주파수의 의미는 이 글에 뒷부분에서 다루겠습니다.
• 이 값을 처음에 다룬 \(x(t) = \color{red}{1}*\cos{2 \pi \color{red}{t}} + \color{blue}{0.8}\sin{2 \pi \color{blue}{3t}}\)와 연계해서 보면 cos의 1Hz 성분 \(\color{red}{t}\)를 음의 주파수, 양의 주파수 반반씩 0.5로 나타내어 지고 (0.5 * 2 = \(\color{red}{1}\)), sin의 3Hz 성분 \(\color{blue}{3t}\)를 음의 주파수, 양의 주파수 반반씩 0.4로 나타내어 집니다. (0.4 * 2 = \(\color{blue}{0.8}\))

연속 시간 푸리에 급수 유도

• 앞에서 다룬 내용을 기반으로 연속 시간 푸리에 급수를 유도해 보도록 하겠습니다.
• 연속 시간 푸리에 급수는 주기 \(T\)를 가지는 연속 함수 \(x(t) = x(t + T)\)를 정현파의 합으로 표현할 수 있음을 의미합니다.

• \[x(t) = \sum_{k=\infty}^{\infty} a_{k} \exp{(j \frac{2\pi k}{T})t}\]
• \[\exp{j\theta} = \cos{\theta} + j \sin{\theta}\]

• 이 성질은 오일러 공식을 이용하였을 때, 지수 함수 부가 정현파의 합으로 표현되는 것을 이용하기 때문에 성립하는 것을 알 수 있습니다.
• 또한 푸리에 급수에서 \(a_{k}\)를 기준으로 식을 정리하면 다음과 같이 정리할 수 있습니다.

• \[a_{k} = \frac{1}{T} \int_{0}^{T} x(t) \exp{(-j \frac{2\pi k}{T}t)} dt\]

• 이번 글에서는 푸리에 급수로 나타내는 \(x(t)\) 식의 의미와 \(a_{k}\)로 식을 전개하는 방법에 대하여 다루어 보도록 하겠습니다.

• 푸리에 급수의 의미와 주파수 분석에서의 활용에서 자세히 다룬 것 처럼 푸리에 급수의 의미를 알기 위해서는 orthogonal function에 대한 의미를 알아야 합니다.
• 이 의미는 벡터의 내적을 통하여 확장할 수 있습니다. 두 벡터 \(\overrightarrow{i}, \overrightarrow{j}\) 가 내적한다면 \(\overrightarrow{i} \cdot \overrightarrow{j} = 0\) 관계를 가지고 이 때,직교함을 알 수 있었습니다. 그리고 직교하는 N개의 벡터를 이용하여 N차원의 모든 좌표를 표현할 수 있음을 확인하였습니다.
• 이 개념을 함수 영역으로 확장하겠습니다. 먼저 함수는 벡터의 개념이 확장된 것으로 이해할 수 있습니다. 함수 \(f(t)\)에서 \(t\)의 값에 따라 함수 값이 출력이 되는데 이를 벡터 형태로 나타낼 수 있고 함수값이 무한이 늘어나면 무한 차원의 벡터로 해석할 수 있습니다.
• 이러한 관점에서 두 함수 \(f_{1}(t), f_{2}(t)\)를 내적해 보도록 하겠습니다. 두 함수의 내적을 할 때, 범위는 \([a, b]\) 구간으로 두고 이 구간의 함수값에 대하여 내적을 하기 위해 정적분을 하도록 하겠습니다.

• \[\int_{a}^{b} f_{1}(t) f_{1}(t) f_{2}(t) dt = 0\]

• 위 식을 함수의 내적이라고 보았을 때 \(f_{1}(t), f_{2}(t)\)는 구간 \([a, b]\)에서 직교한다는 것을 알 수 있습니다. 여기까지는 벡터의 내적 개념과 큰 차이가 없습니다.
• 이 개념을 이용하면 구간 \([a, b]\)에서 직교하는 함수 \(f_{1}(t), f_{2}(t)\)를 이용하면 구간 \([a, b]\)의 모든 함수를 표현할 수 있다고 생각할 수 있습니다.
• 예를 들어 함수 \(f_{1}(t), f_{2}(t), f_{3}(t)\)가 구간 \([a, b]\)에서 직교한다고 가정해 보겠습니다. 임의의 함수 \(f_{n}(t)\)는 다음과 같이 표현할 수 있습니다.

• \[f_{n}(t) = a_{1}f_{1}(t) + a_{2}f_{2}(t) + a_{3}f_{3}(t) = \sum_{i=1}^{\infty} a_{i}f_{i}(t)\]

• 합으로 표현된 \(f_{i}(t)\)는 구간 \([a, b]\)에서 서로 직교하는 함수의 집합으로 표현할 수 있습니다. 이를 orthogonal set이라고 합니다.

• \[x(t) = \sum_{k=\infty}^{\infty} a_{k} \exp{(j \frac{2\pi k}{T})t}\]

• 그러면 위 식에서 \(\exp{(j \frac{2\pi k}{T})t}\)가 모든 정수 \(k\) 에 대하여 orthogonal set인지 증명을 하면 어떠한 연속 함수를 정현파의 합으로 표현할 수 있음을 확인할 수 있습니다.

이산 시간 푸리에 급수 유도