1. 1-Dimension Discrete Fourier Transform
1.1. 1D Discrete Fourier Transform
Why do we need to do Discrete Fourier Transform(DFT)? A Discrete Fourier Transform has been proposed since we cannot apply Continuous Fourier Transform in the real world. Specifically, a continuous fourier transform requires us to integrate from negative infinite to the positive infinite, which is impossible. Therefore, countable samples should be set in the domain so as to apply discrete fourier transform. This process converts a wave or an image from time domain to continuous domain. (By doing this process, we can get some benefits: saving data, extract the information we want, etc)
Let’s take a look at a simple example of sine wave. This sine wave is , whose frequency is 1 Hz. In order to see the simplest version of Discrete Fourier Transfrom, let’s assume that we are dividing 1 period sine wave into 4 samples.
Now, we want to transform these four points into new points by Discrete Fourier Transform,
Specifially, take a look at be transformed into
Similarly, computations would be made on , and this can be expressed visually by matrix form.
Then, as we can see the below, the time domain – input sequence has been transformed into the frequency-domain – magnitude response.
But, here we can come up with a question:
Why did 3Hz frequency mapping has showed up although there were only 1Hz wave?
⇒ The answer can be found from the “sampling order”
To simply illustrate this, below images could be a good example.
Originally, while we do Fourier Integral or Fourier Transform, the domain is from to . As we assume that we support the sine wave into , the sample numbering should be done in the order of as above. However, actual Discrete Fourier Transform is sampled in the order of . Thus, we can expect that the DFT results will be symmetric to the continuous version of Fourier Transform or Fourier Integral.
This way of calculation concludes the shift of the ramification. As we can see below, the half of the outcome on the negative frequency domain is shifted to the positive frequency domain. (Since this always happens to Fourier Transform, scientists usually use “fft shift” function to visualize it)
Since the image is always symmetric with respect to the half of the Sample Frequency. It is called a Nyquist Limit.
Likewise, wave could be transformed into the frequency domain, resulting frequency 1Hz, and 2Hz.
Thus, the actual frequency domain until Nyquist limit is called the “Nyquist Domain” and the copied frequency is called the “Periodic Mirrored Mapping”
There is an another question:
What happens if we have more sample frequency?
Let’s look at the below discrete transform with 16 samples.
The result can be compared to the first graph with 4 samples.
Since the above samples has 4 times more samples, the intensity is 4 times stronger. And the frequency range has become wider.
Moreover, the Nyquist limit is moved from 2Hz(4/2=2) to 8Hz(16/2).
Therefore, the copied frequency appeared on the 15Hz.
(In medical imaging, lower frequencies are more crucial than higher frequencies. Hence, fourier shifting is essential to handle the information easily.)
1.2. The General Form of Discrete Fourier Transform
Generalizing the samples with an integer N yields the following relations.
1 Dimension Discrete Fourier Transform can be generalized as a matrix form by substituting .
1.3. Inverse Discrete Fourier Transform
How can we implement Dicrete Fourier Transform of the frequency signals?
Surprisingly, by applying Inverse Discrete Fourier Transform, we can perfectly restore the information we have transformed. The relations can be generalized from the below example.
Since complex conjugate is , the simplest multiplication of and is as below.
Did you find the simple relation of and ?
If we generalize that to the integer , (we skip the proof of it using mathematical induction) we can elicit the below relation.
Finally, we get the Inverse Discrete Fourier Transform.
In summary, calculating complex conjugate of can be simply done by just changing the sign of the Discrete Fourier Transform. And after that, dividing by N, sample numbers, results in the form of Inverse Fourier Transform matrix.
1.4. 1D Fast Fourier Transform
Since the discrete transform’s cost is too expensive(), An alternative method is developed by Yates, Frank which is extremely faster than that of Discrete Fourier Transform. The following example can be helpful to clarify this.
(Example Matrix with 4 samples)
The strategy of Fast Fourier Transform is seperating even terms and odd terms to lower the computing cost.
The first step is changing the odd column and even column to gather same parities.
The second step is using the characteristic of complex plane. Since , , the higher terms of can be simplified to lower terms.
The third step is simplifying the matrix to lower the cost of computation.
Computating cost is changed from to .
The more samples we have, the stronger the FFT is.
The Generalized Fast Fourier Transform can be illustrated as below diagram.
To implement FFT, we need to seperate the even terms and odd terms first. And then adding and subtracting each pair of even parities and odd parities will outcome the beautiful ramifications.
2.1. 2D Discrete Fourier Transform & Fast Fourier Transform
The actual goal of conducting Fourier Transform is applying it to 2 Dimension images such as MRI images or CT images. It sounds hard, but the algorithm is actually simple if we understood 1 dimension algorithm.
It is nothing but just doing 1D DFT/FFT 2 times to rows and to columns.
But one thing we need to notice is that as we can see from the above algorithm, the lower frequency is centered at the each corners (as we remind 1D Fourier Transform results are biased), especially left top corner.
So, by fourier shifting( the built in function is fftshift2(img) in matlab), the lower frequencies are shifted to the center of the image and the higher frequencies are located to the edge.
(The simple example of 2D DFT & FFT)
As we transform the sine waves, the DFT/FFT catches the 1 hz frequency each. The -component is of the row frequency, and the -component is of the column frequency.
If we apply Inverse Fourier Transform, it perfectly recovers the original image.
(The example of phantom(512 * 512))
Here we can think of another question in the current research topic:
Can we recover the image even though we don’t have 100% samples from frequency domain?
We come up with this question because when we first get images from CT scan, the results are handed in the form of 2 dimension frequency images. And then recover them to the real image.
However, it takes almost 1 hour to scan a human body without any movement. If the woman moves a little bit, or sneeze, the image can be completely distorted. This is a huge loss in monetary, and time aspect.
If we Inverse Fourier Transform the 50% sampled frequency image, the result is weird as above. This effect can be understood by Poisson Summation Formula. (We do not handle this in this page)
This problem has been solved recently by using deep learning technique. If you are interested, I recommend you to refer the research of Changmin Hyun, Department of Computational Science and Engineering, Yonsei University.
Writer: Keunsik Jung, Youngbin Cho, Hyunchul Cho
- Discrete Fourier Transform – Simple Step by Step. Simon Xu. https://www.youtube.com/watch?v=mkGsMWi_j4Q&t=328s
- Kreyszig, E. (2006). Advanced engineering mathematics (10th ed.). Hoboken, NJ: Wiley.
- Yates, Frank (1937). “The design and analysis of factorial experiments”. Technical Communication no. 35 of the Commonwealth Bureau of Soils.
- Fast Fourier Transform. (n.d.)l. in Wikipedia. Retrieved August 30, 2017, from https://ko.wikipedia.org/wiki/%EA%B3%A0%EC%86%8D_%ED%91%B8%EB%A6%AC%EC%97%90_%EB%B3%80%ED%99%98