Reading: Fourier Transforms

CSC 262 - Computer Vision - Weinman

Summary:

We briefly direct your attention to the most important ideas in the assigned readings on the Fourier transform.

8.3 Spatial Frequency and Fourier Transforms

Key idea:

An image is just a (strangely shaped) vector. Bam! All the stuff you know from Linear Algebra about vectors will apply to the objects we know as images. We've been looking at images in the standard basis, which is not very useful for computing.

8.3.1 Fourier Transforms

We'll unpack all the math in class, so don't panic about the equations. Key ideas:  

• Instead of the standard basis (i.e., a big set of images/vectors where there's a "1" at a single pixel and zeros everywhere else), we're going to use basis images like those in Figure 8.6; adding sinusoids in the right proportions can make any image! (The basis is complete.)
• The first equation's double integral is like sum, which is like a dot product, which is a projection. This tell us how much the original image/vector (in the standard basis) "looks like" the basis image/vector. (Said differently, it tells us how much of that basis vector we need in the recipe-its coefficient.)

If a standard image is the column "vector" x and the new set of basis vectors are collected as rows in the matrix F, then we achieve a change of basis by way of the product

y=Fx.

So now we can play with the image x in its new representation (basis) y.

Linearity

Sure, linear operations are handy.

The Inverse Fourier Transform

Changing back to the original basis (returning after you did something while "through the looking glass") is also handy.

"Go somewhere, do something, come back."

- Professor Gary Sherman, Mathematics Department, Rose-Hulman Institute of Technology

Key Idea:

there's another matrix F⁻¹ so that

x=F−1Fx.

But what's more interesting is what you can do between F⁻¹ and F, so that

^ x   =F−1g(Fx)

when g is some non-linear operation on y=Fx giving you an alternative reconstruction ∧x.

Fourier Transform Pairs

You don't need to dwell on them, but you can see if you spot any functions that have interesting Fourier transforms or operations that have effects on the Fourier transform that you find interesting.

Phase and Magnitude

Don't worry about the equations here yet. There are two different but equivalent ways to think about the key idea. I'll state them both.

Tweedledee:

Each coefficient that we'd been thinking of as paired with a single basis vector (a wave) actually has two basis vectors: a sinusoid wave and a cosine version of the wave, albeit both with the same frequency (wavelength). The image determines how much of each wave there is in the recipe, but it helps to think of them together since they have the same shape and only differ in their wave's starting position.

Tweedledum:

Each Fourier coefficient corresponds to a slightly tunable basis vector. The specific tuning isn't chosen arbitrarily (it depends on the specific image being represented), but is flexible (so it can represent any image). That tuning knob is the phase (offset) of the wave at the specified frequency.

8.4 Sampling and Aliasing

Good! You made it this far. Those are the hugest ideas. Next are some "fun" and "interesting" (yes, those are professor quotes¹ around the adjectives) properties of images that the Fourier transform relates to and helps us understand.

8.4.1 Sampling

Really, there's not a whole lot here to dwell on (definitely not the math!) other to know that sampling is a thing that exists, and you should know what it is.

• Focus on Figure 8.10 to clarify the "what"
• Focus on Figure 8.9 to suggest why the sampling rate is important to image fidelity

Key foreshadowing:

"unsuccessful sampling schemes cause high frequency information to appear as lower frequency information." (Figure 8.9 caption)

8.4.2 Aliasing

Key idea:

"a signal that is sampled too slowly will be misrepresented by the samples; high spatial frequency components of the original signal will appear as low spatial frequency components in the sampled signal, an effect known as aliasing." (non-bold emphasis added)

That's really it in a nutshell, we're not going to derive the math, but in class we'll unpack Figures 8.11 and 8.12 (showing how aliasing comes to be), by examining the Fourier coefficients of a sampled function. Spend some time to see if you can make a little sense of these figures.

---

Footnotes:

¹Professor quotes are similar to scare quotes or air quotes as a modifer for the meaning of the term. In this case, they are terms the professor would use to describe the phenomenon, but which most other sane, normal people would never, ever apply.)