iTranslated by AI

The content below is an AI-generated translation. This is an experimental feature, and may contain errors. View original article
🎨

Thinking about Image Processing (1) — Fast Fourier Transform

に公開

Objective

When you open an image processing textbook, you often encounter explanations of low-pass filters where images are Fourier transformed to cut high-frequency components. Then, pictures like the following are presented as a visualization of the Fourier transform.

I want to briefly explore what this "Grand Cross"—or whatever that cross of light is—actually represents.

Fast Fourier Transform

Looking at Fast Fourier Transform on Wikipedia:

A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT).

In other words, its true identity is the Discrete Fourier Transform. Let's set aside the "fast" part of the algorithm for a moment and review the Discrete Fourier Transform.

A general definition of the Fourier transform for a 1D continuous function f, with Lebesgue measure \mu, would be something like the following:

\begin{align*} \hat{f}(\xi) = \int_{-\infty}^\infty f(x) \exp (-2\pi i \xi x) d \mu(x) \end{align*}

Taking an appropriate N \in \mathbb{N}, let's set:

\begin{align*} F(\xi) := \hat{f}(\xi / N) = \int_{-\infty}^\infty f(x) \exp \left(-2\pi i \frac{\xi x}{N} \right) d \mu(x) \end{align*}

Next, let f be a function defined discretely on \mathcal{D}_N := \{0, 1, \ldots, N-1 \}. Correspondingly, let's change the measure from the Lebesgue measure to \lambda(x) = \sum_{n=0}^{N-1} \delta_n (x). Here, \delta_n (x) is a Dirac measure with a peak at x = n \in \mathbb{N}. While the measure changes, we will reuse the symbols on the left side:

\begin{align*} F(\xi) &= \int_{-\infty}^\infty f(x) \exp \left(-2\pi i \frac{\xi x}{N} \right) d \lambda(x) \\ &= \sum_{n=0}^{N-1} \int_{-\infty}^\infty f(x) \exp \left(-2\pi i \frac{\xi x}{N} \right) \delta_n (x) dx \\ &= \sum_{n=0}^{N-1} f(n) \exp \left(-2\pi i \frac{n \xi}{N} \right) \tag{1} \end{align*}

I'm not sure if this is the proper way to derive it, but Eq. (1) is the Discrete Fourier Transform. On the other hand, the Inverse Discrete Fourier Transform is:

\begin{align*} f(x) &= \frac{1}{N} \sum_{n=0}^{N-1} F(n) \exp \left(2\pi i \frac{n x}{N} \right) \end{align*}

Naive Implementation of 1D Discrete Fourier Transform

Since we will use them later, let's import the following:

import numpy as np
from PIL import Image

Then, we naively implement the 1D Discrete Fourier Transform from its definition:

def naive_dft(a: np.ndarray):
    N = a.shape[0]
    exps = np.exp(-2*np.pi*1j*np.arange(N)/N)
    return np.array([np.sum(a * exps ** m) for m in range(N)])


def naive_idft(a: np.ndarray):
    N = a.shape[0]
    exps = np.exp(2*np.pi*1j*np.arange(N)/N)
    return np.array([np.sum(a * exps ** m) for m in range(N)]) / N

Let's test it appropriately:

a = np.arange(10, dtype=complex)
print(np.allclose(naive_dft(a), np.fft.fft(a)))
print(np.allclose(naive_idft(a), np.fft.ifft(a)))
print(np.allclose(np.fft.ifft(np.fft.fft(a)), a))
print(np.allclose(naive_idft(naive_dft(a)), a))

True
True
True
True

It seems to be working fine.

Naive Implementation of 2D Discrete Fourier Transform

Thinking along the same lines as the 1D version, and considering the multidimensional version of the standard Fourier transform, the implementation is as follows. It is quite naive and the efficiency seems terrible, but that is not the purpose this time.

def naive_dft2(a: np.ndarray):
    def coeff(a, m, n):
        h, w = a.shape
        exps = [np.exp(-2*np.pi*1j*p*m/h)*np.exp(-2*np.pi*1j*np.arange(w)*n/w)
                for p in range(h)]
        exps = np.array(exps).reshape(a.shape)
        return np.sum(a * exps)
    a_ = np.array([coeff(a, m, n)
                   for m in range(a.shape[0]) for n in range(a.shape[1])])
    return a_.reshape(a.shape)


def naive_idft2(a: np.ndarray):
    def coeff(a, m, n):
        h, w = a.shape
        exps = [np.exp(2*np.pi*1j*p*m/h)*np.exp(2*np.pi*1j*np.arange(w)*n/w)
                for p in range(h)]
        exps = np.array(exps).reshape(a.shape)
        return np.sum(a * exps)
    a_ = np.array([coeff(a, m, n)
                   for m in range(a.shape[0]) for n in range(a.shape[1])])
    return (a_ / np.prod(np.array(a.shape))).reshape(a.shape)

Let's test it appropriately:

b = np.arange(4*5, dtype=complex).reshape(4, 5)
print(np.allclose(naive_dft2(b), np.fft.fft2(b)))
print(np.allclose(naive_idft2(b), np.fft.ifft2(b)))

True
True

It seems to be working fine.

Applications in Image Processing

In image processing textbooks, an API called fftshift is used where the cross of light appears. Based on my research, this seems to be a process that changes the perspective on \mathbb{Z}^2 / [0, 1]^2 (a 2D torus), scrolling so that the origin of the frequency space is positioned at the center of the image. Therefore, I will implement it as follows:

def naive_fftshift(fimg):
    return np.roll(fimg, [v // 2 for v in fimg.shape], [0, 1])

I thought about what to use as an image and found an article: Ukiyoe and Japanese paintings too! The Art Institute of Chicago releases over 50,000 works for free download! Commercial use OK. I decided to use Under the Wave off Kanagawa (Kanagawa oki nami ura), also known as The Great Wave, from the series “Thirty-Six Views of Mount Fuji (Fugaku sanjūrokkei)”.

I have resized the image and converted it to single-channel grayscale so that the calculation time remains manageable even with a naive implementation.

Let's calculate right away:

%%time

img = np.array(im)
fimg = naive_dft2(img)

mag = 15*np.log(np.abs(naive_fftshift(fimg)))
img2 = naive_idft2(fimg)

CPU times: user 4min 9s, sys: 1.56 s, total: 4min 11s
Wall time: 4min 12s

If you overlook the fact that it is surprisingly slow, you will notice that we have obtained the familiar results often seen in textbooks.

The identity of the "cross of light" is essentially:

  1. Scrolling so that the low-frequency components are at the center.
  2. Taking the absolute value of the complex data to make it real numbers.
  3. Taking the logarithm and scaling it appropriately.

That is what it boils down to.

Since most of the data consists of low-frequency components, this leads into the common explanation that cutting the high-frequency components and performing an inverse discrete Fourier transform results in a low-pass filter.

Summary

In terms of content, it is exactly as described in image processing textbooks, so there is nothing particularly new. However, I believe that by implementing the APIs I had been using without much thought myself, what goes on inside has become much clearer.

GitHubで編集を提案

Discussion