2
$\begingroup$

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?

$\endgroup$
9
  • $\begingroup$ Please edit your question for clarity. What do you mean by "1D image?" Are you talking about a line scan? Normally images are 2D or if you have really fancy sensors, 3D. A 1D data set is usually a time series or similar, more traditional "signal" in the signals and systems sense. $\endgroup$
    – TimWescott
    Mar 11, 2023 at 0:37
  • $\begingroup$ (A) What package are you using? I'm getting magnitudes (after normalization) of [1, 0.707, 0, 0.707, 1, 0.707, 0, 0.707]. (B) irregular samples can have non-intuitive spectra, at least until you've been thumped with them often enough so that they become intuitive. This problem is exacerbated by short samples that don't really get a chance to establish a true pattern. Does your pattern truly repeat after 8 samples, or is this just the first eight samples of some different or more complicated pattern? $\endgroup$
    – TimWescott
    Mar 11, 2023 at 0:45
  • $\begingroup$ By 1-D image, I mean either the #rows or #cols = 1 and the other dimension > 1. This is what I have shown in the example, height of image = 1pixel, width = 8 pixels. $\endgroup$
    – cppcoder
    Mar 11, 2023 at 0:46
  • $\begingroup$ @TimWescott (A) I'm using opencv and CV:Mat type is CV_16U. These are just test pattern to understand how to interpret DFT magnitude. I have real samples, which have multiple repeating patterns of different pitches. When I ran DFT on real sample of 330 pixels, I got non-zero values for lot of K's. Let me see if I can attach the plot later. $\endgroup$
    – cppcoder
    Mar 11, 2023 at 1:00
  • $\begingroup$ This is stack exchange, where we want to see the whole question in the question itself. Please edit your question with this information, to make it complete. $\endgroup$
    – TimWescott
    Mar 11, 2023 at 1:01

1 Answer 1

4
+50
$\begingroup$

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.

animation of first case

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:

animation of 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.

$\endgroup$
5
  • $\begingroup$ Cool animations! :-) $\endgroup$
    – Peter K.
    Mar 11, 2023 at 15:20
  • 2
    $\begingroup$ @PeterK. Thanks, finally cracked the nut on how to do animations properly using Python's Matplotlib.animation library. This opens up a lot of visual opportunities! This animation also runs in "frequency domain" mode such the the IQ plot is in the frequency domain and represents the magnitude and phase of an FIR filter. We'll have to wait patiently for a relevant FIR question. $\endgroup$ Mar 11, 2023 at 15:29
  • 1
    $\begingroup$ @DanBoschen - Amazing explanation. Simply blown away by the detail and effort. If I understand correctly, non-zero magnitude in frequency domain, does not mean there are patterns of that frequency present in the time domain It is simply those frequencies are required to construct the time domain signal. Is that correct? $\endgroup$
    – cppcoder
    Mar 12, 2023 at 21:41
  • $\begingroup$ @cppcoder It is a correct statement that those frequencies are required to reconstruct the time domain signal we are given (a finite duration signal). With consideration to that finite duration signal, if we allowed that signal to be periodically repeated, then those ARE the frequencies present in that periodically repeated signal. For all other cases, the non zero magnitude results can be a result of spectral leakage rather than actual frequencies present (and this would be with consideration to a much longer signal for which we have captured, or windowed, a small portion of). $\endgroup$ Mar 12, 2023 at 22:50
  • $\begingroup$ There are lots of caveats and more than can be explained in the length of that comment, but the referenced post at the end as well as many other posts here on spectral leakage go into this in a lot more detail. I hope that has all helped you! $\endgroup$ Mar 12, 2023 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.