Real Fast Fourier Transform (FFT) in Qt



  • After looking for a Qt-based library doing Fourier transforms for a while, I decided to create one myself. This is not a "question", but rather a discussion for people searching for FFT in Qt in the future.

    The library is a little "big in size", but this is a trade-off for increased compile-time optimization (faster execution time). The library is based on FFTReal (developed by Laurent de Soras). The library as is (currently) only supports real calculations (no complex numbers), which makes it optimal for most sound and image processors. The library is open source and there are a number of pre-compiled versions and installers available. The aim of this library is to provide a easy-to-use interface, especially for people not that familiar with FFT or Fourier series in general.

    Here are some details on the library:

    Name: QRealFourier

    Current version: 0.2.0

    Platform: Windows, Mac, Linux and any platform supported by Qt (only tested MinGW on Windows, but VS should work).

    License: LGPLv3

    SourceForge: "http://sourceforge.net/projects/qrealfourier":http://sourceforge.net/projects/qrealfourier

    GitHub: "http://github.com/visore/QRealFourier":http://github.com/visore/QRealFourier (main Git repository)

    Email: qrealfourier <at> visore.org

    Project: Part of the Visore project ("http://www.visore.org":http://www.visore.org)



  • Wow,
    Great class, I had to develop my own FFT on pure C++ for my thesis project. But this looks good.

    I'll check this with a vibration data analysis on bearings.

    BR,



  • Could I make a center channel extractor with this class or something similar?
    I'd like to make it with Qt.



  • You can make whatever you want with it. It's under the LGPL license.



  • [quote author="goocreations" date="1403847264"]You can make whatever you want with it. It's under the LGPL license.[/quote]
    Yeah, I know it, but do you know how can I make the Center Channel Extractor with the class (or something similar)?



  • Do you refer to extracting frequencies that are common in both the left and right channels? If so, I have not done this previously. I would start by searching on Google for academic articles that explain how to do this. Or add "lecture slides" to your search, this often gives good results. Alternativley, you can ask a question on "http://dsp.stackexchange.com/":http://dsp.stackexchange.com/ I think that you will have more luck there than on the Qt forums.



  • I am getting a segmentation fault, when I try to create a QRealFourier object.

    I have downloaded this library
    http://sourceforge.net/projects/qrealfourier/files/Version 0.3.0/Libraries/qrealfourier-0.3.0-windows-32bit-mingw.zip

    and linked the dll to my project file with
    @LIBS += -L$$PWD/lib/ -llibqrealfourier@

    When I try to cerate a Transformer object like
    @QFourierTransformer transformer;@

    the debugger throws a segmentation fault in the line, the object should have been created.

    Can anybody tell me what I am missing?



  • I am getting a segmentation fault, when I try to create a QRealFourier object.

    I have downloaded this library
    http://sourceforge.net/projects/qrealfourier/files/Version 0.3.0/Libraries/qrealfourier-0.3.0-windows-32bit-mingw.zip

    and linked the dll to my project file with
    @LIBS += -L$$PWD/lib/ -llibqrealfourier@

    When I try to cerate a Transformer object like
    @QFourierTransformer transformer;@

    the debugger throws a segmentation fault in the line, the object should have been created.

    Can anybody tell me what I am missing?



  • Hi there schmauz, sorry for the late reply. I have no idea why you get a segmentation fault. Could you please send me the code snippet where you actually create and use QFourierTransformer. Have you tried the examples I've provided, do they also segfault? And I would suggest checking out the code from github, since I rarely update the files on sourceforge.



  • Hi there schmauz, sorry for the late reply. I have no idea why you get a segmentation fault. Could you please send me the code snippet where you actually create and use QFourierTransformer. Have you tried the examples I've provided, do they also segfault? And I would suggest checking out the code from github, since I rarely update the files on sourceforge.



  • Hi,

    Can you please post the full content instead of just saying QFourierTransformer transformer;?

    That might give clear view to the guys and that will help others to understand better on the usage.



  • Hi,

    Can you please post the full content instead of just saying QFourierTransformer transformer;?

    That might give clear view to the guys and that will help others to understand better on the usage.



  • At goocreations:
    Don't be sorry! It's all good :)

    I have embedded your code from gitHub directly to my project and it works!
    I will get back to the library when I am done testing.

    For now I have another, more mathematical question:

    As far as I can tell, each index in the fft-array represents one frequency, that fits completely into the window I am watching.
    For example 10hz in a 1 second window will result in a sharp imaginary Peak at index (FFT_SIZE/2 + 10).

    What if my window is 1 second long and my frequency is 10.25Hz.
    Is it possible to generate a sharp peak for that, too?
    Sorry that I can't explain it better, but I have attached a picture where I have done a "frequency sweep" from 10Hz to 11Hz.

    "frequency_sweep.png":http://i.imgur.com/85jCQO4.png

    The spectrum is the output of the forwardTransformation, rescaled like this:
    @result = 2 * sqrt(real_part ^ 2 + imaginary_part ^ 2) / FFT_SIZE@

    10Hz and 11Hz give sharp peaks, anything in between is not humanly readable.

    Can I "up the resolution" from 1Hz to, let's say 0.25Hz, so that every spectrum in the picture would show just one peak?
    Or is that mathematically impossible / absurd?

    Again, sorry, I am mighty confused right now and don't exactly know what I am talking about ;)

    My final goal is to look at a window of 1 second and to get sharp peaks for tenths of a Hz...

    At kumararajas:
    Sorry for being so vague, but that is basically all the code that mattered.
    I started a new QWidgets Project, added the one line I have posted to the .pro file, loaded goocreations' headers into the project and tried to create a QFourierTransformer object in the MainWindow constructor.
    I will get back to that as soon as I have figured out a bunch of other stuff ;)



  • At goocreations:
    Don't be sorry! It's all good :)

    I have embedded your code from gitHub directly to my project and it works!
    I will get back to the library when I am done testing.

    For now I have another, more mathematical question:

    As far as I can tell, each index in the fft-array represents one frequency, that fits completely into the window I am watching.
    For example 10hz in a 1 second window will result in a sharp imaginary Peak at index (FFT_SIZE/2 + 10).

    What if my window is 1 second long and my frequency is 10.25Hz.
    Is it possible to generate a sharp peak for that, too?
    Sorry that I can't explain it better, but I have attached a picture where I have done a "frequency sweep" from 10Hz to 11Hz.

    "frequency_sweep.png":http://i.imgur.com/85jCQO4.png

    The spectrum is the output of the forwardTransformation, rescaled like this:
    @result = 2 * sqrt(real_part ^ 2 + imaginary_part ^ 2) / FFT_SIZE@

    10Hz and 11Hz give sharp peaks, anything in between is not humanly readable.

    Can I "up the resolution" from 1Hz to, let's say 0.25Hz, so that every spectrum in the picture would show just one peak?
    Or is that mathematically impossible / absurd?

    Again, sorry, I am mighty confused right now and don't exactly know what I am talking about ;)

    My final goal is to look at a window of 1 second and to get sharp peaks for tenths of a Hz...

    At kumararajas:
    Sorry for being so vague, but that is basically all the code that mattered.
    I started a new QWidgets Project, added the one line I have posted to the .pro file, loaded goocreations' headers into the project and tried to create a QFourierTransformer object in the MainWindow constructor.
    I will get back to that as soon as I have figured out a bunch of other stuff ;)



  • Yeah, you are right, I don't completely understand what you are looking for. As far as I understand, you want to change the resolution of your output frequencies, is that right? You can achieve that by:

    1. Change the resolution of your time-domain inputs. A smaller window of samples will result in a lower resolution in the frequency spectrum. A larger window is equal to higher resolution frequencies. That means you either have to change your input duration of 1s or change the sample rate. If you want to keep 1s at 10 Hz for some reason, I would go with option two.
    2. Ignore the time-domain and simply "resample" the frequencies. There are many ways to do this, just google for "resampling". An easy way to get half the resolution, is to simply average the neighboring frequencies. To increase the resolution, simply add frequencies in between, by taking the average of the left and right frequency. If you upsample using this technique, you will loose information/accuracy and I would rather go with a well-known algorithm that can do that accurately.

    Hope I understood you correctly.



  • Yeah, you are right, I don't completely understand what you are looking for. As far as I understand, you want to change the resolution of your output frequencies, is that right? You can achieve that by:

    1. Change the resolution of your time-domain inputs. A smaller window of samples will result in a lower resolution in the frequency spectrum. A larger window is equal to higher resolution frequencies. That means you either have to change your input duration of 1s or change the sample rate. If you want to keep 1s at 10 Hz for some reason, I would go with option two.
    2. Ignore the time-domain and simply "resample" the frequencies. There are many ways to do this, just google for "resampling". An easy way to get half the resolution, is to simply average the neighboring frequencies. To increase the resolution, simply add frequencies in between, by taking the average of the left and right frequency. If you upsample using this technique, you will loose information/accuracy and I would rather go with a well-known algorithm that can do that accurately.

    Hope I understood you correctly.



  • Thanks for the quick response!

    I think you understood correctly.
    I will look into option 2, but what do you mean by "change the sample rate" in option 1?

    Let's say, I have an analogue signal that contains valuable information between 0 and 2 Hz. The sampling frequency of the a/d converter is 100Hz.

    To transform roughly one second of this signal, I have to set my FFT_SIZE to 128 and the output array will contain level information between 0 and 128Hz. That's because the input and output array have to be the same size... correct?

    If I increase the a/d sampling frequency to 1kHz, my FFT_SIZE would have to be 1024 and the output array will contain level information between 0 and 1024Hz... at least that's what I think.

    I COULD increase my sampling window to 10 seconds, but I don't want to ;)

    What I want is the output array to contain level information between 0 and 2Hz divided by FFT_SIZE... so maybe resampling is the way to go... I will google the s*** out of that!



  • Thanks for the quick response!

    I think you understood correctly.
    I will look into option 2, but what do you mean by "change the sample rate" in option 1?

    Let's say, I have an analogue signal that contains valuable information between 0 and 2 Hz. The sampling frequency of the a/d converter is 100Hz.

    To transform roughly one second of this signal, I have to set my FFT_SIZE to 128 and the output array will contain level information between 0 and 128Hz. That's because the input and output array have to be the same size... correct?

    If I increase the a/d sampling frequency to 1kHz, my FFT_SIZE would have to be 1024 and the output array will contain level information between 0 and 1024Hz... at least that's what I think.

    I COULD increase my sampling window to 10 seconds, but I don't want to ;)

    What I want is the output array to contain level information between 0 and 2Hz divided by FFT_SIZE... so maybe resampling is the way to go... I will google the s*** out of that!



  • Ahh, understand. You will need a resampling or interpolation algorithm. An easy way would be to simply use "linear interpolation":http://en.wikipedia.org/wiki/Linear_interpolation and interpolate the frequencies between 0 and 2 Hz. However, this is only an approximation of the frequencies. This is not a problem if you don't need accurate frequencies. However, if you need a good resolution of the frequencies between 0 and 2 Hz, you either need to increase the sample rate or increase the sample window size.

    There are other more accurate approximations besides linear interpolation. You can use higher degree "polynomials":http://en.wikipedia.org/wiki/Polynomial_interpolation, "Fourier polynomials ":http://en.wikipedia.org/wiki/Trigonometric_interpolation, or even an "AR model":http://en.wikipedia.org/wiki/Autoregressive_model. However, you have to use a linear least squares fit to estimate the coefficients of these polynomials/models, which on the other hand requires you to implement more code. Luckley for you, I've already implemented it with Qt classes, here "headers":https://github.com/visore/Visore/tree/master/code/essentials/headers/vimatrix and here "source":https://github.com/visore/Visore/tree/master/code/essentials/sources/vimatrix. You can use the ViMatrix and ViVector classes (mathematical matrices and vectors) and the ViSystemSolver to solve the polynomials as described in the Wikipedia articles. Use the function "solve" to estimate the polynomial coefficients.

    I've published an "conference paper":ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6776913 about a couple of interpolation algorithms on the time-domain of audio signals, but it will work perfectly for your frequency problem as well. I sadly can only give you the IEEExplore link, and because of copyright issues can't give you the pdf "publicly".

    Or as I already said, if the accuracy/resolution is not that important, simply use linear interpolation. Very easy to calculate.



  • Ahh, understand. You will need a resampling or interpolation algorithm. An easy way would be to simply use "linear interpolation":http://en.wikipedia.org/wiki/Linear_interpolation and interpolate the frequencies between 0 and 2 Hz. However, this is only an approximation of the frequencies. This is not a problem if you don't need accurate frequencies. However, if you need a good resolution of the frequencies between 0 and 2 Hz, you either need to increase the sample rate or increase the sample window size.

    There are other more accurate approximations besides linear interpolation. You can use higher degree "polynomials":http://en.wikipedia.org/wiki/Polynomial_interpolation, "Fourier polynomials ":http://en.wikipedia.org/wiki/Trigonometric_interpolation, or even an "AR model":http://en.wikipedia.org/wiki/Autoregressive_model. However, you have to use a linear least squares fit to estimate the coefficients of these polynomials/models, which on the other hand requires you to implement more code. Luckley for you, I've already implemented it with Qt classes, here "headers":https://github.com/visore/Visore/tree/master/code/essentials/headers/vimatrix and here "source":https://github.com/visore/Visore/tree/master/code/essentials/sources/vimatrix. You can use the ViMatrix and ViVector classes (mathematical matrices and vectors) and the ViSystemSolver to solve the polynomials as described in the Wikipedia articles. Use the function "solve" to estimate the polynomial coefficients.

    I've published an "conference paper":ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6776913 about a couple of interpolation algorithms on the time-domain of audio signals, but it will work perfectly for your frequency problem as well. I sadly can only give you the IEEExplore link, and because of copyright issues can't give you the pdf "publicly".

    Or as I already said, if the accuracy/resolution is not that important, simply use linear interpolation. Very easy to calculate.



  • Thanks for the kind support!

    I have done a little research and testing about interpolation and found, that upsampling my signal with cubic splines works pretty well for me!

    Now I have another mathematical question.
    Is it possible, to convolute two non periodic signals by multiplying their FFTs?

    Below I have linked two pictures.
    The first one is the convolution of two sine waves, the second one is the convolution of two gaussian bells.

    The FFT-size is 1024, and the graphs from top to bottom are read:

    1. Signal1
    2. Signal2
    3. FFT1 (from Signal1)
    4. FFT2 (from Signal2)
    5. FFT1 * FFT2
    6. inverse transformation of FFT1*FFT2

    Periodic: http://i.imgur.com/skNcBK1.png
    Non Periodic: http://i.imgur.com/EJYcKTn.png

    As you can see, the sine waves convolute just fine. The gaussian bells however do not.

    So the question remains:
    Is there a way to convolute non periodic signals using your qRealFourier class?

    Thank you,

    schmaunz



  • Thanks for the kind support!

    I have done a little research and testing about interpolation and found, that upsampling my signal with cubic splines works pretty well for me!

    Now I have another mathematical question.
    Is it possible, to convolute two non periodic signals by multiplying their FFTs?

    Below I have linked two pictures.
    The first one is the convolution of two sine waves, the second one is the convolution of two gaussian bells.

    The FFT-size is 1024, and the graphs from top to bottom are read:

    1. Signal1
    2. Signal2
    3. FFT1 (from Signal1)
    4. FFT2 (from Signal2)
    5. FFT1 * FFT2
    6. inverse transformation of FFT1*FFT2

    Periodic: http://i.imgur.com/skNcBK1.png
    Non Periodic: http://i.imgur.com/EJYcKTn.png

    As you can see, the sine waves convolute just fine. The gaussian bells however do not.

    So the question remains:
    Is there a way to convolute non periodic signals using your qRealFourier class?

    Thank you,

    schmaunz



  • I see no reason why convolution should not work for non-periodic functions.

    Are you sure your entire Gaussian bell (both of them) fit into your 1024 sample window? Did you pad your windows with 0?



  • I see no reason why convolution should not work for non-periodic functions.

    Are you sure your entire Gaussian bell (both of them) fit into your 1024 sample window? Did you pad your windows with 0?



  • can i have your email? because i want to ask you about coding FFT in qt creator,thanks a lot


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.