In response to my recent post about genetically selecting cosine waves for image approximation, several reddit commentors said that I should just have taken the Fourier transform, kept the largest 100 coefficients and did the inverse Fourier transform. [I haven’t run the RMS calculation on the result yet, but visually, it looks pretty nice with my test image. More details on that in a later post.]
The Lisp code that I used in that article didn’t actually use Fast Fourier Transforms. To test the commentors’ claims, I needed an FFT library in Lisp. I searched around a bit and found an FFI (Foreign Function Interface) wrapper around the FFTW library. After fiddling with that library and the wrapper for about two hours, I bailed on it and wrote my own Fast Fourier Transform library entirely in Lisp.
More information as well as links to getting the code are here: nklein / Software / CL-FFT.
In typical reddit manner they are wrong. You should’ve done the DCT.
Go look at how jpegs are compressed and you’ll see that you didn’t much information anyways.
I know all about DCTs. A few jobs ago, I did image-processing with a bent toward “what can we do with JPEG images without inverse DCT-ing them”. You’re missing a word in your last sentence there though… was that “you’ll see that you didn’t lose much information anyways” or what?
Anyhow… DCTs have much of the same stricture as DFTs did…. they are much happier with axis-aligned modulations that are at a frequency that’s a power-of-two divided by the image size. For other things, they really spread around the power more than I was hoping my GA would.
Have you done any benchmarks against FFTW? I’d be interested in the results, even with an unoptimized version of CL-FFT.
I never got FFTW working on my Mac. I may play with it some more to try to get a better idea of the speed comparison.
That said, it looks like I lose terribly to Bordeaux-FFT though. It only handles one-dimensional arrays, but I should probably look to it for some guidance about how to make this really sing. For a 1,048,576 sample array, my FFT takes 4.92 seconds while the Bordeaux-FFT library takes 0.72 seconds.
Did you know about http://vintage-digital.com/hefner/software/bordeaux-fft/manual.html ?
No, I didn’t. Another person pointed it out in this thread. I don’t know how I missed it when I was searching Google for FFT and Lisp because it comes up in the top ten hits. All I found before is FFTW bindings. Also, Bordeaux FFT isn’t mentioned on the Cliki, nor is it hosted on common-lisp.net like Bordeaux Threads is.
I will get Bordeaux FFT on the Cliki and on my page. Thanks for the heads up.