Hacker News Reader

Comment by zulko | Hacker News Reader

I knew I was going to have this remark :) Now correct me if I am wrong, but I think the FFT (which computes the discrete Fourier transform) cannot replace the continous fourier transform in my case, because the optimal periods I find are non-integer values. In the first case, the holes are separated by 7.5 pixels. The FFT could only have told me that they are separated by 7 or 8 pixels, which is not precise enough. Same thing for the tempo, a beat corresponds to 7.1 frames of the video, and a FFT would have told me 7.

If someone knows a way to use the FFT to get non-integer periods (apart from oversampling the signal) I'll gladly change the code.

View on HN

The maximum frequency you can detect is limited by your sampling rate, but there's not a limit on the precision with which you can break those frequencies up.

It's controlled by a parameter NFFT -- the PSD will compute (NFFT/2+1) values evenly spaced between 0 and the Nyquist frequency.

So say the frame rate is 15Hz and you compute with NFFT=2048, then PSD[970] contains the amplitude at 7.09Hz.

This was a really cool project by the way!

Thanks, I learned something. I will try it and amend the blog when I have time.

Forgot to say, great post! :)

Also, it's not as widely known as the FFT, but if you know roughly the frequency of interest you can use the Goertzel algorithm to calculate a chosen number of bins around that specific freq and then pick the max of them to find the freq of interest, instead of when using the FFT having to calculate a bunch of bins using a large nFFT in order to get enough freq resolution and then discarding 99% of the results. Going further, compared to the original Goertzel, the Generalized Goertzel algorithm does the same thing but allows you to query non-integer multiples of the fundamental frequency: http://asp.eurasipjournals.com/content/2012/1/56

There are a lot of parametric (as opposed to the nonparametric FFT) methods for tracking frequency, I'm not totally convinced they're applicable to this case, but I think they might be fun to try out. Maybe start here: http://en.wikipedia.org/wiki/Multiple_signal_classification

Reply on news.ycombinator.com