I have to compute the FFT of sparse binary images - where pixel values are either zero or one, but mostly zero. I'm currently using FFTW under MinGW but I'd like to know if a faster implementation (for this particular type of images) exists.
check this golden reference... S. Mallat, A wavelet tour of signal processing : the sparse way. Academic Press, 2009.
Have a look at:
Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price: Nearly optimal sparse fourier transform. STOC 2012: 563-578
Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price: Simple and practical algorithm for sparse Fourier transform. SODA 2012: 1183-1194
I don't know if it considers binary data, there may be further optimizations.
check this golden reference... S. Mallat, A wavelet tour of signal processing : the sparse way. Academic Press, 2009.
Did you look at MATLAB? If i understand your question right, MATLAB is solution. An algorithm is not needed also, there is ready functions in MATLAB, also fft function. If you look at the Help Menu, it will be useful for you.
From the following link, you can access to paper and code on sparse FFT.
http://groups.csail.mit.edu/netmit/sFFT/index.html
Dear Sebastiano, Matthias, Ziad, and Yuji. Thank you so much for those references. I have a busy day today, but I will look into them as soon as I can.
Dear Sevda, thank you for your suggestion. I do often use Octave (rather than Matlab) for algorithm design and testing, but for this particular application I would like to achieve near-realtime performance, and I have to perform several 3D FFT's per frame, so I'm developing in C/C++. The FFTW libraries are quite fast, already (Octave uses those same libraries for fft), but given the characteristics of my data I'm thinking an ad-hoc algorithm could work better than a generic FFT.
My initial intuition was that any gains you might see would be relatively modest. On the first of your logN interations, the binary nature of the data lets you replace the multiplications with simple selection of the twiddle factors. The set of twiddle factors is closed under multiplication, so products of individual twiddle factors can be reduced to index arithmetic. But once you start adding non-zero terms together, you can't do this any more (unless you create a really big table). Whether an approach like that would be worth the trouble probably depends on just how sparse your data are.
They have studied that in MIT for long, here are latest publications. http://groups.csail.mit.edu/netmit/sFFT/paper.html
Yeah, as Carlos Angulo specified, recently there was an article published in IEEE Spectrum referring to MIT's new invention of FFT on record breaking processing speed. You could start from there.
- Badges
- Science topic
- Similar topics
- Engineering
- Electrical Engineering
- Signal Processing
- Image Processing