Department of Electrical, Electronic and Computer Engineering

ESP 411 | Special Assignment Report | | Mark awarded | |

Plagiarism declaration

1. I understand what plagiarism is and am aware of the University’s policy in this regard.
2. I declare that this report is my own original work. Where other people’s work has been used (either from a printed source, Internet or any other source), this has been properly acknowledged and referenced in accordance with departmental requirements.
3. I have not used work previously produced by another student or any other person to hand in as my own.
4. I have not allowed, and will not allow, anyone to copy my work with the intention of passing it off as his or her own work.

Name | Student number | Signature | | | | Date | |

Contents Table of Figures 3 Acronyms Used 3 PART 1 Filtering in the Frequency Domain 3 Introduction 3 Review of Prior Knowledge 4 Complex Numbers 4 Fourier series 4 Fourier Transform 4 Convolution Theorem 5 Overview 5 2-D FFT 6 DFT 6 IDFT 7 2-D FFT 7 Comparison with 1-D FFT 8 2-D FFT and Image Processing 8 Image Smoothing and Sharpening 9 Smoothing 9 Sharpening 11 Conclusion 13 PART 2 Application of Filtering in the Frequency Domain 13 Introduction 13 Gaussian Filter Theoretical Analysis 13 Gaussian Low Pass Filter 14 Gaussian High Pass Filter 14 Gaussian Filter Design 15 Practical Results 16 Conclusion 17 References 18

Table of Figures Figure 1: Input Signal Transformed to Frequency Domain 5 Figure 2: Flow Diagram of Filtering in the Frequency Domain 5 Figure 3: Spatial VS Frequency Domain 5 Figure 4: 2-D Sinusoidal Wave 7 Figure 5: Flow Diagram of Filtering in the Frequency Domain 9 Figure 6: Graphical Representation of an Ideal Low Pass Filter 10 Figure 7: Image that was smoothed 11 Figure 8: Graphical Representation of an Ideal High Pass Filter 11 Figure 9: Edges Clearly Shown before Pass Band Attenuation Edited 12 Figure 10: Final Result of an Image sharpened 12 Figure 11: Graphical Representation of a Gaussian Filter 13 Figure 12: Graphical Representation of a Gaussian Low Pass Filter 14 Figure 13: Graphical Representation of a Gaussian High Pass Filter 15 Figure 14: Original Image and its FFT 16 Figure 15: Smoothed Image and FFT 16 Figure 16: Edged Image and its FFT 17 Figure 17: Sharpened Image and its FFT 17

Acronyms Used 1-D | One dimensional | 2-D | Two dimensional | FT | Fourier transform | FFT | Fast Fourier transform | DFT | Discrete Fourier transform | IDFT | Inverse Discrete Fourier transform | HP | High Pass | LP | Low Pass | P | Power | GSM | Global systems for mobile communication |
PART 1 Filtering in the Frequency Domain
Introduction
This report will cover the topic of filtering in the frequency domain which is a very common image and signal processing technique. There will be an in depth study on filtering in the frequency domain, covering topics like 1-d FFT’s; 2-d FFT’s, image smoothing and image sharpening. In Part 2 a practical application is given on a Gaussian filtering technique that is designed to either smoothen or sharpen the image.
Review of Prior Knowledge
This section is purely to review basic knowledge of the Fourier series. The Fourier series can be used to illustrate any periodic function as the sum of sine and cosine values. Any non-Periodic function can be transformed into the Fourier series with the use of Fourier transforms (FT). There are continuous FT; Discrete FT and Single/multivariate FT.
Complex Numbers
From [5]
C=R+jI
C=Ccosθ+jsinθ
C= R2+ I2
Euler’s representation is:
C=Cejθ, ejθ=cosθ+jsinθ
Fourier series
From [5] ft= n=-∞∞cnej(2πnT)t cn= 1TT/2T/2f(t)×ej(2πnT)tdt
Fourier Transform
This is used to transform a continuous time/spatial domain signal into a frequency domain signal. Equation to convert to frequency domain is [5]:
Ift= Fμ= -∞∞f(t)×e-j2πμtdt
And transforming it back (the inverse Fourier transform)[5]: ft= I-1Fu= -∞∞F(μ)×ej2πμtdt
Figure [ 1 ]: Input Signal Transformed to Frequency Domain
The following image shows an input signal transformed to the frequency domain signal [8]:
Convolution Theorem
This theorem is very important as it will be used throughout the discussing and computing of filtering in the frequency domain. It states that multiplication in one domain is convolution in the other. The following is the equations used [5]. ft*ht= -∞∞f(τ)×ht- τdτ
Thus the Fourier transform is
Ift*ht=-∞∞f(τ)[-∞∞ht- τdt]dτ
And through reversing the order of integration you get
Ift*ht=F(μ)×H(μ)
This covers about most of the basic knowledge and theorems needed for filtering in the frequency domain. DFT, IDFT and 2-d Fourier transforms will be discussed further on.
Overview
One of the common signal (even image) processing techniques is filtering in the frequency domain. This will result in the signal being smoother or sharper; the signal can be de-blurred and even restored to previous state. Note that for images the FFT ‘scans’ over the image while splitting each part up into ‘frequencies’.
Figure [ 3 ]: Spatial VS Frequency Domain
Figure [ 2 ]: Flow Diagram of Filtering in the Frequency Domain
To be able to filter in the frequency domain the image must be transformed from the spatial domain into the frequency domain (via FFT). Then the resulting complex image must be must be multiplied with a chosen filter and the converted back into the spatial domain. The following figure and flow diagram will help clarify things [7].
Thus the image and filter is designed and their frequency domain is calculated through the use of:
Ift= Fμ= -∞∞f(t)×e-j2πμtdt
Keep in mind that the FFT used for image processing is going to be the 2-d FFT. This is because the image is 2 dimensional thus its FFT values will be stored in a 2-d array of values. The 2-d explanation will follow in the next section.
Then the two spatial domains must be convoluted together. But since it is easier to multiply two data sets than to convolute them, we decide to multiply them in frequency domain. This is the reason for the FFT in the previous step.
One can now view the processed image but take note it is still in frequency domain thus the FFT is transformed inversely to obtain final value ft= I-1Fu= -∞∞F(μ)×ej2πμtdt
The final steps to filter in the frequency domain are [6]: 1. Multiply the image/photo inputted by (-1)x+y ,this will help center the transform 2. Compute the 2-d DFT (F(u,v)) of the resulting image obtained prior. 3. Multiply the DFT with the filter, Hu,v=Fu,v×G(u,v) . 4. Calculate the 2-d IDFT transform, and obtain the real part, named Hx,y. 5. Finally multiply the result by (-1)x+y to obtain final image
2-D FFT
In frequency application on does not always get is I dimensional and periodic signals. You can get anything from continuous signals to 2/3 dimensional signals. This section will discuss 2-d FFT but also cover the other principles like DFT and IDFT that helps show how 2-d FFTs work.
DFT
Discrete Fourier transforms are used calculate a signals’ frequency spectrum and with that information you can examine frequency, amplitude and phase. Secondly the DFT can find a systems frequency response from the impulse response. It is helpful especially since it calculates multiple samples, over an interval. The samples don’t even have to be periodic. Note that when talking about FFTs in this report it means fast Fourier transform which means basically that it’s a DFT calculated efficiently.
The following is the equation for DFT [5]:
Fm= n=0M-1fn×e-j2πmnM ,m=0,1,2,3,…,M-1
M is the number of samples taken.
IDFT
Inverse Discrete Fourier transforms are used to reverse the DFT applied to the signal. It basically uses F(u) discrete data points to get f(n). The following is the equation for IDFT [5]: fn= m=0M-1Fm×ej2πmnM ,n=0,1,2,3,…,M-1
For image processing the DFT and IDFT takes on a bit of a different form [5]:
DFT: Fu= x=0M-1fx×e-j2πuxM , IDFT: f(x)=1M u=0M-1F(u)×ej2πuxM ,u,x=0,1,2,3,…,M-1
There are also some DFT properties to take note of [5]:
Periodicity
Fu= Fu+kM ,fx= f(x+kM)
Convolution
fx*hx= m=0M-1fm×hx-m ,m=0,1,2,3,….,M-1

2-D FFT
2-d FFTs are used when there are horizontal and vertical spatial points that need to be transformed into the frequency domain. Thus when the image function, f(x,y), is separated into a combination of harmonic functions. The standard equation for the 2-d Fourier transform and the 2-d inverse is [10]:
Fu,v= -∞∞fx,y×e-j2πxu+yvdxdy fx,y= -∞∞F(u,v)×ej2πxu+yvdudv
Figure [ 4 ]: 2-D Sinusoidal Wave
Below is an image of a 2-d sinusoid that will usually use the above equation if there is a need to examine it [10].

But for a more effective method the 2-d D/FFT is better for image processing. As it allows for you to insert the image size to determine how many samples needs to be taken, because f(x,y) is a digital image with the size M X N. The direct transform is [5]:
Fu,v= x=0M-1y=0N-1fx,y×e-j2π(uxM+vyn) ,x=0,1,2,3,…,M-1 ,y=0,1,2,3,…,N-1
And the inverse transform is [5]: fx,y= 1MN u=0M-1v=0N-1Fu,v×ej2π(uxM+vyn) ,u=0,1,2,3,…,M-1 ,v=0,1,2,3,…,N-1
These equations can be simplified as shown in the Comparison section below, so that the2-d operation consists out of two 1-d operations.
Comparison with 1-D FFT
Remember that:
Fμ= -∞∞f(t)×e-j2πμtdt ft= -∞∞F(μ)×ej2πμtdt
Fu,v= -∞∞fx,y×e-j2πxu+yvdxdy fx,y= -∞∞F(u,v)×ej2πxu+yvdudv
Where 1-d FFTs have only 1 frequency axis for horizontal frequencies, the 2-d FFTs have 2 frequency axes for horizontal and vertical frequency, which makes it perfect for image processing [9]. There is an easy way to use 2-d FFTs with 1-d FFTs as you are able to split 2-d function, equation given below.
Fu,v= y= -∞∞[x= -∞∞f(x,y)×e-j2πuxdx]×e-j2πvydy
Thus where the 1-d usually transforms the rows first, for 2-d application it will transform the rows first then the columns. Thus 1-d FFTs are used for data that is one dimensional like audio or energy signals and 2-d FFTs are used for data that is two dimensional like images
2-D FFT and Image Processing
As we now know the Fourier transform splits the image into ‘frequencies’ and measures the amplitude at each point. To elaborate the Fourier transform measures the spatial ‘frequency’ in the image. Thus an image with lots of jagged at abrupt color transitions contains many high frequencies. The same is true for low frequencies but for long, smooth color transitions.
In image processing 2-d FFT will almost always be used. It will be used in the filtering applications as this is the mathematical concept that allows images to be represented in the frequency domain (remember images are 2 dimensional). Thus before convolution (or multiplication) takes place the 2-d FFT will be calculated of the image and filter. This will allow multiplication to takes place.
Practical uses for 2-d FFT are in image processing. Firstly you can un-blur or un-sharp an image by simply reversing the filtering process (as discussed in the section about smoothing and sharpening). This can be used if an important picture, like a criminal stealing, is blurred and unable to identify. Secondly it can be used in image compression which is helpful in order to view photos on smaller devices or to safe space on the storage device. Next a few practical uses for image smoothing and sharpening is given. This is given because a 2-d Gaussian FFT is used in part 2.
Applications for a image smoothing [5] can be: * Satellite and aero imagery to remove any unwanted scan lines in the obtained image. * In OCR systems to bridge small gaps in texts and paragraphs. * Can be used in the publishing (advertising, magazines etc.) world to remove faults and lines to give a smoother and subtle result.
Applications for a image sharpening [5] can be:
Image Smoothing and Sharpening
Image smoothing and sharpening is used in many aspects in the real world like image processing and statistics. In this report we will look more in depth into image processing. To be more specific we will look at blurring, highlighting details and noise reduction.
The flow diagram is given again below as these are the steps in which the smoothing and shaping will be achieved in. The smoothing and sharpening section will cover more of the different theorems and concepts that will be used if you want the exact steps check the overview section.
Figure [ 5 ]: Flow Diagram of Filtering in the Frequency Domain

Smoothing
The goal of smoothing is to capture important patterns in the data while leaving out unwanted factors like noise. Edges and noise contribute to the high frequency components of an image’s Fourier transform [5]. Thus the individual points (like noise) are reduced while points lower than the neighboring points are increased leading to a smoother image. The smoothed values can be convoluted with the original image in order to obtain the final image [1].
For image smoothing (also known as blurring) an ideal low pass filter is used as it attenuates high frequency values. A graphical representation is given below [3]:
Figure [ 6 ]: Graphical Representation of an Ideal Low Pass Filter
An ideal low pass filter is specified as [3]:
Hu,v= 1 Du,v≤ D00 Du,v> D0
Du,v= (u- P2)2+(v- Q2)2
Now note: * D(u,v) is the distance between the origin and the point (u,v) * D0 is a positive constant, also known as the cut-off frequency * P and Q are the sizes of the zero padded image
One way to indicate cut-off frequency is through circles enclosing a specific amount of power in the image given [3].
PT=u=0P-1v=0Q-1Pu.v=u=0P-1v=0Q-1|Fu,v|2
α=100 × u=0P-1v=0Q-1P(u,v)PT

Thus looking at the above equation, with a radius of D0 , the DFT will enclose as certain percent of power known as α. Thus using the above equations one can filter the image given, in order to smoothen out the ‘high frequency’ values of the image. Also through increasing/decreasing the radius D0 the blurriness can be more/less. Below is given an example of image smoothing [2].
Figure [ 7 ]: Image that was smoothed
There are other algorithms that can be used in place of just the ideal high pass filter namely: * Butterworth low pass filter * Gaussian low pass filter * Laplacian smoothing * Additive smoothing * Kernel smoother
Further discussion on the Gaussian low pass filter algorithm will be discussed in Part 2.
Sharpening
The goal of sharpening is to enhance high frequency aspects while eliminating low frequency components. Edges and noise contribute to the high frequency components of an image’s Fourier transform [5]. Thus the individual points (like noise) are increased while points lower than the neighboring points are decreased leading to a sharper image. The smoothed values can be convoluted with the original image in order to obtain the final image [1].
Figure [ 8 ]: Graphical Representation of an Ideal High Pass Filter
For image sharpening an ideal high pass filter is used as it attenuates low frequency values. A graphical representation is given below [3]:
An ideal high pass filter is specified as [3]:
Hu,v= 0 Du,v≤ D01 Du,v> D0
Du,v= (u- P2)2+(v- Q2)2
Now note: * D(u,v) is the distance between the origin and the point (u,v) * D0 is a positive constant, also known as the cut-off frequency * P and Q are the sizes of the zero padded image
Keep in mind that the ideal high pass filter can be designed through the use of the low pass filter with the identity:
HHPu,v= 1- HLP(u,v)
One way to indicate cut-off frequency is through circles enclosing a specific amount of power in the image given [3].
PT=u=0P-1v=0Q-1Pu.v=u=0P-1v=0Q-1|Fu,v|2
α=100 × u=0P-1v=0Q-1P(u,v)PT
Thus looking at the above equation, with a radius of D0 , the DFT will enclose as certain percent of power known as α. Thus using the above equations one can filter the image given, in order to attenuate out the ‘low frequency’ values of the image, this will cause the higher frequency lines to be more visible and clearer while the smaller frequency values fade away. Also through increasing/decreasing the radius D0 the sharpness can be more/less.
Figure [ 9 ]: Edges Clearly Shown before Pass Band Attenuation Edited
Figure [ 10 ]: Final Result of an Image sharpened
Note that when applying the above algorithm that the lower frequencies will basically become zero. A way to get a final image result you can apply some attenuation to increase the filters pass band a bit. This basically allows that smaller frequencies are still passed through a bit but not enhanced as the higher frequencies are. Below is given an example the image edge detection and the final sharper result after attenuation has been brought into consideration [4].
There are other algorithms that can be used in place of just the ideal high pass filter namely: * Butterworth high pass filter * Gaussian high pass filter * Laplacian sharpening
Further discussion on the Gaussian high pass filter algorithm will be discussed in Part 2.
Conclusion
One can see now that there is no limit in analyzing signals in the frequency domain. Filtering in the frequency domain is a sub part to that, and this allows one endless control over signal, images and even motion pictures. With knowledge about 2-d FFTs one gains a lot of control over any form of signals (1 – 3 dimensional).
PART 2 Application of Filtering in the Frequency Domain
Introduction
The purpose of this part was to apply filtering in the frequency domain onto an image. A Gaussian low- and high pass filter will be used, in order to smoothen and sharpen the image given as input. The filter is designed out of first principles using Matlab to help simulate the results.
Gaussian Filter Theoretical Analysis
Figure [ 11 ]: Graphical Representation of a Gaussian Filter
In previous sections the ideal low- and high pass filters were discussed, and their uses in image processing. Gaussian filters are filters whose impulse response is a Gaussian function. They are more advantages than the ideal filters because of almost no overshoot and minimal rise and fall time. They are applied. They also have a minimal group delay. Below is an illustration of a Gaussian filter [11]:
Gaussian Low Pass Filter
The Low pass filters will attenuate any high frequencies, like noise, and smoothen out the image. The equations are [3]:
Hu,v= e-D2(u,v)2×D02
Du,v= (u- P2)2+(v- Q2)2
Now note: * D(u,v) is the distance between the origin and the point (u,v) * D0 is a positive constant, also known as the cut-off frequency * P and Q are the sizes of the zero padded image
The filter that is designed as a result of these equations is [3]:
Figure [ 12 ]: Graphical Representation of a Gaussian Low Pass Filter

Thus with a lower cutoff frequency the image will be smoother (more blurry).
Gaussian High Pass Filter
High pass filters will attenuate any low frequencies and sharpen the image. The equations are [3]:
Hu,v=1- e-D2(u,v)2×D02
Du,v= (u- P2)2+(v- Q2)2
Now note: * D(u,v) is the distance between the origin and the point (u,v) * D0 is a positive constant, also known as the cut-off frequency * P and Q are the sizes of the zero padded image

The filter that is designed as a result of these equations is [3]:
Figure [ 13 ]: Graphical Representation of a Gaussian High Pass Filter

Thus with a lower cutoff frequency the image will be sharper.
Gaussian Filter Design
For designing these filters the following steps were taken in order to achieve the desired results. Firstly the image was grayed then the 2-d FFT was calculated of the grayed original image. The FFT is taken because it is easier to analyze the picture in that domain and it eliminates convolution in the spatial domain so that there can now be multiplied in the frequency domain (later on).
Next the Low pass filter is designed. This step is done for both the smoothing and shaping part of the program. It will use the size of the MxN image to determine the new radius size (or D(u,v) in the equations. It also needs a cutoff frequency for the filter which will impact the blurriness or sharpness of the image.
Now for the LP filter the following is done. The LP filter transfer function H(u,v) is now multiplied with the images’ FFT imageFFT(u,v). This is done over the entire range of image size (thus for loops). This new LP FFT will now be reconverted with a 2-d IFFT, to obtain the newly sharpened image in spatial domain. The original and smoothed image is outputted along with the original and filtered images’ FFT.
For the HP filter the following is done. The Low pass filter transfer function H(u,v) is changed with the filter identity to get the HP filters transfer function:
HHPu,v= 1- HLP(u,v)
Note that the HP filter transfer function Hu,v is correct but if you multiply it with the images’ FFT imageFFT(u,v) you will get a result where the edges are clearly visible but the lower frequency values are almost completely attenuated. Thus the resulting image isn’t a clear sharpen image of the original. To account for this the pass band attenuation is increased to allow some lower frequencies to pass. The equation for this is:
Hnewu,v= a+b×Hold(u,v)
After this the old HP function and the new HP function is multiplied with the images’ FFT imageFFT(u,v). This is done over the entire range of image size (thus for loops). This new/old HP FFT will now be reconverted with a 2-d IFFT, to obtain the newly sharpened image in spatial domain. The original, edged and sharpened image is outputted along with the original and edged images’ FFT.
Practical Results
The following results were obtained from the practical simulation, in the LP result the cutoff frequency was 0.1 and in the HP result the cutoff frequency was 0.025.
Firstly the original image that was used and its frequency response:
Figure [ 14 ]: Original Image and its FFT

Figure [ 15 ]: Smoothed Image and FFT
Secondly the smoothed image and its frequency response:
Figure [ 16 ]: Edged Image and its FFT
Lastly the edged and sharpened image and their frequency responses:
Figure [ 17 ]: Sharpened Image and its FFT

Conclusion
As one can clearly see there was definite smoothing and sharpening that took place. The original image was sent through the filter correctly and it gave the desired results. There are a lot of real world applications for the Gaussian filters [11]. In GSM devices for wireless communication. In Gaussian frequency-shift keying. And of course in image processing, more accurately the Canny Edge Detector.

References
[1]http://en.wikipedia.org/wiki/Smoothing
[2]http://commons.wikimedia.org/wiki/File:Wiener_filter_-_my_dog.JPG
[3]http://ee.lamar.edu/gleb/dip/04-2%20-%20Using%20frequency%20filters.pdf
[4] http://stackoverflow.com/questions/6094957/high-pass-filter-for-image-processing-in-python-by-using-scipy-numpy
[5] http://www-old.me.gatech.edu/me6406/Frequency%20domain%20filtering%20%28SH%20Foong%29.pdf
[6] http://www.learningace.com/doc/347059/6d3ac23cdaf98dd756762d6e0bf99373/lec012_frequency
[7] http://www.scratchapixel.com/lessons/mathematics-physics/discrete-cosine-transform-dct/one-dimensional-dct/
[8] http://www.twi-global.com/technical-knowledge/published-papers/analysis-of-cross-correlation-and-wavelet-de-noising-for-the-reduction-of-the-effects-of-dispersion-in-long-range-ultrasonic-tes/
[9]http://www.mee.tcd.ie/~sigmedia/pmwiki/uploads/Teaching.4S1b/handout4_4s1.pdf
[10] http://cmp.felk.cvut.cz/~hlavac/TeachPresEn/11ImageProc/12FourierTxEn.pdf
[11] http://en.wikipedia.org/wiki/Gaussian_filter