There's a catch though: most FFT methods require power-of-two image sizes, not ideal for image processing. Stretching the image will distort the frequency domain, making the FFT somewhat pointless. Adding borders will add new frequencies making it somewhat pointless again. Affine transform perhaps? Or is there another method that doesn't need POT?
I'm not sure about GPGPU implementations, but for generalized FFT there are algorithms that can operate on multiples of 3, 5, and maybe even 7s or higher (and then there's the completely general but slow-as- all-get-out DFT algorithm that works on any size). Then, you just implement butterflies for all the underlying factors, and composite them (that's why Powers of Two are so popular -- you just have 1 butterfly that you keep reusing). So if you wanted to do 100, for example, it would factorize to 2*2*5*5, so you'd need butterflies for radix-2 and radix-5. 1025 would require 5*5*41, so you'd need a 5 and a 41 (radix-41 would be hard, I'm guessing ;).
If you filter with nearest neighbor, I don't _think_ you add frequencies, technically (as long as you keep the scaling in mind) -- you're just adding gaps to the FFT output. That said, it's been a _long_ time since I took any DSP courses, so I'm very rusty, and might be totally wrong. You're right about borders though, those will break things. If I recall correctly, the way to handle edges is to reflect about the edge (so you get the same pixels, but in reverse)? that's what JPEG does for non-multiples-of-8 sized images, I think (though JPEG uses DCT, a relative of FFT). Hopefully someone more on top of DSP (or even math in general? ;) can set me straight here.
If you're seriously going to want high speed, high quality 2D FFTs, you _might_ want to look at Accelerate.framework, which has optimized 1D and 2D FFT functions (Though they're definitely limited to powers of two -- but reflecting the image in 2 dimensions to the next highest power of two might help you there, if my above fuzzy recollection of edge reflection is accurate)), or even FFTW (http://www.fftw.org) which has multidimensional non-power-of-two DFT support. Perhaps not as fast as GPU with POT dimensions, but the genericness might be worth the tradeoff.
-- [ christopher wright ] [email protected] http://kineme.net/
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ Do not post admin requests to the list. They will be ignored. Quartzcomposer-dev mailing list ([email protected]) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/quartzcomposer-dev/archive%40mail-archive.com This email sent to [email protected]
