Chapter 5 - Frequency and Scale

Preliminary remark: this chapter is intended for (at least) two weeks, since it is very detailed and probably introduces you to concepts you are not so familiar with yet. Thus, we have two dedicated Q&A sessions, after which is the pentecost break, where you can digest the tons of material you have learned so far.

The chapter is mainly devoted to an in-depth analysis of the Fourier transform as a tool to analyze the frequency content in a image. This transformation decomposes the image into a linear combination of elementary waves with a certain direction and frequency. There is an intimate relationships between Fourier transform and convolution, which we explore in detail, and which will give us a means to better understand image filtering. As a particular application, we will be able to understand aliasing and constraints on the sampling rate, necessary when we later look at different scales of an image.

Table of contents

Part 1 - Frequency and perception, Fourier's idea and elementary waves

Slides 1-23

We first start with an intuitive understanding of frequency, and explore how the human visual system reacts to different frequency content. We exploit the frequency-dependent sensitivity in hybrid images, which merge different parts of the frequency spectrum from two different images to create interesting effect of an image changing with viewing distance. To move towards a more profound understanding of frequency content, we first illustrate Fourier's initial idea on a 1D signal, which we approximate using sines of different amplitudes and frequencies.

For images, of course, we require two-dimensional building blocks. These are cosine waves which are parametrized by wave number, amplitude and phase. We explore how exactly these parameters influence the shape of the wave, since we need a thorough understanding of these building blocks in later chapters.


Index

00:00 Introduction, idea and usefulness for frequency content in an image
06:00 Human vision, sensitivity to frequency: Campbell-Robson curve
09:48 Hybrid images, change of frequency with viewing distance, Gabor filters
18:23 Idea of the Fourier transform, decomposition of a 1D signal into sine waves
23:00 Fourier series and frequency spectrum
25:10 Generalization to 2D: elementary cosine waves in 2D
29:05 Understanding wave number and frequency, the "direction" of the wave
35:00 Understanding phase and amplitude
38:40 Examples: how do elementary waves with different parameters look like?
45:30 Outlook: why we need complex numbers


Part 2a - Decomposition of a function into elementary waves

Slides 24-44

It turns out that waves can best be described using the complex exponential function, so we give a quick introduction to what we need from complex number theory - algebraic rules, Euler's formula and in particular the polar decomposition. Equipped with this background, we introduce elementary waves in the image plane, which are parametrized by the wave number - essentially a combination of frequency and direction. Multiplication of an elementary wave with another complex number changes amplitude and phase by the norm and argument of this number, respectively. We use this property to obtain the Fourier decomposition of a function as an infinite linear combination (i.e. integral) over all elementary waves multiplied by certain complex coefficients which depend on this function. The map from wave number to coefficient is called the Fourier transform of the function. We show basic properties of the Fourier transform on examples.


Index

00:00 Introduction, the complex number plane
05:11 Algebraic rules, multiplication of complex numbers
09:20 Side note (optional): on the beauty of complex numbers
13:07 Euler's formula
17:05 Polar representation of a complex number, norm and argument
20:00 Complex representation of the elementary wave
22:54 Changing phase and amplitude by multiplication with a complex number
24:58 The Fourier transform: coefficients in an infinite linear combination of complex elementary waves
33:35 Example: the Fourier transform of a cosine wave, constraints on the coefficients of real-valued functions
41:20 More examples for different elementary waves, rotation of a wave rotates the Fourier transform
44:40 Superposition principle: linearity of the transform
45:40 Fourier transform of real world images, influence of noise on the amplitude spectrum
49:10 Fun experiment: exchanging amplitude and phase of two images, what is more important?
51:30 Summary and outlook

Notes

13:08 A main reason why this formula is so beatiful is the special case of $t=2\pi$, for which you get $$e^{2 \pi i} - 1 = 0.$$ Thus, you have an equation which relates $1, 2, i, e$ and $\pi$ to each other in one simple formula.


Part 2b - Computing the Fourier Coefficients

Slides 45-51

The elementary waves form a basis of the space of complex-valued functions, and coefficients with respect to a basis can be computed by projection onto the basis vectors, i.e. the inner product of the elementary wave with the function. However, in order to define this properly, we need first the notion of inner product on a complex vector space, second the notion of inner product of two functions, which we both define. Given this, we can finally give a full definition of the Fourier transform and its inverse, and obtain a deeper understanding of the formulas which are typically found in books.


Index

00:00 Introduction, computing the coefficients of a vector with respect to an orthonormal basis.
05:30 The complex number plane as a vector space over the real numbers
12:10 The complex number plane as a vector space over the complex numbers
14:30 The "Hermitian" inner product on a complex vector space, conjugate of a complex number
23:20 Vector spaces of functions, norm and inner product of complex-valued functions
32:30 Understanding and computing the Fourier coefficients of a complex valued function
37:10 Theorem: the Fourier transform and inverse Fourier transform of a complex valued function
39:10 Summary and Outlook


Part 3 - The Fourier transform under image shifts, convolutions and derivatives

Slides 52-71

We analyze what happens the Fourier coefficients when we shift the original function, convolve it with a filter, or take partial derivatives, respectively. We first note that when we shift the function, this leads to a wave-number dependent change of phase in the Fourier transformation, leaving amplitudes unchanged. We can use this to determine how convolution interacts with the Fourier transform, as convolution is essentially an infinite linear combination of shifted versions of the image. Thus, we derive a very important theorem, the convolution theorem, which says that the Fourier transform of a convolution of two functions is the point-wise product of the individual Fourier transforms. We show some immediate applications of this theorem to better understand filtering. Finally, we find that taking partial derivatives amplifies high frequencies, i.e. substantially increases noise.


Index

00:00 Introduction, shifting an elementary wave
05:10 The shift theorem: change in the Fourier coefficients when the function is shifted
10:15 Example: Fourier transform of a square, shifting the square
12:18 Relation of convolution to shifting: convolution as a linear combination of shifted functions
15:10 Convolution of an elementary wave
20:10 Fourier transform of a function convolved with a filter: the convolution theorem
26:30 Note: efficient computation of convolutions with large kernels via fast Fourier transform
28:25 Example: Fourier transform of a Gaussian, Gaussian filtering in the Fourier domain
34:10 Fourier transform of a box filter, understanding why box filtering is bad
35:55 High-pass, low-pass and band-pass filters, the difference of Gaussian filter as a band-pass filter
42:20 The Fourier transform of derivatives of a function, taking derivatives amplifies high frequencies
47:40 Fast Fourier Transform (FFT) in Matlab, some implementation details to keep in mind
52:20 Summary of the properties of the Fourier transform, outlook

Notes

21:00 The formula on the right hand side is a bit sloppy for the sake of readability. What is actually meant is convolution of $g$ with the function $$q \mapsto f(q) = \int_{\mathbb{R}^2} \hat f(\omega) W_\omega(q) d\omega,$$ and in the result (which is again a function) we plug in $p$. So a precise way to write it would be $$\left(g * \left(q \mapsto \int_{\mathbb{R}^2} \hat f(\omega) W_\omega(q) d\omega \right) \right) (p).$$ I hope you can forgive me the abbreviation.


Part 4 - Image pyramids, the sampling theorem and aliasing

Slides 72-99

In order to detect patterns which are given at a different scale than the image where we want to detect them, we need to look at different versions of the image at different resolutions. Thus, it can be necessary to lower the sampling rate. We note that this results in so-called aliasing artifacts if done in a straight-forward manner. The reason is the Nyquist theorem, which gives an upper limit of frequency which can be correctly represented with a given sampling rate. In particular, to generate image pyramids with version of the image at different resolutions, we need to filter the image before every downsampling step.


Index

00:00 Introduction, patch detection at different scales
05:40 We observe strange "aliasing" artifacts when reducing sampling rate
11:53 The aliasing effect explained, the sampling theorem
20:46 Illustrations of the Nyquist limit on an example
23:30 Solution to the downsampling problem: further band-limit the signal
29:20 Gaussian image pyramid and origins in computer graphics (mipmapping)
34:10 Laplacian pyramid: difference of Gaussians at different levels
36:10 Summary and outlook


Proof of the sampling theorem

This is an optional section, intended for everyone interested in the proof of the sampling theorem. Since some very advanced mathematics is required to do it in a fully rigorous manner, we can only give a sketch and an intuitive understanding of the concepts involved, but I believe it will be illuminating if you take the effort to work through it.


Index

00:00 Introduction, how to define a unit impulse for functions?
06:40 The Delta (Dirac) distribution as a limit of a sequence of Gaussians
12:50 Remark (not important for proof): Delta as an element of the "dual space" of a space of functions
18:10 Delta comb and its Fourier transform
25:00 Visual illustration for why the Fourier transform of the comb is a comb with reciprocal distances
29:25 Sampling as multiplication with a comb in the spatial domain, the Fourier transform of the sampled function
34:20 Nyquist limit explained: aliasing-free means no overlap of the copies of the frequency band