# Working around FFT windowing?

I have the following problem, that I ran into recently, when calculating the spectra of data that I obtain from a measurement technique, we are using in our group.

In short what we do in the technique, is record a movie of a fluctuating, nearly circular object and determine the contour in each frame of the movie. We then use the spectrum of these fluctuations to measure physical properties of the object.

I have now refined the algorithm that we use for tracking the object, so that it is more precise and we are able to determine the contours up to much shorter wavelengths or correspondingly up to a much higher number of modes.

The physical theory behind the system predicts that the fluctuation-amplitude at low mode numbers will be much larger than the at high mode numbers - spanning up to 5 orders of magnitude over the now observable range of modes.

With the now much large mode range and the correspondingly huge range of amplitudes in the spectrum, I seem to have run into an artifact caused by the windowing inherent to the FFT that we use to calculate the spectrum. The spectrum above shows seven different, simulated datasets of a static object. The only thing that changes between the datasets is an increasing image SNR of the movie images (red: high SNR; yellow: low SNR). As can be seen the spectra of the different datasets seem to consist of two contributions: 1) windowing-function/kernel with periodic maxima and minima 2) noisy contribution from the increasingly imprecise contour tracking due to the decreasing SNR. This contribution seems to be summed to the window-function and dominates the spectrum in the ranges, where the windowing-function has a minimum (especially for high-SNR datasets).

Now in the figure below you can see the experimental spectra of an object that almost stops fluctuating towards the end of the measurement/movie (blue: spectrum at movie beginning, green: spectrum at end of movie). (Note: the x-axis is now in wave numbers here – proportional to the inverse wavelength) In the blue spectrum we see: 1. We can see that the spectrum is dominated by the fluctuations of the object over the first ~50 modes (e.g. for wavenumber<=0.1e8). 2. After this we see the contribution from the window-function. 3. After this we see that at the position of the first minimum of the window function (1.1e8<=wavenumber<=1.6e8), we are again able to see the actual fluctuations of the object. This is confirmed by the fact, that we are able to distinguish between the two spectra of the initially strong fluctuating object (blue) and the lower fluctuating object at the later time (green) in this range. If we were only to see image noise in this range, then the blue and the green spectrum should overlap in this range.

Furthermore when looking at the autocorrelation functions of each mode I found the following: In the ranges (wavenumber<=0.1e8) and (1.1e8<=wavenumber<=1.6e8) the autocorrelation functions exhibit correlation whereas in the other regions, the time series of the modes are completely decorrelated as would be expected of noise.

So after this lengthy introduction, I have the following questions:

1. Is my assumption that this is related to the window-function justified? If so I don't understand exactly why yet...
2. Furthermore perhaps someone could suggest a means to get around this artifact of the FFT windowing.

I have been reading up on different window-functions, but from what I understand, they all have an even wider main lobe than the rectangular window-function of the FFT. Since I seem to be “running into” the main lobe with my spectrum, I am not sure if a different window-function would help.

Perhaps there is some way of using the fact that I am dealing with circular contours, so that the signal I am processing is not windowed, but intrinsically periodic and "infinite" (as is the FFT)?!

Could low-pass filtering (perhaps with a Butterworth filter) of the signal before performing the FFT help?

Note 1: Clarification of what is being Fourier-tranformed

The object-tracking algorithm yields cartesian coordinates (x_i,y_i), which I transform to polar coordinates (theta_i,r_i) using the center-of-mass as center coordinate. The signal that I FFT is r_i-, e.g. the deviation from the average radius of the contour Thus, in principle, the signal should truly be periodic – which is what I meant by “intrinsically periodic” above. By rectangular window I meant the intrinsic windowing due to the finite input signal to the FFT. I am not using any additional windowing-function at the moment.

Notes 2: Follow-up on effect of Zero-padding on FFT With regards to the scaling behavior of the spectra, I performed the following tests as suggested by Eric Jacobsen. In the plots below I show the same dataset performing the FFT with varying levels of zero-padding. Color coding of plots of the FFT with different zero-paddings: red: no padding, green: +1 zero padding, blue: +4 zero padding, cyan: +6 zero padding data-length: 2048 (for each the same) Plot of the FFT of the contour of a single movie frame Plot of the fluctuations of the spectrum calculated as the variance of the values of each mode:

<|c|^2>_t-<|c|>_t^2

where c is the FFT of the signal. Plots of the two components of the variance of the non-zero-padded transform:

red: <|c|^2>_t, blue: <|c|>_t^2

As can be seen, the contribution due to the window-function is present in both in slightly different intensity and thus is not cancelled out, when calculating the difference.

EDIT: To finish off this topic: I found out that the observed sinc-like pattern in the spectrum was not caused by windowing of the FFT, but rather by the pattern of the pixels that (unfortunately) still show up significantly in the tracked signal. Combined with the interpolation of the pixels, this results in a convolution with a triangular kernel (see linear interpolation and its frequency response; so sinc^2 see here)

In the end, what led me to the realization, was the fact that due to the inverse behavior in Fourier space any large patterns are produced by a small structure in real-space (see also one of my comments), as is the case for the windowing-effect of the FFT.

I marked the answer by Eric Jacobsen as correct, since he suggested, that the structure may also be caused by something very different from the windowing-effect of the FFT.

• The signal you're FFTing is the distance-from-center or -from-perfect-circle around the object in one movie frame (no time involved), yes? So then it is truly periodic and you should not be using any window function whatsoever because the FFT by itself is suited for your problem. I suspect you're already doing that and calling it a rectangular window — just checking. – Kevin Reid Dec 31 '13 at 16:37
• Sorry for the late answer (new years). You are exactly right. The object-tracking algorithm yields cartesian coordinates (x_i,y_i), which I transform to polar coordinates (theta_i,r_i) using the center-of-mass as center coordinate. The signal that I FFT is r_i-<r_i>, e.g. the deviation from the average radius of the contour. – packoman Jan 3 '14 at 8:49
• So, yes, in principle the signal should truly be periodic. And also I don't use any windowing. By rectangular window I meant (as you've correctly suspected) the intrinsic windowing due to the finite input signal to the FFT. – packoman Jan 3 '14 at 9:00

I'm not quite clear about the scaling in your plots, but the sinx/x response due to the FFT length, assuming the data length and the FFT length match (i.e., there is no zero-padding), has a main-lobe width of only two bins. It looks like your plots may be either heavily zero-padded or the sinx/x you're seeing may be due to something else.

The sinx/x response shape appears in a number of unexpected places, like antenna patterns, diffraction, etc., so it's possible that it is due to something other than the FFT. If you keep the size of the FFT constant and change the data length, zero-padding the difference, the sinx/x main lobe due to the rectangular window should widen as the date length shrinks. That would be a way to see whether the sinx/x shape is due to the window or some other effect.

• Hi. Thanks for your suggestions. I have updated my post including some plots of the FFT with varying zero-padding. The windowing function does seem to change with the zero-padding. However I am not sure, whether this windowing is in addition to the window-function of the non-zero-padded FFT as the FFT of the zero-padded versions have minima-values similar to those of the non-zero-padded FFT. Note however, that the size of the FFT is varying slightly, while the data length is kept constant. That was the easiest way, hope its still helpful. Perhaps you still have some ideas? Thanks in advance. – packoman Jan 3 '14 at 12:21
• If I understand correctly you're keeping the data length at 2048 but increasing the length of the FFT? I'm not sure what your notation of +1, +4, +6, etc., means. Keeping the data length the same and adding zeroes to increase the DFT length means that the length of the rectangular window stays constant, you're just interpolating more points into the FT. So, ideally, the frequency-domain characteristics shouldn't change, there'd just be more points in it. – Eric Jacobsen Jan 4 '14 at 20:33
• Yes. Correct. Data length is constant at 2048. +1,+4,+6, etc refers to the zero-padding that I use, e.g. +1: one zero added, +4: 4 zeros added, etc. By adding zeros to the signal I am interpolating and accordingly should change the frequency domain properties, as you say. But as you can see the results are very different regarding the supposed windowing function (e.g. number of observed minima). Can I then take this as clear indication/proof that the minima in the non-padded FFT of the signal are indeed caused by windowing and are not some property of the signal. What is your opinion on this? – packoman Jan 7 '14 at 17:17

If your signal is truly periodic, and you are using no window (= rectangular window), then you need to insure that the fundamental frequency is centered directly in an FFT bin. I assume that the frame rate of your video capture is not syncronized to the fundamental frequency of the objects fluctuation rate. If you are looking for large dynamic range, the ratio of sampling frequency to the fundamental signal frequency needs to be an integer to very high accuracy.

If this is not possible then you can use more advanced techniques. One technique I have used in the past is to use the raw FFT to do a frequency estimation using 3rd-order peak interpolation, and then do a sample-rate conversion on the input signal buffer to pull the fundamental frequency directly into a bin. Then you take the FFT again, and should get good results.

You can also google "sine-wave curve-fit", which is another way to accurately extract the fundamental frequency. One advantage of this technique is that it produces a residual output which is equal to the signal with the fundamental component removed. In that case you might be able to get away with an un-syncronized FFT of the residual since the big main lobe of the fundamental (which is responsible for most of the window leakage) has been removed.

• That is a very interesting point.I had also considered this, but did not know how to check/correct this. Note that, when transforming (x_i,y_i)->(theta_i,r_i) any deviation of the centre from its theoretically correct position would cause a large contribution in the fundamental mode of r_i-<r_i>, which makes this plausible. Two questions: 1) By "sine-wave curve-fit" you mean actual fitting in real-space and subtracting the contribution? 2) Shouldn't the main-lobe be only 2 bins wide for a mismatched situation (see reply by Eric Jacobsen) – packoman Jan 3 '14 at 13:51
• Actually I mis-spoke, the bin frequencies are n*fs/K where K is the fft length and 0 <= n <= K-1. When the frequency is outside of a bin then most bins are non-zero and there is significant energy +/- several bins around the fundamental. If you want to achieve spectral leakage numbers below, say, 100 dB, then you will need to align the input frequency to within 0.001% of the true bin center. A simple 5-line Matlab program will quickly illustrate the accuracy required. – Bob Jan 3 '14 at 15:45
• Regarding the sine-wave curve fit, yes, the algorithm iteratively finds the best match in amplitude, frequency, and phase and subtracts out a theroretically perfect matched sine-wave. It works best if the SNR is reasonably high and the harmonics are not excessively large compared to the fundamental. – Bob Jan 3 '14 at 15:47
• Hi. Sorry for the late answer. I tried your idea of fitting and subtracting the principle sine frequency. Unfortunately that didn't solve the problem. The spectrum remains almost the same, except for the frequency that I substract out. I also tried resampling the signal r_i-<r_i>_i, so that the sampling points are equidistant and coincide with (2*pi/N)*(0...N-1), supposing that the fundamental frequency should already coincide with the FFT window (since the profile is circular in 2*pi). Unfortunately that did not help either. Not sure what to try now. – packoman Jan 8 '14 at 17:10
• Furthermore I played with the FFT of sine-signals in MATLAB to see how a frequency-mismatch affects spectral leakage. What I found is (unsuprisingly) similar reported here: dsp.stackexchange.com/questions/10120/… While I understand that the FFT of the rectangular window gives you the sinc-function (as is the case in diffraction), I fail to see how this could be the cause of the structure I am seeing. – packoman Jan 8 '14 at 17:38