Can DFT magnitude be used to identify repeating patterns in an Image?

Question

Given the DFT magnitude vector of an 1-D image, I want to understand if we can calculate the size and pitch of repeating patterns in the image. Is this possible? I took a few test images and calculated DFT magnitude using openCV https://docs.opencv.org/3.4/d8/d01/tutorial_discrete_fourier_transform.html. Then I tried to calculate the repeating pattern size from the DFT magnitude. Here is an example. "1-D Image row" below shows the grayscale values of the 8 pixels in the image.

1-D Image   0   128 0   128 0   128 0   128  
Magnitude   1   0   0   0   1   0   0   0   
k           0   1   2   3   4   -3  -2  -1

Based on few other posts, my understanding of the index (k) in the DFT magnitude vector is as follows: k represents the maximum number of cycles of a pattern of specific size (size= Sample Size in pixels (N)/k), that can exist in the image. For example, for K=4 and N=8, pattern width has to be 8/4 = 2 pixels and there is maximum 4 cycles possible. In the above example, I see 0, 128, 0 pattern of width 2 pixels repeated 3 times and hence K=4 has the strongest magnitude.

K=0 corresponds to DC frequency. The magnitude vector repeats after K=N/2 and hence I marked those indices as -3, -2, -1. I do not use these values presently.

However, the above assumption of k does not hold for another image.

1-D Image   0   0    128 0    128 0    0    0
Magnitude   1   0.94 0   0.94 1   0.94 0    0.94
K           0   1    2   3    4   -3  -2    -1

I see only 0-128-0 pattern repeating twice and no other repeating patterns. But we still have strong magnitude for K=1 and K=3? Why is this?

Can someone explain what K captures and given DFT magnitude can it be used to identify repeating patterns in the image?

Answer 1

Yes, the DFT magnitude can reveal repetition patterns in an image. I provide an intuitive understanding for the results returned by the DFT which will hopefully make the interpretation of the DFT magnitudes clearer with regards to periodicity.

The DFT when given in its common form as follows:

$$X[k] = \sum_{n=0}^{N-1}x[n]e^{-j 2 \pi n k /N} \tag{1} \label{1}$$

Would have the following results for the OP's test waveforms. Since the magnitude is only of interest, what is given below is $|X[k]|$ as returned by the absolute value of the fft function in MATLAB, Octave and Python's scipy.fft:

abs(fft([0, 128, 0, 128, 0, 128, 0, 128]))

> [512, 0, 0, 0, 512, 0, 0, 0]

This matches the OP's intuition that the time domain is repeating 4 times over the duration of the input resulting in a DC offset as indicated by the first bin at $k=0$ and a frequency of 4 cycles/sample as indicated by the value at $k=4$. Due to mathematical equivalence with periodicity in the Fourier Transform (what I refer to as implied periodicity), this is also -4 cycles/sample since as the OP has shown we can count down negatively from the last sample to indicate positive or negative rotations. I'll explain that little bombshell about negative frequencies later but first let's see what the result for the second example is and how we interpret it:

abs(fft([0, 0, 128, 0, 128, 0, 0, 0])

> [256.0000, 181.0193, 0, 181.0193, 256.0000, 181.0193, 0, 181.0]

Unlike the first case which resulted in a minimum solution of $k=0$ as DC and one other frequency bin $k=4$, this one consists of all the frequency bins except $k=2$ and $k=6$.

The intuition on this is gained in first reviewing the inverse DFT, which is the time domain reconstruction given as follows:

$$x[n] = \frac{1}{N}\sum_{n=0}^{N-1}X[k]e^{j 2 \pi n k /N} \tag{2} \label{2}$$

I find a lot of insight from the continuous time Fourier Series Expansion (FSE) and it's reconstruction, where we recall from that theory (thanks to Josepeh Fourier's publication from 1828!) that any continuous time function can be decomposed into a sum of spinning phasors. Yes "spinning phasors"; I recommend to start with that instead of sinusoids if you really want to dive into the weeds of DSP. So instead of picturing sinusoids, and then with that having to convert the nice single spinning phasor with magnitude and phase as $Ke^{j\phi} = K\angle \phi$ into a more complicated expression with a sine and cosine as $\frac{K}{2} \cos(\phi)+ j\frac{K}{2} \sin(\phi)$, just stick with the phasor and picture a bicycle wheel spinning. Then we can easily comprehend the notion of positive and negative frequencies in terms of direction of rotation, and readily understand the equations for the DFT and inverse DFT as written above directly. (And this applies to the intuition that can be obtained with many more operations of time or space and frequency in signal processing). The FSE decomposes the finite duration time domain function (or similarly infinite duration periodic function) into a series of spinning phasors, each with a constant magnitude and starting phase in time. The fundamental frequency is $1/T$ where $T$ is the total length in time of the finite duration or the period for the periodic waveform case), and the only frequencies that exist will be integer multiples of the fundamental frequency (this makes sense as in the case of a periodic waveform extending to infinity, these are the only solutions that will periodically repeat in the summation). The discrete case as we use for the DFT and inverse DFT is the same thing only sampled in time, and sampled in frequency.

With that we see from equation \ref{2} that the time domain reconstruction is a sum of spinning phasors, each with a magnitude and starting phase as given by the complex value $X[k]$ for each $k$, and each spins at a multiple of the fundamental frequency as $k \omega_o$ where $\omega_o=2 \pi n/N$. Note that the sum of spinning phasors on the complex plane in the time domain is accomplished by placing each phasor on the end of the previous in the sum, with the end point as the total summation at any given point in time.

Here is a animation as a continuous time interpretation of the Discrete Fourier Transform demonstrating the result of the OP's first case, which resulted in a time domain reconstruction given by just two phasors each with magnitude $512/N = 512/8 = 64$ as $64 + 64e^{j4\omega_o}$, where I use $\omega_o = 2\pi n/N$ to represent the fundamental frequency.

I note that the frequency domain magnitude shown has been scaled by $\frac{1}{N}$ to represent the magnitude of the phasors for the time domain reconstruction (as given by equation \ref{2}). So in this graphic we see the "spinning phasors" in the IQ Phasor diagram, where the DC component is fixed with time, as DC, so does not spin, and then the one rotating is spinning at four times the rate of the fundamental frequency. The fundamental frequency as well as all the other components has a magnitude of 0 in this case. The magnitude and phase of this complex result is shown in the time domain on the left hand side, consistent with the distance from the end point of the sum of the two phasors at any point in time.

With that here is the same plot using the OP's second case:

Note here in the time domain, at the discrete sample times used, the waveform is always zero except at $n=2$ and $n=4$. However in order to represent this as "spinning phasors" using the recipe as stated (a fundamental frequency at the inverse of the total time duration, which here would be $1/N$ cycles/sample, and only integer multiples of that frequency), several frequency components are required such that the total sum will result in the time domain samples.

So with that understanding, and to answer the OP's question, note the comparison of the OP's two waveforms when each is continued periodically in time:

[0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, 0, 128, ...]

[0, 0, 128, 0, 128, 0, 0, 0, 0, 0, 128, 0, 128, 0, 0, 0, ...]

The first pattern repeats without variation while in the second case there is repetition and skips, which results in many more frequency components. Those frequency components are the discrete frequencies (as the rate of rotation of each spinning phasor) that represent the time domain waveform as given, at those sample locations, with their respective repetition rates.

This and further details of the DFT and its interpretations is exampled in more detail at this post.