Convolution and the Fourier Transform: Math! (in pictures!!)
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 34 | |
| Author | ||
| License | 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 | |
| Identifiers | 10.5446/38546 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
Bangbangcon (!!CON 2016)29 / 34
3
15
16
17
18
19
24
28
30
32
34
00:00
MathematicsFourier transformConvolutionComputer animation
00:11
Fourier transformConvolutionMathematicsConvolutionType theoryCartesian coordinate systemMultiplication signFourier transformProjective planeBitTheory of relativityNichtlineares GleichungssystemJSONXMLComputer animationProgram flowchart
01:07
Group actionPulse (signal processing)Medical imagingField (computer science)Greatest element2 (number)Sinc functionInterface (computing)Food energyDistanceMathematicsCartesian coordinate systemCausalityMultiplication signData transmissionComputer animation
02:00
SurfaceMathematicsFood energyReflection (mathematics)Medical imagingCross section (physics)Slide ruleGreatest elementRow (database)Line (geometry)Pulse (signal processing)Interface (computing)Single-precision floating-point format
02:35
ConvolutionData compressionPulse (signal processing)MathematicsFrequencyPulse (signal processing)10 (number)Different (Kate Ryan album)MetreCross-correlationTransmitterRadarDisplacement MappingCharge carrierMaxima and minimaDemo (music)Inheritance (object-oriented programming)Shape (magazine)Product (business)RhombusImage resolutionConvolutionCartesian coordinate systemCodeMedical imagingFood energyOperator (mathematics)Envelope (mathematics)Point (geometry)SatelliteRectangleNichtlineares GleichungssystemSurfaceDivision (mathematics)MultiplicationLine (geometry)Functional (mathematics)AreaCode division multiple accessComputer animation
05:28
Image processingCross-correlationOperator (mathematics)Functional (mathematics)Image processingConvolutionMedical imagingRow (database)Order (biology)Computer animation
05:42
ConvolutionMedical imagingOperator (mathematics)Cross-correlationOrder (biology)Noise (electronics)PreprocessorComputer animation
06:00
Cartesian coordinate systemRecursionSet (mathematics)Image processingCross-correlationMedical imagingComputer animation
06:20
Fourier transformFourier transformDifferent (Kate Ryan album)Trigonometric functionsDisk read-and-write headFunctional (mathematics)Transformation (genetics)Discrete groupSummierbarkeitCross-correlationDiagram
06:43
SurfaceSquare numberFrequencySummierbarkeitHecke operatorPoint (geometry)Diagram
07:16
Data compressionData compressionFrequencyOrder of magnitudeConnectivity (graph theory)Phase transitionMultiplication signSpacetimeTerm (mathematics)Band matrixSpectrum (functional analysis)DiagramComputer animation
07:40
FrequencyConnectivity (graph theory)FrequencyOrder of magnitudePlotterComputer animation
07:51
Fourier transformNumberConnectivity (graph theory)FrequencyInformationComputer animation
08:04
Frequency1 (number)Spectrum (functional analysis)FrequencyNoise (electronics)Computer animation
08:13
TelecommunicationNoise (electronics)Process (computing)Fourier transformComputer animation
08:29
Line (geometry)Group actionMedical imagingIntegrated development environmentNoise (electronics)Computer animation
09:03
Digital signal processingRaw image formatSocial classComputer animation
09:12
Line (geometry)Fourier transformFrequencyExpected valueSpacetimeOutlierComputer animationDiagram
09:40
Noise (electronics)Line (geometry)Fourier transformInformationComputer animation
09:49
Inverse elementNoise (electronics)Phase transitionFourier transformDiagram
10:15
Fourier transformTheoremConvolutionMedical imagingCellular automatonAlgorithmFourier transformSocial classLoginTheoremSummierbarkeitMultiplication signSignal processingConvolutionInverse elementView (database)Image processingCompilation albumComputer animationLecture/Conference
11:30
Computer animation
11:41
Power (physics)FreewareProgram flowchart
Transcript: English(auto-generated)
00:19
Thank you.
00:24
Oh, too far away. I will be presenting two related concepts today, convolution and the Fourier transform. And rather than diving into the equations, my goal is to just give a quick graphical explanation of each of them, which has been helped greatly by Allison already taking care of the Fourier transform, and then show how I've used them in my own research,
00:42
and then show other applications that might be of use in your own projects. And 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 gory details required to actually use them. And if you have seen this stuff before, my goal is simply to entertain you with
01:03
what I consider to be a mind-blowingly cool application of electrical engineering. I'm a geophysicist, and my research group uses airborne ice penetrating 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,
01:21
and the radar transmits a pulse of energy, and then listens to reflected signal. And we can plot the resulting energy received at the airplane, like this, where the y-axis is the time since transmission, which corresponds to the distance underneath the airplane, and the x-axis is the strength of the field at that time. And so this peak here corresponds to the air-ice interface.
01:43
All of these wiggles are layers within the ice, as the chemical composition changes and causes reflections. And then this littler peak at the bottom is the ice-rock interface. And as the airplane flies along, the radar pulses at 6,000 times a second. And we can combine all of those pulses into an image like this, which you can think
02:02
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
02:21
the ice-rock interface, and then 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
02:41
on two functions, and 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,
03:00
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.
03:23
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.
03:41
That's it. Okay, going back to the radar, how would we use this? Our early ice penetrating radars transmitted a square pulse, which might be, oh, a couple hundred nanoseconds long over a 60 megahertz carrier frequency. But a problem with a pulse shaped like this is that it's hard to find the exact center of the reflected pulse because the energy envelope is just a rectangle.
04:04
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
04:21
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. Starts 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.
04:45
So we've maintained our signal, 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
05:04
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
05:22
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.
05:42
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.
06:02
In here, I have two features corresponding to vertical and horizontal edges in the image. As you can see, it nicely picks out the edges in the Recurse Center 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.
06:23
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 Allison'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.
06:44
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 the radar data, which is a little more interesting. And just like Allison did, as we add more and more frequencies to our summation, the resulting signal gets closer and closer and closer to the original data.
07:07
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 Allison showed, this immediately goes into compression, and that's all I'm going
07:21
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, yadda yadda yadda. So rather than drawing out the sinusoids, you can represent a Fourier transform in terms
07:40
of the magnitude and the phase of each frequency component. And note that for the magnitude, I've drawn it in 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.
08:03
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 in a processing pipeline for our radar receiver electronics.
08:22
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.
08:45
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.
09:01
So previously, my group had found a way to remove it that added these artifacts, drove me crazy. 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.
09:21
And here again, we're plotting it in frequency space. So there's a big peak around zero 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
09:44
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
10:03
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. Makes me a lot happier to not have those obnoxious artifacts.
10:24
Okay. 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
10:44
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 your philosophical view,
11:08
about how to calculate a discrete Fourier transform in N log N. This is great. N 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,
11:25
is computationally feasible thanks to the convolution theorem and the Fourier transform. Thank you. I will leave you with penguins.