Convolution and the Fourier Transform: Math! (in pictures!!)
CC Attribution - ShareAlike 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this
Lindzey, Laura
Do you want to understand how GPS or cell phones work? MP3 or JPEG compression? Are you playing with image processing? Solving PDEs? Learning about how to process ice-penetrating radar data used for studying Antarctica? (errrr...that's me.) Convolution and the Fourier transform are mathematical tools that make all of these possible. I think that the way these tools are usually presented is intimidating and non-intuitive. I think in pictures, not equations, so this talk attempts to give a graphical intuition of what these techniques actually do and where they can be useful, with examples from my own work.
 Thank you. Cool. Hi everybody. Too far away. I will be presenting two related concepts today, convolution in the Fourier transform. Rather than diving into the equations, my goal is to give a quick graphical explanation of each of them, which has been helped greatly by Alison already taking care of the Fourier transform, and then show how I've used them in my own research, and then show other applications that might be of use in your own projects. If you have not seen this stuff before, my goal is for you to get a little bit of intuition about what types of things these tools are useful for so you will recognize when it's time to go look up all the great details required to actually use them. You have seen this stuff before, my goal is simply to entertain you with what I consider to be a mind-blowingly cool application of electrical engineering. I'm a geophysicist, and my research group uses airborne ice-print-rating radar to study Antarctica. So how does this work? As we fly above the ice sheet, we use an old World War II era DC-3, a lot of fun, and the radar transmits a pulse of energy and then listens to reflected signal. We can plot the resulting energy received to the airplane like this, where the y-axis is a time-sensitive transmission, which corresponds to the distance underneath the airplane, and the x-axis is the strength of the field at that time. This peak here corresponds to the air-ice interface. All of these wiggles are layers within the ice, as they can look at composition changes and causes reflections. This little peak at the bottom is the ice-rock interface. As the airplane flies along, the radar pulses at 6,000 times a second. We can combine all of those pulses into an image like this, which you can think of as a two-dimensional cross-section of the ice sheet. Each column in the image corresponds to the record from a single pulse of energy, like I plotted on the previous slide just in grayscale now. And again, this top right line is the surface. The brighter reflection at the bottom is the ice-rock interface. Since ice is almost transparent to radar energy, we can easily see through several kilometers. I think our record last season was like 4.8 kilometers, and I think we've gotten higher than that before. Okay, back to the math. I'm going to start with cross-correlation, which is a mathematical operation that acts on two functions. For this demo, I'm just going to be using super simple F and G. I think of cross-correlation as finding how similar these two functions are and the displacement at which they are best aligned. So to do this in pictures, you just start with F, and then you slide G along it, and then you calculate their product, which I'm showing here on the second line. The area underneath their product is just defined to be the cross-correlation at that point, where the point is how far you've displaced or slid G along. And yes, it can be negative, just indicating that they are anti-correlated. Okay. So quick disambiguation. This is the equation for the operation we just did. I've drawn a new function that's not symmetric. You'll also hear about convolution, which is this. The only difference between correlation and convolution is that minus sign, which all that means is you just need to mirror H before you slide it along G. That's it. Okay. Going back to the radar. How would we use this? Our early ice-print trading radars transmitted a square pulse, which might be a couple hundred nanoseconds long over a 60 megahertz carrier frequency. But a problem with a pulse shape like this is that it's hard to find the exact center of the reflected pulse because the energy envelope is just a rectangle. And you want this exact center because you want to know where the surface is to more detail than tens of meters. So you might think that you could just try correlating the transmitted pulse shape with the pulse that was recorded back at the airplane, and then the exact displacement at which you get the maximum cross-correlation is the surface. However, with this shape of a pulse, it leads to a fairly broad peak. That diamond isn't really what we want. So instead, we transmit a chirped signal, start at a low frequency, ramping up to a higher one. If you self-correlate a chirp, you get a much narrower peak with the same peak power. So we've maintained our penetration ability to the ice, but you have much better vertical resolution. And so rather than tens of meters, we can see features that are about three meters apart. Cool. Okay. Another application of convolution would be code division multiple access, which is a technique that's used for GPS satellites, cell phone signals, et cetera. The goal is to be able to have a bunch of different devices all transmitting on the same frequency band, but then for me to be able to say, I want the signal just from that satellite, and it's all it is, is convolving the code for the satellite with the data from everybody, and the data from that satellite pops right back out. And sorry, I couldn't come up with a fast image for that one. Cross-correlation is also useful in image processing. It's the same idea, but rather than sliding a 1D function across another 1D function, you slide a 2D image across a 2D image along every row. So a common operation might be to do correlation or convolution with a Gaussian in order to blur or smooth the image. This is a common pre-processing step for other pipelines or to help beat down some noise. It's also used for feature extraction. And here I have two features corresponding to vertical and horizontal edges in the image. And as you can see, it nicely picks out the edges in the RecurSenter logo. A bunch of image processing applications will use a much richer feature set and then try to do classification on it. Okay, so that's it for correlation for now. So what's a Fourier transform? And I think of a Fourier transform as a way to express an arbitrary function at the sum of sinusoids. This is the exact same idea as the discrete cosine transformation from Alice's talk. The differences between them are some of those gory details I promised to leave out. And they really don't matter for the picture you need to have in your head. So usually the example is a square wave and I'm so sick of that. So let's just look at the bedrock surface and wait our data, which is a little more interesting. And just like Alice did, as we add more and more frequencies to our summation, the resulting signal gets closer and closer and closer to the original data. As you can see, this converged remarkably quickly. Heck, n equals 50 was pretty good for a signal that had over 4,000 points in it. And as Alice showed, this immediately goes into compression. And that's all I'm going to say there. Instead I want to spend more time on the frequency spectrum because that's a more common way for electrical engineers to talk, they'll be talking frequency space bandwidth, yada, yada, yada. So rather than drawing out the sinusoids, you can represent a Fourier transform in terms of the magnitude and the phase of each frequency component. And note that for the magnitude I've drawn it on a log plot. So all of these over here are actually really small numbers. And so from this, you can see that the higher frequency components of the Fourier transform of the data that I took this transform of aren't very important. Almost all of the information is in these lower ones, which is just another way of saying that we can throw those away without losing much detail. So I've used the frequency spectrum as a way to characterize and remove noise recently and processing pipeline for our radar receiver electronics. So, sorry, I totally mangled that. There's noise due to our radar receiver electronics and it's possible to remove it after characterizing it with the Fourier transform. So this is an image of the raw, almost unprocessed data that shows the noise well. And yes, you can see the lines up there. All these horizontal lines are way too regular to be anything that we care about. These are electronic noise. There's not something in the environment. And this was a problem because this stuff is obscuring the dimmest echoes. And if we can get rid of it, we gain about 10 decibels of signal to noise ratio at the very deepest dimmest spots. So previously my group had found a way to remove it that added these artifacts, drove me crazy. I mean, I had just taken a digital signal processing class and said, we can do better than this. So going back to the raw data, let's consider the Fourier transform of the region between the dotted lines. Looks like this. And here again, we're plotting it in frequency space. So there's a big peak around 0 megahertz, which is just the constant offset. And then there's those humps centered around 10 megahertz. And these correspond to the frequencies that we are transmitting. So this looks like you'd expect. There's no clear outliers, sadly. So instead, let's go back and look at a region that only contains noise, no signal in it. Yep, horizontal lines. Fourier transform of this is way more informative. You have these sharp peaks at 10 megahertz. And everything else is much weaker. Great. So now we know the amplitude and the phase of the sinusoid that corresponds to this noise, which means that we can take the Fourier transform of our data, subtract out that amplitude and phase from the single sinusoid that it belongs to, do the inverse Fourier transform and get data without the noise. And the resulting image looks like this. It makes me a lot happier to not have those obnoxious artifacts. OK. So why did I choose to pair these two topics? If you go by the definition of convolution with that sum that I didn't really talk about, computing it is O of n squared. Because each step, you're multiplying every cell with every cell. However, the convolution theorem tells us that the Fourier transform of f convolved with g is equal to the Fourier transform of f times the Fourier transform of g. So if you can efficiently calculate the forward and inverse Fourier transforms, you can efficiently calculate the convolution. And back in 1965, an algorithm was discovered or invented, depending on the philosophical view, about how to calculate a discrete Fourier transform and n log n. This is great. So it's squared to n log n. And so combined with the convolution theorem, this makes a whole class of solutions computationally feasible. So all the image processing, signal processing that I talked about in the first half of this talk is computationally feasible thanks to the convolution theorem and the Fourier transform. Thank you. I will leave you with penguins. Good luck.
 Thank you.  Cool.  Hi everybody.  Too far away.  I will be presenting two related concepts today, convolution in the Fourier transform.  Rather than diving into the equations, my goal is to give a quick graphical explanation  of each of them, which has been helped greatly by Alison already taking care of the Fourier  transform, and then show how I've used them in my own research, and then show other applications  that might be of use in your own projects.  If you have not seen this stuff before, my goal is for you to get a little bit of intuition  about what types of things these tools are useful for so you will recognize when it's  time to go look up all the great details required to actually use them.  You have seen this stuff before, my goal is simply to entertain you with what I consider  to be a mind-blowingly cool application of electrical engineering.  I'm a geophysicist, and my research group uses airborne ice-print-rating radar to study  Antarctica.  So how does this work?  As we fly above the ice sheet, we use an old World War II era DC-3, a lot of fun, and  the radar transmits a pulse of energy and then listens to reflected signal.  We can plot the resulting energy received to the airplane like this, where the y-axis  is a time-sensitive transmission, which corresponds to the distance underneath the airplane, and  the x-axis is the strength of the field at that time.  This peak here corresponds to the air-ice interface.  All of these wiggles are layers within the ice, as they can look at composition changes  and causes reflections.  This little peak at the bottom is the ice-rock interface.  As the airplane flies along, the radar pulses at 6,000 times a second.  We can combine all of those pulses into an image like this, which you can think of as  a two-dimensional cross-section of the ice sheet.  Each column in the image corresponds to the record from a single pulse of energy, like  I plotted on the previous slide just in grayscale now.  And again, this top right line is the surface.  The brighter reflection at the bottom is the ice-rock interface.  Since ice is almost transparent to radar energy, we can easily see through several kilometers.  I think our record last season was like 4.8 kilometers, and I think we've gotten higher  than that before.  Okay, back to the math.  I'm going to start with cross-correlation, which is a mathematical operation that acts  on two functions.  For this demo, I'm just going to be using super simple F and G. I think of cross-correlation  as finding how similar these two functions are and the displacement at which they are  best aligned.  So to do this in pictures, you just start with F, and then you slide G along it, and  then you calculate their product, which I'm showing here on the second line.  The area underneath their product is just defined to be the cross-correlation at that  point, where the point is how far you've displaced or slid G along.  And yes, it can be negative, just indicating that they are anti-correlated.  Okay.  So quick disambiguation.  This is the equation for the operation we just did.  I've drawn a new function that's not symmetric.  You'll also hear about convolution, which is this.  The only difference between correlation and convolution is that minus sign, which all  that means is you just need to mirror H before you slide it along G. That's it.  Okay.  Going back to the radar.  How would we use this?  Our early ice-print trading radars transmitted a square pulse, which might be a couple hundred  nanoseconds long over a 60 megahertz carrier frequency.  But a problem with a pulse shape like this is that it's hard to find the exact center  of the reflected pulse because the energy envelope is just a rectangle.  And you want this exact center because you want to know where the surface is to more  detail than tens of meters.  So you might think that you could just try correlating the transmitted pulse shape with  the pulse that was recorded back at the airplane, and then the exact displacement at which you  get the maximum cross-correlation is the surface.  However, with this shape of a pulse, it leads to a fairly broad peak.  That diamond isn't really what we want.  So instead, we transmit a chirped signal, start at a low frequency, ramping up to a  higher one.  If you self-correlate a chirp, you get a much narrower peak with the same peak power.  So we've maintained our penetration ability to the ice, but you have much better vertical  resolution.  And so rather than tens of meters, we can see features that are about three meters apart.  Cool.  Okay.  Another application of convolution would be code division multiple access, which is a  technique that's used for GPS satellites, cell phone signals, et cetera.  The goal is to be able to have a bunch of different devices all transmitting on the  same frequency band, but then for me to be able to say, I want the signal just from that  satellite, and it's all it is, is convolving the code for the satellite with the data from  everybody, and the data from that satellite pops right back out.  And sorry, I couldn't come up with a fast image for that one.  Cross-correlation is also useful in image processing.  It's the same idea, but rather than sliding a 1D function across another 1D function,  you slide a 2D image across a 2D image along every row.  So a common operation might be to do correlation or convolution with a Gaussian in order to  blur or smooth the image.  This is a common pre-processing step for other pipelines or to help beat down some noise.  It's also used for feature extraction.  And here I have two features corresponding to vertical and horizontal edges in the image.  And as you can see, it nicely picks out the edges in the RecurSenter logo.  A bunch of image processing applications will use a much richer feature set and then try  to do classification on it.  Okay, so that's it for correlation for now.  So what's a Fourier transform?  And I think of a Fourier transform as a way to express an arbitrary function at the sum  of sinusoids.  This is the exact same idea as the discrete cosine transformation from Alice's talk.  The differences between them are some of those gory details I promised to leave out.  And they really don't matter for the picture you need to have in your head.  So usually the example is a square wave and I'm so sick of that.  So let's just look at the bedrock surface and wait our data, which is a little more  interesting.  And just like Alice did, as we add more and more frequencies to our summation, the resulting  signal gets closer and closer and closer to the original data.  As you can see, this converged remarkably quickly.  Heck, n equals 50 was pretty good for a signal that had over 4,000 points in it.  And as Alice showed, this immediately goes into compression.  And that's all I'm going to say there.  Instead I want to spend more time on the frequency spectrum because that's a more common way  for electrical engineers to talk, they'll be talking frequency space bandwidth, yada,  yada, yada.  So rather than drawing out the sinusoids, you can represent a Fourier transform in terms  of the magnitude and the phase of each frequency component.  And note that for the magnitude I've drawn it on a log plot.  So all of these over here are actually really small numbers.  And so from this, you can see that the higher frequency components of the Fourier transform  of the data that I took this transform of aren't very important.  Almost all of the information is in these lower ones, which is just another way of saying  that we can throw those away without losing much detail.  So I've used the frequency spectrum as a way to characterize and remove noise recently  and processing pipeline for our radar receiver electronics.  So, sorry, I totally mangled that.  There's noise due to our radar receiver electronics and it's possible to remove it after characterizing  it with the Fourier transform.  So this is an image of the raw, almost unprocessed data that shows the noise well.  And yes, you can see the lines up there.  All these horizontal lines are way too regular to be anything that we care about.  These are electronic noise.  There's not something in the environment.  And this was a problem because this stuff is obscuring the dimmest echoes.  And if we can get rid of it, we gain about 10 decibels of signal to noise ratio at the  very deepest dimmest spots.  So previously my group had found a way to remove it that added these artifacts, drove  me crazy.  I mean, I had just taken a digital signal processing class and said, we can do better  than this.  So going back to the raw data, let's consider the Fourier transform of the region between  the dotted lines.  Looks like this.  And here again, we're plotting it in frequency space.  So there's a big peak around 0 megahertz, which is just the constant offset.  And then there's those humps centered around 10 megahertz.  And these correspond to the frequencies that we are transmitting.  So this looks like you'd expect.  There's no clear outliers, sadly.  So instead, let's go back and look at a region that only contains noise, no signal in it.  Yep, horizontal lines.  Fourier transform of this is way more informative.  You have these sharp peaks at 10 megahertz.  And everything else is much weaker.  Great.  So now we know the amplitude and the phase of the sinusoid that corresponds to this  noise, which means that we can take the Fourier transform of our data, subtract out that amplitude  and phase from the single sinusoid that it belongs to, do the inverse Fourier transform  and get data without the noise.  And the resulting image looks like this.  It makes me a lot happier to not have those obnoxious artifacts.  OK.  So why did I choose to pair these two topics?  If you go by the definition of convolution with that sum that I didn't really talk about,  computing it is O of n squared.  Because each step, you're multiplying every cell with every cell.  However, the convolution theorem tells us that the Fourier transform of f convolved  with g is equal to the Fourier transform of f times the Fourier transform of g.  So if you can efficiently calculate the forward and inverse Fourier transforms, you can efficiently  calculate the convolution.  And back in 1965, an algorithm was discovered or invented, depending on the philosophical  view, about how to calculate a discrete Fourier transform and n log n.  This is great.  So it's squared to n log n.  And so combined with the convolution theorem, this makes a whole class of solutions computationally  feasible.  So all the image processing, signal processing that I talked about in the first half of this  talk is computationally feasible thanks to the convolution theorem and the Fourier transform.  Thank you.  I will leave you with penguins.  Good luck.
__Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_0_71.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_72_119.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_120_287.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_288_383.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_384_3011.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_3012_4571.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_4572_12539.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_12540_12599.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_12600_12731.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_12732_13979.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_13980_14495.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_14496_14723.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_14724_15371.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_15372_17255.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_17256_17459.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_17460_17807.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_17808_17855.png __Con_2016_-_Convolution_and_the_Fourier_Transform__Math___in_pictures____By_Laura_Lindzey_rzCO5fQys_17856_17861.png