Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 46 ยท Filtering and Edges

The Frequency Domain and the FFT

See an image as a sum of waves: compute the 2D FFT with NumPy, read the spectrum, apply low-pass, high-pass and notch filters, and remove periodic noise.

Until now you have looked at an image as a grid of pixels in space: position (x, y) and brightness. There is a second, equally complete way to describe the same picture, in terms of frequency. A slow, smooth change of brightness across the picture (a clear sky) is a low frequency. A rapid alternation (a fine fence, text, noise, a sharp edge) is a high frequency. The Fourier transform converts an image from the spatial domain into the frequency domain, and its fast algorithm, the FFT, makes it cheap.

Why bother? Because some jobs are far easier in the frequency domain: removing a periodic pattern, blurring or sharpening with huge kernels, finding the fine texture of a fabric, or compressing an image (JPEG works on a related transform). This lesson shows the transform, how to read a spectrum, and three filter families, all with NumPy. It continues from Convolution and Correlation and Blur and Denoise.

An image is a sum of waves

Jean-Baptiste Fourier's idea is that any signal can be written as a sum of sine waves of different frequencies, amplitudes and phases. A 2D image needs 2D waves: stripes at some angle with some spacing. The 2D discrete Fourier transform (DFT) of an N by N image gives N by N complex numbers, one per wave:

  • the magnitude says how strongly that wave is present;
  • the phase says where its stripes are shifted to.

NumPy computes it with np.fft.fft2. By default the zero-frequency term (the average brightness, called the DC component) sits in the corner of the output. np.fft.fftshift moves it to the centre, so low frequencies are near the middle and high frequencies near the edges, which is how spectra are normally drawn.

Python A single stripe pattern has two spikes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Three stripes across the image show up as two spikes at columns +3 and -3 (a real signal always has a mirror-image pair), and nothing else. The round trip proves the frequency view contains exactly the same information as the pixel view.

Reading a spectrum

For natural images the magnitude spectrum has a typical look: a very bright centre and values that fall off rapidly toward the edges, because most of the image energy is in smooth regions. Because the range is enormous, spectra are displayed on a log scale (np.log1p(magnitude)).

Some rules of thumb:

  • A sharp edge in the image spreads energy along a line in the spectrum, perpendicular to the edge direction.
  • Fine texture puts energy far from the centre.
  • A regular pattern (a printed halftone, a scan-line artefact) shows up as isolated bright dots.
  • Rotating the image rotates its spectrum by the same angle.
Python Where does the energy live?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The smooth image keeps essentially all its energy in the innermost ring. The checkerboard spreads energy across rings (its sharp corners need high frequencies, and its regular blocks give isolated peaks). Random noise has energy at every frequency, and the outer rings hold most of it simply because they cover more area. That is why a low-pass filter removes noise but also detail.

Filtering in the frequency domain

The convolution theorem is the reason frequency-domain filtering is so useful: convolution in the spatial domain equals multiplication in the frequency domain. To filter an image you can:

  1. take its FFT,
  2. multiply by a filter mask (1 means keep, 0 means remove, anything in between is partial),
  3. take the inverse FFT.

For a large kernel this is much faster than sliding the kernel over every pixel: the cost is about N^2 log N instead of N^2 k^2. Three standard masks:

Filter Keeps Effect
Low-pass Frequencies near the centre Blurs, removes noise and fine detail
High-pass Frequencies far from the centre Keeps edges and detail, removes smooth regions
Band-pass / notch A ring, or small spots Isolates a texture scale, or removes a periodic pattern

A hard cut-off (a perfect circle mask) causes ringing: ripples around edges. A smooth mask such as a Gaussian low-pass H(d) = exp(-d^2 / (2 D0^2)), where d is the distance from the centre and D0 the cut-off radius, avoids it.

Python Low-pass and high-pass with the FFT

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Gaussian low-pass cuts the error from about 25 to about 15 (the square is blurred a little, so it cannot reach zero), but the ideal (hard-edged) filter does a bit worse because ringing adds new errors. The high-pass of a flat region is close to zero while the pixels at the square's edge have large magnitude, so the high-pass result is an edge map (compare it with the gradient filters in Edge Detection).

Removing periodic noise with a notch filter

Some noise is not random: a scanner or a camera sensor can add a regular stripe pattern. In pixel space the stripes are mixed into the content and hard to remove. In frequency space they are a handful of bright dots, and you can delete exactly those.

Python Notch filter against stripe noise

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Removing about one percent of the spectrum eliminates almost all of the stripe error while barely touching the blob, because the blob lives at low frequencies and the stripes at a single specific high frequency. In a spatial filter you would have to blur the whole image to get rid of them.

Practical points

  • Padding and borders. The FFT treats the image as if it repeats forever, so a bright left edge "wraps around" to the dark right edge. Pad the image (or apply a smooth window such as a Hann window) before filtering to prevent edge artefacts.
  • Colour images. Filter each channel separately, or only the luminance.
  • Size. The FFT is fastest for sizes that factor into small primes (powers of two are ideal); libraries pad to a fast size for you.
  • Phase matters. The magnitude tells you what is present, the phase tells you where. If you swap the phase of two images, the result looks like the image whose phase you kept, so never discard the phase when filtering.
  • Where it is used. Fast large-kernel convolution, image registration (phase correlation), deblurring, texture analysis, JPEG-style compression (the discrete cosine transform is a close relative) and the analysis of sharpness and motion blur.

Tip: For small kernels (3 by 3, 5 by 5) ordinary spatial convolution is faster. Reach for the FFT when the filter is large, or when the problem is naturally described in frequency terms.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which part of an image is represented by high frequencies?

    Rapid changes in brightness need high-frequency waves. Smooth regions need only low frequencies.
  2. 2. What does np.fft.fftshift do to a 2D spectrum?

    By default the DC component sits at index [0, 0]. fftshift swaps quadrants so low frequencies are in the middle.
  3. 3. What is the convolution theorem's practical message?

    Multiplying the FFT of an image by an FFT-domain filter mask and transforming back gives the same result as convolving with the corresponding kernel.
  4. 4. Why is a Gaussian low-pass preferred over an ideal (hard cut-off) low-pass?

    A sharp circular cut-off in frequency creates ripples in space; a smooth mask does not.
  5. 5. A scanned page has a regular stripe pattern. How does it appear in the spectrum, and how do you remove it?

    Periodic patterns concentrate their energy at specific frequencies, so zeroing small regions around those spots removes them.

Summary

  • The 2D FFT rewrites an image as waves; low frequencies carry smooth structure, high frequencies carry edges, texture and noise.
  • Magnitude says how much of each wave is present, phase says where; both are needed to rebuild the image.
  • Spectra are shown shifted (DC in the centre) and on a log scale.
  • Filtering = FFT, multiply by a mask, inverse FFT. Low-pass blurs, high-pass keeps detail, notch masks remove periodic noise.
  • Smooth masks (Gaussian) avoid ringing; padding or windowing avoids wrap-around artefacts.
  • The FFT pays off for large kernels and for patterns that are simple in frequency space.

Next: Edge Detection.