# My fft gives always gives the correct frequency or double the correct frequency

I can safely say that my fft algorithm, implemented with pyfftw, works as intended when a sine wave with a certain frequency is passed.

Now: I want to analyze the gray variations of a video, every circa 5 seconds. I know for a fact that the signal inside the video is "beating" at a frequency of ~2Hz. The first five seconds of the video are returned with a 2.08Hz, which is correct. The second portion should return around 1.89, but 3.77 (the double) is returned instead! In the third part we are looking for 1.81Hz and in that case the algorithm returns the correct number.

We pass on to another video: every single portion of the video should return about 2.10Hz on average, and my algorithm ALWAYS returns the around the double: 4.18Hz.

On another video the correct frequency is always returned for each 5 seconds windows we create. This is my algorithm:

fft(avg_grey)
fps = 25
frames = len(avg_grey) # equal to the of frames in the video, every frame is averaged on gray
video_length = frames/fps
sample_space = 1/frames
outsz = (samples // 2) + 1
inarr = pyfftw.empty_aligned(frames, dtype="float64")
outarr = pyfftw.empty_aligned(outsz, dtype="complex128")
fft_obj = pyfftw.FFTW(inarr, outarr)
avg_grey = avg_grey - np.mean(avg_grey)  # DC removal
inarr[:] = avg_grey
fft_obj()

amplitudes = np.sqrt((outarr.real ** 2) + (outarr.imag ** 2)) / outsz
freqs = abs(fftfreq(samples, sample_space/2))[:outsz]/video_length (dividing total beats by video length)


Now: we can't ignore the fact that my FFT algorithm always returns the exact value or its double, and both values are peaking in the FFT graph! Some examples:

This should return 1.31Hz, and it's returning EXACTLY 2.63Hz, while 1.31 it's still imposing in the graph!

Second example:

This is working majestically: infact 5.4Hz is what we are looking for.

Last example, here it's the same pulsating object but the difference is that the first graph represents the first 5 seconds of the video and the correct frequency (around 2Hz), and the second one the seconds from 5 to 10 but with exactly double the frequency, while it's still possible to see a peak where the right frequency is.

I desperately need to understand this, I cannot wrap my head around the fact that it's always the correct value or its double, but it never happens when a sinewave is passed as input, only with my videos. I thought about noise in the video, but why then exactly the double of the frequency? The correct solution is always returned, but sometimes is doubled.

The 'beat' that you are looking for is a periodic signal but NOT a sine wave. So it can be represented as a sum of sine waves: the fundamental and multiples of it (harmonics).

$$x[t] = \sum_{n=0}^{P-1} a_n \cos(n \omega_0 t + \phi_n)$$ where $$\omega_0$$ is the fundamental frequency.

I'm guessing you are looking for the maximum of the spectrum, but there is no specific reason why the fundamental, $$a_0$$, should have the highest energy. In fact, for many signals that's not the case and there are cases where the fundamental is zero.

One possible workaround here is to find the dominant spikes and determine whether they are multiples of each other. If yes, go with the lowest or the spacing between the lines. This will cover most but not all possible cases of harmonic structure.

If you need to cover all cases, look into autocorrelation, phase locked loops or delay locked loops. Google "pitch detection" for some pointers.

• Yes, the problem of period estimation often yields estimates that are rational harmonics of the true period.
– Peter K.
Jul 8 at 1:30