welcome to the sixth lecture of ENG 860 special topics in digital image processing so today I want to continue discussion on discrete Fourier transform so in this lecture we will go over some material from last lecture and then we will continue with discrete Fourier transform of functions with one variable then I talked a little bit on the extensions of functions and concepts from functions of one variable to two variables then I talked a little bit about the properties of 2d discrete Fourier transform and its inverse and then later on I will talk a little bit about basics of filtering in the frequency domain so let's just begin by an overview of what was discussed last time So you remember the definition for continuous and discrete impulse function. So for the continuous impulse function we had it defined as a very narrow spike or to be more precise a zero width spike at location t equals zero. So based on this, this is the definition that we have for the continuous impulse function. delta t equals infinity for t being zero and it's zero otherwise so this definition by itself is very weak because we in reality we cannot have a spike with zero duration and with infinite magnitude so to make it more mathematically plausible we add this integral constraint which basically states that the area under the curve of a continuous impulse function is 1. So the integral from negative infinity to positive infinity of delta t over all the values of t equals 1. Based on this integral constraint we can have the very important shifting property of the impulse function which is mainly used if you want to take individual samples of any other function. So let's just say we want to take a sample of function f of t at location t equals zero and we assume that function f of t is continuous at location t equals zero.
So in that case the integral from infinity negative infinity to positive infinity of this multiplication would be equal to f at location zero. What if we have a shifted version of the delta function? So the same shifting property applies except here. Now we get the value of function f at location t0, basically the location of the impulse. A similar set of definitions can be defined for discrete impulse function.
For discrete impulse function, we define it as delta of x. which is 1 for x being 0 and which is 0 otherwise and instead of having an integral constraint now we have a summation constraint which says that the summation of all the values of a delta function equals 1 and this is easily understandable based on this definition that we have for the discrete impulse function but the discrete impulse function has the shifting property as well so instead of using an infinite integral now we are using an infinite summation for all the values of X and the summation of all the values of the summation over all the values of X of this multiplication function will be the value of discrete function F at location X equals 0 and if we have a shifted version of the Delta function that can give us the value of function f at location x0 basically the location of the shifted impulse the next thing that we discussed before was the concept of impulse train so in real applications having individual impulses is usually not enough so the way that we do sampling is by providing an impulse train with known periods so let's say we want to define an impulse train with period Delta T so the way to do it is we represent it as an infinite summation delta t minus n delta t so if n is 0 that gives us the impulse train at the origin if n is 1 that will give us the impulse train at location delta t and if n is negative 1 that will give the impulse at location negative delta t and so on and so forth a similar definition can be done for the discrete impulse train as well, but the difference here is that we are using delta X as the as the period for the impulse train and this is to distinguish between the Variable that we use for continuous function and the variable that we use for discrete functions Also, if you remember we said that if a function is a periodic we can use Fourier series to represent that function but for non-periodic functions We can use Fourier transform. So the way it works is that We calculate this integral for that specific function that will give us the Fourier transform of the non-periodic function So to get the Fourier transform of a non-periodic function we calculate the integral indefinite integral from negative infinity to positive infinity over all values of the variable of the multiplication of the function f of t and this complex exponential function e to the negative j 2 pi u t as you can see here we calculate the integral over all values of t which means that the result of this integral will be only a function of u which is the frequency variable. We can have the definition for the inverse of the Fourier transform in this form and similar to the one above this integral is only a variable of t because this integral is calculated over all the possible values of u which is the frequency variable.
For more detail you can refer to the previous lecture. The function and its Fourier transform can be shown as a pair which signifies that we can go from a function in the signal domain to a function in the Fourier domain and vice versa. So let's take a look at some examples.
So the first example is for the Fourier transform of a box function. We define a box function as a function with a constant value. in a specific range. Here the range is negative w over 2 to positive w over 2 and it's zero otherwise.
So a graphical representation of this box function can be seen here. So if we apply the definition of the Fourier transform to this function we get this representation for the Fourier transform of the box function. So as you can see it is a w sine of pi u w over pi u w. One thing that I should note is that for these lectures I use u and mu to represent a frequency variable.
If you refer to the book that is basically the practice that the book also does. So if we want to show a graphical representation of the Fourier transform this is the graphical representation one thing that you might notice is that for the value of the Fourier transform at at the origin we have both a and w so that means that if we have a box function with higher value for the amplitude or the magnitude at the origin we have Fourier transform that has a higher value at the origin but not only that this value at the origin in the frequency or Fourier transform is also dependent on the width of the impulse as well so if we have an impulse with higher width that means that we have a Fourier transform that has a higher value at the origin another thing is that you see these points of zero crossing as a result of the sine function that we have on the numerator the Fourier transform and the zero crossing happen at location 1 over w apart so it means that if we have a wider box function these zero crossing points are gonna happen much closer to each other also it is beneficial sometimes to use the Fourier spectrum which basically is calculating the amplitude of this function and this way we only have positive values so as you can see it is a different representation of the same Fourier transform but this way we only have positive values and the phase information of the Fourier transform is eliminated so for the next example we want to calculate the Fourier transform of the unit impulse basically the continuous unit impulse located at the origin so again we apply the definition of the Fourier transform and when we look at this we see that this is exactly the same format as the integral that we use to describe the shifting property of the delta function So the result of this integral is going to be the value of this function at location t equals 0. So if we replace t with 0 in the equation, we get that the Fourier transform of a unit impulse located at the origin is 1. And it's a constant function. What about the Fourier transform of an impulse which is located at location t equals t0?
What if the impulse is shifted? So we apply the definition again and then we realize that this is again Can be solved by the shifting property of the Delta function The only difference here is that now we have to evaluate this function at location T0 And if we do that we see that the Fourier transform of the shifted Delta function is e to the negative J 2 pi u T0 One thing that you might notice is that if we calculate the amplitude of these two, the amplitude is going to be 1 in both cases. However, what we have here for the shifted version of the impulse function is that we have a different phase angle than before.
So in the case of regular impulse function at the origin, the phase angle was 0. but for the shifted version of the impulse function now we have a non-zero phase angle so now let's combine all the things that we learned to find the Fourier transform of an impulse train so this is the way that we represent the impulse train again as a summation of individual impulses happen delta t apart so the first thing that we can do is we can represent this function in its Fourier series representation and the reason for that is that this is a periodic function so if we do that we get to this equation which is the Fourier series representation of the impulse train of course more detail was given in the previous lecture Because of the symmetry property of the Fourier transform, which says that if we have a lowercase function f of t, which gives the uppercase function f of u as its Fourier transform, then if we have a function with the form of the Fourier transform of the original function, but with variable t, and then we calculate the Fourier transform, now we have a function. In the form of the original function, but now the variable is negative U so based on this if you remember when we had a shifted version of the impulse function it Fourier transform was a Complex complex exponential function now it means that if we have a function which is a complex exponential function Fourier transform is going to be a Delta function So based on this we can drive the equation for any of these individual complex exponential functions that appear in the Fourier series. So if we combine these concepts together we realize that the Fourier transform of the impulse train is going to be an impulse train itself.
But now the difference is that not only that impulse train is a function of the impulse train itself but it is also a function of the impulse train itself. weighted by 1 over Delta T so that means that if we have an impulse train with higher with larger period that means that in the frequency domain we get an impulse trend with a smaller magnitude but also one thing that you notice is that the the period is now different so the period in the frequency domain is inversely proportional with the period in the signal domain so if you have impulses in the signal domain that are far apart they are going to be closer in the frequency domain and vice versa so now let's see what can we say about the convolution so if you remember from before convolution of two functions involved flipping one function around its origin and then sliding it past the other one and at each displacement location we either perform the integral for the continuous case or we perform the sum of product for the discrete case so the general equation for the convolution can be represented using this equation last lecture we proved that convolution in the signal domain is equivalent to multiplication in the frequency domain because of the properties of the Fourier transform if you have multiplication in the signal domain that is equivalent to having convolution in the frequency domain so this is of course for the continuous case a similar Analogy can be made for the discrete case as well, which you will see later on in this lecture. So now that we have all of this, let's just see what is the frequency or Fourier representation of sampling a function in the signal domain.
So let's just assume we have a function which is continuous and we want to and take some samples of this function because in order to work and process this function in a computer we need to sample and quantize the continuous function so here we only focus on the sampling part so to do the sampling we can multiply the original function original continuous function with an impulse train and if we do that This is a representation that we get at locations of these impulse trains. The amplitude of each one of these individual impulses is modified and these amplitudes are basically the amplitude of the continuous function at that specific location. Mathematically, it can be represented using this equation basically. simple multiplication of the original continuous function and the impulse train if we want to get the value of this sample function at any location what we can do is basically calculate this integral multiplying this function with each one of these individual impulses so now that we have this Let's just see what is the representation of the sample signal in the frequency domain. So to do this we use the concepts from the convolution property of the frequency transform and also the fact that the Fourier transform of an impulse train is an impulse train itself.
So based on the convolution property of the Fourier transform. The Fourier transform of the sample signal is the Fourier transform of the multiplication of the original function and the impulse train. which is equivalent to finding the convolution between the Fourier transform of the continuous signal and the Fourier transform of the impulse train. If you remember from before the Fourier transform of the impulse train is an impulse train itself.
So if we combine these two equations we can see that the Fourier transform of the sampled signal equals to 1 over Delta T a summation over all the values of n f of u minus n Delta T so this equation means that the Fourier transform of the sample function is an infinite periodic sequence of copies of f of u f of u being the Fourier transform of the original continuous function with the period 1 over Delta T so now let's see what does it look like in the frequency domain so let's just assume we have a function in the signal domain for which we have a fourier transform in this form so this fourier transform is called to be band limited because it is zero outside a limited range of frequencies so as we said the fourier transform of the sample signal is basically infinite set of copies of the original Fourier transform that are 1 over Delta T a part basically the period in the frequency domain for this periodic function is all 1 over Delta T so then we can have three cases we can have the cases of over over sample function in which Sampling rate or 1 over delta t is sufficiently large to be able to separate the copies of the sampled function in the frequency domain. So this is the graphical representation for the oversampled case. We can have the case of critically sampled data in which the sampling rate or 1 over delta t is just large enough to separate the sample functions. Fourier transform in the frequency domain as you can see in the case of over sampled function there was a gap between each one of these individual copies for the critically sampled case there is no gap anymore between these copies but at the same time we don't have any overlap either so we are still able to separate one individual Fourier transform among this sequence and then finally we have the case of under sampled data in which the sampling rate or 1 over delta t is not large enough to separate the sample function Fourier transform in the frequency domain and that is the case that we have here as you can see the sampling rate is so low to the point that these individual copies actually overlap and basically summed up together there are these regions that are the result of adding different sections of these for example these two copies they added together to create this this region and because of this it is not possible to extract a single copy of the of the function without any overlap so the sampling theorem states that if you want to extract a single copy of a band limited signal from its samples or in another word if you want to reconstruct a continuous function from its samples we need to have the sampling rate that satisfies this equation so the sampling rate or 1 over delta t need to be at least two times larger than the maximum frequency of the signal so for example here this is going to be positive u max this is going to be negative u max so if you want to have a perfect reconstruction of the continuous signals from its samples the sampling rate should be at least twice as large the maximum frequency and this is what you can see here too so this range is u max this rate is also u max and since this is the critically sampled case that means that it the sampling rate is just large enough to be able to separate the two So, 1 over delta t at this point is going to be equal to 2 u max. So, if 1 over delta t is equal or larger than 2 u max, then the sampling theorem criterion is satisfied.
So, we know, we saw that the Fourier transform of a sample band limited function. which extends from negative infinity to positive infinity in the signal domain is a continuous periodic function that also extends from negative infinity to positive infinity in the frequency domain so in practice we work with finite number of samples so the question becomes how can we drive the discrete Fourier transform of such finite sample sets previously we saw that we can drive the Fourier transform of the sample data with respect to the Fourier transform of the original data. This is the equation that you saw in a previous slide. Basically, the Fourier transform of the sample data is an infinite sum of shifted versions of the Fourier transform of the original signal.
This equation by itself does not provide an expression based on the samples of the data. So, to get that expression what we can do is that we can apply the Fourier transform definition directly to the sample data so let's just apply the Fourier transform definition directly onto the samples so this is f tilde of t which is the sampled function and we know that this one is created by this infinite summation over all values of n of the multiplication the Fourier transform and these individual impulses one thing that we know is that this summation is done over all values of n and this infinite integral is done over all values of t so since the variables are different we can change the order of the summation and the integral and if we do that this is what we get both infinite summation over all values of n of an infinite integral over all values of t for FT Delta and T n minus Delta T e to the negative J 2 pi u T so again this integral can be calculated by taking advantage of the shifting property of the Delta function So that means that we have to evaluate the multiplication of f of t and e to the negative j 2 pi u t at locations of these impulses. So if we do that, this is the equation that we end up with. As you can see, any t value that we had here is going to be replaced with n delta t. Because these impulses are happening at locations n delta t.
One thing that you might notice here is that here we use f subscript n and if we go back to a previous slide this is basically the definition for f subscript k which is the evaluation of function f at location k delta t. So this is a shorthand version of representing the function so if you want to make it complete you can just say f of n delta t and as you saw the last step follows from the sampling equation using an impulse train and the shifting property of the impulse function so now even though we have calculated the equation based on the values of the actual samples of the function it's still that definition is continuous because we didn't put any constraint on the values of u so to build the discrete Fourier transform we need to do sampling over one period of the Fourier transform so to do that let's have m equally spaced samples of the Fourier transform over one period and if you remember from one of the previous figures one period in the Fourier transform of the sampled signal is from 0 to 1 over delta t So if we do that, these are the samples that we get for the sampling of the Fourier transform in one period. So u equals lowercase m over uppercase M multiplied by delta t.
And the lowercase m can change from 0 to m minus 1. So for example, if m is 0, that means that u... at that location will be at zero or at the origin if m is one that means that u will be one over m delta t which is uh one over m delta t apart from uh the origin so now if we replace these values for u these discrete values for u in the equation that we had we get this equation for the discrete Fourier transform and This means that the inverse discrete Fourier transform is Having this form of course a more detailed explanation of the concept It's not going to be covered in this course the reader or the listener can be refer to courses that are specifically designed for digital signal processing to see how these final equations are tracked but again the derivation is pretty straightforward we just need to have some restriction on the value of U because by itself U is continuous so now we replace it with some sum of its samples in the frequency domain so if we combine all of these equations and to be more consistent if we use x and y for the variables in the signal domain basically discrete variables and u and v for the variables in the frequency domain i just mentioned both x and y and u and v for the time that we want to use these definitions on 2D images. So for 1D signals we only use X and U. Then we can rewrite the forward discrete Fourier transform and inverse discrete Fourier transform equation like this.
So we have F of U, a summation over X going from 0 to M minus 1 of F of X e to the negative j 2 pi ux over M. and for this equation to be calculated we have to calculate it for all the values of u which is 0 1 all the way to m minus 1. one thing that you might notice here is that both x and u can change from 0 to m minus 1 and the reason for that is we use exactly the same number of samples in both signal and frequency domain of course you can change this definition for having different number of samples in the signal and frequency domain but at the end of the day it is not going to be important as long as you account for the overlap that you might have so because of this for now we consider only the cases for which the number of samples in the signal domain and in the frequency domain are exactly the same and we can have the inverse discrete Fourier transform equation in this form f of x is going to be equal to 1 over m the summation over all values of u over one period from u equals 0 to m minus 1 f of u e to the j 2 pi u x over m one thing that you might notice here is that we have this extra weight for the inverse Fourier transform that is something that we didn't have for the inverse Fourier transform of a continuous function and the reason for that is here we are using discrete samples in the signal domain and also discrete samples in the frequency domain so if you do the calculation to derive at this equation you will see that this weight would appear in the definition of inverse discrete Fourier transform So this definition that we have for the discrete Fourier transform and the inverse discrete Fourier transform have some very nice properties. The first thing that will be very useful is that both the forward and inverse discrete Fourier transform are infinitely periodic with period m and integer k. So one thing that you might notice is that for the original signal we didn't say that it samples or need to be like periodic. So let's say we have a function that has a short duration in the signal domain and we take some samples.
We said that if we calculate its frequency response the frequency response will be periodic but we didn't say anything about. the samples in the signal domain to be periodic. But in order to be able to use the discrete Fourier transform based on the definition that we have, we are practically making the samples in the signal domain also periodic too. So this way we can have a two-way correspondence between Fourier transform and the sampled signal itself. so the way to prove these two properties is just by replacing variable u with u plus k m m is the the period of the repetition and k is an integer so if you replace it here what you end up with is a kernel or like a complex exponential function which is basically rotating around the unit circle and no matter what is the value of integer k it basically rotates and comes back at its original location and that's why we say that both the forward discrete Fourier transform and inverse discrete Fourier transform equation are periodic another thing that we find is very useful is the concept of convolution so we thought that the convolution in the signal domain is equivalent to multiplication in the frequency domain but does this condition also satisfy for the discrete Fourier transform as well and the answer to that is yes of course Since now the discrete Fourier transform and its inverse are periodic.
Any time that we want to calculate convolution we are practically doing circular convolution which has its own restriction as well. So I will show you an example later on. So based on this the discrete Fourier transform of the convolution of F and H equals the discrete Fourier transform of F multiplied by discrete Fourier transform of H on the other hand the discrete Fourier transform of the multiplication of F and H equals 1 over M discrete Fourier transform of F convolved with discrete Fourier transform of H and this 1 over M is basically the constant that appears as a definition of the discrete Fourier transform. So now let's take a look at one example to see how these definitions can be applied.
So let's just assume we have this continuous function for which we are taking four discrete samples. So these samples are at location t0, t0 plus delta t, all the way to t0 plus 3 delta t. So since we are sampling these, We put them at discrete locations. So these discrete locations are now 0, 1, 2 and 3. So you are given these four samples and you are asked to calculate the discrete Fourier transform of this sample function. So one thing that you notice is that we have four samples and as we said before we use exactly the same amount of samples for the discrete Fourier transform domain as well.
So, this is the definition that we have for the discrete Fourier transform. So, in this definition, we have f of u equals the summation from x equals 0 to m minus 1 in this case is going to be 3 f of x e to the negative j 2 pi u x over m which here is going to be 4. so now to calculate each individual component of this frequency response we have to replace all of these values so we have to replace u and then for each value of u we have to calculate this summation so let's just do it for f of 0 so if we replace u with 0 and we calculate this summation we have a summation for x changing from 0 to 3 of f of x e to the negative j 2 pi multiplied by 0 x over 4 so this function becomes e to the 0 which is 1 that means that f of 0 is going to be basically the zeroest component of the frequency transform is going to be the summation of all the values of the original function so f of 0 plus f of 1 plus f of 2 plus f of 3 which is going to be 11. so this is something that is interesting and the reason for that is when you replace U to be 0 that means that you are looking to compute the DC component of the signal so basically the part of the signal that doesn't changes over time in effect this is proportional to the average of the original signal of course it is m multiplied by the average. So now let's see what happens if we want to find the one or the first component of the frequency response.
So in this case we replace u with 1 in this original equation and then we calculate this summation over all the values of x. So If we do that, we are basically summing up all these values, which if we use the Euler equation that I discussed in the first lecture of this chapter, we get the value to be negative 3 plus 2j. This is something to be expected.
It is nothing out of the ordinary for us to have a complex value for the frequency domain. In fact, that is something to be expected. because Fourier transform or discrete Fourier transform are complex in general if we do the same for F2 and F3 we end up with value of negative 1 negative 3 negative negative sorry for F2 we get negative 1 and for 3 we get negative 3 negative 2j so what about the inverse discrete Fourier transform because we are given these samples and we are able to calculate the forward discrete Fourier transform. But let's just check and see if the inverse discrete Fourier transform gives us exactly the original signal.
So this is what we do in the definition of the inverse discrete Fourier transform. What we do is that we replace the value of x and then we calculate this summation for all the values of x and then we multiply this by the value of x. u so if we do that we get the final value for the inverse discrete Fourier transform for for X equals 0 to be 1 which is exactly what we had for the original signal so calculating it for the values of F for X being 1 X being 2 and X being true 3 is left for your practice so one thing that is very interesting that is happening here and you should pay attention to is that there is no direct one-to-one correspondence between any frequency component and any signal component so as you can see here this signal component this frequency component is derived as a result of the summation of all the values of the origin of signal the same applies to for example f of 2 which is derived as a weighted summation of all the values in the original signal. The same can be said for the values of the inverse discrete Fourier transform. So because of that you cannot have a direct one-to-one correspondence between any frequency component and any signal component.
So this is something that you will see later on when we work with images too that frequency transform does not necessarily represent the pixel values or intensity values or signal values but it's representative of the changes in those values so this is something that you need to keep in mind Up to this point all we talked about was functions either continuous or discrete of only one variable. So now it's the time to see what happens for the cases of 2D functions. So from this point forward I want to tell you about how we can extend all those one dimensional functions and apply it into two dimensions.
so the first thing that i want to talk about is for the one-dimensional continuous impulse function so you all remember these definitions that we had for the one-dimensional continuous impulse function the extension from one dimensional to two dimensional is pretty straightforward so anywhere you see a function of one variable you replace it with function of two variable anywhere you see a summation over one variable you replace it with a summation with a double summation over two variable and anywhere you see a single integral over one variable you replace it with a double integral over two variable so based on this the 2d version of the impulse function can be defined like this we have delta of t and z equals zero only when t equals z equals zero so this is the impulse function in two dimensions and that appears at the origin and it is zero otherwise so the integral constraint is still satisfied for the 2d impulse function so the double integral from negative infinity to positive infinity of the delta function over both variable t and variable z equals 1 and based on that we can have the shifting property of the Delta function. So this is the more general case if we have a shifted Delta function at location t0 and v0 which is represented by this function and We multiply it by function f of t and v which is assumed to be continuous at location t0 and v0 and we calculate this double integral over all values of t and v we basically get the evaluation of function f at location t0 and z0 so let's just see how it looks for the case of 2d discrete impulse function so again we have all these definitions for the one-dimensional discrete impulse function For two dimensions, anywhere we had the function of one variable, we replace it with the function of two variables. So, delta x becomes delta x and y. And this function is only one when x and y are zero and it's zero otherwise. As for the summation constraint, if we calculate the double summation over all the values of x and y of the delta function, that is going to be equal to one.
As for the shifting properties, if we have a shifted version of the delta function at location x0 and y0, and we multiply it with the function f of x, y, which is, you can say, also discrete, the result of this double summation over all values of x and y equals f of x0 and y0. So here you can see a representation of them. 2d discrete impulse function which is a shifted version so it it appears at location x 0 and y 0 so one thing that you notice is that x and y together they are representing the plane not necessarily a coordinate axis but they are representing a plane of all the possible values of X and Y so now let's see how how does 2d Fourier transform look like so for the continuous one-dimensional Fourier transform we had these equations and we had the Fourier transform pair the extension from 1d to 2d is very straightforward anywhere we had the function of one variable now we have a function of two variables anywhere we had a function of sorry is a single integral over one variable now we have a double integral over two variable so for them Continuous variables we use here t and v and for the continuous frequency variables we use u and v. So f of u and v equals double infinite integral of f of t and v e to the negative j 2 pi u t plus v z.
And for the inverse we have f of t and v double integral f of u and v e to the j 2 pi UT plus VZ over all the values of B U and B and as for the Fourier transform pair we have this pair F of T and V and F of U and B so let's just take a look at one example before we had the example of a one-dimensional box function so now here we have a two-dimensional box function or like a rectangle function so this function now extend along both dimension t and dimension z but the extent is different along each dimension so for dimension t it's going to be from negative t over 2 to positive t over 2 and along z it's going to be negative z over 2 over positive z over 2. So if we apply this definition for the Fourier transform into this function, we see that outside this specified region, the value of this multiplication is going to be 0 because the box function is 0. But inside that, its value is 1. And now we have to calculate this double integral over this range for this function a e to the negative j 2 pi multiplied by by ut plus vz. So one thing that you might notice is that this complex exponential function can be separated into two functions one being e to the negative j 2 pi ut and the other one will be e to the negative j 2 pi vz. So if we do that that means that we can calculate these integrals separately and if we do that This is the result that we get for the Fourier transform of the 2D box function or the rectangle function. So if you remember from the one-dimensional box function, the equation was AW sine of pi UW over pi UW.
So now we have the equation to be AT. V sine of pi u t over pi u t multiplied by sine of pi V Z over pi V Z so in effect you're calculating the multiplication of two Sink functions one along the u-axis and another one along the b-axis So this is the Fourier spectrum of the Fourier transform of this function So what about the 2D sampling and 2D sampling theorem? So similar to the 1D case, sampling in the 2D can be done by an impulse train. So here we define the impulse train as a double summation of all these individual impulses. So here you see that we have variable m and variable n which are integer values.
and we have delta t and delta v as the periods along the t and v direction so if we want to calculate the sample of any two-dimensional function or two-dimensional surface we simply multiply the function by the two-dimensional impulse strength and this is the graphical representation of the two-dimensional impulse strength so now let's just see what happens to the sampling theorem so if we have function f of t and z And the function needs to be band limited. We say it is band limited if the 2D Fourier transform is zero outside a rectangle in the frequency domain. And this rectangle is specified by two limits, one along the U direction and one along the V direction. So mathematically...
f of u and v is zero for any value of u and v which is outside this range so graphically this is basically a graphical representation of a 2d band limited function so now the 2d sampling theorem states that a continuous band limited function f of t and v can be recovered with no error from a set of its samples 2d samples if the sampling rates are satisfying these two conditions so the sampling rate along the t direction needs to be at least two times larger than the maximum frequency along the u direction and the sampling rate along the z direction is going to be at least two times larger than the maximum frequency along the direction so what happens for the 2d sampling is that in the one-dimensional case we had infinitely many copies of the original Fourier transform along only one direction now since we are working with 2d we basically have infinitely many copies of the samples in the whole frequency plane which is created by u and v. So to get the separation we need to have a sampling rate that satisfies these two conditions. So we have a sampling rate along t and we have a sampling rate along z. Otherwise we may have overlap.
So one thing that you should notice is that this overlap does not necessarily happen along both directions. So it is possible that you only have overlap along direction U or only along direction B. And that is because you might have a situation in which one of these conditions is satisfied while the other one is not.
But in reality either of these cases happen if you have overlap that is equivalent to having aliasing in the sample so now let's see what aliasing looks in two dimensions so similar to one dimensional case aliasing is created as a result of under sampling so generally speaking there are two types of aliasing in images so we can have the case of a spatial aliasing which is related to sampling in the spatial domain and it's more pronounced in images with repetitive patterns and we can have the case of temporal aliasing which is related to sampling in the time domain for example when you're recording a video so a wagon wheel effect is a common example of temporal aliasing if anybody doesn't know what is the wagon wheel effect that is basically when you say you're taking a video of a bicycle and then when you revisit the footage you notice that even though the bicycle is going in one specific direction the spokes of its wheel or tire is rotate or rotating at a different direction as for the special aliasing we can have jaggedness in the line pictures we can have spurious highlights and we can have appearance of frequency patterns that are not necessarily present in the original image as a result of spatial aliasing so here you can see an example of spatial aliasing so here we have three types of pattern we have a low frequency pattern with thicker bars and wider distance between the bars we have a mid frequency pattern with a little bit narrower boards and a little bit smaller smaller distances between the boards and we have the case of high frequency pattern is very narrow bars and with very small distances between the individual bars so this full grid is basically representative of the sampling grid so when you sample this low frequency pattern using this grid you barely notice any effect of aliasing because visually you see that the the sampling rate is much higher than the frequency contained in this pattern but when you move to mid frequency pattern you start to see some rawness Result as as the result of aliasing so there are some faint patterns that appear that are not in the original image. When you try to image this high frequency pattern using that sampling grid, now you clearly see these additional pattern that appear as a result of aliasing. And the reason for that is this sampling grid does not have enough sampling rate.
So its sampling rate is not high enough. So, we have aliasing as a result of under sampling. So now let's take a look at one example. So let's just assume we have a camera with a resolution of 96 by 96 pixels. So the spatial sampling rate is fixed.
And we want to image different patterns by this camera. So we have four patterns. All of these patterns are band limited but the frequency spans are different. So these patterns are all checkerboard patterns and for each one of them the block size is either 16, 6, 0.92 and 0.48 respectively. So the first two patterns that you see here are as a result of using this camera to image the first two patterns with block sizes of 16 and 6. and as you can see you don't notice any sources of aliasing but for these two patterns you see the effect of aliasing for this one there are some additional patterns that appear that are not present in the original checkerboard pattern that you want to image and for this one the aliasing is so heavy that you are actually seeing a pattern with block sizes that are even larger than that the pattern with block sizes of size 6. Let's see another example in which aliasing occurs in an image that is resampled.
So here on the left we have the original image which is of the size 772 and 548 pixel and visually inspecting this image you don't notice any aliasing. But let's just say we resize the image to 33% of its original size by pixel deletion. So we are practically removing two pixels out of every three pixels that we have in this image. Because of the resampling and as a result of aliasing, now you see there are these additional patterns that appear in the scarf and pants of the model.
as we said before for the case of 1d signal we said that if we apply smoothing or low-pass filtering we can heavily reduce the effect of aliasing so this is as a result of smoothing the original image first and then resampling it with the same rate as the image in the middle and as you can see there is not that many that much aliasing in the image of course you see that the final result is a little bit more blurred and the reason for a smoothing before resampling is that by a smoothing we are actually limiting the high frequency components in the image so in such a way when we do resampling we are practically reducing the amount of overlap between all these individual copies of the original signal that appear as a result of the resampling in the frequency domain so now let's see how we can extend the definition for one dimensional discrete Fourier transform to a two dimensional discrete Fourier transform again the extension is pretty straightforward anywhere we have a function of one variable we replace it with a function of two variables anywhere we had a single summation we replace it with a double summation so these three are the discrete Fourier transform the inverse discrete Fourier transform and the discrete Fourier transform pair for a discrete function of one variable and these three are the discrete Fourier transform the inverse discrete Fourier transform and the discrete Fourier transform pair for functions of two variables of course you can realize that when you have regular images of even small size it is not practical to calculate these functions by hand and there are computer procedures that give you the capability to calculate the discrete Fourier transform and inverse discrete Fourier transform with high accuracy and with high speed So now let's just take a look at some of the properties of the 2D discrete Fourier transform. The first thing that we should notice is the sampling intervals in the spatial and frequency domain. And as we saw before, the sampling interval in the spatial and frequency domain are inversely proportional.
So if we have high sampling interval in the frequency domain, that is equivalent to having a low...... low sampling interval in the signal domain or vice versa. As for the translation, we saw before that if we apply a complex exponential function to the original image, we are practically shifting the Fourier transform and if we shift the original image we are practically multiplying the Fourier transform with a complex exponential function. So this is a property that is very useful and you will see how we can use it to basically center the discrete Fourier transform. And one thing that is important is the concept of rotation.
So what happens if you rotate the original image? What happens to its discrete Fourier transform? To answer this question, we can use a polar coordinate using this definition. x equals r cosine of theta, y equals r sine of theta, u equals omega cosine of phi, and v equals omega sine of phi.
So if we create our image and represent it in the polar coordinate as f of r theta plus theta zero, that means that if we rotate our image, the signal domain by theta zero that is equivalent to rotating the its frequency transform but by the exact same amount you will see an example of how this is useful later on as for the periodic behavior of the discrete Fourier transform and its inverse we have a similar analogy to the 1d function for the 2d functions as well so the both 2d discrete Fourier transform and 2d inverse discrete Fourier transform are periodic so in 1d case this can be shown like this so we have this original samples of the discrete Fourier transform it is going to be periodic with period M but one thing that you notice is that when we said we do sampling over one period we actually created the sample from 0 to M minus 1 so as you can see We take the top part or the top half of this copy of the Fourier transform and we took the lower half of this copy of the Fourier transform to get both top and bottom half of only one copy of the Fourier transform. What is usually common is to basically center the discrete Fourier transform and the way to do it is by using this equation of course the difference here is that now we know what is going to be exactly the location of the center or like the shifted version so to do that we replace u0 with upper upper case M over 2 and replace v0 with upper case N over 2 so this is as a result of centering the discrete Fourier transform for 1d case we basically shifted to location M over 2 so that means that u0 is going to be M over 2 for the 2d case we have to do it along both dimension so in this case u0 is going to be M over 2 and v0 is going to be N over 2 and that is something that is very common in practice so in the signal domain that is equivalent to multiplying either like the 1D function with negative 1 to the power X at any given location or the 2D function multiplied by negative 1 to the power X plus Y at any given location you will see how this can help us to better analyze the images in the frequency domain so now let's see what happens with the 2d discrete convolution and again the extension from 1d to 2d is very straightforward so anywhere we have a function of one variable we replace it with the function of two variables And anywhere we have a single summation over one variable, we replace it with double summation over two variable. So similar to the 1D case, because of the periodic behavior of the discrete Fourier transform and its inverse, the convolution is also periodic. So that means that this equation is only evaluated over only one period of the convolution result for discrete signal we actually perform circular convolution which basically means that we repeat the signal at given period and then we perform the rotation of one of them about the origin and then we move it step by step and at each place we calculate the sum of product As for the 2D discrete convolution theorem, we have the discrete Fourier transform of function f and h to be equal to the discrete Fourier transform of f multiplied by discrete Fourier transform of h.
And the discrete Fourier transform of the multiplication of the 2D function f and h is going to be 1 over mn. Basically, mn being the total number of... pixels in these two images in any of these two images multiplied by the convolution of the discrete Fourier transform of F and discrete Fourier transform of H again this is a constant value which is only related dependable on the size of the image that size of these two images and it's assumed that these two have the exact same size so this only changes the basically the amplitude overall and does not change the shape so even if you forget to account for this that is still fine because the shape information does not change by multiplying by this constant now that we got to this point let us see what is the difference between convolution and circular convolution So here to the left we have an example of a regular convolution.
So we have f of m basically a discrete function here is shown as a continuous function but The reason for that is we wanted to have more samples so this function has 400 samples and we have H of M which is again has 400 samples. So if we want to calculate the convolution between the two the first thing that we do is that we mirror H about the origin so this is the mirrored version and then we start. moving it one step at a time and at each step we calculate the sum of product between this displaced function and the original function and if we do that we get the result of a convolution in this form and as you can see now the range of the result of the convolution is from 0 to 800 but what if we want to perform circular convolution so for performing circular convolution we have to make these two functions periodic which basically means that we have to repeat them after each one is finished so this is the periodic version of function f of m and this is the periodic version of function h of m so now if we mirror h about the origin and then we displace it and at each location we calculate the sum of product this is the result that that we get as you can see it is periodic but each period is not similar to the actual convolution so it it looks as if all these convolution results are overlap. So to avoid the overlap we add enough number of zeros to both f and h to basically get rid of the overlap.
So assuming the size of function f to be a and the size of function h to be b for these two functions to have a circular convolution without any overlap the size of each should be at least this much so p needs to be greater than or equal to a plus b minus uh one so for function f if its size is a that means that we have to add b minus one zeros b being the size of function h and for function h we need to add a a minus one zeros For this example that we have here since both of them have the same size and the size is 400 That means that we need to at least add 399 zeros at the end of function F and also 399 zeros at the end of function H and if we do that there won't be any overlap in the result of circular convolution for 2d circular convolution you need to do the same of course you have to do it for both of the dimensions of the image this is the repetition of what we discussed before for the four year spectrum and phase angle but it's worth mentioning again so as we said before the Fourier transform is a complex function in general so therefore it can be shown in a polar form like this so F of u and V equals absolute value of F of u and V multiplied by e to the J Phi of u and V so this absolute value is in effect the Fourier spectrum and is calculated by a square root of summation of the real part of the function squared plus the imaginary part squared as for the phase angle it is defined as the arc tangent of the imaginary part over the real part and you should notice that this is done for each one of the frequency component individually so in effect if you have if you are working with 2d discrete Fourier transform these two functions are examples of element wise operations. There is another representation which is sometimes useful which is called the power spectrum which is basically the Fourier spectrum square so now let's take a look at an example to see how Fourier spectrum and phase angle can be visualized for a sample image so here on top left corner we have the original image for which we calculated the Fourier transform using 2d discrete Fourier transform and this is the representation of the Fourier transform spectrum as you can see it is mostly black but there are two reasons for that first of all if you remember the discrete Fourier transform in general is repetitive and periodic and another thing is that not all the values of the Fourier transform are in the same I would say in the same range so there are something that we need to do in order to be able to better visualize the Fourier transform spectrum the first thing that we need to do is to center the spectrum if you look closely you see some hints of bright regions on the top four on the four corners of this image And that is because we didn't center the Fourier transform. So to do that we apply this element wise multiplication on all the pixels of the image. So we practically multiply each pixel by negative 1 to the power x plus y.
So we change x plus y. We are practically changing this function as well. and that helps us to center the Fourier transform. So, this is the Fourier transform spectrum of the centered Fourier transform. Again, it is very dark to do that.
If you remember from the previous chapter, we said that we can apply log transformation to better visualize the Fourier transform. So, after applying the log transformation to... this image to the Fourier transform spectrum we get this image so the log transformation that we use is defined using this equation one thing that you might notice is that this rectangle image is wider in the vertical direction while it's narrower in the horizontal direction so being narrow in the horizontal direction if you remember from the Fourier transform of the 2d box function we said that if it is narrow along one direction that means that the zero crossing would happen with more distance along that direction in the frequency domain so along the horizontal direction the zero crossing are happening with a larger distance along the vertical direction the zero crossing points are happening the smaller distances because the rectangle is wider along the vertical direction so now let's see what happens if we translate or rotate the the original image so this is the original image being translated and this is the Fourier transform a spectrum of the translated image as you can see the Fourier transform spectrum didn't change and this is because of this property that we had so if you remember when we translate our image we basically multiply the Fourier transform by this complex exponential function so if we calculate the spectrum or the absolute value the absolute value of this complex exponential function is 1 so In effect, the Fourier transform spectrum of the translated image is exactly the same as the Fourier transform of the non-translated image.
What changes is with regard to the phase angle. So, this is the phase angle of the original image and this is the phase angle of the translated image. So, what happens if we rotate the... originally made by certain angle So here you see we have rotated the original image by 45 degrees. So if we calculate the Fourier transform and we calculate the spectrum we see that the Fourier transform spectrum of the rotated image is also rotated by the exact same amount 45 degrees.
As for the phase angle, this is the phase angle of the rotated image. So now the question becomes out of the Fourier transform spectrum and the phase angle, which one is more important? So in another word, in reconstructing the original image, which one of the Fourier spectrum or the phase angle contains more information?
To answer this question, let's just see what happens with this boy's image. So if we calculate the... Fourier transform the discrete Fourier transform of this image and we show the phase angle information you see it practically looks like noise but now let's just use only this phase angle without any Fourier spectrum to reconstruct the image so if we do that this is the image that we get so even though the intensity information is missing but we still can see all the shape features of the image so you see these boundaries that are basically the boundaries that you saw in the original image but what happened if we eliminate the phase angle information and we try to reconstruct the original image by only using the Fourier transform spectrum so this is the result that we get so between these two one thing that you notice is that the reconstruction using only phase angle contains more information related to the original image and because of that phase angle it is is more important than the Fourier transform spectrum so this is the result of reconstructing the boy image using its phase angle and the spectrum of the rectangle image that we saw before so even though it is not 100% accurate still you can infer from this image that this is basically very similar to the original image of course if you use its own Fourier transform spectrum you basically create the the original image and this is the rectangle image that is reconstructed reconstructed using its face but as for the spectrum we use the boys image and again you here see that we can clearly see the rectangle although not hundred percent accurate but this further confirms that between the two spectrum and phase angle phase angle contains more information about the image. But again if you refer back to the original equations there is no one-to-one correspondence between the individual pixels in the original image and individual components in the frequency domain.
So this table summarizes all the discrete Fourier transform definition that we had. So we had the definition for the discrete Fourier transform. We had the definition for the inverse discrete Fourier transform. We had the definition for the Fourier transform spectrum, phase angle.
We talked about the polar representation of the Fourier transform. We talked about the power spectrum of the Fourier transform. We also talked about the average value. And we said that the value of the... Fourier transform at location zero is proportional to the average of the original signal because this value is basically talking about the zero frequency component of the frequency domain or in another word it talks about the dc component of the original signal we talked about the periodic behavior of the discrete Fourier transform and its inverse we saw the definitions for the circular convolution and here is the definition for the circular correlation of course in many of the applications we only care about the circular convolution because if you remember we said that convolution is basically the basis for image filtering then we talked a little bit about separability of the 2d discrete Fourier transform you saw an example of it when we applied the Fourier transform onto the two-dimensional box function and we said that we can separate the basically decompose the complex exponential function into two function and then apply the integrals over one variable and then over another variable so the same can be said about 2d discrete Fourier transform and it can be calculated by computing the one-dimensional discrete Fourier transform along the rows for example first and then we apply the one-dimensional discrete Fourier transform along the columns and the last definition which we didn't talk about what it is pretty interesting and it can be derived directly from the definitions of the discrete Fourier transform is that you can basically use the exact same algorithm that you use to define the original discrete Fourier transform to perform inverse discrete Fourier transform.
So to do that, you need to do is you need to provide the complex conjugate of the discrete Fourier transform to the algorithm and then it gives you a weighted complex conjugate of the original signal. This table summarizes the several discrete Fourier transform pairs that we saw so far. We didn't talk about the symmetry properties that much.
If you're interested you can refer to the table 4.1 in the book. Discrete Fourier transform is a general operator so that means that if you apply it to sum of two function the result is basically summing up the each one of these functions Fourier transform. We talked about the translation, we talked about how translation can be used to center the frequency transform by multiplying the original signal by this function. We talked about how rotation would affect the discrete Fourier transform.
We talked about the convolution theorem and how convolution in the signal domain is equivalent to multiplication in the frequency domain and vice versa we didn't talk about correlation here again because what we care about more is the convolution we saw how we can calculate the Fourier transform of a unit impulse we saw how we can do it for a rectangle function so this one is similar to a 2d box function but it is shifted to location and an a and b here are the definitions for the discrete Fourier transform of sine and cosine function we didn't talk about them but it is good to know that both sine and cosine in the signal domain can be represented as two individual impulse function in the frequency domain and then we can have the property for the differentiation of function and what is the effect in the frequency domain which we didn't talk about here and then lastly the fact that a Gaussian function in the signal domain is equivalent to a Gaussian function in the frequency domain and vice versa of course the value for mean and variance of the Gaussian function is going to change So now that we have covered a lot of theory regarding the Fourier transform and discrete Fourier transform in both one-dimensional and two-dimensional functions, it's now the time to talk about basics of filtering in the frequency domain. So this is something that I briefly go over and I will talk in more detail in the next lecture. So we saw that the Fourier transform is computed by combining all the values of the signal in the spatial domain. modified by the values of the exponential terms. So, because of this, and as you saw in the example, it is impossible to make direct correspondence between specific components of an image and its Fourier transform.
So, we cannot have a direct one-to-one correspondence between one pixel in the image and a frequency component in the Fourier transform domain. since the frequency is directly related to the spatial rate of change we can associate frequencies in the frequency transform with patterns of intensity variations in the image so not necessarily the intensity itself but how the intensity changes going from one location to another so based on this filtering in the Fourier domain is the act of modifying the Fourier transform to achieve a specific objective, followed by inverse Fourier transform to obtain the spatial domain representation of the processed result. So, this can be formulated like this.
So, we have this kernel function, we have this, you can say, any function in the frequency domain for which we calculate the element-wise multiplication with the Fourier transform of the original image then what we do is that we calculate the inverse discrete Fourier transform of this multiplication and since the images that we work with are generally only contain real values we calculate the real part of this inverse discrete Fourier transform to get to the process image so based on this we can have a 7 fifth step approach for filtering an image in the frequency domain so for the first step we have the input image we call it f of x and y with the size m by n m is the number of rows and n is the number of columns so the first thing that we do is that we zero mirror or replicate pad the original image to form f P of X of Y with the size P and Q for P being 2m and Q being 2n and that is to avoid any sort of overlap that we might have in the frequency domain. Then we multiply this image by this function and the reason for that is we want to center the Fourier transform so that way the act of defining any transfer function in the frequency domain is much much simpler. After the second step we calculate the discrete Fourier transform of this multiplication function and we get f of u and v which is the Fourier transform of the result of the previous step.
Now to apply any filter we construct a real symmetric filter transfer function h of u and v of size p multiplied by q so as you can see the size of the filter is the same as the size of the original limit and we place the center of the filter at location p over 2 and q over 2. so now what we need to do is that we need to form this product G of u and b equals H of u and v multiplied by F of u and b and We do it element wise by element wise multiplication So now after this step we have the Fourier transform of the filtered image So to get the original filter image we need to do several things first We need to calculate the inverse discrete Fourier transform So the inverse discrete Fourier transform is a complex function in general. So now since we work with images that are real, we take the real part of the result. And then to basically reverse the effect of the multiplication that we had at the beginning here, we multiply this result by negative 1 to the power x and y, x plus y at any given location in the image. and then finally the final filtered result g of x and y of the same side as the input image can be extracted from the m by n region from the top left quadrant of G P of X and Y of course this seven step procedure is all words so it is better if you see in a practical example so here we have an m by n scanning electron microscope image so as we said the first step is to pad the image to create an image of size 2m by 2n so the way we do it is by applying by padding the image with zeros to its right and bottom of course you can apply the zeros uniformly all around the image but this is the easiest way to do and it's much more straightforward then the next step is to multiply this result by the function negative 1 to the power x plus y at any location. So this is the result of that multiplication.
Now we apply the 2D discrete Fourier transform. And we create both the Fourier transform spectrum and Fourier transform phase angle. So this is a representation of the Fourier transform spectrum.
Now, let's say here we want to apply a Gaussian low-pass filter to the image. So, the way we do it, we define our Gaussian low-pass filter centered at location p over 2 and n over 2. So, basically right at the center. And then what we do is we calculate the element-wide multiplication between this filter. the Fourier transform not necessarily not only the spectrum but both the spectrum and the phase angle so this is a representation of the spectrum of the product of H and F again we don't only rely on the spectrum this is only for representation purposes and then The next step would be to calculate the real part of the inverse discrete Fourier transform and multiply it by negative 1 to the power x plus y at any given location.
So now to get to the final result, we basically extract the top left quarter of the image and that is the result of applying a Gaussian filter. in the frequency domain. You might say okay so this is too much work for a simple Gaussian filter but you need to realize that as we discussed before doing this especially when you have larger images and you have large kernel is usually computationally efficient in comparison to performing 2d convolutions in the signal domain. here you can see more examples of filters in the frequency domain so here we have the original image and here we have the low pass caution filter similar to the one that we saw in the previous lecture but what if we want to apply a high pass filter by calculating the inverse of this function or if you remember the way that I described last time that not necessarily last time the previous chapter that we can create a high-pass filter only by using a low-pass filter so if we do that and we apply to the image we basically get an image of this form as you can see all the uniform regions are almost completely suppressed only thing that is left is the shape information and boundaries of the original image this one is at the result of high pass filtering but with a little bit of bias on zero frequency terms so this way we don't suppress the uniform regions but we enhance the high frequency components and edges.
Of course you will see more examples the next lecture so in general there are two ways to design filters so you can either specify the filter in the spatial domain or you can specify the filter in the frequency domain because of this there are two ways for implementing any filtering tool you can either use a spatial convolution or you can use discrete Fourier transform and inverse discrete Fourier transform to apply your filters so here you can see an example of a one-dimensional Gaussian low-pass filter and this one is the corresponding kernel in the spatial domain of course these two functions are continuous in reality what you need to do is that you need to sample them and here you see an example of a Gaussian high-pass filter in the frequency domain and you see its corresponding corresponding kernel in the signal domain as well so again these two are continuous in reality you use a sample version of them and here is another example that shows how spatial filtering and frequency filtering if done properly they are producing identical results so here is the original image that we have and here is Fourier spectrum On top left corner here we have a spatial kernel and a perspective view of its corresponding frequency domain filter transfer function. Here is the same filter transfer function shown as an image. If anywhere that you have a dark region you are basically dealing with negative values and anywhere you have a bright region here you are dealing with positive values. And in this image on the left, lower left is the result of filtering the original image in the frequency domain with the transfer function defined like this. And here is the result of filtering the same image in the spatial domain with the kernel defined like this.
And as you can see, the results are completely identical. This pretty much concludes all the things that I wanted to talk to you about in this lecture. In the next lecture, I will talk about image smoothing using low pass frequency domain filters, image sharpening using high pass frequency domain filters, then I talk a little bit about selective filtering, and finally I will talk about the fast Fourier transform and why it is being used widely in all.
sort of different signal and image processing applications