Re: [Audacity-quality] Computation of spectrograms (was: Spectrogram Window Size)

[Thor A. <ta...@to...>]

On Thu, May 05, 2011 at 04:48:10AM +0100, Gale Andrews wrote:
> From Martyn Shaw <mar...@gm...> 

[...]

> > Just 3, the ones that have been proposed and tested before, as in:
> > 
> > --- src/prefs/SpectrumPrefs.cpp	(revision 11135)
> > +++ src/prefs/SpectrumPrefs.cpp	(working copy)
> > @@ -47,14 +47,10 @@
> >      mSizeChoices.Add(_("512"));
> >      mSizeChoices.Add(_("1024"));
> >      mSizeChoices.Add(_("2048"));
> > -#ifdef EXPERIMENTAL_FIND_NOTES
> >      mSizeChoices.Add(_("4096"));
> >      mSizeChoices.Add(_("8192"));
> >      mSizeChoices.Add(_("16384"));
> >      mSizeChoices.Add(_("32768 - most narrowband"));
> > -#else
> > -   mSizeChoices.Add(_("4096 - most narrowband"));
> > -#endif //LOGARITHMIC_SPECTRUM
> 
> Thanks, I tried it. The only comment I have is about the performance
> impact. If I have a 5 minute stereo WAV showing in either
> "Spectrogram" mode at 4096 (the current maximum) then switch in Prefs
> to 32768, it takes 10 seconds to display the spectrogram. 

I noticed the same behavior, and upon further investigation I think I
found the problem.

The time it takes to generate the spectrogram depends both on the FFT
window size and on the FFT window- or frame-overlap, figure 4 at
[1] has a good illustration of what I mean. IIUC (please correct me if
I'm wrong), currently Audacity runs ComputeSpectrum for *every* sample
in the signal [*]. So if 'ws' denotes window size and 'n' number of
samples, the complexity becomes (neglecting edge effects):

O(n * ws * log(ws))    (see [2] for FFT complexity)

If we add the implications of a varying overlap we get (according to my
calculations):

O(n/(1-overlap) * log(ws))  (overlap is between 0 and 1)

Which is more optimal. In my experience, an overlap of 90% is more than
enough, and 50% is usually acceptable.

Following this reasoning I've tried to make the overlap variable, but so
far usuccessfully, I'll look at this again when I have more time.
Meanwhile, if someone feels an itch, please have a stab at it.

[...]

[*] I'm basing this on TrackArtist.cpp:1757, WaveClip.cpp:870,
    WaveClip.cpp:919 and WaveClip.cpp:931.

[1] http://cnx.org/content/m0505/latest/#fig3
[2] http://en.wikipedia.org/wiki/Fast_Fourier_transform

-- 
best regards
Thor Andreassen